[TOC] # 線性表 ## 概念 * 線性表是由n（n≥0）個具有相同特性數據元素(結點) a1，a2，…，an組成的有限序列。 * 線性表的長度：所含元素的個數,用n表示，n>=０。當n=0時,表示線性表是一個空表，即表中不包含任何元素。 * 線性表的邏輯結構： :-:  * 線性表的特點 1. 有且僅有一個開始結點`$ a_1 $`，沒有直接前趨，有且僅有一個直接后繼`$ a_2 $`； 2. 有且僅有一個終結結點`$ a_n $`，沒有直接后繼，有且僅有一個直接前趨`$ a_{n-1} $`； 3. 其余的內部結點`$ a_i $`（2≤i≤n-1）都有且僅有一個直接前趨`$ a_{i-1} $`和一個`$ a_{i+1} $`。 * 線性表實例 英文字母表：(A，B，C，D，…，X，Y，Z) 某校1998-2003年計算機數量：(50，100，250，300，500，1200) * 線性表的順序存儲 順序存儲是線性表的一種最簡單的存儲結構，存儲方式是：在內存中為線性表開辟一塊連續的存儲空間。 :-:  * 順序存儲的優缺點 * 優點 1. 邏輯相鄰，物理相鄰，地址連續 2. 可隨機存取任一元素 3. 存儲空間使用緊湊 * 缺點 1. 插入、刪除操作需要移動大量的元素 2. 預先分配空間需按最大空間分配，利用不充分 3. 表容量難以擴充 # 查找算法 * 以查詢學生成績為例 查詢學號“18”的學生成績 查詢“周麗”的成績 :-:  * 按照學號查找相對容易、省時 * 按照姓名查找相對費時 >[danger] 原因：一個有序、一個無序 >[success] 數據存放的方式決定數據查找的方法！ ## 基本概念 * 查找表：由同一類型的數據元素（或記錄）構成的集合 * 查找：查詢(Searching)特定元素是否在表中 * 靜態查找：只查找，不改變集合內的數據元素 * 動態查找：既查找，又改變（增減）集合內的數據元素 * 關鍵字：元素中某個數據項的值，可用來識別一個元素(預先確定的數據元素的某種標志 ) * 主關鍵字：可以唯一標識一個元素的關鍵字 * 次關鍵字：識別若干元素的關鍵字 ## 常見操作 * 查詢某個“特定的”數據元素是否在查找表中； * 檢索某個“特定的”數據元素的各種屬性； * 在查找表中插入一個數據元素； * 從查找表中刪去某個數據元素。 ## 順序表的查找運算 線性表有兩種基本的查找運算： * 按序號查找:要求查找線性表L中第i個數據元素，其結果是A[i] ; * 按內容查找: 要求查找線性表L中與給定值x相等的數據元素，其結果是：若在表L中找到與x相等的元素，則返回該元素在表中的序號；若找不到，則返回一個“空序號”，如-1。 > 算法分析：查找運算可采用順序查找法實現，即從第一個元素開始，依次將表中元素與x相比較，若相等，則查找成功，返回該元素在表中的序號；若x與表中的所有元素都不相等，則查找失敗，返回“-1”。 ## 折半查找(二分查找) 先給數據排序（例如按升序排好），形成有序表，然后再將key與中間元素相比，若key小，則縮小至前半部內查找；若key大，則縮小至后半部內查找。 :-:  >[success] 二分查找失敗時最多比較【`$ log_2N $`】+1次 例題： 1. 折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依次與表中元素 28，6，12，20 比較大小。 2. 對22個記錄的有序表作折半查找，當查找失敗時，至少需要比較 5 次關鍵字。 ## 哈希表 * 哈希表既是一種**查找方法**，又是一種**存貯方法**。 * 哈希表：即散列存儲結構。 * 散列法存儲的基本思想：建立關鍵碼字與其存儲位置的對應關系，或者說，由關鍵碼的值決定數據的存儲地址。 * 優點：查找速度極快（O(1)）,查找效率與元素個數n無關！ # 排序算法 * 冒泡排序 * 基本思想： 兩兩比較待排序數據元素的大小，**發現兩個數據元素的次序相反時即進行交換**，直到沒有反序的數據元素為止。 * 排序過程：設想被排序的數組R［1..N］垂直豎立，將每個數據元素看作有重量的氣泡，根據輕氣泡不能在重氣泡之下的原則，**從下往上掃描數組R**，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復進行，直至最后任何兩個氣泡都是輕者在上，重者在下為止。 * 選擇排序 * 基本思想： 每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最后（或最前），直到全部待排序的數據元素排完。 * 排序過程：  * 插入排序 * 基本思想： 每次將一個待排序的數據元素，插入到前面已經排好序的數列中的適當位置，使數列依然有序；直到待排序數據元素全部插入完為止。 * 排序過程：  * 桶排序 * 基本思想 若待排序的記錄的關鍵字在一個明顯有限范圍內(整型)時,可設計有限個有序桶,每個桶裝入一個值,順序輸出各桶的值,將得到有序的序列。 :-:  * 基數排序 * 基本思想 前面介紹的幾種排序方法都是按數據元素（或記錄關鍵字）值的大小進行排序的 而多關鍵字排序是一種按組成數據元素或關鍵字的各位值進行排序的方法，基數排序借助的就是這種思想，它屬于分布式排序，也稱口袋排序。 基數排序是把邏輯關鍵字看成由若干個子關鍵字復合而成的 假設有n個關鍵字｛r1，r2，…，rn｝需進行排序 每個關鍵字由d元組（k1k2k3…kd）子關鍵字組成，k1是關鍵字值的最高位，kd是關鍵字值的最低位，其基數為rd * 希爾排序 * 基本思想 希爾排序實質上還是一種插入排序，其主要特點是：每一趟以不同的增量進行排序。在每趟的插入排序中，記錄的關鍵字是和同一組中的前一個關鍵字進行比較，所以關鍵字較小的記錄在排序過程中是作跳躍式的移動。 另外，由于開始時增量的取值較大，每組中記錄較少，故排序比較快，隨著增量值的逐步變小，每組中的記錄逐漸變多，但由于此時記錄已基本有序了，因次在進行最后一趟增量為1的插入排序時，只需作少量的比較和移動便可完成排序，從而提高了排序速度。 * 快速排序 * 基本思想 首先對無序的記錄序列進行“一次劃分”，通過一趟排序將待排序列分成兩部分，使其中一部分記錄的關鍵字均比另一部分小，再分別對這兩部分排序，以達到整個序列有序。 * 歸并排序 * 基本思想 歸并排序又稱為表排序，其含義是將兩個有序序列合并成為一個有序序列。 設待排序序列有n個記錄，開始將其看作是n個長度為1 的有序子文件，然后進行歸并，將相鄰的有序子文件兩兩合并，得到n/2個長度為2或1的有序子文件(如果n為奇數，則最后一個有序子文件的長度為1)，再兩兩歸并得到n/4個有序子文件，以此類推，直至得到長為n的有序文件。該有序序列就是原始序列經歸并排序后的有序序列。 :-:  ## 排序的選擇原則 * 當待排序元素個數n較大，排序碼分布隨機，而對穩定性不做要求時，則采用快速排序。 * 當待排序元素個數n大，內存空間允許，且要求排序穩定時，則采用二路歸并排序為宜。 * 當待排序元素個數n大，排序碼分布可能會出現正序或逆序的情形，且對穩定性不做要求時，則采用堆排序或二路歸并排序為宜。 * 當待排序元素個數n小，元素基本有序或分布較隨機，且要求穩定時，則采用直接插入排序。 * 當待排序元素個數n小，對穩定性不做要求時，則采用直接選擇排序為宜，若排序碼不接近逆序，也可以采用直接插入排序。 # 棧 * 棧（stack）：一種特殊的線性表，限定只能在表尾進行插入、 刪除操作的線性表。 * 特點：后進先出LIFO(Last In First Out) ## 棧的概念 * 棧頂(top)：允許插入和刪除數據元素的一端。 * 棧底(bottom)：固定的一端。 * 空棧：不含任何元素。 * 進棧(壓棧push)：插入元素。 * 出棧(退棧pop)：刪除元素。 :-:  例題： 1. 設棧S的初始狀態為空，現有序列1,2,3,4,5，對該序列在棧S上依次進行如下操作（從序列中的1開始）：進棧、進棧、進棧、出棧、進棧、出棧、進棧。問出棧的元素序列是：3,4 2. 若進棧的序列是1、2、3、4、5，問能否得到出棧序列4、3、5、1、2 ？不能 3. 如果一個棧初始時為空，且當前棧中的元素從棧底到棧頂依次為a，b，c（如右圖所示），另有元素d已經出棧，則可能的入棧順序是（ AD ）。  A．a, b, c, d B．b, a, c, d C．a, c, b, d D．d, a, b, c # 隊列 * 隊列也是一種受限的線性表。它的所有插入都在隊列的一端進行，所有刪除都在另一端進行。 * 特點：先進先出(FIFO，First In First Out) * 實例： 例1：到醫院看病，首先需要到掛號處掛號，然后，按號碼順序救診。 例2：乘坐公共汽車，應該在車站排隊，車來后，按順序上車。 ## 隊列的概念 * 允許插入的一端稱為隊尾(Rear)，允許刪除的一端稱為隊頭(Front)。 * 隊列的插入和刪除我們稱為入隊和出隊，新元素入隊就成為新的隊尾元素，刪除元素后，其后繼元素成為新的隊首元素。  例題： 1. 已知隊列(13，2，11，34，41，77，5，7，18，26，15)，第一個進入隊列的元素是13，則第五個出隊列的元素是（??B??? ）。 A） 5??????B） 41??????C） 77??????? D） 13?????? E） 18 2. 設棧S和隊列Q的初始狀態為空，元素e 1 ，e 2 ，e 3 ，e 4 ，e 5 ，e 6依次通過棧S，一個元素出棧后即進入隊列Q，若出隊的順序為e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，則棧S的容量至少應該為（ B ）。 A）2 B）3 C）4 D）5 # 線性結構總結 >[danger] 棧、隊列屬于線性結構。在這種結構中，不管其存儲方式（順序和鏈式）如何，數據元素的邏輯位置之間呈線性關系，即每一個數據元素通常只有一個前驅（除第一個元素外）和一個后繼（除最后一個元素外）。 # 非線性結構 有很多問題數據元素間的邏輯關系不能用線性結構明確、方便地描述出來。一般來說，至少存在一個結點（數據元素）有多于一個前驅或后繼的數據結構稱為非線性結構。具有非線性結構特征的數據結構有兩種： **樹**  **圖**  # 樹 ## 樹的概念 樹是一種常見的非線性的數據結構。樹的遞歸定義如下： 樹是n(n>0)個結點的有限集，這個集合滿足以下條件： 1. 有且僅有一個結點沒有前驅（父親結點），該結點稱為樹的根； 2. 除根外，其余的每個結點都有且僅有一個前驅； 3. 除根外，每一個結點都通過唯一的路徑連到根上（否則有環）。這條路徑由根開始，而未端就在該結點上，且除根以外，路徑上的每一個結點都是前一個結點的后繼（兒子結點）； >[danger] 由上述定義可知，樹結構沒有封閉的回路。 ### 結點的分類  1. 根結點：沒有父親的結點。在樹中有且僅有一個根結點。 2. 分支結點：除根結點外，有孩子的結點稱為分支結點。b，c，x，t，d，i。分支結點亦是其子樹的根； 3. 葉結點：沒有孩子的結點稱為樹葉。w，h，e，f，s，m，o，n，j，u為葉結點。 **根結點到每一個分支結點或葉結點的路徑是唯一的。從根r到結點i的唯一路徑為rcti。** ### 樹的度 1. 結點的度：一個結點的子樹數目稱為該結點的度（區分圖中結點的度）。圖中，結點i度為3，結點t的度為2，結點b的度為1。顯然，所有樹葉的度為0。 2. 樹的度：所有結點中最大的度稱為該樹的度(寬度）。圖中樹的度為3。 ### 樹的高度（深度） 樹是分層次的。結點所在的層次是從根算起的。根結點在第一層，根的兒子在第二層，其余各層依次類推。圖中的樹共有五層。在樹中，父結點在同一層的所有結點構成兄弟關系。 樹中最大的層次稱為樹的深度，亦稱高度。圖中樹的深度為5。 ## 樹的表示方法和存儲結構 ### 樹的表示方法 * 自然界的樹形表示法：用結點和邊表示樹，例如上圖采用的就是自然界的樹形表示法。樹形表示法一般用于分析問題。 * 廣義表方法：先將根結點放入一對圓括號中，然后把它的子樹按由左而右的順序放入括號中，而對子樹也采用同樣方法處理：同層子樹與它的根結點用圓括號括起來，同層子樹之間用逗號隔開，最后用閉括號括起來。例如圖可寫成如下形式（r（a（w，x（d（h），e）），b（f），c（s，t（i（m，o，n），j），u）））@（表示結束） ### 樹的存儲結構 靜態的記錄數組。所有結點存儲在一個數組中，數組元素為記錄類型，包括數據域和長度為n(n 為樹的度)的數組，分別存儲該結點的每一個兒子的下標 例下圖的樹，其記錄數組如下。由于未規定同層結點的次序，因此每個結點兒子的下標序列（Tree[i].ch）任意。其中Tree[i].ch[j]=0說明結點i的第j個兒子不存在。(編號按層編號)  ## 二叉樹 二叉樹是一種很重要的非線性數據結構，它的特點是每個結點最多有兩個孩子，且其子樹有左右之分（有序樹，次序不能任意顛倒）。 ### 二叉樹的遞歸定義和基本形態 二叉樹是以結點為元素的有限集，它或者為空，或者滿足以下條件： 1. 有一個特定的結點稱為根； 2. 余下的結點分為互不相交的子集L和R，其中L是根的左子樹；R是根的右子樹；L和R又是二叉樹； > 由上述定義可以看出，二叉樹和樹是兩個不同的概念 > 1. 樹的每一個結點可以有任意多個，而二叉樹中每個結點的后繼不能超過2； > 2. 樹的子樹可以不分次序（除有序樹外）；而二叉樹的子樹有左右之分。我們稱二叉樹中結點的左后件為左兒子，右后件為右兒子。 ### 二叉樹的基本形態  * 滿二叉樹： 如果一棵深度為K的二叉樹，共有`$ 2_{K-1} $`個結點，即第I層有`$ 2_{I-1} $`的結點，稱為滿二叉樹。 * 完全二叉樹：如果一棵二叉樹最多只有最下面兩層結點度數可以小于2，并且最下面一層的結點都集中在該層最左邊的若干位置上，則稱此二叉樹為完全二叉樹。  ### 二叉樹的基本性質 性質1：在二叉樹的第i（≥1）層上，最多有`$ 2^{i-1} $`個結點 性質2：在深度為k(k≥1)的二叉樹中最多有`$ 2^k-1 $`個結點 性質3：在任何二叉樹中，葉子結點數總比度為2的結點多1,即`$ n_{0} $`=`$ n_{2} $`+1 性質4：具有n個結點的完全二叉樹的深度為Trunc（log2n）+1。 ### 二叉樹的存儲結構 將每個結點依次存放在一維數組中，用數組下標指示結點編號，編號的方法是從根結點開始編號1，然后由左而右進行連續編號。每個結點的信息包括 1. 一個數據域（data）； 2. 三個指針域，其中有父結點編號（prt）、左兒子結點編號（lch）和右兒子結點編號（rch）。  ### 二叉樹的遍歷 * 二叉樹的遍歷是不重復地訪問二叉樹中的每一個結點。在訪問到每個結點時，可以取出結點中的信息，或對結點作其它的處理。 * 如果用L、D、R分別表示遍歷左子樹、訪問根結點、遍歷右子樹，限定先左后右的次序，三種組合DLR、LDR、 LRD * 這三種遍歷規則分別稱為 **先（前）序遍歷、中序遍歷和后序遍歷（以根為標準）**  **前（先）序遍歷** a b d e h i c f g **中序遍歷 ** d b h e i a f c g **后序遍歷** d h i e b f g c a **分析：**  **由遍歷序列確定二叉樹**  已知一棵樹的兩種序列，如何構造該二叉樹 例：已知一棵樹的先序和中序序列分別為： A B C D E F G H I B C A E D G H F I 試構造該二叉樹 > 答：思路： > 1. 首先看先序序列：先序序列先看根，再看左子樹、右子樹，那么A就是該二叉樹的根；然后，看中序序列，中序序列先看左子樹，再看根，再看右子樹，B C 在A 前頭，而且A又是根，那么B C 就是屬于左子樹，D E F G H I 就是屬于右子樹。 > > 2. 其次看左子樹：在先序序列中，左子樹先訪問的是B，然后再是C，那么，B 就是左子樹的根；再看中序序列，左子樹先訪問的也是B，然后再是C，那么C就是B 的右子樹 > > 3. 然后再看右子樹：在先序序列中，右子樹先訪問的是D，那么D就是右子樹的根，再看中序序列，先訪問的是E，然后再是D，那么，E就是右子樹下的左子樹，F G H I 就是右子樹下的右子樹。 > > 4. 最后看右子樹下的右子樹（F G H I）：在先序序列中，先訪問的是F，那么F就是該分支樹的根，再看中序序列，F前面是G H ,后面是I，則G H是分支樹下的左子樹，I是分支樹下的右子樹；又 (F G H ),(G H F)與（A B C),(B C A)一樣，所以G 是分支根，H 是其右子樹。  ### 表達式樹 * 算數表達式是分層的遞歸結構，一個運算符作用于相應的運算對象，其運算對象又可以是任意復雜的表達式。樹的遞歸結構正好用來表示這種表達式。下面只討論二元表達式。 * 二元表達式可以很自然的聯系到二叉樹：以基本運算對象作為葉節點中的數據；以運算符作為非葉節點中的數據，其兩棵子樹是它的運算對象，子樹可以是基本運算對象，也可以是復雜表達式。如圖是一個表達式樹。  * 前綴、中綴和后綴表達式 * 中綴表達式（中綴記法） 我們平時縮寫的表達式，將運算符寫在兩個操作數中間的表達式，稱作中綴表達式。在中綴表達式中，運算符有不同的優先級，圓括號用于改變運算順序，這使得運算規則比較復雜，求值過程不能直接從左到右順序進行，不利于計算機處理。 * 后綴表達式 將運算符寫在兩個操作數之后的表達式稱作后綴表達式。后綴表達式中沒有括號，并且運算符沒有優先級。后綴表達式的求值過程能夠嚴格按照從左到右的順序進行，有利于計算機處理。 * 前綴表達式 前綴表達式是將運算符寫在兩個操作數之前的表達式。和后綴表達式一樣，前綴表達式沒有括號，運算符沒有優先級，能嚴格按照從右到左的順序計算。 * 另外，算式表達式和表達式樹的關系如下： 表達式樹的先根遍歷：前綴表達式 表達式樹的中根遍歷：中綴表達式 表達式樹的后根遍歷：后綴表達式 * 表達式的轉換 利用表達式樹 * 給定一個表達式的中綴形式：(4+1*(5-2))-6/3 * 首先將每個運算加上括號，區分優先級，得到(4+(1*(5-2)))-(6/3) * 括號外的-優先級最低，作為根節點，(4+(1*(5-2)))作為左子樹，(6/3)作為右子樹； * 遞歸的轉換4+(1*(5-2))，+最為根節點，4是左子樹，(1*(5-2))是右子樹。*是右子樹的根節點，1是左子樹，(5-2)是右子樹。最后計算(5-2)，-是根節點，5是左子樹，2是右子樹。得到的表達式樹如文章之初給出的圖。 * 構造好表達式樹之后，前綴表達式和中綴表達式可根據先根遍歷和后根遍歷得到。 * 前綴表達式：- + 4 * 1 - 5 2 / 6 3 * 后綴表達式：4 1 5 2 - * + 6 3 / -