数据结构课程设计--图的建立与输出

《数据结构课程设计--图的建立与输出》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构课程设计数据结构课程设计设计题目：图的建立与输出系别：电子与信息工程学院专业：电子信息工程班级：2009级（1）班姓名：钟海刚学号：200907014134指导教师：余先伦2011年06月20日-16-数据结构课程设计目录一、设计题目（任选其一）…………………………………………3二、运行环境（软、硬件环境）……………………………………3三、算法设计的思想…………………………………………………3四、算法的流程图……………………………………………………3五、算法设计分析……………………………………………………4六、源代码……………………………

2、………………………………4七、运行结果分析……………………………………………………14八、收获及体会………………………………………………………16-16-数据结构课程设计一、设计题目（任选其一）图的建立及输出任务：建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。二、运行环境（软、硬件环境）硬件环境：CPU：1000MHz以上内存：256MB以上硬盘：60G以上软件环境：系统平台：Windows2000/WindowsXP/Window

3、sVista/Windows7运行环境：TC3.0/MicrosoftVisualC++6.0三、算法设计的思想1、存储结构；邻接矩阵邻接表2、遍历方式：深度优先搜索（DFS）广度优先搜索(BFS)也可以对邻接矩阵和临界表直接输出：其中DFS算法通过递归实现，BFS算法通过队列实现。3、拓扑排序和最小生成树（Prime算法），具体实现见代码。四、算法的流程图-16-数据结构课程设计五、算法设计分析首先是建图，图和网的区别在于图没有权值（这里以固定值1代替），网有权值，有向和无向在存储上的区别在于对于有向图，输入a[i][j],只存储a[i][j]

4、,而对于无向图还要存储a[j][i]。其次是功能的实现，邻接表遍历和邻接矩阵遍历都很简单，按照它的存储结构，依次输出每个顶点和它邻接的顶点，时间复杂度分别为O(n+e)和O(n2)；对于DFS算法是通过函数递归实现的,所采用的存储结构式是邻接表，找邻接点所需时间为O(e)，其中e为无向图的边数或有向图的弧数，时间复杂度为O(n+e)。对于BFS算法是用队列实现的，每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对每个顶点访问的顺序不同对于拓扑排序，

5、建立各项顶点的入度的时间复杂度为O(e)，建零入度顶点栈的时间复杂度为O(n)；在拓扑排序过程中，若有向图无环，则每个顶点进一次栈，出一次栈，入度减1的操作在while语句中总共执行e次，所以总的时间复杂度为O(n+e)。对于Prime算法的最小生成树，假设网中有n个顶点，则第一个进行初始化的循环语句的频度为n，第二个循环语句的频度为n-1。其二是重新选择具有最小代价的边，其频度为n。由此，Prime算法的时间复杂度为O(n2)，与网中的边数无关，因此适用于求边稠密的网的最小生成树。六、源代码#include#include

6、tring.h>#include#include#include#include#includeusingnamespacestd;#defineMAX_VERTEX_NUM20#defineMAX1000#defineDG1#defineDN2#defineUDG3#defineUDN4//typedefenum{DG,DN,UDG,UDN}GraphKind;typedefcharVertexType;typedefintVRType;typedefcha

7、rInfoType;structClose{VertexTypedata;//顶点元素VRTypelowcost;intj;-16-数据结构课程设计}closedge[MAX_VERTEX_NUM];//prime算法秋最小生成树的辅助数组typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针intadj;//对于无权图为0或1；对于带权图为权值InfoType*info;//该弧相关信息的指针}ArcNode,AdjMartrix[MAX_VER

8、TEX_NUM][MAX_VERTEX_NUM];//为简便起见邻接矩阵的元素类型，此时部分元素无用typedefstructVNode