长春工业大学人文信息学院。
数据结构是一门实践性很强的课程，只靠读书和做习题是不能提高实践能力的，尤其是在数据结构中要解决的问题更接近于实际。数据结构的课程设计是对学生的一种全面的综合训练，与程序设计语言课程中的课程设计不同，数据结构课程设计属于创造性的活动，需要学生自己进行问题分析、进行数据结构和算法的设计、再上机调试和测试程序。数据结构课程设计是一种自主性很强的学习过程，其教学目的主要有两个：
⑴ 深化理解和掌握书本上的理论知识，将书本上的知识变“活”；⑵理论和实践相结合，使学生学会如何把书本上有关数据结构和算法的知识用于解决实际问题，培养数据结构的应用能力和软件工程所需要的实践能力。
为了达到上述目的，本学期数据结构课程设计题目如下：
1．数组的循环移位。
2．约瑟夫环问题。
3．求二叉树中叶子结点的个数。
4．判断两棵二叉树是否相似。
5．信号放大器。
6．huffman编码。
7．机器调度问题。
8．医院选址问题。
9．简单个人**号码查询系统。
10．各种排序算法时间性能的比较。
11．机器调度问题。
1. 预备知识的学习。
需要学生在实验前复习实验所用的预备知识。这需要学生有自主的学习意识和整理知识的能力。
2. 上机前的准备。
将实现提示中给出的数据类型和算法转换为对应的程序，并进行静态检查，尽量减少语法错误和逻辑错误。上机前的充分准备能高效利用机时，在有限的时间内完成更多的实验内容。
3. 上机调试和测试程序。
调试程序是一个辛苦但充满乐趣的过程，也是培养程序员素质的一个重要环节。很多学生都有这样的经历：化了好长时间去调试程序，错误却越改越多。
究其原因，一方面，是对调试工具不熟悉，出现了错误提示却不知道这种错误是如何产生的；另一方面，没有认识到努力预先避免错误的重要性，也就是对程序进行静态检查。
对程序进行测试，首先需要设计测试数据。在数据结构中测试数据需要考虑两种情况：⑴ 一般情况：
例如循环的中间数据、随机产生的数据等；⑵ 特殊情况：例如循环的边界条件、数据结构的边界条件等。
4. 课程设计报告。
在课程设计完成相关题目后要总结和整理的报告。
1. 问题描述。
对于一个给定的整型数组循环右移i位。
2. 基本要求。
⑴ 在原数组中实现循环右移，不另外申请空间；
⑵ 时间性能尽可能好；
⑶ 分析算法的时间复杂度。
3. 设计思想。
将这个问题看作是把数组ab转换成数组ba（a代表数组的前i个元素，b代表数组中余下的n-i个元素），先将a逆置得到arb，再将b逆置得到arbr，最后将整个arbr逆置得到(arbr)r=ba。设reverse函数执行将数组元素逆置的操作，对abcdefgh向左循环移动3个位置的过程如下：
reverse(0, i-1); 得到cbadefgh
reverse(i, n-1); 得到cbahgfed
reverse(0, n-1); 得到defghabc
具体分析过程请参见主教材第一章思想火花。
4. 算法描述。
1. 问题描述。
设有编号为1，2，……n的n(n>0)个人围成一个圈，每个人持有一个密码m，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。
2. 基本要求。
建立模型，确定存储结构；
对任意n个人，密码为m，实现约瑟夫环问题；
出圈的顺序可以依次输出，也可以用一个数组存储。
3. 设计思想。
首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型：
struct node
int data; /编号。
node *next;
其次，建立一个不带头结点的循环链表并由头指针first指示。具体算法请参见2.1.2自行设计。
最后，设计约瑟夫环问题的算法。下面给出伪**描述，操作示意图如图2-1所示。
1. 问题描述。
已知一棵二叉树，求该二叉树中叶子结点的个数。
2. 基本要求。
⑴ 采用二叉链表作存储结构；
设计递归算法求叶子结点的个数。
3. 设计思想。
求二叉树中叶子结点的个数，即求二叉树的所有结点中左、右子树均为空的结点个数之和。因此可以将此问题转化为遍历问题，在遍历中“访问一个结点”时判断该结点是不是叶子，若是则将计数器累加。算法如下：
1. 问题描述。
设计算法判断给定的两棵二叉树是否相似。
两棵二叉树当且仅当满足以下条件，称这两棵二叉树是相似的：
他们都为空或都只有一个根结点；
他们的左右子树也相似。
2. 基本要求。
采用二叉链表作存储结构；
设计递归算法判断两棵二叉树是否相似。
3. 设计思想。
由二叉树相似的定义，得到如下判定两棵二叉树s和t是否相似的递归函数like：
若s=t=null，则s和t相似，即like(s, t)=1;
若s和t中有一个为null，另一个不为null，则s和t不相似，即like(s, t)=0;
进一步判断s的左子树和t的左子树、s的右子树和t的右子树是否相似。
具体算法如下：
1. 问题描述。
天然气经过管道网络从其生产基地输送到消耗地，在传输过程中，其性能的某一个或几个方面可能会有所衰减（例如气压）。为了保证信号衰减不超过容忍值，应在网络中的合适位置放置放大器以增加信号（例如电压）使其与源端相同。设计算法确定把信号放大器放在何处，能使所用的放大器数目最少并且保证信号衰减不超过给定的容忍值。
2. 基本要求。
建立模型，设计数据结构；
设计算法完成放大器的放置；
分析算法的时间复杂度。
3. 设计思想。
为了简化问题，假设分布网络是二叉树结构，源端是树的根结点，信号从一个结点流向其孩子结点，树中的每一结点（除了根）表示一个可以用来放置放大器的位置。如下图是一个网络示意图，边上标出的是从父结点到子结点的信号衰减量。
对于网络中任一结点i，设d(i)表示结点i与其父结点间的衰减量，d(i)为从结点i到结点i的子树中任一叶子结点的衰减量的最大值，并有如下递推公式：
在此公式中，要计算某结点的d值，必须先计算其孩子结点的d值，因而必须后序遍历二叉树，当访问一个结点时，计算其d值。
例如，d(b)=max=4，若容忍值为3，则在b点或其祖先的任意一点放置放大器，并不能减少b与其后代的衰减量，必须在d点放置一个放大器或在其孩子结点放置一个或多个放大器。若在结点d 处放置一个放大器，则d(b)=2。
根据上述分析，设计如下存储结构：
struct element
struct binode
计算并放置放大器的伪**为：
1. 问题描述。
设某编码系统共有n个字符，使用频率分别为，设计一个不等长的编码方案，使得该编码系统的空间效率最好。
2. 基本要求。
设计数据结构；
设计编码算法；
分析时间复杂度和空间复杂度。
3. 设计思想。
利用huffman编码树求得最佳的编码方案。
根据哈夫曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个结构型的一维数组hufftree，保存哈夫曼树中各结点的信息，每个结点包括：权值、左孩子、右孩子、双亲，如下图所示。由于哈夫曼树中共有2n-1个结点，并且进行n-1次合并操作，所以该数组的长度为2n-1。
构造哈夫曼树的伪**如下：
在哈夫曼树中，设左分支为0，右分支为1，从根结点出发，遍历整棵哈夫曼树，求得各个叶子结点所表示字符的哈夫曼编码。
1. 问题描述。
所谓tsp问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。
2. 基本要求。
上网查找tsp问题的应用实例；
分析求tsp问题的全局最优解的时间复杂度；
设计一个求近似解的算法；
分析算法的时间复杂度。
3. 设计思想。
对于tsp问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅行路线，从中选择最佳的一条。但是用穷举法求解tsp问题的时间复杂度为ο(n!)，当n大到一定程度后是不可解的。
本实验只要求近似解，可以采用贪心法求解：任意选择某个城市作为出发点，然后前往最近的未访问的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。
为便于查找离某顶点最近的邻接点，可以采用邻接矩阵存储该图。算法用伪**描述如下：
1. 问题描述。
n个村庄之间的交通图可以用有向网图来表示，图中边上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？
2. 基本要求。
建立模型，设计存储结构；
设计算法完成问题求解；
分析算法的时间复杂度。
3. 设计思想。
医院选址问题实际是求有向图中心点的问题。首先定义顶点的偏心度。
设图g=（v，e），对任一顶点k，称e(k)=max（i∈v）为顶点k的偏心度。显然，偏心度最小的顶点即为图g的中心点。
如图6-2(a)所示是一个带权有向图，其各顶点的偏心度如图(b)所示。
医院选址问题的算法用伪**描述如下：
1. 问题描述。
人们在日常生活中经常需要查找某个人或某个单位的**号码，本实验将实现一个简单的个人**号码查询系统，根据用户输入的信息（例如姓名等）进行快速查询。
数据结构课程设计指导书
数据结构。课。程。设。计。指。导。书。目录。一 课程设计的基本任务3 二 课程设计的基本要求3 三 课程设计的基本步骤和方法4 四 课程设计说明书 含报告的书写规范5 五 附录 课程设计大纲等内容13 一 课程设计的基本任务。数据结构是一门涉及多门课程的课程，难度较大，需要较好的c语言的程序设计和调...
数据结构课程设计指导书
数据结构。课。程。设。计。指。导。书。一 课程设计的基本任务3 二 课程设计的基本要求3 三 课程设计的基本步骤和方法4 四 课程设计说明书 含报告的书写规范5 五 附录 课程设计大纲等内容13 一 课程设计的基本任务。数据结构是一门涉及多门课程的课程，难度较大，需要较好的c语言的程序设计和调试能力...
数据结构课程设计指导书
指导书。信息工程学院计算机科学与技术专业。2013年12月。数据结构课程设计 指导书。一 课程设计题目与要求。根据课程设计题目规模，要求每个题目3人一组。分组规则如下 按照学号顺序每3人编为一组 或者自由组合 一经确定不得随意调换，题目由各组选派代表抽签确定，设计题目不得更换。选题一 教学计划编制问...