数据结构课程设计报告-跳跃表

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业 数据结构与算法课程设计说明书题 目： 跳跃表的实现与应用 学 院： 计算机科学与工程学院 专 业： 信息安全 姓 名： 学 号： 指导教师： 2014年 10 月 3 日成绩评定标准及成绩能按照格式进行写作，无抄袭现象（10分）报告内容行文通畅，有条理性，无错别字，结构严谨。（10分）能够按照数据结构课设的格式要求、排版要求和字数要求等，有需求分析，系统分析，详细设计，关键技术的介绍和参考文献。（10分）在验收过程中，能合理的回答问题（20分）软件能正常运行，实现所提

2、出的功能（40分）软件代码规范性较好（5分）具有自己的创新或特色（5分） 总成绩： 摘 要跳跃表是一种随机化的数据结构，基于并联的链表，其效率可比拟于二叉查找树（对于大多数操作需要O(log n)平均时间）。基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表(因此得名)。所有操作都以对数随机化的时间进行。跳跃表可以很好解决有序链表查找特定值的困难。本文共有六部分。第一部分介绍了跳跃表程序的系统概述，包括所要具备的基本功能和更高要求功能以及该系统的用户人群；第二部分介绍了该程序的需求分析和开发环境。需求分析包括问题描述、功能需

3、求和跳跃表程序的基本内容。基本内容中简单介绍了跳跃表的定义以及构造步骤、跳跃表的基本操作（包括链表初始化、插入、查找和删除）和复杂度分析；第三部分中详细描述和介绍各个功能模块，以及每个功能具体的实现过程，每个功能具体使用到的数据结构和算法等内容。包括跳跃表的创建、跳跃表程序包含的功能、跳跃表的检索、跳跃表的插入、跳跃表的删除、跳跃表的显示、链表效率比较和退出程序这8个模块；第四部分阐述了在编写程序时自己遇到的一些问题和最后的解决思路和办法；第五部分介绍了系统特色及关键技术；第六部分是结论。包括完成情况、有待改进之处、特殊说明、心得体会等。关键词： 跳跃表；高效；概率；随机化；目 录 TOC o

4、 1-3 h z u 引言跳跃表作为一种新兴的数据结构,以相当高的效率和较低的复杂度散发着其独特的光芒。和同样以编程复杂度低而闻名的“伸展树”相比，跳跃表的效率不但不会比它差,甚至优于前者。 人们在思考一类问题的时候,往往会无意中被局限在一个小范围当中。就拿和平衡树相关的问题来说,人们凭借自己的智慧,创造出了红黑树,AVL树等一些很复杂的数据结构。可是千变万变,却一直走不出“树”这个范围。过高的编程复杂度使得这些成果很难被人们所接受。而跳跃表的出现,使得人们眼前顿时豁然开朗。原来用与树完全不相关的数据结构也能够实现树的功能! “跳跃表”这个名字有着其深远的意义。不仅是因为它形象地描述了自身的结

5、构,更有一点,它象征着一种思考方法,一种“跳出定式”的思考方法。在你面临一个困难却山穷水复疑无路的时候,不妨找到问题的原点,“跳”出思维的定式,说不定在另一条全新的路上,你将会看到胜利的曙光。1 系统概述 系统名称：跳跃表的实现与应用具备的功能包括以下几点：基本功能：（1）设计实现跳跃链表，用于高效地访问链表中的元素。（2）包括的基本操作：建立、查找、插入、删除等操作。（3）将其效率和链表、有序链表的效率进行比较。（4）输入：数据是随机产生；非随机产生两种情况更高要求功能：（5）将跳跃链表的操作封装为DLL。（6）UI设计与实现。3）用户：具有基础计算机操作技能、且懂英语的人群。2 需求分析2

6、.1 系统需求2.1.1 问题描述链表存在的一个缺陷是：在有序链表中查找一个元素是否存在，需要从头开始，依次顺序查找。跳跃链表是有序链表的一个变种，可以进行非顺序查找。二叉树是我们都非常熟悉的一种数据结构。它支持包括查找、插入、删除等一系列的操作。但它有一个致命的弱点，就是当数据的随机性不够时，会导致其树型结构的不平衡，从而直接影响到算法的效率。跳跃表是一种随机化的数据结构，基于并联的链表，其效率可比拟于二叉查找树（对于大多数操作需要O(log n)平均时间）。基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表(因此得名)。

7、所有操作都以对数随机化的时间进行。跳跃表可以很好解决有序链表查找特定值的困难。2.1.2 功能需求跳跃表（Skip List）是1987年才诞生的一种崭新的数据结构，它在进行查找、插入、删除等操作时的期望时间复杂度均为O(logn),有着近乎替代平衡树的本领。而且最重要的一点，就是它的编程复杂度较同类的AVL树，红黑树等要低得多，这使得其无论是在理解还是在推广性上，都有着十分明显的优势。跳跃表由多条链构成（S0，S1，S2 ，Sh），且满足如下三个条件：（1） 每条链必须包含两个特殊元素：+ 和 -（2） S0包含所有的元素，并且所有链中的元素按照升序排列。（3） 每条链中的元素集合必须包含于

8、序数较小的链的元素集合2.1.3基本内容：（1）跳跃表定义以及构造步骤跳跃表定义一个跳表，应该具有以下特征：一个跳表应该有几个层（level）组成；跳表的第一层包含所有的元素；每一层都是一个有序的链表；如果元素x出现在第i层，则所有比i小的层都包含x；第i层的元素通过一个down指针指向下一层拥有相同值的元素；Top指针指向最高层的第一个元素。构建有序链表，如图2-1： 图2-1 有序链表的一个跳跃表如图2-2 图2-2 跳跃表跳跃表构造步骤：1、给定一个有序的链表。2、选择连表中最大和最小的元素，然后从其他元素中按照一定算法（随机）随即选出一些元素，将这些元素组成有序链表。这个新的链表称为一

9、层，原链表称为其下一层。3、为刚选出的每个元素添加一个指针域，这个指针指向下一层中值同自己相等的元素。Top指针指向该层首元素4、重复2、3步，直到不再能选择出除最大最小元素以外的元素。(2)跳跃表的基本操作链表的初始化链表的初始化需要初始化头部，并使头部每层（根据事先定义的MAX_LEVEL）指向末尾（NULL）。插入元素插入元素的时候元素所占有的层数完全是随机的，通过随机算法产生跳表的插入需要三个步骤，第一步需要查找到在每层待插入位置，然后需要随机产生一个层数，最后就是从高层至下插入，插入时算法和普通链表的插入完全相同。删除节点删除节点操作和插入差不多，找到每层需要删除的位置，删除时和操作

10、普通链表完全一样。不过需要注意的是，如果该节点的level是最大的，则需要更新跳表的level。删除操作分为以下三个步骤: i)在跳跃表中查找到这个元素的位置,如果未找到,则退出ii)将该元素所在整列从表中删除iii)将多余的“空链”删除 查找跳表的优点就是查找比普通链表快，当然查找操作已经包含在在插入和删除过程，实现起来比较简单。在跳跃表中查找一个元素x,按照如下几个步骤进行: i)从最上层的链(Sh)的开头开始 ii)假设当前位置为p,它向右指向的节点为q(p与q不一定相邻),且q的值为y。将y与x作比较1) xy输出查询成功及相关信息 2) xy从p向右移动到q的位置 3) xy从p向下

11、移动一格 iii) 如果当前位置在最底层的链中(S0),且还要往下移动的话,则输出查询失败(3)复杂度分析一个数据结构的好坏大部分取决于它自身的空间复杂度以及基于它一系列操作的时间复杂度。跳跃表之所以被誉为几乎能够代替平衡树,其复杂度方面自然不会落后。我们来看一下跳跃表的相关复杂度: 空间复杂度: O（n） (期望) 跳跃表高度: O（logn）(期望)相关操作的时间复杂度: 查找: O（logn）(期望) 插入:O（logn）(期望) 删除: O（logn）(期望) 之所以在每一项后面都加一个“期望”,是因为跳跃表的复杂度分析是基于概率论的。有可能会产生最坏情况,不过这种概率极其微小。2.2

12、 开发环境 本次使用的是最流行的windows平台应用程序开发环境Visual Studio2012，使用的语言是c+， C+是一种静态数据类型检查的，支持多重编程的通用程序设计语言。它支持过程化程序设计，数据抽象，面向对象设计，制作图标等多种程序设计风格。3 详细设计3.1 跳跃表的创建本模块使用了结构体、链表、指针数组以及随机生成数算法首先是结构体的定义：struct node int key; /结点数据 struct node* forward10; /结点指针数组;forward10是一个结构体指针数组，数组里保存着最多可以创建10 层跳跃表。每个结点包含有一个元素域key和（级数+

13、1）个指针域。跳跃表的创建包括以下函数：struct node* initialization(int &level,int &total);/初始化跳跃表函数void insert(struct node* head,int key,int &level);/插入结点函数void printall(struct node* head,int &level); /输出各层链函数初始化函数用于创建一个空的跳跃表并设置当前跳跃表的级数为0，结点总数为0并返回头指针。程序一开始可以选择手动输入和随机生成元素。输入元素后再调用insert函数逐个插入跳跃表，这样便创建了一个跳跃表。然后用printal

14、l函数将创建好的跳跃表各层链输出打印。跳跃表的创建界面如图3-1： 图3-1 跳跃表的创建界面3.2 跳跃表程序包含的功能功能选择界面如图3-2： 图3-2跳跃表功能选择界面该界面使用while（1）循环，当使用了一个功能后程序会再次弹出次窗口，直到用户选择了退出键，程序才会跳出while（1）循环，这样保证了用户使用的方便性和程序功能的完善。该功能用swtich语句实现，实现相对比较简单。程序功能包括结点插入、结点检索、结点删除、跳跃表底层链遍历、跳跃表各层链结构显示、效率比较和退出。其中效率比较会根据用户输入的元素建立跳跃表、链表和有序链表，并将3者的效率进行比较。该界面设计的比较友好，考

15、虑了用户的输入错误。当用户输入的数字不是1到7这7个数时程序会提示用户输入错误，并让用户重新输入。3.3 跳跃表的检索 在程序功能选择界面上选择2就进入了该界面。 本模块使用了结构体、链表、结构体指针以及跳跃表的多层链结构。跳跃表的检索界面如图3-3： 图3-3跳跃表元素检索界面跳跃表的检索用到了以下函数：struct node* search(struct node* head,int key,int level);/检索指定结点的函数struct node* ssearch(struct node* head,int key,int level);/检索指定结点并输出相应路径函数void

16、printall(struct node* head,int &level); /输出各层链函数在跳跃表中查找一个元素x,按照如下几个步骤进行: i)从最上层的链(Sh)的开头开始 ii)假设当前位置为p,它向右指向的节点为q(p与q不一定相邻),且q的值为y。将y与x作比较1) xy输出查询成功及相关信息 2) xy从p向右移动到q的位置 3) xy从p向下移动一格 iii) 如果当前位置在最底层的链中(S0),且还要往下移动的话,则输出查询失败首先程序提示“请输入要检索的数字：”当用户输入一个数时，程序调用search函数检索跳跃表的所有数来判断是否存在要检索的数，如果不存在该数，则提示“

17、没有找到要检索的值！”，再返回到程序功能选择界面。如果存在该数，则提示找到要检索的值并且程序会调用ssearch函数来检索指定结点并输出相应检索路径。最后在调用printall函数将跳跃表的各层链显示出来。3.4 跳跃表的插入本模块使用了结构体、链表、结构体指针以及跳跃表的多层链结构和随机数生成算法。在程序功能选择界面上选择1就进入了该界面。跳跃表的插入用到了以下函数：struct node* search(struct node* head,int key,int level);/检索指定结点的函数void insert(struct node* head,int key,int &leve

18、l);/插入结点函数void print(struct node* head);/输出函数int randX(int &level);/随机级数产生函数 首先明确，向跳跃表中插入一个元素，相当于在表中插入一列从S0中某一位置出发向上的连续一段元素。有两个参数需要确定，即插入列的位置以及它的“高度”。关于插入的位置，我们先利用跳跃表的查找功能，即search函数，找到比x小的最大的数y。根据跳跃表中所有链均是递增序列的原则，x必然就插在y的后面。而插入列的“高度”较前者来说显得更加重要，也更加难以确定。由于它的不确定性，使得不同的决策可能会导致截然不同的算法效率。为了使插入数据之后，保持该数据结

19、构进行各种操作均为O(logn)复杂度的性质，我们引入随机化算法（Randomized Algorithms）。我们定义一个随机决策模块，它的大致内容如下：产生一个0到1的随机数r r random() 。如果r小于一个常数p，则执行方案A， if rlevel时，更新当前级数，令i=level。在删除结点时，分配一个结点空间，但是在删除结点后没有释放掉该指针。我们应该在删除结点后使用delete(r)释放掉指针，并且在每一层链都要删除该结点并且释放。当选择6键来效率比较时，进行了比较后如果再选择6键，我们建立的跳跃表、链表、有序链表都是在上次生成的链表上再添加元素，而不是建立一个空的链表。经

20、过几次调试和反复检查后发现是我们创建了 跳跃表、链表或有序链表后再次创建时没有将链表初始化。于是我们分别用：struct node* initialization(int &level,int &total);/初始化跳跃表函数struct listnode* creatlist(); /创建并初始化链表函数struct listnode* creatorderlist(); /创建并初始化有序链表函数来初始化跳跃表、链表和有序链表5 系统特色及关键技术本程序使用了结构体、链表、结构体指针以及跳跃表的多层链结构和随机数生成算法，头插法，链表的冒泡排序等。我将本程序封装成dll,只显示给用户函数

21、的接口而不显示函数是这么实现的，这样保证了函数的安全性。封装成dll后也便于促进模块式程序的开发，简化部署和安装并减少在磁盘和物理内存中加载的代码的重复量。本程序输出界面设计的比较友好，便于用户使用。当用户输入错误时会有相应的提示和提醒，并且会调用相应的函数来处理错误。6 结论这次的程序基本上运行成功，可以实现跳跃表的插入、删除、查询和显示等基本操作以及3种链表的效率比较。由于时间和知识上的限制，使得程序规模相对较小，功能还不很全面，应用也不完善。原来跳跃表涉及很多知识，而不是枯燥无聊的简单代码而已，利用数据结构方面的知识我们可以设计出更完善的程序。但本次程序在应用方面还有很大的改进。在这次课程设计中遇到了很多问题，但最后在老师的指导和同学的帮助下，终于游逆而解。通过此次课程设计，使我更加扎实的掌握了有关跳跃表和链表方面的知识，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和