《面向对象程序设计》课程设计报告--畅通工程.docx
数据结构课程设计报告题目：畅通工程专业：数字媒体技术班级：数字151姓名：学号：指导教师：目录1问题描述22问题分析33程序设计44程序代码55参考文献66程序设计与运行结果L设计内容及要求1.问题描述某省调查乡村交通状况祠到的统计表中列出了任意两村庄间的距离。省政 府”畅通工程”的目标是使全省负何两个村庄间都可以实现公路交通但不一定 有直接的公路相 连,只要能间接通过公路可达即可，请设计一个方案，在哪些 村庄之间修路才能使铺设的公路总长度最小，并计算最小的公路总长度。2、问题分析假设以每个村庄为顶点，村庄之间的道路为边，可以用一个图来表示各个村 庄之间的 交通道路情况。因为任何两个村庄之间都可以修路，所以有n个村庄 就可以修n(nD /2条道路。显然这是一个完全无向图，根据图的连通性 可知，N个村庄之间只要修nl条 道路就能保证各个村庄之间是相通的，那 么如何在这n(n 1) / 2条道路中选择n-l条呢？这个问题就转化为求连通图的最小生成树问题。求最小生成树有两种方法：Prim算法和KrUSkaI 算法。Prim算法适合求稠密图；KUSkaI算法适合求稀疏图。本问题涉及的边数 较多，因此选用Prinl算法比较台适。3、程序设计选用邻接表作为图的存储结构，每个村庄作为图中的顶点，为了运算方便, 给每个村庄一个编号，边表示两个村庄之间的道路，道路的长度作为边上的权值。深入浅出数据结构与算法涉及的边数较多，因此选用Prim算法比较合适。 /*图的邻接表存储结构*/ define MAXN IOO struct ArcNode/*定义邻接表的边结构* /int adjvex, info;*adjvex是顶点编号，info表示边的长度*/struct ArcNode *nextarc; /* 指向下一条边。/);struct VNode/*定义邻接表的顶点向量*/int data;ArcNode * f irstarc;/* 指向第一条边大/AdjListMAXN;输入设计：第一行给出村庄数目N(GOO),当N为。时，输入结束。随后的N(N- 1)/2行对应村庄间的距离，每行给出一对正整数(分别是两个村庄的编号) 以及两村庄间的距离，村庄从1到N编号。输出设计：输出应建设的每一条道路的村庄编号及距离,并输出应建设道路的 最短距离。基本操作：InitO:初始化界面设计。InputO:输人两个村庄的编号及之间的距离。join(VNode * a, int b, int c):输入数据建立邻接表。PrimO :运用Prim算法求最小生成树。main():主函数。4 .程序代码ftinclude<stdio. h> ftinclude<limits. h> ftinclude<string. h> ftinclude<windows. h> Sdefine MAXN 100 int n, m, visitMAXN+5, lowMAXN+5; int i, a, b, c, Iength=O;struct ArcNode (int adjvex, info;struct ArcNode *nextarc;；struct VNode(int data;ArcNode *firstarc; AdjListNfAXN; void Init()printf (*畅通工程*)；(N<100)nn");Printf (”请输入村庄数目N：void join (VNode *a, int b, int c)ArcNode *p,*q;p=new ArcNode;p->adjvex= b; p->info=c;p->nextarc=NULL;q=a->firstarc;a->firstarc=p;p->nextarc=q;void Input ()(scanf (,%dz, &n);m=n*(n-l)2;Printf ("n请输入对应村庄间的距离：n)；Printf ("格式：村庄A的编号村庄B的编号两村庄间的距离r);printf ("共%d 行n”, m);for(i=l;i<=m;i+)(scanf ("%d%d%d”, &a, &b, &c);join(&AdjLista, b, c);join(&AdjList b, a, c);)void Prim()(int i, j, pos, min, Iength=O;ArcNode *p;printf (z,使用Prim算法计算其最小生成树并输出边nn");system (zzpausez,);puts(,z);memset(visit, 0, sizeof(visit);visit1=-1;pos=l;for(i=2;i<=m;i+)(lowi =INTJfAX;visiti=l;)p=AdjListl. firstarc;whiIe(p!=NULL)(lowp->adjvex=p->info;p=p->nextarc;for(i=l;i<n;i+÷)(Iiiin=INTJlAX;for(j=l;i<=n;j+)(if(visitj!=-l&&lowj<min)min=lowj;pos=J；length+=min;Printf (连接村%d和村%d,公路长度为dnn”, visitpos, pos, lowpos);visitpos=-l;P=AdjListEpos. firstarc;whiIe(p!=NULL)(if(p->adjvex!=-l&&p->info<lowp->adjvex) lowp->adjvex=p->info, visitp->adjvex=pos;p=p->nextarc;)Printf ("最小的公路长度为:%dn”, length);int main ()Init()；InputO ；Prim()；5、参考文献1刘晓华著.数据结构与算法.北京：清华大学出版社，20156.程序测试与运行结果
