數(shù)據(jù)結(jié)構(gòu)與算法分析專題實(shí)驗(yàn)-西安交大-趙仲孟

1、西安交通大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法課程實(shí)驗(yàn)實(shí)驗(yàn)名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程專題實(shí)驗(yàn)所屬學(xué)院：電信學(xué)院專業(yè)班級：計(jì)算機(jī)32班小組成員：指導(dǎo)老師：趙仲孟教授實(shí)驗(yàn)一 背包問題的求解1問題描述假設(shè)有一個(gè)能裝入總體積為T的背包和n件體積分別為 W1,W2,Wn的物品，能否從n件物品中挑選若干件恰好裝滿背包，即使W1+W2+Wm=T,要求找出所有滿足上述條件的解。例如：當(dāng)T=10,各件物品的體積1,8,4,3,5,2時(shí)，可找到下列4組解:（1,4,3,2）（1,4,5）（8,2）（3,5,2）。2. 實(shí)現(xiàn)提示 可利用回溯法的設(shè)計(jì)思想來解決背包問題。首先，將物品排成一列，然后，順序選 取物品裝入背包，若已選取第 i 件

2、物品后未滿，則繼續(xù)選取第 i+1 件，若該件物品 “太大 ”不 能裝入，則棄之，繼續(xù)選取下一件，直至背包裝滿為止。如果在剩余的物品中找不到合適的物品以填滿背包， 則說明 “剛剛 ”裝入的物品 “不合 適”，應(yīng)將它取出 “棄之一邊 ”，繼續(xù)再從 “它之后 ”的物品中選取，如此重復(fù)，直到求得滿足 條件的解，或者無解。由于回溯求解的規(guī)則是 “后進(jìn)先出 ”，自然要用到 “棧 ”。3. 問題分析1、設(shè)計(jì)基礎(chǔ)后進(jìn)先出，用到棧結(jié)構(gòu)。2、分析設(shè)計(jì)課題的要求，要求編程實(shí)現(xiàn)以下功能：a 從n件物品中挑選若干件恰好裝滿背包b.要求找出所有滿足上述條件的解，例如：當(dāng)T=10,各件物品的體積1, 8, 4,3， 5，2

3、時(shí)，可找到下列4組解：（1，4，3，2）、（ 1 ， 4，5）、（ 8 ，2）、（3，5，2）3，要使物品價(jià)值最高，即p1*x1+p2*x1+.+pi*xi（其1<=i<=n，x取0或1，取1表示選取物品i）取得最大值。在該問題中需要決定 x1 . xn的值。假設(shè)按i = 1，2，n的次序來確定xi的值。如果置x1 = 0,則問題轉(zhuǎn)變?yōu)橄鄬τ谄溆辔锲罚次锲?, 3，.，n），背包容量仍為c的背包問題。若置 x1 = 1，問題就變?yōu)殛P(guān)于最大背包容量為c-w1 的問題?，F(xiàn)設(shè) r=c， c-w1 為剩余的背包容量。在第一次決策之后，剩下的問題便是考慮背包容量為r時(shí)的決策。不管x1是0

4、或是 1, x2 , ., xn 必須是第一次決策之后的一個(gè)最優(yōu)方案。也就是說在此問題中,最優(yōu) 決策序列由最優(yōu)決策子序列組成。這樣就滿足了動(dòng)態(tài)規(guī)劃的程序設(shè)計(jì)條件。4. 問題實(shí)現(xiàn)代碼 1：#include"iostream" using namespace std;class Linkpublic:int m;Link *next;Link（int a=0,Link *b=NULL）m=a;next=b;class LStackprivate:Link *top;int size;int a100;public:LStack(int sz=0) top=NULL;size=0

5、; a0=0;LStack() clear();void clear() while(top!=NULL)Link *temp=top; top=top->next; delete temp;size=0;void push(int it, int b) top=new Link(it,top); asize=b;size+;int pop()int it=top->m;Link * ltemp=top->next; delete top; top=ltemp;size-; return it;int topValue()return top->m;int length

6、() return size;int sum() int s=0;for(int i=0;i<size;i+) s=s+ai;return s;void print()for(int i=0;i<size;i+)cout<<ai<<" "cout<<endl;void panduan(int x1,int n, int x2,LStack *x4) int i,ss=0;for(i=x4->pop()+1;i<n;i+) if(x4->sum()+x2i<=x1) x4->push(i,x2i);

7、if(x4->sum()=x1)x4->print();break;if(x4->length()=1&&x4->topValue()=n-1) return ;else panduan(x1, n,x2,x4);int main()LStack *ll=new LStack(0);int m100;int n,z;cout<<" 輸入物品個(gè)數(shù) "<<endl;cin>>n;cout<<" 輸入物品大小 "<<endl; for(int i=0;i<

8、n;i+) cin>>mi;cout<<" 輸入背包大小 "<<endl; cin>>z;ll->push(-1,0);cout<<" 符合條件的解 "<<endl;panduan(z,n,m,ll);return 0;結(jié)果 1：擔(dān)入物品大I軸入背包大10符臺條件的解14 3 214 5B 23 5 2Process returned 0 <0x®> execut ion time : 12.995 s Fres any key to cvncinue.代

9、碼2:#in clude<iostream># in clude<cstri ng>using n amespace std;struct Bagint V;/背包體積int number; /物品數(shù)量int v20;/物品體積int value20;/ 物品價(jià)值int dp2020;/ 最大價(jià)值bag;int max(i nt a,i nt b)return a>b?a:b;int mai n()cout<<"請輸入背包的容量："<<e ndl;cin> >bag.V;cout<<"請

10、輸入物品的數(shù)量："<<e ndl;cin> >bag. nu mber;cout<<"請輸入每件物品的體積："<<e ndl;for(i nt i=1;i<=bag .nu mber;i+)cin> >bag.vi;cout<<"請輸入每件物品的價(jià)值："<<e ndl;for(i nt i=1;i<=bag .nu mber;i+)cin> >bag.valuei;memset(bag.dp,0,sizeof(bag.dp);dp 中的每

11、一個(gè)元素置零for(i nt i=1;i<=bag .nu mber;i+)for(i nt j=O;j<=bag.V;j+)if(j>=bag.vi)bag.dpij=max(bag.dpi-1j,bag.dpi-1j-bag.vi+bag.valuei);elsebag.dpij=bag.dpi-1j;cout<<"最大價(jià)值："<<bag.dpbag.numberbag.V<<endl;return 0;結(jié)果2:熟悉了堆棧的使用，設(shè)用數(shù)組weight1.N存放物品重量，MaxW表示背包的最大裝載量。每進(jìn)棧一個(gè)物品，就

12、從sum中減去該物品的質(zhì)量，設(shè)i為待選物品序號，若sum-weighti>=0，則該物品可選；若 sum-weighti < 0，則該物品不可選，且若i>n,則需退 棧，若此時(shí)?？眨瑒t說明無解。實(shí)驗(yàn)二二叉排序樹的實(shí)現(xiàn)1. 問題描述分別采用二叉鏈表和順序表作存儲結(jié)構(gòu)，實(shí)現(xiàn)對二叉排序樹的操作。2. 基本要求（選擇其中之一方式實(shí)現(xiàn)）(1) 用二叉鏈表作存儲結(jié)構(gòu)實(shí)現(xiàn)二叉排序樹。(2) 以回車符(h '為輸入結(jié)束標(biāo)志，輸入數(shù)列L,生成一棵二叉排序樹T;(3) 對二叉排序樹 T 作中序遍歷，輸出結(jié)果；(4) 計(jì)算二叉排序樹 T查找成功的平均查找長度，輸出結(jié)果；(5) 輸入元素X,

13、查找二叉排序樹T,若存在含x的結(jié)點(diǎn)，則刪除該結(jié)點(diǎn)，并作中序遍歷(執(zhí)行操作 2)；否則，輸出信息 “無 x”；3. 問題分析 可以再二叉樹建立時(shí)記錄每個(gè)節(jié)點(diǎn)移動(dòng)到正確位置所需要的移動(dòng)步數(shù),再用總的移動(dòng)步數(shù)除以總的節(jié)點(diǎn)數(shù)就是平均查找步數(shù)。4. 算法實(shí)現(xiàn)代碼：#include"iostream"#include"math.h"#include"string.h"#include"stdlib.h"using namespace std;class BSTNodepublic:double it;BSTNode *lc;B

14、STNode *rc;BSTNode()lc=rc=NULL;BSTNode(double a,BSTNode* l=NULL, BSTNode* r=NULL)it=a;lc=l;rc=r;BSTNode()double getele()return it;void setele(double a)it=a;inline BSTNode* getlc()return lc;inline BSTNode* getrc()return rc;inline void setlc(BSTNode* a)lc=a;inline void setrc(BSTNode * a)rc=a;bool isle

15、af()return (lc=NULL&&rc=NULL);class BSTfriend class BSTNode;private:BSTNode *root;int nodecount;int cd;void clearhelp(BSTNode*); bool findhelp(BSTNode*, double ); BSTNode* getmin(BSTNode*); BSTNode*deletemin(BSTNode*); BSTNode* insethelp(BSTNode*, double); BSTNode* removehelp(BSTNode*, doubl

16、e); void printhelp(BSTNode* ,int );public:BST()root=NULL; nodecount=0;cd=0; BST() clearhelp(root);void clear() clearhelp(root);nodecount=0;void inset(double a) root=insethelp(root, a);double remove(double a) if(findhelp(root,a)root=removehelp(root,a);nodecount-;cd-;elsecout<<" 無 "<

17、;<a<<endl;void print()if(root=NULL)cout<<"Tree is empty"<<endl;elseprinthelp(root,0);void chazhaochangdu()int a;a=cd/nodecount; cout<<a<<endl;bool BST:findhelp(BSTNode* root, double a) if(root=NULL)return false;if(a<root->it)return findhelp(root->l

18、c,a);else if(a>root->it)return findhelp(root->rc,a);else if(a=root->it)return true;BSTNode* BST:insethelp(BSTNode* root, double a) if(root=NULL) cd+;nodecount+;return new BSTNode(a,NULL,NULL);if(a<=root->it) cd+;root->setlc(insethelp(root->lc,a);else if(a>root->it) cd+;

19、root->setrc(insethelp(root->rc,a);return root;BSTNode* BST: deletemin(BSTNode* rt) if(rt->lc=NULL) return rt->rc;else rt->setlc(deletemin(rt->lc); return rt;BSTNode* BST: getmin(BSTNode* rt) if(rt->lc=NULL) return rt;else return getmin(rt->lc);BSTNode* BST:removehelp(BSTNode*

20、 rt,double a) if(rt=NULL) return NULL;else if(a<rt->it) rt->setlc(removehelp(rt->lc,a);else if(a>rt->it) rt->setrc(removehelp(rt->rc,a);else BSTNode* temp=rt; if(rt->lc=NULL) rt=rt->rc; delete temp;else if(rt->rc=NULL) rt=rt->lc; delete temp;else BSTNode* temp=get

21、min(rt->rc); rt->it=temp->it; rt->setrc(deletemin(rt->rc); delete temp; return rt;void BST: clearhelp(BSTNode* root) if(root=NULL) return;clearhelp(root->lc); clearhelp(root->rc); delete root;void BST: printhelp(BSTNode* root ,int level) if(root=NULL)return ; printhelp(root->

22、lc,level+1);cout<<root->it<<" " printhelp(root->rc,level+1);int main()BST a; string b; int i;cout<<" 輸入數(shù)據(jù)以 n 結(jié)束 "<<endl; for(;)cin>>b;if(b.at(0)='')break;elsea.inset(atof(b.c_str();a.print();cout<<endl<<" 二叉樹的平均搜索長度 &qu

23、ot; a.chazhaochangdu();for(; ;)cout<<" 輸入要?jiǎng)h除的數(shù) "<<endl; double x;cin>>x; a.remove(x); a.print(); return 0; 結(jié)果：實(shí)驗(yàn)三約瑟夫環(huán)1問題描述設(shè)編號為1, 2,，n(n>0)個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)正整數(shù)密碼。開始時(shí)任意給出一個(gè)報(bào)數(shù)上限m，從第一個(gè)人開始順時(shí)針方向自1起順序報(bào)數(shù)，報(bào)到 m時(shí)停止報(bào)數(shù)，報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)人起重新自1報(bào)數(shù)；如此下去直到所有人全部出列為止2基本要求

24、設(shè)計(jì)一個(gè)程序模擬此過程，給出出列人的編號序列。3、實(shí)現(xiàn)提示：程序運(yùn)行之后，首先要求用戶指定初始報(bào)數(shù)的上限值，此題中循環(huán)鏈表可以不設(shè)頭結(jié)點(diǎn)，而且必須注意空表和“非空表”的界限。如N=20時(shí)，若從第一人開始，設(shè)每個(gè)人的編號依次是1, 2, 3,開始報(bào)數(shù)，報(bào)到 20的人出列。代碼：#i nclude"iostream"using n amespace std;class Linkpublic:int m;Link *n ext;Lin k(i nt a=0,Li nk *b=NULL)m=a;n ext=b;class LListprivate :Link* head;Link*

25、 tail;Link* curr;int cnt;void init()/ 初始化鏈表 curr=tail=head=new Link ; tail->next=head;cnt=0;void removeall()/ 清空鏈表 tail->next=NULL;while(head!=NULL) curr=head; head=head->next; delete curr;public :LList()init();LList()removeall();void sethead(int a)/ 輸入頭結(jié)點(diǎn) head->m=a;cnt+;void print()/ 打印

26、鏈表中的元素Link* i1=curr;Link* i2=curr;while(i1->next!=i2) cout<<i1->m<<" " i1=i1->next;cout<<i1->m<<" "/curr=head;void lclear()/ 清空鏈表 removeall();init();void inset(int a)/ 插入元素 curr->next=new Link(a,curr->next); if(tail=curr) tail=curr->ne

27、xt; cnt+;void append(int a)/ 添加元素tail=tail->next=new Link(a,NULL); tail->next=head;cnt+;int remove()/ 刪除元素 if(curr->next=NULL)cout<<"no element"<<endl;return 0;int a=curr->next->m;Link* it=curr->next; if(curr->next=tail)tail=curr;curr->next=curr->next

28、->next; delete it;cnt-;return a;void prev()/ 移動(dòng)到前一個(gè)元素Link* temp=curr; while(temp->next!=curr)temp=temp->next;curr=temp;void next()/ 移動(dòng)到下一 元素curr=curr->next;int length()/ 鏈表長度return cnt;int currpos()/ 當(dāng)前元素的位置Link* temp=head;int i=0;while(temp!=curr) temp=temp->next;i+;return i;void mov

29、etopos(int pos)/ 移動(dòng)到該位置/Assert (pos>=0)&&)(pos<=cnt),"position out of range"); curr=head;for(int i=0;i<pos;i+)curr=curr->next;int getvalue()/ 獲取下一個(gè)元素的值/Assert(curr->next!=NULL,"no value");return curr->next->m;int getcurr()return curr->m;int shaixua

30、n(LList& a,int b)int c,i;/cout<<b;for( i=1;i+)if(i=b)c=a.getcurr();a.prev();/cout<<"dq"<<a.getcurr(); cout<<a.remove()<<endl; a.next();/ cout<<"qqq"<<a.getcurr();break;/cout<<"changd"<<a.length();a.next();return

31、c;int main()LList a;int b,c;cout<<"輸入首結(jié)點(diǎn)"<<endl;cin> >b;a.sethead(b);cout<<"添加元素結(jié)束輸入0結(jié)束"<<endl;int i=1;for(;)cin> >i;if(i=O)break;a.appe nd(i);cout<<"輸入上限"<<endl;cin> >c;for(;a.le ngth()!=O;)c=shaixua n( a,c);return

32、0;結(jié)果：韓入首結(jié)點(diǎn) 崔加元秦結(jié)克輸人0結(jié)克繭入上限!0實(shí)驗(yàn)四 農(nóng)夫過河問題的求解1. 問題描述一個(gè)農(nóng)夫帶著一只狼、一只羊和一棵白菜，身處河的南岸。他要把這些東西 全部運(yùn)到北岸。他面前只有一條小船，船只能容下他和一件物品，另外只有農(nóng)夫 才能撐船。如果農(nóng)夫在場，則狼不能吃羊，羊不能吃白菜，否則狼會(huì)吃羊，羊會(huì) 吃白菜，所以農(nóng)夫不能留下羊和白菜自己離開，也不能留下狼和羊自己離開，而 狼不吃白菜。請求出農(nóng)夫?qū)⑺械臇|西運(yùn)過河的方案。2. 實(shí)現(xiàn)提示求解這個(gè)問題的簡單方法是一步一步進(jìn)行試探，每一步搜索所有可能的選擇 ，對前一步合適的選擇后再考慮下一步的各種方案。要模擬農(nóng)夫過河問題，首先 需要對問題中的每個(gè)

33、角色的位置進(jìn)行描述?？捎?4 位二進(jìn)制數(shù)順序分別表示農(nóng)夫、 狼、白菜和羊的位置。用 0 表在南岸， 1 表示在北岸。例如，整數(shù) 5 （0101） 表示農(nóng) 夫和白菜在南岸，而狼和羊在北岸?，F(xiàn)在問題變成：從初始的狀態(tài)二進(jìn)制 0000（ 全部在河的南岸 ）出發(fā)，尋找一種 全部由安全狀態(tài)構(gòu)成的狀態(tài)序列，它以二進(jìn)制 1111（全部到達(dá)河的北岸 ）為最終目 標(biāo)。總狀態(tài)共 16 種 （0000 到 1111），（或者看成 16 個(gè)頂點(diǎn)的有向圖 ）可采用廣度優(yōu)先或深度 優(yōu)先的搜索策略 -得到從 0000 到 1111 的安全路徑。以廣度優(yōu)先為例：整數(shù)隊(duì)列-逐層存放下一步可能的安全狀態(tài)；Visited16 數(shù)組

34、標(biāo)記該狀態(tài)是否已訪問過，若訪問過，則記錄前驅(qū)狀態(tài)值-安全路徑。最終的過河方案應(yīng)用漢字顯示出每一步的兩岸狀態(tài)。3. 問題分析（1）、農(nóng)夫必須把狼，羊，白菜全部都載過河，且一次只能載一個(gè)；（2）、要求狼和羊不能單獨(dú)在一起，羊和白菜也不能單獨(dú)在一起，即要么羊單獨(dú)在河的一 邊，要么羊和農(nóng)夫在一起。（3）、用一個(gè)數(shù)組記錄訪問過的節(jié)點(diǎn)的前驅(qū)值。4. 算法實(shí)現(xiàn)代碼：#include <iostream>#include<stdlib.h>#define UNVISITED 0#define VISITED 1using namespace std; class Graphprivat

35、e:string status16="人t狼t羊t菜n南t南t南t南nn"," 人 t狼 t羊t菜 n南 t南 t南 t北 nn","人t狼t羊t菜n南t南t北t南nn"," 人 t狼 t羊t菜 n南 t南 t北 t北 nn"," 人 t狼 t羊t菜 n南 t北 t南 t南 nn"," 人 t狼 t羊t菜 n南 t北 t南 t北 nn"," 人 t狼 t羊t菜 n南 t北 t北 t南 nn"," 人 t狼 t羊t菜 n南 t北 t北 t北 nn&

36、quot;," 人 t狼 t羊t菜 n北 t南 t南 t南 nn"," 人 t狼 t羊t菜 n北 t南 t南 t北 nn"," 人 t狼 t羊t菜 n北 t南 t北 t南 nn"," 人 t狼 t羊t菜 n北 t南 t北 t北 nn"," 人 t狼 t羊t菜 n北 t北 t南 t南 nn"," 人 t狼 t羊t菜 n北 t北 t南 t北 nn"," 人 t狼 t羊t菜 n北 t北 t北 t南 nn"," 人 t狼 t羊t菜 n北 t北 t北 t北

37、 nn"int numVertex,numEdge;int *matrix;int *mark;int flag;int a20;int *pre;public:Graph(int numVert)Init(numVert);Graph()delete mark;for(int i=0;i<numVertex;i+)delete matrixi;delete matrix;void Init(int n)numVertex=n; numEdge=0;mark=new intn; for(int i=0;i<numVertex;i+)marki=UNVISITED;matr

38、ix=(int*) new int* numVertex; for(int i=0;i<numVertex;i+) matrixi=new intnumVertex;for(int i=0;i<numVertex;i+)for(int j=0;j<numVertex;j+) matrixij=0;pre=new int20;int n()return numVertex;int e()return numEdge;int first(int v)for(int i=0;i<numVertex;i+)if(matrixvi!=0)return i;return numVe

39、rtex;int next(int v,int w)for(int i=w+1;i<numVertex;i+) if(matrixvi!=0)return i;return numVertex;void setEdge(int v1,int v2,int wt)Assert(wt>0," 非法邊 ");if(matrixv1v2!=0) numEdge+;matrixv1v2=wt;void delEdge(int v1,int v2)if(matrixv1v2!=0)numEdge-;matrixv1v2=0;bool isEdge(int i,int j)r

40、eturn matrixij!=0;int getMark(int v)return markv;void setMark(int v,int val)markv=val;void Assert(bool val,string s)if(!val)cout<<"Program Failed:"<<s<<endl;exit(-1);void DFS(Graph *G,int v)G->setMark(v,VISITED);for(int i=G->first(v);i<G->n();i=G->next(v,i)

41、if(G->getMark(i)=UNVISITED)prei=v;DFS(G,i);G->setMark(i,VISITED);void DFSTraverse(Graph *G)for(int i=0;i<G->n();i+)G->setMark(i,UNVISITED);for(int i=0;i<G->n();i+)if(G->getMark(i)=UNVISITED)DFS(G,i);bool safeCondition(int v)int a4,copyV=v;for(int i=3;i>=0;i-)ai=copyV%2;copyV=copyV/ 2; if(a0=a2)|(a0=a1&&a1=a3) return true;else return false;void setMatrix()for(int i=0;i<16;i+) for(int j=0;j<16;j+) if(i>=0&&i<=7&&j>=8&&j<=