数据结构课设报告

1、 数据结构课程设计报告班级：1613301学号：161330135姓名：王思凡成绩：指导老师：高航1 日程计划管理系统 问题描述设计一个程序，记录并管理日程计划。基本要求（1）日程计划信息包括日程计划ID号，日程计划开始日期和时间，日程计划结束日期和时间，日程计划名，日程计划参与人员，日程计划地点，日程计划提醒日期和时间。（2）采用双向循环链表表示日程计划信息。采用三个双向循环链表：第一个双向循环链表表示未开始的日程计划信息，按照日程计划开始日期和时间先后排序；第二个双向循环链表表示正在进行的日程计划信息（可以多项计划同时进行），按照日程计划开始日期和时间先后排序；第三个双向循环链表表示已过期

2、的日程计划信息，按照日程计划开始的日期和时间倒序排序。（3）日程计划信息采用文件方式输入。日程计划信息信息示例如下，每条信息一行：日程计划ID号 开始日期 开始时间 结束日期 结束时间 计划名 20141011001；2014-10-11；8:00:00; 2014-10-11；10:00:00;数据结构上课；张三; 6202；2014-10-11；7:40:00数据结构：struct Date/日期int year,month,day;struct Time/时间int hour,minute,second;struct Data/存储的数据结构char ID20;Date startDat

3、e,endDate,remindDate;Time startTime,endTime,remindTime;char planeName20;char personName20;char place50;算法思想：用了一共4个双向链表，其中3个是题目要求的链表，还有一个是包括所有提醒的链表，根据当前时间分成3个链表，链表是插入时自动排序的。程序截图：2、算术表达式求值（栈）问题描述一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正实数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7

4、+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。基本要求（1） 从键盘或文件读入一个合法的算术表达式，输出正确的结果。（2） 显示输入序列和栈的变化过程。（3） 考虑算法的健壮性，当表达式错误时，要给出错误原因的提示。数据结构：顺序栈。算法思想：对于一个算术表达式，从左到右运算。首先先给每个运算符附上优先级，当遇到数字时，将数字进入数字栈，如果遇到运算符，使其与运算符栈的栈顶运算符进行优先级比较，若优先级小于栈内运算符，则该运算符进栈。否则，栈顶运算符出栈，同时数字栈出栈两个数字使其运算。将结果入栈，这样重复，直到运算结束，得到结果。3

5、、Huffman编码与解码（Huffman编码、二叉树）问题描述对一篇英文文章（大于2000个英文字符），统计各字符出现的次数，实现Huffman编码，以及对编码结果的解码。基本要求（1） 输出每个字符出现的次数和编码，其中求最小权值要求用堆实现。（2） 在Huffman编码后，要将编码表和英文文章编码结果保存到文件中，编码结果必须是二进制形式，即0 1的信息用比特位表示，不能用字符0和1表示。（3） 提供读编码文件生成原文件的功能。算法思想：通过树形的逻辑结构，以二叉树的结点进行编码，左孩子编码为0，右孩子编码为1。建立以二叉树节点为数据的小根堆从堆中找两个最小的数据，作为其孩子，其权重为两

6、个孩子之和，插入小根堆。这样操作，直到小根堆只剩一个节点。读取哈夫曼文件时一位一位读取，开始指针指向哈夫曼树的根节点，读到0走左，读到1走右，直到到叶子节点，输出叶子节点的值。4、关键路径问题 （图）问题描述设计并实现关键路径的一种应用。基本要求（1）实现拓扑排序和关键路径的发现。（2）可根据自己兴趣，给出一个具体的应用情境，使得该题目成为一个实用软件。（3）结点数目至少在30个以上。建图数据从文件输入，便于检查。5、Hash表应用（查找）问题描述设计散列表实现身份证查找系统，对身份证号进行Hash。 基本要求（1） 设每个记录有下列数据项：身份证号码（虚构，位数和编码规则与真实一致即可）、姓

7、名、地址。 （2） 从文件输入各记录，以身份证号码为关键字建立散列表。 （3） 分别采用开放定址（自行选择和设计定址方案）和链地址两种方案解决冲突；显示发生冲突的次数、每次中解决冲突进行重定位的次数。（4） 查找并显示给定身份信息的记录。（5） 记录条数至少在50条以上。6、排序算法比较 （必做）（排序）问题描述利用随机函数产生10个样本（其中之一已为正序，之一为倒序），每个样本有20000随机整数，利用直接插入排序、希尔排序，冒泡排序、快速排序、选择排序、堆排序，归并排序（递归和非递归），基数排序八种排序方法进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的平均时间7、迷宫问题 （栈与递归）问题描述利用栈操作实现迷宫问题求解。基本要求（1）随机生成模拟迷宫地图，不少于10行10列，存在文件中。（2）动态显示每一步的结果 。宽搜演示：深搜演示：14、编写“连连看”程序。算法思想：两个方块直接能否相连的标准是能否用