第一章 緒論

什么是數(shù)據(jù)結(jié)構(gòu)？

數(shù)據(jù)結(jié)構(gòu)的定義：數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

第二章 算法

算法的特性：有窮性、確定性、可行性、輸入、輸出。

什么是好的算法？ ----正確性、可讀性、健壯性、時(shí)間效率高、存儲(chǔ)量低

函數(shù)的漸近增長(zhǎng)：給定兩個(gè)函數(shù)f(n)和g(n)，如果存在一個(gè)整數(shù)N，使得對(duì)于所有的n>N，f(n)總是比g(n)大，那么，我們說(shuō)f(n)的增長(zhǎng)漸近快于g(n)。于是我們可以得出一個(gè)結(jié)論，判斷一個(gè)算法好不好，我們只通過(guò)少量的數(shù)據(jù)是不能做出準(zhǔn)確判斷的，如果我們可以對(duì)比算法的關(guān)鍵執(zhí)行次數(shù)函數(shù)的漸近增長(zhǎng)性，基本就可以分析出：某個(gè)算法，隨著n的變大，它會(huì)越來(lái)越優(yōu)于另一算法，或者越來(lái)越差于另一算法。

時(shí)間復(fù)雜度（大O階）的計(jì)算方法——如果級(jí)數(shù)展開學(xué)得好的話就很好理解

• 用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。
• 在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。
• 如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)。

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)< O(n!) < O(n^n)

第三章 線性表

線性表是零個(gè)或多個(gè)具有相同類型的數(shù)據(jù)元素的有限序列。

線性表的兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)包括四種：
單鏈表：指針的指向只是從表頭到表尾

靜態(tài)鏈表：數(shù)組的元素都是由兩個(gè)數(shù)據(jù)域組成，data和cur。也就是說(shuō)，數(shù)組的每個(gè)下標(biāo)都對(duì)應(yīng)一個(gè)data和一個(gè)cur。數(shù)據(jù)域data，用來(lái)存放數(shù)據(jù)元素，也就是通常我們要處理的數(shù)據(jù)；而cur相當(dāng)于單鏈表中的next指針，存放該元素的后繼在數(shù)組中的下標(biāo)，我們把cur叫做游標(biāo)。

循環(huán)鏈表：表尾的指針指向表頭

雙向鏈表：不僅有指向后面的指針，還有指向前面的指針

第四章 棧和隊(duì)列

棧stack是限定在表尾進(jìn)行插入和刪除操作的線性表

隊(duì)列queue是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。

棧和隊(duì)列用線性表的順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)：浪費(fèi)空間 操作復(fù)雜

解決方法：對(duì)于棧來(lái)說(shuō)，如果是兩個(gè)相同數(shù)據(jù)類型的棧，則可以用數(shù)組的兩端作棧底的方法來(lái)讓兩個(gè)棧共享數(shù)據(jù)，這就可以最大化地利用數(shù)組的空間；對(duì)于隊(duì)列來(lái)說(shuō)，為了避免數(shù)組插入和刪除時(shí)需要移動(dòng)數(shù)據(jù)，于是就引入了循環(huán)隊(duì)列，使得隊(duì)頭和隊(duì)尾可以在數(shù)組中循環(huán)變化。解決了移動(dòng)數(shù)據(jù)的時(shí)間損耗，使得本來(lái)插入和刪除是O(n)的時(shí)間復(fù)雜度變成了O(1)。

逆波蘭表達(dá)式是什么？——又叫做后綴表達(dá)式，處理四則運(yùn)算，計(jì)算方法采用棧的先進(jìn)后出的方式。

第五章 字符串

KMP算法是什么？
介紹next[j]值的計(jì)算方法？

第六章 樹

樹（Tree）是n（n≥0）個(gè)結(jié)點(diǎn)的有限集。

線性結(jié)構(gòu)和樹結(jié)構(gòu)的比較：

樹的度是什么？各個(gè)結(jié)點(diǎn)度的最大值

樹的存儲(chǔ)結(jié)構(gòu)？雙親表示法、孩子表示法、孩子兄弟表示法（其實(shí)所有的表示法都是在指針域上做手腳）

二叉樹的分類？——斜樹、滿二叉樹、完全二叉樹（若按層序編號(hào)后其編號(hào)與同樣深度的滿二叉樹中編號(hào)結(jié)點(diǎn)在二叉樹中位置完全相同，那它就是完全二叉樹。）

二叉樹的性質(zhì)？——
性質(zhì)1：在二叉樹的第i層至多有2^(i-1)個(gè)結(jié)點(diǎn)（i>=1）
性質(zhì)2 ：深度為k的二叉樹至多有2^k-1個(gè)結(jié)點(diǎn)（k>=1）
性質(zhì)3：對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。
性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為|log2(n)+1|（|x|表示不大于x的最大整數(shù)）。
性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹（其深度為k）的結(jié)點(diǎn)按層序編號(hào)（從第1層到第層，每層從左到右），對(duì)任一結(jié)點(diǎn)i（1≤i≤n）有： 1．如果i=1，則結(jié)點(diǎn)i是二叉樹的根，無(wú)雙親；如果i>1，則其雙親是結(jié)點(diǎn)。 2．如果2i>n，則結(jié)點(diǎn)i無(wú)左孩子（結(jié)點(diǎn)i為葉子結(jié)點(diǎn)）；否則其左孩子是結(jié)點(diǎn)2i。 3．如果2i+1>n，則結(jié)點(diǎn)i無(wú)右孩子；否則其右孩子是結(jié)點(diǎn)2i+1。

二叉樹的順序存儲(chǔ)結(jié)構(gòu)？完全二叉樹使用順序存儲(chǔ)是最好的，不會(huì)浪費(fèi)存儲(chǔ)空間；
對(duì)于一般的二叉樹用二叉鏈表，結(jié)點(diǎn)的結(jié)構(gòu)是 lchild data rchild（中間是數(shù)據(jù)域，兩邊是指針域）

二叉樹遍歷原理（限制從左到右）：

1.前序遍歷：若二叉樹為空，則空操作返回，否則先訪問(wèn)根結(jié)點(diǎn)，然后前序遍歷左子樹，再前序遍歷右子樹。

2.中序遍歷：若樹為空，則空操作返回，否則從最左下結(jié)點(diǎn)開始（注意并不是先訪問(wèn)根結(jié)點(diǎn)），中序遍歷根結(jié)點(diǎn)的左子樹，然后是訪問(wèn)根結(jié)點(diǎn)，最后中序遍歷右子樹。

3.后序遍歷：若樹為空，則空操作返回，否則從左到右先葉子后結(jié)點(diǎn)的方式遍歷訪問(wèn)左右子樹，最后是訪問(wèn)根結(jié)點(diǎn)。

4.層序遍歷：若樹為空，則空操作返回，否則從樹的第一層，也就是根結(jié)點(diǎn)開始訪問(wèn)，從上而下逐層遍歷，在同一層中，按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問(wèn)。

二叉樹遍歷的性質(zhì)：
? 已知前序遍歷序列和中序遍歷序列，可以唯一確定一棵二叉樹。
? 已知后序遍歷序列和中序遍歷序列，可以唯一確定一棵二叉樹。
? 注意，已知前序和后序遍歷，是不能確定一棵二叉樹的。

什么是線索二叉樹？——指向前驅(qū)和后繼的指針?lè)Q為線索，加上線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹就稱為線索二叉樹。其實(shí)線索二叉樹，等于是把一棵二叉樹轉(zhuǎn)變成了一個(gè)雙向鏈表，這樣對(duì)我們的插入刪除結(jié)點(diǎn)、查找某個(gè)結(jié)點(diǎn)都帶來(lái)了方便。所以我們對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過(guò)程稱做是線索化。

將樹轉(zhuǎn)換為二叉樹的步驟如下 1.加線。在所有兄弟結(jié)點(diǎn)之間加一條連線。 2.去線。對(duì)樹中每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)的連線，刪除它與其他孩子結(jié)點(diǎn)之間的連線。 3.層次調(diào)整。以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。注意第一個(gè)孩子是二叉樹結(jié)點(diǎn)的左孩子，兄弟轉(zhuǎn)換過(guò)來(lái)的孩子是結(jié)點(diǎn)的右孩子。（兄弟變兒子哈哈?。?/p>

森林轉(zhuǎn)化為二叉樹：
森林是由若干棵樹組成的，所以完全可以理解為，森林中的每一棵樹都是兄弟，可以按照兄弟的處理辦法來(lái)操作。步驟如下： 1.把每個(gè)樹轉(zhuǎn)換為二叉樹。 2.第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹的根結(jié)點(diǎn)的右孩子，用線連接起來(lái)。當(dāng)所有的二叉樹連接起來(lái)后就得到了由森林轉(zhuǎn)換來(lái)的二叉樹。

二叉樹轉(zhuǎn)換為樹
二叉樹轉(zhuǎn)換為樹是樹轉(zhuǎn)換為二叉樹的逆過(guò)程。步驟如下： 1.加線。若某結(jié)點(diǎn)的左孩子結(jié)點(diǎn)存在，則將這個(gè)左孩子的右孩子結(jié)點(diǎn)、右孩子的右孩子結(jié)點(diǎn)、右孩子的右孩子的右孩子結(jié)點(diǎn)……哈，反正就是左孩子的n個(gè)右孩子結(jié)點(diǎn)都作為此結(jié)點(diǎn)的孩子。將該結(jié)點(diǎn)與這些右孩子結(jié)點(diǎn)用線連接起來(lái)。 2.去線。刪除原二叉樹中所有結(jié)點(diǎn)與其右孩子結(jié)點(diǎn)的連線。 3.層次調(diào)整。使之結(jié)構(gòu)層次分明。

判斷一棵二叉樹能夠轉(zhuǎn)換成一棵樹還是森林，標(biāo)準(zhǔn)很簡(jiǎn)單，那就是只要看這棵二叉樹的根結(jié)點(diǎn)有沒(méi)有右孩子，有就是森林，沒(méi)有就是一棵樹。

二叉樹轉(zhuǎn)換成森林，步驟如下： 1.從根結(jié)點(diǎn)開始，若右孩子存在，則把與右孩子結(jié)點(diǎn)的連線刪除，再查看分離后的二叉樹，若右孩子存在，則連線刪除……，直到所有右孩子連線都刪除為止，得到分離的二叉樹。 2.再將每棵分離后的二叉樹轉(zhuǎn)換為樹即可。

樹的遍歷分為兩種方式。 1.一種是先根遍歷樹，即先訪問(wèn)樹的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹。 2.另一種是后根遍歷，即先依次后根遍歷每棵子樹，然后再訪問(wèn)根結(jié)點(diǎn)。

森林的遍歷也分為兩種方式： 1.前序遍歷：先訪問(wèn)森林中第一棵樹的根結(jié)點(diǎn)，然后再依次先根遍歷根的每棵子樹，再依次用同樣方式遍歷除去第一棵樹的剩余樹構(gòu)成的森林。2.后序遍歷：是先訪問(wèn)森林中第一棵樹，后根遍歷的方式遍歷每棵子樹，然后再訪問(wèn)根結(jié)點(diǎn)，再依次同樣方式遍歷除去第一棵樹的剩余樹構(gòu)成的森林。

當(dāng)以二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu)時(shí)，樹的先根遍歷和后根遍歷完全可以借用二叉樹的前序遍歷和中序遍歷的算法來(lái)實(shí)現(xiàn)。

Huffman樹
樹的路徑長(zhǎng)度就是從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。

如果考慮到帶權(quán)的結(jié)點(diǎn)，結(jié)點(diǎn)的帶權(quán)的路徑長(zhǎng)度為從該結(jié)點(diǎn)到樹根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積。樹的帶權(quán)路徑長(zhǎng)度為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。

假設(shè)有n個(gè)權(quán)值{w1,w2,...,wn}，構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子結(jié)點(diǎn)帶權(quán)wk，每個(gè)葉子的路徑長(zhǎng)度為lk，我們通常記作，則其中帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹稱做赫夫曼樹。

構(gòu)造赫夫曼樹的赫夫曼算法描述：
1.根據(jù)給定的n個(gè)權(quán)值{w1,w2,...,wn}構(gòu)成n棵二叉樹的集合F={T1,T2,...,Tn}，其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為wi根結(jié)點(diǎn)，其左右子樹均為空。
2.在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹上根結(jié)點(diǎn)的權(quán)值之和。
3.在F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入F中。
4.重復(fù)2和3步驟，直到F只含一棵樹為止。這棵樹便是赫夫曼樹。

赫夫曼編碼是什么？——設(shè)需要編碼的字符集為{d1,d2,...,dn}，各個(gè)字符在電文中出現(xiàn)的次數(shù)或頻率集合為{w1,w2,...,wn}，以d1,d2,...,dn作為葉子結(jié)點(diǎn)，以w1,w2,...,wn作為相應(yīng)葉子結(jié)點(diǎn)的權(quán)值來(lái)構(gòu)造一棵赫夫曼樹。規(guī)定赫夫曼樹的左分支代表0，右分支代表1，則從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)所經(jīng)過(guò)的路徑分支組成的0和1的序列便為該結(jié)點(diǎn)對(duì)應(yīng)字符的編碼，這就是赫夫曼編碼。

第七章 圖

圖（Graph）是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為：G(V,E)，其中，G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，E是圖G中邊的集合。

無(wú)向邊：若頂點(diǎn)vi到vj之間的邊沒(méi)有方向，則稱這條邊為無(wú)向邊（Edge），用無(wú)序偶對(duì)(vi,vj)來(lái)表示。如果圖中任意兩個(gè)頂點(diǎn)之間的邊都是無(wú)向邊，則稱該圖為無(wú)向圖（Undirected graphs）。

有向邊：若從頂點(diǎn)vi到vj的邊有方向，則稱這條邊為有向邊，也稱為?。ˋrc）。用有序偶<vi,vj>來(lái)表示，vi稱為弧尾（Tail），vj稱為弧頭（Head）。如果圖中任意兩個(gè)頂點(diǎn)之間的邊都是有向邊，則稱該圖為有向圖（Directed graphs）。

簡(jiǎn)單圖——在圖中，若不存在頂點(diǎn)到其自身的邊，且同一條邊不重復(fù)出現(xiàn)，則稱這樣的圖為簡(jiǎn)單圖。

在無(wú)向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在邊，則稱該圖為無(wú)向完全圖。含有n個(gè)頂點(diǎn)的無(wú)向完全圖有n(n-1)/2條邊。

在有向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在方向互為相反的兩條弧，則稱該圖為有向完全圖。含有n個(gè)頂點(diǎn)的有向完全圖有n×(n-1)條邊。

對(duì)于具有n個(gè)頂點(diǎn)和e條邊數(shù)的圖，無(wú)向圖0≤e≤n(n-1)/2，有向圖0≤e≤n(n-1)。

有很少條邊或弧的圖稱為稀疏圖，反之稱為稠密圖。

有些圖的邊或弧具有與它相關(guān)的數(shù)字，這種與圖的邊或弧相關(guān)的數(shù)叫做權(quán)（Weight）。這些權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)。這種帶權(quán)的圖通常稱為網(wǎng)（Network）。

假設(shè)有兩個(gè)圖G=(V,{E})和G'=(V',{E'})，如果V' ?V且E' ?E，則稱G'為G的子圖（Sub-graph）。

對(duì)于無(wú)向圖G=(V,{E})，如果邊(v,v')∈E，則稱頂點(diǎn)v和v'互為鄰接點(diǎn)（Adjacent），即v和v'相鄰接。邊(v,v')依附（incident）于頂點(diǎn)v和v'，或者說(shuō)(v,v')與頂點(diǎn)v和v'相關(guān)聯(lián)。頂點(diǎn)v的度（Degree）是和v相關(guān)聯(lián)的邊的數(shù)目，記為TD(v)。

對(duì)于有向圖G=(V,{E})，如果弧<v,v'>∈E，則稱頂點(diǎn)v鄰接到頂點(diǎn)v'，頂點(diǎn)v'鄰接自頂點(diǎn)v?；?lt;v,v'>和頂點(diǎn)v，v'相關(guān)聯(lián)。以頂點(diǎn)v為頭的弧的數(shù)目稱為v的入度（InDegree），記為ID(v)；以v為尾的弧的數(shù)目稱為v的出度（OutDegree），記為OD(v)；頂點(diǎn)v的度為D(v)=ID(v)+OD(v)。

路徑的長(zhǎng)度是路徑上的邊或弧的數(shù)目。

第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路或環(huán)（Cycle）。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡(jiǎn)單路徑。除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路，稱為簡(jiǎn)單回路或簡(jiǎn)單環(huán)。

在無(wú)向圖G中，如果從頂點(diǎn)v到頂點(diǎn)v'有路徑，則稱v和v'是連通的。如果對(duì)于圖中任意兩個(gè)頂點(diǎn)vi、vj∈V，vi和vj都是連通的，則稱G是連通圖（Connected Graph）。

無(wú)向圖中的極大連通子圖稱為連通分量。注意連通分量的概念，它強(qiáng)調(diào)： 要是子圖； 子圖要是連通的； 連通子圖含有極大頂點(diǎn)數(shù)； 具有極大頂點(diǎn)數(shù)的連通子圖包含依附于這些頂點(diǎn)的所有邊。

在有向圖G中，如果對(duì)于每一對(duì)vi、vj∈V、vi≠vj，從vi到vj和從vj到vi都存在路徑，則稱G是強(qiáng)連通圖。有向圖中的極大強(qiáng)連通子圖稱做有向圖的強(qiáng)連通分量。

所謂的一個(gè)連通圖的生成樹是一個(gè)極小的連通子圖，它含有圖中全部的n個(gè)頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊。如果一個(gè)圖有n個(gè)頂點(diǎn)和小于n-1條邊，則是非連通圖，如果它多于n-1邊條，必定構(gòu)成一個(gè)環(huán)，因?yàn)檫@條邊使得它依附的那兩個(gè)頂點(diǎn)之間有了第二條路徑。

如果一個(gè)有向圖恰有一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度均為1，則是一個(gè)有向樹。一個(gè)有向圖的生成森林由若干棵有向樹組成，含有圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹的弧。

（概念太多總結(jié)一下：圖按照有無(wú)方向分為無(wú)向圖和有向圖。無(wú)向圖由頂點(diǎn)和邊構(gòu)成，有向圖由頂點(diǎn)和弧構(gòu)成?；∮谢∥埠突☆^之分。
圖按照邊或弧的多少分稀疏圖和稠密圖。如果任意兩個(gè)頂點(diǎn)之間都存在邊叫完全圖，有向的叫有向完全圖。若無(wú)重復(fù)的邊或頂點(diǎn)到自身的邊則叫簡(jiǎn)單圖。
圖中頂點(diǎn)之間有鄰接點(diǎn)、依附的概念。無(wú)向圖頂點(diǎn)的邊數(shù)叫做度，有向圖頂點(diǎn)分為入度和出度。
圖上的邊或弧上帶權(quán)則稱為網(wǎng)。
圖中頂點(diǎn)間存在路徑，兩頂點(diǎn)存在路徑則說(shuō)明是連通的，如果路徑最終回到起始點(diǎn)則稱為環(huán)，當(dāng)中不重復(fù)叫簡(jiǎn)單路徑。若任意兩頂點(diǎn)都是連通的，則圖就是連通圖，有向則稱強(qiáng)連通圖。圖中有子圖，若子圖極大連通則就是連通分量，有向的則稱強(qiáng)連通分量。
無(wú)向圖中連通且n個(gè)頂點(diǎn)n-1條邊叫生成樹。有向圖中一頂點(diǎn)入度為0其余頂點(diǎn)入度為1的叫有向樹。一個(gè)有向圖由若干棵有向樹構(gòu)成生成森林。）

5種圖的多重鏈表存儲(chǔ)：
一、鄰接矩陣：圖的鄰接矩陣（Adjacency Matrix）存儲(chǔ)方式是用兩個(gè)數(shù)組來(lái)表示圖。一個(gè)一維數(shù)組vertex[m]存儲(chǔ)圖中頂點(diǎn)信息，一個(gè)二維數(shù)組arc[i][j]（稱為鄰接矩陣）存儲(chǔ)圖中的邊或弧的信息。
設(shè)圖G有n個(gè)頂點(diǎn)，則鄰接矩陣是一個(gè)n×n的方陣，定義為：

這是一個(gè)對(duì)稱矩陣，有了這個(gè)矩陣，我們就可以很容易地知道圖中的信息。
1.我們要判定任意兩頂點(diǎn)是否有邊無(wú)邊就非常容易了。
2.我們要知道某個(gè)頂點(diǎn)的度，其實(shí)就是這個(gè)頂點(diǎn)vi在鄰接矩陣中第i行（或第i列）的元素之和。
3.求頂點(diǎn)vi的所有鄰接點(diǎn)就是將矩陣中第i行元素掃描一遍，arc[i][j]為1就是鄰接點(diǎn)。
二、鄰接表
鄰接矩陣在處理稀疏圖時(shí)會(huì)浪費(fèi)存儲(chǔ)空間，鄰接表是其改進(jìn)。
鄰接表的處理辦法：
1.圖中頂點(diǎn)用一個(gè)一維數(shù)組存儲(chǔ)，當(dāng)然，頂點(diǎn)也可以用單鏈表來(lái)存儲(chǔ)，不過(guò)數(shù)組可以較容易地讀取頂點(diǎn)信息，更加方便。另外，對(duì)于頂點(diǎn)數(shù)組中，每個(gè)數(shù)據(jù)元素還需要存儲(chǔ)指向第一個(gè)鄰接點(diǎn)的指針，以便于查找該頂點(diǎn)的邊信息。
2.圖中每個(gè)頂點(diǎn)vi的所有鄰接點(diǎn)構(gòu)成一個(gè)線性表，由于鄰接點(diǎn)的個(gè)數(shù)不定，所以用單鏈表存儲(chǔ)，無(wú)向圖稱為頂點(diǎn)vi的邊表，有向圖則稱為頂點(diǎn)vi作為弧尾的出邊表。
三、十字鏈表
對(duì)于有向圖，鄰接表是有缺陷的。關(guān)心了出度問(wèn)題，想了解入度就必須要遍歷整個(gè)圖才能知道，反之，逆鄰接表解決了入度卻不了解出度的情況?？梢园燕徑颖砗湍驵徑颖碜鲈谝黄?，成為十字鏈表。
重新定義頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)為data firstin firstout
重新定義的邊表結(jié)點(diǎn)結(jié)構(gòu)為 tailvex headvex headlink taillink
其中tailvex是指弧起點(diǎn)在頂點(diǎn)表的下標(biāo)，headvex是指弧終點(diǎn)在頂點(diǎn)表中的下標(biāo)，headlink是指入邊表指針域，指向終點(diǎn)相同的下一條邊，taillink是指邊表指針域，指向起點(diǎn)相同的下一條邊。如果是網(wǎng)，還可以再增加一個(gè)weight域來(lái)存儲(chǔ)權(quán)值。
四、鄰接多重表
重新定義邊表結(jié)點(diǎn)結(jié)構(gòu)為：ivex ilink jvex jlink
其中ivex和jvex是與某條邊依附的兩個(gè)頂點(diǎn)在頂點(diǎn)表中的下標(biāo)。ilink指向依附頂點(diǎn)ivex的下一條邊，jlink指向依附頂點(diǎn)jvex的下一條邊。這就是鄰接多重表結(jié)構(gòu)。
鄰接多重表與鄰接表的差別，僅僅是在于同一條邊在鄰接表中用兩個(gè)結(jié)點(diǎn)表示，而在鄰接多重表中只有一個(gè)結(jié)點(diǎn)。
五、邊集數(shù)組
邊集數(shù)組是由兩個(gè)一維數(shù)組構(gòu)成。一個(gè)是存儲(chǔ)頂點(diǎn)的信息；另一個(gè)是存儲(chǔ)邊的信息，這個(gè)邊數(shù)組每個(gè)數(shù)據(jù)元素由一條邊的起點(diǎn)下標(biāo)（begin）、終點(diǎn)下標(biāo)（end）和權(quán)（weight）組成。
邊集數(shù)組關(guān)注的是邊的集合，在邊集數(shù)組中要查找一個(gè)頂點(diǎn)的度需要掃描整個(gè)邊數(shù)組，效率并不高。因此它更適合對(duì)邊依次進(jìn)行處理的操作，而不適合對(duì)頂點(diǎn)相關(guān)的操作。
圖的遍歷：
深度優(yōu)先遍歷 廣度優(yōu)先遍歷
深度優(yōu)先遍歷類似樹的前序遍歷，圖的廣度優(yōu)先遍歷就類似于樹的層序遍歷。

找連通網(wǎng)的最小生成樹，經(jīng)典的有兩種算法，普里姆算法和克魯斯卡爾算法。
普里姆Prim算法：
假設(shè)N=(V,{E})是連通網(wǎng)，TE是N上最小生成樹中邊的集合。算法從U={u0}(u0∈V)，TE={}開始。重復(fù)執(zhí)行下述操作：在所有u∈U,v∈V-U的邊(u,v)∈E中找一條代價(jià)最小的邊(u0,v0)并入集合TE，同時(shí)v0并入U(xiǎn)，直至U=V為止。此時(shí)TE中必有n-1條邊，則T=(V,{TE})為N的最小生成樹。
此算法的時(shí)間復(fù)雜度為O(n2)。
（說(shuō)白了，普里姆算法是以某頂點(diǎn)為起點(diǎn)，逐步找各頂點(diǎn)上最小權(quán)值的邊來(lái)構(gòu)建最小生成樹的。）
克魯斯卡爾（Kruskal）算法：
假設(shè)N=(V,{E})是連通網(wǎng)，則令最小生成樹的初始狀態(tài)為只有n個(gè)頂點(diǎn)而無(wú)邊的非連通圖T={V,{}}，圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。在E中選擇代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價(jià)最小的邊。依次類推，直至T中所有頂點(diǎn)都在同一連通分量上為止。
此算法的Find函數(shù)由邊數(shù)e決定，時(shí)間復(fù)雜度為O(loge)，而外面有一個(gè)for循環(huán)e次。所以克魯斯卡爾算法的時(shí)間復(fù)雜度為O(eloge)。
（說(shuō)白了，把邊的權(quán)值小的先占下來(lái)當(dāng)做連通分量，再試圖把他們連起來(lái)。）
對(duì)比兩個(gè)算法，克魯斯卡爾算法主要是針對(duì)邊來(lái)展開，邊數(shù)少時(shí)效率會(huì)非常高，所以對(duì)于稀疏圖有很大的優(yōu)勢(shì)；而普里姆算法對(duì)于稠密圖，即邊數(shù)非常多的情況會(huì)更好一些。

計(jì)算最短路徑：
迪杰斯特拉（Dijkstra）算法——并不是一下子就求出了源點(diǎn)到終點(diǎn)的最短路徑，而是一步步求出它們之間頂點(diǎn)的最短路徑，過(guò)程中都是基于已經(jīng)求出的最短路徑的基礎(chǔ)上，求得更遠(yuǎn)頂點(diǎn)的最短路徑，最終得到你要的結(jié)果。
弗洛伊德（Floyd）算法——從圖的帶權(quán)鄰接矩陣A=[a(i,j)] n×n開始，遞歸地進(jìn)行n次更新，即由矩陣D(0)=A，按一個(gè)公式，構(gòu)造出矩陣D(1)；又用同樣地公式由D(1)構(gòu)造出D(2)；……；最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號(hào)頂點(diǎn)到j(luò)號(hào)頂點(diǎn)的最短路徑長(zhǎng)度，稱D(n)為圖的距離矩陣。
時(shí)間復(fù)雜度是O(n3)。

在一個(gè)表示工程的有向圖中，用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)之間的優(yōu)先關(guān)系，這樣的有向圖為頂點(diǎn)表示活動(dòng)的網(wǎng)，我們稱為AOV網(wǎng)（ActivityOn Vertex Network）。
拓?fù)湫蛄校涸O(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的有向圖，V中的頂點(diǎn)序列v1，v2，……，vn，滿足若從頂點(diǎn)vi到vj有一條路徑，則在頂點(diǎn)序列中頂點(diǎn)vi必在頂點(diǎn)vj之前。則我們稱這樣的頂點(diǎn)序列為一個(gè)拓?fù)湫蛄小?br> 所謂拓?fù)渑判颍鋵?shí)就是對(duì)一個(gè)有向圖構(gòu)造拓?fù)湫蛄械倪^(guò)程。構(gòu)造時(shí)會(huì)有兩個(gè)結(jié)果，如果此網(wǎng)的全部頂點(diǎn)都被輸出，則說(shuō)明它是不存在環(huán)（回路）的AOV網(wǎng)；如果輸出頂點(diǎn)數(shù)少了，哪怕是少了一個(gè)，也說(shuō)明這個(gè)網(wǎng)存在環(huán)（回路），不是AOV網(wǎng)。
對(duì)AOV網(wǎng)進(jìn)行拓?fù)渑判虻幕舅悸肥牵簭腁OV網(wǎng)中選擇一個(gè)入度為0的頂點(diǎn)輸出，然后刪去此頂點(diǎn)，并刪除以此頂點(diǎn)為尾的弧，繼續(xù)重復(fù)此步驟，直到輸出全部頂點(diǎn)或者AOV網(wǎng)中不存在入度為0的頂點(diǎn)為止。
分析整個(gè)算法，對(duì)一個(gè)具有n個(gè)頂點(diǎn)e條弧的AOV網(wǎng)來(lái)說(shuō)，掃描頂點(diǎn)表，將入度為0的頂點(diǎn)入棧的時(shí)間復(fù)雜為O(n)，而之后的while循環(huán)中，每個(gè)頂點(diǎn)進(jìn)一次棧，出一次棧，入度減1的操作共執(zhí)行了e次，所以整個(gè)算法的時(shí)間復(fù)雜度為O(n+e)。

在一個(gè)表示工程的帶權(quán)有向圖中，用頂點(diǎn)表示事件，用有向邊表示活動(dòng)，用邊上的權(quán)值表示活動(dòng)的持續(xù)時(shí)間，這種有向圖的邊表示活動(dòng)的網(wǎng)，我們稱之為AOE網(wǎng)（Activity On Edge Net-work）。
盡管AOE網(wǎng)與AOV網(wǎng)都是用來(lái)對(duì)工程建模的，但它們還是有很大的不同，主要體現(xiàn)在AOV網(wǎng)是頂點(diǎn)表示活動(dòng)的網(wǎng)，它只描述活動(dòng)之間的制約關(guān)系，而AOE網(wǎng)是用邊表示活動(dòng)的網(wǎng)，邊上的權(quán)值表示活動(dòng)持續(xù)的時(shí)間。因此，AOE網(wǎng)是要建立在活動(dòng)之間制約關(guān)系沒(méi)有矛盾的基礎(chǔ)之上，再來(lái)分析完成整個(gè)工程至少需要多少時(shí)間，或者為縮短完成工程所需時(shí)間，應(yīng)當(dāng)加快哪些活動(dòng)等問(wèn)題。
我們把路徑上各個(gè)活動(dòng)所持續(xù)的時(shí)間之和稱為路徑長(zhǎng)度，從源點(diǎn)到匯點(diǎn)具有最大長(zhǎng)度的路徑叫關(guān)鍵路徑，在關(guān)鍵路徑上的活動(dòng)叫關(guān)鍵活動(dòng)。
計(jì)算關(guān)鍵路徑：
1.事件的最早發(fā)生時(shí)間etv（earliest time ofvertex）：即頂點(diǎn)vk的最早發(fā)生時(shí)間。
2.事件的最晚發(fā)生時(shí)間ltv（latest time ofvertex）：即頂點(diǎn)vk的最晚發(fā)生時(shí)間，也就是每個(gè)頂點(diǎn)對(duì)應(yīng)的事件最晚需要開始的時(shí)間，超出此時(shí)間將會(huì)延誤整個(gè)工期。
3.活動(dòng)的最早開工時(shí)間ete（earliest time ofedge）：即弧ak的最早發(fā)生時(shí)間。
4.活動(dòng)的最晚開工時(shí)間lte（latest time ofedge）：即弧ak的最晚發(fā)生時(shí)間，也就是不推遲工期的最晚開工時(shí)間。

第八章 查找

查找表（Search Table）是由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。

靜態(tài)查找表（Static Search Table）：只作查找操作的查找表。它的主要操作有：（1）查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中。（2）檢索某個(gè)“特定的”數(shù)據(jù)元素和各種屬性。

動(dòng)態(tài)查找表（Dynamic Search Table）：在查找過(guò)程中同時(shí)插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已經(jīng)存在的某個(gè)數(shù)據(jù)元素。顯然動(dòng)態(tài)查找表的操作就是兩個(gè)：（1）查找時(shí)插入數(shù)據(jù)元素。（2）查找時(shí)刪除數(shù)據(jù)元素。

為了提高查找的效率，我們需要專門為查找操作設(shè)置數(shù)據(jù)結(jié)構(gòu)，這種面向查找操作的數(shù)據(jù)結(jié)構(gòu)稱為查找結(jié)構(gòu)。

順序查找（Sequential Search）又叫線性查找，是最基本的查找技術(shù)，它的查找過(guò)程是：從表中第一個(gè)（或最后一個(gè)）記錄開始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值比較，若某個(gè)記錄的關(guān)鍵字和給定值相等，則查找成功，找到所查的記錄；如果直到最后一個(gè)（或第一個(gè)）記錄，其關(guān)鍵字和給定值比較都不等時(shí)，則表中沒(méi)有所查的記錄，查找不成功。
時(shí)間復(fù)雜度為O(n)。

有序表查找：對(duì)目標(biāo)實(shí)現(xiàn)進(jìn)行有序化
折半查找：折半查找（Binary Search）技術(shù)，又稱為二分查找。它的前提是線性表中的記錄必須是關(guān)鍵碼有序（通常從小到大有序），線性表必須采用順序存儲(chǔ)。折半查找的基本思想是：在有序表中，取中間記錄作為比較對(duì)象，若給定值與中間記錄的關(guān)鍵字相等，則查找成功；若給定值小于中間記錄的關(guān)鍵字，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間記錄的關(guān)鍵字，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過(guò)程，直到查找成功，或所有查找區(qū)域無(wú)記錄，查找失敗為止。時(shí)間復(fù)雜度來(lái)是O(logn)。
插值查找（Interpolation Search）是根據(jù)要查找的關(guān)鍵字key與查找表中最大最小記錄的關(guān)鍵字比較后的查找方法，其核心就在于插值的計(jì)算公式(key-a[low])/(a[high]-a[low])。時(shí)間復(fù)雜度來(lái)也是O(logn)。
斐波那契查找算法的核心在于： 1）當(dāng)key=a[mid]時(shí)，查找就成功； 2）當(dāng)key<a[mid]時(shí)，新范圍是第low個(gè)到第mid-1個(gè)，此時(shí)范圍個(gè)數(shù)為F[k-1]-1個(gè)； 3）當(dāng)key>a[mid]時(shí)，新范圍是第m+1個(gè)到第high個(gè)，此時(shí)范圍個(gè)數(shù)為F[k-2]-1個(gè)。

索引按照結(jié)構(gòu)可以分為線性索引、樹形索引和多級(jí)索引。我們重點(diǎn)介紹三種線性索引：稠密索引、分塊索引和倒排索引。
稠密索引：是指在線性索引中，將數(shù)據(jù)集中的每個(gè)記錄對(duì)應(yīng)一個(gè)索引項(xiàng)。
分塊索引：對(duì)于分塊有序的數(shù)據(jù)集，將每塊對(duì)應(yīng)一個(gè)索引項(xiàng)，這種索引方法叫做分塊索引。
倒排索引 ：記錄號(hào)表存儲(chǔ)具有相同次關(guān)鍵字的所有記錄的記錄號(hào)（可以是指向記錄的指針或者是該記錄的主關(guān)鍵字）。這樣的索引方法就是倒排索引（in-verted index）。

二叉排序樹（Binary Sort Tree），又稱為二叉查找樹。當(dāng)我們對(duì)它進(jìn)行中序遍歷時(shí)，就可以得到一個(gè)有序的序列。它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹。
? 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)構(gòu)的值；
? 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
? 它的左、右子樹也分別為二叉排序樹。
總之，二叉排序樹是以鏈接的方式存儲(chǔ)，保持了鏈接存儲(chǔ)結(jié)構(gòu)在執(zhí)行插入或刪除操作時(shí)不用移動(dòng)元素的優(yōu)點(diǎn)，只要找到合適的插入和刪除位置后，僅需修改鏈接指針即可。插入刪除的時(shí)間性能比較好。而對(duì)于二叉排序樹的查找，走的就是從根結(jié)點(diǎn)到要查找的結(jié)點(diǎn)的路徑，其比較次數(shù)等于給定值的結(jié)點(diǎn)在二叉排序樹的層數(shù)。極端情況，最少為1次，即根結(jié)點(diǎn)就是要找的結(jié)點(diǎn)，最多也不會(huì)超過(guò)樹的深度。也就是說(shuō)，二叉排序樹的查找性能取決于二叉排序樹的形狀?？蓡?wèn)題就在于，二叉排序樹的形狀是不確定的。
所以，進(jìn)行優(yōu)化的方法是讓二叉樹的左右兩邊最好平衡一下，這樣二叉樹的深度最淺，查找最節(jié)省時(shí)間。

平衡二叉樹（Self-Balancing Binary SearchTree或Height-Balanced Binary Search Tree），是一種二叉排序樹，其中每一個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度差至多等于1。
我們將二叉樹上結(jié)點(diǎn)的左子樹深度減去右子樹深度的值稱為平衡因子BF（Balance Factor），那么平衡二叉樹上所有結(jié)點(diǎn)的平衡因子只可能是-1、0和1。
距離插入結(jié)點(diǎn)最近的，且平衡因子的絕對(duì)值大于1的結(jié)點(diǎn)為根的子樹，我們稱為最小不平衡子樹。

平衡二叉樹構(gòu)建的基本思想就是在構(gòu)建二叉排序樹的過(guò)程中，每當(dāng)插入一個(gè)結(jié)點(diǎn)時(shí)，先檢查是否因插入而破壞了樹的平衡性，若是，則找出最小不平衡子樹。在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點(diǎn)之間的鏈接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹。

多路查找樹（muitl-way search tree），其每一個(gè)結(jié)點(diǎn)的孩子數(shù)可以多于兩個(gè)，且每一個(gè)結(jié)點(diǎn)處可以存儲(chǔ)多個(gè)元素。由于它是查找樹，所有元素之間存在某種特定的排序關(guān)系。

2-3樹是這樣的一棵多路查找樹：其中的每一個(gè)結(jié)點(diǎn)都具有兩個(gè)孩子（我們稱它為2結(jié)點(diǎn)）或三個(gè)孩子（我們稱它為3結(jié)點(diǎn)）。
一個(gè)2結(jié)點(diǎn)包含一個(gè)元素和兩個(gè)孩子（或沒(méi)有孩子），且與二叉排序樹類似，左子樹包含的元素小于該元素，右子樹包含的元素大于該元素。不過(guò)，與二叉排序樹不同的是，這個(gè)2結(jié)點(diǎn)要么沒(méi)有孩子，要有就有兩個(gè)，不能只有一個(gè)孩子。
一個(gè)3結(jié)點(diǎn)包含一小一大兩個(gè)元素和三個(gè)孩子（或沒(méi)有孩子），一個(gè)3結(jié)點(diǎn)要么沒(méi)有孩子，要么具有3個(gè)孩子。如果某個(gè)3結(jié)點(diǎn)有孩子的話，左子樹包含小于較小元素的元素，右子樹包含大于較大元素的元素，中間子樹包含介于兩元素之間的元素。
并且2-3樹中所有的葉子都在同一層次上。

2-3-4樹：它其實(shí)就是2-3樹的概念擴(kuò)展，包括了4結(jié)點(diǎn)的使用。一個(gè)4結(jié)點(diǎn)包含小中大三個(gè)元素和四個(gè)孩子（或沒(méi)有孩子），一個(gè)4結(jié)點(diǎn)要么沒(méi)有孩子，要么具有4個(gè)孩子。如果某個(gè)4結(jié)點(diǎn)有孩子的話，左子樹包含小于最小元素的元素；第二子樹包含大于最小元素，小于第二元素的元素；第三子樹包含大于第二元素，小于最大元素的元素；右子樹包含大于最大元素的元素。
B樹：，2-3樹是3階B樹，2-3-4樹是4階B樹。
一個(gè)m階的B樹具有如下屬性：
? 如果根結(jié)點(diǎn)不是葉結(jié)點(diǎn)，則其至少有兩棵子樹。
? 每一個(gè)非根的分支結(jié)點(diǎn)都有k-1個(gè)元素和k個(gè)孩子，其中。每一個(gè)葉子結(jié)點(diǎn)n都有k-1個(gè)元素，其中。
? 所有葉子結(jié)點(diǎn)都位于同一層次。
? 所有分支結(jié)點(diǎn)包含下列信息數(shù)據(jù)

B+樹是應(yīng)文件系統(tǒng)所需而出的一種B樹的變形樹，注意嚴(yán)格意義上講，它其實(shí)已經(jīng)不是第六章定義的樹了。在B樹中，每一個(gè)元素在該樹中只出現(xiàn)一次，有可能在葉子結(jié)點(diǎn)上，也有可能在分支結(jié)點(diǎn)上。而在B+樹中，出現(xiàn)在分支結(jié)點(diǎn)中的元素會(huì)被當(dāng)作它們?cè)谠摲种ЫY(jié)點(diǎn)位置的中序后繼者（葉子結(jié)點(diǎn)）中再次列出。另外，每一個(gè)葉子結(jié)點(diǎn)都會(huì)保存一個(gè)指向后一葉子結(jié)點(diǎn)的指針。下圖是B+樹。

一棵m階的B+樹和m階的B樹的差異在于：
有n棵子樹的結(jié)點(diǎn)中包含有n個(gè)關(guān)鍵字；
所有的葉子結(jié)點(diǎn)包含全部關(guān)鍵字的信息，及指向含這些關(guān)鍵字記錄的指針，葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接；
所有分支結(jié)點(diǎn)可以看成是索引，結(jié)點(diǎn)中僅含有其子樹中的最大（或最?。╆P(guān)鍵字。

散列表查找（哈希表）
散列技術(shù)是在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系f，使得每個(gè)關(guān)鍵字key對(duì)應(yīng)一個(gè)存儲(chǔ)位置f（key）。查找時(shí)，根據(jù)這個(gè)確定的對(duì)應(yīng)關(guān)系找到給定值key的映射f（key），若查找集合中存在這個(gè)記錄，則必定在f（key）的位置上。我們把這種對(duì)應(yīng)關(guān)系f稱為散列函數(shù)，又稱為哈希（Hash）函數(shù)。

采用散列技術(shù)將記錄存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中，這塊連續(xù)存儲(chǔ)空間稱為散列表或哈希表（Hash table）。

設(shè)計(jì)好的散列函數(shù)：1計(jì)算簡(jiǎn)單 2散列地址分布均勻。方法有：
直接地址法：取關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址
數(shù)字分析法：使用關(guān)鍵字的一部分來(lái)計(jì)算散列存儲(chǔ)位置的方法

平方取中法：
折疊法：折疊法是將關(guān)鍵字從左到右分割成位數(shù)相等的幾部分（注意最后一部分位數(shù)不夠時(shí)可以短些），然后將這幾部分疊加求和，并按散列表表長(zhǎng)，取后幾位作為散列地址。
除留余數(shù)法：
隨機(jī)數(shù)法：選擇一個(gè)隨機(jī)數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的散列地址。也就是f(key)=random(key)。這里random是隨機(jī)函數(shù)。當(dāng)關(guān)鍵字的長(zhǎng)度不等時(shí)，采用這個(gè)方法構(gòu)造散列函數(shù)是比較合適的。

處理三列沖突的方法：
開放定址法：所謂的開放定址法就是一旦發(fā)生了沖突，就去尋找下一個(gè)空的散列地址，只要散列表足夠大，空的散列地址總能找到，并將記錄存入。
再散列函數(shù)法：使用多個(gè)散列函數(shù)，如果發(fā)生沖突，則換一個(gè)散列函數(shù)。
鏈地址法：將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)鏈接在同一個(gè)單鏈表中。若選定的散列表長(zhǎng)度為m，則可將散列表定義為一個(gè)由m個(gè)頭指針組成的指針數(shù)組T[0..m-1]。
公共溢出區(qū)法：為所有沖突的單列出一個(gè)區(qū)域

散列查找的平均查找長(zhǎng)度取決于哪些因素？1．散列函數(shù)是否均勻 2．處理沖突的方法 3．散列表的裝填因子

第九章 排序

假設(shè)ki=kj(1≤i≤n,1≤j≤n,i≠j），且在排序前的序列中ri領(lǐng)先于rj（即i<j）。如果排序后ri仍領(lǐng)先于rj，則稱所用的排序方法是穩(wěn)定的；反之，若可能使得排序后的序列中rj領(lǐng)先ri，則稱所用的排序方法是不穩(wěn)定的。

內(nèi)排序是在排序整個(gè)過(guò)程中，待排序的所有記錄全部被放置在內(nèi)存中。外排序是由于排序的記錄個(gè)數(shù)太多，不能同時(shí)放置在內(nèi)存，整個(gè)排序過(guò)程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能進(jìn)行。

排序算法的性能主要受3個(gè)方面的影響：時(shí)間性能、輔助空間、算法的復(fù)雜性。按照算法的復(fù)雜度分為兩大類，冒泡排序、簡(jiǎn)單選擇排序和直接插入排序?qū)儆诤?jiǎn)單算法，而希爾排序、堆排序、歸并排序、快速排序?qū)儆诟倪M(jìn)算法。

冒泡排序（Bubble Sort）一種交換排序，它的基本思想是：兩兩比較相鄰記錄的關(guān)鍵字，如果反序則交換，直到?jīng)]有反序的記錄為止。

簡(jiǎn)單選擇排序法（Simple Selection Sort）就是通過(guò)n-i次關(guān)鍵字間的比較，從n-i＋1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第i（1≤i≤n）個(gè)記錄交換之。

直接插入排序：基本操作是將一個(gè)記錄插入到已經(jīng)排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增1的有序表。

希爾排序（相當(dāng)于直接插入法的升級(jí)）：：將相距某個(gè)“增量”的記錄組成一個(gè)子序列，這樣才能保證在子序列內(nèi)分別進(jìn)行直接插入排序后得到的結(jié)果是基本有序而不是局部有序。逐漸縮小這個(gè)“增量”。

堆排序（相當(dāng)于簡(jiǎn)單選擇排序的升級(jí)）：
堆是具有下列性質(zhì)的完全二叉樹：每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值，稱為大頂堆；或者每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值，稱為小頂堆。
堆排序（Heap Sort）就是利用堆（假設(shè)利用大頂堆）進(jìn)行排序的方法。它的基本思想是，將待排序的序列構(gòu)造成一個(gè)大頂堆。此時(shí)，整個(gè)序列的最大值就是堆頂?shù)母Y(jié)點(diǎn)。將它移走（其實(shí)就是將其與堆數(shù)組的末尾元素交換，此時(shí)末尾元素就是最大值），然后將剩余的n-1個(gè)序列重新構(gòu)造成一個(gè)堆，這樣就會(huì)得到n個(gè)元素中的次大值。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列了。

歸并排序：歸并排序（Merging Sort）就是利用歸并的思想實(shí)現(xiàn)的排序方法。它的原理是假設(shè)初始序列含有n個(gè)記錄，則可以看成是n個(gè)有序的子序列，每個(gè)子序列的長(zhǎng)度為1，然后兩兩歸并，得到|n/2|（|x|表示不小于x的最小整數(shù)）個(gè)長(zhǎng)度為2或1的有序子序列；再兩兩歸并，……，如此重復(fù)，直至得到一個(gè)長(zhǎng)度為n的有序序列為止，這種排序方法稱為2路歸并排序。

快速排序（排序算法王者，20世紀(jì)十大算法之一！卻是前面最慢的冒泡排序的升級(jí)）：基本思想是通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序的目的。

總結(jié)：
歸類

時(shí)間復(fù)雜度比較：

從最好情況看，反而冒泡和直接插入排序要更勝一籌，也就是說(shuō)，如果你的待排序序列總是基本有序，反而不應(yīng)該考慮4種復(fù)雜的改進(jìn)算法。 從最壞情況看，堆排序與歸并排序又強(qiáng)過(guò)快速排序以及其他簡(jiǎn)單排序。

從這三組時(shí)間復(fù)雜度的數(shù)據(jù)對(duì)比中，我們可以得出這樣一個(gè)認(rèn)識(shí)。堆排序和歸并排序就像兩個(gè)參加奧數(shù)考試的優(yōu)等生，心理素質(zhì)強(qiáng)，發(fā)揮穩(wěn)定。而快速排序像是很情緒化的天才，心情好時(shí)表現(xiàn)極佳，碰到較糟糕環(huán)境會(huì)變得差強(qiáng)人意。但是他們?nèi)绻紒?lái)比賽計(jì)算個(gè)位數(shù)的加減法，它們反而算不過(guò)成績(jī)極普通的冒泡和直接插入。 從空間復(fù)雜度來(lái)說(shuō)，歸并排序強(qiáng)調(diào)要馬跑得快，就得給馬吃個(gè)飽?？焖倥判蛞灿邢鄳?yīng)的空間要求，反而堆排序等卻都是少量索取，大量付出，對(duì)空間要求是O(1)。如果執(zhí)行算法的軟件所處的環(huán)境非常在乎內(nèi)存使用量的多少時(shí)，選擇歸并排序和快速排序就不是一個(gè)較好的決策了。

從穩(wěn)定性來(lái)看，歸并排序獨(dú)占鰲頭，我們前面也說(shuō)過(guò)，對(duì)于非常在乎排序穩(wěn)定性的應(yīng)用中，歸并排序是個(gè)好算法。 從待排序記錄的個(gè)數(shù)上來(lái)說(shuō)，待排序的個(gè)數(shù)n越小，采用簡(jiǎn)單排序方法越合適。反之，n越大，采用改進(jìn)排序方法越合適。這也就是我們?yōu)槭裁磳?duì)快速排序優(yōu)化時(shí)，增加了一個(gè)閥值，低于閥值時(shí)換作直接插入排序的原因。

因此對(duì)于數(shù)據(jù)量不是很大而記錄的關(guān)鍵字信息量較大的排序要求，簡(jiǎn)單排序算法是占優(yōu)的。