参考skiplist的设计与开发课件

《参考skiplist的设计与开发课件》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、沈阳航空航天大学课程设计报告第2章详细设计沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：SkipList的设计与实现院（系）：计算机学院专业：计算机科学与技术班级：04010101学号：2010040101017姓名：沈晓峰指导教师：郑志勇完成日期：2012年1月11日-18-沈阳航空航天大学课程设计报告第2章详细设计目录第1章概要设计………………………………………………………………...-1-1.1题目的内容与要求…………………………………………………………...-1-1.2总体结构……………………………………………

2、………………………...-1-第2章详细设计-2-2.1菜单选项模块………………………………………………………………...-2-2.2跳表的创建…………………………………………………………………...-3-2.3跳表的查找…………………………………………………………………...-4-2.4跳表的插入…………………………………………………………………...-5-2.5跳表的删除…………………………………………………………………...-6-2.6跳表的输出…………………………………………………………………...-7-第3章调试分析-6-第4章使用说

3、明与执行结果-7-参考文献-9-附录（程序清单）-10--18-沈阳航空航天大学课程设计报告第2章详细设计-18-沈阳航空航天大学课程设计报告第2章详细设计第1章概要设计1.1题目的内容与要求内容：SkipList作为有序链表结构的一种扩展，如图所示，其中a是普通的单链表；而b是在此基础上加上第二层（level2）的额外指针，这些额外的指针指向间隔为2的下个结点，SkipList因此而得名；类似的c是加上level3后的SkipList。SkipList上查找的基本思想是从最高的Level层上查找，找到key所在的范围后，在从较低层次继续重复查

4、找操作，直到Level1。要求：1）设计并实现一个SkipList数据结构并包括、删除、查找等操作；2）能够对一个SkipList实例实现动态演示。（选作）1.2总体结构本程序主要有五个功能：创建跳跃表、跳跃表的插入、跳跃表的删除、跳跃表的输出、跳跃表的查找。跳跃表的插入和删除：这个是通过先查找所需要的位置，然后插入数，最后用表一级的链表生成一个跳跃表。跳跃表的查找：这个是通过从三级确定一个大范围，再从二级确定一个小范围，最后在在一级中找到所要查找的数。-18-沈阳航空航天大学课程设计报告第2章详细设计跳跃表的创建：这个是先创建一个一级的普通链

5、表，再通过这个一级链表形成一个跳跃表。跳跃表的输出：这个是通过各个级用链表的方法输出。跳跃链表跳表的创建跳表的删除跳表的插入跳表的查找跳表的输出图1.1功能模块图第2章详细设计2.1菜单选项模块控制整个程序的运行，控制菜单操作，通过主函数模块分别调用各个模块，实现各项功能，流程如图2.1所示。-18-沈阳航空航天大学课程设计报告第2章详细设计054123跳表的输出跳表的删除输入aa的值开始输出主菜单选项结束跳表的插入跳表的查找跳表的创建图2.1主模块流程图1）输出主菜单，输入a的值；2）如果a=1，进行跳表的创建；如果a=2，进行跳表的查找；如

6、果a=3，进行跳表的插入；如果a=4，进行跳表的删除；如果a=5，进行跳表的输出；如果a=0，结束程序。2.2跳表的创建输入所需的数值，并以负数结束输入。函数先创建一个普通的一级链表，然后通过跳表的升级，分别将相隔为二的结点升级成二级链表，相隔为三的结点升级成三级链表。算流程如图2.2所示。-18-沈阳航空航天大学课程设计报告第2章详细设计是否创建头结点，并将各个结点连接，创建成一级链表通过update()函数，分别将相隔二的，创建为二级链表，相隔为散的创建为三级链表。Creat（）返回主菜单判断输入的值是否为升序，图2.2函数Creat（）流

7、程图注释：1）创建头结点，并将各个结点连接，创建成一级链表2）通过update()函数，分别将相隔二的，创建为二级链表，相隔为散的创建为三级链表。3）判断输入的值是否为升序。3）返回主函数。2.3跳表的查找通过从跳表的三级链表确定一个大范围，再从跳表的二级链表确定一个小范围，最后在在一级中找到所要查找的数。如图2.3-18-沈阳航空航天大学课程设计报告第2章详细设计Y确定数值在跳表的三级链表的范围确定数值在跳表的二级链表的范围Search()返回结果查找该数值在以上范围内是否存在。图2.3Search()函数流程图注释：1）确定数值在跳表的三级

8、链表的范围。2）确定数值在跳表的二级链表的范围。3）查找该数值在以上范围内是否存在。4）返回结果。2.4跳表的插入通过跳表的查找确定插入数值的地址，再