數(shù)據(jù)結(jié)構(gòu)與算法 課件 第1、2章 數(shù)據(jù)結(jié)構(gòu)概述、線性表

1.1數(shù)據(jù)結(jié)構(gòu)的基本概念

1.2算法1.1數(shù)據(jù)結(jié)構(gòu)的基本概念1.1.1為什么要學習數(shù)據(jù)結(jié)構(gòu)圖靈獎獲得者尼古拉斯·沃斯(NiklausWirth)提出程序就是“數(shù)據(jù)結(jié)構(gòu)?+?算法”，這說明了數(shù)據(jù)結(jié)構(gòu)和算法在程序設(shè)計中所起的重要作用。用計算機求解任何問題都離不開程序，程序設(shè)計的一般過程如圖1.1所示。我們通過程序設(shè)計解決某個實際問題一般需要經(jīng)過以下幾個階段：(1)分析階段：對問題進行分析，抽象出數(shù)據(jù)模型，形成求解問題的基本思路，確定解決問題的方案；(2)設(shè)計階段：將數(shù)據(jù)以及數(shù)據(jù)之間的關(guān)系存儲到計算機的內(nèi)存中，設(shè)計數(shù)據(jù)處理的算法；(3)實現(xiàn)階段：將算法轉(zhuǎn)換為用某種程序設(shè)計語言編寫的程序，并進行測試、修改，直到確定出合適的程序設(shè)計方法。

1.1.2什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)(Data)是信息的載體，它是描述客觀事物的數(shù)字、字符以及所有能輸入到計算機中并被計算機程序處理的符號的集合。例如，一個代數(shù)方程的求解程序中所用的數(shù)據(jù)是整數(shù)和實數(shù)；一個編譯程序或文本編輯程序中所使用的數(shù)據(jù)是字符串。隨著計算機應(yīng)用領(lǐng)域的擴大，數(shù)據(jù)的含義更為廣泛，如圖像、聲音等都可以通過編碼成為數(shù)據(jù)。數(shù)據(jù)元素(DataElement)是數(shù)據(jù)的基本單位。有些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點、頂點、記錄。有時，一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項(DataItem)組成。數(shù)據(jù)項是具有獨立含義的、不可再分割的最小標識單位。例如，某校某專業(yè)的學生成績表如表1.1所示。我們把學生成績表稱為一個數(shù)據(jù)，表中的每一行是一個數(shù)據(jù)元素，它由學號、姓名、性別、各科成績及平均成績等數(shù)據(jù)項組成。數(shù)據(jù)結(jié)構(gòu)(DataStructure)是數(shù)據(jù)元素之間的相互關(guān)系，即數(shù)據(jù)的組織形式。一般來說，數(shù)據(jù)結(jié)構(gòu)所研究的主要內(nèi)容包括以下三個方面：(1)數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系。(2)數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計算機中的存儲方式。數(shù)據(jù)的存儲結(jié)構(gòu)又稱為數(shù)據(jù)的物理結(jié)構(gòu)。(3)數(shù)據(jù)的運算：對數(shù)據(jù)施加的操作。數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學模型。數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)，它是依賴于計算機語言的。對機器語言而言，存儲結(jié)構(gòu)是具體的，但我們只在高級語言的層次上來討論存儲結(jié)構(gòu)。數(shù)據(jù)的運算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)之上。每一種邏輯結(jié)構(gòu)都有一組基本運算，例如對數(shù)據(jù)進行查找、插入、刪除、排序等運算。在數(shù)據(jù)的邏輯結(jié)構(gòu)層面上，我們只需要知道這些基本運算“做什么”，而不需要考慮“如何做”。只有確定了數(shù)據(jù)的存儲結(jié)構(gòu)，我們才能夠具體實現(xiàn)這些基本運算。1.1.3數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)用于描述數(shù)據(jù)中各個元素的邏輯關(guān)系。如圖1.2所示，根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為以下四類：(1)集合：數(shù)據(jù)元素之間除了“屬于同一集合”的關(guān)系之外，沒有其他關(guān)系。(2)線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在“一對一”的前后順序關(guān)系，除第一個元素和最后一個元素之外，其余元素都有唯一的一個直接前驅(qū)元素和唯一的一個直接后繼元素。(3)樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在“一對多”的層次關(guān)系，除最頂層的元素之外，其余元素都有若干個直接后繼元素。(4)圖結(jié)構(gòu)：數(shù)據(jù)元素之間存在“多對多”的任意關(guān)系，每個元素都有若干個直接前驅(qū)元素和若干個直接后繼元素。由于集合具有簡單性和松散性，因此不在數(shù)據(jù)結(jié)構(gòu)課程的討論范圍內(nèi)。數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。線性表、棧、隊列、串等屬于線性結(jié)構(gòu)，而樹形結(jié)構(gòu)和圖結(jié)構(gòu)屬于非線性結(jié)構(gòu)。1.1.4數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)又稱為數(shù)據(jù)的存儲方法，是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機中的表示。也就是說，存儲結(jié)構(gòu)除了要存儲數(shù)據(jù)元素，還要隱式或者顯式地表示數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)的存儲結(jié)構(gòu)分為以下四種：1)順序存儲結(jié)構(gòu)借助元素在存儲器的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系，元素之間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)，由此得到的存儲表示稱為順序存儲結(jié)構(gòu)(SequentialStorageStructure)。通常順序存儲結(jié)構(gòu)是借助于程序語言的數(shù)組(又稱為向量)來描述的。該方法主要應(yīng)用于線性數(shù)據(jù)結(jié)構(gòu)。非線性的數(shù)據(jù)結(jié)構(gòu)也可以通過某種線性化的方法來實現(xiàn)順序存儲。2)鏈式存儲結(jié)構(gòu)借助指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系，即邏輯上相鄰的元素在物理位置上不一定相鄰，由此得到的存儲表示稱為鏈式存儲結(jié)構(gòu)(LinkedStorageStructure)，通常要借助于程序語言的指針類型來描述它。3)索引存儲結(jié)構(gòu)索引存儲結(jié)構(gòu)是指在存儲數(shù)據(jù)元素的同時，還建立附加的索引表。索引表中的每一項稱為索引項，其一般形式是(關(guān)鍵字，地址)，關(guān)鍵字是能夠唯一標識一個元素的那些數(shù)據(jù)項。若每個元素在索引表中都有一個索引項，則該索引表稱為稠密索引(DenseIndex)；若一組元素在索引表中對應(yīng)一個索引項，則該索引表稱為稀疏索引(SparseIndex)。稠密索引中索引項的地址指示元素所在的存儲位置，而稀疏索引中索引項的地址則指示一組元素的起始存儲位置。4)散列存儲結(jié)構(gòu)散列存儲結(jié)構(gòu)的基本思想是根據(jù)數(shù)據(jù)元素的關(guān)鍵字直接計算出該元素的存儲地址。上述四種基本的存儲方法既可以單獨使用，也可以組合起來對數(shù)據(jù)結(jié)構(gòu)進行存儲。同一種邏輯結(jié)構(gòu)采用不同的存儲方法，可以得到不同的存儲結(jié)構(gòu)。至于選擇何種存儲結(jié)構(gòu)來表示相應(yīng)的邏輯結(jié)構(gòu)，應(yīng)當考慮算法運算是否方便以及時間和空間要求等因素。1.2算法1.2.1算法的定義與性質(zhì)數(shù)據(jù)的運算是通過算法(Algorithm)描述的。對實際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，設(shè)計一個好的算法，是程序設(shè)計的本質(zhì)。算法與數(shù)據(jù)結(jié)構(gòu)是互相依賴、互相聯(lián)系的。算法是對特定問題求解步驟的描述，是指令的有限序列。算法必須滿足以下性質(zhì)：(1)輸入性：0至多個輸入，這些輸入取自于某個特定的對象的集合。(2)輸出性：1至多個輸出，這些輸出是同輸入有著某種特定關(guān)系的量。(3)有窮性：對于合法的輸入值，算法在執(zhí)行有窮步之后結(jié)束。(4)確定性：對于相同的輸入執(zhí)行相同的路徑，即對于相同的輸入只能得出相同的輸出。(5)可行性：用于描述算法的操作都是足夠基本的，即算法中描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。需要說明的是，算法與程序是有區(qū)別的。算法具有有窮性，而程序不一定具有有窮性。1.2.2描述算法的工具數(shù)最大公約數(shù)的算法算法設(shè)計者在構(gòu)思和設(shè)計了一個算法之后，必須清楚準確地將所設(shè)計的求解步驟記錄下來，即描述算法。常用的描述算法的工具有自然語言、流程圖、程序設(shè)計語言和偽代碼等。下面以求兩個正整數(shù)最大公約數(shù)的算法為例進行介紹。1.自然語言用自然語言描述算法的優(yōu)點是容易理解，缺點是不夠嚴謹，容易出現(xiàn)二義性，并且算法通常較為冗長。求兩個正整數(shù)最大公約數(shù)的算法用自然語言描述如下：步驟1：將m除以n得到余數(shù)r。步驟2：若r等于0，則n為最大公約數(shù)，算法結(jié)束；否則執(zhí)行步驟3。步驟3：將n的值賦給m，r的值賦給n，重復(fù)執(zhí)行步驟1。2．流程圖用流程圖描述算法的優(yōu)點是直觀易懂，缺點是嚴密性不如程序設(shè)計語言，靈活性不如自然語言。用流程圖描述的求兩個正整數(shù)最大公約數(shù)的算法如圖1.3所示。在計算機應(yīng)用早期，使用流程圖描述算法占據(jù)著統(tǒng)治地位，但實踐證明，這種描述方法使用起來非常不方便。3．程序設(shè)計語言用程序設(shè)計語言描述的算法能夠由計算機執(zhí)行，缺點是抽象性差。設(shè)計者在設(shè)計算法時由于受到程序設(shè)計語言的語法規(guī)則限制，往往忽視了算法的正確性和邏輯性。求兩個正整數(shù)最大公約數(shù)的算法用C語言描述時，所編寫的程序如下：4．偽代碼偽代碼(Pseudocode)是介于自然語言和高級語言之間的方法，它遵循某一程序設(shè)計語言的基本語法，但操作指令可以結(jié)合自然語言來設(shè)計。至于自然語言的成分有多少，取決于算法的抽象程度。抽象程度高，偽代碼中的自然語言就多一些，程序設(shè)計語言的語句就少一些；反之亦然。求兩個正整數(shù)最大公約數(shù)的算法用偽代碼描述如下：上述偽代碼可以再具體一些，即抽象程度低一些，也就是說程序設(shè)計語言的成分多一些。我們可用類C語言來描述算法。類C語言遵循C語言的語法規(guī)則，但不必拘泥于C語言的實現(xiàn)細節(jié)，又容易轉(zhuǎn)換為C程序。通常用類C語言的函數(shù)來描述算法，重點給出算法的邏輯，忽略局部變量的聲明，并且不在主函數(shù)中調(diào)用。求兩個正整數(shù)最大公約數(shù)的算法用類C語言描述如下：1.2.3對算法的評價標準我們通常從正確性、易讀性、健壯性和高效性等四個方面評價算法的質(zhì)量。正確性是指算法能夠完成預(yù)定的功能。易讀性決定了算法是否易于閱讀和理解，以便對程序進行調(diào)試、修改和擴充。健壯性體現(xiàn)在當環(huán)境發(fā)生變化時，算法能夠適當?shù)刈龀龇磻?yīng)或進行處理，不會產(chǎn)生不需要的運行結(jié)果。高效性是指算法在時間和空間兩個方面的效率。1．算法的高效性算法的時間特性是指執(zhí)行算法所需要的計算時間長短，算法的空間特性則是執(zhí)行算法所需要的輔助存儲空間大小。當然我們希望選用一個占用存儲空間小、運行時間短的算法。然而上述要求常常相互抵觸，要節(jié)約算法的執(zhí)行時間，往往要以犧牲更多的空間為代價；而為了節(jié)省空間，可能要耗費更多的計算時間。算法的時間特性和空間特性通常會與問題的規(guī)模有關(guān)，因此我們只能根據(jù)具體情況有所側(cè)重。一個算法所需的計算時間，應(yīng)當是該算法中每條語句的執(zhí)行時間之和，而每條語句的執(zhí)行時間是該語句的執(zhí)行次數(shù)(稱為頻度)與該語句執(zhí)行一次所需時間的乘積。但是，當算法轉(zhuǎn)換為程序之后，每條語句執(zhí)行一次所需的時間取決于機器的指令性能、速度以及編譯所產(chǎn)生的代碼質(zhì)量，這是很難確定的。我們假設(shè)每條語句執(zhí)行一次所需的時間均是一個單位時間，一個算法的計算時間就是該算法中所有語句的頻度之和。這樣，我們就可以獨立于機器的軟、硬件系統(tǒng)來分析算法的時間特性。一般情況下，算法中基本操作重復(fù)執(zhí)行的時間是問題規(guī)模n的某個函數(shù)f(n)，算法的漸進時間復(fù)雜度(簡稱時間復(fù)雜度(TimeComplexity))記為它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，f(n)一般是算法中頻度最大的語句頻度。當有循環(huán)嵌套時，算法的時間復(fù)雜度是由最內(nèi)層語句的頻度f(n)決定的。對于某些算法，即使問題規(guī)模相同，如果輸入的數(shù)據(jù)不同，其時間開銷也不同。一般來說，最好情況作為算法性能的代表，沒有什么意義。將最壞情況作為計算時間復(fù)雜度的依據(jù)，能夠說明算法的運行時間最壞能壞到什么程度，這一點在實時系統(tǒng)中尤為重要。算法的空間復(fù)雜度是指在算法執(zhí)行過程中所需要的輔助存儲空間數(shù)量。輔助存儲空間是除算法本身和輸入輸出數(shù)據(jù)所占存儲空間之外，為算法臨時開辟的存儲空間，記為其中，n為問題的規(guī)模，其分析方法與算法的時間復(fù)雜度類似。2．算法的易讀性一個高質(zhì)量的算法除了正確和運行效率高之外，還對算法的易讀性有一定的要求。算法的易讀性主要體現(xiàn)在算法的結(jié)構(gòu)、代碼的書寫格式以及注釋等方面。當我們遇到一個較為復(fù)雜的問題時，往往會先對問題進行分解，使每個子問題盡可能簡單，這樣有助于對整個問題的解決。類似地，較為復(fù)雜問題的算法通常也是由一個個模塊組成的，而每個模塊的功能相對獨立。這是對算法結(jié)構(gòu)方面的基本要求。對算法中模塊的要求是獨立性高，也就是應(yīng)當盡可能做到高內(nèi)聚、低耦合。在代碼書寫格式方面應(yīng)當采用縮進的方式突出分支、循環(huán)、嵌套等結(jié)構(gòu)，這樣可以清晰地體現(xiàn)算法的視覺組織。算法中的注釋就是對算法進行必要的說明，幫助我們理解算法。注釋分為序言性注釋和功能性注釋兩種。2.1線性表的邏輯結(jié)構(gòu)

2.2線性表的順序存儲結(jié)構(gòu)

2.3線性表的鏈式存儲結(jié)構(gòu)

2.4順序表與鏈表的比較2.1線性表的邏輯結(jié)構(gòu)2.1.1線性表的定義線性表(LinearList)是由n(n≥0)個數(shù)據(jù)元素(結(jié)點)組成的有限序列，其中元素的個數(shù)n為線性表的長度。當n?=?0時稱為空表，通常將非空線性表(n?>?0)記為線性表中各元素具有相同的特性，i是數(shù)據(jù)元素ai在線性表中的位序，即位置序號。從線性表的定義可以看出它的邏輯特征：對于一個非空線性表，有且僅有一個開始結(jié)點a1，有且僅有一個終端結(jié)點an；除第一個結(jié)點外，其余結(jié)點ai(2≤i≤n)均有且僅有一個直接前驅(qū)ai-1；除最后一個結(jié)點外，其余結(jié)點ai(1≤i≤n-1)均有且僅有一個直接后繼ai+1。2.1.2線性表的基本運算每一種數(shù)據(jù)的邏輯結(jié)構(gòu)都對應(yīng)一組基本運算。這里只是給出抽象的運算，而運算的具體實現(xiàn)只有在確定了數(shù)據(jù)的存儲結(jié)構(gòu)之后才能考慮。對線性表實施的基本運算主要有以下幾種：1)?InitList(&L)線性表初始化初始條件：線性表L不存在。運算結(jié)果：構(gòu)造一個空的線性表。2)?SetNull(L)置空表初始條件：線性表L已存在。運算結(jié)果：將表L置為空表。3)?Length(L)求表長度初始條件：線性表L已存在。運算結(jié)果：返回表L中的數(shù)據(jù)元素個數(shù)。4)?Get(L,i)取元素值初始條件：線性表L已存在。運算結(jié)果：返回表L中第i個數(shù)據(jù)元素ai的值或元素的位置信息。5)?Locate(L,x)定位，按值查找初始條件：線性表L已存在。運算結(jié)果：若表L中存在一個或多個值為x的元素，返回第一個查找到的數(shù)據(jù)元素的位序；否則返回一個特殊值。6)?Insert(L,x,i)插入初始條件：線性表L已存在。運算結(jié)果：在表L中第i個位置上插入值為x的元素。若插入成功，表長加1。7)?Delete(L,i)刪除初始條件：線性表L已存在。運算結(jié)果：刪除表L中第i個數(shù)據(jù)元素。若刪除成功，表長減1。需要說明的是每種基本運算用一個函數(shù)來表示，函數(shù)的參數(shù)L是指向線性表結(jié)構(gòu)體的指針。其中線性表初始化運算使線性表從不存在到存在，顯然指針L的指向發(fā)生了變化；置空表、插入和刪除運算使線性表的內(nèi)容發(fā)生了變化，但指針的指向并不會發(fā)生變化；求表長度、取元素值和定位運算，指針L和表的內(nèi)容都沒有發(fā)生變化。上述運算并不是線性表的全部運算。因為對于不同應(yīng)用問題中所使用的線性表，所需執(zhí)行的運算可能不同，所以我們不可能也沒有必要事先定義一組適合各種需要的運算。因此，通常的做法是只給出一組最基本的運算，對于實際問題中涉及的其他更為復(fù)雜的運算，可以用基本運算的組合(調(diào)用基本運算)來實現(xiàn)。例2.1將線性表A按元素值奇、偶數(shù)拆分成兩個表，A表存放奇數(shù)，B表存放偶數(shù)。算法如下：2.2線性表的順序存儲結(jié)構(gòu)2.2.1線性表的順序存儲——順序表將一個線性表存儲到計算機中，可以采用許多不同的方法，其中既簡單又自然的是順序存儲方法，即把線性表的元素按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。用這種方法存儲的線性表簡稱為順序表(SequentialList)。由于線性表中所有元素類型都是相同的，因此每個元素所占用存儲空間的大小亦是相同的。假設(shè)順序表中每個元素占用c個存儲單元，那么第一個單元的存儲地址是該元素的存儲地址，順序表中開始元素a1的存儲地址是Loc(a1)，那么元素ai的存儲地址Loc(ai)可通過式(2-2)計算。其中Loc(a1)是順序表的第一個元素a1的存儲地址，通常稱作順序表的起始地址或基地址。在順序表中，每個結(jié)點ai的存儲地址是該結(jié)點在表中位置i的線性函數(shù)。只要知道順序表的起始地址，順序表中任一數(shù)據(jù)元素都可隨機存取。因此順序表是一種隨機存取的存儲結(jié)構(gòu)，可以對順序表順序存取(SequentialAccess)或隨機存取(RandomAccess)。由于程序設(shè)計語言中的數(shù)組也采用順序存儲結(jié)構(gòu)，故可用一維數(shù)組存放線性表的元素。又因為數(shù)組的長度往往大于線性表的實際長度，所以順序表還應(yīng)該用一個變量來表示表的當前長度，我們用結(jié)構(gòu)類型來定義順序表的類型。在上述定義中，存放線性表結(jié)點的數(shù)組長度maxsize應(yīng)當選擇適當，使得它既能夠滿足表結(jié)點數(shù)目動態(tài)增加的需要，又不至于預(yù)先定義得過大而浪費存儲空間。圖2.1是線性表順序存儲示意圖，我們可以看出順序表的特點是邏輯上相鄰的結(jié)點其物理位置上亦相鄰。由于線性表結(jié)點的位序從1開始，而C語言中數(shù)組的下標從0開始，因此關(guān)于線性表中數(shù)據(jù)元素的位序(邏輯位置)和存放它的數(shù)組下標(物理位置)之間的關(guān)系通常有兩種處理方式：第一種方式是從下標為0的數(shù)組元素開始存放，則結(jié)點的位序等于數(shù)組元素的下標加一；第二種方式是從下標為1的數(shù)組元素開始使用，這樣結(jié)點的位序和數(shù)組的下標是相等的，使用起來會更簡單自然一些，下標為0的元素不用或用作其他用途。若L是指向順序表的指針，則a1～an分別存儲在L->data[0]～L->data[L->last-1]中，L->last表示線性表當前的長度。2.2.2線性表的基本運算在順序表上的實現(xiàn)在順序表中，線性表的有些基本運算很容易實現(xiàn)。例如，設(shè)L是指向某一順序表的指針，則置空表的操作是將表的長度置0，即L->last=0；求表的長度和取表中第i個元素值的操作只需分別返回L->last和L->data[i-1]即可。下面重點討論表初始化、插入和刪除運算。1．順序表的初始化在函數(shù)中建立一個空順序表L，指針L從沒有指向順序表變?yōu)橹赶蛞粋€空表，顯然指針L的指向發(fā)生了變化。如何將這一變化的結(jié)果帶回到主調(diào)函數(shù)，我們給出以下三種方式，并進行比較。算法2.1通過函數(shù)返回值將結(jié)果帶回到主調(diào)函數(shù)。在函數(shù)中定義的指針指向順序表，指針作為函數(shù)的返回值。算法2.2采用指向指針的指針作為函數(shù)參數(shù)，通過函數(shù)的參數(shù)將結(jié)果帶回到主調(diào)函數(shù)。第一級指針L指向第二級指針?*L，L的指向沒有改變，而?*L的指向發(fā)生了變化。函數(shù)運行結(jié)束，將?*L的指向帶回到主調(diào)函數(shù)。算法2.3采用指針的引用作為函數(shù)參數(shù)，通過函數(shù)的參數(shù)將結(jié)果帶回到主調(diào)函數(shù)。參數(shù)的類型使用了C++?語言中的指針類型的引用，可以將指針所指向的結(jié)構(gòu)體動態(tài)存儲帶回到主調(diào)函數(shù)。2．順序表的插入在線性表的第i(1≤i≤n+1)個位置上插入一個新結(jié)點x，并且使表的長度加1，即使變?yōu)殚L度是n?+?1的線性表由于順序表存在“上溢”的可能，因此在插入之前需要判斷表的數(shù)組空間是否已滿。若已經(jīng)滿，則返回值為0，表示插入不成功；否則返回值為1，表示插入成功。在順序表中，由于結(jié)點的物理順序必須與結(jié)點的邏輯順序保持一致，因此我們必須按照an到ai的順序依次將an～ai后移一個位置，為插入的x讓出存儲位置，然后在該位置上插入新結(jié)點x。僅當插入位置i?=?n?+?1時，才無須移動結(jié)點，直接將新結(jié)點x添加到表的末尾。插入過程如圖2.2所示，具體算法描述如下所示：算法2.4在順序表的第i個位置上插入一個新結(jié)點x?，F(xiàn)在分析順序表插入算法的時間復(fù)雜度。顯然算法2.4的時間主要花費在結(jié)點的移動上，移動結(jié)點的個數(shù)不僅依賴于表的長度n，而且與插入的位置i有關(guān)。for語句的循環(huán)體執(zhí)行了n-i+1次。當i?=?n+1時，由于循環(huán)變量的終值大于初值，結(jié)點后移語句不執(zhí)行；當i?=?1時，結(jié)點后移語句執(zhí)行n次，移動表中所有結(jié)點。也就是說，該算法在最好情況下時間復(fù)雜度是O(1)，最壞情況時間復(fù)雜度是O(n)。由于插入可能在表中任意位置上進行，因此需分析算法的平均性能。在長度為n的順序表中插入一個結(jié)點，移動結(jié)點次數(shù)的期望值(平均移動次數(shù))為假設(shè)pi是在第i位置上插入一個結(jié)點的概率，并且在表中任何合法位置(1≤i≤n+1)插入結(jié)點的概率相等，則因此，在等概率插入的情況下，有也就是說，在順序表上做插入運算，平均要移動表中的一半結(jié)點。就數(shù)量級而言，算法的時間復(fù)雜度仍然是O(n)。3．順序表的刪除線性表的刪除運算是指將表的第i(1≤i≤n)個結(jié)點刪去，并且使表的長度減1，即使變成長度為n-1的線性表順序表還存在“下溢”的可能。如果是空表，返回值為0，表示刪除不成功；否則返回值為1，表示刪除成功。和插入運算類似，在順序表中實現(xiàn)刪除運算也必須移動結(jié)點，才能反映出結(jié)點間的邏輯關(guān)系的變化。若i?=?n，則無須移動；若1≤i≤n-1，則必須將表中位置i+1,i+2,…,n上的結(jié)點依次前移到位置i,i?+?1,…,n-1上。這兩種情況下的時間復(fù)雜度分別是O(1)和O(n)。順序表中結(jié)點的刪除過程見圖2.3。算法2.5刪除順序表的第i個結(jié)點。算法2.5的平均性能分析與插入算法類似。在長度為n的順序表中刪除一個結(jié)點，移動結(jié)點次數(shù)的期望值(平均移動次數(shù))為式中，pi表示刪除表中第i個結(jié)點的概率。在等概率的假設(shè)下，有由此可得即在順序表上做刪除運算，平均要移動表中約一半的結(jié)點，算法的時間復(fù)雜度為O(n)。2.3線性表的鏈式存儲結(jié)構(gòu)2.3.1單鏈表1．單鏈表概述單鏈表(SingleLinkedList)是指在內(nèi)存中用一組連續(xù)的或不連續(xù)的存儲單元來存儲線性表的數(shù)據(jù)元素，每個元素含有一個數(shù)據(jù)域(data)和一個指針域(next)。這兩部分信息組成了單鏈表中的一個結(jié)點，如圖2.4所示。單鏈表中每個結(jié)點的數(shù)據(jù)域用于存放結(jié)點的數(shù)據(jù)，指針域存放結(jié)點的直接后繼結(jié)點的地址。由于開始結(jié)點無前驅(qū)結(jié)點，故應(yīng)設(shè)頭指針head指向開始結(jié)點；終端結(jié)點無后繼結(jié)點，它的指針域為空，即NULL(圖示中也可以用^表示)。單鏈表正是通過頭指針以及每個結(jié)點的指針域?qū)⒕€性表的n個結(jié)點按其邏輯順序鏈接在一起。下面給出用C語言描述的單鏈表結(jié)點類型定義：指針變量簡稱指針，用于存放結(jié)點的地址，即用于指向結(jié)點。一個結(jié)點就是一個結(jié)構(gòu)體變量。若指針的值非空，則它指向一個類型為linklist的結(jié)點；若指針的值為空，則它不指向任何結(jié)點。指針所指向的結(jié)點存儲空間是在程序執(zhí)行過程中生成和釋放的，故稱為動態(tài)存儲空間。在C語言中，通過下面兩個標準函數(shù)生成或釋放結(jié)點。生成結(jié)點：p=(linklist*)malloc(sizeof(linklist));

釋放結(jié)點：free(p);函數(shù)malloc的返回值類型是void*，然后進行強制類型轉(zhuǎn)換得到一個類型為linklist的結(jié)點空間。p中所存放的是該結(jié)點的首地址，也可以說，p指向該結(jié)點。如果結(jié)點變量不再使用，調(diào)用函數(shù)free刪除結(jié)點所占的存儲空間。我們必須通過指針來訪問結(jié)點，即用?*p表示結(jié)點。用p->data和p->next或者?(*p).data和?(*p).next表示結(jié)點的數(shù)據(jù)域和指針域，前者是比較常用的形式。2．頭結(jié)點特別需要指出的是，單鏈表以及后面所討論的循環(huán)鏈表和雙向鏈表均可以帶頭結(jié)點或者不帶頭結(jié)點，見圖2.7和圖2.8。頭結(jié)點就是在單鏈表的第一個結(jié)點之前附設(shè)一個結(jié)點，頭結(jié)點數(shù)據(jù)域可以存放一些特殊信息。如果數(shù)據(jù)域為整型，可以存放鏈表的長度信息。使用頭結(jié)點的好處如下：(1)由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中，所以對鏈表第一個結(jié)點的操作同其他結(jié)點一樣，無需特殊處理。(2)無論鏈表是否為空，其頭指針是指向頭結(jié)點的非空指針，因此對空表與非空表的處理也就統(tǒng)一了。從上述兩點我們可以看出，使用頭結(jié)點可以降低鏈表操作的復(fù)雜性和出現(xiàn)錯誤的機會。3．單鏈表的基本運算下面我們將以帶頭結(jié)點的單鏈表為例，講述如何實現(xiàn)線性表的幾種基本運算。1)建立單鏈表假設(shè)單鏈表結(jié)點的數(shù)據(jù)域類型是字符型，可逐個輸入字符，并以換行符“\n”作為輸入結(jié)束標志。動態(tài)建立單鏈表通常有以下兩種方法：(1)頭插法建表從空表開始，每次將輸入的字符作為新結(jié)點插入到表頭，鏈表中結(jié)點的次序與輸入字符的順序相反。請注意，圖2.9中給出的序號與算法中的序號是對應(yīng)的，表示在建表過程中的操作次序。算法2.6用頭插法建立單鏈表。算法2.6中循環(huán)語句的循環(huán)體執(zhí)行了n次，所以時間復(fù)雜度為O(n)。(2)尾插法建表如圖2.10所示，將新結(jié)點插入到表尾，鏈表中結(jié)點的次序與輸入字符的順序相同。算法2.7用尾插法建立單鏈表。如果在單鏈表中不設(shè)置頭結(jié)點，采用尾插法建表，需要對第一個結(jié)點進行特殊處理。請讀者自行分析下面的算法2.8，并體會不設(shè)置頭結(jié)點的缺點。算法2.8用尾插法建立不帶頭結(jié)點的單鏈表。2)單鏈表的查找(1)按序號查找由于鏈表不是隨機存儲結(jié)構(gòu)，因此即使知道被訪問結(jié)點的序號i，也不能像順序表那樣直接按序號訪問結(jié)點，只能從頭指針出發(fā)，沿著結(jié)點的指針域進行搜索，直至找到第i個結(jié)點為止。設(shè)單鏈表的長度為n，并且規(guī)定頭結(jié)點的位序為0，要查找第i個結(jié)點，僅當1≤i≤n時，才能查找到。在算法2.9中，我們從頭結(jié)點開始沿著鏈表掃描，用指針p指向當前掃描到的結(jié)點，用j作計數(shù)器，累計當前已掃描的結(jié)點數(shù)。p的初值指向頭結(jié)點，j的初值為0，當p指向下一個結(jié)點時，計數(shù)器j的值相應(yīng)加1。分析循環(huán)語句中的表達式，結(jié)束循環(huán)有兩種可能：一種是j等于i，此時指針p所指向的結(jié)點就是要查找的第i個結(jié)點；另一種可能是p->next為NULL并且j小于i，則單鏈表中不存在第i個結(jié)點。(2)按值查找。在單鏈表中查找是否存在給定查找值key的結(jié)點，若存在，則返回該結(jié)點的地址；否則返回NULL。算法2.10按值查找單鏈表。3)單鏈表的插入在單鏈表中插入或刪除元素，只需要修改指針的指向，不需要移動結(jié)點。如圖2.11所示，將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到元素ai-1與ai之間。由于單鏈表只能做“后插”，不能做“前插”，因此必須先使指針p指向第i個結(jié)點的直接前驅(qū)結(jié)點，然后將新結(jié)點插入在指針p所指向的結(jié)點之后。算法2.11插入單鏈表。設(shè)鏈表的長度為n，合法的插入位置是1≤i≤n+1。當i=1時，p指向頭結(jié)點；當i=n+1時，p指向終端結(jié)點。因此，用i-1作為實參調(diào)用Get時可完成插入位置的合法性檢查。算法的時間主要耗費在查找操作Get上，所以時間復(fù)雜度為O(n)。在涉及改變指針指向的操作中，一定要注意操作的次序，否則容易出錯。假如上面的③、④號操作的順序顛倒過來，會造成鏈表斷開，后面一截鏈表“丟失”了，如圖2.12所示。4)單鏈表的刪除要在單鏈表中刪除第i個結(jié)點ai，首先應(yīng)找到它的直接前驅(qū)結(jié)點ai-1的存儲位置p，然后使p->next指向ai的直接后繼結(jié)點，即把結(jié)點ai從鏈上摘下。刪除結(jié)點的示意圖如圖2.13所示。算法2.12刪除單鏈表。2.3.2循環(huán)鏈表循環(huán)鏈表(CircularLinkedList)是一種首尾相接的鏈式存儲結(jié)構(gòu)。循環(huán)鏈表一般是指單循環(huán)鏈表，其特點是單鏈表中最后一個結(jié)點的指針域指向頭結(jié)點或開始結(jié)點，整個鏈表形成一個環(huán)，從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點。帶頭結(jié)點的單循環(huán)鏈表如圖2.14所示。在用頭指針表示的單循環(huán)鏈表中，找開始結(jié)點a1的時間復(fù)雜度為O(1)。然而要找到終端結(jié)點an，則需要從頭指針開始遍歷整個鏈表，其時間復(fù)雜度為O(n)。如果改用尾指針rear表示帶頭結(jié)點的單循環(huán)鏈表(見圖2.15)，則開始結(jié)點a1和終端結(jié)點an的存儲位置分別是rear->next->next和rear，查找這兩個結(jié)點的時間復(fù)雜度都是O(1)。因此，在實際應(yīng)用中采用尾指針表示單循環(huán)鏈表，可以使某些運算易于實現(xiàn)且效率高。2.3.3雙向鏈表在單循環(huán)鏈表中，雖然從任一結(jié)點出發(fā)能找到其直接前驅(qū)結(jié)點，但需要遍歷整個鏈表，其時間復(fù)雜度為O(n)。如果在每個結(jié)點內(nèi)再增加一個指向其直接前驅(qū)結(jié)點的指針域prior，就可以快速查找直接前驅(qū)結(jié)點。這樣的鏈表稱為雙向鏈表(DoubleLinkedList)，其結(jié)點的結(jié)構(gòu)體類型定義如下：與單向循環(huán)鏈表類似，雙向鏈表也可以采用循環(huán)表，將頭結(jié)點和終端結(jié)點鏈接起來，構(gòu)成順時針和逆時針的兩個環(huán)，如圖2.16所示。設(shè)指針p指向雙向鏈表中的某個結(jié)點，則p->prior->next讀作p所指結(jié)點的前驅(qū)指針域所指結(jié)點的后繼指針域，與p的指向是相同的。類似地，p->next->prior也與p的指向相同。在雙向鏈表中既可以進行“后插”，也可以進