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

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

ID:8498604

大小:325.00 KB

页数:17页

时间:2018-03-29

数据结构课程设计图的建立与输出)_第1页
数据结构课程设计图的建立与输出)_第2页
数据结构课程设计图的建立与输出)_第3页
数据结构课程设计图的建立与输出)_第4页
数据结构课程设计图的建立与输出)_第5页
资源描述:

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

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

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

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

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

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

6、clude#includeusingnamespacestd;#defineMAX_VERTEX_NUM20#defineMAX1000#defineDG1#defineDN2#defineUDG3#defineUDN4//typedefenum{DG,DN,UDG,UDN}GraphKind;typedefcharVertexType;typedefintVRType;typedefcharInfoType;structClose{VertexTypedata;//顶点元素VRTypelowcost;intj;-17-数据结构课

7、程设计}closedge[MAX_VERTEX_NUM];//prime算法秋最小生成树的辅助数组typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针intadj;//对于无权图为0或1;对于带权图为权值InfoType*info;//该弧相关信息的指针}ArcNode,AdjMartrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//为简便起见邻接矩阵的元素类型,此时部分元素无用typedefstructVNode{intoutdegr

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

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

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