下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 图的存储与遍历算法-数据结构-课程设计

图的存储与遍历算法-数据结构-课程设计.doc

图的存储与遍历算法-数据结构-课程设计

姚Susie
2018-01-24 0人阅读 举报 0 0 暂无简介

简介:本文档为《图的存储与遍历算法-数据结构-课程设计doc》,可适用于IT/计算机领域

图的存储与遍历算法数据结构课程设计图的存储与遍历算法数据结构课程设计图的存储与遍历算法课程设计目的本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程为了让大家更好地理解与运用所学知识提高动手能力我们进行了此次课程设计实习。这次课程设计不但要求实习者掌握《数据结构》中的各方面知识还要求实习者具备一定的C语言基础和编程能力。具体说来这次课程设计主要有两大方面目的。一是让实习者通过实习掌握《数据结构》中的知识。对于《图的存储与遍历》这一课题来说所要求掌握的数据结构知识主要有:图的邻接表存贮结构、队列的基本运算实现、邻接表的算法实现、图的广度优先搜索周游算法实现、图的深度优先搜索周游算法实现。二是通过实习巩固并提高实习者的C语言知识并初步了解VisualC的知识提高其编程能力与专业水平。第二章课程设计内容和要求课程设计内容该课题要求以邻接表的方式存储图输出邻接表并要求实现图的深度、广度两种遍历。图的邻接表的建立与输出对任意给定的图(顶点数和边数自定)并且对有向图与无向图都应进行讨论根据邻接表的存储结构建立图的邻接表并输出之。尽量用图形化的方式输出邻接表。图的遍历的实现图的遍历包括图的广度优先遍历与深度优先遍历。对于广度优先遍历应利用队列的五种基本运算(置空队列、进队、出队、取队头元素、判队空)来实现。首先建立一空队列从初始点出发进行访问当被访问时入队访问完出队。并以队列是否为空作为循环控制条件。对于深度优先遍历则采用递归或非递归算法来实现。运行环境该程序的运行环境为Windowsxp系统MicrosoftVisualC版本。第三章课程设计分析图的存储本课题要求采取邻接表的存储结构。邻接表是一种链式的存储结构在邻接表中对图中每个顶点建立一个单链表第i个单链表中的结点表示依附于顶点Vi的边(对有向图是以顶点Vi为尾的弧)。每个结点由个域组成其中邻接点域(adjvex)指示与顶点Vi邻接的点在图中的位置链域(nextarc)指示下一条边或弧的结点数据域(info)存储和边或弧相关的信息如权值等。所以一开始必须先定义邻接表的边结点类型以及邻接表类型并对邻接表进行初始化然后根据所输入的相关信息包括图的顶点数、边数、是否为有向以及各条边的起点与终点序号建立图的邻接表。此时要分两种情况:有向图与无向图。对于无向图一条边的两的个顶点互为邻接点所以在存储时应向起点的单链表表头插入一边结点即终点。同时将终点的单链表表头插入一边结点即起点。对于有向图只能向起点的单链表的表头插入一个边结点即终点。但不能反过来。至于邻接表的输出由于不了解C中的绘图操作故采用for语句输出各结点并配合一些符号完成邻接表的输出。图的遍历图的深度优先遍历假设初始状态是图中所有顶点未曾被访问深度优先遍历可以从图的初始点出发访问初始点然后依次从v未被访问的邻接点出发深度优先遍历图直至图中所有和v有路径相通的顶点都被访问到若此时仍有顶点未被访问到则从另一个未被访问的顶点出发重复上述过程直至所有点都被访问到为止。这是一个递归的过程。所以在实现深度优先遍历的过程中必须递归调用深度优先搜索函数。而且在深度优先搜索函数中必须设一标志数组以标记结点是否被访问。具体过程应为:先访问初始点Vi并标志其已被访问。此时定义一指向边结点的指针p并建立一个while()循环以指针所指对象不为空为控制条件当Vi的邻接点未被访问时递归调用深度优先遍历函数访问之。然后将p指针指向下一个边结点。这样就可以完成图的深度优先遍历了。图的广度优先遍历广度优先搜索遍历类似于树的按层次遍历的过程。假设从图中某顶点v出发在访问了v之后访问它们的邻接点并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点的邻接点”被访问直到图中所有已被访问的顶点的邻接点都被访问到。若此时图中尙有顶点未被访问则另选图中一个未曾被访问的顶点作起始点重复上述过程直到图中所有顶点都被访问到为止。换句话说广度优先搜索遍历图的过程是以v为起始点由近及远依次访问和v有路径相通且路径长度为„„的顶点。所以要实现算法必须先建立一个元素类型为整形的空队列并定义队首与队尾指针同时也要定义一个标志数组以标记结点是否被访问。同样也是从初始点出发开始访问访问初始点标志其已被访问并将其入队。当队列非空时进行循环处理。当结点被访问时对其进行标志并入队列。通过while()循环并以是否被访问为控制条件访问所有结点完成图的广度优先遍历。第四章算法(数据结构)描述图的存储结构的建立。定义邻接表的边结点类型以及邻接表类型structedgenode{intadjvex该弧所指向的顶点的位置edgenode*next指向下条条弧的指针}定义邻接表的边结点类型typedefedgenode**adjlist定义邻接表类型初始化图的邻接表需建立一个邻接表初始化函数对图的邻接表进行初始化。即建立一个所有边结点都为空的邻接表。voidInitGAdjoin(adjlistGL,intn)初始化图的邻接表{GL=newedgenode*nfor(inti=i<=ni)GLi=}建立并输出图的邻接表首先必须输入图的相关信息包括图的顶点数、边数、各条边的起点和终点为保证输入数据的正确性我在程序中设计了一个判断所输结点是否越界的函数check()当所输的顶点序号超出序号的范围时则报错并要求重新输入。还有就图是否有向此时可定义一变量图的是否有向可用变量的值来表示。此处定了变量m当图为无向时m等于。图为有向时m等于。用if()语句判断m的值就可将图分有向和无向两种情况来进行分析了。对于无向图各条边的起点和终点互为邻接点。所以必须把起点添加到终点的邻接点域中并把终点添加到起点的邻接点域中。而对于有向图只能是将弧头添加到弧尾的邻接点域中。最后是输出邻接表即对于每个顶点输出其邻接点。由于不了解C中绘图函数的用法所以利用一些符号来达到图形化的效果。邻接表输出的相关代码如下:cout<<"图的邻接表为:"<<endlfor(i=i<=ni){edgenode*p=GLicout<<i<<"|"<<"V"<<ifor(p=GLip!=p=p>next)cout<<"||>|"<<p>adjvexcout<<"|^|"cout<<endl}输出邻接表图的遍历深度优先遍历图的邻接表假设初始状态是图中所有顶点未曾被访问深度优先遍历可以从图的初始点出发访问初始点然后依次从v未被访问的邻接点出发深度优先遍历图直至图中所有和v有路径相通的顶点都被访问到若此时仍有顶点未被访问到则从另一个未被访问的顶点出发重复上述过程直至所有点都被访问到为止。这是一个递归的过程。所以在实现深度优先遍历的过程中必须递归调用深度优先搜索函数。而且在深度优先搜索函数中必须设一标志数组以标记结点是否被访问。具体过程应为:在深度优先遍历函数的参数中定义一个标志数组bool*visited当某结点已被访问时标志数组的值为关键字ture未被访问时其值为关键字false。先访问初始点Vi并标志其已被访问。此时定义一指向边结点的指针p并建立一个while()循环以指针所指对象不为空为控制条件当Vi的邻接点未被访问时递归调用深度优先遍历函数访问之。然后将p指针指向下一个边结点。这样就可以完成图的深度优先遍历了。深度优先遍历的相关代码如下:voiddfsAdjoin(adjlistGL,bool*visited,inti,intn)搜索邻接表GL表示的图从初始点出发深度优先{cout<<i<<''''visitedi=trueedgenode*p=GLiwhile(p!=){intj=p>adjvexj为Vi的一个邻接点的序号if(!visitedj)dfsAdjoin(GL,visited,j,n)p=p>next使p指向Vi单链表的下一个边结点}}广度优先遍历图的邻接表图的广度优先遍历是从初始点出发访问初始点再访问初始点的邻接点。当初始点的所有邻接点都被访问过时再依次访问各邻接点的邻接点。如此循环下去。算法的实现必须依靠辅助队列结点被访问后对其进行标记并将结点入队列。所以要实现算法必须先建立一个元素类型为整形的空队列并定义队首与队尾指针同时也要定义一个标志数组bool*visited以标记结点是否被访问。同图的存储与遍历算法数据结构样也是从初始点Vi出发开始访问访问初始点标志其已被访问并将已访问过的初始点序号i入队。当队列非空时进行循环处理删除队首元素第一次执行时k的值为i即front=(front)MaxLength。然后取Vk邻接表的表头指针intk=qfrontedgenode*p=GLk。当边结点指针p不为空时通过while()循环并以p是否为空为控制条件依次搜索Vk的每一个结点。若Vj没有被访问过则进行处理。访问完后将p指向p>next。其中的while循环部分的代码如下:while(p!=){依次搜索Vk的每一个结点intj=p>adjvexVj为Vk的一个邻接点if(!visitedj){若Vj没有被访问过则进行处理cout<<j<<''''visitedj=truerear=(rear)MaxLengthqrear=j}p=p>next}这样就可以访问所有结点完成图的广度优先遍历。第五章源代码程序图的存储与遍历h头文件图#ifndefGRAPHH#defineGRAPHH#defineMAXVRTEXNUMstructedgenode{intadjvexedgenode*next}定义邻接表的边结点类型typedefedgenode**adjlist定义邻接表类型voidInitGAdjoin(adjlistGL,intn)初始化图的邻接表voidCreateAdjoin(adjlistGL,intn,intm)建立图的邻接表voiddfsAdjoin(adjlistGL,bool*visited,inti,intn)从初始点出发深度优先搜索由邻接表GL表示的图voidbfsAdjoin(adjlistGL,bool*visited,inti,intn)从初始点出发广度优先搜索由邻接表GL表示的图#endif实现文件图cpp#include<iostreamh>#include<stdioh>#include"图h"voidCheck(intn,inti,intj)voidInitGAdjoin(adjlistGL,intn)初始化图的邻接表{GL=newedgenode*nfor(inti=i<=ni)GLi=}voidCreateAdjoin(adjlistGL,intn,intm)建立图的邻接表{inti,j,k,ecout<<"输入图的总边数:"cin>>eif(m==){建立无向图for(k=k<ek){cout<<"输入第"<<k<<"条边的起点和终点序号~"<<endlcin>>i>>jCheck(n,i,j)edgenode*p=newedgenodep>adjvex=jp>next=GLiGLi=p向序号为i的单链表的表头插入一个边结点p=newedgenodep>adjvex=ip>next=GLjGLj=p向序号为j的单链表的表头插入一个边结点}cout<<endl<<"=============="<<endlcout<<"图的邻接表为:"<<endlfor(i=i<=ni){edgenode*p=GLicout<<i<<"|"<<"V"<<ifor(p=GLip!=p=p>next)cout<<"||>|"<<p>adjvexcout<<"|^|"cout<<endl}输出邻接表}elseif(m==){建立有向图for(k=k<=ek){cout<<"输入第"<<k<<"条边的起点和终点序号~"<<endlcin>>i>>jCheck(n,i,j)向序号为i的表头插入一个边结点edgenode*p=newedgenodep>adjvex=jp>next=GLiGLi=pmyeducscnfor(p=GLip!=p=p>next)cout<<"||>|"<<p>adjvexcout<<"|^|"cout<<endl}输出邻接表}}voiddfsAdjoin(adjlistGL,bool*visited,inti,intn)从初始点出发深度优先搜索邻接表GL表示的图{cout<<i<<''''visitedi=trueedgenode*p=GLiwhile(p!=){intj=p>adjvexj为Vi的一个邻接点的序号if(!visitedj)dfsAdjoin(GL,visited,j,n)p=p>next使p指向Vi单链表的下一个边结点}}voidbfsAdjoin(adjlistGL,bool*visited,inti,intn)从初始点出发广度优先搜索邻接表GL表示的图{constintMaxLength=intqMaxLength={}图的存储与遍历算法数据结构定义一个队列q,其元素类型为整形intfront=,rear=定义队首和队尾指针cout<<i<<''''访问Vivisitedi=true标记初始点Vi已访问过qrear=i将已访问过的初始点序号i入队while(front!=rear){当队列非空时进行循环处理front=(front)MaxLength删除队首元素第一次执行时k的值为iintk=qfrontedgenode*p=GLk取Vk邻接表的表头指针while(p!=){依次搜索Vk的每一个结点intj=p>adjvexVj为Vk的一个邻接点if(!visitedj){若Vj没有被访问过则进行处理cout<<j<<''''visitedj=truerear=(rear)MaxLengthqrear=j}p=p>next}}}voidCheck(intn,inti,intj)检查输入的边序号是否越界若越界则重输{while(){if(i<=||i>n||j<=||j>n)输入~"cout<<"输入有误,请重新elsereturncin>>i>>j}}主函数程序文件主函数cpp#include<iostreamh>#include"图h"voidmain(){inti,n,mcout<<"=============="<<endlmyeducscncout<<"输入是否有向(为无为有):"cin>>mbool*visited=newboolnadjlistglInitGAdjoin(gl,n)CreateAdjoin(gl,n,m)cout<<"=============="<<endlcout<<"图的深度优先遍历序列:"<<endlfor(i=i<=ni)visitedi=falsedfsAdjoin(gl,visited,,n)cout<<endl<<"=============="<<endlcout<<"图的广度优先遍历序列:"<<endlfor(i=i<=ni)visitedi=falsebfsAdjoin(gl,visited,,n)cout<<endl}图的存储与遍历算法数据结构运行结果分析由于实习之初对邻接表的存储结构了解不是很清楚所以在运行出了一个小错误即在输出邻接表时每个结点都少了一个邻接点。通过仔细分析发现是输出邻接表的语句不对其中的for()循环语句中的控制条件:p>next!=出了问题。将其改成p!=后邻接表便可顺利输出。下面就是经修改后以有向图G和无向图G为例的程序运行结果。VVVVVVVVV有向图G的运行结果图G的运行结果(无向图G的运行结果图G的运行结果第七章结束语转眼为期两周的《数据结构》课程设计实习即将结束了。在这次实习中自己的C语言知识和数据结构知识得到了巩固编程能力也有了一定的提高。同时也学会了解决问题的方法。总结起来自己主要有以下几点体会:必须牢固掌握基础知识。由于C语言是大一所学知识有所遗忘且未掌握好这学期所学的《数据结构》这门课所以在实习之初感到棘手。不知如何下手但在后来的实习过程中自己通过看书和课外资料并请教其他同学慢慢地对C语言和数据结构知识有所熟悉。这时才逐渐有了思路。所以这次实习之后我告诫自己:今后一定要牢固掌握好专业基础知识。必须培养严谨的科学态度。自己在编程时经常因为一些类似于“少了分号”的小错误而导致错误不够认真细致这给自己带来了许多麻烦。编程是一件十分严谨的事情容不得马虎。所以在今后自己一定要培养严谨的科学态度。我想这不仅是对于程序设计做任何事都应如此。这次课程设计也让我充分认识到《数据结构》这门课的重要性。它给我们一个思想和大纲让我们在编程时容易找到思路不至于无章可循。同时它也有广泛的实际应用。总之在这次实习中自己的C语言以及数据结构知识得到提高编程能力也得到了提高。第八章参考文献(杨路明C语言程序设计教程北京邮电大学出版社(徐孝凯数据结构课程实验清华大学出版社(严蔚敏吴伟民数据结构(C语言版)清华大学出版社

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/15

图的存储与遍历算法-数据结构-课程设计

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利