最短路径问题设计报告

1、山东交通学院计算14级数据结构课程设计报告题目推销员问题院(系、部) 信息科学与电气工程学院专 业 计算机科学与技术 班 级 计算141 学 号 140811119 姓 名 李淑涵 指导教师 董佑平 完成时间 2015/12/24 成 绩 课程设计报告规范1需求分析有一个推销员要到N（N>0）个城市去推销产品，他从某个城市出发，经历每个城市，且每个城市只能去一次，然后回到初始城市，以距离作为代价，他希望找出一个最佳路径。这N个城市相互都有道路可通，但距离各不相同，城市个数和各个城市的相通距离可由学生自己设定。要求：（1）可以输入城市个数（不少于10个）、输入城市信息和城市之间的距离（为整

2、数）；（2）按照输入出发城市，根据城市的距离最短给出路径选择。（3）界面要求：有合理的提示和人机交互通过题目分析发现，转换为数据结构中的最短路径问题。2概要设计Void Write(int i,int n,char S25,struct Path *G2525,int num_S);/*计算Ginum_S*/ void Travel(int size,int i,int n,char S25,struct Path *G2525,int num_S);/*标记VS的顶点，然后调用Write函数来填表*/ void Trip(int n,char S25,struct Path *G2525);

3、/*计算min_distance并输出*/ void Printpath(char S,int path,struct Path *G25,int n);/*打印输出路径*/主要用到以上4个函数，写出输入的矩阵后调用travel函数来进行遍历，然后计算出min_distance并输出，打印出输出路径，计算结束。 3详细设计 int Getmin(struct Path *G2525,int i,int num_S,char S25)/*查找Gin链表的结点*/ struct Path *temp; for(temp=Ginum_S;temp!=NULL;temp=temp->next)

4、if(strcmp(S,temp->pass)=0) break; return temp->min_distance; void Trip(int n,char S,struct Path *G25)/*计算min_distance并输出*/ int i,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;i<n;i+) Si='0' Si='0' G0n-1=(s

5、truct Path *)malloc(sizeof(struct Path); G0n-1->min_distance=30000; /*G0n-1->min_distance为无穷大*/ for(i=1;i<n;i+) if(G0n-1->min_distance>C0i+Gin-2->min_distance) G0n-1->min_distance=C0i+Gin-2->min_distance; G0n-1->nextcity=i; printf("最短距离:%dn",G0n-1->min_distanc

6、e); void Travel(int size,int i,int n,char S25,struct Path *G2525,int num_S)/*标记VS的顶点，然后调用Write函数来填表*/ int k; if(size=0) for(k=n-1;k>0;k-)/*求顶点k通过集合S到终点的最短路径*/ if(Sk='0')/*k不在集合S中*/ Write(k,n,S,G,num_S); else for(k=i;k<=n-size;k+) Sk='1' Travel(size-1,k+1,n,S,G,num_S); Sk='0

7、' void Write(int i,int n,char S25,struct Path *G2525,int num_S)/*计算Ginum_S*/ int k,pre_min; struct Path *temp_path; temp_path=(struct Path *)malloc(sizeof(struct Path); strcpy(temp_path->pass,S); temp_path->next=NULL; temp_path->min_distance=30000; for(k=1;k<=n-1;k+)/*对每个属于集合S的k,计算G(

8、k,S)=minCik+G(k,s-k)*/ if(Sk='1') /*j在集合S*/ Sk='0' /*S=S-k*/ pre_min=Getmin(G,k,num_S-1,S); /*求G(k,s-k)的值*/ Sk='1' /*做循环，故要恢复集合s ，选择别的k值*/ if(temp_path->min_distance>Cik+pre_min)/*G(k,S)=minCik+G(k,s-k)*/ temp_path->min_distance=Cik+pre_min; temp_path->nextcity=k;

9、 temp_path->next=Ginum_S;/*把temp_path插入到Ginum_S的队头*/ Ginum_S=temp_path; void Printpath(char S,int output,struct Path *G25,int n)/*打印输出路径*/ int i,j,k; struct Path *temp; for(i=1;i<n;i+) Si='1' S0='0' Si='0' output0=0; for(k=n-1,i=1,j=G0k->nextcity;k>0;i+,k-) output

10、i=j; Sj='0' for(temp=Gjk-1;temp!=NULL;temp=temp->next) if(strcmp(temp->pass,S)=0) break;j=temp->nextcity; 4调试与测试正常运行的程序，正常的输出结果。发现错误，少进行了一步循环，进行调试，如上图。5使用说明1.首先运行程序2.根据提示输入城市个数3.输入对应的城市距离矩阵4.等待结果6课程设计总结通过此次课程设计，使我更加扎实的掌握了有关数据结构方面的知识，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出

11、了前期我在这方面的知识欠缺和经验不足。实践出真知，通过亲自动手制作，使我们掌握的知识不再是纸上谈兵。 过而能改，善莫大焉。在课程设计过程中，我们不断发现错误，不断改正，不断领悟，不断获取。最终的检测调试环节，本身就是在践行“过而能改，善莫大焉”的知行观。这次课程设计终于顺利完成了，在设计中遇到了很多问题，最后在老师的指导下，终于游逆而解。在今后社会的发展和学习实践过程中，一定要不懈努力，不能遇到问题就想到要退缩，一定要不厌其烦的发现问题所在，然后一一进行解决，只有这样，才能成功的做成想做的事，才能在今后的道路上劈荆斩棘，而不是知难而退，那样永远不可能收获成功，收获喜悦，也永远不可能得

12、到社会及他人对你的认可！ 课程设计诚然是一门专业课，给我很多专业知识以及专业技能上的提升，同时又是一门讲道课，一门辩思课，给了我许多道，给了我很多思，给了我莫大的空间。同时，设计让我感触很深。使我对抽象的理论有了具体的认识。通过这次课程设计，熟悉了C和C+的运用；了解了求解最短路径的方法；以及如何提高运算的性能等等，掌握了编程的方法和技术，通过查询资料，也了解了遗传算法，退火算法原理。 我认为，在这学期的实验中，不仅培养了独立思考、动手操作的能力，在各种其它能力上也都有了提高。更重要的是，在实验课上，我们学会了很多学习的方法。而这是日后最实用的，真的是受益匪浅。要面对社会的

13、挑战，只有不断的学习、实践，再学习、再实践。这对于我们的将来也有很大的帮助。以后，不管有多苦，我想我们都能变苦为乐，找寻有趣的事情，发现其中珍贵的事情。就像中国提倡的艰苦奋斗一样，我们都可以在实验结束之后变的更加成熟，会面对需要面对的事情。 回顾起此课程设计，至今我仍感慨颇多，从理论到实践，在这段日子里，可以说得是苦多于甜，但是可以学到很多很多的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从

14、而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，但可喜的是最终都得到了解决。  实验过程中，也对团队精神的进行了考察，让我们在合作起来更加默契，在成功后一起体会喜悦的心情。果然是团结就是力量，只有互相之间默契融洽的配合才能换来最终完美的结果。7附录#include <stdio.h> #include <stdlib.h> #include <string.h> #include <malloc.h>/*要用到 malloc 申请空间*/ #include <conio.h>

15、/*其中定义了通过控制台进行数据输入和数据输出的函数，主要是一些用户通过按键盘产生的对应操作*/ struct Path/*结构定义*/ char pass25;/*标记是否已经过该城市*/ int min_distance;/*当前已知的从i出发的最小距离*/ int nextcity;/*下一个出发的城市*/ struct Path *next; ; int C2525; int Getmin(struct Path *G2525,int i,int num_S,char S25);/*查找Gin链表的结点*/ void Write(int i,int n,char S25,struct

16、Path *G2525,int num_S);/*计算Ginum_S*/ void Travel(int size,int i,int n,char S25,struct Path *G2525,int num_S);/*标记VS的顶点，然后调用Write函数来填表*/ void Trip(int n,char S25,struct Path *G2525);/*计算min_distance并输出*/ void Printpath(char S,int path,struct Path *G25,int n);/*打印输出路径*/ /*S表示用字符数组显示的城市集合*/ void main()

17、 int n,i,j;/* n城市个数，i行，j列*/ int output25; char S25; struct Path *G2525; printf("请输入城市个数:n");/*输入城市个数*/ scanf("%d",&n); printf("输入各城市之间距离矩阵:n");/*输入矩阵*/ for(i=0;i<n;i+) for(j=0;j<n;j+) scanf("%d",&Cij);/*输入的矩阵存到C中*/ printf("城市个数:%dn",n);

18、 for(i=0;i<n;i+) for(j=0;j<n;j+) printf("%dt",Cij); printf("n"); /*输出矩阵*/ for(i=0;i<n;i+) Si='0' Si='0'/*表示一个字符串的结束*/ for(i=0;i<n;i+) Gi0=(struct Path*)malloc(sizeof(struct Path); / 分配大小为sizeof(struct Path)的内存空间，同时将内存地址指正转换成struct Path*类型，该用法一般是为结构体指针分

19、配内存空间。 strcpy(Gi0->pass,S); /*将前者复制到后者区域内*/ Gi0->min_distance=Ci0; Gi0->next=NULL; for(i=0;i<n;i+) for(j=1;j<n;j+) Gij=NULL; Trip(n,S,G); Printpath(S,output,G,n); printf("路线演示:n");/*路线演示*/ for(i=0;i<n;i+) printf("%d->",outputi+1); printf("1n"); getc

20、h(); int Getmin(struct Path *G2525,int i,int num_S,char S25)/*查找Gin链表的结点*/ struct Path *temp; for(temp=Ginum_S;temp!=NULL;temp=temp->next) if(strcmp(S,temp->pass)=0) break; return temp->min_distance; void Trip(int n,char S,struct Path *G25)/*计算min_distance并输出*/ int i,size_S; for(size_S=1;si

21、ze_S<=n-2;size_S+) Travel(size_S,1,n,S,G,size_S);/*从1出发求|S|=size_S的min_distance*/ for(i=0;i<n;i+) Si='0' Si='0' G0n-1=(struct Path *)malloc(sizeof(struct Path); G0n-1->min_distance=30000; /*G0n-1->min_distance为无穷大*/ for(i=1;i<n;i+) if(G0n-1->min_distance>C0i+Gin-

22、2->min_distance) G0n-1->min_distance=C0i+Gin-2->min_distance; G0n-1->nextcity=i; printf("最短距离:%dn",G0n-1->min_distance); void Travel(int size,int i,int n,char S25,struct Path *G2525,int num_S)/*标记VS的顶点，然后调用Write函数来填表*/ int k; if(size=0) for(k=n-1;k>0;k-)/*求顶点k通过集合S到终点的最短路

23、径*/ if(Sk='0')/*k不在集合S中*/ Write(k,n,S,G,num_S); else for(k=i;k<=n-size;k+) Sk='1' Travel(size-1,k+1,n,S,G,num_S); Sk='0' void Write(int i,int n,char S25,struct Path *G2525,int num_S)/*计算Ginum_S*/ int k,pre_min; struct Path *temp_path; temp_path=(struct Path *)malloc(sizeof(struct Path); strcpy(temp_path->pass,S); temp_path->next=NULL; temp_path->min_dist