首页 > 代码库 > 实验三 跳表算法设计与实现
实验三 跳表算法设计与实现
一、实验名称：跳表算法设计与实现
二、实验目的：
- 掌握跳表的数据结构。
- 掌握跳表插入算法的思想和实现。
三、实验内容
完善下列程序，并回答问题。
1 #include <iostream.h> 2 #include<stdlib.h> 3 4 enum ResultCode{Underflow, Overflow, Success, Duplicate, RangeError, NotPresent}; 5 template <class T> 6 struct SNode 7 { 8 SNode(int mSize) 9 {10 link=new SNode* [mSize];11 }12 ~SNode(){ delete[] link;}13 T element;14 SNode<T>**link;15 };16 17 template<class T>18 class SkipList 19 {20 public:21 SkipList(T large, int mLev); 22 ~SkipList(){};23 ResultCode Insert(T x); //函数定义见3.1.1节24 void printList(){ // zengjiabufei25 SNode<T> *p;26 for(int le = levels; le>=0;le--){27 p = head->link[le];28 cout<<"head->";29 SNode<T> *q;30 q = head->link[0];31 while(p != tail){32 while(q->element != p->element){33 cout<<"---";34 q = q->link[0];35 } 36 if(p->element<10) cout<<"-";37 cout<<p->element;38 cout<<"-";39 p = p->link[le];40 q = q->link[0];41 }42 while(q!= tail){cout<<"---";q = q->link[0];}43 cout<<"tail";44 cout<<endl;45 }46 };47 private:48 int Level();49 SNode<T>* SaveSearch(T x);50 int maxLevel, levels;51 SNode<T> *head, *tail, **last;52 };53 54 template <class T>55 SkipList<T>::SkipList(T large, int mLev)56 {57 maxLevel=mLev; levels=0;58 head=new SNode<T>(maxLevel+1); //指向包括元素域和maxLevel+1个指针的头结点59 tail=new SNode<T>(0); //指向只有元素域，不包含指针域的尾结点60 last=new SNode<T>*[maxLevel+1]; //maxLevel+1个指针61 tail->element=large; //尾结点中保存作为哨兵值的最大值large62 for (int i=0; i<=maxLevel; i++)63 head->link[i]=tail; //头结点的所有指针指向尾结点64 }65 66 template <class T>67 int SkipList<T>::Level()68 {69 学生书写部分70 }71 72 template <class T>73 SNode<T>* SkipList<T>::SaveSearch(T x)74 {75 学生书写部分76 }77 template <class T>78 ResultCode SkipList<T>::Insert(T x)79 {80 学生书写部分81 }82 83 void main(){84 int maxlevel = 5;85 SkipList<int> slist(10000,maxlevel);86 int ele[30] = {3,7,19,22,70,28,43,2,6,18,21,69,47,42};87 int n = 14;88 cout<<"---跳表---"<<endl<<endl;89 cout<<"分别插入的数字为：";90 for(int j = 0; j < n; j++) cout<<ele[j]<<",";91 cout<<"\n初始状态：\n";92 slist.printList();93 for(int i = 0; i < n; i++) {94 slist.Insert(ele[i]);95 cout<<"\n插入"<<ele[i]<<"后"<<endl;96 slist.printList();97 }98 }
程序问题
1. SkipList的构造函数中，参数large和mLev分别代表什么语义？程序insert中，if(lev>levels) 语句的作用是什么？
2. 分析跳表插入算法，给出插入算法的流程图，或者描述算法思想。
3. 如果输入3,7,19,22,70,28,43,2,6,18,21,69,47,42，实际运行的跳表的最终结构是：
4. 如果输入1到30，层数为7时，实际运行最终的跳表结构是什么。
5. （选做）新建新的程序文件，在上述程序的基础上，修改插入算法，使之可以允许插入重复元素，并输入3,7,19,22,70,28,43,2,6,18,21,69,47,42,3,7,19,22,70,28,43,2,6,18,21,69,47,42, 观察运行结果。
实验三 跳表算法设计与实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。