数据结构课程设计报告跳跃表Word文档格式.docx
《数据结构课程设计报告跳跃表Word文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告跳跃表Word文档格式.docx（20页珍藏版）》请在冰点文库上搜索。
需求分析包括问题描述、功能需求和跳跃表程序的基本内容。
基本内容中简单介绍了跳跃表的定义以及构造步骤、跳跃表的基本操作（包括链表初始化、插入、查找和删除）和复杂度分析；
第三部分中详细描述和介绍各个功能模块，以及每个功能具体的实现过程，每个功能具体使用到的数据结构和算法等内容。
包括跳跃表的创建、跳跃表程序包含的功能、跳跃表的检索、跳跃表的插入、跳跃表的删除、跳跃表的显示、链表效率比较和退出程序这8个模块；
第四部分阐述了在编写程序时自己遇到的一些问题和最后的解决思路和办法；
第五部分介绍了系统特色及关键技术；
第六部分是结论。
包括完成情况、有待改进之处、特殊说明、心得体会等。
关键词：
跳跃表；
高效；
概率；
随机化；
目录
引言1
1系统概述1
2需求分析1
2.1系统需求1
2.1.1问题描述1
2.1.2功能需求2
2.1.3基本内容：
2
2.2开发环境4
3详细设计4
3.1跳跃表的创建4
3.2跳跃表程序包含的功能5
3.3跳跃表的检索6
3.4跳跃表的插入7
3.5跳跃表的删除7
3.6跳跃表的显示8
3.6.1跳跃表底层链遍历8
3.6.2跳跃表的各层链结构显示8
3.7链表效率比较9
3.8退出程序11
4所遇到的问题和分析解决11
5系统特色及关键技术11
6结论12
参考文献13
引言
跳跃表作为一种新兴的数据结构,以相当高的效率和较低的复杂度散发着其独特的光芒。
和同样以编程复杂度低而闻名的“伸展树”相比，跳跃表的效率不但不会比它差,甚至优于前者。
人们在思考一类问题的时候,往往会无意中被局限在一个小范围当中。
就拿和平衡树相关的问题来说,人们凭借自己的智慧,创造出了红黑树,AVL树等一些很复杂的数据结构。
可是千变万变,却一直走不出“树”这个范围。
过高的编程复杂度使得这些成果很难被人们所接受。
而跳跃表的出现,使得人们眼前顿时豁然开朗。
原来用与树完全不相关的数据结构也能够实现树的功能!
“跳跃表”这个名字有着其深远的意义。
不仅是因为它形象地描述了自身的结构,更有一点,它象征着一种思考方法,一种“跳出定式”的思考方法。
在你面临一个困难却山穷水复疑无路的时候,不妨找到问题的原点,“跳”出思维的定式,说不定在另一条全新的路上,你将会看到胜利的曙光。
1系统概述
1）系统名称：
跳跃表的实现与应用
2）具备的功能包括以下几点：
基本功能：
（1）设计实现跳跃链表，用于高效地访问链表中的元素。
（2）包括的基本操作：
建立、查找、插入、删除等操作。
（3）将其效率和链表、有序链表的效率进行比较。
（4）输入：
数据是随机产生；
非随机产生两种情况
更高要求功能：
（5）将跳跃链表的操作封装为DLL。
（6）UI设计与实现。
3）用户：
具有基础计算机操作技能、且懂英语的人群。
2需求分析
2.1系统需求
2.1.1问题描述
链表存在的一个缺陷是：
在有序链表中查找一个元素是否存在，需要从头开始，依次
顺序查找。
跳跃链表是有序链表的一个变种，可以进行非顺序查找。
二叉树是我们都非常熟悉的一种数据结构。
它支持包括查找、插入、删除等一系列的操作。
但它有一个致命的弱点，就是当数据的随机性不够时，会导致其树型结构的不平衡，
从而直接影响到算法的效率。
2.1.2功能需求
跳跃表（SkipList）是1987年才诞生的一种崭新的数据结构，它在进行查找、插入、删除等操作时的期望时间复杂度均为O（logn）,有着近乎替代平衡树的本领。
而且最重要的一点，就是它的编程复杂度较同类的AVL树，红黑树等要低得多，这使得其无论是在理解还是在推广性上，都有着十分明显的优势。
跳跃表由多条链构成（S0，S1，S2„„，Sh），且满足如下三个条件：
（1）每条链必须包含两个特殊元素：
+∞和-∞
（2）S0包含所有的元素，并且所有链中的元素按照升序排列。
（3）每条链中的元素集合必须包含于序数较小的链的元素集合
（1）跳跃表定义以及构造步骤
跳跃表定义
一个跳表，应该具有以下特征：
1.一个跳表应该有几个层（level）组成；
2.跳表的第一层包含所有的元素；
3.每一层都是一个有序的链表；
4.如果元素x出现在第i层，则所有比i小的层都包含x；
5.第i层的元素通过一个down指针指向下一层拥有相同值的元素；
6.Top指针指向最高层的第一个元素。
构建有序链表，如图2-1：
图2-1有序链表
的一个跳跃表如图2-2
图2-2跳跃表
跳跃表构造步骤：
1、给定一个有序的链表。
2、选择连表中最大和最小的元素，然后从其他元素中按照一定算法（随机）随即选出一些元素，将这些元素组成有序链表。
这个新的链表称为一层，原链表称为其下一层。
3、为刚选出的每个元素添加一个指针域，这个指针指向下一层中值同自己相等的元素。
Top指针指向该层首元素
4、重复2、3步，直到不再能选择出除最大最小元素以外的元素。
（2）跳跃表的基本操作
链表的初始化
链表的初始化需要初始化头部，并使头部每层（根据事先定义的MAX_LEVEL）指向末尾（NULL）。
插入元素
插入元素的时候元素所占有的层数完全是随机的，通过随机算法产生
跳表的插入需要三个步骤，第一步需要查找到在每层待插入位置，然后需要随机产生一个层数，最后就是从高层至下插入，插入时算法和普通链表的插入完全相同。
删除节点
删除节点操作和插入差不多，找到每层需要删除的位置，删除时和操作普通链表完全一样。
不过需要注意的是，如果该节点的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向下移动一格
iii）如果当前位置在最底层的链中（S0）,且还要往下移动的话,则输出查询失败
（3）复杂度分析
一个数据结构的好坏大部分取决于它自身的空间复杂度以及基于它一系列操作的时间复杂度。
跳跃表之所以被誉为几乎能够代替平衡树,其复杂度方面自然不会落后。
我们来看一下跳跃表的相关复杂度:
空间复杂度:
O（n）（期望）
跳跃表高度:
O（logn）（期望）
相关操作的时间复杂度:
查找:
O（logn）（期望）
插入:
O（logn）（期望）
删除:
之所以在每一项后面都加一个“期望”,是因为跳跃表的复杂度分析是基于概率论的。
有可能会产生最坏情况,不过这种概率极其微小。
2.2开发环境
本次使用的是最流行的windows平台应用程序开发环境VisualStudio2012，使用的语言是c++，C++是一种静态数据类型检查的，支持多重编程的通用程序设计语言。
它支持过程化程序设计，数据抽象，面向对象设计，制作图标等多种程序设计风格。
3详细设计
3.1跳跃表的创建
本模块使用了结构体、链表、指针数组以及随机生成数算法
首先是结构体的定义：
structnode{
intkey;
//结点数据
structnode*forward[10];
//结点指针数组
};
forward[10]是一个结构体指针数组，数组里保存着最多可以创建10层跳跃表。
每个
结点包含有一个元素域key和（级数+1）个指针域。
跳跃表的创建包括以下函数：
structnode*initialization（int&
level,int&
total）;
//初始化跳跃表函数
voidinsert（structnode*head,intkey,int&
level）;
//插入结点函数
voidprintall（structnode*head,int&
//输出各层链函数
初始化函数用于创建一个空的跳跃表并设置当前跳跃表的级数为0，结点总数为0并返回头指针。
程序一开始可以选择手动输入和随机生成元素。
输入元素后再调用insert函数逐个插入跳跃表，这样便创建了一个跳跃表。
然后用printall函数将创建好的跳跃表各层链输出打印。
跳跃表的创建界面如图3-1：
图3-1跳跃表的创建界面
3.2跳跃表程序包含的功能
功能选择界面如图3-2：
图3-2跳跃表功能选择界面
该界面使用while
（1）循环，当使用了一个功能后程序会再次弹出次窗口，直到用户选择了退出键，程序才会跳出while
（1）循环，这样保证了用户使用的方便性和程序功能
的完善。
该功能用swtich语句实现，实现相对比较简单。
程序功能包括结点插入、结点
检索、结点删除、跳跃表底层链遍历、跳跃表各层链结构显示、效率比较和退出。
其中效率比较会根据用户输入的元素建立跳跃表、链表和有序链表，并将3者的效率进行比较。
该界面设计的比较友好，考虑了用户的输入错误。
当用户输入的数字不是1到7这7个数时程序会提示用户输入错误，并让用户重新输入。
3.3跳跃表的检索
在程序功能选择界面上选择2就进入了该界面。
本模块使用了结构体、链表、结构体指针以及跳跃表的多层链结构。
跳跃表的检索界面如图3-3：
图3-3跳跃表元素检索界面
跳跃表的检索用到了以下函数：
structnode*search（structnode*head,intkey,intlevel）;
//检索指定结点的函数
structnode*ssearch（structnode*head,intkey,intlevel）;
//检索指定结点并输出相应路径函数
首先程序提示“请输入要检索的数字：
”当用户输入一个数时，程序调用search函数检索跳跃表的所有数来判断是否存在要检索的数，如果不存在该数，则提示“没有找到要检索的值！
”，再返回到程序功能选择界面。
如果存在该数，则提示找到要检索的值并且程序会调用ssearch函数来检索指定结点并输出相应检索路径。
最后在调用printall
函数将跳跃表的各层链显示出来。
3.4跳跃表的插入
本模块使用了结构体、链表、结构体指针以及跳跃表的多层链结构和随机数生成算法。
在程序功能选择界面上选择1就进入了该界面。
跳跃表的插入用到了以下函数：
voidprint（structnode*head）;
//输出函数
intrandX（int&
//随机级数产生函数
首先明确，向跳跃表中插入一个元素，相当于在表中插入一列从S0中某一位置出发向上的连续一段元素。
有两个参数需要确定，即插入列的位置以及它的“高度”。
关于插入的位置，我们先利用跳跃表的查找功能，即search函数，找到比x小的最大的数y。
根据跳跃表中所有链均是递增序列的原则，x必然就插在y的后面。
而插入列的“高度”较前者来说显得更加重要，也更加难以确定。
由于它的不确定性，使得不同的决策可能会导致截然不同的算法效率。
为了使插入数据之后，保持该数据结构进行各种操作均为O（logn）复杂度的性质，我们引入随机化算法（RandomizedAlgorithms）。
我们定义一个随机决策模块，它的大致内容如下：
产生一个0到1的随机数rr←random（）。
如果r小于一个常数p，则执行方案A，ifr<
pthendoA否则，执行方案BelsedoB
初始时列高为1。
插入元素时，不停地执行随机决策模块。
如果要求执行的是A操作，则将列的高度加1，并且继续反复执行随机决策模块。
直到第i次，模块要求执行的是B操作，我们结束决策，并向跳跃表中插入一个高度为i的列。
此时我们用randX生成随机级数，这样我们就确定了要插入的位置和“高度”，接着用insert函数将要插入的数插入跳跃表中，在插入过程中程序会自动根据大小将元素排序。
最后将插入后的跳跃表显示出来并统计当前结点数。
3.5跳跃表的删除
在程序功能选择界面上选择3就进入了该界面。
本模块使用了结构体、链表、结构体指针等。
删除界面如图3-4：
图3-4跳跃表元素删除界面
跳跃表的删除要用到的函数如下：
intdeletenode（structnode*head,int&
//删除指定结点函数
从跳跃表中删除一个元素x删除操作分为以下三个步骤：
（1）在跳跃表中查找到这个元素的位置，如果未找到，则退出
（2）将该元素所在整列从表中删除
（3）将多余的“空链”删除
首先程序提示“请输入要删除的数字：
”当用户输入一个数时，程序调用search函数检索跳跃表的所有数来判断是否存在要检索的数，如果不存在该数，则提示“没有找到要删除的值！
如果存在该数，则程序会调用deletenode函数来删除指定结点。
最后在调用print函数将删除后的跳跃表显示出来并统计删除后跳跃表现有的结点数。
3.6跳跃表的显示
3.6.1跳跃表底层链遍历
在程序功能选择界面上选择4就进入了该界面。
传入头指针head，用print函数将跳跃表的0层链（包含跳跃表的全部元素的有序链表）的全部元素输出出来。
3.6.2跳跃表的各层链结构显示
在程序功能选择界面上选择5就进入了该界面。
传入头指针head和层数level，用printall函数将跳跃表的各层链（包含跳跃表的0层到level层的有序链表）的全部元素输出出来。
3.7链表效率比较
本模块使用了结构体、链表、结构体指针以及跳跃表的多层链结构和随机数生成算法，头插法，链表的冒泡排序等。
在程序功能选择界面上选择6就进入了该界面。
首先提示用户输入要创建链表的结点数，然后让用户选择手动输入或随机生成元素，这样便创建好了跳跃表、链表和有序链表。
（要非常注意的是，在加入元素前要把原链表初始化，否则再运行此功能时会在原来链表上再添加元素，而不是新建一个链表）然后将3种链表输出显示。
1.各链表的建立和输出
程序界面如图3-5：
图3-5各种链表的建立和输出
跳跃表的建立和输出用到如下函数：
链表和有序链表用到的结构体为：
structlistnode{
intdata;
structlistnode*next;
链表的建立和输出用到了：
structlistnode*creatlist（）;
//创建链表函数
intinsertlist（structlistnode*llist,intkey）;
//插入链表函数
voidprintlist（structlistnode*llist）;
//输出链表函数
链表创建时把头指针llist置为空，在插入元素时使用头插法在llist后插入元素，然后将链表元素逐个输出。
有序链表的建立和输出用到了：
structlistnode*creatorderlist（）;
//创建有序链表函数
structlistnode*insertorderlist（structlistnode*olist,intkey）;
//插入有序链表并排序函数
voidprintorderlist（structlistnode*olist）;
链表创建时把头指针olist置为空，在插入元素时使用头插法在olist后插入元素，然后用冒泡排序算法对建立的链表进行排序，最后将链表元素逐个输出。
2.各链表查找效率比较
程序先提示用户输入要比较的次数，然后提示用户输入要查找的数。
如果要查找的数不存在，则程序提示“在跳跃表/链表/有序链表中不存在该数，查找失败！
”。
重新查找。
如果要查找的数存在，则将查找路径显示出来并将各链表查找的次数和该数在各链表的位置显示出来。
再次查找。
直到次数达到用户输入的比较次数，退出到程序功能选择界面。
该界面可以很好的多次比较3种链表在查找某个数时所用的步骤，从而对比出它们的效率高低。
效率比较界面如图3-6：
图3-6各链表效率比较界面
统计跳跃表的查找效率用到了如下函数：
intskipk（structnode*head,intkey,intlevel）;
//输出在跳跃表中查找key所用步骤数k函数
voidskipz（structnode*head,intkey）;
//输出key在跳跃链表中的位置函数，z为位置
用skipk函数查找该元素时用k记录所用步骤并且输出查找路径，在skipz函数搜索目标元素后输出元素位置z
统计链表的查找效率用到了：
intsearchlist（structlistnode*llist,int&
m,int&
x）;
//在链表中查找元素x函数
该函数从头到尾地查找目标元素，同时统计查找步骤数和记录目标数位置，然后将查找步骤和元素位置输出。
统计有序链表的查找效率用到了：
intsearchorderlist（structlistnode*olist,int&
与链表不同之处在于有序链表经过冒泡排序后是按顺序递增的，所以查找的数越靠前面，所用步骤数越少。
3.8退出程序
一个程序的退出功能是必不可少的。
4所遇到的问题和分析解决
我在编写程序时遇到的问题及解决方法如下：
（1）插入元素到跳跃表时不知道要从最高层到层每层都插入该元素。
我们要从最高层开始，向最高层插入元素成功后，转向下一层，一直到最底层，这样才算在整个跳跃表中插入了该元素。
（2）随机分配的级数可能会大于当前级数。
我们用i记录随机分配的层数，并判断i和当前级数level的大小，当i>
level时，更新当前级数，令i=level。
（3）在删除结点时，分配一个结点空间，但是在删除结点后没有释放掉该指针。
我们应该在删除结点后使用delete（r）释放掉指针，并且在每一层链都要删除该结点并且释放。
（4）当选择6键来效率比较时，进行了比较后如果再选择6键，我们建立的跳跃表、链表、有序链表都是在上次生成的链表上再添加元素，而不是建立一个空的链表。
经过几次调试和反复检查后发现是我们创建了跳跃表、链表或有序链表后再次创建时没有将链表初始化。
于是我们分别用：
//创建并初始化链表函数
//创建并初始化有序链表函数
来初始化跳跃表、链表和有序链表
5系统特色及关键技术
本程序使用了结构体、链表、结构体指针以及跳跃表的多层链结构和随机数生成算法，头插法，链表的冒泡排序等。
我将本程序封装成dll,只显示给用户函数的接口而不显示函数是这么实现的，这样保证了函数的安全性。
封装成dll后也便于促进模块式程序的开发，简化部署和安装并减少在磁盘和物理内存中加载的代码的重复量。
本程序输出界面设计的比较友好，便于用户使用。
当用户输入错误时会有相应的提示和提醒，并且会调用相应的函数来处理错误。
6结论
这次的程序基本上运行成功，可以实现跳跃表的插入、删除、查询和显示等基本操作以及3种链表的效率比较。
由于时间和知识上的限制，使得程序规模相对较小，功能还不很全面，应用也不完善。
原来跳跃表涉及很多知识，而不
升级会员 