數(shù)據(jù)結(jié)構(gòu)（Java版）課件全套 呂云翔 第1-8章 緒論、線性表、棧和隊(duì)列- 查找

第1章緒論

目錄2引言基本概念算法小結(jié)第一部分第二部分第三部分第四部分學(xué)習(xí)目的課程內(nèi)容數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)類型與抽象數(shù)據(jù)類型算法的概念算法描述算法分析第一部分引言學(xué)習(xí)目的4抽象模型實(shí)踐積累信息處理從具體問題中抽象出適當(dāng)?shù)臄?shù)學(xué)模型：分析問題，提取操作的對(duì)象，找出操作對(duì)象之間的邏輯關(guān)系，給出相應(yīng)的數(shù)學(xué)模型。設(shè)計(jì)解決此數(shù)學(xué)模型的算法。編程、運(yùn)行、調(diào)試，得出結(jié)果設(shè)計(jì)算法學(xué)會(huì)使用計(jì)算機(jī)解決實(shí)際的應(yīng)用問題課程內(nèi)容5過程抽象實(shí)現(xiàn)評(píng)價(jià)邏輯結(jié)構(gòu)基本運(yùn)算數(shù)據(jù)表示數(shù)據(jù)處理儲(chǔ)存結(jié)構(gòu)算法不同數(shù)據(jù)結(jié)構(gòu)比較和算法性能分析第二部分基本概念數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)7數(shù)據(jù)

數(shù)據(jù)(Data)是能夠被計(jì)算機(jī)程序識(shí)別、存儲(chǔ)、加工和處理的描述客觀事物的數(shù)字等符號(hào)集合的總稱。數(shù)據(jù)項(xiàng)

數(shù)據(jù)項(xiàng)(DataItem)是具有獨(dú)立含義的、數(shù)據(jù)不可分割的最小標(biāo)識(shí)單位，是數(shù)據(jù)元素的組成部分，也可稱為字段和域。數(shù)據(jù)元素

數(shù)據(jù)元素(DataElement)是數(shù)據(jù)的基本單位，又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)和記錄，是一個(gè)數(shù)據(jù)整體中可以標(biāo)識(shí)和訪問的數(shù)據(jù)單元。數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)8數(shù)據(jù)對(duì)象

數(shù)據(jù)對(duì)象(DataObject)是性質(zhì)相同的數(shù)據(jù)元素的集合，也叫數(shù)據(jù)元素類，是數(shù)據(jù)的一個(gè)子集，數(shù)據(jù)元素是數(shù)據(jù)對(duì)象的一個(gè)實(shí)例。數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)(DataStructure)是相互之間存在著一種或者多種關(guān)系的數(shù)據(jù)元素的集合，數(shù)據(jù)結(jié)構(gòu)概念包含3個(gè)方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的操作，只有3個(gè)方面的內(nèi)容相同才能稱為完全相同的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)9數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間存在的邏輯關(guān)系，由數(shù)據(jù)元素的集合和定義在此集合上的關(guān)系組成。兩要素：數(shù)據(jù)元素的集合、關(guān)系的集合。數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)分類10邏輯結(jié)構(gòu)樹形結(jié)構(gòu)商業(yè)策略集合圖形結(jié)構(gòu)線性結(jié)構(gòu)集合中元素的關(guān)系極為松散，關(guān)系為“屬于同一個(gè)集合”。線性結(jié)構(gòu)是數(shù)據(jù)元素中具有線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)，線性結(jié)構(gòu)中的結(jié)點(diǎn)存在“一對(duì)一”的關(guān)系。樹形結(jié)構(gòu)是數(shù)據(jù)元素之間具有層次關(guān)系的一種非線性結(jié)構(gòu)，樹形結(jié)構(gòu)中的結(jié)點(diǎn)存在“一對(duì)多”的關(guān)系。圖形結(jié)構(gòu)也是一種非線性結(jié)構(gòu)，圖形結(jié)構(gòu)中的結(jié)點(diǎn)存在“多對(duì)多”的關(guān)系。數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)11邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)表示或?qū)崿F(xiàn)叫數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，也叫物理結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系角度觀察數(shù)據(jù)，與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的；而數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，依賴于計(jì)算機(jī)。12存儲(chǔ)結(jié)構(gòu)索引存儲(chǔ)結(jié)構(gòu)商業(yè)策略順序存儲(chǔ)結(jié)構(gòu)散列存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)在連續(xù)的存儲(chǔ)單元中存放數(shù)據(jù)元素，元素的物理存儲(chǔ)次序和邏輯次序一致，即物理位置相鄰的元素在邏輯上也相鄰，每個(gè)元素與其前驅(qū)元素和后繼元素的存儲(chǔ)位置相鄰，數(shù)據(jù)元素的物理存儲(chǔ)結(jié)構(gòu)體現(xiàn)它們之間的邏輯關(guān)系。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)使用地址分散的存儲(chǔ)單元存放數(shù)據(jù)元素，邏輯上相鄰的數(shù)據(jù)元素的物理位置不一定相鄰，數(shù)據(jù)元素間的邏輯關(guān)系通常由附加的指針表示，指針記錄前驅(qū)元素和后繼元素的存儲(chǔ)地址。索引存儲(chǔ)結(jié)構(gòu)在存儲(chǔ)數(shù)據(jù)元素的基礎(chǔ)上增加索引表。散列存儲(chǔ)結(jié)構(gòu)也叫哈希存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的具體存儲(chǔ)地址根據(jù)該數(shù)據(jù)元素的關(guān)鍵字值通過散列函數(shù)直接計(jì)算出來。數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)分類13數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)操作數(shù)據(jù)操作是指對(duì)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素進(jìn)行運(yùn)算或處理。數(shù)據(jù)操作定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都需要一組對(duì)其數(shù)據(jù)元素進(jìn)行處理以實(shí)現(xiàn)特定功能的操作，如插入、刪除、更新等。數(shù)據(jù)操作的實(shí)現(xiàn)依賴于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。常用的數(shù)據(jù)操作：創(chuàng)建操作、插入操作、刪除操作、查找操作、修改操作、遍歷操作、銷毀操作數(shù)據(jù)類型

數(shù)據(jù)類型(DataType)是一組性質(zhì)相同的值的集合和定義在此集合上的一組操作的總稱。在用高級(jí)程序語言編寫的程序中必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量明確說明它們所屬的數(shù)據(jù)類型。高級(jí)程序設(shè)計(jì)語言通常預(yù)定義基本數(shù)據(jù)類型和構(gòu)造數(shù)據(jù)類型。

基本數(shù)據(jù)類型：只能作為一個(gè)整體來進(jìn)行處理不可分解的數(shù)據(jù)類型。

構(gòu)造數(shù)據(jù)類型：使用已有的基本數(shù)據(jù)類型和已定義的構(gòu)造數(shù)據(jù)類型通過一定的語法規(guī)則組織起來的數(shù)據(jù)類型。數(shù)據(jù)抽象15

數(shù)據(jù)抽象是指“定義和實(shí)現(xiàn)相分離”，即將一個(gè)類型的數(shù)據(jù)及其上的操作的邏輯含義和具體實(shí)現(xiàn)相分離，只考慮執(zhí)行什么操作(做什么)，而不考慮怎樣實(shí)現(xiàn)這些操作(怎樣做)。

數(shù)據(jù)抽象是一種信息隱蔽技術(shù)，可利用數(shù)據(jù)抽象研究復(fù)雜對(duì)象，忽略次要和實(shí)現(xiàn)細(xì)節(jié)，抽象出本質(zhì)特征，抽象層次越高，復(fù)用程度越高。

數(shù)據(jù)抽象是通過抽象數(shù)據(jù)類型來實(shí)現(xiàn)的。抽象數(shù)據(jù)類型16

抽象數(shù)據(jù)類型(AbstractDataType，ADT)是從問題的數(shù)學(xué)模型中抽象出來的邏輯結(jié)構(gòu)及定義在邏輯結(jié)構(gòu)上的一組操作，僅描述了數(shù)據(jù)的特性和數(shù)據(jù)操作的語法規(guī)則，隱藏了數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和操作的實(shí)現(xiàn)細(xì)節(jié)。

抽象數(shù)據(jù)類型是實(shí)現(xiàn)軟件模塊化設(shè)計(jì)思想的重要手段，一個(gè)抽象數(shù)據(jù)類型是描述一種特定功能的基本模塊，由各種基本模塊可組織和構(gòu)造起來一個(gè)大型的軟件系統(tǒng)。

在一般的面向?qū)ο笳Z言中，抽象數(shù)據(jù)類型通常可以采用抽象類或接口的方式進(jìn)行描述。第三部分算法算法的概念算法的定義

算法是有窮規(guī)則的集合，其規(guī)則確定一個(gè)解決某一特定類型問題的指令序列，其中每一條指令表示計(jì)算機(jī)的一個(gè)或者多個(gè)操作。算法的概念算法必須滿足以下5個(gè)特性。有窮性：對(duì)于任意的合法輸入值，算法必須在執(zhí)行有窮步驟后結(jié)束，并且每一步都在有窮的時(shí)間內(nèi)完成。確定性：算法對(duì)各種情況下執(zhí)行的每個(gè)操作都有確切的規(guī)定，算法的執(zhí)行者和閱讀者都能明確其含義和如何執(zhí)行，并且在任何條件下算法都只有一條執(zhí)行路徑?？尚行裕核惴ㄖ械牟僮鞅仨毝伎梢酝ㄟ^已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)，并且每一條指令都符合語法規(guī)則，滿足語義要求，都能被確切執(zhí)行。有輸入：輸入數(shù)據(jù)是算法的處理對(duì)象，一個(gè)算法具有零個(gè)或多個(gè)輸入數(shù)據(jù)，既可以由算法指定，也可以在算法執(zhí)行過程中通過輸入得到。有輸出：輸出數(shù)據(jù)是算法對(duì)輸入數(shù)據(jù)進(jìn)行信息加工后得到的結(jié)果，輸出數(shù)據(jù)和輸入數(shù)據(jù)具有確定的對(duì)應(yīng)關(guān)系，即算法的功能。一個(gè)算法有一個(gè)或多個(gè)輸出數(shù)據(jù)。20基本目標(biāo)高效率商業(yè)策略正確性可讀性健壯性算法應(yīng)滿足應(yīng)用問題的需求，這是算法設(shè)計(jì)最重要、最基本的目標(biāo)。算法應(yīng)具有良好的容錯(cuò)性，可以檢查錯(cuò)誤是否出現(xiàn)并且對(duì)錯(cuò)誤進(jìn)行適當(dāng)?shù)奶幚?，即使輸入的?shù)據(jù)不合適，也能避免出現(xiàn)不可控的結(jié)果。算法的執(zhí)行時(shí)間越短，時(shí)間效率越高；算法執(zhí)行時(shí)所占的存儲(chǔ)空間越小，空間效率越高。時(shí)間效率和空間效率往往不可兼得，用戶在解決實(shí)際問題時(shí)要根據(jù)實(shí)際情況權(quán)衡得失，進(jìn)行高效率算法的設(shè)計(jì)。算法的表達(dá)思路應(yīng)清晰，層次分明，易于理解，可讀性強(qiáng)，以便于后續(xù)對(duì)算法的使用和修改。算法的概念

算法設(shè)計(jì)的4個(gè)基本目標(biāo)算法的概念

算法與數(shù)據(jù)結(jié)構(gòu)21算法建立在數(shù)據(jù)結(jié)構(gòu)之上，對(duì)數(shù)據(jù)結(jié)構(gòu)的操作需要使用算法來描述。算法設(shè)計(jì)依賴于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法實(shí)現(xiàn)依賴于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。22算法描述010203自然語言用中文或英文對(duì)算法進(jìn)行表達(dá)，簡(jiǎn)單易懂，但缺乏嚴(yán)謹(jǐn)性。自然語言使用某種具體的程序設(shè)計(jì)語言（如Python語言）對(duì)算法進(jìn)行描述。此種方式嚴(yán)謹(jǐn)，算法可直接在計(jì)算機(jī)上執(zhí)行，但算法復(fù)雜、不易理解，需要借助大量的外部注釋才能使用戶明白。程序設(shè)計(jì)語言偽代碼是介于自然語言和程序設(shè)計(jì)語言之間的算法描述語言，是將程序設(shè)計(jì)語言的語法規(guī)則用自然語言進(jìn)行表示，忽略了嚴(yán)格的語法規(guī)則和描述細(xì)節(jié)，更易被用戶理解，并且更容易轉(zhuǎn)換成程序設(shè)計(jì)語言執(zhí)行。偽代碼23算法描述

例題設(shè)計(jì)算法求兩個(gè)整數(shù)的最大公約數(shù)。假設(shè)c為兩個(gè)整數(shù)a和b的最大公約數(shù)。用數(shù)學(xué)方法求兩個(gè)數(shù)的最大公約數(shù)，分別將a和b兩個(gè)整數(shù)分解成若干質(zhì)因數(shù)的乘積，再從中選擇最大的公約數(shù)。此種方法很難用于實(shí)際計(jì)算之中，因?yàn)榇髷?shù)的質(zhì)因數(shù)很難進(jìn)行分解。質(zhì)因數(shù)分解法中國(guó)古代的數(shù)學(xué)經(jīng)典著作《九章算術(shù)》中寫道：“以少減多，更相減損，求其等也，以等數(shù)約之，即除也，其所以相減者皆等數(shù)之重疊，顧以等數(shù)約之?！逼渲校葦?shù)即指兩數(shù)的最大公約數(shù)。更相減損法實(shí)際上，輾轉(zhuǎn)相除法就是現(xiàn)代版的更相減損術(shù)，使用循環(huán)實(shí)現(xiàn)：輾轉(zhuǎn)相除法算法分析24算法分析技術(shù)主要是通過某種方法討論算法的復(fù)雜度，評(píng)價(jià)算法的效率，以便在解決實(shí)際問題時(shí)根據(jù)實(shí)際情況和算法的優(yōu)缺點(diǎn)對(duì)算法進(jìn)行取舍。算法的優(yōu)劣主要通過算法復(fù)雜度進(jìn)行衡量，復(fù)雜度的高低反映了所需計(jì)算機(jī)資源的多少。計(jì)算機(jī)資源主要包括時(shí)間資源和空間資源。因此算法的復(fù)雜度通常以時(shí)間復(fù)雜度和空間復(fù)雜度來體現(xiàn)。算法分析

算法的時(shí)間復(fù)雜度25R算法的時(shí)間復(fù)雜度(TimeComplexity)是指算法的執(zhí)行時(shí)間隨問題規(guī)模的變化而變化的趨勢(shì)，反映算法執(zhí)行時(shí)間的長(zhǎng)短。

算法分析

算法的時(shí)間復(fù)雜度通常采用算法的漸進(jìn)分析中的大O表示法作為算法時(shí)間復(fù)雜度的漸進(jìn)度量值，稱為算法的漸進(jìn)時(shí)間復(fù)雜度。大O表示法是指當(dāng)且僅當(dāng)存在正整數(shù)c和n?0，使得0≤T(n)≤cf(n)對(duì)所有的n≥n0成立時(shí)，算法執(zhí)行時(shí)間的增長(zhǎng)率與f(n)的增長(zhǎng)率相同，記為T(n)=O(f(n))。一般地，如果f(n)=aknk+ak-1nk-1+…+a1n1+a0，且ai≥0，T(n)=O(nk)，即使用大O表示法時(shí)只需保留關(guān)于數(shù)據(jù)元素個(gè)數(shù)n的多項(xiàng)式的最高次冪的項(xiàng)并去掉其系數(shù)。比如，若算法的執(zhí)行時(shí)間是常數(shù)級(jí)，不依賴數(shù)據(jù)量的大小，則時(shí)間復(fù)雜度為O(1)；若算法的執(zhí)行時(shí)間與數(shù)據(jù)量為線性關(guān)系，則時(shí)間復(fù)雜度為O(n)；對(duì)數(shù)級(jí)、平方級(jí)、立方級(jí)、指數(shù)級(jí)的時(shí)間復(fù)雜度分別為O(log2n)、O(n2)、O(n3)、O(2n)。這些函數(shù)按數(shù)量級(jí)遞增排列具有下列關(guān)系：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)27R010203一個(gè)循環(huán)的時(shí)間代價(jià)=循環(huán)次數(shù)每次執(zhí)行的基本指令數(shù)目多個(gè)并列的循環(huán)的時(shí)間代價(jià)=每個(gè)循環(huán)的時(shí)間代價(jià)之和多層嵌套循環(huán)的時(shí)間代價(jià)=每層循環(huán)的時(shí)間代價(jià)之積算法分析

算法的時(shí)間復(fù)雜度循環(huán)語句的時(shí)間代價(jià)一般可用以下3條原則進(jìn)行分析：算法分析

算法的空間復(fù)雜度算法的空間復(fù)雜度(SpaceComplexity)是指算法執(zhí)行時(shí)所占用的額外存儲(chǔ)空間量隨問題規(guī)模的變化而變化的趨勢(shì)。執(zhí)行一個(gè)算法所需要的存儲(chǔ)空間主要包含以下兩個(gè)部分。(1)固定空間部分：主要包括算法的程序指令、常量、變量所占的空間，與所處理問題的規(guī)模無關(guān)。(2)可變空間部分：主要包括輸入的數(shù)據(jù)元素占用的空間和程序運(yùn)行過程中額外的存儲(chǔ)空間，與處理問題的規(guī)模有關(guān)。算法分析

算法的空間復(fù)雜度當(dāng)問題的規(guī)模為n時(shí)，S(n)表示此時(shí)算法占用的存儲(chǔ)空間量，稱為算法的空間復(fù)雜度，當(dāng)n增大時(shí)S(n)也隨之增大。通常采用算法的漸進(jìn)分析中的大O表示法作為算法空間復(fù)雜度的漸進(jìn)度量值，稱為算法的漸進(jìn)空間復(fù)雜度，記作S(n)=O(f(n))，其分析與算法的漸進(jìn)時(shí)間復(fù)雜度相同。算法描述

例題設(shè)n為正整數(shù)，試確定下列程序段中語句“x+=1”的頻度。算法描述

例題設(shè)n為正整數(shù)，試確定下列程序段中語句“x+=1”的頻度。算法描述

例題設(shè)n為正整數(shù)，試確定下列程序段中語句“x+=1”的頻度。解：(1)i為1時(shí)，j值只能取1，語句執(zhí)行一次；i為2時(shí)，j可取1或2，語句執(zhí)行兩次；i為n時(shí)，j可取1、2、…,n，語句執(zhí)行n次，所以語句頻度=1+2+…+n=n(n+1)/2。(2)i為1時(shí)，j值只能取1，k值可取1、2、…、n，語句執(zhí)行n次；i為2時(shí)，j可取1或2，k值可取1、2、…、n，語句執(zhí)行2n次；i為n時(shí)，j可取1、2、…、n，語句執(zhí)行n×n次，所以語句頻度=n2(n+1)/2。(3)i與j初始和為1，其后每循環(huán)一次i和j中有且僅有一個(gè)值增1，即i與j的和增1。由于循環(huán)條件為i+j<=n，因此循環(huán)共執(zhí)行n次。所以，語句頻度為n。(4)分析y的初始值為100，當(dāng)y≤0時(shí)循環(huán)結(jié)束，x++每執(zhí)行10次y減小1，所以x+=1的語句頻度為1000。第四部分小結(jié)34小結(jié)(1)數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩個(gè)方面。數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)4種。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)分為順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)構(gòu)4種。(2)集合中的數(shù)據(jù)元素是相互獨(dú)立的，在線性結(jié)構(gòu)中數(shù)據(jù)元素具有“一對(duì)一”的關(guān)系，在樹形結(jié)構(gòu)中數(shù)據(jù)元素具有“一對(duì)多”的關(guān)系，在圖形結(jié)構(gòu)中數(shù)據(jù)元素具有“多對(duì)多”的關(guān)系。(3)抽象數(shù)據(jù)類型描述了數(shù)據(jù)的特性和數(shù)據(jù)操作的語法規(guī)則，隱藏了數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和操作的實(shí)現(xiàn)細(xì)節(jié)。在Python語言中抽象數(shù)據(jù)類型用抽象類的定義來實(shí)現(xiàn)。(4)算法的設(shè)計(jì)應(yīng)該滿足正確性、健壯性、高效率和可讀性4個(gè)目標(biāo)。(5)算法分析主要包括對(duì)時(shí)間復(fù)雜度和空間復(fù)雜度的分析，通常用大O表示法進(jìn)行表示。謝謝觀看第2章線性表

目錄37線性表及其基本操作2.1線性表的存儲(chǔ)和實(shí)現(xiàn)2.1.1抽象數(shù)據(jù)類型描述2.1.2線性表順序存儲(chǔ)2.1.3線性表的線性表的基本概念2.2順序表2.2.1順序表的基本操作實(shí)現(xiàn)2.2.1目錄38線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)2.3單鏈表2.3.1順序表與鏈表的比較2.4單鏈表的基本操作實(shí)現(xiàn)2.3.2其他鏈表2.3.3小結(jié)2.1線性表及其基本操作線性表的基本概念40線性表(LinearList)是其組成元素間具有線性關(guān)系的一種線性結(jié)構(gòu)，是由n個(gè)具有相同數(shù)據(jù)類型的數(shù)據(jù)元素a0、a1、…、an-1構(gòu)成的有限序列，一般表示為：(a0,ai,…ai,ai+1,…,an-1)其中，數(shù)據(jù)元素ai可以是字母、整數(shù)、浮點(diǎn)數(shù)、對(duì)象或其他更復(fù)雜的信息，i代表數(shù)據(jù)元素在線性表中的位序號(hào)(0≤i<n)，n是線性表的元素個(gè)數(shù)，稱為線性表的長(zhǎng)度，當(dāng)n=0時(shí)線性表為空表。線性表的基本概念例1：英文字母表(A,B,…,Z)是一個(gè)表長(zhǎng)為26的線性表。例2：表2.1所示的書籍信息表中的所有記錄序列構(gòu)成了一個(gè)線性表，線性表中的每個(gè)數(shù)據(jù)元素都是由書名、作者、出版社、價(jià)格4個(gè)數(shù)據(jù)項(xiàng)構(gòu)成的記錄。表2.1書籍信息表書名作者出版社價(jià)格軟件工程實(shí)用教程呂云翔清華大學(xué)出版社49.00線性表的基本概念42D={ai|0≤i<n}R={r}r={<ai,ai-1>|0≤i<n-1}線性表中的數(shù)據(jù)元素具有線性的“一對(duì)一”的邏輯關(guān)系，是與位置有關(guān)的即第i個(gè)元素ai處于第i-1個(gè)元素ai-1的后面和第i+1個(gè)元素ai+1的前面。這種位置上的有序性就是一種線性關(guān)系，可以用二元組表示為L(zhǎng)=(D,R)，其中有右圖關(guān)系：ai-1aiai+1線性表的基本概念43ai-1aiai+1a0an-1……開始結(jié)點(diǎn)沒有

前驅(qū)元素有且僅有一個(gè)前驅(qū)元素和后繼元素終端結(jié)點(diǎn)沒有

后繼元素抽象數(shù)據(jù)類型描述44Python描述解：length()=7；isEmpty()返回false；get(3)返回4；indexOf(4)返回3；display()輸出1,2,3,4,5,6,7；insert(2,7)執(zhí)行后線性表A變?yōu)?,2,7,3,4,5,6,7；remove(4)執(zhí)行后線性表A變?yōu)?,2,3,4,6,7。抽象數(shù)據(jù)類型描述45【例2.1】有線性表A=(1,2,3,4,5,6,7)，求length()、isEmpty()、get(3)、indexOf(4)、display()、insert(2,7)和remove(4)等基本運(yùn)算的執(zhí)行結(jié)果。線性表的存儲(chǔ)和實(shí)現(xiàn)46基于順序存儲(chǔ)的實(shí)現(xiàn)基于鏈?zhǔn)酱鎯?chǔ)的實(shí)現(xiàn)在2.1.2節(jié)中，線性表的抽象數(shù)據(jù)Python抽象類包含了線性表的主要基本操作，如果要使用這個(gè)接口，還需要具體的類來實(shí)現(xiàn)。線性表的Python抽象類的實(shí)現(xiàn)方法主要有以下兩種。ai-1aiai+1ai-1aiai+12.2線性表的順序存儲(chǔ)順序表48線性表的順序存儲(chǔ)結(jié)構(gòu)是把線性表中的所有元素按照其邏輯順序依次存儲(chǔ)到計(jì)算機(jī)的內(nèi)存單元中指定存儲(chǔ)位置開始的一塊連續(xù)的存儲(chǔ)空間中，稱為順序表。順序表用一組連續(xù)的內(nèi)存單元依次存放數(shù)據(jù)元素，元素在內(nèi)存中的物理存儲(chǔ)次序和它們?cè)诰€性表中的邏輯次序一致，即元素ai與其前驅(qū)元素ai-1和后繼元素ai+1的存儲(chǔ)位置相鄰，如圖2.2所示。圖2.2順序表定義順序表49又因?yàn)閿?shù)據(jù)表中的所有數(shù)據(jù)元素具有相同的數(shù)據(jù)類型，所以只要知道順序表的基地址和數(shù)據(jù)元素所占存儲(chǔ)空間的大小即可計(jì)算出第i個(gè)數(shù)據(jù)元素的地址，可表示為：Loc(ai)=Loc(a0)+i×c，其中0≤i≤n-1其中，Loc(ai)是數(shù)據(jù)元素ai的存儲(chǔ)地址，Loc(a0)是數(shù)據(jù)元素a0的存儲(chǔ)地址，即順序表的基地址，i為元素位置，c為一個(gè)數(shù)據(jù)元素占用的存儲(chǔ)單元。可以看出，計(jì)算一個(gè)元素地址所需的時(shí)間為常量，與順序表的長(zhǎng)度n無關(guān)；存儲(chǔ)地址是數(shù)據(jù)元素位序號(hào)i的線性函數(shù)。因此，存取任何一個(gè)數(shù)據(jù)元素的時(shí)間復(fù)雜度為O(1)，順序表是按照數(shù)據(jù)元素的位序號(hào)隨機(jī)存取的結(jié)構(gòu)。順序表50特點(diǎn)在線性表中邏輯上相鄰的元素在物理存儲(chǔ)位置上也同樣相鄰可按照數(shù)據(jù)元素的位序號(hào)進(jìn)行隨機(jī)存取進(jìn)行插入、刪除操作需要移動(dòng)大量的數(shù)據(jù)元素需要進(jìn)行存儲(chǔ)空間的預(yù)先分配，可能會(huì)造成空間浪費(fèi)，但存儲(chǔ)密度較高順序表51描述可以使用數(shù)組來描述線性表的順序存儲(chǔ)結(jié)構(gòu)。在程序設(shè)計(jì)語言中數(shù)組是一種構(gòu)造數(shù)據(jù)類型。數(shù)組存儲(chǔ)具有相同數(shù)據(jù)類型的元素集合，數(shù)組的存儲(chǔ)單元個(gè)數(shù)稱為數(shù)組長(zhǎng)度，每個(gè)存儲(chǔ)單元的地址是連續(xù)的，每個(gè)元素連續(xù)存儲(chǔ)。數(shù)組通過下標(biāo)識(shí)別元素，元素的下標(biāo)是其存儲(chǔ)單元序號(hào)，表示元素在數(shù)組中的位置。一維數(shù)組使用一個(gè)下標(biāo)唯一確定一個(gè)元素，二維數(shù)組使用兩個(gè)下標(biāo)唯一確定一個(gè)元素。順序表52Python描述順序表53Python描述順序表54Python描述順序表55Python描述順序表56Python描述順序表的基本操作實(shí)現(xiàn)57插入操作insert(i,x)是在長(zhǎng)度為n的順序表的第i個(gè)數(shù)據(jù)元素之前插入值為x的數(shù)據(jù)元素，其中0≤i≤n，當(dāng)i=0時(shí)在表頭插入，當(dāng)i=n時(shí)在表尾插入，在插入操作完成后表長(zhǎng)加1，順序表的邏輯結(jié)構(gòu)由(a0,a1,…,ai-1,ai,…,a-n-1)變成了(a0,a1,…,ai-1,x,ai,…,a-n-1)，如圖2.3所示。插入操作圖2.3插入操作前后的順序表存儲(chǔ)結(jié)構(gòu)圖順序表的基本操作實(shí)現(xiàn)58步驟判斷順序表的存儲(chǔ)空間是否已滿，若已滿則拋出異常01判斷參數(shù)i的值是否滿足0≤i≤curLen，若不滿足則拋出異常02將插入位置及其之后的所有數(shù)據(jù)元素后移一個(gè)存儲(chǔ)位置03在位置i處插入新的數(shù)據(jù)元素x04表長(zhǎng)加105順序表的基本操作實(shí)現(xiàn)59【算法2.1】順序表的插入操作算法順序表的基本操作實(shí)現(xiàn)60

順序表的基本操作實(shí)現(xiàn)61

順序表的基本操作實(shí)現(xiàn)62

順序表的基本操作實(shí)現(xiàn)63刪除操作remove(i,x)是將長(zhǎng)度為n的順序表的第i個(gè)數(shù)據(jù)元素刪除，其中0≤i≤n-1，刪除操作完成后表長(zhǎng)減1，順序表的邏輯結(jié)構(gòu)由(a0,a1,…,ai-1,ai,…,an-1)變成了(a0,a1,…,ai-1,ai+1,…,an-1)，如圖2.4所示。刪除操作圖2.4刪除操作前后的順序表存儲(chǔ)結(jié)構(gòu)圖順序表的基本操作實(shí)現(xiàn)64步驟判斷參數(shù)i是否滿足0≤i≤curLen-1，若不滿足則拋出異常01將第i個(gè)數(shù)據(jù)元素之后的數(shù)據(jù)元素都向前移動(dòng)一個(gè)存儲(chǔ)單元02表長(zhǎng)減103順序表的基本操作實(shí)現(xiàn)65【算法2.2】順序表的刪除操作算法順序表的基本操作實(shí)現(xiàn)66

順序表的基本操作實(shí)現(xiàn)67返回比較位置初次出現(xiàn)查找操作indexOf(x)是在長(zhǎng)度為n的順序表中尋找初次出現(xiàn)的數(shù)據(jù)元素值為x的數(shù)據(jù)元素的位置。其主要步驟為將x與順序表中的每一個(gè)數(shù)據(jù)元素的值進(jìn)行比較，若相等，則返回該數(shù)據(jù)元素的位置；若比較結(jié)束未找到等值的數(shù)據(jù)元素，返回-1。查找操作順序表的基本操作實(shí)現(xiàn)68【算法2.3】順序表的查找操作算法順序表的基本操作實(shí)現(xiàn)69

順序表的基本操作實(shí)現(xiàn)70【例2.3】建立一個(gè)由a~z的26個(gè)字母組成的字母順序表，求每個(gè)字母的直接前驅(qū)和直接后繼，編程實(shí)現(xiàn)。順序表的基本操作實(shí)現(xiàn)71【例2.4】建立一個(gè)順序表，表中數(shù)據(jù)為5個(gè)學(xué)生的成績(jī)(89,93,92,90,100)，然后查找成績(jī)?yōu)?0的數(shù)據(jù)元素，并輸出其在順序表中的位置。順序表的基本操作實(shí)現(xiàn)72靜態(tài)特性順序表利用元素的物理存儲(chǔ)次序反映線性表元素的邏輯關(guān)系，不需要額外的存儲(chǔ)空間進(jìn)行元素間關(guān)系的表達(dá)。順序表是隨機(jī)存儲(chǔ)結(jié)構(gòu)，存取元素ai的時(shí)間復(fù)雜度為O(1),并且實(shí)現(xiàn)了線性表抽象數(shù)據(jù)類型所要求的基本操作。①動(dòng)態(tài)特性插入和刪除操作的效率很低，每插入或刪除一個(gè)數(shù)據(jù)元素，元素的移動(dòng)次數(shù)較多，平均移動(dòng)順序表中數(shù)據(jù)元素個(gè)數(shù)的一半；并且數(shù)組容量不可更改，存在因容量小造成數(shù)據(jù)溢出或者因容量過大造成內(nèi)存資源浪費(fèi)的問題。②綜上所述，順序表具有較好的靜態(tài)特性、較差的動(dòng)態(tài)特性2.3線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)74

采用鏈?zhǔn)酱鎯?chǔ)方式存儲(chǔ)的線性表稱為鏈表，鏈表是用若干地址分散的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，邏輯上相鄰的數(shù)據(jù)元素在物理位置上不一定相鄰，必須采用附加信息表示數(shù)據(jù)元素之間的邏輯關(guān)系，因此鏈表的每一個(gè)結(jié)點(diǎn)不僅包含元素本身的信息數(shù)據(jù)域，而且包含元素之間邏輯關(guān)系的信息，即邏輯上相鄰結(jié)點(diǎn)地址的指針域。單鏈表75單鏈表是指結(jié)點(diǎn)中只包含一個(gè)指針域的鏈表，指針域中儲(chǔ)存著指向后繼結(jié)點(diǎn)的指針。單鏈表的頭指針是線性表的起始地址，是線性表中第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址，可作為單鏈表的唯一標(biāo)識(shí)。單鏈表的尾結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)，所以其指針域值為None。為了使操作簡(jiǎn)便，在第一個(gè)結(jié)點(diǎn)之前增加頭結(jié)點(diǎn)，單鏈表的頭指針指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的數(shù)據(jù)域不存放任何數(shù)據(jù)，指針域存放指向第一個(gè)結(jié)點(diǎn)的指針。空單鏈表的頭指針head為None。單鏈表76圖2.5不帶頭結(jié)點(diǎn)的單鏈表圖2.6帶頭結(jié)點(diǎn)的單鏈表單鏈表77單鏈表的結(jié)點(diǎn)的存儲(chǔ)空間是在插入和刪除過程中動(dòng)態(tài)申請(qǐng)和釋放的，不需要預(yù)先分配，從而避免了順序表因存儲(chǔ)空間不足需要擴(kuò)充空間和復(fù)制元素的過程，避免了順序表因容量過大造成內(nèi)存資源浪費(fèi)的問題，提高了運(yùn)行效率和存儲(chǔ)空間的利用率。單鏈表78Python描述結(jié)點(diǎn)類描述單鏈表79Python描述單鏈表類描述單鏈表80Python描述單鏈表類描述單鏈表81Python描述單鏈表類描述單鏈表82Python描述單鏈表類描述單鏈表83Python描述單鏈表類描述單鏈表84Python描述單鏈表類描述單鏈表85Python描述單鏈表類描述單鏈表的基本操作實(shí)現(xiàn)86查找位序查找get(i)是返回長(zhǎng)度為n的單鏈表中第i個(gè)結(jié)點(diǎn)的數(shù)據(jù)域的值，其中0≤i≤n-1。由于單鏈表的存儲(chǔ)空間不連續(xù)，因此必須從頭結(jié)點(diǎn)開始沿著后繼結(jié)點(diǎn)依次進(jìn)行查找。查找操作indexOf(x)是在長(zhǎng)度為n的單鏈表中尋找初次出現(xiàn)的數(shù)據(jù)域值為x的數(shù)據(jù)元素的位置。主要步驟為將x與單鏈表中的每一個(gè)數(shù)據(jù)元素的數(shù)據(jù)域進(jìn)行比較，若相等，則返回該數(shù)據(jù)元素在單鏈表中的位置；若比較結(jié)束未找到等值的數(shù)據(jù)元素，返回-1單鏈表的基本操作實(shí)現(xiàn)87【算法2.4】位序查找算法單鏈表的基本操作實(shí)現(xiàn)88【算法2.5】按值查找單鏈表的基本操作實(shí)現(xiàn)89插入插入操作insert(i,x)是在長(zhǎng)度為n的單鏈表的第i個(gè)結(jié)點(diǎn)之前插入數(shù)據(jù)域值為x的新結(jié)點(diǎn)，其中0≤i≤n，當(dāng)i=0時(shí)，在表頭插入，當(dāng)i=n時(shí)在表尾插入。與順序表相比，單鏈表不需要移動(dòng)一批數(shù)據(jù)元素，而只需要改變結(jié)點(diǎn)的指針域，改變有序?qū)?，即可?shí)現(xiàn)數(shù)據(jù)元素的插入，即<ai-1,ai>轉(zhuǎn)變?yōu)?lt;ai-1,x>和<x,ai>，如圖2.7所示。單鏈表的基本操作實(shí)現(xiàn)90插入圖2.7單鏈表上的插入單鏈表的基本操作實(shí)現(xiàn)91步驟查找到插入位置的前驅(qū)結(jié)點(diǎn)，即第i-1個(gè)結(jié)點(diǎn)。創(chuàng)建數(shù)據(jù)域值為x的新結(jié)點(diǎn)。修改前驅(qū)結(jié)點(diǎn)的指針域?yàn)橹赶蛐陆Y(jié)點(diǎn)的指針，新結(jié)點(diǎn)的指針域?yàn)橹赶蛟趇個(gè)結(jié)點(diǎn)的指針。單鏈表的基本操作實(shí)現(xiàn)92【算法2.6】帶頭結(jié)點(diǎn)的單鏈表的插入操作。單鏈表的基本操作實(shí)現(xiàn)93【算法2.7】不帶頭結(jié)點(diǎn)的單鏈表的插入操作。單鏈表的基本操作實(shí)現(xiàn)94代碼分析由于鏈?zhǔn)酱鎯?chǔ)采用的是動(dòng)態(tài)存儲(chǔ)分配空間，所以在進(jìn)行插入操作之前不需要判斷存儲(chǔ)空間是否已滿。在帶頭結(jié)點(diǎn)的單鏈表上進(jìn)行插入操作時(shí)，無論插入位置是表頭、表尾還是表中，操作語句都是一致的。但是在不帶頭結(jié)點(diǎn)的單鏈表上進(jìn)行插入操作時(shí)，在表頭插入和在其他位置插入新結(jié)點(diǎn)的語句是不同的，需要分兩種情況進(jìn)行處理。單鏈表的基本操作實(shí)現(xiàn)95刪除刪除操作remove(i,x)是將長(zhǎng)度為n的單鏈表的第i個(gè)結(jié)點(diǎn)刪除，其中0≤i≤n-1。與順序表相比，單鏈表不需要移動(dòng)一批數(shù)據(jù)元素，而只需要改變結(jié)點(diǎn)的指針域，實(shí)現(xiàn)有序?qū)Φ母淖?，即可刪除結(jié)點(diǎn)，即<ai-1,ai>和<ai,ai+1>轉(zhuǎn)變?yōu)?lt;ai-1,ai+1>，如下圖所示。單鏈表的基本操作實(shí)現(xiàn)96步驟判斷單鏈表是否為空。查找待刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。修改前驅(qū)結(jié)點(diǎn)的指針域?yàn)榇齽h除結(jié)點(diǎn)的指針域。單鏈表的基本操作實(shí)現(xiàn)97【算法2.8】刪除操作。單鏈表的基本操作實(shí)現(xiàn)98單鏈表的建立1)頭插法

將新結(jié)點(diǎn)插入到單鏈表的表頭，讀入的數(shù)據(jù)順序與結(jié)點(diǎn)順序相反?！舅惴?.9】頭插法。單鏈表的基本操作實(shí)現(xiàn)99單鏈表的建立2)尾插法

將新結(jié)點(diǎn)插入到單鏈表的表尾，讀入的數(shù)據(jù)順序與結(jié)點(diǎn)順序相同?！舅惴?.10】尾插法。單鏈表的基本操作實(shí)現(xiàn)100【例2.5】編程實(shí)現(xiàn)將列表中的元素構(gòu)建成一個(gè)有序的單鏈表。單鏈表的基本操作實(shí)現(xiàn)101【例2.5】編程實(shí)現(xiàn)將列表中的元素構(gòu)建成一個(gè)有序的單鏈表。其他鏈表102循環(huán)鏈表循環(huán)鏈表與單鏈表的結(jié)構(gòu)相似，只是將鏈表的首尾相連，即尾結(jié)點(diǎn)的指針域?yàn)橹赶蝾^結(jié)點(diǎn)的指針，從而形成了一個(gè)環(huán)狀的鏈表。循環(huán)鏈表與單鏈表的操作算法基本一致，判定循環(huán)鏈表中的某個(gè)結(jié)點(diǎn)是否為尾結(jié)點(diǎn)的條件不是它的后繼結(jié)點(diǎn)為空，而是它的后繼結(jié)點(diǎn)是否為頭結(jié)點(diǎn)。在實(shí)現(xiàn)循環(huán)鏈表時(shí)可用頭指針或尾指針或二者同時(shí)使用來標(biāo)識(shí)循環(huán)鏈表，通常使用尾指針來進(jìn)行標(biāo)識(shí)，可簡(jiǎn)化某些操作。其他鏈表103雙向鏈表雙向鏈表的結(jié)點(diǎn)具有兩個(gè)指針域，一個(gè)指針指向前驅(qū)結(jié)點(diǎn)，一個(gè)指針指向后繼結(jié)點(diǎn)。使得查找某個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)不需要從表頭開始順著鏈表依次進(jìn)行查找，減小時(shí)間復(fù)雜度。其他鏈表104結(jié)點(diǎn)類描述其他鏈表105基本操作實(shí)現(xiàn)其與單鏈表的不同之處主要在于進(jìn)行插入和刪除操作時(shí)每個(gè)結(jié)點(diǎn)需要修改兩個(gè)指針域。【算法2.11】插入操作其他鏈表106基本操作實(shí)現(xiàn)【算法2.12】刪除操作。2.4順序表與鏈表的比較順序表與鏈表比較108

順序表鏈表優(yōu)點(diǎn)（1）可進(jìn)行高效隨機(jī)存取；（2）存儲(chǔ)密度高，空間開銷??；（3）實(shí)現(xiàn)簡(jiǎn)單，便于使用（1）靈活，可進(jìn)行存儲(chǔ)空間的動(dòng)態(tài)分配；（2）插入、刪除效率高缺點(diǎn)（1）需要預(yù)先分配存儲(chǔ)空間；（2）不便于進(jìn)行插入和刪除操作（1）存儲(chǔ)密度低；（2）不可按照位序號(hào)隨機(jī)存取小結(jié)109雙向鏈表的結(jié)點(diǎn)具有兩個(gè)指針域，一個(gè)指針指向前驅(qū)結(jié)點(diǎn)，一個(gè)指針指向后繼結(jié)點(diǎn)，使得查找某個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)不需要從表頭開始順著鏈表依次進(jìn)行查找，減小時(shí)間復(fù)雜度。循環(huán)鏈表將鏈表的首尾相連，即尾結(jié)點(diǎn)的指針域?yàn)橹赶蝾^結(jié)點(diǎn)的指針，從而形成了一個(gè)環(huán)狀的鏈表。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈表，不能直接訪問給定位置上的數(shù)據(jù)元素，必須從頭結(jié)點(diǎn)開始沿著后繼結(jié)點(diǎn)進(jìn)行訪問，時(shí)間復(fù)雜度為O(n)。在插入或刪除數(shù)據(jù)元素時(shí)不需要移動(dòng)任何數(shù)據(jù)元素，只需要更改結(jié)點(diǎn)的指針域即可，時(shí)間復(fù)雜度為O(1)。線性表的順序存儲(chǔ)結(jié)構(gòu)稱為順序表，可用數(shù)組實(shí)現(xiàn)，可對(duì)數(shù)據(jù)元素進(jìn)行隨機(jī)存取，時(shí)間復(fù)雜度為O(1)，在插入或刪除數(shù)據(jù)元素時(shí)時(shí)間復(fù)雜度為O(n)。線性表是其組成元素間具有線性關(guān)系的一種線性結(jié)構(gòu)，其實(shí)現(xiàn)方式主要為基于順序存儲(chǔ)的實(shí)現(xiàn)和基于鏈?zhǔn)酱鎯?chǔ)的實(shí)現(xiàn)。110感謝聆聽！第3章棧和隊(duì)列

主要內(nèi)容112棧的基本概念棧的抽象數(shù)據(jù)類型描述順序棧與鏈棧隊(duì)列的基本概念隊(duì)列的抽象數(shù)據(jù)類型描述順序隊(duì)列、鏈隊(duì)列與優(yōu)先級(jí)隊(duì)列棧和隊(duì)列的比較棧的基本概念113棧是一種特殊的線性表，其插入、刪除操作只能在表的尾部進(jìn)行。在棧中允許進(jìn)行插入、刪除操作的一端稱為棧頂，另一端稱為棧底。通常，棧的插入操作叫入棧，棧的刪除操作叫出棧。由于棧的插入和刪除操作只允許在棧頂進(jìn)行，每次入棧的元素即成為棧頂元素，每次最先出棧的總是棧頂元素，所以棧是一種后進(jìn)先出的線性表。棧的抽象數(shù)據(jù)類型描述114棧中的數(shù)據(jù)元素和數(shù)據(jù)間的邏輯關(guān)系與線性表相同，是由n個(gè)具有相同數(shù)據(jù)類型的數(shù)據(jù)元素構(gòu)成的有限序列棧的抽象數(shù)據(jù)類型描述11501020304GOAL棧的抽象數(shù)據(jù)Java抽象類包含了棧的主要基本操作，如果要使用這個(gè)類還需要具體的類來實(shí)現(xiàn)。棧的Java抽象類的實(shí)現(xiàn)方法主要有以下兩種。(1)基于順序存儲(chǔ)的實(shí)現(xiàn)，為順序棧；(2)基于鏈?zhǔn)酱鎯?chǔ)的實(shí)現(xiàn)，為鏈棧。順序棧116順序棧用數(shù)組實(shí)現(xiàn)，因?yàn)槿霔：统鰲２僮鞫际窃跅ｍ斶M(jìn)行，所以增加變量top來指示棧頂元素的位置，top指向棧頂元素存儲(chǔ)位置的下一個(gè)存儲(chǔ)單元的位置，空棧時(shí)top=0。順序棧的入棧操作117主要流程：(1)判斷順序棧是否為滿，若滿則拋出異常。(2)將x存入top所指的存儲(chǔ)單元位置。(3)top加1。順序棧的出棧操作118主要流程：(1)判斷順序棧是否為空，若空則返回null。(2)top減1。(3)返回top所指的棧頂元素的值。例題119利用順序棧實(shí)現(xiàn)括號(hào)匹配的語法檢查。解：括號(hào)匹配是指程序中出現(xiàn)的括號(hào)，左、右括號(hào)的個(gè)數(shù)是相同的，并且需要先左后右依次出現(xiàn)。括號(hào)是可以嵌套的，一個(gè)右括號(hào)與其前面最近的一個(gè)左括號(hào)匹配，使用棧保存多個(gè)嵌套的左括號(hào)。鏈棧120采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧稱為鏈棧，由于入棧和出棧只能在棧頂進(jìn)行，不存在在棧的任意位置進(jìn)行插入和刪除的操作，所以不需要設(shè)置頭結(jié)點(diǎn)，只需要將指針top指向棧頂元素結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)的指針域指向其后繼結(jié)點(diǎn)即可。鏈棧121鏈棧的入棧操作122主要流程：(1)構(gòu)造數(shù)據(jù)值域?yàn)閤的新結(jié)點(diǎn)。(2)改變新結(jié)點(diǎn)和首結(jié)點(diǎn)的指針域，使新結(jié)點(diǎn)成為新的棧頂結(jié)點(diǎn)。鏈棧的出棧操作123主要流程：(1)判斷鏈棧是否為，若空則返回null。(2)修改top指針域的值空，返回被刪結(jié)點(diǎn)的數(shù)據(jù)域值。124分析可得，使用單鏈表實(shí)現(xiàn)棧，入棧和出棧操作的實(shí)現(xiàn)為單鏈表的頭插入和頭刪除，時(shí)間復(fù)雜度為O(1)。例題125設(shè)有編號(hào)為1、2、3、4的4輛列車順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的車站，具體寫出這4輛列車開出車站的所有可能的順序。解：至少有14種。全進(jìn)之后再出的情況只有1種：4,3,2,1。進(jìn)3個(gè)之后再出的情況有3種：3,4,2,1；3,2,4,1；3,2,1,4。進(jìn)兩個(gè)之后再出的情況有5種：2,4,3,1；2,3,4,1；2,1,3,4；2,1,4,3；2,1,3,4。進(jìn)一個(gè)之后再出的情況有5種：1,4,3,2；1,3,2,4；1,3,4,2；1,2,3,4；1,2,4,3。在執(zhí)行操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后棧頂元素和棧底元素分別是什么？例題126編程實(shí)現(xiàn)漢諾塔問題的求解。假設(shè)有3個(gè)分別命名為x、y、z的塔座，在塔座x上插有n個(gè)直徑和序號(hào)均為1、2、…、n的圓盤。要求將塔座x上的n個(gè)圓盤借助塔座y移動(dòng)到塔座z上，仍按照相同的序號(hào)排列，并且每次只能移動(dòng)一個(gè)圓盤，在任何時(shí)候都不能將一個(gè)較大的圓盤壓在較小的圓盤之上。解：分析問題可知，當(dāng)n=1時(shí)只要將序號(hào)為1的圓盤從x直接移動(dòng)到z即可；當(dāng)n>1時(shí)則需要將序號(hào)小于n的n-1個(gè)圓盤移動(dòng)到y(tǒng)上，再將序號(hào)為n的圓盤移動(dòng)到z上，然后將y上的n-1個(gè)圓盤移動(dòng)到z上。如何將n-1個(gè)圓盤移動(dòng)到z上是一個(gè)和原問題相似的問題，只是規(guī)模變小，可以用同樣的方法求解。代碼如右：隊(duì)列的基本概念127

隊(duì)列是一種特殊的線性表，其插入操作只能在表的尾部進(jìn)行，刪除操作只能在表頭進(jìn)行。在隊(duì)列中允許進(jìn)行插入操作的一端稱為隊(duì)尾，允許進(jìn)行刪除操作的另一端稱為隊(duì)首。通常，隊(duì)列的插入操作叫入隊(duì)，隊(duì)列的刪除操作叫出隊(duì)。沒有數(shù)據(jù)元素的隊(duì)列稱為空隊(duì)列。

由于插入和刪除操作分別在隊(duì)尾和隊(duì)首進(jìn)行，最先入隊(duì)的元素總是最先出隊(duì)，因此隊(duì)列具有先進(jìn)先出的特點(diǎn)。隊(duì)列的抽象數(shù)據(jù)類型描述128隊(duì)列中的數(shù)據(jù)元素和數(shù)據(jù)間的邏輯關(guān)系與線性表相同，是由n個(gè)具有相同數(shù)據(jù)類型的數(shù)據(jù)元素構(gòu)成的有限序列隊(duì)列的抽象數(shù)據(jù)類型描述129隊(duì)列的抽象數(shù)據(jù)Java抽象類包含了隊(duì)列的主要基本操作，如果要使用這個(gè)接口，還需要具體的類來實(shí)現(xiàn)。Java抽象類的實(shí)現(xiàn)方法主要有以下兩種。(1)基于順序存儲(chǔ)的實(shí)現(xiàn)，為順序隊(duì)列。(2)基于鏈?zhǔn)酱鎯?chǔ)的實(shí)現(xiàn)，為鏈隊(duì)列。順序隊(duì)列130入隊(duì)操作

出隊(duì)操作順序隊(duì)列的存儲(chǔ)結(jié)構(gòu)與順序棧類似，可用數(shù)組實(shí)現(xiàn)，因?yàn)槿腙?duì)和出隊(duì)操作分別在隊(duì)尾和隊(duì)首進(jìn)行，所以增加變量front來指示隊(duì)首元素的位置，rear指示隊(duì)尾元素的下一個(gè)存儲(chǔ)單元的位置。順序隊(duì)列131順序隊(duì)列類的Java語言描述如下：132順序隊(duì)列類的Java語言描述如下：順序隊(duì)列循環(huán)隊(duì)列133分析發(fā)現(xiàn)，順序隊(duì)列的多次入隊(duì)和出隊(duì)操作會(huì)造成有存儲(chǔ)空間卻不能進(jìn)行入隊(duì)操作的“假溢出”現(xiàn)象。假溢出順序隊(duì)列之所以會(huì)出現(xiàn)“假溢出”現(xiàn)象是因?yàn)轫樞蜿?duì)列的存儲(chǔ)單元沒有重復(fù)使用機(jī)制，為了解決順序隊(duì)列因數(shù)組下標(biāo)越界而引起的“溢出”問題，可將順序序列的首尾相連，形成循環(huán)順序隊(duì)列。134循環(huán)隊(duì)列循環(huán)順序隊(duì)列進(jìn)行入隊(duì)和出隊(duì)操作后的狀態(tài)變化如圖：有新的問題產(chǎn)生——隊(duì)空和隊(duì)滿的判定條件都變?yōu)閒ront==rear，為了解決這一問題，可少利用一個(gè)存儲(chǔ)單元，隊(duì)列最多存放maxSize-1個(gè)數(shù)據(jù)元素，隊(duì)空的判定條件為front==rear，隊(duì)滿的判定條件為front=(rear+1)%maxSize。135循環(huán)隊(duì)列循環(huán)順序隊(duì)列類和順序隊(duì)列類的Java語言描述相似，僅是指示變量front和rear的修改以及隊(duì)滿的判定條件發(fā)生了變化。136循環(huán)隊(duì)列循環(huán)順序隊(duì)列類和順序隊(duì)列類的Java語言描述相似，僅是指示變量front和rear的修改以及隊(duì)滿的判定條件發(fā)生了變化。137例題假定用于順序存儲(chǔ)一個(gè)隊(duì)列的數(shù)組的長(zhǎng)度為N，隊(duì)首和隊(duì)尾指針分別為front和rear，寫出求此隊(duì)列長(zhǎng)度(即所含元素個(gè)數(shù))的公式。解：當(dāng)rear大于等于front時(shí)隊(duì)列長(zhǎng)度為rear-front，也可以表示為(rear-front+N)%N；當(dāng)rear小于front時(shí)隊(duì)列被分成兩個(gè)部分，前部分在數(shù)組尾部，其元素個(gè)數(shù)為N-1-front，后部分在數(shù)組首部，其元素個(gè)數(shù)為rear+1，兩者相加為rear-front+N。綜上所述，在任何情況下隊(duì)列長(zhǎng)度的計(jì)算公式都為(rear-front+N)%N。在執(zhí)行操作序列EnQueue(1)、EnQueue(3)、DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后隊(duì)首元素和隊(duì)尾元素分別是什么？EnQueue(k)表示整數(shù)k入隊(duì)，DeQueue表示隊(duì)首元素出隊(duì)。138鏈隊(duì)列鏈隊(duì)列用單鏈表實(shí)現(xiàn)，由于入隊(duì)和出隊(duì)分別在隊(duì)列的隊(duì)尾和隊(duì)首進(jìn)行，不存在在隊(duì)列的任意位置進(jìn)行插入和刪除的情況，所以不需要設(shè)置頭結(jié)點(diǎn)，只需要將指針front和rear分別指向隊(duì)首結(jié)點(diǎn)和隊(duì)尾結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)的指針域指向其后繼結(jié)點(diǎn)即可。入隊(duì)操作

出隊(duì)操作139鏈隊(duì)列順序隊(duì)列類的Java語言描述如下：利用Node類，鏈隊(duì)列的Java語言描述如圖。140鏈隊(duì)列順序隊(duì)列類的Java語言描述如下：利用Node類，鏈隊(duì)列的Java語言描述如圖。優(yōu)先級(jí)隊(duì)列

有些應(yīng)用中的排隊(duì)等待問題僅按照“先來先服務(wù)”原則不能滿足要求，還需要將任務(wù)的重要程度作為排隊(duì)的依據(jù)。例如操作系統(tǒng)中的進(jìn)程調(diào)度管理，每個(gè)進(jìn)程都有一個(gè)優(yōu)先級(jí)值表示進(jìn)程的緊急程度，優(yōu)先級(jí)高的進(jìn)程先執(zhí)行，同級(jí)進(jìn)程按照先進(jìn)先出原則排隊(duì)等待，因此操作系統(tǒng)需要使用優(yōu)先級(jí)隊(duì)列來管理和調(diào)度進(jìn)程。

優(yōu)先級(jí)隊(duì)列是在普通隊(duì)列的基礎(chǔ)之上將隊(duì)列中的數(shù)據(jù)元素按照關(guān)鍵字的值進(jìn)行有序排列。優(yōu)先級(jí)隊(duì)列在隊(duì)首進(jìn)行刪除操作，但為了保證隊(duì)列的優(yōu)先級(jí)順序，插入操作不一定在隊(duì)尾進(jìn)行，而是按照優(yōu)先級(jí)插入到隊(duì)列的合適位置。

和其他數(shù)據(jù)結(jié)構(gòu)類似，優(yōu)先級(jí)隊(duì)列也可以采用順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)。但為了快速地訪問優(yōu)先級(jí)高的元素以及快速地插入數(shù)據(jù)元素，通常使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。141優(yōu)先級(jí)隊(duì)列優(yōu)先級(jí)隊(duì)列結(jié)點(diǎn)類描述在此優(yōu)先隊(duì)級(jí)列中，數(shù)據(jù)元素的優(yōu)先級(jí)別依據(jù)優(yōu)先數(shù)的大小進(jìn)行判定，即優(yōu)先數(shù)越小優(yōu)先級(jí)別越大。優(yōu)先級(jí)隊(duì)列優(yōu)先級(jí)隊(duì)列類的描述及實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列（續(xù)）優(yōu)先級(jí)隊(duì)列類的描述及實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列（續(xù)）優(yōu)先級(jí)隊(duì)列類的描述及實(shí)現(xiàn)例題利用優(yōu)先級(jí)隊(duì)列模仿操作系統(tǒng)的進(jìn)程管理問題，要求優(yōu)先級(jí)高的進(jìn)程先獲得CPU，優(yōu)先級(jí)相同的進(jìn)程先到的先獲得CPU。假設(shè)操作系統(tǒng)中的進(jìn)程由進(jìn)程號(hào)和進(jìn)程優(yōu)先級(jí)兩部分組成。棧與隊(duì)列的比較147相同點(diǎn)（1）均為線性結(jié)構(gòu)，數(shù)據(jù)元素間具有“一對(duì)一”的邏輯關(guān)系；（2）都有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種實(shí)現(xiàn)方式；（3）操作受限，插入操作均在表尾進(jìn)行(優(yōu)先級(jí)隊(duì)列除外)；（4）插入與刪除操作都具有常數(shù)時(shí)間不同點(diǎn)（1）棧刪除操作在表尾進(jìn)行，具有后進(jìn)先出特性；隊(duì)列的刪除操作在表頭進(jìn)行，具有先進(jìn)先出特性。（2）順序?？梢詫?shí)現(xiàn)多?？臻g共享，而順序隊(duì)列則不同小1)棧是一種特殊的線性表，它只允許在棧頂進(jìn)行插入和刪除操作，具有后進(jìn)先出的特性，各種運(yùn)算的時(shí)間復(fù)雜度為O(1)。棧采用順序存儲(chǔ)結(jié)構(gòu)或者鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。(3)循環(huán)隊(duì)列是將順序隊(duì)列的首尾相連，解決“假溢出”現(xiàn)象的發(fā)生。(2)隊(duì)列是一種特殊的線性表，它只允許在表頭進(jìn)行刪除操作、在表尾進(jìn)行插入操作，具有先進(jìn)先出的特性，各種運(yùn)算的時(shí)間復(fù)雜度為O(1)。隊(duì)列采用順序存儲(chǔ)結(jié)構(gòu)或者鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。(4)優(yōu)先級(jí)隊(duì)列是在普通隊(duì)列的基礎(chǔ)之上將隊(duì)列中的數(shù)據(jù)元素按照關(guān)鍵字的值進(jìn)行有序排列。在表頭進(jìn)行刪除操作，插入操作按照優(yōu)先級(jí)插入到隊(duì)列的合適位置。謝謝觀看第2章串和數(shù)組

目錄151串的基本概念、抽象描述和分類串的模式匹配數(shù)組的概念、特性、遍歷特殊矩陣的壓縮存儲(chǔ)4.14.24.34.4總結(jié)4.54.1串的基本概念、抽象描述和分類4.1.1串的基本概念153順序存儲(chǔ)字符串線性表字符串也叫串，是由字符組成的有限序列，是一種常用的非數(shù)值數(shù)據(jù)。串的邏輯結(jié)構(gòu)是線性表，串是一種特殊的線性表，其每個(gè)數(shù)據(jù)元素都是一個(gè)字符。但是串的操作特點(diǎn)與線性表不同，主要是對(duì)子串進(jìn)行操作，通常采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。字符串可以表示為str="a0a1…ai…an-1"，其中str為串名，也叫串變量；i為字符ai在串中的位序號(hào)；雙引號(hào)中的字符序列稱為串值；n為串的長(zhǎng)度；當(dāng)n=0時(shí)字符串不包含任何字符，為空串；當(dāng)字符串由一個(gè)或多個(gè)空白字符組成時(shí)為空白串。串變量4.1.1串的基本概念154字符串中任意個(gè)連續(xù)字符組成的子序列稱為字符串的子串，此字符串為該子串的主串。子串在主串中的位置是指子串在主串中第一次出現(xiàn)時(shí)的第一個(gè)字符在主串中的位置?？沾侨我獯淖哟總€(gè)字符串都是其自身的子串，除自身外，主串的其他子串稱為主串的真子串。串的比較規(guī)則和字符的比較規(guī)則有關(guān)，字符的比較規(guī)則由所屬的字符集的編碼決定。兩個(gè)串相等是指串長(zhǎng)度相同并且各對(duì)應(yīng)位置上的字符也相同。兩個(gè)串的大小由對(duì)應(yīng)位置上的首個(gè)不同字符的大小決定，字符比較次序是從頭開始依次向后。當(dāng)兩個(gè)串的長(zhǎng)度不等而對(duì)應(yīng)位置上的字符都相同時(shí)較長(zhǎng)的串定義為較大。4.1.2串的抽象數(shù)據(jù)類型描述155字符串是數(shù)據(jù)元素類型為字符的線性表，其抽象數(shù)據(jù)類型描述與線性表相似，又根據(jù)串在實(shí)際問題中的應(yīng)用抽象出串的基本操作，可得串的抽象數(shù)據(jù)類型Java語言描述如左邊所示。4.1.2串的抽象數(shù)據(jù)類型描述156字符串的抽象數(shù)據(jù)類型Java抽象類包含了串的主要基本操作，如果要使用這個(gè)接口，還需要具體的類來實(shí)現(xiàn)。串的Java抽象類的實(shí)現(xiàn)方法主要有以下兩種：(1)基于順序存儲(chǔ)的實(shí)現(xiàn)，為順序串；(2)基于鏈?zhǔn)酱鎯?chǔ)的實(shí)現(xiàn)，為鏈串。4.1.3順序串1571.順序串的描述：順序串與順序表的邏輯結(jié)構(gòu)相同，存儲(chǔ)結(jié)構(gòu)類似，均可用數(shù)組來存儲(chǔ)數(shù)據(jù)元素。但串具有獨(dú)特的不同于線性表的操作，屬于特殊類型的線性表。下圖所示為順序串。4.1.3順序串158實(shí)現(xiàn)IString抽象類的順序串類的Java語言描述如下：4.1.3順序串159實(shí)現(xiàn)IString抽象類的順序串類的Java語言描述如下：4.1.3順序串160實(shí)現(xiàn)IString抽象類的順序串類的Java語言描述如下：4.1.3順序串161實(shí)現(xiàn)IString抽象類的順序串類的Java語言描述如下：4.1.3順序串162實(shí)現(xiàn)IString抽象類的順序串類的Java語言描述如下：4.1.3順序串1632.順序串基本操作的實(shí)現(xiàn)

順序串有許多基本操作，例如，求子串操作、插入操作、刪除操作、連接操作、比較操作。

下面，我們對(duì)這幾個(gè)操作逐個(gè)使用Java實(shí)現(xiàn)。4.1.3順序串1641)求子串操作求子串操作subString(begin,end)是返回長(zhǎng)度為n的字符串中位序號(hào)從begin到end-1的字符序列，其中0≤begin≤n-1，begin<end≤n。其主要步驟如下：(1)檢查參數(shù)begin和end是否滿足0≤begin≤n-1和begin<end≤n，若不滿足，拋出異常。(2)返回位序號(hào)為begin到end-1的字符序列。代碼如左圖所示4.1.3順序串1652)插入操作插入操作insert(i,str)是在長(zhǎng)度為n的字符串的第i個(gè)元素之前插入串str，其中0≤i≤n。其主要步驟如下：(1)判斷參數(shù)i是否滿足0≤i≤n，若不滿足，則拋出異常。(2)重新分配存儲(chǔ)空間為n+m，m為插入的字符串str的長(zhǎng)度。(3)將第i個(gè)及之后的數(shù)據(jù)元素向后移動(dòng)m個(gè)存儲(chǔ)單元。(4)將str插入到字符串從i開始的位置。4.1.3順序串1663)刪除操作刪除操作delete(begin,end)是將長(zhǎng)度為n的字符串的位序號(hào)為begin到end-1的元素刪除，其中參數(shù)begin和end滿足0≤begin≤curLen-1和begin<end≤curLen。其主要步驟如下：(1)判斷參數(shù)begin和end是否滿足0≤begin≤curLen-1和begin<end≤curLen，若不滿足，則拋出異常。(2)將字符串位序號(hào)為end的數(shù)據(jù)元素及其之后的數(shù)據(jù)元素向前移動(dòng)到位序號(hào)為begin的位置。(3)字符串長(zhǎng)度減小end-begin。4.1.3順序串1674)連接操作5)比較操作4)concat(str)是將串str插入到字符串的尾部，此時(shí)調(diào)用insert(curLen,str)即可實(shí)現(xiàn)。5)比較操作compareTo(str)是將字符串與串str按照字典序進(jìn)行比較。若當(dāng)前字符串較大，返回1；若相等，返回0。若當(dāng)前字符串較小，返回-1。其主要步驟如下：(1)確定需要比較的字符的個(gè)數(shù)n為兩個(gè)字符串長(zhǎng)度的較小值。(2)從下標(biāo)0至n-1依次進(jìn)行比較。4.1.3順序串168【例4.1】編寫一個(gè)程序，完成構(gòu)造串、判斷串是否為空、返回串的長(zhǎng)度、求子串等操作。示例答案：4.1.4鏈串169鏈串的描述：鏈串采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)類似，可以采用單鏈表存儲(chǔ)串值。鏈串由一系列大小相同的結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)用數(shù)據(jù)域存放字符，指針域存放指向下一個(gè)結(jié)點(diǎn)的指針。與線性表不同的是每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域可以是一個(gè)字符或者多個(gè)字符。若每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)橐粋€(gè)字符，這種鏈表稱為單字符鏈表；若每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)槎鄠€(gè)字符，則稱為塊鏈表。在塊鏈表中每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域不一定被字符占滿，可通過添加空字符或者其他非串值字符來簡(jiǎn)化操作。如圖所示為兩種不同類型的鏈串。4.1.4鏈串170鏈串的優(yōu)缺點(diǎn)：在串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，單字符鏈表的插入、刪除操作較為簡(jiǎn)單，但存儲(chǔ)效率低。塊鏈表雖然存儲(chǔ)效率較高但插入、刪除操作需要移動(dòng)字符，較為復(fù)雜。此外，與順序串相比，鏈串需要從頭部開始遍歷才能訪問某個(gè)位置的元素。所以用戶在應(yīng)用中需要根據(jù)實(shí)際情況選擇合適的存儲(chǔ)結(jié)構(gòu)。4.2串的模式匹配4.2串的模式匹OAL串的模式匹配也叫查找定位，指的是在當(dāng)前串中尋找模式串的過程，主要的模式匹配算法有BruteForce算法和KMP算法。4.2.1BruteForce算法173BruteForce算法從主串的第一個(gè)字符開始和模式串的第一個(gè)字符進(jìn)行比較，若相等，則繼續(xù)比較后續(xù)字符；否則從主串的第二個(gè)字符開始重新和模式串進(jìn)行比較。依此類推，直到模式串的每個(gè)字符依次與主串的字符相等，匹配成功。4.2.1BruteForce算法174BruteForce算法的實(shí)現(xiàn)簡(jiǎn)單，但效率非常低。m為模式串的長(zhǎng)度，n為主串的長(zhǎng)度。（1）最好情況：第一次匹配即成功，比較次數(shù)為模式串的長(zhǎng)度m，時(shí)間復(fù)雜度為O(m)。（2）最壞情況：每次匹配比較至模式串的最后一個(gè)字符，并且比較了目標(biāo)串中所有長(zhǎng)度為m的子串，此時(shí)的時(shí)間復(fù)雜度為O(m×n)。缺點(diǎn)：每次匹配沒有利用前一次匹配的比較結(jié)果，使算法中存在較多的重復(fù)比較，降低了算法的效率；如果利用部分字符匹配的結(jié)果，可將算法的效率提高。因此提出了KMP算法，在下一節(jié)進(jìn)行介紹。4.2.2KMP算法1751.算法分析設(shè)主串為s="ababcabdabcabca"、模式串為p="abcabc"，指針i、j分別指示主串和模式串所比較字符的位序號(hào)。當(dāng)某次匹配不成功時(shí)有si≠pj，并且si-jsi-j+1…si-1=p0p1…pj-1。此時(shí)需要尋找前綴子串p0p1…pk-1=pj-kpj-k+1…pj-1，其中0<k<j，這時(shí)候即滿足si-ksi-k+1…si-1=p0p1…pk-1，下一次匹配可直接比較si和pk。此外，為了減少比較次數(shù)，k應(yīng)取最大值，即p0p1…pk-1應(yīng)為滿足此性質(zhì)的最長(zhǎng)前綴子串。若k不存在，下一次匹配則直接比較si和p0。4.2.2KMP算法1762.K值的計(jì)算通過前面的分析已知，每次模式串開始比較的位置（即k的值）僅與模式串本身有關(guān)。一般用next[j]來表示pj對(duì)應(yīng)的k值。初始時(shí)可定義next[0]=-1，next[1]=0。設(shè)next[j]=k，則p0p1…pk-1=pj-kpj-k+1…pj-1，k為滿足等式的最大值。計(jì)算next[j+1]的值。(1)若pk=pj，則存在p0p1…pk-1pk=pj-kpj-k+1…pj-1pj，此時(shí)next[j+1]=k+1。(2)若pk≠pj，可以把計(jì)算next[j]的值的問題看成新的模式匹配過程，主串為p，模式串為p的前綴子串。出現(xiàn)不匹配，應(yīng)將模式串的比較位置變?yōu)閗′=next[k]，若pj=p_(k^')，則next[j+1]=k′+1=next[k]+1，否則繼續(xù)執(zhí)行步驟(2)，直到pj=pk，或者當(dāng)k=0并且pj≠pk時(shí)next[j+1]=0。4.2.2KMP算法1772.K值的計(jì)算代碼實(shí)現(xiàn)：4.2.2KMP算法1783.KMP算法步驟設(shè)主串的長(zhǎng)度為n、模式串的長(zhǎng)度為m，求next[]的時(shí)間復(fù)雜度為O(m)。在KMP中，因主串的下標(biāo)不需要回退，比較次數(shù)最多為n-m+1，所以KMP算法的時(shí)間復(fù)雜度為O(m+n)。KMP算法的主要步驟如下。(1)計(jì)算模式串的next[]函數(shù)值。(2)i為主串的比較字符位序號(hào)，j為模式串的比較字符位序號(hào)。當(dāng)字符相等時(shí)，i、j分別加1后繼續(xù)比較；否則i的值不變，j=next[j]，繼續(xù)比較。(3)重復(fù)步驟(2)，直到j(luò)等于模式串的長(zhǎng)度時(shí)匹配成功，否則匹配失敗。4.2.2KMP算法1793.KMP算法步驟小測(cè)試：請(qǐng)計(jì)算str=“abcababc”的next[j]的值

參考答案：當(dāng)j=0時(shí)，next[0]=-1;當(dāng)j=1時(shí)，next[1]=0;當(dāng)j=2時(shí)，next[2]=0;當(dāng)j=3時(shí)，next[3]=0;當(dāng)j=4時(shí)，next[4]=1;當(dāng)j=5時(shí)，next[5]=2;當(dāng)j=6時(shí)，next[6]=1;當(dāng)j=7時(shí)，next[7]=2。4.3數(shù)組的概念、特性和遍歷4.3.1數(shù)組的基本概念數(shù)組是n個(gè)具有相同數(shù)據(jù)類型的數(shù)據(jù)元素構(gòu)成的集合，數(shù)組元素按某種次序存儲(chǔ)在地址連續(xù)的存儲(chǔ)單元中,是順序存儲(chǔ)的隨機(jī)存儲(chǔ)結(jié)構(gòu)。數(shù)組元素在數(shù)組中的位置稱為數(shù)組元素的下標(biāo)，用戶通過下標(biāo)可以訪問相應(yīng)的數(shù)組元素。數(shù)組下標(biāo)的個(gè)數(shù)是數(shù)組的維數(shù)，具有一個(gè)下標(biāo)的數(shù)組叫一維數(shù)組，具有兩個(gè)下標(biāo)的數(shù)組叫二維數(shù)組。一維數(shù)組的邏輯結(jié)構(gòu)是線性表，多維數(shù)組是線性表的擴(kuò)展。二維數(shù)組可以看成數(shù)組元素是一維數(shù)組的數(shù)組。下圖所示為二維數(shù)組的矩陣表示。4.3.1數(shù)組的基本概念二維數(shù)組中的每個(gè)數(shù)據(jù)元素ai,j都受到兩個(gè)關(guān)系的約束，即行關(guān)系和列關(guān)系。ai.,j+1是ai,j在行關(guān)系中的后繼元素；ai+1,j是ai,j在列關(guān)系中的后繼元素。因?yàn)槎S數(shù)組可以看成數(shù)組元素是一維數(shù)組的數(shù)組，所以二維數(shù)組也可看成線性表，即A=(a0,a1,…,an-1)，其中每個(gè)數(shù)據(jù)元素ai是一個(gè)列向量的線性表，即ai=(a0i,a1i,…,am-1i);或者表述為A=(a0,a1,…,am-1)，其中每個(gè)數(shù)據(jù)元素ai是一個(gè)行向量的線性表，即ai=(a0i,a1i,…,an-1i)。其中，每個(gè)元素同時(shí)屬于兩個(gè)線性表，第i行的線性表和第j列的線性表，具體可以分析如下：（1）a0,0是起點(diǎn)，沒有前驅(qū)元素；am-1,n-1是終點(diǎn)，沒有后繼元素。（2）邊界元素ai,0和a0,j（1≤j<n,1≤i<m）只有一個(gè)前驅(qū)元素；ai,n-1和am-1,j（0≤j<n-1,1≤i<m-1）只有一個(gè)后繼元素。（3）ai,j（1≤j<n-1,1≤i<m-1）有兩個(gè)前驅(qū)元素和兩個(gè)后繼元素。4.3.2數(shù)組的特性數(shù)組元素被存放在一組地址連續(xù)的存儲(chǔ)單元里，并且每個(gè)數(shù)據(jù)元素的大小相同，故只要已知首地址和每個(gè)數(shù)據(jù)元素占用的內(nèi)存單元大小即可求出數(shù)組中任意數(shù)據(jù)元素的存儲(chǔ)地址。對(duì)于一維數(shù)組A[n]，數(shù)據(jù)元素的存儲(chǔ)地址為L(zhǎng)oc(i)=Loc(0)+i×L(0≤i<n)，其中Loc(i)是第i個(gè)元素的存儲(chǔ)地址，Loc(0)是數(shù)組的首地址，L是每個(gè)數(shù)據(jù)元素占用的字節(jié)數(shù)。對(duì)于二維數(shù)組，采用行優(yōu)先順序進(jìn)行存儲(chǔ)，即先存儲(chǔ)數(shù)組的第一行，再依次存儲(chǔ)其他各行。對(duì)于一個(gè)n×m的數(shù)組A[n][m]，數(shù)組元素的存儲(chǔ)地址為L(zhǎng)oc(i,j)=Loc(0,0)+(i×m+j)×L，其中Loc(i,j)是第i行第j列的數(shù)組元素的存儲(chǔ)地址，Loc(0,0)是數(shù)組的首地址，L是每個(gè)數(shù)據(jù)元素占用的字節(jié)數(shù)。4.3.2數(shù)組的特性將計(jì)算數(shù)組元素的存儲(chǔ)位置的公式推廣到一般情況，可得n維數(shù)組A[m1][m2]…[mn]的數(shù)據(jù)元素的存儲(chǔ)位置：在n維數(shù)組中，計(jì)算數(shù)組中數(shù)據(jù)元素的存儲(chǔ)地址的時(shí)間復(fù)雜度為O(1)，n維數(shù)組是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。4.3.3數(shù)組的遍歷185行主序數(shù)組遍歷列主序?qū)ΧS數(shù)組進(jìn)行遍歷操作有兩種次序，即行主序和列主序。（1）行主序：以行序?yàn)橹饕涡颍葱行蜻f增訪問數(shù)組的每行，同一行按列序遞增訪問數(shù)組元素。（2）列主序：以列序?yàn)橹饕涡?，按列序遞增訪問數(shù)組的每列，同一列按行序遞增訪問數(shù)組元素。4.3.3數(shù)組的遍歷186SWOT舉例：請(qǐng)你設(shè)計(jì)一個(gè)算法，求二維數(shù)組A[n,n]的兩條對(duì)角線元素之和。答案示例：4.4特殊矩陣的壓縮存儲(chǔ)4.4特殊矩陣的壓縮存儲(chǔ)188在科學(xué)技術(shù)和工程計(jì)算的許多領(lǐng)域，矩陣是數(shù)值分析問題研究的對(duì)象。特殊矩陣是具有許多相同數(shù)據(jù)元素或者零元素且數(shù)據(jù)元素的分布具有一定規(guī)律的矩陣，例如對(duì)稱矩陣、三角矩陣和對(duì)角矩陣。數(shù)據(jù)壓縮技術(shù)是計(jì)算機(jī)軟件領(lǐng)域研究的一個(gè)重要問題，圖像、音頻、視頻等多媒體信息都需要進(jìn)行數(shù)據(jù)壓縮存儲(chǔ)。本節(jié)將以特殊矩陣為例介紹矩陣的壓縮存儲(chǔ)。矩陣采用二維數(shù)組進(jìn)行存儲(chǔ)，至少占用m×n個(gè)存儲(chǔ)單元。當(dāng)矩陣的階數(shù)很大時(shí)，矩陣所占用的存儲(chǔ)空間巨大，因此需要研究矩陣的壓縮存儲(chǔ)問題，根據(jù)不同矩陣的特點(diǎn)設(shè)計(jì)不同的壓縮存儲(chǔ)方法，節(jié)省存儲(chǔ)空間，同時(shí)保證采用壓縮存儲(chǔ)的矩陣仍然能夠正確地進(jìn)行各種矩陣運(yùn)算。4.4特殊矩陣的壓縮存儲(chǔ)常用的矩陣壓縮存儲(chǔ)方法主要有以下兩種：(1)對(duì)于零元素分布有規(guī)律的特殊矩陣，采用線性壓縮或三角形的二維數(shù)組，只存儲(chǔ)有規(guī)律的部分元素。(2)對(duì)于零元素分布沒有規(guī)律的特殊矩陣，只存儲(chǔ)非零元素。下面，我們分別介紹一下不同類型的矩陣壓縮存儲(chǔ)方式4.4.1三角矩陣的壓縮存儲(chǔ)三角矩陣包括上三角矩陣和下三角矩陣。假如是一個(gè)n階矩陣，由n（n+1）/2個(gè)元素組成。當(dāng)i<j時(shí)矩陣中的數(shù)據(jù)元素滿足=0，矩陣為下三角矩陣；當(dāng)i>j時(shí)，矩陣中的數(shù)據(jù)元素滿足=0，矩陣為上三角矩陣。三角矩陣中具有近一半的分布有規(guī)律的零元素，所以三角矩陣采取只存儲(chǔ)主對(duì)角線以及上/下三角部分的矩陣元素的壓縮方法，主要分為以下兩種：線性壓縮存儲(chǔ)2.使用三角形的二維數(shù)組壓縮存儲(chǔ)4.4.1三角矩陣的壓縮存儲(chǔ)線性壓縮存儲(chǔ)將下三角矩陣的主對(duì)角線及其以下元素按行主序順序壓縮成線性存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)元素的個(gè)數(shù)為n（n+1）/2，其中元素的存儲(chǔ)地址如下：其中，注意L為數(shù)據(jù)元素所占據(jù)存儲(chǔ)空間的字節(jié)數(shù)。計(jì)算各數(shù)據(jù)元素的存儲(chǔ)地址的時(shí)間復(fù)雜度為O（1）,三角矩陣的線性壓縮存儲(chǔ)結(jié)構(gòu)是隨機(jī)存儲(chǔ)結(jié)構(gòu)。4.4.1三角矩陣的壓縮存儲(chǔ)2.使用三角形的二維數(shù)組壓縮存儲(chǔ)三角形的二維數(shù)組實(shí)際上是一種動(dòng)態(tài)數(shù)組結(jié)構(gòu)，第i行一維數(shù)組的長(zhǎng)度為i+1，存儲(chǔ)在mat[i][j]中，如圖4.4所示。計(jì)算各數(shù)據(jù)元素的存儲(chǔ)地址的時(shí)間復(fù)雜度為O（1）,此壓縮存儲(chǔ)結(jié)構(gòu)是隨機(jī)存儲(chǔ)結(jié)構(gòu)。4.4.2對(duì)稱矩陣的壓縮存儲(chǔ)n階對(duì)稱矩陣是指一個(gè)n階矩陣中的數(shù)據(jù)元素滿足ai,j=aj,i。對(duì)稱矩陣在進(jìn)行壓縮存儲(chǔ)時(shí)只存儲(chǔ)主對(duì)角線和上/下部分?jǐn)?shù)據(jù)元素，即將對(duì)稱矩陣的主對(duì)角線及其上/下部分?jǐn)?shù)據(jù)元素按行主序順序壓縮成線性存儲(chǔ)，占用n（n+1）/2個(gè)存儲(chǔ)單元,矩陣元素的線性壓縮存儲(chǔ)地址為：4.4.3對(duì)角矩陣的壓縮存儲(chǔ)如果一個(gè)矩陣的所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域，則稱該矩陣為對(duì)角矩陣。它是一個(gè)n階矩陣，除了主對(duì)角線上的元素，其科元素均為0，則是主對(duì)角矩陣；除了主對(duì)角線上及主對(duì)角線上下各一個(gè)元素外，其余元素均為0，為三對(duì)角矩陣。在壓縮存儲(chǔ)對(duì)角矩陣時(shí)，只存儲(chǔ)主對(duì)角線及其兩側(cè)部分的元素。如壓縮存儲(chǔ)主對(duì)角矩陣，將主對(duì)角元素順序壓縮成線性存儲(chǔ)，存儲(chǔ)元素個(gè)數(shù)為n，矩陣數(shù)據(jù)元素的線性壓縮存儲(chǔ)地址為：4.4.4

稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣是指矩陣中的非零元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素個(gè)數(shù)并且非零元素的分布沒有規(guī)律的矩陣。設(shè)矩陣中有t個(gè)非零元素，非零元素占元素總數(shù)的比例稱為矩陣的稀疏因子，通常稀疏因子小于0.05的矩陣稱為稀疏矩陣。一般使用以下幾種方法進(jìn)行稀疏矩陣的壓縮存儲(chǔ)。稀疏矩陣的非零元素三元組稀疏矩陣的十字鏈表存儲(chǔ)4.4.4

稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的非零元素三元組稀疏矩陣的壓縮存儲(chǔ)原則是只存儲(chǔ)矩陣中的非零元素，而僅存儲(chǔ)非零元素是不夠的，必須存儲(chǔ)該元素在矩陣中的位置。矩陣元素的行號(hào)、列號(hào)和元素值稱為該元素的三元組。在Java語言中稀疏矩陣的三元組表示的結(jié)點(diǎn)結(jié)構(gòu)定義如下：4.4.4

稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的非零元素三元組稀疏矩陣的三元組順序表類的定義如下：4.4.4

稀疏矩陣的壓縮存儲(chǔ)2.稀疏矩陣的十字鏈表存儲(chǔ)當(dāng)稀疏矩陣中非零元素的位置或個(gè)數(shù)經(jīng)常發(fā)生變化時(shí)不宜采用三元組順序表存儲(chǔ)結(jié)構(gòu)，而應(yīng)該采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。十字鏈表是稀疏矩陣的另一種存儲(chǔ)結(jié)構(gòu)，在十字鏈表中稀疏矩陣的非零元素用一個(gè)結(jié)點(diǎn)來表示，每個(gè)結(jié)點(diǎn)由5個(gè)域組成。row域存放該元素的行號(hào)，column域存放該元素的列號(hào)，value域存放該元素的值，right域存放與該元素同行的下一個(gè)非零元素結(jié)點(diǎn)的指針，down域存放與該元素同列的下一個(gè)非零元素結(jié)點(diǎn)的指針。每個(gè)非零數(shù)據(jù)元素結(jié)點(diǎn)既是某個(gè)行鏈表中的一個(gè)結(jié)點(diǎn)，也是某個(gè)列鏈表中的結(jié)點(diǎn)，整個(gè)稀疏矩陣構(gòu)成了一個(gè)十字交叉的鏈表，這樣的鏈表就稱為十字鏈表。4.4.4

稀疏矩陣的壓縮存儲(chǔ)2.稀疏矩陣的十字鏈表存儲(chǔ)在Java語言中可以將稀疏矩陣的十字鏈表表示的結(jié)點(diǎn)結(jié)構(gòu)定義如下：稀疏矩陣的十字鏈表類的定義如右：4.4.4

稀疏矩陣的壓縮存儲(chǔ)2.稀疏矩陣的十字鏈表存儲(chǔ)在Java語言中可以將稀疏矩陣的十字鏈表表示的結(jié)點(diǎn)結(jié)構(gòu)定義如下：稀疏矩陣的十字鏈表類的定義如右：4.4.4

稀疏矩陣的壓縮存儲(chǔ)下面，我們做一個(gè)例題，來深入了解不同存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn):已知A為稀疏矩陣，試從空間和時(shí)間角度比較采用二維數(shù)組和三元組順序表兩種不同的存儲(chǔ)結(jié)構(gòu)完成求運(yùn)算的優(yōu)缺點(diǎn)。參考答案:設(shè)稀疏矩陣為m行n列，如果采用二維數(shù)組存儲(chǔ)，其空間復(fù)雜度為O(m×n)；因?yàn)橐獙⑺械木仃囋乩奂悠饋?，所以需要用一個(gè)兩層的嵌套循環(huán)，其時(shí)間復(fù)雜度也為O(m×n)。如果采用三元組順序表進(jìn)行壓縮存儲(chǔ)，假設(shè)矩陣中有t個(gè)非零元素，其空間復(fù)雜度為O(t)，將所有的矩陣元素累加起來只需將三元組順序表掃描一遍，其時(shí)間復(fù)雜度也為O(t)。當(dāng)t<<m×n時(shí)采用三元組順序表存儲(chǔ)可獲得較好的時(shí)空性能。4.5總結(jié)4.5總結(jié)203(1)字符串是數(shù)據(jù)元素類型為字符的線性表，串具有插入、刪除、鏈接、查找、比較等基本操作。

(2)字符串具有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種存儲(chǔ)結(jié)構(gòu)。字符串的順序存儲(chǔ)結(jié)構(gòu)叫順序串，與順序表的邏輯結(jié)構(gòu)相同，存儲(chǔ)結(jié)構(gòu)類似，均可用數(shù)組來存儲(chǔ)數(shù)據(jù)元素。字符串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)叫鏈串，和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)類似，可以采用單鏈表存儲(chǔ)串值。鏈串由一系列大小相同的結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)用數(shù)據(jù)域存放字符，指針域存放指向下一個(gè)結(jié)點(diǎn)的指針。

(3)串的模式匹配也叫查找定位，指的是在當(dāng)前串中尋找模式串的過程，主要的模式匹配算法有BruteForce算法和KMP算法。

4.5總結(jié)204(4)數(shù)組是n個(gè)具有相同數(shù)據(jù)類型的數(shù)據(jù)元素構(gòu)成的集合，數(shù)組元素按某種次序存儲(chǔ)在地址連續(xù)的存儲(chǔ)單元中，是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。

(5)特殊矩陣是具有許多相同數(shù)據(jù)元素或者零元素且數(shù)據(jù)元素的分布具有一定規(guī)律的矩陣，例如對(duì)稱矩陣、三角矩陣和對(duì)角矩陣。為了節(jié)省存儲(chǔ)空間，對(duì)矩陣進(jìn)行壓縮存儲(chǔ)。特殊矩陣的壓縮存儲(chǔ)方法是將呈現(xiàn)規(guī)律性分布的、值相同的多個(gè)矩陣元素壓縮存儲(chǔ)到一個(gè)存儲(chǔ)空間。

(6)稀疏矩陣是具有較多零元素，并且非零元素的分布無規(guī)律的矩陣。稀疏矩陣的壓縮存儲(chǔ)是只給非零數(shù)據(jù)元素分配存儲(chǔ)空間。

THEEND第5章樹形結(jié)構(gòu)目錄207樹二叉樹哈夫曼樹及哈夫曼編碼樹和森林第一節(jié)第二節(jié)第三節(jié)第四節(jié)第一節(jié)樹樹的基本概念209提出語義網(wǎng)絡(luò)是奎廉（J.R.Quillian）1968年在研究人類聯(lián)想記憶時(shí)提出的一種心理學(xué)模型。他認(rèn)為記憶是由概念間的聯(lián)系實(shí)現(xiàn)的。隨后在他設(shè)計(jì)的可教式語言理解器（TeachableLanguageComprehendent）中又把它用作為知識(shí)表示方法。1972年，西蒙（Simon）在他的自然語言理解系統(tǒng)中也采用了語義網(wǎng)絡(luò)知識(shí)表示法。1975年,亨德里克（GGHendrix）又對(duì)全稱量詞的表示提出了語義網(wǎng)絡(luò)分區(qū)技術(shù)。目前，語義網(wǎng)絡(luò)已經(jīng)成為人工智能中應(yīng)用較多的一種知識(shí)表示方法，尤其是在自然語言處理方面的應(yīng)用。1.1樹的基本概念210子樹根節(jié)點(diǎn)互不相交樹是數(shù)據(jù)元素之間具有層次關(guān)系的非線性結(jié)構(gòu)，是由n個(gè)結(jié)點(diǎn)構(gòu)成的有限集合，結(jié)點(diǎn)數(shù)為0的樹叫空樹。樹必須滿足以下條件。(1)有且僅有一個(gè)被稱為根的結(jié)點(diǎn)。(2)其余結(jié)點(diǎn)可分為m個(gè)互不相交的有限集合，每個(gè)