数据结构课程设计说明
肖波
xiaobo@
一、时间说明
本学期到下学期五一之前完成即可。期间如果提前完成，随时可以发邮件给老师联系验收（教三楼803房间，Tel:62283059-1007）。
二、课程设计验收说明
验收时提交源程序、报告电子版和打印后的纸板，最终成绩按优/良/中/及格/不及格形式给出。
设计报告封面必须按照附录后的模版填写。报告内容应包含问题描述；分析、设计、实现；运行结果分析、总结等。
每个题目允许最多2人一组合作完成。实验报告只写一份即可。但每人的分工必须在报告中如实阐述清楚。最后的总结及个人心得最好每人单独撰写。小组中每人成绩相同，若小组中某成员工作量非常小，也会影响小组的成绩。
三、题目
题目共计7个，可任选1个。
题目一 动态内存管理
动态内存管理是操作系统的基本功能之一，其作用是响应用户程序对内存的申请和释放请求。用户程序根据所需要的容量向系统申请内存空间。内存使用完后通知系统进行回收。如C语言使用malloc函数和free函数实现内存的申请和释放，C++语言使用new和delete操作符实现内存的申请和释放。
教材2.5.2节详述了动态内存管理的实现，请编写程序实现并进行测试。
题目二 优先队列调度算法设计
完成课本3.4.2节的优先队列调度算法.
题目三 快速串查找操作
串查找算法除了BF算法外，还有KMP算法或BM算法等，试实现这两种算法之一或全部实现。
题目四 BMP文件操作类库设计
Bmp文件是我们经常使用的图像文件格式，课本4.4.1节介绍了其结构，并给出了简单的类库设计。试实现该类库，并完成一些简单的图像处理操作，如4.4.2节的平滑，课本140页的灰度变换等。
题目五 背包问题求解算法
课本110页最后一道习题给出了最简单的背包问题。求解方法在课后答案中已经给出。若不存在解，也可找到最接近背包可承载的最大质量S但不超过S的解。试编写一个Windows小软件，界面输入背包可承载的最大质量上限S，以及所有的物品质量（可用空格隔开）后，软件给出存在的一个（或多个）解。
题目六 排序算法时间性能比较
说明：实现所有课本上讲解的较快的4种内部排序算法。通过界面允许使用者设定排序数个数N(N可以很大，如100000)，自动随机产生N个数，然后依次使用各个算法进行排序，并记录每个排序所使用的平均时间，按时间由小到大将各个排序名称进行排序。将N及按用时排序后的排序名称和其用时追加到日志中，供日后分析。同时，对其用时和课本上的算法复杂度分析进行比较。并与STL中的sort函数进行比较。
所有的排序算法集成到1个类中：
template <class T>
class Sort{ public:
Sort ( int * a, int n, int sorttype); //唯一接口 private:
……
};
构造函数Sort ( T * a, int n, int sorttype)的说明：
第一个参数a，存放待排序的数据，假设数据为简单数据类型。构造函数执行完后，即将a中的所有数据排好序了。最终结果仍然存储在a所指向的内存中。
第二个参数n，表示待排序的数据的个数
第三个参数 sorttype, 表示排序类型，sorttype =0为STL中的sort函数排序，sorttype =1为希尔排序，sorttype =2为快速排序，sorttype =3为堆排序，sorttype =4为归并排序。
测试程序使用VC++开发，测试程序中使用Sort类的对象，N可取多个不同数量级的值，对每个N值，每种算法要执行10次，取其平均排序时间、平均移动次数以及平均比较次数。
最后可利用辅助软件（如FindGraph软件包）给出图示。例：
题目七 智力游戏求解算法
中国的华容道、起源于匈牙利的魔方以及起源于法国的独立钻石棋并称为智力游戏界的三个不可思议。互联网上对于这三种游戏的设计算法也很多。
华容道游戏
华容道的初始状态有很多，建议选择比较流行的一种，俗称横刀立马。如下：
图中棋子共10个，滑动棋子，把曹操移正下方出口。日本藤村幸三朗曾在《数理科学》杂志上发表华容道基本布局的最少步法为85步。后来清水达雄找出更少的步法为83步。美国著名数学家马丁·加德纳又进一步把它减少为81步。此后，至今还未曾见到打破这一记录的报道。
魔方游戏
魔方是给定一种混乱状态，通过转动不同的6个面，最后实现每个面上的颜色相同。如图所示：
使用计算机求解目前最快平均20步就可以了，而人类操作最快的也需要50多步。世界上最快的人9.77秒就可以还原一个魔方（记录创造于20xx年10月13日的荷兰公开赛），记录保持者是来自荷兰的Erik Akkersdijk。
独立钻石棋
独立钻石棋游戏玩法如跳棋，但不能走步，只能跳。棋盘图a所示。
开始时，除中心单元格外将每个单元格放置一个旗子。共放置32个棋子。如图b所示。
a图 b图
开始走棋时，棋子跳过相邻的棋子到空位上，并且把跳过的棋子吃掉。棋沿棋盘的格线横跳、纵跳，但是不能斜跳，直到最后剩下一个棋子才算胜利。
评判独立钻石水平的级别是：最后剩下5只棋子——颇好；剩下4只棋子——很好；剩下3只棋子——聪明；剩下2只棋子——尖子；剩下1只棋子——大师；最后剩下1只，而且在正中央——天才。试一试你的程序执行完后会胜几个棋子。
在19xx年以前，人们都以为要取得天才最少是要跳23步（连跳作一步计）。但在19xx年都丹尼把纪录提高到19步；而在19xx年布荷特创下了18次的世界纪录！这纪录后来由英国剑桥大学的比斯尼教授从数学上证明为绝对的世界纪录。换句话说，要取得天才，最少需要18步才可。19xx年，在上海举行的独立钻石徵解赛中，中国女工万萍萍，找到另一种不同於布荷特的18步取得天才的方法。后来上海计算机研究所开动了大型的计算机，希望找出用18步取得天才的各种方法，结果得出令人惊异的答案：独立钻石以18步取得天才的方法只有两种，一种是布荷特的，另一种便是万萍萍的。 设计要求
试选择任意一款游戏，实现其解决算法。如果能实现其GUI界面则更好。可参考互
联网上的各种算法。
附录：课程设计报告封面
北京邮电大学课程设计报告
第二篇：数据结构课程设计题目
数据结构课程设计题目（2009级）
1. 通信录管理系统
任务：以单链表存储通信录中的人员信息，包括bianhao 、姓名、性别、电话、地址，通过此系统可以实现如下功能：
（1）通信录链表的建立；
（2）人员记录的插入；
（3）人员记录的查询；
（4）人员记录的删除；
（5）人员记录的输出。
要求：根据以上任务说明，设计程序完成功能。
2．个人帐簿管理系统设计
任务： 个人帐簿管理系统记录某人每月的全部收入及各项开支情况，包括食品消费，房租，子女教育费用，水电费，医疗费，储蓄等。进入系统后可以输入和修改某月的收支情况，可以对每月的开支从小到大进行排序，可以根据输入的月份查询每月的收支情况。 要求：根据以上任务说明，设计数据结构，并设计程序完成功能。
3．约瑟夫环问题
任务：设编号为1，2，3，??，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。
要求：根据以上任务说明，设计数据结构，并设计程序完成功能。
4. 利用栈求表达式的值
任务：建立试题库文件，随机产生n个题目；题目涉及加减乘除，带括号的整数混合运算；随时可以退出；保留历史分数，能回顾历史，给出与历史分数比较后的评价。（假设这是一个可供小学生练习算术运算的小系统）
要求：根据以上任务说明，设计程序完成功能。
5．简化的0/1背包问题的求解
任务：假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , ? , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + ? + wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2）、（1，4，5）、（8，2）、（3，5，2）。
要求：根据以上任务说明，设计数据结构，并设计程序完成功能。
6. 一元多项式计算
任务：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输出。
要求：根据以上任务说明，设计数据结构，并设计程序完成功能。
7. 文本处理
任务：设文本信息（包括英文字母、数字、空格、括号及其他符号）存储于一个文本文件中，编写程序统计出其中英文字母、数字、空格的个数。要求：
（1）分别统计出其中英文字母数和空格数及整篇文章总符号数；
（2）统计指定的字符串在文章中出现的次数，并输出；
（3）删除指定的字符串，并将后面的字符前移。
提示：设文本文件中的信息按行存储，每行最多不超过80个字符，共N行；使用线性表，逐行从文件中读取字符信息到线性表中，分别用几个子函数实现相应的功能。
8. 二叉树的中序、前序、后序的递归、非递归遍历算法，应包含建树的实现。
任务：设计一个程序，实现二叉树的前序、中序、后序的递归、非递归遍历运算。 要求：
（1）创建二叉树；
（2）二叉树的前序、中序、后序的递归遍历运算实现；
（3）二叉树的前序、中序、后序的非递归遍历运算实现。
9. Huffman编码/译码器
任务：设计一个利用哈夫曼算法的编码和译码系统。
要求：建立一个文本文件，统计该文件中各字符频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成原文件。
“压缩文件”即：读文件、统计文件中的字符个数、对文件进行哈夫曼编码和译码、并将编码译码后的字符存储在文件中。
根据以上任务说明，设计数据结构，并设计程序完成功能。
10. 校园导航问题
设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。
11. 散列表的设计与实现
任务:设计散列表实现电话号码查找系统。
要求:
(1) 设每个记录有下列数据项：电话号码、用户名、地址；
(2) 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；
(3) 采用一定的方法解决冲突；
(4) 查找并显示给定电话号码的记录；
(5) 查找并显示给定用户名的记录。
12. 排序综合
任务：利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。 要求：
（1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。
（2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。
备注：鼓励同学自选设计题目，各位同学可以自选一些有一定难度、有一定工作量、有一定实用意义的课题。但注意，自选课题不得超过2题。