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

数据结构课程设计报告题 目 SkipList基本操作 专业年级 09 计科 组 员 指导教师 目录一.问题描述………………………………………………3二.系统概要设计…………………………………………31类的设计………………………………………32主要函数设计…………………………………3三.详细设计………………………………………………4四.系统测试………………………………………………13五.时间复杂度分析……………………………………… 14 1查找的时间复杂度分析………………………14 2插入和删除的时间复杂度分析………………14六.任务分配………………………………………………14七.参考文献………………………………………………14八.总结及心得体会………………………………………15一.问题描述跳跃表（Skip List）简单地说是增加了向前指针的链表.它是1987年才诞生的一种崭新的数据结构，通过在有序链表上的全部或部分节点增加额外的指针,来提高有哪些信誉好的足球投注网站性能。在进行查找、插入、删除等操作时的期望时间复杂度均为O(logn),有着近乎替代平衡树的本领。而且最重要的一点，就是它的编程复杂度较同类的AVL树，红黑树等要低得多，这使得其无论是在理解还是在推广性上，都有着十分明显的优势。跳跃表由多条链构成（S0，S1，S2 ……，Sh），且满足如下三个条件：每条链必须包含两个特殊元素：+∞ 和 -∞S0包含所有的元素，并且所有链中的元素按照升序排列。每条链中的元素集合必须包含于序数较小的链的元素集合，即：要求：编程实现跳跃表的初始化、查找、删除、插入等操作。二.系统概要设计1.类的设计（1）跳表结点类SkipNode（2）跳表类SkipList私有成员： maxLevel 允许的跳表最高级别level当前非空链的最高级别 TailKey 最后一个结点里放的正无穷 SkipNodeT* head附加头结点指针 SkipNodeT* tail附加尾结点指针 SkipNodeT** last每条链上的最后一个元素的指针 setGrade(int* grade,int L,int H,int lev)为从L到H之间的元素分配lev级别 randLevel()在[0,level]之间随机产生一个级别公有成员： SkipList(T large,int maxLev) 构造函数 CreateSkipList(T* A,int n) 创建跳表 ~SkipList() 析构函数Display()显示各级链表SkipNodeT* Search(T x) 有哪些信誉好的足球投注网站指定元素 Exist(T x) 判断元素在跳表中是否存在Insert(T x) 跳表中插入元素Remove(T x) 删除跳表中指定值的结点2主要函数设计CreateSkipList(T* A,int n)作用：创建跳表参数表：A[] 创建跳跃表的数组 n数组元素个数算法思想：跳表的最下层组成一普通单链表，第21，2?21， 3?21，…结点链接成为第一层链接，第22，2?22， 3?22，…成为第二层链接…一个有n个元素的跳表有级数level=int（log（n）/log(2)）.利用setGrade()函数为每个结点分配级别，并把级别存入grade数组。将A 中数建立各级链表。（2）Search(T x)作用：有哪些信誉好的足球投注网站指定值的x的结点指针参数表：x 要有哪些信誉好的足球投注网站的元素算法思想：游标指针从最高级链的第一个元素开始，如果找到就返回当前指针，如果x比当前结点大就继续向后，如果比当前结点小就降级，若未找到就返回尾指针的值。（3）Exist(T x)作用：判断元素是否存在参数表：x 要判断的元素算法思想：原理同Search(T x)，返回值不同。（4）Insert(T x)将作用：元素插入跳表参数表：x 要插入的元素算法思想:从最高级别开始向下有哪些信誉好的足球投注网站，如果x小于ptr下个结点的值，将当前ptr记录到数组中，到下级有哪些信誉好的足球投注网站，如果大于则继续有哪些信誉好的足球投注网站，为插入的结点分配级别后插入各级链表中（5）Remove(T x)作用：从链表中删除元素参数表：x要删除的元素算法思想：从最高级别开始向下有哪些信誉好的足球投注网站，找到后记录下当前删除节点的前驱指针，继续降级，从各级链表中删除三.详细设计#includeiostream.h#includestdlib.h#includecmath#includectime#define DefaultSize 12//SkipNode结构 跳表的结点声明和定义,E为结点数据域类型,K为关键码的类型templateclass Tstruct SkipNode{ T data; //数据域 SkipNodeT** link;