《数据结构》课程设计.docx
《《数据结构》课程设计.docx》由会员分享,可在线阅读,更多相关《《数据结构》课程设计.docx(52页珍藏版)》请在冰点文库上搜索。
《数据结构》课程设计
长江大学
算法与数据结构
课程设计
班级:
13级****
姓名:
******
指导老师:
******
2015年6月22日~~2015年7月3日
一、设计方案和实现过程----------------------------------------------------P1
二、测试----------------------------------------------------------------------------P7
三、使用说明----------------------------------------------------------------------P11
四、难点与收获------------------------------------------------------------------P13
五、实现代码----------------------------------------------------------------P14
六、指导老师意见-----------------------------------------------------------P36
一、设计方案和实现过程
第一步:
设计一个基于VC或VS的应用程序。
要利用多级菜单实现各种功能。
内容如下:
1.无向图的基本操作及应用
1创建无向图的邻接矩阵
2创建无向图的邻接表
3无向图的深度优先遍历
4无向图的广度优先遍历
2.无向网的基本操作及应用
1创建无向网的邻接矩阵
2创建无向网的邻接表
3求最小生成树
3.有向图的基本操作及应用
1创建有向图的邻接矩阵
2创建有向图的邻接表
3拓扑排序
4.有向网的基本操作及应用
1创建有向网的邻接矩阵
2创建有向网的邻接表
3关键路径
4单源最短路径
第二步:
设计菜单
voidShowMainMenu()
{
cout<<"\n";
cout<<"***************图的基本操作及应用******************\n";
cout<<"*1无向图的基本操作及应用*\n";
cout<<"*2无向网的基本操作及应用*\n";
cout<<"*3有向图的基本操作及应用*\n";
cout<<"*4有向网的基本操作及应用*\n";
cout<<"*5退出*\n";
cout<<"***************************************************\n";
}
voidUDG()
{
MGraphMG;
ALGraphALG;
intn;
do
{
cout<<"\n";
cout<<"***************无向图的基本操作及应用***************\n";
cout<<"*1创建无向图的邻接矩阵*\n";
cout<<"*2创建无向图的邻接表*\n";
cout<<"*3无向图的深度优先遍历*\n";
cout<<"*4无向图的广度优先遍历*\n";
cout<<"*5退出*\n";
cout<<"****************************************************\n";
cin>>n;
switch(n){
case1:
CreatUDG_M(MG);break;
case2:
CreatUDG_ALG(ALG);
dispgraph(ALG);break;
case3:
break;
case4:
break;
default:
if(n!
=5)
cout<<"错误,重新输入\n";
}
}while(n!
=5);
}
voidUDN()
{
MGraphMN;
ALGraphALN;
intn;
do{
cout<<"\n";
cout<<"***************无向网的基本操作及应用***************\n";
cout<<"*1创建无向网的邻接矩阵*\n";
cout<<"*2创建无向网的邻接表*\n";
cout<<"*3prim算法求最小生成树*\n";
cout<<"*4kraskal算法求最小生成树*\n";
cout<<"*5退出*\n";
cout<<"****************************************************\n";
cin>>n;
switch(n){
case1:
CreatUDN_M(MN);break;
case2:
CreatUDN_ALG(ALN);
dispgraph_N(ALN);break;
case3:
break;
case4:
break;
default:
if(n!
=5)
cout<<"错误,重新输入\n";
}
}while(n!
=5);
}
voidDG()
{
intn;
do
{
cout<<"\n";
cout<<"***************有向图的基本操作及应用***************\n";
cout<<"*1创建有向图的邻接矩阵*\n";
cout<<"*2创建有向图的邻接表*\n";
cout<<"*3拓扑排序*\n";
cout<<"*4退出*\n";
cout<<"****************************************************\n";
cin>>n;
switch(n){
case1:
break;
case2:
break;
case3:
break;
default:
if(n!
=4)
cout<<"错误,重新输入\n";
}
}while(n!
=4);
}
voidDN()
{
intn;
do{
cout<<"\n";
cout<<"***************有向网的基本操作及应用***************\n";
cout<<"*1创建有向网的邻接矩阵*\n";
cout<<"*2创建有向网的邻接表*\n";
cout<<"*3关键路径*\n";
cout<<"*4单源顶点最短路径问题*\n";
cout<<"*5退出*\n";
cout<<"****************************************************\n";
cin>>n;
switch(n){
case1:
break;
case2:
break;
case3:
break;
case4:
break;
case5:
break;
default:
if(n!
=6)
cout<<"错误,重新输入\n";
}
}while(n!
=6);
}
voidmain()
{
intn;
do{
ShowMainMenu();
cin>>n;
switch(n){
case1:
UDG();break;
case2:
UDN();break;
case3:
DG();break;
case4:
DN();break;
default:
if(n!
=5)
cout<<"错误,重新输入\n";
}
}while(n!
=5);
}
无论多少级菜单,都可以用这种模式实现,并且当前菜单不用担心前面的问题,只需编写当前的功能函数
第三步:
添加功能函数
二、测试
1.无向图的基本操作及应用(课本P157,G2)
课本P168,(a)
2.无向网的基本操作及应用(类似课本P168,(a))
课本P174,(a)
3.有向图的基本操作及应用(课本P157,G1)
4.有向网的基本操作及应用(课本P188,G6)
三、使用说明
按照图中的提示进行输入输出;但有些事情是需要注意的:
一:
四种图的邻接矩阵存储结构的创建有相应的出错机制,出错后一般不会让执行程序终止,而四种图的邻接表存储结构的创建没有,只有在输入图的顶点数和弧(边)数时会有出错机制,在这以后输入出错就会让程序终止执行;
二:
邻接表存储结构中,在输入弧的弧头弧尾或边的顶点x和顶点y时,必须和之前输入的顶点名完全相同,邻接矩阵有出错机制,不用担心输错;
三、输入顶点数,边数,弧数,权值只能是正整数,不能是字母或标点符号;
四、在求关键路径和单源最短问题时,要确认输入的图是否是与该算法相关的图;
五、每次输入多余的数据会被屏蔽掉,不会出错。
四、难点与收获
对我来说,该程序设计的难度比较大,其主要难点有以下几点:
一:
设计的知识范围广,由于数据结构学得不是很好,所以很多算法只是一知半解,虽然能够理解,但要是自己独立去实现,不去查找和参考相关的资料,几乎是很难按时完成任务;
二:
代码没有好的设计理念和层次,完成时警告非常多,有时候感觉这有点打击人的信心;
三:
部分算法只是知其然,而不知所以然,没有完全掌握。
比如,该程序所以的实现代码中只有邻接矩阵和邻接表存储结构的定义,四种图的创建和显示是自己独立完成的,其他的算法只是修改了一下,自己敲上去的。
还有图的邻接矩阵有相应的较为完善的出错机制,输入错误和多余的输入并不会引起程序死机,限于时间关系,图的邻接存储结构只有简单的出错机制。
我的主要收获有以下几点:
1调试。
这是我收获最大的一部分之一。
不管你解决问题的方案写的多完善,不管你的实现过程写的多么详细,如果程序调试不过关,一切都是白搭。
尤其是超过200行的代码,如果你不懂得调试,那么你的程序将会漏洞百出,甚至不知道错在何处。
2.编程模块。
超过300行的代码最好放在另一个头文件中,用#include包含在主程序中,
避免主程序过于臃肿,也可以做成编程模块,还提高了程序的重用率。
3.fllush(stdin)和头文件crtexe.c.。
在输入过程中,如果不小心多输入了其他的字符,很可能让执行程序终止执行,fflush(stdin)可以只提取要输入的那部分字符,将多余的输入舍弃。
五、实现代码
下面依次有以下几个文件:
Main.cpp,Graph.h,Sqstack.h,CirQueue.h,UDGraph,h,UNGraph.h,DGraph.h,DNGraph.h。
//main.cpp
#include
#include
usingnamespacestd;
typedefcharVertexType;
#include"Graph.h"
#include"UDGraph.h"
#include"UNGraph.h"
#include"DGraph.h"
#include"DNGraph.h"
voidShowMainMenu()
{
cout<<"\n";
cout<<"***************图的基本操作及应用******************\n";
cout<<"*1无向图的基本操作及应用*\n";
cout<<"*2无向网的基本操作及应用*\n";
cout<<"*3有向图的基本操作及应用*\n";
cout<<"*4有向网的基本操作及应用*\n";
cout<<"*5退出*\n";
cout<<"***************************************************\n";
}
voidUDG()
{
MGraphMG;
ALGraphALG;
intn;
do
{
cout<<"\n";
cout<<"***************无向图的基本操作及应用***************\n";
cout<<"*1创建无向图的邻接矩阵*\n";
cout<<"*2创建无向图的邻接表*\n";
cout<<"*3无向图的深度优先遍历*\n";
cout<<"*4无向图的广度优先遍历*\n";
cout<<"*5退出*\n";
cout<<"*************************************************\n";
cin>>n;
switch(n){
case1:
CreatUDG_M(MG);break;
case2:
CreatUDG_ALG(ALG);
dispgraph(ALG);break;
case3:
CreatUDG_ALG(ALG);
dfstraverse(ALG);//进行深度优先遍历的输出break;
case4:
CreatUDG_M(MG);
BFSTraver(MG);//进行广度优先遍历的输出break;
default:
if(n!
=5)
cout<<"错误,重新输入\n";
}
}while(n!
=5);
}
voidUDN()
{
MGraphMG;
ALGraphALG;
intn;
do{
cout<<"\n";
cout<<"***************无向网的基本操作及应用***************\n";
cout<<"*1创建无向网的邻接矩阵*\n";
cout<<"*2创建无向网的邻接表*\n";
cout<<"*3prim算法求最小生成树*\n";
cout<<"*4kraskal算法求最小生成树*\n";
cout<<"*5退出*\n";
cout<<"****************************************************\n";
cin>>n;
switch(n){
case1:
CreateUDN_M(MG);break;
case2:
CreateUDN(ALG);
dispUDN(&ALG);break;
case3:
CreateUDN_M(MG);
prim(MG);break;
case4:
CreateUDN_M(MG);
Kruskal(MG);break;
default:
if(n!
=5)
cout<<"错误,重新输入\n";
}
}while(n!
=5);
}
voidDG()
{
MGraphMG;
ALGraphALG;
intn;
do
{
cout<<"\n";
cout<<"***************有向图的基本操作及应用***************\n";
cout<<"*1创建有向图的邻接矩阵*\n";
cout<<"*2创建有向图的邻接表*\n";
cout<<"*3拓扑排序*\n";
cout<<"*4退出*\n";
cout<<"****************************************************\n";
cin>>n;
switch(n){
case1:
CreatDG_M(MG);break;
case2:
CreatDG_ALG(ALG);
dispgraph(ALG);break;
case3:
CreatDG_ALG(ALG);
TopologicalSort(ALG);break;
default:
if(n!
=4)
cout<<"错误,重新输入\n";
}
}while(n!
=4);
}
voidDN()
{
MGraphMG;
ALGraphALG;
intn;
PathMatrixp1;
ShortPathTabled1;
dist2d;
path2p;
do{
cout<<"\n";
cout<<"***************有向网的基本操作及应用***************\n";
cout<<"*1创建有向网的邻接矩阵*\n";
cout<<"*2创建有向网的邻接表*\n";
cout<<"*3关键路径*\n";
cout<<"*4单源顶点最短路径问题*\n";
cout<<"*5每对顶点最短路径问题*\n";
cout<<"*6退出*\n";
cout<<"****************************************************\n";
cin>>n;
switch(n){
case1:
CreateDNG_M(MG);break;
case2:
CreateDN(ALG);
dispDN(&ALG);break;
case3:
CreateDN(ALG);
CriticalPath(ALG);break;
case4:
CreateDNG_M(MG);
ShortestPath(MG,1,p1,d1);break;
case5:
CreateDNG_M(MG);
Floyd(MG,p,d);
break;
default:
if(n!
=6)
cout<<"错误,重新输入\n";
}
}while(n!
=6);
}
voidmain()
{
intn;
do{
ShowMainMenu();
cin>>n;
switch(n){
case1:
UDG();break;
case2:
UDN();break;
case3:
DG();break;
case4:
DN();break;
default:
if(n!
=5)
cout<<"错误,重新输入\n";
}
}while(n!
=5);
}
---------------------------------------------------------------------------------------------------------------------------
//Graph.h
#defineMAXVEX30
#defineMAXCOST1000
typedefintInfoType;
typedefstruct
{
VertexTypevexs[MAXVEX];
intarcs[MAXVEX][MAXVEX];
intvexnum,arcnum;
}MGraph;
typedefstructarcnode
{
intadjvex;//邻接点序号
intw;//边或狐上的权
InfoType*info;
structarcnode*next;
}ArcNode;
typedefstructvnode
{
VertexTypedata;//顶点信息
intindegree;
ArcNode*firstarc;//指向下一个边结点
}Vnode,AdjList[MAXVEX];
typedefstruct
{
AdjListvertices;
intvexnum,arcnum;
}ALGraph;
//Sqstack.h
#defineSTACK_INIT_SIZE999
typedefintElemType;
typedefstruct/*定义栈类型*/
{
ElemType*base;
ElemType*top;
intstacksize;
intlength;
}SqStack;
voidInitStack(SqStack&S)/*初始化栈*/
{
S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!
S.base)
exit(-1);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
S.length=0;
}
intStackEmpty(SqStackS)/*判断栈空否*/
{
if(S.top==S.base)return1;
else
return0;
}
voidPush(SqStack&S,ElemTypee)/*把数据压入栈*/
{
if(S.top-S.base>=S.stacksize)//判断栈没有满
{
S.base=(ElemType*)realloc(S.base,
(S.stacksize+10)*sizeof(ElemType));
if(!
S.base)exit(-1);
S.top=S.base+S.stacksize;
S.stacksize+=10;
}
*(S.top++)=e;
++S.length;
}
intPop(SqStack&S,ElemType&e)/*删除栈顶元素*/
{
if(S.top==S.base)return0;
e=*--S.top;
--S.length;
return1;
}
------------------------------------------------------------------------------------------------------------------------------
//CirQueue.h
structQueue//创建队列的数据结构类型
{
intsave[20];
inttou,wei;
};//initial
voidInitQueue(Queue*q)//初始化一个队列,各元素都至空
{
inti;
for(i=0;i<20;i++)
q->save[i]=0;
q->tou=0;
q->wei=0;
}//EnQueue
voidEnQueue(Queue*q,intn)//在队尾插入元素n为队列的一个新元素
{
q->save[q->wei]=n;
q->wei++;
}//DeQueue
voidDeQueue(Queue*q,int&n)//删除q的队头元素,并用n返回
{
n=q->save[q->tou];
q->tou++;
}
//Empty
intQueueEmpty(Queue*q)//把整个队列置空
{
if(q->tou==q->wei)
return0;
else
return1;
}
//