数据结构课程设计题目(2013 年版):
(1-6 题必做, 做完 9 题以上并演示答辩参评优秀)
1、图书管理系统(必做)(线性表)
[问题描述]
设计一个程序,记录并统计图书使用情况。
[基本要求]
(1)图书信息包括图书 ID 号,图书名,出版社名,出版年月,馆藏册数。
(2)学生信息包括学号,姓名,班级,在借册数,已还册数,违约次数。
(3)借阅信息包括图书 ID 号,图书名,学号,姓名,借阅日期,应还日期,归还日
期。
(4)采用顺序存储线性表表示图书信息。采用顺序存储线性表表示学生信息。采用双
向循环链表表示借阅信息 。其中一个双向循环链表表示在借的借阅信息,按照图书 ID
号非递减排序;另一个双向循环链表表示已还的借阅信息,按照图书 ID 号非递减排序。
(5)图书信息,学生信息、借阅信息采用文件方式输入。
图书信息示例如下,每条信息一行:
16000001 数据结构 清华大学出版社 2012.10
学生信息示例如下,每条信息一行:
161340106 张三 1613401
10
借阅信息示例如下,每条信息一行:
标志位 1(1 表示借阅 2 表示归还) 16000001 数据结构 161340106 张三
2013.9.12 (借阅时表示借阅日期,应还日期自动生成,根据借阅日期+60 天; 归还
时表示归还日期, 归还日期要在借阅日期之后,应还日期之前,如果超过应还日期,
则记录一次违约次数)。
30
5
例如借阅: 1 16000001 数据结构 161340106 张三 2013.9.12
归还: 2 16000001 数据结构 161340106 张三 2013.10.20
(6)规定每位学生不能同时借阅同一本书两本及以上。图书归还后,将该条借阅信息
从借阅链表中转移到归还链表中。
(7)要求模拟数据中图书信息至少 30 本以上,学生信息至少 20 条以上,借阅信息至
少 50 条以上。
(8)能够统计每一本图书被借阅次数(已还),在借册数。查询每一位学生的借阅历
史明细记录。统计学生平均借阅次数,最大借阅次数,最少借阅次数。
(9)可在此要求基础上进行功能扩展。
2、算术表达式求值 (必做) (栈)
[问题描述]
一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)
组成的。假设操作数是正实数,运算符只含加减乘除等四种运算符,界限符有左右括
号和表达式起始、结束符“#”,如:#(7+15)*(23-28/4)#。引入表达式起始、结
束符是为了方便。编程利用“算符优先法”求算术表达式的值。
[基本要求]
(1) 从键盘或文件读入一个合法的算术表达式,输出正确的结果。
(2) 显示输入序列和栈的变化过程。
(3) 考虑算法的健壮性,当表达式错误时,要给出错误原因的提示。
3、二叉树的应用 (必做)(二叉树)
[问题描述]
编程实现二叉树的建立,先序、中序、后序、层序遍历(递归和非递归方法),二
叉树的高度、繁茂度,交换左右子树,统计叶子节点的数目,判断是否为完全二叉树,
按树的形态在屏幕上打印输出。
[基本要求]
(1) 从文件中读入建树信息,树的节点数目不小于 20 个,树的高度不小于 4。
(2) 建树信息采用两行英文字符表示,每个英文字符代表一个结点,第 1 行为树的
中序遍历结果,第 2 行为树的后序遍历结果。
4、Huffman 编码与解码 (必做)(Huffman 编码、二叉树)
[问题描述]
对一篇英文文章(大于 2000 个英文字符),统计各字符出现的次数,实现 Huffman
编码,以及对编码结果的解码。
[基本要求]
(1) 输出每个字符出现的次数和编码,其中求最小权值要求用堆实现。
(2) 在 Huffman 编码后,要将编码表和英文文章编码结果保存到文件中,编码结果
必须是二进制形式,即 0 1 的信息用比特位表示,不能用字符’0’和’1’表示。
(3) 提供读编码文件生成原文件的功能。
5、关键路径问题 (必做) (图)
[问题描述]
设计并实现关键路径的一种应用。
[基本要求]
(1)实现拓扑排序和关键路径的发现。
(2)给出一个具体的应用环境。
6、排序算法比较 (必做)(排序)
[问题描述]
利用随机函数产生 N 个随机整数(N = 500,1000,1500,2000,2500,…,30000),
利用直接插入排序、折半插入排序,起泡排序、快速排序、选择排序、堆排序,基数
排序七种排序方法(可添加其它排序方法)进行排序(结果为由小到大的顺序),并统
计每一种排序所耗费的时间(即比较次数)。
[基本要求]
(1) 原始数据存在文件中,每个整数一行,方便读入。
(2) 屏幕显示每种排序所花的比较次数。
7、迷宫问题 (选做)(栈与递归)
[问题描述]
利用栈操作实现迷宫问题求解。
[基本要求]
(1)随机生成模拟迷宫地图,不少于 10 行 10 列,存在文件中。
(2)动态显示每一步的结果 。
(3)可在此基础上有改进方法。
8、家谱管理系统(选做) (树)
[问题描述]
实现具有下列功能的家谱管理系统
[基本要求]
(1)输入文件以存放最初家谱中各成员的信息,成员的信息中均应包含以下内容:姓
名、出生日期、婚否、地址、健在否、死亡日期(若其已死亡),也可附加其它信息、
但不是必需的。
(2)实现数据的存盘和读盘。
(3)以图形方式显示家谱。
(4)显示第 n 代所有人的信息。
(5)按照姓名查询,输出成员信息(包括其本人、父亲、孩子的信息)。
(6)按照出生日期查询成员名单。
(7)输入两人姓名,确定其关系。
(8)某成员添加孩子。
(9)删除某成员(若其还有后代,则一并删除)。
(10)修改某成员信息。
(11)按出生日期对家谱中所有人排序。
(12)打开一家谱时,提示当天生日的健在成员。
(13)要求建立至少 30 个成员的数据,以较为直观的方式显示结果,并提供文稿形式
以便检查。
(14)界面要求:有合理的提示,每个功能可以设立菜单,根据提示,可以完成相关
的功能要求。
(15)存储结构:根据系统功能要求自行设计,但是要求相关数据要存储在数据文件
中。测试数据:要求使用 1、全部合法数据;2、局部非法数据。进行程序测试,以保
证程序的稳定。
9、公交线路提示 (选做) (图)
[问题描述]
建立南京主要公交线路图。
[基本要求]
(1)输入任意两站点,给出最佳的乘车线路和转车地点。
注:路线信息网址:http://www.njkgc.cn/ 上有最新的公交线路信息
10、 社交网络图实现(选做) (图)
[问题描述]
设计并实现一种简单的社交网络模型图。
[基本要求]
(1) 每个人的信息是一个结点,人与人的联系构成边。个人信息里要有地理坐标信
息,以便后续应用中能方便找靠近的人。
(2) 根据输入的任意两个人信息,给出他们之间的联系路径,最少经过多少人构成
联系。
(3) 根据位置信息的动态变化,找寻附近能够联络的人,能够通过 1 次中间人能联
络的人等。
(4)模拟仿真结点的联络密切程度,根据联络密切程度发现社交网络中的小团体。
(5)可根据自己的创意添加更多的功能。
成绩评定细则:
1. 正确性:程序是否可以运行,结果是否正确(20 分)
2. 功能的完备性:是否实现要求的所有子功能(40 分)
3. 课程设计报告中的算法说明的清晰程度,课程设计报告中总结的深刻程度(20 分)
4. 独立完成情况( 40 分)
总计:100 分
加分项目:
1.健壮性:异常处理的情况
2.可读性:代码编写是否规范,是否便于阅读。如函数、变量命名,‘{ }’的缩进,
关键位置适量注释等
3.功能的完善:除要求实现的功能外,完成了其它的功能,实现了功能的完善
4.界面的设计:可视化界面,或者交互良好的 DOS 界面
编程语言:C、C++ 或 JAVA 任选其一
检查方式:
1. 总体上检查程序的代码量,正确性,可读性,健壮性,功能的完备性,代码量,程
序的结构是否合理;局部检查三个以上函数块
2. 检查程序时同时检查课程设计报告的电子文档
3. 检查时间:每个学生的检查时间 10 分钟
时间安排:
1 上机时间安排
2 课程设计报告上交时间
3 课程设计检查时间
课程设计报告要求:
1.所有的课程设计报告,均要有封面,包括:课题名称、班级、学号、学生姓名、成
绩和指导教师;
2.给出自己采用的数据结构;
3.给出算法设计思想;
4.给出实现的源程序,并在必要的代码处给出注释;
5.给出测试数据和结果;
6.给出算法的时间复杂度、另外可以提出算法的改进方法;
7.给出结束语:说明完成课程设计的情况,心得体会;课程设计报告的电子文档在上
机检查程序时一并检查;书面文档在指定的时间内上交。