信息与计算科学课程设计

信息与计算科学数据结构课程设计指导一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。

二、设计要求在本课程设计过程中要求学生：（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。

凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩。

（3）认真编写课程设计报告。

课程设计报告的书写格式及要求见附录2。

三、设计步骤1、问题分析和任务定义；2、数据类型和系统设计；3、编码实现和静态检查；4、上机调试；5、总结和整理课程设计报告。

四、考核方式和成绩评定考核分为两个部分：●程序运行情况：按规定时间到机房运行程序，由老师检查运行情况。

学生能对自己的程序面对教师提问并能熟练地解释清楚。

●课程设计报告：是否按规定书写课程设计报告的各项内容。

课程设计成绩采用五级分制。

100%=上机检查（50%）+课程设计报告（50%）五、上交相关内容要求上交的成果的内容必须由以下四个部分组成，缺一不可1．上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）；2．上交程序的说明文件：（保存在.doc中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明；3．课程设计报告：按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成；1、需求分析1．程序的功能；2．输入输出的要求；3．测试数据。

2、概要设计包括程序设计组成框图，程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）。

3、详细设计包括模块功能说明（如函数功能、入口及出口参数说明，函数调用关系描述等），每个模块的算法设计说明（可以是描述算法的流程图）。

源程序要按照写程序的规则来编写。

要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。

4、调试分析测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。

5、核心源程序清单和执行结果源程序要按照写程序的规则来编写。

要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。

附录1 数据结构课程设计的具体内容本次课程设计完成如下模块（共11个模块，抽签决定自己所做题目的序号） 1、一元多项式乘法 1) 问题描述已知A (x )=a 0+a 1x +a 2x 2+……+a n x n 和B (x )=b 0+b 1x +b 2x 2+……+b m x m ，并且在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) 设计思想可以采用回溯法实现该问题的求解。

回溯法是一种不断试探及时纠正错误的搜索方法。

从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续入口(1, 1) 出口(6, 8) 图2 迷宫示意图，其中1代表有障碍，0代表无障碍前进的方向有八个，分别是上、下、左、右、左上、左下、右上、右下试探，直到所有可能的通路都搜索到，或找到一条通路，或无路可走又返回到入口点。

在求解过程中，为了保证在任何位置上都能沿原路退回，需要一个后进先出的栈来保存从入口到当前位置的路径。

可以将迷宫定义成一个二维数组，则每个点有8个试探方向，如当前点的坐标是(x, y)，与其相邻的8个点的坐标都可根据与该点的相邻方位而得到，规定试探顺序为顺时针方向，将这8个方向的坐标增量放在一个结构数组move[8]中，在move数组中，每个元素由两个域组成：x表示横坐标增量，y表示纵坐标增量。

这样会很方便地求出从某点(x，y)按某一方向v (0≤v≤7) 到达新点（i，j）的坐标：i=x+move[v].x；j=y+move[v].y。

算法用伪代码描述如下：1. 栈初始化；2. 将入口点坐标(x , y)及该点的方向d（设为-1）入栈；3. 当栈不空时循环执行下述操作：3.1 (x , y , d)<==栈顶元素出栈；3.2 求出下一个要试探的方向d++ ;3.3 沿顺时针试探每一个方向，执行下述操作：3.3.1 如果方向d可走，则3.3.1.1 将(x , y , d)入栈；3.3.1.2 求新点坐标(i, j)；3.3.1.3 将新点(i , j)切换为当前点(x , y)；3.3.1.4 若(x, y)是终点，则算法结束；否则，重置d=0；3.3.2 否则，试探下一个方向d++；3、抽签游戏1)问题描述抽签是我们日常生活中经常遇到的一件事，并且其形式有很多种。

这里介绍一种抽签游戏，如图3所示，最上面一排是游戏的参加者——称为抽签者，最下面一排是签号（奖品、公差等）。

每个人依次顺着竖线往下走，当碰到横线时，即转横向前进，碰到竖线再往下，以此类推，则游戏结束后，抽签者会一一对应到最下面一排的签号。

2. 基本要求(1) 设计存储结构存储抽签者、签号、游戏用横线、竖线等； (2) 设计算法实现抽签； (3) 存储游戏的最终结果。

3. 设计思想分析上面的抽签游戏的示例，遇到一条横线，代表这两个竖线的数据就要交换顺序，例如，原来的顺序为{A 0, A 1, A 2, A 3, A 4}，经过第0层横线后，顺序为{A 1, A 0, A 3, A 2, A 4}，再经过第1层横线后，顺序为{A 1,A 3,A 0,A 2,A 4}，以此类推，最后顺序为{A 4, A 1, A 0, A 2, A 3}，对应到{p 0, p 1, p 2, p 3, p 4}。

在该游戏中，需解决以下问题：(1) 抽签游戏可以多人参与，只要加上竖线和横线即可。

那么，如何表示这些参与者呢？ 解决：假设有n 个人参加，可以用一个一维数组A[n]来记录n 个抽签者。

(2) 签号如何存储？解决：签号的存储也可设计成一个一维数组p[n]来记录n 个签号。

(3) 如何存储游戏的最终结果？解决：设计一维数组B[n]存储最终的对应结果，同时在执行过程中记载中间结果。

(4) 当碰到某一横线跨在第i 条和第i +1条竖线上时，如何交换数据？解决：用一维数组B[n]来存放游戏过程中的中间结果和最终结果，通过交换B[i]和B[i+1]的值解决交换数据问题。

(5) 如何表示抽签游戏的竖线和横线布局？解决：设计一个二维数组M[m][n]，M[i][j]表示第i 层上第j 条和第j +1条竖线之间是否有横线，其值为0或1，1代表有横线，0代表没有横线。

图3所述示例对应的数组M 如图41 0 1 00 1 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 1算法设计要点如下：(1) 按从上到下、由左到右的方式遍历数组M ，若某元素值为1，则进行数据交换。

(2) 在数据交换的过程中，用一维数组B 来存放游戏过程中的顺序和最终的顺序，即： 如果M[i][j]=1，则B[j]←→B[j+1]； (3) 最后B[n]即为所求； 4、信号放大器 1) 问题描述天然气经过管道网络从其生产基地输送到消耗地，在传输过程中，其性能的某一个或几个方面可能会有所衰减（例如气压）。

为了保证信号衰减不超过容忍值，应在网络中的合适位置放置放大器以增加信号（例如电压）使其与源端相同。

设计算法确定把信号放大器放在何处，能使所用的放大器数目最少并且保证信号衰减不超过给定的容忍值。

2) 基本要求(1) 建立模型，设计数据结构； (2) 设计算法完成放大器的放置； (3) 分析算法的时间复杂度。

3) 设计思想为了简化问题，假设分布网络是二叉树结构，源端是树的根结点，信号从一个结点流向其孩子结点，树中的每一结点（除了根）表示一个可以用来放置放大器的位置。

图5是一个网络示意图，边上标出的是从父结点到子结点的信号衰减量。

对于网络中任一结点i ，设d (i )表示结点i 与其父结点间的衰减量，D (i )为从结点i 到结点i 的子树中任一叶子结点的衰减量的最大值，并有如下递推公式：在此公式中，要计算某结点的D 值，必须先计算其孩子结点的D 值，因而必须后序遍图5 网络分布示意图D (i )=0 若i 为叶结点D (i )= max{D (j ) + d (j )} 若i 不是叶结点且j 是i 的孩子历二叉树，当访问一个结点时，计算其D值。

例如，D(B)=max{D(D)+d(D)，D(E)}=4，若容忍值为3，则在B点或其祖先的任意一点放置放大器，并不能减少B与其后代的衰减量，必须在D点放置一个放大器或在其孩子结点放置一个或多个放大器。

若在结点D处放置一个放大器，则D(B)=2。

根据上述分析，设计如下存储结构：STRUCT ELEMENT{int D; // 该结点的衰减量int d; // 父结点的衰减量bool boost; //当且仅当本处设置放大器，则boost为true};struct BiNode{element data;BiNode *lchild,*rchild;};计算并放置放大器的伪代码为：1. D(i) = 0 ;2. for (i 的每个孩子j )2.1 如果D(j) +d(j)>容忍值，则在j处放置放大器;2.2 否则D(i) = max{D(i)，D(j) +d(j)} ;【思考题】本题假设分布网络是一棵二叉树结构，如果是树结构应如何设计算法？5、哈夫曼编码1) 问题描述设某编码系统共有n个字符，使用频率分别为{w1, w2,…, w n}，设计一个不等长的编码方案，使得该编码系统的空间效率最好。

2) 基本要求(1) 设计数据结构；(2) 设计编码算法；(3) 分析时间复杂度和空间复杂度。