资源描述：
《数据结构与算法专题实验实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、“数据结构与程序设计”专题实验实验报告课程：数据结构与算法实验名称：“数据结构与程序设计”专题实验系别：计算机科学与技术目录实验一：背包问题的求解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.解题思路27
2、4.算法设计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件物
3、品后未满，则继续选取第i+1件，若该件物品“太大”不能装入，则弃之，继续选取下一件，直至背包装满为止。如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入的物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直到求得满足条件的解，或者无解。由于回溯求解的规则是“后进先出”，自然要用到“栈”。进一步考虑：如果每件物品都有体积和价值，背包又有大小限制，求解背包中存放物品总价值最大的问题解---最优解或近似最优解。3.算法设计背包问题的可形式化描述为：给定C>0,>0,>0,，要求找出n元0/1向量，使得，而且达到最大。因此0/1背包问题是一个特殊的
4、整数规划问题。设0/1背包问题的最优值为m(i,j)，即背包容量是j，可选择物品为i,i+1,…,n时0/1背包问题的最优值。由0/1背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下：max{m(i+1,j),m(i+1,j-)+}m(i,j)=m(i+1,j)m(n,j)=04.程序源码#definemaxsize1024#definenull0#include#include#includetypedefstruct{intlast;intdata[maxsize];}seqlist;//定义顺序表结构体typed
5、efstruct{inttop;intsum;intdata[maxsize];}seqstack;//定义栈结构体seqstack*init_seqstack(){seqstack*s;s=newseqstack;if(!s){printf("空间不足");returnnull;}else{s->top=-1;s->sum=0;returns;}}//栈初始化intempty_seqstack(seqstack*s){if(s->top==-1)return1;elsereturn0;}//判断空栈intpush_seqstack(seqlist*l,inti,seqstack*s)
6、//入栈{if(s->top==maxsize-1)return0;else{s->top++;s->data[s->top]=i;//顺序表中第i个元素，i入栈s->sum=s->sum+l->data[i];//栈中sum加和！return1;}}intpop_seqstack(seqlist*l,seqstack*s,int*x)//出栈{if(empty_seqstack(s))return0;else{*x=s->data[s->top];s->sum=s->sum-l->data[s->data[s->top]];s->top--;return1;}}seqlist*ini
7、t_seqlist(){seqlist*l;intx=1;l=newseqlist;l->last=0;printf("请依次输入个物品的大小，输入0结束。");scanf("%d",&x);while(x!=0){l->data[l->last]=x;l->last++;scanf("%d",&x);}returnl;}//创建数组，储存物品体积voidknapsk(intn,seqlist*l){seqstack*s;intflag=1
