《面向对象程序设计》课程设计报告-畅通工程

《面向对象程序设计》课程设计报告PAGE2/7《数据结构》课程设计报告题目：畅通工程专业：数字媒体技术班级：数字151姓名：学号：指导教师：成绩：

目录1问题描述22问题分析33程序设计44程序代码55参考文献66程序设计与运行结果1、设计内容及要求1.问題描述

某省调查乡村交通状况禍到的统计表中列出了任意两村庄间的距离。省政府”畅通工程”的目标是使全省負何两个村庄间都可以实现公路交通但不一定有直接的公路相

连．只要能间接通过公路可达即可，请设计一个方案，在哪些村庄之间修路才能使铺设的

公路总长度最小，并计算最小的公路总长度。

2、问题分析

假设以每个村庄为顶点，村庄之间的道路为边，可以用一个图来表示各个村庄之间的

交通道路情况。因为任何两个村庄之间都可以修路，所以有n个村庄就可以修n（n－l）／2

条道路。显然这是一个完全无向图，根据图的连通性可知，N个村庄之间只要修n一1条

道路就能保证各个村庄之间是相通的，那么如何在这n（n一1）／2条道路中选择n一1条

呢？这个问题就转化为求连通图的最小生成树问题。求最小生成树有两种方法：Prim

算法和Kruskal算法。Prim算法适合求稠密图；Kuskal算法适合求稀疏图。本问题涉及的边数较多，因此选用Prim算法比较台适。

3、程序设计

选用邻接表作为图的存储结构，每个村庄作为图中的顶点，为了运算方便，给每个村

庄一个编号，边表示两个村庄之间的道路，道路的长度作为边上的权值。深入浅出数据结构与算法涉及的边数较多,因此选用Prim算法比较合适。

/*图的邻接表存储结构

*/

#define

MAXN

100

struct

ArcNode

/*

定义邻接表的边结构*

/

{int

adjvex,info;

/*adjvex是顶点编号,info表示边的长度*/

struct

ArcNode

*nextarc;

/*

指向下一条边。/

｝；

struct

VNode/*定义邻接表的顶点向量*/

{int

data;

ArcNode

*

firstarc;/*

指向第一条边大/

}AdjList[MAXN];

输入设计:

第一行给出村庄数目N(<100),当N为0时，输入结束。随后的

N(N-

1)/2行对应村庄间的距离，每行给出一对正整数(分别是两个村庄的编号)以及两村庄间的距离，村庄从1到N

编号。

输出设计:

输出应建设的每一条道路的村庄编号及距离,并输出应建设道路的最短距离。

基本操作:

Init():

初始化界面设计。

Input():

输人两个村庄的编号及之间的距离。

join(VNode

*

a,int

b,int

c):

输人数据建立邻接表。

Prim():

运用Prim

算法求最小生成树。

main():

主函数。

4.程序代码

#include<stdio.h>#include<limits.h>#include<string.h>#include<windows.h>#defineMAXN100intn,m,visit[MAXN+5],low[MAXN+5];inti,a,b,c,length=0;structArcNode{ intadjvex,info; structArcNode*nextarc;};structVNode{ intdata; ArcNode*firstarc; }AdjList[MAXN];voidInit(){ printf("************畅通工程********************"); printf("请输入村庄数目N：(N<100)\n\n");}voidjoin(VNode*a,intb,intc){ ArcNode*p,*q; p=newArcNode; p->adjvex=b;p->info=c;p->nextarc=NULL; q=a->firstarc; a->firstarc=p; p->nextarc=q;}voidInput(){ scanf("%d",&n); m=n*(n-1)/2; printf("\n请输入对应村庄间的距离：\n"); printf("格式：村庄A的编号村庄B的编号两村庄间的距离\n"); printf("共%d行\n",m); for(i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); join(&AdjList[a],b,c); join(&AdjList[b],a,c); }}voidPrim(){ inti,j,pos,min,length=0; ArcNode*p; printf("\n使用Prim算法计算其最小生成树并输出边\n\n"); system("pause"); puts(""); memset(visit,0,sizeof(visit)); visit[1]=-1; pos=1; for(i=2;i<=m;i++) { low[i]=INT_MAX; visit[i]=1; } p=AdjList[1].firstarc; while(p!=NULL) { low[p->adjvex]=p->info; p=p->nextarc; } for(i=1;i<n;i++) { min=INT_MAX; for(j=1;i<=n;j++) { if(visit[j]!=-1&&low[j]<min) min=low[j]; pos=j; length+=min; printf("连接村%d和村%d,公路长度为%d\n\n",visit[pos],pos,low[pos]); visit[pos]=-1; p=AdjList[pos].firstarc; while(p!=NULL) { if(p->adjvex!=-1&&p->info<low[p->adjvex]) low[p->adjvex]=p->info,visit[p->adjvex]=pos; p=p->nexta