数据结构课程设计报告_2

《数据结构课程设计报告_2》由会员分享，可在线阅读，更多相关《数据结构课程设计报告_2（22页珍藏版）》请在金锄头文库上搜索。

1、课程设计报告课程设计报告题目题目:在 n 个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用（邻接表和邻接矩阵）两种，采用课本上的两种求解算法。一、需求分析一、需求分析1.1 已知一个无向连通网表示 n 个城市以及城市间可能设置的通信网络线路， 其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相 应的代价。对于 n 个点的连通网能建立许多不同的生成树，每一棵生成树都可 以是一个通信网。我们要选择一棵生成树，使总的耗费最小。 1.2 该无向连通图的建立需要使用两种存储结构，即邻接表和邻接矩阵。 1.3 实现最小生成树需要使用两种算法。即普里姆算法和克鲁斯卡尔

2、。 1.4 程序通过人机交互实现数据的输入和输出。 1.5 测试数据（a,b）:2 ; (a,c):3; (a,d):4; (c,d):4; (b,d):5二二、概要设计、概要设计程序分为两大部分存储部分和算法部分；存储部分分为邻接矩阵和邻接表， 而且包含了两者直接的互相转换；算法部分分为普里母算法和克鲁斯卡尔算法。1.抽象数据类型图的定义如下抽象数据类型图的定义如下ADT Graph 数据对象 V;V 是具有相同特性的数据元素的集合，成为顶点集。 数据关系 R：R = VR VR = （v,w）|v,w 为 V 集合中的元素， （v,w）表示 v 和 w 之间存 在的路径 基本操作 P; C

3、reateMGraph(MGraph *G) 初始条件：V 是图的顶点集，VR 是图的边的集合。 操作结果：按 V 和 VR 的定义构造图 G，用邻接矩阵存储。 CreateALGraph(ALGraph *G) 初始条件：V 是图的顶点集，VR 是图的边的集合。 操作结果：按 V 和 VR 的定义构造图 G，用邻接表存储。LocateVex（G，u） 初始条件：图 G 存在，u 和 G 中顶点有相同的特征。 操作结果：若 G 中存在顶点 u，则返回该顶点在图中的位置；否则返回其 他信息。 MiniSpanTree_PRIM（G, u) 初始条件：图 G 存在，u 是图 G 中的一个顶点。 操

4、作结果：用普利姆算法从第 u 个顶点出发构造网 G 的最小生成树 T，输 出 T 的各条边。 Kriuskal(G) 初始条件：图 G 存在 操作结果：用克鲁斯卡尔算法构造图 G 的最小生成树 T，输出 T 的各条边。ListToMat(MGraph *G1,ALGraph *G2) 初始条件：图 G2 存在 操作结果：把图的邻接表存储结构转换为邻接矩阵存储结构，用图 G1 表示。MatToList(MGraph *G1,ALGraph *G2) 初始条件：图 G1 存在 操作结果：把图的邻接矩阵存储结构转换为邻接表存储结构，用图 G2 表示。LocateVex(MGraph *G,Verte

5、xType u) 初始条件：图G存在，u和G中顶点有相同特征 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1 ADT Graph2.主程序主程序void main() 创建图 G，并按不同的存储结构输出。 对图的存储结构进行转换 使用算法构造最小生成树并输出各边 3.模块间的调用关系模块间的调用关系主模块子模块三、详细设计三、详细设计1.图和顶点的定义图和顶点的定义#define OK 1 #define ERROR 0 #define TURE 1 #define FALSE 0 #define OVERFLOW -1 #define INFEASIBLE -2 typed

6、ef int Status; #define INFINITY 32767 /两地之间没有架设线路的权值为最大数。 #define MAX_VERTEX_NUM 20 /城市的数目最大为 20 #define MAX_NAME 5/城市名称的最大长度为 5typedef char VertexTypeMAX_NAME;/城市的名称用字符数组存储 typedef int VRType; /两城市间的关系类型1.1 邻接矩阵存储表示的图的结构体类型的定义 typedef struct ArcCell VRType adj;/*顶点关系类型。对无权图，用 1（是）或 0(否）表示相邻否*/*对带权全

7、图，则为权值类型*/ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct VertexType vexsMAX_VERTEX_NUM; /*顶点向量*/AdjMatrix arcs; /*邻接矩阵*/int vexnum,arcnum; /*图的当前顶点数和弧数*/MGraph;1.2 邻接表类型存储表示的图的结构体类型的定义 typedef struct ANode /* 弧的结点结构类型 */ int end; /弧尾在邻接表头结点中的位置int begin; /弧头在邻接表头结点中的位置 int weight; /*

8、该弧的相关信息,这里用于存放权值 */struct ANode *nextarc; /* 指向下一条弧的指针 */ ANode; typedef struct Vnode /* 邻接表头结点的类型 */ VertexType vertex; /* 顶点信息，城市名称 */int bianhao; /城市在邻接表头结点数组中的相应编号ANode *firstarc; /* 指向第一条弧 */ VNode,AdjListMAX_VERTEX_NUM; /* AdjList 是邻接表类型 */ typedef struct AdjList adjlist; /* 邻接表 */int vexnum,a

9、rcnum; /* 图中顶点数 n 和边数 e */ ALGraph; 2.Prim 算法的思想算法的思想假设 V 是图中顶点的集合 ,E 是图中边的集合 ,TE 为最小生成树中的边的集合,则 prim 算法通过以下步骤可以得到最小生成树 : （1）初始化:U=u 0,TE=f。此步骤设立一个只有结点 u 0 的结点集 U 和一个空的边集 TE 作为最小生成树的初始形态 ,在随后的算法执行中 ,这个 形态会不断的发生变化 ,直到得到最小生成树为止。 （2）在所有 uU,vVU 的边(u,v)E 中,找一条权最小的边 (u 0,v 0)， 将此边加进集合 TE 中，并将此边的非 U 中顶点加入

10、U 中。此步骤的功能是 在边集 E 中找一条边,要求这条边满足以下条件 :首先边的两个顶点要分别 在顶点集合 U 和 VU 中,其次边的权要最小。找到这条边以后 ,把这条边放 到边集 TE 中,并把这条边上不在 U 中的那个顶点加入到 U 中。这一步骤在 算法中应执行多次 ,每执行一次,集合 TE 和 U 都将发生变化 ,分别增加一条 边和一个顶点 ,因此,TE 和 U 是两个动态的集合 ,这一点在理解算法时要密切 注意。 （3）如果 U=V,则算法结束;否则重复步骤 2。可以把本步骤看成循环终止 条件。我们可以算出当 U=V 时,步骤 2 共执行了 n1 次(设 n 为图中顶点的 数目),T

11、E 中也增加了 n1 条边,这 n1 条边就是需要求出的最小生成树的 边。 Prim 算法假设网中有 N 个顶点，则第一个进行初始化的循环语句频度为 n，第 二个循环语句的频度为 n-1。其中有两个内循环；由此普里母算法的时间复杂 度为 O(n2),与网中的边数无关！3.克鲁斯卡尔算法的思想为克鲁斯卡尔算法的思想为假设 WN=(V,E) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔 算法构造最小生成树的过程为： （1）先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶 点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。 （2）从网的边集 E 中选取一条权值最小的边

12、，若该条边的两个顶点分属不 同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成 一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该 取下一条权值最小的边再试之。（3）依次类推，重复上述操作，直至森林中只有一棵树，也即子图中含有 n-1条边为止。 克鲁斯卡尔算法至多对 e 条边各扫描一次时间复杂度为 O（eloge） 。4.编写程序使用到的函数为编写程序使用到的函数为(a)程序中用来实现邻接矩阵和邻接表存储、输出以及互相转化的函数 Status InitALGraph(ALGraph *G) /初始化邻接表 void CreateALGraph(ALGraph *

13、G) /创建邻接表 Status InitMGraph(MGraph *G) /初始化邻接表 Status CreateMGraph(MGraph *G) /创建邻接表 Status MatToList(MGraph *G1,ALGraph *G2) /将邻接矩阵G1转换成邻接表G2 Status ListToMat(MGraph *G1,ALGraph *G2) /将邻接表G1转换成邻接矩阵G2 Status PrintMGraph(MGraph *G) /输出邻接矩阵g Status PrintALGraph(ALGraph *G) /输出邻接表G (b)程序中用来完成prim和krius

14、kal算法的函数 int mininum(minside closedge,MGraph *G) / 求closedege数组中lowcost的最小正值 void MiniSpanTree_PRIM(MGraph *G,VertexType u) / 用普利姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边void InsertSort(EdgeType E,int n) /对E0.n-1按权值递增有序的进行直接插入排序 void Kriuskal(ALGraph *G) /克鲁斯卡尔算法 (c) 查找顶点U在图中的位置 int LocateVex(MGraph *G,VertexT

15、ype u) /查找顶点U在图中的位置5.主函数模块为：主函数模块为：void main() 定义邻接矩阵存储结构的图； 定义邻接表存储结构的图；选择一种存储结构画出图，并输出； 邻接矩阵和邻接表相互转化，得到两种类型的存储图，并输出转换后的图；选择一种算法得到最小生成树并输出生成树的各边。 6.模块间的调用层次模块间的调用层次四、编码与测试四、编码与测试这个阶段主要是对代码的编写及代码正确性的检验。通过前面的详细设计 的分析，这个阶段是完成各个函数的功能， 在编程的过程中出现了许多的错误，导致功能的无法实现，出现的错误主 要有及心的： 1.对于结构体的成员的调用心得：结构体变量名调用函数时使用符号.,对于结构体指针使用符号 -或者是先使用*取得变量名在使用.调用成员。 2.函数调用时指针的传递心得：这个主要是C+与C语言的区别，在C+中函数的参数中有 (a,c):3; (a,d):4; (c,d):4; (b,d):5采用邻接表存储的输入及邻接表转换为邻接矩阵并显示采用邻接表存储的输入及邻接表转换为邻接矩阵并显示通过通过 Prim 算法显示最小生成树的各边算法显示最小生成树的各边采用邻接矩阵存储的输入采用邻接矩阵存储的输入邻接矩阵转换为邻接表并显示及通过邻接矩阵转换为邻接表并显示及通