文档介绍：20

数据结构课程设计

系别
电子信息系
专业
计算机科学与技术
班级学号

姓名

指导教师

成绩

2012年7 月12日
1
目录
1 需求分析 2
2 概要设计 2
2. 1抽象数据类型定义............................................................................................................2
2 . 2模块划分............................................................................................................................3
3 详细设计 4
3. 1数据类型的定义 4
3. 2主要模块的算法描述 6
4 调试分析 10
5 用户手册 10
6 测试结果......................................................................................................................................11
7 附录(源程序清单）.....................................................................................................................13
参考文献 20
2
一、需求分析
，只需要架设n-1条线路即可，而要以最低的经济代价建设这个通信网，就需要在这个网中求最小生成树。
(1)利用克鲁斯卡尔算法求网的最小生成树。
(2)实现教科书节中定义的抽象数据类型 MFSet 。以此表示构造生成树过程中的连通分量。
(3)输入顶点个数，输入顶点序号（用整型数据[0，1，2，……，100]表示），输入定点之间的边的权值（整型数据）。系统构造无向图，并求解最小生成树。
(4)以图形和文本两种形式输出最小生成树。
：
(1)随机生成一个图；
(2)输入图坐标信息；
(3)以文本形式输出最小生成树；
(4)以图形形式输出最小生成树；
(5)以图形形式输出构造的图；
(6)结束。
测试数据
(1)用户输入需要构造的图形顶点个数，假设顶点个数为4；
(2)C语言函数随机生成的图形，顶点分别为a,b,c,d,权值分别为：
ab=75,ac=99,ad=80,bc=33,bd=93,cd=19；
(3)最小生成树边的权值分别为:ab=75,bc=33,cd=19;
(4)结束。
概要设计
1. 图的抽象数据类型定义
ADT Gragh{
数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。
数据关系R：
R＝{VR}
VR＝{<v,w>| v,w∈V且P(v,w)，<v,w>表示从v到w的弧，
谓词P(v,w)定义了弧<v,w>的意义或信息 }
基本操作P：
CreateGraph(&G，V，VR)；
初始条件：V是图的顶点集，VR是图中弧的集合。
操作结果：按V和VR的定义构造图G。
DestroyGragh(&G)；
初始条件：图G存在。
操作结果：销毁图G。
GetVex(G，v)；
初始条件：图G存在，v是G中某个顶点。
操作结果：返回v的值。
FirstAdjvex(G,v)；
初始条件：图G存在，v是G中某个顶点。
3
操作结果：返回v的第一个邻接顶点，则返回“空”。
NextAdjVex(G,v,w)；
初始条件：图G存在，v是G