数据结构课程设计报告-最短路径算法-二叉树的三种遍历

1、数据结构课程设计报告班 级： 计算机科学与技术 132班姓 名：赖恒财扌旨导教师:董跃华成 绩：应习挖/豁信息工程学院2015年 7月 8日目录图的最短路径算法实现1. 需求分析11.1程序设计内容11.2设计要求12. 概要设计23详细设计23.1数据类型的定义 23.2功能模块的设计 23.3主程序流程94. 调试分析104.1 问题回顾和分析 104.2.经验和体会 115. 测试结果12二叉树的遍历1. 设计目的132. 需求分析142.1课程设计的内容和要求 142.2选题的意义及背景 143. 概要设计143.1设计思想143.2程序数据类型163.3 程序模块分析 163.3.1

2、置空栈163.3.2 入栈173.3.3 出栈173.3.4取栈顶操作 判空栈 173.4函数关系：184. 详细设计184.1二叉树算法程序截图和结果 1.85. 程序测试结果及问题分析 196. 总结20参考文献21附录1 22附录226图的最短路径算法实现 基于floyd最短路径算法1. 需求分析设计校园平面图，所含景点不少于8个。以图中顶点表示学校内各景点，存放景点的名称、景点介绍信息等；以边表示路径，存放路径长度信息。要求将这些信息保存在文件graph.txt中，系统执行时所处理的数据要对此文件分别进行读写操作。1.1程序设计内容1 从文件graph.txt中读取相应

3、数据，创建一个图，使用邻接矩阵表示图2 景点信息查询：为来访客人提供校园任意景点相关信息的介绍；3 .问路查询：为来访客人提供校园任意两个景点之间的一条最短路径1.2设计要求(1) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应。(2) 程序要添加适当的注释，程序的书写要采用缩进格式。(3) 根据实验报告模板详细书写实验报告，在实验报告中给出校园平面图。(4) 校园平面图中的校园景点信息保存在文件graph.txt中。2. 概要设计此程序主要实现以下几个模块，基于下面几个模块完全可以实现此题要求(1) .图的创建(2) .输出提供可选查询景点(3) .景点介绍查询处理(4)

4、 .查找两景点间的最短路径(5) . Floyd 算法(核心)3. 详细设计3.1数据类型的定义校园道路是双向通行的， 可设校园平面图是一个带权的无向图，用邻接矩阵表示此无向网。邻接矩阵的数据类型定义如下:typedef structchar name100;/名字char in fo10000;/介绍VertexType;/顶点结构typedef structVertexType vexs10;int arcs100100;/邻接矩阵int vexnu m,arc num;/顶点个数，边的个数MGraph;/图结构3.2功能模块的设计3.2.1 图的创建校园平面图可以表示成为一个无向网，用一

5、个MGraph 类型的变量 mg表示这张无向网。网中包含了景点的名字和信息，以及表示各景点之间是否有路可达邻接矩阵，同时还保存了景点个数和边数。其俱体定义如下：void ini tGraph() freope n(graph.txt, r, stdi n); sca nf(%d %d, &mg.vex num, &mg.arc nu m);/打开文件/读取顶点数、边数/循环输入景点、景点介绍for (int i = 0; i mg.vex num; i+) sca nf(%s %s, &mg.vexsi. name, &mg.vexsi.i nfo);/初始化矩阵，任意两点之间没有路for (

6、int i = 0; i 100; i+) for (i nt j = 0; j 100; j+) mg.arcsij = 999999;/输入距离for (int i = 0; i mg.arc num; i+) char from100;char to100;/f表示开始结点编号，t表示目的结点编号, int f, t, dis;scan f(%s %s %d, &from, &to, &dis);/把景点名字换成编号for (int j = 0; j mg.vex nu m; j+) if (strcmp(mg.vexsj. name, from) = 0) f = j; if (str

7、cmp(, to) = 0) t = j;/999999 相当于无穷大/开始结点名/结束结点名dis表示两点间的距离/创建邻接矩阵mg.arcsft = dis;mg.arcstf = dis;floyd();/floyd算法计算各两点之间的最短路径，后文定义freope n( CON, r, stdi n);/改变输入流程序中用到的关于学校各景点及信息的的数据保存在graph.txt文件中，文件的具体信息如下：Graph.txt8 15校门江西理工大学校门主教学校教学主楼，有11层二教学校二号教学楼图书馆供学生自习或借书体育场一个大的田径场，包括足球场，女生宿舍 生

8、女生住宿的地方南门 ？学校通向外面的一个小门蕙莘园食堂学校有三个食堂，其中一个就是蕙莘园食堂，靠近男生宿舍。校门图书馆110校门主教30校门体育场70校门南门90校门女生宿舍110主教图书馆50主教二教10二教蕙莘园食堂50二教体育场30图书馆体育场70图书馆蕙莘园食堂60体育场蕙莘园食堂40体育场南门40南门女生宿舍20蕙莘园食堂女生宿舍130graph.txt文件中的格式是，第一行包括两个整数，第一个整数是景点的个数n,也就是图中的结点个数，第二个整数是边的数量m。接着n行数据分别是学校的每个景点(结点)每个景点后的是对景点的介绍。再接着的m行是路径信息，每条路径信息有三部分数据组成，分别

9、是起始结点，终止结点，和它们之间的路径长度。322 提供可选景点提供可选景点信息这一模块，是向用户展示从graph.txt文件中读取到的学校的各大景 点，告诉用户提供的可查看的景点有哪些。景点信息用一个for循环输出。此外为了方便对景点的各项操作，我们在输出所有可选景点的同时还为它们进行了数字编号，在后面的查询或找路过程中还需要输入烦琐的景点名称，只需要输入想要查询的景点的对应编号即可进行 操作。简单方便，实用，用户体验性好。输出提供的可选景点的代码如下：/输出可选景点，并进行编号void outPlace() prin tf(本校景点有：n);for (int i = 0; i 请选择您要查

10、询的景点(0 - %d:n,mg.vex nu m);scan f(%d, &n);if (n = 0 & n 请输入要查询的两景点a b ( a b表示景点编号):n);scan f(%d %d, &a, & b);if (a = 0 & a = 0 & b mg.vex num) prin tf(nn ”)；prin tf(|起始地 |目的地 |最短路径|n);printf(”n);prin tf(| %s | %s |%4d|n, mg.vexsa. name,mg.vexsb. name, mg.arcsab);printf(”nn ”)；elseprintf(输入有误！n);3.2.

11、5 Floyd算法计算任意两点间的最短路径(重点)在这个问题中需要用到floyd算法，这是此问题中的核心重点，也是难点，下面也将重点介绍。Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。 该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特弗 洛伊德命名。路径矩阵：通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=a(i,j) n Xn开始，递归地进行 n次更新，即由矩阵 D(0)=A ,按一个公式，构造出矩阵D(1);又用同样地公式由D(1)构造出D(2);；最后又用同样的公式由D(n-1)构造出矩阵D(n

12、)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。采用松弛技术(松弛操作)，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为 0(nA3)。状态转移方程：其状态转移方程如下：mapi,j:=mi nmapi,k+m apk,j,mapi,jmapi,j表示i到j的最短距离，K是穷举i,j的断点，mapn,n初值应该为0,或者按照题 目意思来做。当然，如果这条路没有通的话，还必须特殊处理，比如没有mapi,k这条路。算法过程：1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果

13、两点之间没有边相连，则权为无穷大。2，对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比已知的路径更短。如果是更新它。把图用邻接矩阵 G表示出来，如果从 Vi到Vj有路可达，则Gi,j=d ，d表示该路的长 度；否则Gi,j=无穷大。定义一个矩阵D用来记录所插入点的信息，Di,j表示从Vi到Vj需要经过的点，初始化Di,j=j。把各个顶点插入图中，比较插点后的距离与原来的距离，Gi,j = min( Gi,j, Gi,k+Gk,j) ，如果 Gi,j的值变小，则 Di,j=k。在 G 中包含有两点 之间最短道路的信息，而在D中则包含了最短通路径的信息。比如，要寻找从 V5到V1的

14、路径。根据 D，假如D(5,1)=3 则说明从V5到V1经过V3，路径为V5,V3,V1，如果D(5,3)=3，说明V5与V3直接相连，如果 D(3,1)=1，说明V3与V1直接相连。在符合本问题时的 Floyd算法的具体实现代码如下:/Floyd 算法计算任两点间的最短路径void floyd() int i, j, k;for (i = 0; i mg.vex num; i+) for (j = 0; j mg.vex nu m; j+) for (k = 0; k = (mg.arcsik + mg.arcsij) mg.arcsjk = mg.arcsik + mg.arcsij;3.

15、3主程序流程在主程序中，首先通过ini tGraph()读取图文件并创建图信息，然后展示用户可选择的菜单，用户根据菜单提示进行操作。用户输入指令后，系统根据用户的输入指令进行1、景点信息查询 2、最短路径的查询。如果是用户要求查询景点信息，输入了相应的指令， 则系统调用景点信息查询模块out In fo()。如果用户要求查询景点信息，并输入了相应的指令，则系统调用最短路径查询模块min dista nce()具体操作流程如下图：退出指令out In fo()*退出min dista nce()结束图 3 .3 14. 调试分析4.1问题回顾和分析在程序设计中的遇到的问题有 ；1、文件读取和操作

16、。2、输入文件的字符编码的选择。3、求最短路径算法的选择。问题1、文件的读取操作。起初用了好多种文件操作的方法，不知道用哪种方式读取文件，最后看见同学用了一种文件读取方式可以正确读取文件，于是就把那个方法给引用过来了。问题2、输入文件的字符编码的选择。由于不同的编译器对字符编码的要求不一，所以 要选择正确的字符编码，程序可以正确地读取文件并显示。问题3、求最短路径算法的选择。最初对于最短路径算法，我首先想到的是Dijkstra算 法，但后来发现Dijkstra算法每次只能计算两点之间的最短路径，在这个问题中用起来比较 烦琐，最后发现Floyd算法可以很好地解决这个问题，于是毫不犹豫地选择了Fl

17、oyd算法。42经验和体会通过这次数据结构课程设计我觉得要设计一个程序不简单，尤其是要设计出一个很好的程序，那更是难上加难，在今后的学习中还要不断加强自己设计程序的能力，进行更多的程序设计实践，提高设计程序和写程序的水平。5.测试结果ES|堂 舍食H- nun 校T一图体女南鳶 佯 常 巒 锦 悌 悌 侔 停 01234567. I .am 您有以.选择:1.查询景点2-查找最短跻径I输入对应编号执行相应操作，输入-1结束操作您词罩了 1 .查询量点信，息请选择您要查询的量点0-8）:蕙莘园食堂匕学校有三个食堂，其中一个就是蔦莘园食堂.靠近男主宿書。!看硬玉拯；iIH:1 .查询最点茲査找最想

18、蹄径!I输入对应编号执行相应操作，输入-1結束操作；恰;小请输入婪查询的两号点a Jb （a腺示景邑编号）=起始地 ! 目的地 !最燉確校门 ! 蕙莘园食堂 !90您有次下选择,1查询最点2 -查找量短路径：_编書塑亍相甲操作，邁入-1琴束舞存_：書按任意键继续 二叉树的三种遍历基于栈的非递归遍历1.设计目的数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储 结构。数据结构是信息的一种组织方式，其目的是为了提高

19、算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们 之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算 机专业的核心课程， 它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的

20、重 要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力， 促进学生的综合应用能力和专业素质的提高。 通过此 次课程设计主要达到以下目的：一、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；二、 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；三、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；四训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风2需求分析2.1课程设计的内容和要求二叉树的遍历

21、：对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基 本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种 遍历，输出三种遍历的结果。2.2选题的意义及背景二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉链存储结构的每 个结点包含三个域，分别是数据域，左孩子指针域，右孩子指针域。因此每个结点为leftchilddatarightchild由二叉树的定义知可把其遍历设计成递归算法。共有前序遍历、中序遍历、后序遍历。可先用这三种遍历输出二叉树的结点。采用递归算法设计，以前序遍历为例，它要求首先要访问根节点，然后前序遍历左子树和前序遍历

22、右子树。特点在于所有未被访问的节点中，最后访问结点的左子树的根结点将 最先被访问，这与堆栈的特点相吻合。因此可借助堆栈实现二叉树的递归遍历。将输出结果与递归结果比较来检验正确性，因此程序结果可做成菜单方便这两种算法的结果查看。3.概要设计3.1设计思想所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。这里提到的“访问”是指对结点施行某种操作，操作可以是输出结点信息，修改结点的数据值等，但要求这种访问不破坏它原来的数据结构。我们访问是输出结点信息data，且以二叉链表作为二叉树的存储结构。由于二叉树是一种非线性结构，每个结点可能有一个以上的直接后继，因此，必须规

23、定遍历的规则，并按此规则遍历二叉树，最后得到二叉树所有结点的一个线性序列。令L,R,D分别代表二叉树的左子树、右子树、根结点，则遍历二叉树有 6中规则：DLR、DRL、LDR、LRD、RDL、RKD。若规定二叉树中必须先左后右(左右顺序不能颠倒)，则只有DLR、LDR、LRD三种遍历规则。称 DLR先序遍历，LDR中序遍历，LRD后序遍历。3.1.1先序遍历二叉树若二叉树非空，依次进行如下操作：(1) 访问根结点(2) 先序遍历左子树(3) 先序遍历右子树3.1.2中序遍历二叉树若二叉树非空，依次进行如下操作:(1 )中序遍历左子树(2)访问根结点(3 )中序遍历右子树3.1.3后序遍历二叉树

24、若二叉树非空，依次进行如下操作:(1 )后序遍历左子树(2 )后序遍历右子树(3 )访问根结点3.2程序数据类型typedef struct BiTNodechar data;struct BiTNode *LChild; struct BiTNode *RChild; BiTNode,*BiTree;typedef struct sno deBiTNode pp; struct snode *n ext; lin kstack no de,*li nkstack;3.3程序模块分析3.3.1置空栈lin kstack Ini tBiTree()Lin kstack top;top=(l in

25、 kstack)malloc(sizeof(struct sno de); if(!top) printf( “ EROORi” );top=NULL;return top;332入栈void Push(li nkstack top,BiTNode x)lin kstack temp;temp=(li nkstack)malloc(sizeof(struct sno de); temp_pp=x;temp-n ext=top-n ext;top-n ext=temp;3.3.3出栈BiTNode Pop(li nkstack top) BiTNode ss;lin kstack node *t

26、emp; temp=top-n ext;top-n ext=temp-n ext; ss=temp-pp;return ss;3.3.4取栈顶操作int getTop(BiTree T,char &e) if(!T)return 0; e=T-data;return 1;3.3.5判空栈int lin kstackempty(l in kstack top) if (! top ) return 1; else return 0;3.4函数关系:4.详细设计4.1二叉树算法程序截图和结果例如：输入二叉树为：A(B(,D(E,F),C(G(,H(I,J),K)它的前序遍历为：ABDEFCGHIJ

27、K它的中序遍历为：BEDFAGIHJCK它的后序遍历为：EFDBIJHGKCA当输入数据为A(B(,D(E,F),C(G(,H(I,J),K)显示结果如下:AB,CG,H ,)冃HBDEFCCHIJK BEDFAGIHJCK EPDBIJMCKCA :键续图 4.1.15. 程序测试结果及问题分析通过与递归的遍历结果相比较之后，用堆栈实现的非递归遍历算法得出了正确的遍历结果，可以对二叉树进行遍历操作。但是程序中树的结点已经建立好不能随意改动这确实是一个缺点因此可以进行改进，可以用递归的方法建立一棵二叉树，先建 立左子树，在建立右子树这样用户输入的字符可以直接用来建树程序的灵活性会更强。6. 总

28、结通过一周的数据结构实训，进一步加深了对数据结构整体的理解，明白了链表的各种操作的实质，并且对老师课上讲的各种算法进行了实际的运用，更加掌握了各种算法的使用方法，例如链表的创建，查找，插入，二叉树的遍历等算法。而且，通过这一次的实训，不仅加深了对数据结构知识的了解，更复习了以前学习过的c语言，重新复习了栈等经典算法，而且对于以前不懂得地方，例如主函数与子函数之间的实参，形参之间的传递，并且在二叉树的遍历部分复习了递归算法的使用。这一周的实训，我深刻的领悟到，遇到困难， 一定不要畏惧，自己多动脑思考思考，所联系自己以前学过的知识，便会有很大的进展，还 有就是，往往一些错误都不是编写的逻辑错误，而

29、是一些小错误点， 例如忘记另外一部分的大括号，忘记分号等等，这提醒自己以后要细心，不要错在一些小问题上。在这次课程设计中在，虽然不会成功的编写一个完整的程序，但是在看程序的过程中，不断的上网查资料以及翻阅相关书籍，通过不断的模索，测试，发现问题，解决问题和在老师的帮助下一步一步慢慢的正确运行程序决问题，终于完成了这次课程设计，虽然这次课程设计结束了但是总觉得自已懂得的知识很是不足，学无止境，以后还会更加的努力深入的学习。参考文献1严蔚敏，吴伟民数据结构（C语言版），北京：清华大学出版社，2009.20112顾泽元，刘文强，数据结构（C语言版），北京：北京航空航天大学出版社，3徐德民最新C语言程

30、序设计M电子工业出版社.1992年4唐策善，黄刘生数据结构M中国科学技术出版社.1992年仲萃豪，冯玉琳.程序设计方法学M北京科学技术出版社.1985年 宁正元，王秀丽，算法与数据结构清华大学出版社，20067谭浩强，数据结构教程上级实验指导清华大学出版社，2008.8朱站立，数据结构-使用C语言西安：西安交通大学出版社，2004.附录1最短路径源代码#include #include #include #includealgorithmusing namespace std;const int MAXPLACE = 100;typedef structchar name100;char in

31、fo10000;VertexType; / 顶点结构typedef structVertexType vexs10;int arcs100100;/邻接矩阵int vexnum, arcnum;/顶点个数，边的个数MGraph; / 图结构MGraph mg;void floyd() int i, j, k;for (i = 0; ivmg.vexnum; i+)for (j = 0; jvmg.vexnum; j+)for (k = 0; kvmg.vexnum; k+)mg.arcsij = min(mg.arcsij, mg.arcsi k + mg.arcskj);void initG

32、raph() freopen(graph.txt, r, stdin);scanf(%d %d, &mg.vexnum, &mg.arcnum);/输入景点信息for (int i = 0; i mg.vexnum; i+) scanf(%s %s, &, &);/初始化矩阵for (int i = 0; i 100; i+) for (int j = 0; j 100; j+) mg.arcsij = 999999;/输入距离for (int i = 0; i mg.arcnum; i+) char from100;char to100;i

33、nt f, t, dis;scanf(%s %s %d, &from, &to, &dis);/把景点换成编号for (int j = 0; j mg.vexnum; j+) if (strcmp(, from) = 0) f = j;if (strcmp(, to) = 0) t = j;/创建邻接矩阵mg.arcsft = dis;mg.arcstf = dis;floyd();/算出各两点之间的最短路径freopen(CON, r, stdin);void outPlace() printf(本校景点有：n);for (int i =

34、0; i 请选择您要查询的景点(0 - %d )scanf(%d, & n);if (n = 0 & n 请输入要查询的两景点a b (a b表示景点编号):n);scanf(%d %d, &a, & b);if (a = 0 & a = 0 & b mg.vexnum) printf(nn);printf(|起始地 |目的地 |最短路径|n);printf(n);,printf(|%s|%s|%4d|, mg.arcsab);printf(nn);elseprintf(输入有误！ n);int main() int a; initGrap

35、h(); outPlace(); while (1) printf(n);printf(|您有以下选择：|n);printf(n);printf(|n);printf(| 1.查询景点t 2.查找最短路径|n);printf(|n);printf(n);printf(|printf(”输入对应编号执行相应操作，输入-1结束操作|n);n);scanf(%d, &a); if (a = -1) break;if (a = 1) outlnfo();if (a = 2) mindistance();return 0;附录2二叉树遍历源代码#include #include #include usi

36、ng namespace std;#define MaxSize 100#define MaxWidth 40typedef char ElemType;typedef struct nodeElemType data;struct node *left, *right;int isOut = 0;/访问次数(后序遍历会用到) BTree;void creatree(BTree *BT, char *str)BTree *stackMaxSize, *p;int top = -1, k, j = 0;/*top为栈指针,k指定是左还是右孩子，j为str指针*/char ch;*BT = NUL

37、L;ch = strj;while (ch != 0)switch (ch)case (:top+; stacktop = p; k = 1; /*为左结点 */break;case ):top-;break;case ,:k = 2; /*为右结点 */break;default: p = (BTree *)malloc(sizeof(BTree);p-data = ch; p-left = p-right = NULL; p-isOut = 0;if (*BT = NULL) /* 根结点 */*BT = p;elseswitch (k)case 1:stacktop-left = p;b

38、reak;case 2:stacktop-right = p;j+；ch = strj;void disptree(BTree *BT) BTree *stackMaxSize, *p;int levelMaxSize2, top, n, i, width = 4;if (BT != NULL)printf(n凹入表示法:n);top = 1;stacktop = BT; /*根结点入栈 */leveltop0 = width;while (top0)p = stacktop; /*退栈并凹入显示该结点值 */n = leveltop0;for (i = 1; i data);for (i = n + 1; i right != NULL)/*将右子树根结点入栈*/top+;stacktop = p-right;leveltop0 = n + width; /*显示场宽