資料結構基礎概念

資料結構

目錄

資料結構

一些概念

線性表

棧和隊列

棧

隊列

串

數組和廣義表

數組

廣義表

樹和二叉樹

二叉樹

周遊二叉樹和線索二叉樹

樹和森林

哈弗曼樹/霍夫曼樹

圖周遊與回溯

圖

圖的存儲形式

圖的周遊

生成樹和最小生成樹

雙連通圖和關節點

有向無環圖及其應用

查找

動态查找

查找總結

B_樹的B+樹B_樹

B+樹

哈希表

内部排序

外部排序

有效的算法設計

一些概念

    資料結構就是研究資料的邏輯結構和實體結構以及它們之間互相關系，并對這種結構定義相應的運算，而且確定經過這些運算後所得到的新結構仍然是原來的結構類型。

1. 資料：所有能被輸入到計算機中，且能被計算機處理的符号的集合。是計算機操作的對象的總稱。
2. 資料元素：資料（集合）中的一個“個體”，資料及結構中讨論的基本機關
3. 資料項：資料的不可分割的最小機關。一個資料元素可由若幹個資料項組成。
4. 資料類型：在一種程式設計語言中，變量所具有的資料種類。整型、浮點型、字元型等等
5. 邏輯結構：資料之間的互相關系。
   1. 集合結構：中的資料元素除了同屬于一種類型外，别無其它關系。
   2. 線性結構：資料元素之間一對一的關系
   3. 樹形結構：資料元素之間一對多的關系
   4. 圖狀結構或網狀結構：結構中的資料元素之間存在多對多的關系
6. 實體結構/存儲結構：資料在計算機中的表示。實體結構是描述資料具體在記憶體中的存儲（如：順序結構、鍊式結構、索引結構、哈希結構）等
7. 在資料結構中,從邏輯上可以将其分為線性結構和非線性結構
8. 資料結構的基本操作的設定的最重要的準則是,實作應用程式與存儲結構的獨立。實作應用程式是“邏輯結構”，存儲的是“實體結構”。邏輯結構主要是對該結構操作的設定，實體結構是描述資料具體在記憶體中的存儲（如：順序結構、鍊式結構、索引結構、希哈結構）等。
9. 順序存儲結構中，線性表的邏輯順序和實體順序總是一緻的。但在鍊式存儲結構中，線性表的邏輯順序和實體順序一般是不同的。
10. 算法五個特性： 有窮性、确定性、可行性、輸入、輸出
11. 算法設計要求：正确性、可讀性、健壯性、高效率與低存儲量需求。(好的算法)
12. 算法的描述有僞程式、流程圖、N-S結構圖等。E-R圖是實體聯系模型，不是程式的描述方式。
13. 設計算法在執行時間時需要考慮：算法選用的規模、問題的規模
14. 時間複雜度：算法的執行時間與原操作執行次數之和成正比。時間複雜度有小到大：O(1)、O(logn)、O(n)、O(nlogn)、O(n2)、O(n3)。幂次時間複雜度有小到大O(2n)、O(n!)、O(nn)
15. 空間複雜度：若輸入資料所占空間隻取決于問題本身，和算法無關，則隻需要分析除輸入和程式之外的輔助變量所占額外空間。

線性表

    線性表是一種典型的線性結構。頭結點無前驅有一個後繼，尾節點無後繼有一個前驅。連結清單隻能順序查找，定位一個元素的時間為O(N)，删除一個元素的時間為O(1)

1. 線性表的順序存儲結構：把線性表的結點按邏輯順序依次存放在一組位址連續的存儲單元裡。用這種方法存儲的線性表簡稱順序表。是一種随機存取的存儲結構。順序存儲指記憶體位址是一塊的，随機存取指通路時可以按下标随機通路，存儲和存取是不一樣的。如果是存儲，則是指按順序的，如果是存取，則是可以随機的，可以利用元素下标進行。數組比線性表速度更快的是：原地逆序、傳回中間節點、選擇随機節點。 
   1. 便于線性表的構造和任意元素的通路
   2. 插入：插入新結點，之後結點後移。平均時間複雜度:O(n)
   3. 删除：删除節點，之後結點前移。平均時間複雜度:O(n)
2. 線性連結清單：用一組任意的存儲單元來依次存放線性表的結點，這組存儲單元即可以是連續的，也可以是不連續的，甚至是零散分布在記憶體中的任意位置上的。是以，連結清單中結點的邏輯次序和實體次序不一定相同。為了能正确表示結點間的邏輯關系，在存儲每個結點值的同時，還必須存儲訓示其後繼結點的位址。data域是資料域，用來存放結點的值。next是指針域（亦稱鍊域），用來存放結點的直接後繼的位址（或位置）。不需要事先估計存儲空間大小。 
   1. 單連結清單中每個結點的存儲位址是存放在其前趨結點next域中，而開始結點無前趨，故應設頭指針head指向開始結點。同時，由于最後一個結點無後繼，故結點的指針域為空，即NULL。頭插法建表(逆序)、尾插法建表(順序)。增加頭結點的目的是算法實作上的友善，但增大了記憶體開銷。 
      1. 查找：隻能從連結清單的頭指針出發，順鍊域next逐個結點往下搜尋，直到搜尋到第i個結點為止。是以，連結清單不是随機存取結構。
      2. 插入：先找到表的第i-1的存儲位置，然後插入。新結點先連後繼，再連前驅。
      3. 删除：首先找到ai-1的存儲位置p。然後令p–>next指向ai的直接後繼結點，即把ai從鍊上摘下。最後釋放結點ai的空間.r=p->next;p->next=r->next;delete r。
      4. 判斷一個單向連結清單中是否存在環的最佳方法是快慢指針。
   2. 靜态連結清單：用一維數組來實作線性連結清單，這種用一維數組表示的線性連結清單，稱為靜态連結清單。靜态：展現在表的容量是一定的。（數組的大小）；連結清單：插入與删除同前面所述的動态連結清單方法相同。靜态連結清單中指針表示的是下一進制素在數組中的位置。
   3. 靜态連結清單是用數組實作的，是順序的存儲結構，在實體位址上是連續的，而且需要預先配置設定大小。動态連結清單是用申請記憶體函數（C是malloc,C++是new）動态申請記憶體的，是以在連結清單的長度上沒有限制。動态連結清單因為是動态申請記憶體的，是以每個節點的實體位址不連續，要通過指針來順序通路。靜态連結清單在插入、删除時也是通過修改指針域來實作的，與動态連結清單沒有什麼分别
   4. 循環連結清單：是一種頭尾相接的連結清單。其特點是無須增加存儲量，僅對表的連結方式稍作改變，即可使得表處理更加友善靈活。 
      1. 在單連結清單中，将終端結點的指針域NULL改為指向表頭結點的或開始結點，就得到了單鍊形式的循環連結清單，并簡單稱為單循環連結清單。由于循環連結清單中沒有NULL指針，故涉及周遊操作時，其終止條件就不再像非循環連結清單那樣判斷p或p—>next是否為空，而是判斷它們是否等于某一指定指針，如頭指針或尾指針等。
   5. 雙向連結清單:在單連結清單的每個結點裡再增加一個指向其直接前趨的指針域prior。這樣就形成的連結清單中有兩個方向不同的鍊。雙連結清單一般由頭指針唯一确定的，将頭結點和尾結點連結起來構成循環連結清單，并稱之為雙向連結清單。設指針p指向某一結點，則雙向連結清單結構的對稱性可用下式描述：p—>prior—>next=p=p—>next—>prior。從兩個方向搜尋雙連結清單，比從一個方向搜尋雙連結清單的方差要小。 
      1. 插入：先搞定插入節點的前驅和後繼，再搞定後結點的前驅，最後搞定前結點的後繼。
      2. 在有序雙向連結清單中定位删除一個元素的平均時間複雜度為O(n)
      3. 可以直接删除目前指針所指向的節點。而不需要像單向連結清單中，删除一個元素必須找到其前驅。是以在插入資料時，單向連結清單和雙向連結清單操作複雜度相同，而删除資料時，雙向連結清單的性能優于單向連結清單

棧和隊列

棧

    棧(Stack)是限制在表的一端進行插入和删除運算的線性表，通常稱插入、删除的這一端為棧頂(Top)，另一端為棧底(Bottom)。先進後出。top= -1時為空棧，top=0隻能說明棧中隻有一個元素，并且元素進棧時top應該自增

1. 順序存儲棧：順序存儲結構
2. 鍊棧：鍊式存儲結構。插入和删除操作僅限制在鍊頭位置上進行。棧頂指針就是連結清單的頭指針。通常不會出現棧滿的情況。 不需要判斷棧滿但需要判斷棧空。
3. 兩個棧共用靜态存儲空間,對頭使用也存在空間溢出問題。棧1的底在v[1]，棧2的底在V[m]，則棧滿的條件是top[1]+1=top[2]。
4. 基本操作：删除棧頂元素、判斷棧是否為空以及将棧置為空棧等
5. 對于n各元素的入棧問題，可能的出棧順序有C(2n,n)/(n+1)個。
6. 堆棧溢出一般是循環的遞歸調用、大資料結構的局部變量導緻的

應用，代碼：

1. 進制轉換
2. 括号比對的檢驗
3. 行編輯程式
4. 迷宮求解：若目前位置“可通”，則納入路徑，繼續前進;若目前位置“不可通”，則後退，換方向繼續探索;若四周“均無通路”，則将目前位置從路徑中删除出去。
5. 表達式求解：字首、中綴、字尾。 
   1. 操作數之間的相對次序不變;
   2. 運算符的相對次序不同;
   3. 中綴式丢失了括弧資訊，緻使運算的次序不确定
   4. 字首式的運算規則為:連續出現的兩個操作數和在它們之前且緊靠它們的運算符構成一個最小表達式
   5. 字尾式的運算規則為:運算符在式中出現的順序恰為表達式的運算順序;每個運算符和在它之前出現且緊靠它的兩個操作數構成一個最小表達式。
6. 實作遞歸：多個函數嵌套調用的規則是：後調用先傳回。
7. 浏覽器曆史紀錄，Android中的最近任務，Activity的啟動模式，CPU中棧的實作，Word自動儲存，解析計算式，解析xml/json。解析XML時，需要校驗節點是否閉合，節點閉合的話，有頭尾符号相對應，遇到頭符号将其放入棧中，遇到尾符号時，彈出棧的内容，看是否有與之對應的頭符号，棧的特性剛好符合符号比對的就近原則。
8. 不是所有的遞歸程式都需要棧來保護現場，比方說求階乘的，是單向遞歸，直接用循環去替代從1乘到n就是結果了，另外一些需要棧儲存的也可以用隊列等來替代。不是所有的遞歸轉化為非遞歸都要用到棧。轉化為非遞歸主要有兩種方法：對于尾遞歸或單向遞歸，可以用循環結構算法代替

隊列

    隊列(Queue)也是一種運算受限的線性表。它隻允許在表的一端進行插入，而在另一端進行删除。允許删除的一端稱為隊頭(front)，允許插入的一端稱為隊尾(rear)。先進先出。

1. 順序隊列：順序存儲結構。當頭尾指針相等時隊列為空。在非空隊列裡，頭指針始終指向隊頭前一個位置，而尾指針始終指向隊尾元素的實際位置
2. 循環隊列。在循環隊列中進行出隊、入隊操作時，頭尾指針仍要加1，朝前移動。隻不過當頭尾指針指向向量上界（MaxSize-1）時，其加1操作的結果是指向向量的下界0。除非向量空間真的被隊列元素全部占用，否則不會上溢。是以，除一些簡單的應用外，真正實用的順序隊列是循環隊列。故隊空和隊滿時頭尾指針均相等。是以，我們無法通過front=rear來判斷隊列“空”還是“滿”
3. 鍊隊列：鍊式存儲結構。限制僅在表頭删除和表尾插入的單連結清單。顯然僅有單連結清單的頭指針不便于在表尾做插入操作，為此再增加一個尾指針，指向連結清單的最後一個結點。
4. 設尾指針的循環連結清單表示隊列,則入隊和出隊算法的時間複雜度均為O(1)。用循環連結清單表示隊列，必定有連結清單的頭結點，入隊操作在連結清單尾插入，直接插入在尾指針指向的節點後面，時間複雜度是常數級的；出隊操作在連結清單表頭進行，也就是删除表頭指向的節點，時間複雜度也是常數級的。
5. 隊空條件：rear==front，但是一般需要引入新的标記來說明棧滿還是棧空，比如每個位置布爾值
6. 隊滿條件：(rear+1) % QueueSize==front，其中QueueSize為循環隊列的最大長度
7. 計算隊列長度：（rear-front+QueueSize）% QueueSize
8. 入隊：（rear+1）% QueueSize
9. 出隊：（front+1）% QueueSize
10. 假設以數組A[N]為容量存放循環隊列的元素,其頭指針是front,目前隊列有X個元素,則隊列的尾指針值為(front+X mod N)

串

    串(String)是零個或多個字元組成的有限序列。長度為零的串稱為空串(Empty String)，它不包含任何字元。通常将僅由一個或多個空格組成的串稱為空白串(Blank String) 注意：空串和空白串的不同，例如“  ”和“”分别表示長度為1的空白串和長度為0的空串。

串的表示和實作：

1. 定長順序存儲表示。靜态存儲配置設定的順序表。
2. 堆配置設定存儲表示。存儲空間是在程式執行過程中動态配置設定而得。是以也稱為動态存儲配置設定的順序表
3. 串的鍊式存儲結構。

串比對：将主串稱為目标串，子串稱之為模式串。蠻力法比對。KMP算法比對。Boyer-Moore算法比對。

數組和廣義表

    數組和廣義表可看成是一種特殊的線性表，其特殊在于: 表中的元素本身也是一種線性表。記憶體連續。根據下标在O(1)時間讀/寫任何元素。

二維數組，多元數組，廣義表、樹、圖都屬于非線性結構

數組

1. 數組的順序存儲：行優先順序；列優先順序。數組中的任一進制素可以在相同的時間記憶體取，即順序存儲的數組是一個随機存取結構。
2. 關聯數組(Associative Array)，又稱映射（Map）、字典（ Dictionary）是一個抽象的資料結構，它包含着類似于(鍵，值)的有序對。 不是線性表。
3. 矩陣的壓縮：
   1. 對稱矩陣、三角矩陣：直接存儲矩陣的上三角或者下三角元素。注意區分i>=j和i

廣義表

    廣義表（Lists，又稱清單）是線性表的推廣。廣義表是n(n≥0)個元素a1,a2,a3,…,an的有限序列，其中ai或者是原子項，或者是一個廣義表。若廣義表LS（n>=1)非空，則a1是LS的表頭，其餘元素組成的表(a2,…an)稱為LS的表尾。廣義表的元素可以是廣義表，也可以是原子，廣義表的元素也可以為空。表尾是指除去表頭後剩下的元素組成的表，表頭可以為表或單元素值。是以表尾不可以是單個元素值。

例子：

1. A=（）——A是一個空表，其長度為零。
2. B=（e）——表B隻有一個原子e，B的長度為1。
3. C=（a,(b,c,d))——表C的長度為2，兩個元素分别為原子a和子表(b,c,d)。
4. D=（A，B，C）——表D的長度為3，三個元素都是廣義 表。顯然，将子表的值代入後，則有D=(( ),(e),(a,(b,c,d)))。
5. E=（a,E）——這是一個遞歸的表，它的長度為2，E相當于一個無限的廣義表E=(a,(a,(a,(a,…)))).

三個結論：

1. 廣義表的元素可以是子表，而子表的元素還可以是子表。由此，廣義表是一個多層次的結構，可以用圖形象地表示
2. 廣義表可為其它表所共享。例如在上述例4中，廣義表A，B，C為D的子表，則在D中可以不必列出子表的值，而是通過子表的名稱來引用。
3. 廣義表的遞歸性

考點：

1. 廣義表是0個或多個單因素或子表組成的有限序列，廣義表可以是自身的子表，廣義表的長度n>=0，是以可以為空表。廣義表的同級元素(直屬于同一個表中的各元素)具有線性關系
2. 廣義表的表頭為空，并不代表該廣義表為空表。廣義表()和(())不同。前者是長度為0的空表，對其不能做求表頭和表尾的運算；而後者是長度為l的非空表(隻不過該表中惟一的一個元素是空表)，對其可進行分解，得到的表頭和表尾均是空表()
3. 已知廣義表LS＝((a,b,c),(d,e,f)),運用head和tail函數取出LS中原子e的運算是head(tail(head(tail(LS)))。根據表頭、表尾的定義可知：任何一個非空廣義表的表頭是表中第一個元素，它可以是原子，也可以是子表，而其表尾必定是子表。也就是說，廣義表的head操作，取出的元素是什麼，那麼結果就是什麼。但是tail操作取出的元素外必須加一個表——“（）“。tail(LS)＝((d,e,f))；head(tail(LS))=(d,e,f)；tail(head(tail(LS)))=(e,f)；head(tail(head(tail(LS))))=e。
4. 二維以上的數組其實是一種特殊的廣義表
5. 在（非空）廣義表中：1、表頭head可以是原子或者一個表 2、表尾tail一定是一個表 3.廣義表難以用順序存儲結構 4.廣義表可以是一個多層次的結構

樹和二叉樹

    一種非線性結構。樹是遞歸結構，在樹的定義中又用到了樹的概念。

基本術語：

1. 樹結點：包含一個資料元素及若幹指向子樹的分支；
2. 孩子結點：結點的子樹的根稱為該結點的孩子；
3. 雙親結點：B結點是A結點的孩子，則A結點是B結點的雙親；
4. 兄弟結點：同一雙親的孩子結點；
5. 堂兄結點：同一層上結點；
6. 結點層次：根結點的層定義為1；根的孩子為第二層結點，依此類推；
7. 樹的高（深）度：樹中最大的結點層
8. 結點的度：結點子樹的個數
9. 樹的度： 樹中最大的結點度。
10. 葉子結點：也叫終端結點，是度為0的結點；
11. 分枝結點：度不為0的結點（非終端結點）；
12. 森林：互不相交的樹集合；
13. 有序樹：子樹有序的樹，如：家族樹；
14. 無序樹：不考慮子樹的順序；

二叉樹

    二叉樹可以為空。二叉樹結點的子樹要區分左子樹和右子樹，即使隻有一棵子樹也要進行區分，說明它是左子樹，還是右子樹。這是二叉樹與樹的最主要的差别。注意區分：二叉樹、二叉查找樹/二叉排序樹/二叉搜尋樹、二叉平衡(查找)樹

    二叉平衡樹肯定是一顆二叉排序樹。堆不是一顆二叉平衡樹。

    二叉樹與樹是不同的，二叉樹不等價于分支樹最多為二的有序樹。當一個結點隻包含一個子節點時，對于有序樹并無左右孩子之分，而對于二叉樹來說依然有左右孩子之分，是以二叉樹與樹是兩種不同的結構。

性質：

1. 在二叉樹的第 i 層上至多有2i-1個結點。
2. 深度為 k 的二叉樹上至多含 2k-1 個結點（k≥1）
3. 對任何一棵二叉樹，若它含有n0個葉子結點、n2個度為 2 的結點，則必存在關系式：n0= n2+1。
4. 具有 n 個結點的完全二叉樹的深度為⎣log2 n⎦+1 。
5. n個結點的二叉樹中，完全二叉樹具有最小的路徑長度。
6. 如果對一棵有n個結點的完全二叉樹的結點按層序編号,則對任一結點i（1<=i<=n),有： 
   1. 如果i＝1，則結點i無雙親，是二叉樹的根；如果i>1，則其雙親的編号是 i/2(整除）。
   2. 如果2i>n，無左孩子；否則，其左孩子是結點2i。
   3. 如果2i＋1>n，則結點i無右孩子；否則，其右孩子是結點2i＋1。

二叉樹的存儲結構

1. 順序存儲結構：僅僅适用于滿或完全二叉樹，結點之間的層次關系由性質5确定。
2. 二叉連結清單法：每個節點存儲左子樹和右子樹。三叉連結清單：左子樹、右子樹、父節點，總的指針是n+2
3. 在有n個結點的二叉連結清單中，值為非空的鍊域的個數為n-1。在有N個結點的二叉連結清單中必定有2N個鍊域。除根結點外，其餘N-1個結點都有一個父結點。是以，一共有N-1個非空鍊域，其餘2N-(N-1)=N+1個為空鍊域。
4. 二叉鍊存儲法也叫孩子兄弟法，左指針指向左孩子，右指針指向右兄弟。而中序周遊的順序是左孩子，根，右孩子。這種周遊順序與存儲結構不同，是以需要堆棧儲存中間結果。而中序周遊檢索二叉樹時，由于其存儲結構跟周遊順序相符，是以不需要用堆棧。

周遊二叉樹和線索二叉樹

    周遊二叉樹：使得每一個結點均被通路一次，而且僅被通路一次。非遞歸的周遊實作要利用棧。

• 先序周遊DLR：根節點->左子樹->右子樹
• 中序周遊LDR：左子樹->根節點->右子樹。必須要有中序周遊才能得到一棵二叉樹的正确順序
• 後續周遊LRD：左子樹->右子樹->根節點。需要棧的支援。

• 層次周遊：用一維數組存儲二叉樹時,總是以層次周遊的順序存儲結點。層次周遊應該借助隊列。
• 線索二叉樹：對二叉樹所有結點做某種處理可在周遊過程中實作；檢索（查找）二叉樹某個結點，可通過周遊實作；如果能将二叉樹線索化，就可以簡化周遊算法，提高周遊速度，目的是加快查找結點的前驅或後繼的速度。

1. 如何線索化？以中序周遊為例，若能将中序序列中每個結點前趨、後繼資訊儲存起來，以後再周遊二叉樹時就可以根據所儲存的結點前趨、後繼資訊對二叉樹進行周遊。對于二叉樹的線索化，實質上就是周遊一次二叉樹，隻是在周遊的過程中，檢查目前結點左，右指針域是否為空，若為空，将它們改為指向前驅結點或後繼結點的線索。前驅就是在這一點之前走過的點，不是下一将要去往的點。
2. 加上結點前趨後繼資訊（結索）的二叉樹稱為線索二叉樹。n個結點的線索二叉樹上每個結點有2個指針域（指向左孩子和右孩子），總共有2n個指針域；一個n個結點的樹有n-1條邊，那麼空指針域= 2n - (n-1) = n + 1，即線索數為n+1。指針域tag為0，存放孩子指針，為1，存放前驅/後繼節點指針。
3. 線索樹下結點x的前驅與後繼查找：設結點x相應的左（右）标志是線索标志，則lchild(rchild)就是前驅(後繼），否則：
   1. LDR–前驅：左子樹中最靠右邊的結點；後繼：右子樹中最靠左邊的結點
   2. LRD–前驅：右子樹的根，若無右子樹，為左子樹跟。後繼：x是根，後繼是空；x是雙親的右孩子、x是雙親的左孩子，但雙親無右孩子，雙親是後繼；x是雙親的左孩子，雙親有右孩子，雙親右子樹中最左的葉子是後繼
   3. DLR–對稱于LRD線索樹—将LRD中所有左右互換，前驅與後繼互換，得到DLR的方法。
   4. 為簡化線索連結清單的周遊算法，仿照線性連結清單，為線索連結清單加上一頭結點，約定： 
      1. 頭結點的lchild域：存放線索連結清單的根結點指針；
      2. 頭結點的rchild域: 中序序列最後一個結點的指針；
      3. 中序序列第一結點lchild域指向頭結點;
      4. 中序序列最後一個結點的rchild域指向頭結點;

中序周遊的線索二叉樹以及線索二叉樹連結清單示意圖 、

1. 一棵左右子樹均不空的二叉樹在前序線索化後,其中空的鍊域的個數是1。
2. 前序和後續線索化後空鍊域個數都是1，中序是2。
3. 二叉樹線上索化後，仍不能有效求解的問題是前序求前序先驅，後序求後序後繼。

中序周遊的順序為：左、根、右，是以對于每一非空的線索，左子樹結點的後繼為根結點，右子樹結點的前驅為根結點，再遞歸的執行上面的過程，可得非空線索均指向其祖先結點。在中序線索二叉樹中,每一非空的線索均指向其祖先結點。

在二叉樹上加上結點前趨、後繼線索後，可利用線索對二叉樹進行周遊,此時，不需棧，也不需遞歸。基本步驟：

1. p=T->lchild; p指向線索連結清單的根結點；
2. 若線索連結清單非空，循環： 
   1. 循環，順着p左孩子指針找到最左下結點；通路之；
   2. 若p所指結點的右孩子域為線索，p的右孩子結點即為後繼結點循環： p=p->rchild； 并通路p所指結點；（在此循環中，順着後繼線索通路二叉樹中的結點）
   3. 一旦線索“中斷”，p所指結點的右孩子域為右孩子指針，p=p->rchild，使 p指向右孩子結點；

樹和森林

    樹的存儲結構：

1. 雙親表示法
2. 孩子表示法
3. 利用圖表示樹
4. 孩子兄弟表示法（二叉樹表示法）：連結清單中每個結點的兩指針域分别指向其第一個孩子結點和下一個兄弟結點

将樹轉化成二叉樹：右子樹一定為空

1. 加線：在兄弟之間加一連線
2. 抹線：對每個結點，除了其左孩子外，去除其與其餘孩子之間的關系
3. 旋轉：以樹的根結點為軸心，将整樹順時針轉45°

森林轉換成二叉樹：

1. 将各棵樹分别轉換成二叉樹
2. 将每棵樹的根結點用線相連
3. 以第一棵樹根結點為二叉樹的根
4. 樹與轉換後的二叉樹的關系：轉換後的二叉樹的先序對應樹的先序周遊；轉換後的二叉樹的中序對應樹的後序周遊

哈弗曼樹/霍夫曼樹

1. 路徑：從一個祖先結點到子孫結點之間的分支構成這兩個結點間的路徑；
2. 路徑長度：路徑上的分支數目稱為路徑長度；
3. 樹的路徑長度：從根到每個結點的路徑長度之和。
4. 結點的權：根據應用的需要可以給樹的結點賦權值；
5. 結點的帶權路徑長度：從根到該結點的路徑長度與該結點權的乘積；
6. 樹的帶權路徑長度=樹中所有葉子結點的帶權路徑之和；通常記作 WPL=∑wi×li
7. 哈夫曼樹：假設有n個權值(w1, w2, … , wn)，構造有n個葉子結點的二叉樹，每個葉子結點有一個 wi作為它的權值。則帶權路徑長度最小的二叉樹稱為哈夫曼樹。最優二叉樹。字首碼的定義：在一個字元集中，任何一個字元的編碼都不是另一個字元編碼的字首。霍夫曼編碼就是字首碼，可用于快速判斷霍夫曼編碼是否正确。霍夫曼樹是滿二叉樹，若有n個節點，則共有(n+1)/2個碼子

給定n個權值作為n的葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為霍夫曼樹(Huffman Tree)。霍夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。

假設哈夫曼樹是二叉的話，則度為0的結點個數為N，度為2的結點個數為N-1，則結點總數為2N-1。哈夫曼樹的結點個數必為奇數。

哈夫曼樹不一定是完全二叉樹，但一定是最優二叉樹。

若度為m的哈夫曼樹中,其葉結點個數為n,則非葉結點的個數為[(n-1)/(m-1)]。邊的數目等于度。

圖周遊與回溯

    圖搜尋->形成搜尋樹

1. 窮舉法。
2. 貪心法。多步決策，每步選擇使得構成一個問題的可能解，同時滿足目标函數。
3. 回溯法。根據題意，選取度量标準，然後将可能的選擇方法按度量标準所要求順序排好，每次處理一個量，得到該意義下的最優解的分解處理。

圖

    無向圖

1. 回路或環：第一個頂點和最後一個頂點相同的路徑。
2. 簡單回路或簡單環：除第一個頂點和最後一個頂點之外，其餘頂點不重複出現的回路
3. 連通：頂點v至v’ 之間有路徑存在
4. 連通圖：無向圖圖 G 的任意兩點之間都是連通的，則稱G是連通圖。
5. 連通分量：極大連通子圖，子圖中包含的頂點個數極大
6. 所有頂點度的和必須為偶數

有向圖：

1. 回路或環：第一個頂點和最後一個頂點相同的路徑。
2. 簡單回路或簡單環：除第一個頂點和最後一個頂點之外，其餘頂點不重複出現的回路。
3. 連通：頂點v至v’之間有路徑存在
4. 強連通圖：有向圖G的任意兩點之間都是連通的，則稱G是強連通圖。各個頂點間均可達。
5. 強連通分量：極大連通子圖
6. 有向圖頂點的度是頂點的入度與出度之和。鄰接矩陣中第V行中的1的個數是V的出度
7. 生成樹：極小連通子圖。包含圖的所有n個結點，但隻含圖的n-1條邊。在生成樹中添加一條邊之後，必定會形成回路或環。
8. 完全圖：有 n(n-1)/2 條邊的無向圖。其中n是結點個數。必定是連通圖。
9. 有向完全圖：有n(n-1)條邊的有向圖。其中n是結點個數。每兩個頂點之間都有兩條方向相反的邊連接配接的圖。
10. 一個無向圖 G=(V,E) 是連通的，那麼邊的數目大于等于頂點的數目減一：|E|>=|V|-1，而反之不成立。如果 G=(V,E) 是有向圖，那麼它是強連通圖的必要條件是邊的數目大于等于頂點的數目：|E|>=|V|，而反之不成立。沒有回路的無向圖是連通的當且僅當它是樹，即等價于：|E|=|V|-1。

圖的存儲形式

    鄰接矩陣和權重鄰接矩陣 

1. 無權有向圖：出度: i行之和；入度: j列之和。
2. 無權無向圖：i結點的度: i行或i列之和。
3. 權重鄰接矩陣：相連為w，不相連為∞

鄰接表 

1. 用頂點數組表、邊（弧）表表示該有向圖或無向圖
2. 頂點數組表：用數組存放所有的頂點。數組大小為圖頂點數n
3. 邊表（邊結點表）：每條邊用一個結點進行表示。同一個結點的所有的邊形成它的邊結點單連結清單。
4. n個頂點的無向圖的鄰接表最多有n(n-1)個邊表結點。有n個頂點的無向圖最多有n*(n-1)/2條邊，此時為完全無向圖，而在鄰接表中每條邊存儲兩次，是以有n*(n-1)個結點

圖的周遊

    深度優先搜尋利用棧，廣度優先搜尋利用隊列

求一條從頂點i到頂點s的簡單路徑–深搜。求兩個頂點之間的一條長度最短的路徑–廣搜。當各邊上的權值均相等時,BFS算法可用來解決單源最短路徑問題。

生成樹和最小生成樹

每次周遊一個連通圖将圖的邊分成周遊所經過的邊和沒有經過的邊兩部分，将周遊經過的邊同圖的頂點構成一個子圖，該子圖稱為生成樹。是以有DFS生成樹和BFS生成樹。

生成樹是連通圖的極小子圖，有n個頂點的連通圖的生成樹必定有n-1條邊,在生成樹中任意增加一條邊，必定産生回路。若砍去它的一條邊，就會把生成樹變成非連通子圖

最小生成樹：生成樹中邊的權值(代價)之和最小的樹。最小生成樹問題是構造連通網的最小代價生成樹。

Kruskal算法：令最小生成樹集合T初始狀态為空，在有n個頂點的圖中選取代價最小的邊并從圖中删去。若該邊加到T中有回路則丢棄，否則留在T中；依此類推，直至T中有n-1條邊為止。

Prim算法、Kruskal算法和Dijkstra算法均屬于貪心算法。

1. Dijkstra算法解決的是帶權重的有向圖上單源最短路徑問題，該算法要求所有邊的權重都為非負值。
2. Dijkstra算法解決了從某個原點到其餘各頂點的最短路徑問題，由循環嵌套可知該算法的時間複雜度為O(N*N)。若要求任一頂點到其餘所有頂點的最短路徑，一個比較簡單的方法是對每個頂點當做源點運作一次該算法，等于在原有算法的基礎上，再來一次循環，此時整個算法的複雜度就變成了O(N*N*N)。
3. Bellman-Ford算法解決的是一般情況下的單源最短路徑問題，在這裡，邊的權重可以為負值。該算法傳回一個布爾值，以表明是否存在一個從源節點可以到達的權重為負值的環路。如果存在這樣一個環路，算法将告訴我們不存在解決方案。如果沒有這種環路存在，算法将給出最短路徑和它們的權重。

雙連通圖和關節點

若從一個連通圖中删去任何一個頂點及其相關聯的邊，它仍為一個連通圖的話，則該連通圖被稱為重（雙）連通圖。

若連通圖中的某個頂點和其相關聯的邊被删去之後，該連通圖被分割成兩個或兩個以上的連通分量，則稱此頂點為關節點。

沒有關節點的連通圖為雙連通圖

1. 若生成樹的根結點，有兩個或兩個以上的分支，則此頂點(生成樹的根)必為關節點；
2. 對生成樹上的任意一個非葉“頂點”，若其某棵子樹中的所有“頂點”沒有和其祖先相通的回邊，則該“頂點”必為關節點。

有向無環圖及其應用

拓撲排序。在用鄰接表表示圖時,對有n個頂點和e條弧的有向圖而言時間複雜度為O(n+e)。一個有向圖能被拓撲排序的充要條件就是它是一個有向無環圖。拓撲序列唯一不能唯一确定有向圖。

AOV網(Activity On Vertex)：用頂點表示活動，邊表示活動的優先關系的有向圖稱為AOV網。AOV網中不允許有回路，這意味着某項活動以自己為先決條件。

拓撲有序序列：把AOV網絡中各頂點按照它們互相之間的優先關系排列一個線性序列的過程。若vi是vj前驅，則vi一定在vj之前；對于沒有優先關系的點，順序任意。

拓撲排序：對AOV網絡中頂點構造拓撲有序序列的過程。方法：

1. 在有向圖中選一個沒有前驅的頂點且輸出之
2. 從圖中删除該頂點和所有以它為尾的弧
3. 重複上述兩步，直至全部頂點均已輸出；或者當圖中不存在無前驅的頂點為止(此時說明圖中有環）

采用深度優先搜尋或拓撲排序算法可以判斷出一個有向圖中是否有環(回路).深度優先搜尋隻要在其中記錄下搜尋的節點數n，當n大于圖中節點數時退出，并可以得出有回路。若有回路，則拓撲排序通路不到圖中所有的節點，是以也可以得出回路。廣度優先搜尋過程中如果通路到一個已經通路過的節點，可能是多個節點指向這個節點，不一定是存在環。

算法描述：

1. 把鄰接表中入度為0的頂點依此進棧
2. 若棧不空，則 
   1. 棧頂元素vj退棧并輸出；
   2. 在鄰接表中查找vj的直接後繼vk，把vk的入度減1；若vk的入度為0則進棧
3. 若棧空時輸出的頂點個數不是n，則有向圖有環；否則，拓撲排序完畢。

AOE網：帶權的有向無環圖，其中頂點表示事件，弧表示活動，權表示活動持續時間。在工程上常用來表示工程進度計劃。

一些定義：

1. 事件的最早發生時間（ve(j)）：從源點到j結點的最長的路徑。意味着事件最早能夠發生的時間。
2. 事件的最遲發生時間（vl(j)）：不影響工程的如期完工，事件j必須發生的時間。
3. 活動ai由弧

查找

順序查找、折半查找、索引查找、分塊查找是靜态查找，動态查找有二叉排序樹查找，最優二叉樹查找，鍵樹查找，哈希表查找

靜态查找表

順序表的順序查找：應用範圍：順序表或線性連結清單表示的表，表内元素之間無序。查找過程：從表的一端開始逐個進行記錄的關鍵字和給定值的比較。

順序有序表的二分查找。平均查找時間(n+1)/n log2(n+1)

分塊查找：将表分成幾塊，塊内無序，塊間有序，即前一塊中的最大值小于後一塊中的最小值。并且有一張索引表，每一項存放每一塊的最大值和指向該塊第一個元素的指針。索引表有序，塊内無序。是以，塊間查找用二分查找，塊内用順序查找，效率介于順序和二分之間；先确定待查記錄所在塊，再在塊内查找。是以跟表中元素個數和塊中元素個數都有關。

1. 用數組存放待查記錄,
2. 建立索引表，由每塊中最大（小）的關鍵字及所屬塊位置的資訊組成。
3. 當索引表較大時，可以采用二分查找
4. 在資料量極大時，索引可能很多，可考慮建立索引表的索引，即二級索引，原則上索引不超過三級

分塊查找平均查找長度：ASLbs = Lb + Lw。其中，Lb是查找索引表确定所在塊的平均查找長度， Lw是在塊中查找元素的平均查找長度。在n一定時，可以通過選擇s使ASL盡可能小。當s=sqrt(n)時，ASL最小。

1. 時間：順序查找最差，二分最好，分塊介于兩者之間
2. 空間：分塊最大，需要增加索引資料的空間
3. 順序查找對表沒有特殊要求
4. 分塊時資料塊之間在實體上可不連續。是以可以達到插入、删除資料隻涉及對應的塊；另外，增加了索引的維護。
5. 二分查找要求表有序，是以若表的元素的插入與删除很頻繁，維持表有序的工作量極大。
6. 在表不大時，一般直接使用順序查找。

動态查找

二叉排序樹的結點删除：

1. x為葉子結點，則直接删除
2. x隻有左子樹xL或隻有右子樹xR ,則令xL或xR直接成為雙親結點f的子樹；
3. x即有左子樹xL也有右子樹xR，在xL中選值最大的代替x，該資料按二叉排序樹的性質應在最右邊。

平衡二叉樹：每個結點的平衡因子都為 1、－1、0 的二叉排序樹。或者說每個結點的左右子樹的高度最多差1的二叉排序樹。

平衡二叉樹的平衡：

1. 左調整(新結點插入在左子樹上的調整)： 
   1. LL(插入在結點左子樹的左子樹上)：旋轉前後高度都為h+1
   2. LR(新插入結點在左子樹的右子樹上)：旋轉前後高度仍為h+1
2. 右調整(新結點插入在右子樹上進行的調整): 
   1. RR(插入在的右子樹的右子樹上)：處理方法和 LL對稱
   2. RL(插入在的右子樹的左子樹上)：處理方法和 LR對稱

平衡樹建立方法：

1. 按二叉排序樹插入結點
2. 如引起結點平衡因子變為|2|，則确定旋轉點，該點是離根最遠（或最接近于葉子的點）
3. 确定平衡類型後進行平衡處理，平衡後以平衡點為根的子樹高不變
4. 最小二叉平衡樹的節點的公式如下 F(n)=F(n-1)+F(n-2)+1 這個類似于一個遞歸的數列，可以參考Fibonacci數列，1是根節點，F(n-1)是左子樹的節點數量，F(n-2)是右子樹的節點數量。

常見的平衡二叉樹：

1. 紅黑樹是平衡二叉樹，也就是左右子樹是平衡的，高度大概相等。這種情況等價于一塊完全二叉樹的高度，查找的時間複雜度是樹的高度，為logn，插入操作的平均時間複雜度為O(logn)，最壞時間複雜度為O(logn) 
   1. 節點是紅色或黑色。
   2. 根是黑色。
   3. 所有葉子都是黑色（葉子是NIL節點）。
   4. 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)
   5. 從任一節點到其每個葉子的所有簡單路徑 都包含相同數目的黑色節點。
2. avl樹也是自平衡二叉樹；紅黑樹和AVL樹查找、插入、删除的時間複雜度相同；包含n個内部結點的紅黑樹的高度是o(logn); TreeMap 是一個紅黑樹的實作，能保證插入的值保證排序
3. STL和linux多使用紅黑樹作為平衡樹的實作： 
   1. 如果插入一個node引起了樹的不平衡，AVL和RB-Tree都是最多隻需要2次旋轉操作，即兩者都是O(1)；但是在删除node引起樹的不平衡時，最壞情況下，AVL需要維護從被删node到root這條路徑上所有node的平衡性，是以需要旋轉的量級O(logN)，而RB-Tree最多隻需3次旋轉，隻需要O(1)的複雜度。
   2. 其次，AVL的結構相較RB-Tree來說更為平衡，在插入和删除node更容易引起Tree的unbalance，是以在大量資料需要插入或者删除時，AVL需要rebalance的頻率會更高。是以，RB-Tree在需要大量插入和删除node的場景下，效率更高。自然，由于AVL高度平衡，是以AVL的search效率更高。
   3. map的實作隻是折衷了兩者在search、insert以及delete下的效率。總體來說，RB-tree的統計性能是高于AVL的。

查找總結

1. 既希望較快的查找又便于線性表動态變化的查找方法是哈希法查找。二叉排序樹查找，最優二叉樹查找，鍵樹查找，哈希法查找是動态查找。分塊、順序、折半、索引順序查找均為靜态。分塊法應該是将整個線性表分成若幹塊進行儲存，若動态變化則可以添加在表的尾部（非順序結構），時間複雜度是O(1)，查找複雜度為O(n)；若每個表内部為順序結構，則可用二分法将查找時間複雜度降至O(logn)，但同時動态變化複雜度則變成O(n)；順序法是挨個查找，這種方法最容易實作，不過查找時間複雜度都是O(n)，動态變化時可将儲存值放入線性表尾部，則時間複雜度為O(1)；二分法是基于順序表的一種查找方式，時間複雜度為O(logn)；通過哈希函數将值轉化成存放該值的目标位址，O（1）
2. 二叉樹的平均查找長度為O(log2n)——O(n).二叉排序樹的查找效率與二叉樹的高度有關，高度越低，查找效率越高。二叉樹的查找成功的平均查找長度ASL不超過二叉樹的高度。二叉樹的高度與二叉樹的形态有關，n個節點的完全二叉樹高度最小，高度為[log2n]+1,n個節點的單隻二叉樹的高度最大，高度為n，此時查找成功的ASL為最大(n+1)/2，是以二叉樹的高度範圍為[log2n]+1——n.
3. 鍊式存儲不能随機通路，必須是順序存儲

B_樹的B+樹

B_樹

    B-樹就是B樹。m階B_樹滿足或空，或為滿足下列性質的m叉樹：

1. 樹中每個結點最多有m棵子樹
2. 根結點在不是葉子時，至少有兩棵子樹
3. 除根外，所有非終端結點至少有⎡m/2⎤棵子樹
4. 有s個子樹的非葉結點具有 n = s-1個關鍵字，結點的資訊組織為:(n,A0,K1,A1,K2,A2 … Kn，An)。這裡：n為關鍵字的個數，ki（i=1,2,…,n)為關鍵字，且滿足Ki小于Ki+1,，Ai(i=0,1,..n)為指向子樹的指針。
5. 所有的葉子結點都出現在同一層上，不帶資訊（可認為外部結點或失敗結點）。
6. 關鍵字集合分布在整顆樹中
7. 任何一個關鍵字出現且隻出現在一個結點中
8. 搜尋有可能在非葉子結點結束
9. 其搜尋性能等價于在關鍵字全集内做一次二分查找
10. 隻适用于随機檢索，不适用于順序檢索。
11. 有結點的平衡因子都為零
12. M階B-樹中含有N個關鍵字，最大深度為log⎡m/2⎤(n+1)/2+2

B_樹中結點的插入

1. m代表B_樹的階，插入總發生在最低層
2. 插入後關鍵字個數小于等于 m-1,完成。
3. 插入後關鍵字個數等于m,結點分裂，以中點資料為界一分為二，中點資料放到雙親結點中。這樣就有可能使得雙親結點的資料個數為m,引起雙親結點的分裂，最壞情況下一直波及到根，引起根的分裂——B_樹長高。

3階B_樹的插入。每個結點最多3棵子樹，2個資料；最少2棵子樹，1個資料。是以3階B_樹也稱為2-3樹。

B_樹中結點的删除

1. 删除發生在最底層 
   1. 被删關鍵字所在結點中的關鍵字數目大于等于 m/2 ，直接删除。
   2. 删除後結點中資料為⎡m/2⎤-2，而相鄰的左（右）兄弟中資料大于⎡m/2⎤-1，此時左（右兄弟）中最大（小）的資料上移到雙親中，雙親中接（靠）在它後（前）面的資料移到被删資料的結點中
   3. 其左右兄弟結點中資料都是⎡m/2⎤-1，此時和左（右）兄弟合并，合并時連同雙親中相關的關鍵字。此時，雙親中少了一項，是以又可能引起雙親的合并，最壞一直到根，使B-樹降低一層。
2. 删除不在最底層 
   1. 在大于被删資料中選最小的代替被删資料，問題轉換成在最底層的删除

B+樹

    在實際的檔案系統中，用的是B+樹或其變形。有關性質與操作類似與B_樹。

差異：

1. 有n棵子樹的結點中有n個關鍵字，每個關鍵字不儲存資料，隻用來索引，所有資料都儲存在葉子節點。
2. 所有葉子結點中包含全部關鍵字資訊，及對應記錄位置資訊及指向含有這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大的順序連結。(而B樹的葉子節點并沒有包括全部需要查找的資訊)
3. 所有非葉子為索引，結點中僅含有其子樹根結點中最大（或最小）關鍵字。 (而B樹的非終節點也包含需要查找的有效資訊)
4. 非葉最底層順序聯結，這樣可以進行順序查找

B+特性

1. 所有關鍵字都出現在葉子結點的連結清單中（稠密索引），且連結清單中的關鍵字恰好是有序的；
2. 不可能在非葉子結點命中
3. 非葉子結點相當于是葉子結點的索引（稀疏索引），葉子結點相當于是存儲（關鍵字）資料的資料層
4. 更适合檔案索引系統
5. B+樹插入操作的平均時間複雜度為O(logn)，最壞時間複雜度為O(logn)

查找過程

• 在 B+ 樹上，既可以進行縮小範圍的查找，也可以進行順序查找；
• 在進行縮小範圍的查找時，不管成功與否，都必須查到葉子結點才能結束；
• 若在結點内查找時，給定值≤Ki， 則應繼續在 Ai 所指子樹中進行查找

插入和删除的操作：類似于B_樹進行，即必要時，也需要進行結點的“分裂”或“合并”。

為什麼說B+tree比B樹更适合實際應用中作業系統的檔案索引和資料庫索引？

1. B+tree的磁盤讀寫代價更低 
   1. B+tree的内部結點并沒有指向關鍵字具體資訊的指針。是以其内部結點相對B 樹更小。如果把所有同一内部結點的關鍵字存放在同一盤塊中，那麼盤塊所能容納的關鍵字數量也越多。一次性讀入記憶體中的需要查找的關鍵字也就越多。相對來說IO讀寫次數也就降低了。
   2. 舉個例子，假設磁盤中的一個盤塊容納16bytes，而一個關鍵字2bytes，一個關鍵字具體資訊指針2bytes。一棵9階B-tree(一個結點最多8個關鍵字)的内部結點需要2個盤快。而B+樹内部結點隻需要1個盤快。當需要把内部結點讀入記憶體中的時候，B樹就比B+樹多一次盤塊查找時間(在磁盤中就是盤片旋轉的時間)。
2. B+tree的查詢效率更加穩定 
   1. 由于非終結點并不是最終指向檔案内容的結點，而隻是葉子結點中關鍵字的索引。是以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導緻每一個資料的查詢效率相當。

B樹和B+樹都是平衡的多叉樹。B樹和B+樹都可用于檔案的索引結構。B樹和B+樹都能有效的支援随機檢索。B+樹既能索引查找也能順序查找.

哈希表

1. 在記錄的存儲位址和它的關鍵字之間建立一個确定的對應關系；這樣不經過比較，一次存取就能得到元素。
2. 哈希函數——在記錄的關鍵字與記錄的存儲位置之間建立的一種對應關系。是從關鍵字空間到存儲位置空間的一種映象。
3. 哈希表——應用哈希函數，由記錄的關鍵字确定記錄在表中的位置資訊，并将記錄根據此資訊放入表中，這樣構成的表叫哈希表。
4. Hash查找适合于關鍵字可能出現的值的集合遠遠大于實際關鍵字集合的情形。
5. 更适合查找，不适合頻繁更新
6. Hash表等查找複雜依賴于Hash值算法的有效性，在最好的情況下，hash表查找複雜度為O(1)。隻有無沖突的hash_table複雜度才是O(1)。一般是O(c)，c為哈希關鍵字沖突時查找的平均長度。插入，删除，查找都是O(1)。平均查找長度不随表中結點數目的增加而增加,而是随負載因子的增大而增大
7. 由于沖突的産生，使得哈希表的查找過程仍然是一個給定值與關鍵字比較的過程。

根據抽屜原理，沖突是不可能完全避免的，是以，選擇好的散列函數和沖突處理方法：

1. 構造一個性能好，沖突少的Hash函數
2. 如何解決沖突

常用的哈希函數

1. 直接定址法。僅适合于：位址集合的大小 == 關鍵字集合的大小
2. 數字分析法。對關鍵字進行分析，取關鍵字的若幹位或其組合作哈希位址。僅适合于：能預先估計出全體關鍵字的每一位上各種數字出現的頻度。
3. 平方取中法。以關鍵字的平方值的中間幾位作為存儲位址。
4. 折疊法。将關鍵字分割成位數相同的幾部分，然後取這幾部分的疊加和（舍去進位）做哈希位址。移位疊加/間界疊加。适合于: 關鍵字的數字位數特别多，且每一位上數字分布大緻均勻情況。
5. 除留餘數法。取關鍵字被某個不大于哈希表表長m的數p除後所得餘數作哈希位址，即H(key)=key%p，p<=m。
6. 随機數法。取關鍵字的僞随機函數值作哈希位址，即H(key)=random(key)，适于關鍵字長度不等的情況。

沖突解決

1. 開放定址法。當沖突發生時，形成一個探查序列；沿此序列逐個位址探查，直到找到一個空位置（開放的位址），将發生沖突的記錄放到該位址中。即Hi=(H(key)+di) % m，i=1,2,……k(k<=m-1)，H(key)哈希函數，m哈希表長，di增量序列。缺點：删除：隻能作标記，不能真正删除；溢出；載因子過大、解決沖突的算法選擇不好會發生聚集問題。要求裝填因子α較小，故當結點規模較大時會浪費很多空間。 
   1. 線性探測再散列：di=1，2，3，…，m-1
   2. 二次探測再散列：di=12,-12,22,-22,…，±k2（k<=m/2）
   3. 僞随機探測再散列: di為僞随機數序列
2. 鍊位址法：将所有關鍵字為同義詞的記錄存儲在一個單連結清單中，并用一維數組存放頭指針。拉鍊法中可取α≥1，且結點較大時，拉鍊法中增加的指針域可忽略不計，是以節省空間。一旦發生沖突，在目前位置給單連結清單增加結點就行。
3. 其他方法：再哈希法、建立公共溢出區
4. 在用拉鍊法構造的散清單中，删除結點的操作易于實作。拉鍊法的缺點是：指針需要額外的空間，故當結點規模較小時，開放定址法較為節省空間。由于拉鍊法中各連結清單上的結點空間是動态申請的,故它更适合于造表前無法确定表長的情況。拉鍊法解決沖突時，需要使用指針，訓示下一個元素的存儲位置
5. 開哈希表–鍊式位址法;閉哈希表–開放位址法.開哈希和閉哈希主要的差別在于，随着哈希表的密集度提高，使用閉哈希時，不僅會與相同哈希值的元素發生沖突，還容易與不同哈希值的元素發生沖突；而開哈希則不受哈希表疏密與否的影響，始終隻會與相同哈希值的元素沖突而已。是以在密集度變大的哈希表中查找時，顯然開哈希的平均搜尋長度不會增長。
6. 設有n個關鍵字具有相同的Hash函數值，則用線性探測法把這n個關鍵字映射到Hash表中需要做n*(n-1)/2次線性探測。如果使用二次探測再散列法将這n個關鍵字存入哈希表，至少要進行n*(n+1)/2次探測

Hash查找效率：裝填因子=表中記錄數/表容量

有B+Tree/Hash_Map/STL Map三種資料結構。對于記憶體中資料，查找性能較好的資料結構是Hash_Map，對于磁盤中資料，查找性能較好的資料結構是B+Tree。Hash操作能根據散列值直接定位資料的存儲位址，設計良好的hash表能在常數級時間下找到需要的資料，但是更适合于記憶體中的查找。B+樹是一種是一種樹狀的資料結構，适合做索引，對磁盤資料來說，索引查找是比較高效的。STL_Map的内部實作是一顆紅黑樹，但是隻是一顆在記憶體中建立二叉樹樹，不能用于磁盤操作，而其記憶體查找性能也比不上Hash查找。

内部排序

1. 内部排序：全部資料可同時放入記憶體進行的排序。
2. 外部排序：檔案中資料太多，無法全部調入記憶體進行的排序。

插入類：

1. 直接插入排序。最壞情況是資料遞減序，資料比較和移動量最大，達到O(n2)，最好是資料是遞增序，比較和移動最少為O(n)。趟數是固定的n-1，即使有序，也要依次從第二個元素開始。排序趟數不等于時間複雜度。

   

2. 折半插入排序 。由于插入第i個元素到r[1]到r[i-1]之間時，前i個資料是有序的，是以可以用折半查找确定插入位置，然後插入。
3. 希爾排序。縮小增量排序。5-3-1。在實際應用中，步長的選取可簡化為開始為表長n的一半（n/2），以後每次減半，最後為1。插入的改進，最後一趟已基本有序，比較次數和移動次數相比直接插入最後一趟更少

   

交換類：

1. 冒泡排序。O(n2)通常認為冒泡是比較差的，可以加些改進，比如在一趟中無資料的交換，則結束等措施。 
   1. 在資料已基本有序時，冒泡是一個較好的方法
   2. 在資料量較少時（15個左右）可以用冒泡

   3. 

2. 快速排序。 
   1. 時間複雜度。最好情況：每次支點總在中間，O(nlog2n)，平均O(nlog2n)。最壞，資料已是遞增或遞減，O(n2)。pivotkey的選擇越靠近中央，即左右兩個子序列長度越接近，排序速度越快。越無序越快。
   2. 空間複雜度。需棧空間以實作遞歸，最壞情況：S(n)=O(n)；一般情況：S(n)=O(log2n)
   3. 在序列已是有序的情況下，時間複雜度最高。原因：支點選擇不當。改進：随機選取支點或最左、最右、中間三個元素中的值處于中間的作為支點，通常可以避免最壞情況。是以，快速排序在表已基本有序的情況下不合适。
   4. 在序列長度已較短時，采用直接插入排序、起泡排序等排序方法。序列的個數通常取10左右。

   5. 

選擇類排序：

1. 簡單選擇排序。O(n2)。總比較次數n(n-1)/2。
2. 堆排序。建堆 O(n)，篩選排序O(nlogn)。找出若幹個數中最大/最小的前K個數，用堆排序是最好。小根堆中最大的數一定是放在葉子節點上，堆本身是個完全二叉樹，完全二叉樹的葉子節點的位置大于[n/2]。時間複雜度不會因為待排序序列的有序程度而改變，但是待排序序列的有序程度會影響比較次數。
3. 歸并排序。時間：與表長成正比，若一個表表長是m，另一個是n，則時間是O(m+n)。單獨一個數組歸并，時間：O(nlogn)，空間：O(n)，比較次數介于(nlogn)/2和(nlogn)-n+1，指派操作的次數是(2nlogn)。歸并排序算法比較占用記憶體，但卻是效率高且穩定的排序算法。在外排序中使用。歸并的趟數是logn。
4. 基數排序。在一般情況下，每個結點有 d 位關鍵字，必須執行 t = d次配置設定和收集操作。配置設定的代價：O(n)；收集的代價：O(rd) （rd是基數）；總的代價為：O( d ×(n + rd))。适用于以數字和字元串為關鍵字的情況。
5. 枚舉排序，通常也被叫做秩排序，比較計數排序。對每一個要排序的元素，統計小于它的所有元素的個數，進而得到該元素在整個序列中的位置，時間複雜度為O(n2)

比較法分類的下界：O(nlogn)

排序算法的一些特點：

1. 堆排序、冒泡排序、快速排序在每趟排序過程中,都會有一個元素被放置在其最終的位置上。
2. 有字元序列 ｛Q,H,C,Y,P,A,M,S,R,D,F,X｝ ,新序列{F,H,C,D,P,A,M,Q,R,S,Y,X}，是快速排序算法一趟掃描的結果。(拿Q作為分割點,快速排序一輪。二路歸并，第一趟排序，得到 n / 2 個長度為 2 的各自有序的子序列，第二趟排序，得到 n / 4 個長度為 4 的各自有序的子序列H Q C Y A P M S D R F X。如果是快速排序的話，第一個元素t将會被放到一個最準确的位置，t前的數均小于t，後面的數均大于t。希爾排序每個小分組内将會是有序的。堆排序，把它構成一顆二叉樹的時候，該堆要麼就是大根堆，要麼就是小根堆，第一趟Y排在最後；冒泡，那麼肯定會有資料下沉的動作，第一趟有A在第一位。)
3. 在檔案”局部有序”或檔案長度較小的情況下,最佳内部排序的方法是直接插入排序。（歸并排序要求待排序列已經部分有序，而部分有序的含義是待排序列由若幹有序的子序列組成，即每個子序列必須有序，并且其時間複雜度為O(nlog2n)；直接插入排序在待排序列基本有序時，每趟的比較次數大為降低，即n-1趟比較的時間複雜度由O(n^2)降至O(n)。在待排序的元素序列基本有序或者每個元素距其最終位置不遠也可用插入排序，效率最高的排序方法是插入排序）
4. 排序趟數與序列的原始狀态有關的排序方法是優化冒泡和快速排序法。(插入排序和選擇排序不管序列的原始狀态是什麼都要執行n-1趟，優化冒泡和快排不一定。仔細了解排序的次數和比較次數的差別)
5. 不穩定的排序方法：快排，堆排，希爾，選擇
6. 要與關鍵字的初始排列次序無關,那麼就是最好、最壞、一般的情況下排序時間複雜度不變, 總共有堆排序,歸并排序,選擇排序,基數排序
7. 快速排序、Shell 排序、歸并排序、直接插入排序的關鍵碼比較次數與記錄的初始排列有關。折半插入排序、選擇排序無關。(直接插入排序在完全有序的情況下每個元素隻需要與他左邊的元素比較一次就可以确定他最終的位置；折半插入排序，比較次數是固定的，與初始排序無關；快速排序，初始排序不影響每次劃分時的比較次數，都要比較n次，但是初始排序會影響劃分次數，是以會影響總的比較次數，但快排平均比較次數最小；歸并排序在歸并的時候，如果右路最小值比左路最大值還大，那麼隻需要比較n次，如果右路每個元素分别比左路對應位置的元素大，那麼需要比較2*n-1次，是以與初始排序有關)
8. 精儉排序，即一對數字不進行兩次和兩次以上的比較，插入和歸并是“精儉排序”。插入排序，前面是有序的，後面的每一個元素與前面有序的元素比較，比較過的就是有序的了，不會再比較一次。歸并每次合并後，内部都是有序的，内部的元素之間不用再比較。選擇排序，每次在後面的元素中找到最小的，找最小元素的過程是在沒有排好序的那部分進行，所有肯定會比較多次。堆排序也需比較多次。

外部排序

1. 生成合并段（run）：讀入檔案的部分記錄到記憶體－>在記憶體中進行内部排序－>将排好序的這些記錄寫入外存，形成合并段－>再讀入該檔案的下面的記錄，往複進行，直至檔案中的記錄全部形成合并段為止。
2. 外部合并：将上一階段生成的合并段調入記憶體，進行合并，直至最後形成一個有序的檔案。
3. 外部排序指的是大檔案的排序，即待排序的記錄存儲在外存儲器上，待排序的檔案無法一次裝入記憶體，需要在記憶體和外部存儲器之間進行多次資料交換，以達到排序整個檔案的目的。外部排序最常用的算法是多路歸并排序，即将原檔案分解成多個能夠一次性裝入記憶體的部分，分别把每一部分調入記憶體完成排序。然後，對已經排序的子檔案進行多路歸并排序
4. 不管初始序列是否有序, 冒泡、選擇排序時間複雜度是O(n^2),歸并、堆排序時間複雜度是O(nlogn）
5. 外部排序的總時間 = 内部排序（産出初始歸并段）所需時間 + 外存資訊讀取時間 + 内部歸并所需的時間
6. 外排中使用置換選擇排序的目的,是為了增加初始歸并段的長度。減少外存讀寫次數需要減小歸并趟數
7. 根據記憶體容量設若幹個輸入緩沖區和一個輸出緩沖區。若采用二路歸并，用兩個輸入緩沖。
8. 歸并的方法類似于歸并排序的歸并算法。增加的是對緩沖的監視，對于輸入，一旦緩沖空，要到相應檔案讀後續資料，對于輸出緩沖，一旦緩沖滿，要将緩沖内容寫到檔案中去。
9. 外排序和内排序不隻是考慮内外排序算法的性能，還要考慮IO資料交換效率的問題，記憶體存取速度遠遠高于外存。影響外排序的時間因素主要是記憶體與外設交換資訊的總次數

有效的算法設計

1. 貪心法。Dijkstra的最短路徑(時間複雜度O(n2))；Prim求最小生成樹鄰接表存儲時是O(n+e),圖O(n2)；關鍵路徑及關鍵活動的求法。
2. 回溯法
3. 分支限界法
4. 分治法。分割、求解、合并。二分查找、歸并排序、快速排序。
5. 動态規劃。Floyd-Warshall算法求解圖中所有點對之間最短路徑時間複雜度為O(n3)

動态規劃解題的方法是一種高效率的方法，其時間複雜度通常為O(n2)，O(n3)等，可以解決相當大的資訊量。（數塔在n<=100層時，可以在很短的時間内得到問題解）

• 适用的原則：原則為優化原則，即整體優化可以分解為若幹個局部優化。
• 動态規劃比窮舉法具有較少的計算次數
• 遞歸算法需要很大的棧空間，而動态規劃不需要棧空間

貪心和動态規劃的差别：

1. 所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動态規劃算法的主要差別。
2. 在動态規劃算法中，每步所作的選擇往往依賴于相關子問題的解。因而隻有在解出相關子問題後，才能作出選擇。而在貪心算法中，僅在目前狀态下作出最好選擇，即局部最優選擇。然後再去解作出這個選擇後産生的相應的子問題。
3. 貪心算法所作的貪心選擇可以依賴于以往所作過的選擇，但決不依賴于将來所作的選擇，也不依賴于子問題的解。正是由于這種差别，動态規劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行,以疊代的方式作出相繼的貪心選擇，每作一次貪心選擇就将所求問題簡化為一個規模更小的子問題。

P問題

1. P問題，如果它可以通過運作多項式次(即運作時間至多是輸入量大小的多項式函數的一種算法獲得解決），可以找到一個能在多項式的時間裡解決它的算法。—-确定性問題
2. NP問題，雖然可以用計算機求解，但是對于任意常數k，它們不能在O(nk)時間内得到解答，可以在多項式的時間裡驗證一個解的問題。所有的P類問題都是NP問題。
3. NP完全問題，知道有效的非确定性算法，但是不知道是否存在有效的确定性算法，同時，不能證明這些問題中的任何一個不存在有效的确定性算法。這類問題稱為NP完全問題。