搜索
I算法与数据结构课程设计题目：图遍历的演示专业班级：09级网络姓名：李勋辉学号：09780011指导教师：成绩：_______________II目录摘要..........................................1前言..........................................1正文...........................................1问题描述...........................................................1逻辑设计...........................................................1详细设计...........................................................6程序编码...........................................................7程序的调试与测试..................................................10结果分析..........................................................12使用说明..........................................................13设计总结.......................................13参考文献.......................................14六、附件.......................................151摘要（1）使用键盘的操作实行各种信息的输入（包括员图的结点、结点之间的连线）；并将相应结果输出等功能；（2）建立图，规定图的结点的个数少于十个，实现图的遍历（3）算法对于一些精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；对算法实现过程中的异常情况能给出出错信息；（4）图的遍历的方法有广度优先遍历和深度优先遍历，按照设计任务书的要求实现图的两种遍历，并且输出结果（5）较高要求：实现图形化操作界面。前言该设计要求学生本学期对数据结构的学习为背景，设计出一个简单的能够实现图的遍历的系统。通过该题目的设计过程，可以加深理解图、图的遍历、图的广度优先遍历，图的深度优先遍历、图的创建等一系列算法的创建，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。正文问题描述该课题要求熟悉图的结构和其基本操作，掌握数组的建立和使用方法，学会利用递归和非递归的方法对其进行遍历。和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。遍历常用两种方法：深度优先搜索遍历；广度优先搜索遍历逻辑设计1图的创建该课题主要是以邻接矩阵的方式存储图，并以图形的方式输出图，所以在图的创建的过程中主要是输入图中各结点的关系，比方说1号结点和2号结点之间有联系，那么就得输入（1，2），但是总得设置一个结束的条件，在这里我就以（0，0）2结束，这样比较好控制。而且初始化时得把所有邻接矩阵都初始化为0，那么当两个结点有关系时就可以设置为1.2图的输出图的输出主要是以printfgraph（）函数实现的。因为输出图的特殊性，结点的位置如果随机的定义，工程量太大，而且涉及到数学方面的计算，所以我就把结点初定为6个。并且已经定好结点的位置，但是结点与结点之间的联系却没有定好，是按用户输入的情况进行连接的。3图的深度优先遍历当用户需要深度优先遍历时，由于公共变量visited里的值可能会受到其他的变化，所以一开始就把所有结点都定义为未访问，然后当其访问到哪个结点时再把相应的结点的visited设置为1，即已经访问。再用visitvex函数显示该结点已访问。再查找该结点的下一个结点，实行递归。直到所有的结点都已经访问完。4图的广度优先遍历当用户需要广度优先遍历时，首先得初始化一个队列，并初始化其为一个空队列。而且由于公共变量visited里的值可能会受到其他的变化，所以一开始就把所有结点都定义为未访问，然后当其访问到哪个结点时再把相应的结点的visited设置为1，即已经访问。再用visitvex函数显示该结点已访问。然后再把该结点入队。只要队不为空。就把队里的结点出队。并查找下一个结点，直到所有的结点都已经访问完5输入输出的要求5．1输入的要求本来可以手动输入要遍历的总结点数，但是由于结点位置如果以这种方式的话就无法确定，即使有一定的规律，而边的确定也不好把握，所以本设计中已经定好了结点的相应位置，我们只需要输入结点之间是不是有边连接就可行，并输入那条边所连接的起始点和终点。5．2输出的要求因为本课题要求的是演示图的遍历过程，所以我们必须在构建好邻接矩阵后要3把整个图给显示出来。而且重点要演示图的遍历，所以在图中要演示这个过程，在本设计中我是遍历一个结点要求再按一个键再遍历下一个结点，这样也不会因为遍历过程太快根本就看不到这个过程，而且我是用填充图形的方式显示这个结点，这样比较打眼。当使用另外一种遍历方式时，我就把填充图形函数的方式的颜色更改一下。这样就可以完成整个设计的需要。5.3设计方案5.3、1总体设计流程1图的初始化定义图并初始化图2.建立图的邻接表3.图的遍历1.图的深度优先搜索2.图的广度优先搜索5.3、2图的遍历的模块化1.图的存储结构；2.图的输入；3.BFS和DFS编码；4概要设计2.1主函数功能模块图：图2.1.1主函数功能模块图主函数main()Printfvertex（）输出结点的位置Creatgraph(g,n)初始化图，并使之存在邻接矩阵里Printfgraph(g)输出整个图输入menu调用BESTraverse(g)调用dfstraverse(g)重新输入退出5主流程图开始（创建图）CreateGraph():按从键盘的数据建立图按照自己的要求输入图的结点数和弧数输入结点名称和结点直接的接连关系BFSGrahp()：广度优先遍历DFSGrahp()：深度优先遍历输出遍历结果输出遍历结果结束图的遍历的演示6详细设计1抽象数据类型图的定义如下：ADTGraph{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}基本运算：creatgraph(g,n):建立一个邻接矩阵并以一个二元数组存储BESTraverse(g):将图以广度优先算法的思路进行遍历printgraph(g):将图按照自己存储的二元数组以图形的方式输出dfstraverse(g):将图以深度优先算法的思路进行遍历｝ADTGraph2抽象数据类型队列的定义如下：ADTQueue{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}约定其中a1端为队列头，an端为队列尾基本操作：initqueue(q)操作结果：构造一个空队列。queempty(q)初始条件：队列q已存在。操作结果：若q为空队列，则返回0，否则返回1enqueue(q,e)初始条件：队列q已存在。操作结果：插入元素e为q的新的队尾元素。dequeue(q)初始条件：q为非空队列。操作结果：删除q的队头元素，并用t返回其值。}ADTQueue7程序编码3.1采用C语言定义相关的数据类型3.1.1图的定义/*定义图*/typedefstruct{intV[M]intR[M][M]intvexnum}Graph/*创建图*/voidcreatgraph(Graph*g,intn){inti,j,r1,r2gvexnum=n/*顶点用i表示*/for(i=1i=ni++){gV[i]=i}/*初始化R*/for(i=1i=ni++)for(j=1j=nj++){gR[i][j]=0}3．1．2队列的定义8typedefstruct{intV[M];intfront;intrear;}Queue;3.2写出各模块的类C码算法3.2.1Creatgraph(g,n)/*创建图函数伪代码*/Begin//开始n=g-vexnumfor(i=1;i=n;i++)/*顶点用i表示*/theni=g-V[i]for(i=1;i=n;i++)/*初始化R*/for(j=1;j=n;j++)then0=g-R[i][j]Scanfr1,r2while(r1!=0&&r2!=0)do1=g-R[r1][r2]1=g-R[r2][r1]scanfr1,r2enddoEnd/*算法结束*/3.2.2BESTraverse(g)/*广度优先算法*/begin(Queue*)malloc(sizeof(Queue))＝Queue*q//初始化qfor(i=1;i=g-vexnum;i++)//将所有的结点的访问标志都定为0then0=visited[i]initqueue(q)for(i=1;i=g-vexnum;i++)thenif(!visited[i])/*如果尚未被访问则置访问标志为1并且输出入队*/then9visited[i]=1;/**/visitvex(g,g-V[i])enqueue(q,g-V[i])while(quempty(q)==1)doi=dequeue(q);//将队列中的元素出队for(j=1;j=g-vexnum;j++){if(g-R[i][j]!=0&&visited[j]==0)//输出i结点所有未访问的邻接点{visited[j]=1;visitvex(g,j);enqueue(q,j);}}endifenddoend/*算法结束*/3.2.3dfstraverse(g)/*深度优先算法的伪代码*/beginfor(i=1;i=g-vexnum;i++)0=visited[i]for(i=1;i=g-vexnum;i++)if(!visited[i])thendfs(g,i)endifend/*算法结束*/3.2.4printgraph(g)/*输出图*/begin/*画结点*/for(i=0;i6;i++){circle(r[i][0],r[i][1],12)10outtextxy(r[i][0],r[i][1],s[i])}/*画出各结点之间有联系的线段*/for(i=1;i=g-vexnum;i++)for(j=1;j=g-vexnum;j++)thenif(g-R[i][j]!=0)thenif(i==1&&j==2)line(l[0][0],l[0][1],l[0][2],l[0][3])elseif((i==1)&&(j==3))line(l[1][0],l[1][1],l[1][2],l[1][3])elseif((i==2)&&(j==3))line(l[2][0],l[2][1],l[2][2],l[2][3])elseif((i==2)&&(j==4))line(l[3][0],l[3][1],l[3][2],l[3][3])elseif((i==2)&&(j==5))line(l[4][0],l[4][1],l[4][2],l[4][3])elseif((i==3)&&(j==5))line(l[5][0],l[5][1],l[5][2],l[5][3])elseif((i==3)&&(j==6))line(l[6][0],l[6][1],l[6][2],l[6][3])elseif((i==4)&