数据结构课设之跳跃链表

桂林电子科技大学综合设计说明书用纸《数据结构与算法》课程设计说明书题目：跳跃链表的实现学院：计算机科学与工程专业：信息安全姓名：学号：指导教师：张瑞霞2014年10月21日（请将以下内容放入封面后面）成绩评定标准及成绩能按照格式进行写作，无抄袭现象（10分）报告内容行文通畅，有条理性，无错别字，结构严谨。（10分）能够按照数据结构课设的格式要求、排版要求和字数要求等，有需求分析，系统分析，详细设计，关键技术的介绍和参考文献。（10分）在验收过程中，能合理的回答问题（20分）软件能正常运行，实现所提出的功能（40分）软件代码规范性较好（5分）具有自己的创新或特色（5分）总成绩：摘要SkipList是一种随机化的数据结构，基于并联的链表，其效率可比拟于二叉查找树（对于大多数操作需要O(logn)平均时间）。基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表(因此得名)。所有操作都以对数随机化的时间进行。SkipList可以很好解决有序链表查找特定值的困难。跳跃链表在进行查找、插入、删除等操作时的时间复杂度均为O(logn),有着近乎替代平衡树的本领。而且最重要的一点，就是它的编程复杂度较同类的AVL树，红黑树等要低得多，这使得其无论是在理解还是在推广性上，都有着十分明显的优势。为测试跳跃链表的查找效率，向读者介绍跳跃链表的基本结构与代码实现，本文将划分为主要三部分。第一部分是概述。它会从功能、效率等方面对跳跃表作一个初步的介绍，并给出其图形结构，以便读者对跳跃表有个形象的认识。第二部分将介绍跳跃链表的测试系统的具体实现框架与代码，并简单介绍开发环境与编程语言。第三部分将介绍跳跃表的三种基本操作——查找，插入和删除，并对它们的时空复杂度进行分析。最后是本次课设的总结与系统的优缺点评价。【关键字】跳跃表高效概率随机化目录HYPERLINK摘要 3HYPERLINK引言 1HYPERLINK1 系统概述 1HYPERLINK2需求分析 1HYPERLINK2.1系统需求 1HYPERLINK2.2开发环境 4HYPERLINK3详细设计 6HYPERLINK3.1系统框架 6HYPERLINK3.2主要代码 7HYPERLINK3.3运行界面与测试结果 9HYPERLINK3.4复杂度分析 10HYPERLINK4所遇到的问题和分析解决 12HYPERLINK5系统特色与关键技术 12HYPERLINK5.1特色与关键技术 12HYPERLINK5.2系统不足之处 14HYPERLINK6结论及体会 14HYPERLINK参考文献 15桂林电子科技大学综合设计说明书用纸第21页引言比较几种常用的数据结构，我们不难发现，以下总结。数组作为最常见的数据结构，在实现方面简单，并且查找高效，但数组一旦显式的被申明后，其大小就固定了，不能动态进行扩充。不利于动态维护，无法实行高效的插入删除操作，而且一旦数组的长度过长，容易存在内存的浪费。链表动态维护灵活，但是空间和时间额外耗费较大；数组大小固定，元素位置固定，但是操作不灵活，且容易浪费空间，但是时间耗费较小，尤其是元素变化不大的时候效率很高。双向链表比单向的更灵活，但是空间耗费也更大二叉树支持包括查找、插入、删除等一系列的操作。但它有一个致命的弱点，就是当数据的随机性不够时，会导致其树型结构的不平衡，从而直接影响到算法的效率。跳跃表（SkipList）作为一种崭新的数据结构，它在进行查找、插入、删除等操作时的期望时间复杂度均为O(logn),有着近乎替代平衡树的本领。最为关键的一点，它的编程复杂度较同类的AVL树，红黑树等要低得多，这使得其无论是在理解还是在推广性上，都有着十分明显的优势。系统概述系统主要使用C++进行编写，中间夹渣一些C的输出语法。编译环境为VC6.0。整体设计为结构体与指针构成跳跃表。系统在DOS下面运行，设计有一个简易的跳转界面。开始为欢迎界面，用户首先要选择选择手动输入创建跳跃表或者是系统随机生成跳跃表，创建完成和剖，进入功能功能选择菜单，用户可以选择对生成跳跃表进行查找，增加，或者删除操作。同时可选择进行系统查找性能测试。对于查找，用户可以选择按位置查找或者按值查找。同样，删除也具有按位置删除和按值删除。2需求分析2.1系统需求跳跃表（SkipList）简单地说是增加了向前指针的链表.它是1987年才诞生的一种崭新的数据结构，通过在有序链表上的全部或部分节点增加额外的指针,来提高搜索性能。在进行查找、插入、删除等操作时的期望时间复杂度均为O(logn),有着近乎替代平衡树的本领。而且最重要的一点，就是它的编程复杂度较同类的AVL树，红黑树等要低得多，这使得其无论是在理解还是在推广性上，都有着十分明显的优势。跳跃表由多条链构成（S0，S1，S2……，Sh），且满足如下三个条件：每条链必须包含两个特殊元素：+∞和-∞S0包含所有的元素，并且所有链中的元素按照升序排列。每条链中的元素集合必须包含于序数较小的链的元素集合，即：跳跃链表的定义与构造：定义：一个跳表，应该具有以下特征：1. 一个跳表应该有几个层（level）组成；2. 跳表的第一层包含所有的元素；3. 每一层都是一个有序的链表；4. 如果元素x出现在第i层，则所有比i小的层都包含x；5. 第i层的元素通过一个down指针指向下一层拥有相同值的元素；6. 在每一层中，-1和1两个元素都出现(分别表示INT_MIN和INT_MAX)；7. Top指针指向最高层的第一个元素。构建有序链表：如图2-1 图2-1一个跳跃表如下：如图2-2

图2-2构造步骤：1、给定一个有序的链表。2、选择连表中最大和最小的元素，然后从其他元素中按照一定算法（随机）随即选出一些元素，将这些元素组成有序链表。这个新的链表称为一层，原链表称为其下一层。

3、为刚选出的每个元素添加一个指针域，这个指针指向下一层中值同自己相等的元素。Top指针指向该层首元素

4、重复2、3步，直到不再能选择出除最大最小元素以外的元素。功能需求：编程实现跳跃表的初始化、查找、删除、插入等操作。实现原理一、查找目的：在跳跃表中查找一个元素x

在跳跃表中查找一个元素x，按照如下几个步骤进行：

1.从最上层的链（Sh）的开头开始

2.假设当前位置为p，它向右指向的节点为q（p与q不一定相邻），且q的值为y。将y与x作比较

(1)x=y输出查询成功及相关信息

(2)x>y从p向右移动到q的位置

(3)x3.如果当前位置在最底层的链中（S0），且还要往下移动的话，则输出查询失败二、插入目的：向跳跃表中插入一个元素x首先明确，向跳跃表中插入一个元素，相当于在表中插入一列从S0中某一位置出发向上的连续一段元素。有两个参数需要确定，即插入列的位置以及它的“高度”。关于插入的位置，我们先利用跳跃表的查找功能，找到比x小的最大的数y。根据跳跃表中所有链均是递增序列的原则，x必然就插在y的后面。而插入列的“高度”较前者来说显得更加重要，也更加难以确定。由于它的不确定性，使得不同的决策可能会导致截然不同的算法效率。为了使插入数据之后，保持该数据结构进行各种操作均为O(logn)复杂度的性质，我们引入随机化算法（RandomizedAlgorithms）。我们定义一个随机决策模块，它的大致内容如下：产生一个0到1的随机数rr←random()如果r小于一个常数p，则执行方案A，ifr否则，执行方案BelsedoB初始时列高为1。插入元素时，不停地执行随机决策模块。如果要求执行的是A操作，则将列的高度加1，并且继续反复执行随机决策模块。直到第i次，模块要求执行的是B操作，我们结束决策，并向跳跃表中插入一个高度为i的列。三、删除目的：从跳跃表中删除一个元素x

删除操作分为以下三个步骤：（1）在跳跃表中查找到这个元素的位置，如果未找到，则退出

（2）将该元素所在整列从表中删除

（3）将多余的“空链”删除使用范围：面向数据结构开发学习人员，学生以及院校任课老师！简易，清晰介绍跳跃链表定义与构造，并编程实现跳跃表的初始化、查找、删除、插入等操作。运行界面：在DOS系统下面运行，其中一个界面如下：输出要求：输出是为让用户直观了解跳跃链表的构造与使用，在CMD界面下测试使用，用户输入相应的数据构造跳跃链表，编程实现跳跃表的初始化、查找、删除、插入等操作。故障处理：故障主要出现原因是对跳跃链表不熟悉，需要到图书馆查阅相关方面书籍或者文献，网上查找并学习相关资料！同时对开发环境vs2012的不掌握导致，基本使用规则，调试工具的使用情况需要熟悉！c++的语法掌握情况也是课设能否完成的关键，特别是指针，还有链表方面知识需要巩固！2.2开发环境操作系统：window7旗舰版开发工具：vc6.0开发语言：C++（1）Windows7旗舰版属于微软公司开发的Windows7系统系列中的终结版本，是为了取代WindowsXP系统的新系统，Windows7的版本还有简易版、家庭普通版、家庭高级版、专业版。而且旗舰版是所有Windows7系统中是最贵的（正版系统）也是功能最完善的系统。拥有Windows7HomePremium和Windows7Professional的全部功能，，硬件要求与HomePremium和Professional基本相同，没有太大差距。（2）VisualC++6.0，简称VC或者VC6.0，是微软推出的一款C++编译器，将“高级语言”翻译为“机器语言（低级语言）”的程序。VisualC++是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出VisualC++1.0后，随着其新版本的不断问世，VisualC++已成为专业程序员进行软件开发的首选工具。虽然微软公司推出了VisualC++.NET(VisualC++7.0)，但它的应用的很大的局限性，只适用于Windows2000、WindowsXP和WindowsNT4.0。所以实际中，更多的是以VisualC++6.0为平台。VisualC++6.0不仅是一个C++编译器，而且是一个基于Windows操作系统的可视化集成开发环境（integrateddevelopmentenvironment，IDE）。VisualC++6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导ClassWizard等开发工具。这些组件通过一个名为DeveloperStudio的组件集成为和谐的开发环境。C++介绍：C++是在C语言的基础上开发的一种集面向对象编程、泛型编程和过程化编程于一体的编程语言[。应用较为广泛，是一种静态数据类型检查的，支持多重编程的通用程序设计语言。它支持过程化程序设计，数据抽象，面向对象设计，制作图标等多种程序设计风格。（3）C++是在C语言的基础上开发的一种集面向对象编程、泛型编程和过程化编程于一体的编程语言。应用较为广泛，是一种静态数据类型检查的，支持多重编程的通用程序设计语言。它支持过程化程序设计，数据抽象，面向对象设计，制作图标等多种程序设计风格。最新正式标准C++14于2014年8月18日公布。C++是一种使用非常广泛的电脑程序设计语言。它是一种静态数据类型检查的，支持多范型的通用程序设计语言。C++支持过程化程序设计、数据抽象化、面向对象程序设计、泛型程序设计、基于原则设计等多种程序设计风格。贝尔实验室的比雅尼•斯特劳斯特鲁普博士在20世纪80年代发明并实现了C++。起初，这种语言被称作“CwithClasses”（“包含类的C语言”），作为C语言的增强版出现。随后，C++不断增加新特性。虚函数（virtualfunction）、操作符重载（operatoroverloading）、多重继承（multipleinheritance）、模板（template）、异常处理（exception）、RTTI(Runtimetypeinformation)、命名空间（namespace）逐渐纳入标准。1998年国际标准组织（ISO）颁布了C++程序设计语言的国际标准ISO/IEC14882-1998。另外，就目前学习C++而言，可以认为它是一门独立的语言；它并不依赖C语言，我们可以完全不学C语言，而直接学习C++。根据《C++编程思想》（ThinkinginC++）一书所评述的，C++与C的效率往往相差在±5%之间。所以有部分人认为在大多数场合中，C++完全可以取代C语言。C++语言发展大概可以分为三个阶段：第一阶段从80年代到1995年。这一阶段C++语言基本上是传统类型上的面向对象语言，并且凭借著接近C语言的效率，在工业界使用的开发语言中占据了相当大份额；第二阶段从1995年到2000年，这一阶段由于标准模板库（STL）和后来的Boost等程序库的出现，泛型程序设计在C++中占据了越来越多的比重性。当然，同时由于Java、C#等语言的出现和硬件价格的大规模下降，C++受到了一定的冲击；第三阶段从2000年至今，由于以Loki、MPL等程序库为代表的产生式编程和模板元编程的出现，C++出现了发展历史上又一个新的高峰，这些新技术的出现以及和原有技术的融合，使C++已经成为当今主流程序设计语言中最复杂的一员。3详细设计3.1系统框架本程序主要有五个功能：创建跳跃表、跳跃表的插入、跳跃表的删除、跳跃表的输出、跳跃表的查找、跳跃表的查找性能测试。跳跃表的插入：这个是通过先查找所需要的位置，然后插入数，最后用表一级的链表生成一个跳跃表。跳跃表的删除：这个是通过先查找所需要的位置，然后删除数，最后用表一级的链表生成一个跳跃表。跳跃表的查找：这个是通过从三级确定一个大范围，再从二级确定一个小范围，最后在在一级中找到所要查找的数。跳跃表的创建：这个是先创建一个一级的普通链表，再通过这个一级链表形成一个跳跃表。跳跃表的输出：这个是通过各个级用链表的方法输出。跳跃表的查找性能测试：系统随机生成跳跃表，通过多次查找并统计查找花费次数，技术平均查找次数。系统共计两个菜单界面：主菜单：图3.1-1跳跃链表测试系统跳跃链表测试系统4退出3开发者信息4退出3开发者信息2输入创建跳跃链表1随机创建跳跃链表图3-1功能菜单：图3-2功能选择菜单功能选择菜单按值删除添加元素显示跳跃表显示层数性能测试按位置删除按值查找返回上一级按位置查找按值删除添加元素显示跳跃表显示层数性能测试按位置删除按值查找返回上一级按位置查找图3-23.2主要代码跳跃表的结构如下：使用结构体定义跳跃表，key表示节点的位置，value表示值//节点typedefstructnodeStructure{intkey;intvalue;structnodeStructure*forward[1];}nodeStructure;//跳表typedefstructskiplist{intlevel;nodeStructure*header;}skiplist;跳跃表的查找：由于跳跃表的结构设置，查找跳跃表可以通过两种方式查找，按位置查找、按值查找。为了统计查找次数与打印查找路径，本系统共定义了五条查找函数。查找代码基本相似，这里写出其中一个查找函数：//搜索指定key的valueintsearch(skiplist*sl,intkey){nodeStructure*p,*q=NULL;p=sl->header;//从最高层开始搜intk=sl->level;for(inti=k-1;i>=0;i--){while((q=p->forward[i])&&(q->key<=key)){if(q->key==key){returnq->value;}p=q;}}returnNULL;}跳跃表的插入：//插入节点boolinsert(skiplist*sl,intkey,intvalue){nodeStructure*update[MAX_LEVEL];nodeStructure*p,*q=NULL;p=sl->header;intk=sl->level;//从最高层往下查找需要插入的位置//填充updatefor(inti=k-1;i>=0;i--){while((q=p->forward[i])&&(q->key<key)){p=q;}update[i]=p;}//不能插入相同的keyif(q&&q->key==key){returnfalse;}//产生一个随机层数K//新建一个待插入节点q//一层一层插入k=randomLevel();//更新跳表的levelif(k>(sl->level)){for(inti=sl->level;i<k;i++){update[i]=sl->header;}sl->level=k;}q=createNode(k,key,value);//逐层更新节点的指针，和普通列表插入一样for(intj=0;j<k;j++){q->forward[j]=update[j]->forward[j];update[j]->forward[j]=q;}returntrue;}跳跃表的删除：与插入基本相识，不再写出。3.3运行界面与测试结果系统开始运行界面：开始运行界面如图3.3-1所示。用户可以选择随机创建跳跃链表，或者输入创建跳跃链表。用户选择1或者2，界面跳转到功能选择界面图3.3-2。选择3可以查看开发者信息与版本号，选择4直接退出系统。图3.3-1功能选择界面：图3.3-23.4复杂度分析一个数据结构的好坏大部分取决于它自身的空间复杂度以及基于它一系列操作的时间复杂度。跳跃表之所以被誉为几乎能够代替平衡树，其复杂度方面自然不会落后。我们来看一下跳跃表的相关复杂度：空间复杂度：O(n) （期望）跳跃表高度：O(logn) （期望）相关操作的时间复杂度： 查找： O(logn) （期望） 插入： O(logn) （期望） 删除： O(logn) （期望） 之所以在每一项后面都加一个“期望”，是因为跳跃表的复杂度分析是基于概率论的。有可能会产生最坏情况，不过这种概率极其微小。下面我们来一项一项分析。空间复杂度分析O(n)假设一共有n个元素。根据性质1，每个元素插入到第i层（Si）的概率为pi-1，则在第i层插入的期望元素个数为npi-1，跳跃表的元素期望个数为，当p取小于0.5的数时，次数总和小于2n。所以总的空间复杂度为O(n)跳跃表高度分析O(logn)根据性质1，每个元素插入到第i层（Si）的概率为pi，则在第i层插入的期望元素个数为npi-1。考虑一个特殊的层：第1+层。层的元素期望个数为=1/n2，当n取较大数时，这个式子的值接近0，故跳跃表的高度为O(logn)级别的。查找的时间复杂度分析O(logn)我们采用逆向分析的方法。假设我们现在在目标节点，想要走到跳跃表最左上方的开始节点。这条路径的长度，即可理解为查找的时间复杂度。设当前在第i层第j列那个节点上。如果第j列恰好只有i层（对应插入这个元素时第i次调用随机化模块时所产生的B决策，概率为1-p），则当前这个位置必然是从左方的某个节点向右跳过来的。如果第j列的层数大于i（对应插入这个元素时第i次调用随机化模块时所产生的A决策，概率为p），则当前这个位置必然是从上方跳下来的。（不可能从左方来，否则在以前就已经跳到当前节点上方的节点了，不会跳到当前节点左方的节点）设C(k)为向上跳k层的期望步数（包括横向跳跃）有：C(0)=0C(k)=(1-p)(1+向左跳跃之后的步数)+p(1+向上跳跃之后的步数)=(1-p)(1+C(k))+p(1+C(k-1))C(k)=1/p+C(k-1)C(k)=k/p 而跳跃表的高度又是logn级别的，故查找的复杂度也为logn级别。对于记忆化查找（Searchwithfingers）技术我们可以采用类似的方法分析，很容易得出它的复杂度是O(logk)的（其中k为此次与前一次两个被查找元素在跳跃表中位置的距离）。插入与删除的时间复杂度分析O(logn) 插入和删除都由查找和更新两部分构成。查找的时间复杂度为O(logn)，更新部分的复杂度又与跳跃表的高度成正比，即也为O(logn)。 所以，插入和删除操作的时间复杂度都为O(logn)4所遇到的问题和分析解决做课设的时候并不总是一帆风顺，当遇到问题的时候，总是第一时间与同学讨论分析或者进行百度。写代码的时候，主要遇到这个问题。由于跳跃链表的level是随机生成的，为了确保跳跃表的值随机性与层数的随机性。调用系统的随机数产生函数rand();产生随机层数代码如下：//随机产生层数intrandomLevel(){ //srand((unsigned)time(NULL));intk=1;while(rand()%2)k++;k=(k<MAX_LEVEL)?k:MAX_LEVEL;returnk;}多次测试表明，该随机数并不是真正的随机数。通过百度得知，系统的随机数产生是基于一个线性算法，当用户传递一个参数进入，系统通过计算得出相应的结果。由于传递参数不同，导致得到的“随机数”结果不一样，用户可以通过srand()函数设置随机数种子、如果用户未设定种子，系统默认种子为一，因为之前为设置随机数种子，导致每次产生的随机数都一样。导致跳跃表不具有随机性，导致性能测试不具有可靠性与广泛性。处理方法：引入系统时间做随机数种子：#include<time.h>srand((unsigned)time(NULL));由于系统时间不断变化，随机数种子不断变化，似的计算出来的随机数具有普遍意义上的随机性。5系统特色与关键技术5.1特色与关键技术第一：系统的特色在于多个查找函数，函数定义如下：//搜索指定key的valueintsearch(skiplist*sl,intkey)；//查找指定的value所在的keyintsearchbyvalue(skiplist*sl,intvalue)；//搜索指定key的value并返回查找次数，打印查找路径intsearchpathkey(skiplist*sl,intkey)；//查找指定的value并返回查找的次数查找打印查找路径intsearchpathval(skiplist*sl,intvalue)；//查找指定的value并返回查找的次数intsearchpath(skiplist*sl,intvalue)；用户可以通过多个查找函数，选择多种方式进行查找，同时，删除函数也可以选择两种方式进行查找并删除。跳跃表节点定义：typedefstructnodeStructure{intkey;intvalue;structnodeStructure*forward[1];}nodeStructure;由于key,与value两个变量，使得用户在使用跳跃表时可以有多种方式实现跳跃表的查询与删除。为了追踪查找路径，本系统没有采用传统的堆栈结构保存查找路径，而是在代码查找的同时，直接打印出查找路径：cout<<q->value<<"->";巧妙的化简了算法实现的难度，并减少了运行时间花销。同时，为了实现统计查找单个元素所花费次数，使用一个count变量追踪代码，每查找一次：count=count+1;，最终返回count的值：returncount;完整代码如下：for(inti=k-1;i>=0;i--){while((q=p->forward[i])&&(q->value<=value)){ count=count+1; cout<<q->value<<"->";if(q->value==value){returncount; //break;}p=q;}}第二：跳跃表的构造如下跳跃表由多条链构成（S0，S1，S2……，Sh），且满足如下三个条件：每条链必须包含两个特殊元素：+∞和-∞S0包含所有的元素，并且所有链中的元素按照升序排列。每条链中的元素集合必须包含于序数较小的链的元素集合，即：跳跃的构造是所有链中的元素按照升序排列。但是，由于存在随机产生的元素，并不能确保随机数是