數據結構的一些復習點

數據結構知識點總結


概論
1：數據的結構直接影響算法的選擇和效力。
2：數據->數據元素（元素，結點，記錄）數據的基本單位->數據項（字段，域）數據不可分割的最小單位
3：數據類型：原子數據類型：值不可分（整型，字符型，實型）和結構數據類型：值可分解（數組類型，結構類型）用戶自己定義的
4：數據結構：邏輯結構，物理結構：存儲結構（數據結構在計算機中的表示），運算特點。
邏輯結構：集合，線性結構（1對1），樹型結構（1對多），圖狀結構（多對多）
運算：插入，刪除，查找，排序。
數據結構定義：按某種邏輯關系組織起來的1批數據，利用計算機語言，按1定的存儲表示方法把它們存儲在
計算機的存儲器中，并在這些數據上定義了1個運算的集合。
數據的4種基本存儲方法：
順序存儲方法：邏輯上相鄰的節點存儲在物理位置相鄰的存儲單位中，結點之間的邏輯關系由存儲單元的鄰接關系來體現。
該方法主要利用于線性的數據結構。
鏈接存儲方法：不要求邏輯上相鄰的結點在物理位置上也相鄰，結點之間的邏輯關系是由附加的指針來表示的。
索引存儲方法：存儲結點信息的同時，建立附加的索引表。索引表中的每項稱為索引項。索引項的1般情勢：（關鍵字，地址）
散列存儲方法：根據結點的關鍵字直接計算出該結點的存儲地址。
例子：線性結構+順序存儲方法+棧=順序棧，線性結構+鏈接存儲方法+隊列=鏈隊列。
5：算法特性：有窮性，肯定性，可行性，輸入，輸出。
6：算法好壞的判斷根據：正確性，硬朗性，可讀性，履行耗費時間，履行耗費空間。
7：經常使用函數關系排序：c < log2n 8：算法是通過數據結構求解問題的步驟，程序是用數據類型描寫的算法。
9：數據結構：
基礎數據結構：
線性結構：線性表，棧，隊列，串
非線性結構：數組，廣義表，樹，2叉樹，圖
利用數據結構：查找，內部排序，外部排序，文件。


線性表
1：線性表特點：
有且只有1個“第1元素”
有且只有1個“最后元素”
除第1個元素以外，其他元素都有唯1的直接前趨
除最后元素以外，其他元素都有唯1的直接后繼
2：線性表的基本操作：初始化，清除，求表長，插入數據，刪除數據，
取得后繼結點，取得前趨結點，取得位置i的節點，定位（按值查找）
在插入數據，刪除數據，定位中平均移動比較次數是n/2，這3個操作的時間復雜度是O（n）。
3：線性表的存儲結構用數組來實現
4：順序表：順序存儲結構的線性表
特點：元素在計算機內部存儲的物理位置相鄰來表示線性表中數據元素之間的邏輯相鄰關系。
1段連續的內存空間來保存線性表結點的值。
5：在順序存儲中，能夠方便的查找指定位置的結點值，但是，插入和刪除結點比較麻煩。
5：鏈表：鏈式存儲結構的線性表
6：單鏈表：1個結點只包括1個指針域，1個結點結構=數據域+指針域。指針域保存地址信息。
用單鏈表來表示線性表時，結點之間的邏輯關系是由結點中的指針來唆使的。
7：為了方便判斷空表，插入和刪除結點，我們在單鏈表的第1個結點前面加上1個頭結點。
單鏈表的頭指針L指向頭結點，如果L->next=null,表示鏈表為空表。
8：單鏈表中，任何兩個結點的存儲位置之間沒有固定的聯系，要尋覓某1個結點，必須從頭指針動身，
   1個1個結點地向后尋覓。
9：線性表的鏈式存儲方式利用不連續的內存空間來保存結點的信息，因此，在結點中，不但需要保存結點
本身的數據值，還需要利用指針域保存指向直接后繼的指針。
10：單鏈表的操作：清除鏈表，求表長，定位查找，插入數據，刪除數據時間復雜度為O（n）
11：在鏈式存儲中，插入或刪除結點不需要大量的移動結點；但是在定位時，卻需要遍歷全部鏈表。
12：單循環鏈表：如果把單鏈表的最后1個節點的指針域指向第1個結點（頭結點）。則構成1個首尾相連的循環鏈表。
13：循環鏈表中判斷1個鏈表是不是為空，需要看頭結點的next域是不是等于本身。
14：循環鏈表建立和判斷的時間復雜度為O（1），插入和刪除的時間復雜度為O（n）
15：雙向鏈表：兩個指針域，1個指向直接前趨，1個指向直接后繼。
16：雙向鏈表中結點的特點，結點的next的prior是結點本身，結點的prior的next是結點本身。
17：判斷雙向鏈表為空表：看是不是兩個指針域都為NULL。
18：雙向鏈表的建立和判斷時間復雜度為O（1），插入和刪除的時間復雜度為O（n）
19：雙向循環鏈表：雙向鏈表中的頭結點和尾結點連接起來。
20：判斷雙向循環鏈表為空表：看是不是兩個指針域都指向本身。
21：線性表順序存儲與鏈式存儲的比較
時間角度：當線性表的操作操作主要是進行查找，而很少進行插入和刪除時，應當采取順序表進行存儲
當對頻繁的插入和刪除操作的線性表，則應當采取鏈表作為為存儲結構
空間角度：順序表的存儲空間是靜態分配的，在程序引入前必須規定其存儲閨蜜，如果估計過大，會造成空間的浪費。估計太小，會造成空間的溢出。
動態鏈表是動態分配的，只要內存空間有空閑，就不會產生溢出。
線性表的長度變化比較大時，應當采取動態鏈表為存儲結構。
22：順序表是采取數組實現的，鏈表是采取指針（動態鏈表）或游標（靜態鏈表）來實現的。


棧和隊列
1：棧和隊列：操作受限的線性表，稱為限定性的線性表結構。
2：棧：僅允許在1端進行插入和刪除運算線性表。落后先出（LIFO）線性表
棧頂：允許進行插入和刪除的那1端。
棧底：不可以進行插入和刪除的那1端（線性表的表頭）
進棧，入棧，壓棧：在1個棧中插入新元素，成為新的棧頂元素
出站，退棧：在1個棧中刪除1個元素，刪除棧頂元素，使下1個成為新的棧頂元素。
3：棧的基本操作：構造空棧，清除所有元素，判斷棧是不是為空，返回棧頂元素，入棧，出棧。
4：根據存儲結構：順序棧，鏈棧
順序棧：利用地址連續的存儲單元順次寄存從棧底到棧頂的數組元素，數組0位置的元素作為棧底元素
top=⑴，表示棧空；top=maxsize⑴，表示棧滿，就相當于1維數組
在做入棧操作前，首先要判定棧是不是滿（滿了叫上溢）；入棧指針top先加1，然后入棧。
在做出棧操作前，先要判定棧是不是為空（空的為下溢）；出棧指針top先減1，然后出棧（指針+1）。
鏈棧：相當于結點構成的單鏈表。
棧頂元素為單鏈表的第1個結點，由于棧頂元素操作頻繁，所以常常用沒有頭結點的單鏈表。
鏈棧是動態分配結點空間的，所以操作時無需斟酌上溢問題。
鏈棧的優點：可以使多個棧同享空間；在棧中元素變化的數量較大，且存在多個棧的情況下，鏈棧是棧的首選存儲方式。
5：棧的利用：數值進制轉換，括號匹配問題，子程序的調用，遞歸實現
6：隊列：限定在表的1段進行插入而在另外一端進行刪除的線性表。先進先出線性表（FIFO）
隊頭：允許刪除的1端
隊尾：允許插入的1端
入隊：向隊列中插入新元素，成為新的隊尾元素
出隊：從隊列中刪除元素，其后繼元素成為新的隊頭元素。
7：隊列的基本操作：構造空隊列，判斷隊列為空，求隊列長度，返回隊頭元素，插入隊尾元素，刪除隊頭元素，清除隊列元素。
8：根據存儲結構：鏈隊列，順序隊列
鏈隊列：限制僅在表頭進行刪除和在表尾進行插入的單鏈表。具有兩個指針（頭指針，尾指針）
頭指針指向頭結點，隊尾指針指向真實的隊尾元素結點。
判斷鏈隊列為空：頭指針和尾指針全部指向頭結點。
入隊：先將尾指針指向的元素的指針指向入隊元素，然后尾指針指向入隊元素。
出隊：修改頭指針中的指針，指向后繼結點，但是當刪除的元素是最后1個元素時，尾指針需要指向回頭結點。
順序隊列：用1組地址連續的存儲單元順次寄存從隊列頭到隊列尾的元素。
這里除定義1維數組還需要兩個指針指向隊頭和隊尾。
初始化空隊列：front=rear=0；
入隊：元素插入到rear所指向的空單元內，rear+1；
出隊：刪除數組頭結點，front+1
在非空隊列中，頭指針始終指向隊頭元素，而尾指針始終指向隊尾元素的下1個位置。
假溢出：當產生了若干次出隊入隊操作后，尾指針到了最后，沒法插入了，但是隊列元素<隊列的單元數。
避免假溢出現象：使用循環隊列。
循環隊列：數組大小maxsize，數組所表示的循環隊列最多允許有maxsize⑴個結點，rear所指的單元始終為空。
循環隊列隊滿條件：(rear+1)%maxsize==front
循環隊列隊空條件：rear==front
9：隊列的利用：打印楊輝3角，迷宮問題。
10：遞歸：如果1個函數直接調用自己或通過1系列調用間接地調用自己。
直接遞歸：在函數體內直接調用本身
間接調用：1個函數通過調用其他函數并由其他函數反過來又調用該函數
11:用到遞歸方法的情況：
第1種情況：定義是遞歸的。比如階乘，Fibonacci數列
第2種情況：數據結構時遞歸的。比如鏈表就是1種遞歸的數據結構
第3種情況：有些問題本身沒有明顯的遞歸結構，但用遞歸方法求解更簡單。
12：遞歸消除：由于遞歸程序運行時要花費較多的時間和空間，效力較低，有時需要消去1個程序中最常常履行部份的遞歸調用。
經常使用的是用迭代和棧進行遞歸消除。

串
1：串（字符串）：是1種特殊的線性表，它的每一個節點僅由1個字符組成。通經常使用雙引號把串中字符括起來。
2：空串：長度為0的串
3：空格串：串中都是空格字符，它有長度。
4：子串：串中任意個連續字符組成的子序列。
5：串：串變量（值可以改變），串常量（只能被援用不能改變其值）
6：順序串：串的順序存儲結構，用1組地址連續的存儲單元來順次寄存串中的字符序列。字符數組表示。
串結束標志：1般使用“\0”來肯定串是不是結束。也能夠把串長度放在ch[0]中。
基本操作：求串長，串復制，串聯接，求子串，串刪除。
缺點：事前定義了串長，這在程序運行前是很難估計的
定義了串的最大長度，串值空間被肯定，是靜態的，插入，連接操作被限制。
7：串的堆存儲結構：仍然是1組空間足夠大的，地址連續的存儲單元寄存串值字符序列，不同的是
存儲空間的大小不是預先定義的，而是在程序履行進程中動態分配的。
指向字符串存儲空間的是字符指針而非數組，若為空串，則指針為null。
8：鏈串：串的鏈式存儲結構：每一個結點僅存儲1個字符。便于插入和刪除。
9：塊鏈：由于鏈串每一個結點的指針域所占空間比字符域大，存儲空間利用率低，
所以在鏈串的每一個結點寄存多個字符，這樣的結點叫做塊。塊的大小就是結點所容納字符的個數。
當結點大小大于1時，串的長度不1定正好是結點大小的整數倍，因此用特殊字符“#”填充。
10：串的模式匹配：子串定位操作。
兩種方法：n是主串長度，m是模式串長度
第1種：時間復雜度O（mn）
KMP算法：時間復雜度O（m+n）

多維數組和廣義表
1：多維數組和廣義表：非線性結構。
邏輯結構：每一個數據元素可能有多個直接前趨和多個直接后繼。
2：數組只有兩種基本運算————讀和寫
讀：給定1組下標，讀出相應的元素
寫：給定1組下標，修改相應的元素
3：數組的存儲結構：1般取數組的開始地址作為基準，然后考察其他元素相對此基準的偏移量。因此基準加上該數組元素的偏移量就是該元素的絕對地址。
由于內存是1段連續的1維存儲空間，其實不是1個多維的存儲空間，因此多維數組中的數據要存儲在內存匯總，需要依照1定
的順序存儲在1維空間中。
4：矩陣的緊縮存儲：矩陣中有很多值相同的元素或零值元素，為了節省存儲空間，需要對他們進行緊縮存儲。
對稱矩陣，3角矩陣（上3角或下3角是常數），對角矩陣（除主對角線和主對角線相鄰兩側的若干條對角線的元素以外，其余元素皆為0）
5：稀疏矩陣：
3元組表：根據原矩陣上非零元素的行號，列號和值來作為3元組中的1個值。
6：廣義表：又稱為列表，它是線性表的推行。就是放寬了線性表元素是原子項這個限制。允許他們具有本身獨立的類型結構。
廣義表可以表示為：LS=(a1...ai...an)。LS是廣義表的名字，n是廣義表的長度，若ai本身就是廣義表，則稱為它是LS的子表。
空表：不包括任何元素的廣義表。
用大寫字母表示廣義表，小寫字母表示原子。
若廣義表非空，則a1稱為LS的表頭，其余元素組成的表(a2...ai...an)稱為LS的表尾。明顯，表尾1定是子表，表頭可以是原子也能夠是子表。
廣義表結構：廣義表是遞歸定義的。
不斟酌廣義表內部的結構，廣義表就是1個線性表，反之，線性表就是1個不含子表的廣義表。
廣義表的深度：該表展開后所含括號的層數。
7：特殊廣義表：
（）：長度為0的空表，對其不能求表頭和表尾的運算。
（（））：長度為1的非空表，對其進行分解，得到的表頭和表尾均是空表。
8：純表：廣義表可以與樹對應，沒有同享和遞歸的成份
9：再入表：廣義表中的元素存在同享。
10：遞歸表：廣義表中有自己。有遞歸。
11：廣義表獨有的運算：取表頭和表尾。
在廣義表中取某個元素，需要將該元素所在的子表逐漸分離出來，直到所求的元素成為某個子表的表頭，再用取表頭運算取出。
總的來講最后1步肯定是取表頭。

樹和2叉樹
1：樹是n個結點的有限集T，當n=0時，稱為空樹，當n>0時，滿足以下條件
有且只有1個稱為樹根的結點
當n>1時，除樹根結點之外的其余n⑴個結點可以劃分為m個互不相交的有限集，每個集合本身又是1個數。
2：樹的特點：
樹中有且只有1個結點為樹根的結點
樹中各子樹是互不相交的集合。
3：相干概念：結點的度（結點具有子樹的數目）
4：樹的基本操作：初始化，求樹根，創建1顆樹，求雙親結點，求孩子結點， 插入子樹，刪除子樹，樹的遍歷，清除樹，判斷樹空。
5：2叉樹：由n個結點的有限集構成，此集合可能為空集，也可能由1個根結點及兩顆互不相交的左，右子樹組成，并且左，右子樹都是2叉樹。
6：2叉樹的特點：
2叉樹有且唯一1個結點被稱為樹根的結點
當n>1時，每一個結點最多有兩顆子樹（即2叉樹不存在度大于2的結點）
2叉樹的子樹有左，右之分，且其次序不能任意顛倒，它是有序樹。
7：2叉樹的基本操作：基本和樹1樣，但是在求孩子結點的時候，有左孩子和右孩子之分。
8：滿2叉樹：1顆深度為k且有2^k⑴個結點的2叉樹。
9：完全2叉樹：深度為k，有n個結點的2叉樹當且僅當其每個結點都與深度為k的滿2叉樹逐一對應。
特點：
葉子結點只可能在層次最大的兩層上出現
對任1結點，若其右分支下子孫最大層次為p，則左分支下子孫的最大層次為p或p+1
10：滿2叉樹必為完全2叉樹，完全2叉樹不1定是滿2叉樹。
11：2叉樹的性質：
在2叉樹的第i層最多有2^(i⑴)個結點。
深度為k的2叉樹最多有2^k⑴個結點。
對任意1顆2叉樹BT，如果其葉子結點樹為n0，度為2的結點數為n2，則n0=n2+1
推倒進程：n=n0+n1+n2，n=1+n1+2n2
對n個結點的完全2叉樹的深度為logN+1，logN取下限，表示不大于logN的最大整數
對具有n個結點的完全2叉樹，如果對其結點按層次編號，則對任1結點i，有
如果i=1，則結點i是2叉樹的樹根，無雙親；如果i>1,則其雙親是i/2取下限
如果2i>n，則結點i無左孩子；如果2i<=n，則其左孩子是2i；
如果2i+1>n，則結點i無右孩子;如果2i+1<=n,則其右孩子是2i+1。
12：2叉樹的順序存儲：用1組連續的存儲單元來存儲2叉樹的數據元素。
在存儲的時候，對普通2叉樹必須修補成完全2叉樹進行存儲，這也造成了存儲空間的浪費。這是順序存儲的最大缺點。
13：2叉樹的鏈式存儲：2叉樹的結點應由1個數據元素和分別指向其左，右子樹的各個分支構成。
因此2叉樹的鏈表中的結點包括3個域：數據域和指向左，右子樹的指針域。稱為2叉鏈表。
14：使用鏈式存儲結構來存儲2叉樹比使用順序結構存儲2叉樹更加方便，也更容易反應結點之間的邏輯關系。
15：2叉樹的遍歷：
先根遍歷2叉樹：根節點-左子樹-右子樹
中根遍歷2叉樹：左子樹-根結點-右子樹
后根遍歷2叉樹：左子樹-右子樹-根結點
16：線索2叉樹：加上了指針“線索”的2叉鏈表組成的2叉樹:目的是為了加速遍歷進程和充分利用存儲空間
線索：在有n個結點的2叉鏈表中有2n個指針域，但只要n⑴個指針域用來寄存左右指針，其余n+1個指針域均為空。
因此用這n+1個空指針域來寄存遍歷進程中的前趨和后繼的指針。
規定：
若結點有左子樹，則lchild指向左孩子，否則ltag=1，lchild指向直接前趨結點。
若結點有右子樹，則rchild指向右孩子，否則rtag=1，rchild指向直接后繼結點。
17：線索化：實質是在2叉鏈表的空鏈域中填寫相應結點在1定遍歷次序下的前趨和后繼的地址。而這個地址只能在動態的遍歷進程中才能得到。
18：在中跟遍歷中：
在線索樹中查找前趨結點：當ltag=1，lchild就是其前趨結點；當ltag=0時，lchild就是其左子樹右鏈下最后1個結點。
在線索數中查找后繼結點：當rtag=1，rchild就是其后繼結點；當rtag=0時，rchild就是其右子樹左鏈下最后1個結點。
19：樹的存儲結構
雙親表示法：用1組連續的存儲空間（數組）來存儲樹中的結點，每一個數組元素不但包括結點本身的信息，
還保存雙親結點的下標號。
好處：查找某個結點的雙親容易
壞處：查找某個結點的孩子結點很困難。
孩子鏈表表示法：把每一個結點的孩子結點排列起來，構成1個單鏈表（孩子鏈表）。
然后將這樣的將n個這樣的數據元素放在1組連續的存儲空間中。
好處：容易求得1個結點的孩子結點。
壞處：求得1個結點的雙親結點就很困難。
孩子兄弟鏈表表示法：鏈表中的結點有兩個鏈域，分別指向第1個孩子結點和下1個（右）兄弟結點。
好處：容易實現數的任何操作，在結點上加上雙親域，可以方便雙親的查找。
20：樹，森林和2叉樹之間的轉換
由于樹的孩子兄弟鏈表示法和2叉樹的2叉鏈表表示法完全1樣，所以之間很容易實現相互轉換
樹轉換成2叉樹：
-加線：在樹中所有相鄰的兄弟之間加1條線。
-抹線：對樹中每一個結點，除其左孩子外抹去該結點與其余孩子之間的連線。
-整理：以樹的根結點為軸心，將整樹按順時針旋轉45度。
可以證明，樹轉換所構成的2叉樹是唯1的。
轉換成的2叉樹中，左分支上的各結點在原來的樹中是父子關系，右分枝上的各結點在原來的樹中是兄弟關系。
森林轉換成2叉樹：
-將森林中的每棵樹轉換成相應的2叉樹
-第1課樹不動，從第2課樹開始，順次把后1顆2叉樹的根結點作為前1顆2叉樹根的右子樹。
樹轉換成2叉樹根結點沒有右子樹，森林轉換成2叉樹，根結點有右子樹。
2叉樹轉換成樹：
-加線：若某結點是其雙親的左孩子，則把該結點右鏈上所有的結點都與該結點的雙親結點用線連接起來。
-抹線：抹掉原2叉樹中所以雙親結點與其左孩子右鏈上所有結點的連線。
-整理
能夠轉換成樹的2叉樹1定沒有右子樹
2叉樹轉換成森林：
-將2叉樹中根結點與其右孩子連接，及沿右分支搜索到的所以右孩子間連線全部抹掉，使之成為孤立的2叉樹。
-將孤立的2叉樹還原成樹。
21：樹的遍歷
先根遍歷：
訪問根結點
從左到右，順次先根遍歷根結點的每顆樹。
后根遍歷
從左到右，順次后根遍歷根結點的每顆樹
訪問根結點。
層次遍歷
若樹非空，則遍歷方法是先訪問第1層上的結點，然后順次遍歷第2層到第n層的結點。
22：森林的遍歷
先根遍歷：
訪問森林中第1顆樹的根結點
先根遍歷第1棵樹的根結點的子樹森林
先根遍歷除去第1顆樹以后剩余的樹構成的森林。
中根遍歷：
中根遍歷森林中第1顆樹的根結點的子樹森林
訪問第1顆樹的根結點
中根遍歷除去第1顆樹以后剩余的樹構成的森林
后根遍歷：
后根遍歷森林中第1顆樹的根結點的子樹森林
后根遍歷除去第1課樹以后剩余的樹構成的森林
訪問第1顆樹的根結點
23：森林的先根遍歷，中根遍歷和后根遍歷相對轉換成的2叉樹的先根遍歷，中根遍歷和后根遍歷相對應
24：樹的先根遍歷，后根遍歷分別于森林的先根遍歷和中根遍歷。
25：哈夫曼樹（最好判定樹）：由n個帶權葉子結點構成的所有2叉樹中帶權路徑長度WPL最小的2叉樹。
WPL：樹的帶權路徑長度：結點的權值*結點的路徑長度，然后所以結點的帶權路徑長度相加。
樹帶權路徑長度越小越好。
26：前綴編碼：任意1個編碼不能成為其他任意編碼的前綴。利用哈夫曼算法，可以設計出前綴編碼
好處：可以減少定長編碼的總位數。
27：哈夫曼樹中沒有長度為1的結點，1顆n個葉子結點的哈夫曼樹共有2n⑴個結點。
可以用1個1維數組來表示各個結點，數組中每一個元素包括4個數據項：結點的權值，結點的雙親下標和結點左右孩子。
28：2叉樹的1些結論
1顆2叉樹的前根序列和中根遍歷可肯定1顆2叉樹
1顆2叉樹的后根序列和中根遍歷可肯定1顆2叉樹
但是前和后不能肯定。
含有n個結點的2叉樹共有1/(n+1)*C(n|2n);和出棧次數1樣
任何1顆2叉樹的葉子結點在先根，中根和后根遍歷序列中的相對次序不產生改變。

圖
1：線性表：數據元素之間僅存在線性關系，每一個數據元素只有1個直接前趨和1個直接后繼；
樹：數據元素之間有著明顯的層次關系，且每層上的數據元素可能和下1層中多個元素（孩子）相干聯，但只能和上1層
中1個元素相干聯；
圖形結構：結點之間的關系可以是任意的，圖中任意兩個數據之間都可能相干，每一個結點都可以有多個直接前趨和多個直接后繼。
2：樹是圖的特殊情況。
3：有向邊，無向邊（v1,v2）
4：無向完全圖：n個頂點的無向圖，如果任意兩個頂點間都有1條直接邊相連。
有n(n⑴)/2條邊
5：有向完全圖：n個頂點的有向圖，如果任意兩個頂點間都有方向互為相反的兩條邊相連
有n(n⑴)條邊
6：路徑長度：這條路徑上邊的數目。
8：簡單路徑：除第1個頂點和最后1個頂點以外，其余頂點都不同的路徑
9：簡單回路：第1個頂點和最后1個頂點相同的簡單路徑。
10：相干概念：連通圖，連通份量（極大連通子圖），強連通圖，強連通份量，弱連通圖（有向圖中，最少有單向通路），弱連通份量。
11：度：頂點所具有的邊的數目
    出度：以某頂點為尾的邊的數目
    入度：以某頂點為終點的邊的數目
    1個頂點的度=出度+入度
12：生成樹：連通圖的G的1個子圖如果是1顆包括G的所以頂點的樹，
n個頂點的生成樹具有n⑴條邊。
13：圖的存儲結構：鄰接矩陣，鄰接表，鄰接多重表，10字鏈表
14：若圖為權圖：若不是E(G)中的邊，則這條邊的權值a12為0或無窮大。
若圖為非權圖：如果頂點v1，v2之間無邊，則a12=0；
如果頂點v1，v2之間有邊，則a12=1。
15：無向圖的鄰接矩陣是對稱的，而有向圖的鄰接矩陣不1定對稱。
 用鄰接矩陣表示具有n個頂點的有向圖時，要用n^2個單元存儲鄰接矩陣
 用鄰接矩陣表示具有n個頂點的無向圖時，只需要存入3角矩陣，只需n(n+1)/2個存儲單元。
16：鄰接矩陣來表示圖，易判定圖中任意兩個頂點之間是不是有邊相連，也易求得各個頂點的度數。
對無向圖，鄰接矩陣第i行元素之和就是圖中第i個頂點的度數。
對有向圖，第i行元素之和是頂點i的出度，第i列元素之和是頂點i的入度。
17：鄰接矩陣并不是圖的順序存儲結構，只是借助了數組這1數據類型來表示圖中元素間的相干關系。
18：鄰接矩陣的事件復雜度為O（n^2）。
19：鄰接表表示法：圖的鏈式存儲結構，包括兩部份：鏈表和向量
鄰接表：在鄰接鏈表中，對圖中每一個頂點vi都建立1個單鏈表，第i個單鏈表中的結點表示依附于頂點i的邊。
鄰接表中的每一個結點由兩個域組成：頂點域和鏈域。
表頭結點：數據域和鏈域。所有表頭結點寄存在1個頂點表中。
將無向圖的鄰接表稱為邊表，將有向圖的鄰接表稱為出邊表。
20：若無向圖中有n個頂點，e條邊，則鄰接鏈表需n個表頭結點和2e個表結點，每一個結點有兩個域
對邊很少的圖，用鄰接鏈表比用鄰接矩陣更節省存儲單元。
21：逆鄰接表：為了計算有向圖的入度；鄰接表可以計算有向圖的出度。
22：鄰接表的時間復雜度：O（n+e）
23：當邊數較少時，鄰接表比較好；當邊數較多時，鄰接矩陣比較好。
24：鄰接矩陣是唯1的，鄰接表不是唯1的。
25：圖的遍歷：深度優先搜索法和廣度優先搜索法。
26：深度優先搜索法：類似于樹的前序遍歷。當訪問了1個頂點以后，盡可能向縱深方向去訪問下1個未被訪問的頂點。
遍歷的時間復雜度取決于存儲結構
鄰接表：O（n+e）
鄰接矩陣：O（n^2）
27：廣度優先搜索遍歷：類似于樹的層次遍歷
遍歷的時間復雜度取決于存儲結構
鄰接表：O（n+e）
鄰接矩陣：O（n^2）
遍歷的空間復雜度為O（n），輔助空間是隊列和標志數組
28：非連通圖的遍歷：進行屢次DFS或BFS算法，從某個頂點動身進行遍歷，履行1次不能保證訪問到所以頂點
為此，需要再選擇未被訪問的頂點作為出發點，再次履行DFS或BFS。
29：生成樹是連通圖的極小連通子圖：由于n個頂點的連通圖最少有n⑴條邊，而所以包括n⑴條邊及n個頂點的連通圖都是無回路的樹。
30：生成樹：連通圖G的1個子圖如果是1顆包括G的所有頂點的樹。
31：構造最小生成樹：
盡量選擇權值小的邊，但不能構成回路
選取n⑴條恰當的邊以連接網的n個頂點
32：構造最小生成樹的普里姆（prim）算法，從頂點動身尋覓最短邊。
算法的時間復雜度為O（n^2）,比較合適構造稠密圖的最小生成樹，與邊數無關。
33：構造最小生成樹的克魯斯卡爾（kruskal）算法，選取n⑴條最小的邊
算法的時間復雜度為O（eloge），與網中數目e相干，合適稀疏圖的最小生成樹。
34：最短路徑：
迪杰斯特拉（dijkstra）：提出1個按路徑長度遞增的次數產生最短路徑的算法。
算法的時間復雜度O（n^2）
弗洛伊德（floyd）：求每對頂點之間你的最短路徑
算法的時間復雜度O（n^3），比較合適稠密圖，需要求A^n和path^n;
35：AOV網：以頂點表示活動，有向邊表示活動之間的前后關系的網
36：拓撲排序：構造AOV網的拓撲有序序列的操作。是定義在有向圖上的1種操作。AOV網不應當出現回路。
算法時間復雜度O（n+e）
37：對AOV網進行拓撲排序的步驟是：
在AOV當選取1個入度為0的頂點并輸出它
從網中刪去該頂點，并且刪去從該頂點發出的全部有向邊
重復上面兩個步驟，直到網中全部頂點均已輸出，或當前圖中不存在入度為0的頂點位置，后1種情況說明有向圖有回路。
38：AOV網的拓撲有序序列不唯1。
39：AOE網：頂點表示子工程（事件），邊表示活動，邊上的權表示活動所需的時間。
40：關鍵路徑：從開始頂點到結束頂點的最長路徑長度。1個AOE網可能有多條關鍵路徑，他們的長度是1樣的。
41：最早開始時間：1個時間vk能夠產生的最早時間取決于從始點v1到頂點vk的最長路徑長度。
42：最遲開始時間：1個時間vk允許的最遲產生時間，應當等于結束頂點事件vn的最早產生時間減去vk到vn的最長路徑長度。
43：最遲開始時間-最早開始時間
若為0，則活動為關鍵活動，否則為非關鍵活動。
44：關鍵路徑的辨認：為了使AOE網所代表的工程盡快完成，要先辨認關鍵路徑，只有縮短關鍵路徑上的關鍵活動所需時間才能縮短全部工期。
45：關鍵活動算法：
對AOE網進行拓撲排序，按拓撲排序的次序求出各頂點事件的最早產生時間ve，若有向圖中有回路，則算法結束，否則履行下1步
按拓撲序列的逆序求出各頂點事件的最遲產生時間vl
根據求得的各頂點的ve，vl，求出各活動ai的最早開始時間e(i)和最遲開始時間l(i)，若e(i)=l(i)，則ai為關鍵活動。
46：不論出度還是入度，頂點的度之和等于圖邊數的兩倍。
47：用鄰接表表示圖進行廣度優先遍歷，通常采取隊列來實現算法。
48：用鄰接表表示圖進行深度優先遍歷，通常采取棧來實現算法。


查找
1：查找表：同1類型的數據元素（或記錄，結點）構成的集合。
2：關鍵字：數據元素中某個數據項的值，用它可以標識或辨認1個數據元素。
3：查找：給定1個關鍵字K，在含有n個結點的查找表中找出關鍵字等于給定值K的結點。
若查找成功，返回結點的信息或該結點在表中的信息。
若查找失敗，返回相干的唆使信息。
4：動態查找表：若在查找的同時需要對表進行修改操作（如插入，刪除等）。
5：靜態查找表：若對表只進行查找操作（查詢，檢索等）。
6：內查找：如果查詢進程都在內存中進行。
7：外查找：如果查詢進程需要訪問外存。
8：平均查找長度（ASL）：查找進程中對關鍵字需要履行的平均比較次數。
衡量1個查找算法效力高低的標準。
9：線性表的查找
順序查找：從表的1端開始，順序掃描線性表，順次將掃描到的結點關鍵字和給定值K相比較。
R[0]作哨兵，從后往前判斷
順序查找的存儲結構：適用于線性表的順序存儲結構，也使用也鏈式存儲結構（使用單鏈表，掃描從表頭開始）
順序查找的平均查找長度：（n+1）/2
順序查找改進：每當查找成功時，就將找到的結點和后繼結點交換，減少查找幾率大的結點的比較次數。
順序查找的優點：算法簡單，對表結構無任何要求，不關注關鍵字是不是有序。
順序查找的缺點：查找效力低，當n特別大時，不宜用順序查找。
2分查找（折半查找）：效力較高的查找算法，要求線性表是有序表，并且要用向量作為表的存儲結構。
2分查找的基本思想：
首先肯定該區間內的中點位置
然后將待查的K值與中點位置進行比較：若相等，查找成功返回位置；否則肯定新的區間差找
如果中間位置大于k，則新的區間則是左子表
如果中間位置小與K，則新的區間則是右子表
重復上面這個進程，直至找到關鍵字為K的結點。
2分查找判定樹：把當前查找區間的中間位置上的結點作為根，左子表和右子表中的結點分別作為根的左子樹和右子樹。
2分查找成功時的平均查找長度：log（n+1）⑴
2分查找失敗時的平均查找長度：log（n+1）取上限
2分查找的平均查找長度：logn
2分查找的優點：查找效力高，但是要排序關鍵字，最高效的排序需要花費O（nlogn）
2分查找的缺點：只合適順序存儲結構，合適1經建立就很少改動而又常常需要查找的線性表。
分塊查找（索引查找）：性能介于順序查找和2分查找之間
分塊查找表的索引結構：
分塊有序的線性表：前1塊的最大關鍵字小于后1塊的最小關鍵字
索引表：抽取各塊中最大關鍵字及其起始位置構成1個索引表，索引表是遞增有序表。
分塊查找的基本思想:
首先查找索引表，可采取2分查找或順序查找看看結點在哪1塊。
然后在已確認的塊中進行順序查找。
分塊查找的平均查找長度
2分查找肯定塊：log(n/s+1)+s/2
順序查找肯定塊：(s^2+2s+n)/(2s)
s=n取根號
分塊查找的優點：在表中插入或刪除1個記錄時，只要找到該記錄所屬的塊，便可在該塊內進行插入和刪除運算。
由于塊中的記錄的寄存是任意的，所以插入或刪除的時候不需要移動大量的結點。
分塊查找的缺點：增加1個輔助數組的存儲空間和將初始表分塊排序的運算。
在這3種查找方式中，2分查找效力最高，但是只適用于靜態查找表。
10：樹表
2叉排序樹（2叉查找樹）：
若它的左子樹非空，則左子樹上所有的結點的值小于根結點的值
若它的右子樹非空，則右子樹上所有的結點的值大于根結點的值
左右子樹本身又個數1顆2叉排序樹
樹排序：2叉排序樹的中序遍歷是1個有序遍歷，平均履行時間O（nlogn）
對相同的實力，樹排序是堆排序的2⑶倍，因此在1般情況下構造2叉排序樹是為了查找，其實不是為了排序。
2叉排序樹的插入：
若2叉排序樹為空，則為待插入的關鍵字申請1個新結點，并令其為根；
若2叉樹不為空，則將key和根的關鍵字比較：
若2者相等，說明樹中已有此關鍵字，不必插入
若key小于根關鍵字，則插入左子樹
若key大于根關鍵字，則插入右子樹
2叉排序樹的刪除：
p為葉子結點，只需將p的雙親parent中指向p的指針域置為空；
p只有1個孩子，只需將child和p的雙親直接連接就能夠，然后刪除p；
p有兩個孩子，替換p為p右子樹下最左側的點，刪除該點。
2叉排序樹上的查找：2叉排序樹構建不唯1，2分查找樹是唯1的
2叉排序樹的查找的平均查找長度與2叉樹的形態有關
最壞情況查找長度：構成1顆單樹，（n+1）/2
最好情況查找長度，構成1顆形態與2分查找樹相似的排序樹，logn
插入，刪除和查找算法的時間復雜度均為O（logn）
2叉排序樹和2分查找的比較：
平均時間差不多，
如果有序表是靜態查找表，用2分查找
如果有序表是動態查找表，用2叉排序樹
平衡2叉樹：指樹中任1結點的左右子樹的高度大致相同，為了保證2叉排序樹的高度為logn
滿2叉樹是完全平衡的，只要2叉樹的高度O（logn），可以看成是平衡的。
AVL樹中任1結點的左右子樹的高度之差的絕對值不超過1
最壞情況下，n個結點的AVL樹高度為1.44logn
完全平衡的2叉樹高度為log2n，AVL樹是接近最優的。
B-樹：查詢的文件較大，且文件寄存在磁盤等直接存取裝備中，為了減少查詢進程中對磁盤的讀寫次數。
特性：
每一個結點最少包括以下數據域(n,p0,k1,p1,k2,...,ki,pi)k表示關鍵字（關鍵字序列遞增有序），p表示指針
所有葉子結點都在同1層，葉子的層數為樹的高度h
每一個非根結點中所含關鍵字個數j為(m/2⑴)<=j<=m⑴（m為樹的階樹）
由于內部結點的度數正好是關鍵字總數+1，所以每一個非根結點最少有m/2顆子樹，最多有m顆子樹
高度為n的3階B-樹的結點最少是2^n⑴
1顆高度為h的B-樹，任1葉子結點所處的層數為h，當向B-樹插入1個新關鍵字時，為檢索插入位置所需讀取h個結點。
11：散列表的查詢：不同于順序查找，2分查找，2叉排序樹，不以關鍵字的比較為基本操作，而是采取直接尋址技術。
12：散列的基本思想：以結點的關鍵字K為自變量，通過1個肯定的函數關系h，計算出對的函數值，然后把這個值解釋為結點
的存儲地址，將結點存入函數值所指的存儲位置上。在查找時，根據要查找的關鍵字用同1函數計算出地址
再到相應的單元里去取出要找的結點。
13：散列表沖突問題：兩個不同的關鍵字，由于散列函數值相同，因此被映照到同1表位置上。
沖突不可能完全避免。
避免沖突的辦法：
關鍵字的個數小于或等于散列表的長度
選擇適合的散列函數
14：裝填因子：a=填入的結點n/表長m。a越大，表越滿，沖突的機會也越大，通常去a<=1。
15：散列函數的選擇：
平方取中法：先通過求關鍵字的平方值擴大相近數之間的差別，然后根據表長度取中間的幾位數作為散列函數值。
除留余數法：最簡單經常使用的1種方法。就是用表長m去除關鍵字，取其余數作為散列地址。m最好取素數。
相乘取整法：
首先用關鍵字key乘上某個常數A（0 然后用m乘以該小數后取整。
隨機函數法：保證隨機函數值在0-（m⑴）之間。通常，當關鍵字長度不等時采取此方法來構造散列函數。
16：處理沖突的方法
開放地址法：沖突產生時，使用某種探查技術在散列表中構成1個探查序列，沿此序列逐一單元查找，直到找到給定的關鍵字
或碰到1個開放的地址為止。hi=（h（key）+ di）% m  0<=i<=m⑴
裝填因子：0.5-0.9
探測序列的方法：
線性探查法：探查序列：hi=（h（key）+ i）% m  0<=i<=m⑴ 即di=i
缺點：堆積現象嚴重。
2次探查法：跳躍式探查。hi=（h（key）+ i*i）% m  0<=i<=m⑴ 即di=i^2
缺點：可以減少堆積現象，但是不容易探查到全部散列空間。
兩重散列法：開放地址法中最好的方法之1。hi=（h（key）+ i * h1（key））% m  0<=i<=m⑴ 即di=i * h1（key）
用了兩個散列函數。h1（key）=key%(m⑴)+1
m為素數，則h1（key）取1-（m⑴）之間的任何數均與m互素。
m為2的方冪，則h1（key）取1-（m⑴）之間的任何奇數。
拉鏈法：將所有關鍵字為同義詞的結點鏈接到同1個單鏈表中。
拉鏈法的優點：
拉鏈法處理沖突簡單，沒有堆積現象
拉鏈法結點空間動態申請，合適造表前沒法確認表長的情況
拉鏈法可以a>=1
刪除結點比較容易，直接在鏈表上刪除；而對開放地址表來講，只能在被刪結點上做標記，不能真實的刪除結點
拉鏈法的缺點：
指針需要額外的空間，當結點范圍小，與拉鏈法相比，開放地址發更省空間。
17：性能分析
查找：散列表的平均查找長度比順序查找，2分查找等完全依賴與關鍵字比較的查找要小很多。
查找成功ASL：查找次數之和/關鍵字個數
查找失敗ASL：查找不成功時對關鍵字需要履行的平均比較次數。
直接找關鍵字到第1個地址上關鍵字為空的距離便可，初始位置只能是MODn的0-n⑴；
18：總結：
由同1個散列函數，不同的解決沖突方法構造的散列表，其平均查找長度是不同的
散列表的平均查找長度不是結點個數n的函數，而是裝填因子a的函數。
順序查找O（n），其他查找O（logn），散列法查找O（1）

排序：
1：排序方法的穩定性：在待排序的文件中，若存在多個關鍵字相同的記錄，經過排序后這些相同的關鍵字的記錄之間的相對次序
保持不變。反之，則是排序方法是不穩定的。
2：內部排序：排序進程中全部文件都在寄存在內存中進行處理的。
1般適用于記錄個數不多的小文件
插入排序，選擇排序，交換排序，歸并排序，基數排序
3：外部排序：排序進程中需要進行數據的內，外存之間的交換。
1般使用于記錄個數太多，不能1次性將全部記錄放入內存的大文件
4：排序算法的性能評價：
履行算法所需的時間
履行算法所需的輔助空間：O(1)是就地排序，非就地排序1般是O(n)
算法本身的復雜程度
5：不同存儲方式的排序進程：順序表，鏈表，索引表。
6：插入排序：每次將1個待排序的記錄，按其關鍵字大小插入已排序好的文件中的適當位置，直到全部記錄插入完位置
（就像打牌1樣，邊抓邊整理）。
直接插入排序：在排序中，引入哨兵這個概念，作用是：
在進入循環之前，保存了r[i]的副本，使得不致于由于記錄后移而丟失r[i]中內容
在while循環中監視下標j是不是越界，1旦越界，直接退出
引入哨兵后使得測試查找循環條件的時間大約減少了1半
算法分析：
時間復雜度：
關鍵詞遞增有序（正序）：O（n）
關鍵詞遞減有序（反序）：O（n^2）
關鍵詞無序（平均）：O（n^2）
空間復雜度：
輔助空間1個監視哨，O（1），就地排序
直接插入排序是1個穩定的排序
希爾排序：直接插入排序的改進，先取1個小與n的整數d作為第1個增量，把文件分成d組，然后排序，然后減少增量
的值進行排序，最后增量變成1進行排序。
算法分析:
希爾排序的履行時間依賴于增量序列：
最后1個增量必須是1
應當避免序列中的值為倍數
當n較大時，希爾排序比較和移動的次數約為n^1.3
希爾排序時間性能上明顯優于直接插入排序
希爾排序是不穩定的。
7：交換排序：兩兩比較待排序記錄的關鍵字，發現兩個記錄的次序相反時即進行交換，直到沒有反序的記錄出現
冒泡排序：從下往上掃描數組，1旦違背輕氣泡不能再重氣泡之下的原則，就讓其調換，直到最后任何兩個氣泡都是輕者在上，重者在下。
算法分析：
時間復雜度：
關鍵詞遞增有序（正序）：O（n）
關鍵詞遞減有序（反序）：O（n^2）
關鍵詞無序（平均）：O（n^2）
空間復雜度：
輔助空間1個監視哨，O（1），就地排序
冒泡排序是1個穩定的排序
快速排序(霍爾排序)：采取分治法的思想，將原問題分解成若干個范圍更小但結構與原問題相似的子問題，遞歸解決子問題
然后將這些子問題的解組合為原問題的解。
3個步驟：
分解：在數組中任選1個基準，順次劃分左右兩個較小的子區間，最后使得左區間的值<基準值<右區間值
求解；遞歸對左右區間進行快速排序
組合：求解后已有序了，排序好了，實際上是個空操作。
算法分析：
快速排序的時間主要耗費在劃分操作上，對長度為k的區間進行劃分，共需進行k⑴次關鍵字的比較。
在無序數組當選擇劃分的基準關鍵字是決定算法性能的關鍵。
時間復雜度：
最壞：劃分后基準是在最左側或最右側O（n^2）
最好：劃分基準是中值O（nlogn）
平均：O（nlogn）
空間復雜度：快速排序需要1個棧來實現
最好：O（logn）
最壞：O（n）
快速排序是非穩定的。
8：選擇排序：每趟從待排序的記錄當選出關鍵字最小的記錄，順序寄存在已排序好的子文件的后面，直到全部記錄排序終了。
直接選擇排序：n個記錄經過n⑴此直接選擇排序得到有序結果
第1趟，在無序區當選擇最小的值和第1個元素交換，
第2趟，在2-n當選擇最小的值和第2個元素交換。。。
算法分析：
時間復雜度：O（n^2）
空間復雜度：
輔助空間1個監視哨，O（1），就地排序
直接選擇排序是不穩定排序。
堆排序：是1樹型選擇排序，其特點是：在排序進程中，將序列看成是1顆完全2叉樹的順序存儲結構，利用完全2叉樹
中雙親結點和孩子結點之間的內在關系，在當前無序區當選擇關鍵字最大（或最小）的記錄。
堆的定義：n個關鍵字序列k1，k2，。。。kn稱為堆，當且僅當滿足以下關系ki<=k2i且ki<=k(2i+1)
或ki>=k2i且ki>=k(2i+1),存儲序列可以看作是1顆完全2叉樹的存儲結構
堆的實質：是滿足1下性質的完全2叉樹：樹中任1非葉結點的關鍵字均不大于（或不小于）其左右孩子結點的關鍵字。
大根堆：根結點的關鍵字是堆里所有結點關鍵字中最大者
小根堆：根結點的關鍵字是堆里所有結點關鍵字中最小者
注意：堆中任意子樹也是堆。
堆排序與直接選擇排序的區分：在直接選擇排序中，會出現重復的比較次數，由于堆排序可以通過樹型結構保存
部份比較結果，因此能夠減少比較次數。

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈