《图的建立与遍历》数据结构课程设计

PAGE7届课程设计《图的建立与遍历》课程设计论文学生姓名学号所属学院信息工程学院专业计算机科学与技术班级计算机指导教师教师职称讲师塔里木大学教务处制目录前言 1正文 11.1课程设计的教学目的和任务 11.2课程设计的主要内容 11.3课程设计报告的要求 22.1.问题描述及基本要求 22.2.算法思想 22.3模块划分 32.3.1深度优先搜索 32.3.2广度优先搜索法 42.3.3分析与探讨 42.3.4图的存储 52.4测试数据 82.5测试情况 8总结 10参考文献： 10附录 11课程总结 14前言图遍历又称图的遍历，属于数据结构中的内容。指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面:①在图结构中，没有一个"自然"的首结点，图中任意一个顶点都可作为第一个被访问的结点。②在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。③在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。④在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。正文1.1课程设计的教学目的和任务(1)使学生进一步理解和掌握所学的各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。(2)使学生初步掌握软件开发过程的问题分析、设计、编码、测试等基本方法和基本技能。(3)使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。(4)使学生能用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。1.2课程设计的主要内容(1)问题分析和任务定义。根据题目的要求，充分地分析和理解问题，明确问题要求做什么？限制条件是什么？(2)逻辑设计。对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图。(3)物理设计。定义相应的存储结构并写出各函数的伪代码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。(4)程序编码。把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚。(5)程序调试与测试。采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。(6)结果分析。程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。(7)撰写课程设计报告。1.3课程设计报告的要求课程设计报告要求规范书写。应当包括如下内容：⑴问题描述：描述要求编程解决的问题。⑵基本要求：给出程序要达到的具体的要求。⑶测试数据：设计测试数据，或具体给出测试数据。要求测试数据能全面地测试所设计程序的功能。⑷算法思想：描述解决相应问题算法的设计思想。⑸模块划分：描述所设计程序的各个模块（即函数）功能。⑹数据结构：给出所使用的基本抽象数据类型，所定义的具体问题的数据类型，以及新定义的抽象数据类型。⑺源程序：给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。⑻测试情况：给出程序的测试情况，并分析运行结果。⑼算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；经验和体会等。⑽参考文献：列出参考的相关资料和书籍。2.1.问题描述及基本要求利用深度优先搜索和广度优先搜索完成出具的排序。/要求建立一个菜单，菜单包含4个菜单项供选择：1、建立图的邻接矩阵；2、建立图的邻接表；3、对图进行深度优先遍历；4、对图进行广度优先遍历。要求从键盘输入无向有权图的顶点数、边数、每条边的起始顶点序号、终点序号、权值，将每条边的信息存入到邻接矩阵和邻接表中。从键盘输入深度优先遍历和广度优先遍历图时初始出发的顶点的序号，要求在遍历过程中输出访问过的结点序号。2.2.算法思想遍历图的过程实质上是通过边或弧找邻接点的过程，因此广度优先搜索遍历图和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的结点，如果它还有以此为起点而未搜过的边，就沿着边继续搜索下去。当结点v的所有边都已被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个过程反复进行直到所有结点都被发现为止。深度优先搜索基本算法如下{递归算法}：PROCEDUREdfs_try(i);FORi:=1tomaxrDOBEGINIF子结点mr符合条件THENBEGIN产生的子结点mr入栈；IF子结点mr是目标结点THEN输出ELSEdfs_try(i+1);栈顶元素出栈;END;END;宽度优先搜索算法（又称广度优先搜索算法）是最简单的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijksta单源最短路径算法和Prim最小生成树算法都采用了与宽度优先搜索类似的思想。宽度优先搜索的核心思想是：从初始结点开始，应用算符生成第一层结点，检查目标结点是否在这些后继结点中，若没有，再用产生式规则将所有第一层的结点逐一扩展，得到第二层结点，并逐一检查第二层结点中是否包含目标结点。若没有，再用算符逐一扩展第二层所有结点……，如此依次扩展，直到发现目标结点为止。宽度优先搜索基本算法如下：list[1]:=source;{加入初始结点，list为待扩展结点的表}head:=0;{队首指针}foot:=1;{队尾指针}REPEAThead:=head+1;FORx:=1to规则数DOBEGIN根据规则产生新结点nw;IFnot_appear(nw,list)THEN{若新结点队列中不存在，则加到队尾}BEGINfoot:=foot+1;list[foot]:=nw;list[foot].father:=head;IFlist[foot]=目标结点THEN输出；END；END；UNTILhead>foot;{队列为空表明再无结点可扩展}2.3模块划分2.3.1深度优先搜索深度优先搜索法是树的先根遍历的推广，它的基本思想是:从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下:Booleanvisited[MAX_VERTEX_NUM];//访问标志数组Status(*VisitFunc)(intv);//VisitFunc是访问函数，对图的每个顶点调用该函数voidDFSTraverse(GraphG,Status(*Visit)(intv)){VisitFunc=Visit;for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//访问标志数组初始化for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);//对尚未访问的顶点调用DFS}voidDFS(GraphG,intv){//从第v个顶点出发递归地深度优先遍历图Gvisited[v]=TRUE;VisitFunc(v);//访问第v个顶点for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))//FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空(0)。//若w是v的邻接顶点，NextAdjVex返回v的(相对于w的)下一个邻接顶点。//若w是v的最后一个邻接点，则返回空(0)。if(!visited[w])DFS(G,w);//对v的尚未访问的邻接顶点w调用DFS}2.3.2广度优先搜索法图的广度优先搜索是树的按层次遍历的推广，它的基本思想是:首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2,…,vit，并均标记已访问过，然后再按照vi1,vi2,…,vit的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。其非递归算法如下:Booleanvisited[MAX_VERTEX_NUM];//访问标志数组Status(*VisitFunc)(intv);//VisitFunc是访问函数，对图的每个顶点调用该函数voidBFSTraverse(GraphG,Status(*Visit)(intv)){VisitFunc=Visit;for(v=0;v<G.vexnum,++v)visited[v]=FALSE;initQueue(Q);//置空辅助队列Qfor(v=0;v<G.vexnum;++v)if(!visited[v]){visited[v]=TRUE;VisitFunc(v);EnQueue(Q,v);//v入队列while(!QueueEmpty(Q)){DeQueue(Q,u);//队头元素出队并置为ufor(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))if(!Visited[w]){//w为u的尚未访问的邻接顶点Visited[w]=TRUE;VisitFunc(w);EnQueue(Q,w);}}}2.3.3分析与探讨目录结构是一种典型的树形结构，为了方便对目录的查找，遍历等操作，可以选择孩子兄弟双亲链表来存储数的结构。程序中要求对目录的大小进行重新计算，根据用户的输入来建立相应的孩子兄弟双亲链表，最后输入树形结构。可以引入一个Tree类，将树的构造，销毁，目录大小的重新计算（reSize），建立树形链表结构（parse），树形结构输出（outPut）等一系列操作都封装起来，同时对于每一个树的借点，它的私有变量除了名称（Name），大小（Size）和层数（Depth）之外，根据孩子兄弟双亲链表表示的需要，还要设置三个指针，即父指针（Tree*parent）,下一个兄弟指针（Tree*NextSibling）和第一个孩子指针（Tree*Firstchild）。下面是几个主要函数的实现。1.建立树形链表结构的函数parse()根据输入来确定树形关系是，首先读取根借点目录/文件名和大小值，并根据这些信息建立一个新的节点；然后读入后面的各行信息，对于同一括号中的内容，即具有相同父节点的那些节点建立兄弟关联。这个函数实际上是采用层数遍历建立树形链表结构。定义一个Tree*类型的数组treeArray[]，用来存放目录的节点信息，并定义两个整型变量head和rear，head值用来标记当前节点的父节点位置，每处理完一对括号，head需要增加1,即下一对待处理括号的父节点在treeArray[]中要往后移一个位置。如果当前处理的节点是目录类型，则将它放在treeArray[]数组中，rear是treeArray[]的下标变量，加入一个树的节点，并和head所指的父节点建立关联，但是不用放入treeArray[]中。2.目录大小重新计算函数reSize()输入数据中对目录大小的初始化值一般为1，而目录的真正大小应该是自身的大小和它包含的所有文件及子目录的大小之和。因此，在计算目录大小的时候，需要遍历它下面所有的文件和子目录，可以采用递归嵌套的后序遍历方式。另外要注意，采用孩子兄弟双亲链表表示时，父目录下的所有子目录和子文件都在该父目录的左子树上（右字数第一个节点是该目录的兄弟节点），所以遍历的时候只需要遍历目录的左字数即可。3.输出树形结构的函数outPut()输出是一个线序遍历的过程。为完成对树形的输出，兄弟目录之前需要相同的缩进，用’|’上下相连，而斧子目录或父目录和子文件之间需要设定正确的缩进，子目录或子文件要比父目录向右缩进8个空格。设置一个标志数组flag[11]（每个目录下最大层次数为10），当前Tree*temp指针所指的节点如果有兄弟节点，则置flag数组值为1，否则置为0；并由此节点反复查询它的祖先节点的情况，知道根节点位置。输出时，遇到flag[]=1时，屏幕输出“|”，表明是兄弟节点；遇到flag[]=0时则输出“”，这样就可以保证兄弟节点之间有相同的缩进，而子节点总比父节点享有缩进8个空格。2.3.4图的存储图的深度优先遍历假设初始状态是图中所有顶点未曾被访问，深度优先遍历可以从图的初始点出发，访问初始点，然后依次从v未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时仍有顶点未被访问到，则从另一个未被访问的顶点出发，重复上述过程，直至所有点都被访问到为止。这是一个递归的过程。所以在实现深度优先遍历的过程中必须递归调用深度优先搜索函数。而且在深度优先搜索函数中必须设一标志数组以标记结点是否被访问。具体过程应为：先访问初始点Vi，并标志其已被访问。此时定义一指向边结点的指针p，并建立一个while（）循环，以指针所指对象不为空为控制条件，当Vi的邻接点未被访问时，递归调用深度优先遍历函数访问之。然后将p指针指向下一个边结点。这样就可以完成图的深度优先遍历了。图的广度优先遍历：广度优先搜索遍历类似于树的按层次遍历的过程。假设从图中某顶点v出发，在访问了v之后访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点的邻接点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到。若此时图中尙有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程是以v为起始点，由近及远，依次访问和v有路径相通且路径长度为1，2，……的顶点。所以要实现算法必须先建立一个元素类型为整形的空队列，并定义队首与队尾指针，同时也要定义一个标志数组以标记结点是否被访问。同样，也是从初始点出发开始访问，访问初始点，标志其已被访问，并将其入队。当队列非空时进行循环处理。当结点被访问时对其进行标志，并入队列。通过while（）循环，并以是否被访问为控制条件，访问所有结点，完成图的广度优先遍历。定义邻接表的边结点类型以及邻接表类型：structedgenode{ intadjvex;//该弧所指向的顶点的位置edgenode*next;//指向下条条弧的指针};//定义邻接表的边结点类型typedefedgenode**adjlist;//定义邻接表类型初始化图的邻接表：需建立一个邻接表初始化函数对图的邻接表进行初始化。即建立一个所有边结点都为空的邻接表。voidInitGAdjoin(adjlist&GL,intn)//初始化图的邻接表{ GL=newedgenode*[n]; for(inti=1;i<=n;i++)GL[i]=NULL;}建立并输出图的邻接表首先必须输入图的相关信息，包括图的顶点数、边数、各条边的起点和终点，为保证输入数据的正确性，我在程序中设计了一个判断所输结点是否越界的函数check（）当所输的顶点序号超出序号的范围时则报错，并要求重新输入。还有就图是否有向，此时可定义一变量，图的是否有向，可用变量的值来表示。此处定了变量m，当图为无向时，m等于0。图为有向时m等于1。用if（）语句判断m的值，就可将图分有向和无向两种情况来进行分析了。对于无向图，各条边的起点和终点互为邻接点。所以必须把起点添加到终点的邻接点域中，并把终点添加到起点的邻接点域中。而对于有向图，只能是将弧头添加到弧尾的邻接点域中。最后是输出邻接表，即对于每个顶点，输出其邻接点。由于不了解C++中绘图函数的用法，所以利用一些符号来达到图形化的效果。邻接表输出的相关代码如下：cout<<"图的邻接表为:"<<endl;for(i=1;i<=n;i++){edgenode*p=GL[i];cout<<i-1<<"|"<<"V"<<i;for(p=GL[i];p!=NULL;p=p->next)cout<<"|-|->|"<<p->adjvex;cout<<"|^|";cout<<endl;}//输出邻接表图的遍历深度优先遍历图的邻接表：假设初始状态是图中所有顶点未曾被访问，深度优先遍历可以从图的初始点出发，访问初始点，然后依次从v未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时仍有顶点未被访问到，则从另一个未被访问的顶点出发，重复上述过程，直至所有点都被访问到为止。这是一个递归的过程。所以在实现深度优先遍历的过程中必须递归调用深度优先搜索函数。而且在深度优先搜索函数中必须设一标志数组以标记结点是否被访问。具体过程应为：在深度优先遍历函数的参数中定义一个标志数组bool*&visited，当某结点已被访问时，标志数组的值为关键字ture，未被访问时其值为关键字false。先访问初始点Vi，并标志其已被访问。此时定义一指向边结点的指针p，并建立一个while（）循环，以指针所指对象不为空为控制条件，当Vi的邻接点未被访问时，递归调用深度优先遍历函数访问之。然后将p指针指向下一个边结点。这样就可以完成图的深度优先遍历了。深度优先遍历的相关代码如下：voiddfsAdjoin(adjlistGL,bool*&visited,inti,intn)//从初始点出发深度优先搜索邻接表GL表示的图{ cout<<i<<''; visited[i]=true; edgenode*p=GL[i]; while(p!=NULL){ intj=p->adjvex;//j为Vi的一个邻接点的序号 if(!visited[j]) dfsAdjoin(GL,visited,j,n); p=p->next;//使p指向Vi单链表的下一个边结点 }}广度优先遍历图的邻接表：图的广度优先遍历是从初始点出发，访问初始点，再访问初始点的邻接点。当初始点的所有邻接点都被访问过时，再依次访问各邻接点的邻接点。如此循环下去。算法的实现必须依靠辅助队列，结点被访问后，对其进行标记，并将结点入队列。所以要实现算法必须先建立一个元素类型为整形的空队列，并定义队首与队尾指针，同时也要定义一个标志数组bool*&visited以标记结点是否被访问。同样，也是从初始点Vi出发开始访问，访问初始点，标志其已被访问，并将已访问过的初始点序号i入队。当队列非空时进行循环处理，删除队首元素，第一次执行时k的值为i，即front=(front+1)%MaxLength。然后取Vk邻接表的表头指针intk=q[front];edgenode*p=GL[k]。当边结点指针p不为空时，通过while（）循环，并以p是否为空为控制条件，依次搜索Vk的每一个结点。若Vj没有被访问过则进行处理。访问完后，将p指向p->next。其中的while循环部分的代码如下：while(p!=NULL){ //依次搜索Vk的每一个结点 intj=p->adjvex;//Vj为Vk的一个邻接点 if(!visited[j]){//若Vj没有被访问过则进行处理 cout<<j<<''; visited[j]=true; rear=(rear+1)%MaxLength; q[rear]=j; } p=p->next;}这样就可以访问所有结点，完成图的广度优先遍历2.4测试数据输入顶点数和弧数:89

输入8个顶点.

输入顶点0:a

输入顶点1:b

输入顶点2:c

输入顶点3:d

输入顶点4:e

输入顶点5:f

输入顶点6:g

输入顶点7:h

输入9条弧.

输入弧0:ab1

输入弧1:bd1

输入弧2:be1

输入弧3:dh1

输入弧4:eh1

输入弧5:ac1

输入弧6:cf1

输入弧7:cg1

输入弧8:fg12.5测试情况输入数据后出现的效果：图1编译初始界面图2编码界面小结通过该题目的设计过程,对数据结构以及二叉树的逻辑结构,存储结构的理解,对树的数据结构上基本运算的实现有所掌握,对课本中所学的各种数据结构进一步理解和掌握,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。完成所有的工作是非常困难和耗时的。在以后的学习中我会更加注意自己各个方面的能力的协调发展。在课程设计时我遇到了很多的问题，在老师的帮助，和对各种资料的查阅中，将问题解决，培养了我自主动手，独立研究的能力，为今后在学习工作中能更好的发展打下了坚实的基础。参考文献：[1]谭浩强编著.C++课程设计.北京：清华大学社，2004[2]S.B.Lippman，J.Lajoie著.潘爱民译.C++Primer（3rdEdition）中文版.北京：中国电力出版社，2002[3]H.M.Deitel，PaulJamesDeitel著.薛万鹏译.C++程序设计教程.北京：机械工业出版社，2000[4]StephenR.Savis著.C++ForDummies4thedition，IDGBooksWorldwide，Inc.，2002[5]HarveyM.Deitel.JackW.Davidson著.邱仲潘译.C++大学教程（第二版）.北京：电子工业出版社，2002[6]JamesP.Cohoon.JackW.Davidson著.刘瑞挺等译.C++程序设计（第三版）.北京：电子工业出版社附录#include<iostream>//#include<malloc.h>#defineINFINITY32767#defineMAX_VEX20//最大顶点个数#defineQUEUE_SIZE(MAX_VEX+1)//队列长度usingnamespacestd;bool*visited;//访问标志数组//图的邻接矩阵存储结构typedefstruct{char*vexs;//顶点向量intarcs[MAX_VEX][MAX_VEX];//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数}Graph;//队列类classQueue{public:voidInitQueue(){base=(int*)malloc(QUEUE_SIZE*sizeof(int));front=rear=0;}voidEnQueue(inte){base[rear]=e;rear=(rear+1)%QUEUE_SIZE;}voidDeQueue(int&e){e=base[front];front=(front+1)%QUEUE_SIZE;}public:int*base;intfront;intrear;};//图G中查找元素c的位置intLocate(GraphG,charc){for(inti=0;i<G.vexnum;i++)if(G.vexs[i]==c)returni;return-1;}//创建无向网voidCreateUDN(Graph&G){inti,j,w,s1,s2;chara,b,temp;printf("输入顶点数和弧数:");scanf("%d%d",&G.vexnum,&G.arcnum);temp=getchar();//接收回车G.vexs=(char*)malloc(G.vexnum*sizeof(char));//分配顶点数目printf("输入%d个顶点.\n",G.vexnum);for(i=0;i<G.vexnum;i++){//初始化顶点printf("输入顶点%d:",i);scanf("%c",&G.vexs[i]);temp=getchar();//接收回车}for(i=0;i<G.vexnum;i++)//初始化邻接矩阵for(j=0;j<G.vexnum;j++)G.arcs[i][j]=INFINITY;printf("输入%d条弧.\n",G.arcnum);for(i=0;i<G.arcnum;i++){//初始化弧printf("输入弧%d:",i);scanf("%c%c%d",&a,&b,&w);//输入一条边依附的顶点和权值temp=getchar();//接收回车s1=Locate(G,a);s2=Locate(G,b);G.arcs[s1][s2]=G.arcs[s2][s1]=w;}}//图G中顶点k的第一个邻接顶点intFirstVex(GraphG,intk){if(k>=0&&k<G.vexnum){//k合理for(inti=0;i<G.vexnum;i++)if(G.arcs[k][i]!=INFINITY)returni;}return-1;}//图G中顶点i的第j个邻接顶点的下一个邻接顶点intNextVex(GraphG,inti,intj){if(i>=0&&i<G.vexnum&&j>=0&&j<G.vexnum){//i,j合理for(intk=j+1;k<G.vexnum;k++)if(G.arcs[i][k]!=INFINITY)returnk;}return-1;}//深度优先遍历voidDFS(GraphG,intk){inti;if(k==-1){//第一次执行DFS时,k为-1for(i=0;i<G.vexnum;i++)if(!visited[i])DFS(G,i);//对尚未访问的顶点调用DFS}else{visited[k]=true;printf("%c",G.