数据结构课程设计

设计说明书。

数学与计算机科学学院。

2024年12月30日。

课程设计任务书。

2016—2017学年第一学期。

设计内容：1.设计任务。

1) 任意给出一个带权值的连通网络图，能够遍历图中的所有节点；

2) 根据普里姆的算法思想，输出针对这个连通网络图的最小生成树；

3) 界面友好，可操作性强。

2.需求分析。

对系统的功能及性能要求进行分析，写出需求规格说明书（可行性分析报告、系统的分层dfd图）；

3.软件设计。

软件设计分两个阶段进行：总体设计和详细设计；

总体设计：确定系统总体设计方案，完成系统的模块结构图及模块的功能说明；

详细设计：对模块内部过程及数据结构进行设计，以及进行数据库设计、用户界面设计等编写出该项目的详细设计报告；

4.具体编码。

编写程序，要求给出详细的注释，包括：模块名、模块功能、中间过程的功能、变量说明等。同时编写用户使用手册、程序模块说明等文档；

5.软件测试。

所有测试过程要求采用综合测试策略，应事先制订测试计划，并要求保留所有测试用例，完成测试报告。

指导教师：申静教研室负责人：申静

课程设计评阅。

摘要。设计一个程序，用该程序实现普里姆算法构造最小生成树。在设计该程序时，vc++作为软件开发环境，程序采用邻接矩阵的存储方式建立带权的无向网络图和利用普里姆算法对所建的网络图求最小代价生成树。

操作比较简单，界面清晰，易于接受。

关键词：最短路径；普里姆算法；最小生成树。

目录。1课题描述 1

2需求分析 2

2.1任务分析 2

2.2理解prim思想 2

3设计过程 3

3.1概要设计 3

3.2程序设计流程图 3

4具体编码分析 6

5程序调试与分析 10

5.1上机调试 10

5.2程序执行过程 10

6结果分析 13

7总结 14

附录： 16

在我们的平时生活中，人们都希望花最少的时间或者最少的金钱将一件事情办成，例如：一个邮递员想走最短的路把手中的物件送到收件人手中，通信公司想花费最少的金钱把通信网络覆盖在n个城市之间，这些都可归纳为求最短路径问题。

本课题利用普里姆算法来实现譬如通信网络中各种连接方式中的最短路径问题，从而达到一条最优线路，以使金钱或时间的花费最小，达到解决成本的目的。本课题将各个城市抽象成为一个个节点，连接各个城市之间的网络作为连接各个节点的边。于是就将城市的空间分布抽象成为一个网络图，再将各条边的距离抽象成为各节点之间的权值。

在原来的基础上建立一个带有权值的网络图。

整个算法通过各个子函数之间的嵌套调用，从主函数开始顺序往下执行，首先调用creat()函数创建无向网并采用邻接矩阵的方式来存储；然后将该网对应的邻接矩阵通过调用display()函数输出；最后调用prim ()函数求出该网所对应的最小生成树，并且在prim ()函数中通过嵌套调用minium ()函数求出辅助数组close中权值最小的边，从而完成了本设计的要求。

开发工具：visual c++ 6.0

本设计是基于最小生成树普里姆算法的思想上，以实现在网络中可以选择出最**路，从而达到省时省力的效果。

假设要在n个城市之间建立通信联络网，则联通n个城市只需要n-1条线路，然而n个城市之间最多可能设置n(n-1)/2条线路，此时，自然会考虑一个问题，如何在这些可能的线路中选择n-1条，使的在最节省经费的前提下建立起这个通信网。这就可以简化为构造联通网的最小代价生成树（简称最小生成树）问题。根据普里姆的算法思想，输出连通网络图的最小生成树。

本次设计要求编写一个能够实现最小生成树的程序，构造一个可视化的界面，得到一个最短路径的结果。

任务：根据普里姆的算法思想，输出连通网络图的最小生成树。

prim算法（普里姆算法）的基本思想：假设g =（v，e）是一个具有n个顶点的连通网，t=(u,te)是g的最小生成树，其中u是t的顶点集，te是t的边集，u和te的初值均为空集。算法开始时，首先从v中任取一个顶点（假定取v0），将它并入u中，此时u=，然后只要u是v的真子集，就从那些其一个端点已在t中，另一个端点仍在t外的所有边中，找一条最短（即权值最小）边，假定为（i,j），其中vi∈u,vj∈(v-u),并把该边（i,j）和顶点j分别并入t的边集te和顶点集u，如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后就把所有n个顶点都并入到生成树t的顶点集中，此时u=v，te中含有n-1条边，t就是最后得到的最小生成树。

可以看出，在普利姆算法中，是采用逐步增加u中的顶点，常称为“加点法”。为了实现这个算法在本设计中需要设置一个辅助数组closedge[ ]以记录从u到v-u具有最小代价的边。当辅助数组中存在两个或两个以上的最小代价的边时，此时最小生成树的形态就不唯一，此时可以在程序中采用递归的算法思想求出每个最小生成树。

如图3.1所示。

图2.1普利姆算法构造最小生成树的过程。

1.子函数int locate(adjmatrix *g,int v)

实现过程：是求出某个顶点在顶点向量表中的位置，在其函数体中通过for循环将某一顶点与顶点向量表中的所有顶点进行比较，当出现两者相等时，将该顶点在vexs[max]数组中的下标通过return语句返回，否则返回-1；

2.子函数adjmatrix *creat(adjmatrix *g)

功能：是完成无向网的创建。

实现过程：是完成无向网的创建，在其函数体中，首先通过键盘输入网中顶点数，若顶点个数<=1时，将标志变量flag置为1并显示“最小生成树不存在”，然后返回主调函数；否则，继续通过键盘输入网中的边数，通过二重for循环初始化邻接矩阵，然后输入各个顶点的编号及每条边的权值，调用函数locate()求出每条边所对应的两个顶点在顶点向量表中的位置后，将对应在邻接矩阵中的相应位置赋予权值，从而在邻接矩阵中存放了相关连的顶点之间边的权值，完成无向网的存储；

3. 子函数int minium(adjmatrix *g,node close)

实现过程：是求出辅助数组close中权值最小的边，在其函数体中，首先将最小权值（min）置为infinit（∞）通过for循环将辅助数组中的各条边的权值与min进行比较，最终使得min中存放的是当前数组close中最小的权值，并将其在辅助数组中的相应位置返回主调函数中；

4. 子函数void prim(adjmatrix *g,int u)

功能：是利用prim（普里姆）算法求出无向网所对应的最小生成树。在其函数体中，首先，定义adjmatrix *p用于存放最小生成树中的顶点（按生成最小生成树时的顺序存放），调用函数locate()求出起点u在顶点向量表中的位置，将u存放到p的顶点向量表中，初始化初始化u=，利用for循环对v-u中的顶点i,初始化close[i]，再利用for循环找n-1条边(n=g->vexnum)，其中，调用函数minium()求出辅助数组close中权值最小的边，并将其在辅助数组中的相应位置返回到主调函数中并赋给k0，此时close[k0]中存有当前最小边(u0, v0)的信息，将边所对应的终点放入p的顶点向量表中，累加边的权值；然后，输出《起点终点权值》；最后，在顶点v0并入u之后，利用for循环更新closedge[i]；当所有的顶点v0都纳入u集合之后，输出最小生成树中的顶点序列及最小生成树的权值之和。

5. 子函数void display(adjmatrix *g)

功能：是创建的无向网所对应的邻接矩阵；

6. 主函数void main()

功能：是完成对上述各子函数的调用，完成本次设计的要求，在其函数体中，通过while循环可以实现重复创建网以及可以从网中的不同顶点出发求出对应的最小生成树。

各程序模块之间的层次（调用）关系，用流程图表示如图3.1所示。否。否。

是。图3.1程序流程图。

流程图反映了整个算法中各个子函数之间的嵌套调用，从主函数开始顺序往下执行，首先调用creat()函数创建无向网并采用邻接矩阵的方式来存储；然后将该网对应的邻接矩阵通过调用display()函数输出；最后调用prim ()函数求出该网所对应的最小生成树，并且在prim ()函数中通过嵌套调用minium ()函数求出辅助数组close中权值最小的边，从而完成了本设计的要求。

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了