数据结构课程设计

目录。前言 21.1设计背景和意义 2

1.1.1数据结构简介 2

1.1.2选择算法的原因 2

1.2设计的原理和内容 2

工程概况 2

2.1 项目所用的时间 2

2.2项目负责人 2

2.3项目指导人 2

正文 33.1 设计的目的和意义 3

3.2 目标和总体方案 3

3.3 设计方法和内容 3

3.3.1 硬件环境 4

3.3.2软件环境 4

3.3.3 设计流程图 4

3.4 程序的设计思想和内容 4

3.4.1程序设计最小生成树的基本运行环境 5

3.4.3运行分析及要求 7

3.4.4测试结果及界面的截图 8

3.5 结论 9

参考文献 10

前言。1.1设计背景和意义。

1.1.1数据结构简介。

数据结构是计算机程序设计的重要理论设计基础，它不仅是计算机学科的核心课程，而且成为其他理工专业的热门选修课。数据结构是计算机存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率的算法。

比如在计算机**处理器中，cpu接到一个中断请求便会停下当前正在执行的指令去处理这个中断请求完成中断操作，首先要做的就是保护现场。保护现场需要将下一条指令的地址指针和当前指令返回地址等重要的数据进行存储。在众多的数据结构中，这些重要的数据被存储到栈这个数据结构中。

1.1.2选择算法的原因。

在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。

有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。

1.2设计的原理和内容。

本次程序设计采用c语作为描述和实现算法的程序语言，主要的设计思路就是完成对图的操作，如图的构造、图的最短路径、图的输出等等，这些操作都是通过c语言程序来实现的。最后的结果就是运行程序时能够完成对以上设计的操作。

工程概况。2.1 项目所用的时间。

从这个项目开始到结束总共历时七天。完成于2024年12月18日。

2.2项目负责人。

张振东，男，计算机科学与技术14-1，学生。

2.3项目指导人。

吴刚，男，信息工程学院教师，讲师。

正文。3.1 设计的目的和意义。

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

（1）利用普利姆算法求通信网络的最小生成树；（2）输出生成树中各边及权值。

3.2 目标和总体方案

1)、如何选择存储结构去建立一个带权网络。

2)、如何在所选存储结构下输出这个带权网络。

3)、如何实现prim算法的功能。

4)、如何从每个顶点开始找到所有的最小生成树的顶点。

5)、如何输出最小生成树的边及其权值。

此问题的关键在于如何实现prim算法，实现的过程中如何得到构成最小生成树的所有顶点，此外输出也是一个关键问题所在，在此过程中经过了多次调试。

首先我们对问题进行大致的概要分析：

这个问题主要牵涉到通过prim的基本算法思想实现程序所要求的功能，该算法的主要思想是：假设n=（v，）是连通网，te是n上最小生成树中边的集合。算法从u=( u0∈v),te={}开始，重复执行下述操作：

在所有u∈u,v∈v-u的边（u,v）∈e中找一条代价最小的边（u0,v0）并入集合te，同时v0并入u，直至u=v为止。此时te中必有n-1条边，则t=（v，）为n的最小生成树。

问题的输入数据的格式为：首先提示输入带权网络的顶点边数，我定义的为整形数据型，然后输入每一条边的信息，即边的两个顶点以及权值，是十进制整数类型，这样我们就建立一个带权网络，并用邻接矩阵来存储，生成一个方阵显示出来。

问题的输出数据格式为：输出是以邻接矩阵存储结构下的方阵，以及从不同顶点开始省城的最小生成树。

题目要求以及达到目标：题目要求用普利姆算法实现任意给定的网和顶点的所有最小生成树，并且输出各边的权值。

由于时间只有七天，故做了如下的计划安排，将这项工程分为两大部分：程序的设计和程序的调试。

首先在程序的设计部分由分为几个步骤：

第一步：查阅有关数据结构栈操作的资料，用一到两天的时间。

第二步：设计这个项目的整体架构和算法，用一到两天的时间。

第三步：选择一门程序设计语言进行算法的描述，两天的时间。

其次，进行程序的调试，用一天。

3.3 设计方法和内容。

3.3.1 硬件环境。

微型计算机：联想台式品牌机。

**处理器：pentuim 4 主频：3.0ghz

主存容量： 512m

硬盘容量： 80g

3.3.2软件环境。

windows xp 操作系统。

microsoft notepad 记事本程序。

microsoft visual c++编译器。

3.3.3 设计流程图。

图3-1 程序流程图。

3.4 程序的设计思想和内容。

prim算法求最小生成树的主要思想。此算法是普利姆与2024年提出的一种构造最小生成树的算法，主要思想是：假设n=（v，）是连通网，te是n上最小生成树中边的集合。

算法从u=( u0∈v),te={}开始，重复执行下述操作：在所有u∈u,v∈v-u的边（u,v）∈e中找一条代价最小的边（u0,v0）并入集合te，同时v0并入u，直至u=v为止。此时te中必有n-1条边，则t=（v，）为n的最小生成树。

对于最小生成树问题。

最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。

3.4.1程序设计最小生成树的基本运行环境。

1）预处理。

#include <>

#define inf 9999

#define max 40

#define linelenght 77

2）普里姆算法。

void prim(int g[max],int nprim的函数 */

int lowcost[max],closest[max];

int i,j,k,min;

for(i=2;i<=n;in个顶点，n-1条边 */

lowcost[i]=g[1][i初始化 */

closest[i]=1顶点未加入到最小生成树中 */

lowcost[1]=0标志顶点1加入u集合 */

for(i=2;i<=n;i形成n-1条边的生成树 */

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了