1、数据结构课程设计指导1数据结构课程设计指导书邢振祥电子与信息工程系计算机应用教研室2010-11-18数据结构课程设计指导12一、课程设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、课程设计要求1重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；2按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩。3认真编写课程设计报告。课程设计报告的书写格式及要求见附录二。三、课程设计环境1windows 操作系统；2Visual
2、 C+应用程序软件。四、课程设计内容按实际题目要求，完成数据结构课程设计，具体内容见附录二。 五、课程设计步骤1问题分析和任务定义；2数据类型和系统设计；3编码实现和静态检查；4上机调试；5总结和整理课程设计报告。六、考核方式和成绩评定考核分为两个部分： 程序运行情况：按规定时间到机房运行程序，由老师检查运行情况。学生能对自己的程序面对教师提问并能熟练地解释清楚。 实验报告：是否按规定书写实验报告的各项内容。课程设计成绩采用五级分制。100%=上机检查（50%）+课程设计报告（50%）七、上交相关内容要求上交的成果的内容必须由以下四个部分组成，缺一不可。1上交源程序：学生按照课程设计的具体要求
3、所开发的所有源程序（应该放到一个文件夹中） ；2上交程序的说明文件：（保存在.doc 中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明；3课程设计报告：（保存在 word 文档中，文件名要求 按照“ 姓名-学号-课程设计报告“ 起名，如文件名为“张三-101- 课程设计报告”.doc ）按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成。数据结构课程设计指导13内容要求：一、需求分析1 程序的功能；2 输入输出的要求；3 测试数据。二、概要设计包括程序设计组成框图，程序中使用的存储结构设计说明（如果指定存储结构请写
4、出该存储结构的定义） 。三、详细设计包括模块功能说明（如函数功能、入口及出口参数说明，函数调用关系描述等） ，每个模块的算法设计说明（可以是描述算法的流程图） 。源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。四、调试分析测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？） ，算法的改进设想。五、核心源程序清单和执行结果源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。数据结构课程设计指导14附录一 数据结构课程设计的具体内容本次课程设计完成
5、如下模块（共 36 个模块，抽签决定自己所做题目的序号）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)问题描述迷宫求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷
6、宫中寻找通路以到达出口。例如，图 2 所示为一个迷宫示意图，其中双边矩形表示迷宫，1 代表有障碍，0 代表无障碍。2) 基本要求(1) 设计数据结构存储迷宫；(2) 设计存储结构保存从入口到出口的通路；(3) 设计算法完成迷宫问题的求解；(4) 分析算法的时间复杂度。3) 设计思想可以采用回溯法实现该问题的求解。回溯法是一种不断试探及时纠正错误的搜索方法。从入口出发，按某一方向向前探索，若能走通（未走过的） ，即某处可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都搜索到，或找到一条通路，或无路可走又返回到入口点。0
7、 1 2 3 4 5 6 7 8 90 1 1 1 1 1 1 1 1 1 11 1 0 1 1 1 0 1 1 1 12 1 1 0 1 0 1 1 1 1 13 1 0 1 0 0 0 0 0 1 14 1 0 1 1 1 0 1 1 1 15 1 1 0 0 1 1 0 0 0 16 1 0 1 1 0 0 1 1 0 17 1 1 1 1 1 1 1 1 1 1入口(1, 1)出口(6, 8)图 2 迷宫示意图，其中 1 代表有障碍，0 代表无障碍前进的方向有八个，分别是上、下、左、右、左上、左下、右上、右下数据结构课程设计指导15在求解过程中，为了保证在任何位置上都能沿原路退回，需要
8、一个后进先出的栈来保存从入口到当前位置的路径。可以将迷宫定义成一个二维数组，则每个点有 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
9、）入栈；3. 当栈不空时循环执行下述操作：3.1 (x , y , d)容忍值，则在 j 处放置放大器 ;2.2 否则 D(i) = maxD(i)，D (j) +d(j) ;【思考题】本题假设分布网络是一棵二叉树结构，如果是树结构应如何设计算法？5哈夫曼编码1) 问题描述设某编码系统共有 n 个字符，使用频率分别为w 1, w2, , wn，设计一个不等长的编码方案，使得该编码系统的空间效率最好。2) 基本要求(1) 设计数据结构；(2) 设计编码算法；(3) 分析时间复杂度和空间复杂度。3) 设计思想利用 Huffman 编码树求得最佳的编码方案。根据哈夫曼算法，建立哈夫曼树时，可以将哈夫
10、曼树定义为一个结构型的一维数组 HuffTree，保存哈夫曼树中各结点的信息，每个结点包括：权值、左孩子、右孩子、双亲，如图 6 所示。由于哈夫曼树中共有 2n-1 个结点，并且进行 n-1 次合并操作，所以该数组的长度为 2n-1。构造哈夫曼树的伪代码如下：1. 数组 huffTree 初始化，所有元素结点的双亲、左右孩子都置为-1；weight lchild rchild parent图 6 哈夫曼树的结点结构数据结构课程设计指导192. 数组 huffTree 的前 n 个元素的权值置给定权值 wn；3. 进行 n-1 次合并3.1 在二叉树集合中选取两个权值最小的根结点，其下标分别为
11、i1, i2；3.2 将二叉树 i1、i2 合并为一棵新的二叉树 k；在哈夫曼树中，设左分支为 0，右分支为 1，从根结点出发，遍历整棵哈夫曼树，求得各个叶子结点所表示字符的哈夫曼编码。【思考题】对于采用哈夫曼编码树进行的编码，如何设计解码算法？6TSP 问题1) 问题描述所谓 TSP 问题是指旅行家要旅行 n 个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。2) 基本要求(1) 上网查找 TSP 问题的应用实例；(2) 分析求 TSP 问题的全局最优解的时间复杂度；(3) 设计一个求近似解的算法；(4)
12、分析算法的时间复杂度。3) 设计思想对于 TSP 问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅行路线，从中选择最佳的一条。但是用穷举法求解 TSP 问题的时间复杂度为 (n!)，当 n 大到一定程度后是不可解的。本实验只要求近似解，可以采用贪心法求解：任意选择某个城市作为出发点，然后前往最近的未访问的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。为便于查找离某顶点最近的邻接点，可以采用邻接矩阵存储该图。算法用伪代码描述如下：1. 任意选择某个顶点 v 作为出发点；2. 执行下述过程，直到所有顶点都被访问：2.1 v=最后一个被访问的顶点；2.2
13、在顶点 v 的邻接点中查找距离顶点 v 最近的未被访问的邻接点 j；2.2 访问顶点 j；3. 从最后一个访问的顶点直接回到出发点 v；【思考题】上网查找 TSP 问题的应用实例，写一篇综述报告。7医院选址问题1)问题描述n 个村庄之间的交通图可以用有向网图来表示，图中边上的权值表示从村庄 i 到村庄 j的道路长度。现在要从这 n 个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？数据结构课程设计指导1102) 基本要求(1) 建立模型，设计存储结构；(2) 设计算法完成问题求解；(3) 分析算法的时间复杂度。3) 设计思想医院选址问题实际是求有向图中
14、心点的问题。首先定义顶点的偏心度。设图 G=（V ，E） ，对任一顶点 k，称 E(k)=maxd(i, k)（iV）为顶点 k 的偏心度。显然，偏心度最小的顶点即为图 G 的中心点。如图 7(a)所示是一个带权有向图，其各顶点的偏心度如图(b)所示。医院选址问题的算法用伪代码描述如下：1对加权有向图，调用 Floyd 算法，求每对顶点间最短路径长度的矩阵；2对最短路径长度矩阵的每列求大值，即得到各顶点的偏心度；3具有最小偏心度的顶点即为所求。【思考题】图的存储结构和算法的设计需要一定的灵活性和技巧。从医院选址问题的求解过程，你有什么感想？8简单个人电话号码查询系统1) 问题描述人们在日常生活中经常需要查找某个人或某个单位的电话号码，本实验将实现一个简单的个人电话号码查询系统，根据用户输入的信息（例如姓名等）进行快速查询。2) 基本要求(1) 在外存上，用文件保存电话号码信息；(2) 在内存中，设计数据结构存储电话号码信息；(3) 提供查询功能：根据姓名实现快速查询；(4) 提供其他维护功能：例如插入、删除、修改等；(5) 按电话号码进行排序。3) 设计思想由于需要管理的电话号码信息较多，而且要在程序运行结束后仍然保存电话号码信息，所以电a bcde1253214 顶点 偏心度a b 6b 8d 5e 7(a) (b)图 7 带权有向图及各顶点的偏心度
