《2022年太原理工大学数据结构课程设计 .pdf》由会员分享，可在线阅读，更多相关《2022年太原理工大学数据结构课程设计 .pdf（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 程序设计课程设计专业班级：计科 1402 学号：2014006935 学生姓名：陈志棚指导教师：李丹丹、孟亮、王华名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 33 页 - - - - - - - - - 2 2016 年 1 月 10 日1.谁拿了最多奖学金【问题描述】某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同：1) 院士奖学金，每人8000 元，期末平均成绩高于80 分（80 ） ，并且在本学期内发表1 篇或 1 篇以
2、上论文的学生均可获得；2) 五四奖学金，每人4000 元，期末平均成绩高于85 分（85 ） ，并且班级评议成绩高于 80 分（ 80 ）的学生均可获得；3) 成绩优秀奖，每人2000 元，期末平均成绩高于90 分（ 90 ）的学生均可获得；4) 西部奖学金，每人1000 元，期末平均成绩高于85 分（ 85 ）的西部省份学生均可获得；5) 班级贡献奖，每人850 元，班级评议成绩高于80 分（ 80）的学生干部均可获得；只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。例如姚林的期末平均成绩是87 分，班级评议成绩82 分，同时他还是一位学生干部，那么他
3、可以同时获得五四奖学金和班级贡献奖，奖金总数是4850 元。【设计需求及分析】现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件） 。输入数据格式格式：输入的第一行是一个整数N（1 = N 80&ST1.article=1) money1=8000; else money1=0; return money1; int wusi(Student ST2)/五四奖学金 int money2; if(ST2.averscore85&ST2.banjiscore80) money2=4000; else money2=0; return money2; i
4、nt Chengjiyouxiu(Student ST3)/成绩优秀奖 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 33 页 - - - - - - - - - 5 int money3; if(ST3.averscore90) money3=2000; else money3=0; return money3; int xibu(Student ST4)/西部奖学金 int money4; if(ST4.averscore85&ST4.ch2=Y) money4=1
5、000; else money4=0; return money4; int banjigongxian(Student ST5)/班级贡献奖学金 int money5; if(ST5.banjiscore80&ST5.ch1=Y) money5=850; else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 33 页 - - - - - - - - - 6 money5=0; return money5; 3.主函数：int main() int N,i,j,k;
6、int sum=0;/ 存储奖学金总数printf( 请输入学生总数N：n); scanf(%d,&N); Student ArryN;/存储学生信息int MonN;/ 储存学生的奖学金; printf( 请输入学生姓名、期末平均成绩、班级评议成绩、是否学生干部、是否西部省份、论文发表数:n); for(i=0;iN;i+) scanf(%s %d %d %c %c %d,&(Arryi.name),&(Arryi.averscore),&(Arryi.banjiscore),&(Arryi.ch1),&(Arryi.ch2),&(Arryi.article); Moni=yuanshi(A
7、rryi)+wusi(Arryi)+Chengjiyouxiu(Arryi)+xibu(Arryi)+banjigongxian(Arryi); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 33 页 - - - - - - - - - 7 k=0; for(j=1;jMonk) k=j; printf( 奖学金最多的是:n%sn%dn,Arryk.name,Monk); for(i=0;iN;i+) sum=sum+Moni; printf( 奖学金总数为:%dn,s
8、um); return 0; 【实例测试及运行结果】【使用说明】1、 运行程序后输入学生总数；2、 输完总人数后分别输入各学生的姓名、期末平均成绩、班级评议成绩、是否学生干部、是否西部省份、论文发表数，每输完一个学生，以回车表示该学生信息录入完毕；3、 所以学生信息输完后回车，程序会自动得到结果！名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 33 页 - - - - - - - - - 8 【心得体会】1、 程序设计思路不难，主要是定义两个数组，一个结构体数组用于存储学
9、生信息，一个数组用于存储学生所得的奖学金，两个数组的下标相互对应，即一个数组学生信息对应着另一个数组中该学生所得奖学金，之后找出数组中奖学金最多的学生并输出学生信息和奖学金总数，最后输出所以学生所得的奖学金总数！2、 通过该程序，能够让我更好的掌握结构数组的使用。3、 程序可以加以改进，将判断是否能拿到奖学金的5 个函数写成一个函数，这样能够使程序更加简洁！2、统计数字【问题描述】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 33 页 - - - - - - - - -
10、 9 某次科研调查时得到了n个自然数，每个数均不超过1500000000 （1.5* 109） 。已知不相同的数不超过10000 个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。【设计需求及分析】原 始 数 据 保 存 在 文 件 count.in中 ， 文 件 包 含n+1行 。 第1 行 是 整 数n(1=n=200000)，表示自然数的个数；第2n+1 行每行一个自然数。结果保存在文件count.out中，文件count.out包含m行（m为n个自然数中不相同数的个数） ，按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间
11、用一个空格隔开【设计功能的实现】 （用 C或 C+描述）#includestdio.h #includestdlib.h 1、 定义一个顺序查找函数，用于每次在文件中读取数据时判断存储的数组中是否有该数据，如果已存在，则返回该数据在数组中对应的下标，不存在，则返回0；int Locate(int r,int e,int length)/顺序查找函数 int i=0; while(i=length)&(ri!=e) i+; if(i=length) return i; else return 0; 2、 定义一个直接插入排序函数，用于将已存完数据的数组将里面数据从小到大排序；void InsSo
12、rt(int r,int c,int length)/直接插入排序 int i,j; for(i=2;ir0) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 33 页 - - - - - - - - - 10 rj+1=rj;cj+1=cj; j-; rj+1=r0;cj+1=c0; 3、 主函数：int main() FILE *fp,*out; int str10,cou10,temp;/str用来储存来自文件的数据，cou 用来储存相同数据的个数， str和 co
13、u 下标互相对应。temp 为临时储存 int i=1,j=1,k,t; 课程设计程序程序2count.in.txt,r); 课程设计程序程序2count.out.txt,w); if(fp=NULL) printf(无法打开输入文件); exit(0); if(out=NULL) printf(无法打开输出文件); exit(0); fscanf(fp,%d,&t); printf(共有 %d个自然数 n,t); for(i;i=t;i+) fscanf(fp,%d,&temp); printf(%dn,temp); k=Locate(str,temp,j-1);/查找函数，若查找成功，返回
14、temp 在数组str中的数组下标，否则返回0 if(k) couk+;/数组 str中有 temp 该自然数，则对应计数数组cou 加 1； else strj=temp;/查找不成功，则将temp 插入到 str中 couj=1; j+; /结束后 j 为 str数组长度 InsSort(str,cou,j);/将 str数组中的自然数按从小到大排序，cou 数组对应下标也跟着变化名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 33 页 - - - - - - -
15、- - 11 printf(统计的结果为:n); for(i=1;ij;i+) printf(%d %dn,stri,coui);/屏幕输出统计结果 fprintf(out,%d %dn,stri,coui);/将结果输出到count.out中 fclose(fp); fclose(out); 【实例测试及运行结果】待读取的文件程序运行结果：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 33 页 - - - - - - - - - 12 输出文件：【使用说明】1、 将
16、需要统计的数字保存到文本文件中，文件名为“count.in ”，并将文件放到程序对应的路劲下（课程设计程序程序 2count.in.txt ） ；2、 运行程序，则会在程序对应的输出路径（课程设计程序 程序 2count.out.txt ）中输出一个统计结果的count.out文件文件。3、 打开 coun.out 文件文本便可查看结果。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 33 页 - - - - - - - - - 13 【心得体会】1、 本道题的思路是：
17、 定义两个数组str和 cou，数组 str用于存储来自文本“count.in”中的自然数，数组cou 用于存储自然数出现的个数。两个数组下标相互对应（同一个下标在两个数组中分别表示自然数和该自然数出现的次数）。 通过 fscanf函数每次向文件中读取一个自然数时，判断该读取的自然数在数组str中是否存在，如果存在，则在 cou 数组中对应的将改自然数出现的次数加1，如果不存在，则将该自然数插入到数组 str中。最后将数组str 中的自然数通过排序按从小到大排序，cou 数组中的数按str 数组相对应的发生变化。最后将str 和 cou 数组中的数据输出到“ count.out ”文件文本中。
18、2、 通过该程序，让我加深对文件文本的操作，以及对查找和排序的使用。3、 该程序可以加以改进，将str 和 cou 这两个数组定义到一个结构体中，这样能够使程序更加精悍。3文件文本单词的计数【问题描述】假设有如下的英文文本文档：(此处为太原理工大学学校简介英文版) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 33 页 - - - - - - - - - 14 Taiyuan University of Technology (TUT) has its history
19、 traced all the way back to the Western Learning School of Shanxi Grand Academy (1902), which was one of the three earliest national universities in China. With the tradition and development of over 100 years, TUT is now a general university with engineering as the major, sciences and technology int
20、egrated and coordinate development of multiple disciplines. It is a university that is included in the “Project 211” - the national higher education promotion program for 100 top universities in China. 设计 C 或 C+ 程序，统计在这样的英文文本文件中，出现了多少个单词，每个单词出现了几次。连续的英文字符都认为单词(不包括数字 )，单词之间用空格或标点符号分隔。【设计需求及分析】要统计英文文本
21、文件中出现了哪些单词，就要从文件中读取字符，读取出来的连续英文字符认为是一个单词，遇空格或标点符号单词结束。使用线性表记录单词以及每个单词出现的次数。线性表中的单词按字典顺序存储。【设计功能的实现】 （用 C或 C+描述）#include stdio.h #include stdlib.h #include string.h 1、 定义一个线性表用于存储文件文本中读取的单词和记录单词出现的次数：typedef struct char word21; /存储单词，不超过20 个字符int count; /单词出现的次数 ElemType; typedef struct ElemType elem
22、; /存储空间基址 Seqlist; 2、 定义一个字符串顺序查找函数，用于每次在文件中读取数据时判断存储的数组中是否有该数据，如果已存在，则返回该数据在数组中对应的下标，不存在，则返回0；int LocateElem(Seqlist r,char e,int length)/字符串顺序查找函数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 33 页 - - - - - - - - - 15 int i=0; while(i=length)&(strcmp(ri.ele
23、m.word,e)!=0)/strcmp为字符串比较函数，相等则返回0 i+; if(i=length) return i; else return 0; 3、 定义一个字符串直接插入排序函数，用于将已存完数据的数组将里面数据从小到大排序；void InsertList(Seqlist r,int length)/字符串直接插入排序 int i,j; for(i=2;i0)/若字符串rj.elem.word大于字符串 r0.elem.word ，则返回值大于0 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - -
24、 - - - - - 第 15 页，共 33 页 - - - - - - - - - 16 rj+1=rj; j-; rj+1=r0; 4、 主函数：int main() FILE *fp,*out; int i=1,j,n; int length=0;/ 储存数组 str 的长度Seqlist str100; char temp21;/临时储存变量课程设计程序程序 3tyut.txt,r); 课程设计程序程序3counttyut.txt,w); if(fp=NULL) printf( 无法打开输入文件!); exit(0); 名师资料总结 - - -精品资料欢迎下载 - - - - - -
25、- - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 33 页 - - - - - - - - - 17 if(out=NULL) printf( 无法打开输出文件!); exit(0); while(fscanf(fp,%s,temp)!=EOF) j=LocateElem(str,temp,length); if(j=0)/ 数组 str 中不存在temp ，将 temp 插入到数组str 中strcpy(stri.elem.word,temp);/strcpy字符串赋值函数，将temp 中的字符串赋值给stri.elem.word s
26、tri.elem.count=1; length+;/ 数组 str 长度加 1 i+; else strj.elem.count+;/若数组 str 中存在 temp ， 则该字符串的计数count 加 1 InsertList(str,length);/调用字符串直接插入排序printf( 统计结果为 :n); for(n=1;nlength;n+) printf(%10s %dn,strn.elem.word,strn.elem.count);/屏幕输出统计结果fprintf(out,%10s %dn,strn.elem.word,strn.elem.count);/将 结 果 输 出
27、到名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 33 页 - - - - - - - - - 18 counttyut.txt中 fclose(fp); return 0; 【实例测试及运行结果】1、程序运行结果：2、输入文件文本：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 33 页 - - - - - - - - - 19 4、 输出文本
28、文件：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 33 页 - - - - - - - - - 20 【心得体会】1、 本道题设计思路是：定义一个结构体数组str用于存储从文本本件中读取到的单词和各单词出现的次数，通过fscanf函数每次从文件文本中读取一个单词时，判断该单词在数组str.elem.word中是否存在，如果存在，则在str.elem.count中将该单词出现的次数加1，如果不存在，则将该单词插入到str.elem.word中。最 后 将 数 组str
29、中 的 单 词 按 字 典 顺 序 从 小 到 大 排 序 ， 并 将str.elem.word和str.elem.count数据输出到“counttyut.txt ”文件文本中。2、通过该程序，让我更加熟练的掌握如何从一个文件文本中读取一个字符串，以及更深度的掌握字符串大小的比较。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 33 页 - - - - - - - - - 21 5、交通咨询系统（最短路径问题）【问题描述】在交通网络非常发达, 交通工具和交通方式不断更
30、新的今天, 人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需要的时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中的顶点表示城市，边表示城市之间的交通关系。这个交通系统可以回答出行旅客提出的各种路径选择问题。例如，问题之一：“一位旅客要从 A城到 B城，他希望选择一条途中中转次数最少的路线。”假设图中每一站都需要换车， 那么这个问题反映到图上就是要找一条从顶点A到顶点 B的所含边数目最少的路径。我们只需要从顶点A出发对图作广度优先搜索，一旦遇到顶点B 就终止。由此所得广度优先生成树上，从根顶点 A 到顶点
31、 B 的路径就是中转次数最少的路径。路径上A 与 B之间的顶点就是路径的中转站，但这只是一类最简单的图的最短路径问题。系统还可以回答诸如此类的等等的路径选择问题。设计一个交通咨询系统，为出差、旅游或做其他出行的客人提供各种路径选择信息查询服务。【设计需求及分析】设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所需时间或所需费用。本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现任两个城市顶点之间的最短路径问题。名师资料总结 - - -精品资料欢迎下载 - -
32、 - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 33 页 - - - - - - - - - 22 建立图的存储结构邻接矩阵是表示图形中顶点之间相邻关系的矩阵。图的邻接矩阵是定义如下的n 阶方阵：设 G= （V，E）是一个图，结点集为。G的邻接矩阵,E,0E,)(,)(jijijijinnjiijnnijvvvvvvvvwaaA）或当（，或）或当（，当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一个具有n 个
33、元素的一维数组来存储顶点信息，其中下标为i 的元素存储顶点 i 的信息。因此，图的邻接矩阵的存储结构定义如下：#definf MVNum 50 /最大顶点数typedef struct VertexType vexsMVNum; /顶点数组，类型假定为char 型 Adjmatrix arcsMVNumMVNum; /邻接矩阵，假定为int型MGraph; 单源最短路径最短路径的提法很多。在这里先讨论单源最短路径问题：即已知有向图（带权），我们希望找出从某个源点SV到 G中其余各顶点的最短路径。为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。那么，如何求得给定有向图的单源
34、最短路径呢？迪杰斯特拉（Dijkstra）提出按路径长度递增产生诸点的最短路径算法，称之为迪杰斯特拉算法。nvvvV,21名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 33 页 - - - - - - - - - 23 迪杰斯特拉算法求最短路径的实现思想是：设G= （V，E）是一个有向图，结点集为，v,v,vVn21，cost 是表示 G的邻接矩阵， costij表示有向边 的权。若不存在有向边 ，则 costij的权为无穷大（这里取值为32767） 。设 S 是一个
35、集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点v1为源点，集合S的初态只包含一个元素，即顶点v1。数组 dist记录从源点到其他顶点当前的最短距离， 其初值为disti=costv1i,i=1,2, ,n 。从 S之外的顶点集合V-S中选出一个顶点w，使 distw的值最小。于是从源点到达w只通过 S中顶点，把w加入集合 S中，调整 dist中记录的从源点到V-S 中每个顶点v 的距离：从原来的distv和distw+costwv中选择较小的值作为新的distv。重复上述过程，直到V-S 为空。最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist
36、记录了源点到V 中其余各顶点之间的最短路径，path 是最短路径的路径数组，其中pathi表示从源点到顶点i 之间的最短路径的前驱顶点。因此，迪杰斯特拉算法可用自然语言描述如下：初始化 S和 D，置空最短路径终点集，置初始的最短路径值；Sv1=TRUE; Dv1=0 ； /S集初始时只有源点，源点到源点的距离为0；While (S集中顶点数 n) 开始循环，每次求得v1到某个 v 顶点的最短路径，并加v 到 S集中；Sv=TRUE；更新当前最短路径及距离； 任意一对顶点间最短路径名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名
37、师精心整理 - - - - - - - 第 23 页，共 33 页 - - - - - - - - - 24 任意一对顶点间最短路径问题，是对于给定的有向网络图G= （V，E） ，要对 G中任意一对顶点有序对“ v,w(vw)” , 找出 v 到 w的最短路径。要解决这个问题，我们可以依次把有向网络图中每个顶点作为源点，重复执行前面讨论的迪杰斯特拉算法n 次，即可以求得每对顶点之间的最短路径。这里还可以用另外一种方法，称作费洛伊德（Floyd ）算法。费洛伊德（ Floyd ）算法算法的基本思想是：假设求从顶点 vi到 vj的最短路径。如果从 vi到 vj存在一条长度为arcsij的路径，该路
38、径不一定是最短路径，还需要进行n 次试探。首先考虑路径 和是否存在。 如果存在，则比较 和的路径长度，取长度较短者为当前所求得的最短路径。该路径是中间顶点序号不大于1的最短路径。 其次，考虑从 vi到 vj是否包含有顶点v2为中间顶点的路径，若没有，则说明从 vi到 vj的当前最短路径就是前一步求出的；若有，那么 可分解为 和, 而这两条路径是前一次找到的中间顶点序号不大于1 的最短路径，将这两条路径长度相加就得到路径的长度。将该长度与前一次中求出的从vi到 vj的中间顶点序号不大于1 的最短路径比较，取其长度较短者作为当前求得的从vi到 vj的中间顶点序号不大于2 的最短路径。依此类推，直到
39、顶点vn加入当前从 vi到 vj的最短路径后，选出从vi到 vj的中间顶点序号不大于n 的最短路径为止。由于图 G中顶点序号不大于n，所以vi到 vj的中间顶点序号不大于n 的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是vi到 vj的最短路径。【设计功能的实现】 （用 C或 C+描述）#include #include #define MVNum 100 /最大顶点数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 24 页，共 33 页 - - - - - - - -
40、 - 25 #define Maxint 32767 enum boolean FALSE,TRUE ; typedef char VertexType; typedef int Adjmatrix; typedef struct VertexType vexsMVNum; /顶点数组，类型假定为char 型Adjmatrix arcsMVNumMVNum; /邻接矩阵，假定为int 型MGraph; int D1MVNum,P1MVNum; int DMVNumMVNum,PMVNumMVNum; void CreateMGraph(MGraph *G,int n,int e) /采用邻接矩
41、阵表示法构造有向图G，n,e 表示图的当前顶点数和边数int i,j,k,w; for(i=1;ivexsi=(char)i; for(i=1;i=n;i+) for(j=1;jarcsij=Maxint; /初始化邻接矩阵printf( 输入 %d 条边的 i,j 以及 w:n,e); for(k=1;karcsij=w; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 25 页，共 33 页 - - - - - - - - - 26 printf( 有向图的存储结构建立完毕!n)
42、; void Dijkstra(MGraph *G,int v1,int n) /用 Dijkstra 算法求有向图G 的 v1 顶点到其他顶点v 的最短路径Pv 及其权 Dv /设 G 是有向图的邻接矩阵，若边 不存在，则Gij=Maxint /Sv 为真当且仅当v 属于 s,即已求得从v1 到 v 得最短路径int D2MVNum,P2MVNum; int v,i,w,min; enum boolean SMVNum; for(v=1;varcsv1v; /置初始的最短路径值if(D2vMaxint) P2v=v1; /v1 是 v 的前驱（双亲）else P2v=0; /v 无前驱 /e
43、nd for D2v1=0;Sv1=TRUE; for(i=2;in;i+) min=Maxint; for(w=1;w=n;w+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 26 页，共 33 页 - - - - - - - - - 27 if(!Sw & D2wmin) v=w;min=D2w; Sv=TRUE; for(w=1;warcsvwarcsvw; P2w=v; printf( 路径长度路径 n); for(i=1;i=n;i+) printf(%5d,D2i);
44、 printf(%5d,i);v=P2i; while(v!=0) printf(-%d,v); v=P2v; printf(n); void Floyd(MGraph *G,int n) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 27 页，共 33 页 - - - - - - - - - 28 int i,j,k,v,w; for(i=1;i=n;i+) for(j=1;jarcsij!=Maxint) Pij=j; else Pij=0; Dij=G-arcsij; for
45、(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j=n;j+) if(Dik+Dkj%d,k); k=Pkw; printf(-%d,w); printf( 路径长度 : %dn,Dvw); else if(xz=1) printf( 求单源路径 ,输入源点v:); scanf(%d,&v); Dijkstra(G,v,n); printf( 结束求最短路径,再见 !n); 【实例测试及运行结果】1、 有向图：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第
46、30 页，共 33 页 - - - - - - - - - 31 2、 运行结果：【使用说明】建立一个有向图的存储结构有向图的邻接矩阵是不对称的，实现其算法，我们只需要输入有向图的有向边及权值即可。采用邻接矩阵表示法构造有向图G，输入图中顶点个数和边数，初始化邻接矩阵，紧跟着系统提示输入边及权值，则系统提示有向图的存储结构建立完毕。地杰斯特拉算法为了解决单源路径问题，我们提出了迪杰斯特拉算法，它主要是按路径长度递增产生名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 31 页，共 33
47、 页 - - - - - - - - - 32 顶点的最短路径算法，其实现如下：初始化 S 和 D，置空最短路径终点集，置初始的最短路径值；Sv1=TRUE;Dv1=0;/S集初始时只有源点，源点到源点的距离为0；While(S 集中顶点数 n) 开始循环，每次求得v1 到某个 v 顶点的最短路径，并加V 到 S 集中；Sv=TRUE; 更新当前最短路径及距离； 弗洛伊德算法任意一对顶点间最短路径，假设求从顶点vi 到 vj 的最短路径。如果从vi 到 vj 存在一条长度为arcsij 的路径，该路径不一定是最短路径，还需要进行n 次试探。首先考虑路径 vi，v1和 v1， vj是否存在。如果
48、存在，则比较路径vi，vj和 vi，v1，vj的路径长度，取长度较短者为当前所求得的最短路径。该路径是中间顶点序号不大于1的最短路径。 其次，考虑从 vi 到 vj 是否包含有顶点v2 为中间顶点的路径 vi，v2，vj ，若没有，则说明从vi 到 vj 的当前最短路径就是前一步求出的；若有，那么vi，v2， vj可分解为 vi， v2和 v2， vj ，而这两条路径是前一次找到的中间点序号不大于1 的最短路径，将这两条路径长度相加就得到路径vi， v2，vj的长度。将该长度与前一次中求出的从vi 到 vj 的中间顶点序号不大于2 的最短路径。依次类推，直至顶点vn 加入当前从vi 到 vj
49、的最短路径后，选出从vi 到 vj 的中间顶点序号不大于 n 的最短路径为止。由于图G 中顶点序号不大于n，所以 vi 到 vj 的中间顶点序号不大于 n 的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是vi 到 vj的最短路径。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 32 页，共 33 页 - - - - - - - - - 33 【心得体会】在该程序中，有向图的邻接矩阵是不对称的，实现其算法，我们只需要输入有向图的有向边及权值即可。总的来说，这次课程设计还是学到了一些东西，经过我们不断的实验，找到了错误答案，学到了很多东西，所以在编程中和调试中要养成认真分析的善于发现问题并及时解决的习惯，不懂的及时问老师或其他同学。通过本次实验，让我们对图的基本结构有了更好的认识，有效的解决了最短路径问题，对两个算法的使用有了更好的掌握。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 33 页，共 33 页 - - - - - - - - -