数据结构与算法分析专题实验-西安交大-赵仲孟

1、西安交通大学数据结构与算法课程实验实验名称：数据结构与算法课程专题实验所属学院：电信学院专业班级：计算机32班小组成员：指导老师：赵仲孟教授实验一 背包问题的求解1问题描述假设有一个能装入总体积为T的背包和n件体积分别为 W1,W2,Wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使W1+W2+Wm=T,要求找出所有满足上述条件的解。例如：当T=10,各件物品的体积1,8,4,3,5,2时，可找到下列4组解:（1,4,3,2）（1,4,5）（8,2）（3,5,2）。2. 实现提示 可利用回溯法的设计思想来解决背包问题。首先，将物品排成一列，然后，顺序选 取物品装入背包，若已选取第 i 件

2、物品后未满，则继续选取第 i+1 件，若该件物品 “太大 ”不 能装入，则弃之，继续选取下一件，直至背包装满为止。如果在剩余的物品中找不到合适的物品以填满背包， 则说明 “刚刚 ”装入的物品 “不合 适”，应将它取出 “弃之一边 ”，继续再从 “它之后 ”的物品中选取，如此重复，直到求得满足 条件的解，或者无解。由于回溯求解的规则是 “后进先出 ”，自然要用到 “栈 ”。3. 问题分析1、设计基础后进先出，用到栈结构。2、分析设计课题的要求，要求编程实现以下功能：a 从n件物品中挑选若干件恰好装满背包b.要求找出所有满足上述条件的解，例如：当T=10,各件物品的体积1, 8, 4,3， 5，2

3、时，可找到下列4组解：（1，4，3，2）、（ 1 ， 4，5）、（ 8 ，2）、（3，5，2）3，要使物品价值最高，即p1*x1+p2*x1+.+pi*xi（其1<=i<=n，x取0或1，取1表示选取物品i）取得最大值。在该问题中需要决定 x1 . xn的值。假设按i = 1，2，n的次序来确定xi的值。如果置x1 = 0,则问题转变为相对于其余物品（即物品2, 3，.，n），背包容量仍为c的背包问题。若置 x1 = 1，问题就变为关于最大背包容量为c-w1 的问题。现设 r=c， c-w1 为剩余的背包容量。在第一次决策之后，剩下的问题便是考虑背包容量为r时的决策。不管x1是0

4、或是 1, x2 , ., xn 必须是第一次决策之后的一个最优方案。也就是说在此问题中,最优 决策序列由最优决策子序列组成。这样就满足了动态规划的程序设计条件。4. 问题实现代码 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<<" 输入物品个数 "<<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;结果 1：擔入物品大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; /物品数量int v20;/物品体积int value20;/ 物品价值int dp2020;/ 最大价值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、输入物品的数量："<<e ndl;cin> >bag. nu mber;cout<<"请输入每件物品的体积："<<e ndl;for(i nt i=1;i<=bag .nu mber;i+)cin> >bag.vi;cout<<"请输入每件物品的价值："<<e ndl;for(i nt i=1;i<=bag .nu mber;i+)cin> >bag.valuei;memset(bag.dp,0,sizeof(bag.dp);dp 中的每

11、一个元素置零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<<"最大价值："<<bag.dpbag.numberbag.V<<endl;return 0;结果2:熟悉了堆栈的使用，设用数组weight1.N存放物品重量，MaxW表示背包的最大装载量。每进栈一个物品，就

12、从sum中减去该物品的质量，设i为待选物品序号，若sum-weighti>=0，则该物品可选；若 sum-weighti < 0，则该物品不可选，且若i>n,则需退 栈，若此时栈空，则说明无解。实验二二叉排序树的实现1. 问题描述分别采用二叉链表和顺序表作存储结构，实现对二叉排序树的操作。2. 基本要求（选择其中之一方式实现）(1) 用二叉链表作存储结构实现二叉排序树。(2) 以回车符(h '为输入结束标志，输入数列L,生成一棵二叉排序树T;(3) 对二叉排序树 T 作中序遍历，输出结果；(4) 计算二叉排序树 T查找成功的平均查找长度，输出结果；(5) 输入元素X,

13、查找二叉排序树T,若存在含x的结点，则删除该结点，并作中序遍历(执行操作 2)；否则，输出信息 “无 x”；3. 问题分析 可以再二叉树建立时记录每个节点移动到正确位置所需要的移动步数,再用总的移动步数除以总的节点数就是平均查找步数。4. 算法实现代码：#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<<" 输入数据以 n 结束 "<<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<<" 输入要删除的数 "<<endl; double x;cin>>x; a.remove(x); a.print(); return 0; 结果：实验三约瑟夫环1问题描述设编号为1, 2,，n(n>0)个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出一个报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到 m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1报数；如此下去直到所有人全部出列为止2基本要求

24、设计一个程序模拟此过程，给出出列人的编号序列。3、实现提示：程序运行之后，首先要求用户指定初始报数的上限值，此题中循环链表可以不设头结点，而且必须注意空表和“非空表”的界限。如N=20时，若从第一人开始，设每个人的编号依次是1, 2, 3,开始报数，报到 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)/ 输入头结点 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()/ 移动到前一个元素Link* temp=curr; while(temp->next!=curr)temp=temp->next;curr=temp;void next()/ 移动到下一 元素curr=curr->next;int length()/ 链表长度return cnt;int currpos()/ 当前元素的位置Link* temp=head;int i=0;while(temp!=curr) temp=temp->next;i+;return i;void mov

29、etopos(int pos)/ 移动到该位置/Assert (pos>=0)&&)(pos<=cnt),"position out of range"); curr=head;for(int i=0;i<pos;i+)curr=curr->next;int getvalue()/ 获取下一个元素的值/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<<"输入首结点"<<endl;cin> >b;a.sethead(b);cout<<"添加元素结束输入0结束"<<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;结果：韩入首结点 崔加元秦结克输人0结克繭入上限!0实验四 农夫过河问题的求解1. 问题描述一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西 全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫 才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会 吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而 狼不吃白菜。请求出农夫将所有的东西运过河的方案。2. 实现提示求解这个问题的简单方法是一步一步进行试探，每一步搜索所有可能的选择 ，对前一步合适的选择后再考虑下一步的各种方案。要模拟农夫过河问题，首先 需要对问题中的每个

33、角色的位置进行描述。可用 4 位二进制数顺序分别表示农夫、 狼、白菜和羊的位置。用 0 表在南岸， 1 表示在北岸。例如，整数 5 （0101） 表示农 夫和白菜在南岸，而狼和羊在北岸。现在问题变成：从初始的状态二进制 0000（ 全部在河的南岸 ）出发，寻找一种 全部由安全状态构成的状态序列，它以二进制 1111（全部到达河的北岸 ）为最终目 标。总状态共 16 种 （0000 到 1111），（或者看成 16 个顶点的有向图 ）可采用广度优先或深度 优先的搜索策略 -得到从 0000 到 1111 的安全路径。以广度优先为例：整数队列-逐层存放下一步可能的安全状态；Visited16 数组

34、标记该状态是否已访问过，若访问过，则记录前驱状态值-安全路径。最终的过河方案应用汉字显示出每一步的两岸状态。3. 问题分析（1）、农夫必须把狼，羊，白菜全部都载过河，且一次只能载一个；（2）、要求狼和羊不能单独在一起，羊和白菜也不能单独在一起，即要么羊单独在河的一 边，要么羊和农夫在一起。（3）、用一个数组记录访问过的节点的前驱值。4. 算法实现代码：#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<=