数据结构课程设计——小组任务

《数据结构课程设计——小组任务》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程设计----小组设计报告专业：计算机科学与技术班级：组号：10组长姓名（学号）：副组长姓名（学号）：组员姓名（学号）：指导教师：冯向阳日期：16年1月6日至16年1月14日目录1组内成员贡献表32课程设计目的33课程设计内容和要求34任务完成情况35设计名称45.1图45.1.1设计目的45.1.2设计内容及要求45.1.3需求分析55.1.4概要设计65.1.5详细代码95.1.6使用说明95.1.7测试结果与分析105.2赫夫曼编码的应用135.2.1设计目的135.2.2设计内容及要求135.2.3需求分析14

2、5.2.4概要设计145.2.5详细代码145.2.6使用说明145.2.7测试结果与分析145.3体会与感想146参考文献14附录14附录一：14附录二：19附录三：24附录四：26附录五：33表1-1组内成员贡献表1组内成员贡献表姓名（学号）学号贡献度100100100（总计）3002课程设计目的1、学习获取知识的方法；2、提高发现问题、分析问题和解决实际问题的能力；3、加强创新意识和创新精神；4、加强团队的分工与合作；5、掌握面向实际背景思考问题的方法。3课程设计内容和要求内容：第一章前言第二章顺序表与链表第三章树与二叉树

3、第四章图第五章赫夫曼编码要求：完成第2章、第3章中每章2个设计任务中的至少一个任务。在完成个人任务1的基础上，完成第4章2个设计任务中的至少一个任务。每人必须在完成个人任务的基础上提交个人任务的设计报告，内容包括：任务名称、目的、具体内容、需求分析、概要设计、主要代码分析、测试结果、收获与体会。无论是个人任务还是小组任务希望各小组团队合作，小组成员之间应互相讨论，互相启发。4任务完成情况任务完成情况介绍，如表3-1.表3-1任务完成情况表完成任务名称有向图无向图最小生成树问题赫夫曼编码的应用5设计名称5.1图5.1.1设计目的熟

4、悉图的基本应用5.1.2设计内容及要求1.有向图（1）键盘输入数据，建立一个有向图的邻接表，并输出该邻接表。（2）采用邻接表存储实现有向图的深度优先遍历。（3）试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径（i<>j）。（4）已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，若有则印出该路径上的顶点。（5）在主函数中设计一个简单的菜单，分别调试上述算法。2.无向图（1）建立一个无向图的邻接表，并输出该邻接表。（2）采用邻接表存储实现无向图的深度优先遍历。（3）无向图采用邻接表存储

5、方式，试写出删除边（i，j）的算法，并输出深度优先遍历的结果。（4）在主函数中设计一个简单的菜单，分别调试上述算法。3.选做题：（1）最小生成树问题：若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。设无向图的顶点数不超过30个，并为简单起见，图中边的权值设成小于100的整数。步骤：1)利用普里姆算法求网的最小生成树。2)以文本形式输出生成树中各条边以及他们的权值.例.测试运行实例：对下图求最小生成树。5.1.3需求分析本程序用C编写，通过算法实现图的广度优

6、先遍历和深度优先遍历，并且实现最小生成树和关键路径的基本问题。5.1.4概要设计1.有向图类文件：Yx.h设计结构体typedefstructBNode{intorder;structBNode*next;}bnode;typedefstruct{intinfo;structBNode*fnext;}hnode;typedefstruct{hnodelist[50];intn,e;}Graph;yx()参数：无功能：构造函数，初始化成员变量voidcreate()参数：无功能：创建有向图的邻接链表voidout()参数：无功能：

7、输出邻接链表voidDFS(intv)参数：要遍历的起点功能：深度优先遍历voidifExistPath(intx,inty)参数:点x,点y功能:判断是否存在x到y的路径，并依据结果给成员变量sign赋值booljud()参数：无功能：根据sign的值返回真假voidPathAll(intu,intv,intpath[],intd)参数：点u,点v,数组,初始值为-1的整型功能：输出所有简单路径2.无向图类文件yx.h设计结构体typedefstructBNode{intorder;structBNode*next;}bnod

8、e;typedefstruct{intinfo;structBNode*fnext;}hnode;typedefstruct{hnodelist[50];intn,e;}Graph;wx();参数：无功能：构造函数，初始化成员变量voidcreate()参数：无