数据结构实验报告 最小生成树

Fpg

Fpg 实验五 最小生成树

一、需求分析

1、本程序の目の是要建设一个最经济の网，，输出相应の最小生成树。在这里都用整型数来代替。

2、测试数据

见下程序。

二、概要设计

主程序：

int main()

{

初始化；

while (条件)

{

接受命令;

处理命令;

}

return 0;

}

三、详细设计

#include//头文件

using namespace std;

#define MAX_VERTEX_NUM 20//最大结点数

#define MAX 200

typedef struct Close//结构体 Fpg

Fpg {

char adjvex;

int lowcost;

}Close,close[MAX_VERTEX_NUM];

typedef struct ArcNode

{

int adjvex;

ArcNode *nextarc;

int info;

}ArcNode;

typedef struct VNode

{

char data;

ArcNode *firstarc;

}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct

{

AdjList verties;

int vexnum,arcnum;

}ALGraph;

ALGraph G;//对象G

int LocateVek(ALGraph ,char );//返回结点位置

int minimum(close);//返回最小数

void MinSpanTree_PRIM(ALGraph,char);//最小生成树

void Create(ALGraph &);//创建邻接表

int main()

{

char a;int i=1;

Create(G);

/*for(int i=1;i<=G.vexnum;i++)

{

for(s=G.verties[i].firstarc;s!=NULL;s=s->nextarc)

数据结构课程设计报告

题目： 最小生成树问题

院（系）： 计算机工程学院

学生姓名:

班级： 学号:

起迄日期:

指导教师:

2011—2012年度 第 2 学期

一、需求分析

1.问题描述：

在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。

2.基本功能

在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。

程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。

3.输入输出

以文本形式输出最小生成树，同时输出它们的权值。通过人机对话方式即用户通过自行选择命令来输入数据和生成相应的数据结果。

二、 概要设计

1.设计思路：

因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和

prim算法两种方法来生成最小生成树。根据要求，需采用多种存储结构，所

以我选择采用了邻接表和邻接矩阵两种存储结构。

2.数据结构设计：

图状结构：

ADT Graph{

数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。

数据关系R：R={VR}

VR={|v,w∈V且P(v,w)，表示从v到w的弧，

谓词P(v,w)定义了弧的意义或信息}

基本操作：

CreateGraph( &G, V, VR )

初始条件：V是图的顶点集，VR是图中弧的集合。

操作结果：按V和VR的定义构造图G。

DestroyGraph( &G )

初始条件：图G存在。

操作结果：销毁图G。

.

教育资料 上海电力学院

数据结构（JAVA）课程设计

题 目:____最小生成树_______

学生姓名：_****___________

学 号：_____*******_______

院 系： 计算机科学与技术学院

专业年级： ______*****___级

20**年 *月**日 .

教育资料 .

教育资料 目录

1.设计题目................................................1

2.需求分析................................................1

1）运行环境................................................1

2）输入的形式和输入值的范围................................1

3）输出的形式描述..........................................1

4）功能描述................................................1

5）测试数据...............................................1

3.概要设计................................................1

1）抽象数据类型定义描述...................................1

.2）功能模块设计..........................................1

3）模块层次调用关系图......................................2

实验目的：

1、学会将信息存入带头结点的单链表中。

2、能够对节点中的信息进行查找、插入、删除和更新等操作。

3、学会对单链表的信息进行灵活运用，能够结合到实际运用中。

实验内容：

【问题描述】：将若干城市的信息，存入一个带头结点的单链表。结点中的城市信息包括：城市名，城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。

【基本要求】

（1）给定一个城市名，返回其位置坐标；

（2）给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。

【测试数据】

由学生依据软件工程的测试技术自己确定。注意测试边界数据。

实验步骤：

（一）需求分析

1、本演示程序中，需要建立一个新的城市链表，链表建成后根据计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中的运算命令和输入相应的数据并输出结果；

2、程序执行的命令包括：

1）建立城市链表；2）查找城市；3）添加城市；4）删除城市；5）城市更新；6）输出链表；7）城市搜索；8）退出链表。

3、测试数据：

城市名：wuhan 坐标：（23，12）人口：939 面积：352 中南民族大学管理学院学生实验报告

城市名：beijing 坐标：（73，32）人口：637 面积：673

城市名：shanghai 坐标：（43，22）人口：876 面积：342

（二）概要设计

1、数据类型定义：

单链表的存储结构

typedef struct LNode

{ ElemType data;

struct LNode *next;

}LNode,*LinkList;

typedef struct

{

char name[20];

int x;