数据结构课程设计图的存储与遍历报告.doc

该【数据结构课程设计图的存储与遍历报告 】是由【读书百遍】上传分享，文档一共【20】页，该文档可以免费在线阅读，需要了解更多关于【数据结构课程设计图的存储与遍历报告 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。《数据构造》课程设计
题目图的存储与遍历
学生姓名
指引教师
学院
专业班级
完毕时间
目录
第一章课程设计目的 2 第二章课程设计内容和规定 2 第三章课程设计分析 3 第四章算法描述 4 第五章源代码 8 第六章运营成果分析 13 第七章结束语 15 第八章参照文献 15
第一章课程设计目的
本学期我们对《数据构造》这门课程进行了学****这门课程是一门实践性非常强的课程,为了让人们更好地理解与运用所学知识,提高动手能力,我们进行了本次课程设计实****这次课程设计不仅规定实****者掌握《数据构造》中的各方面知识,还规定实****者具有一定的C语言基本和编程能力。
具体说来,这次课程设计重要有两大方面目的。
一是让实****者通过实****掌握《数据构造》中的知识。对于《图的存储与遍历》这一课题来说,所规定掌握的数据构造知识重要有:图的邻接表存贮构造、队列的基本运算实现、邻接表的算法实现、图的广度优先搜索环游算法实现、图的深度优先搜索环游算法实现。
二是通过实****巩固并提高实****者的C语言知识,并初步理解VisualC++的知识,提高其编程能力与专业水平。
第二章课程设计内容和规定

该课题规定以邻接表的方式存储图,输出邻接表,并规定实现图的深度、广度两种遍历。

对任意给定的图(顶点数和边数自定),并且对有向图与无向图都应进行讨论,根据邻接表的存储构造建立图的邻接表并输出之。尽量用图形化的方式输出邻接表。

图的遍历涉及图的广度优先遍历与深度优先遍历。对于广度优先遍历应运用队列的五种基本运算(置空队列、进队、出队、取队头元素、判队空)来实现。一方面建立一空队列,从初始点出发进行访问,当被访问时入队,访问完出队。并以队列与否为空作为循环控制条件。对于深度优先遍历则采用递归或非递归算法来实现。

该程序的运营环境为Windowsxp系统,MicrosoftVisualC++。
第三章课程设计分析

本课题规定采用邻接表的存储构造。邻接表是一种链式的存储构造,在邻接表中,对图中每个顶点建立一种单链表,第i个单链表中的结点表达依附于顶点Vi的边(对有向图是以顶点Vi为尾的弧)。每个结点由3个域构成,其中邻接点域(adjvex)批示与顶点Vi邻接的点在图中的位置,链域(nextarc)批示下一条边或弧的结点;数据域(info)存储和边或弧有关的信息,如权值等。
因此一开始必须先定义邻接表的边结点类型以及邻接表类型,并对邻接表进行初始化,然后根据所输入的有关信息,涉及图的顶点数、边数、与否为有向,以及各条边的起点与终点序号,建立图的邻接表。此时要分两种状况:有向图与无向图。对于无向图,一条边的两的个顶点,互为邻接点,因此在存储时,应向起点的单链表表头插入一边结点,即终点。同步将终点的单链表表头插入一边结点,即起点。对于有向图,只能向起点的单链表的表头插入一种边结点,即终点。但不能反过来。至于邻接表的输出,由于不理解C++中的绘图操作,故采用for语句输出各结点,并配合某些符号完毕邻接表的输出。


假设初始状态是图中所有顶点未曾被访问,深度优先遍历可以从图的初始点出发,访问初始点,然后依次从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;
}
这样就可以访问所有结点,完毕图的广度优先遍历。
第五章源代码
程序图的存储与遍历

#ifndefGRAPH_H
#defineGRAPH_H
#defineMAX_VRTEX_NUM20
structedgenode{
intadjvex;
edgenode*next;
};//定义邻接表的边结点类型
typedefedgenode**adjlist;
//定义邻接表类型
voidInitGAdjoin(adjlist&GL,intn);
//初始化图的邻接表
voidCreateAdjoin(adjlist&GL,intn,intm);
//建立图的邻接表
voiddfsAdjoin(adjlistGL,bool*&visited,inti,intn);
//从初始点出发深度优先搜索由邻接表GL表达的图
voidbfsAdjoin(adjlistGL,bool*&visited,inti,intn);
//从初始点出发广度优先搜索由邻接表GL表达的图
#endif

#include<>
#include<>
#include""
voidCheck(intn,int&i,int&j);
voidInitGAdjoin(adjlist&GL,intn)
//初始化图的邻接表
{
GL=newedgenode*[n];
for(inti=1;i<=n;i++)GL[i]=NULL;
}
voidCreateAdjoin(adjlist&GL,intn,intm)
//建立图的邻接表
{