实验3讲解 实验5，6说明 韩路新 2016年3月25日.

Presentation on theme: "实验3讲解 实验5，6说明 韩路新 2016年3月25日."— Presentation transcript:

1 实验3讲解 实验5，6说明 韩路新 2016年3月25日

2 第三次实验讲解 基数排序的内部排序请使用稳定的线性时间排序（桶排序 or 计数排序） C / C++ 的伪随机数原理 注意科学的数据分析方法
让基数排序能显示其时间复杂度上的优越性 C / C++ 的伪随机数原理 rand = rand * c1 + c2 srand()初始化第一个rand值 C / C++的time()函数以ms为单位 未过1ms时srand((unsigned)time(NULL))初始化出的值不变 所以srand((unsigned)time(NULL))只需放在主函数里，执行一次就好 注意科学的数据分析方法

3 实验基本信息 和 实验报告格式 实验报告要求以及提交的邮箱的地址同第一个实验要求PPT上的内容
Lab 5和Lab 6的实验时间为2016年4月5日和2016年4月12日，实验报告Deadline为4月15 日24: 00 以下PPT不加说明页数均为《CLRS 2nd Edition 中文版》 这次代码量极大，大家一定要实验课前提前做，有问题可以及时向老师或者助教提问。我 们助教应该是21:30下班，最多延长检查到22:00（实验室要关门）。如果觉得写不完的请 务必提前做，谢谢。 Ps，大家在写代码的时候务必加上注释，方便助教查阅。

4 实验5 红黑树相关 实验内容：红黑树的插入、删除和查找 为了简单起见，不妨假设所有数字都是不同的
插入、删除：P167 & P172 RB-INSERT & RB-DELETE 查找第k小的数 P182 OS-SELECT(k) 查找值为key的数为第几小，没有的话返回-1 P182 & P153 OS-RANK(TREE-SEARCH(key)) 如果有能力直接写成一个当然更好啦（其实很简单，大家可以想一下）

5 Cont’d 实验检查： 随机n(n≥15)个互异的数，一个一个进行插入 查找第k小的数（两次） 删除某两个数（输入数字的值）
输出随机化的数 中序遍历（P152）这棵树给助教检查（应该得到的是一个排好序的数列） 查找第k小的数（两次） 删除某两个数（输入数字的值） 再次中序遍历给助教检查 求某个数是第几小的（两次）

6 Cont’d 也就是说最终你的程序的输入输出应该是这样的： 先输出一个随机化的乱序的互异的数组，数组长 ≥ 15
再输出红黑树插入后的中序遍历的结果 输入两个数k1和k2，分别求k1小和k2小的值并输出 输入两个数key1和key2，删除key1和key2对应的节点之后输出中序遍历结果 输入两个数key1和key2，求key1和key2分别是第几小的并输出。

7 CONT’D 实验报告（和实验6一起交）： 评分标准：
加分项（2分）：自行设计一个较方便的函数，使得在检查时能够显示树的详细信息，以便能够观 察到结点插入、删除前后树的结构变化(包括结点颜色，秩，父子节点关系等信息)，推荐可视化出 来。 Graphviz软件，这个软件相当简单，相当好用，大家可以学习使用一下 实验报告（和实验6一起交）： 对实现的算法理论分析。将n取2^k(k=5..20)时插入求时间，然后查找所有节点求时间，然后删 除所有节点求时间，以上三个时间做表做图分析。 与之前的n个无序数求第k小的方法进行比较（时空、编程复杂度？在线 / 离线等） 评分标准： 代码10分（插入3 + 删除 3 + 查找 3 + 代码清晰度 1）+ 加分项（2分）

8 实验6 区间树相关 如果你上个实验做完了，这个实验将会比较简单： 实验内容：区间树插入、删除、查找
因为可以把上个实验的红黑树直接拿来修改一下 实验内容：区间树插入、删除、查找 插入、删除：可以直接修改上个实验的红黑树 查找需要实现： 1.返回与给定区间重叠的一个区间 2.返回与给定区间重叠的所有区间 请注意，这两个算法的实现不一样，时间复杂度也不一样，请分别实现

9 Cont’d 实验检查，类似于上一个实验： 实验报告，也类似于上一个实验： 先输出一个随机化的乱序的互异的数对数组，数组长 ≥ 15
再输出红黑树插入后的中序遍历的结果 输入两个数对key1和key2，返回与给定区间重叠的一个区间并输出 输入两个数对key1和key2，删除key1和key2对应的节点之后输出中序遍历结果 输入两个数对key1和key2，返回与给定区间重叠的所有区间并输出。 实验报告，也类似于上一个实验： 对实现的算法理论分析。将n取2^k(k=5..20)时插入求时间，然后查找所有节点求时间，然后删除所有节点 求时间，以上三个时间做表做图分析。

10 Cont’d 评分标准： 代码6分（插入删除2 + 查找 2*2） 两个实验报告合集：4分

11 That’s all Thanks for Listening Question is Welcomed