《数据结构》课程设计.docx

1、数据结构课程设计 长江大学算法与数据结构课程设计班 级：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、 创建有向图的邻接矩阵2 创建有向图的邻接表3 拓扑排序4 有向网的基本操作及应用1 创建有向网的邻接矩阵2 创建有向网的邻接表3 关键路径4 单源最短路径第二步：设计菜单 void ShowMainMenu() coutn; cout *图的基本操作及应用*n; cout * 1 无向图的基本操作及应用 *n; cout * 2 无向网的基本操作及应用 *n; cout * 3 有向图的基本操作及应用 *n; cout * 4 有向网的基本操作及应用 *n; cout * 5 退出 *n; cout *n;void UDG() MGraph MG; ALGraph ALG; int n; d

3、o coutn; cout *无向图的基本操作及应用*n; cout * 1 创建无向图的邻接矩阵 *n; cout * 2 创建无向图的邻接表 *n; cout * 3 无向图的深度优先遍历 *n; cout * 4 无向图的广度优先遍历 *n; cout * 5 退出 *n; coutn; switch(n) case 1:CreatUDG_M(MG);break; case 2:CreatUDG_ALG(ALG); dispgraph(ALG);break; case 3:break; case 4:break; default: if (n!=5) cout错误，重新输入n; whil

4、e(n!=5);void UDN() MGraph MN; ALGraph ALN; int n; do coutn; cout *无向网的基本操作及应用*n; cout * 1 创建无向网的邻接矩阵 *n; cout * 2 创建无向网的邻接表 *n; cout * 3 prim算法求最小生成树 *n; cout * 4 kraskal算法求最小生成树 *n; cout * 5 退出 *n; coutn; switch(n) case 1:CreatUDN_M(MN);break; case 2:CreatUDN_ALG(ALN); dispgraph_N(ALN);break; case

5、3:break; case 4:break; default: if (n!=5) cout错误，重新输入n; while(n!=5); void DG() int n; do coutn; cout *有向图的基本操作及应用*n; cout * 1 创建有向图的邻接矩阵 *n; cout * 2 创建有向图的邻接表 *n; cout * 3 拓扑排序 *n; cout * 4 退出 *n; coutn; switch(n) case 1:break; case 2:break; case 3:break; default: if (n!=4) cout错误，重新输入n; while(n!=4

6、);void DN() int n; do coutn; cout *有向网的基本操作及应用*n; cout * 1 创建有向网的邻接矩阵 *n; cout * 2 创建有向网的邻接表 *n; cout * 3 关键路径 *n; cout * 4 单源顶点最短路径问题 *n; cout * 5 退出 *n; coutn; switch(n) case 1:break; case 2:break; case 3:break; case 4:break; case 5:break; default: if (n!=6) coutn; switch(n) case 1:UDG();break; ca

7、se 2:UDN();break; case 3:DG();break; case 4: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）三、使用说明按照图中的提示进行输入输出；

8、但有些事情是需要注意的：一：四种图的邻接矩阵存储结构的创建有相应的出错机制，出错后一般不会让执行程序终止，而四种图的邻接表存储结构的创建没有，只有在输入图的顶点数和弧（边）数时会有出错机制，在这以后输入出错就会让程序终止执行；二：邻接表存储结构中，在输入弧的弧头弧尾或边的顶点x和顶点y时，必须和之前输入的顶点名完全相同，邻接矩阵有出错机制，不用担心输错；三、输入顶点数，边数，弧数，权值只能是正整数，不能是字母或标点符号；四、在求关键路径和单源最短问题时，要确认输入的图是否是与该算法相关的图；五、每次输入多余的数据会被屏蔽掉，不会出错。四、难点与收获对我来说，该程序设计的难度比较大，其主要难点有

9、以下几点：一：设计的知识范围广，由于数据结构学得不是很好，所以很多算法只是一知半解，虽然能够理解，但要是自己独立去实现，不去查找和参考相关的资料，几乎是很难按时完成任务；二：代码没有好的设计理念和层次，完成时警告非常多，有时候感觉这有点打击人的信心；三：部分算法只是知其然，而不知所以然，没有完全掌握。比如，该程序所以的实现代码中只有邻接矩阵和邻接表存储结构的定义，四种图的创建和显示是自己独立完成的，其他的算法只是修改了一下，自己敲上去的。还有图的邻接矩阵有相应的较为完善的出错机制，输入错误和多余的输入并不会引起程序死机，限于时间关系，图的邻接存储结构只有简单的出错机制。我的主要收获有以下几点：

10、1调试。这是我收获最大的一部分之一。不管你解决问题的方案写的多完善，不管你的实现过程写的多么详细，如果程序调试不过关，一切都是白搭。尤其是超过 200行的代码，如果你不懂得调试，那么你的程序将会漏洞百出，甚至不知道错在何处。2.编程模块。超过 300 行的代码最好放在另一个头文件中，用#include包含在主程序中，避免主程序过于臃肿，也可以做成编程模块，还提高了程序的重用率。3.fllush（stdin）和头文件crtexe.c.。在输入过程中，如果不小心多输入了其他的字符，很可能让执行程序终止执行，fflush(stdin)可以只提取要输入的那部分字符，将多余的输入舍弃。五、实现代码下面依

11、次有以下几个文件：Main.cpp, Graph.h , Sqstack.h, CirQueue.h, UDGraph,h, UNGraph.h , DGraph.h, DNGraph.h。 /main.cpp#include #include using namespace std;typedef char VertexType;#include Graph.h#include UDGraph.h#include UNGraph.h#include DGraph.h#include DNGraph.hvoid ShowMainMenu()coutn;cout*图的基本操作及应用*n;cout

12、* 1 无向图的基本操作及应用*n;cout* 2 无向网的基本操作及应用*n;cout* 3 有向图的基本操作及应用*n;cout* 4 有向网的基本操作及应用*n;cout* 5 退出*n;cout*n;void UDG()MGraph MG;ALGraph ALG;int n;docoutn;cout*无向图的基本操作及应用*n;cout* 1 创建无向图的邻接矩阵*n;cout* 2 创建无向图的邻接表*n;cout* 3 无向图的深度优先遍历*n;cout* 4 无向图的广度优先遍历*n;cout* 5 退出*n;coutn;switch(n)case 1:CreatUDG_M(MG

13、);break;case 2:CreatUDG_ALG(ALG);dispgraph(ALG);break;case 3:CreatUDG_ALG(ALG);dfstraverse(ALG);/进行深度优先遍历的输出break;case 4:CreatUDG_M(MG);BFSTraver(MG);/进行广度优先遍历的输出break;default:if (n!=5)cout错误，重新输入n;while(n!=5);void UDN()MGraph MG;ALGraph ALG;int n;docoutn;cout*无向网的基本操作及应用*n;cout* 1 创建无向网的邻接矩阵*n;cout

14、* 2 创建无向网的邻接表*n;cout* 3 prim 算法求最小生成树*n;cout* 4 kraskal 算法求最小生成树*n;cout* 5 退出*n;coutn;switch(n)case 1:CreateUDN_M(MG);break;case 2:CreateUDN(ALG);dispUDN(&ALG);break;case 3:CreateUDN_M(MG);prim(MG);break;case 4:CreateUDN_M(MG);Kruskal(MG);break;default:if (n!=5)cout错误，重新输入n;while(n!=5);void DG()MGra

15、ph MG;ALGraph ALG;int n;docoutn;cout*有向图的基本操作及应用*n;cout* 1 创建有向图的邻接矩阵*n;cout* 2 创建有向图的邻接表*n;cout* 3 拓扑排序*n;cout* 4 退出*n;coutn;switch(n)case 1:CreatDG_M(MG);break;case 2:CreatDG_ALG(ALG);dispgraph(ALG);break;case 3:CreatDG_ALG(ALG);TopologicalSort(ALG);break;default:if (n!=4)cout错误，重新输入n;while(n!=4);

16、void DN()MGraph MG;ALGraph ALG;int n;PathMatrix p1;ShortPathTable d1;dist2 d;path2 p;docoutn;cout*有向网的基本操作及应用*n;cout* 1 创建有向网的邻接矩阵*n;cout* 2 创建有向网的邻接表*n;cout* 3 关键路径*n;cout* 4 单源顶点最短路径问题*n;cout* 5 每对顶点最短路径问题*n;cout* 6 退出*n;coutn;switch(n)case 1:CreateDNG_M(MG);break;case 2:CreateDN(ALG);dispDN(&ALG)

17、;break;case 3:CreateDN(ALG);CriticalPath(ALG);break;case 4:CreateDNG_M(MG);ShortestPath(MG,1,p1,d1);break;case 5:CreateDNG_M(MG);Floyd(MG,p,d);break;default:if (n!=6)coutn;switch(n)case 1:UDG();break;case 2:UDN();break;case 3:DG();break;case 4:DN();break;default:if (n!=5)cout=S.stacksize)/判断栈没有满S.ba

18、se=(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;int Pop(SqStack &S,ElemType &e)/*删除栈顶元素*/if(S.top=S.base) return 0;e=*-S.top;-S.length;return 1;-/CirQueue.hstruct Queue/创建队列的数据结构类型int save20;int

19、tou,wei;/initialvoid InitQueue(Queue *q)/初始化一个队列，各元素都至空int i;for(i=0;isavei=0;q-tou=0;q-wei=0;/EnQueuevoid EnQueue(Queue *q,int n)/在队尾插入元素 n 为队列的一个新元素q-saveq-wei=n;q-wei+;/DeQueuevoid DeQueue(Queue *q,int &n)/删除 q 的队头元素，并用 n 返回n=q-saveq-tou;q-tou+;/Emptyint QueueEmpty(Queue *q)/把整个队列置空if(q-tou=q-wei)return 0;elsereturn 1;/