下载文档原格式
1.引言数据结构是计算机科学与技术专业的一门核心专业基础课程，是一门理论性强、思维抽象、难度较大的课程。
在软件工程专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。
通过本门课程的学习，我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力。
我认为学习数据结构的最终目的是为了获得求解问题的能力。
对于现实世界中的问题，我们应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。
图是一种非常重要的数据结构，在《数据结构》中也占着相当大的比重。
这个学期的数据结构课程中，我们学习了很多图的存储结构，有邻接矩阵、邻接表、十字链表等。
其中邻接矩阵和邻接表为图的主要存储结构。
图的邻接矩阵存储结构的主要特点是把图的边信息存储在一个矩阵中，是一种静态存储方法。
图的邻接表存储结构是一种顺序存储与链式存储相结合的存储方法。
从空间性能上说，图越稀疏邻接表的空间效率相应的越高。
从时间性能上来说，邻接表在图的算法中时间代价较邻接矩阵要低。
本课程设计主要是实现使用邻接表存储结构存储一个图，并在所存储的图中实现深度优先和广度优先遍历以及其链表结构的输出。
2.需求分析2.1 原理当图比较稀疏时，邻接表存储是最佳的选择。
并且在存储图的时候邻接表要比邻接矩阵节省时间。
在图存储在系统中后，我们有时还需要对图进行一些操作，如需要添加一个顶点，修改一个顶点，或者删除一个顶点，而这些操作都需要一图的深度优先及广度优先遍历为基础。
本系统将构建一个图，图的结点存储的是int型数据。
运行本系统可对该图进行链式结构输出、深度优先及广度优先遍历。
控制方法如下：表2-1 控制键的功能2.2 要求（1）建立基于邻接表的图；（2）对图进行遍历；（3）输出遍历结果；2.3 运行环境(1)WINDOWS 7系统(2)C++ 编译环境2.4 开发工具C++语言3.数据结构分析本课程设计是针对于图的，程序中采用邻接表进行数据存储。
图的遍历及其应用实现一、实验目的1．熟悉图常用的存储结构。
2．掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。
3．会用图的遍历解决简单的实际问题。
二、实验内容从键盘上输入图的顶点和边的信息,建立图的邻接表存储结构,然后以深度优先搜索和广度优先搜索遍历该图,并输出起对应的遍历序列. 试设计程序实现上述图的类型定义和基本操作,完成上述功能。
该程序包括图类型以及每一种操作的具体的函数定义和主函数。
12534三、实验步骤㈠、数据结构与核心算法的设计描述自己定义的数据类型#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码，如OK 等*/typedef int Boolean;//Boolean 是布尔类型,其值是TRUE 或FALSE */#define MAX_NAME 3 /* 顶点字符串的最大长度+1 */typedef char VertexType[MAX_NAME]; /* 字符串类型*/#define ElemType inttypedef struct Qnode{ ElemType data; //数据域Qnode *next; //指针域}Qnode ,*Queueptr;typedef struct{Queueptr front; //头指针Queueptr rear; //尾指针}LinkQueue;在广度遍历中需要需要用到队列,下面就是对队列的基本应用v oid InitQueue(LinkQueue & Q)//初始化队列void EnQueue(LinkQueue & Q,ElemType x)//插入值为X的结点到队列中ElemType DeQueue (LinkQueue & Q,int &x)int QueueEmpty(LinkQueue & Q)int LocateVex(ALGraph G,VertexType u){ /* 初始条件: 图G 存在,u 和G 中顶点有相同特征*//* 操作结果: 若G 中存在顶点u,则返回该顶点在图中位置;否则返回-1 */}Status CreateGraph(ALGraph &G){ /* 采用邻接表存储结构,构造没有相关信息的图G}void DestroyGraph(ALGraph &G){ /* 初始条件: 图G 存在。
5.3图的遍历的演示班级：信管08-2 姓名：陈明学号：0801051401一．需求分析1.在连通的无向图中，实现访问全部节点的操作。
2.演示程序以用户和计算机的对话形式进行。
既在计算机上显示提示信息。
3.程序执行的命令包括：创建无向图显示邻接表，图的广度遍历，图的深度遍历等二．概要设计图的定义类型：ADT Graph{数据对象V：若干顶点组成的集合数据关系R：R={VR}VR＝{<v,w>| v,w∈V 且<v,w>表示从v 到w 有一条弧，可代表v认识w 或v到w有路等)}基本操作：CreatGraph(&G, V, VR);// 按定义(V, VR) 构造图GDestroyGraph(&G); // 销毁图GInsertVex(&G, v); //在图G中增添新顶点v。
DeleteVex(&G, v);// 删除G中顶点v及其相关的弧InsertArc(&G, v, w); //在G中增添弧<v,w>，若G是无向的，则还增添对称弧<w,v>DeleteArc(&G, v, w); //在G中删除弧<v,w>，若G是无向的，则还删除对称弧<w,v>}三．详细设计1.邻接表的定义：typedef struct ArcNode{int adjvex;struct ArcNode *nextarc;}ArcNode;typedef struct VNode{int num;ArcNode *firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedef struct ALGraph{AdjList vertices;int vexnum,arcnum;}ALGraph;2.图的深度优先遍历void dfs(ALGraph &G,int v){//深度优先遍历ArcNode *p;visited[v]=1;printf("%4d",G.vertices[v].num);p=G.vertices[v].firstarc;while(p!=NULL){if(visited[p->adjvex]==0) dfs(G,p->adjvex);//递归p=p->nextarc;}}3．图的广度优先遍历void bfs(ALGraph &G,int vi){//从第vi个开始广度优先遍历int v,i,front,rear;ArcNode *p;front=0;rear=1;for(i=1;i<=MAX_VERTEX_NUM;i++) visited[i]=0;visited[vi]=1;printf("%4d",G.vertices[vi].num);queue[rear]=vi; //queue相当于队列queuewhile(front!=rear){//顶点没有全部遍历front=front+1;v=queue[front];p=G.vertices[v].firstarc;while(p!=NULL){if(visited[p->adjvex]==0){visited[p->adjvex]=1;printf("%4d",p->adjvex);rear=rear+1;queue[rear]=p->adjvex;}p=p->nextarc;}}}2.主程序及创建程序的代码void main(){ALGraph G;int n,i,j,s,d,c;ArcNode *p,*q;printf(" 图的遍历\n");printf("-----------------------------------------------------------\n");for(i=1;i<=MAX_VERTEX_NUM;i++) visited[i]=0;printf("请输入图的顶点个数：");scanf("%d",&G.vexnum);printf("请输入图的顶点边数：");scanf("%d",&G.arcnum);// printf("\n");for(i=1;i<=G.vexnum;i++){G.vertices[i].num=i;G.vertices[i].firstarc=NULL;}for(j=1;j<=G.arcnum;j++){printf("第%d条边=〉端点序号:",j);scanf("%d",&s);printf("第%d条边=〉邻接点序号:",j);scanf("%d",&d);p=(ArcNode*)malloc(sizeof(ArcNode));q=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=d;q->adjvex=s;p->nextarc =G.vertices[s].firstarc;G.vertices[s].firstarc=p;q->nextarc=G.vertices[d].firstarc;G.vertices[d].firstarc=q;}printf("构成的邻接表为如下形式");for(i=1;i<=G.vexnum;i++){printf("\n%8d",G.vertices[i].num);p=G.vertices[i].firstarc;while(p){printf("%4d",p->adjvex);p=p->nextarc;}}n=1;while(n){printf(" \n 图的遍历\n");printf("--------------------------------------------------------------\n");printf("深度优先搜索(1) 广度优先搜索(2) 运行结束(3)\n");scanf("%d",&c);switch(c){case 1:printf("深度优先搜索序列:");dfs(G,1);break;case 2:printf("广度优先搜索序列:");bfs(G,1);break;case 3:n=0;break;default:n=0;}}}四．调试分析1．本程序较为直观的显示了测试者想要创建的图。
目录一、课题的主要功能 (2)1.1设计内容 (2)1.2对课程设计功能的需求分析 (2)二、课题的功能模块的划分 (2)2.1模块划分 (2)2.2系统的概要设计 (3)三、主要功能的实现 (4)3.1算法思想 (4)1.图的邻接矩阵的建立 (4)2.图的遍历的实现 (4)3.2数据结构 (4)3.3主函数流程图 (5)3.4深度优先遍历流程图 (6)3.5深度优先遍历递归 (7)3.6深度优先遍历流程图 (9)3.7广度优先遍历递归流程图 (10)四、程序调试 (11)4.1程序的调试分析 (11)4.2程序的测试结果 (11)五、总结 (15)六、附件 (16)6.1源程序一、课题的主要功能1.1设计内容演示图的深度优先, 广度优先遍历过程，并输出原图结构及遍历结果。
要求图的结点数不能少于6个。
可以由系统随机生成图，也可以由用户手动输入图。
报告中要写出画图的思路；画出图的结构，有兴趣的同学可以进一步改进图的效果。
1.2对课程设计功能的需求分析图的遍历并不需要是一个过于复杂的工作环境，一般来说：最合适的才是最好的。
软件设计必须符合我们使用实际情况的需要。
根据要求，图的遍历主要功能如下：1.用户可以随时建立一个有向图或无向图；2.用户可以根据自己的需要，对图进行深度遍历或广度遍历；3.用户可以根据自己的需要对图进行修改；4.在整个程序中,用户可以不断的按照不同的方式对图进行遍历,若不继续,用户也可以随时跳出程序,同时,如果用户输入的序号错误,程序会提示用户重新输入序号；二、课题的功能模块的划分2.1模块划分1.队列的初始化、进队、出队、队列空、队列满的函数void InitQueue(CirQueue *Q) //初始化队列int QueueEmpty(CirQueue *Q)//队列是否为空int QueueFull(CirQueue *Q)//队列满Void EnQueue(CirQueue *Q,int x)//将队员进队int DeQueue(CirQueue *Q)//将队员出队2.创建图的函数void CreateMGraph(MGraph *G)//根据用户需要创建一个图3.图的深度优先遍历递归void DFSM(MGraph *G,int i)/*含有输出已访问的顶点的语句*/4.图的广度优先遍历递归void BFSM(MGraph *G,int k) /*含有输出已访问的顶点的语句*/5.深度优先遍历void DFSTraverseM(MGraph *G)/*调用DFSM函数*/6.广度优先遍历void BFSTraverseM(MGraph *G) /*调用BFSM函数*/7.主函数main() /*包含一些调用和控制语句*/2.2系统的概要设计三、主要功能的实现3.1算法思想本课题所采用的是邻接矩阵的方式存储图，实现图的深度、广度两种遍历，并将每种遍历结果输出来。
2012级计算机科学与技术专业《数据结构》课程设计文档设计题目图的遍历班级12网路工程组长学号3121101124 姓名庄俊坤学号3121101135 姓名林捷学号3121101136 姓名周柏煌学号3121101160 姓名赵云鹏学号3111101119 姓名谢国印完成日期2014.1前言图遍历又称图的遍历，属于数据结构中的内容。
指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。
图的遍历操作和树的遍历操作功能相似。
图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。
一、设计题目图遍历的演示二、实验目的：本课程设计是《数据结构》课程的组成之一，也是它的继续和延伸。
采用集中学习方法，分组完成一个小型应用系统。
开设本课程的目的是使学生通过参加小型软件的开发过程，进一步了解并掌握数据结构与算法的设计方法，具备初步的分析和设计能力；同时培养学生的创新能力和创新意识，锻炼他们的团队协作精神。
三、问题描述：由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面：①在图结构中，没有一个“自然”的首结点，图中任意一个顶点都可作为第一个被访问的结点。
②在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。
③在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。
④在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。
四、功能要求（1）以邻接表作为存储结构；（2）由用户指定遍历的起点；（3）实现深度优先和广度优先遍历；（4）输出深度优先遍历和广度优先遍历的结点访问序列；（5）并给出相应生成树的边集。
（6）给出至少3组测试数据，其中图顶点的个数大于10小于30。
较高要求：建立深度和广度生成树，按凹入表或树形打印生成树。
