数据结构课设报告汇编.doc

数据结构 课程设计报告 班级：1613301 学号：161330135 姓名：王思凡 成绩： 指导老师：高航 日程计划管理系统 [问题描述]。[基本要求] （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 struct Date //日期 { int year,month,day; }; struct Time //时间 { int hour,minute,second; ; struct Data //存储的数据结构 { char ID[20]; Date startDate,endDate,remindDate; Time startTime,endTime,remindTime; char planeName[20]; char personName[20]; char place[50]; }; 用了一共4个双向链表，其中3个是题目要求的链表，还有一个是包括所有提醒的链表，根据当前时间分成3个链表，链表是插入时自动排序的。 程序截图： 2、算术表达式求值（栈） [问题描述]一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正实数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。[基本要求]（1） 从键盘或文件读入一个合法的算术表达式，输出正确的结果。（2） 显示输入序列和栈的变化过程。 （3） 考虑算法的健壮性，当表达式错误时，要给出错误原因的提示。 3、Huffman编码与解码（Huffman编码、二叉树） [问题描述[基本要求]’0’和’1’表示。 （3） 提供读编码文件生成原文件的功能。 算法思想： 通过树形的逻辑结构，以二叉树的结点进行编码，左孩子编码为‘0’，右孩子编码为‘1’。建立以二叉树节点为数据的小根堆从堆中找两个最小的数据，作为其孩子，其权重为两个孩子之和，插入小根堆。这样操作，直到小根堆只剩一个节点。读取哈夫曼文件时一位一位读取，开始指针指向哈夫曼树的根节点，读到0走左，读到1走右，直到到叶子节点，输出叶子节点的值。 4、关键路径问题 （图） [问题描述[基本要求] 5、Hash表应用（查找） [问题描述] 设计散列表实现身份证查找系统，对身份证号进行Hash。 [基本要求] （1） 设每个记录有下列数据项：身份证号码（虚构，位数和编码规则与真实一致即可）、姓名、地址。 （2） 从文件输入各记录，以身份证号码为关键字建立散列表。 （3） 分别采用开放定址（自行选择和设计定址方案）和链地址两种方案解决冲突；显示发生冲突的次数、每次中解决冲突进行重定位的次数。 （4） 查找并显示给定身份信息的记录。 （5） 记录条数至少在50条以上。 6、排序算法比较 （必做）（排序） [问题描述] 利用随机函数产生10个样本（其中之一已为正序，之一为倒序），每个样本有20000随机整数，利用直接插入排序、希尔排序，冒泡排序、快速排序、选择排序、堆排序，归并排序（递归和非递归），基数排序八种排序方法进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的平均时间 7、迷宫问题 问题描述[基本要求] 宽搜演示： 深搜演示： 14、编写“连连看”程序。 算法思想： 两个方块直接能否相连的标准是能否用不超过3条线段将他们相连，所以只要扫描其中两个点能扩张出的线段，判断能否到达对方（1条线的情况）或两个点的线段能否相交（2条线的情况）或两条线段上的点能否直线连接到另一条线上（3条