數據結構（Java版）課件全套 呂云翔 第1-8章 緒論、線性表、棧和隊列- 查找

第1章緒論

目錄2引言基本概念算法小結第一部分第二部分第三部分第四部分學習目的課程內容數據與數據結構數據類型與抽象數據類型算法的概念算法描述算法分析第一部分引言學習目的4抽象模型實踐積累信息處理從具體問題中抽象出適當的數學模型：分析問題，提取操作的對象，找出操作對象之間的邏輯關系，給出相應的數學模型。設計解決此數學模型的算法。編程、運行、調試，得出結果設計算法學會使用計算機解決實際的應用問題課程內容5過程抽象實現評價邏輯結構基本運算數據表示數據處理儲存結構算法不同數據結構比較和算法性能分析第二部分基本概念數據與數據結構7數據

數據(Data)是能夠被計算機程序識別、存儲、加工和處理的描述客觀事物的數字等符號集合的總稱。數據項

數據項(DataItem)是具有獨立含義的、數據不可分割的最小標識單位，是數據元素的組成部分，也可稱為字段和域。數據元素

數據元素(DataElement)是數據的基本單位，又可稱為元素、結點、頂點和記錄，是一個數據整體中可以標識和訪問的數據單元。數據與數據結構8數據對象

數據對象(DataObject)是性質相同的數據元素的集合，也叫數據元素類，是數據的一個子集，數據元素是數據對象的一個實例。數據結構

數據結構(DataStructure)是相互之間存在著一種或者多種關系的數據元素的集合，數據結構概念包含3個方面的內容，即數據的邏輯結構、數據的存儲結構和數據的操作，只有3個方面的內容相同才能稱為完全相同的數據結構。數據與數據結構

數據的邏輯結構9數據的邏輯結構是指數據元素之間存在的邏輯關系，由數據元素的集合和定義在此集合上的關系組成。兩要素：數據元素的集合、關系的集合。數據與數據結構

數據的邏輯結構分類10邏輯結構樹形結構商業(yè)策略集合圖形結構線性結構集合中元素的關系極為松散，關系為“屬于同一個集合”。線性結構是數據元素中具有線性關系的數據結構，線性結構中的結點存在“一對一”的關系。樹形結構是數據元素之間具有層次關系的一種非線性結構，樹形結構中的結點存在“一對多”的關系。圖形結構也是一種非線性結構，圖形結構中的結點存在“多對多”的關系。數據與數據結構

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

數據的存儲結構分類13數據與數據結構

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

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

基本數據類型：只能作為一個整體來進行處理不可分解的數據類型。

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

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

數據抽象是一種信息隱蔽技術，可利用數據抽象研究復雜對象，忽略次要和實現細節(jié)，抽象出本質特征，抽象層次越高，復用程度越高。

數據抽象是通過抽象數據類型來實現的。抽象數據類型16

抽象數據類型(AbstractDataType，ADT)是從問題的數學模型中抽象出來的邏輯結構及定義在邏輯結構上的一組操作，僅描述了數據的特性和數據操作的語法規(guī)則，隱藏了數據的存儲結構和操作的實現細節(jié)。

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

在一般的面向對象語言中，抽象數據類型通?？梢圆捎贸橄箢惢蚪涌诘姆绞竭M行描述。第三部分算法算法的概念算法的定義

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

算法設計的4個基本目標算法的概念

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

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

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

算法分析

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

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

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

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

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

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

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

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

前驅元素有且僅有一個前驅元素和后繼元素終端結點沒有

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

順序表的基本操作實現61

順序表的基本操作實現62

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

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

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

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

將新結點插入到單鏈表的表頭，讀入的數據順序與結點順序相反。【算法2.9】頭插法。單鏈表的基本操作實現99單鏈表的建立2)尾插法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

稀疏矩陣的壓縮存儲稀疏矩陣的非零元素三元組稀疏矩陣的壓縮存儲原則是只存儲矩陣中的非零元素，而僅存儲非零元素是不夠的，必須存儲該元素在矩陣中的位置。矩陣元素的行號、列號和元素值稱為該元素的三元組。在Java語言中稀疏矩陣的三元組表示的結點結構定義如下：4.4.4

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

稀疏矩陣的壓縮存儲2.稀疏矩陣的十字鏈表存儲當稀疏矩陣中非零元素的位置或個數經常發(fā)生變化時不宜采用三元組順序表存儲結構，而應該采用鏈式存儲結構表示。十字鏈表是稀疏矩陣的另一種存儲結構，在十字鏈表中稀疏矩陣的非零元素用一個結點來表示，每個結點由5個域組成。row域存放該元素的行號，column域存放該元素的列號，value域存放該元素的值，right域存放與該元素同行的下一個非零元素結點的指針，down域存放與該元素同列的下一個非零元素結點的指針。每個非零數據元素結點既是某個行鏈表中的一個結點，也是某個列鏈表中的結點，整個稀疏矩陣構成了一個十字交叉的鏈表，這樣的鏈表就稱為十字鏈表。4.4.4

稀疏矩陣的壓縮存儲2.稀疏矩陣的十字鏈表存儲在Java語言中可以將稀疏矩陣的十字鏈表表示的結點結構定義如下：稀疏矩陣的十字鏈表類的定義如右：4.4.4

稀疏矩陣的壓縮存儲2.稀疏矩陣的十字鏈表存儲在Java語言中可以將稀疏矩陣的十字鏈表表示的結點結構定義如下：稀疏矩陣的十字鏈表類的定義如右：4.4.4

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

(2)字符串具有順序存儲結構和鏈式存儲結構兩種存儲結構。字符串的順序存儲結構叫順序串，與順序表的邏輯結構相同，存儲結構類似，均可用數組來存儲數據元素。字符串的鏈式存儲結構叫鏈串，和線性表的鏈式存儲結構類似，可以采用單鏈表存儲串值。鏈串由一系列大小相同的結點組成，每個結點用數據域存放字符，指針域存放指向下一個結點的指針。

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

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

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

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

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