图基本操作的编程实现湖北汽车工业学院数据结构

1、HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY数据结构实 验 报 告实验项目图基本操作的编程实现学生姓名学生学号完成日期2014年12月11日指导教师马老师，实验成绩评阅日期评阅教师实验六 图基本操作的编程实现【实验目的】图基本操作的编程实现要求：图基本操作的编程实现（2学时，验证型），阅读程序功能方面要求掌握图的建立、遍历、插入、删除等基本操作的编程实现，程序设计方面要求掌握图的遍历。存储结构可以在顺序结构、链接结构等中选择，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。【实验内容】一、在给出的程序代码基础上，首先排除遇到的语法问题，然后通

2、过填空完成遍历的任务，通过自己绘制的图形进行验证。本部分资料直接通过.cpp文件直接给出。请注意下载。为了保证在实验时间内完成，最好提前预习。涉及的主要问题包括：常用语句也出错了。基础部分的结点存储结构的一维数组设计需要自己写。图的数据结构定义部分。显示图的结构。主要遍历的功能设计。存储结构主要是邻接矩阵，最后可以通过提供参考答案来对比。邻接表的程序代码删除了更多的部分，且不提供参考答案，供有能力的学生自己研究。二、如果希望自行独立编程，可以实现对图进行存储（邻接矩阵或邻接表都可以，学生自由选择），之后可以询问任何两个结点之间是否有通路和路径数。以下的题目都可以作为独立编程的题目设计一个将图形

3、转成邻接链表的程序。设计一个深度优先搜索法来查找图形的程序。设计一个广度优先搜索法来查找一个图形的程序。鼓励开发出难度更高的程序。【思考问题】1. 图的定义和特性？2. 图的主要存储结构是什么？是独立的某种还是多种数据结构的综合？3. 图的主要遍历思路是哪些？4. 举出图的应用范例？【注意事项】1.开发语言：使用C+。2.可以自己增加其他功能。【实验分析、说明过程】 【大体介绍】深度遍历程序主要是利用了栈的先进后出的思想，回溯，递归的思想，而广度遍历主要是利用了队列的思想，先进先出。【深度遍历】【代码说明】1先从开始指定的结点进行访问，然后标记位它为一，（代表他已经被访问过）2然后取他的第一个

4、邻接点。3然后进入循环，循环条件为邻接点不为空，如果这个邻接结点，没有被标记，则执行语句递归，再次执行该函数，然后再继续寻找该点的邻接结点，依次进行下去，最后直到递归返回到第一层，结束程序。【画图显示】 dateabcdefg 0 1 2 3 4 5 6ag 1b 7 2e 5cf 6d 4 3【广度遍历】【代码说明】1. 从某个结点开始，把这个结点入队，然后设置标志为1.2. 执行循环体里面的内容，条件为队列不为空，循环体，先将队列出队，然后查找这个点是否具有邻接点，如果有结点先判断这个邻接点是否时被标记过的，如果没被标记，就先访问这个结点，设置标志位为1，然后入队。3. 反复进行2步骤，直

5、到队列为空。【画图演示】abcdefgdate 0 1 2 3 4 5 6ag 1b 6 2e 7cf 3d 5 4【遍历显示】【代码说明】可以利用双层for循环，对关系矩阵进行遍历，如果没有关系，则输出，如果有关系，则输出一，关系矩阵的对角线输出0；【实验截图】【实验小结】 (总结本次实验的重难点及心得、体会、收获)总结：对于这次的实验，由于图的思想还是不能很好的理解，在编写程序的时候十分的蹩脚，在图的遍历的时候，主要有利用邻接矩阵为存储结构，但是对于它的遍历的思路还不是十分的清晰，有时还会混淆，在自己做完实验以后，又继续对代码进行研究，还有遍历的思路进行整理，一遍一遍的画图，对照着程序画图

6、，将它遍历的思想深深地理解，现可以利用图进行编写程序，也有了那些思想，现在编写那些程序觉得比以前好了不少，最起码思路有了一个很大的跃升，编写代码顺着思路及可以了，虽然还是有不少的漏洞。对于这节的图的思路对于以后的编程是有很大的帮助的，这节课主要是更多的倾向于算法的思想，邻接矩阵：对于N个点的图，需要N×N的矩阵表示点与点之间是否有边的存在。这种表示法的缺点是浪费空间，尤其是对于N×N的矩阵是稀疏矩阵，即边的数目远远小于N×N的时候，浪费了巨大的存储空间。邻接链表：对于任何一个node A，外挂一个邻接链表，如果存在 A->X这样的边，就将X链入链表。 这种表

7、示方法的优点是节省空间，缺点是所有链表都存在的缺点，地址空间的不连续造成缓存命中降低，性能有不如临界矩阵这样的数组。【程序部分代码】void graph:depthfirstsearch(const int startpoint,int visited,void visit(char item)/深度优先遍历/深度优先遍历实现代码int neighborpoint;visit(getvalue(startpoint);visitedstartpoint=1;neighborpoint=getfirstneighbor(startpoint);while(neighborpoint!=-1)if

8、(!visitedneighborpoint)depthfirstsearch(neighborpoint,visited,visit);neighborpoint=getnextneighbor(startpoint,neighborpoint);void graph:breadthfirstsearch(const int startpoint,int visited,void visit(char item)/广度优先遍历/广度优先遍历实现代码char getqueuehead,neighborpoint;SeqQueue queue;visit(getvalue(startpoint)

9、;visitedstartpoint=1;queue.enqueue(startpoint);while(!queue.isempty()getqueuehead=queue.dequeue();neighborpoint=getfirstneighbor(getqueuehead);while(neighborpoint!=-1)if(!visitedneighborpoint)visit(getvalue(neighborpoint);visitedneighborpoint=1;queue.enqueue(neighborpoint);neighborpoint=getnextneighbor(getqueuehead,neighborpoint);void graph:showgraph()/图的显示函数for(i=0;i<Vertices.ListSize();i+)/用邻接矩阵来模拟图的边的相关信息for(j=0;j<Vertices.ListSize();j+)if(ge