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

这是最后提交的文档资料格式，必须包含几个部分，如果是四到五个人完成要求文档不少于 70 页，3-4 个人完成要求不少于 50 页。数据结构课程设计题 目 图的存储与遍历 学生姓名 指导教师 学 院 专业班级 完成时间 1目 录（要求自动生成）第一章 课程设计目的 2第二章 课程设计内容和要求 2第三章 课程设计分析 3第四章 算法描述 4第五章 源代码 8第六章 运行结果分析 13第七章 结束语 15第八章 参考文献 152第一章 课程设计目的本学期我们对数据结构这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求实习者掌握数据结构中的各方面知识，还要求实习者具备一定的 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 ）指3示下一条边或弧的结点；数据域（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 定义邻接表的边结点类型以及邻接表类型4struct edgenodeint adjvex; /该弧所指向的顶点的位置edgenode * next; /指向下条条弧的指针; /定义邻接表的边结点类型typedef edgenode * * adjlist; /定义邻接表类型4.1.2 初始化图的邻接表需建立一个邻接表初始化函数对图的邻接表进行初始化。即建立一个所有边结点都为空的邻接表。void InitGAdjoin(adjlist&GL,int n)/初始化图的邻接表GL=new edgenode*n;for(int i=1;inext)cout|"adjvex;coutadjvex; /j 为 Vi 的一个邻接点的序号if(!visitedj)dfsAdjoin(GL,visited,j,n);p=p->next; /使 p 指向 Vi 单链表的下一个边结点4.2.2 广度优先遍历图的邻接表图的广度优先遍历是从初始点出发，访问初始点，再访问初始点的邻接点。当初始点的所有邻接点都被访问过时，再依次访问各邻接点的邻接点。如此循环下去。算法的实现必须依靠辅助队列，结点被访问后，对其进行标记，并将结点入队列。所以要实现算法必须先建立一个元素类型为整形的空队列，并定义队首与队尾指针，同时也要定义一个标志数组 bool*& visited 以标记结点是否被访问。6同样，也是从初始点 Vi 出发开始访问，访问初始点，标志其已被访问，并将已访问过的初始点序号 i 入队。当队列非空时进行循环处理，删除队首元素，第一次执行时 k 的值为 i，即 front=(front+1)%MaxLength。然后取 Vk 邻接表的表头指针 int k=qfront; edgenode* p=GLk。当边结点指针 p 不为空时，通过while（）循环，并以 p 是否为空为控制条件，依次搜索 Vk 的每一个结点。若Vj 没有被访问过则进行处理。访问完后，将 p 指向 p->next。其中的 while 循环部分的代码如下：while(p!=NULL)/依次搜索 Vk 的每一个结点int j=p->adjvex; /Vj 为 Vk 的一个邻接点if(!visitedj) /若 Vj 没有被访问过则进行处理coutnext;这样就可以访问所有结点，完成图的广度优先遍历。第五章 源代码（源代码必须给注释，代码由谁写的请在相应的代码后写明组成员名称）程序 图的存储与遍历头文件 图.h#ifndef GRAPH_H#define GRAPH_H#define MAX_VRTEX_NUM 20struct edgenodeint adjvex;edgenode * next; /定义邻接表的边结点类型（由张三写的）typedef edgenode *adjlist; /定义邻接表类型void InitGAdjoin(adjlist &GL,int n); 7/初始化图的邻接表void CreateAdjoin(adjlist &GL,int n,int m); /建立图的邻接表void dfsAdjoin(adjlist GL,bool*&visited,int i,int n);/从初始点出发深度优先搜索由邻接表 GL 表示的图void bfsAdjoin(adjlist GL,bool*&visited,int i,int n);/从初始点出发广度优先搜索由邻接表 GL 表示的图#endif实现文件 图.cpp#include#include#include"图.h"void Check(int n,int& i,int& j);void InitGAdjoin(adjlist&GL,int n)/初始化图的邻接表GL=new edgenode*n;for(int i=1;i>e;if(m=0)/建立无向图for(k=0;k>i>>j;Check(n,i,j);edgenode*p=new edgenode;8p->adjvex=j;p->next=GLi;GLi=p;/向序号为 i 的单链表的表头插入一个边结点p=new edgenode;p->adjvex=i;p->next=GLj;GLj=p;/向序号为 j 的单链表的表头插入一个边结点coutnext)cout|"adjvex;cout>i>>j;Check(n,i,j);/向序号为 i 的表头插入一个边结点edgenode