數(shù)據(jù)結(jié)構(gòu)課設(shè)之跳躍鏈表

桂林電子科技大學(xué)綜合設(shè)計(jì)說(shuō)明書用紙《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)說(shuō)明書題目：跳躍鏈表的實(shí)現(xiàn)學(xué)院：計(jì)算機(jī)科學(xué)與工程專業(yè)：信息安全姓名：學(xué)號(hào)：指導(dǎo)教師：張瑞霞2014年10月21日（請(qǐng)將以下內(nèi)容放入封面后面）成績(jī)?cè)u(píng)定標(biāo)準(zhǔn)及成績(jī)能按照格式進(jìn)行寫作，無(wú)抄襲現(xiàn)象（10分）報(bào)告內(nèi)容行文通暢，有條理性，無(wú)錯(cuò)別字，結(jié)構(gòu)嚴(yán)謹(jǐn)。（10分）能夠按照數(shù)據(jù)結(jié)構(gòu)課設(shè)的格式要求、排版要求和字?jǐn)?shù)要求等，有需求分析，系統(tǒng)分析，詳細(xì)設(shè)計(jì)，關(guān)鍵技術(shù)的介紹和參考文獻(xiàn)。（10分）在驗(yàn)收過(guò)程中，能合理的回答問(wèn)題（20分）軟件能正常運(yùn)行，實(shí)現(xiàn)所提出的功能（40分）軟件代碼規(guī)范性較好（5分）具有自己的創(chuàng)新或特色（5分）總成績(jī)：摘要SkipList是一種隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)，基于并聯(lián)的鏈表，其效率可比擬于二叉查找樹(shù)（對(duì)于大多數(shù)操作需要O(logn)平均時(shí)間）?；旧希S列表是對(duì)有序的鏈表增加上附加的前進(jìn)鏈接，增加是以隨機(jī)化的方式進(jìn)行的，所以在列表中的查找可以快速的跳過(guò)部分列表(因此得名)。所有操作都以對(duì)數(shù)隨機(jī)化的時(shí)間進(jìn)行。SkipList可以很好解決有序鏈表查找特定值的困難。跳躍鏈表在進(jìn)行查找、插入、刪除等操作時(shí)的時(shí)間復(fù)雜度均為O(logn),有著近乎替代平衡樹(shù)的本領(lǐng)。而且最重要的一點(diǎn)，就是它的編程復(fù)雜度較同類的AVL樹(shù)，紅黑樹(shù)等要低得多，這使得其無(wú)論是在理解還是在推廣性上，都有著十分明顯的優(yōu)勢(shì)。為測(cè)試跳躍鏈表的查找效率，向讀者介紹跳躍鏈表的基本結(jié)構(gòu)與代碼實(shí)現(xiàn)，本文將劃分為主要三部分。第一部分是概述。它會(huì)從功能、效率等方面對(duì)跳躍表作一個(gè)初步的介紹，并給出其圖形結(jié)構(gòu)，以便讀者對(duì)跳躍表有個(gè)形象的認(rèn)識(shí)。第二部分將介紹跳躍鏈表的測(cè)試系統(tǒng)的具體實(shí)現(xiàn)框架與代碼，并簡(jiǎn)單介紹開(kāi)發(fā)環(huán)境與編程語(yǔ)言。第三部分將介紹跳躍表的三種基本操作——查找，插入和刪除，并對(duì)它們的時(shí)空復(fù)雜度進(jìn)行分析。最后是本次課設(shè)的總結(jié)與系統(tǒng)的優(yōu)缺點(diǎn)評(píng)價(jià)。【關(guān)鍵字】跳躍表高效概率隨機(jī)化目錄HYPERLINK摘要 3HYPERLINK引言 1HYPERLINK1 系統(tǒng)概述 1HYPERLINK2需求分析 1HYPERLINK2.1系統(tǒng)需求 1HYPERLINK2.2開(kāi)發(fā)環(huán)境 4HYPERLINK3詳細(xì)設(shè)計(jì) 6HYPERLINK3.1系統(tǒng)框架 6HYPERLINK3.2主要代碼 7HYPERLINK3.3運(yùn)行界面與測(cè)試結(jié)果 9HYPERLINK3.4復(fù)雜度分析 10HYPERLINK4所遇到的問(wèn)題和分析解決 12HYPERLINK5系統(tǒng)特色與關(guān)鍵技術(shù) 12HYPERLINK5.1特色與關(guān)鍵技術(shù) 12HYPERLINK5.2系統(tǒng)不足之處 14HYPERLINK6結(jié)論及體會(huì) 14HYPERLINK參考文獻(xiàn) 15桂林電子科技大學(xué)綜合設(shè)計(jì)說(shuō)明書用紙第21頁(yè)引言比較幾種常用的數(shù)據(jù)結(jié)構(gòu)，我們不難發(fā)現(xiàn)，以下總結(jié)。數(shù)組作為最常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，在實(shí)現(xiàn)方面簡(jiǎn)單，并且查找高效，但數(shù)組一旦顯式的被申明后，其大小就固定了，不能動(dòng)態(tài)進(jìn)行擴(kuò)充。不利于動(dòng)態(tài)維護(hù)，無(wú)法實(shí)行高效的插入刪除操作，而且一旦數(shù)組的長(zhǎng)度過(guò)長(zhǎng)，容易存在內(nèi)存的浪費(fèi)。鏈表動(dòng)態(tài)維護(hù)靈活，但是空間和時(shí)間額外耗費(fèi)較大；數(shù)組大小固定，元素位置固定，但是操作不靈活，且容易浪費(fèi)空間，但是時(shí)間耗費(fèi)較小，尤其是元素變化不大的時(shí)候效率很高。雙向鏈表比單向的更靈活，但是空間耗費(fèi)也更大二叉樹(shù)支持包括查找、插入、刪除等一系列的操作。但它有一個(gè)致命的弱點(diǎn)，就是當(dāng)數(shù)據(jù)的隨機(jī)性不夠時(shí)，會(huì)導(dǎo)致其樹(shù)型結(jié)構(gòu)的不平衡，從而直接影響到算法的效率。跳躍表（SkipList）作為一種嶄新的數(shù)據(jù)結(jié)構(gòu)，它在進(jìn)行查找、插入、刪除等操作時(shí)的期望時(shí)間復(fù)雜度均為O(logn),有著近乎替代平衡樹(shù)的本領(lǐng)。最為關(guān)鍵的一點(diǎn)，它的編程復(fù)雜度較同類的AVL樹(shù)，紅黑樹(shù)等要低得多，這使得其無(wú)論是在理解還是在推廣性上，都有著十分明顯的優(yōu)勢(shì)。系統(tǒng)概述系統(tǒng)主要使用C++進(jìn)行編寫，中間夾渣一些C的輸出語(yǔ)法。編譯環(huán)境為VC6.0。整體設(shè)計(jì)為結(jié)構(gòu)體與指針構(gòu)成跳躍表。系統(tǒng)在DOS下面運(yùn)行，設(shè)計(jì)有一個(gè)簡(jiǎn)易的跳轉(zhuǎn)界面。開(kāi)始為歡迎界面，用戶首先要選擇選擇手動(dòng)輸入創(chuàng)建跳躍表或者是系統(tǒng)隨機(jī)生成跳躍表，創(chuàng)建完成和剖，進(jìn)入功能功能選擇菜單，用戶可以選擇對(duì)生成跳躍表進(jìn)行查找，增加，或者刪除操作。同時(shí)可選擇進(jìn)行系統(tǒng)查找性能測(cè)試。對(duì)于查找，用戶可以選擇按位置查找或者按值查找。同樣，刪除也具有按位置刪除和按值刪除。2需求分析2.1系統(tǒng)需求跳躍表（SkipList）簡(jiǎn)單地說(shuō)是增加了向前指針的鏈表.它是1987年才誕生的一種嶄新的數(shù)據(jù)結(jié)構(gòu)，通過(guò)在有序鏈表上的全部或部分節(jié)點(diǎn)增加額外的指針,來(lái)提高搜索性能。在進(jìn)行查找、插入、刪除等操作時(shí)的期望時(shí)間復(fù)雜度均為O(logn),有著近乎替代平衡樹(shù)的本領(lǐng)。而且最重要的一點(diǎn)，就是它的編程復(fù)雜度較同類的AVL樹(shù)，紅黑樹(shù)等要低得多，這使得其無(wú)論是在理解還是在推廣性上，都有著十分明顯的優(yōu)勢(shì)。跳躍表由多條鏈構(gòu)成（S0，S1，S2……，Sh），且滿足如下三個(gè)條件：每條鏈必須包含兩個(gè)特殊元素：+∞和-∞S0包含所有的元素，并且所有鏈中的元素按照升序排列。每條鏈中的元素集合必須包含于序數(shù)較小的鏈的元素集合，即：跳躍鏈表的定義與構(gòu)造：定義：一個(gè)跳表，應(yīng)該具有以下特征：1. 一個(gè)跳表應(yīng)該有幾個(gè)層（level）組成；2. 跳表的第一層包含所有的元素；3. 每一層都是一個(gè)有序的鏈表；4. 如果元素x出現(xiàn)在第i層，則所有比i小的層都包含x；5. 第i層的元素通過(guò)一個(gè)down指針指向下一層擁有相同值的元素；6. 在每一層中，-1和1兩個(gè)元素都出現(xiàn)(分別表示INT_MIN和INT_MAX)；7. Top指針指向最高層的第一個(gè)元素。構(gòu)建有序鏈表：如圖2-1 圖2-1一個(gè)跳躍表如下：如圖2-2

圖2-2構(gòu)造步驟：1、給定一個(gè)有序的鏈表。2、選擇連表中最大和最小的元素，然后從其他元素中按照一定算法（隨機(jī)）隨即選出一些元素，將這些元素組成有序鏈表。這個(gè)新的鏈表稱為一層，原鏈表稱為其下一層。

3、為剛選出的每個(gè)元素添加一個(gè)指針域，這個(gè)指針指向下一層中值同自己相等的元素。Top指針指向該層首元素

4、重復(fù)2、3步，直到不再能選擇出除最大最小元素以外的元素。功能需求：編程實(shí)現(xiàn)跳躍表的初始化、查找、刪除、插入等操作。實(shí)現(xiàn)原理一、查找目的：在跳躍表中查找一個(gè)元素x

在跳躍表中查找一個(gè)元素x，按照如下幾個(gè)步驟進(jìn)行：

1.從最上層的鏈（Sh）的開(kāi)頭開(kāi)始

2.假設(shè)當(dāng)前位置為p，它向右指向的節(jié)點(diǎn)為q（p與q不一定相鄰），且q的值為y。將y與x作比較

(1)x=y輸出查詢成功及相關(guān)信息

(2)x>y從p向右移動(dòng)到q的位置

(3)x3.如果當(dāng)前位置在最底層的鏈中（S0），且還要往下移動(dòng)的話，則輸出查詢失敗二、插入目的：向跳躍表中插入一個(gè)元素x首先明確，向跳躍表中插入一個(gè)元素，相當(dāng)于在表中插入一列從S0中某一位置出發(fā)向上的連續(xù)一段元素。有兩個(gè)參數(shù)需要確定，即插入列的位置以及它的“高度”。關(guān)于插入的位置，我們先利用跳躍表的查找功能，找到比x小的最大的數(shù)y。根據(jù)跳躍表中所有鏈均是遞增序列的原則，x必然就插在y的后面。而插入列的“高度”較前者來(lái)說(shuō)顯得更加重要，也更加難以確定。由于它的不確定性，使得不同的決策可能會(huì)導(dǎo)致截然不同的算法效率。為了使插入數(shù)據(jù)之后，保持該數(shù)據(jù)結(jié)構(gòu)進(jìn)行各種操作均為O(logn)復(fù)雜度的性質(zhì)，我們引入隨機(jī)化算法（RandomizedAlgorithms）。我們定義一個(gè)隨機(jī)決策模塊，它的大致內(nèi)容如下：產(chǎn)生一個(gè)0到1的隨機(jī)數(shù)rr←random()如果r小于一個(gè)常數(shù)p，則執(zhí)行方案A，ifr否則，執(zhí)行方案BelsedoB初始時(shí)列高為1。插入元素時(shí)，不停地執(zhí)行隨機(jī)決策模塊。如果要求執(zhí)行的是A操作，則將列的高度加1，并且繼續(xù)反復(fù)執(zhí)行隨機(jī)決策模塊。直到第i次，模塊要求執(zhí)行的是B操作，我們結(jié)束決策，并向跳躍表中插入一個(gè)高度為i的列。三、刪除目的：從跳躍表中刪除一個(gè)元素x

刪除操作分為以下三個(gè)步驟：（1）在跳躍表中查找到這個(gè)元素的位置，如果未找到，則退出

（2）將該元素所在整列從表中刪除

（3）將多余的“空鏈”刪除使用范圍：面向數(shù)據(jù)結(jié)構(gòu)開(kāi)發(fā)學(xué)習(xí)人員，學(xué)生以及院校任課老師！簡(jiǎn)易，清晰介紹跳躍鏈表定義與構(gòu)造，并編程實(shí)現(xiàn)跳躍表的初始化、查找、刪除、插入等操作。運(yùn)行界面：在DOS系統(tǒng)下面運(yùn)行，其中一個(gè)界面如下：輸出要求：輸出是為讓用戶直觀了解跳躍鏈表的構(gòu)造與使用，在CMD界面下測(cè)試使用，用戶輸入相應(yīng)的數(shù)據(jù)構(gòu)造跳躍鏈表，編程實(shí)現(xiàn)跳躍表的初始化、查找、刪除、插入等操作。故障處理：故障主要出現(xiàn)原因是對(duì)跳躍鏈表不熟悉，需要到圖書館查閱相關(guān)方面書籍或者文獻(xiàn)，網(wǎng)上查找并學(xué)習(xí)相關(guān)資料！同時(shí)對(duì)開(kāi)發(fā)環(huán)境vs2012的不掌握導(dǎo)致，基本使用規(guī)則，調(diào)試工具的使用情況需要熟悉！c++的語(yǔ)法掌握情況也是課設(shè)能否完成的關(guān)鍵，特別是指針，還有鏈表方面知識(shí)需要鞏固！2.2開(kāi)發(fā)環(huán)境操作系統(tǒng)：window7旗艦版開(kāi)發(fā)工具：vc6.0開(kāi)發(fā)語(yǔ)言：C++（1）Windows7旗艦版屬于微軟公司開(kāi)發(fā)的Windows7系統(tǒng)系列中的終結(jié)版本，是為了取代WindowsXP系統(tǒng)的新系統(tǒng)，Windows7的版本還有簡(jiǎn)易版、家庭普通版、家庭高級(jí)版、專業(yè)版。而且旗艦版是所有Windows7系統(tǒng)中是最貴的（正版系統(tǒng)）也是功能最完善的系統(tǒng)。擁有Windows7HomePremium和Windows7Professional的全部功能，，硬件要求與HomePremium和Professional基本相同，沒(méi)有太大差距。（2）VisualC++6.0，簡(jiǎn)稱VC或者VC6.0，是微軟推出的一款C++編譯器，將“高級(jí)語(yǔ)言”翻譯為“機(jī)器語(yǔ)言（低級(jí)語(yǔ)言）”的程序。VisualC++是一個(gè)功能強(qiáng)大的可視化軟件開(kāi)發(fā)工具。自1993年Microsoft公司推出VisualC++1.0后，隨著其新版本的不斷問(wèn)世，VisualC++已成為專業(yè)程序員進(jìn)行軟件開(kāi)發(fā)的首選工具。雖然微軟公司推出了VisualC++.NET(VisualC++7.0)，但它的應(yīng)用的很大的局限性，只適用于Windows2000、WindowsXP和WindowsNT4.0。所以實(shí)際中，更多的是以VisualC++6.0為平臺(tái)。VisualC++6.0不僅是一個(gè)C++編譯器，而且是一個(gè)基于Windows操作系統(tǒng)的可視化集成開(kāi)發(fā)環(huán)境（integrateddevelopmentenvironment，IDE）。VisualC++6.0由許多組件組成，包括編輯器、調(diào)試器以及程序向?qū)ppWizard、類向?qū)lassWizard等開(kāi)發(fā)工具。這些組件通過(guò)一個(gè)名為DeveloperStudio的組件集成為和諧的開(kāi)發(fā)環(huán)境。C++介紹：C++是在C語(yǔ)言的基礎(chǔ)上開(kāi)發(fā)的一種集面向?qū)ο缶幊?、泛型編程和過(guò)程化編程于一體的編程語(yǔ)言[。應(yīng)用較為廣泛，是一種靜態(tài)數(shù)據(jù)類型檢查的，支持多重編程的通用程序設(shè)計(jì)語(yǔ)言。它支持過(guò)程化程序設(shè)計(jì)，數(shù)據(jù)抽象，面向?qū)ο笤O(shè)計(jì)，制作圖標(biāo)等多種程序設(shè)計(jì)風(fēng)格。（3）C++是在C語(yǔ)言的基礎(chǔ)上開(kāi)發(fā)的一種集面向?qū)ο缶幊?、泛型編程和過(guò)程化編程于一體的編程語(yǔ)言。應(yīng)用較為廣泛，是一種靜態(tài)數(shù)據(jù)類型檢查的，支持多重編程的通用程序設(shè)計(jì)語(yǔ)言。它支持過(guò)程化程序設(shè)計(jì)，數(shù)據(jù)抽象，面向?qū)ο笤O(shè)計(jì)，制作圖標(biāo)等多種程序設(shè)計(jì)風(fēng)格。最新正式標(biāo)準(zhǔn)C++14于2014年8月18日公布。C++是一種使用非常廣泛的電腦程序設(shè)計(jì)語(yǔ)言。它是一種靜態(tài)數(shù)據(jù)類型檢查的，支持多范型的通用程序設(shè)計(jì)語(yǔ)言。C++支持過(guò)程化程序設(shè)計(jì)、數(shù)據(jù)抽象化、面向?qū)ο蟪绦蛟O(shè)計(jì)、泛型程序設(shè)計(jì)、基于原則設(shè)計(jì)等多種程序設(shè)計(jì)風(fēng)格。貝爾實(shí)驗(yàn)室的比雅尼?斯特勞斯特魯普博士在20世紀(jì)80年代發(fā)明并實(shí)現(xiàn)了C++。起初，這種語(yǔ)言被稱作“CwithClasses”（“包含類的C語(yǔ)言”），作為C語(yǔ)言的增強(qiáng)版出現(xiàn)。隨后，C++不斷增加新特性。虛函數(shù)（virtualfunction）、操作符重載（operatoroverloading）、多重繼承（multipleinheritance）、模板（template）、異常處理（exception）、RTTI(Runtimetypeinformation)、命名空間（namespace）逐漸納入標(biāo)準(zhǔn)。1998年國(guó)際標(biāo)準(zhǔn)組織（ISO）頒布了C++程序設(shè)計(jì)語(yǔ)言的國(guó)際標(biāo)準(zhǔn)ISO/IEC14882-1998。另外，就目前學(xué)習(xí)C++而言，可以認(rèn)為它是一門獨(dú)立的語(yǔ)言；它并不依賴C語(yǔ)言，我們可以完全不學(xué)C語(yǔ)言，而直接學(xué)習(xí)C++。根據(jù)《C++編程思想》（ThinkinginC++）一書所評(píng)述的，C++與C的效率往往相差在±5%之間。所以有部分人認(rèn)為在大多數(shù)場(chǎng)合中，C++完全可以取代C語(yǔ)言。C++語(yǔ)言發(fā)展大概可以分為三個(gè)階段：第一階段從80年代到1995年。這一階段C++語(yǔ)言基本上是傳統(tǒng)類型上的面向?qū)ο笳Z(yǔ)言，并且憑借著接近C語(yǔ)言的效率，在工業(yè)界使用的開(kāi)發(fā)語(yǔ)言中占據(jù)了相當(dāng)大份額；第二階段從1995年到2000年，這一階段由于標(biāo)準(zhǔn)模板庫(kù)（STL）和后來(lái)的Boost等程序庫(kù)的出現(xiàn)，泛型程序設(shè)計(jì)在C++中占據(jù)了越來(lái)越多的比重性。當(dāng)然，同時(shí)由于Java、C#等語(yǔ)言的出現(xiàn)和硬件價(jià)格的大規(guī)模下降，C++受到了一定的沖擊；第三階段從2000年至今，由于以Loki、MPL等程序庫(kù)為代表的產(chǎn)生式編程和模板元編程的出現(xiàn)，C++出現(xiàn)了發(fā)展歷史上又一個(gè)新的高峰，這些新技術(shù)的出現(xiàn)以及和原有技術(shù)的融合，使C++已經(jīng)成為當(dāng)今主流程序設(shè)計(jì)語(yǔ)言中最復(fù)雜的一員。3詳細(xì)設(shè)計(jì)3.1系統(tǒng)框架本程序主要有五個(gè)功能：創(chuàng)建跳躍表、跳躍表的插入、跳躍表的刪除、跳躍表的輸出、跳躍表的查找、跳躍表的查找性能測(cè)試。跳躍表的插入：這個(gè)是通過(guò)先查找所需要的位置，然后插入數(shù)，最后用表一級(jí)的鏈表生成一個(gè)跳躍表。跳躍表的刪除：這個(gè)是通過(guò)先查找所需要的位置，然后刪除數(shù)，最后用表一級(jí)的鏈表生成一個(gè)跳躍表。跳躍表的查找：這個(gè)是通過(guò)從三級(jí)確定一個(gè)大范圍，再?gòu)亩?jí)確定一個(gè)小范圍，最后在在一級(jí)中找到所要查找的數(shù)。跳躍表的創(chuàng)建：這個(gè)是先創(chuàng)建一個(gè)一級(jí)的普通鏈表，再通過(guò)這個(gè)一級(jí)鏈表形成一個(gè)跳躍表。跳躍表的輸出：這個(gè)是通過(guò)各個(gè)級(jí)用鏈表的方法輸出。跳躍表的查找性能測(cè)試：系統(tǒng)隨機(jī)生成跳躍表，通過(guò)多次查找并統(tǒng)計(jì)查找花費(fèi)次數(shù)，技術(shù)平均查找次數(shù)。系統(tǒng)共計(jì)兩個(gè)菜單界面：主菜單：圖3.1-1跳躍鏈表測(cè)試系統(tǒng)跳躍鏈表測(cè)試系統(tǒng)4退出3開(kāi)發(fā)者信息4退出3開(kāi)發(fā)者信息2輸入創(chuàng)建跳躍鏈表1隨機(jī)創(chuàng)建跳躍鏈表圖3-1功能菜單：圖3-2功能選擇菜單功能選擇菜單按值刪除添加元素顯示跳躍表顯示層數(shù)性能測(cè)試按位置刪除按值查找返回上一級(jí)按位置查找按值刪除添加元素顯示跳躍表顯示層數(shù)性能測(cè)試按位置刪除按值查找返回上一級(jí)按位置查找圖3-23.2主要代碼跳躍表的結(jié)構(gòu)如下：使用結(jié)構(gòu)體定義跳躍表，key表示節(jié)點(diǎn)的位置，value表示值//節(jié)點(diǎn)typedefstructnodeStructure{intkey;intvalue;structnodeStructure*forward[1];}nodeStructure;//跳表typedefstructskiplist{intlevel;nodeStructure*header;}skiplist;跳躍表的查找：由于跳躍表的結(jié)構(gòu)設(shè)置，查找跳躍表可以通過(guò)兩種方式查找，按位置查找、按值查找。為了統(tǒng)計(jì)查找次數(shù)與打印查找路徑，本系統(tǒng)共定義了五條查找函數(shù)。查找代碼基本相似，這里寫出其中一個(gè)查找函數(shù)：//搜索指定key的valueintsearch(skiplist*sl,intkey){nodeStructure*p,*q=NULL;p=sl->header;//從最高層開(kāi)始搜intk=sl->level;for(inti=k-1;i>=0;i--){while((q=p->forward[i])&&(q->key<=key)){if(q->key==key){returnq->value;}p=q;}}returnNULL;}跳躍表的插入：//插入節(jié)點(diǎn)boolinsert(skiplist*sl,intkey,intvalue){nodeStructure*update[MAX_LEVEL];nodeStructure*p,*q=NULL;p=sl->header;intk=sl->level;//從最高層往下查找需要插入的位置//填充updatefor(inti=k-1;i>=0;i--){while((q=p->forward[i])&&(q->key<key)){p=q;}update[i]=p;}//不能插入相同的keyif(q&&q->key==key){returnfalse;}//產(chǎn)生一個(gè)隨機(jī)層數(shù)K//新建一個(gè)待插入節(jié)點(diǎn)q//一層一層插入k=randomLevel();//更新跳表的levelif(k>(sl->level)){for(inti=sl->level;i<k;i++){update[i]=sl->header;}sl->level=k;}q=createNode(k,key,value);//逐層更新節(jié)點(diǎn)的指針，和普通列表插入一樣for(intj=0;j<k;j++){q->forward[j]=update[j]->forward[j];update[j]->forward[j]=q;}returntrue;}跳躍表的刪除：與插入基本相識(shí)，不再寫出。3.3運(yùn)行界面與測(cè)試結(jié)果系統(tǒng)開(kāi)始運(yùn)行界面：開(kāi)始運(yùn)行界面如圖3.3-1所示。用戶可以選擇隨機(jī)創(chuàng)建跳躍鏈表，或者輸入創(chuàng)建跳躍鏈表。用戶選擇1或者2，界面跳轉(zhuǎn)到功能選擇界面圖3.3-2。選擇3可以查看開(kāi)發(fā)者信息與版本號(hào)，選擇4直接退出系統(tǒng)。圖3.3-1功能選擇界面：圖3.3-23.4復(fù)雜度分析一個(gè)數(shù)據(jù)結(jié)構(gòu)的好壞大部分取決于它自身的空間復(fù)雜度以及基于它一系列操作的時(shí)間復(fù)雜度。跳躍表之所以被譽(yù)為幾乎能夠代替平衡樹(shù)，其復(fù)雜度方面自然不會(huì)落后。我們來(lái)看一下跳躍表的相關(guān)復(fù)雜度：空間復(fù)雜度：O(n) （期望）跳躍表高度：O(logn) （期望）相關(guān)操作的時(shí)間復(fù)雜度： 查找： O(logn) （期望） 插入： O(logn) （期望） 刪除： O(logn) （期望） 之所以在每一項(xiàng)后面都加一個(gè)“期望”，是因?yàn)樘S表的復(fù)雜度分析是基于概率論的。有可能會(huì)產(chǎn)生最壞情況，不過(guò)這種概率極其微小。下面我們來(lái)一項(xiàng)一項(xiàng)分析。空間復(fù)雜度分析O(n)假設(shè)一共有n個(gè)元素。根據(jù)性質(zhì)1，每個(gè)元素插入到第i層（Si）的概率為pi-1，則在第i層插入的期望元素個(gè)數(shù)為npi-1，跳躍表的元素期望個(gè)數(shù)為，當(dāng)p取小于0.5的數(shù)時(shí)，次數(shù)總和小于2n。所以總的空間復(fù)雜度為O(n)跳躍表高度分析O(logn)根據(jù)性質(zhì)1，每個(gè)元素插入到第i層（Si）的概率為pi，則在第i層插入的期望元素個(gè)數(shù)為npi-1。考慮一個(gè)特殊的層：第1+層。層的元素期望個(gè)數(shù)為=1/n2，當(dāng)n取較大數(shù)時(shí)，這個(gè)式子的值接近0，故跳躍表的高度為O(logn)級(jí)別的。查找的時(shí)間復(fù)雜度分析O(logn)我們采用逆向分析的方法。假設(shè)我們現(xiàn)在在目標(biāo)節(jié)點(diǎn)，想要走到跳躍表最左上方的開(kāi)始節(jié)點(diǎn)。這條路徑的長(zhǎng)度，即可理解為查找的時(shí)間復(fù)雜度。設(shè)當(dāng)前在第i層第j列那個(gè)節(jié)點(diǎn)上。如果第j列恰好只有i層（對(duì)應(yīng)插入這個(gè)元素時(shí)第i次調(diào)用隨機(jī)化模塊時(shí)所產(chǎn)生的B決策，概率為1-p），則當(dāng)前這個(gè)位置必然是從左方的某個(gè)節(jié)點(diǎn)向右跳過(guò)來(lái)的。如果第j列的層數(shù)大于i（對(duì)應(yīng)插入這個(gè)元素時(shí)第i次調(diào)用隨機(jī)化模塊時(shí)所產(chǎn)生的A決策，概率為p），則當(dāng)前這個(gè)位置必然是從上方跳下來(lái)的。（不可能從左方來(lái)，否則在以前就已經(jīng)跳到當(dāng)前節(jié)點(diǎn)上方的節(jié)點(diǎn)了，不會(huì)跳到當(dāng)前節(jié)點(diǎn)左方的節(jié)點(diǎn)）設(shè)C(k)為向上跳k層的期望步數(shù)（包括橫向跳躍）有：C(0)=0C(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 而跳躍表的高度又是logn級(jí)別的，故查找的復(fù)雜度也為logn級(jí)別。對(duì)于記憶化查找（Searchwithfingers）技術(shù)我們可以采用類似的方法分析，很容易得出它的復(fù)雜度是O(logk)的（其中k為此次與前一次兩個(gè)被查找元素在跳躍表中位置的距離）。插入與刪除的時(shí)間復(fù)雜度分析O(logn) 插入和刪除都由查找和更新兩部分構(gòu)成。查找的時(shí)間復(fù)雜度為O(logn)，更新部分的復(fù)雜度又與跳躍表的高度成正比，即也為O(logn)。 所以，插入和刪除操作的時(shí)間復(fù)雜度都為O(logn)4所遇到的問(wèn)題和分析解決做課設(shè)的時(shí)候并不總是一帆風(fēng)順，當(dāng)遇到問(wèn)題的時(shí)候，總是第一時(shí)間與同學(xué)討論分析或者進(jìn)行百度。寫代碼的時(shí)候，主要遇到這個(gè)問(wèn)題。由于跳躍鏈表的level是隨機(jī)生成的，為了確保跳躍表的值隨機(jī)性與層數(shù)的隨機(jī)性。調(diào)用系統(tǒng)的隨機(jī)數(shù)產(chǎn)生函數(shù)rand();產(chǎn)生隨機(jī)層數(shù)代碼如下：//隨機(jī)產(chǎn)生層數(shù)intrandomLevel(){ //srand((unsigned)time(NULL));intk=1;while(rand()%2)k++;k=(k<MAX_LEVEL)?k:MAX_LEVEL;returnk;}多次測(cè)試表明，該隨機(jī)數(shù)并不是真正的隨機(jī)數(shù)。通過(guò)百度得知，系統(tǒng)的隨機(jī)數(shù)產(chǎn)生是基于一個(gè)線性算法，當(dāng)用戶傳遞一個(gè)參數(shù)進(jìn)入，系統(tǒng)通過(guò)計(jì)算得出相應(yīng)的結(jié)果。由于傳遞參數(shù)不同，導(dǎo)致得到的“隨機(jī)數(shù)”結(jié)果不一樣，用戶可以通過(guò)srand()函數(shù)設(shè)置隨機(jī)數(shù)種子、如果用戶未設(shè)定種子，系統(tǒng)默認(rèn)種子為一，因?yàn)橹盀樵O(shè)置隨機(jī)數(shù)種子，導(dǎo)致每次產(chǎn)生的隨機(jī)數(shù)都一樣。導(dǎo)致跳躍表不具有隨機(jī)性，導(dǎo)致性能測(cè)試不具有可靠性與廣泛性。處理方法：引入系統(tǒng)時(shí)間做隨機(jī)數(shù)種子：#include<time.h>srand((unsigned)time(NULL));由于系統(tǒng)時(shí)間不斷變化，隨機(jī)數(shù)種子不斷變化，似的計(jì)算出來(lái)的隨機(jī)數(shù)具有普遍意義上的隨機(jī)性。5系統(tǒng)特色與關(guān)鍵技術(shù)5.1特色與關(guān)鍵技術(shù)第一：系統(tǒng)的特色在于多個(gè)查找函數(shù)，函數(shù)定義如下：//搜索指定key的valueintsearch(skiplist*sl,intkey)；//查找指定的value所在的keyintsearchbyvalue(skiplist*sl,intvalue)；//搜索指定key的value并返回查找次數(shù)，打印查找路徑intsearchpathkey(skiplist*sl,intkey)；//查找指定的value并返回查找的次數(shù)查找打印查找路徑intsearchpathval(skiplist*sl,intvalue)；//查找指定的value并返回查找的次數(shù)intsearchpath(skiplist*sl,intvalue)；用戶可以通過(guò)多個(gè)查找函數(shù)，選擇多種方式進(jìn)行查找，同時(shí)，刪除函數(shù)也可以選擇兩種方式進(jìn)行查找并刪除。跳躍表節(jié)點(diǎn)定義：typedefstructnodeStructure{intkey;intvalue;structnodeStructure*forward[1];}nodeStructure;由于key,與value兩個(gè)變量，使得用戶在使用跳躍表時(shí)可以有多種方式實(shí)現(xiàn)跳躍表的查詢與刪除。為了追蹤查找路徑，本系統(tǒng)沒(méi)有采用傳統(tǒng)的堆棧結(jié)構(gòu)保存查找路徑，而是在代碼查找的同時(shí)，直接打印出查找路徑：cout<<q->value<<"->";巧妙的化簡(jiǎn)了算法實(shí)現(xiàn)的難度，并減少了運(yùn)行時(shí)間花銷。同時(shí)，為了實(shí)現(xiàn)統(tǒng)計(jì)查找單個(gè)元素所花費(fèi)次數(shù)，使用一個(gè)count變量追蹤代碼，每查找一次：count=count+1;，最終返回count的值：returncount;完整代碼如下：for(inti=k-1;i>=0;i--){while((q=p->forward[i])&&(q->value<=value)){ count=count+1; cout<<q->value<<"->";if(q->value==value){returncount; //break;}p=q;}}第二：跳躍表的構(gòu)造如下跳躍表由多條鏈構(gòu)成（S0，S1，S2……，Sh），且滿足如下三個(gè)條件：每條鏈必須包含兩個(gè)特殊元素：+∞和-∞S0包含所有的元素，并且所有鏈中的元素按照升序排列。每條鏈中的元素集合必須包含于序數(shù)較小的鏈的元素集合，即：跳躍的構(gòu)造是所有鏈中的元素按照升序排列。但是，由于存在隨機(jī)產(chǎn)生的元素，并不能確保隨機(jī)數(shù)是