數(shù)據(jù)結構課外實驗報告

1、數(shù)據(jù)結構與算法專題實驗實驗報告 班級： 學號： 姓名： 同組： 目錄實驗一 背包問題的求解*2代碼A3代碼B7實驗二 農(nóng)夫過河問題的求解*9實驗四 八皇后問題*16代碼A17代碼B21實驗五 約瑟夫環(huán)問題仿真*24實驗七 二叉排序樹與平衡二叉樹的實現(xiàn)*28代碼A30代碼B38實驗九 學生成績分析*44代碼A45代碼B55實驗總結*68【題目1】實驗一 背包問題的求解【問題描述】假設有一個能裝入總體積為T的背包和n件體積分別為w1,w2,wn的物品，能否從n件物品中挑選若干件恰好裝滿背包，即使w1+w2+wm=T，要求找出所有滿足上述條件的解。 例如：當T=10，各件物品的體積1,8,4,3,5

2、,2時，可找到下列4組解： (1,4,3,2) (1,4,5) (8,2) (3,5,2)?！緦崿F(xiàn)提示】可利用回溯法的設計思想來解決背包問題。首先，將物品排成一列，然后，順序選取物品裝入背包，若已選取第i件物品后未滿，則繼續(xù)選取第i+1件，若該件物品“太大”不能裝入，則棄之，繼續(xù)選取下一件，直至背包裝滿為止。如果在剩余的物品中找不到合適的物品以填滿背包，則說明“剛剛”裝入的物品“不合適”，應將它取出“棄之一邊”，繼續(xù)再從“它之后”的物品中選取，如此重復，直到求得滿足條件的解，或者無解。由于回溯求解的規(guī)則是“后進先出”，自然要用到“?！薄＿M一步考慮：如果每件物品都有體積和價值，背包又有大小限制，

3、求解背包中存放物品總價值最大的問題解-最優(yōu)解或近似最優(yōu)解。【代碼及結果】#include<iostream>#include<stdio.h>#include<stdlib.h>#define MAXSIZE 20using namespace std;int sum=0;int flag=0;template<class T>class Sqstackprivate:T *base;int top;int stacksize;public:Sqstack(int m);Sqstack()delete base;top=0;stacksize=0

4、;void push(int x); T pop();void stacktranverse();int stackempty();template<class T>Sqstack<T>:Sqstack(int m)base = new Tm;top = -1;stacksize = m;template<class T>int Sqstack<T>:stackempty()if(top=-1)return 0;elsereturn 1;template<class T>void Sqstack<T>:push(int x

5、)if(top=stacksize-1)cout<<"棧滿"<<endl;top+;basetop=x;template<class T>T Sqstack<T>:pop()int x;if(top=-1)cout<<"不能出棧"<<endl;x=basetop;basetop=NULL;top-;return x;template<class T>void Sqstack<T>:stacktranverse()int m=top;cout<<&q

6、uot;可選擇背包重量分別為："<<endl;while(m>=0)cout<<basem-<<'t'cout<<endl;void bagproblem(int t,int n) int i; int l=1; int wMAXSIZE; Sqstack<int>s1(2000); Sqstack<int>s2(2000); for(i=0;i<n;i+)cin>>wi;for(int k=0;k<n;k+)i=k;sum=0;l=1;while(l)sum=sum

7、+wi;if(sum<t)s1.push(wi);s2.push(i);if(i=n-1)s1.pop();i=s2.pop();sum=sum-wi;elseif(sum=t)s1.push(wi);s2.push(i);s1.stacktranverse();sum=sum-wi;flag=1;s1.pop();i=s2.pop();if(i=n-1)s1.pop();i=s2.pop();sum=sum-wi;elseif(sum>t)sum=sum-wi;if(i=n-1)s1.pop();i=s2.pop();sum=sum-wi;if(i=n-1)int j=s1.st

8、ackempty();if(!j)l=0;elses1.pop();i=s2.pop();sum=sum-wi;int j=s1.stackempty();if(!j)l=0;i+;int main()int t,n;void bagproblem(int t,int n);cout<<"輸入背包總容量n"cin>>t;cout<<"輸入物品個數(shù)n"cin>>n;cout<<"輸入每個物品的重量n" bagproblem(t,n);if(flag=0)cout<<

9、"無解"<<endl;return 0; 【代碼及結果】#include<iostream>using namespace std;#define size 10struct stacks /*棧定義*/int datasize; /*棧大小*/int top;stack;int main() int wsize; int V; /*背包體積 */ int k=0; int i=0; int j=1; int number; /*物品總件數(shù) */ int s=0; cout<<"請輸入可供選擇裝入物品的個數(shù)："<

10、<endl; cin>>number; cout<<"請輸入各件物品的體積："<<endl; for(i=0;i<number;i+) cin>>wi; for(i=0;i<number;i+) s=s+wi; cout<<"總體積："<<s<<endl; cout<<"請輸入背包的總體積："<<endl; cin>>V; if(V<0|V>s) cout<<"背包

11、總體積錯誤！"<<endl; for(i=0;i<number;i+) stack.datai=0; /*棧初始化 */ stack.top=0; while(stack.top!=0|k!=number) while(V>0&&k<=number) if(V>=wk) /*物品體積小于背包體積時，該物品體積入棧*/ stack.datastack.top=k; stack.top+; V-=wk; /*背包體積數(shù)減少*/ k+; /*下一件物品*/ if(V=0) cout<<"第"<<

12、j<<"個符合條件的解"<<endl; for(i=0;i<stack.top;i+) /*棧內(nèi)所有元素出棧*/ cout<<wstack.datai<<" " j+; /*解數(shù)目加一*/ cout<<endl; k=stack.data-stack.top; /*在剩余的物品中找不到合適的物品以填滿背包，退棧*/ stack.datastack.top=0; V+=wk; k+;return 0;【題目】實驗二 農(nóng)夫過河問題的求解【問題描述】 一個農(nóng)夫帶著一只狼、一只羊和一棵白菜，身處河

13、的南岸。他要把這些東西全部運到北岸。他面前只有一條小船，船只能容下他和一件物品，另外只有農(nóng)夫才能撐船。如果農(nóng)夫在場，則狼不能吃羊，羊不能吃白菜，否則狼會吃羊，羊會吃白菜，所以農(nóng)夫不能留下羊和白菜自己離開，也不能留下狼和羊自己離開，而狼不吃白菜。請求出農(nóng)夫將所有的東西運過河的方案?！緦崿F(xiàn)提示】求解這個問題的簡單方法是一步一步進行試探，每一步搜索所有可能的選擇，對前一步合適的選擇后再考慮下一步的各種方案。要模擬農(nóng)夫過河問題，首先需要對問題中的每個角色的位置進行描述?？捎?位二進制數(shù)順序分別表示農(nóng)夫、 狼、白菜和羊的位置。用0表在南岸，1表示在北岸。例如，整數(shù)5 (0101)表示農(nóng)夫和白菜在南岸，而

14、狼和羊在北岸?，F(xiàn)在問題變成：從初始的狀態(tài)二進制0000(全部在河的南岸)出發(fā)，尋找一種全部由安全狀態(tài)構成的狀態(tài)序列，它以二進制1111(全部到達河的北岸)為最終目標?？偁顟B(tài)共16種(0000到1111)，(或者看成16個頂點的有向圖)可采用廣度優(yōu)先或深度優(yōu)先的搜索策略-得到從0000到1111的安全路徑。以廣度優(yōu)先為例：整數(shù)隊列-逐層存放下一步可能的安全狀態(tài)；Visited16數(shù)組標記該狀態(tài)是否已訪問過，若訪問過，則記錄前驅狀態(tài)值-安全路徑。最終的過河方案應用漢字顯示出每一步的兩岸狀態(tài)?！敬a及結果】#include <iostream>#include<stdlib.h&g

15、t;#define UNVISITED 0#define VISITED 1using namespace std;class Graphprivate: 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北

16、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", "人t狼t羊t菜n北t北t北t南nn", "人t狼t羊t菜n北t北t北t北nn" ; int numV

17、ertex,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

18、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;

19、return numVertex; 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; bo

20、ol isEdge(int i,int j) return 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(

21、v);i<G->n();i=G->next(v,i) 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 a

22、4,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<=15)|(j>=0&&j<=7&&i>=8&a

23、mp;&i<=15)&&safeCondition(i)&&safeCondition(j) int a4,b4,copyI=i,copyJ=j; for(int k=3;k>=0;k-) ak=copyI%2; copyI=copyI/2; for(int k=3;k>=0;k-) bk=copyJ%2; copyJ=copyJ/2; int sum=0; for(int k=1;k<4;k+) if(ak!=bk) sum+; if(sum<=1) matrixij=1; void print_path(int s,in

24、t v,int *pre) if(s=v) cout<<statusv; return; print_path(s,prev,pre); cout<<statusv; int* getPre() return pre; ;int main() Graph g(16); g.setMatrix(); g.DFSTraverse(&g); /cout<<"一種安全的過河方案是："<<endl<<endl; g.print_path(0,15,g.getPre(); return 0;【題目】實驗四 八皇后問題

25、【問題描述】設在初始狀態(tài)下在國際象棋的棋盤上沒有任何棋子（這里的棋子指皇后棋子）。然后順序在第1行，第2行第8行上布放棋子。在每一行中共有8個可選擇的位置，但在任一時刻棋盤的合法布局都必須滿足3個限制條件（1）任意兩個棋子不得放在同一行（2）任意兩個棋子不得放在同一列上（3）任意棋子不得放在同一正斜線和反斜線上?！净疽蟆烤帉懬蠼獠⑤敵龃藛栴}的一個合法布局的程序?！緦崿F(xiàn)提示】在第i行布放棋子時，從第1列到第8列逐列考察。當在第i行第j列布放棋子時，需要考察布放棋子后在行方向、列方向、正斜線和反斜線方向上的布局狀態(tài)是否合法，若該棋子布放合法，再遞歸求解在第i+1行布放棋子；若該棋子布放不合法，

26、移去這個棋子，恢復布放該棋子前的狀態(tài)，然后再試探在第i行第j+1列布放棋子?！敬a及結果】#include <iostream>using namespace std;int count=0;int notDanger(int row,int j,int (*chess)8) int i,k,flag1=0,flag2=0,flag3=0,flag4=0,flag5=0; /判斷豎直方向 for(i=0;i<8;i+) if(*(*(chess+i)+j) !=0) flag1=1; break; /判斷左上方 for(i=row,k=j;i>=0&&k

27、>=0;i-,k-) if(*(*(chess+i)+k)!=0) flag2=1; break; /判斷右下方 for(i=row,k=j;i<8&&k<8;i+,k+) if(*(*(chess+i)+j)!=0) flag3=1; break; /判斷右上方 for(i=row,k=j;i>=0&&k<8;i-,k+) if(*(*(chess+i)+k)!=0) flag4=1; break; /判斷左下方 for(i=row,k=j;i<8&&k>=0;i+,k-) if(*(*(chess+i

28、)+k)!=0) flag4=1; break; if(flag1|flag2|flag3|flag4|flag5) return 0; else return 1;void EightQueen(int row,int n,int (*chess)8) int chess288,i,j; for(i=0;i<8;i+) for(j=0;j<8;j+) chess2ij=chessij; if(row=8) cout<<"第 "<<+count<<" 種方案"<<endl; for(i=0;i&

29、lt;8;i+) for(j=0;j<8;j+) cout<<*(*(chess2+i)+j)<<" " cout<<endl; cout<<endl; else for(j=0;j<n;j+) if(notDanger(row,j,chess) for(i=0;i<8;i+) *(*(chess2+row)+i)=0; *(*(chess2+row)+j)=1; EightQueen(row+1,n,chess2 ); int main() int chess88; for(int i=0;i<8;i

30、+) for(int j=0;j<8;j+) chessij=0; EightQueen(0,8,chess); cout<<"總共有 "<<count<<"種方案"<<endl; return 0;【代碼及結果】算法分析 采用回溯法算法，在一定約束條件下探索前進，若遇到阻礙則沿原路回退，需要用棧來保存曾經(jīng)達到的每一個狀態(tài)，棧頂即為回退的第一站。采用八行八列的棋盤，則易知每個皇后占據(jù)一行，則只需考慮他們列所在的序號，從第一個皇后開始，確定一個位置后，在搜索第二個皇后的位置，每前進一步需檢驗是否為安全位

31、置，若滿足，則當前位置進棧，開始搜索下一位置，直到找到問題的解；否則棧頂元素出棧，回溯到上一個皇后，繼續(xù)嘗試下一位置 安全位置的檢驗：r表示行數(shù)，c表示列數(shù)，設置數(shù)組a8則沿左下右上方相對角線的元素r+c為常數(shù)，且有14-0+1=15種,設置數(shù)組b15;沿左上右下方向的元素r-c等于常數(shù),且有7-(-7)+1=15，設置數(shù)組c15 任取位置（r，c）表示某一皇后的位置， ac=1,表示第同一列上有皇后，ac=0,表示第同一列上無皇后 br+c=1,表示同一左下至右上對角線上有皇后 br+c=0,表示同一左下至右上對角線上無皇后cr-c+7=1, ,表示同一左上至右下對角線上有皇后cr-c+7=

32、0, ,表示同一左上至右下對角線上無皇后#include <iostream>#include <stack>using namespace std;int chess88=0;/棋盤/* 定義棧結點，表示一個皇后的位置*/typedef struct Node int row; /* 行*/ int col; /* 列*/ bool isMarked; /* 是否標記*/;/* 進行皇后問題處理 返回找到的答案個數(shù) */int eightqueenSolve() /定義堆棧 stack<Node> stack; /標志，表示同一列及對角線上是否有皇后 in

33、t a8 = 0, b15 = 0, d15 = 0; int r, c, i,j; int scount = 0; /初始化解決方案個數(shù)為零 Node topNode; /初始化棧 for(i = 0; i <8; i+) topNode.row = 0; topNode.col = 7 - i; topNode.isMarked = false; stack.push(topNode); /以行為單位開始回溯 while(!stack.empty() topNode = stack.top();/棧頂元素 r = topNode.row; c = topNode.col; if(to

34、pNode.isMarked=false) / 如果棧頂元素的位置并沒有確立 if(ac | br-c+7 | dr+c) /如果同一列或同一對角線上已有皇后，則退回*/ stack.pop(); else /占據(jù)這個位置，標志此位置 ac = 1; br-c+7 = 1; dr+c = 1; /標記棧頂元素的isMarked 值 topNode.isMarked = true; stack.pop(); stack.push(topNode); chessrc = 1;/標記棋盤對應位置 if(r = 7) / 如果此時已經(jīng)到達最后一行,則表示成功,輸出相關信息 for(i=0;i<8

35、;+i) for(j=0;j<8;+j) if(chessij=1) cout<<"("<<i+1<<","<<j+1<<")" cout<<endl; scount+; / 解決方案數(shù)增 else / 如果此時沒有到達最后一行,則繼續(xù)進棧并初始化 for(i = 0; i < 8; i+) topNode.row = r + 1; topNode.col = 7 - i; topNode.isMarked = false; stack.push(to

36、pNode); else /如果棧頂元素位置已確立,則棧頂元素出棧，初始化標志,繼續(xù)尋找其它的方法 ac = 0; br-c+7 = 0; dr+c = 0; chessrc = 0; stack.pop(); return scount;int main() int scount = 0; scount = eightqueenSolve(); cout<<scount<<"sulotions found."<<endl; return 0;【題目】實驗五 約瑟夫環(huán)問題仿真【問題描述】設編號為1，2，n(n>0)個人按順時針方向圍

37、坐一圈，每人持有一個正整數(shù)密碼。開始時任意給出一個報數(shù)上限m，從第一個人開始順時針方向自1起順序報數(shù)，報到m時停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人起重新自1報數(shù)；如此下去直到所有人全部出列為止。【基本要求】設計一個程序模擬此過程，給出出列人的編號序列。【實現(xiàn)提示】可考慮不帶頭結點的單鏈表結構?！緶y試數(shù)據(jù)】N=7，七個人的密碼依次為3，1，7，2，4，8，4.初始報數(shù)上限值m=20?！敬a及結果】#include<iostream>#include<stdio.h>#include<stdlib.h>using name

38、space std;template<class T>struct NodeT data;T m;Node<T> *next;template<class T>class Slinklistprivate:Node<T> *Head;public:Slinklist();Slinklist();void Createlist(int n);T Delete(int i);int Empty();template<class T>Slinklist<T>:Slinklist()Head= new Node<T>H

39、ead->next = Head;template<class T>Slinklist<T>:Slinklist()Node<T>*p,*q;q=Head;while(q->next!=Head)q = q->next;while(Head!=Head->next)p = Head;Head = Head->next;q->next = Head;delete p;Head = NULL;template<class T>void Slinklist<T>:Createlist(int n)Node

40、<T>*p,*s;p = Head;for(int i=1;i<=n;i+)s = new Node<T>s->data = i;cin>>s->m;s->next = p->next;p->next = s;p = s;template<class T>T Slinklist<T>:Delete(int i)Node<T> *p,*q;T x,y;p = Head;int j = 0;while(j<i-1)p = p->next;j+;q = p->next;p-&

41、gt;next = q->next;x = q->data;y = q->m;delete q;cout<<x<<'t'return y;template<class T>int Slinklist<T>:Empty()if(Head=Head->next)return 0;elsereturn 1;void yuesefuproblem(int m,int n)int i=0;int l=1;int k;Slinklist<int>L;cout<<"請輸入每個人的m值"<<endl;L.Createlist(n);cout<<n<<"個人退出游戲的次序為："<<endl;while(l)k=m%n;if(k=0&&i=0)i=n;elseif (i!=1&&i!=0)i=(