内容发布更新时间 : 2024/12/26 1:55:27星期一 下面是文章的全部内容请认真阅读。
数据结构课程设计实验报告
班级：10010706 姓 名：杨德刚 学 号：2007302415 电 话 ：15891480939 日期：2008.11.4
第一部分：求最短路径
◎实验题目: 求最短路径
◎实验目的：通过编写程序，加强对网的结构建立和最短路径算法
◎实验内容：已知n个顶点的有向网的顶点为V1, V2, V3, …,Vn,其代价矩阵定义为Dn×n=dij,描述如下：dij表示顶点i到顶点j的距离。编写程序，找出任意两个顶点之间的最短路径并输出路径及路径长度。
能够建立有向网的储存结构，输入任意两个顶点，均能找出它们之间的最短路径。 一、程序形式
1． 本演示程序中，进入运行界面，程序提示输入操作和数据存放文件名及起终点，然后程序读入数据后建立有向网数据结构，输入完毕后输出结果。 2． 程序执行的命令包括：
（1）输入要进行的操作和数据存放文件名 （2）构造有向网 （3）输入起终点并求得最短路径 （4）输出结果 （5）结束。 3． 程序数据存储格式： 6 （顶点个数）
v0 v1 v2 v3 v4 v5 （顶点名） 0 50 10 -1 45 -1 （边） -1 0 15 50 10 -1 20 -1 0 15 -1 -1 -1 20 -1 0 35 -1 -1 -1 -1 30 0 -1 -1 -1 -1 3 -1 0 4．运行界面：
二 概要设计
为了实现上述操作，可以以图为数据结构并以邻接矩阵为其存储结构 1. 图定义
typedef char vnode;//顶点的名字 typedef struct { vnode **vex; //图的顶点 int vexnum,arcnum; //图的顶点数和弧数 int **arc; // 图的弧 }ALGraph;
2. 各函数及其作用
1). 求得顶点在图中顶点数组中的下标函数 int locatevex(ALGraph *G,char *v1)
初始条件：图的顶点数组已经输入
操作结果：得到v1在图中顶点数组中的下标,并返回 2). 构造图函数（三元组）
void creatGraph(ALGraph *G,char *fi)
操作结果：输入各个顶点及弧的信息构造图(三元组) 3). 构造图函数（矩阵）
Void creatGraphm (ALGraph *G,char *fi)
操作结果：输入各个顶点及弧的信息构造图（矩阵） 4). 打印输出最短路径函数
void printpath(ALGraph *G,int i,int **p,long *d)
初始条件：图已经建立并且已求得最短路径 操作结果：输出以数组下标i为起点的最短路径 5). 求最短路径函数
void shortestpath(ALGraph *G,char *sou)
初始条件：图已经构造完毕，即各个顶点和狐的信息已经输入 操作结果：得到从sou始的所有顶点的最短路径 6).主函数 void main()
初始条件：各个基本操作已经实现，图已建立 操作结果：求得图的最短路径并输出 3． 本程序包含五个模块： （1） 主程序模块：main()
（2） 求得顶点在图中顶点数组中的下标模块: locatevex() （3） 构造图模块: creatGraph()或creatGraphm() （4） 打印输出最短路径模块 （5） 求最短路径模块 4.模块调用图：
主程序模块 Main() 构造图模块creatGraph() 或creatGraphm() 求最短路径模块 shortestpath() 求得顶点在图中顶点数组中的下标模块locatevex() 打印输出最短路径模块 printpath() 详细设计见源码。 三、主要算法
迪杰斯特拉算法，每次求得从i到某个顶点v的最短路径，直到求得到终点的最短路径。
for(k=1;k
if(final[de]==TRUE)break; //已经求得最短路径 }
四、实验总结
1.本次实验体会：
1）.程序要不断修改，即使是经典算法，但因为人的不同也会有不一样的效率。 2）.努力使程序增强对特殊情况的处理能力。 3）.尽量对不同情形提供多的应对策略。
4). 很多算法都有其特殊适用性，很少有完美的的算法。
2．算法设计思想：本算法为贪心算法，贪心算法一般地分阶段求解一个问题，在每个阶段它都把当前出现的当作是最好去处理,即局部的最优。
3. 算法的时空分析和改进设想：
本程序算法所用空间为图的邻接矩阵存储结构空间及辅助运算空间。求最短路径时间复杂度为O(n*n)。当用邻接表作存储结构时，可以缩短一些时间，但时间复杂度仍为0(n*n)。对于路径的记录方法，可以采用只记录每个顶点前面点的方法，这样可以倒推求得路径，同时可以节省存储空间和缩短程序运算时间。但是根本上时间复杂度仍不变为0(n*n)。本程序也可以用弗洛伊德算法，对于同一个图的最短路径问题，弗洛伊德算法O(n*n*n)可以一次求得所有点间的最短路径，可以不必像迪杰斯特拉算法那样对于同一个图每次都要重新求最短路径，但对于不同图两者都要重新执行，而且迪杰斯特拉算法时间复杂度要更小，所以对于同一个图求多个路径可能弗洛伊德算法要好一些，但对于不同图则迪杰斯特拉算法要优。
4．调试算法过程中出现的问题及改进方法：
1）.程序中有判断路径最大值（不通）与一个数相加后是否大于最大值的语句，如果定义最大值为0x7fffffff（整型最大正值），则与一个正数相加后变为负数，结果比最大值小的到错误结果，改进是以整型最大正值的一半视为不通的临界点，大于其则视为不通。 当然可视具体情况将路径长度类型改为long或unsigned int类型，但同样的问题依然会存在。
2）.当两点间无路径时若要求得最短路径时出错，可能是没有处理特殊情况的语句。一定要将特殊异常情况考虑在内。