教學課件：《數(shù)據(jù)結(jié)構(gòu)與算法》辛運幃

第1章緒論1.1數(shù)據(jù)結(jié)構(gòu)簡介

1.2有關(guān)的預備知識1.1.1數(shù)據(jù)結(jié)構(gòu)的發(fā)展歷史20世紀40年代

只能直接對二進制數(shù)進行計算，這種數(shù)據(jù)根本談不上什么結(jié)構(gòu)，有結(jié)構(gòu)也是非常簡單的。20世紀50年代各種高級程序設計語言紛紛出現(xiàn)，所能描述的數(shù)據(jù)類型也逐漸增多。在FORTRAN、BASIC等語言中，都允許使用數(shù)組，其中最簡單的是一維數(shù)組，這已經(jīng)是一種典型的數(shù)據(jù)結(jié)構(gòu)了。20世紀60年代美國計算機界出現(xiàn)了信息結(jié)構(gòu)這一名稱，后來改用數(shù)據(jù)結(jié)構(gòu)。1968年，由美國計算機協(xié)會（ACM）頒發(fā)了建議性的計算機教學計劃，計劃中規(guī)定數(shù)據(jù)結(jié)構(gòu)作為獨立的一門課程。同年，世界著名的計算機科學家、美國的D.E.Knuth教授的巨著《計算機程序設計藝術(shù)》第一卷《基本算法》出版。20世紀60年代末到70年代初結(jié)構(gòu)程序設計成為程序設計方法學的主要內(nèi)容，人們對數(shù)據(jù)結(jié)構(gòu)越來越重視，著名的計算機科學家N.Wirth寫了《算法+數(shù)據(jù)結(jié)構(gòu)=程序》。

20世紀80年代以后抽象數(shù)據(jù)類型概念的引入，將數(shù)據(jù)類型和與之相結(jié)合的操作合為一體，而將操作的具體實現(xiàn)和它的定義分離開來，將數(shù)據(jù)結(jié)構(gòu)的理論和實踐提高到一個新的水平。1.1.2數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語

數(shù)據(jù)能輸入到計算機中并能被計算機處理的一切對象。這里必須強調(diào)指出，所謂數(shù)據(jù)絕不能僅僅理解為整數(shù)或?qū)崝?shù)這種狹義的“數(shù)”，必須作廣義的理解。例如，一個用某種程序設計語言編寫的源程序、一篇文稿、一張地圖、一幅照片、一首歌曲等等，都可以視為“數(shù)據(jù)”。今后隨著計算機的發(fā)展，還將不斷擴大數(shù)據(jù)的范圍。數(shù)據(jù)元素

數(shù)據(jù)的基本單位。由于數(shù)據(jù)的范圍非常廣泛，因此其基本單位也是可大可小的。大到可以是一個國家的地圖、一本書、一部電影，小到可以是一個字符，甚至是計算機中的一位。對于較大的單位，還可以由稱為“數(shù)據(jù)項”的較小單位組成。如圖書館中一本書的卡片就可以包含書名、作者名、出版社名、書號和出版日期等數(shù)據(jù)項。數(shù)據(jù)對象

具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。因為在實際應用中不會同時處理一切類型的數(shù)據(jù)，總是對特定的問題處理一種或幾種對象。例如用計算機求素數(shù)這個問題只涉及“整數(shù)”這種數(shù)據(jù)對象。數(shù)據(jù)結(jié)構(gòu)

彼此具有一定關(guān)系的數(shù)據(jù)元素的集合。事實上，這些關(guān)系反映了客觀世界事物之間的聯(lián)系。一般來說，數(shù)據(jù)有四類基本結(jié)構(gòu)：

集合

線性結(jié)構(gòu)

樹型結(jié)構(gòu)

圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)

四類基本結(jié)構(gòu)中數(shù)據(jù)元素之間的關(guān)系。集合線性結(jié)構(gòu) 樹形結(jié)構(gòu)圖結(jié)構(gòu)

圖1.1四類基本結(jié)構(gòu)示意圖

抽象數(shù)據(jù)類型（AbstractDataType，簡稱ADT）

抽象數(shù)據(jù)類型是指指一個數(shù)學模型和定義在該模型上的一組操作。

棧的抽象數(shù)據(jù)類型描述定義：元素類型為T的棧，由T的有限序列組成，對棧可以進行以下的操作：1)創(chuàng)建一個空棧；2)測試棧是否為空；3)壓棧操作，即當棧不滿時將一個新元素加入到棧頂部；4)出棧操作，即當棧不空時刪除棧頂元素；5)取棧頂元素，即當棧不空時輸出棧頂元素；1.2.1集合

集合是數(shù)學中最基本的概念之一，所以對它無法下一個嚴格的數(shù)學定義，正如幾何中無法定義點、直線一樣。因此，我們只能對集合作描述性的說明。集合：一群無重復的對象的全體；元素： 集合中的對象稱為集合的元素；常用的表示方法列舉法(窮舉法)

在描述元素個數(shù)較少的集合時，將集合中元素全部列出并括在一對花括號之內(nèi)的方法。

例如S={a,b,c,d}，表示集合S由a、b、c、d四個元素組成。集合描述法對于元素個數(shù)較多的集合或由無窮多個元素組成的集合，可以用集合描述模式{x|P(x)}來指定，其中x表示該集合中的任一元素，P(x)是一個謂詞，它對x進行限定。有關(guān)術(shù)語和記號屬于

如果x是集合S中的一個元素，則稱x屬于S，記作x∈S；否則，稱x不屬于S，記作xS。包含

對于兩個集合A、B，若集合A的元素都是集合B的元素，則稱集合A包含于集合B中（或稱集合B包含集合A），記作AB或BA，并且稱A是B的子集。兩個集合A和B相等，當且僅當AB且BA。

集合的并集合A和B的并是由A的所有元素和B的所有元素合并在一起組成的集合，記作A∪B，即A∪B={x|x∈A或x∈B}。集合的交集合A和B的交是由A和B的所有公共元素組成的集合，記作A∩B，即A∩B={x|x∈A且x∈B}。集合上的關(guān)系

集合A上的關(guān)系R是A中元素的某些有序?qū)ε嫉募?。如?x,y)R，可記為xRy。例如，A是一切整數(shù)組成的集合，R={(x,y)|x,y∈A且x<y}定義了A上的“小于”關(guān)系。此時，(2,5)∈R，

而(6,3)R。等價關(guān)系集合上的等價關(guān)系設R是集合A上的一個關(guān)系。我們說：（1）如果對A中任一元素a，都有aRa，則稱R是自反的關(guān)系。（2）如果對A中的任何元素a，b，從aRb能推出

bRa，則稱R是對稱的關(guān)系。（3）如果對A中的任何元素a，b，c，從aRb和bRc

能推出aRc，則稱R是傳遞的關(guān)系。若關(guān)系R同時是自反的、對稱的和傳遞的，則稱R為等價關(guān)系。等價類集合上的等價類等價關(guān)系的一個重要性質(zhì)是：集合A上的一個等價關(guān)系R可將A劃分為若干個互不相交的子集，它們稱為A上的等價類。對A中的每個元素a，我們約定用[a]表示a所在的等價類，即[a]={x|aRx}。例題

例1.1

考慮非負整數(shù)集N上的模3同余關(guān)系R，

R={(a,b)|a,b∈N,amod3=bmod3}。那么，集合{0，3，6，…，3n，…}形成一個等價類，用[0]表示。集合{1，4，7，…，3n+1，…}形成另一個等價類，用[1]表示。還有一個等價類是集合{2，5，8，…，3n+2，…}，用[2]表示。顯然N=[0]∪[1]∪[2]，即關(guān)系R將N劃分為3個等價類。1.2.2遞歸遞歸

一般來說，一個函數(shù)或表達式在定義時又用到它自身，就說這個定義是遞歸的。就算法來說，如果一個算法的實現(xiàn)步驟中又需要調(diào)用它自己，就稱這個算法是遞歸的。例題例1.2N的階乘N！整數(shù)N的階乘是N的函數(shù)F(N)，它的定義是：

F(0)=1(1.1)F(N)=N*(N-1)*(N-2)*…*1(N>0)(1.2)

如果將（1.2）式寫為遞歸的形式就是：

F(N)=N*F(N-1)（N>0）(1.3)

下面給出計算N!的C++函數(shù)，由于長整型變量字長的限制，N不能太大。longrfact(intn){ //計算n的階乘

assert((n>=0)&&(n<=12)); //assert是一個宏，

//當其后的邏輯表達式為真時，

//繼續(xù)執(zhí)行下一條語句，否則退出執(zhí)行

if(n<=1)return1; returnn*rfact(n-1); //遞歸調(diào)用

}

1.2.3數(shù)學證明方法反證法反證法也稱歸謬法，是數(shù)學中一種常用的證明方法。應用反證法證明一個問題時，一般采用如下的步驟： ①假定命題不成立； ②進行一系列的推理； ③在推理過程中出現(xiàn)了下列情況之一：

ⅰ與已知條件矛盾；

ⅱ與公理矛盾；

ⅲ與已證明過的定理矛盾；

ⅳ自相矛盾。④由于上述矛盾的出現(xiàn),可以斷言“假定命題不成立”是錯誤的；⑤肯定原來的命題是正確的。例題例1.3證明是無理數(shù)用反證法。設是有理數(shù)，則它可以寫為的形式，且p、q互素。

但是，若=，則2q2=p2

?，F(xiàn)在分析p、q的奇偶性，因為2q2為偶數(shù)，則p應為偶數(shù)，且q為奇數(shù)（因為p、q互素）。這時，等式左邊2q2只含有一個偶因子2（因為q2為奇數(shù)），而等式右邊p2至少含有兩個偶因子2（因為p為偶數(shù)），它們不可能相等，得出矛盾。即為無理數(shù)。數(shù)學歸納法數(shù)學歸納法也稱為完全歸納法，它是用“有限”步驟解決“無限”問題的一種嚴格證明方法。它的理論基礎是下述的數(shù)學歸納法原理。數(shù)學歸納法原理假定對一切非負整數(shù)n，有一個命題M(n)，如果我們能證明： ①M(0)為真； ②設對任意的k≥0，M(k)為真，能推出M(k+1)為真；則對一切n≥0，M(n)為真。證明:

我們可以用反證法證明這一原理。設對某個正整數(shù)N，M(N)非真，根據(jù)②，M(N-1)也非真。連續(xù)用②N次之后，得出M(0)非真，與①矛盾。歸納法原理得證。當我們證過這一歸納法原理以后，在以后證明某個關(guān)于非負整數(shù)n的命題P(n)時，只需證明①、②兩點即可。第①點稱為歸納基礎，第②點稱為歸納步驟。在②中“設對任意的k≥0，M(k)為真”這一句話，稱為歸納法假設。例題例1.4求證下述命題S(n)：“從1開始連續(xù)n個奇數(shù)的和是n的平方”。即公式1+3+5+…+2n-1=n2證明用數(shù)學歸納法。(1)歸納基礎n=1。12=1，顯然。(2)歸納步驟設對任意的m≥1，S(m)為真，要證S(m+1)為真。根據(jù)歸納法假設1+3+5+…+2m-1=m2而1+3+5+…+2m-1+2(m+1)–1=m2+2(m+1)–1=m2+2m+1=(m+1)2

。從而證明了S(n)成立。22222第2章算法的基本概念與算法分析

2.1算法的基本概念

2.2算法的評估2.3算法的復雜性度量2.1.1一個簡單的算法問題 把攝氏溫度值轉(zhuǎn)換為華氏溫度值。 已知計算公式為：F=(9/5)C+32，其計算過程可描述如下：輸入一個攝氏溫度值C；C乘以常數(shù)9/5=1.8；乘積與常數(shù)32相加；輸出相加的結(jié)果F。 這就是求解該問題的算法，不過，計算機“看”不懂這個算法，需要用程序設計語言描述： #include＜iostream.h＞

voidmain（）

{

floatC,F；

constfloatfac=1.8，inc=32.0；

cout<<"EnterCelsiustemperature："；

cin>>C； ∥輸入攝氏溫度值

F=C；

F=C

fac；

F=F+inc;

cout<<endl<<"TheFahrenheittemperatureis："；

cout<<F<<"F(=“<<C<<"C)＼n"；

｝

例如輸入40.2，計算結(jié)果將在屏幕上顯示：

EnterCelsiustemperature：40.2

TheFahrenheittemperatureis：104.36F(=40.2C)2.1.2什么是算法算法1.Webster辭典定義：算法即在有限步驟內(nèi)解一個數(shù)學問題的過程，步驟中常常包括某一操作的重復。更廣義地說，一個算法就是為解一個問題或?qū)崿F(xiàn)某一目標的逐步過程。2.D.E.Knuth定義：一個算法，就是一個有窮規(guī)則的集合，其中之規(guī)則規(guī)定了一個解決某一特定類型的問題的運算序列；此外，它還應有五個重要特性：有窮性：一個算法必須總是在執(zhí)行有窮步之后結(jié)束；確定性：算法的每一步驟，必須是確切地定義的；輸入：有0或多個輸入值；輸出：有1或多個輸出值；能行性：算法中要做的運算都是相當基本的，能夠精確地進行的。3.形式化定義：算法就是一個對任一有效輸入能夠停機的Turing機。2.1.3算法與問題如同生物學家把自然界的所有生物作為自己的研究對象，計算（Computation）學科或稱計算機科學則把問題作為自己的研究對象。用計算機來解決問題（Problemsolving）稱為問題求解。算法要解決的是一類問題，算法的執(zhí)行則針對的是問題的實例。每一個問題都可以看作是該問題的所有實例（instance）的集合。一個問題的一個實例就是為計算該問題所需的一組輸入。例：整數(shù)乘法問題 全部可能輸入集合：{<a,b>|a,b∈Z}，其中Z表示整數(shù)集；一個實例：<2,4>,求：2×4=?旅行商問題(TravelingSalesmanProblem)

實例集為：{n,Wn*n=[Wij]|n∈Z,Wij∈R,i,j∈[1,…,n]}； 一個實例：n=4,該實例（n,W）就是求環(huán)游4個城市(1,2,3,4)且代價和最小的周游路線，其中權(quán)矩陣W給出了4個城市之間的距離（代價），Wij表示由城市i到城市j的距離（代價）。語言L<G,Σ>的識別問題 其中G為文法，Σ為一字符集。L(G)為Σ上由G生成的語言，L(G)∈Σ*，Σ*表示由Σ中的字符組成的所有字符串集合。 語言L的識別問題{G,Σ,ω|ω∈Σ*}的一個實例ω∈Σ*，識別算法判斷ω∈L(G)是否成立。 一般對于問題P，總有其相應的實例集I，那么，一個算法A是問題P的算法，意味著把P的任一實例input∈I作為A的輸入，都能得到問題P的正確的輸出。一個問題可以有許多個不同的算法。2.1.4算法與程序程序(Program)可以用來描述算法，同一個算法可以用不同的語言編寫的程序來描述。程序不一定是算法。程序設計可以分為四個層次：算法、方法學、語言和工具。抽象級更新速度算法程序設計方法程序設計語言編程工具2.2.1算法的正確性算法的正確性是評估的前提。有些算法，特別是一些十分精致巧妙的算法，其正確性需要證明，有的證明難度較大，例如無向圖單源最短路徑問題的Dijkstra算法，構(gòu)造最優(yōu)二分搜索樹的動態(tài)規(guī)劃算法的Knuth改進。有些算法，其正確性是明顯的， 例如選擇排序算法。2.2.2時間代價評估算法的時間代價是算法分析的核心。算法的時間代價的大小用算法的時間復雜度(TimeComplexity)來度量。但要考慮到以下因素： 用來運行算法的計算機的性能的差別；算法運行的軟件平臺和描述語言的差別；算法所解的問題是多種多樣的；同一問題的算法對不同的實例，所花的時間開銷也可能有很大的差別。2.2.3空間代價空間消耗是衡量算法優(yōu)劣的另一重要因素。算法的空間代價的大小用算法的空間復雜度（SpaceComplexity）來度量。不過算法的空間復雜性分析的重要性常常列于時間復雜性分析之后。在許多應用問題中，人們往往以適當增加算法的空間代價來減少時間代價?？臻g復雜度的分析類似于時間復雜度的分析，其有關(guān)的概念和方法幾乎是平行的。2.2.4最優(yōu)性一個算法不一定是最優(yōu)的。所謂最優(yōu)算法是指在某一種度量標準之下，優(yōu)于該問題的所有（可能的）算法。一般，某一問題的最優(yōu)算法是指在時間復雜度的計算基礎上的最優(yōu)性。

例：求n個不同整數(shù)中的最大元MaxElement

對于任何n個整數(shù)，要求其最大元，至少需進行n-1次比較，因此，可以說上述算法Max(S)是最優(yōu)的。為了證明在n個不同元中求出最大元，至少需n-1次比較，可以把n個元劃分為三個動態(tài)的組A,B,C：A：未知元的集合B：已肯定不是最大元的元素集合C：最大元的集合。

不難證明，任何一個通過二元比較求最大元的算法都是要從三個集合的元數(shù)為(n,0,0)（即|A|=n,|B|=0,|C|=0）狀態(tài)開始，經(jīng)過運行，最終達到(0,n-1,1)狀態(tài)，即：這實際上是元素從集合A向B和C中移動的過程。但每次兩個元的比較至多只可把一個較小的元素從集合A移至集合B。因此，任何最大元算法至少要進行n-1次比較，從而證明了上述最大元算法Max(A)是最優(yōu)的。2.3.1算法復雜性度量的基本操作算法的時間代價的度量不應依賴于算法運行的硬件和軟件平臺，因此不能從下面幾個方面來度量時間代價：

算法運行的實際執(zhí)行時間；運行過程中所執(zhí)行的指令條數(shù)；運行過程中程序循環(huán)的次數(shù)。 因此需要引入基本操作的概念來度量時間代價。 基本操作就是指算法運行中起主要作用且花費最多時間的操作。例如：兩個實數(shù)矩陣的乘法問題中，矩陣的實數(shù)元素之間的數(shù)乘是基本操作；對N個整數(shù)進行排序的算法中，整數(shù)間的比較是基本操作。問題實例長度算法運行的時間（或空間）代價還與問題實例長度，即輸入規(guī)模有關(guān)，這稱為問題實例長度。

問題實例長度是指作為該問題的一個實例的輸入規(guī)模大小。例如：

排序問題：問題實例長度是待排序元素序列的長度n；

矩陣乘積：問題實例長度是矩陣（指n階方陣）的階數(shù)n；

圖的最短路徑問題：圖G=<V,E>的頂點數(shù)n=||V||和邊數(shù)m=||E||是問題實例長度；

字符串匹配問題：文本T的長度n，亦可再加上樣本P的長度m為問題實例長度。2.3.2問題實例長度算法的時間（或空間）代價由該算法用于問題長度為n的實例所需要的基本操作次數(shù)來刻畫。一般一個算法的時間復雜度用函數(shù)T(n)

或T(n,m)

表示，空間復雜度用S(n)表示。算法的比較是根據(jù)復雜度函數(shù)的漸進性質(zhì)的比較進行的。 例如：算法A和算法B，其時間復雜度函數(shù)為TA(n)和TB(n)，在圖2.1中，雖然當n<n0時TB(n)<TA(n)，但在n>n0時，或說n充分大時(n→∞)，有TA(n)<TB(n)，因此認為算法A優(yōu)于算法B。2.3.3復雜度函數(shù)及其漸進性質(zhì)圖2.1算法的漸進性質(zhì)

例：插入排序算法Insertsort

n=10時，有三種輸入： 正序：123456789109次比較 逆序：1098765432145次比較 隨機：3745102961828次比較 同一算法，相同的問題長度，不同的輸入，其時間代價一般不同。因此在實際的算法分析中，復雜度函數(shù)值T(n)不是唯一的，在大多數(shù)情況下取其最大值，即最壞情形的時間（空間）復雜度。2.3.4最壞情形和最好情形

設Dn為問題P的所有長度為n的實例集合，輸入實例I∈Dn，||I||=n，而t(I)為用來解問題P的算法A在以I為輸入時的執(zhí)行代價（基本操作次數(shù)），則

W(n)稱為算法A的最壞情形(WorstCase)時間復雜度。類似的，還可以定義最好情形（BestCase）時間復雜度：

2.3.5平均情形和算法的期望復雜度在許多實際問題中，使算法A耗費最大代價W(n)的實例往往只占很小的一部分，而大多數(shù)實例耗費的代價常常遠小于W(n)，用W(n)來表示算法的代價一般比實際的開銷大很多。因此，評價算法性能的更好的方法是用期望復雜度(ExpectedComplexity)，或稱平均情形

(AverageCase)復雜度。

設算法A的輸入為I∈Dn的概率為P(I)，則

其中P(I)滿足為實例輸入I出現(xiàn)的概率，t(I)為算法A完成實例I的耗費值（即基本操作次數(shù)）。期望復雜度比最壞情形復雜度更好的刻畫了算法的性能，但是，由于Dn一般很大，P(I)和t(I)較難計算，因此，平均情形的復雜度分析比較難。例如：在數(shù)組L[1,…,n]中搜索，求使L[j]=X的位置j。

順序搜索算法SeqSearch

因為L[1,…,n]長度為n，不同的輸入實例由X的值決定，實例集Dn由下列實例組成： （1）X在L中，共有n種情況：I1,…,In，Ii表示X=L[i] (i=1,…,n)； （2）X不在L中，這時X有許多可能值，把它們統(tǒng)記為 In+1。因為當X=L[k]時，t(Ik)=k，(k=1,…,n)，X不在L中時，t(In+1)=n。這時W(n)容易計算：

W(n)=MAX{t(Ik)|k=1,2,…,n,n+1}=n。

但計算A(n)則應首先設定I在Dn中的分布： 設X在L中的概率為q，故X不在L中的概率為1-q，假定X在L中，它等于L的n個元素是等可能的，即P(Ik)=Pk=q/n,(k=1,…,n),P(In+1)=Pn+1=1-q，

當q=1，即已知X在L中，A(n)=(n+1)/2，q=1/2，即X有一半可能在L中，A(n)=3n/4+1/4。也就是說，在上面的假設條件下，我們的順序搜索的平均代價大約是n/2次比較和3n/4次比較。

各種復雜度函數(shù)的表示方法大致可按表達的精確程度分為下面的三個等級：解析表達式 用解析表達式刻畫復雜度函數(shù)是最精確的表達方式。例如求n元中之最大元算法MaxElement的復雜度為T(n)=W(n)=A(n)=n–1。 順序搜索算法的最壞情形時間復雜度為W(n)=n；在指定分布條件及q=1情形下的期望時間復雜度為A(n)=(n+1)/2。2.3.6復雜度函數(shù)的表示階（Order）表達式 對于算法的復雜度的研究主要是側(cè)重在其漸進性質(zhì)，即當問題長度n比較大的情形。為了簡化算法復雜度分析的方法，往往只需計算當問題規(guī)模較大時算法的漸進復雜度的階。定義1.1

稱（復雜度）函數(shù)T(n)是O(f(n))的，即T(n)=O(f(n))，如果存在常數(shù)c>0與n0

，當n>n0

時有T(n)≤cf(n)。例如：T1(n)=(n+1)/2=O(n), T2(n)=3n2+4n+5=O(n2)定義1.2

稱（復雜度）函數(shù)T(n)是Ω(f(n))的，即T(n)=Ω(f(n))，如果存在常數(shù)c>0與n0

，當n>n0時有T(n)≥cf(n)。

例如：T1(n)=(n+1)/2=Ω(n),

T2(n)=3n2+4n+5=Ω(n2)定義1.3

稱（復雜度）函數(shù)T(n)是θ(f(n))的，即T(n)=θ(f(n))，如果存在常數(shù)c1,c2>0與n0

，當n>n0

時有c1f(n)≥T(n)≥c2f(n)。 例如：T1(n)=(n+1)/2=θ(n),

T2(n)=3n2+4n+5=θ(n2)

顯然，如果T(n)=O(f(n))且T(n)=Ω(f(n))，則T(n)=θ(f(n))。2.4算法設計與分析的重要性摩爾(Moore)定律：計算機處理器的運算速度每十八個月要翻一番。但是，電子計算機的運算速度肯定是有上限的，它不可能一直“翻”下去，即使計算機的速度不斷提高，算法研究仍然是必要的。無論硬件性能如何提高，算法研究仍然是推動計算機技術(shù)發(fā)展的關(guān)鍵。

2.4.1一個實例

插入排序算法和歸并排序算法中，后者較優(yōu)。 對n(=1000000)個數(shù)據(jù)進行排序。 在一臺高速的計算機A（每秒鐘處理109條指令）上，采用插入排序算法。 在一臺較慢的計算機B（每秒鐘處理107條指令）上，采用歸并排序算法。 在計算機A上運行插入排序算法，對n項數(shù)據(jù)排序，需要執(zhí)行2n2條指令，共需時間為：(2*(106)2)/109＝2000(sec)

在計算機B上運行歸并排序算法，對n項數(shù)據(jù)排序，需要執(zhí)行50nlogn條指令，共需時間為：(50*106*log106)≈100(sec)2.4.2計算機應用領域的變化在了解計算機性能不斷提高的同時，必須看到，人類使用計算機解決的應用問題也在不斷變化：應用的范圍不斷擴張；應用問題的規(guī)模不斷增加；應用問題本身也越來越復雜。

計算機技術(shù)的進步離不開算法研究，如多媒體技術(shù)中的數(shù)據(jù)壓縮算法的研究，計算機安全中數(shù)據(jù)加密算法的研究。許多組合優(yōu)化，也只能靠算法的研究來解決，例如：旅行商(TravelSalesman)難解問題 假定計算機每秒可處理1000000次浮點運算，采用一般TSP算法解n=10（十個城市）的情形約需0.18秒；但當城市數(shù)n=20，同一機器上運行需要1929年！試想，這時改用速度提高100倍的計算機，可以縮短為19年，這仍然是不可接受的。2.4.3 計算機技術(shù)的發(fā)展需要設計有效算法

0-1背包(0-1Knapsack)問題

n=10需1ms，n=60需要366世紀！這時計算機提高速度10000倍，仍要3.66年。

算法與計算復雜性理論的研究表明，當問題的復雜度較高時單純靠提高計算機性能是不能解決問題的。 設五種復雜度函數(shù)分別為n，n2，n5，2n，3n，采用速度為每秒鐘處理1000000次基本操作的PC機，其處理問題長度分別為n=10，30，60的實例的時間代價如下表：

表2.1時間代價需求表表2.2機器速度提高對解題能力的影響2.5.1MAXMIN問題的平凡算法

步驟：①

:求n元中的最小元；②

:求余下的n–1個元中的最大元。

例：求最大最小元的平凡算法MAXMIN1

算法是正確的以元素之間的比較為基本操作，則①的代價為n–1，②的代價為n–2，故總時間代價為2n–3。故T(n)=W(n)=A(n)=2n–3，亦可記為T(n)=O(n)或T(n)=θ(n)。空間代價除了數(shù)組L之外，只需幾個工作單元，一般記為S(n)=O(1)。算法的最優(yōu)性討論：從n元中求最小元用n-1次比較，從n–1元中求最大元用n–2次比較都是最優(yōu)的。但把二者合起來用2n–3次比較求最大、最小元并不一定最優(yōu)。求MIN與MAX時它們是相關(guān)的，例如L[i]>L[j]指出L[i]不可能是最小元，L[j]不可能是最大元，因此算法MAXMIN1應可改進。2.5.2第一次改進把求MAX和MIN放在一起處理：

例：求最大最小元的改進算法MAXMIN2

此算法需2n–2次比較，即T(n)=W(n)=A(n)=

2n–2。沒有改進，但可發(fā)現(xiàn)循環(huán)體中的不合理處：如果(MAX<L[i])為真，則(MIN>L[i])為假，故有改進算法II。2.5.3第二個改進算法例：求最大最小元的改進算法MAXMIN3

最好情形B(n)=n–1，最壞情形W(n)=2n–2，平均情形時間復雜度A(n)應介于二者之間，估計A(n)<2n–3。2.5.4采用淘汰賽策略的改進算法“淘汰賽算法”

MAXMIN：step1.對n個元兩兩比較，共用

n/2

次比較；step2.對“勝者組”（即step1比較中的較大元，及當n為奇數(shù)時未參加比較的元）共

n/2

個元素求最大元，共用

n/2

-1次比較；step3.對“敗者組”（即step1比較中的較小元，及n為奇數(shù)時未參加比較的元）共

n/2

個元素求最小元，共用

n/2

-1次比較； 在step1、step2分別求出的最大元、最小元即所求。不難證明，無論n為奇偶，都有：算法MAXMIN是假定n=2k條件下設計的，對于一般的正整數(shù)n時間復雜度應為T(n)=W(n)=A(n)=3n/2

-2。算法MAXMIN的設計包含一定的設計技巧，有時采用設計有效算法的一些常用設計技術(shù)（將在第九章介紹）也可以收到改進算法復雜度的效果。例如，我們可以采用分治策略，按照分治策略，把L[1,…,n]劃分為兩部分L1、L2，用同一算法對L1、L2分別求最大最小元，兩個最大元中較大者和兩個最小元中較小者即所求。MAXMIN問題的分治算法同樣可以把算法復雜度降至大約1.5n。2.5.5算法MAXMIN的討論算法MAXMIN的時間復雜度是不可改進的，因此它是一個最優(yōu)算法。MAXMIN問題的分治算法是一個遞歸算法。在遞歸算法進行復雜度分析時，一般要遇到解遞歸方程或遞歸不等式。 這里僅對一類最常見的遞歸方程進行討論： 其中：整數(shù)a≥1，b>1，c≥0，T(n)，d(n)為非負（整）函數(shù)。利用下面的結(jié)果，可以對不同情形分別判斷函數(shù)T(n)的階。主項定理1

對于上面的遞歸方程（2.1），有(a)如果，若a>1則 ；若a=1則；(b)如果，若a<b則；若a=b則；若a>b則；利用主項定理1對算法MAXMIN進行分析，T(n)=2T(n/2)+2可以立即得到：

這與T(n)=

3n/2

-2一致。下面的主項定理2一般被稱為主項定理（Mastertheorem），與主項定理1的依據(jù)實際是相同的，不過，其結(jié)果比主項定理1更強。主項定理2（Mastertheorem）對于遞歸方程(2.1)，有(1)如果對某常數(shù)ε>0成立，

則；(2)如果，則；(3)如果對某常數(shù)ε>0成立，且存在常數(shù)e<1使得對所有充分大的n，有，則。 END求n個不同整數(shù)中的最大元MaxElementtemplate<classType>intMax(TypeS[],intn){

Typemax=S[0];

inti=1;

while(i<n){

if(max<S[i])max=S[i];i++;}returnmax;}返回選擇排序算法template<classType>

voidSelectionSort(TypeA[],intn){

for(inti=1;i<=n-1;i++){

intmin=i;

for(intj=i+1;j<=n;j++)

if(A[j]<A[min])min=j;

Swap(A[i],A[min]);

}

return;

}返回插入排序算法InsertSort

template<classType>voidInsertSort(TypeA[],intn){for(inti=2;i<=n;i++){TypeV=A[i];

intj=i-1;

while((A[j]>V)&&(j>0)){A[j+1]=A[j];j=j–1;}A[j+1]=V;

return;}返回順序搜索算法SeqSearch

template<classType>intSearch(TypeL[],TypeX,intn){

intj=1;while((j<=n)&&(L[j]!=X))j++;

returnj;}返回求最大最小元的平凡算法MAXMIN1template<classType>#include<iostream.h>voidMAXMIN1(TypeL[],intn){TypeMAX=L[1];for(inti=2;i<=n;i++)

if(MAX<L[i]){MAX=L[i];

intj=i;}Swap(L[i],L[n]);//把最大元換到最后

TypeMIN=L[1];

for(i=2;i<n;i++)if(MIN>L[i])MIN=L[i]; cout<<“MAX=“<<MAX<<”,MIN=“<<MIN<<

endl;return;}返回求最大最小元的改進算法MAXMIN2template<classType>#include<iostream.h>voidMAXMIN2(TypeL[],intn){TypeMAX=L[1];TypeMIN=L[1];

for(inti=2;i<=n;i++){

if(MAX<L[i])MAX=L[i];

if(MIN>L[i])MIN=L[i];}

cout<<"MAX="<<MAX<<",MIN="

<<MIN<<endl;

return;}返回求最大最小元的改進算法MAXMIN3template<classType>#include<iostream.h>voidMAXMIN3(TypeL[],intn){TypeMAX=L[1];TypeMIN=L[1];

for(inti=2;i<=n;i++){

if(MAX<L[i])MAX=L[i];

elseif(MIN>L[i])MIN=L[i];}cout<<"MAX="<<MAX<<",MIN="<<MIN<<endl;

return;}返回第三章線性表3.1線性表的定義和基本運算3.2線性表的實現(xiàn)3.3線性表的應用3.1線性表的定義和基本運算為了引入線性表的概念，我們先舉幾個例子。例3.1（2，6，8，3，9，4）是一個線性表，其中的數(shù)據(jù)元素是整數(shù)，按表中列出的順序排列，表中共有6個數(shù)據(jù)元素。例3.2（A，B，C，D，E，…，X，Y，Z）是一個線性表，其中的數(shù)據(jù)元素是英文大寫字母，按字母表的順序排列，共有26個數(shù)據(jù)元素。示例例3.3圖3.1所表示的學生入學成績表也是一個線性表。其中的數(shù)據(jù)元素是每個學生在表中所占的一行，包括姓名、準考證號、性別、年齡和總分等共5個數(shù)據(jù)項。通常把這種數(shù)據(jù)元素稱為紀錄。表中所列出的學生人數(shù)就是表中數(shù)據(jù)元素的個數(shù)。姓名 準考證號 性別 年齡 總分陳義平030010023男 18 589陸東 030010025男 19 568王曉敏030010037女 18574┇ ┇ ┇ ┇ ┇李志強030010123男 19 617

圖3.1學生入學成績表線性表的定義線性表

一個線性表（list）是由同類型數(shù)據(jù)元素構(gòu)成的有限序列，記作 （a0,a1,…,an-1）。這個定義中強調(diào)兩個特性，一個是強調(diào)每個數(shù)據(jù)元素ai（i=0，…，n-1）必須是同類型的數(shù)據(jù)，不能將不同類型的數(shù)據(jù)并列在一個線性表內(nèi)。另一個是強調(diào)表中數(shù)據(jù)元素的有序性，也就是說每個元素在表中都有自己的位置術(shù)語當線性表中不包含任何元素時，稱之為空表，記作（）。表中具有元素的個數(shù)稱為線性表的長度。線性表的第一個元素稱為表頭，最后一個元素稱為表尾。對于表中第i個元素ai來說，第i-1個元素ai-1稱為它的直接前趨（簡稱前趨），第i+1個元素ai+1稱為它的直接后繼（簡稱后繼）。當然，表頭沒有直接前趨，表尾沒有直接后繼。

下面就根據(jù)線性表的一組操作來定義該對象的抽象數(shù)據(jù)類型（ADT）。我們借助于C++的類（class）來描述線性表的抽象數(shù)據(jù)類型。這里ELEM類型表示線性表中數(shù)據(jù)元素所具有的任何數(shù)據(jù)類型。用戶在實際應用中，可以用具體的數(shù)據(jù)類型來代替，如整型int，或用戶自定義的復雜結(jié)構(gòu)等。線性表類的ADTclasslist{ //線性表類的ADTpublic: list(constintsz=LIST_SIZE); //構(gòu)造函數(shù)

~list()； //析構(gòu)函數(shù)

voidclear(); //從表中清除所有元素

voidinsert(constELEM&); //在當前位置插入一個元素

ELEMremove()； //刪除并返回當前元素的值

voidsetFirst(); //置光標于第一個位置

voidprev(); //移動光標到前一位置

voidnext(); //移動光標到下一位置

intlength()const; //返回表的當前長度

voidsetPos(constint); //置光標于指定位置

voidsetValue(constELEM&); //置當前元素的值

ELEMcurrValue()const; //返回當前元素的值

boolisEmpty()const; //如果表為空則返回TRUE boolisInList()const; //如果光標在表內(nèi)則返回TRUE boolfind(constELEM&); //從當前位置開始找到某個值第一次出現(xiàn)的地方};3.2線性表的實現(xiàn)

上一節(jié)提出的線性表的基本操作還是抽象的，如何具體實現(xiàn)這些操作首先依賴于線性表的存儲結(jié)構(gòu)。常用的存儲結(jié)構(gòu)有兩種，分別是順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。3.2.1順序存儲結(jié)構(gòu)基本思想用一組連續(xù)的存儲單元依次存放線性表中各個元素。在C++表示中，只要用一個一維數(shù)組就可以了。但是，由于線性表的長度可以改變，只用固定長度的數(shù)組是不足以表示線性表的實際情況的。因此，線性表的當前長度也必須要用一個整數(shù)來記錄。

順序表把表中的元素存儲在數(shù)組中相鄰的位置，數(shù)組下標與線性表元素的位置相對應。換句話說，就是表中第i個元素存在數(shù)組的第i個位置。表頭總是在第0個位置，這就使得對表中任意一個元素的隨機訪問非常容易。只要給出表中元素的序號，它在數(shù)組中對應的位置很容易確定，該元素的值就可以直接獲取。因此用setPos()函數(shù)訪問表中任一元素只需O(1)時間。

既然順序表把表中的元素存儲在數(shù)組的相鄰單元中，insert()和remove()函數(shù)就必須支持這個約定。在表尾插入和刪除元素是比較容易的，只需花費O(1)的時間。但是，如果我們想在表頭插入一個元素，那么當前表中所有元素都必須向表尾方向移動一個位置以騰出空間（插入過程如圖3.2所示）。平均說來，插入和刪除要移動表中一半元素，即需要O(n)時間。示例插入27

圖3.2在順序表的表頭插入一個元素需要表中所有元素向表尾方向移動一個位置示意圖115231960123456789115231960123456789(a)(b)27115231960123456789(c)順序存儲實現(xiàn)線性表類私有部分中包括了類的數(shù)據(jù)成員：存儲線性表元素的數(shù)組listarray；表的最大長度msize；當前實際長度numinlist；當前元素在數(shù)組中的位置curr。意味著它們不能在類的成員以外的函數(shù)中直接使用。classlist{ //基于數(shù)組的線性表類private: intmsize; //表的最大長度

intnuminlist; //表中元素的實際個數(shù)

intcurr; //表中當前元素的位置

ELEM*listarray; //存儲表元素的數(shù)組public: list(constintsz=LIST_SIZE); //構(gòu)造函數(shù)

~list(); //析構(gòu)函數(shù)

voidclear(); //從表中清除所有元素

voidinsert(constELEM&); //在當前位置插入一個元素

ELEMremove()； //刪除并返回當前元素的值

voidsetFirst(); //置光標于第一個位置

voidprev(); //移動光標到前一位置

voidnext(); //移動光標到下一位置

intlength()const; //返回表的當前長度

voidsetPos(constint); //置光標于指定位置

voidsetValue(constELEM&); //設置當前元素的值

ELEMcurrValue()const; //返回當前元素的值

boolisEmpty()const; //如果表為空則返回TRUE boolisInList()const; //如果光標在表內(nèi)則返回TRUE boolfind(constELEM&); //從當前位置開始尋找元素的值};list::list(constintsz) //構(gòu)造函數(shù)：初始化

{msize=sz;numinlist=curr=0;listarray=newELEM[sz];}list::~list() //析構(gòu)函數(shù)：釋放數(shù)組所占空間

{delete[]listarray;}voidlist::clear() //從表中清除所有元素

{numinlist=curr=0;}

在表中當前位置插入新元素時，需要先判斷表中數(shù)據(jù)不滿，且插入的位置正確。//在當前位置插入元素itemvoidlist::insert(countELEM&item){ //數(shù)組必須未滿并且curr必須是一個合理位置

assert((numinlist<msize)&&(curr>=0)&&(curr<=numinlist)); for(inti=numinlist;i>curr;i--) listarray[i]=listarray[i-1]; listarray[curr]=item; numinlist++;}

刪除元素時與插入情況類似，也需要先判斷表不是空表如果要對被刪除的數(shù)據(jù)進行相關(guān)操作，需要返回該數(shù)據(jù)。//刪除并返回當前元素ELEMlist::remove(){ assert(!isEmpty()&&isInList()) //要刪除的元素必須在表中

ELEMtemp=listarray[curr]; //保存被刪除的元素

for(inti=curr;i<numinlist-1;i++) //被刪元素后面的全部元素前移一個位置

listarray[i]=listarray[i+1]; numinlist--; //表的當前長度減1 returntemp;}voidlist::setFirst() //置光標于第一個位置

{curr=0;}voidlist::prev() //移動光標到前一個位置

{curr--；}voidlist::next() //移動光標到下一個位置

{curr++;}intlist::length()const //返回表的當前長度

{returnnuminlist;}voidlist::setPos(constintpos) //置光標于指定位置

{curr=pos;}voidlist::setValue(constELEM&val){ //為當前元素ELEM賦值

assert(isInList()); listarray[curr]=val;}ELEMlist::currValue()const{ //返回當前元素的值

assert(isInList()) returnlistarray[curr];}boollist::isEmpty()const //如果表為空則返回TRUE {returnnuminlist==0;}boollist::isInList（）const //如果當前位置在表中則返回TRUE {return（curr>=0）&&(curr<numinlist);}boollist::find(constELEM&val){ //查找表中元素（從當前位置開始直到表尾）

while(isInList()) if(currValue()==val)returnTRUE; //如果找到則返回TRUE elsenext(); returnFALSE; //如果找不到則返回FALSE}3.2.2鏈式存儲結(jié)構(gòu)鏈表鏈表是由一系列叫做結(jié)點（node）的對象連接起來的數(shù)據(jù)結(jié)構(gòu)。一般來說，結(jié)點之間用指針來連接。定義link類：存儲元素值的element域；存儲結(jié)點指針的next域；Link類的定義classlink{ //一個單鏈表結(jié)點public: ELEMelement; //該結(jié)點的數(shù)據(jù)元素的值

link*next; //鏈表中指向下一個結(jié)點的指針

link(constELEM&elemval,link*nextval=NULL) //構(gòu)造函數(shù)1 {element=elemval;next=nextval;} //給出數(shù)據(jù)元素ELEM的值

link(link*nextval=NULL){next=nextval;} //構(gòu)造函數(shù)2 ~link(){} //析構(gòu)函數(shù)};classlist{ //單鏈表類private: link*head; //指向鏈表頭的指針

link*tail; //指向鏈表尾的指針

link*curr; //指向當前元素的指針public: list(constintsz=LIST_SIZE); //構(gòu)造函數(shù)

~list(); //析構(gòu)函數(shù)

voidclear(); //從表中清除所有元素

voidinsert(constELEM&); //在當前位置插入一個新元素

ELEMremove(); //刪除并返回當前元素

voidsetFirst(); //置光標于第一個位置

voidnext(); //移動光標到下一位置

voidprev(); //移動光標到前一位置

intlength()const; //返回表的當前長度

voidsetPos(constint); //置光標于指定位置

voidsetValue(constELEM&); //給當前位置的元素賦值

ELEMcurrValue()const; //返回當前元素的值

boolisEmpty()const; //如果表為空則返回TRUE boolisInList()const; //如果光標在表內(nèi)則返回TRUE boolfind(constELEM&); //從當前位置開始尋找等于某個值的元素};示例curr指向的位置

head curr192512191116122511(a)headcurr(b)圖3.3

鏈表實現(xiàn)示例

(a)插入16之前(b)插入16之后的應有結(jié)果插入一個新元素的步驟首先，要創(chuàng)建一個新的結(jié)點，并且賦給它一個值；其次，新結(jié)點的next值要指向當前結(jié)點；第三，當前結(jié)點的前趨結(jié)點的next指針要指向新插入的結(jié)點；但是，在單鏈表的情況下，從當前結(jié)點找它的前趨結(jié)點并不那么容易。查找前趨結(jié)點方案一從表頭開始，直到找到當前結(jié)點的前趨結(jié)點為止，這樣做平均要花費O(n)的時間（n為表的當前長度）。方案二用新元素的值替代當前結(jié)點元素的值，而在當前結(jié)點之后插入一個新結(jié)點，并把原來結(jié)點的值賦給這個新結(jié)點。可惜的是，對于刪除操作，仍然需要知道當前結(jié)點的前趨結(jié)點。查找前趨結(jié)點方案三讓curr指向當前結(jié)點的前趨結(jié)點。例如在圖3.3(a)中，值為12的結(jié)點是當前結(jié)點，則讓curr指向它的前一個結(jié)點（值為25的結(jié)點）。這樣做就使得插入和刪除都相當容易。這種新的“當前”結(jié)點的定義方式又帶來新的問題，如果表中只有一個元素，那么curr所要指向的前趨結(jié)點就不存在了。因此表中只有一個結(jié)點或沒有結(jié)點的時候就屬于難于處理的特殊情況。

鑒于上述的問題，解決的辦法是在鏈表中增加一個表頭結(jié)點。這個結(jié)點是鏈表的第一個結(jié)點，它和表中其他結(jié)點的結(jié)構(gòu)一樣，只是不存放任何數(shù)據(jù)元素。headcurr^圖3.4使用表頭結(jié)點后空表的表示方法192512191116122511(a)curr(b)headcurrhead圖3.5使用帶有頭結(jié)點和轉(zhuǎn)義的curr指針的插入圖示(a)插入數(shù)值16之前的鏈表(b)插入數(shù)值16之后的應有結(jié)果插入和刪除操作的實現(xiàn)一行C++語句就可以了：

curr->next=newlink(item,curr->next);它實際上做了所有的三個步驟。運算符new創(chuàng)建了一個新的鏈表結(jié)點，表中結(jié)點的構(gòu)造函數(shù)有兩個參數(shù)，第一個是元素的值item，第二個是要放在結(jié)點上的next值。插入只需要O(1)的時間2512curr…………插入16：162512…………16curr(a)(b)圖3.6在鏈表中插入一個結(jié)點的過程(a)插入前的鏈表(b)插入后的鏈表從鏈表中刪除一個結(jié)點

從鏈表中刪除一個結(jié)點只需要先用一個指針指向被刪結(jié)點，然后將curr所指結(jié)點的next直接指向被刪結(jié)點的后繼結(jié)點即可。remove()函數(shù)是用下面的兩行語句來實現(xiàn)的：link*itemp=curr->next; //先記住被刪結(jié)點的位置curr->next=itemp->next; //從鏈表中刪除要刪的結(jié)點刪除過程也只需要O(1)的時間。2512…………16(a)curr2512…………16(b)curr圖3.7

從鏈表中刪除一個結(jié)點的過程(a)刪除（結(jié)點16）前的鏈表(b)刪除后的鏈表采用鏈表存儲方式的實現(xiàn)list::list(constintsz) //構(gòu)造函數(shù)

{head=curr=newlink;}list::~list(){ //析構(gòu)函數(shù)

while(head!=NULL){ //釋放鏈表的所有節(jié)點占用的空間

curr=head; head=head->next; deletecurr; }}清空表voidlist::clear(){ //從表中刪除所有元素

while(head->next!=NULL){//返回鏈表的所有結(jié)點到自由空間（保留表頭結(jié)點）

curr=head->next; head->next=curr->next; deletecurr; } curr=head;}插入操作//在當前位置插入元素itemvoidlist::insert(constELEM&item){ assert(curr!=NULL); curr->next=newlink(item,curr->next);}刪除操作ELEMlist::remove(){ assert(isInList()); ELEMtemp=curr->next->element; link*ltemp=curr->next; curr->next=ltemp->next; if(tail==ltemp)tail=curr; deleteltemp; returntemp;}其他操作voidlist::setFirst() {curr=head;}voidlist::next() {if(curr!=NULL)curr=curr->next;}其他操作voidlist::prev(){ link*temp=head; if((curr==NULL)||(curr==head)) {curr=NULL;return;} while((temp!=NULL)&&(temp->next!=curr) temp=temp->next; curr=temp;}intlist::length()const{ intcnt=0; for(link*temp=head->next;temp!=NULL;temp=temp->next) cnt++; returncnt;}其他操作voidlist::setPos(constintpos){ curr=head; for(inti=0;(curr!=NULL)&&(i<pos);i++) curr=curr->next;}voidlist::setValue(constELEM&val) {assert(isInList());curr->next->element=val;}ELEMlist::currValue()const {assert(isInList());returncurr->next->element;}boollist::isEmpty()const {returnhead->next==NULL;}boollist::isInList()const {return(curr!=NULL)&&(curr->next!=NULL);}查找方法find方法是從curr開始查找val值在表中最先出現(xiàn)的地方。boollist::find(constELEM&val){ while(isInList()) if(cuur->next->element==val)returnTRUE; elsecurr=curr->next; returnFALSE;}3.2.3兩種基本實現(xiàn)方法的比較空間效率時間效率順序表存儲每個數(shù)據(jù)元素時沒有浪費空間訪問：在順序表中是直接定位的，所需的操作次數(shù)是O(1)插入和刪除：平均時間和最差時間均為O(n)鏈表每個結(jié)點上除存儲數(shù)據(jù)元素外，還要存放一個指針，這個指針一般稱為結(jié)構(gòu)性開銷。訪問：單鏈表不能直接訪問上述元素，只能從表頭開始逐個查找，直到找到第i個結(jié)點為止。平均時間和最差時間均為O(n)插入和刪除：鏈表的insert和remove操作所需時間僅為O(1)3.2.4循環(huán)鏈表循環(huán)鏈表就是將單鏈表中最后一個結(jié)點的指針指向頭結(jié)點，使整個鏈表構(gòu)成一個環(huán)形。當然，這種鏈表就不再需要尾指針tail了。循環(huán)鏈表的優(yōu)點是從任一結(jié)點出發(fā)都可以訪問到表中所有各結(jié)點。

19251211headcurr圖3.8一個循環(huán)鏈表3.2.5雙向鏈表雙向鏈表將單鏈表中單方向的指針增加為兩個方向的指針，一個向后指向它的后繼結(jié)點，另一個向前指向它的前趨結(jié)點。19251211headcurr圖3.9

一個雙向鏈表雙向鏈表結(jié)點的實現(xiàn)如下classlink{public: ELEMelement; link*next; link*prev; link(constELEM&elemval,li