2015版数据结构课程设计.docx

2015版数据结构课程设计

第一篇：2015版数据结构课程设计数据结构课程设计题目（2015年版）：（1-6题必做，做完9题以上可参评优秀）1、日程计划管理系统（必做）（线性表）[问题描述]设计一个程序，记录并管理日程计划。[基本要求]（1）日程计划信息包括日程计划ID号，日程计划开始日期和时间，日程计划结束日期和时间，日程计划名，日程计划参与人员，日程计划地点，日程计划提醒日期和时间。（2）采用双向循环链表表示日程计划信息。采用三个双向循环链表：第一个双向循环链表表示未开始的日程计划信息，按照日程计划开始日期和时间先后排序；第二个双向循环链表表示正在进行的日程计划信息（可以多项计划同时进行），按照日程计划开始日期和时间先后排序；第三个双向循环链表表示已过期的日程计划信息，按照日程计划开始的日期和时间倒序排序。（3）日程计划信息采用文件方式输入。日程计划信息信息示例如下，每条信息一行：日程计划ID号开始日期开始时间结束日期结束时间计划名„20141011001；2014-10-11；8:00:00;2014-10-11；10:00:00;数据结构上课；张三;6202；2014-10-11；7:40:00（4）要求模拟数据中日程计划信息至少30条以上。（5）实现以下功能：a.输入新的计划；b.根据当前时间查询未开始的计划，包括当天未开始的计划、本周或本月未开始的计划；c.查询并输出已结束的计划；d.查询正在进行的计划；e.根据当前时间，输出正提醒即将开始的计划。（6）可在此要求基础上进行功能扩展，比如周期性重复计划的设臵和提醒等。2、算术表达式求值(必做)（栈）[问题描述]一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正实数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。[基本要求]（1）从键盘或文件读入一个合法的算术表达式，输出正确的结果。（2）显示输入序列和栈的变化过程。（3）考虑算法的健壮性，当表达式错误时，要给出错误原因的提示。(4)实现非整数的处理（可选功能）。3、Huffman编码与解码(必做)（Huffman编码、二叉树）[问题描述]对一篇英文文章（大于2000个英文字符），统计各字符出现的次数，实现Huffman编码，以及对编码结果的解码。[基本要求]（1）输出每个字符出现的次数和编码，其中求最小权值要求用堆实现。（2）在Huffman编码后，要将编码表和英文文章编码结果保存到文件中，编码结果必须是二进制形式，即01的信息用比特位表示，不能用字符’0’和’1’表示。（3）提供读编码文件生成原文件的功能。4、关键路径问题（必做）（图）[问题描述]设计并实现关键路径的一种应用。[基本要求]（1）实现拓扑排序和关键路径的发现。（2）可根据自己兴趣，给出一个具体的应用情境，使得该题目成为一个实用软件。（3）结点数目至少在30个以上。建图数据从文件输入，便于检查。5、Hash表应用（必做）（查找）[问题描述]设计散列表实现身份证查找系统，对身份证号进行Hash。[基本要求]（1）设每个记录有下列数据项：身份证号码（虚构，位数和编码规则与真实一致即可）、姓名、地址。（2）从文件输入各记录，以身份证号码为关键字建立散列表。（3）分别采用开放定址（自行选择和设计定址方案）和链地址两种方案解决冲突；显示发生冲突的次数、每次中解决冲突进行重定位的次数。（4）查找并显示给定身份信息的记录。（5）记录条数至少在50条以上。6、排序算法比较（必做）（排序）[问题描述]利用随机函数产生N个随机整数（N=500，1000，1500，2000，2500，…,30000），利用直接插入排序、折半插入排序，起泡排序、快速排序、选择排序、堆排序，基数排序七种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间（即比较次数和交换次数）。[基本要求]（1）原始数据存在文件中，每个整数一行，方便读入。（2）屏幕显示每种排序所花的比较次数和交换次数。（3）给出已有序的整数（正序和倒序）上述方法的变化情况，显示在特例情况下的比较次数和交换次数。7、迷宫问题(选做)（栈与递归）[问题描述]利用栈操作实现迷宫问题求解。[基本要求]（1）随机生成模拟迷宫地图，不少于10行10列，存在文件中。（2）动态显示每一步的结果。（3）可在此基础上有改进方法。8、家谱管理系统（选做）（树）[问题描述]实现具有下列功能的家谱管理系统。[基本要求]（1）输入文件以存放最初家谱中各成员的信息，成员的信息中均应包含以下内容：姓名