图的遍历课程设计报告.doc

广东工业大学华立学院 课 程 设 计（论文）课程名称 数据结构 题目名称 图的遍历 学生学部（系） 专业班级 学 号 学生姓名 指导教师 二八 年 七 月 八 日广东工业大学华立学院课程设计（论文）任务书题目名称数据结构学生学部（系）专业班级姓 名学 号一、课程设计（论文）的内容图的遍历任务：实现图的深度优先, 广度优先遍历算法，并输出原图结构及遍历结果。二、课程设计（论文）的要求与数据（1）函数功能要划分好（2）总体设计应画流程图（3）程序要加必要的注释（4）要提供程序测试方案三、课程设计（论文）应完成的工作（1）按照课程设计要求完成报告，具体内容包括：具体任务；软件环境；算法设计思想及流程图；.源代码；调试分析及算法的改进设想；运行结果；总结；参考文献等。（2）课程设计报告可采用统一规范的格式单面打印，并装订成册上交。（3）以班级为单位刻一张光盘上交。四、课程设计（论文）进程安排序号设计（论文）各阶段内容地点起止日期1布置任务2-2032008.5.272软件设置、收集资料、确定题目2008.5.28-2008.6.223按要求进行设计2008.6.23-2008.7.64完成设计,验收上交2008.7.8五、应收集的资料及主要参考文献1数据结构使用C语言（第3版）朱战立 编，西安交通大学出版社。2四川中外科技文化交流中心 组编（王松 主编）.Visual C+ 6.0程序设计与开发指南.北京：高等教育出版社，20043朱晴婷，黄海鹰，陈莲君.Visual C+程序设计基础与实例分析.北京：清华大学出版社，2004发出任务书日期： 2008 年 5 月 27 日 指导教师签名：计划完成日期： 2008 年 7 月 8 日 教学单位责任人签章：目 录任务书1目 录41）.具体任务52）.软件环境53）.算法设计思想及流程图54）.源代码：65）.调试分析:116）.运行结果117）.参考文献118）.收获及体会12一、具体任务1. 实现图的深度优先，广度优先遍历算法，并输出原图结构及遍历结果。2.通过这次的程序设计，加深对图的遍历的认识，加强编程的能力。二、运行环境（软、硬件环境）硬件环境：CPU 2.0Hz 硬盘160G 内存1G 软件环境：Windows Xp Microsoft Visual C+ 6.0三、算法设计思想及流程图定义变量输入节点的个数创建图打印图 是输出图的遍历if(menu=b) 否 if(menu=d)是 否实现深度递归遍历if(menu=d) 是 否结束输入”b”或者“d四、源代码#define M 20 #include #include #include /*定义图*/ typedef struct int VM; int RMM; int vexnum; Graph; /*创建图*/ void creatgraph(Graph *g,int n) int i,j,r1,r2; g-vexnum=n; /*顶点用i表示*/ for(i=1;iVi=i; /*初始化R*/ for(i=1;i=n;i+) for(j=1;jRij=0; /*输入R*/ printf(请按如下形式（2，4）输入R(0,0 END):n); scanf(%d,%d,&r1,&r2); while(r1!=0&r2!=0) g-Rr1r2=1; g-Rr2r1=1; scanf(%d,%d,&r1,&r2); /*打印图的邻接矩阵*/ void printgraph(Graph *g) int i,j; for(i=1;ivexnum;i+) for(j=1;jvexnum;j+) printf(%2d ,g-Rij); printf(n); /*全局变量：访问标志数组*/ int visitedM; /*访问顶点*/ void visitvex(Graph *g,int vex) printf(%d ,g-Vvex); /*获取第一个未被访问的邻接节点*/ int firstadjvex(Graph *g,int vex) int w,i; for(i=1;ivexnum;i+) if(g-Rvexi=1&visitedi=0) w=i; break; else w=0; return w; /*获取下一个未被访问的邻接节点(深度遍历)*/ int nextadjvex(Graph *g,int vex,int w) int t; t=firstadjvex(g,w); return t; /*深度递归遍历*/ void dfs(Graph *g,int vex) int w; visitedvex=1; visitvex(g,vex); for(w=firstadjvex(g,vex);w0;w=nextadjvex(g,vex,w) if(!visitedw) dfs(g,w); void dfstraverse(Graph *g) int i; for(i=1;ivexnum;i+) visitedi=0; for(i=1;ivexnum;i+) if(!visitedi) dfs(g,i); /*定义队列*/ typedef struct int VM; int front; int rear; Queue; /*初始化队列*/ initqueue(Queue *q) q-front=0; q-rear=0; /*判断队列是否为空*/ int quempty(Queue *q) if(q-front=q-rear) return 0; else return 1; /*入队操作*/ enqueue(Queue *q,int e) if(q-rear+1)%M=q-front) printf(The queue is overflow!n); return 0; else q-Vq-rear=e; q-rear=(q-rear+1)%M; return 1; /*出队操作*/ dequeue(Queue *q) int t; if(q-front=q-rear) printf(The queue is empty!n); return 0; else t=q-Vq-front; q-front=(q-front+1)%M; return t; /*广度遍历*/ void BESTraverse(Graph *g) int i; Queue *q=(Queue *)malloc(sizeof(Queue); for(i=1;ivexnum;i+) visitedi=0; initqueue(q); for(i=1;ivexnum;i+) if(!visitedi) visitedi=1; visitvex(g,g-Vi); enqueue(q,g-Vi); while(!quempty(q) int u,w; u=dequeue(q); for(w=firstadjvex(g,u);w0;w=nextadjvex(g,u,w) if(!visitedw) visitedw=1; visitvex(g,w); enqueue(q,w); /*主程序*/ main() int n; Graph *g=(Graph *)malloc(sizeof(Graph); char menu; printf(请输入节点的个数:n); scanf(%d,&n); creatgraph(g,n); printf(This is the linjiejuzhen of graph:n); printgraph(g); input: printf(Please input b or d or q ,Breadth_first: b Depth_first: d quit: qn); while(menu=getchar()=n); if(menu=b) printf(Breadth_first:n); BESTraverse(g); printf(n); goto input; else if(menu=d) printf(Depth_first:n); dfstraverse(g); printf(n); goto input; else if(menu=q) exit(0); else printf(Input error!Please input b or d!n); 五、调试分析及算法的改进设想1 由于对图的性质和算法掌握的比较好，所以在程序运行是比较顺利，没有遇到大的问题。2 每输入一个结点都要判别是在该边的哪个指针域，增加了时间复杂度，有待改进。3 程序的时间复杂度依赖于输入的结点和边的信息。4 通过本次实习，我在编程上的能力又有所提高。但本程序的可读性还不是很好，在以后的实习过程中会注意该点。5 增加变量，修改程序为动态输入，增加程序适用范围。6 为主函数增加循环功能,让程序能循环运行;六、运行结果七、参 考 文 献1数据结构使用C语言（第3版）朱战立 编，西安交通大学出版社。2 四川中外科技文化交流中心 组编（王松 主编）.Visual C+ 6.0程序设计与开发指南.北京：高等教育出版社，20043 朱晴婷，黄海鹰，陈莲君.Visual C+程序设计基础与实例分析.北京：清华大学出版社，2004心得体会通过这次的课程设计巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。够按要求编写课程设计报告书，能正确阐述设计和实验结果，正确绘制系统和程序框图。通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。课程设计是把我们所学的理论知识进行系统的总结并应用于实践的良好