1、 数据结构（C 语言）课程设计 题目：关键路径关键路径 班级： 姓名： 学号： 日期： 一实习目的 通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括 系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的 选择、设计、实现以及操作方法，为进一步的应用开发打好基础。 二问题描述 设计、实现从图的某一点到其余各点的关键路径。 三需求分析 需要输入图的领接矩阵，并且输入开始的顶点， 实现这个顶点到图中其余各点的关键路径。 四概要设计 领接矩阵是表示定点之间相邻关系的矩阵，设 G=（V，E）是具有 n个顶点的 图，则 G 的领接矩阵是具有如下性质的 n阶方阵： A=（aij）n*n
2、其中 aij = 0,若从 vi 到 vj 无边相连; aij = w,若从 vi 到 vj 有边相连且此边的权为 w; Dijkstra 算法的基本思想是从 vs 出发，逐步地向外探寻最短路。执行过程中， 于每个点对应，记录下一个数，他表示从 vs 到该点的最短路的权。 五详细设计及代码， #include #include void Dijkstra(int n,int v,int dist,int prev,int *cost) int u=v; int i; int j; int maxint = 1000; /定义一个最大的数值，作为不 相连的两个节点的代价权值 int *s; /具
3、有最短路径的节点子集 s. s=(int *)malloc(sizeof(int) * n); /初始化最小路径代 价和前一跳节点值 for(i=1;i“,wayj); printf(“%dn“,u); void main() int i,j,t; int n,v,u; int *cost; /代价矩阵 int *dist; /最短路径代价 int *prev; /前一跳节点空间 printf(“please intput the node number: “); scanf(“%d“, printf(“please intput the cost status:n“); cost=(int
4、*)malloc(sizeof(int)*(n+1); for(i = 1;i=n;i+) costi = (int *)malloc(sizeof(int)*(n+1); / 输入代价矩阵 for(j = 1;j=n;j+) for(t=1;t=n;t+) scanf(“%d“, dist = (int *)malloc(sizeof(int)*n); prev = (int *)malloc(sizeof(int)*n); printf(“please input the source node: “); scanf(“%d“, Dijkstra(n,v,dist,prev,cost);
5、printf(“n“); printf(“Have confirm the best pathn“); printf(“n“); for(i=1;i=n;i+) if(i != v) printf(“the distance cost from node %d to node %d is %dn“,v,i,disti); printf(“the pre-node of node %d is node %d n“,i,previ); ShowPath(n,v,i,dist,prev); 六测试分析 1. 操作员管理功能. 开始按照 n个顶点的图输入n阶矩阵的 n的个数， 建立 n阶矩阵， 输入所
6、需 开始的顶点，即可得到这点到图中其余各顶点的关键路径。 七程序运行结果： 八项目进度及成绩评定 课题名称： 数据结构实习数据结构实习关键路径关键路径 完成者： 许晓博 1、 设计进度及完成情况 日 期 内 容 2010年12月 20 2010年12月 21 2010年12月 23 2010年12月 24 2、成绩评定： 设计成绩： 指导老师： 2010 年 月 日 日 期 内 容 2010年12月 20 参看关于图的生成的相关资料，理解了图、有向图和无向 图及其操作的概念和它的作用。 系统认识了图的生成的构造算法和对它的各种操作算法。 2010年12月 21 完成总体设计，划分了功能模块。 根据图和构造算法的特点设计好了程序使用的结构体。 2010年12月 23 骤个实现细分的功能模块。 完成各个功能模块的编
