数据结构课程设计指导(题目).doc

1、需求分析、需求分析 1 程序的功能； 2 输入输出的要求； 3 测试数据。 2、概要设计、概要设计 包括程序设计组成框图，程序中使用的存储结构设计说明（如果指定存储结构请写 出该存储结构的定义） 。 3、详细设计、详细设计 包括模块功能说明（如函数功能、入口及出口参数说明，函数调用关系描述等） ， 每个模块的算法设计说明（可以是描述算法的流程图） 。 源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功 能部分要加上清晰的程序注释。 4、调试分析、调试分析 测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问 题的思考（问题是哪些？问题如何解决？） ，算法的改进设想。 5、核心源程序清单和执行结果、核心源程序清单和执行结果 源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功 能部分要加上清晰的程序注释。 1、一元多项式乘法、一元多项式乘法 1) 问题描述问题描述 已知 A(x)=a0+a1x+a2x2+anxn和 B(x)=b0+b1x+b2x2+bmxm，并且在 A(x)和 B(x)中 指数相差很多，求 A(x)=A(x)*B(x)。 2) 基本要求基本要求 (1)设计存储结构表示一元多项式； (2)设计算法实现一元多项式乘法； (3)分析算法的时间复杂度和空间复杂度。 2、 迷宫问题迷宫问题 1)问题描述问题描述 迷宫求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒 子的入口处赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷 宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。例如，图 2 所 示为一个迷宫示意图，其中双边矩形表示迷宫，1 代表有障碍，0 代表无障碍。 2) 基本要求基本要求 (1) 设计数据结构存储迷宫； (2) 设计存储结构保存从入口到出口的通路； (3) 设计算法完成迷宫问题的求解； (4) 分析算法的时间复杂度。 3) 设计思想设计思想 可以采用回溯法实现该问题的求解。回溯法是一种不断试探及时纠正错误的搜索方法。 从入口出发，按某一方向向前探索，若能走通（未走过的） ，即某处可以到达，则到达新点， 否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继 续试探，直到所有可能的通路都搜索到，或找到一条通路，或无路可走又返回到入口点。 0123456789 01111111111 11011101111 21101011111 31010000011 41011101111 51100110001 61011001101 71111111111 入口(1, 1) 出口(6, 8) 图 2 迷宫示意图，其中 1 代表有障碍，0 代表无障碍 前进的方向有八个，分别是上、下、左、右、左上、左下、右上、右下 在求解过程中，为了保证在任何位置上都能沿原路退回，需要一个后进先出的栈来保 存从入口到当前位置的路径。 可以将迷宫定义成一个二维数组，则每个点有 8 个试探方向，如当前点的坐标是(x, y)， 与其相邻的 8 个点的坐标都可根据与该点的相邻方位而得到，规定试探顺序为顺时针方向， 将这 8 个方向的坐标增量放在一个结构数组 move8中，在 move 数组中，每个元素由两个 域组成：x 表示横坐标增量，y 表示纵坐标增量。这样会很方便地求出从某点(x，y)按某一 方向 v (0v7) 到达新点（i，j）的坐标：i=x+movev.x ； j=y+movev.y。 算法用伪代码描述如下： 1. 栈初始化； 2. 将入口点坐标(x , y)及该点的方向 d（设为-1）入栈； 3. 当栈不空时循环执行下述操作： 3.1 (x , y , d)容忍值，则在 j 处放置放大器; 2.2 否则 D(i) = maxD(i)，D(j) +d(j) ; 【思考题思考题】本题假设分布网络是一棵二叉树结构，如果是树结构应如何设计算法？ 5、哈夫曼编码、哈夫曼编码 1) 问题描述问题描述 设某编码系统共有 n 个字符，使用频率分别为w1, w2, , wn，设计一个不等长的编码 方案，使得该编码系统的空间效率最好。 2) 基本要求基本要求 (1) 设计数据结构； (2) 设计编码算法； (3) 分析时间复杂度和空间复杂度。 3) 设计思想设计思想 利用 Huffman 编码树求得最佳的编码方案。 根据哈夫曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个结构型的一维数组 HuffTree，保存哈夫曼树中各结点的信息，每个结点包括：权值、左孩子、右孩子、双亲， 如图 6 所示。由于哈夫曼树中共有 2n-1 个结点，并且进行 n-1 次合并操作，所以该数组的 长度为 2n-1。 构造哈夫曼树的伪代码如下： 1. 数组 huffTree 初始化，所有元素结点的双亲、左右孩子都置为-1； 2. 数组 huffTree 的前 n 个元素的权值置给定权值 wn； 3. 进行 n-1 次合并 3.1 在二叉树集合中选取两个权值最小的根结点，其下标分别为 i1, i2； 3.2 将二叉树 i1、i2 合并为一棵新的二叉树 k； 在哈夫曼树中，设左分支为 0，右分支为 1，从根结点出发，遍历整棵哈夫曼树，求得 各个叶子结点所表示字符的哈夫曼编码。 【思考题思考题】对于采用哈夫曼编码树进行的编码，如何设计解码算法？ 6、TSP 问题问题 1) 问题描述问题描述 所谓 TSP 问题是指旅行家要旅行 n 个城市，要求各个城市经历且仅经历一次，并要求 所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广 为人知的问题。 2) 基本要求基本要求 (1) 上网查找 TSP 问题的应用实例； (2) 分析求 TSP 问题的全局最优解的时间复杂度； (3) 设计一个求近似解的算法； (4) 分析算法的时间复杂度。 3) 设计思想设计思想 对于 TSP 问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有 可能的旅行路线，从中选择最佳的一条。但是用穷举法求解 TSP 问题的时间复杂度为(n!)， 当 n 大到一定程度后是不可解的。 本实验只要求近似解，可以采用贪心法求解：任意选择某个城市作为出发点，然后前 往最近的未访问的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。 为便于查找离某顶点最近的邻接点，可以采用邻接矩阵存储该图。算法用伪代码描述 如下： weight lchild rchild parent 图 6 哈夫曼树的结点结构 1. 任意选择某个顶点 v 作为出发点； 2. 执行下述过程，直到所有顶点都被访问： 2.1 v=最后一个被访问的顶点； 2.2 在顶点 v 的邻接点中查找距离顶点 v 最近的未被访问的邻接点 j； 2.2 访问顶点 j； 3. 从最后一个访问的顶点直接回到出发点 v； 【思考题思考题】上网查找 TSP 问题的应用实例，写一篇综述报告。 7、医院选址问题、医院选址问题 1)问题描述问题描述 n 个村庄之间的交通图可以用有向网图来表示，图中边上的权值表示从村庄 i 到 村庄 j 的道路长度。现在要从这 n 个村庄中选择一个村庄新建一所医院，问这所医院应建 在哪个村庄，才能使所有的村庄离医院都比较近？ 2) 基本要求基本要求 (1) 建立模型，设计存储结构； (2) 设计算法完成问题求解； (3) 分析算法的时间复杂度。 3) 设计思想设计思想 医院选址问题实际是求有向图中心点的问题。首先定义顶点的偏心度。 设图 G=（V，E） ，对任一顶点 k，称 E(k)=maxd(i, k)（iV）为顶点 k 的偏心度。 显然，偏心度最小的顶点即为图 G 的中心点。 如图 7(a)所示是一个带权有向图，其各顶点的偏心度如图(b)所示。 医院选址问题的算法用伪代码描述如下： 1对加权有向图，调用 Floyd 算法，求每对顶点间最短路径长度的矩阵； 2对最短路径长度矩阵的每列求大值，即得到各顶点的偏心度； 3具有最小偏心度的顶点即为所求。 【思考题思考题】图的存储结构和算法的设计需要一定的灵活性和技巧。从医院选址问题的 ab c d e 1 2 5 32 1 4 顶点偏心度 a b 6 b 8 d 5 e 7 (a) (b) 图 7 带权有向图及各顶点的偏心度 求解过程，你有什么感想？ 8、 排序二叉树的遍历（排序二叉树的遍历（ 用递归或非递归的方法都可以）用递归或非递归的方法都可以） 1)1)问题描述问题描述 输入树的各个结点，建立排序二叉树，对建立的排序二叉树进行层次、先序、中序和 后序遍历并统计该二叉树中叶子结点的数目。 2)2)基本要求基本要求 (1)用菜单实现 (2)能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列和叶子结点的数目。 9、集合运算、集合运算 1)问题描述问题描述 使用链表来表示集合，完成集合的合并，求交集等操作。 2) 基本要求基本要求 （1）用链表表示两个集合 （2）对两个集合分别从小到大排序 （3）两个集合合并成另一个新集合，如数值相同，合并为一个数据项 （4）求出两个集合的交集建立一个新的集合。 附录 2：课程设计说明书规范 一、课程设计说明书规范 课程设计说明书是课程设计主要成果之一，对于设计类，应包括图纸、程序、实物成 果等。 1、说明书基本格式 说明书可以手写或打印，书写要用黑或蓝黑墨水，书写工整；打印时正文采用 5 号宋 体，A4 纸，页边距均为 20mm，行间距采用 18 磅。文中标题采用宋体加粗。 2、说明书结构及要求 （1）封面（见附录 3） 包括：题目、系别、班级、完成日期、成绩及指导教师（签字） 、学生姓名等项。 （2）课程设计任务书 （格式见附录 4） （3）目录 要求层次清晰，给出标题及页次。最后一项为“参考资料“。 打印时各章题序及标题用小 4 号黑体, 其余用小 4 号宋体。 （4）正文 正文应按照目录所确定的顺序依次撰写，要求计算准确，论述清楚、简练、通顺，插 图清晰整洁。文中图、标及公式应规范地绘制和书写。 （5）参考资料 参考资料按下述顺序和格式书写： 1毛昶熙，周名德等闸坝工程水力学与设计管理.北京：水利电力出版社，1995：89 如参考网上资料，请写明网址。 注：正文内容可参考以下内容：注：正文内容可参考以下内容： 正文 a)总体设计（程序设计组成框图、流程图） b)详细设计（模块功能说明（如函数功能、入口及出口参数说明，函数调用关 系描述等） c)调试与测试：调试方法，测试结果的分析与讨论，测试过程中遇到的主要问 题及采取的解决措施 d)关键源程序清单和执行结果：清单中应有足够的注释问题描述和功能设计 （附录（附录 3 3：封面要求：）：封面要求：） 学 号 数据结构课程设计 设计说明书 题目 起止日期： 2009 年 10 月 20 日 至 2009 年 12 月 14 日 学生姓名 班级 成绩 指导教师 (签字 ) 电子与信息工程系电子与信息工程系 年年 月月 日日 附表 4 天津城市建设学院 课程设计任务书 20092010 学年第学年第 1 学期学期 电子与信息工程 系 专业 班级 课程设计名称： 数据结构课程设计 设计题目： 完成期限：自 2009 年 10 月 20 日至 2009 年 12 月 14 日共 周 设计依据、要求及主要内容（可另加附页）： 一、设计目的 熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。 二、设计要求 在本课程设计过程中要求学生： （1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务； （2