最短路径问题设计报告.docx
《最短路径问题设计报告.docx》由会员分享，可在线阅读，更多相关《最短路径问题设计报告.docx（17页珍藏版）》请在冰点文库上搜索。
最短路径问题设计报告
山东交通学院
计算14级数据结构课程设计报告
题目
推销员问题
院（系、部）信息科学与电气工程学院
专业计算机科学与技术
班级计算141
学号*********
姓名李淑涵
指导教师董佑平
完成时间2015/12/24
成绩
课程设计报告规范
1．需求分析
有一个推销员要到N（N>0）个城市去推销产品，他从某个城市出发，经历每个城市，且每个城市只能去一次，然后回到初始城市，以距离作为代价，他希望找出一个最佳路径。
这N个城市相互都有道路可通，但距离各不相同，城市个数和各个城市的相通距离可由学生自己设定。
要求：
（1）可以输入城市个数（不少于10个）、输入城市信息和城市之间的距离（为整数）；
（2）按照输入出发城市，根据城市的距离最短给出路径选择。
（3）界面要求：
有合理的提示和人机交互
通过题目分析发现，转换为数据结构中的最短路径问题。
2．概要设计
VoidWrite（inti,intn,charS[25],structPath*G[25][25],intnum_S）;/*计算G[i][num_S]*/
voidTravel（intsize,inti,intn,charS[25],structPath*G[25][25],intnum_S）;/*标记V－S的顶点，然后调用Write函数来填表*/
voidTrip（intn,charS[25],structPath*G[25][25]）;/*计算min_distance并输出*/
voidPrintpath（charS[],intpath[],structPath*G[][25],intn）;/*打印输出路径*/
主要用到以上4个函数，写出输入的矩阵后调用travel函数来进行遍历，然后计算出min_distance并输出，打印出输出路径，计算结束。
3．详细设计
intGetmin（structPath*G[25][25],inti,intnum_S,charS[25]）/*查找G[i][n]链表的结点*/
{structPath*temp;
for（temp=G[i][num_S];temp!
=NULL;temp=temp->next）
if（strcmp（S,temp->pass）==0）
break;
returntemp->min_distance;
}
voidTrip（intn,charS[],structPath*G[][25]）/*计算min_distance并输出*/
{inti,size_S;
for（size_S=1;size_S<=n-2;size_S++）
{Travel（size_S,1,n,S,G,size_S）;/*从1出发求|S|=size_S的min_distance*/
for（i=0;iS[i]='0';
S[i]='\0';
}
G[0][n-1]=（structPath*）malloc（sizeof（structPath））;
G[0][n-1]->min_distance=30000;/*G[0][n-1]->min_distance为无穷大*/
for（i=1;i{if（G[0][n-1]->min_distance>C[0][i]+G[i][n-2]->min_distance）
{G[0][n-1]->min_distance=C[0][i]+G[i][n-2]->min_distance;
G[0][n-1]->nextcity=i;
}
}
printf（"最短距离:
%d\n",G[0][n-1]->min_distance）;
}
voidTravel（intsize,inti,intn,charS[25],structPath*G[25][25],intnum_S）/*标记V－S的顶点，然后调用Write函数来填表*/
{intk;
if（size==0）
{for（k=n-1;k>0;k--）/*求顶点k通过集合S到终点的最短路径*/
if（S[k]=='0'）/*k不在集合S中*/
Write（k,n,S,G,num_S）;
}
else
{for（k=i;k<=n-size;k++）
{S[k]='1';
Travel（size-1,k+1,n,S,G,num_S）;
S[k]='0';
}
}
}
voidWrite（inti,intn,charS[25],structPath*G[25][25],intnum_S）/*计算G[i][num_S]*/
{
intk,pre_min;
structPath*temp_path;
temp_path=（structPath*）malloc（sizeof（structPath））;
strcpy（temp_path->pass,S）;
temp_path->next=NULL;
temp_path->min_distance=30000;
for（k=1;k<=n-1;k++）/*对每个属于集合S的k,计算G（k,S）=min{C[i][k]+G（k,s-{k}）}*/
{if（S[k]=='1'）/*j在集合S*/
{S[k]='0';/*S=S-{k}*/
pre_min=Getmin（G,k,num_S-1,S）;/*求G（k,s-{k}）的值*/
S[k]='1';/*做循环，故要恢复集合s，选择别的k值*/
if（temp_path->min_distance>C[i][k]+pre_min）/*G（k,S）=min{C[i][k]+G（k,s-{k}）}*/
{temp_path->min_distance=C[i][k]+pre_min;
temp_path->nextcity=k;
}
}
}
temp_path->next=G[i][num_S];/*把temp_path插入到G[i][num_S]的队头*/
G[i][num_S]=temp_path;
}
voidPrintpath（charS[],intoutput[],structPath*G[][25],intn）/*打印输出路径*/
{inti,j,k;
structPath*temp;
for（i=1;iS[i]='1';
S[0]='0';
S[i]='\0';
output[0]=0;
for（k=n-1,i=1,j=G[0][k]->nextcity;k>0;i++,k--）
{output[i]=j;
S[j]='0';
for（temp=G[j][k-1];temp!
=NULL;temp=temp->next）
if（strcmp（temp->pass,S）==0）
break;
j=temp->nextcity;
}
}
4．调试与测试
正常运行的程序，正常的输出结果。
发现错误，少进行了一步循环，进行调试，如上图。
5．使用说明
1.首先运行程序
2.根据提示输入城市个数
3.输入对应的城市距离矩阵
4.等待结果
6．课程设计总结
通过此次课程设计，使我更加扎实的掌握了有关数据结构方面的知识，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验不足。
实践出真知，通过亲自动手制作，使我们掌握的知识不再是纸上谈兵。
过而能改，善莫大焉。
在课程设计过程中，我们不断发现错误，不断改正，不断领悟，不断获取。
最终的检测调试环节，本身就是在践行“过而能改，善莫大焉”的知行观。
这次课程设计终于顺利完成了，在设计中遇到了很多问题，最后在老师的指导下，终于游逆而解。
在今后社会的发展和学习实践过程中，一定要不懈努力，不能遇到问题就想到要退缩，一定要不厌其烦的发现问题所在，然后一一进行解决，只有这样，才能成功的做成想做的事，才能在今后的道路上劈荆斩棘，而不是知难而退，那样永远不可能收获成功，收获喜悦，也永远不可能得到社会及他人对你的认可！
课程设计诚然是一门专业课，给我很多专业知识以及专业技能上的提升，同时又是一门讲道课，一门辩思课，给了我许多道，给了我很多思，给了我莫大的空间。
同时，设计让我感触很深。
使我对抽象的理论有了具体的认识。
通过这次课程设计，熟悉了C和C++的运用；了解了求解最短路径的方法；以及如何提高运算的性能等等，掌握了编程的方法和技术，通过查询资料，也了解了遗传算法，退火算法原理。
我认为，在这学期的实验中，不仅培养了独立思考、动手操作的能力，在各种其它能力上也都有了提高。
更重要的是，在实验课上，我们学会了很多学习的方法。
而这是日后最实用的，真的是受益匪浅。
要面对社会的挑战，只有不断的学习、实践，再学习、再实践。
这对于我们的将来也有很大的帮助。
以后，不管有多苦，我想我们都能变苦为乐，找寻有趣的事情，发现其中珍贵的事情。
就像中国提倡的艰苦奋斗一样，我们都可以在实验结束之后变的更加成熟，会面对需要面对的事情。
回顾起此课程设计，至今我仍感慨颇多，从理论到实践，在这段日子里，可以说得是苦多于甜，但是可以学到很多很多的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。
通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。
在设计的过程中遇到问题，可以说得是困难重重，但可喜的是最终都得到了解决。
实验过程中，也对团队精神的进行了考察，让我们在合作起来更加默契，在成功后一起体会喜悦的心情。
果然是团结就是力量，只有互相之间默契融洽的配合才能换来最终完美的结果。
7．附录
#include
#include
#include
#include/*要用到malloc申请空间*/
#include/*其中定义了通过控制台进行数据输入和数据输出的函数，主要是一些用户通过按键盘产生的对应操作*/
structPath/*结构定义*/
{charpass[25];/*标记是否已经过该城市*/
intmin_distance;/*当前已知的从i出发的最小距离*/
intnextcity;/*下一个出发的城市*/
structPath*next;
};
intC[25][25];
intGetmin（structPath*G[25][25],inti,intnum_S,charS[25]）;/*查找G[i][n]链表的结点*/
voidWrite（inti,intn,charS[25],structPath*G[25][25],intnum_S）;/*计算G[i][num_S]*/
voidTravel（intsize,inti,intn,charS[25],structPath*G[25][25],intnum_S）;/*标记V－S的顶点，然后调用Write函数来填表*/
voidTrip（intn,charS[25],structPath*G[25][25]）;/*计算min_distance并输出*/
voidPrintpath（charS[],intpath[],structPath*G[][25],intn）;/*打印输出路径*/
/*S[]表示用字符数组显示的城市集合*/
voidmain（）
{intn,i,j;/*n城市个数，i行，j列*/
intoutput[25];
charS[25];
structPath*G[25][25];
printf（"请输入城市个数:
\n"）;/*输入城市个数*/
scanf（"%d",&n）;
printf（"输入各城市之间距离矩阵:
\n"）;/*输入矩阵*/
for（i=0;ifor（j=0;jscanf（"%d",&C[i][j]）;/*输入的矩阵存到C中*/
printf（"城市个数:
%d\n",n）;
for（i=0;i{for（j=0;jprintf（"%d\t",C[i][j]）;
printf（"\n"）;
}/*输出矩阵*/
for（i=0;iS[i]='0';
S[i]='\0';/*表示一个字符串的结束*/
for（i=0;i{G[i][0]=（structPath*）malloc（sizeof（structPath））;//分配大小为sizeof（structPath）的内存空间，同时将内存地址指正转换成structPath*类型，该用法一般是为结构体指针分配内存空间。
strcpy（G[i][0]->pass,S）;/*将前者复制到后者区域内*/
G[i][0]->min_distance=C[i][0];
G[i][0]->next=NULL;
}
for（i=0;ifor（j=1;jG[i][j]=NULL;
Trip（n,S,G）;
Printpath（S,output,G,n）;
printf（"路线演示:
\n"）;/*路线演示*/
for（i=0;iprintf（"%d->",output[i]+1）;
printf（"1\n"）;
getch（）;
}
intGetmin（structPath*G[25][25],inti,intnum_S,charS[25]）/*查找G[i][n]链表的结点*/
{structPath*temp;
for（temp=G[i][num_S];temp!
=NULL;temp=temp->next）
if（strcmp（S,temp->pass）==0）
break;
returntemp->min_distance;
}
voidTrip（intn,charS[],structPath*G[][25]）/*计算min_distance并输出*/
{inti,size_S;
for（size_S=1;size_S<=n-2;size_S++）
{Travel（size_S,1,n,S,G,size_S）;/*从1出发求|S|=size_S的min_distance*/
for（i=0;iS[i]='0';
S[i]='\0';
}
G[0][n-1]=（structPath*）malloc（sizeof（structPath））;
G[0][n-1]->min_distance=30000;/*G[0][n-1]->min_distance为无穷大*/
for（i=1;i{if（G[0][n-1]->min_distance>C[0][i]+G[i][n-2]->min_distance）
{G[0][n-1]->min_distance=C[0][i]+G[i][n-2]->min_distance;
G[0][n-1]->nextcity=i;
}
}
printf（"最短距离:
%d\n",G[0][n-1]->min_distance）;
}
voidTravel（intsize,inti,intn,charS[25],structPath*G[25][25],intnum_S）/*标记V－S的顶点，然后调用Write函数来填表*/
{intk;
if（size==0）
{for（k=n-1;k>0;k--）/*求顶点k通过集合S到终点的最短路径*/
if（S[k]=='0'）/*k不在集合S中*/
Write（k,n,S,G,num_S）;
}
else
{for（k=i;k<=n-size;k++）
{S[k]='1';
Travel（size-1,k+1,n,S,G,num_S）;
S[k]='0';
}
}
}
voidWrite（inti,intn,charS[25],structPath*G[25][25],intnum_S）/*计算G[i][num_S]*/
{
intk,pre_min;
structPath*temp_path;
temp_path=（structPath*）malloc（sizeof（structPath））;
strcpy（temp_path->pass,S）;
temp_path->next=NULL;
temp_path->min_distance=30000;
for（k=1;k<=n-1;k++）/*对每个属于集合S的k,计算G（k,S）=min{C[i][k]+G（k,s-{k}）}*/
{if（S[k]=='1'）/*j在集合S*/
{S[k]='0';/*S=S-{k}*/
pre_min=Getmin（G,k,num_S-1,S）;/*求G（k,s-{k}）的值*/
S[k]='1';/*做循环，故要恢复集合s，选择别的k值*/
if（temp_path->min_distance>C[i][k]+pre_min）/*G（k,S）=min{C[i][k]+G（k,s-{k}）}*/
{temp_path->min_distance=C[i][k]+pre_min;
temp_path->nextcity=k;
}
}
}
temp_path->next=G[i][num_S];/*把temp_path插入到G[i][num_S]的队头*/
G[i][num_S]=temp_path;
}
voidPrintpath（charS[],intoutput[],structPath*G[][25],intn）/*打印输出路径*/
{inti,j,k;
structPath*temp;
for（i=1;iS[i]='1';
S[0]='0';
S[i]='\0';
output[0]=0;
for（k=n-1,i=1,j=G[0][k]->nextcity;k>0;i++,k--）
{output[i]=j;
S[j]='0';
for（temp=G[j][k-1];temp!
=NULL;temp=temp->next）
if（strcmp（temp->pass,S）==0）
break;
j=temp->nextcity;
}
}
升级会员 