《数据结构课程设计-图的遍历和生成树求解问题的研究与实现》由会员分享，可在线阅读，更多相关《数据结构课程设计-图的遍历和生成树求解问题的研究与实现（25页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计设计说明书图的遍历和生成树求解问题的研究与实现学生姓名学号班级信管 061成绩指导教师计算机科学与技术系计算机科学与技术系20082008 年年 3 3 月月 8 8 日日数据结构 课程设计评阅书题目图的遍历和生成树求解问题的研究与实现学生姓名秦洁学号0621024014指导教师评语及成绩指导教师签名：年 月 日答辩评语及成绩答辩教师签名：年 月 日教研室意见总成绩：室主任签名：年 月 日课程设计任务书20072008 学年第一学期学年第一学期专业： 信息管理与信息系统 学号： 0621024014 姓名： 秦洁 课程设计名称： 数据结构课程设计 设计题目： 图的遍历和生成树求
2、解问题的研究与实现 完成期限：自 2008 年 2 月 25 日至 2008 年 3 月 7 日共 2 周设计依据、要求及主要内容（可另加附页）：设计依据：数据结构算法设计 要求：先任意创建一个图； 图的 DFS,BFS 的递归和非递归算法的实现最小生成树（两个算法）的实现，求连通分量的实现要 求用邻接矩阵、邻接表、十字链表多种结构存储实现。主要内容：对创建的图采用邻接矩阵、邻接表、十字链表等多种结构存储，并完成图的 DFS 和BFS 操作。指导教师（签字）： 教研室主任（签字）： 批准日期： 年 月 日 摘摘 要要 图是一种较线形表和树更为复杂的数据结构。在图形结构中，节点之间的关系可以是任
3、意的， 图中任意两个数据元素之间都可能相关。本程序是采用邻接矩阵、邻接表、十字链表等多种结构存 储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结 构。对图的遍历分别采用了广度优先遍历和深度优先遍历。关键词：关键词： 图；存储；遍历；深度；广度目目 录录 1 课题描述1 2 设计过程22.1 设计思路2 2.2 设计流程图3 2.3 程序源代码4 3 编译运行 17 总结 19 参考文献 201 1 课题描述课题描述 图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个 元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素
4、之间有着明显的层次关系，并且 每一层上的数据元素可能和下一层中多个元素（即其孩子节点）相关，但只能和上一层中一个元素 （即其双亲节点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素 之间都可能相关。因此，图的应用极为广泛，特别是近年来的迅速发展，已深入到诸如语言学、逻 辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。本程序是采用邻接矩阵、邻接 表、十字链表等多种结构存储来实现对图的存储。对图的遍历分别采用了广度优先遍历和深度优先 遍历。开发工具：Visual C+6.02 2设计过程本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。对图的
5、遍历分 别采用了广度优先遍历和深度优先遍历。2.12.1 设计思路设计思路 这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成 了这个程序。 因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系， 每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的， 图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种 结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式 存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。2.22.2 设计流
6、程图设计流程图开始创建图 G用邻接表存储图If y=yNY显示图的邻接矩阵KRUSCAL 算法显示图的邻接表深度优先遍历广度优先遍历最小生成树PRIM输入字母If y=y结束NY图的连通分量输入一个数20134562.32.3 程序源代码程序源代码#include #include using namespace std; #define int_max 10000#define inf 9999 #define max 20/邻接矩阵定义typedef struct ArcCellint adj;char *info;ArcCell,AdjMatrix2020;typedef struct
7、char vexs20;AdjMatrix arcs;int vexnum,arcnum; /有向图的当前顶点数和弧数MGraph_L;/int localvex(MGraph_L G,char v)/返回 V 的位置int i=0;while(G.vexsi!=v) +i;return i;int creatMGraph_L(MGraph_L int i,j,w;coutG.vexnumG.arcnum;for(i=0;i!=G.vexnum;+i)coutG.vexsi;for(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j) G.arcsij.adj=
8、int_max;G.arcsij.info=NULL;for(int k=0;k!=G.arcnum;+k) coutv1v2w;/输入一条边依附的两点及权值i=localvex(G,v1);/确定顶点 V1 和 V2 在图中的位置j=localvex(G,v2);G.arcsij.adj=w;G.arcsji.adj=w;coutadjvex=j;gra.verticesi.firstarc=arc;arc-nextarc=NULL;p=arc;+j;while(G.arcsij.adj!=int_maxtem-adjvex=j; gra.verticesi.firstarc=tem;tem
9、-nextarc=arc;arc=tem;+j;-j;else if(G.arcsij.adj!=int_maxarc-adjvex=j;p-nextarc=arc;arc-nextarc=NULL;p=arc; gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;/*for(i=0;i!=gra.vexnum;+i) arcnode *p;coutadjvex;p=p-nextarc;coutadjvex;p=p-nextarc;coutadjvex;int nextadjvex(algraph gra,vnode v,int w)/返回依附顶点 V 的相对于 W
10、 的下一个顶点 arcnode *p;p=v.firstarc;while(p!=NULLif(p-adjvex=wreturn p-adjvex;if(p-adjvex=w int initqueue(linkqueue q.front=q.rear;if(!q.front)return 0;q.front-next=NULL;return 1;int enqueue(linkqueue p=(queueptr)malloc(sizeof(qnode);if(!p)return 0;p-data=e;p-next=NULL;q.rear-next=p;q.rear=p;return 1;in
11、t dequeue(linkqueue if(q.front=q.rear)return 0;p=q.front-next;e=p-data;q.front-next=p-next;if(q.rear=p)q.rear=q.front;free(p);return 1;int queueempty(linkqueue q)/判断队为空 if(q.front=q.rear)return 1;return 0;void bfstra(algraph gra)/广度优先遍历 int i,e;linkqueue q;for(i=0;i!=gra.vexnum;+i)visitedi=0;initque
12、ue(q);for(i=0;i!=gra.vexnum;+i)if(!visitedi) visitedi=1;cout=0;we=nextadjvex(gra,gra.verticese,we) if(!visitedwe)visitedwe=1;cout=0;we=nextadjvex(gra,gra.verticesi,we)/ coutp-lowcost)s=p-lowcost;return s;*/int prim(int gmax,int n) /最小生成树 PRIM 算法 int lowcostmax,prevexmax; /LOWCOST存储当前集合 U 分别到剩余结点的最短路
13、径/prevex存储最短路径在 U 中的结点int i,j,k,min; for(i=2;i0)f=acrvisitedf;return f;void kruscal_arc(MGraph_L G,algraph gra) edg edgs20;int i,j,k=0;for(i=0;i!=G.vexnum;+i)for(j=i;j!=G.vexnum;+j)if(G.arcsij.adj!=10000)edgsk.pre=i;edgsk.bak=j;edgsk.weight=G.arcsij.adj;+k;int x,y,m,n;int buf,edf;for(i=0;i!=gra.arcnum;+i)acrvisitedi=0; for(j=0;j!=G.arcnum;+j)m=10000;for(i=0;i!=G.arcnum;+i)if(edgsi.weights;switch(s)case 0:couty;if(y=n)break; 3 3 编译运行编译运行图 3.1 创建无向图 G图 3.2 程序主菜单图 3.3 选择菜单图 3.1 选择菜单及结束总总 结结课程设计的过程是艰辛的，但是收获却是很大的。这次课程设计我主要是应用以前学习的数据结构与面向对象程序设计知识，综合起来才完成了这个程序，虽然程序很小，但是付出却是艰辛的。首先，综合课程设计让我把以
