全套課件-數(shù)據(jù)結構與算法分析

第1章數(shù)據(jù)結構概論1.1什么是數(shù)據(jù)結構1.2基本概念和術語1.2.1數(shù)據(jù)結構的發(fā)展

1.2.2數(shù)據(jù)結構的基本概念和術語

1.3抽象數(shù)據(jù)類型和數(shù)據(jù)結構1.4學習數(shù)據(jù)結構的意義1.5算法1.5.1算法及其性質1.5.2算法描述的分析

1.1什么是數(shù)據(jù)結構信息中的各個數(shù)據(jù)元素并不是孤立存在的，它們之間存在著一定的結構關系。一般說來，使用計算機解決具體問題時，通常需要幾個步驟：分析具體問題得到數(shù)學模型，設計解決數(shù)學模型的算法，編制程序并調試，最后得到最終答案。在數(shù)據(jù)結構中數(shù)據(jù)之間的關系主要有兩種，它們分別是線性關系和非線性關系，其中非線性關系又可以分為樹型關系和圖關系。數(shù)據(jù)的邏輯結構和存儲結構是密不可分的兩個方面，在實現(xiàn)算法時，首先應解決數(shù)據(jù)的存儲問題。1.1什么是數(shù)據(jù)結構數(shù)據(jù)之間既要考慮存儲，又要考慮數(shù)據(jù)單位之間的關系，在確定了存儲結構后，根據(jù)存儲的結構再來確定相應操作的實現(xiàn)方法。簡單說數(shù)據(jù)結構是研究數(shù)據(jù)的存儲、數(shù)據(jù)之間的關系和對數(shù)據(jù)實現(xiàn)各種操作的一門學科。1.1什么是數(shù)據(jù)結構數(shù)據(jù)結構的定義可以記作：Data-Structure=（D，R）其中D是數(shù)據(jù)元素的有限集合，R是D上的關系。一般情況下，“關系”是指數(shù)據(jù)元素之間存在的邏輯關系，也稱為數(shù)據(jù)的邏輯結構。數(shù)據(jù)在計算機內的存儲表示（或映象）稱為數(shù)據(jù)的存儲結構或物理結構。1.1什么是數(shù)據(jù)結構邏輯結構體現(xiàn)的是數(shù)據(jù)元素之間的邏輯關系，換句話說就是從操作對象中抽象出來的數(shù)學模型，因此又稱為抽象結構，通常習慣說的數(shù)據(jù)結構一般就是指的邏輯結構。然而討論數(shù)據(jù)結構的目的是為了在計算機中實現(xiàn)對數(shù)據(jù)的操作，因此還需要研究數(shù)據(jù)的存儲結構。存儲結構是數(shù)據(jù)在計算機內的表示（映象），又稱物理結構。它包括數(shù)據(jù)元素的表示和關系的表示。1.1什么是數(shù)據(jù)結構由于映象的方法不同，所以同一種的邏輯結構可以映象成兩種不同的存儲結構：順序映象（順序存儲結構）和非順序映象（非順序存儲結構）。順序映象的特點是在順序存儲結構（一般用一維數(shù)組）中體現(xiàn)數(shù)據(jù)之間的關系；而非順序存儲結構則一般采用指針實現(xiàn)數(shù)據(jù)之間的關系，包括鏈式存儲結構（鏈表）和散列結構等。數(shù)據(jù)的存儲結構要能夠正確反映數(shù)據(jù)元素之間的邏輯關系。也就是說數(shù)據(jù)的邏輯結構和數(shù)據(jù)的存儲結構是密不可分的兩個方面，任何一個算法的設計取決于選定的邏輯結構，而算法的實現(xiàn)則依賴于采用的存儲結構。1.1什么是數(shù)據(jù)結構順序映象（順序存儲結構）是借助元素在存儲器中位置表示數(shù)據(jù)元素之間的邏輯關系，或邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元里，結點的邏輯關系由存儲單元的鄰接關系來體現(xiàn)；而非順序映象（鏈式存儲結構）是借助元素存儲地址的指針表示元素之間的邏輯關系，或邏輯上相鄰的結點在物理位置上可相鄰，可不相鄰，邏輯關系由附加的指針段表示。1.1什么是數(shù)據(jù)結構數(shù)據(jù)的非順序存儲結構除包括鏈式存儲結構（簡稱鏈表）以外，還有散列存儲結構、索引存儲結構等。鏈式存儲結構是利用指針直接表示數(shù)據(jù)元素之間的關系。散列結構的基本思想是根據(jù)結點的關鍵字，利用散列函數(shù)直接計算出該結點的存儲地址。索引存儲結構是指在存儲結點信息的同時，還建立附加的索引表。索引表的每一項稱為索引項，索引項的一般形式是：（關鍵字，地址）。關鍵字：能夠惟一標識一個結點的那些數(shù)據(jù)項集合；索引存儲結構分為稠密索引和稀疏索引，其中稠密索引是指每個結點在索引表中都有一個索引項的索引表；而稀疏索引是指一組結點在索引表中對應一個索引項的索引表。1.1什么是數(shù)據(jù)結構針對存儲結構，數(shù)據(jù)元素存儲在計算機中，應對每個數(shù)據(jù)元素確定其取值范圍屬性就是數(shù)據(jù)類型。數(shù)據(jù)類型是和數(shù)據(jù)結構密切相關的一個概念，用以刻畫（程序）操作對象的特征。數(shù)據(jù)類型根據(jù)是否允許分解分為原子類型和結構類型，其中原子類型是指其值不可再分的數(shù)據(jù)類型，例如整型、字符型等；而結構類型是指其值可以再分解為若干成分（分量）的數(shù)據(jù)類型，例如數(shù)組的值由若干分量組成。根據(jù)數(shù)據(jù)的結構（邏輯結構和存儲結構）特性在數(shù)據(jù)的生存期間的變動情況，將數(shù)據(jù)結構分為靜態(tài)結構和動態(tài)結構。靜態(tài)結構是指在數(shù)據(jù)存在期不發(fā)生任何變動，例如高級語言中的靜態(tài)數(shù)組；而動態(tài)結構是指在一定范圍內結構的大小可以發(fā)生變動，如使用的堆棧。1.1什么是數(shù)據(jù)結構總之，數(shù)據(jù)結構所要研究的主要內容簡單歸納為以下三個方面：⑴研究數(shù)據(jù)元素之間的客觀聯(lián)系（邏輯結構）；⑵研究數(shù)據(jù)在計算機內部的存儲方法（存儲結構）；⑶研究如何在數(shù)據(jù)的各種結構（邏輯的和物理的）上實施有效的操作或處理（算法）。所以數(shù)據(jù)結構是一門抽象地研究數(shù)據(jù)之間的關系的學科。1.2基本概念和術語1.2.1數(shù)據(jù)結構的發(fā)展數(shù)據(jù)結構作為一門獨立的課程始于1968年，在我國數(shù)據(jù)結構作為一門獨立課程在80年代初，早期的數(shù)據(jù)結構對課程的范圍沒有明確的規(guī)定，數(shù)據(jù)結構的內容幾乎和圖論、樹的理論是相同的，在60到70年代隨著大型程序的出現(xiàn)，軟件也相對獨立，結構程序設計逐步成為程序設計方法學的主要內容，人們已經認識到程序設計的實質就是對所確定的問題選擇一種好的結構，從而設計一種好的算法。1.2基本概念和術語1.2.2數(shù)據(jù)結構的基本概念和術語

數(shù)據(jù)結構是指數(shù)據(jù)之間的相互形式，即數(shù)據(jù)的組織形式。數(shù)據(jù)結構分為邏輯結構和存儲結構。邏輯結構是指數(shù)據(jù)元素之間的邏輯關系；存儲結構是指數(shù)據(jù)元素及其關系在計算機內的表示。數(shù)據(jù)是對客觀事物的符號表示，在計算機科學中是指輸入到計算機中并能夠被計算機識別、存儲和加工處理的符號的總稱。數(shù)據(jù)由數(shù)據(jù)項組成。數(shù)據(jù)項（數(shù)據(jù)元素）是指具有獨立含義的最小識別單位（數(shù)據(jù)中不可分割的最小單位）。數(shù)據(jù)項又稱項或字段。1.2基本概念和術語1.2.2數(shù)據(jù)結構的基本概念和術語數(shù)據(jù)項有邏輯形式（logicalform）和物理形式（physicalform）兩個方面。用ADT給出的數(shù)據(jù)項的定義是它的邏輯形式，數(shù)據(jù)結構中對數(shù)據(jù)項的實現(xiàn)是它的物理形式。在存儲結構中包括了數(shù)據(jù)元素的表示和數(shù)據(jù)元素之間的關系表示。數(shù)據(jù)元素存儲在計算機中，計算機中表示信息的最小單位是二進制數(shù)的一位，稱為位（bit），由若干位組成一個位串表示一個數(shù)據(jù)元素，稱為元素或結點，也可以描述為結點是數(shù)據(jù)處理的數(shù)據(jù)單位，它可能是一條記錄或一個數(shù)據(jù)項或組合數(shù)據(jù)項。對應結點定義根據(jù)結點所處位置的不同可以將表中的結點分為前趨和后繼結點，對表中任意結點，處于該結點之前的所有結點稱為該結點的前趨結點，處于該結點之后的所有結點稱為該結點的后繼結點，與之相鄰的前趨結點稱為直接前趨結點，與之相鄰的后繼結點稱為直接后繼結點；表中的第一個結點稱為開始結點，表中最后一個沒有后繼的結點稱為終端結點。1.3抽象數(shù)據(jù)類型和數(shù)據(jù)結構數(shù)據(jù)類型是指一個值的集合以及在這些值上定義的一組操作的總稱。抽象數(shù)據(jù)類型（AbstractDataType簡稱ADT）是指抽象數(shù)據(jù)組織和與之相關的操作。每一個操作由它的輸入和輸出定義。抽象數(shù)據(jù)類型的定義取決于它的一組邏輯特性，而與其在計算機內的表示和實現(xiàn)無關。抽象數(shù)據(jù)類型可以定義為：（D，S，P）其中D表示數(shù)據(jù)對象，S是D上的關系集，P是對D的基本操作集。1.3抽象數(shù)據(jù)類型和數(shù)據(jù)結構ADT使用偽碼描述為：ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>

數(shù)據(jù)關系：<數(shù)據(jù)關系的定義>

基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名1.4學習數(shù)據(jù)結構的意義算法+數(shù)據(jù)結構=程序。其中數(shù)據(jù)結構是指數(shù)據(jù)邏輯結構和物理結構，算法是對數(shù)據(jù)運算的描述。由此可見程序設計的實質是對具體問題選擇一種好的數(shù)據(jù)結構，再設計一個好的算法，而好的算法通常取決于實際問題的數(shù)據(jù)結構。1.5算法1.5.1算法及其性質算法是指解決問題的一種方法或者一個過程。一個問題可以用多種算法來解決，一個給定的算法解決一個特定的問題。數(shù)據(jù)結構與算法之間存在著密切的關系?？梢哉f不了解施加于數(shù)據(jù)上的算法需求就無法決定數(shù)據(jù)結構；反之算法的結構設計和選擇又依賴于作為其基礎的數(shù)據(jù)結構。即數(shù)據(jù)結構為算法提供了工具。算法是利用這些工具來實施解決問題的最優(yōu)方案。1.5算法1.5.1算法及其性質算法就是解決問題的方法。算法是解決某個特定問題的一些指令的集合；由人們組織起來加以準備加以實施的有限的基本步驟。流程圖是圖形化的算法，程序是用計算機語言描述的算法。在計算機領域內，一個算法實質上是根據(jù)處理問題的需要，在數(shù)據(jù)的邏輯結構和存儲結構的基礎上施加的一種運算。1.5算法1.5.1算法及其性質一個完整的算法應該滿足以下幾條性質：⑴正確性。算法必須完成所期望的功能，得到的結果必須是正確的。⑵確定性。組成算法的指令必須是清晰的、無二義性。也就是說算法的每一個步驟都必須準確定義。準確定義是指所描述的行為必須是對人或機器而言是可讀的、可執(zhí)行的。每一步必須在有限的時間內執(zhí)行完畢，同時必須是我們所力所能及的，能夠依賴于具體的工具來執(zhí)行的工序。⑶有窮性。算法必須在有限的步驟內結束。如果一個算法由無限的步驟組成，該算法不可能有計算機程序實現(xiàn)。⑷有效性。算法的指令必須具有可執(zhí)行性。⑸可終止性。算法必須可以終止，即不能進入死循環(huán)。一個算法可以沒有輸入，但是至少應該有一個輸出。1.5算法1.5.2算法描述的分析

一、算法設計要求⑴正確性。算法設計應滿足具體問題的需求。它至少應該包括對輸入、輸出及加工過程等的明確的無歧義性的描述?！罢_”涵義通常包含程序無語法錯誤、程序能夠得到正確的結果、程序對不合法的數(shù)據(jù)的輸入應有滿足要求的結果。一般對程序的測試時，以錄入不合法數(shù)據(jù)得到滿足要求的結果作為衡量程序是否合格的標準。⑵可讀性。算法主要是為了人的閱讀與交流，算法可讀性好有助于人對算法的理解。⑶健壯性。當輸入非法的數(shù)據(jù)時，算法能夠適當?shù)刈鞒龇磻蜻M行處理，不會產生莫名其妙的輸出結果。⑷效率與低存儲量需求。效率是指算法的執(zhí)行時間，一般對問題的求解方法很多，執(zhí)行時間短的算法效率高。存儲量的需求是指算法執(zhí)行過程所需要的最大的存儲容量，存儲空間越小，則算法越好。1.5算法1.5.2算法描述的分析

二、算法分析算法的分析主要是指判斷算法的優(yōu)劣，判斷一個算法的好壞一般從兩個方面考慮，即從時間角度和從空間角度上衡量算法。一般算法分析從時間角度考慮的比較多。當然判斷一個算法的好與壞，不能以時間或空間衡量簡單化，而是根據(jù)實際情況綜合考慮。度量一個程序的執(zhí)行時間通常有兩種方法：⑴事后統(tǒng)計方法。⑵事前分析估算的方法。1.5算法1.5.2算法描述的分析將算法的求解問題的輸入稱為問題的規(guī)模，并用一個整數(shù)n表示。在算法的每個步驟中，可能有若干條語句，而頻度就是指每條語句的執(zhí)行次數(shù)。一個算法的時間復雜度是指算法的時間耗費。簡單說，就是以一條基本語句的執(zhí)行時間為基本單位，該算法所有語句中總的基本語句的執(zhí)行次數(shù)，就是該算法的時間耗費，它是該算法所求解的問題規(guī)模n的函數(shù)。當問題的規(guī)模n趨向無窮大時，我們把時間復雜度的數(shù)量階稱為算法的漸進時間復雜度。一般我們把漸進時間復雜度稱為算法的時間復雜度，記做“O”（Order）。1.5算法1.5.2算法描述的分析算法的時間復雜度，記做“O”（Order），它有嚴格的數(shù)學定義：若T（n）和f（n）是定義在正整數(shù)集合上的兩個函數(shù)，則T（n）＝O（f（n））表示存在正的常數(shù)C和n0，使得當n

n0時都滿足0≤T（n）≤C*f（n）?？臻g復雜度（SpaceComplexity）類似于時間復雜度，是指該算法所耗費的存儲空間，也是問題規(guī)模n的函數(shù)。一般是指漸進空間復雜度。記作：S（n）=O（f（n））其中n是問題的規(guī)模（大?。?。第2章線性表2.1線性表類型的定義2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈式存儲結構2.3.1單向鏈表

2.3.2單鏈表的基本運算

2.3.3循環(huán)鏈表

2.3.4雙鏈表

2.4鏈表應用舉例2.5順序表和鏈表的比較2.1線性表類型的定義線性表是n個數(shù)據(jù)元素的有限序列。其一般描述為：A=（a1，a2，……an）其中A稱為線性表的名稱，每個ai（n≥i≥1）稱為線性表的數(shù)據(jù)元素，具體n的值含義則稱為線性表中包含有數(shù)據(jù)元素的個數(shù)，也稱為線性表的長度；當n的值等于0時，表示該線性表是空表。每個數(shù)據(jù)元素的含義在不同情況下各不相同，它們可能是一個字母、一個數(shù)字、也可以是一條記錄等。一般情況下，在線性表中每個ai的描述的是一組相同屬性的數(shù)據(jù)。2.1線性表類型的定義線性表的離散定義是：B=<A，R>，其中A包含n個結點（a1，a2……an），R只包含一個關系。R={（ai-1，ai）|I=1，2，……n}，線性表中包含的數(shù)據(jù)元素個數(shù)為線性表的長度。一個數(shù)據(jù)元素通常包含多個數(shù)據(jù)項，此時每個數(shù)據(jù)元素稱為記錄，含有大量的記錄的線性表稱為文件。在稍微復雜的線性表中，一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成。線性表是一個比較靈活的數(shù)據(jù)結構，它的長度根據(jù)需要增長或縮短，也可以對線性表的數(shù)據(jù)元素進行不同的操作（如訪問數(shù)據(jù)元素、插入、刪除數(shù)據(jù)元素等）。2.1線性表類型的定義使用抽象數(shù)據(jù)類型ADT定義線性表如下：ADTlist{數(shù)據(jù)對象：D={ai|ai∈元素集合，i=1，2，……n，n≥0}數(shù)據(jù)關系：R={〈ai-1，ai〉|ai-1，ai∈元素集合，i=1，2，……n}基本操作：{將以上對線性表的操作搬下來，每個函數(shù)注明輸入輸出}}ADTlist2.2線性表的順序表示和實現(xiàn)線性表的存儲結構分為順序存儲和非順序存儲。其中順序存儲也稱為向量存儲或一維數(shù)組存儲。（1）順序表線性表的順序存儲，也稱為向量存儲，又可以說是一維數(shù)組存儲。線性表中結點存放的物理順序與邏輯順序完全一致，它叫向量存儲（一般指一維數(shù)組存儲），與此同時對應A=（a1，a2，．．．an）線性表而言。實際上，數(shù)據(jù)的存儲邏輯位置由數(shù)組的下標決定。所以相鄰的元素之間地址的計算公式為（假設每個數(shù)據(jù)元素占有c個存儲單元）：LOC（ai+1）=LOC（ai）+c2.2線性表的順序表示和實現(xiàn)（1）順序表對線性表的所有數(shù)據(jù)元素，假設已知第一個數(shù)據(jù)元素a1的地址為d1，每個結點占有c個存儲單元，則第i個數(shù)據(jù)元素ai的地址為：di=d1+（i-1）*c線性表的第一個數(shù)據(jù)元素的位置通常稱做起始位置或基地址。線性表的這種機內表示稱做線性表的順序存儲結構或順序映象（Sequentialmapping），使用這種存儲結構存儲的線性表又稱做順序表。其特點是，表中相鄰的元素之間具有相鄰的存儲位置。在使用一維數(shù)組時，數(shù)組的下標起始位置根據(jù)給定的問題確定，或者根據(jù)實際的高級語言的規(guī)定確定。2.2線性表的順序表示和實現(xiàn)（1）順序表順序分配的線性表的可以直接使用一維數(shù)組描述為：typearraylist[]；//type的類型根據(jù)實際需要確定//通常用在數(shù)組的元素個數(shù)不是很多且可以對數(shù)組元素“枚舉”的情況下。也可以使用符合類型數(shù)組的動態(tài)進行動態(tài)定義。typearrayname[]；該代碼只是對應用數(shù)組的聲明，還沒有對該數(shù)組分配空間，因此不能訪問數(shù)組。只有對數(shù)組進行初始化并申請內存資源后，才能夠對數(shù)組中元素進行使用和訪問。arrayname=newtype[arraysize]；其作用是給名稱為arrayname的數(shù)組分配arraysize個類型為type大小的空間；其中arraysize表示數(shù)組的長度，它可以是整型的常量和變量；如果arraysize是常量，則分配固定大小的空間，如果是變量，則表示根據(jù)參數(shù)動態(tài)分配數(shù)組的空間。2.2線性表的順序表示和實現(xiàn)（2）順序表基本運算的實現(xiàn)線性表的順序存儲的結構，容易實現(xiàn)線性表的某些操作，如隨機存取第i個數(shù)據(jù)元素等，但是在插入或刪除數(shù)據(jù)元素時則是比較煩瑣，所以順序存儲結構比較適合存取數(shù)據(jù)元素。應該注意java的數(shù)組下標從0開始。下面考慮線性表順序存儲的插入、刪除和排序的實現(xiàn)方法。順序表的“求表長”和取第i個數(shù)據(jù)元素的時間復雜度均為O（1），因為可以直接求出線性表的長度，順序存儲下可可以實現(xiàn)隨機存取，可以直接取得數(shù)據(jù)元素，而不需要移動元素。2.3線性表的鏈式存儲結構線性表的順序存儲結構的特點是邏輯關系上相鄰的兩個元素在物理位置上也相鄰，因此隨機存取元素時比較簡單，但是這個特點也使得在插入和刪除元素時，造成大量的數(shù)據(jù)元素移動，同時如果使用靜態(tài)分配存儲單元，還要預先占用連續(xù)的存儲空間，可能造成空間的浪費或空間的溢出。如果采用鏈式存儲，就不要求邏輯上相鄰的數(shù)據(jù)元素在物理位置上也相鄰，因此它沒有順序存儲結構所具有的弱點，但同時也失去了可隨機存取的優(yōu)點。2.3線性表的鏈式存儲結構2.3.1單向鏈表任意存儲單元存儲線性表的數(shù)據(jù)元素，對于鏈式存儲線性表時，其特點形式如圖所示：DATANEXT其中data是數(shù)據(jù)域，存放數(shù)據(jù)元素的值；next是指針域，存放相鄰的下一個結點的地址，單向鏈表是指結點中的指針域只有一個的沿著同一個方向表示的鏈式存儲結構。因為結點是一個獨立的對象，所以能夠實現(xiàn)獨立的結點類。2.3線性表的鏈式存儲結構2.3.1單向鏈表對于鏈式分配線性表，整個鏈表的存取必須是從頭指針開始，頭指針指示鏈表中第一個結點的存儲位置。同時由于最后一個數(shù)據(jù)元素，沒有直接后繼，則線性鏈表中最后一個結點的指針為“空”（null）。在使用單鏈表結點時，必須完成三步：首先創(chuàng)建一個新結點；為該結點賦一個新值；新結點的next域賦值個當前元素；當前結點的前驅的next域要指向新插入的結點。2.3線性表的鏈式存儲結構2.3.2單鏈表的基本運算①建立鏈表

因為單向鏈表的長度不固定，所以應采用動態(tài)建立單向鏈表的方法。動態(tài)地建立單向鏈表的常用方法有如下兩種：尾插入法該方法是將新結點插到當前鏈表的表尾上，為此必須增加一個尾指針tail的開銷，使其始終指向當前鏈表的尾結點；或者增加一個循環(huán)用來查找鏈表的末尾結點，然后將新結點插入到鏈表的末尾。此方法的優(yōu)點是，在固定head頭指針后，該指針就不能再變了。不會因為不斷修改頭指針，造成頭指針的丟失。實際上動態(tài)建立鏈表的過程，就是不斷插入新結點的過程；2.3線性表的鏈式存儲結構2.3.2單鏈表的基本運算頭插入法如果我們在鏈表的開始結點之前附加一個結點，并稱它為頭結點，那么會帶來以下兩個優(yōu)點：第一，由于開始結點的位置被存放在頭結點的指針域中，所以在鏈表的第一個位置上的操作就和在表的其他位置上操作一致，無須進行特殊處理；第二，無論鏈表是否為空，其頭指針是指向頭結點的非空指針（空表中頭結點的指針域空），因此空表和非空表的處理也就統(tǒng)一了。2.3線性表的鏈式存儲結構②查找運算按序號查找：在鏈表中，即使知道被訪問結點的序號i，也不能像順序表中那樣直接按序號i訪問結點，而只能從鏈表的頭指針出發(fā)，順著鏈域next逐個結點往下搜索，直至搜索到第i個結點為止（一般采用計數(shù)器的方式）。鏈表不是隨機存取結構，只能順序存取。查找之前首先要做到從頭（head）開始，然后再逐個向后查找，查找過程中，每向后移動依次，計數(shù)器增加1，直到找到第i個結點（查找成功）或找完整個鏈表，沒有第i個結點（查找失?。?。2.3線性表的鏈式存儲結構②查找運算按數(shù)值查找

查找結點有時可以按數(shù)值查找，按值查找是在鏈表中，查找是否有結點值等于給定值key的結點，若有的話，則返回首次找到的其值為key的結點的存儲位置；否則返回null。查找過程從開始結點出發(fā)，順著鏈域逐個將結點的值和給定值key作比較，有兩種情況，curr.val=key（查找成功）；curr=null也沒有出現(xiàn)curr.val=key的條件（查找失?。?。2.3線性表的鏈式存儲結構③求鏈表長度求鏈表長度基本同按序號查找，從頭結點開始順著鏈域掃描，用指針curr指向當前掃描到的結點（原因是頭結點指針不能變），用len作計數(shù)器，累計當前掃描的結點數(shù)，直至curr=null，返回長度len就可以了。④刪除結點刪除結點是將表中的某個結點從表中刪除，實際上還是利用查找算法，找到滿足條件的將要刪除的結點后，注意刪除過程中，使用的指針是被刪除結點的直接前驅結點的指針，直接刪除即可。2.3線性表的鏈式存儲結構⑤打印鏈表的所有元素

打印鏈表的所有結點的數(shù)值，與求鏈表的長度的方法基本類同，只是在找到每個結點的后面，增加一條打印命令，去掉計數(shù)命令，在次方法中需要特別處理的是鏈表為空時的情況。在整個單向鏈表的所有操作中，只要做到單向鏈表的初始化后，剩下比較重要的算法是對鏈表的插入、刪除和查詢操作，只要比較靈活地掌握插入、刪除和查詢三個基本的操作，其它的大部分操作可以利用以上的三種基本操作組合實現(xiàn)。2.3線性表的鏈式存儲結構在單鏈表中，因為指針是單一方向，結點的查找只能從前向后查找，不能反向查找，所以在插入、刪除結點時，特別是在某個結點之前插入，或者刪除某個結點時，需要利用結點的前趨結點的指針，所以在查找結點時，需要保留結點的直接前趨結點位置。也因為在單鏈表中，結點的查找只能從前向后查找，不能反向查找，所以在單向鏈表中，頭結點的非常重要，不能丟失。2.3線性表的鏈式存儲結構2.3.3循環(huán)鏈表

循環(huán)鏈表又稱為循環(huán)線性鏈表，其存儲結構基本同單向鏈表，是在單向鏈表的基礎上加以改進形成的，它可以解決單向鏈表中單方向查找的缺點。因為單向鏈表只能沿著一個方向，不能反向查找，并且最后一個結點的指針域的值是null，為解決單向鏈表的缺點，可以利用末尾結點的空指針完成前向查找。將單鏈表的末尾結點的指針域的null變?yōu)橹赶虻谝粋€結點，邏輯上形成一個環(huán)型，該存儲結構稱之為單向循環(huán)鏈表。相對單鏈表而言，有以下的優(yōu)點：在不增加任何空間的情況下，能夠已知任意結點的地址，可以找到鏈表中的所有結點（環(huán)向查找）。當然在查找某個結點的前驅結點時，需要增加時間開銷完成，查找的時間復雜度是O（n）。2.3線性表的鏈式存儲結構2.3.3循環(huán)鏈表

循環(huán)線性鏈表中已知鏈表中任何結點，可以找到鏈表中的所有結點，我們一般還是習慣把頭結點作為已知條件，但是如果已知條件是頭結點，將在以下的插入或刪除結點時造成不方便：刪除末尾結點第一個結點前插入新結點在第一種情況下，雖然能夠完成刪除，但是，需要我們從頭結點開始逐個查找結點直到找到最后一個結點的直接前驅結點，然后才能夠刪除，整個算法的時間復雜度是O（n）。在第二種情況下，雖然能夠完成插入，但是，需要我們從頭結點開始逐個查找結點直到找到最后一個結點，然后才能夠插入，因為我們需要修改最后一個結點的指針域，整個算法的時間復雜度是O（n）。2.3線性表的鏈式存儲結構2.3.3循環(huán)鏈表以上的兩種情況造成無謂的時間開銷，為解決這個問題，我們通常在循環(huán)鏈表以末尾結點指針為已知條件，這樣以上的兩種情況，都可以直接完成，因為已知末尾結點可以直接找到頭結點，此時的時間復雜度為O（1），這樣在不增加任何開銷的情況下，減少了時間的開銷?？盏难h(huán)線性鏈表根據(jù)定義可以與單向鏈表相同，也可以不相同。判斷循環(huán)鏈表的末尾結點條件也就不同于單向鏈表，不同之處在于是單向鏈表是判別最后結點的指針域是否為空，而循環(huán)線性鏈表末尾結點的判定條件是其指針域的值指向頭結點。2.3線性表的鏈式存儲結構2.3.3循環(huán)鏈表循環(huán)鏈表的插入、刪除運算基本同單向鏈表，只是查找時判別條件不同而已；但是這種循環(huán)鏈表實現(xiàn)各種運算時的危險之處在于：鏈表沒有明顯的尾端，可能使算法進入死循環(huán)，所以判斷條件應該用curr.next()!=head替換單向鏈表的curr.next()!=null完成遍歷所有結點。2.3線性表的鏈式存儲結構2.3.4雙鏈表

單循環(huán)鏈表中，雖然從任一已知結點出發(fā)能找到其直接前趨結點，但時間耗費是O（n）。若希望從表中快速確定一個結點的直接前趨，可以在單鏈表的每個結點里再增加一個指向其直接前趨的指針域prior。這樣形成的鏈表中有兩條方向不同的鏈，故稱之為雙（向）鏈表。雙向鏈表的運算類似單向鏈表的運算，主要包括插入結點、刪除結點、查詢結點等運算。2.3線性表的鏈式存儲結構2.3.4雙鏈表①雙鏈表的插入結點

雙向鏈表的插入結點的實現(xiàn)比較簡單，基本同單向鏈表，只不過在某個結點前或后插入新的結點時，只要找到該結點就可以了。另外在第一個結點之前插入時同單向鏈表插入結點，需要單獨處理。在插入過程中和單向鏈表的主要的不同點是修改的指針的個數(shù)不同。單向鏈表修改兩個指針；雙向鏈表需要修改四個指針。2.3線性表的鏈式存儲結構2.3.4雙鏈表①雙鏈表的插入結點插入結點應分為以下幾個步驟：申請新結點，同時給新結點的數(shù)據(jù)域、兩個指針域賦值；將當前結點的next域指向新結點；將當前結點的直接后繼的前驅指針指向新結點。2.3線性表的鏈式存儲結構2.3.4雙鏈表②雙向鏈表的刪除結點

雙向鏈表的刪除結點的實現(xiàn)基本同單向鏈表，只不過在某個結點前或后刪除新的結點時，只要找到該結點就可以了，不需要保留前驅結點。另外在刪除第一個結點時同單向鏈表刪除頭結點，需要單獨處理。在刪除過程中和單向鏈表的主要的不同點是修改的指針的個數(shù)不同。單向鏈表修改一個指針；雙向鏈表需要修改兩個指針。2.3線性表的鏈式存儲結構2.3.4雙鏈表②雙向鏈表的刪除結點

刪除雙向鏈表的結點步驟有：修改當前結點的next域修改當前結點的后繼結點前驅結點指針③雙向鏈表的查詢結點

雙向鏈表的查詢結點的實現(xiàn)基本同單向鏈表，只要按照next的方向找到該結點就可以了，不需要保留前驅結點。如果找到，返回結點位置，否則返回null。查找結點的步驟是：從頭結點開始，直到找到該結點或是查找失敗。2.4鏈表應用舉例例1．鏈式存儲下的一元多項式加法例2．Josephus問題例3：使用迭代器編寫一個將鏈接線性表逆序打印的算法。2.5順序表和鏈表的比較線性表的存儲有兩種：順序存儲表和鏈式存儲表。具體存儲方式可根據(jù)具體問題的要求和性質來決定。根據(jù)線性表定長與不定長確定：順序存儲結構一般要求數(shù)據(jù)存放的物理和邏輯地址連續(xù)；而鏈式存儲結構數(shù)據(jù)存放地址可連續(xù)可不連續(xù)，在線性表長度沒有確定的情況下，一般采用鏈式存儲結構比較好，反之應以順序存儲為主。2.5順序表和鏈表的比較一般選擇存儲結構時可以主要從以下兩個方面考慮：（1）基于空間的考慮順序表的存儲空間是靜態(tài)分配的，在程序執(zhí)行之前一般必須明確規(guī)定它的存儲規(guī)模。若線性表的長度n變化較大，則存儲規(guī)模難于預先確定（定義太大可能浪費空間，定義太小又可能不夠用）。因此，當線性表的長度變化較大，難以估計其存儲規(guī)模時，以采用動態(tài)鏈表作為存儲結構為好。反之如果存儲規(guī)模比較小，并且線性表的長度一般固定時，可使用順序存儲。存儲密度=（結點數(shù)據(jù)本身所占的存儲量）/（結點結構所占的存儲總量）一般地，存儲密度越大，存儲空間的利用率就越高。順序表的存儲密度為1，而鏈表的存儲密度小于1。由此可知，當線性表的長度變化不大，易于事知確定其大小時，為了節(jié)約存儲空間，宜采用順序表作為存儲結構。2.5順序表和鏈表的比較（2）基于時間的考慮順序表是由向量實現(xiàn)的，它是一種隨機存取結構，對表中任一結點都可在O（1）時間內直接地存取，而鏈表中的結點，需順序存取，應從頭指針起順著鏈指針掃描結點才能獲得。因此，若對線性表的操作主要是進行查找，很少做插入和刪除操作時，采用順序表的存儲結構比較好。反之，如果在線性表中需要做較多的插入和刪除，如果采用順序存取，可能造成大量的數(shù)據(jù)移動，在時間上的開銷較大，而采用鏈式存儲時，只需要修改相應地指針就可以了。2.5順序表和鏈表的比較如果比較偏重線性表的查找，通常很少對線性表進行插入刪除操作時，因為順序存儲結構為隨機存?。ù嫒∷俣瓤欤準酱鎯Y構為順序存?。ㄏ鄬^慢），此時應所以應采用順序存儲結構較好。第3章棧和隊列第3章棧和隊列堆棧和隊列是兩種特殊的線性表。堆棧的主要特點是只能在棧頂操作，也就是遵循先進后出的運算規(guī)則。隊列的主要的特點是只能在一端插入，另一端刪除的一種線性表，也就是遵循先進先出的運算規(guī)則。3.1棧3.1.1棧定義及基本概念棧（Stack）又稱堆棧，是限制在表的一端進行插入和刪除運算的線性表。通常稱能夠進行插入、刪除運算的這一端為棧頂（Top），另一端稱為棧底（Bottom）。當表中沒有元素時稱為空棧。習慣上將每次刪除（也稱為退棧）操作又稱為彈出（POP）操作。刪除的元素總是當前棧中“最新”的元素（棧頂元素）。每次插入（稱為進棧）操作稱為壓入（PUSH）操作，壓入的元素總是當前棧中“最新”的元素。3.1棧3.1.1棧定義及基本概念

在空棧中最先插入的元素總被放在棧的底部，只有所有元素被彈出之后它才能被刪除。當棧滿時進棧運算稱為“上溢”；當?？諘r退棧運算稱為“下溢”。堆棧的存儲結構有順序存儲結構和鏈式存儲結構兩種，在順序存儲結構下，可以考慮堆棧的上溢，而在鏈式存儲結構下，不必考慮對雜貨內的上溢現(xiàn)象，只需要考慮堆棧的下溢現(xiàn)象。3.1棧3.1.1棧定義及基本概念堆棧上溢是一種出錯狀態(tài)，應該設法避免之；而下溢則可能是正?，F(xiàn)象，通常下溢用來作為程序控制轉移的條件。堆棧的運算規(guī)則是按后進先出的原則進行的（又稱為后進先出），簡稱為LIFO（lastinfirstout）表。就線性表而言，實現(xiàn)棧的方法有很多，我們著重介紹順序棧（arrary-basedstack）和鏈式（linkedstack）棧，它們類似于順序表和鏈式表。3.1棧3.1.1棧定義及基本概念棧的基本運算一般有以下幾種：①InitStack（S）構造一個空棧S。②StackEmpty（S）判?？?，若S為空棧返回TRUE，否則返回FALSE。③StackFull（S）判棧滿，若S為滿棧，則返回TRUE，否則返回FALSE。該運算只適用于棧的順序存儲結構。④Push（S，x）進棧。若棧S不滿，則將元素x壓入S的棧頂。⑤Pop（S）退棧。若棧S非空，則將S的棧頂元素彈出，并返回該元素。⑥StackTop（S）取堆棧的棧頂元素，不修改棧頂指針。比較重要的運算就是入棧和出棧兩種。3.1棧3.1.2順序棧

順序棧的實現(xiàn)從本質上講，就是順序線性表實現(xiàn)的簡化。惟一重要的是需要確定應該用數(shù)組的哪一端表示棧頂。一種選擇是把數(shù)組的第0個位置作為棧頂。根據(jù)線性表的函數(shù)，所有的插入(insert)和刪除(remove)操作都在第0個位置的元素上進行。由于這時每次push(insert)或者pop(remove)操作都需要把當前棧中的所有元素在數(shù)組中移動一個位置，因此效率不高。如果棧中有n個元素，則時間代價為O(n)。另一種選擇是當棧中有n個元素時把位置n-1作棧頂。也就是說，當向棧中壓人元素時，把它們添加到線性表的表尾，成員函數(shù)pop也是刪除表尾元素。在這種情況下，每次push或者pop操作的時間代價僅為O(1)。3.1棧3.1.2順序棧堆棧的運算主要考慮堆棧的入棧和出棧算法。其原因是在堆棧的基本運算中有六種：判斷堆?？铡⒍褩３跏蓟?、判斷堆棧滿（僅限于順序存儲的情況下），入棧元素、出棧元素、取棧頂元素等，而入棧時需要考慮的操作步驟是：堆棧初始化，然后判斷堆棧是否為滿，如果不滿，則可以插入元素（入棧）；出棧時，需要考慮的步驟是：判斷堆棧是否為空，如果不空，刪除元素（出棧），出棧之前，保存棧頂元素。也就是說，堆棧的入出棧運算包含了其他的六種基本運算，取棧頂元素的運算，只是不用修改棧頂?shù)闹羔樁选?.1棧3.1.3鏈式棧

堆棧的鏈式存儲，稱為鏈棧（單向鏈表存儲堆棧）。鏈式棧的基本運算同順序棧，定義也同線性表的鏈表定義，它是對鏈表實現(xiàn)的簡單化（因為它只是對鏈表的頭部操作）。它的元素只能在表頭進行插入和刪除。在鏈式存儲結構中，不需要給出表頭結點，因為其中惟一的已知條件是棧頂指針top，它是指向鏈式棧的第一個結點（相當于頭結點）。堆棧的各種運算比鏈式存儲的普通線性表運算實現(xiàn)時要方便得多，主要原因是堆棧的各種運算只能在堆棧的一端操作，堆棧是特殊的線性表，我們只要考慮對線性表的一端操作的情況，并且只能在一端插入刪除（棧頂）；而線性表除此之外（不限定一端插入刪除），還需要考慮另外一端結點以及中間的結點的插入、刪除、查詢等操作，理解時，我們可以把堆棧的入出堆棧運算當作線性表的一端進行插入刪除的特例即可。注意：堆棧的運算一定遵循“先進后出”的運算規(guī)則。3.1棧3.1.4順序棧和鏈式棧的比較

實現(xiàn)鏈式棧和順序棧的操作，都是需要常數(shù)時間，即時間復雜度為O（1）。主要兩者從空間和時間兩個方面考慮：初始時，順序堆棧必須說明一個固定的長度，當堆棧不夠滿時，造成一些空間的浪費，而鏈式堆棧的長度可變則是長度不需要預先設定，相對比較節(jié)省空間，但是在每個結點中，設置了一個指針域，從而產生了結構開銷。3.1棧3.1.4順序棧和鏈式棧的比較當需要多個堆棧共享時，順序存儲中可以充分利用順序棧的單向延伸性?？梢允褂靡粋€數(shù)組存儲兩個堆棧，使每個堆棧從各自的端點向中間延伸，這樣浪費的空間就會減少。但這種情況只有當兩個堆棧的空間需求有相反的需求時，這種方法才有效。也就是說，最好一個堆棧增長，一個堆?？s短。反之，如果兩個堆棧同時增長，則可能比較容易造成堆棧的溢出。如果多個順序堆棧共享空間，則可能需要大量的數(shù)據(jù)移動，造成時間的開銷增大。而鏈式堆棧由于存儲的不連續(xù)性，一般不存在堆棧滿的問題，所以一般不需要棧的共享。

3.1棧3.1.5棧的應用舉例

（一）表達式的轉換

（二）遞歸

（三）漢內塔（hanoi）問題

（四）互遞歸

3.2隊列3.2.1隊列定義及基本概念

1、隊列定義隊的操作是在兩端進行，其中一端只能進行插入，該端稱為隊列的隊尾，而另一端只能進行刪除，該端稱為隊列的隊首。一般情況下，入隊操作又稱為隊列的插入，出隊操作又稱為隊列的刪除。隊列的運算規(guī)則是FIFO（FirstInFirstOut），或者叫做先進先出規(guī)則。隊列的存儲具有順序和鏈式存儲兩種。隊列在順序存儲時，經常出現(xiàn)“假溢出”現(xiàn)象，解決“假溢出”現(xiàn)象的方法有很多種，但通常采用循環(huán)隊列方式存儲。隊列的主要作用是：用于某種先后順序處理的問題中，如：操作系統(tǒng)的作業(yè)調度、打印任務的調度等。3.2隊列3.2.1隊列定義及基本概念2、隊列的基本運算隊列的基本運算通常和堆棧的基本運算類似，有以下6種：①置空隊；//構造一個空隊列。②判對空；//隊空返回真，否則返回假。③判對滿；//隊滿返回真，否則返回假，僅限于順序存儲結構。④入隊；//隊列非滿時，從隊尾插入元素。⑤出隊；//隊列非空時，從隊首刪除元素。⑥取隊首元素；//返回隊首元素，不修改隊首指針。

3.2隊列3.2.2順序隊列

隊列的順序存儲結構稱為順序隊列，順序隊列實際上是運算受限的順序表，和順序表一樣，順序隊列也必須用一個向量空間來存放當前隊列中的元素。由于隊列的隊頭和隊尾的位置是變化的，因而要設置兩個指針front和和rear分別指示隊頭元素和隊尾元素在向量空間中的位置，它們的初值在隊列初始化時可以置為0。入隊時將新元素插入rear所指的位置，然后將rear加1。出隊時，刪去front所指的元素，然后將front加1并返回被刪元素。由此可見，當頭尾指針相等時隊列為空。在非空隊列里，頭指針始終指向隊頭元素，而尾指針始終指向隊尾元素的下一個位置。3.2隊列3.2.2順序隊列

隊列同堆棧一樣也有上溢和下溢現(xiàn)象。此外隊列中還存在“假溢出”現(xiàn)象。所謂“假溢出”是指在入隊和出隊操作中，頭尾指針不斷增加而不減小或只減小而不增加，致使被刪除元素的空間無法重新利用，最后造成隊列中有空閑空間，但是不能夠插入元素，也不能夠刪除元素的現(xiàn)象。因此，盡管隊列中實際的元素個數(shù)遠遠小于向量空間的規(guī)模，但也可能由于尾指針已超越向量空間的上界而不能進行入隊或出隊操作。該現(xiàn)象稱為假上溢。解決假上溢現(xiàn)象的方法有很多種，如固定隊首指針，一旦刪除元素，需要移動所有元素后，修改隊尾指針，這樣又可以插入元素了，只有在不能插入元素時，隊列才滿，否則可以一直插入元素，這種方法雖然能夠解決“假溢出”，但需要造成大量的數(shù)據(jù)元素的移動；現(xiàn)在解決“假溢出”比較好的解決方案是使用循環(huán)向量，存儲在循環(huán)向量中的隊列稱為循環(huán)隊列（circularQuene）。3.2隊列3.2.2順序隊列

假設向量的空間是m，只要在入出隊列時，將隊首和隊尾的指針對m做求模運算即可實現(xiàn)隊首和隊為指針的循環(huán)，即隊首和隊尾指針的取值范圍是0到m-1之間。入隊時：rear=（rear+1）%maxsize出隊時：front=（front+1）%mixsize但是入隊和出隊時front和rear的取值不能夠確定隊列的空和滿。因為入隊時，rear指針不斷增加一個，當rear指針“追上”front指針時，此時隊列已經滿了，此時滿的條件是rear=front；反之，當出隊時，front指針不斷增加一個，當front指針“追上”rear指針時，此時隊列已經空了，此時隊列空的條件是rear=front。由此可見隊空和隊滿的條件是相同的，都是front=rear。3.2隊列3.2.2順序隊列

區(qū)分隊空和隊滿的方法有多種。方法一：我們可以設置浪費一個空間單元，也就是假定rear指向的是剛剛插入元素的位置，front指向剛剛刪除元素的位置。也就是說在入隊時，先不修改rear的值，而是先判斷（rear+1）%maxsize=front，如果成立，表示隊列已滿（此時實際還有front指向的位置空閑），出隊時，只要判斷front=rear，如果成立表示隊已空，否則只要front=（front+1）%maxsize直接刪除元素即可。此種方法存儲的數(shù)據(jù)元素個數(shù)是maxsize-1個，是利用浪費一個空間來換取隊空與滿的條件。方法二：設定一個變量來表示隊列中的元素個數(shù)，利用該變量的值與隊列的最大容量比較，如果該變量的值與最大容量相等，則表示隊滿，如果該變量的只為0，此時表示隊列為空。此方法與第一種方法的不同之處在于，每次入隊、出隊一個元素時，需要修改隊列中的數(shù)據(jù)元素的個數(shù)。3.2隊列3.2.3鏈式隊列

定義鏈隊列的存儲結構基本和線性表的定義相同，不過需要在結構中指明的是隊首和隊尾的數(shù)據(jù)類型不再是整型而是指針類型。隊列的各種運算比鏈式存儲的普通線性表運算實現(xiàn)時要方便得多，主要原因是隊列的各種運算只能在隊列的兩端操作，隊列是特殊的線性表，我們只要考慮對線性表的兩端操作的情況，并且只能一端插入（隊首），另一端刪除（隊尾）；而線性表除此之外（不限定一端插入、一端刪除），還需要考慮中間的結點的插入、刪除、查詢等操作，理解時，我們可以把隊列的入出隊運算當作線性表兩端進行插入刪除的特例即可。3.2隊列3.2.3鏈式隊列

主要考慮隊列的入隊和出隊算法。其原因是在隊列的基本運算中有六種：判斷隊空、隊列初始化、判斷隊列滿（僅限于順序存儲的情況下），入隊元素、出隊元素、取隊首元素等，而入隊時需要操作的步驟是：初始化，然后判斷隊列是否為滿，如果不滿，則可以插入元素（入隊）；出隊時，需要考慮的操作步驟是：判斷隊列是否為空，如果不空，刪除元素（出隊），出隊之前，保存隊首元素。也就是說，隊列的入出隊運算包含了其他的六種基本運算，取隊首元素的運算，只是不用修改隊首的指針而已。3.2隊列3.2.3鏈式隊列

以單向循環(huán)隊列為例，只要保留末尾結點指針（假設是隊尾指針），主要原因是如果保存隊首和隊尾指針，結構開銷較大，原因是循環(huán)隊列中，已知任意結點，可以找到所有結點，所以只要保留一個結點就可以了。如果已知結點的指針是頭結點指針，此時入隊出隊運算的時間復雜度為O（n）（主要時間花費在查詢結點上）；而如果已知結點的指針是末尾結點指針，此時不需要查詢結點，直接進行入隊和出隊運算，時間復雜度O（1），各種運算實現(xiàn)也比較方便。在出隊算法中，一般只需修改隊頭指針。但當原隊中只有一個結點時，該結點既是隊頭也是隊尾，故刪去此結點時亦需修改尾指針，且刪去此結點后隊列變空。3.2隊列3.2.4隊列的應用

（一）合并兩個隊列假設有兩個隊列，要求將兩個隊列合并到一起，合并時交替使用兩個隊列中的元素，并把剩余的隊列中的元素添加在最后，將產生的新隊列返回。（二）模擬客戶服務系統(tǒng)

第4章數(shù)組和廣義表4.1多維數(shù)組4.1.1數(shù)組定義

數(shù)組是數(shù)據(jù)結構的基本結構形式，它是一種順序式的結構，數(shù)組是存儲同一類型數(shù)據(jù)的數(shù)據(jù)結構，使用數(shù)組時需要定義數(shù)組的大小和存儲數(shù)據(jù)的數(shù)據(jù)類型，數(shù)組分為一維數(shù)組和多維數(shù)組。數(shù)組的維數(shù)是由數(shù)組的下標的個數(shù)確定的，一個下標稱為一維數(shù)組，一個下標以上的數(shù)組稱為多維數(shù)組。從這個意義上講，確定了對于數(shù)組的一個下標總有一個相應的數(shù)值與之對應的關系；或者說數(shù)組是有限個同類型數(shù)據(jù)元素組成的序列。數(shù)組的基本操作包括：initarray（&A）；//初始化數(shù)組destroyarray（&A）；//銷毀數(shù)組assign（&A，e）；//數(shù)組賦值value（A，&e）；//取數(shù)組的某個元素copyarray（M，&T）；//復制一個數(shù)組printarray（M）；//打印數(shù)組的元素4.1多維數(shù)組4.1.1數(shù)組定義一維數(shù)組一維數(shù)組是指下標的個數(shù)只有一個的數(shù)組，有時稱為向量，是最基本的數(shù)據(jù)類型，在java中需要事先聲名，程序才能夠在編譯過程中預留內存空間。聲明的格式一般是：<數(shù)據(jù)類型><變量名稱>[]=new<數(shù)據(jù)類型>[<數(shù)組大小>]；

4.1多維數(shù)組4.1.1數(shù)組定義多維數(shù)組多維數(shù)組是指下標的個數(shù)有兩個以上，我們比較常用的是二維數(shù)組（因為三維以上的數(shù)組存儲可以簡化為二維數(shù)組的存儲）。下面以二維數(shù)組為例說明多維數(shù)組。二維數(shù)組的聲明同一維數(shù)組。格式為：<數(shù)據(jù)類型><數(shù)組名稱>[][]=new<數(shù)據(jù)類型>[size1][size2];4.1多維數(shù)組4.1.2數(shù)組的存儲一維數(shù)組的存儲一維數(shù)組的數(shù)據(jù)存儲按照順序存儲，邏輯地址和物理地址都是連續(xù)的。如果已知第一個數(shù)據(jù)元素的地址loc(a1)，則第i個元素的地址loc(ai)為：loc(ai)=loc(a1)+（i-1）*c假設數(shù)組的下標從1開始，只要求出第i個元素之前存放了多少個數(shù)據(jù)元素即可（實際上有i-1個元素），每個元素占有c個存儲單元，再乘以c，就是第i個元素的起始地址。如果下標從0開始，則第i個元素之前就有i個元素，此時上面的公式就變?yōu)椋簂oc(ai)=loc(a1)+i*c由此可見，求數(shù)組中數(shù)據(jù)元素的地址，已知條件必須是知道第一個元素的地址，然后主要是找出該元素之前已經存儲了多少個數(shù)據(jù)元素。在一維數(shù)組中，只要知道任何一個元素的地址即可求出其它元素的地址，但在多維數(shù)組中，已知條件必須是第一個數(shù)據(jù)元素地址。4.1多維數(shù)組4.1.2數(shù)組的存儲多維數(shù)組以二維數(shù)組的順序存儲為例說明，二維數(shù)組在順序存儲時一般有兩種：行優(yōu)先順序：存儲時先按行從小到大的順序存儲，在每一行中按列號從小到大存儲。列優(yōu)先順序：存儲時先按列從小到大的順序存儲，在每一列中按行號從小到大存儲。以上的兩種存儲順序中，第一個被存放的元素總是第一行第一列的數(shù)據(jù)元素，所以該元素的地址是我們的已知條件。同樣在二維數(shù)組中比較典型的是計算數(shù)據(jù)的存儲位置。4.1多維數(shù)組4.1.2數(shù)組的存儲多維數(shù)組假設二維數(shù)組是m*n的二維數(shù)組（共有m行，每行有n列）。第一個數(shù)據(jù)元素的地址是loc(a11)，則第i行第j列的數(shù)據(jù)元素的地址的計算公式應為（按照行優(yōu)先順序存儲）：loc(aij)=loc(a11)+[（i-1）*n+j-1]*c假設下標從1開始，我們需要計算出i行前面已經存儲了i-1行元素，每行有n個元素，共有（i-1）*n個數(shù)據(jù)元素，在第i行元素中，j列之前有j-1個數(shù)據(jù)元素，共有（i-1）*n+j-1個元素，每個元素占有c個存儲單元，只要乘以c就可以了。其中l(wèi)oc(aij)表示第i行第j列數(shù)據(jù)元素的內存的起始位置，loc(a11)表示第一個數(shù)據(jù)元素的內存位置，c表示每個數(shù)據(jù)元素所占有的內存空間的大小，如果下標從0開始，只要不用減1即可。4.1多維數(shù)組4.1.2數(shù)組的存儲多維數(shù)組如果按列優(yōu)先順序存儲，則地址的計算為：loc(aij)=loc(a11)+[（j-1）*m+i-1]*c假設下標從1開始，其中l(wèi)oc(aij)表示第i行第j列的數(shù)據(jù)元素的內存起始位置，loc(a11)表示第一個數(shù)據(jù)元素的內存位置，c表示每個數(shù)據(jù)元素所占有的內存空間的大小；主要還是計算第i行j列元素之前有多少個數(shù)據(jù)元素。如果下標從0開始，只要不用減1即可。按此公式可以推廣到多維數(shù)組的數(shù)據(jù)元素的地址計算（假設按照行優(yōu)先順序存儲）：m行n列縱標為k的三維數(shù)組，假設第一個元素的地址是loc(a111)，如果按行優(yōu)先順序存儲，i行j列縱標為p的數(shù)據(jù)元素的地址為（可以將它分解為二維數(shù)組）：loc(aijp)=loc(a111)+[(i-1)*n*k+(j-1)*k+p-1]*c;如果下標從0開始，只要不用減1即可。讀者可以從以上的地址公式中可以找出一定的地址計算規(guī)律：多維數(shù)組中按行優(yōu)先計算公式用一個下標乘以后面的最大值。4.1多維數(shù)組4.1.3顯示二維數(shù)組的內容一般情況下，只要定義了數(shù)組的存儲順序，數(shù)組的存儲順序就不會改變了，所以對數(shù)組的各種操作后，應按照數(shù)組的已定義的存儲順序存儲；也就是說，如果是按行優(yōu)先順序存儲，在對數(shù)組操作后，即使改變了存儲順序，應加以改變仍然按照行優(yōu)先順序存儲。

4.2矩陣的壓縮存儲4.2.1矩陣的壓縮存儲所謂矩陣的壓縮存儲，也就是在存儲數(shù)組時，盡量減少存儲空間，但是數(shù)組中的每個元素必須存儲，所以在矩陣存儲中，如果有規(guī)律可尋，只要存儲其中一部分，而另一部分的存儲地址可以通過相應的算法將它計算出來，從而占有比較少的存儲空間達到存儲整個矩陣的目的，稱為矩陣的壓縮存儲。矩陣的壓縮存儲僅是針對特殊矩陣的；而對于沒有規(guī)律可循的二維數(shù)組則不能夠使用壓縮存儲。二維數(shù)組（矩陣）的壓縮存儲一般有三種，它們分別是對稱矩陣、稀疏矩陣和三角矩陣。三種矩陣中以稀疏矩陣比較常見。

4.2矩陣的壓縮存儲4.2.1矩陣的壓縮存儲特殊矩陣若n階矩陣A中的元素滿足以下條件：aij=ajii≥1，j≥1則稱為n階對稱矩陣。對于對稱矩陣，如果不采用壓縮存儲，占有的存儲單元有n2個，因為是對稱矩陣，所以只要存儲對角的數(shù)據(jù)元素和一半的數(shù)據(jù)元素即可，占有的存儲單元有n（n-1）/2個存儲單元中。如果我們以行序為主序存儲其下三角（包括對角線）的元素，其上三角的元素可以推算出來。4.2矩陣的壓縮存儲4.2.1矩陣的壓縮存儲特殊矩陣如果用一維數(shù)組存儲一個對稱矩陣，只要將對稱矩陣存儲在一個最大下標為n（n-1）/2的一維數(shù)組S中即可。此時按照行優(yōu)先順序存儲，數(shù)據(jù)元素aij與數(shù)組S的下標k的對應關系為：

i(i-1)/2+j-1當i≥j時

k=j(j-1)/2+i-1當i＜j時4.2矩陣的壓縮存儲4.2.1矩陣的壓縮存儲特殊矩陣對于任意給定的一組下標（i，j），均可在S中找到元素aij，反之，對所有元素都能夠確定在S中位置，當i＜j時，根據(jù)對稱矩陣的性質推算即可。由此可以看出對稱矩陣的存儲可以使用一維數(shù)組S存儲，占用的空間不再是n2，而是n（n-1）/2空間減少了接近一半，實現(xiàn)了二維數(shù)組的壓縮存儲。所謂對角矩陣是指，矩陣的所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，即除了主對角線上和直接在主對角線上、下方若干條對角線上的元素之外，其余元素皆為零。

4.2矩陣的壓縮存儲4.2.1矩陣的壓縮存儲特殊矩陣也可以按照某個原則（或者以行序為主序，或者以列序為主序，或者按對角線的順序）將對角矩陣B的所有非零元素壓縮存儲到一個一維數(shù)組LTB[1…3n-2]中。這里不妨仍然以行序為主序的原則對B進行壓縮存儲，當B中任一非零元素bij與LTB[k]之間存在著如下一一對應關系：k=2*i+j-2時，則有bij=LTB[k]。稱LTB[1…3n-2]為對角矩陣B的壓縮存儲。上面討論的幾種特殊矩陣中，非零元素的分布都具有明顯的規(guī)律，因而都可以被壓縮存儲到一個一維數(shù)組中，并能夠確定這些矩陣的每個非零元素在一維數(shù)組中的存儲位置。但是，對于那些非零元素在矩陣中的分布沒有規(guī)律的特殊矩陣(如稀疏矩陣)，則需要尋求其他方法來解決壓縮存儲問題。

4.2矩陣的壓縮存儲4.2.1矩陣的壓縮存儲稀疏矩陣對稀疏矩陣很難下一個確切的定義，它只是一個憑人們的直覺來理解的概念。一般認為，一個較大的矩陣中，零元素的個數(shù)相對于整個矩陣元素的總個數(shù)所占比例較大時，該矩陣就是一個稀疏矩陣。例如，有一個6×6階的矩陣A，其36個元素中只有8個非零元素，那么，可以稱矩陣A為稀疏矩陣。稀疏矩陣一般是指矩陣中的大部分元素為零，僅有少量元素非零的矩陣稱為稀疏矩陣；或者說矩陣A（m×n）中有S個非零元素，如果S遠遠小于矩陣的元素總數(shù)，稱A為稀疏矩陣。稀疏矩陣的存儲一般只要保存非零元素即可，對于零元素可以不與保存，這樣可以實現(xiàn)稀疏矩陣的壓縮存儲。

4.2矩陣的壓縮存儲4.2.1矩陣的壓縮存儲稀疏矩陣稀疏矩陣的壓縮存儲采用三元組的方法實現(xiàn)。其存儲規(guī)則如下：每一個非零元素占有一行，每行中包含非零元素所在的行號、列號、非零元素的數(shù)值。為完整描述稀疏矩陣，一般在第一行描述矩陣的行數(shù)、列數(shù)和非零元素的個數(shù)。其邏輯描述為：（rowcolvalue）其中row表示行號，col表示列號，value表示非零元素的值。如果每個非零元素按照此種方法存儲，雖然能夠完整地描述非零元素，但如果矩陣中有整行（或整列）中沒有非零元素，此時可能不能夠還原成原來的矩陣，所以為了完整地描述稀疏矩陣，在以上描述的情況下，如果增加一行的內容，該行包括矩陣的總的行數(shù)、矩陣的總的列數(shù)，矩陣中非零元素的個數(shù)，就可以還原為原來的矩陣描述了。

4.2矩陣的壓縮存儲4.2.1矩陣的壓縮存儲稀疏矩陣歸納起來，若一個稀疏矩陣有t個非零元素，則需要用t+1行的三元組來表示稀疏矩陣。到底矩陣何時使用三元組存儲呢？一般對m×n的矩陣來說，只要滿足（t+1）*3≤m*n這個條件，使用三元組存儲可以節(jié)省空間，否則更加浪費空間，也就沒有必要使用三元組存儲，所以稀疏矩陣中的非零元素的個數(shù)t是能否使用三元組存儲的關鍵。

4.2矩陣的壓縮存儲4.2.2稀疏矩陣轉換為三元組存儲

首先應該將稀疏矩陣轉換為三元組存儲，然后才利用三元組的存儲，實現(xiàn)對矩陣的各種運算。對于矩陣的運算一般有矩陣的轉置，在轉置時值得注意的是：在矩陣的存儲規(guī)則已經確定的情況下（如按行優(yōu)先存儲），實現(xiàn)矩陣的運算（如轉置）時，應仍然保留原來的存儲規(guī)則。改進的轉置方法可以利用對原始的三元組的元素的掃描，直接確定該元素在轉置后的三元組中的行，這樣可以將原始三元組中的元素直接放在轉置后的三元組中即可。這種方法需要增加兩個一維數(shù)組的結構開銷，稱為快速轉置。4.3廣義表4.3.1廣義表的定義廣義表是線性表的擴展，具體定義為n（n≥0）個元素的有限集合。其中元素有以下兩種類型：1）一個原子元素（指不可再分的元素）；2）一個可以再分的元素（或稱為一個子表）。如果所有元素都是原子元素，則稱為線性表，如果含有子表則是廣義表。4.3廣義表4.3.1廣義表的定義廣義表的基本操作：initGlist(&L)//創(chuàng)建空的廣義表creatGlist(&L,S)//由S創(chuàng)建廣義表LdestroyGlist(&L)//銷毀廣義表LGlistlength（L）//求廣義表的長度Glistdepth（L）//求廣義表的深度Gethead(L)//求廣義表L的頭Gettail(L)//求廣義表的表尾Insertfirst_Glist(&L,e)//插入元素e作為廣義表L的第一個元素Deletefirst_Glist(&L,&e)//刪除廣義表L的第一個元素，并用e返回其值4.3廣義表4.3.1廣義表的定義廣義表一般記作：LS=（a1，a2，…，an）其中LS是廣義表的名稱，n是廣義表的長度。常見的廣義表為：A=（）B=（（））C=（a,b）D=（A，B，C）E=（a,E）廣義表中含有元素的個數(shù)稱為廣義表的長度，廣義表中含有的括號對數(shù)稱為廣義表的深度。4.3廣義表4.3.1廣義表的定義三個重要結論：列表的元素可以是子表，而子表的元素還可以是子表…。由此，列表是一個多層次的結構，可以用圖形象地表示。例如圖4-1表示的是列表D。圖中以圓圈表示列表，以方塊表示原子元素。列表可為其它列表所共享。例如在上述例子中，列表A、B和C為D的子表，則在D中可以不必列出子表的值，而是通過子表的名稱來引用。列表可以是一個遞歸的表，即列表也可以是其本身的一個子表。例如列表E就是一個遞歸的表。4.3廣義表4.3.2廣義表的存儲廣義表的存儲方法有很多種，一般采用鏈表存儲。采用鏈表存儲時的結點存儲的邏輯結構（如圖所示）一般是：其中flag表示標志位，當flag為0時，該結點表示原子元素，當flag為1時，該結點表示子表；當flag為0時，info表示原子元素的值，當flag為1時，info表示指針，指向該子表的第一個結點；link表示指針，指向廣義表的下一個元素。Flaginfolink第5章樹

5.1樹的概念5.2二叉樹的定義5.3二叉樹的性質5.4二叉樹的存儲結構5.5二叉樹的遍歷5.6線索二叉樹5.7樹和二叉樹的轉換及樹的存儲結構5.8哈夫曼樹及其應用5.1樹的概念5.1.1樹的定義

樹是一種數(shù)據(jù)結構，表示為TREE=（D，R）；其中：D是具有相同特性的數(shù)據(jù)元素的集合；R是元素集合D上的關系集合，如果D中只含有一個數(shù)據(jù)元素，則R為空集。或者用遞歸定義為：樹是N（N>0）個結點的有限集合，其唯一關系具有下列屬性：集合中存在唯一的一個結點，稱為樹根，該結點沒有前驅；除根結點外，其余結點分為M（M≥0）個互不相交的集合，其中每一個集合都是一棵樹，并稱其為根的子樹。

5.1樹的概念5.1.2基本術語一個結點的子樹個數(shù)稱為該結點的度（degree）一棵樹中結點度的最大值稱為該樹的度度為零的結點稱為葉子（leaf）或者終端結點度不為零的結點稱為分支結點或者非終端結點除根結點之外的分支結點統(tǒng)稱為內部結點樹中結點的后繼結點稱為兒子（child）或者兒子結點，簡稱兒子

結點的前驅結點稱為兒子的雙親（parents）或者父親結點，簡稱父親同一個父親的兒子互稱為兄弟（sibling）

5.1樹的概念若樹中存在一個結點序列k1k2k3…kj，使得ki是ki+1的父親（1≤i＜j），則稱該結點序列是從k1到kj的一條路徑（path）或者道路路徑的長度等于j-1，它是該路徑所經過的邊（即連接兩個結點的線段）的數(shù)目若樹中結點k到ks存在一條路徑，則稱k是ks的祖先（Ancestor），ks是k的子孫（Descendant）結點的層數(shù)（level）是從根開始算起的。設根結點的層數(shù)為1，其余結點的層數(shù)等于其父親結點的層數(shù)加1樹中結點的最大層數(shù)稱為樹的高度（Height）或者深度（Depth）

5.1樹的概念若把樹中每個結點的各子樹看成從左到右有次序的（即不能互換），則稱該樹為有序樹（OrderedTree）；否則稱為無序樹（UnorderedTree）森林（Forest）是m（m≥0）棵互不相交樹的集合樹形結構是非線性結構

祖先與子孫的關系則是對父子關系的延伸，其定義了樹中結點的縱向次序

如果規(guī)定k1和k2是兄弟，且k1在k2的左邊，則k1的任一子孫都在k2的任一子孫的左邊，則定義了樹中結點的橫向次序

5.2二叉樹的定義二叉樹是由n（n≥0）結點的有限集合，此集合或者為空，或者由一個根結點加上兩棵分別稱為左、右子樹的，互不相交的二叉樹組成二叉樹可以為空集，因此根可以有空的左子樹或者右子樹，亦或者左、右子樹皆為空從二叉樹定義中可以看出，二叉樹結構與一般樹結構區(qū)別如下：（1）二叉樹可以為空樹，即不包含任何結點；一般樹至少應有一個結點。（2）二叉樹區(qū)別于度數(shù)為2的有序樹，在二叉樹中允許某些結點只有右子樹而沒有左子樹；而有序樹中，一個結點如果沒有第一子樹就不可能有第二子樹的存在。

5.3二叉樹的性質5.3.1二叉樹性質性質1二叉樹第i（i≥1）層上的結點數(shù)最多為2i-1

性質2高度為k的二叉樹最多有2k-1個結點

性質3對任何二叉樹T，設n0、n1、n2分別表示度數(shù)為0、1、2的結點個數(shù)，則n0=n2+1

5.3二叉樹的性質性質4具有n個結點的完全二叉樹（包括滿二叉樹）的高度為（或者）性質5滿二叉樹原理

非空滿二叉樹的葉結點數(shù)等于其分支結點數(shù)加1性質6一棵非空二叉樹空子樹的數(shù)目等于其結點數(shù)目加1

5.3二叉樹的性質5.3.2二叉樹的抽象數(shù)據(jù)類型

下列給出一個二叉樹結點的JAVA接口，稱之為BinNode。BinNode類中存儲了指向Object類的引用。創(chuàng)建二叉樹時，可以根據(jù)需要而采用實際的數(shù)據(jù)類型。成員函數(shù)包括返回元素的值，返回左、右結點指針，設置元素的值，以了標志該結點是否為葉結點。interfaceBinNode{//二叉樹結點的抽象數(shù)據(jù)類型//返回并設置元素值publicObjectelement();publicObjectsetElement(Objectv);

5.3二叉樹的性質//返回并設置左孩子publicBinnodeleft();publicBinnodesetLeft(BinNodep);

//返回并設置右孩子publicBinnoderight();publicBinnodesetRight(BinNodep);

//判斷是否為葉結點publicbooleanisLeaf();}//interfaceBinNode5.4二叉樹的存儲結構5.4.1二叉樹順序存儲結構

二叉樹的順序存儲結構是把二叉樹的所有結點按照一定的次序順序存儲到一組包含n個存儲單元的空間中

二叉樹順序存儲的原則是：不管給定的二叉樹是不是完全二叉樹，都看作完全二叉樹，即按完全二叉樹的層次次序（從上到下，從左到右）把各結點依次存入數(shù)組中

5.4二叉樹的存儲結構在順序存儲結構中，由某結點的存儲單元地址可以推出其父親、左兒子、右兒子及兄弟的地址，假設給定結點的地址為I，則：（1）若I＝1，則該結點是為根結點，無父親。（2）若I≠1，則該結點的父親結點地址為I／2的整數(shù)部分。（3）若2×I≤n，則該結點的左兒子結點地址為2×I，否則該結點無左兒子。（4）若2×I+1≤n，則該結點的右兒子結點地址為2×I+1，否則該結點無右兒子。（5）若I為奇數(shù)（不為1），則該結點的左兄弟為I-1。（6）若I為偶數(shù)（不為n），則該結點的右兄弟為I+1。5.4二叉樹的存儲結構5.4.2二叉樹的鏈接存儲結構

二叉樹的鏈接存儲中每個結點由數(shù)據(jù)域和指針域兩部分組成

二叉樹每個結點的指針域有兩個，一個指向左兒子，一個指向右兒子

還需一個鏈表的頭指針指向根結點

二叉樹的鏈接存儲結構也稱為二叉鏈表

若二叉樹為空，則根結點為NULL

5.4二叉樹的存儲結構5.4.3二叉樹的實現(xiàn)舉例1．以數(shù)組方式實現(xiàn)二叉樹

先依次序輸入元素值，一一建立二叉樹數(shù)組，