数据结构课外实验报告

1、数据结构与算法专题实验实验报告 班级： 学号： 姓名： 同组： 目录实验一 背包问题的求解*2代码A3代码B7实验二 农夫过河问题的求解*9实验四 八皇后问题*16代码A17代码B21实验五 约瑟夫环问题仿真*24实验七 二叉排序树与平衡二叉树的实现*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)。【实现提示】可利用回溯法的设计思想来解决背包问题。首先，将物品排成一列，然后，顺序选取物品装入背包，若已选取第i件物品后未满，则继续选取第i+1件，若该件物品“太大”不能装入，则弃之，继续选取下一件，直至背包装满为止。如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入的物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直到求得满足条件的解，或者无解。由于回溯求解的规则是“后进先出”，自然要用到“栈”。进一步考虑：如果每件物品都有体积和价值，背包又有大小限制，

3、求解背包中存放物品总价值最大的问题解-最优解或近似最优解。【代码及结果】#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<<"输入物品个数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; /*物品总件数 */ int s=0; cout<<"请输入可供选择装入物品的个数："<

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; /*背包体积数减少*/ k+; /*下一件物品*/ if(V=0) cout<<"第"<<

12、j<<"个符合条件的解"<<endl; for(i=0;i<stack.top;i+) /*栈内所有元素出栈*/ cout<<wstack.datai<<" " j+; /*解数目加一*/ cout<<endl; k=stack.data-stack.top; /*在剩余的物品中找不到合适的物品以填满背包，退栈*/ stack.datastack.top=0; V+=wk; k+;return 0;【题目】实验二 农夫过河问题的求解【问题描述】 一个农夫带着一只狼、一只羊和一棵白菜，身处河

13、的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请求出农夫将所有的东西运过河的方案。【实现提示】求解这个问题的简单方法是一步一步进行试探，每一步搜索所有可能的选择，对前一步合适的选择后再考虑下一步的各种方案。要模拟农夫过河问题，首先需要对问题中的每个角色的位置进行描述。可用4位二进制数顺序分别表示农夫、 狼、白菜和羊的位置。用0表在南岸，1表示在北岸。例如，整数5 (0101)表示农夫和白菜在南岸，而

14、狼和羊在北岸。现在问题变成：从初始的状态二进制0000(全部在河的南岸)出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸)为最终目标。总状态共16种(0000到1111)，(或者看成16个顶点的有向图)可采用广度优先或深度优先的搜索策略-得到从0000到1111的安全路径。以广度优先为例：整数队列-逐层存放下一步可能的安全状态；Visited16数组标记该状态是否已访问过，若访问过，则记录前驱状态值-安全路径。最终的过河方案应用汉字显示出每一步的两岸状态。【代码及结果】#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、【问题描述】设在初始状态下在国际象棋的棋盘上没有任何棋子（这里的棋子指皇后棋子）。然后顺序在第1行，第2行第8行上布放棋子。在每一行中共有8个可选择的位置，但在任一时刻棋盘的合法布局都必须满足3个限制条件（1）任意两个棋子不得放在同一行（2）任意两个棋子不得放在同一列上（3）任意棋子不得放在同一正斜线和反斜线上。【基本要求】编写求解并输出此问题的一个合法布局的程序。【实现提示】在第i行布放棋子时，从第1列到第8列逐列考察。当在第i行第j列布放棋子时，需要考察布放棋子后在行方向、列方向、正斜线和反斜线方向上的布局状态是否合法，若该棋子布放合法，再递归求解在第i+1行布放棋子；若该棋子布放不合法，

26、移去这个棋子，恢复布放该棋子前的状态，然后再试探在第i行第j+1列布放棋子。【代码及结果】#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;【代码及结果】算法分析 采用回溯法算法，在一定约束条件下探索前进，若遇到阻碍则沿原路回退，需要用栈来保存曾经达到的每一个状态，栈顶即为回退的第一站。采用八行八列的棋盘，则易知每个皇后占据一行，则只需考虑他们列所在的序号，从第一个皇后开始，确定一个位置后，在搜索第二个皇后的位置，每前进一步需检验是否为安全位

31、置，若满足，则当前位置进栈，开始搜索下一位置，直到找到问题的解；否则栈顶元素出栈，回溯到上一个皇后，继续尝试下一位置 安全位置的检验：r表示行数，c表示列数，设置数组a8则沿左下右上方相对角线的元素r+c为常数，且有14-0+1=15种,设置数组b15;沿左上右下方向的元素r-c等于常数,且有7-(-7)+1=15，设置数组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; /* 是否标记*/;/* 进行皇后问题处理 返回找到的答案个数 */int eightqueenSolve() /定义堆栈 stack<Node> stack; /标志，表示同一列及对角线上是否有皇后 in

33、t a8 = 0, b15 = 0, d15 = 0; int r, c, i,j; int scount = 0; /初始化解决方案个数为零 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 /占据这个位置，标志此位置 ac = 1; br-c+7 = 1; dr+c = 1; /标记栈顶元素的isMarked 值 topNode.isMarked = true; stack.pop(); stack.push(topNode); chessrc = 1;/标记棋盘对应位置 if(r = 7) / 如果此时已经到达最后一行,则表示成功,输出相关信息 for(i=0;i<8

35、;+i) for(j=0;j<8;+j) if(chessij=1) cout<<"("<<i+1<<","<<j+1<<")" cout<<endl; scount+; / 解决方案数增 else / 如果此时没有到达最后一行,则继续进栈并初始化 for(i = 0; i < 8; i+) topNode.row = r + 1; topNode.col = 7 - i; topNode.isMarked = false; stack.push(to

36、pNode); else /如果栈顶元素位置已确立,则栈顶元素出栈，初始化标志,继续寻找其它的方法 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;【题目】实验五 约瑟夫环问题仿真【问题描述】设编号为1，2，n(n>0)个人按顺时针方向围

37、坐一圈，每人持有一个正整数密码。开始时任意给出一个报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1报数；如此下去直到所有人全部出列为止。【基本要求】设计一个程序模拟此过程，给出出列人的编号序列。【实现提示】可考虑不带头结点的单链表结构。【测试数据】N=7，七个人的密码依次为3，1，7，2，4，8，4.初始报数上限值m=20。【代码及结果】#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=(