数据结构课程设计报告样本(图的存储与遍历)

数据结构课程设计报告样本(图的存储与遍历)本文简介：这是最后提交的文档资料格式，必须包含几个部分，如果是四到五个人完成要求文档不少于70页，3-4个人完成要求不少于50页。《数据结构》课程设计题目图的存储与遍历学生姓名指导教师学院专业班级完成时间目录（要求自动生成）第一章课程设计目的2第二章课程设计内容和要求2第三章课程设计分析3第四章算法描述4第五

数据结构课程设计报告样本(图的存储与遍历)本文内容：

这是最后提交的文档资料格式，必须包含几个部分，如果是四到五个人完成要求文档不少于70页，3-4个人完成要求不少于50页。

《数据结构》课程设计

题

目

图的存储与遍历

学生姓名

指导教师

学

院

专业班级

完成时间

目

录（要求自动生成）

第一章

课程设计目的2第二章

课程设计内容和要求2第三章

课程设计分析3第四章

算法描述4第五章

源代码8第六章

运行结果分析13第七章

结束语15第八章

参考文献15

第一章

课程设计目的

本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求实习者掌握《数据结构》中的各方面知识，还要求实习者具备一定的C语言基础和编程能力。

具体说来，这次课程设计主要有两大方面目的。

一是让实习者通过实习掌握《数据结构》中的知识。对于《图的存储与遍历》这一课题来说，所要求掌握的数据结构知识主要有：图的邻接表存贮结构、队列的基本运算实现、邻接表的算法实现、图的广度优先搜索周游算法实现、图的深度优先搜索周游算法实现。

二是通过实习巩固并提高实习者的C语言知识，并初步了解Visual

C++的知识，提高其编程能力与专业水平。

第二章

课程设计内容和要求

2.1课程设计内容组成员名称和分工（谁负责了哪个部分）

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

2.1.1图的邻接表的建立与输出

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

2.1.2

图的遍历的实现

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

2.2

运行环境

该程序的运行环境为Windows

xp系统，Microsoft

Visual

C++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

定义邻接表的边结点类型以及邻接表类型

struct

edgenode{

int

adjvex;

//该弧所指向的顶点的位置

edgenode

next;

//指向下条条弧的指针

};

//定义邻接表的边结点类型

typedef

edgenode

adjlist;

//定义邻接表类型

4.1.2

初始化图的邻接表

需建立一个邻接表初始化函数对图的邻接表进行初始化。即建立一个所有边结点都为空的邻接表。

void

InitGAdjoin(adjlist

for(int

i=1;inext)

cout|“adjvex;

coutadjvex;

//j为Vi的一个邻接点的序号

if(!visited[j])

dfsAdjoin(GL,visited,j,n);

p=p->next;

//使p指向Vi单链表的下一个边结点

}

}

4.2.2

广度优先遍历图的邻接表

图的广度优先遍历是从初始点出发，访问初始点，再访问初始点的邻接点。当初始点的所有邻接点都被访问过时，再依次访问各邻接点的邻接点。如此循环下去。算法的实现必须依靠辅助队列，结点被访问后，对其进行标记，并将结点入队列。

所以要实现算法必须先建立一个元素类型为整形的空队列，并定义队首与队尾指针，同时也要定义一个标志数组bool*

edgenode*

p=GL[k]。当边结点指针p不为空时，通过while（）循环，并以p是否为空为控制条件，依次搜索Vk的每一个结点。若Vj没有被访问过则进行处理。访问完后，将p指向p->next。其中的while循环部分的代码如下：

while(p!=NULL){

//依次搜索Vk的每一个结点

int

j=p->adjvex;

//Vj为Vk的一个邻接点

if(!visited[j]){

//若Vj没有被访问过则进行处理

coutnext;

}

这样就可以访问所有结点，完成图的广度优先遍历。

第五章

源代码（源代码必须给注释，代码由谁写的请在相应的代码后写明组成员名称）

程序

图的存储与遍历

头文件

图.h

#ifndef

GRAPH_H

#define

GRAPH_H

#define

MAX_VRTEX_NUM

20

struct

edgenode{

int

adjvex;

edgenode

next;

};

//定义邻接表的边结点类型（由张三写的）

typedef

edgenode*adjlist;

//定义邻接表类型

void

InitGAdjoin(adjlist

//初始化图的邻接表

void

CreateAdjoin(adjlist

//建立图的邻接表

void

dfsAdjoin(adjlist

GL,bool*

//从初始点出发深度优先搜索由邻接表GL表示的图

void

bfsAdjoin(adjlist

GL,bool*

//从初始点出发广度优先搜索由邻接表GL表示的图

#endif

实现文件

图.cpp

#include

#include

#include“图.h“void

Check(int

n,int

void

InitGAdjoin(adjlist

for(int

i=1;i>e;

if(m==0){

//建立无向图

for(k=0;k>i>>j;

Check(n,i,j);

edgenode*p=new

edgenode;

p->adjvex=j;

p->next=GL[i];

GL[i]=p;

//向序号为i的单链表的表头插入一个边结点

p=new

edgenode;

p->adjvex=i;

p->next=GL[j];

GL[j]=p;

//向序号为j的单链表的表头插入一个边结点

}

coutnext)

cout|“adjvex;

cout>i>>j;

Check(n,i,j);

//向序号为i的表头插入一个边结点

edgenode*p=new

edgenode;

p->adjvex=j;

p->next=GL[i];

GL[i]=p;

}

coutnext)

cout|“adjvex;

coutadjvex;

//j为Vi的一个邻接点的序号

if(!visited[j])

dfsAdjoin(GL,visited,j,n);

p=p->next;

//使p指向Vi单链表的下一个边结点

}

}

void

bfsAdjoin(adjlist

GL,bool*

int

q[MaxLength]={0};

//定义一个队列q,其元素类型为整形

int

front=0,rear=0;

//定义队首和队尾指针

coutadjvex;

//Vj为Vk的一个邻接点

if(!visited[j]){

//若Vj没有被访问过则进行处理

coutnext;

}

}

}

void

Check(int

n,int

}

}

主函数程序文件

主函数.cpp

#include

#include“图.h“void

main()

{

int

i,n,m;

cout>n;

cout>m;

bool*visited=new

bool[n];

adjlist

gl;

InitGAdjoin(gl,n);

CreateAdjoin(gl,n,m);

coutnext!=NULL出了问题。将其改成p!=NULL后，邻接表便可顺利输出。下面就是经修改后以有向图G1和无向图G2为例的程序运行结果。

V

V

V

V

V1V2

V1V2

V

V3

V

V

V3V4

V4V5

图1

G1

图2

G2

1.有向图G1的运行结果

图3

G1的运行结果

2．无向图G2的运行结果

图4

G2的运行结果

第七章

结束语

转眼，为期两周的《数据结构》课程设计实习即将结束了。在这次实习中，自己的C语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高。同时也学会了解决问题的方法。总结起来，自己主要有以下几点体会：

1.必须牢固掌握基础知识。由于C语言是大一所学知识，有所遗忘，且未掌握好这学期所学的《数据结构》这门课，所以在实习之初感到棘手。不知如何下手，但在后来的实习过程中自己通过看书和课外资料，并请教其他同学，慢慢地对C语言和数据结构知识有所熟悉。这时才逐渐有了思路。所以，这次实习之后，我告诫自己：今后一定要牢固掌握好专业基础知识。

2.必须培养严谨的科学态度。自己在编程时经常因为一些类似于“少了分号”的小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十分严谨的事情，容不得马虎。所以在今后自己一定要培养严谨的科学态度。我想这不仅是对于程序设计，做任何事都应如此。

3.这次课程设计也让我充分认识到《数据结构》这门课的重要性。它给我们一个思想和大纲，让我们在编程时容易找到思路，不至于无章可循。同时它也有广泛的实际应用。

总之，在这次实习中，自己的C语言以及数据结构知识得到提高，编程能力也得到了提高。

第八章

参考文献（要求不少于5篇，可以是论文，可以是专著）

1．

杨路明

C语言程序设计教程

北京邮电大学出版社

2．

徐孝凯

数据结构课程实验

清华大学出版社

3．

严蔚敏

吴伟民

数据结构（C语言版）

清华大学出版社