西安文理学院软件学院课程设计报告设计名称:数据结构课程设计设计题目:对给定的图结构和起点,深度优先搜索学生学号:1402120324专业班级:12级软工3班学生姓名:孙晓发学生成绩:指导教师(职称):任强(讲师)课题工作时间:2014.6.16 至2014.6.27说明:1、报告中的任务书、进度表由指导教师在课程设计开始前填写并发给每个学生。
2、学生成绩由指导教师根据学生的设计情况给出各项分值及总评成绩。
3、所有学生必须参加课程设计的答辩环节,凡不参加答辩者,其成绩一律按不及格处理。
答辩由指导教师实施。
4、报告正文字数一般应不少于3000字,也可由指导教师根据本门综合设计的情况另行规定。
5、平时表现成绩低于6分的学生,取消答辩资格,其本项综合设计成绩按不及格处理。
软件学院课程设计任务书[1]程杰.指导教师:院长:日期:2014年6月16日软件学院课程设计进度安排表学生姓名:孙晓发学号:1402120324 专业:软件工程班级:12级3班指导教师签名:2014年6月16日成绩评定表学生姓名:孙晓发学号:1402120324 专业:软件工程班级:12级3班摘要摘要:深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。
本次程序目的在于实现对于给定图结构和起点,产生其所有深度优先遍历序列。
本程序将采用图的邻接矩阵的存储方法,用C语言实现遍历的全过程。
关键词:C语言;图的遍历;邻接矩阵存储;深度优先遍历目录摘要 (VI)第一章课题背景 (1)1.1 背景 (1)1.2 目的 (1)第二章设计简介及设计方案论述 (2)2.1设计思路及方案 (2)第三章详细设计 (3)3.1创建邻接矩阵 (3)3.1.1利用二维数组来创建邻接矩阵 (3)3.2创建图 (4)3.3深度优先遍历 (4)第四章设计结果及分析 (5)4.1结果 (5)4.2分析 (5)总结 (8)参考文献 (9)附录(代码) (10)第一章课题背景1.1 背景图是一种比树更为复杂的非线性结构。
在树状结构中,结点间具有分层次关系每一层上的结点只能和上一层中的至多一个结点相关,但是可能和下一层的多个结点相关。
而在图中,任意两个结点之间可能相关,既结点之间的邻接关系可以是任意的。
因此,常用图状结构来描述各种复杂的数据对象,在自然科学、社会科学和人文科学等许多领域有着非常广泛的应用。
深度优先搜索是一种在开发爬虫早期使用较多的方法。
它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。
在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行深度优先搜索,即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。
深度优先搜索沿着HTML文件上的超链走到不能再深入为止,然后返回到某一个HTML文件,再继续选择该HTML 文件中的其他超链。
当不再有其他超链可选择时,说明搜索已经结束。
1.2 目的涉及到数据结构遍会涉及到对应存储方法的遍历问题。
本次程序采用邻接矩阵的存储方法,并且以深度优先实现遍历的过程得到其遍历序列。
深度优先遍历图的方法是,从图中某顶点v出发:(1)访问顶点v;(2)依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;(3)若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。
第二章 设计简介及设计方案论述2.1设计思路及方案设计流程如图:图2-1 设计流程利用二维矩阵创建邻接矩阵,同时还需要一个一维数组来存储顶点信息。
之后利用创建的邻接矩阵来创建图,最后用深度优先的方法来实现遍历。
图 2-2 原始图 1.从0开始,首先找到0的关联顶点32.由3出发,找到1;由1出发,没有关联的顶点。
3.回到3,从3出发,找到2;由2出发,没有关联的顶点。
4.回到4,出4出发,找到1,因为1已经被访问过了,所以不访问。
所以最后顺序是0,3,1,2,4第三章详细设计3.1创建邻接矩阵3.1.1利用二维数组来创建邻接矩阵:int main(void){//动态创建存放边的二维数组int(*edge)[VERTEXNUM]=(int(*)[VERTEXNUM])malloc(sizeof(int)*VERTEXNUM*VERTEXNUM);int i,j;for(i=0;i<VERTEXNUM;i++){for(j=0;j<VERTEXNUM;j++){edge[i][j] = 0;}}邻接矩阵还需要一个一维数组来存储各个顶点的信息,以便于在后面遍历的过程中判断该顶点是否已遍历过:int* vertexStatusArr = (int*)malloc(sizeof(int)*VERTEXNUM); for(i=0;i<VERTEXNUM;i++){vertexStatusArr[i] = 0;}printf("after init:\n");displayGraph(edge);创建图:createGraph(edge,0,3);createGraph(edge,0,4);createGraph(edge,3,1);createGraph(edge,3,2);createGraph(edge,4,1);printf("after create:\n");displayGraph(edge);深度优先遍历声明:DFT(edge,vertexStatusArr);free(edge);return 0;}3.2创建图因为创建的图必须与一维数组的标志相符合,因此此函数已在前面声明并确定,在这里试对于二维数组正确性的判断,以方便在前面的应用:void createGraph(int (*edge)[VERTEXNUM], int start, int end){edge[start][end] = 1;}打印存储的图void displayGraph(int (*edge)[VERTEXNUM]){int i,j;for(i=0;i<VERTEXNUM;i++){for(j=0;j<VERTEXNUM;j++){printf("%d ",edge[i][j]);}printf("\n");}}3.3深度优先遍历void DFT(int (*edge)[VERTEXNUM], int* vertexStatusArr){printf("start BFT graph:\n");int i;for(i=0;i<VERTEXNUM;i++){DFTcore(edge,i,vertexStatusArr);}printf("\n");}深度遍历并判断顶点是否被遍历过,对于未访问的邻接递归调用DFTcore:void DFTcore(int (*edge)[VERTEXNUM],int i,int* vertexStatusArr){if(vertexStatusArr[i] == 1){return;}printf("%d ",i);vertexStatusArr[i] = 1;int j;for(j=0;j<VERTEXNUM;j++){if(edge[i][j] == 1){DFTcore(edge, j, vertexStatusArr);}}}第四章设计结果及分析4.1结果结果如图所示:图4-1 运行结果4.2分析此程序的图如下:图4-2 原始图遍历从0开始,第一步到3图4-3 第一次遍历与3相连的有1和2,在此先遍历1图4-4 第二次遍历而与1相关的没有,则返回到3,与3相连的有1和2,1遍历过,所以遍历2图4-5 第三次遍历2没有与之相关的顶点返回3,3的所有相关都遍历过,返回0,只剩下4图4-6 第四次遍历与4相关的1已遍历过,返回0,0的所有相关都已遍历,则深度优先遍历结束。
遍历顺序:0 3 1 2 4总结本次课程设计是对上课内容的实践,由于大部分内容教材或上课都有讲过或提到,所以程序内容大多才用课本上的方法。
个别部分如有向图的定义部分教材上的程序逻辑复杂所以采用《大话数据结构》上的代码。
东挪西挪算是凑到了代码主体部分,后面则统一变量使代码成为一个完整的整体。
过程烦是烦了点,但是还是完成了设计及运行,经过本次设计对于课本内容的理解又得到一次加深,但是也暴漏出一些问题。
比如,代码是照抄的,不是很理解,所以在后面运行出错时变的束手无策,但是通过请教舍友及再次认真翻阅课本和资料,最终完成设计。
看来在学习的过程中态度是第一位的,认真并善于在恰当的时机请教他人,能提高自己的学习效率和更快的解决问题。
所以态度很重要!参考文献[1]程杰.大话数据结构[M].北京:清华大学出版社,2011[2]韩利凯、李军.数据结构[M].浙江:浙江大学出版社,2013[3]谢若阳.数据结构[M].北京:清华大学出版社,2010[4]黄国瑜、叶乃菁.数据结构[M].北京:清华大学出版社,2009附录(代码)#include <stdio.h>#include <malloc.h>#define VERTEXNUM 5void createGraph(int (*edge)[VERTEXNUM], int start, int end);void displayGraph(int (*edge)[VERTEXNUM]);void DFT(int (*edge)[VERTEXNUM],int* vertexStatusArr);void DFTcore(int (*edge)[VERTEXNUM],int i,int* vertexStatusArr);int main(void){//动态创建存放边的二维数组int (*edge)[VERTEXNUM] = (int (*)[VERTEXNUM])malloc(sizeof(int)*VERTEXNUM*VERTEXNUM);int i,j;for(i=0;i<VERTEXNUM;i++){for(j=0;j<VERTEXNUM;j++){edge[i][j] = 0;}}//存放顶点的遍历状态,0:未遍历,1:已遍历int* vertexStatusArr = (int*)malloc(sizeof(int)*VERTEXNUM); for(i=0;i<VERTEXNUM;i++){vertexStatusArr[i] = 0;}printf("after init:\n");displayGraph(edge);//创建图createGraph(edge,0,3);createGraph(edge,0,4);createGraph(edge,3,1);createGraph(edge,3,2);createGraph(edge,4,1);printf("after create:\n");displayGraph(edge);//深度优先遍历DFT(edge,vertexStatusArr);free(edge);return 0;}//创建图void createGraph(int (*edge)[VERTEXNUM], int start, int end){edge[start][end] = 1;}//打印存储的图void displayGraph(int (*edge)[VERTEXNUM]){int i,j;for(i=0;i<VERTEXNUM;i++){for(j=0;j<VERTEXNUM;j++){printf("%d ",edge[i][j]);}printf("\n");}}//深度优先遍历void DFT(int (*edge)[VERTEXNUM], int* vertexStatusArr){printf("start BFT graph:\n");int i;for(i=0;i<VERTEXNUM;i++){DFTcore(edge,i,vertexStatusArr);}printf("\n");}void DFTcore(int (*edge)[VERTEXNUM],int i,int* vertexStatusArr){ if(vertexStatusArr[i] == 1){return;}printf("%d ",i);vertexStatusArr[i] = 1;int j;for(j=0;j<VERTEXNUM;j++){if(edge[i][j] == 1){DFTcore(edge, j, vertexStatusArr);}}}PS代码来自于网络,非原创。