数据结构与算法专题实验实验报告.docx

“数据结构与程序设计”专题实验实验报告课 程：数据结构与算法实验名称：“数据结构与程序设计”专题实验系 别：计算机科学与技术目录实验一：背包问题的求解31.问题描述32.解题思路33.算法设计44.程序源码55.运行结果8实验二：八皇后问题91.问题描述92.设计要求93.解题思路94.算法设计95.程序源码106.运行结果（部分）12实验三：哈夫曼压缩/解压缩算法（编译码器）131.问题描述132.设计要求133.解题思路134.算法设计13（1）压缩文件13（2）解压文件145.程序源码146.运行结果24实验四：全国交通咨询模拟系统271.问题描述272.设计要求273.解题思路274.算法设计27（1）交通网络图的存储结构27（2）最短路径问题（迪杰斯特拉算法）285.程序源码286.运行结果44实验总结48实验一：背包问题的求解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件物品后未满，则继续选取第i+1件，若该件物品“太大”不能装入，则弃之，继续选取下一件，直至背包装满为止。如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入的物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直到求得满足条件的解，或者无解。由于回溯求解的规则是“后进先出”，自然要用到“栈”。进一步考虑：如果每件物品都有体积和价值，背包又有大小限制，求解背包中存放物品总价值最大的问题解-最优解或近似最优解。3.算法设计背包问题的可形式化描述为：给定C0, 0, 0,，要求找出n元0/1向量，使得，而且达到最大。因此0/1背包问题是一个特殊的整数规划问题。设0/1背包问题的最优值为m( i, j )，即背包容量是j，可选择物品为i,i+1,n时0/1背包问题的最优值。由0/1背包问题的最优子结构性质，可以建立计算m( i, j )的递归式如下： maxm( i+1, j ), m( i+1, j-)+ m( i, j )=m(i+1,j) m(n,j)=0 4.程序源码#define maxsize 1024#define null 0#include#include#includetypedef struct int last; int datamaxsize;seqlist; /定义顺序表结构体typedef struct int top; int sum; int datamaxsize;seqstack; /定义栈结构体seqstack *init_seqstack() seqstack *s; s=new seqstack; if(!s) printf(空间不足); return null; else s-top=-1; s-sum=0; return s; /栈初始化int empty_seqstack(seqstack *s) if (s-top=-1) return 1; else return 0; /判断空栈 int push_seqstack(seqlist *l,int i,seqstack *s) /入栈 if(s-top=maxsize-1) return 0; else s-top+; s-datas-top=i; /顺序表中第i 个元素，i 入栈 s-sum=s-sum+l-datai; /栈中sum加和！ return 1; int pop_seqstack(seqlist *l,seqstack *s,int *x) /出栈 if(empty_seqstack(s) return 0; else *x=s-datas-top; s-sum=s-sum-l-datas-datas-top; s-top-; return 1; seqlist *init_seqlist() seqlist *l; int x=1; l=new seqlist; l-last=0; printf(请依次输入个物品的大小，输入0结束。n); scanf(%d,&x); while(x!=0) l-datal-last=x; l-last+; scanf(%d,&x); return l; /创建数组，储存物品体积 void knapsk(int n,seqlist *l) seqstack *s; int flag=1; int i=0; int t; s=init_seqstack(); /初始化栈命名为S while(flag!=0) while(ilast) push_seqstack(l,i,s); if(s-sum=n) printf(可行的解是:); for(t=0;ttop;t+) printf(%d ,l-datas-datat); printf(n); pop_seqstack(l,s,&i); i+; else if(s-sumn) pop_seqstack(l,s,&i); i+; else i+; while(i=l-last+1) flag=pop_seqstack(l,s,&i); i+; if(flag=0) printf(执行完毕); 5.运行结果实验二：八皇后问题1.问题描述设在初始状态下在国际象棋的棋盘上没有任何棋子（这里的棋子指皇后棋子）。然后顺序在第1行，第2行第8行上布放棋子。在每一行中共有8个可选择的位置，但在任一时刻棋盘的合法布局都必须满足3个限制条件（1）任意两个棋子不得放在同一行（2）任意两个棋子不得放在同一列上（3）任意棋子不得放在同一正斜线和反斜线上。2.设计要求编写求解并输出此问题的一个合法布局的程序。3.解题思路在第i行布放棋子时，从第1列到第8列逐列考察。当在第i行第j列布放棋子时，需要考察布放棋子后在行方向、列方向、正斜线和反斜线方向上的布局状态是否合法，若该棋子布放合法，再递归求解在第i+1行布放棋子；若该棋子布放不合法，移去这个棋子，恢复布放该棋子前的状态，然后再试探在第i行第j+1列布放棋子。4.算法设计s1数据初始化。s2从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置（n，m）是否等于0（未被占领）。如果是，摆放第n个皇后，并宣布占领（记得姚横列竖列斜列一起设置），接着进行递归；如果不是，测试下一个位置（n，m+1），但是如果当n8时，便打印出结果。输出函数我使用printf输出，运行形式为：第m种方法为：00000*005.程序源码#includestatic board88;int knock(int i,int j)/放置棋子 int temp_i,temp_j,k; temp_i=i;temp_j=j; for(i=i-1;i=0;i-) if(boardij=1) return 1; for(i=temp_i-1,k=temp_j+1,j=temp_j-1;i=0;i-,j-,k+) if(j=0&boardij=1) return 1; if(k8&boardik=1) return 1; return 0;void chess(int i)/设置棋盘 int j; for(i=i;i8;i+) for(j=0;j8;j+) boardij=0; void display(void)/输出 int i,j; static int n=1; printf(n第%d种n,n+); for(j=0;j8;j+) for(i=0;i8;i+) if(boardij=1) printf(* ); else printf(0 ); printf(n); printf(n);void fun(int i,int j) if(i8) for(j=j;j8;j+) chess(i);if(knock(i,j)=1)continue;boardij=1;fun(i+1,0); elsedisplay();void main()fun(0,0);6.运行结果（部分）实验三：哈夫曼压缩/解压缩算法（编译码器）1.问题描述利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，要求在发送端通过一个编码系统对传输数据预先编码（压缩）；在接收端将传来的数据进行译码（解压缩复原）。试为这样的通信站编写一个哈夫曼编译码系统-哈夫曼压缩/解压缩算法。2.设计要求1）通信内容可以是任意的多媒体文件；2）自己设定字符大小，统计该文件中不同字符的种类（字符集、个数）、出现频率（在该文件中）；3）构建相应的哈夫曼树，并给出个字符的哈夫曼编码；4）对源文件进行哈夫曼压缩编码形成新的压缩后文件（包括哈夫曼树）；5）编写解压缩文件对压缩后文件进行解码还原成源文件。3.解题思路不同源文件形成的压缩文件中应该包含相应的哈夫曼树结构，以便解压缩系统直接译码还原之。参考哈夫曼树一节内容，但要求编写的软件能完整的对任意文件完成压缩/解压缩。4.算法设计（1）压缩文件s1压缩文件时要先对源文件进行统计，统计字符的种类及出现的次数（即权值）。统计完成之后，建立哈弗曼树：每次选取权值最小且无parent的结点作为左右孩子，建成一棵二叉树，且设置新的二叉树的根结点的权值为其左右孩子的权值之和。直至建成含有2*n-1个结点的哈弗曼树。s2编码完成之后，开始对源文件进行压缩。从源文件读一个字符，从叶子结点中找出和此字符相同的字符结点，将其编码写入一个临时字符组codes；当codes的长度大于等于8时，将其前8位转换成字符写入目标文件中；重复1和2此过程，直至读完源文件中的所有字符；若codes最后还有剩余的不足8位的01代码，则将其低位补0至8位，再写入目标文件。（2）解压文件从被压缩的文件中读出FileLength、n的值，以及每个叶子结点的信息：字符、字符对应的编码。从被压缩的文件编码区读出一个字符，将其值转化成二进制形式（不足8位的高位要补0），存入codes中，直至codes的长度不小于所有叶子结点的编码的长度；用for循环查找出第一个和codes的01字符串匹配的叶子结点编码，将该叶子结点的字符写入目标文件，并将codes的字符串前移，前移位数=该叶子结点编码的长度。重复1和2过程，直至写入的字符数与源文件的长度FileLength相同。5.程序源码#include #include #include #include #include struct nodelong weight; /权值unsigned char ch;/字符int parent,lchild,rchild;char code256;/编码的位数最多为256位 int CodeLength;/编码长度hfmnode512;void compress();void uncompress(); /主函数void main()int choice; printf(请选择13：n); printf(1.压缩文件n); printf(2.解压文件n); printf(3.退 出n);scanf(%d,&choice);if(choice=1)compress();else if(choice=2)uncompress(); else if(choice=3)return; else printf(输入错误！);/压缩函数 void compress()int i,j;char infile20,outfile20;FILE *ifp,*ofp; unsigned char c;/long FileLength,filelength=0;int n,m;/叶子数和结点数int s1,s2; /权值最小的两个结点的标号char codes256;long sumlength=0;float rate,speed;int count=0;clock_t start1, start2,finish1,finish2; double duration1,duration2;void encode(struct node *nodep,int n);/编码函数int select(struct node *nodep,int pose);/用于建哈弗曼树中选择权值最小的结点的函数 printf(请输入要压缩的文件名:); scanf(%s,infile); ifp=fopen(infile,rb);if(ifp=NULL)printf(文件名输入错误，文件不存在!n); return;printf(请输入目标文件名:);scanf(%s,outfile);ofp=fopen(outfile,wb);if(ofp=NULL) printf(文件名输入错误，文件不存在!n); return;start1=clock() ;/开始计时1/统计文件中字符的种类以及各类字符的个数/先用字符的ASCII码值代替结点下标FileLength=0; while(!feof(ifp) fread(&c,1,1,ifp); hfmnodec.weight+; FileLength+;FileLength-; /文件中最后一个字符的个数会多统计一次，所以要减一hfmnodec.weight-;/再将ASCII转换为字符存入到结点的ch成员里，同时给双亲、孩子赋初值-1 n=0; for(i=0;i256;i+)if(hfmnodei.weight!=0)hfmnodei.ch=(unsigned char)i; n+;/叶子数 hfmnodei.lchild=hfmnodei.rchild=hfmnodei.parent=-1; m=2*n-1;/哈弗曼树结点总数 j=0; for(i=0;i256;i+)/去掉权值为0的结点 if(hfmnodei.weight!=0) hfmnodej=hfmnodei; j+; for(i=n;im;i+)/初始化根结点hfmnodei.lchild=hfmnodei.rchild=-1;hfmnodei.parent=-1;/建立哈弗曼树 for(i=n;im;i+) s1=select(hfmnode,i-1); hfmnodei.lchild=s1; hfmnodes1.parent=i; s2=select(hfmnode,i-1); hfmnodei.rchild=s2; hfmnodes2.parent=i; hfmnodei.weight=hfmnodes1.weight+hfmnodes2.weight; /编码encode(hfmnode,n); finish1=clock();duration1=(double)(finish1- start1) / CLOCKS_PER_SEC; /*printf( 哈弗曼树编码用时为：%f secondsn, duration1 );*/ printf(编码完成，是否查看编码信息: y or n?n); c=getch(); if(c=y)printf(n); printf(叶子数为%d,结点数为%dn,n,m); for(i=0;in;i+)printf(%d号叶子结点的权值为：%ld,双亲为：%d,左右孩子：%d,编码为：%sn,i,hfmnodei.weight,hfmnodei.parent,hfmnodei.lchild,hfmnodei.code);start2=clock() ;/开始计时2 fseek(ifp,0,SEEK_SET);/将ifp指针移到文件开头位置 fwrite(&FileLength,4,1,ofp);/将FileLength写入目标文件的前4个字节的位置 fseek(ofp,8,SEEK_SET);/再将目标文件指针ofp移到距文件开头8个字节位置 codes0=0;/将编码信息写入目标文件 while(!feof(ifp) fread(&c,1,1,ifp); filelength+; for(i=0;i=8) for(i=0;i8;i+)/将codes的前8位01代码表示的字符存入c if(codesi=1) c=(c1)|1; else c=c0) strcat(codes,00000000); for(i=0;i8;i+) if(codesi=1) c=(c1)|1; else c=c1; fwrite(&c,1,1,ofp); sumlength+; sumlength+=8;printf(编码区总长为：%ld个字节n,sumlength-8); /将sumlength和n的值写入目标文件，为的是方便解压 fseek(ofp,4,SEEK_SET); fwrite(&sumlength,4,1,ofp);/把sumlength写进目标文件的第5-8个字节里 fseek(ofp,sumlength,SEEK_SET); fwrite(&n,4,1,ofp);/把叶子数n写进编码段后面的4个字节的位置/为方便解压，把编码信息存入n后面的位置/存储方式为：n*（字符值（1个字节）+该字符的01编码的位数（1个字节）+编码（字节数不确定，用count来计算总值） for(i=0;in;i+) fwrite(&(hfmnodei.ch),1,1,ofp); c=hfmnodei.CodeLength;/编码最长为256位，因此只需用一个字节存储 fwrite(&c,1,1,ofp); /写入字符的编码 if(hfmnodei.CodeLength%8!=0) for(j=hfmnodei.CodeLength%8;j8;j+)/把编码不足8位的在低位补0,赋值给C，再把C写入 strcat(hfmnodei.code,0); while(hfmnodei.code0!=0)/开始存入编码，每8位二进制数存入一个字节 c=0; for(j=0;j8;j+) if(hfmnodei.codej=1) c=(c1)|1; else c=c1; strcpy(hfmnodei.code,hfmnodei.code+8);/编码前移8位，继续存入编码 count+; /编码占的字节数的总值 fwrite(&c,1,1,ofp); printf(n); finish2=clock(); duration2=(double)(finish2- start2) / CLOCKS_PER_SEC; /*printf( 写入目标文件用时为：%f secondsn, duration2);*/ printf( 压缩用时为：%f secondsn, duration1+duration2); speed=(float)FileLength/(duration1+duration2)/1000; printf(n压缩速率为：%5.2f KB/Sn,speed);printf(n); printf(源文件长度为：%ld个字节n,FileLength);sumlength=sumlength+4+n*2+count; /计算压缩后文件的长度printf(压缩后文件长度为：%ld个字节n,sumlength);rate=(float)sumlength/(float)FileLength;printf(压缩率(百分比)为：%4.2f%n,rate*100); fclose(ifp); fclose(ofp); return;/建立哈弗曼树中用于选择最小权值结点的函数int select(struct node *nodep,int pose) int i;int s1;long min=2147483647;/s初值为long型的最大值for(i=0;i=pose;i+)if(nodepi.parent!=-1)continue;if(nodepi.weightmin)min=nodepi.weight; s1=i;return s1;/返回书签/哈弗曼编码函数void encode(struct node *nodep,int n) /从叶子向根求每个字符的哈弗曼编码int start;int i,f,c;char codes256;codesn-1=0; /编码结束符for(i=0;in;i+) /逐个字符求哈弗曼编码 start=n-1; for(c=i,f=nodepi.parent;f!=-1;c=f,f=nodepf.parent) start-; if(nodepf.lchild=c) codesstart=0; else codesstart=1; strcpy(nodepi.code,&codesstart); nodepi.CodeLength=strlen(nodepi.code); /返回书签/解压函数void uncompress() /解压文件 clock_t start, finish; double duration;FILE *ifp,*ofp; char infile20,outfile20; long FileLength,sumlength,filelength;int n,m; int i,j,k;char buf256,codes256; unsigned char c;int maxlength;float speed; printf(请输入要解压的文件名:); scanf(%s,infile); ifp=fopen(infile,rb);if(ifp=NULL) printf(文件名输入错误，文件不存在!n); return; printf(请输入目标文件名:); scanf(%s,outfile); ofp=fopen(outfile,wb);if(ofp=NULL) printf(文件名输入错误，文件不存在!n); return;start=clock() ;/开始计时 fread(&FileLength,4,1,ifp);/从压缩文件读出FileLength、sumlength fread(&sumlength,4,1,ifp); fseek(ifp,sumlength,SEEK_SET); /利用sumlength读出n的值 fread(&n,4,1,ifp); printf(n解码信息:源文件长度为%d个字节,字符种类n=%dn,FileLength,n); for(i=0;i0) m=hfmnodei.CodeLength/8+1;/m为编码占的字节数 else m=hfmnodei.CodeLength/8; for(j=0;jstrlen(buf);k-) strcat(hfmnodei.code,0); /再把二进制编码存进hfmnode.code中 strcat(hfmnodei.code,buf); hfmnodei.codehfmnodei.CodeLength=0;/去掉编码中多余的0 /找出编码长度的最大值 maxlength=0; for(i=0;imaxlength) maxlength=hfmnodei.CodeLength;/开始写入目标文件 fseek(ifp,8,SEEK_SET); /指针指向编码区，开始解码 filelength=0; codes0=0; buf0=0; while(1) while(strlen(codes)strlen(buf);k-) strcat(codes,0);/把缺掉的0补上 strcat(codes,buf);/codes中此时存的为一串01编码 for(i=0;in;i+) /在codes中查找能使其前weight位和hfmnode.code相同的i值，weight即为codelength if(memcmp(hfmnodei.code,codes,(unsigned int)hfmnodei.CodeLength)=0) break; strcpy(codes,codes+hfmnodei.CodeLength);/更新codes的值 c=hfmnodei.ch; fwrite(&c,1,1,ofp); filelength+; if(filelength=FileLength) break;/写入结束 finish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC; printf( n解压完成，解压用时为：%f secondsn, duration ); fseek(ifp,0,SEEK_SET); FileLength=0; while(!feof(ifp) fread(&c,1,1,ifp); FileLength+;FileLength-; speed=(float)FileLength/duration/1000;/*printf(此文件长度为：%ld个字节n,FileLength);*/printf(n解压速度为：%5.2fKB/Sn,speed); fclose(ifp); fclose(ofp); return;6.运行结果实验四：全国交通咨询模拟系统1.问题描述处于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能地短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。2.设计要求(1)提供对城市信息进行编辑（如添加或删除）的功能。(2)城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。(3)提供两种最优决策：最快到达和最省钱到达。全程只考虑一种交通工具。(4)旅途中耗费的总时间应该包括中转站的等候时间。(5)咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具。输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。3.解题思路(1)对全国城市交通图和列车时刻表及飞机航班表进行编辑，应该提供文件形式输入和键盘输入两种方式。飞机航班表的信息应包括：起始站的出发时间、终点站的到达时间和票价；列车时刻表则需根据交通图给出各个路段的详细信息，例如：对从北京到上海的火车，需给出北京至天津、天津至徐州及徐州至上海各段的出发时间、到达时间及票价等信息。(2)以邻接表作交通图的存储结构，表示边的结构内除含有邻接点的信息外，还应包括交通工具、路程中耗费的时间和花费以及出发和到达的时间等多种属性。(3)*可考虑增加旅途中转次数最少的最优决策。4.算法设计设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所 需时间或所需费用。本设计共分两个部分，一是建立交通网络图的存储结构；二是解决最短路径问题。（1）交通网络图的存储结构邻接矩阵是表示图形中顶点之间相邻关系的矩阵。图的邻接矩阵是定义如下的n阶方阵：设G=（V，E）是一个图，结点集为。G的邻接矩阵（2）最短路径问题（迪杰斯特拉算法）初始化S和D，置空最短路径终点集，置初始的最短路径值；Sv1=TRUE; Dv1=0； /S集初始时只有源点，源点到源点的距离为0；While (S集中顶点数n)开始循环，每次求得v1到某个v顶点的最短路径，并加v到S集中；Sv=TRUE；更新当前最短路径及距离；5.程序源码#include #include #define ERR 0#define OK 1#define Dij_MAXN 33#define VERTEXMAXNUM 31#define STRINGMAXNUM 20#define TRAFFICMAXNUM 10const char CityFile =E:city.txt;/存取的文件地址const char TrainFile =E:train.txt;const char FlightFile =E:flight.txt;typedef short int CityType;typedef struct TrafficNode/交通方式编码char nameSTRINGMAXNUM; /班次int StartTime,StopTime; /起止时间int EndCity; /城市int Cost; /票价 TrafficNodeDat;typedef struct VNodeCityType city;int TrainNum,FlightNum; /标记数组里元素个数TrafficNodeDat TrainTRAFFICMAXNUM; /火车数组成员为结构体，记录了到达城市、起止时间、票价和班次TrafficNodeDat FlightTRAFFICMAXNUM;/飞机数组成员为结构体，记录了到达城市、起止时间、票价和班次 VNodeDat;typedef struct PNodeint City;int TraNo; PNodeDat;VNodeDat AdjListVERTEXMAXNUM