數(shù)據(jù)結(jié)構(gòu)與算法 課件全套 （周大為）第1-10章 數(shù)據(jù)結(jié)構(gòu)概述 -并行數(shù)據(jù)結(jié)構(gòu)及應(yīng)用

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

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

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

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

2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

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

釋放結(jié)點(diǎn)：free(p);函數(shù)malloc的返回值類型是void*，然后進(jìn)行強(qiáng)制類型轉(zhuǎn)換得到一個(gè)類型為linklist的結(jié)點(diǎn)空間。p中所存放的是該結(jié)點(diǎn)的首地址，也可以說(shuō)，p指向該結(jié)點(diǎn)。如果結(jié)點(diǎn)變量不再使用，調(diào)用函數(shù)free刪除結(jié)點(diǎn)所占的存儲(chǔ)空間。我們必須通過(guò)指針來(lái)訪問(wèn)結(jié)點(diǎn)，即用?*p表示結(jié)點(diǎn)。用p->data和p->next或者?(*p).data和?(*p).next表示結(jié)點(diǎn)的數(shù)據(jù)域和指針域，前者是比較常用的形式。2．頭結(jié)點(diǎn)特別需要指出的是，單鏈表以及后面所討論的循環(huán)鏈表和雙向鏈表均可以帶頭結(jié)點(diǎn)或者不帶頭結(jié)點(diǎn)，見(jiàn)圖2.7和圖2.8。頭結(jié)點(diǎn)就是在單鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，頭結(jié)點(diǎn)數(shù)據(jù)域可以存放一些特殊信息。如果數(shù)據(jù)域?yàn)檎?，可以存放鏈表的長(zhǎng)度信息。使用頭結(jié)點(diǎn)的好處如下：(1)由于開(kāi)始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中，所以對(duì)鏈表第一個(gè)結(jié)點(diǎn)的操作同其他結(jié)點(diǎn)一樣，無(wú)需特殊處理。(2)無(wú)論鏈表是否為空，其頭指針是指向頭結(jié)點(diǎn)的非空指針，因此對(duì)空表與非空表的處理也就統(tǒng)一了。從上述兩點(diǎn)我們可以看出，使用頭結(jié)點(diǎn)可以降低鏈表操作的復(fù)雜性和出現(xiàn)錯(cuò)誤的機(jī)會(huì)。3．單鏈表的基本運(yùn)算下面我們將以帶頭結(jié)點(diǎn)的單鏈表為例，講述如何實(shí)現(xiàn)線性表的幾種基本運(yùn)算。1)建立單鏈表假設(shè)單鏈表結(jié)點(diǎn)的數(shù)據(jù)域類型是字符型，可逐個(gè)輸入字符，并以換行符“\n”作為輸入結(jié)束標(biāo)志。動(dòng)態(tài)建立單鏈表通常有以下兩種方法：(1)頭插法建表從空表開(kāi)始，每次將輸入的字符作為新結(jié)點(diǎn)插入到表頭，鏈表中結(jié)點(diǎn)的次序與輸入字符的順序相反。請(qǐng)注意，圖2.9中給出的序號(hào)與算法中的序號(hào)是對(duì)應(yīng)的，表示在建表過(guò)程中的操作次序。算法2.6用頭插法建立單鏈表。算法2.6中循環(huán)語(yǔ)句的循環(huán)體執(zhí)行了n次，所以時(shí)間復(fù)雜度為O(n)。(2)尾插法建表如圖2.10所示，將新結(jié)點(diǎn)插入到表尾，鏈表中結(jié)點(diǎn)的次序與輸入字符的順序相同。算法2.7用尾插法建立單鏈表。如果在單鏈表中不設(shè)置頭結(jié)點(diǎn)，采用尾插法建表，需要對(duì)第一個(gè)結(jié)點(diǎn)進(jìn)行特殊處理。請(qǐng)讀者自行分析下面的算法2.8，并體會(huì)不設(shè)置頭結(jié)點(diǎn)的缺點(diǎn)。算法2.8用尾插法建立不帶頭結(jié)點(diǎn)的單鏈表。2)單鏈表的查找(1)按序號(hào)查找由于鏈表不是隨機(jī)存儲(chǔ)結(jié)構(gòu)，因此即使知道被訪問(wèn)結(jié)點(diǎn)的序號(hào)i，也不能像順序表那樣直接按序號(hào)訪問(wèn)結(jié)點(diǎn)，只能從頭指針出發(fā)，沿著結(jié)點(diǎn)的指針域進(jìn)行搜索，直至找到第i個(gè)結(jié)點(diǎn)為止。設(shè)單鏈表的長(zhǎng)度為n，并且規(guī)定頭結(jié)點(diǎn)的位序?yàn)?，要查找第i個(gè)結(jié)點(diǎn)，僅當(dāng)1≤i≤n時(shí)，才能查找到。在算法2.9中，我們從頭結(jié)點(diǎn)開(kāi)始沿著鏈表掃描，用指針p指向當(dāng)前掃描到的結(jié)點(diǎn)，用j作計(jì)數(shù)器，累計(jì)當(dāng)前已掃描的結(jié)點(diǎn)數(shù)。p的初值指向頭結(jié)點(diǎn)，j的初值為0，當(dāng)p指向下一個(gè)結(jié)點(diǎn)時(shí)，計(jì)數(shù)器j的值相應(yīng)加1。分析循環(huán)語(yǔ)句中的表達(dá)式，結(jié)束循環(huán)有兩種可能：一種是j等于i，此時(shí)指針p所指向的結(jié)點(diǎn)就是要查找的第i個(gè)結(jié)點(diǎn)；另一種可能是p->next為NULL并且j小于i，則單鏈表中不存在第i個(gè)結(jié)點(diǎn)。(2)按值查找。在單鏈表中查找是否存在給定查找值key的結(jié)點(diǎn)，若存在，則返回該結(jié)點(diǎn)的地址；否則返回NULL。算法2.10按值查找單鏈表。3)單鏈表的插入在單鏈表中插入或刪除元素，只需要修改指針的指向，不需要移動(dòng)結(jié)點(diǎn)。如圖2.11所示，將值為x的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到元素ai-1與ai之間。由于單鏈表只能做“后插”，不能做“前插”，因此必須先使指針p指向第i個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，然后將新結(jié)點(diǎn)插入在指針p所指向的結(jié)點(diǎn)之后。算法2.11插入單鏈表。設(shè)鏈表的長(zhǎng)度為n，合法的插入位置是1≤i≤n+1。當(dāng)i=1時(shí)，p指向頭結(jié)點(diǎn)；當(dāng)i=n+1時(shí)，p指向終端結(jié)點(diǎn)。因此，用i-1作為實(shí)參調(diào)用Get時(shí)可完成插入位置的合法性檢查。算法的時(shí)間主要耗費(fèi)在查找操作Get上，所以時(shí)間復(fù)雜度為O(n)。在涉及改變指針指向的操作中，一定要注意操作的次序，否則容易出錯(cuò)。假如上面的③、④號(hào)操作的順序顛倒過(guò)來(lái)，會(huì)造成鏈表斷開(kāi)，后面一截鏈表“丟失”了，如圖2.12所示。4)單鏈表的刪除要在單鏈表中刪除第i個(gè)結(jié)點(diǎn)ai，首先應(yīng)找到它的直接前驅(qū)結(jié)點(diǎn)ai-1的存儲(chǔ)位置p，然后使p->next指向ai的直接后繼結(jié)點(diǎn)，即把結(jié)點(diǎn)ai從鏈上摘下。刪除結(jié)點(diǎn)的示意圖如圖2.13所示。算法2.12刪除單鏈表。2.3.2循環(huán)鏈表循環(huán)鏈表(CircularLinkedList)是一種首尾相接的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。循環(huán)鏈表一般是指單循環(huán)鏈表，其特點(diǎn)是單鏈表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)或開(kāi)始結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)，從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)。帶頭結(jié)點(diǎn)的單循環(huán)鏈表如圖2.14所示。在用頭指針表示的單循環(huán)鏈表中，找開(kāi)始結(jié)點(diǎn)a1的時(shí)間復(fù)雜度為O(1)。然而要找到終端結(jié)點(diǎn)an，則需要從頭指針開(kāi)始遍歷整個(gè)鏈表，其時(shí)間復(fù)雜度為O(n)。如果改用尾指針rear表示帶頭結(jié)點(diǎn)的單循環(huán)鏈表(見(jiàn)圖2.15)，則開(kāi)始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an的存儲(chǔ)位置分別是rear->next->next和rear，查找這兩個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度都是O(1)。因此，在實(shí)際應(yīng)用中采用尾指針表示單循環(huán)鏈表，可以使某些運(yùn)算易于實(shí)現(xiàn)且效率高。2.3.3雙向鏈表在單循環(huán)鏈表中，雖然從任一結(jié)點(diǎn)出發(fā)能找到其直接前驅(qū)結(jié)點(diǎn)，但需要遍歷整個(gè)鏈表，其時(shí)間復(fù)雜度為O(n)。如果在每個(gè)結(jié)點(diǎn)內(nèi)再增加一個(gè)指向其直接前驅(qū)結(jié)點(diǎn)的指針域prior，就可以快速查找直接前驅(qū)結(jié)點(diǎn)。這樣的鏈表稱為雙向鏈表(DoubleLinkedList)，其結(jié)點(diǎn)的結(jié)構(gòu)體類型定義如下：與單向循環(huán)鏈表類似，雙向鏈表也可以采用循環(huán)表，將頭結(jié)點(diǎn)和終端結(jié)點(diǎn)鏈接起來(lái)，構(gòu)成順時(shí)針和逆時(shí)針的兩個(gè)環(huán)，如圖2.16所示。設(shè)指針p指向雙向鏈表中的某個(gè)結(jié)點(diǎn)，則p->prior->next讀作p所指結(jié)點(diǎn)的前驅(qū)指針域所指結(jié)點(diǎn)的后繼指針域，與p的指向是相同的。類似地，p->next->prior也與p的指向相同。在雙向鏈表中既可以進(jìn)行“后插”，也可以進(jìn)行“前插”，插入一個(gè)結(jié)點(diǎn)應(yīng)當(dāng)修改四個(gè)指針的指向。1．在結(jié)點(diǎn)?*p之后插入結(jié)點(diǎn)?*s雙向鏈表的后插操作如圖2.17所示，在結(jié)點(diǎn)?*p之后插入結(jié)點(diǎn)?*s需要注意以下兩點(diǎn)：(1)先修改待插入結(jié)點(diǎn)?*s的前驅(qū)和后繼指針域，以免發(fā)生“斷鏈”現(xiàn)象；(2)然后修改結(jié)點(diǎn)?*p的后繼指針域所指結(jié)點(diǎn)的前驅(qū)指針域，最后修改結(jié)點(diǎn)?*p的后繼指針域。算法2.13雙向鏈表的后插。2．在結(jié)點(diǎn)?*p之前插入結(jié)點(diǎn)?*s雙向鏈表的前插操作如圖2.18所示，應(yīng)當(dāng)先修改待插入結(jié)點(diǎn)的前驅(qū)和后繼指針域，然后修改結(jié)點(diǎn)?*p的前驅(qū)指針域所指結(jié)點(diǎn)的后繼指針域，最后修改結(jié)點(diǎn)?*p的前驅(qū)指針域。算法2.14雙向鏈表的前插。這兩種插入方法對(duì)指針操作的順序不是唯一的，但也不是任意的。操作次序不當(dāng)就有可能錯(cuò)誤地插入，還有可能“丟失”一部分鏈表。3．刪除結(jié)點(diǎn)?*p雙向鏈表中刪除結(jié)點(diǎn)?*p的操作如圖2.19所示，刪除一個(gè)結(jié)點(diǎn)需要改變兩個(gè)指針的指向。算法2.15雙向鏈表的刪除。4．建立雙向鏈表與單鏈表的建立類似，建立雙向鏈表也分為頭插法和尾插法。算法2.16采用頭插法建立帶有頭結(jié)點(diǎn)的雙向循環(huán)鏈表。2.4順序表與鏈表的比較線性表可以采用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)表示。在實(shí)際應(yīng)用中應(yīng)當(dāng)根據(jù)具體問(wèn)題的要求和性質(zhì)進(jìn)行選擇，通常需要考慮以下幾點(diǎn)：1．空間特性順序表的存儲(chǔ)空間是靜態(tài)分配的，在程序執(zhí)行之前必須確定它的存儲(chǔ)規(guī)模。若線性表的長(zhǎng)度變化較大，則存儲(chǔ)線性表的順序表空間長(zhǎng)度難以預(yù)先確定。估計(jì)過(guò)大將造成空間浪費(fèi)，估計(jì)過(guò)小又將使空間溢出機(jī)會(huì)增多。鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的，只要內(nèi)存還有空閑，就不會(huì)產(chǎn)生溢出。因此，當(dāng)線性表的長(zhǎng)度變化較大，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)較為適宜。此外還可以從結(jié)點(diǎn)的存儲(chǔ)密度(StorageDensity)來(lái)考慮，結(jié)點(diǎn)的存儲(chǔ)密度定義為一般地，存儲(chǔ)密度越大，存儲(chǔ)空間的利用率就越高。順序表中每個(gè)結(jié)點(diǎn)只存放數(shù)據(jù)元素，其存儲(chǔ)密度等于1；而鏈表的每個(gè)結(jié)點(diǎn)除了存放數(shù)據(jù)元素，還要存放指示元素之間邏輯關(guān)系的指針，顯然其存儲(chǔ)密度小于1。假如單鏈表結(jié)點(diǎn)的數(shù)據(jù)域類型為整型，指針?biāo)嫉目臻g與整型量相同，都是4個(gè)字節(jié)，則單鏈表的存儲(chǔ)空間利用率為50%；若不考慮順序表空間中的空閑區(qū)，則順序表的存儲(chǔ)空間利用率為100%。2．時(shí)間特性順序表是一種順序存儲(chǔ)結(jié)構(gòu)，對(duì)表中任一結(jié)點(diǎn)都可以在O(1)的時(shí)間復(fù)雜度下直接存?。欢嫒℃湵碇械哪硞€(gè)結(jié)點(diǎn)，必須從頭指針開(kāi)始沿著鏈表順序查找，時(shí)間復(fù)雜度為O(n)。在鏈表中進(jìn)行插入和刪除操作不需要移動(dòng)元素，只需修改指針的指向即可，其時(shí)間復(fù)雜度為O(1)，前插仍為O(1)；在順序表中的插入和刪除操作平均需要移動(dòng)一半的元素，時(shí)間復(fù)雜度為O(n)。作為一般規(guī)律，如果對(duì)線性表的操作以查找為主，采用順序存儲(chǔ)結(jié)構(gòu)較好；如果以插入、刪除為主，并且數(shù)據(jù)量不是很大，則采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)為宜?？傊?，線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)各有其優(yōu)缺點(diǎn)，不能籠統(tǒng)地說(shuō)哪種存儲(chǔ)結(jié)構(gòu)更好，只能根據(jù)實(shí)際問(wèn)題的需要，并對(duì)各方面的優(yōu)缺點(diǎn)加以綜合考慮，才能最終選定比較適宜的存儲(chǔ)結(jié)構(gòu)。3.1棧

3.2隊(duì)列3.1棧3.1.1棧的定義及基本運(yùn)算棧(Stack)是限定僅在表的一端進(jìn)行插入或刪除操作的線性表。插入、刪除的一端稱為棧頂(Top)，另一端稱為棧底(Bottom)。不含任何元素的空表稱為空棧。對(duì)于非空棧S?=?(a1,a2,…,an)，a1是棧底元素，an是棧頂元素。如圖3.1所示，進(jìn)棧的順序是a1,a2,…,an，出棧的順序正好相反。因此，棧是一種后進(jìn)先出的(LastInFirstOut)的線性表。棧的常用基本運(yùn)算有以下六種：(1)?InitStack(&S)棧初始化：操作結(jié)果是構(gòu)造一個(gè)空棧S。(2)?SetNull(S)置空棧：棧S已存在，將棧S清為空棧。(3)?Empty(S)判斷?？眨喝魲為空則返回“真”值；否則返回“假”值。(4)?Push(S,x)進(jìn)棧：若棧S不滿，將數(shù)據(jù)元素x插入棧頂，并返回入棧是否成功的狀態(tài)信息。入棧操作會(huì)改變棧的內(nèi)容。(5)?Pop(S,&x)出棧：若棧S非空，刪除棧頂數(shù)據(jù)元素，通過(guò)參數(shù)x帶回棧頂元素，并返回出棧是否成功的狀態(tài)信息。出棧操作會(huì)使棧的內(nèi)容發(fā)生變化。(6)?GetTop(S,&x)取棧頂元素：若棧S非空，通過(guò)參數(shù)x帶回棧頂元素，并返回取棧頂元素是否成功的狀態(tài)信息。該操作完成后，棧的內(nèi)容不變。3.1.2棧的順序存儲(chǔ)結(jié)構(gòu)和基本運(yùn)算的實(shí)現(xiàn)1．棧的順序存儲(chǔ)結(jié)構(gòu)——順序棧棧的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱順序棧(SequentialStack)。順序棧采用一維數(shù)組來(lái)存儲(chǔ)，并且用一個(gè)整型量Top指示當(dāng)前棧頂?shù)奈恢茫覀儾环涟裈op稱為棧頂指針。順序棧的類型定義如下：其中，maxsize是數(shù)組空間的長(zhǎng)度；datatype是棧中元素的類型。設(shè)S是指向SeqStack結(jié)構(gòu)體類型數(shù)據(jù)的指針。順序棧本質(zhì)上是順序表的簡(jiǎn)化，我們需要確定用數(shù)組的哪一端作為棧底。通常把數(shù)組中下標(biāo)為0的一端作為棧底，那么S->data[0]是棧底元素，S->data[S->Top]是棧頂元素。當(dāng)S->Top?=?-1時(shí)為空棧，滿棧時(shí)S->Top=maxsize-1。對(duì)于順序棧，入棧時(shí)要先判斷棧是否已滿，棧滿簡(jiǎn)稱為“上溢”；出棧時(shí)需判斷棧是否為空，?？蘸?jiǎn)稱為“下溢”。入棧操作S->Top加1，出棧操作S->Top減1。圖3.2說(shuō)明了棧中元素和棧頂指針之間的關(guān)系。2．順序?；具\(yùn)算的實(shí)現(xiàn)1)棧初始化算法3.1建立空順序棧。2)置空棧算法3.2順序棧置空。3)判斷?？账惴?.3判順序棧S是否為空棧。4)入棧算法3.4順序棧入棧。5)出棧算法3.5順序棧棧頂元素出棧。6)取棧頂元素算法3.6取順序棧的棧頂元素。3．多個(gè)順序棧共享連續(xù)空間在同時(shí)使用兩個(gè)或多個(gè)順序棧時(shí)，為了避免某個(gè)棧發(fā)生上溢，而其余棧還有很多未用空間的情況出現(xiàn)，可讓這些棧共享同一個(gè)一維數(shù)組空間，相互之間調(diào)劑余缺，既節(jié)約了存儲(chǔ)空間，又降低了發(fā)生上溢的概率。下面以兩個(gè)順序棧共享同一個(gè)數(shù)組空間的情況進(jìn)行討論。兩個(gè)棧共享一個(gè)數(shù)組空間的結(jié)構(gòu)類型定義如下：將兩個(gè)棧的棧底分別固定在一維數(shù)組空間的兩端，棧頂向中間延伸，空閑區(qū)域在數(shù)組的中部，如圖3.3所示。只有當(dāng)兩個(gè)棧占滿整個(gè)數(shù)組空間時(shí)(S->Top1+1等于S->Top2)，才會(huì)發(fā)生上溢。設(shè)i表示整型數(shù)值，它只取1或者2，分別表示對(duì)1號(hào)?；蛘?號(hào)棧進(jìn)行操作。這里我們只給出兩個(gè)棧共享空間的入棧和出棧操作。進(jìn)棧操作的算法如下所示：當(dāng)存儲(chǔ)棧的數(shù)組中沒(méi)有空閑單元時(shí)為棧滿。此時(shí)1號(hào)棧的棧頂與2號(hào)棧的棧頂處于相鄰的位置，即Top1+1?=?Top2(或Top1?=?Top2-1)。另外，對(duì)于2號(hào)棧的入棧，Top2應(yīng)當(dāng)是減1而不是加1。出棧操作的算法如下所示：當(dāng)Top1=-1時(shí)，1號(hào)棧為空；當(dāng)Top2=maxsize時(shí)，2號(hào)棧為空。另外，對(duì)于2號(hào)棧的出棧，Top2應(yīng)當(dāng)是加1而不是減1。3.1.3棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和基本運(yùn)算的實(shí)現(xiàn)1.棧的鏈接存儲(chǔ)結(jié)構(gòu)——鏈棧棧的鏈接存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱鏈棧(LinkedStack)，通常用單鏈表表示。鏈棧的結(jié)點(diǎn)結(jié)構(gòu)類型定義如下：由于鏈棧是動(dòng)態(tài)分配元素存儲(chǔ)空間的，因此在對(duì)棧進(jìn)行操作時(shí)不存在上溢的問(wèn)題。我們將單鏈表的表頭定義為棧頂。由于只能在棧頂進(jìn)行入棧和出棧操作，因此只能在表頭插入和刪除，可以說(shuō)鏈棧是操作受限的單鏈表。既然只能在表頭進(jìn)行操作，所以也就沒(méi)有必要設(shè)置頭結(jié)點(diǎn)了。如圖3.5所示，S是LinkStack類型的指針，指向鏈棧，可以看作是棧的接口。Top是棧頂指針，指向棧頂結(jié)點(diǎn)。當(dāng)Top等于NULL時(shí)為空棧。2．鏈?；具\(yùn)算的實(shí)現(xiàn)鏈?；具\(yùn)算的實(shí)現(xiàn)實(shí)質(zhì)上是單鏈表基本運(yùn)算的簡(jiǎn)化。由于對(duì)棧的操作都是在棧頂(單鏈表的表頭)進(jìn)行的，因此算法的時(shí)間復(fù)雜度均為O(1)。1)棧初始化算法3.7建立空鏈棧。2)置空棧算法3.8鏈棧置空。3)入棧算法3.9鏈棧入棧。4)出棧算法3.10鏈棧棧頂元素出棧。5)取棧頂元素算法3.11取鏈棧的棧頂元素。3.1.4順序棧和鏈棧的比較從時(shí)間特性方面來(lái)看，實(shí)現(xiàn)順序棧和鏈棧的所有基本運(yùn)算的算法，其時(shí)間復(fù)雜度都是O(1)，因此唯一可以比較的是空間特性。棧初始化時(shí)，順序棧必須確定一個(gè)固定的長(zhǎng)度作為棧的容量，所以有存儲(chǔ)元素個(gè)數(shù)的限制和空間浪費(fèi)的問(wèn)題。鏈棧沒(méi)有棧滿的問(wèn)題，只有當(dāng)內(nèi)存沒(méi)有可用空間時(shí)才會(huì)出現(xiàn)不能入棧的情況，但是每個(gè)元素都需要一個(gè)指針域，從而又產(chǎn)生了結(jié)構(gòu)性的開(kāi)銷。所以當(dāng)棧的使用過(guò)程中元素個(gè)數(shù)變化較大時(shí)，用鏈棧是適宜的；反之，應(yīng)該采用順序棧。3.2隊(duì)列3.2.1隊(duì)列的定義及基本運(yùn)算隊(duì)列(Queue)也是一種運(yùn)算受限的線性表。它只允許在表的一端進(jìn)行插入，該端稱為隊(duì)尾(Rear)；在表的另一端進(jìn)行刪除，該端稱為隊(duì)頭(Front)。當(dāng)隊(duì)列中沒(méi)有元素時(shí)稱為空隊(duì)列。隊(duì)列亦稱作先進(jìn)先出(FirstInFirstOut)的線性表，簡(jiǎn)稱為FIFO表。設(shè)隊(duì)列中的元素為a1,a2,…,an，a1是隊(duì)頭元素，an是隊(duì)尾元素。隊(duì)列中的元素都是按照a1,a2,…,an的順序依次入隊(duì)和出隊(duì)的。圖3.6是隊(duì)列的示意圖。隊(duì)列的主要基本運(yùn)算如下：(1)?InitQueue(&Q)隊(duì)列初始化：構(gòu)造一個(gè)空隊(duì)列Q。(2)?SetNull(Q)置空隊(duì)：將隊(duì)列Q清空。(3)?Length(Q)求隊(duì)列長(zhǎng)度：返回隊(duì)列中元素的個(gè)數(shù)。(4)?Empty(Q)判空隊(duì)：若隊(duì)列Q為空隊(duì)列，返回“真”值；否則返回“假”值。(5)?EnQueue(Q,x)入隊(duì)：若隊(duì)列Q非滿，將元素x插入Q的隊(duì)尾。(6)?DeQueue(Q)出隊(duì)：若隊(duì)列Q非空，刪除隊(duì)頭元素，返回Q的隊(duì)頭元素。(7)?GetFront(Q)取隊(duì)頭元素：若隊(duì)列Q非空，返回Q的隊(duì)頭元素；Q中元素保持不變。3.2.2隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和基本運(yùn)算的實(shí)現(xiàn)1．隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)——順序隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列，采用數(shù)組存儲(chǔ)隊(duì)列中的元素。本書(shū)約定，在非空隊(duì)列中隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針rear指向隊(duì)尾元素的位置。如果是空隊(duì)，隊(duì)頭、隊(duì)尾指針相等。隊(duì)尾指針減去隊(duì)頭指針就是隊(duì)列的長(zhǎng)度。當(dāng)然也可以約定隊(duì)頭指針front指向隊(duì)頭元素的位置，隊(duì)尾指針rear指向隊(duì)尾元素的后一個(gè)位置。順序隊(duì)列的結(jié)構(gòu)類型定義如下：順序隊(duì)列中出隊(duì)、入隊(duì)操作的情況如圖3.7所示。順序隊(duì)列中可能出現(xiàn)“上溢”和“下溢”現(xiàn)象，并且還存在“假上溢”現(xiàn)象。也就是說(shuō)，盡管隊(duì)列的數(shù)組空間雖然未被占滿，但尾指針已達(dá)到數(shù)組的上界而不能進(jìn)行入隊(duì)操作。例如在圖3.7(c)或(d)的情況下，再進(jìn)行入隊(duì)操作，則會(huì)出現(xiàn)“假上溢”。采用循環(huán)隊(duì)列(CircularQueue)的方法可以較好地解決“假上溢”問(wèn)題，即將數(shù)組看作一個(gè)首尾相接的圓環(huán)，如圖3.8所示。在循環(huán)隊(duì)中通過(guò)取模運(yùn)算修改隊(duì)尾指針和隊(duì)頭指針，具體描述為：在循環(huán)隊(duì)列中，入隊(duì)時(shí)尾指針向前追趕頭指針，出隊(duì)時(shí)頭指針向前追趕尾指針。由圖3.9可以看出，在隊(duì)空和隊(duì)滿時(shí)都有sq->front等于sq->rear，無(wú)法區(qū)分空隊(duì)和滿隊(duì)。通常采用少用一個(gè)元素空間的方法來(lái)解決這個(gè)問(wèn)題，如圖3.10所示。判斷空隊(duì)和滿隊(duì)的條件分別是：2．循環(huán)隊(duì)列基本運(yùn)算的實(shí)現(xiàn)我們用前面所述方法來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列上的基本運(yùn)算。1)隊(duì)列初始化算法3.12生成空循環(huán)隊(duì)列。對(duì)于循環(huán)隊(duì)列來(lái)說(shuō)，只要隊(duì)頭和隊(duì)尾指針相等即為空隊(duì)，所以這里置為0～maxsize-1之間的任何一個(gè)值都可以，但一般置為0。2)置空隊(duì)算法3.13循環(huán)隊(duì)列置空。3)求隊(duì)列長(zhǎng)度算法3.14求循環(huán)隊(duì)列長(zhǎng)度。4)入隊(duì)算法3.15循環(huán)隊(duì)列入隊(duì)。5)出隊(duì)算法3.16循環(huán)隊(duì)列出隊(duì)。6)取隊(duì)頭元素算法3.17取循環(huán)隊(duì)列的隊(duì)頭元素。3.2.3隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和基本運(yùn)算的實(shí)現(xiàn)1．隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——鏈隊(duì)列隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱鏈隊(duì)列，它是僅限在表頭刪除和表尾插入的單鏈表。為了便于在表尾做插入操作，需要增加一個(gè)尾指針，指向單鏈表中的最后一個(gè)結(jié)點(diǎn)。我們將鏈隊(duì)列的頭指針和尾指針?lè)庋b在一起作為一個(gè)結(jié)構(gòu)體。下面是其類型定義：為了運(yùn)算方便，鏈隊(duì)列中通常也帶有頭結(jié)點(diǎn)。圖3.11給出了鏈隊(duì)列的示意圖，圖中q為L(zhǎng)inkQueue類型的指針。鏈隊(duì)列不會(huì)出現(xiàn)隊(duì)滿的情況。2．鏈隊(duì)列基本運(yùn)算的實(shí)現(xiàn)1)隊(duì)列初始化算法3.18生成空鏈隊(duì)列。2)置空隊(duì)算法3.19鏈隊(duì)列置空。3)判隊(duì)空算法3.20鏈隊(duì)列判空隊(duì)。4)入隊(duì)算法3.21鏈隊(duì)列入隊(duì)。鏈隊(duì)列不會(huì)出現(xiàn)“上溢”的情況，不需要判斷隊(duì)滿。5)出隊(duì)算法3.22鏈隊(duì)列出隊(duì)。6)取隊(duì)頭元素算法3.23取鏈隊(duì)列的隊(duì)頭元素。4.1串的概念及基本運(yùn)算

4.2串的順序存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)

4.3串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

4.4串的模式匹配算法4.1串的概念及基本運(yùn)算4.1.1串的定義串(String)是由多個(gè)或零個(gè)字符組成的有限序列，記作S?=?"c1c2c3…cn"(n≥0)。其中，S是串名，由雙引號(hào)括起來(lái)的字符序列稱為串值，但雙引號(hào)本身不屬于串；ci(1≤i≤n)是串中的字符，i是字符在串中的位置序號(hào)；n是串的長(zhǎng)度，表示串中字符的個(gè)數(shù)。不包含任何字符的串稱為空串，例如""是長(zhǎng)度為0的空串。串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。子串在主串中的序號(hào)定義為子串在主串中首次出現(xiàn)的位置序號(hào)。例如，設(shè)S1和S2分別為，S1?=?"Thisisastring"?和S2?=?"is"，則S2是S1的子串，S1是S2的主串。S2在S1中出現(xiàn)了兩次，首次出現(xiàn)在主串的第3個(gè)位置上，因此S2在S1中的序號(hào)是3。特別需要一提的是，空串是任意串的子串，任意串是其自身的子串。通常串可以分為串變量和串常量。正如我們所知道的，在程序中常量只能被引用但不能改變其值，而變量的值可以改變。在C語(yǔ)言中，串變量可以用字符型數(shù)組來(lái)表示，串常量可以用雙引號(hào)括起來(lái)的字符序列直接表示或者用符號(hào)常量來(lái)表示。4.1.2串的基本運(yùn)算串的基本運(yùn)算和線性表有很大的差別。線性表的插入、刪除等運(yùn)算都以“單個(gè)元素”作為操作對(duì)象；而串的運(yùn)算通常是對(duì)串的整體或一部分進(jìn)行操作，如串的復(fù)制、串的比較、插入和刪除子串等。下面介紹串的部分基本運(yùn)算。(1)?StrLength(S)求串長(zhǎng)：計(jì)算并返回串的長(zhǎng)度。(2)?StrCopy(S1,S2)串賦值：將S2賦給S1。S1是串變量，S2是串常量或者是串變量。(3)?StrCat(S1,S2)串連接：將S2連接在S1的后面。S1是串變量，S2是串常量或者是串變量。(4)?StrCmp(S1,S2)串比較：若S1?=?S2，則運(yùn)算結(jié)果為0；若S1?>?S2，則運(yùn)算結(jié)果大于0；若S1?<?S2，則運(yùn)算結(jié)果小于0。兩個(gè)串的比較，實(shí)際上比較的是字符的ASCII碼值。從第一個(gè)位置上的字符開(kāi)始逐個(gè)字符進(jìn)行比較，當(dāng)?shù)谝淮纬霈F(xiàn)字符不等的情況時(shí)，即可得到比較的結(jié)果。(5)?StrIndex(S,T)子串定位：若串T是串S的子串，則運(yùn)算結(jié)果為T在S中首次出現(xiàn)的位置，否則運(yùn)算結(jié)果為0。(6)?SubStr(Sub,S,i,len)求子串：串S非空，且1≤i≤StrLength(S)，0≤len≤StrLength(S)，運(yùn)算結(jié)果是得到S串從第i個(gè)字符開(kāi)始的長(zhǎng)度為len的子串，并將其賦給T。如果len為0，則賦給Sub的是空串。(7)?StrInsert(S,i,T)串插入：串S和T均為非空串，且1≤i≤StrLength(S)+1。結(jié)果是將串T插入到串S的第i個(gè)字符位置上，串S的值被改變。(8)?Strdelete(S,i,len)串刪除：串S非空，且1≤i≤StrLength(S)，0≤len≤StrLength(S)，運(yùn)算結(jié)果是刪除S串中從第i個(gè)字符開(kāi)始的長(zhǎng)度為len的子串，串S的值被改變。(9)?StrRep(S,T,R)串替換：串S、T、R均非空，運(yùn)算結(jié)果是用串R替換串S中所有子串T，串S的值被改變。以上是串的基本運(yùn)算，其中前5個(gè)運(yùn)算是最基本的，其余的串運(yùn)算一般可以由這些最基本的串運(yùn)算組合而成。4.2串的順序存儲(chǔ)結(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)4.2.1串的順序存儲(chǔ)結(jié)構(gòu)串的順序存儲(chǔ)結(jié)構(gòu)又稱為順序串。與線性表的順序存儲(chǔ)結(jié)構(gòu)類似，順序串用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列，其中每個(gè)結(jié)點(diǎn)是單個(gè)字符。串的定長(zhǎng)順序存儲(chǔ)表示也稱為靜態(tài)存儲(chǔ)分配的順序串。定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)是指直接使用定長(zhǎng)的字符數(shù)組來(lái)定義，數(shù)組的上界預(yù)先給出。串的長(zhǎng)度一般有三種表示方法：(1)用一個(gè)整型變量來(lái)表示串的長(zhǎng)度，如圖4.1所示。此時(shí)順序串的類型定義和順序表類似，定義如下：在這種存儲(chǔ)方式下，可以直接得到順序串的長(zhǎng)度為s->length。(2)在串的末尾設(shè)置串結(jié)束符。在有些編程語(yǔ)言中，采用特定的終結(jié)符表示串的結(jié)束，例如C語(yǔ)言用轉(zhuǎn)義字符?'\0'?作為串結(jié)束符，如圖4.2所示。?這種方式不能直接得到串的長(zhǎng)度，而是通過(guò)判斷當(dāng)前字符是否為?'\0'?來(lái)確定串是否結(jié)束，從而求得串的長(zhǎng)度。此時(shí)，順序串的定義如下：這就是為什么在上述定義中，串空間最大值maxstrlen為256，但最多只能存放255個(gè)字符的原因，因?yàn)楸仨毩粢粋€(gè)字節(jié)來(lái)存放?'\0'?字符作為串結(jié)束符。(3)設(shè)置順序串存儲(chǔ)空間：chars[maxsize+1];?，用s[0]存放串的實(shí)際長(zhǎng)度，而串值存放在s[1]～s[maxsize]中，如圖4.3所示。這樣可以使得字符的序號(hào)與存儲(chǔ)位置的下標(biāo)一致。在下面關(guān)于順序串的討論中，為了和C語(yǔ)言的字符串運(yùn)算保持一致，順序串采用第2種存儲(chǔ)方式，即從數(shù)組下標(biāo)0開(kāi)始存放字符，并且在串尾存儲(chǔ)串結(jié)束符?'\0'。4.2.2順序串基本運(yùn)算的實(shí)現(xiàn)1．順序串的基本運(yùn)算1)求串長(zhǎng)算法4.1求順序串的長(zhǎng)度，即統(tǒng)計(jì)串中字符的個(gè)數(shù)。2)串賦值(串復(fù)制)算法4.2將串s2復(fù)制給串s1。3)串比較算法4.3比較兩個(gè)串s1和s2的大小。若s1>s2，返回值大于0；若s1=s2，返回值等于0；若s1<s2，返回值小于0。4)串連接算法4.4將s1和s2兩個(gè)串首尾連接成一個(gè)新的串s1。2．使用C語(yǔ)言的字符串運(yùn)算庫(kù)函數(shù)使用C語(yǔ)言的字符串運(yùn)算庫(kù)函數(shù)，需要包含頭文件string.h，庫(kù)函數(shù)名均為小寫(xiě)。我們先定義使用的幾個(gè)相關(guān)變量：說(shuō)明：字符串從字符數(shù)組下標(biāo)為0的元素開(kāi)始存放。(1)?strlen(S)求串長(zhǎng)度：返回字符串長(zhǎng)度。(2)?strcpy(&T,S)復(fù)制串：將源串復(fù)制給目標(biāo)串。(3)?strcmp(S1,S2)比較串：比較兩個(gè)串的大小，返回整型值。(4)?strcat(&T,S)串連接：將串S連接到串T的末尾，返回指向串T的指針。(5)?strstr(S,Sub)子串定位：查找串Sub在串S中第一次出現(xiàn)的位置。若查找到，則返回該位置信息，否則返回NULL。(6)?strchr(S,C)字符定位：查找字符C在串S中第一次出現(xiàn)的位置。若查找到，則返回該位置信息，否則返回NULL。在串的順序存儲(chǔ)結(jié)構(gòu)中，串操作的時(shí)間復(fù)雜度基于串的長(zhǎng)度n，即時(shí)間復(fù)雜度為O(n)。上述操作的另一個(gè)特點(diǎn)是，當(dāng)在操作中出現(xiàn)串值序列的長(zhǎng)度超過(guò)上界maxsize時(shí)，約定用截尾法處理，這種情況不僅在連接串時(shí)可能發(fā)生，在串的插入等其他操作也可能發(fā)生。這個(gè)弊病可以采用動(dòng)態(tài)分配串的存儲(chǔ)空間的方式來(lái)克服。4.3串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和順序表類似，在順序串上進(jìn)行插入、刪除操作不方便，需要移動(dòng)大量的元素。采用鏈表存儲(chǔ)串值可以提高插入、刪除的效率。串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈串。鏈串便于進(jìn)行插入和刪除運(yùn)算，但存儲(chǔ)空間利用率太低。由于串中的每個(gè)元素是一個(gè)字符，因此用鏈表存儲(chǔ)串值時(shí)存在結(jié)點(diǎn)大小的問(wèn)題。也就是說(shuō)，在每個(gè)結(jié)點(diǎn)存放一個(gè)字符還是存放多個(gè)字符。圖4.4(a)和(b)中每個(gè)結(jié)點(diǎn)分別可以存放1個(gè)字符和4個(gè)字符。如果每個(gè)結(jié)點(diǎn)放多個(gè)字符，當(dāng)串長(zhǎng)不是結(jié)點(diǎn)大小的整數(shù)倍時(shí)，鏈表中的最后一個(gè)結(jié)點(diǎn)不一定被串值完全占滿，可以用特殊的字符(例如?'\0'或?'#'?)來(lái)填充。為了方便串的操作，當(dāng)以鏈表存儲(chǔ)串值時(shí)，除頭指針外，還可以附設(shè)一個(gè)尾指針指向鏈表中的最后一個(gè)結(jié)點(diǎn)，并給出當(dāng)前串的長(zhǎng)度。這樣定義的優(yōu)點(diǎn)是便于進(jìn)行連接操作，并且對(duì)于涉及串長(zhǎng)的操作時(shí)速度較快。圖4.4(b)是結(jié)點(diǎn)大小為4的鏈串示意圖，其類型定義如下：在該存儲(chǔ)方式下，結(jié)點(diǎn)大小的選擇非常重要，它會(huì)影響處理的效率。定義串的存儲(chǔ)密度為串值的存儲(chǔ)位與實(shí)際分配存儲(chǔ)位的比值。當(dāng)存儲(chǔ)密度小時(shí)，運(yùn)算處理方便，但是占用的存儲(chǔ)空間大；而當(dāng)存儲(chǔ)密度大時(shí)，占用的空間小，但是運(yùn)算量大。若鏈串中的每個(gè)結(jié)點(diǎn)存放一個(gè)字符，結(jié)點(diǎn)的指針域占4個(gè)字節(jié)，那么鏈串的存儲(chǔ)密度只有20%；如果每個(gè)結(jié)點(diǎn)存放多個(gè)字符，例如4個(gè)字符，則存儲(chǔ)密度可以達(dá)到50%，有效地提高了存儲(chǔ)空間的利用率。在大多數(shù)情況下，對(duì)串進(jìn)行操作時(shí)，只需要像單鏈表一樣按從頭到尾的順序掃描即可。對(duì)于結(jié)點(diǎn)大小大于1的情況，需要注意串尾的無(wú)效字符。4.4串的模式匹配算法子串定位又稱為串的模式匹配(PatternMatching)，是串運(yùn)算中最重要的操作之一。將主串稱為目標(biāo)串(TargetString)，子串稱為模式串(PatternString)，所謂模式匹配，就是在目標(biāo)串中查找模式串的出現(xiàn)位置，例如在文本中查找是否存在給定的單詞及出現(xiàn)的位置。串的模式匹配算法分為簡(jiǎn)單的模式匹配算法和改進(jìn)的模式匹配算法兩種。4.4.1簡(jiǎn)單的模式匹配算法簡(jiǎn)單的模式匹配算法又稱為窮舉的模式匹配算法或是樸素的模式匹配算法，也稱為Brute-Force算法，簡(jiǎn)稱BF算法。假設(shè)T為目標(biāo)串(主串)，P為模式串(子串)，則有其中，0＜m≤n。在實(shí)際應(yīng)用中，模式串長(zhǎng)度m通常遠(yuǎn)遠(yuǎn)小于目標(biāo)串長(zhǎng)度n，即m<<n。下面給出采用順序串結(jié)構(gòu)時(shí)，不依賴其他串運(yùn)算的簡(jiǎn)單的模式匹配算法。算法4.5順序串簡(jiǎn)單的模式匹配。分別利用計(jì)數(shù)指針i和j指示目標(biāo)串T和模式串P中當(dāng)前比較的字符位序。算法的基本思想是：從目標(biāo)串T的第pos個(gè)字符開(kāi)始與模式串P的第一個(gè)字符進(jìn)行比較，若相等，則繼續(xù)比較后面的字符；否則從目標(biāo)串的下一個(gè)字符開(kāi)始與模式串的第一個(gè)字符進(jìn)行下一趟比較。重復(fù)此過(guò)程，直至模式串中的每個(gè)字符依次與目標(biāo)串中的一個(gè)連續(xù)的字符序列相等，則匹配成功，函數(shù)值為與模式串中第一個(gè)字符相等的字符在目標(biāo)串中的位序；如果各趟比較均不相等，則匹配不成功，函數(shù)返回值為0。如果在匹配過(guò)程中出現(xiàn)ti?≠?pj的情況，即本趟匹配失敗，那么下一趟匹配應(yīng)該使指針j等于1(即指向p1)，而指針i則等于i-j+2(即指向ti-j+2)。這樣，指針i必須由當(dāng)前位置i回溯到i-j+2的位置上。圖4.6給出了模式串P?=?"abc"?與目標(biāo)串T?=?"abbabca"?的簡(jiǎn)單的模式匹配過(guò)程(pos=1)。下面我們?cè)賮?lái)討論以結(jié)點(diǎn)大小為1的單鏈表存儲(chǔ)串實(shí)現(xiàn)簡(jiǎn)單的模式匹配算法。在算法中使用指針shift指向每一趟在目標(biāo)串中比較的起始位置，若一趟比較中出現(xiàn)不相等的字符，則指針shift右移指向下一個(gè)結(jié)點(diǎn)，繼續(xù)下一趟的比較。匹配成功，返回shift所指向的結(jié)點(diǎn)地址；匹配不成功，返回空地址值。具體算法如下：算法4.6鏈串簡(jiǎn)單的模式匹配。簡(jiǎn)單的模式匹配算法雖然簡(jiǎn)單，但效率較低，這是因?yàn)樵谝惶似ヅ渲校繕?biāo)串內(nèi)可能存在多個(gè)和模式串“部分匹配”的子串，而引起計(jì)數(shù)指針的多次回溯。特別地，在某些情況下，該算法的效率很低。在最壞情況下，每一趟不成功的匹配都發(fā)生在模式串P的最后一個(gè)字符與主串T中相應(yīng)字符的比較時(shí)，則在主串T中新一趟比較的起始位置為i-m+1。若第i趟匹配成功，則前i-1趟不成功的匹配中每趟都比較了m次，而第i趟成功的匹配也比較了m次。所不同的是，前i-1趟均是在第m次比較時(shí)不匹配，而第i趟的m次比較都成功匹配。所以，第i趟成功匹配共進(jìn)行了i?×?m次比較。因此，在最壞情況下，匹配成功的比較次數(shù)為其中，qi為匹配成功的等概率。由于n>>m，故最壞情況下BF算法的時(shí)間復(fù)雜度為O(n?×?m)。4.4.2改進(jìn)的模式匹配算法BF算法雖然簡(jiǎn)單，但由于帶有回溯而效率低。KMP算法是一種改進(jìn)的模式匹配算法，由D.E.Knuth、J.H.Morris和V.R.Pratt同時(shí)發(fā)現(xiàn)，因此人們稱它為克努特-莫里斯-普拉特操作，簡(jiǎn)稱KMP算法。KMP算法的關(guān)鍵是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)，以達(dá)到快速匹配的目的。1．KMP算法的基本思想BF算法的目標(biāo)串存在回溯，目標(biāo)串T與模式串P逐個(gè)比較字符，若T[i]?≠?P[j](0≤i＜n，0≤j＜m)，則下趟匹配目標(biāo)串從T[i]退回到T[i-j+1]開(kāi)始與模式串P[0]比較。實(shí)際上，這種丟棄前面匹配信息的方法極大地降低了匹配效率。目標(biāo)串的回溯是不必要的，T[i-j+1]與P[0]的比較結(jié)果可由前一趟匹配結(jié)果得到。我們以主串(目標(biāo)串)T?=?"abcabb"、模式串P?=?"abb"，或者主串(目標(biāo)串)T="aacaab"、模式串P?=?"aab"?為例進(jìn)行分析。如圖4.7所示，第1趟匹配，有T[0]?=?P[0]，T[1]?=?P[1]，T[2]?≠?P[2]。①若P[1]?≠?P[0]，則T[1]?≠?P[0]，下趟匹配從T[2]與P[0]開(kāi)始比較；②若P[1]?=?P[0]，則T[1]?=?P[0]，下趟匹配從T[2]與P[1]開(kāi)始比較?？傊?，當(dāng)T[2]?≠?P[2]時(shí)，無(wú)論P(yáng)[1]與P[0]是否相同，下趟匹配都從T[2]開(kāi)始比較，即目標(biāo)串不回溯；而模式串要根據(jù)P[1]與P[0]是否相同，確定從P[0]或P[1]開(kāi)始比較。KMP算法的基本思想是主串不回溯。如果希望某趟在T[i]和P[j]匹配失敗后，下標(biāo)i不回溯，下標(biāo)j回溯至某個(gè)位置k，使得P[k]對(duì)準(zhǔn)T[i]繼續(xù)進(jìn)行比較，那么關(guān)鍵的問(wèn)題是如何確定位置k。模式串T中的每一個(gè)字符T[j]都對(duì)應(yīng)一個(gè)k值，這個(gè)k值僅依賴于模式串本身字符序列的構(gòu)成，與主串P無(wú)關(guān)。對(duì)于每一個(gè)模式串，我們可以事先計(jì)算出模式串的內(nèi)部匹配信息，在匹配失敗時(shí)最大移動(dòng)模式串，以減少匹配次數(shù)。2．next數(shù)組定義用next數(shù)組元素next[j]表示P[j]對(duì)應(yīng)的k值(0≤j<m)，根據(jù)上述分析，其定義如下：當(dāng)j?=?0時(shí)，若T[i]?≠?P[0]，接著從T[i+1]?與P[0]?開(kāi)始比較，取k?=?-1。對(duì)模式串中某些字符P[j]，當(dāng)?"p0…pj-1"?串中有多個(gè)相同的前綴和后綴子串時(shí)，k取較大值。例如，P?=?"aaab"，若j=3，"aaa"?中相同的前綴子串和后綴子串有?"a"?和?"aa"，長(zhǎng)度分別為1和2，即當(dāng)t[i]?≠?P[3]時(shí)，T[i]?可與P[1]?或P[2]?繼續(xù)比較，k取較大值2。模式串P?=?"abcabc"?的next數(shù)組元素值如表4.1所示。3．KMP算法的偽代碼KMP算法的時(shí)間復(fù)雜度是O(n+m)。與BF算法相比，增加了很大難度。我們先給出KMP算法和計(jì)算next數(shù)組算法的偽代碼，這樣有助于對(duì)算法的理解。KMP算法用偽代碼描述如下：計(jì)算next數(shù)組值的算法用偽代碼描述如下：算法4.7KMP算法，用函數(shù)Index_KMP來(lái)實(shí)現(xiàn)。算法4.8利用函數(shù)Get_Next計(jì)算next數(shù)組值的算法。5.1數(shù)組

5.2特殊矩陣的壓縮存儲(chǔ)

5.3稀疏矩陣的壓縮存儲(chǔ)

5.4廣義表5.1數(shù)組5.1.1數(shù)組的基本概念數(shù)組中各元素具有相同的類型，數(shù)組元素具有值和確定元素位置的下標(biāo)。通常可以把一維數(shù)組稱為向量，多維數(shù)組是向量的擴(kuò)充。由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界。因此，數(shù)組的處理比其他復(fù)雜的結(jié)構(gòu)更為簡(jiǎn)單。一維數(shù)組可表示為An?=?[a1，a2，…，an]，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)一個(gè)數(shù)組下標(biāo)，它具有線性表的結(jié)構(gòu)，即除了第一個(gè)元素和最后一個(gè)元素，每個(gè)元素存在一個(gè)直接前驅(qū)元素和一個(gè)直接后繼元素。二維數(shù)組可表示為3在二維數(shù)組中，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)一對(duì)數(shù)組下標(biāo)，在行方向上和列方向上都存在一個(gè)線性關(guān)系，即存在兩個(gè)前驅(qū)(前件)和兩個(gè)后繼(后件)；也可看作是以線性表為數(shù)據(jù)元素的線性表。也就是說(shuō)，一個(gè)m行n列的二維數(shù)組，可以看成由m個(gè)長(zhǎng)度為n的一維數(shù)組(行)所組成的線性表，也可以看成n個(gè)長(zhǎng)度為m的一維數(shù)組(列)所組成的線性表，即在n維數(shù)組中，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)n個(gè)下標(biāo)，受n個(gè)關(guān)系的制約，其中任一個(gè)關(guān)系都是線性關(guān)系。它可看作是數(shù)據(jù)元素為n-1維數(shù)組的一維數(shù)組。多維數(shù)組是對(duì)線性表的擴(kuò)展，線性表中的數(shù)據(jù)元素本身又是一個(gè)多層次的線性表。5.1.2數(shù)組的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中一般采用順序存儲(chǔ)結(jié)構(gòu)來(lái)存放數(shù)組。而內(nèi)存結(jié)構(gòu)是一維的，因此存放二維數(shù)組或多維數(shù)組，就必須按照某種順序?qū)?shù)組中的元素形成一個(gè)線性序列，然后將這個(gè)線性序列存放在內(nèi)存中。下面討論二維數(shù)組的存儲(chǔ)方式。1)行優(yōu)先順序存儲(chǔ)將數(shù)組元素按行向量的順序存儲(chǔ)，即第i+1行的元素存放在第i行的元素之后。元素存儲(chǔ)的線性序列為2)列優(yōu)先順序存儲(chǔ)將數(shù)組元素按列向量的順序存儲(chǔ)，即第j+1列的元素存放在第j列的元素之后。元素存儲(chǔ)的線性序列為在多數(shù)計(jì)算機(jī)語(yǔ)言中，二維數(shù)組都是按行優(yōu)先的順序存儲(chǔ)的，少數(shù)語(yǔ)言采用按列優(yōu)先的順序存儲(chǔ)。按照上述兩種存儲(chǔ)二維數(shù)組的線性序列，若已知數(shù)組存儲(chǔ)的起始地址，下標(biāo)的上、下界，以及每個(gè)數(shù)組元素所占用的存儲(chǔ)單元個(gè)數(shù)，就可以計(jì)算出元素aij的存儲(chǔ)地址，從而對(duì)數(shù)組元素隨機(jī)存取。例如，二維數(shù)組A[c1..d1,c2..d2]?按行優(yōu)先的順序存儲(chǔ)在內(nèi)存中，假設(shè)每個(gè)元素占d個(gè)存儲(chǔ)單元，計(jì)算元素aij的地址公式為其中Loc(ac1c2)是數(shù)組的起始地址；元素aij前面的i-c1行中共有(i-c1)?×?(d2-c2+1)個(gè)元素，第i行上元素aij前面又有j-c2個(gè)元素。類似地，我們可以得出當(dāng)二維數(shù)組A[c1…d1，c2…d2]按列優(yōu)先的順序存儲(chǔ)在內(nèi)存中時(shí)，元素aij的地址計(jì)算公式為5.2特殊矩陣的壓縮存儲(chǔ)5.2.1三角矩陣在n階方陣中，以主對(duì)角線進(jìn)行劃分，如果矩陣的下三角(不包括主對(duì)角線)中的元素均為值相同的常數(shù)，則稱為上三角矩陣；反之稱為下三角矩陣。在多數(shù)情況下，三角矩陣的常數(shù)為零。這兩種三角矩陣如圖5.1所示。為簡(jiǎn)便起見(jiàn)，可以用向量A[0…n(n+1)/2]壓縮存儲(chǔ)三角矩陣，其中A[0]～A[n(n+1)/2-1]存儲(chǔ)矩陣下(上)三角中的元素，向量的最后一個(gè)分量A[n(n+1)/2]存儲(chǔ)三角矩陣中的常數(shù)。下三角矩陣按行優(yōu)先的順序存儲(chǔ)，A[k]與aij的對(duì)應(yīng)關(guān)系為上三角矩陣按列優(yōu)先的順序存儲(chǔ)，A[k]與aij的對(duì)應(yīng)關(guān)系為5.2.2對(duì)稱矩陣若n階方陣A中的元素關(guān)于主對(duì)角線對(duì)稱，即滿足下述性質(zhì)：則稱A為對(duì)稱矩陣。如果采用一維數(shù)組存儲(chǔ)矩陣中的上三角或下三角元素，使對(duì)稱的兩個(gè)元素共享同一個(gè)存儲(chǔ)空間，可以節(jié)省近一半的存儲(chǔ)空間。存儲(chǔ)n階對(duì)稱方陣時(shí)，一維數(shù)組的長(zhǎng)度為n(n+1)/2。同樣，可以用向量A[0…n(n+1)/2-1]壓縮存儲(chǔ)對(duì)稱矩陣。下三角矩陣按行優(yōu)先的順序存儲(chǔ)，A[k]與aij的對(duì)應(yīng)關(guān)系為對(duì)于上三角矩陣中的元素aij(i<j)，因?yàn)閍ij?=?aji，相當(dāng)于按列優(yōu)先的順序存儲(chǔ)，所以A[k]與aij的對(duì)應(yīng)關(guān)系為對(duì)于任意給定一組下標(biāo)(i，j)，均可在A[n(n+1)/2]中找到矩陣元素aij；反之，對(duì)所有的k?=?0，1，2…，

，都能確定元素A[k]在矩陣中的位置(i，j)。由此，稱A[n(n+1)/2]為n階對(duì)稱矩陣A的壓縮存儲(chǔ)，見(jiàn)圖5.2。圖5.3給出了一個(gè)4階對(duì)稱方陣，按行優(yōu)先的順序存儲(chǔ)下三角矩陣，按列優(yōu)先的順序存儲(chǔ)上三角矩陣。圖5.4是其存儲(chǔ)形式。5.2.3對(duì)角矩陣所謂對(duì)角矩陣，是指方陣中的所有非零元素集中在以主對(duì)角線為中心的帶狀區(qū)域內(nèi)，帶狀區(qū)域之外的元素值均為零。帶寬為3的對(duì)角矩陣又稱為三對(duì)角矩陣，如圖5.5所示。顯然，當(dāng)?|i-j|?>?1時(shí)，元素aij為0。一般地，對(duì)于k對(duì)角矩陣(k為奇數(shù))，當(dāng)?|i-j|?>?(k-1)/2時(shí)，元素aij為0。n階三對(duì)角矩陣有3n-2個(gè)非零元素，采用向量A[0…3n-3]按行優(yōu)先的順序壓縮存儲(chǔ)三對(duì)角矩陣。每個(gè)非零元素與向量下標(biāo)的對(duì)應(yīng)關(guān)系為上述各種特殊矩陣的非零元素的分布都具有一定的規(guī)律，采用向量壓縮存儲(chǔ)，通過(guò)元素與向量的對(duì)應(yīng)關(guān)系，仍然可以對(duì)矩陣中的元素進(jìn)行隨機(jī)存取。5.3稀疏矩陣的壓縮存儲(chǔ)5.3.1稀疏矩陣的三元組表存儲(chǔ)將稀疏矩陣中的非零元素的行號(hào)、列號(hào)和元素值作為一個(gè)三元組(i,j,aij)，所有非零元素的三元組按行優(yōu)先(或列優(yōu)先)的順序排列，便得到一個(gè)結(jié)點(diǎn)均是三元組的線性表。我們將該線性表的順序存儲(chǔ)結(jié)構(gòu)稱為三元組表。在下面的討論中，三元組均以按行優(yōu)先的順序排列。在三元組表中，除了要表示非零元素之外，還需要表示矩陣的行、列數(shù)及非零元素的總個(gè)數(shù)。三元組表的結(jié)構(gòu)類型定義描述為設(shè)a為spmattrix型指針變量，圖5.6(a)所示的稀疏矩陣A的三元組表如圖5.6(b)所示。下面以矩陣的轉(zhuǎn)置為例，說(shuō)明采用三元組表的形式存儲(chǔ)稀疏矩陣，如何實(shí)現(xiàn)矩陣的轉(zhuǎn)置運(yùn)算。一個(gè)m?×?n的矩陣A，它的轉(zhuǎn)置矩陣B是一個(gè)n?×?m的矩陣，且A[i][j]?=?B[j][i]，1≤i≤m，1≤j≤n，即A的行是B的列，A的列是B的行。例如圖5.6(a)中的A和圖5.7(a)中的B互為轉(zhuǎn)置矩陣。為了敘述方便，下面將三元組表?*a中的成員a->data簡(jiǎn)稱為三元組表，因?yàn)橄鄬?duì)于其他成員而言，它是主要的。將A轉(zhuǎn)置為B，就是將A的三元組表a->data置換為B的三元組表b->data，如果只是互換a->data中i和j的內(nèi)容，那么所得到的b->data是按列存放的矩陣B的三元組表，還必須重新排列b->data中各結(jié)點(diǎn)的順序。由于A的列是B的行，如果按a->data的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣B的三元組表b->data必定是按行優(yōu)先的順序存放。算法的基本思想是：對(duì)a->data按列掃描n趟，在第col趟掃描中，找出所有列號(hào)等于col的那些三元組，將它們的行號(hào)、列號(hào)和元素值分別放入b->data的列號(hào)、行號(hào)和元素值中，即可得到B的按行優(yōu)先的壓縮存儲(chǔ)表示。以圖5.6和圖5.7為例，設(shè)col?=?1，則掃描a->data找到列號(hào)為1的三元組依次是(1,1,3)和(3,1,2)，存入b->data后為(1,1,3)和(1,3,2)，恰好為B中第1行的兩個(gè)非零元素。只要依次取col=1,2,3,4，即可得到a->data的轉(zhuǎn)置矩陣b->data。下面給出具體的算法。算法5.1矩陣的轉(zhuǎn)置(用三元組表存儲(chǔ)矩陣)。該算法的時(shí)間主要耗費(fèi)在col和ano的二重循環(huán)上，算法的時(shí)間復(fù)雜度為O(n?×?t)，t?<<m?×?n。而通常用二維數(shù)組表示矩陣時(shí)，其轉(zhuǎn)置算法的時(shí)間復(fù)雜度是O(m?×?n)。如果非零元素個(gè)數(shù)大于矩陣的行數(shù)，從轉(zhuǎn)置算法的時(shí)間復(fù)雜度來(lái)說(shuō)，采用三元組表存儲(chǔ)就不合適了，可考慮十字鏈表存儲(chǔ)。5.3.2稀疏矩陣的十字鏈表存儲(chǔ)當(dāng)矩陣的非零元素個(gè)數(shù)和位置在操作過(guò)程中變化較大時(shí)，不宜采用順序存儲(chǔ)結(jié)構(gòu)來(lái)表示三元組的線性表。例如，對(duì)于“將矩陣B加到矩陣A上”的操作，由于非零元素的插入或刪除將會(huì)引起A.data中元素的移動(dòng)。對(duì)于這種情況，采用十字鏈表存儲(chǔ)稀疏矩陣更為恰當(dāng)。十字鏈表存儲(chǔ)稀疏矩陣的基本思想是將每個(gè)非零元素對(duì)應(yīng)的三元組作為鏈表的結(jié)點(diǎn)，結(jié)點(diǎn)由5個(gè)域組成，其結(jié)構(gòu)如圖5.8所示。結(jié)點(diǎn)的結(jié)構(gòu)體類型定義如下：圖5.9給出了一個(gè)3行4列有4個(gè)非零元素的稀疏矩陣存儲(chǔ)在十字鏈表的示意圖。我們可以看到同一行的非零元素結(jié)點(diǎn)通過(guò)right域鏈接成一個(gè)循環(huán)鏈表，同一列的非零元素結(jié)點(diǎn)通過(guò)down域鏈接成一個(gè)循環(huán)鏈表，每個(gè)非零元素既是某個(gè)行鏈表中的一個(gè)結(jié)點(diǎn)，又是某個(gè)列鏈表中的一個(gè)結(jié)點(diǎn)，整個(gè)矩陣構(gòu)成類一個(gè)十字交叉的鏈表，故稱這樣的存儲(chǔ)結(jié)構(gòu)為十字鏈表?？捎脙蓚€(gè)分別存儲(chǔ)行鏈表和列鏈表頭指針的一維數(shù)組表示，h[i]是其數(shù)組元素。5.4廣義表5.4.1廣義表的概念及基本運(yùn)算1．廣義表概述廣義表一般記作其中，LS是廣義表的名稱；n(≥0)是它的長(zhǎng)度。在線性表的定義中，ai(1≤i≤n)只限于單元素。而在廣義表的定義中，ai可以是單元素，也可以是廣義表，分別稱為廣義表LS的原子和子表。習(xí)慣上，用大寫(xiě)字母表示廣義表的名稱，用小寫(xiě)字母表示原子。當(dāng)廣義表LS非空時(shí)，稱第一