数据结构课程设计报告

1、数据结构课程设计报告2015年 6 月一、构造 n 个城市连接的最小生成树一、问题描述一个地区的 n 个城市间的距离网，用 Prim 算法或 Kruskal 算法建立最小生成树，并计算得到的最小生成树的代价。基本要求：（ 1） 城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。（ 2）表示城市间距离网的邻接矩阵( 要求至少6 个城市， 10 条边 )二、设计思路这个问题主要通过PRIM的基本算法实现求最小生成树，该算

2、法的主要思想是：设置两个辅助一维数组lowcost 和 closevertex，其中 lowcost同来保存集合V-U 中各顶点与集合U 中各顶点构成的边中具有最小权值的边的权值；数组closevertex用来保存依附于该边的在集合U 中的顶点。假设初始状态时， U=（ u0）（ u0 为出发的顶点），这时有lowcost0=0;它表示顶点u0 已加入集合 U中，数组lowcost 的其他各分量的值是顶点u0 到其余各顶点所构成的直接边的权值。然后不断选区权值最小的边（ ui ，uk ），每选取一条边，就将lowcost （ k）置为 0，表示顶点 uk 已加入集合 U中。优于顶点uk 从集合

3、 V-U 进入集合U 后，这两个集合的内容发生了变化，就要依据具体情况更新数组lowcost和 closevertex中部分分量的内容。最后closevertex中即为所建立的最小生成树。三、数据结构定义#define INFINITY 30000 #define MaxVertexNum 30/定义一个权值的最大值图的最大顶点数为30typedef structint n,e;/城市数和道路数int edgesMaxVertexNumMaxVertexNum; /MGraph;邻接矩阵typedef structint adjvertex; int lowcost; ClosEdge;/某顶

4、点与已构造好的部分生成树的顶点之间权值最小的顶点某顶点与已构造好的部分生成树的顶点之间的最小权值用 PRIM 算法求最小生成树时的辅助数组四、系统功能模块介绍开始输入城市数、道路数G=（ V,E ）为一网图，建立无向图邻接矩阵求最小生成树辅助数组close_edge初始化 ; U=ufor(i=0;i<vertexNum-1;i+)在辅助数组中选择权值最小的顶点k 并将 k 并入 U 集，修改辅助数组i<vertexNum-1？是否最小生成树构造完毕打印出最小生成树的各条边及权值五、程序清单（ 1）创建城市间的邻接矩阵存储并输出矩阵void CreateMgraph(MGraph

5、*G) /建立无向图G 的邻接矩阵存储int i,j;int start,end,weight;printf("请输入城市数和道路数:");cin>>G->n>>G->e;cout<<"n="<<G->n<<",e="<<G->e;for(i=0;i<G->n;i+)/初始化邻接矩阵for(j=0;j<G->n;j+)if(i=j)G->edgesij=0;elseG->edgesij=INFINITY;

6、cout<<endl<<" 请输入一条道路连接的两城市和其间的距离 for(i=0;i<G->e;i+):"<<endl;cin>>start>>end>>weight;G->edgesstartend=weight;G->edgesendstart=weight;cout<<" 邻接矩阵为：for(i=0;i<G->n;i+) /"<<endl;输出邻接矩阵for(j=0;j<G->n;j+)if(G->

7、edgesij=INFINITY)cout<<" "<<" "elsecout<<G->edgesij<<" "cout<<endl;（ 2 ）用 PRIM 算法求城市间的最小生成树并得到最小代价void MiniSpanTree_PRIM(MGraph *G,int u)ClosEdge close_edgeMaxVertexNum;int i,j,w,k;int totalCost=0;for(i=0;i<G->n;i+)if(i!=u)close_ed

8、gei.adjvertex=u;close_edgei.lowcost=G->edgesui;close_edgeu.lowcost=0;for(i=0;i<G->n-1;i+)w=INFINITY;for(j=0;j<G->n;j+)if(close_edgej.lowcost!=0&&close_edgej.lowcost<w)w=close_edgej.lowcost;k=j;close_edgek.lowcost=0;for(j=0;j<G->n;j+)if(G->edgeskj<close_edgej.low

9、cost)close_edgej.adjvertex=k;close_edgej.lowcost=G->edgeskj;cout<<"打印最小代价生成树的各条边："<<endl;for(i=0;i<G->n;i+)if(i!=u)cout<<i<<"->"<<close_edgei.adjvertex<<","<<G->edgesiclose_edgei.adjvertex<<endl; totalCost=t

10、otalCost+G->edgesiclose_edgei.adjvertex;cout<<"总代价为： "<<totalCost<<endl;（ 3 ）主函数int main()int v;MGraph G;cout<<"*构造 n 个城市连接的最小生成树问题*"<<endl<<endl;cout<<"1.输入城市个数和道路数"<<endl;cout<<"2.输入相邻两城市和其间的距离"<<

11、;endl;cout<<"3.以邻接矩阵存储各个城市间的距离并输出矩阵"<<endl;cout<<"4.用 PRIM算法得出 n 个城市连接的最小生成树"<<endl;cout<<"5.打印 n 个城市连接的最小生成树路径"<<endl<<endl;CreateMgraph(&G);cout<<" 请输入从哪个城市开始："cin>>v;MiniSpanTree_PRIM(&G,v);retur

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

13、3）打印最小生成树各条边及最小代价七、课程设计总结最小生成树主要由PRIM算法完成，通过整体构思，先确立了基本步骤：1. 建立一个具有n 个顶点的无向图2.创建一个邻接矩阵来存储该图，然后初始化矩阵3.根据 Prim 算法，得到了最小生成树以及各边的权值。在不断地努力下，完成了此这次课程设计的第一个任务。本次实验，既巩固和加深了对数据结构的理解，认识到数据结构是计算机专业一门重要的专业技术基础课程，还提高了我综合运用本课程所学知识的能力，提高了我的组织数据及编写程序的能力。而且在设计的过程中，并不是单纯的看看教材就能解决我们的实际问题，所以还要去查找各种我们所需要的资料。要完成一个课程设计的课

14、题并不是一次就能编译成功的，中间会出现很多的大问题小问题，改错是个很繁琐的问题。通过这次课程设计培养了我独立思考，深入研究，分析问题，解决问题的能力。二、运动会分数统计一、问题描述参加运动会有n 个学校，学校编号为1n。比赛分成m个男子项目，和w 个女子项目。项目编号为男子1m，女子 m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5 、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。(m<=20,n<=20)功能要求：1) 可以输入各个项目的前三名或前五名的成绩；2) 能统计各学校总分，3) 可以按学校编号、学校总分、男女团

15、体总分排序输出；4) 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。规定：输入数据形式和范围：20 以内的整数 ( 如果做得更好可以输入学校的名称，运动项目的名称 )输出形式：有中文提示，各学校分数为整型界面要求：有合理提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。二、设计思路根据运动会分数统计系统的问题分析及要求，可以将此系统分为四个模块：信息输入模块，信息统计模块，信息排序模块和信息查询模块。（ 1）信息输入模块：输入各个学校编号，项目编号，规定该项目取前3 名还是前5 名，然后输入此项目获得的名次数目以及获得的名次，得分由系统自动统计。（

16、 2）信息统计模块：主要用来统计各个学校获得的总分情况。主要涉及函数tongjiScore()。（ 3）信息排序模块：可以对学生信息实现按学校编号，按学校总得分，按男团体总分，按女团体总分排序。主要涉及函数Sort( ），sort_schoolNum()，sort_score()，sort_maleScore()，sort_femaleScore()（ 4）信息查询模块：可以按学校编号查询学校某个项目情况，按项目编号查询取得名次的学校。主要涉及函数 Query_itemNum() ， Query_schoolNum() 。三、数据结构定义（ 1 ）项目数据表：运动会开始前必须详细制定本次运动会

17、所需的参赛项目为接下来报名、场地的准备提供依据。该数据表包括每个项目的编号、取名次的数目、要取的名次以及各个名次对应的分数。在初始输入时仅输入项目编号、取名次的数目及要取的名次，而各名次对应的分数将由系统自动统计。#include<iostream>#include <windows.h>using namespace std;#define n 4/#define m 2/#define w 2/typedef struct学校数目男子项目个数女子项目个数int itemNum;int top;/int range5;int mark5;ItemNode;/项目编号取

18、名次数目名次分数（ 2 ）学校数据表：该数据表存储了各个参赛学校的总体情况，包括学校的编号、女子团体总分和学校总分。其中学校编号是提前输入的，而其他三项内容将在输入得分以及名次等信息后由系统进行自动统计。男子团体总分、typedef structint schoolNum; /学校编号int score;/学校总分int maleScore;/男团体总分int femaleScore; /女团体总分ItemNode cm+w; /项目数组SchoolNode;SchoolNode s20;四、系统功能模块介绍（ 1）总体设计运动会分数统计系统输入信息统计总分信息排序信息查询按按按按按按学学男女

19、学项校校团团校目编总总总编编号分分分号号（ 2 ）信息输入及分数统计功能void input( )是信息输入函数，输入学校编号，项目编号、取名次的数目及要取的名次，而各名次对应的分数将由系统自动统计。信息输入完后，可以用tongjiScore()函数统计各个学校总分。开始初始化数组si,i=1;i<=n输入学校编号、项目编号、名次等信息i+;i<n?是tongjiScore()结束（ 2）信息排序功能menu2( )，sort_schoolNum() ， sort_score()，sort_maleScore() ，sort_femaleScore() 是排序输出菜单函数以及四种排

20、序输出。输出一个菜单显示各种排序功能，利用switch 语句实现按学校编号，按学校总分，按男团体总分，按女团体总分排序。下图采用直接插入排序的方法实现按男团体总分由低到高输出。开始显示排序菜单，选择排序功能for(i=2;i<=n;i+)while(s0.maleScore<sj.maleScore&&j>0)NYN交换数据输出结束（ 3）信息查询功能menu3( )，Query_schoolNum( ) ，Query_itemNum( )函数是查询菜单函数以及两个信息查询函数。显示主菜单，利用switch( ) 语句选择功能，实现按学校编号查询某项目和按项目

21、编号查询信息，并输出该学校某个项目情况或者某个项目取得前3 或前 5 的学校信息。按学校编号查询某项目功能如下：开始输入查询的学校编号学校是否存在？否是输入查询的项目编号提示错误，返回主菜单项目是否存在？否是循环查找；输出信息结束五、程序清单（ 1）欢迎界面void menu()cout<<endl<<endl<<endl<<endl<<endl<<endl<<endl;cout<<"(o)(o)"<<endl;cout<<"(o) (o)&qu

22、ot;<<endl;cout<<"(o)欢迎使用运动会分数统计系统！ (o)"<<endl;cout<<"(o) (o)"<<endl;cout<<"(o)(o)"<<endl;Sleep(1200);system("cls");（ 2 ）输入信息函数void input()int i,j,k,t; for(i=1;i<=n;i+) si.score=0;si.maleScore=0;si.femaleScore=0;for(

23、i=1;i<=n;i+)cout<<"请输入第"<<i<<"个学校编号( 共 "<<n<<"个 ):"cin>>si.schoolNum;for(j=0;j<m+w;j+)cout<<"请输入项目编号( 共 "<<m+w<<" 个 ):"cin>>si.ci.itemNum;cout<<"取前3 名or前 5 名:"cin>&g

24、t;si.cj.top;cout<<"获得几个名次："cin>>k;for(t=0;t<k;t+)cout<<" 请输入取得的名次 cin>>si.cj.ranget; if(si.cj.top=3) switch(si.cj.ranget) :"case 1:si.cj.markt=5; break;case 2:si.cj.markt=3; break;case 3:si.cj.markt=2; break;if(si.cj.top=5)switch(si.cj.ranget)case 1:si.

25、cj.markt=7; break;case 2:si.cj.markt=5; break;case 3:si.cj.markt=3; break;case 4:si.cj.markt=2; break;case 5:si.cj.markt=1; break;si.score=si.score+si.cj.markt; /if(j<m)si.maleScore=si.maleScore+si.cj.markt;按取前三名还是取前五名分别记分elsesi.femaleScore=si.femaleScore+si.cj.markt;cout<<endl;cout<<

26、" 信息已输入完！"<<endl<<endl;（ 3 ）统计总分函数void tongjiScore()cout<<"*统计各个学校总分的结果为：*"<<endl;cout<<"|-|-|n" ;cout<<"|学校编号 |学校总分 |n"cout<<"|-|-|n" ;for(int i=1;i<=n;i+)cout<<"|"<<setw(8)<<s

27、i.schoolNum<<"|"<<endl;|"<<setw(8)<<si.score<<"cout<<"|-|-|n" ;（ 4 ）按学校编号排序函数void sort_schoolNum()/按学校编号输出printf("nt*按学校编号排序输出*n");cout<<"|-|-|-|-|n" ;cout<<"|学校编号|男团体总分|女团体总分cout<<"|-|-

28、|-|-|n" ;|学校总分| n"for(int i=1;i<=n;i+)cout<<" |"<<setw(8)<<si.schoolNum<<" |"<<setw(8)<<si.femaleScore<<" |"<< setw(6)<<si.score<<" |"<<endl ; cout<<" |-|-|-|-|n" ;

29、cout<<endl;|"<<setw(8)<<si.maleScore<<"（ 5 ）按学校总分排序函数，采用了直接插入排序算法。（按男团体总分排序函数、按女团体总分排序函数与按总分排序方法差不多，就不贴这两个函数了）void sort_score()/按学校总分输出int i,j;for(i=2;i<=n;i+)s0.maleScore=si.maleScore;s0.femaleScore=si.femaleScore;s0.score=si.score;s0.schoolNum=si.schoolNum;j=i-

30、1;while(s0.score<sj.score&&j>0)sj+1.maleScore=sj.maleScore;sj+1.femaleScore=sj.femaleScore;sj+1.score=sj.score;sj+1.schoolNum=sj.schoolNum;j-;sj+1.maleScore=s0.maleScore;sj+1.femaleScore=s0.femaleScore;sj+1.score=s0.score;sj+1.schoolNum=s0.schoolNum;printf("nt*按学校总分排序输出*n");c

31、out<<"|-|-|-|-|n" ;cout<<"|学校编号 |学校总分| 男团体总分 |女团体总分 | n"cout<<"|-|-|-|-|n" ;for(i=1;i<=n;i+)cout<<"|"<<setw(8)<<si.schoolNum<<"|"<<setw(8)<<si.maleScore<<"|"<<setw(8)<&

32、lt;si.femaleScore<<"cout<<"|-|-|-|-|n" ;|"<<endl ;|"<<setw(8)<<si.score<<" cout<<endl;（ 6 ）按学校编号查询学校某个项目情况函数void Query_schoolNum() /按学校编号查询某项目int i,j,k;cout<<" 要查询的学校编号:"cin>>i;if(i>n)cout<<"错

33、误 ! 这个学校没有参加此次运动会!"<<endl;elsecout<<"请输入要查询的项目编号："cin>>j;printf("nt*按学校编号查询某项目*n");if(j>m+w|j<=0)cout<<" 此次运动会没有这个项目！"<<endl;elsecout<<" 这个项目取前"<<s1.cj-1.top<<"for(k=0;k<5;k+)if(si.cj-1.rangek!

34、=0)名 , 该学校的成绩如下:"<<endl<<endl;printf("nt*cout<<"|-|-|-|-|n" ;按学校编号查询某项目学校编号项目编号*n");取得的得分取得的名次n"cout<<"|-|-|-|-|n" ;cout<<"|"<<setw(8)<<i<<" |"<<setw(8)<<j<<" |"<<setw(8)<<si.cj-1.markk<<"|"<<setw(8)<<si.cj-1.rangek<<"|"<<endl ;cout<<"|-|-|-|-|n" ;（ 7 ）按项目