《数据结构课程设计》模版（学生）V2014

西安文理学院软件学院课程设计报告设计名称： 数据结构课程设计 设计题目： 图的遍历和生成树求解 学生学号： 专业班级： 学生姓名： 学生成绩： 指导教师（职称）： 高寅生（教授） 课题工作时间： 2014.6.16 至 2014.6.27 说明：1、报告中的任务书、进度表由指导教师在课程设计开始前填写并发给每个学生。2、学生成绩由指导教师根据学生的设计情况给出各项分值及总评成绩。3、所有学生必须参加课程设计的答辩环节，凡不参加答辩者，其成绩一律按不及格处理。答辩由指导教师实施。4、报告正文字数一般应不少于3000字，也可由指导教师根据本门综合设计的情况另行规定。5、平时表现成绩低于6分的学生，取消答辩资格，其本项综合设计成绩按不及格处理。软件学院课程设计任务书学生姓名 学号 专业班级 设计题目图的遍历和生成树求解问题的研究与实现内容概要：设计或开发环境：Visual C+6.0 技术：C+语言主要内容：1先任意创建一个图；2图的DFS,BFS的递归和非递归算法的实现最小生成树（两个算法）的实现，求连通分 量的实现要求用邻接矩阵、邻接表、十字链表多种结构存储实现。3对创建的图采用邻接矩阵、邻接表、十字链表等多种结构存储，并完成图的DFS和BFS操作。文献资料：1严蔚敏，吴伟民.数据结构（C语言版）.北京：清华大学出版社.20042Bruce Eckel .Thinking in C+（C+ 编程思想，刘宗田 等译）.机械工业出版社.20003钱能.C+程序设计教程第二版.北京：清华大学出版社.20054谭浩强. c语言程序设计.北京：清华大学出版社.20055李兰，刘天印.C+程序设计实验指导.北京：北京大学出版社.2006设计要求：1分析课程设计题目的要求；2写出详细设计说明；3编写程序代码，调试程序使其能正确运行； 4设计完成的软件要便于操作和使用，有整齐、美观的使用界面； 5设计完成后提交课程设计报告和源代码文件的电子文档工作期限：设计工作自2014年6月16日至2014年6月27日止。指导教师： 院长： 日 期：2014年6月16日软件学院课程设计进度安排表学生姓名： 学号： 专业： 班级： 起止日期内 容备注6月16日 6月 17日下任务书；收集、阅读、整理相关参考文献，并进行归纳和概括总结，完成项目/任务背景介绍部分文字内容。6月18日11月20日系统功能设计和模块设计、系统体系结构构建。6月21日6月24日各功能模块编码实现，系统各功能模块调试与维护。6月25日6月26日系统功能集成、系统调试与测试，按照模板要求撰写课程设计/项目设计报告。6月27日课程设计/项目设计分组答辩，提交课程设计/项目设计报告以及相关文档，进行成绩评定。指导教师签名： 2014年6月16日成绩评定表学生姓名： 学号： 专业： 班级： 类别合计分值各项分值评分标准实际得分合计得分平时表现1010按时参加设计指导，无违反纪律情况。完成情况3020按设计任务书的要求完成了全部任务，能完整演示其设计内容，符合要求。10能对其设计内容进行详细、完整的介绍，并能就指导教师提出的问题进行正确的回答。报告质量3510报告文字通顺，内容翔实，论述充分、完整，立论正确，结构严谨合理；报告字数符合相关要求，工整规范，整齐划一。5课题背景介绍清楚，综述分析充分。5设计方案合理、可行，论证严谨，逻辑性强，具有说服力。5符号统一；图表完备、符合规范要求。5能对整个设计过程进行全面的总结，得出有价值的结论或结果。5参考文献数量在2篇以上，格式符合要求，在正文中正确引用。答辩情况2510在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。15在规定时间内能准确、完整、流利地回答教师所提出的问题。总评成绩： 分 指导教师： （签字） 日期：2014 年6月 27 日摘 要摘要：图是一种较线形表和树更为复杂的数据结构。在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。此程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。关键词：图；存储；遍历；深度；广度 西安文理学院软件学院 课程设计报告目 录摘 要vi第一章 课题背景（或绪论、概述）11.1课题所设背景及要求11.1.1课题背景11.1.2目的和任务11.1.3课程设计要求11. 2 设计内容1第二章 设计简介及设计方案论述22.1 设计题目22.2设计要求22.3设计思路22.4设计方案2第三章 详细设计33.1 主模块设计33.2 目录主要源码73.2 数据结构设计7第四章 设计结果及分析84.1 编码和调试84.1.1 调试过程84.1.2 结果展示84.3 设计分析11总结12参考文献13附录主要程序代码14- 7 -第一章 课题背景（或绪论、概述）这一章应说明本设计课题的背景、目的、意义、应解决的主要问题及应达到的技术要求；本设计的基本理论依据和主要工作内容。1.1课题所设背景及要求1.1.1课题背景这一章设计课题是计算机科学与技术专业重要的实践性环节之一，是在学生学习完数据结构与C+面向对象程序设计课程后进行的一次全面的综合练习。1.1.2目的和任务 1.巩固和加深学生对数据结构和C+语言课程的基本知识的理解和掌握； 2.掌握数据结构或C语言编程和程序调试的基本技能； 3.利用数据结构与C+语言进行基本的软件设计； 4.掌握书写C+程序设计说明文档的能力；5.提高运用数据结构或C+语言解决实际问题的能力。1.1.3课程设计要求 1.分析课程设计题目的要求； 2.写出详细设计说明； 3.编写程序代码，调试程序使其能正确运行； 4.设计完成的程序软件要便于操作和使用，有整齐、美观的使用界面；5.设计完成后提交课程设计报告和源代码文件的电子文档。1. 2 设计内容1.先任意创建一个图；2.图的DFS,BFS的递归和非递归算法的实现最小生成树（两个算法）的实现，求连通分量的实现要求用邻接矩阵、邻接表、十字链表多种结构存储实现。3.对创建的图采用邻接矩阵、邻接表、十字链表等多种结构存储，并完成图的DFS和BFS操作。第二章 设计简介及设计方案论述2.1 设计题目图的遍历和生成树求解问题的研究与实现 2.2设计要求1. 问题描述（功能要求）： 编写图的遍历和生成树求解问题的研究与实现: (1)先任意创建一个图； (2)图的DFS,BFS的递归和非递归算法的实现最小生成树（两个算法）的实现,求连通分量的实现要求用邻接矩阵、邻接表、十字链表多种结构存储实现。(3)对创建的图采用邻接矩阵、邻接表、十字链表等多种结构存储,并完成图的DFS和BFS操作。2.其他要求：只能利用数据结构知识，使用C/C+语言，源程序要有适当的注释，使程序容易阅读。2.3设计思路这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。2.4设计方案根据系统的功能要求，可以将问题解决分为以下步骤： 1.分析系统中的各个实体之间的关系及属性和行为； 2.根据问题描述，设计系统的类层次；3.完成类层次中各类的描述（包括属性和行为）；4.完成类中各个成员函数的定义；5.完成系统总结报告以及系统使用说明书；6.功能测试；7.完善系统总结报告以及系统使用说明书。 第三章 详细设计3.1 主模块设计3.1.1 开始创建图G用邻接表存储图If y=yNY显示图的邻接矩阵KRUSCAL算法显示图的邻接表深度优先遍历广度优先遍历最小生成树PRIM输入字母If y=y结束NY图的连通分量输入一个数20134563.1.1主要流程图如上图3.1.2显示图的邻接矩阵信息模块输入0显示图矩阵 返回主模块 输入字母返回主模块进入相应模块任意键返回主模块执行“0.显示邻接矩阵”操作时，调用typedef struct ArcCell时，将调用构造函数定义并创建邻接矩阵，对输入的信息用while循环语句实现图的读出并同时进行对信息进行输入（由定义数组实现）int creatMGraph_L(MGraph_L &G)创建图用邻接矩阵3.1.3显示图的邻接表信息模块输入1显示邻接表 返回主模块 输入字母返回主模块 进入相应模块任意键返回主模块 执行“1.显示邻接表”操作时，调用typedef struct arcnode时，将调用构造函数定义并创建邻接表，创建typedef struct vnode函数邻接链表顶点头接点。定义int creatadj(algraph &gra,MGraph_L G)用邻接表存储图。对输入的信息用for循环语句及if条件实现表的读出并同时进行对信息进行输入（由定义数组实现）3.1.4深度优先遍历信息模块 输入2 深度优先 返回主模块 输入字母返回主模块 进入相应模块任意键返回主模块执行“2.深度优先遍历”操作时，void adjprint(algraph gra)定义相应函数。假设初始状态的图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v相连的顶点都被访问过。若此图中尚有顶点未被访问过，则另选图中一个未曾被访问的顶点作为新的起点，重复以上步骤，直至图中所有顶点都被访问到为止。3.1.5广度优先遍历信息模块输入3 广度优先 返回主模块 输入字母返回主模块 进入相应模块任意键返回主模块执行“3.广度优先遍历”操作时，void bfstra(algraph gra)定义相应函数。设图的初态是所有顶点均未访问过。在该图中任选一个顶点v为源点，则广度优先遍历定义为：首先访问出发点v，接着依次访问v的所有邻接点w1,w2,.,wn,然后再依次访问与w1,w2,.,wn邻接的所有未曾访问过的顶点。以此类推，直至图中所有和源点v有路径相通的顶点都已被访问到为止。3.1.6最小生成树信息模块输入4 生成树 返回主模块 输入字母返回主模块 进入相应模块任意键返回主模块执行“4最小生成树的实现”操作时，定义int prim(int gmax,int n) 最小生成树PRIM算法，构造 int lowcostmax,prevexmax;函数存储当前集合U分别到剩余结点的最短路径。lowcosti=g1i;初始化prevexi=1;顶点未加入到最小生成树中lowcost1=0;标志顶点1加入U集合 用for循环形成n-1条边的生成树寻找满足边的一个顶点在U,另一个顶点在V的最小边 。3.1.7图的连通分量信息模块输入6 连通分量 返回主模块 输入字母返回主模块 进入相应模块任意键返回主模块 执行“6.图的连通分量”操作时，调用int bfstra_fen(algraph gra)函数求连通分量，定义数组，运用for循环实现图的连通分量。3.1.8出模块 退出时，释放内存。然后 return(0)退出程序。3.2 目录主要源码 1目录主要源码void main() algraph gra; MGraph_L G; int i,d,g2020; char a=a; d=creatMGraph_L(G); creatadj(gra,G); vnode v; coutendl#注意：若该图为非强连通图(含有多个连通分量)时endl 最小生成树不存在,则显示为非法值。endlendl; cout菜单endlendl; cout0、显示该图的邻接矩阵endl; cout1、显示该图的邻接表endl; cout2、深度优先遍历endl; cout3、广度优先遍历endl; cout4、最小生成树PRIM算法endl; cout5、最小生成树KRUSCAL算法endl; cout6、该图的连通分量endlendl;2.源码解释menu()函数完成打印菜单和接收用户选择功能。3.2 数据结构设计typedef struct ArcCellint adj; char *info;ArcCell,AdjMatrix2020;typedef struct char vexs20; AdjMatrix arcs; int vexnum,arcnum; MGraph_L; 源码解释:对结构体使用直接处理。 第四章 设计结果及分析4.1 编码和调试在设计该程序第我采用了结构化程序方法编制，并在源代码的基础上添加了中文注释，但是在该系统的编写过程中仍然有很多错误，主要是：注释文字的排版，定义错误，句式的语法错误。在完善程序时，我将源代码逐一排查，反复的琢磨和研究，力图在上机运行时少一些低级错误，如：“：”等。在仔细检查之后，将源代码上机调试进行编译，在编译和连接过程中发现错误，屏幕上显示出错信息，根据提示找到出错的位置，并加以改正直到显示出我预期的效果。4.1.1 调试过程1.首先，在本次调试过程中我遇见了在上机前根本没有想到的错误：在注释时，注释文字应写在一起中间不能有中断，不能再其中包含语言的语句，否则会产生错误，例如格式不正确或是多了字符等。2.缺少变量定义或是定义的位置不正确由于该程序比较长，前后的变量容易混淆，但是在错误信息的提示下也不是很容易找到。需要注意的是在定义时候有些函数使用同样的变量名却表示不同的作用，因此使用过程中要非常的小心，在定义及定义的位置也需要特别的留意。为减少这些不必要的麻烦，采用不同的变量名来表示，从而解决了变量名混淆问题。3.句式的语法错误大多的语法错误在相关的参考书下可以修改解决。主要是平时看书不仔细，不注意细节而产生的。如：没有注意具体数据使用是有一定的范围限定：过分的注重分号的重要性而在for，if，while语句中添加多余；在使用文件的时候忘记将文件先打开，对打开的方式与使用的情况不是很注意而造成匹配问题；还有漏掉形参的定义使值不能传递等等。这些语法错误有信息的提示是可以排除的。其实，编译，链接的成功并不意味着该程序的成功。逻辑上的错误，机器不容易检查出来，这时候就需要编译人员相当的耐心和细心对数据结果进行分析去把问题找出来。其间，可以采用“分段检查”的方法，在程序的不同位置设置几个cout函数语句，输出有关的变量值，铸段往下检查，或用debug进行测试，对检查出的错误进行修改，当调试完毕后记得将设置的cout都删除。若在程序中找不到问题，则进行另一方面程序的检查与修改。如此循环，直到最后程序的运行成功。在本次的程序编译过程中，我就是遇见修改许多次后编译能通过，能够运行程序时才想起要去查看数据文件中的数据记录。有时候数据记录却显示不出来，开始怀疑什么地方把变量的定义或使用错误。此时才在每个主要函数的操作过程中添加cout语句去检查是否有问题。如果有错误，就说明该函数编写有错误。以此类推，不断缩小检查错误的范围，直到把错误找出来，并进行修改。因此，再找到错误时就及时改正，使得程序功能显示正常。以上就是调试的过程。4.1.2 结果展示步骤一： 根据提示输入相应的字符，从而实现无向图的创建，如图所示： 图41创建无向图G步骤二：根据数字提示从06选择要操作的功能，如图42所示： 图42程序主菜单步骤三： 键入相应数字回车，会出现“是否继续？”，现在就可以直接选择对应的信息，如图43所示： 图43选择菜单步骤四：键入相应的数字回车，会出现“是否继续？”，就可以直接实现所需要的功能的信息，如图44所示： 图44选择菜单及结束 4.3 设计分析 通过对此次课程设计的了解与实践，让我深有感触。就设计方面来说，页面并不美观，所要求图的创建各种结构存储并不完整，图的DFS,BFS的递归和非递归算法的实现最小生成树（两个算法）的实现，求连通分量的实现要求用邻接矩阵、邻接表、十字链表多种结构存储实现。在程序中通过对函数与指针和数组的调用，实现相应的功能。 总结参考文献1 严蔚敏，吴伟民.数据结构（C语言版）.北京：清华大学出版社.2004.102 Bruce Eckel .Thinking in C+（C+ 编程思想，刘宗田 等译）.机械工业出版社.2000.093 钱能.C+程序设计教程第二版.北京：清华大学出版社.2005.054 谭浩强. c语言程序设计.北京：清华大学出版社.2005.065 李兰，刘天印.C+程序设计实验指导.北京：北京大学出版社.2006.11附录主要程序代码#include #include using namespace std; #define int_max 10000#define inf 9999 #define max 20/邻接矩阵定义typedef struct ArcCell int adj; char *info;ArcCell,AdjMatrix2020;typedef struct 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 &G)/创建图用邻接矩阵表示char v1,v2; int i,j,w; cout创建无向图endl请输入图G顶点和弧的个数:(4 6)不包括“()”G.vexnumG.arcnum; for(i=0;i!=G.vexnum;+i) cout输入顶点iG.vexsi; for(i=0;i!=G.vexnum;+i) for(j=0;j!=G.vexnum;+j) G.arcsij.adj=int_max; G.=NULL; for(int k=0;k!=G.arcnum;+k) cout输入一条边依附的顶点和权:(a b 3)不包括“()”v1v2w;/输入一条边依附的两点及权值 i=localvex(G,v1);/确定顶点V1和V2在图中的位置 j=localvex(G,v2); G.arcsij.adj=w; G.arcsji.adj=w; cout图G邻接矩阵创建成功！endl; return G.vexnum;void ljjzprint(MGraph_L G) int i,j; for(i=0;i!=G.vexnum;+i) for(j=0;j!=G.vexnum;+j) coutG.arcsij.adj ; coutadjvex=j; gra.verticesi.firstarc=arc; arc-nextarc=NULL; p=arc; +j; while(G.arcsij.adj!=int_max&j!=G.vexnum) tem=(arcnode *)malloc(sizeof(arcnode); tem-adjvex=j; gra.verticesi.firstarc=tem; tem-nextarc=arc; arc=tem; +j; -j; else if(G.arcsij.adj!=int_max&j!=G.vexnum) arc=(arcnode *)malloc(sizeof(arcnode); arc-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; couti ; p=gra.verticesi.firstarc; while(p!=NULL) coutadjvex; p=p-nextarc; coutendl; cout图G邻接表创建成功！endl; return 1; void adjprint(algraph gra) int i; for(i=0;i!=gra.vexnum;+i) arcnode *p; couti ; p=gra.verticesi.firstarc; while(p!=NULL) coutadjvex; p=p-nextarc; coutadjvex; int nextadjvex(algraph gra,vnode v,int w)/返回依附顶点V的相对于W的下一个顶点 arcnode *p; p=v.firstarc; while(p!=NULL&p-adjvex!=w) p=p-nextarc; if(p-adjvex=w&p-nextarc!=NULL) p=p-nextarc; return p-adjvex; if(p-adjvex=w&p-nextarc=NULL) return -10; int initqueue(linkqueue &q)/初始化队列 q.rear=(queueptr)malloc(sizeof(qnode); q.front=q.rear; if(!q.front) return 0; q.front-next=NULL; return 1; int enqueue(linkqueue &q,int e)/入队 queueptr p; p=(queueptr)malloc(sizeof(qnode); if(!p) return 0; p-data=e; p-next=NULL; q.rear-next=p; q.rear=p; return 1; int dequeue(linkqueue &q,int &e)/出队 queueptr p; 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; initqueue(q); for(i=0;i!=gra.vexnum;+i) if(!visitedi) visitedi=1; coutgra.verticesi.data; enqueue(q,i); while(!queueempty(q) dequeue(q,e); / cout e=0;we=nextadjvex(gra,gra.verticese,we) if(!visitedwe) visitedwe=1; coutgra.verticeswe.data; enqueue(q,we); int dfs(algraph gra,int i);/声明DFS深度优先int dfstra(algraph gra) int i,j; for(i=0;i!=gra.vexnum;+i) visitedi=0; for(j=0;j!=gra.vexnum;+j) if(visitedj=0) dfs(gra,j); return 0; int dfs(algraph gra,int i) visitedi=1; int we1;/ coutivisitediendl; coutgra.verticesi.data;/ cout=0;we=nextadjvex(gra,gra.verticesi,we) / coutwevisitedweendl; we1=we; / coutnextadjvex(gra,gra.verticesi,we)endl; if(visitedwe=0) / cout dfs(gra,we);/endl; / coutiwe1endl; we=we1; / coutnextadjvex(gra,gra.verticesi,we)endl; return 12; int bfstra_fen(algraph gra)/求连通分量 int i,j; for(i=0;i!=gra.vexnum;+i) visitedi=0; for(j=0;j!=gra.vexnum;+j) if(visitedj=0) dfs(gra,j); coutendl; return 0; typedef struct int adjvex; int lowcost; closedge;/*int minimum(closedge *p);int minispantree(MGraph_L G,char u) int k,j,i; closedge closedge_a20; k=localvex(G,u);/ coutkendl; for(j=0;j!=G.vexnum;+j) if(j!=k) closedge_aj.adjvex=u; closedge_aj.lowcost=G.arcskj.adj; for(i=1;i!=G.vexnum;+i) k=minimum(closedge_a); coutk; coutclosedge_ak.adjvex G.vexskendl; closedge_ak.lowcost=0; for(j=0;j!=G.vexnum;+j) if(G.arcskj.adjp-lowcost) s=p-lowcost; return s; int prim(int gmax,int n) /最小生成树PRIM算法 int lowcostmax,prevexmax; /LOWCOST存储当前集合U分别到剩余结点的最短路径 /prevex存储最短路径在U中的结点 int i,j,k,min; for(i=2;i=n;i+) /n个顶点，n-1条边 lowcosti=g1i; /初始化 prevexi=1; /顶点未加入到最小生成树中 lowcost1=0; /标志顶点1加入U集合 for(i=2;i=n;i+) /形成n-1条边的生成树 min=inf; k=0; for(j=2;j=n;j+) /寻找满足边的一个顶点在U,另一个顶点在V的最小边 if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d)%dt,prevexk-1,k-1,min); lowcostk=0; /顶点k加入U for(j=2;j=n;j+) /修改由顶点k到其他顶点边的权值 if(gkj0) 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) e