管道铺设问题数据结构课程设计

发布时间：2024-11-10

一、摘要N(N>10)个居民区之间需要铺设煤气管道。假设任意两个居民区之间都可以铺设煤气管道，但代价不同。程序要求:事先任意两居民区之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民区之间铺设煤气管道所需代价最小，并将结果以图形方式在屏幕上输出。

数据结构课程设计报告

管道设计问题

——二维数组的运用

班级：姓名：指导教师：成绩：__________________________

2010年 1 月 20日

一、摘要........................................................................................... 3 二、引言........................................................................................... 3 三、需求分析 .................................................................................. 3 四、概要设计 .................................................................................. 4 1.普里姆算法分析 ..................................................................... 4 2.模块分析 .................................................................................. 5 3.抽象数据类型分析................................................................. 5 5.全部流程 .................................................................................. 6 五、详细设计 .................................................................................. 7 1.算法分析 .................................................................................. 7 ①信息输入模块................................................................... 7 ②建立最小生成树并输出结果 ......................................... 8 2.源程序代码 ............................................................................. 9 六、测试结果 ................................................................................ 14 程序开始 ................................................................................... 14 信息输入 ................................................................................... 14 输出结果 ................................................................................... 15 七、设计体会 ................................................................................ 15 八、结束语 .................................................................................. 16 参考文献......................................................................................... 16

一、摘要

N(N>10)个居民区之间需要铺设煤气管道。假设任意两个居民区之间都可以铺设煤气管道，但代价不同。问题的实质就是编写相应程序求解最小生成树问题。程序要求：

事先任意两居民区之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民区之间铺设煤气管道所需代价最小，并将结果以图形方式在屏幕上输出。

二、引言

C语言作为一门最通用的语言，在过去很流行，将来依然会如此。几乎每一个理工科或者其他专业的学生毫不例外地要学习它。

从C语言产生到现在，它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中，都能看到C语言的影子。学习、掌握C语言是每一个计算机技术人员的基本功之一。

C语言具有高级语言的强大功能，却又有很多直接操作计算机硬件的功能，因此，C语言通常又被称为中级语言。

实际生活中最小生成树的问题具有很大的意义。例如，本文所讨论的构架居民区之间铺设煤气管道代价最小，还有在若干的地区见铺设光缆，等等。最小生成树让许多诸如求造价最小、最短路径等最优化的现实问题找到了理论依据，并提供了有效的解决方法。

三、需求分析

在N(N>10)个居民区之间铺设煤气管道所需代价最小，即求最小生成树问题。在我们的课程中介绍了两种求解方法：普里姆（prim）算法和克鲁斯卡尔（kruskal）算法。普里姆算法与网的变数无关，时间复杂度为O（n2),适宜求解边稠密的网的最小生成树。而克鲁斯卡尔算法正好相反，时间复杂度为O（eloge）（e为网中边的数目），故而该算法适宜求边稀疏的最小生成树。

由于在实际应用中，居民区数量一般很有限，而任何两个居民区间都可能有连线，即这样的图应该是边较为稠密的。因此，我们选择普里姆算法对问题进行求解。

1、建立一个带权无向图的邻接矩阵，然后进行深度和广度优先搜索遍历，并输出遍历的结果序列。最后若此图是连通图，输出该网的一颗最小生成树。

2、网中顶点的编号从0开始顶点的信息为字符。 3、按照网的邻接矩阵定义输出该矩阵。

4、在非连通图的情况下要能够按深度和广度优先搜索遍历整个网。 5、用普里姆法构造最小生成树。在最小生成树算法中，应判断该网是否连通，如果非连通，则需输出提示信息并退出程序。

四、概要设计

1.普里姆算法分析

①普里姆算法思想

普里姆方法的思想是：在图中任取一个顶点k0作为开始点，令U={k0}，W=V-U，其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在W中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删去这些顶点，然后重新调整U中顶点到W中顶点的距离, 使之保持最小，再重复此过程，直到W为空集止。

②该算法过程描述

(1)在图G=(V, E) （V表示顶点，E表示边）中，从集合V中任取一个顶点（例如取顶点k0）放入集合 U中，这时 U={k0}，集合T(E)为空。

(2) 从k0出发寻找与U中顶点相邻（另一顶点在V中）权值最小的边的另一顶点k1，并使k1加入U。即U={k0,k1 }，同时将该边加入集合T(E)中。

(3) 重复(2)，直到U = V为止。

(4)这时T(E)中有n-1条边，T = (U, T(E))就是一棵最小生成树。

Prim算法示意图

2.模块分析

根据对模型的功能分析，该管道铺设设计可以具有以下功能： ①管道铺设信息的输入； ②最小生成树信息的输出；下

面

我

们

给

出

相

应

的

功

能

模

块

图

：

3.抽象数据类型分析

areanum 居民区总数（顶点总数）； edgenum 边的总数；

date[][20] 邻接矩阵存储图结构； s 边的权值；

short_way[i] 居民区i到到目前生成树中所有点集U中某个居民区的路程最小

值

near_area[i] U中能使其最小的居民区

5.全部流程

五、详细设计

1.算法分析

①信息输入模块

//读入图的信息，并将邻接矩阵输出 void read（）

{//输入顶点个数和边的条数

printf（"请输入：顶点数，边数：\n"); scanf("%d,%d",&areanum,&edgenum); //初始化矩阵各元素值 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 < edgenum; i++) {

scanf("%d,%d,%d",&from,&to,&ws); 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"); } }

②建立最小生成树并输出结果

void prim(int date[][MAXNODE],int areanum,int near_area[]) {//辅助数组short_way,near_area

//short_way[i]表示居民区i到到目前生成树中所有点集U中某个居民区（点）的路程最小值

//near_city[i]表示U中能使其最小的居民区(点) int short_way [areanum]; int min; int i,j,k; //0已经放入U中

//初始化short_way 和 near_area for(i = 1; i < areanum; i++) {

short_way[i] = date[0][i]; near_area[i] = 0; }

short_way[i]=0; near_area[0] = 0;

for(i = 1; i < areanum; i++)//有n-1条边要加入生成树,所以只要循环n-1次即可 {

min =INFINITY;// 求生成树外顶点到生成树内顶点具有最小权值的边 j=1;k=1;

while(j<areanum)//确定当前具有最小权值的边及位置 {

if(short_way[j]!=0 && short_way[j] < min) {

min = short_way[j]; k=j; } j++; }

printf("居民区序号为%d，居民区路程（边的权值）为%d",k,min); short_way[k]=0; for(j=0;j<n;j++) {

if(date[k][j]<short_way[j]) {

short_way[j] = date[k][j]; near_area[j] = k; } } }

2.源程序代码

#include<stdio.h> #define INFINITY 9999 void main() {int a1;

printf("%46s\n","管道铺设方案选择"); for(a1=0;a1<21;a1++) printf(" ");

for(a1=0;a1<34;a1++)

printf("*"); printf("\n");

for(a1=0;a1<21;a1++) printf(" ");

printf("* *"); printf("\n"); for(a1=0;a1<21;a1++) printf(" "); printf("*");

printf("欢迎使用本程序，本程序可以帮助您*"); printf("\n"); for(a1=0;a1<21;a1++) printf(" "); printf("*");

printf("选择最佳管道铺设方案！ *"); printf("\n"); for(a1=0;a1<21;a1++) printf(" ");

printf("* *"); printf("\n"); for(a1=0;a1<21;a1++) printf(" ");

for(a1=0;a1<34;a1++) printf("*"); printf("\n");

//输入顶点个数和边的条数 //system("color 3e");

int date[20][20]; int areanum;

int edgenum;

printf("请输入：\n居民区个数，每个点可以的铺设路线：\n"); scanf("%d,%d",&areanum,&edgenum); //初始化矩阵各元素值 int i,j;

for(i=0;i<areanum;i++) for(j=0;j<areanum;j++) date[i][j]=INFINITY; //读入边 int from,to,m;

printf("输入边,格式为i, j, k,表示i居民点到j居民点的距离是（米）:\n");

for(i=0;i<edgenum;i++) {

scanf("%d,%d,%d",&from,&to,&m); date[from][to] = m; date[to][from] = m; }

//输出邻接矩阵

printf("输出邻接矩阵为：\n"); for(i=0;i<areanum;i++) {

for(j=0;j<areanum;j++) {

printf("%d\t",date[i][j]); }

printf("\n"); }

//prim();

//辅助数组short_way,near_area

//short_way[i]表示居民区i到到目前生成树中所有点集U中某个居民区（点）的路程最小值

//near_area[i]表示U中能使其最小的居民区(点) int short_way[20]; int near_area[20]; int min; int k,s,price; //0已经放入U中

//初始化short_way 和 near_area for(i = 1; i < areanum; i++) {

short_way[i] = date[0][i]; near_area[i] = 0; }

short_way[i]=0; near_area[0] = 0; s=0;

printf("从居民区0出发,\n");

for(i = 1; i < areanum; i++)//有n-1条边要加入生成树,所以只要循环n-1次即可 {

min =INFINITY;// 求生成树外顶点到生成树内顶点具有最小权值的边 j=1;k=1;

while(j<areanum)//确定当前具有最小权值的边及位置 {

if(short_way[j]!=0 && short_way[j] < min) {

min = short_way[j];

k=j; } j++; }

printf("从居民区%d到居民区%d，居民区路程（边的权值）为%d米\n",near_area[k],k,min); short_way[k]=0; s+=min;

for(j=0;j<areanum;j++) {

if(date[k][j]<short_way[j]) {

short_way[j] = date[k][j]; near_area[j] = k; } } }

printf("%d个居民区之间铺设煤气管道总长度最短的长度为:%d米\n",areanum,s);

printf("请输入单位长度的价格（元）：\n"); scanf("%d",&price);

printf("所以%d个居民区之间铺设煤气管道所需最小代价为:%d元\n",areanum,s*price);

printf("\n谢谢使用！\n本程序编写者：杨烨\n"); }

六、测试结果

程序开始

信息输入

输出结果

七、设计体会

通过数据结构的课程设计使我们对所学知识有了更好的理解，也增强了大家的动手能力。同时也发现了自己的很多不足之处，对知识的应用能力很是欠缺，应用软件的能力及编程水平与课程要求更是存在很大的差距。

程序的运行结果与理论推导结果完全吻合，即该算法与程序设计满足课程设计要求。该程序的主要优点是简单易懂，不存在理解上的障碍，也很自然地能想到这种解法。主要缺点是程序的变动性比较差——初始化邻接矩阵后结果就固定

了。如果能加入图的修改、插入、删除等操作，我想应该会更好很多，但由于时间等诸多方面的原因在这就不多做论述了。

八、结束语

转眼，为期两周的《数据结构》课程设计即将结束了。在这次课程设计中我的C语言知识和数据结构知识得到了巩固。编程能力也有了一定的提高。同时也学会了解决问题的方法。总结起来，自己主要有以下几点体会：

1.必须牢固的掌握基础知识。由于C语言是大一所学知识，又说遗忘，同时没有掌握好这学期说学的《数据结构》这门课，所以在课程设计初期感到无从下手，但在后来的设计过程中自己通过看书和课外资料，并请教其他同学，慢慢地堆C语言和数据结构知识有所熟悉。这时才逐渐有了思路。所以，在这次课程设计以后，我告诫自己：今后一定要牢固地掌握好专业基础知识。

2.必须培养严谨的科学态度。我在编写程序时经常因为一些类似于“少了分号”的小错误导致程序调试失败，不够认真仔细，这给自己带来了许多的麻烦。编程时一件十分严谨的事情，容不得马虎。所以在今后我一定要培养严谨的科学态度。我认为这不仅仅是对于编程，做任何事情都应如此。

3.这次课程设计也让我充分的认识到《数据结构》这门课的重要性。它给我们一个思想和大纲，让我们在编程时更容易找到思路，不至于无章可循。同时它也有广泛的实际应用价值。

总之，在这次课程设计中，我的C语言以及数据结构知识得到提高，编程能力也得到了提高。

参考文献

1. 刘玉龙《数据结构与算法实用教程》电子工业出版社 2. 谭浩强《C语言设计》第三版清华大学出版社 3. 严蔚敏《数据结构（C语言版）》清华大学出版社 4. 苏仕华《数据结构自学辅导》清华大学出版社

管道铺设问题数据结构课程设计.doc 将本文的Word文档下载到电脑

下载这篇word文档

上一篇：第九章计数原理、概率、随机变量及其分布第3课时(高考总复习·数学文)

下一篇：社会主义核心价值观在我心中