课程设计报告模板张苗.doc

内蒙古科技大学本科生课程设计说明书题 目：C语言课程设计 图的遍历 学生姓名：张苗学 号：1376807337专 业：计算机科学与技术班 级：3班指导教师：周李涌内蒙古科技大学课程设计任务书课程名称数据结构课程设计设计题目图的遍历指导教师周李涌时间2013年秋学期第15周至第19周一、教学要求1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。图的遍历以数组表示法或邻接表表示图，在此基础上实现对图的遍历。要求设计类（或类模板）来描述图，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：v 输入图、输出图v 求图中顶点V的第一个邻接点v 求图中顶点V的下一个邻接点v 深度优先遍历图v 广度优先遍历图 并设计主函数测试该类（或类模板）。三、设计要求及成果1. 分析课程设计题目的要求2. 写出详细设计说明3. 编写程序代码，调试程序使其能正确运行4. 设计完成的软件要便于操作和使用5. 设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1. 根据平时上机考勤、表现和进度，教师将每天点名和检查2. 根据课程设计完成情况，必须有可运行的软件。3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4. 根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1数据结构 （C语言版）严蔚敏、吴伟民 主编 清华大学出版社 2004.112数据结构课程设计案例精编（用C/C+描述），李建学 等 编著，清华大学出版社 2007.23.数据结构:用面向对象方法与C+语言描述，殷人昆 主编，清华大学出版社 2007.6目 录内蒙古科技大学课程设计任务书I第一章 需求分析31.1引言31.2任务概述31.3数据描述31.4功能需求31.5性能需求31.6运行需求41.7任务计划4第二章概要设计52.1总体设计52.2数据类型设计（或数据结构设计）52.3接口设计 /函数声明52.4运行界面设计5第三章详细设计73.1输入模块设计73.2输出模块设计73.3查找模块设计73.4排序模块设计73.5保存及读取模块设计7第四章测试分析84.1测试程序执行情况84.2出现的问题和解决的方法8第五章用户手册（可选）95.1使用说明95.2运行说明9第六章课程设计总结10附录：程序代码11参考文献12致谢13第一章 需求分析1.1 引言本学期我们对数据结构这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求实习者掌握数据结构中的各方面知识，还要求实习者具备一定的C语言基础和编程能力。具体说来，这次课程设计主要有两大方面目的。一是让实习者通过实习掌握数据结构中的知识。对于图的存储与遍历这一课题来说，所要求掌握的数据结构知识主要有：图的邻接表存贮结构、队列的基本运算实现、邻接表的算法实现、图的广度优先搜索周游算法实现、图的深度优先搜索周游算法实现。二是通过实习巩固并提高实习者的C语言知识，并初步了解Visual C+的知识，提高其编程能力与专业水平。1.2 任务概述 (1) 输入的形式和输入值的范围；(2) 输出的形式；(3) 程序所能达到的功能；(4) 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。1.3 数据描述例子：输入顶点数和边数：4 5接着输入顶点字符串：1 2 3 4 1.4 功能需求以数组表示法或邻接表表示图，在此基础上实现对图的遍历。要求设计类（或类模板）来描述图，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：v 输入图、输出图v 求图中顶点V的第一个邻接点v 求图中顶点V的下一个邻接点v 深度优先遍历图v 广度优先遍历图 并设计主函数测试该类（或类模板）。1.5 运行需求在codeblock上运行，c语言程序1.6 任务计划 我们需要先进行总体设计，有一个大致的方向，然后我们需要把数据的结构类型确定下来，第三步要把函数接口设计出来，第四步把运行界面设计，我就把大致程序框架做了出来。 我们接下来就应该进行详细的设计来完成所需要的功能了第二章 概要设计2.1 总体设计图的实现深度优先遍历广度优先遍历输出图输入图创建图访问下一个邻接顶点访问邻接顶点2.2 数据类型设计（或数据结构设计）1.定义结点结构类型typedef struct nodeint adjvex;struct node *next;EdgeNode;2.定义虚拟结点结构类型typedef struct vnodechar vertex;EdgeNode *firstedge;VertexNode;3.邻接表类型typedef struct AdjList adjlist;int n,e; ALGraph;2.3 接口设计 可参考用以下表格形式：表2.1：函数列表函数名函数格式 /即函数首部函数功能CreatALGraph创建图DFS深度优先遍历BFS广度优先遍历第三章 详细设计3.1图的存储本课题要求采取邻接表的存储结构。邻接表是一种链式的存储结构，在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的弧）。每个结点由3个域组成，其中邻接点域（adjvex）指示与顶点Vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的结点；数据域（info）存储和边或弧相关的信息，如权值等。所以一开始必须先定义邻接表的边结点类型以及邻接表类型，并对邻接表进行初始化，然后根据所输入的相关信息，包括图的顶点数、边数、是否为有向，以及各条边的起点与终点序号，建立图的邻接表。此时要分两种情况：有向图与无向图。对于无向图，一条边的两的个顶点，互为邻接点，所以在存储时，应向起点的单链表表头插入一边结点，即终点。同时将终点的单链表表头插入一边结点，即起点。对于有向图，只能向起点的单链表的表头插入一个边结点，即终点。但不能反过来。至于邻接表的输出，由于不了解C+中的绘图操作，故采用for语句输出各结点，并配合一些符号完成邻接表的输出。3.2 图的遍历3.2.1 图的深度优先遍历假设初始状态是图中所有顶点未曾被访问，深度优先遍历可以从图的初始点出发，访问初始点，然后依次从v未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时仍有顶点未被访问到，则从另一个未被访问的顶点出发，重复上述过程，直至所有点都被访问到为止。这是一个递归的过程。所以在实现深度优先遍历的过程中必须递归调用深度优先搜索函数。而且在深度优先搜索函数中必须设一标志数组以标记结点是否被访问。具体过程应为：先访问初始点Vi，并标志其已被访问。此时定义一指向边结点的指针p，并建立一个while（）循环，以指针所指对象不为空为控制条件，当Vi的邻接点未被访问时，递归调用深度优先遍历函数访问之。然后将p指针指向下一个边结点。这样就可以完成图的深度优先遍历了。void DFSM(ALGraph *G,int i)EdgeNode *p;printf(%c ,G-adjlisti.vertex);visitedi=TRUE;p=G-adjlisti.firstedge;while(p)DFSM(G,p-adjvex);p=p-next;void DFS(ALGraph *G)int i;for(i=0;in;i+)visitedi=FALSE;for(i=0;in;i+)if(!visitedi)DFSM(G,i);3.2.2 图的广度优先遍历广度优先搜索遍历类似于树的按层次遍历的过程。假设从图中某顶点v出发，在访问了v之后访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点的邻接点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到。若此时图中尙有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程是以v为起始点，由近及远，依次访问和v有路径相通且路径长度为1，2，的顶点。所以要实现算法必须先建立一个元素类型为整形的空队列，并定义队首与队尾指针，同时也要定义一个标志数组以标记结点是否被访问。同样，也是从初始点出发开始访问，访问初始点，标志其已被访问，并将其入队。当队列非空时进行循环处理。当结点被访问时对其进行标志，并入队列。通过while（）循环，并以是否被访问为控制条件，访问所有结点，完成图的广度优先遍历。void BFS(ALGraph *G,int k) int i,f=0,r=0;EdgeNode *p;int cqMaxVertexNum;for(i=0;in;i+)visitedi=FALSE;for(i=0;in;i+)cqi=-1;printf(%c ,G-adjlistk.vertex);visitedk=TRUE;cqr=k;while(cqf!=-1) i=cqf; f=f+1;p=G-adjlisti.firstedge;while(p)if(!visitedp-adjvex) printf(%c ,G-adjlistp-adjvex.vertex);visitedp-adjvex=TRUE;r=r+1; cqr=p-adjvex;p=p-next;第四章 测试分析4.1 测试程序执行情况第五章 用户手册（可选）5.1 使用说明5.2 运行说明第六章 课程设计总结 转眼，为期两周的数据结构课程设计实习即将结束了。在这次实习中，自己的C语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高。同时也学会了解决问题的方法。总结起来，自己主要有以下几点体会：1.必须牢固掌握基础知识。由于C语言是大一所学知识，有所遗忘，且未掌握好这学期所学的数据结构这门课，所以在实习之初感到棘手。不知如何下手，但在后来的实习过程中自己通过看书和课外资料，并请教其他同学，慢慢地对C语言和数据结构知识有所熟悉。这时才逐渐有了思路。所以，这次实习之后，我告诫自己：今后一定要牢固掌握好专业基础知识。2.必须培养严谨的科学态度。自己在编程时经常因为一些类似于“少了分号”的小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十分严谨的事情，容不得马虎。所以在今后自己一定要培养严谨的科学态度。我想这不仅是对于程序设计，做任何事都应如此。3.这次课程设计也让我充分认识到数据结构这门课的重要性。它给我们一个思想和大纲，让我们在编程时容易找到思路，不至于无章可循。同时它也有广泛的实际应用。总之，在这次实习中，自己的C语言以及数据结构知识得到提高，编程能力也得到了提高。附录：程序代码#includestdio.h#includestdlib.h#define MaxVertexNum 50typedef struct nodeint adjvex;struct node *next;EdgeNode;typedef struct vnodechar vertex;EdgeNode *firstedge;VertexNode;typedef VertexNodeAdjListMaxVertexNum;typedef struct AdjList adjlist;int n,e; ALGraph;void CreatALGraph(ALGraph *G) int i,j,k;char a;EdgeNode *s;printf(请输入顶点数和边数: );scanf(%d,%d,&G-n,&G-e);scanf(%c,&a);printf(请输入顶点字符串:);for(i=0;in;i+)scanf(%c,&a);G-adjlisti.vertex=a;G-adjlisti.firstedge=NULL;printf(输入边，创造邻接表：n);for(k=0;ke;k+) scanf(%d%d,&i,&j);s=(EdgeNode *)malloc(sizeof(EdgeNode);s-adjvex=j;s-next=G-adjlisti.firstedge;G-adjlisti.firstedge=s;s=(EdgeNode *)malloc(sizeof(EdgeNode);s-adjvex=i;s-next=G-adjlistj.firstedge;G-adjlistj.firstedge=s;typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;void DFSM(ALGraph *G,int i)EdgeNode *p;printf(%c ,G-adjlisti.vertex);visitedi=TRUE;p=G-adjlisti.firstedge;while(p)DFSM(G,p-adjvex);p=p-next;void DFS(ALGraph *G)int i;for(i=0;in;i+)visitedi=FALSE;for(i=0;in;i+)if(!visitedi)DFSM(G,i); void BFS(ALGraph *G,int k) int i,f=0,r=0;EdgeNode *p;int cqMaxVertexNum;for(i=0;in;i+)visitedi=FALSE;for(i=0;in;i+)cqi=-1;printf(%c ,G-adjlistk.vertex);visitedk=TRUE;cqr=k;while(cqf!=-1) i=cqf; f=f+1;p=G-adjlisti.firstedge;while(p)if(!visitedp-adjvex) printf(%c ,G-adjlistp-adjvex.vertex);visitedp-adjvex=TRUE;r=r+1; cqr=p-adjvex;p=p-next;int main()int i;ALGraph *G;G=(ALGraph *)malloc(sizeof(ALGraph);CreatALGraph(G);printf(Print Graph DFS: );DFS(G);printf(n);printf(Print Graph BFS: );BFS(G,3);printf(n);参考文献1 杨路明 C语言程序设计教程 北京邮电大学出版社2 徐孝凯 数据结构课程实验 清华大学出版社3 严蔚敏 吴伟民 数据结构（C语言版） 清华大学出版社致谢