算法实验报告计算机学院.doc

算法实验报告 姓名：邓诗文 班级：CS0906 学号：U200915052 日期：2011.11.81. 实验目的 背包问题：研究应用递归思想，背包算法。应用数据结构基础知识进行实际问题求解与分析。 最优二分检索树：通过编程实现最优二分检索树的构造，熟悉二分检索的思想从而掌握算法。 多段图：通过编程实现多段图的最短路径长度，了解多段图的向前处理和向后处理，熟悉算法。 单源点最短路径：运用Dijkstra 算法实现单源点最短路径，熟悉算法。2 实验分析 单源点最短路径：若按长度递增的次序生成从源点s到其它顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源点的最短路径看作是已生成的源点到其自身的长度为0的路径）。 多段图：对于向前处理法，汇点的COST0，求前一段的每一个结点的COST，对于此段的结点，COST为下段各结点中各个结点的COST（下段结点）W（此结点到下结点权重）的最小值，结果保存在数组中。依次求至源点的COST，即为最优解。向后处理法则是反过来求。 最优二分检索树：构造一棵最优二分检索树不用算法，可以 把0.1对应的作为根，大于他的为左子树，小于他的为右子树，依此类推。背包问题： 令n个物品的重量和价值分别存储于数组w和v中，限制重量为tw.程序用一个n元组（x0,x1,xn-1)表示物品选择的解，其中xi=0表示第i个物品没有选取，而xi=1则表示第i个物品被选取。只要搜索所有的n元组，就可以得到问题的解。每个分量取值为0或1的n元组的个数共为2n个，而每个n元组其实对应了一个长度为n的二进制数，且这些二进制数的取值范围为02n-1.因此，如果把02-1分别转化为相应的二进制数，则可以得到所需要的2n个n元组。3 实验源代码及结果 1.单源点最短路径#include #define N 5 #define MAX 100000#define SWAP(a,b) doint tmp;tmp=a;a=b;b=tmp;while(0)void fun(const int quanN,const int shunxuN,int jieguoN)/Dijkstra算法主体 int i,v,j; for(i=0;iN;i+) v=shunxui; for(j=0;jN;j+) if(jieguov+quanvjjieguoj) jieguoj=jieguov+quanvj; main() int quanNN=0,10,3,20,MAX,/邻接矩阵 10,0,2,5,MAX, 3,2,0,MAX,15, 20,5,MAX,0,11, MAX,MAX,15,11,0; int n,shunxuN,i,j,jieguoN; printf(输入查找点序号:0N:); scanf(%d,&n);/起点 for(i=0;iN;i+) shunxui=i; jieguoi=MAX; jieguon=0; for(i=1;i0)&quannjquannshunxuj-1;j-)/将各结点插入排序 SWAP(shunxuj,shunxuj-1); fun(quan,shunxu,jieguo);/调用 printf(目的地是：);/打印 for(i=0;iN;i+) printf(%-3d,i); printf(n最短路径：); for(i=0;iN;i+) printf(%-3d,jieguoi); 实验结果如下：2. 最优二分检索树#include #include #include #define N 4void OBST(int P, int Q, int RN+1, int n)int WN+1N+1, CN+1N+1;for(int i=0; i=N; i+) / 将初值全部置为0 for(int j=0; j=N; j+) Wij=Cij=Rij=0;for(i=0; i=n-1; i+) / 初始化过程 Wii = Qi; Rii = 0; Cii = 0; Wii+1 = Qi+Qi+1+Pi+1; /含一个节点的最优树 Rii+1 = i+1; Cii+1 = Qi+Qi+1+Pi+1;Wnn = Qn; Rnn = 0; Cnn = 0;for(int m=2; m=n; m+) /找有m个结点的最优树 for(int i=0; i=n-m; i+) int j = i+m; Wij = Wij-1+Pj+Qj; int k = i+1; / 找使得Cik-1+Ckj最小的k,且ik=j int min = Cik-1+Ckj; for(int L=i+2; L=j; L+) int temp = CiL-1+CLj; if(tempmin) min = temp; k = L; Cij = Wij+Cik-1+Ckj; Rij = k; printf(List as Wij,Cij,Rij: n); / 输出W,C,R的表格printf(%7s%-11s%-11s%-11s%-11s%-11s, ,0,1,2,3,4);for(i=0; i=N; i+) printf(n%-3d, i); for(int j=0; j=N; j+) printf( %-3d%-3d%-3d ,Wij, Cij, Rij);/ getTree()函数将获得的根结点按照树的结点编号存储到数组tree中void getTree(int tree, int num, int R5, int i, int j)if(!Rij) return; / 子树为空时返回treenum = Rij; / 以递归的形式将各个根节点存入数组中getTree(tree, num*2, R, i, Rij-1); / 左子树进行递归getTree(tree, num*2+1, R, Rij, j); / 右子树进行递归void main()int PN+1=0, 3, 3, 1, 1; / 使用14号单元int QN+1=2, 3, 1, 1, 1; / 使用04号单元int RN+1N+1; / 保存各个根结点OBST(P, Q, R, N); / 找最优二分检索树int num=(int)pow(2, N); / 计算需要存储该树的最多空间int* tree=(int *)malloc(sizeof(int)*num);for(int i=0; inum; i+) treei = 0; / 将树清空getTree(tree, 1, R, 0, N); / 由Rij获取最优二叉检索树 / 按照树的编码方式存入数组tree中printf(nnThe OBST Tree as Follows:n);for(i=1; inum; i+) / 输出在数组中存储的树的结点 printf(%2d(%d)t, i, treei); if(i%5=0) printf(n);实验结果如下：3. 背包问题#include #define size 20struct stacksint datasize;int top;stack;void main() int wsize;int V; int k=0;? ? int i=0; int j=1; int number; int s=0; printf(n请输入可供选择装入物品的个数：); scanf(%d,&number); printf(n请输入各件物品的体积：); for(i=0;inumber;i+) scanf(%d,&wi); for(i=0;inumber;i+) s=s+wi; printf(n可供选择的物品的总体s=%dn,s); printf(n请输入背包的总体积：); scanf(%d,&V); if(Vs) printf(n输入背包体积错误); printf(n); for(i=0;i0&k=wk) stack.datastack.top=k; stack.top+; V-=wk; k+; if(V=0) printf(第%d个符合条件的解：,j); for(i=0;istack.top;i+) printf(%d ,wstack.datai); j+;printf(n); k=stack.data-stack.top;stack.datastack.top=0; V+=wk;k+;while(!(stack.top=0&k=number);实验结果如下：4. 多段图#includeiostream.h #includestdlib.h #define MAXPOINT 3/定义最大的顶点数目 #define limit 32767 /设置没有路径的权代替无穷大 struct record /没个顶点的数据结构设置为一个数组队列 int number; /顶点号 int flag; /标志是否从队列中被选过如果为1表示选过为0表示未选 int allpath; /从源点到这个点的当前最短距离（权最小） pathMAXPOINT+1; int costMAXPOINT+1MAXPOINT+1; /用来表示图的邻接矩阵 void main() int i,j,temp,front=1,rear=MAXPOINT,N,minnumber; /temp表示在数组队列中的当前下标 front表示队列首 rear表示队列尾 /N 表示待输入的源点号码 minnumber 表示选中的点的号码 int min=32768; /设置一个初始值 for(i=1;i=MAXPOINT;i+) for(j=1;j=MAXPOINT;j+) cout请输入从第i点到第j点的路径长度(权)如果没有路径的话请输入32767 costij; /初始化所有点之间的（权）路径值 /cout请输入源点号N; for(N=MAXPOINT;N=1;N-)/把每一个点轮流地都设置为起点，可以求出任意一对顶点之间的最短路径 for(i=front;i=1) /控制循环次数 for(temp=front;temp=MAXPOINT;temp+) if(pathtemp.allpathmin&pathtemp.flag=0)/选出一个具有最值 /的点 minnumber=pathtemp.number; min=pathtemp.allpath ; min=32768; pathminnumber.flag=1;/把选中的点的标志变量置1表示已经被选过避免选中 for(i=1;i=MAXPOINT;i+)/进行类似广度优先搜索，更新最短路径 if(i!=minnumber)&(pathminnumber.allpath+costminnumberipathi.allpath) pathi.allpath=pathminnumber.allpath+costminnumberi; rear-;/次数减1 rear=MAXPOINT; /恢复数组以便于下一点的循环 for(j=1;j=MAXPOINT;j+) cout第N点到第j点的最短