《数据结构课程设计指导2012.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计指导2012.doc（27页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计指导电子与信息工程系一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、设计要求在本课程设计过程中要求学生：（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩。（3）认真编写课程设计报告。课程设计报告的书写格式及要求见附录2。三、设计步骤1、 问题分析和任务定义；2、 数据结构和算法的设计；3、 编码实现和静态检查；4、 上机调试；5、总结
2、和整理课程设计报告。四、时间和机房安排18周星期时间机房一8:1511:301楼1号机房一14:0015:301楼3号机房三8:1511:301楼1号机房三14:0015:301楼2号机房五、考核方式和成绩评定考核分为两个部分：l 验收：按规定时间到机房运行程序，由老师检查运行情况。学生能对自己的程序面对教师提问并能熟练地解释清楚，要求验收时需要数据文件的程序提前建好数据文件，无数据文件要求的把原始数据提前输入，等老师验收。l 实验报告：是否按规定书写实验报告的各项内容。课程设计成绩采用五级分制。100%=上机检查（50%）+课程设计报告（50%）六、上交相关内容要求上交的成果的内容必须由以下
3、四个部分组成，缺一不可1 上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）；2 上交程序的说明文件：（保存在.doc中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明；3 课程设计报告：（保存在word 文档中，文件名要求 按照学号-姓名起名，如文件名为 09730101-张三.doc ），具体要求见后面。附录1 数据结构课程设计的具体内容1、一元多项式乘法1) 问题描述已知A(x)=a0+a1x+a2x2+anxn和B(x)=b0+b1x+b2x2+bmxm，并且在A(x)和B(x)中指数相差很多，求A(x
4、)=A(x)*B(x)。2) 基本要求(1)设计存储结构表示一元多项式；(2)设计算法实现一元多项式乘法；(3)分析算法的时间复杂度和空间复杂度。2、 迷宫问题1)问题描述迷宫求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。例如，图2所示为一个迷宫示意图，其中双边矩形表示迷宫，1代表有障碍，0代表无障碍。012345678901111111111入口(1, 1)出口(6, 8) 图2 迷宫示意图，其中1代表有障碍，0代表无障碍前进
5、的方向有八个，分别是上、下、左、右、左上、左下、右上、右下110111011112110101111131010000011410111011115110011000161011001101711111111112) 基本要求(1) 设计数据结构存储迷宫；(2) 设计存储结构保存从入口到出口的通路；(3) 设计算法完成迷宫问题的求解；(4) 分析算法的时间复杂度。3) 设计思想可以采用回溯法实现该问题的求解。回溯法是一种不断试探及时纠正错误的搜索方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，
6、换下一个方向再继续试探，直到所有可能的通路都搜索到，或找到一条通路，或无路可走又返回到入口点。在求解过程中，为了保证在任何位置上都能沿原路退回，需要一个后进先出的栈来保存从入口到当前位置的路径。可以将迷宫定义成一个二维数组，则每个点有8个试探方向，如当前点的坐标是(x, y)，与其相邻的8个点的坐标都可根据与该点的相邻方位而得到，规定试探顺序为顺时针方向，将这8个方向的坐标增量放在一个结构数组move8中，在move数组中，每个元素由两个域组成：x表示横坐标增量，y表示纵坐标增量。这样会很方便地求出从某点(x，y)按某一方向 v (0v7) 到达新点（i，j）的坐标：i=x+movev.x ；
7、 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) ;4、哈夫曼编码1) 问题描述设某编码系统共有n个字符，使用频率分别为w1, w2, , wn，设计一个不等长的编码方案，使得该编码系统的空间效率最好。2) 基本要求(1) 设计数据结构；(2) 设计编码算法；(3) 分析时间复杂度和空间复杂度。3) 设计思想 利用Huffman编码树求得最佳的编码方案。根据哈夫
8、曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个结构型的一维数组HuffTree，保存哈夫曼树中各结点的信息，每个结点包括：权值、左孩子、右孩子、双亲，如图6所示。由于哈夫曼树中共有2n-1个结点，并且进行n-1次合并操作，所以该数组的长度为2n-1。weight lchild rchild parent 图6 哈夫曼树的结点结构 构造哈夫曼树的伪代码如下：1. 数组huffTree初始化，所有元素结点的双亲、左右孩子都置为-1； 2. 数组huffTree的前n个元素的权值置给定权值wn； 3. 进行n-1次合并 3.1 在二叉树集合中选取两个权值最小的根结点，其下标分别为i1, i2； 3
9、.2 将二叉树i1、i2合并为一棵新的二叉树k；在哈夫曼树中，设左分支为0，右分支为1，从根结点出发，遍历整棵哈夫曼树，求得各个叶子结点所表示字符的哈夫曼编码。【提高】输入一篇英文文章，统计每个字符出现的次数，并以此构造哈夫曼树和输出每个字符的哈夫曼编码，最后输出这篇文章的编码。5、TSP问题（回溯法求解）1) 问题描述所谓TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。2) 基本要求(1) 上网查找TSP问题的应用实例；(2) 分析求TSP问题的全局最优解的时间复杂度；(3)
10、设计一个求近似解的算法；(4) 分析算法的时间复杂度。3) 设计思想对于TSP问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅行路线，从中选择最佳的一条。但是用穷举法求解TSP问题的时间复杂度为(n!)，当n大到一定程度后是不可解的。本实验可以采用回溯法求解，使用邻接矩阵存储该图。【提示】可参考计算机算法设计与分析（电子工业出版社）6、TSP问题（贪心法求解）1) 问题描述所谓TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。2) 基本要求(1) 上网查找TSP问题的应用实例；(2) 分析求TSP问题的全局最优解的时间复杂度；(3) 设计一个求近似解的算法；(4) 分析算法的时间复杂度。3) 设计思想对于TSP问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅行路线，从中选择最佳的
