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

ID:9400508

大小:98.50 KB

页数:15页

时间:2018-04-30

数据结构课程设计报告样本(图的存储与遍历)_第1页
数据结构课程设计报告样本(图的存储与遍历)_第2页
数据结构课程设计报告样本(图的存储与遍历)_第3页
数据结构课程设计报告样本(图的存储与遍历)_第4页
数据结构课程设计报告样本(图的存储与遍历)_第5页
资源描述:

《数据结构课程设计报告样本(图的存储与遍历)》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、这是最后提交的文档资料格式,必须包含几个部分,如果是四到五个人完成要求文档不少于70页,3-4个人完成要求不少于50页。《数据结构》课程设计题目图的存储与遍历学生姓名指导教师学院专业班级完成时间目录(要求自动生成)第一章课程设计目的2第二章课程设计内容和要求2第三章课程设计分析3第四章算法描述4第五章源代码8第六章运行结果分析13第七章结束语15第八章参考文献15第一章课程设计目的本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程,为了让大家更好地理解与运用所学知识,提高动手能力,我们进

2、行了此次课程设计实习。这次课程设计不但要求实习者掌握《数据结构》中的各方面知识,还要求实习者具备一定的C语言基础和编程能力。具体说来,这次课程设计主要有两大方面目的。一是让实习者通过实习掌握《数据结构》中的知识。对于《图的存储与遍历》这一课题来说,所要求掌握的数据结构知识主要有:图的邻接表存贮结构、队列的基本运算实现、邻接表的算法实现、图的广度优先搜索周游算法实现、图的深度优先搜索周游算法实现。二是通过实习巩固并提高实习者的C语言知识,并初步了解VisualC++的知识,提高其编程能力与专业水平。第二章课程设计内

3、容和要求2.1课程设计内容组成员名称和分工(谁负责了哪个部分)该课题要求以邻接表的方式存储图,输出邻接表,并要求实现图的深度、广度两种遍历。2.1.1图的邻接表的建立与输出对任意给定的图(顶点数和边数自定),并且对有向图与无向图都应进行讨论,根据邻接表的存储结构建立图的邻接表并输出之。尽量用图形化的方式输出邻接表。2.1.2图的遍历的实现图的遍历包括图的广度优先遍历与深度优先遍历。对于广度优先遍历应利用队列的五种基本运算(置空队列、进队、出队、取队头元素、判队空)来实现。首先建立一空队列,从初始点出发进行访问,当

4、被访问时入队,访问完出队。并以队列是否为空作为循环控制条件。对于深度优先遍历则采用递归或非递归算法来实现。2.2运行环境该程序的运行环境为Windowsxp系统,MicrosoftVisualC++6.0版本。第三章课程设计分析3.1图的存储本课题要求采取邻接表的存储结构。邻接表是一种链式的存储结构,在邻接表中,对图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边(对有向图是以顶点Vi为尾的弧)。每个结点由3个域组成,其中邻接点域(adjvex)指示与顶点Vi邻接的点在图中的位置,链域(nex

5、tarc)指示下一条边或弧的结点;数据域(info)存储和边或弧相关的信息,如权值等。所以一开始必须先定义邻接表的边结点类型以及邻接表类型,并对邻接表进行初始化,然后根据所输入的相关信息,包括图的顶点数、边数、是否为有向,以及各条边的起点与终点序号,建立图的邻接表。此时要分两种情况:有向图与无向图。对于无向图,一条边的两的个顶点,互为邻接点,所以在存储时,应向起点的单链表表头插入一边结点,即终点。同时将终点的单链表表头插入一边结点,即起点。对于有向图,只能向起点的单链表的表头插入一个边结点,即终点。但不能反过来。

6、至于邻接表的输出,由于不了解C++中的绘图操作,故采用for语句输出各结点,并配合一些符号完成邻接表的输出。3.2图的遍历3.2.1图的深度优先遍历假设初始状态是图中所有顶点未曾被访问,深度优先遍历可以从图的初始点出发,访问初始点,然后依次从v未被访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到;若此时仍有顶点未被访问到,则从另一个未被访问的顶点出发,重复上述过程,直至所有点都被访问到为止。这是一个递归的过程。所以在实现深度优先遍历的过程中必须递归调用深度优先搜索函数。而且在深度优先搜索

7、函数中必须设一标志数组以标记结点是否被访问。具体过程应为:先访问初始点Vi,并标志其已被访问。此时定义一指向边结点的指针p,并建立一个while()循环,以指针所指对象不为空为控制条件,当Vi的邻接点未被访问时,递归调用深度优先遍历函数访问之。然后将p指针指向下一个边结点。这样就可以完成图的深度优先遍历了。3.2.2图的广度优先遍历广度优先搜索遍历类似于树的按层次遍历的过程。假设从图中某顶点v出发,在访问了v之后访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点的邻接点”被访问,直到图中

8、所有已被访问的顶点的邻接点都被访问到。若此时图中尙有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直到图中所有顶点都被访问到为止。换句话说,广度优先搜索遍历图的过程是以v为起始点,由近及远,依次访问和v有路径相通且路径长度为1,2,……的顶点。所以要实现算法必须先建立一个元素类型为整形的空队列,并定义队首与队尾指针,同时也要定义一个标志数组以标记结点

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
正文描述:

《数据结构课程设计报告样本(图的存储与遍历)》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、这是最后提交的文档资料格式,必须包含几个部分,如果是四到五个人完成要求文档不少于70页,3-4个人完成要求不少于50页。《数据结构》课程设计题目图的存储与遍历学生姓名指导教师学院专业班级完成时间目录(要求自动生成)第一章课程设计目的2第二章课程设计内容和要求2第三章课程设计分析3第四章算法描述4第五章源代码8第六章运行结果分析13第七章结束语15第八章参考文献15第一章课程设计目的本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程,为了让大家更好地理解与运用所学知识,提高动手能力,我们进

2、行了此次课程设计实习。这次课程设计不但要求实习者掌握《数据结构》中的各方面知识,还要求实习者具备一定的C语言基础和编程能力。具体说来,这次课程设计主要有两大方面目的。一是让实习者通过实习掌握《数据结构》中的知识。对于《图的存储与遍历》这一课题来说,所要求掌握的数据结构知识主要有:图的邻接表存贮结构、队列的基本运算实现、邻接表的算法实现、图的广度优先搜索周游算法实现、图的深度优先搜索周游算法实现。二是通过实习巩固并提高实习者的C语言知识,并初步了解VisualC++的知识,提高其编程能力与专业水平。第二章课程设计内

3、容和要求2.1课程设计内容组成员名称和分工(谁负责了哪个部分)该课题要求以邻接表的方式存储图,输出邻接表,并要求实现图的深度、广度两种遍历。2.1.1图的邻接表的建立与输出对任意给定的图(顶点数和边数自定),并且对有向图与无向图都应进行讨论,根据邻接表的存储结构建立图的邻接表并输出之。尽量用图形化的方式输出邻接表。2.1.2图的遍历的实现图的遍历包括图的广度优先遍历与深度优先遍历。对于广度优先遍历应利用队列的五种基本运算(置空队列、进队、出队、取队头元素、判队空)来实现。首先建立一空队列,从初始点出发进行访问,当

4、被访问时入队,访问完出队。并以队列是否为空作为循环控制条件。对于深度优先遍历则采用递归或非递归算法来实现。2.2运行环境该程序的运行环境为Windowsxp系统,MicrosoftVisualC++6.0版本。第三章课程设计分析3.1图的存储本课题要求采取邻接表的存储结构。邻接表是一种链式的存储结构,在邻接表中,对图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边(对有向图是以顶点Vi为尾的弧)。每个结点由3个域组成,其中邻接点域(adjvex)指示与顶点Vi邻接的点在图中的位置,链域(nex

5、tarc)指示下一条边或弧的结点;数据域(info)存储和边或弧相关的信息,如权值等。所以一开始必须先定义邻接表的边结点类型以及邻接表类型,并对邻接表进行初始化,然后根据所输入的相关信息,包括图的顶点数、边数、是否为有向,以及各条边的起点与终点序号,建立图的邻接表。此时要分两种情况:有向图与无向图。对于无向图,一条边的两的个顶点,互为邻接点,所以在存储时,应向起点的单链表表头插入一边结点,即终点。同时将终点的单链表表头插入一边结点,即起点。对于有向图,只能向起点的单链表的表头插入一个边结点,即终点。但不能反过来。

6、至于邻接表的输出,由于不了解C++中的绘图操作,故采用for语句输出各结点,并配合一些符号完成邻接表的输出。3.2图的遍历3.2.1图的深度优先遍历假设初始状态是图中所有顶点未曾被访问,深度优先遍历可以从图的初始点出发,访问初始点,然后依次从v未被访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到;若此时仍有顶点未被访问到,则从另一个未被访问的顶点出发,重复上述过程,直至所有点都被访问到为止。这是一个递归的过程。所以在实现深度优先遍历的过程中必须递归调用深度优先搜索函数。而且在深度优先搜索

7、函数中必须设一标志数组以标记结点是否被访问。具体过程应为:先访问初始点Vi,并标志其已被访问。此时定义一指向边结点的指针p,并建立一个while()循环,以指针所指对象不为空为控制条件,当Vi的邻接点未被访问时,递归调用深度优先遍历函数访问之。然后将p指针指向下一个边结点。这样就可以完成图的深度优先遍历了。3.2.2图的广度优先遍历广度优先搜索遍历类似于树的按层次遍历的过程。假设从图中某顶点v出发,在访问了v之后访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点的邻接点”被访问,直到图中

8、所有已被访问的顶点的邻接点都被访问到。若此时图中尙有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直到图中所有顶点都被访问到为止。换句话说,广度优先搜索遍历图的过程是以v为起始点,由近及远,依次访问和v有路径相通且路径长度为1,2,……的顶点。所以要实现算法必须先建立一个元素类型为整形的空队列,并定义队首与队尾指针,同时也要定义一个标志数组以标记结点

显示全部收起
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。
关闭