數據結構課程設計報告---skiplist基本操作

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

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

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　數據結構　　課程設計報告　　題目 SkipList基本操作 　　專業(yè)年級 　　組員

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、;/p>　　#define DefaultSize 12　　//SkipNode結構跳表的結點聲明和定義,E為結點數據域類型,K為關鍵碼的類型　　template<class T>　　struct SkipNode<b&g

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

39、p>　　};　　//Display()公有成員函數,顯示各級鏈表的內容　　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()公有成員函數,通過描述數組串創(chuàng)建跳表　　template<class T>　　void SkipList<T>::Cr

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

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

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

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

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

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

50、　　//Search()公有成員函數,在跳表中搜索指定值x的元素的結點指針　　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)　　{　　//如果找到就返回當前結點指針</p&

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

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

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

56、gt;　　};　　//如果沒有找到就返回尾指針的值　　return tail;　　};　　//Exist()公有成員函數,判斷元素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比當前結點大,就繼續(xù)向后　　else if(x>ptr->data)　　{　　base=ptr;　　ptr=ptr->

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

78、>link[grade]->data==x)　　{　　//記錄下當前要刪除結點的前驅指針　　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()私有成員函數,把下表從L到H的結點分配lev的級數<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左右的結點　　setGrade(grade,L,q-1,lev-1);　　setGrade(grade,q+1,H,lev-1);　　};

84、　};　　//randLevel()私有成員函數，在[0,level]之間隨機產生一個級別　　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); //產生跳表

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

88、/p>　　cout<<"2.刪除元素\n";　　cout<<"3.添加元素\n";　　cout<<"4.結束操作\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<<"添加的值已經存在\n";　　}　　else<

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

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

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

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

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

102、>　　C(k) = (1-p)(1+向左跳躍之后的步數)+p(1+向上跳躍之后的步數)　　= (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層插入的期望元素個數為np^(i-1)。h層的元素期望個數為 np^0+np^1+...+np^(h-1)，當n取較大數時，這個式子的值接近0，故跳躍表的高度為O(logn)級別，故查找的復雜度也為logn級別。　　對于記憶化查找（Search with fingers）技術我們可以采用類似的方法分析，很容易得出它的復雜度是O(logk)的（其中k為此次與前一次兩個被查

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

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

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

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

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

溫馨提示

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

數據結構課程設計報告---skiplist基本操作

文檔簡介

溫馨提示

最新文檔

評論

數據結構課程設計報告---skiplist基本操作

文檔簡介

溫馨提示

最新文檔

評論

免費下載