實驗三 跳表算法設計與實現，實驗跳表算法
一、實驗名稱：跳表算法設計與實現
二、實驗目的：
三、實驗內容
完善下列程序，並回答問題。
![]()
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(){ // zengjiabufei
25 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; //尾結點中保存作為哨兵值的最大值large
62 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 }
View Code
程序問題
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, 觀察運行結果。
