《数据结构》课程设计.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;
}
//
升级会员 