數(shù)據(jù)結(jié)構(gòu)課程設計報告---skiplist基本操作

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：docx 頁數(shù)：15 大?。?13.12KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩14頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)　　課程設計報告　　題目 SkipList基本操作 　　專業(yè)年級 　　組員

2、 　　指導教師 　　目錄　　一.問題描述………………………………………………3　　二.系統(tǒng)概要設計…………………………………………3　　1類的

3、設計………………………………………3　　2主要函數(shù)設計…………………………………3　　三.詳細設計………………………………………………4　　四.系統(tǒng)測試………………………………………………13　　五.時間復雜度分析……………………………………… 14

4、　　1查找的時間復雜度分析………………………14　　2插入和刪除的時間復雜度分析………………14　　六.任務分配………………………………………………14　　七.參考文獻………………………………………………14　　八.總結(jié)及心得體會……………………………

5、…………15　　一.問題描述　　跳躍表（Skip List）簡單地說是增加了向前指針的鏈表.它是1987年才誕生的一種嶄新的數(shù)據(jù)結(jié)構(gòu)，通過在有序鏈表上的全部或部分節(jié)點增加額外的指針,來提高搜索性能。在進行查找、插入、刪除等操作時的期望時間復雜度均為O(logn),有著近乎替代平衡樹的本領(lǐng)。而且最重要的一點，就是它的編

6、程復雜度較同類的AVL樹，紅黑樹等要低得多，這使得其無論是在理解還是在推廣性上，都有著十分明顯的優(yōu)勢。　　跳躍表由多條鏈構(gòu)成（S0，S1，S2 ……，Sh），且滿足如下三個條件：　　每條鏈必須包含兩個特殊元素：+∞ 和 -∞　　S0包含所有的元素，并且所有鏈中的元素按照升序排列。<p

7、>　　每條鏈中的元素集合必須包含于序數(shù)較小的鏈的元素集合，即：　　要求：編程實現(xiàn)跳躍表的初始化、查找、刪除、插入等操作。　　二.系統(tǒng)概要設計　　1.類的設計　?。?）跳表結(jié)點類SkipNod

8、e　?。?）跳表類SkipList　　私有成員： 　　maxLevel 允許的跳表最高級別　　level 當前非空鏈的最高級別　　TailKey 最

9、后一個結(jié)點里放的正無窮　　SkipNode<T>* head 附加頭結(jié)點指針　　SkipNode<T>* tail 附加尾結(jié)點指針　　SkipNode<T>** last 每條鏈上的最后一個元素的指針　　setGrad

10、e(int* grade,int L,int H,int lev) 為從L到H之間的元素分配lev級別　　randLevel() 在[0,level]之間隨機產(chǎn)生一個級別　　公有成員： 　　SkipList(T large,int maxLev) 構(gòu)造函數(shù)

11、　　CreateSkipList(T* A,int n) 創(chuàng)建跳表　　~SkipList() 析構(gòu)函數(shù)　　Display() 顯示各級鏈表　　SkipNode<T>* Search(T x) 搜索指定元素

12、Exist(T x) 判斷元素在跳表中是否存在　　Insert(T x) 跳表中插入元素　　Remove(T x) 刪除跳表中指定值的結(jié)點　　2主要函數(shù)設計　　CreateSkipList(T* A,int n)

13、　　作用：創(chuàng)建跳表　　參數(shù)表：A[] 創(chuàng)建跳躍表的數(shù)組　　n 數(shù)組元素個數(shù)　　算法思想：跳表的最下層組成一普通單鏈表，第21，2?21， 3?21，…結(jié)點鏈接成為第一層鏈接，第22，2?22， 3?22，…成為第二層鏈接…一個有n個元素的跳表有級數(shù)

14、level=int（log（n）/log(2)）.　　利用setGrade()函數(shù)為每個結(jié)點分配級別，并把級別存入grade數(shù)組。將A 中數(shù)建立各級鏈表。　?。?）Search(T x)　　作用：搜索指定值的x的結(jié)點指針　　參數(shù)表：x 要搜索的元素

15、　　算法思想：游標指針從最高級鏈的第一個元素開始，如果找到就返回當前指針，如果x比當前結(jié)點大就繼續(xù)向后，如果比當前結(jié)點小就降級，若未找到就返回尾指針的值。　?。?）Exist(T x)　　作用：判斷元素是否存在　　參數(shù)表：x 要判斷的元素　　算法思想

16、：原理同Search(T x)，返回值不同。　　（4）Insert(T x)將　　作用：元素插入跳表　　參數(shù)表：x 要插入的元素　　算法思想:從最高級別開始向下搜索，如果x小于ptr下個結(jié)點的值，將當前ptr記錄到數(shù)組中，到下級搜索

17、，如果大于則繼續(xù)搜索，為插入的結(jié)點分配級別后插入各級鏈表中　?。?）Remove(T x)　　作用：從鏈表中刪除元素　　參數(shù)表：x要刪除的元素　　算法思想：從最高級別開始向下搜索，找到后記錄下當前刪除節(jié)點的前驅(qū)指針，繼續(xù)降級，從各級鏈表中刪除<

18、;p>　　三.詳細設計　　#include<iostream.h>　　#include<stdlib.h>　　#include<cmath>　　#include<ctime><

19、;/p>　　#define DefaultSize 12　　//SkipNode結(jié)構(gòu) 跳表的結(jié)點聲明和定義,E為結(jié)點數(shù)據(jù)域類型,K為關(guān)鍵碼的類型　　template<class T>　　struct SkipNode<b&g

20、t;　　{　　T data; //數(shù)據(jù)域　　SkipNode<T>** link; //指針域數(shù)組　　SkipNode(T x,int size=DefaultSize)//構(gòu)造函數(shù)

21、　　{　　data=x;　　link=new SkipNode<T>*[size];　　//如果內(nèi)存分配失敗　　if(link==NULL)

22、　　{　　cout<<"內(nèi)存分配失敗!"<<endl;　　exit(1);　　};　　//把指

23、針數(shù)組初始化為NULL　　for(int i=0;i<size;i++)　　link[i]=NULL;　　};　　~SkipNode() //析構(gòu)函數(shù)<p&

24、gt;　　{delete [] link;};　　};　　//SkipList類模板跳表的類模板即通過多級鏈表的組織方式提高搜索的效率,0級鏈表的排列順序是從左到右升序　　template<class T>　　clas

25、s SkipList　　{　　private:　　int maxLevel; //允許的跳表最高級別　　int level; //當前非空鏈的最高級別</p

26、>　　T TailKey; //最后一個結(jié)點里放的正無窮　　SkipNode<T>* head; //附加頭結(jié)點指針　　SkipNode<T>* tail; //附加尾結(jié)點指針　　SkipNode<T>** last;

27、//每條鏈上的最后一個元素的指針　　//為從L到H之間的元素分配lev級別　　void setGrade(int* grade,int L,int H,int lev);　　//在[0,level]之間隨機產(chǎn)生一個級別　　int randLevel();

28、;　　public:　　//構(gòu)造函數(shù)　　SkipList(T large,int maxLev);　　//通過描述數(shù)組來創(chuàng)建一個跳表　　void CreateSkipList

29、(T* A,int n);　　//析構(gòu)函數(shù)　　~SkipList();　　//顯示各級鏈表的內(nèi)容　　void Display();　　//搜索指定內(nèi)容x的結(jié)點<p

30、>　　SkipNode<T>* Search(T x);　　//判斷元素在跳表中是否存在　　bool Exist(T x);　　//把指定的元素x插入到當前的跳表中去　　bool Insert(T x);　　//

31、刪除跳表中指定值的結(jié)點　　bool Remove(T x);　　};　　//構(gòu)造函數(shù) 構(gòu)造一個空鏈表　　template<class T>　　SkipList<T>:

32、:SkipList(T large,int maxLev)　　{　　maxLevel=maxLev; //初始化最高級別　　level=0; //當前初始級別為0級　　TailKey=large;

33、 //為結(jié)點中的最大關(guān)鍵碼　　//創(chuàng)建附加頭結(jié)點　　head=new SkipNode<T>(-1000,maxLevel+1);　　//創(chuàng)建一個附加尾結(jié)點　　tail=new SkipNode<T>(T

34、ailKey,maxLevel+1);　　//為last數(shù)組開辟內(nèi)存,并進行初始化　　last=new SkipNode<T>*[maxLevel];　　for(int i=0;i<=maxLevel;i++)　　last[i]=head;</p&

35、gt;　　//讓head附加頭結(jié)點里的指針全部指向tail,表示鏈表空　　for(i=0;i<=maxLevel;i++)　　head->link[i]=tail;　　};　　//析構(gòu)函數(shù),釋放跳表的

36、內(nèi)存空間　　template<class T>　　SkipList<T>::~SkipList()　　{　　//游標指針　　Ski

37、pNode<T>* ptr=head;　　SkipNode<T>* pre=head;　　//依次刪除每個結(jié)點　　while(pre!=NULL)　　{　　//把ptr

38、先移到后面的鏈表頭　　ptr=ptr->link[0];　　//釋放pre結(jié)點的空間　　delete pre;　　pre=ptr;　　};</

39、p>　　};　　//Display()公有成員函數(shù),顯示各級鏈表的內(nèi)容　　template<class T>　　void SkipList<T>::Display()

40、;　　{　　//游標指針　　SkipNode<T>* ptr=head;　　//遍歷各級鏈表　　for(int i=0;i<=level;i++)</p

41、>　　{　　cout<<i<<"級鏈:";　　ptr=head->link[i];　　while(ptr!=tail)　　{</b&

42、gt;　　cout<<ptr->data<<" ";　　ptr=ptr->link[i];　　}　　cout<<endl;&

43、lt;b>　　};　　};　　//CreateSkipList()公有成員函數(shù),通過描述數(shù)組串創(chuàng)建跳表　　template<class T>　　void SkipList<T>::Cr

44、eateSkipList(T* A,int n)　　{ 　　int* grade=new int[n]; //存放級數(shù)的數(shù)組　　for(int i=0;i<n;i++) //把級別數(shù)組初始化為0　　grade[

45、i]=0;　　level=int(log(n)/log(2));//根據(jù)n求最大級別　　//為每個結(jié)點分配級別，并把級別存入grade數(shù)組　　setGrade(grade,0,n-1,level);　　//先把A中的取出來建立各級鏈表<p&g

46、t;　　for(i=0;i<n;i++)　　{　　//新建一個結(jié)點　　SkipNode<T>* newNode=new SkipNode<T>(A[i]);　　//建

47、立第i個結(jié)點的各級鏈表　　for(int j=0;j<=grade[i];j++)　　{　　//掛入第j級鏈中　　last[j]->link[j]=newNode;

48、　　//第j級游標指針向后推進　　last[j]=newNode;　　};　　};　　//掛上附加尾結(jié)點<

49、p>　　for(i=0;i<=level;i++)　　last[i]->link[i]=tail;　　//釋放grade數(shù)組的空間　　delete [] grade;　　};

50、　　//Search()公有成員函數(shù),在跳表中搜索指定值x的元素的結(jié)點指針　　template<class T>　　SkipNode<T>* SkipList<T>::Search(T x)　　{

51、　//游標指針從最高級鏈的第一個元素開始　　SkipNode<T>* ptr=head->link[level];　　//當前級別鏈表的回溯指針　　SkipNode<T>* base=head;　　int grade=level;</p

52、>　　//從最高級鏈開始依次往下搜索　　//在第grade級鏈中進行搜索　　while(base!=tail && grade!=-1)　　{　　//如果找到就返回當前結(jié)點指針</p&

53、gt;　　if(x==ptr->data)　　return ptr;　　//如果x比當前結(jié)點大,就繼續(xù)向后　　else if(x>ptr->data)　　{<p&g

54、t;　　base=ptr;　　ptr=ptr->link[grade];　　}　　//如果x比當前結(jié)點小,就降級　　else if(x<ptr->data)

55、　　{　　//從次級的base重新開始搜索　　grade--;　　ptr=base->link[grade];　　};</p&

56、gt;　　};　　//如果沒有找到就返回尾指針的值　　return tail;　　};　　//Exist()公有成員函數(shù),判斷元素x在當前跳表中是否存在

57、　　template<class T>　　bool SkipList<T>::Exist(T x)　　{　　//游標指針從最高級鏈的第一個元素開始　　SkipNode<T>* p

58、tr=head->link[level];　　//當前級別鏈表的回溯指針　　SkipNode<T>* base=head;　　int grade=level;　　//從最高級鏈開始依次往下搜索　　//在第grad

59、e級鏈中進行搜索　　while(base!=tail && grade!=-1)　　{　　//如果找到就返回真　　if(x==ptr->data)　　return tru

60、e;　　//如果x比當前結(jié)點大,就繼續(xù)向后　　else if(x>ptr->data)　　{　　base=ptr;　　ptr=ptr->

61、link[grade];　　}　　//如果x比當前結(jié)點小,就降級　　else if(x<ptr->data)　　{　　//從次級的base重新

62、開始搜索　　grade--;　　ptr=base->link[grade];　　};　　};　　//如果沒有找

63、到就返回假　　return false;　　};　　//Insert()公有成員函數(shù),把元素x插入到當前的跳表中去,成功就返回true　　template<class T>　　bo

64、ol SkipList<T>::Insert(T x)　　{　　//如果元素已經(jīng)存在就返回false　　if(Exist(x)||x>TailKey)　　return false;<p&

65、gt;　　//為新元素創(chuàng)建新的結(jié)點　　SkipNode<T>* newNode=new SkipNode<T>(x);　　//用于存放要插入的結(jié)點前在各級鏈表中的指針　　SkipNode<T>** preLoc=new SkipNode<T>*[level+1];&

66、lt;/p>　　//游標指針　　SkipNode<T>* ptr=head;　　//從最高級別開始向下搜索　　int grade=level;　　//尋找新結(jié)點在各級鏈表中插入位置</p&

67、gt;　　while(grade!=-1)　　{　　//如果x小于ptr下個結(jié)點的值　　if(x<ptr->link[grade]->data)　　{<

68、;/p>　　//把當前的ptr記錄到preLoc數(shù)組中　　preLoc[grade]=ptr;　　//來到下級鏈繼續(xù)進行搜索　　grade--;　　}

69、;　　//如果x大于ptr下個結(jié)點的值　　else if(x>ptr->link[grade]->data)　　ptr=ptr->link[grade];　　};　　//為待插入的結(jié)點隨機

70、分配級別　　int g=randLevel();　　//把新結(jié)點newNode插入到各級鏈表中　　for(int i=g;i>=0;i--)　　{　　//把新結(jié)點掛入第i級鏈表中<

71、/p>　　newNode->link[i]=preLoc[i]->link[i];　　preLoc[i]->link[i]=newNode;　　};　　return true;<b&

72、gt;　　};　　Remove()公有成員函數(shù),刪除跳表中指定值的元素結(jié)點　　template<class T>　　bool SkipList<T>::Remove(T x)　　{</

73、p>　　//如果指定的元素不存在　　if(!Exist(x))　　return false;　　//用于存放要刪除的結(jié)點前在各級鏈表中的指針　　SkipNode<T>** preLoc=new SkipNode<T>*[

74、level+1];　　//把該數(shù)組初始化為NULL　　for(int i=0;i<=level+1;i++)　　preLoc[i]=NULL;　　//游標指針　　SkipNode<

75、T>* ptr=head;　　//從最高級別開始向下搜索　　int grade=level;　　//尋找新結(jié)點在各級鏈表中插入位置　　while(grade!=-1)　　{</p&

76、gt;　　//如果x小于ptr下個結(jié)點的值　　if(ptr->link[grade]->data>x)　　//x在當前級的鏈表中不存在,　　//來到下級鏈繼續(xù)進行搜索　　grade--;<

77、/p>　　//如果x大于ptr下個結(jié)點的值　　else if(ptr->link[grade]->data<x)　　ptr=ptr->link[grade];　　//如果等于ptr下個結(jié)點的值　　else if(ptr-

78、>link[grade]->data==x)　　{　　//記錄下當前要刪除結(jié)點的前驅(qū)指針　　preLoc[grade]=ptr;　　//繼續(xù)降級

79、;　　grade--;　　};　　};　　//把該元素在各級鏈中進行刪除　　for(i=0;preLoc[i]!=NULL;i++)&

80、lt;p>　　preLoc[i]->link[i]=preLoc[i]->link[i]->link[i];　　return true;　　};　　setGrade()私有成員函數(shù),把下表從L到H的結(jié)點分配lev的級數(shù)<p

81、>　　template<class T>　　void SkipList<T>::setGrade(int* grade,int L,int H,int lev)　　{　　//如果下界小于上界　　if(L&

82、lt;H && lev>0)　　{　　//取中間元素　　int q=int((L+H)/2);　　//設置該元素的級別　　grade

83、[q]=lev;　　//遞歸設置q左右的結(jié)點　　setGrade(grade,L,q-1,lev-1);　　setGrade(grade,q+1,H,lev-1);　　};

84、　};　　//randLevel()私有成員函數(shù)，在[0,level]之間隨機產(chǎn)生一個級別　　template<class T>　　int SkipList<T>::randLevel()　　{</b&g

85、t;　　srand(time(0));　　return rand()%(level+1);　　};　　void main()　　{

86、　　int e=1000,d=4;　　SkipList<int> s(e,d);　　int sp[12]={1,3,5,12,15,18,21,32,35,45,55,66};　　s.CreateSkipList(sp,12); //產(chǎn)生跳表

87、　　s.Display();//輸出原始跳表　　int k=1;　　while(k!=4) //操作菜單的設計　　{　　cout<<"1.搜索元素\n";<

88、/p>　　cout<<"2.刪除元素\n";　　cout<<"3.添加元素\n";　　cout<<"4.結(jié)束操作\n";　　cin>>k;&

89、lt;/p>　　switch(k)　　{　　case 1:cout<<"輸入搜索的元素"<<endl;　　int a;<

90、/p>　　cin>>a; 　　if(s.Search(a)->data==1000)　　{cout<<"該值不存在！\n"<<'\n';}　　else

91、　　{　　cout<<"元素:"<<s.Search(a)->data<<"存在\n"<<'\n';　　}&

92、lt;/p>　　break;　　case 2:cout<<"輸入刪除的元素"<<endl;　　int b;　　cin>>b;</

93、b>　　if(s.Search(b)->data==1000)　　{cout<<"該值不存在！\n"<<'\n';}　　else　　{<

94、/b>　　s.Remove(b);　　cout<<"刪除后跳表顯示："<<endl;　　s.Display();　　}　　b

95、reak;　　case 3:cout<<"輸入添加的元素"<<endl;　　int c;　　cin>>c;　　if(s

96、.Search(b)->data!=1000)　　{　　cout<<"添加的值已經(jīng)存在\n";　　}　　else<

97、/p>　　{　　s.Insert(c);　　cout<<"添加后跳表顯示："<<endl;　　s.Display();　　}

98、　　break;　　case 4:;　　}　　}　　}&

99、lt;/b>　　四.系統(tǒng)測試　　五.時間復雜度分析　　1.查找的時間復雜度分析O(logn)　　我們采用逆向分析的方法。假設我們現(xiàn)在在目標節(jié)點，想要走到跳躍表最左上方的開始節(jié)點。這條路徑的長

100、度，即可理解為查找的時間復雜度。　　設當前在第i層第j列那個節(jié)點上。　　如果第j列恰好只有i層（對應插入這個元素時第i次調(diào)用隨機化模塊時所產(chǎn)生的B決策，概率為1-p），則當前這個位置必然是從左方的某個節(jié)點向右跳過來的。　　如果第j列的層數(shù)大于i（對應插入這個元素時第i次調(diào)用隨機化模塊時所產(chǎn)生的A決策，概率為p），

101、則當前這個位置必然是從上方跳下來的。（不可能從左方來，否則在以前就已經(jīng)跳到當前節(jié)點上方的節(jié)點了，不會跳到當前節(jié)點左方的節(jié)點）　　設C(k)為向上跳k層的期望步數(shù)（包括橫向跳躍）　　有：　　C(0) = 0<p

102、>　　C(k) = (1-p)(1+向左跳躍之后的步數(shù))+p(1+向上跳躍之后的步數(shù))　　= (1-p)(1+C(k)) + p(1+C(k-1))　　C(k) = 1/p + C(k-1)　　C(k) = k/p　　每個元素插入到第i層（Si）的概率為p^i

103、60;，則在第i層插入的期望元素個數(shù)為np^(i-1)。h層的元素期望個數(shù)為 np^0+np^1+...+np^(h-1)，當n取較大數(shù)時，這個式子的值接近0，故跳躍表的高度為O(logn)級別，故查找的復雜度也為logn級別。　　對于記憶化查找（Search with fingers）技術(shù)我們可以采用類似的方法分析，很容易得出它的復雜度是O(logk)的（其中k為此次與前一次兩個被查

104、找元素在跳躍表中位置的距離）。　　2.插入和刪除的時間復雜度分析O(logn)　　插入和刪除都由查找和更新兩部分構(gòu)成。查找的時間復雜度為O(logn)，更新部分的復雜度又與跳躍表的高度成正比，即也為O(logn)。所以，插入和刪除操作的時間復雜度都為O(logn)　　六.任務分配</b&g

105、t;　　此次本小組共3個成員，任務分配如下：　　XXX：主要負責跳表的初始化，主函數(shù)的編寫　　XXX：主要負責跳表的查找和插入功能的編寫　　XXX：主要負責跳表的刪除功能的編寫及整個程序的整合　　七.參考文獻&l

106、t;/b>　　1．《數(shù)據(jù)結(jié)構(gòu)（C++版）》　　2．《Visual C++程序設計》　　3．《數(shù)據(jù)結(jié)構(gòu)課程設計實例》　　八.總結(jié)及心得體會　　剛拿到這個題目的時候,我們花了很長的時間,研究

107、這個結(jié)構(gòu).從最初的模糊,然后收集整理資料,經(jīng)過討論,到最后的構(gòu)造.我們收獲了很多.　　經(jīng)過這次的課程設計，我們加深了對書本上普通鏈表的理解，同時也對skip list跳表有了一定的深入了解，理解了跳表的原理，跳表的查找，插入，刪除等基本操作原理。以及跳表在時間復雜度上的優(yōu)勢。對我們自身而言，也是一種編程水平的提高，同時也培養(yǎng)了我們的團隊合作能力。以后我們也會多加練習編寫程序的能力，培養(yǎng)獨立思考，

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設計報告---skiplist基本操作

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設計報告---skiplist基本操作

文檔簡介

溫馨提示

最新文檔

評論

免費下載