1、 - 1 - 数据结构课程设计报告 原题重现：原题重现： 课题课题 5：管道铺设施工的最佳方案选择：管道铺设施工的最佳方案选择 N(N10)个居民之间需要铺设煤气管道。假设任意两个居民个居民之间需要铺设煤气管道。假设任意两个居民 之间都可以铺设煤气管道， 但代价不同。 事先将任意两个居民之之间都可以铺设煤气管道， 但代价不同。 事先将任意两个居民之 间铺设煤气管道的代价存入磁盘文件中。 设计一个最佳方案使得间铺设煤气管道的代价存入磁盘文件中。 设计一个最佳方案使得 这这 N 个居民之间铺设煤气管道所需代价最少，并希望以图形方个居民之间铺设煤气管道所需代价最少，并希望以图形方 式在屏幕上输出结果
2、。式在屏幕上输出结果。 一、算法思想一、算法思想 1,数据结构设计数据结构设计 （1） 代价文件的结构代价文件的结构 代价文件代价文件主要主要存储存储 表示表示 N(N10) 个居民个居民的符号的符号,以及以及 两个居民之间铺设煤气管道的代价两个居民之间铺设煤气管道的代价。除此之外代价文。除此之外代价文 件是用来件是用来得到图的存储结构得到图的存储结构的，考虑到图的，考虑到图的的存储结构存储结构 定义定义中有中有 vexsN数组存储顶点，以及数组存储顶点，以及 arcsNN数组数组 存储边，存储边，vexnum,arcnum 这两个变量分别表示顶点数这两个变量分别表示顶点数 和边数；最后考虑格
3、式。和边数；最后考虑格式。 所以综合以上考虑代价文件的结构如下：所以综合以上考虑代价文件的结构如下： 第一行存顶第一行存顶 点个数，边的个数；接下来存顶点点个数，边的个数；接下来存顶点，也就是表示居民，也就是表示居民 的符号，第二行的符号，第二行 A，第三行，第三行 B，第四行，第四行 ；然后；然后 存存边边和和边边的的权权值值（例如（例如 A B 32A B 32）以）以这这种形式种形式存放到磁存放到磁 盘文件中。盘文件中。 - 2 - （2） 图的存储结构：邻接矩阵。图的存储结构：邻接矩阵。 邻接矩阵是表示图形中顶点之间相邻关系的矩阵。 一个邻接矩阵是表示图形中顶点之间相邻关系的矩阵。 一
4、个 图图的邻接矩阵是唯一的。图的邻接矩阵表示，除了需要的邻接矩阵是唯一的。图的邻接矩阵表示，除了需要 用一个二维数组用一个二维数组存储顶点之间的相邻关系的邻接矩阵存储顶点之间的相邻关系的邻接矩阵 外， 通常还需要使用一个具有外， 通常还需要使用一个具有 n个元素的一维数组来存个元素的一维数组来存 储顶点信息，其中下标为储顶点信息，其中下标为 i 的元素存储顶点的元素存储顶点 vi 的信息。的信息。 因此，图的邻接矩阵的存储结构定义如下：因此，图的邻接矩阵的存储结构定义如下： #define N 20 #define INFINITY 9999 typedef struct char vexsN; int arcsNN; int vexnum,arcnum; MGraph; （3） 最小生成树的存储结构最小生成树的存储结构 因为准备采用因为准备采用 prime 算法，所以存储结构定义如下：算法，所以存储结构定义如下： typedef struct char adjvex; int lowcost; close; close
