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

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

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

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

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

5、】4eCQCQCOCO5fco1co请输入选顶：a当前图的坐标和结点如下:0123abed.当前图的邻接矩阵如下：011oo10co11co6QOOO1CO0COQO0CO110Sf1个列d一序第历8从遍k定先OO此诛请按任意犍继綾请输入选顶：S当前图的坐标和结点如下:012345ahcaef当前图的邻接矩阵如下已011COcoc：o0co1co10cocococ：c-0c：o1c：c-CO01cc-11e1CQcoGQ熾難"开始遍历abcdf9请按任意键继续总结：对于这次的实验，由于图的思想还是不能很好的理解，在编写程序的时候十分的蹩脚，在图的遍历的时候，主要有利用邻接矩阵为存储结

6、构，但是对于它的遍历的思路还不是十分的清晰，有时还会混淆，在自己做完实验以后，又继续对代码进行研究，还有遍历的思路进行整理，一遍一遍的画图，对照着程序画图，将它遍历的思想深深地理解，现可以利用图进行编写程序，也有了那些思想，现在编写那些程序觉得比以前好了不少，最起码思路有了一个很大的跃升，编写代码顺着思路及可以了，虽然还是有不少的漏洞。对于这节的图的思路对于以后的编程是有很大的帮助的，这节课主要是更多的倾向于算法的思想，邻接矩阵：对于N个点的图，需要NXN的矩阵表示点与点之间是否有边的存在。这种表示法的缺点是浪费空间，尤其是对于NXN的矩阵是稀疏矩阵，即边的数目远远小于NXN的时候，浪费了巨大

7、的存储空间。邻接链表：对于任何一个nodeA，外挂一个邻接链表，如果存在A->X这样的边，就将X链入链表。这种表示方法的优点是节省空间，缺点是所有链表都存在的缺点，地址空间的不连续造成缓存命中降低，性能有不如临界矩阵这样的数组。【程序部分代码】voidgraph:depthfirstsearch(constintstartpoint,intvisited,voidvisit(charitem)/探度优先遍历/深度优先遍历实现代码intneighBorpoint;visit(getvalue(startpoint);visitedstartpoint=l;neighborpoint二get

8、firstneighbor(startpoint);while(neighborpoint!=-l)if(!visitedneighborpoint)depthfirstsearch(neighborpoint,visited,visit);neighborpoint二getnextneighbor(startpoint,neighborpoint);voidgraph:breadthfirstsearch(constintstartpoint,intvisited,voidvisit(charitem)/广度优先遍历/广度优先遍历实现代码chargetqueuehead,neighborpo

9、int;SeqQueuequeue;visit(getvalue(startpoint);visitedstartpoint=l;queue.enqueue(startpoint);while(!queue.isempty()getqueuehead二queue.dequeue();neighborpoint二getfirstneighbor(getqueuehead);while(neighborpoint!=l)if(!visitedneighborpoint)visit(getvalue(neighborpoint);visitedneighborpoint=l;queue.enqueue(neighborpoint);neighborpoint二getnextneighbor(getqueuehead,neighborpoint);voidgraph:showgraph()/图的显示函数for(i=0;i<Vertices.ListSize();i+)/用邻接矩阵来模拟图的边的相关