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

《数据结构课程设计报告---skiplist基本操作》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构课程设计报告题目SkipList基本操作专业年级09计科组员指导教师目录一.问题描述………………………………………………3二.系统概要设计…………………………………………31类的设计………………………………………32主要函数设计…………………………………3三.详细设计………………………………………………4四.系统测试………………………………………………13五.时间复杂度分析………………………………………141查找的时间复杂度分析………………………142插入和删除的时间复杂度分析……………

2、…14六.任务分配………………………………………………14七.参考文献………………………………………………14八.总结及心得体会………………………………………15一.问题描述跳跃表（SkipList）简单地说是增加了向前指针的链表.它是1987年才诞生的一种崭新的数据结构，通过在有序链表上的全部或部分节点增加额外的指针,来提高搜索性能。在进行查找、插入、删除等操作时的期望时间复杂度均为O(logn),有着近乎替代平衡树的本领。而且最重要的一点，就是它的编程复杂度较同类的AVL树，红黑树等要低得多

3、，这使得其无论是在理解还是在推广性上，都有着十分明显的优势。跳跃表由多条链构成（S0，S1，S2……，Sh），且满足如下三个条件：（1）每条链必须包含两个特殊元素：+∞和-∞（2）S0包含所有的元素，并且所有链中的元素按照升序排列。（3）每条链中的元素集合必须包含于序数较小的链的元素集合，即：要求：编程实现跳跃表的初始化、查找、删除、插入等操作。二.系统概要设计1.类的设计（1）跳表结点类SkipNode（2）跳表类SkipList私有成员：maxLevel允许的跳表最高级别level当前非空链

4、的最高级别TailKey最后一个结点里放的正无穷SkipNode*head附加头结点指针SkipNode*tail附加尾结点指针SkipNode**last每条链上的最后一个元素的指针setGrade(int*grade,intL,intH,intlev)为从L到H之间的元素分配lev级别randLevel()在[0,level]之间随机产生一个级别公有成员：SkipList(Tlarge,intmaxLev)构造函数CreateSkipList(T*A,intn)创建跳表~S

5、kipList()析构函数Display()显示各级链表SkipNode*Search(Tx)搜索指定元素Exist(Tx)判断元素在跳表中是否存在Insert(Tx)跳表中插入元素Remove(Tx)删除跳表中指定值的结点2主要函数设计（1）CreateSkipList(T*A,intn)作用：创建跳表参数表：A[]创建跳跃表的数组n数组元素个数算法思想：跳表的最下层组成一普通单链表，第21，2•21，3•21，…结点链接成为第一层链接，第22，2•22，3•22，…成为第二层链接…一个

6、有n个元素的跳表有级数level=int（log（n）/log(2)）.利用setGrade()函数为每个结点分配级别，并把级别存入grade数组。将A中数建立各级链表。（2）Search(Tx)作用：搜索指定值的x的结点指针参数表：x要搜索的元素算法思想：游标指针从最高级链的第一个元素开始，如果找到就返回当前指针，如果x比当前结点大就继续向后，如果比当前结点小就降级，若未找到就返回尾指针的值。（3）Exist(Tx)作用：判断元素是否存在参数表：x要判断的元素算法思想：原理同Search(Tx

7、)，返回值不同。（4）Insert(Tx)将作用：元素插入跳表参数表：x要插入的元素算法思想:从最高级别开始向下搜索，如果x小于ptr下个结点的值，将当前ptr记录到数组中，到下级搜索，如果大于则继续搜索，为插入的结点分配级别后插入各级链表中（5）Remove(Tx)作用：从链表中删除元素参数表：x要删除的元素算法思想：从最高级别开始向下搜索，找到后记录下当前删除节点的前驱指针，继续降级，从各级链表中删除三.详细设计#include#include#i

8、nclude#include#defineDefaultSize12//SkipNode结构跳表的结点声明和定义,E为结点数据域类型,K为关键码的类型templatestructSkipNode{Tdata;//数据域SkipNode**link;//指针域数组SkipNode(Tx,intsize=DefaultSize)//构造函数{data=x;link=newSkipNode*[size];//如果内存分配失败if(link==NU