数据结构课程设计.docx

数据结构课程设计.docx

《数据结构课程设计.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计.docx（21页珍藏版）》请在冰点文库上搜索。

数据结构课程设计

西安文理学院软件学院

课程设计报告

设计名称：

数据结构课程设计

设计题目：

对给定的图结构和起点，深度优先搜索

学生学号：

1402120324

专业班级：

12级软工3班

学生姓名：

孙晓发

学生成绩：

指导教师（职称）：

任强（讲师）

课题工作时间：

2014.6.16至2014.6.27

说明：

1、报告中的任务书、进度表由指导教师在课程设计开始前填写并发给每个学生。

2、学生成绩由指导教师根据学生的设计情况给出各项分值及总评成绩。

3、所有学生必须参加课程设计的答辩环节，凡不参加答辩者，其成绩一律按不及格处理。

答辩由指导教师实施。

4、报告正文字数一般应不少于3000字，也可由指导教师根据本门综合设计的情况另行规定。

5、平时表现成绩低于6分的学生，取消答辩资格，其本项综合设计成绩按不及格处理。

软件学院课程设计任务书

学生姓名

孙晓发

学号

1402120324

专业班级

12级软工3班

设计题目

对给定的图结构和起点，深度优先搜索

内容概要：

开发环境为VC6++，图的邻接矩阵存储，给定图和起点的深度优先遍历

文献资料：

[1]程杰.大话数据结构[M].北京:

清华大学出版社2011

[2]韩利凯、李军.数据结构[M].浙江:

浙江大学出版社2013

设计要求：

设计程序完成如下功能：

对给定的图结构和起点，产生其所有的深度优先搜索便利序列。

工作期限：

设计工作自2014年6月16日至2014年6月27日止。

指导教师：

院长：

日期：

2014年6月16日

软件学院课程设计进度安排表

学生姓名：

孙晓发学号：

1402120324专业：

软件工程班级：

12级3班

起止日期

内容

备注

6月16日～6月17日

下任务书；收集、阅读、整理相关参考文献，并进行归纳和概括总结，完成项目/任务背景介绍部分文字内容。

6月18日～11月20日

系统功能设计和模块设计、系统体系结构构建。

6月21日～6月24日

各功能模块编码实现，系统各功能模块调试与维护。

6月25日～6月26日

系统功能集成、系统调试与测试，按照模板要求撰写课程设计/项目设计报告。

6月27日

课程设计/项目设计分组答辩，提交课程设计/项目设计报告以及相关文档，进行成绩评定。

指导教师签名：

2014年6月16日

成绩评定表

学生姓名：

孙晓发学号：

1402120324专业：

软件工程班级：

12级3班

类别

合计

分值

各项分值

评分标准

实际得分

合计得分

平时表现

10

10

按时参加设计指导，无违反纪律情况。

完成情况

30

20

按设计任务书的要求完成了全部任务，能完整演示其设计内容，符合要求。

10

能对其设计内容进行详细、完整的介绍，并能就指导教师提出的问题进行正确的回答。

报告质量

35

10

报告文字通顺，内容翔实，论述充分、完整，立论正确，结构严谨合理；报告字数符合相关要求，工整规范，整齐划一。

5

课题背景介绍清楚，综述分析充分。

5

设计方案合理、可行，论证严谨，逻辑性强，具有说服力。

5

符号统一；图表完备、符合规范要求。

5

能对整个设计过程进行全面的总结，得出有价值的结论或结果。

5

参考文献数量在2篇以上，格式符合要求，在正文中正确引用。

答辩情况

25

10

在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。

15

在规定时间内能准确、完整、流利地回答教师所提出的问题。

总评成绩：

分

指导教师（签名）：

日期：

2014年6月27日

摘要

摘要：

深度优先搜索属于图算法的一种，英文缩写为DFS即DepthFirstSearch.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

本次程序目的在于实现对于给定图结构和起点，产生其所有深度优先遍历序列。

本程序将采用图的邻接矩阵的存储方法，用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设计流程

利用二维矩阵创建邻接矩阵，同时还需要一个一维数组来存储顶点信息。

之后利用创建的邻接矩阵来创建图，最后用深度优先的方法来实现遍历。

深度优先遍历是连通图的一种遍历策略。

其基本思想如下：

设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边（x，y）。

若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边（x，y）到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。

上述过程直至从x出发的所有边都已检测过为止。

例如下图中（既本次设计用到的图）：

图2-2原始图

1.从0开始，首先找到0的关联顶点3

2.由3出发，找到1；由1出发，没有关联的顶点。

3.回到3，从3出发，找到2；由2出发，没有关联的顶点。

4.回到4，出4出发，找到1，因为1已经被访问过了，所以不访问。

所以最后顺序是0,3,1,2,4

第三章详细设计

3.1创建邻接矩阵

3.1.1利用二维数组来创建邻接矩阵：

intmain（void）{

//动态创建存放边的二维数组

int（*edge）[VERTEXNUM]=（int（*）[VERTEXNUM]）malloc（sizeof（int）*VERTEXNUM*VERTEXNUM）;

inti,j;

for（i=0;i

for（j=0;j

edge[i][j]=0;

}

}

邻接矩阵还需要一个一维数组来存储各个顶点的信息，以便于在后面遍历的过程中判断该顶点是否已遍历过：

int*vertexStatusArr=（int*）malloc（sizeof（int）*VERTEXNUM）;

for（i=0;i

vertexStatusArr[i]=0;

}

printf（"afterinit:

\n"）;

displayGraph（edge）;

创建图：

createGraph（edge,0,3）;

createGraph（edge,0,4）;

createGraph（edge,3,1）;

createGraph（edge,3,2）;

createGraph（edge,4,1）;

printf（"aftercreate:

\n"）;

displayGraph（edge）;

深度优先遍历声明：

DFT（edge,vertexStatusArr）;

free（edge）;

return0;

}

3.2创建图

因为创建的图必须与一维数组的标志相符合，因此此函数已在前面声明并确定，在这里试对于二维数组正确性的判断，以方便在前面的应用：

voidcreateGraph（int（*edge）[VERTEXNUM],intstart,intend）{

edge[start][end]=1;

}

打印存储的图

voiddisplayGraph（int（*edge）[VERTEXNUM]）{

inti,j;

for（i=0;i

for（j=0;j

printf（"%d",edge[i][j]）;

}

printf（"\n"）;

}

}

3.3深度优先遍历

voidDFT（int（*edge）[VERTEXNUM],int*vertexStatusArr）{

printf（"startBFTgraph:

\n"）;

inti;

for（i=0;i

DFTcore（edge,i,vertexStatusArr）;

}

printf（"\n"）;

}

深度遍历并判断顶点是否被遍历过，对于未访问的邻接递归调用DFTcore：

voidDFTcore（int（*edge）[VERTEXNUM],inti,int*vertexStatusArr）{

if（vertexStatusArr[i]==1）{

return;

}

printf（"%d",i）;

vertexStatusArr[i]=1;

intj;

for（j=0;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的所有相关都已遍历，则深度优先遍历结束。

遍历顺序：

03124

总结

本次课程设计是对上课内容的实践，由于大部分内容教材或上课都有讲过或提到，所以程序内容大多才用课本上的方法。

个别部分如有向图的定义部分教材上的程序逻辑复杂所以采用《大话数据结构》上的代码。

东挪西挪算是凑到了代码主体部分，后面则统一变量使代码成为一个完整的整体。

过程烦是烦了点，但是还是完成了设计及运行，经过本次设计对于课本内容的理解又得到一次加深，但是也暴漏出一些问题。

比如，代码是照抄的，不是很理解，所以在后面运行出错时变的束手无策，但是通过请教舍友及再次认真翻阅课本和资料，最终完成设计。

看来在学习的过程中态度是第一位的，认真并善于在恰当的时机请教他人，能提高自己的学习效率和更快的解决问题。

所以态度很重要！

参考文献

[1]程杰.大话数据结构[M].北京:

清华大学出版社，2011

[2]韩利凯、李军.数据结构[M].浙江:

浙江大学出版社，2013

[3]谢若阳.数据结构[M].北京：

清华大学出版社，2010

[4]黄国瑜、叶乃菁.数据结构[M].北京：

清华大学出版社，2009

附录（代码）

#include

#include

#defineVERTEXNUM5

voidcreateGraph（int（*edge）[VERTEXNUM],intstart,intend）;

voiddisplayGraph（int（*edge）[VERTEXNUM]）;

voidDFT（int（*edge）[VERTEXNUM],int*vertexStatusArr）;

voidDFTcore（int（*edge）[VERTEXNUM],inti,int*vertexStatusArr）;

intmain（void）{

//动态创建存放边的二维数组

int（*edge）[VERTEXNUM]=（int（*）[VERTEXNUM]）malloc（sizeof（int）*VERTEXNUM*VERTEXNUM）;

inti,j;

for（i=0;i

for（j=0;j

edge[i][j]=0;

}

}

//存放顶点的遍历状态，0：

未遍历，1：

已遍历

int*vertexStatusArr=（int*）malloc（sizeof（int）*VERTEXNUM）;

for（i=0;i

vertexStatusArr[i]=0;

}

printf（"afterinit:

\n"）;

displayGraph（edge）;

//创建图

createGraph（edge,0,3）;

createGraph（edge,0,4）;

createGraph（edge,3,1）;

createGraph（edge,3,2）;

createGraph（edge,4,1）;

printf（"aftercreate:

\n"）;

displayGraph（edge）;

//深度优先遍历

DFT（edge,vertexStatusArr）;

free（edge）;

return0;

}

//创建图

voidcreateGraph（int（*edge）[VERTEXNUM],intstart,intend）{

edge[start][end]=1;

}

//打印存储的图

voiddisplayGraph（int（*edge）[VERTEXNUM]）{

inti,j;

for（i=0;i

for（j=0;j

printf（"%d",edge[i][j]）;

}

printf（"\n"）;

}

}

//深度优先遍历

voidDFT（int（*edge）[VERTEXNUM],int*vertexStatusArr）{

printf（"startBFTgraph:

\n"）;

inti;

for（i=0;i

DFTcore（edge,i,vertexStatusArr）;

}

printf（"\n"）;

}

voidDFTcore（int（*edge）[VERTEXNUM],inti,int*vertexStatusArr）{

if（vertexStatusArr[i]==1）{

return;

}

printf（"%d",i）;

vertexStatusArr[i]=1;

intj;

for（j=0;j

if（edge[i][j]==1）{

DFTcore（edge,j,vertexStatusArr）;

}

}

}

PS代码来自于网络，非原创