数据结构课程设计

扬州大学信息学院。

数据结构》--课程设计报告。

题目：连接城市的最小生成树

班级：信息1101

学号： 111405122

姓名：汪梦毕

同组成员。指导教师：王丽爱。

一、设计题目。

连接城市的最小生成树。

二、需求分析。

若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。要求：

1）根据数据建立图；

2）能够保存**件；

3）能够从保存过的文件中读取**件；

4）能够显示最小生成树，应包括道路两端城市名称、道路长度以及最小生成树的代价。。

三、概要设计。

根据需求结果分析确定程序的总体设计，首先在每个功能中都有输入和输出，所以设计时需要采取交互的方式。通过编写一个主菜单功能来实现添加道路信息、生成最小生成树、读入文件、写入文件、退出等各个功能模块的调用，从而更好的协调的各个功能模块之间的关系。

系统功能模块图如图1所示：

图1 四、详细设计。

1、图的数据结构表示本设计采用邻接表方式表示图，顶点集合采用链式存储结构。

邻接表有两种数据结构，一种是顶点结构，另一种是弧的结构，顶点结构的第一个域是顶点的序号，第二个域是定点的名称，第三个域是指向下一顶点的指针，第四个域是指向有该顶点射出的弧。弧结构的第一个域是弧的另一端点的序号，第二个域是弧的权值，第三个域是指向下一条由出射顶点射出的弧。结构如图2s所示：

顶点结构。弧的结构。

图22、求解最短路径的算法。

构造最小生成树有两种经典的算法，一种是prim算法，还有一种kruskal算法，本设计采用prim算法。

3、数据结构定义。

typedef struct rode

return pnode;

node *findnodebyid(int id)

return pnode;

node *addnode(char nodename)

dstnode = findnodebyname(dst);

if(dstnode ==null){