数据结构课程设计报告---SkipList基本操作

1、 数据结构数据结构 课程设计报告课程设计报告 题题 目目 SkipList 基本操作基本操作 专业年级专业年级 组组 员员 指导教师指导教师 目录目录 一一. .问题描述问题描述3 3 二二. .系统概要设计系统概要设计3 3 1 1 类的设计类的设计3 3 2 2 主要函数设计主要函数设计3 3 三三. .详细设计详细设计4 4 四四. .系统测试系统测试1313 五五. .时间复杂度分析时间复杂度分析 1414 1 1 查找的时间复杂度分析查找的时间复杂度分析1414 2 2 插入和删除的时间复杂度分析插入和删除的时间复杂度分析1414 六六. .任务分配任务分配1414 七七. .参考文

2、献参考文献1414 八八. .总结及心得体会总结及心得体会1515 一.问题描述 跳跃表（Skip List）简单地说是增加了向前指针的链表.它是 1987 年才诞生的一种崭 新的数据结构，通过在有序链表上的全部或部分节点增加额外的指针,来提高搜索性能。在 进行查找、插入、删除等操作时的期望时间复杂度均为 O(logn),有着近乎替代平衡树的本 领。而且最重要的一点，就是它的编程复杂度较同类的 AVL 树，红黑树等要低得多，这使得 其无论是在理解还是在推广性上，都有着十分明显的优势。 跳跃表由多条链构成（S0，S1，S2 ，Sh） ，且满足如下三个条件： （1） 每条链必须包含两个特殊元素：+

3、 和 - （2） S0包含所有的元素，并且所有链中的元素按照升序排列。 （3） 每条链中的元素集合必须包含于序数较小的链的元素集合，即： h SSSS. 210 要求：编程实现跳跃表的初始化、查找、删除、插入等操作。 二.系统概要设计 1.类的设计 （1）跳表结点类 SkipNode （2）跳表类 SkipList 1私有成员： maxLevel 允许的跳表最高级别 level 当前非空链的最高级别 TailKey 最后一个结点里放的正无穷 SkipNode* head 附加头结点指针 SkipNode* tail 附加尾结点指针 SkipNode* last 每条链上的最后一个元素的指针 setGrade(int* grade,int L,int H,int lev) 为从 L 到 H 之间的元素分配 lev 级别 r