数据结构课程设计报告

《数据结构》

课程设计报告。

2023年6月。

一、构造n个城市连接的最小生成树。

1、问题描述

一个地区的n个城市间的距离网，用prim算法或kruskal算法建立最小生成树，并计算得到的最小生成树的代价。基本要求：

（1）城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。

（2）表示城市间距离网的邻接矩阵(要求至少6个城市，10条边)

2、设计思路。

这个问题主要通过prim的基本算法实现求最小生成树，该算法的主要思想是：设置两个辅助一维数组lowcost和closevertex，其中lowcost同来保存集合v-u中各顶点与集合u中各顶点构成的边中具有最小权值的边的权值；数组closevertex用来保存依附于该边的在集合u中的顶点。假设初始状态时，u=（u0）（u0为出发的顶点），这时有lowcost[0]=0;它表示顶点u0已加入集合u中，数组lowcost的其他各分量的值是顶点u0到其余各顶点所构成的直接边的权值。

然后不断选区权值最小的边（ui，uk），每选取一条边，就将lowcost（k）置为0，表示顶点uk已加入集合u中。优于顶点uk从集合v-u进入集合u后，这两个集合的内容发生了变化，就要依据具体情况更新数组lowcost和closevertex中部分分量的内容。最后closevertex中即为所建立的最小生成树。

3、数据结构定义。

#define infinity 30000 //定义一个权值的最大值

#define maxvertexnum 30 //图的最大顶点数为30

typedef struct

int n,e城市数和道路数。

int edges[maxvertexnum][maxvertexnum]; 邻接矩阵。

mgraph;

typedef struct

int adjvertex; /某顶点与已构造好的部分生成树的顶点之间权值最小的顶点。

int lowcost; /某顶点与已构造好的部分生成树的顶点之间的最小权值。

closedge用prim算法求最小生成树时的辅助数组

4、系统功能模块介绍。

输入城市数、道路数。

g=（v,e）为一网图，建立无向图邻接矩阵。

求最小生成树。

辅助数组close_edge初始化； u=

for(i=0;i

在辅助数组中选择权值最小的顶点k并将k并入u集，修改辅助数组。i是。否。

最小生成树构造完毕。

打印出最小生成树。

的各条边及权值。

5、程序清单。

1）创建城市间的邻接矩阵存储并输出矩阵。

void createmgraph(mgraph *g) /建立无向图g的邻接矩阵存储。

int i,j;

int start,end,weight;

printf("请输入城市数和道路数：")

cin>>g->n>>g->e;

cout<<"n="

for(i=0;in;i初始化邻接矩阵。

for(j=0;jn;j++)

cout< for(i=0;ie;i++)

cout<<"邻接矩阵为："

cout< }

2）用prim算法求城市间的最小生成树并得到最小代价。

void minispantree_prim(mgraph *g,int u)

closedge close_edge[maxvertexnum];

int i,j,w,k;

int totalcost=0;

for(i=0;in;i++)

if(i!=u)

close_edge[u].lowcost=0;

for(i=0;in-1;i++)

cout<<"打印最小代价生成树的各条边："

if(i!=u)

cout<<"总代价为："<

3）主函数。

int main()

int v;

mgraph g;

cout《构造n个城市连接的最小生成树问题< cout<<1.输入城市个数和道路数"< cout<<2.输入相邻两城市和其间的距离"< cout<<3.

以邻接矩阵存储各个城市间的距离并输出矩阵"< cout<<4.用prim算法得出n个城市连接的最小生成树"< cout<<5.打印n个城市连接的最小生成树路径"< createmgraph(&g);

cout<<"请输入从哪个城市开始：";

cin>>v;

minispantree_prim(&g,v);

return 0;

6、运行及调试分析。

1、调试分析。

本程序的主要功能是对无向网进行邻接矩阵的初始化，然后用prim算法求出城市间的最小生成树，得出最小代价。prim算法的思路是逐步将城市纳入生成树中，这里的关键步骤是要找到权值最小的顶点k，在prim算法中，第一个for循环的执行次数为n-1，第二个for循环中又包括一个while循环和一个for循环，执行次数为2（n-1）（n-1），所以prim算法的时间复杂度是o（n*n）。由此可见，prim算法与网中边数无关，适合求边稠密的网的最小生成树。

2、测试结果。

1）输入城市间信息。

2）输出城市间邻接矩阵。

3）打印最小生成树各条边及最小代价。

7、课程设计总结。

最小生成树主要由prim算法完成，通过整体构思，先确立了基本步骤：1.建立一个具有n个顶点的无向图 2.

创建一个邻接矩阵来存储该图，然后初始化矩阵 3.根据prim算法，得到了最小生成树以及各边的权值。在不断地努力下，完成了此这次课程设计的第一个任务。

本次实验，既巩固和加深了对数据结构的理解，认识到《数据结构》是计算机专业一门重要的专业技术基础课程，还提高了我综合运用本课程所学知识的能力，提高了我的组织数据及编写程序的能力。而且在设计的过程中，并不是单纯的看看教材就能解决我们的实际问题，所以还要去查找各种我们所需要的资料。要完成一个课程设计的课题并不是一次就能编译成功的，中间会出现很多的大问题小问题，改错是个很繁琐的问题。

通过这次课程设计培养了我独立思考，深入研究，分析问题，解决问题的能力。

2、运动会分数统计。

一、问题描述。

参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。

不同的项目取前五名或前三名积分；取前五名的积分分别为，前三名的积分分别为；哪些取前五名或前三名由学生自己设定。(m<=20,n<=20) 功能要求：

1) 可以输入各个项目的前三名或前五名的成绩；

2) 能统计各学校总分，3) 可以按学校编号、学校总分、男女团体总分排序输出；

4) 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。

规定：输入数据形式和范围：20以内的整数(如果做得更好可以输入学校的名称，运动项目的名称)

输出形式：有中文提示，各学校分数为整型。

2、设计思路。

根据运动会分数统计系统的问题分析及要求，可以将此系统分为四个模块：信息输入模块，信息统计模块，信息排序模块和信息查询模块。

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了