数据结构课程设计图的存储与遍历报告.docx
《数据结构课程设计图的存储与遍历报告.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计图的存储与遍历报告.docx（16页珍藏版）》请在冰点文库上搜索。
数据结构课程设计图的存储与遍历报告
数据结构课程设计图的存储与遍历报告
《数据结构》课程设计
题目图的存储与遍历
学生姓名
指导教师
学院
专业班级
完成时间
第一章课程设计目的2第二章课程设计内容和要求2第三章课程设计分析3第四章算法描述4第五章源代码8第六章运行结果分析13第七章结束语15第八章参考文献15
第一章课程设计目的
本学期我们对《数据结构》这门课程进行了学习。
这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。
这次课程设计不但要求实习者掌握《数据结构》中的各方面知识，还要求实习者具备一定的C语言基础和编程能力。
具体说来，这次课程设计主要有两大方面目的。
一是让实习者通过实习掌握《数据结构》中的知识。
对于《图的存储与遍历》这一课题来说，所要求掌握的数据结构知识主要有：
图的邻接表存贮结构、队列的基本运算实现、邻接表的算法实现、图的广度优先搜索周游算法实现、图的深度优先搜索周游算法实现。
二是通过实习巩固并提高实习者的C语言知识，并初步了解VisualC++的知识，提高其编程能力与专业水平。
第二章课程设计内容和要求
2.1课程设计内容
该课题要求以邻接表的方式存储图，输出邻接表，并要求实现图的深度、广度两种遍历。
2.1.1图的邻接表的建立与输出
对任意给定的图（顶点数和边数自定），并且对有向图与无向图都应进行讨论，根据邻接表的存储结构建立图的邻接表并输出之。
尽量用图形化的方式输出邻接表。
2.1.2图的遍历的实现
图的遍历包括图的广度优先遍历与深度优先遍历。
对于广度优先遍历应利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。
首先建立一空队列，从初始点出发进行访问，当被访问时入队，访问完出队。
并以队列是否为空作为循环控制条件。
对于深度优先遍历则采用递归或非递归算法来实现。
2.2运行环境
该程序的运行环境为Windowsxp系统，MicrosoftVisualC++6.0版本。
第三章课程设计分析
3.1图的存储
本课题要求采取邻接表的存储结构。
邻接表是一种链式的存储结构，在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的弧）。
每个结点由3个域组成，其中邻接点域（adjvex）指示与顶点Vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的结点；数据域（info）存储和边或弧相关的信息，如权值等。
所以一开始必须先定义邻接表的边结点类型以及邻接表类型，并对邻接表进行初始化，然后根据所输入的相关信息，包括图的顶点数、边数、是否为有向，以及各条边的起点与终点序号，建立图的邻接表。
此时要分两种情况：
有向图与无向图。
对于无向图，一条边的两的个顶点，互为邻接点，所以在存储时，应向起点的单链表表头插入一边结点，即终点。
同时将终点的单链表表头插入一边结点，即起点。
对于有向图，只能向起点的单链表的表头插入一个边结点，即终点。
但不能反过来。
至于邻接表的输出，由于不了解C++中的绘图操作，故采用for语句输出各结点，并配合一些符号完成邻接表的输出。
3.2图的遍历
3.2.1图的深度优先遍历
假设初始状态是图中所有顶点未曾被访问，深度优先遍历可以从图的初始点出发，访问初始点，然后依次从v未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时仍有顶点未被访问到，则从另一个未被访问的顶点出发，重复上述过程，直至所有点都被访问到为止。
这是一个递归的过程。
所以在实现深度优先遍历的过程中必须递归调用深度优先搜索函数。
而且在深度优先搜索函数中必须设一标志数组以标记结点是否被访问。
具体过程应为：
先访问初始点Vi，并标志其已被访问。
此时定义一指向边结点的指针p，并建立一个while（）循环，以指针所指对象不为空为控制条件，当Vi的邻接点未被访问时，递归调用深度优先遍历函数访问之。
然后将p指针指向下一个边结点。
这样就可以完成图的深度优先遍历了。
3.2.2图的广度优先遍历
广度优先搜索遍历类似于树的按层次遍历的过程。
假设从图中某顶点v出发，在访问了v之后访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点的邻接点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到。
若此时图中尙有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。
换句话说，广度优先搜索遍历图的过程是以v为起始点，由近及远，依次访问和v有路径相通且路径长度为1，2，……的顶点。
所以要实现算法必须先建立一个元素类型为整形的空队列，并定义队首与队尾指针，同时也要定义一个标志数组以标记结点是否被访问。
同样，也是从初始点出发开始访问，访问初始点，标志其已被访问，并将其入队。
当队列非空时进行循环处理。
当结点被访问时对其进行标志，并入队列。
通过while（）循环，并以是否被访问为控制条件，访问所有结点，完成图的广度优先遍历。
第四章算法（数据结构）描述
4.1图的存储结构的建立。
4.1.1定义邻接表的边结点类型以及邻接表类型
structedgenode{
intadjvex;//该弧所指向的顶点的位置
edgenode*next;//指向下条条弧的指针
};//定义邻接表的边结点类型
typedefedgenode**adjlist;//定义邻接表类型
4.1.2初始化图的邻接表
需建立一个邻接表初始化函数对图的邻接表进行初始化。
即建立一个所有边结点都为空的邻接表。
voidInitGAdjoin（adjlist&GL,intn）
//初始化图的邻接表
{
GL=newedgenode*[n];
for（inti=1;i<=n;i++）GL[i]=NULL;
}
4.1.3建立并输出图的邻接表
首先必须输入图的相关信息，包括图的顶点数、边数、各条边的起点和终点，为保证输入数据的正确性，我在程序中设计了一个判断所输结点是否越界的函数check（）当所输的顶点序号超出序号的范围时则报错，并要求重新输入。
还有就图是否有向，此时可定义一变量，图的是否有向，可用变量的值来表示。
此处定了变量m，当图为无向时，m等于0。
图为有向时m等于1。
用if（）语句判断m的值，就可将图分有向和无向两种情况来进行分析了。
对于无向图，各条边的起点和终点互为邻接点。
所以必须把起点添加到终点的邻接点域中，并把终点添加到起点的邻接点域中。
而对于有向图，只能是将弧头添加到弧尾的邻接点域中。
最后是输出邻接表，即对于每个顶点，输出其邻接点。
由于不了解C++中绘图函数的用法，所以利用一些符号来达到图形化的效果。
邻接表输出的相关代码如下：
cout<<"图的邻接表为:
"<for（i=1;i<=n;i++）{
edgenode*p=GL[i];
cout<for（p=GL[i];p!
=NULL;p=p->next）
cout<<"|-|->|"<adjvex;
cout<<"|^|";
cout<}//输出邻接表
4.2图的遍历
4.2.1深度优先遍历图的邻接表
假设初始状态是图中所有顶点未曾被访问，深度优先遍历可以从图的初始点出发，访问初始点，然后依次从v未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时仍有顶点未被访问到，则从另一个未被访问的顶点出发，重复上述过程，直至所有点都被访问到为止。
这是一个递归的过程。
所以在实现深度优先遍历的过程中必须递归调用深度优先搜索函数。
而且在深度优先搜索函数中必须设一标志数组以标记结点是否被访问。
具体过程应为：
在深度优先遍历函数的参数中定义一个标志数组bool*&visited，当某结点已被访问时，标志数组的值为关键字ture，未被访问时其值为关键字false。
先访问初始点Vi，并标志其已被访问。
此时定义一指向边结点的指针p，并建立一个while（）循环，以指针所指对象不为空为控制条件，当Vi的邻接点未被访问时，递归调用深度优先遍历函数访问之。
然后将p指针指向下一个边结点。
这样就可以完成图的深度优先遍历了。
深度优先遍历的相关代码如下：
voiddfsAdjoin（adjlistGL,bool*&visited,inti,intn）
//从初始点出发深度优先搜索邻接表GL表示的图
{
cout<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单链表的下一个边结点
}
}
4.2.2广度优先遍历图的邻接表
图的广度优先遍历是从初始点出发，访问初始点，再访问初始点的邻接点。
当初始点的所有邻接点都被访问过时，再依次访问各邻接点的邻接点。
如此循环下去。
算法的实现必须依靠辅助队列，结点被访问后，对其进行标记，并将结点入队列。
所以要实现算法必须先建立一个元素类型为整形的空队列，并定义队首与队尾指针，同时也要定义一个标志数组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<visited[j]=true;
rear=（rear+1）%MaxLength;
q[rear]=j;
}
p=p->next;
}
这样就可以访问所有结点，完成图的广度优先遍历。
第五章源代码
程序图的存储与遍历
头文件图.h
#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
实现文件图.cpp
#include
#include
#include"图.h"
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）
//建立图的邻接表
{
inti,j,k,e;
cout<<"输入图的总边数：
";
cin>>e;
if（m==0）{
//建立无向图
for（k=0;kcout<<"输入第"<"<cin>>i>>j;
Check（n,i,j）;
edgenode*p=newedgenode;
p->adjvex=j;
p->next=GL[i];
GL[i]=p;
//向序号为i的单链表的表头插入一个边结点
p=newedgenode;
p->adjvex=i;
p->next=GL[j];
GL[j]=p;
//向序号为j的单链表的表头插入一个边结点
}
cout<cout<<"图的邻接表为:
"<for（i=1;i<=n;i++）{
edgenode*p=GL[i];
cout<for（p=GL[i];p!
=NULL;p=p->next）
cout<<"|-|->|"<adjvex;
cout<<"|^|";
cout<}
//输出邻接表
}
elseif（m==1）{//建立有向图
for（k=1;k<=e;k++）{
cout<<"输入第"<"<cin>>i>>j;
Check（n,i,j）;
//向序号为i的表头插入一个边结点
edgenode*p=newedgenode;
p->adjvex=j;
p->next=GL[i];
GL[i]=p;
}
cout<<"图的邻接表为:
"<for（i=1;i<=n;i++）{
edgenode*p=GL[i];
cout<for（p=GL[i];p!
=NULL;p=p->next）
cout<<"|-|->|"<adjvex;
cout<<"|^|";
cout<}
//输出邻接表
}
}
voiddfsAdjoin（adjlistGL,bool*&visited,inti,intn）
//从初始点出发深度优先搜索邻接表GL表示的图
{
cout<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单链表的下一个边结点
}
}
voidbfsAdjoin（adjlistGL,bool*&visited,inti,intn）
//从初始点出发广度优先搜索邻接表GL表示的图
{
constintMaxLength=30;
intq[MaxLength]={0};
//定义一个队列q,其元素类型为整形
intfront=0,rear=0;
//定义队首和队尾指针
cout<//访问Vi
visited[i]=true;
//标记初始点Vi已访问过
q[++rear]=i;
//将已访问过的初始点序号i入队
while（front!
=rear）{
//当队列非空时进行循环处理
front=（front+1）%MaxLength;
//删除队首元素，第一次执行时k的值为i
intk=q[front];
edgenode*p=GL[k];
//取Vk邻接表的表头指针
while（p!
=NULL）{
//依次搜索Vk的每一个结点
intj=p->adjvex;
//Vj为Vk的一个邻接点
if（!
visited[j]）{
//若Vj没有被访问过则进行处理
cout<visited[j]=true;
rear=（rear+1）%MaxLength;
q[rear]=j;
}
p=p->next;
}
}
}
voidCheck（intn,int&i,int&j）
//检查输入的边序号是否越界，若越界则重输
{
while
（1）{
if（i<=0||i>n||j<=0||j>n）
cout<<"输入有误,请重新输入！
";
elsereturn;
cin>>i>>j;
}
}
主函数程序文件主函数.cpp
#include
#include"图.h"
voidmain（）
{
inti,n,m;
cout<<"=============="<cout<<"输入图的顶点数:
";
cin>>n;
cout<<"输入是否有向（0为无，1为有）:
";
cin>>m;
bool*visited=newbool[n];
adjlistgl;
InitGAdjoin（gl,n）;
CreateAdjoin（gl,n,m）;
cout<<"=============="<cout<<"图的深度优先遍历序列:
"<for（i=1;i<=n;i++）visited[i]=false;
dfsAdjoin（gl,visited,1,n）;
cout<cout<<"图的广度优先遍历序列:
"<for（i=1;i<=n;i++）visited[i]=false;
bfsAdjoin（gl,visited,1,n）;
cout<}
第六章运行结果分析
由于实习之初对邻接表的存储结构了解不是很清楚，所以在运行出了一个小错误，即在输出邻接表时，每个结点都少了一个邻接点。
通过仔细分析，发现是输出邻接表的语句不对，其中的for（）循环语句中的控制条件：
p->next!
=NULL出了问题。
将其改成p!
=NULL后，邻接表便可顺利输出。
下面就是经修改后以有向图G1和无向图G2为例的程序运行结果。
V1V2V1V2
V3
V3V4V4V5
图1G1图2G2
1.有向图G1的运行结果
图3G1的运行结果
2．无向图G2的运行结果
图4G2的运行结果
第七章结束语
转眼，为期两周的《数据结构》课程设计实习即将结束了。
在这次实习中，自己的C语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高。
同时也学会了解决问题的方法。
总结起来，自己主要有以下几点体会：
1.必须牢固掌握基础知识。
由于C语言是大一所学知识，有所遗忘，且未掌握好这学期所学的《数据结构》这门课，所以在实习之初感到棘手。
不知如何下手，但在后来的实习过程中自己通过看书和课外资料，并请教其他同学，慢慢地对C语言和数据结构知识有所熟悉。
这时才逐渐有了思路。
所以，这次实习之后，我告诫自己：
今后一定要牢固掌握好专业基础知识。
2.必须培养严谨的科学态度。
自己在编程时经常因为一些类似于“少了分号”的小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。
编程是一件十分严谨的事情，容不得马虎。
所以在今后自己一定要培养严谨的科学态度。
我想这不仅是对于程序设计，做任何事都应如此。
3.这次课程设计也让我充分认识到《数据结构》这门课的重要性。
它给我们一个思想和大纲，让我们在编程时容易找到思路，不至于无章可循。
同时它也有广泛的实际应用。
总之，在这次实习中，自己的C语言以及数据结构知识得到提高，编程能力也得到了提高。
第八章参考文献
1．杨路明C语言程序设计教程北京邮电大学出版社
2．徐孝凯数据结构课程实验清华大学出版社
3．严蔚敏吴伟民数据结构（C语言版）清华大学出版社
升级会员 