河南城建学院
课
程设计 报告书
专 业：计算机科学与技术
课程设计名称：《数据结构课程设计》
题 目：最小生成树问题
班 级：
学 号：
姓 名：
同 组 人 员:
指 导 老 师：
完 成 时 间： 2012年2月17日
摘要
本课程设计主要解决图的关键路径的实现。在项目管理中，编制网络计划的基本思想就是在一个庞大的网络图中找出关键路径，并对各关键活动，优先安排资源，挖掘潜力，采取相应措施，尽量压缩需要的时间。而对非关键路径的各个活动，只要在不影响工程完工时间的条件下，抽出适当的人力、物力和财力等资源，用在关键路径上，以达到缩短工程工期，合理利用资源等目的。在执行计划过程中，可以明确工作重点，对各个关键活动加以有效控制和调度。关键路径法将项目分解成为多个独立的活动并确定每个活动的工期，然后用逻辑关系（结束-开始、结束-结束、开始-开始和开始结束）将活动连接，从而能够计算项目的工期、各个活动时间特点（最早最晚时间、时差）等。在关键路径法的活动上加载资源后，还能够对项目的资源需求和分配进行分析。
在本程序设计中，要求实现图的关键路径，最小生成树，判断两点之间是否有路径，程序由2个模块组成，分别为主函数的创建及其他相关函数的设计。程序通过调试运行，初步实现了设计目标。在课程设计中，系统开发平台为Windows 2000，程序设计设计语言采用Visual C++，程序运行平台为Windows 98/2000/XP。
关键词 程序设计； C++；图；关键路径
目录
目录 .................................................................................................................................. - 3 -
第一章 开发环境和开发工具 . ......................................................................................... 4
1.1 C/ C ++语言简介 . ............................................................................................... 4
1.1 开发背景 . ............................................................................................................. 4
1.3 开发环境 ................................................................................................................ 5
第二章 算法思想 ............................................................................................................... 6
2.1 系统需求分析 ............................................................................................................... 6
2.2 系统总体设计 ......................................................................................................... 7
2.2.1 系统设计目标 ............................................................................................. 7
2.2.2 开发设计思想 ............................................................................................. 7
2.2.3 系统功能模块设计 ..................................................................................... 9
2.3 算法思想描述 ......................................................................................................... 9
第三章 算法实现 . ........................................................................................................... 11
3.1 数据结构 . ........................................................................................................... 11
3.2 程序模块 ............................................................................................................... 12
1.insertsort 函数 ........................................................................................................... 12
3.3 各模块之间的调用关系 ....................................................................................... 17
3.4 源程序代码 ........................................................................................................... 17
第四章 测试与分析 . ....................................................................................................... 27
4.1 测试数据选择 ....................................................................................................... 27
总 结 ............................................................................................................................. 30
心得体会 ............................................................................................................................. 31
参考文献 ..................................................................................................................... 32
第一章 开发环境和开发工具
1.1 C/ C ++语言简介
C 语言是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言的特点。它由美国贝尔研究所的D.M.Ritchie 于1972年推出。1978后，C 语言已先后被移植到大、中、小及微型机上。它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。它的应用范围广泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类科研都需要用到C 语言，适于编写系统软件，三维，二维图形和动画。具体应用比如单片机以及嵌入式系统开发
C++语言是一种优秀的面向对象程序设计语言，它在C 语言的基础上发展而来，但它比C 语言更容易为人们学习和掌握。C++以其独特的语言机制在计算机科学的各个领域中得到了广泛的应用。面向对象的设计思想是在原来结构化程序设计方法基础上的一个质的飞跃，C++完美地体现了面向对象的各种特性。
1.1 开发背景
数据结构课程是计算机专业最重要的基础课之一，主要研究分析计算机存储、组织数据的方式，使学生能够根据数据对象的特征，选择适当的数据结构、存储结构及相应算法，初步掌握各种算法在时间和空间上的分析技巧，并能够进行算法和程序设计，使所涉及的程序结构清楚，正确易读[3]。数据的组织方法和现实世界问题在计算机内部的表示方法，并能针对应用问题，选择合适的数据逻辑结构、存储结构及其算法，掌握解决复杂问题的程序设计方法和技术。选择合适的数据结构更容易设计出更高效运行或存储效率的算法；图是一种较线性表和树更为复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中的任意两个元素之间都可能相关。
在社会主义建设时期，各个城市建设问题尤其是网络建设尤为重要。在保证各个城市能互相连通的情况下，怎么保证建设网络，怎么建设最省钱是建设工程公司所需考虑的重大情况。从而能节省更多的钱来投资其他地方建设，如农村交通建设。
各个各个城市建设好之后，则可再根据将城市作为一个结点和其它城市再次运用最小生成树。
最小生成树则能有效的解决此问题。例如，以尽可能低的总价建设若干网络管道，把n 个城市联系在一起。
1.3 开发环境
本文所采用的开发环境主要是基于Windows XP系统，编程环境主要是在VC6.0++中。
第二章 算法思想
2.1 系统需求分析
根据课设题目要求，拟将整体程序分为三大模块。以下是三个模块的大体分析：
1. 要确定图的存储形式，通过对题目要求的具体分析。发现该题的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。
2. Kruskal 算法。该算法设置了集合A ，该集合一直是某最小生成树的子集。在每步决定是否把边（u,v ）添加到集合A 中，其添加条件是A ∪{（u,v ）}仍然是最小生成树的子集。我们称这样的边为A 的安全边，因为可以安全地把它添加到A 中而不会破坏上述条件。
3. Dijkstra 算法。算法的基本思路是：假设每个点都有一对标号（d j ,p j ）, 其中d 是从起源点到点j 的最短路径的长度（从顶点到其本身的最短路径是零路（没有弧的路），其长度等于零）；p j 则是从s 到j 的最短路径中j 点的前一点。求解从起源点s 到点j 的最短路径算法的基本过程如下：
1）初始化。起源点设置为：①d s =0,ps 为空；②所有其它点：d i =∞,p i =？；③标
记起源点s ，记k=s，其他所有点设为未标记的。
2）k 到其直接连接的未标记的点j 的距离，并设置：
d j =min[dj , dk +lkj ]
式中，l kj 是从点k 到j 的直接连接距离。
3）选取下一个点。从所有未标记的结点中，选取d j 中最小的一个i ：
d i =min[dj , 所有未标记的点j]
点i 就被选为最短路径中的一点，并设为已标记的。
4）找到点i 的前一点。从已标记的点中找到直接连接到i 的点j *，作为前一点，
设置： i=j*
5) 标记点i 。如果所有点已标记，则算法完全推出，否则，记k=i，转到2）再继续。
而程序中求两点间最短路径算法。其主要步骤是：
① 调用dijkstra 算法。
② 将path 中的第“终点”元素向上回溯至起点，并显示出来。
2.2 系统总体设计
2.2.1 系统设计目标
本次针对数据结构中图的关键路径的实现的程序设计实践不仅可以加深对课程内容的理解，更重要的是可以通过实践进一步掌握程序设计的技能与方法，初步感受软件开发过程的项目管理方法与规范，为更进一步的学习打下基础。数据结构是一门实践性很强的学科。良好的系统设计和分析能力的培养需要通过长期、系统的训练(包括理论和实践两方面) 才能获得。
1) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本
方法和技能；
2) 训练学生灵活应用所学数据结构的基本知识，熟练的完成问题分析、算
法设计、编写程序，求解出指定的问题；
3) 训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生
的理论知识，提高编程水平，并在此过程中培养严谨的科学态度和良好
的工作作风；
4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力。
2.2.2 开发设计思想
基于以上系统设计目标，本文在系统时遵循了以下开发设计思想:
1. 尽量采用现有软硬件环境，及先进的管理系统开发方案，从而达到充分利用现有资源，提高系统开发水平，来达到应用效果的目的。
2. 系统应符合采购、发放、库存的规定，满足企事业日常工作需要，并达到操作过程中的直观、方便、实用、安全等要求。
3. 系统采用模块化程序设计方法，既便于系统功能的各种组合和修改，又便于未参与开发的技术维护人员补充、维护。
4. 系统应具备数据库维护功能，及时根据用户需求进行数据添加、删除、修改等操作。
2.2.3 系统功能模块设计
图2.1 功能模块图
2.3 算法思想描述
1. Kruskal函数：
因为Kruskal 需要一个有序的边集数组，所以要先对边集数组排序。其
次，在执行中需要判断是否构成回路，因此还需另有一个判断函数seeks ，在Kruskal 中调用seeks 。
2. dijkstra函数：
因为从一源到其余各点的最短路径共有n-1条，因此可以设一变量vnum 作为计数器控制循环。该函数的关键在于dist 数组的重新置数。该置数条件是：该顶点是被访问过，并且新起点到该点的权值加上新起点到源点的权值小于该点原权值。因此第一次将其设为：if （s[w]==0&&cost[u][w]+dist[u]
3. printpath1函数：
该函数主要用来输出源点到其余各点的最短路径。因为在主函
数调用该函数前，已经调用了dijkstra 函数，所以所需的dist 、path 、s 数组已经由dijkstra 函数生成，因此在该函数中，只需用一变量控制循环，一一将path 数组中的每一元素回溯至起点即可。其关键在于不同情况下输出形式的不同。
4.printpath2函数：
该函数主要用来输出两点间的最短路径。其主要部分与printpath1函数相同，只是无需由循环将所有顶点一一输出，只需将path 数组中下标为v1的元素回溯至起点并显示出来。
第三章算法实现
3.1 数据结构 ·3.1.1
存储结构定义一个结构体数组，其空间足够大，可将输入的字符串存于
数组中。 struct ees {int bv; int tv; int w; };
3.2 程序模块
1.insertsort 函数（时间复杂度为O(n)）
图3.1 insertsort函数流程图
2．Kruskal 函数（时间复杂度为O(nlogn)）
图3.2 Kruskal 函数流程图
3. dijkstra函数（时间复杂度为O(n)）
图3.3 dijkstra函数流程图
4. printpath1函数（时间复杂度为O(n)）
图3.4 printpath1函数流程图
5. printpath2函数（时间复杂度为O(n)）
图3.5 printpath2函数流程图
3.3 各模块之间的调用关系
3.6各模块之间的调用关系
3.4 源程序代码
#define MAXE 100
struct edges/*边集类型, 存储一条边的起始顶点bv 、终止顶点tv 和权
w*/ {int bv; int tv; int w; };
typedef struct edges edgeset; int seeks(int set[],int v) { int i;
i=v; while(set[i]>0) i=set[i]; return i; }
void kruskal(edgeset ge[],int n,int e) /*ge表示的图是按权值从小到大排列的*/ {
int set[MAXE],v1,v2,i,j;
for(i=1;i
set[i]=0;
i=1; j=1;
while(j
v1=seeks(set,ge[j].bv); /*确定顶点v 所在的连通集*/
v2=seeks(set,ge[j].tv);
if(v1!=v2) /*当v1,v2不在同一顶点集合, 确定该边应当选入生成树*/ {
printf("(%d,%d):%d\n",ge[j].bv,ge[j].tv,ge[j].w);
set[v1]=v2; i++; } }
void insertsort(edgeset ge[],int e) { int i,j; } j++;
for(i=2;i
ge[0]=ge[i];
j=i-1;
while(ge[0].w
ge[j+1]=ge[j];
j--; }
ge[j+1]=ge[0]; } } void
dijkstra(int
cost[MAXE][MAXE],int
dist[MAXE],int
path[MAXE],int s[MAXE],int n,int v0) //求两个点之间的最短路径 {
int u,vnum,w,wm;
for(w=1;w
dist[w]=cost[v0][w];
if(cost[v0][w]
vnum=1; while(vnum
wm=32767;
u=v0;
for(w=1;w
wm=dist[w]; }
s[u]=1; vnum++;
for(w=1;w
if(s[w]==0&&dist[u]+cost[u][w]
dist[w]=dist[u]+cost[u][w];
path[w]=u; } }
void printpath1(int dist[],int path[],int s[],int n,int v0) //printpath1 函数 {
int i,k; }
for(i=1;i
if(s[i]==1) { k=i;
while(k!=v0) {
printf("%d
k=path[k]; }
printf("%d:%d\n",k,dist[i]); }
else
printf("%d
void printpath2(int dist[],int path[],int v0,int v1) //printpath2 函数 { int k;
k=v1; while(k!=v0) {
printf("%d
k=path[k]; }
printf("%d:%d\n",k,dist[v1]); }
main()//输入顶点的个数，边的信息 {
edgeset ge[MAXE];
int
cost[MAXE][MAXE],dist[MAXE],path[MAXE],s[MAXE],a,n,e,i,j,k,v0,v1;
printf("请输入顶点个数:"); scanf("%d",&n);
printf("请输入边的条数:"); scanf("%d",&e);
printf("请输入边的信息（起点，终点，权值）:\n"); for(i=1;i
scanf("%d,%d,%d",&ge[i].bv,&ge[i].tv,&ge[i].w); printf("在下列菜单中进行选择：\n");
printf("1.kruskal算法（（起点，终点）权值）：\n"); printf("2.shortpath（终点
printf("3.shortpath between two point（终点
{ {
case 1:insertsort(ge,e); kruskal(ge,n,e); break;
case 2:printf("请输入起始顶点序号:"); scanf("%d",&v0); for(i=1;i
i=ge[k].bv; switch(a)
j=ge[k].tv; cost[i][j]=ge[k].w; }
for(i=1;i
dijkstra(cost,dist,path,s,n,v0); printpath1(dist,path,s,n,v0);
break;
case 3:printf("请输入起始顶点序号:"); scanf("%d",&v0); printf("请输入终点序号:"); scanf("%d",&v1); for(i=1;i
i=ge[k].bv;
j=ge[k].tv;
cost[i][j]=ge[k].w;
}
for(i=1;i
s[i]=0;
s[v0]=1;
dijkstra(cost,dist,path,s,n,v0); printpath2(dist,path,v0,v1); break; }
printf("在下列菜单中进行选择：\n");
printf("1.kruskal算法（（起点，终点）权值）：\n"); printf("2.shortpath（终点
printf("3.shortpath between two point（终点
第四章测试与分析
4.1 测试数据选择
顶点个数：6 边的个数：10
边的信息（起点 终点 权值）： 1 2 6；1 31；1 4 5；2 3 5；2 5 3； 3 4 5；3 5 6；3 6 4；4 6 2；5 6 6；
·4.2 测试结果分析 ·4.2.1 调试过程
在调试程序时主要遇到一下几类问题： 1. 有时函数中一些数组中的数据无法存储。 2. 对其进行检验发现没有申请空间大小。
3. 在源程序的开头用#define定义数值大小，在使用数组时亦可知道它的空间大小。
4. 此函数中有时出现负值。
5. 对其进行检验发现在程序中∞由32767代替。若cost[u][w]==32767，那么cost[u][w]+dist[u]肯定溢出主负值，因此造成权值出现负值。
6. 但是当cost[u][w]==32767，那么dist[w]肯定不需要重新置数。所以将if （
s[w]==0&&cost[u][w]+dist[u]
）
改
为
：
if(s[w]==0&&cost[u][w]+dist[u]
·4.2.2
程序执行过程
系统使用说明：
1. 输入的数据可以是整数，字符串（如1,2,3）；
2. 本系统可以建立带权图，并能够用Kruskal 算法求改图的最小生成树。而且能够选择图上的任意一点做根结点。还能够求两点之间的最短距离。 3. 该系统会有菜单提示，进行选项： 1.kruskal 2.shortpath
3.shortpath between two point 4.exit
4. 程序实际运行截图
图4.1 输入形式
图4.2 kruskal算法输出
图4.3 最短距离输出
总 结
数据结构是计算机专业的一门专业基础课，设计到计算机软、硬件等各方面的知识，如计算机硬件范围的存储装置和存取方法；计算机软件范围的数据的动态存储与管理，信息检索等。更重要的是，它能实现程序算法和实际高效的结合。 其实我在编程方面并不擅长，水平有限，在程序设计上存在不少缺陷，并且程序如何与实际项目相结合，还需进一步探索。尽管如此，经过了这次图的关键路径的实现的课程设计我从中学到了很多, 不仅是对于一个成熟的程序的构思，还有算法的规范化、高效化，以及如何将算法合理的应用于工程项目中，这是一个关键的环节. 还有就是程序设计和运行测试中遇到的问题该如何解决, 从解决问题中我也学到了许多平时课本上所没有的知识. 当然, 能够实现图的关键路径我自己也感觉有一定的成就感。
在编写源程序代码的过程中对语言的运用还需要提高, 应使写出来的程序更加简洁, 易读懂, 更加满足实际工作的需要. 要想使做出来的程序更好的利用还需根据实际需要在今后的运用中不断的改进和完善。
心得体会
经过我们不懈的努力我们终于完成了本次课程设计，通过这次课程设计，我感觉到要真正做出一个程序并不很容易，但只要用心去做，总会有收获，特别是当我遇到 一个问题，想办法去解决，最后终于找到方法时，心里的那份喜悦之情真是难以形容。编写程序中遇到问题再所难免，应耐心探究其中的原因，从出现问题的地方起，并联系前后程序，仔细推敲，逐个排查。直到最终搞清为止。我们本次做的是图的做小生成树问题，深刻的体会到它的实用性。通过本次课程设计我们发现我们对于C 语言和数据结构还有很多地方不知道，今后需要努力学习。
参考文献
[1]严蔚敏/吴伟民 数据结构（c 语言版） 北京：清华大学出版社 1997.4
[2] 李春葆/曾慧/张植民 数据结构程序设计题典 北京：清华大学出版社
2002.5
河南城建学院
课
程设计 报告书
专 业：计算机科学与技术
课程设计名称：《数据结构课程设计》
题 目：最小生成树问题
班 级：
学 号：
姓 名：
同 组 人 员:
指 导 老 师：
完 成 时 间： 2012年2月17日
摘要
本课程设计主要解决图的关键路径的实现。在项目管理中，编制网络计划的基本思想就是在一个庞大的网络图中找出关键路径，并对各关键活动，优先安排资源，挖掘潜力，采取相应措施，尽量压缩需要的时间。而对非关键路径的各个活动，只要在不影响工程完工时间的条件下，抽出适当的人力、物力和财力等资源，用在关键路径上，以达到缩短工程工期，合理利用资源等目的。在执行计划过程中，可以明确工作重点，对各个关键活动加以有效控制和调度。关键路径法将项目分解成为多个独立的活动并确定每个活动的工期，然后用逻辑关系（结束-开始、结束-结束、开始-开始和开始结束）将活动连接，从而能够计算项目的工期、各个活动时间特点（最早最晚时间、时差）等。在关键路径法的活动上加载资源后，还能够对项目的资源需求和分配进行分析。
在本程序设计中，要求实现图的关键路径，最小生成树，判断两点之间是否有路径，程序由2个模块组成，分别为主函数的创建及其他相关函数的设计。程序通过调试运行，初步实现了设计目标。在课程设计中，系统开发平台为Windows 2000，程序设计设计语言采用Visual C++，程序运行平台为Windows 98/2000/XP。
关键词 程序设计； C++；图；关键路径
目录
目录 .................................................................................................................................. - 3 -
第一章 开发环境和开发工具 . ......................................................................................... 4
1.1 C/ C ++语言简介 . ............................................................................................... 4
1.1 开发背景 . ............................................................................................................. 4
1.3 开发环境 ................................................................................................................ 5
第二章 算法思想 ............................................................................................................... 6
2.1 系统需求分析 ............................................................................................................... 6
2.2 系统总体设计 ......................................................................................................... 7
2.2.1 系统设计目标 ............................................................................................. 7
2.2.2 开发设计思想 ............................................................................................. 7
2.2.3 系统功能模块设计 ..................................................................................... 9
2.3 算法思想描述 ......................................................................................................... 9
第三章 算法实现 . ........................................................................................................... 11
3.1 数据结构 . ........................................................................................................... 11
3.2 程序模块 ............................................................................................................... 12
1.insertsort 函数 ........................................................................................................... 12
3.3 各模块之间的调用关系 ....................................................................................... 17
3.4 源程序代码 ........................................................................................................... 17
第四章 测试与分析 . ....................................................................................................... 27
4.1 测试数据选择 ....................................................................................................... 27
总 结 ............................................................................................................................. 30
心得体会 ............................................................................................................................. 31
参考文献 ..................................................................................................................... 32
第一章 开发环境和开发工具
1.1 C/ C ++语言简介
C 语言是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言的特点。它由美国贝尔研究所的D.M.Ritchie 于1972年推出。1978后，C 语言已先后被移植到大、中、小及微型机上。它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。它的应用范围广泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类科研都需要用到C 语言，适于编写系统软件，三维，二维图形和动画。具体应用比如单片机以及嵌入式系统开发
C++语言是一种优秀的面向对象程序设计语言，它在C 语言的基础上发展而来，但它比C 语言更容易为人们学习和掌握。C++以其独特的语言机制在计算机科学的各个领域中得到了广泛的应用。面向对象的设计思想是在原来结构化程序设计方法基础上的一个质的飞跃，C++完美地体现了面向对象的各种特性。
1.1 开发背景
数据结构课程是计算机专业最重要的基础课之一，主要研究分析计算机存储、组织数据的方式，使学生能够根据数据对象的特征，选择适当的数据结构、存储结构及相应算法，初步掌握各种算法在时间和空间上的分析技巧，并能够进行算法和程序设计，使所涉及的程序结构清楚，正确易读[3]。数据的组织方法和现实世界问题在计算机内部的表示方法，并能针对应用问题，选择合适的数据逻辑结构、存储结构及其算法，掌握解决复杂问题的程序设计方法和技术。选择合适的数据结构更容易设计出更高效运行或存储效率的算法；图是一种较线性表和树更为复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中的任意两个元素之间都可能相关。
在社会主义建设时期，各个城市建设问题尤其是网络建设尤为重要。在保证各个城市能互相连通的情况下，怎么保证建设网络，怎么建设最省钱是建设工程公司所需考虑的重大情况。从而能节省更多的钱来投资其他地方建设，如农村交通建设。
各个各个城市建设好之后，则可再根据将城市作为一个结点和其它城市再次运用最小生成树。
最小生成树则能有效的解决此问题。例如，以尽可能低的总价建设若干网络管道，把n 个城市联系在一起。
1.3 开发环境
本文所采用的开发环境主要是基于Windows XP系统，编程环境主要是在VC6.0++中。
第二章 算法思想
2.1 系统需求分析
根据课设题目要求，拟将整体程序分为三大模块。以下是三个模块的大体分析：
1. 要确定图的存储形式，通过对题目要求的具体分析。发现该题的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。
2. Kruskal 算法。该算法设置了集合A ，该集合一直是某最小生成树的子集。在每步决定是否把边（u,v ）添加到集合A 中，其添加条件是A ∪{（u,v ）}仍然是最小生成树的子集。我们称这样的边为A 的安全边，因为可以安全地把它添加到A 中而不会破坏上述条件。
3. Dijkstra 算法。算法的基本思路是：假设每个点都有一对标号（d j ,p j ）, 其中d 是从起源点到点j 的最短路径的长度（从顶点到其本身的最短路径是零路（没有弧的路），其长度等于零）；p j 则是从s 到j 的最短路径中j 点的前一点。求解从起源点s 到点j 的最短路径算法的基本过程如下：
1）初始化。起源点设置为：①d s =0,ps 为空；②所有其它点：d i =∞,p i =？；③标
记起源点s ，记k=s，其他所有点设为未标记的。
2）k 到其直接连接的未标记的点j 的距离，并设置：
d j =min[dj , dk +lkj ]
式中，l kj 是从点k 到j 的直接连接距离。
3）选取下一个点。从所有未标记的结点中，选取d j 中最小的一个i ：
d i =min[dj , 所有未标记的点j]
点i 就被选为最短路径中的一点，并设为已标记的。
4）找到点i 的前一点。从已标记的点中找到直接连接到i 的点j *，作为前一点，
设置： i=j*
5) 标记点i 。如果所有点已标记，则算法完全推出，否则，记k=i，转到2）再继续。
而程序中求两点间最短路径算法。其主要步骤是：
① 调用dijkstra 算法。
② 将path 中的第“终点”元素向上回溯至起点，并显示出来。
2.2 系统总体设计
2.2.1 系统设计目标
本次针对数据结构中图的关键路径的实现的程序设计实践不仅可以加深对课程内容的理解，更重要的是可以通过实践进一步掌握程序设计的技能与方法，初步感受软件开发过程的项目管理方法与规范，为更进一步的学习打下基础。数据结构是一门实践性很强的学科。良好的系统设计和分析能力的培养需要通过长期、系统的训练(包括理论和实践两方面) 才能获得。
1) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本
方法和技能；
2) 训练学生灵活应用所学数据结构的基本知识，熟练的完成问题分析、算
法设计、编写程序，求解出指定的问题；
3) 训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生
的理论知识，提高编程水平，并在此过程中培养严谨的科学态度和良好
的工作作风；
4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力。
2.2.2 开发设计思想
基于以上系统设计目标，本文在系统时遵循了以下开发设计思想:
1. 尽量采用现有软硬件环境，及先进的管理系统开发方案，从而达到充分利用现有资源，提高系统开发水平，来达到应用效果的目的。
2. 系统应符合采购、发放、库存的规定，满足企事业日常工作需要，并达到操作过程中的直观、方便、实用、安全等要求。
3. 系统采用模块化程序设计方法，既便于系统功能的各种组合和修改，又便于未参与开发的技术维护人员补充、维护。
4. 系统应具备数据库维护功能，及时根据用户需求进行数据添加、删除、修改等操作。
2.2.3 系统功能模块设计
图2.1 功能模块图
2.3 算法思想描述
1. Kruskal函数：
因为Kruskal 需要一个有序的边集数组，所以要先对边集数组排序。其
次，在执行中需要判断是否构成回路，因此还需另有一个判断函数seeks ，在Kruskal 中调用seeks 。
2. dijkstra函数：
因为从一源到其余各点的最短路径共有n-1条，因此可以设一变量vnum 作为计数器控制循环。该函数的关键在于dist 数组的重新置数。该置数条件是：该顶点是被访问过，并且新起点到该点的权值加上新起点到源点的权值小于该点原权值。因此第一次将其设为：if （s[w]==0&&cost[u][w]+dist[u]
3. printpath1函数：
该函数主要用来输出源点到其余各点的最短路径。因为在主函
数调用该函数前，已经调用了dijkstra 函数，所以所需的dist 、path 、s 数组已经由dijkstra 函数生成，因此在该函数中，只需用一变量控制循环，一一将path 数组中的每一元素回溯至起点即可。其关键在于不同情况下输出形式的不同。
4.printpath2函数：
该函数主要用来输出两点间的最短路径。其主要部分与printpath1函数相同，只是无需由循环将所有顶点一一输出，只需将path 数组中下标为v1的元素回溯至起点并显示出来。
第三章算法实现
3.1 数据结构 ·3.1.1
存储结构定义一个结构体数组，其空间足够大，可将输入的字符串存于
数组中。 struct ees {int bv; int tv; int w; };
3.2 程序模块
1.insertsort 函数（时间复杂度为O(n)）
图3.1 insertsort函数流程图
2．Kruskal 函数（时间复杂度为O(nlogn)）
图3.2 Kruskal 函数流程图
3. dijkstra函数（时间复杂度为O(n)）
图3.3 dijkstra函数流程图
4. printpath1函数（时间复杂度为O(n)）
图3.4 printpath1函数流程图
5. printpath2函数（时间复杂度为O(n)）
图3.5 printpath2函数流程图
3.3 各模块之间的调用关系
3.6各模块之间的调用关系
3.4 源程序代码
#define MAXE 100
struct edges/*边集类型, 存储一条边的起始顶点bv 、终止顶点tv 和权
w*/ {int bv; int tv; int w; };
typedef struct edges edgeset; int seeks(int set[],int v) { int i;
i=v; while(set[i]>0) i=set[i]; return i; }
void kruskal(edgeset ge[],int n,int e) /*ge表示的图是按权值从小到大排列的*/ {
int set[MAXE],v1,v2,i,j;
for(i=1;i
set[i]=0;
i=1; j=1;
while(j
v1=seeks(set,ge[j].bv); /*确定顶点v 所在的连通集*/
v2=seeks(set,ge[j].tv);
if(v1!=v2) /*当v1,v2不在同一顶点集合, 确定该边应当选入生成树*/ {
printf("(%d,%d):%d\n",ge[j].bv,ge[j].tv,ge[j].w);
set[v1]=v2; i++; } }
void insertsort(edgeset ge[],int e) { int i,j; } j++;
for(i=2;i
ge[0]=ge[i];
j=i-1;
while(ge[0].w
ge[j+1]=ge[j];
j--; }
ge[j+1]=ge[0]; } } void
dijkstra(int
cost[MAXE][MAXE],int
dist[MAXE],int
path[MAXE],int s[MAXE],int n,int v0) //求两个点之间的最短路径 {
int u,vnum,w,wm;
for(w=1;w
dist[w]=cost[v0][w];
if(cost[v0][w]
vnum=1; while(vnum
wm=32767;
u=v0;
for(w=1;w
wm=dist[w]; }
s[u]=1; vnum++;
for(w=1;w
if(s[w]==0&&dist[u]+cost[u][w]
dist[w]=dist[u]+cost[u][w];
path[w]=u; } }
void printpath1(int dist[],int path[],int s[],int n,int v0) //printpath1 函数 {
int i,k; }
for(i=1;i
if(s[i]==1) { k=i;
while(k!=v0) {
printf("%d
k=path[k]; }
printf("%d:%d\n",k,dist[i]); }
else
printf("%d
void printpath2(int dist[],int path[],int v0,int v1) //printpath2 函数 { int k;
k=v1; while(k!=v0) {
printf("%d
k=path[k]; }
printf("%d:%d\n",k,dist[v1]); }
main()//输入顶点的个数，边的信息 {
edgeset ge[MAXE];
int
cost[MAXE][MAXE],dist[MAXE],path[MAXE],s[MAXE],a,n,e,i,j,k,v0,v1;
printf("请输入顶点个数:"); scanf("%d",&n);
printf("请输入边的条数:"); scanf("%d",&e);
printf("请输入边的信息（起点，终点，权值）:\n"); for(i=1;i
scanf("%d,%d,%d",&ge[i].bv,&ge[i].tv,&ge[i].w); printf("在下列菜单中进行选择：\n");
printf("1.kruskal算法（（起点，终点）权值）：\n"); printf("2.shortpath（终点
printf("3.shortpath between two point（终点
{ {
case 1:insertsort(ge,e); kruskal(ge,n,e); break;
case 2:printf("请输入起始顶点序号:"); scanf("%d",&v0); for(i=1;i
i=ge[k].bv; switch(a)
j=ge[k].tv; cost[i][j]=ge[k].w; }
for(i=1;i
dijkstra(cost,dist,path,s,n,v0); printpath1(dist,path,s,n,v0);
break;
case 3:printf("请输入起始顶点序号:"); scanf("%d",&v0); printf("请输入终点序号:"); scanf("%d",&v1); for(i=1;i
i=ge[k].bv;
j=ge[k].tv;
cost[i][j]=ge[k].w;
}
for(i=1;i
s[i]=0;
s[v0]=1;
dijkstra(cost,dist,path,s,n,v0); printpath2(dist,path,v0,v1); break; }
printf("在下列菜单中进行选择：\n");
printf("1.kruskal算法（（起点，终点）权值）：\n"); printf("2.shortpath（终点
printf("3.shortpath between two point（终点
第四章测试与分析
4.1 测试数据选择
顶点个数：6 边的个数：10
边的信息（起点 终点 权值）： 1 2 6；1 31；1 4 5；2 3 5；2 5 3； 3 4 5；3 5 6；3 6 4；4 6 2；5 6 6；
·4.2 测试结果分析 ·4.2.1 调试过程
在调试程序时主要遇到一下几类问题： 1. 有时函数中一些数组中的数据无法存储。 2. 对其进行检验发现没有申请空间大小。
3. 在源程序的开头用#define定义数值大小，在使用数组时亦可知道它的空间大小。
4. 此函数中有时出现负值。
5. 对其进行检验发现在程序中∞由32767代替。若cost[u][w]==32767，那么cost[u][w]+dist[u]肯定溢出主负值，因此造成权值出现负值。
6. 但是当cost[u][w]==32767，那么dist[w]肯定不需要重新置数。所以将if （
s[w]==0&&cost[u][w]+dist[u]
）
改
为
：
if(s[w]==0&&cost[u][w]+dist[u]
·4.2.2
程序执行过程
系统使用说明：
1. 输入的数据可以是整数，字符串（如1,2,3）；
2. 本系统可以建立带权图，并能够用Kruskal 算法求改图的最小生成树。而且能够选择图上的任意一点做根结点。还能够求两点之间的最短距离。 3. 该系统会有菜单提示，进行选项： 1.kruskal 2.shortpath
3.shortpath between two point 4.exit
4. 程序实际运行截图
图4.1 输入形式
图4.2 kruskal算法输出
图4.3 最短距离输出
总 结
数据结构是计算机专业的一门专业基础课，设计到计算机软、硬件等各方面的知识，如计算机硬件范围的存储装置和存取方法；计算机软件范围的数据的动态存储与管理，信息检索等。更重要的是，它能实现程序算法和实际高效的结合。 其实我在编程方面并不擅长，水平有限，在程序设计上存在不少缺陷，并且程序如何与实际项目相结合，还需进一步探索。尽管如此，经过了这次图的关键路径的实现的课程设计我从中学到了很多, 不仅是对于一个成熟的程序的构思，还有算法的规范化、高效化，以及如何将算法合理的应用于工程项目中，这是一个关键的环节. 还有就是程序设计和运行测试中遇到的问题该如何解决, 从解决问题中我也学到了许多平时课本上所没有的知识. 当然, 能够实现图的关键路径我自己也感觉有一定的成就感。
在编写源程序代码的过程中对语言的运用还需要提高, 应使写出来的程序更加简洁, 易读懂, 更加满足实际工作的需要. 要想使做出来的程序更好的利用还需根据实际需要在今后的运用中不断的改进和完善。
心得体会
经过我们不懈的努力我们终于完成了本次课程设计，通过这次课程设计，我感觉到要真正做出一个程序并不很容易，但只要用心去做，总会有收获，特别是当我遇到 一个问题，想办法去解决，最后终于找到方法时，心里的那份喜悦之情真是难以形容。编写程序中遇到问题再所难免，应耐心探究其中的原因，从出现问题的地方起，并联系前后程序，仔细推敲，逐个排查。直到最终搞清为止。我们本次做的是图的做小生成树问题，深刻的体会到它的实用性。通过本次课程设计我们发现我们对于C 语言和数据结构还有很多地方不知道，今后需要努力学习。
参考文献
[1]严蔚敏/吴伟民 数据结构（c 语言版） 北京：清华大学出版社 1997.4
[2] 李春葆/曾慧/张植民 数据结构程序设计题典 北京：清华大学出版社
2002.5