![点击分享此内容可以赚币 分享](/master/images/share_but.png)
图的遍历实现优秀课程设计数据结构程序图.doc
《图的遍历实现优秀课程设计数据结构程序图.doc》由会员分享,可在线阅读,更多相关《图的遍历实现优秀课程设计数据结构程序图.doc(22页珍藏版)》请在咨信网上搜索。
数据结构课程设计 设计说明书 图遍历实现 学生姓名 英 茜 学 号 班 级 网络1101班 成 绩 指导老师 申 静 数学和计算机科学学院 1 月 4日 课程设计任务书 —第一学期 课程设计名称: 数据结构课程设计 课程设计题目: 图遍历实现 完 成 期 限: 自 12 月23日至 1 月 4 日共 2 周 设计内容: 1. 任务说明 (1) 采取邻接表存放结构创建一个图; (2) 编程实现图深度优先搜索(或广度优先搜索)遍历算法; (3) 输出遍历结果; (4) 给定具体数据调试程序。 2. 要求 1)问题分析和任务定义:依据设计题目标要求,充足地分析和了解问题,明确问题要求做什么? 2)逻辑设计:写出抽象数据类型定义,各个关键模块算法,并画出模块之间调用关系图; 3)具体设计:定义对应存放结构并写出各函数伪码算法。 4)程序编码:把具体设计结果深入求精为程序设计语言程序。 5)程序调试和测试:采取自底向上,分模块进行,即先调试低层函数。 6)结果分析:程序运行结果包含正确输入及其输出结果和含有错误输入及其输出结果。算法时间、空间复杂性分析; 7)编写课程设计汇报。 3. 参考资料 指导老师:申静 教研室责任人:余冬梅 课程设计评阅 评语: 指导老师署名: 年 月 日 摘 要 针对图问题中怎样愈加好地实现图遍历问题,以无向图为例,分别采取广度优先遍历和深度优先遍历算法实现对各节点遍历,以VC++为开发环境进行系统设计和实现,其运行结果表明,系统能很好地完成遍历后节点输出,实现了遍历目标,系统界面友好,可操作性强。 关键词:数据结构;存放结构;邻接矩阵 目 录 一 课题描述 1 二 设计目标和任务 2 2.1课程设计目标 2 2.2课程设计任务 2 三 设计方案和实施 3 3.1总体设计 3 3.2基础操作 3 3.3具体设计 4 四 运行调试结果 6 五 结论和致谢 9 六 附录 11 一 课题描述 数据结构是一门专业基础课,它对学习者要求很明确:学会分析、研究计算机加工数据结构特征,方便为应用设计所需数据选择合适逻辑结构、存放结构及其对应算法,并初步掌握算法时间分析和空间分析技术。其次,该课程学习过程也是复杂程序设计训练过程,要求学习者编写程序结构或设计程序结构体清楚、正确、易读,符合软件工程规范。 图是一个较为复杂且关键数据结构,其特殊性在于图形结构中结点之间关系能够是任意,图中任意两个数据元素之间全部有可能相关。就本课程设计而言应用图论知识讨论怎样在计算机上实现图遍历操作,关键处理图遍历多个方法实现。 本设计采取现在最通用程序设计语言之一—C语言作为数据结构和算法描述语言。 二 设计目标和任务 2.1课程设计目标 深入了解图遍历问题,图DFS,BFS递归和非递归算法实现, 用无向图来实现图遍历。 初步掌握软件开发过程问题分析、系统设计、程序编码、测试等基础方法和技能。 训练学生灵活应用所学数据结构基础知识,熟练完成问题分析、算法设计、编写程序,求解出指定问题。 训练用系统见解和软件开发通常规范进行软件开发,巩固、深化学生理论知识,提升编程水平,并在此过程中培养严谨科学态度和良好工作作风。 提升综合利用所学理论知识和方法独立分析和处理问题能力。 2.2课程设计任务 1)任务说明 用C/C++编写一个程序实现图遍历算法。 从键盘上输入一个图基础信息(图用邻矩阵表示)。图DFS,BFS递归和非递归算法实现;用有向图实现图遍历;用无向图实现图遍历;用邻接矩阵存放图;用邻接表存放图。 2)要求 1>首先输入图结点数; 2>依次输入图各条边(数据之间用空格隔开); 3>输出形式:按用户选择遍历方法给出遍历次序,各字符间用->分隔; 4>程序所能达成功效:能够按要求输出所要结果。 三 设计方案和实施 3.1总体设计 采取邻接矩阵作为图存放结构。程序中关键用到以下抽象数据类型: 抽象数据类型定义 typedef struct{ char *vexs; //顶点向量 int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵 int vexnum,arcnum; //图目前顶点数和弧数 }Graph; 3.2基础操作 CreateUDN(Graph &G) 操作结果:用邻接矩阵创建带权无向网图。 DFS(Graph G,int k) 操作结果:对已存在图进行深度优先遍历。 BFS(Graph G) 操作结果:对已存在图进行广度优先遍历。 choose(Graph G) 操作结果:对将要实现操作步骤进行选择。 程序包含两个模块 主程序模块,其中主函数为 int main{ 输入信息; 依据输入要求进行选择操作和输出; 输出结果; } 选择操作模块—实现具体选择对应操作及输出操作。 两模块之间关系以下图3.1所表示 图3.1 模块关系图 3.3具体设计 程序步骤图图3.2所表示 图3.2 程序步骤图 函数设计程序设计中关键包含下列函数用邻接矩阵创建一个图: void CreateUDN(Graph &G){ 用邻接矩阵创建一个带权无向网图; 输入顶点数和弧数; 输入各个顶点及各条弧; } 递归方法实现图遍历: void DFS(Graph G, int k) { 用递归方法访问图中结点; 对图进行深度优先遍历; } 非递归方法实现图遍历: void BFS(Graph G) { 用队列辅助访问图中结点; 对图进行广度优先遍历; } 选择输出需要遍历方法: void choose(Graph G) { 给出程序运行选项; 对对应输入选项调用对应函数以实施操作; } 四 运行调试结果 例:遍历以下无向图(图 4.1)(a,b,c,d,e分别表示V1 V2 V3 V4 V5五个顶点) 以图4.1为例 步骤一: 运行程序,按提醒首先输入顶点数和弧数。 图4.2输入顶点数和弧数 步骤二: 输入顶点和弧 (1) 输入顶点 图4.3 输入各顶点 (2)输入弧 图4.3 输入各条弧 步骤三: 选择便利方法和选择后结果 选择1操作显示广度优先编历结果 图4.4 广度优先结果 选2操作显示深度优先遍历 图4.4深度优先遍历结果 五 结论和致谢 在程序设计中我关键是处理是给出一个图怎样用多个方法完成图遍历问题,也包含怎样创建一个图,深度优先遍历和广度优先遍历一个图,递归和非递归方法实现图遍历。程序最终经过调试运行,初步实现了设计目标。 图是一个较为复杂且关键数据结构,其特殊性在于图形结构中结点之间关系能够是任意,图中任意两个数据元素之间全部有可能相关。用邻接矩阵作为图数据存放结构很好地处理了图结构难点, 借助于邻接矩阵轻易判定任意两个顶点之间是否有边(或弧)相连,并轻易求得各个顶点度。该程序通俗易懂且实用性强,而且该程序清单具体具体、全方面、含有很强可读性;系统整体上比较完美,能够从键盘获取输入元素,而且能够依据用户输入进行选择性地输出;整体输出画面效果整齐、大方。 这次课程设计也让我充足认识到《数据结构》这门课关键性。它给我们一个思想和纲领,让我们在编程时轻易找到思绪,不至于无章可循。同时它也有广泛实际应用。 最终,我还要尤其感谢我们教导老师申静老师,在她精心教导和帮助下,我设计才得以顺利完成。对她为我们设计所提出宝贵意见表示忠心感谢! 参考文件 [1]谭浩强. C程序设计[第三版]. 北京:清华大学出版社. [2]罗宇等. 数据结构[M ]. 北京邮电大学出版社. [3]严藯敏. 数据结构[C语言版]. 北京:清华大学出版社. [4]杨路明. C语言程序设计教程. 北京邮电大学出版社. [5]徐孝凯. 数据结构课程试验. 清华大学出版社. 六 附录 源程序代码 // 程序功效:采取递归和非递归算法,有向图和无向图,邻接矩阵和邻接表等多个结构存放实现图遍历。 // 程序作者:英茜 // 最终修改日期:-1-3 #include"stdio.h" #include"stdlib.h" #define INFINITY 32767 #define MAX_VEX 20 //最大顶点个数 #define QUEUE_SIZE (MAX_VEX+1) //队列长度 bool *visited; //访问标志数组 int z=1; //图邻接矩阵存放结构 typedef struct{ char *vexs; //顶点向量 int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵 int vexnum,arcnum; //图目前顶点数和弧数 }Graph; class Queue{ //队列类 public: void InitQueue(){ base=(int *)malloc(QUEUE_SIZE*sizeof(int)); front=rear=0; } void EnQueue(int e){ base[rear]=e; rear=(rear+1)%QUEUE_SIZE; } void DeQueue(int &e){ e=base[front]; front=(front+1)%QUEUE_SIZE; } int *base; int front; int rear; }; int Locate(Graph G,char c){ //图G中查找元素c位置 for(int i=0;i<G.vexnum;i++) if(G.vexs[i]==c) return i; return -1; } void CreateUDN(Graph &G){ //创建无向网 int i,j,w,s1,s2; char a,b,c,temp; printf("输入顶点数和弧数(顶点数和弧数之间以空格隔开) : "); scanf("%d%d",&G.vexnum,&G.arcnum); temp=getchar(); //接收回车 G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配顶点数目 printf("输入%d个顶点.\n",G.vexnum); for(i=0;i<G.vexnum;i++){ //初始化顶点 scanf("%c",&G.vexs[i]); temp=getchar(); //接收回车 } for(i=0;i<G.vexnum;i++) //初始化邻接矩阵 for(j=0;j<G.vexnum;j++) G.arcs[i][j]=INFINITY; printf("输入%d条弧.\n",G.arcnum); for(i=0;i<G.arcnum;i++){ //初始化弧 printf("输入弧%d: ",i); scanf("%c %c %d%c",&a,&b,&w,&c); //输入一条边依附顶点和权值 s1=Locate(G,a); s2=Locate(G,b); G.arcs[s1][s2]=G.arcs[s2][s1]=w; } } int FirstVex(Graph G,int k){ //图G中顶点k第一个邻接顶点 if(k>=0 && k<G.vexnum){ //k合理 for(int i=0;i<G.vexnum;i++) if(G.arcs[k][i]!=INFINITY) return i; } return -1; } //图G中顶点i第j个邻接顶点下一个邻接顶点 int NextVex(Graph G,int i,int j){ if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum){ //i,j合理 for(int k=j+1;k<G.vexnum;k++) if(G.arcs[i][k]!=INFINITY) return k; } return -1; } //深度优先遍历 void DFS(Graph G,int k){ int i; if(k==-1){ //第一次实施DFS时,k为-1 for(i=0;i<G.vexnum;i++) if(!visited[i]) DFS(G,i); //对还未访问顶点调用DFS } else{ visited[k]=true; if(z==1) printf("%c",G.vexs[k]); else printf(" -> %c",G.vexs[k]); ++z; //访问第k个顶点 if((z-1)%G.vexnum==0) z=1; for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i)) if(!visited[i]) DFS(G,i); //对k还未访问邻接顶点i递归调用DFS } } //广度优先遍历 void BFS(Graph G){ int k; Queue Q; //辅助队列Q Q.InitQueue(); for(int i=0;i<G.vexnum;i++) if(!visited[i]){ //i还未访问 visited[i]=true; printf("%c ",G.vexs[i]); Q.EnQueue(i); //i入列 while(Q.front!=Q.rear){ Q.DeQueue(k); //队头元素出列并置为k for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w)) if(!visited[w]){ //w为k还未访问邻接顶点 visited[w]=true; printf("-> %c ",G.vexs[w]); Q.EnQueue(w); } } } printf("\n 请继续选择:\n"); } void choose(Graph G){ //对输入选项调用对应函数实施操作 int i,m; visited=(bool *)malloc(G.vexnum*sizeof(bool)); scanf("%d",&m); switch(m){ case 1: printf("广度优先遍历: "); for(i=0;i<G.vexnum;i++) visited[i]=false; BFS(G); choose(G); printf("\n");break; case 2: printf("深度优先遍历: "); for(i=0;i<G.vexnum;i++) visited[i]=false; DFS(G,-1); printf("\n 请继续选择:\n");choose(G);break; case 3:printf("程序结束."); break; default : printf(" 输入错误!\n请在1-3中选择:\n"); choose(G); } } //主函数 void main(){ int i,m; Graph G; CreateUDN(G); printf("有以下选项供选择:\n"); printf("\n"); printf("|*| 1:广度优先遍历 2:深度优先遍历 3:退出本程序!|*|\n"); printf("\n"); printf("请选择(1--3):\n"); choose(G); }- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遍历 实现 优秀 课程设计 数据结构 程序
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【丰****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【丰****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。
关于本文