管道铺设课程设计报告

编号 编号 江江 西西 理理 工工 大大 学学 数数据据结结构构课课程程设设计计报报告告 班班 级 级 学学 号 号 姓姓 名 名 时时 间 间 2015 年 6 月 22 日 2015 年 7 月 3 日 指导教师 指导教师 2015 年年 06 月月 目 录 一 摘要 3 二 引言 3 三 需求分析 3 四 概要设计 4 1 普利姆算法分析 6 2 模块分析 6 3 抽象数据类型分析 6 4 全部流程 6 五 详细设计 7 1 算法分析 7 一 信息输入模块 7 二 建立最小生成树并输出结果 8 2 源程序代码 9 六 测试结果 14 程序开始 14 信息输入 14 输出结果 14 七 设计体会 15 八 结束语 16 参考文献 16 一 摘要 N N 10 个居民区之间需要铺设煤气管道 假设任意两个居民区之间都可以铺 设煤气管道 但代价不同 问题的实质就是编写相应程序求解最小生成树问题 程序要求 事先任意两个居民区之间铺设煤气管道的代价存入磁盘文件中 设计一个最佳 方案使得这 N 个居民区之间铺设煤气管道所需代价最小 并将结果以图形方式在 屏幕上输出 二 引言 C 语言作为一门最通用的语言 从语言产生到现在 它已经成为最重要和最流行的 编程语言之一 在各种流行编程语言中 都能看到 C 语言的影子 学习掌握 C 语言 是每一个计算机技术人员的基本功之一 实际生活中最小生成树的问题具有很大的意义 例如 本文所讨论的构架居民 区之间铺设煤气管道代价最小 还有在若干地区铺设光缆等等 最小生成树让许多 诸如求造价最小 最短路径等最优化的现实问题找到了理论依据 并提供了有效的 解决方法 三 需求分析 在 N N 10 个居民区之间铺设煤气管道所需代价最小 即求最小生成树问 题 在我们的课本中介绍了两种求解方法 普利姆算法和克鲁斯卡尔算法 普利姆 算法与网的变数无关 适宜求解边稠密的网的最小生成树 而克鲁斯卡尔算法正 好相反 适宜求解边稀疏的最小生成树 由于在实际问题中 居民数量一般很有限 而任何两个居民区都可能有连线 即这样的图应该是边较为稠密的 因此 我们选择了普利姆算法对问题进行求解 四 概要设计 1 普利姆算法分析 1 普利姆算法思想 普利姆算法的思想是 在图中人去一个定点 k0 作为开始点 令 U k0 W V U 其中 V 为图中所有顶点集 然后找一个顶点在 U 中 另一个顶点在 w 中的边中最 短 的一条 找到后 将该边作为最小生成树的树边保存起来 并将该边顶点全部加入 U 集合中 并从 W 中删除这些顶点 然后重新调整 U 中顶点到 W 中顶点的距离 使之保持最小 再重复此过程 直到 W 为空集 2 算法过程描述 1 在图 G V E V 是顶点 E 是边 中 从集合 V 中任取一个顶点 如 k0 放入集合 U 中 这时 U k0 集合 T E 为空 2 从 k0 出发寻找与 U 中顶点相邻权值最小的边的另一顶点 k1 并使 k1 加入 U 即 U k0 k1 同时将该边加入集合 T E 中 3 重复 2 直到 U V 为止 4 这时 T E 中有 n 1 条边 T U T E 就是一一颗最小生成树 2 模块分析 根据对模型的功能分析 该管道铺设设计可以具有以下功能 1 管道铺设信息的输入 2 最小生成树信息的输出 功能模块图 3 抽象数据类型分析 areanum 居民区总数 顶点总数 edgenum 边的总数 date 20 邻接矩阵存储图结构 s 边的权值 short way i 居民区 i 到目前生成树中所有点集 U 中某个居民区的路程最小 值 near area i U 中能使其最小的居民区 5 全部流程全部流程 五 详细设计五 详细设计 1 算法分析 1 信息输入模块 读入图的信息 并将邻接矩阵输出 Void read 输入顶点个数和边的条数 Printf 请输入 定点数 变数 n Scanf d d 初始化邻接矩阵各元素值 Int i j k for i 0 i areanum i for j 0 j areanum j date i j INFINITY 读入边 Int from to s Printf 输入边 格式为 i j k 表示 i 到 j 的权值是 k n For i 0 i degenum i Scanf d d d date from to s date to from st 输出邻接矩阵 for i 0 i areanum i for j 0 j areanum j Printf d t date i j Printf n 2建立最小生成树并输出结果 用普里姆算法从第 u 个顶点出发构造网 G 的最小生成树 T 输出 T 的各条边 void MiniSpanTree PRIM MGraph G VertexType u system cls int i j k minside closedge k LocateVex G u for j 0 j G vexnum j 辅助数组初始化 if j k strcpy closedge j adjvex u closedge j lowcost G arcs k j adj closedge k lowcost 0 初始 U u printf 最小代价生成树的各条边为 n for i 1 i G vexnum i 选择其余 G vexnum 1 个顶点 k minimum closedge G 求出 T 的下一个结点 第 K 顶点 printf s s n closedge k adjvex G vexs k 输出生成树的边 closedge k lowcost 0 第 K 顶点并入 U 集 for j 0 j G vexnum j if G arcs k j adj closedge j lowcost 新顶点并入 U 集后重新选择最小边 strcpy closedge j adjvex G vexs k closedge j lowcost G arcs k j adj system pause 2 源程序代码 include include include include include define MAX VERTEX NUM 20 最大顶点个数 define MAX NAME 3 顶点字符串的最大长度 1 define MAX INFO 20 相关信息字符串的最大长度 1 define INFINITY INT MAX 用整型最大值代替 typedef int VRType typedef char InfoType typedef char VertexType MAX NAME 邻接矩阵的数据结构 typedef struct VRType adj 顶点关系类型 对无权图 用 1 是 或 0 否 表示相邻否 对带权图 则为权值类型 InfoType info 该弧相关信息的指针 可无 ArcCell AdjMatrix MAX VERTEX NUM MAX VERTEX NUM 图的数据结构 typedef struct VertexType vexs MAX VERTEX NUM 顶点向量 AdjMatrix arcs 邻接矩阵 int vexnum 图的当前顶点数 arcnum 图的当前弧数 MGraph 记录从顶点集 U 到 V U 的代价最小的边的辅助数组定义 typedef struct VertexType adjvex VRType lowcost minside MAX VERTEX NUM 若 G 中存在顶点 u 则返回该顶点在图中位置 否则返回 1 int LocateVex MGraph G VertexType u int i for i 0 i G vexnum i if strcmp u G vexs i 0 return i return 1 代价保存为文件 代价存入文件 void wenjian system cls FILE fp char s 50 ch strcpy s D record txt if fp fopen s ab NULL printf 无法打开此文件 n exit 0 else printf 请向磁盘中输入原点总数和边的总数 n printf 请输入顶点数边数 n scanf d d printf 请输入各居民点 for int i 1 i N i scanf c in fput G vexs i fp printf 请向磁盘中输入各原点和边的总数同时记录原点 目的点 及相 应的权值 输入 键表示结束 n printf 请向磁盘中输入各原点和边的总数 输入 键表示结束 n ch getchar while ch fputc ch fp ch getchar printf 请向磁盘中输入原点 目的点 及相应的权值 输入 键表示结束 n ch getchar while ch fputc ch fp ch getchar fclose fp system pause 从文件中得到信息构成图 void xianshi system cls FILE fp char s 50 ch strcpy s D record txt if fp fopen s r NULL printf 无法打开此文件 n exit 0 else while feof fp ch fgetc fp putchar ch putchar 10 fclose fp system pause 算法 7 2 P162 采用数组 邻接矩阵 表示法 构造无向网 G int CreateAN MGraph G system cls int i j k w char s MAX INFO info char info VertexType va vb printf 请输入无向网 G 的顶点数 边数 空格区分 scanf d d printf 请输入 d 个顶点的值 n G vexnum for i 0 i G vexnum i 构造顶点向量 scanf s G vexs i for i 0 i G vexnum i 初始化邻接矩阵 for j 0 j G vexnum j G arcs i j adj INFINITY 网初始化为无穷大 G arcs i j info NULL printf 请输入 d 条边的顶点 1 顶点 2 权值 以空格作为间隔 n G arcnum for k 0 k G arcnum k scanf s s d c va vb c 吃掉回车符 i LocateVex G va j LocateVex G vb G arcs i j adj G arcs j i adj w 无向 if IncInfo printf 请输入该边的相关信息 d 个字符 MAX INFO gets s w strlen s if w info char malloc w 1 sizeof char strcpy info s G arcs i j info G arcs j i info info 无向 printf 输出临接矩阵 n for i 0 i G vexnum i for j 0 j G vexnum j if j 3 0 printf n printf d G arcs i j adj return 1 system pause 求 closedge lowcost 的最小正值 int minimum minside SZ MGraph G int i 0 j k min while SZ i lowcost i min SZ i lowcost 第一个不为 0 的值 k i for j i 1 j0 if min SZ j lowcost min SZ j lowcost k j return k 算法 7 9 P175 用普里姆算法从第 u 个顶点出发构造网 G 的最小生成树 T 输出 T 的各条 边 void MiniSpanTree PRIM MGraph G VertexType u system cls int i j k minside closedge k LocateVex G u for j 0 j G vexnum j 辅助数组初始化 if j k strcpy closedge j adjvex u closedge j lowcost G arcs k j adj closedge k lowcost 0 初始 U u printf 最小代价生成树的各条边为 n for i 1 i G vexnum i 选择其余 G vexnum 1 个顶点 k minimum closedge G 求出 T 的下一个结点 第 K 顶点 printf s s n closedge k adjvex G vexs k 输出生成树的边 closedge k lowcost 0 第 K 顶点并入 U 集 for j 0 j G vexnum j if G arcs k j adj closedge j lowcost 新顶点并入 U 集后重新选择最小边 strcpy closedge j adjvex G vexs k closedge j lowcost G arcs k j adj system pause void main system cls MGraph G int xz while 1 system cls printf n printf 管道铺设最佳方案选 择 n printf 0 记录保存为文件 n printf 1 从文件中读记录 n printf 2 构造无向网 n printf 3 求出最小生成树 n printf 4 退出 n printf n printf 请输入操作序号 0 4 n scanf d switch xz case 0 wenjian break case 1 xianshi break case 2 CreateAN break case 3 MiniSpanTree PRIM G G vexs 0 break case 4 exit 0 default printf 输入无效指令 按任意键继续 system pause system pause 六 测试结果 七 设计体会 通过数据结构的课程设计使我们对所学知识有了更好的理解 也增强了大 家的动手能力 同时也发现了自己的很多不足之处 对知识的应用能力很是欠 缺 应用软件的能力及编程水平与课程要求更是存在很大的差距