数据结构课程设计报告

题目：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用（邻接表和邻接矩阵）两种，采用课本上的两种求解算法。

1.1已知一个无向连通网表示n个城市以及城市间可能设置的通信网络线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。

我们要选择一棵生成树，使总的耗费最小。

1.2该无向连通图的建立需要使用两种存储结构，即邻接表和邻接矩阵。

1.3实现最小生成树需要使用两种算法。即普里姆算法和克鲁斯卡尔。

1.4程序通过人机交互实现数据的输入和输出。

1.5测试数据。

（a,b）:2 ; a,c):3; (a,d):4; (c,d):4; (b,d):5

程序分为两大部分存储部分和算法部分；存储部分分为邻接矩阵和邻接表，而且包含了两者直接的互相转换；算法部分分为普里母算法和克鲁斯卡尔算法。

adt graph

vr = 基本操作p;

createmgraph(mgraph *g)

初始条件：v是图的顶点集，vr是图的边的集合。

操作结果：按v和vr的定义构造图g，用邻接矩阵存储。

createalgraph(algraph *g)

初始条件：v是图的顶点集，vr是图的边的集合。

操作结果：按v和vr的定义构造图g，用邻接表存储。

locatevex（g，u）

初始条件：图g存在，u和g中顶点有相同的特征。

操作结果：若g中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。

minispantree_prim（g, u)

初始条件：图g存在，u是图g中的一个顶点。

操作结果：用普利姆算法从第u个顶点出发构造网g的最小生成树t，输出t的各条边。

kriuskal(g)

初始条件：图g存在。

操作结果：用克鲁斯卡尔算法构造图g的最小生成树t，输出t的各条边。

listtomat(mgraph *g1,algraph *g2)

初始条件：图g2存在。

操作结果：把图的邻接表存储结构转换为邻接矩阵存储结构，用图g1表示。

mattolist(mgraph *g1,algraph *g2)

初始条件：图g1存在。

操作结果：把图的邻接矩阵存储结构转换为邻接表存储结构，用图g2表示。

locatevex(mgraph *g,vertextype u)

初始条件：图g存在，u和g中顶点有相同特征。

操作结果：若g中存在顶点u，则返回该顶点在图中位置；否则返回-1

adt graph

void main()

创建图g，并按不同的存储结构输出。

对图的存储结构进行转换。

使用算法构造最小生成树并输出各边。

#define ok1

#define error 0

#define ture 1

#define false 0

#define overflow -1

#define infeasible -2

typedef int status;

#define infinity 32767 //两地之间没有架设线路的权值为最大数。

#define max_vertex_num 20 //城市的数目最大为20

#define max_name 5//城市名称的最大长度为5

typedef char vertextype[max_name];/城市的名称用字符数组存储。

typedef int vrtype; /两城市间的关系类型。

1.1邻接矩阵存储表示的图的结构体类型的定义。

typedef struct arccell

vrtype adj;

/*顶点关系类型。对无权图，用1（是）或0(否）表示相邻否*/

/*对带权全图，则为权值类型*/

}arccell,adjmatrix[max_vertex_num][max_vertex_num];

typedef struct

vertextype vexs[max_vertex_num]; 顶点向量*/

adjmatrix arcs; /邻接矩阵*/

int vexnum,arcnum; /图的当前顶点数和弧数*/

}mgraph;

1.2邻接表类型存储表示的图的结构体类型的定义

typedef struct anode弧的结点结构类型 */

int end; /弧尾在邻接表头结点中的位置。

int begin; /弧头在邻接表头结点中的位置

int weight该弧的相关信息，这里用于存放权值 */

struct anode *nextarc; /指向下一条弧的指针 */

anode;

typedef struct vnode邻接表头结点的类型 */

vertextype vertex顶点信息，城市名称 */

int bianhao; /城市在邻接表头结点数组中的相应编号。

anode *firstarc指向第一条弧 */

vnode,adjlist[max_vertex_num]; adjlist是邻接表类型 */

typedef struct

adjlist adjlist邻接表 */

int vexnum,arcnum图中顶点数n和边数e */

algraph;

假设v是图中顶点的集合，e是图中边的集合，te为最小生成树中的边的集合，则prim算法通过以下步骤可以得到最小生成树：

1）初始化：u=,te=。此步骤设立一个只有结点u 0的结点集u和一个空的边集te作为最小生成树的初始形态，在随后的算法执行中，这个形态会不断的发生变化，直到得到最小生成树为止。

2）在所有u∈u,v∈v－u的边(u,v)∈e中，找一条权最小的边(u 0,v 0)，将此边加进集合te中，并将此边的非u中顶点加入u中。此步骤的功能是在边集e中找一条边，要求这条边满足以下条件：首先边的两个顶点要分别在顶点集合u和v－u中，其次边的权要最小。

找到这条边以后，把这条边放到边集te中，并把这条边上不在u中的那个顶点加入到u中。这一步骤在算法中应执行多次，每执行一次，集合te和u都将发生变化，分别增加一条边和一个顶点，因此，te和u是两个动态的集合，这一点在理解算法时要密切注意。

3）如果u=v,则算法结束；否则重复步骤2。可以把本步骤看成循环终止条件。我们可以算出当u=v时，步骤2共执行了n－1次(设n为图中顶点的数目),te中也增加了n－1条边，这n－1条边就是需要求出的最小生成树的边。

prim算法假设网中有n个顶点，则第一个进行初始化的循环语句频度为n，第二个循环语句的频度为n-1。其中有两个内循环；由此普里母算法的时间复杂度为o(n2),与网中的边数无关！

假设 wn=(v,) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：

1）先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。

2）从网的边集 e 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。

3）依次类推，重复上述操作，直至森林中只有一棵树，也即子图中含有 n-1条边为止。

克鲁斯卡尔算法至多对e条边各扫描一次时间复杂度为o（eloge）。

(a)程序中用来实现邻接矩阵和邻接表存储、输出以及互相转化的函数。

status initalgraph(algraph *g)

/初始化邻接表。

void createalgraph(algraph *g)

/创建邻接表。

status initmgraph(mgraph *g)

/初始化邻接表。

status createmgraph(mgraph *g)

/创建邻接表。

status mattolist(mgraph *g1,algraph *g2)

/将邻接矩阵g1转换成邻接表g2

status listtomat(mgraph *g1,algraph *g2)

/将邻接表g1转换成邻接矩阵g2

status printmgraph(mgraph *g)

/输出邻接矩阵g

status printalgraph(algraph *g){

/输出邻接表g

b)程序中用来完成prim和kriuskal算法的函数。

int mininum(minside closedge,mgraph *g)

/ 求closedege数组中lowcost的最小正值。

void minispantree_prim(mgraph *g,vertextype u)

/ 用普利姆算法从第u个顶点出发构造网g的最小生成树t，输出t的各条边void insertsort(edgetype e,int n)

/对e[0...n-1]按权值递增有序的进行直接插入排序。

void kriuskal(algraph *g)

/克鲁斯卡尔算法。

c) 查找顶点u在图中的位置。

int locatevex(mgraph *g,vertextype u)

/查找顶点u在图中的位置。

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了