数据结构-实验3-图形结构及应用

《数据结构-实验3-图形结构及应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、WORD格式整理哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构与算法课程类型：必修实验项目名称：图形结构及其应用实验题目：图型结构的建立与遍历设计成绩报告成绩指导老师学习参考资料分享WORD格式整理目录：目录：2一、实验目的3二、实验要求及实验环境31.实验内容：32.实验要求：33.实验环境3三、设计思想41．逻辑设计4(1)邻接矩阵4(2)邻接表4(3)队列5(4)队列堆栈52．物理设计6(1)数据读入6(2)广度优先搜索9(3)深度优先搜索——递归实现12(4)深度优先搜索——非递归实现14四、测试结果17初始化与图的读入17展示邻接表读入结果

2、17展示邻接矩阵读入结果18初始提示18提示输入指令：18非法输入19广度优先搜索19深度优先搜索：二层选择19-递归深度优先搜索20-非递归深度优先搜索20展示：二层选择20-展示邻接表读入结果（同前）20-展示邻接矩阵读入结果（同前）20退出及退出确认21五、系统不足与经验体会21六、附录：21源代码：main.cpp21输入21输出21学习参考资料分享WORD格式整理一、实验目的通过实现图形结构，掌握逻辑结构、储存结构及其应用。二、实验要求及实验环境1.实验内容：树型结构的建立与遍历：图的遍历（搜索）算法是图型结构算法的基础，本实验要求编写程序演示图的存储结

3、构的建立和遍历（搜索）过程。2.实验要求：(1)能够建立（有向和无向）图的邻接矩阵和邻接表存储结构(2)能够在邻接矩阵和邻接表存储结构上对（有向和无向）图进行深度优先（递归和非递归都要求）和广度优先搜索(3)能够存储和显示相应的搜索结果（深度优先或广度优先生成森林（或生成树）、深度优先或广度优先序列和编号）(4)以文件形式输入图的顶点和边，并显示相应的结果。要求顶点不少于10个，边不少于13个(5)软件功能结构安排合理，界面友好，便于使用3.实验环境MicrosoftWindows7,Code：：Blocks10.05学习参考资料分享WORD格式整理三、设计思想1

4、．逻辑设计(1)邻接矩阵一个

5、V

6、×

7、V

8、的二维数组AM，满足：AM[i][j]=1，是有向图的边0，不是有向图的边(2)邻接表数据成员：0NextRead1NextRead2NextRead……NumbNextNumbNextRead：阅读标记，表明一个单元是否已读Next：指针。从邻接表中的单元作为头节点，借助指针各自建立链表，每个链表内头节点以外的节点即头节点的可达节点Numb：节点的序号基本操作：插入边：对图中的新有向边，令i,节点对应链表插入一个j广度优先搜索深度优先搜索（递归）深度优先搜索（非递归）学习参考资料分享WORD

9、格式整理(3)队列数据数据数据数据…………头结点数据成员：头结点：指向队首，以方便操作。基本操作：入队：将一个元素插入队首出队：从队尾取出一个元素(4)队列堆栈头结点数据数据数据…………数据数据数据数据…………数据数据数据数据…………数据数据数据数据…………头结点头结点…………数据成员：头结点：每个头结点指向一个队列，只有堆栈顶层的头节点对应的队列才能进行出队、入队操作。基本操作：入栈：头结点压入堆栈出栈：弹出头节点，对头节点对应队列进行操作学习参考资料分享WORD格式整理2．物理设计(1)数据读入有向图以边序列的形式从文件输入，共有17个顶点，30条边：I.邻接

10、表单元：邻接表的基本单位。每个单位包含结点序号和下一单元的指针。邻接表：包含一个单元数组和布尔数组。单元数组中，每个单元代表单元序号对应的结点；每个单元都是一个链表的表头；这一链表储存的是头结点可到达的结点。布尔数组中，每个元素代表其序号对应的结点，用于记录每个结点是否已被读取。操作——增加边：对新的有向边，将b插入邻接表中a作为头结点的链表。学习参考资料分享WORD格式整理II.邻接矩阵由于只是一个二维数组，因此其内容可在程序内直接调用、修改。需要进行初始化。III.读入函数为了方便，本程序同时将图读入邻接矩阵和邻接表。学习参考资料分享WORD格式整理

11、学习参考资料分享WORD格式整理(2)广度优先搜索I.邻接表上的广度优先搜索由于广度优先搜索要多次发起搜索，所以采用主从函数形式：Master：对布尔数组和搜索顺序数组进行初始化，并调用Servant进行广度优先搜索。对每个未被从函数访问的结点，调用从函数，以其为根结点进行广度优先搜索。把广度优先搜索结果输出到文件。学习参考资料分享WORD格式整理Servant：以输入结点为根结点，进行广度优先搜索。将输入结点标记为已读，同时建立队列。建立队列，以根据根结点为最初元素，每次出队一个元素，把这一结点可达而又未读过的结点添加到队列中，如此循环，直到队列清空。学习参考资

12、料分享WO