SkipList的设计与开发

沈阳航空航天大学课 程 设 计 报 告课程设计名称：数据结构课程设计课程设计题目：Skip List 的设计与实现院（系）：计算机学院专 业：计算机科学与技术班 级：04010101学 号：2010040101017姓 名：沈晓峰指导教师：郑志勇完成日期：2012 年 1 月 11 日沈阳航空航天大学课程设计报告 第 2 章 详细设计2沈阳航空航天大学课程设计报告I目 录第 1 章 概要设计 .- 1 -1.1 题目的内容与要求.- 1 -1.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 章 使用说明与执行结果 .- 7 -参考文献 .- 9 -附 录（程序清单） .- 10 -沈阳航空航天大学课程设计报告 第 2 章 详细设计II沈阳航空航天大学课程设计报告 第 1 章 概要设计- 1 -第 1 章 概要设计1.1 题目的内容与要求内容：Skip List 作为有序链表结构的一种扩展，如图所示，其中 a 是普通的单链表；而 b 是在此基础上加上第二层（level 2）的额外指针，这些额外的指针指向间隔为 2 的下个结点，Skip List 因此而得名；类似的 c 是加上 level 3 后的Skip List。Skip List 上查找的基本思想是从最高的 Level 层上查找，找到 key 所在的范围后，在从较低层次继续重复查找操作，直到 Level 1。要求：1）设计并实现一个 Skip List 数据结构并包括、删除、查找等操作；2）能够对一个 Skip List 实例实现动态演示。 （选作）1.2 总体结构本程序主要有五个功能：创建跳跃表、跳跃表的插入、跳跃表的删除、跳跃表的输出、跳跃表的查找。跳跃表的插入和删除：这个是通过先查找所需要的位置，然后插入数，最后用表一级的链表生成一个跳跃表。跳跃表的查找：这个是通过从三级确定一个大范围，再从二级确定一个小沈阳航空航天大学课程设计报告 第 2 章 详细设计- 2 -范围，最后在在一级中找到所要查找的数。跳跃表的创建：这个是先创建一个一级的普通链表，再通过这个一级链表形成一个跳跃表。跳跃表的输出：这个是通过各个级用链表的方法输出。跳跃链表跳表的创建跳表的删除跳表的插入跳表的查找跳表的输出图 1.1 功能模块图第 2 章 详细设计2.1 菜单选项模块控制整个程序的运行，控制菜单操作，通过主函数模块分别调用各个模块，实现各项功能，流程如图 2.1 所示。沈阳航空航天大学课程设计报告 第 2 章 详细设计- 3 -0541 2 3跳表的输出跳表的删除输入 aa 的值开始输出主菜单选项结束跳表的插入跳表的查找跳表的创建图 2.1 主模块流程图1）输出主菜单，输入 a 的值；2）如果 a=1，进行跳表的创建；如果 a=2，进行跳表的查找；如果 a=3，进行跳表的插入；如果 a=4，进行跳表的删除；如果 a=5，进行跳表的输出；如果a=0，结束程序。2.2 跳表的创建输入所需的数值，并以负数结束输入。函数先创建一个普通的一级链表，然后通过跳表的升级，分别将相隔为二的结点升级成二级链表，相隔为三的结点升级成三级链表。算流程如图 2.2 所示。沈阳航空航天大学课程设计报告 第 2 章 详细设计- 4 -是否创建头结点，并将各个结点连接，创建成一级链表通过 update ( )函数，分别将相隔二的，创建为二级链表，相隔为散的创建为三级链表。Creat（）返回主菜单判断输入的值是否为升序，图 2.2 函数 Creat（）流程图注释：1）创建头结点，并将各个结点连接，创建成一级链表2）通过 update ( )函数，分别将相隔二的，创建为二级链表，相隔为散的创建为三级链表。3）判断输入的值是否为升序。3）返回主函数。2.3 跳表的查找通过从跳表的三级链表确定一个大范围，再从跳表的二级链表确定一个小范围，最后在在一级中找到所要查找的数。如图 2.3沈阳航空航天大学课程设计报告 第 2 章 详细设计- 5 -Y确定数值在跳表的三级链表的范围确定数值在跳表的二级链表的范围Search ( )返回结果查找该数值在以上范围内是否存在。图 2.3 Search ( )函数流程图注释：1）确定数值在跳表的三级链表的范围。2）确定数值在跳表的二级链表的范围。3）查找该数值在以上范围内是否存在。4）返回结果。2.4 跳表的插入通过跳表的查找确定插入数值的地址，再在该位置出入结点，然后再通过跳表的升级，形成一个新的跳表。流程如图 2.4 所示。沈阳航空航天大学课程设计报告 第 2 章 详细设计- 6 -通过跳表的查找确定插入数值的地址Insert ( )插入结点通过跳表的升级，形成一个新的跳表返回主函数图 2.4Insert ( )模块图注释：1）通过跳表的查