数据结构课程设计2013

《数据结构课程设计2013》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计题目（2013年）一、必做题1、图书管理系统（线性表）[问题描述]　　设计一个程序，记录并统计图书使用情况。[基本要求]（1）图书信息包括图书ID号，图书名，出版社名，出版年月，馆藏册数。（2）学生信息包括学号，姓名，班级，在借册数，已还册数，违约次数。（3）借阅信息包括图书ID号，图书名，学号，姓名，借阅日期，应还日期，归还日期。（4）采用顺序存储线性表表示图书信息。采用链式存储线性表表示学生信息。采用双向循环链表表示借阅信息。其中一个双向循环链表表示在借的借阅信息，按照图书ID

2、号非递减排序；另一个双向循环链表表示已还的借阅信息，按照图书ID号非递减排序。（5）图书信息，学生信息、借阅信息采用文件方式输入。图书信息示例如下，每条信息一行：16000001数据结构清华大学出版社2012.1030学生信息示例如下，每条信息一行：161340106张三1613401510借阅信息示例如下，每条信息一行：标志位1（1表示借阅2表示归还）16000001数据结构161340106张三2013.9.12（借阅时表示借阅日期，应还日期自动生成，根据借阅日期+60天；归还时表示归还日期，

3、归还日期要在借阅日期之后，应还日期之前，如果超过应还日期，则记录一次违约次数）。例如借阅：116000001数据结构161340106张三2013.9.12归还：216000001数据结构161340106张三2013.10.20（6）规定每位学生不能同时借阅同一本书两本及以上。图书归还后，将该条借阅信息从借阅链表中转移到归还链表中。（7）要求模拟数据中图书信息至少30本以上，学生信息至少20条以上，借阅信息至少50条以上。（8）能够统计每一本图书被借阅次数（已还），在借册数。查询每一位学生的借阅

4、历史明细记录。统计学生平均借阅次数，最大借阅次数，最少借阅次数。（9）可在此要求基础上进行功能扩展。2、算术表达式求值（栈）[问题描述]　　一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正实数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。[基本要求]（1）从键盘或文件读入一个合法

5、的算术表达式，输出正确的结果。（2）显示输入序列和栈的变化过程。（3）考虑算法的健壮性，当表达式错误时，要给出错误原因的提示。3、二叉树的应用（二叉树）[问题描述]编程实现二叉树的建立，先序、中序、后序（递归和非递归方法）、层序遍历，二叉树的高度、繁茂度，交换左右子树，统计叶子节点的数目，判断是否为完全二叉树，按树的形态在屏幕上打印输出。[基本要求]（1）从文件中读入建树信息，树的节点数目不小于20个，树的高度不小于4。（2）建树信息采用两行英文字符表示，每个英文字符代表一个结点，第1行为树的中序

6、遍历结果，第2行为树的后序遍历结果。4、Huffman编码与解码（Huffman编码、二叉树）[问题描述]对一篇英文文章（大于2000个英文字符），统计各字符出现的次数，实现Huffman编码，以及对编码结果的解码。[基本要求]（1）输出每个字符出现的次数和编码，其中求最小权值要求用堆实现。（2）在Huffman编码后，要将编码表和英文文章编码结果保存到文件中，编码结果必须是二进制形式，即01的信息用比特位表示，不能用字符’0’和’1’表示。（3）提供读编码文件生成原文件的功能。5、关键路径问题（

7、图）[问题描述]设计并实现关键路径的一种应用。[基本要求]（1）实现拓扑排序和关键路径的发现。（2）给出一个具体的应用环境。6、排序算法比较（排序）[问题描述]利用随机函数产生10个样本（其中之一已为正序，之一为倒序），每个样本有20000随机整数，利用直接插入排序、希尔排序，冒泡排序、快速排序、选择排序、堆排序，归并排序（递归和非递归），基数排序八种排序方法进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的平均时间[基本要求]（1）原始数据存在文件中，每个整数一行，方便读入。（2）屏幕显

8、示每种排序所花的比较次数。二、选做题1、迷宫问题（栈与递归）[问题描述]利用栈操作实现迷宫问题求解。[基本要求]（1）随机生成模拟迷宫地图，不少于10行10列，存在文件中。（2）动态显示每一步的结果。（3）可在此基础上有改进方法。2、家谱管理系统（树）[问题描述]实现具有下列功能的家谱管理系统[基本要求]（1）输入文件以存放最初家谱中各成员的信息，成员的信息中均应包含以下内容：姓名、出生日期、婚否、地址、健在否、死亡日期（若其已死亡），也可附加其它信息、但不是必需的。（2）实现数据