【正文】 鏈表)。其中ai或者是原子或者是一個(gè)廣義表。 ?、?gòu)V義表通常用圓括號(hào)括起來(lái)，用逗號(hào)分隔其中的元素。 ?、跒榱藚^(qū)分原子和廣義表，書(shū)寫(xiě)時(shí)用大寫(xiě)字母表示廣義表，用小寫(xiě)字母表示原子。 ?、廴魪V義表Ls非空(n≥1)，則al是LS的表頭，其余元素組成的表(a1，a2，…，an)稱為L(zhǎng)s的表尾?！?④廣義表具有遞歸和共享的性質(zhì)廣義表的深度：一個(gè)表展開(kāi)后所含括號(hào)的層數(shù)稱為廣義表的深度。 head=(a，b)=a，tail(a，b)=(b) 前者是長(zhǎng)度為0的空表，對(duì)其不能做求表頭和表尾的運(yùn)算；而后者是長(zhǎng)度為l的由空表作元素的廣義表，可以分解得到的表頭和表尾均是空表()。（1）結(jié)點(diǎn)的度(Degree) 　樹(shù)中的一個(gè)結(jié)點(diǎn)擁有的子樹(shù)數(shù)稱為該結(jié)點(diǎn)的度(Degree)。（2）①路徑（path）若樹(shù)中存在一個(gè)結(jié)點(diǎn)序列k1，k2，…，ki，使得ki是ki+1的雙親(1≤ij)，則稱該結(jié)點(diǎn)序列是從kl到kj的一條路徑(Path)。刪去一棵樹(shù)的根，就得到一個(gè)森林；反之，加上一個(gè)結(jié)點(diǎn)作樹(shù)根，森林就變?yōu)橐豢脴?shù)。例如5層的二叉樹(shù)，第5層上的結(jié)點(diǎn)數(shù)目最多為24=16性質(zhì)2 深度為k的二叉樹(shù)至多有2k1個(gè)結(jié)點(diǎn)(k≥1)。即對(duì)給定的高度，它是具有最多結(jié)點(diǎn)數(shù)的二叉樹(shù)。 （1） 滿二叉樹(shù)是完全二叉樹(shù)，完全二叉樹(shù)不一定是滿二叉樹(shù)。 （3） 在完全二叉樹(shù)中，若某個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它一定沒(méi)有右孩子，即該結(jié)點(diǎn)必是葉結(jié)點(diǎn)。每一層的結(jié)點(diǎn)個(gè)數(shù)恰好是上一層結(jié)點(diǎn)個(gè)數(shù)的2倍。③若2i+2n，則qi的右孩子的編號(hào)是2i+2；否則，qi無(wú)右孩子。用鏈接方式存儲(chǔ)二叉樹(shù)時(shí)，每個(gè)結(jié)點(diǎn)除了存儲(chǔ)結(jié)點(diǎn)本身的數(shù)據(jù)外，還應(yīng)設(shè)置兩個(gè)指針域lchild和rchild，分別指向該結(jié)點(diǎn)的左孩子和右孩子。具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，共有2n個(gè)指針域。先序遍歷的遞歸算法定義：(1)訪問(wèn)根結(jié)點(diǎn)； (2)遍歷左子樹(shù)； (3)遍歷右子樹(shù)。具體方法如下： 首先根據(jù)前序或后序遍歷序列確定二叉樹(shù)的各子樹(shù)的的根，然后根據(jù)中序遍歷序列確定各子樹(shù)根的左右子樹(shù)。線索鏈表的結(jié)點(diǎn)結(jié)構(gòu)：其中:ltag和rtag是增加的兩個(gè)標(biāo)志域，用來(lái)區(qū)分結(jié)點(diǎn)的左、右指針域是指向其左、右孩子的指針，還是指向其前趨或后繼的線索。 線索二叉樹(shù)中，一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)的充要條件為：左、右標(biāo)志均是1。、森林到二叉樹(shù)的轉(zhuǎn)換：樹(shù)中每個(gè)結(jié)點(diǎn)最多只有一個(gè)最左邊的孩子(長(zhǎng)子)和一個(gè)右鄰的兄弟。：：雙親鏈表表示法利用樹(shù)中每個(gè)結(jié)點(diǎn)的雙親唯一性，在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，為每個(gè)結(jié)點(diǎn)附設(shè)一個(gè)指向其雙親的指針parent，惟一地表示任何棵樹(shù)。：孩子鏈表表示法是為樹(shù)中每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)孩子鏈表，并將這些結(jié)點(diǎn)及相應(yīng)的孩子鏈表的頭指針存放在一個(gè)向量中。：一般都只給出兩種次序遍歷樹(shù)的方法：前序(先根次序)遍歷和后序(后根次序)遍歷。① 前序遍歷森林等同于前序遍歷該森林對(duì)應(yīng)的二叉樹(shù)② 后序遍歷森林等同于中序遍歷該森林對(duì)應(yīng)的二叉樹(shù)，樹(shù)種所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和稱為樹(shù)的帶權(quán)路徑長(zhǎng)度。完全二叉樹(shù)就是這種路徑長(zhǎng)度最短的二叉樹(shù)。　　(2)在森林F中選出兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)(當(dāng)這樣的樹(shù)不止兩棵樹(shù)時(shí)，可以從中任選兩棵)，將這兩棵樹(shù)合并成一棵新樹(shù)，為了保證新樹(shù)仍是二叉樹(shù)，需要增加一個(gè)新結(jié)點(diǎn)作為新樹(shù)的根，并將所選的兩棵樹(shù)的根分別作為新根的左右孩子(誰(shuí)左，誰(shuí)右無(wú)關(guān)緊要)，將這兩個(gè)孩子的權(quán)值之和作為新樹(shù)根的權(quán)值。注意：① 初始森林中的n棵二叉樹(shù)，每棵樹(shù)有一個(gè)孤立的結(jié)點(diǎn)，它們既是根，又是葉子最終求得的哈夫曼樹(shù)中共有2n1個(gè)結(jié)點(diǎn)。 ③ 哈夫曼樹(shù)是嚴(yán)格的二叉樹(shù)，沒(méi)有度數(shù)為1的分支結(jié)點(diǎn)。因此設(shè)計(jì)電文總長(zhǎng)最短的二進(jìn)制前綴編碼，就是以n種字符出現(xiàn)的頻率作為權(quán)構(gòu)造一棵哈夫曼樹(shù)，由哈夫曼樹(shù)求得的編碼就是哈夫曼編碼。無(wú)向圖的頂點(diǎn)對(duì)用圓括號(hào)表示(vi,vj)。在無(wú)向圖中，任意兩頂點(diǎn)都有路徑，則稱兩頂點(diǎn)連通。若在一個(gè)圖的每條邊上標(biāo)上某種數(shù)值，該數(shù)值稱為該邊的權(quán)。 鄰接矩陣表示法：vi,vj或(vi,vj)是邊，則值為1，不是邊則值為0。將無(wú)向圖的鄰接表稱為邊表，將有向圖的鄰接表稱為出邊表，將鄰接表的表頭向量稱為頂點(diǎn)表。：遍歷圖的算法是求解圖的連通性、圖的拓?fù)渑判虻人惴ǖ幕A(chǔ)。共需要搜索n2個(gè)矩陣元素，時(shí)間復(fù)雜度為鄰接矩陣O(n2)或鄰接表O(n+e)。 因此，一個(gè)具有n個(gè)頂點(diǎn)的生成樹(shù)有且僅有n1條邊，但有n1條邊的圖不一定是生成樹(shù)，同一個(gè)圖可以有不同的生成樹(shù)。克魯斯卡爾Kruskal算法的時(shí)間復(fù)雜度為O（eloge），主要取決于邊數(shù)，較適合于稀疏圖。 將有向無(wú)環(huán)圖G中所有頂點(diǎn)排成一個(gè)線性序列，若u，v∈E（G），則在線性序列u在v之前，這種線性序列稱為拓?fù)湫蛄小? 拓?fù)渑判虻拿枋鏊枷耄篴、在有向圖中選一個(gè)沒(méi)有前趨(入度為零)的頂點(diǎn)，且輸出之。 拓?fù)渑判驅(qū)嶋H上是對(duì)鄰接表表示的圖G進(jìn)行遍歷的過(guò)程。內(nèi)部排序又分為五類：插入、選擇、交換、歸并和分配排序。排序的時(shí)間開(kāi)銷，一般情況下可用算法中關(guān)鍵字的比較次數(shù)和記錄的移動(dòng)次數(shù)來(lái)衡量。所以R[0]稱為哨兵。 是穩(wěn)定的算法。希爾排序的時(shí)間依賴于增量序列，最后一個(gè)增量必須是1，盡量避免增量互為倍數(shù)的情況。是穩(wěn)定的排序算法?？焖倥判蚴遣环€(wěn)定的。 直接選擇排序：初始時(shí)，R[1..n]為無(wú)序區(qū)，R[1]為空；第一趟是在R[1..n]中選出最小的記錄與R[1]交換，R[1]為有序區(qū)；第二趟是在R[2..n]中選出最小的記錄與R[2]交換，R[1..2]為有序區(qū)?；舅枷耄涸谂判蜻^(guò)程中，將記錄數(shù)組R[1..n]看成是一棵完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹(shù)中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系，在當(dāng)前無(wú)序區(qū)中選擇關(guān)鍵字最大或最小記錄。從?n/2?開(kāi)始。：前面方法都至少需要進(jìn)行?nlogn?次比較，而分配排序?qū)r(shí)間復(fù)雜度降為O(n)。d趟箱排序。一般的排序方法都可以在順序結(jié)構(gòu)上實(shí)現(xiàn)，當(dāng)記錄本身信息量較大時(shí)，可采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 運(yùn)算查找的主要操作是關(guān)鍵字的比較，因此把查找過(guò)程中的平均比較次數(shù)(也稱為平均查找長(zhǎng)度)作為衡量算法效率優(yōu)劣的標(biāo)準(zhǔn)。 對(duì)于有序表來(lái)說(shuō)，該算法的平均查找長(zhǎng)度是(n+1)/2。由于二分查找是在有序表上進(jìn)行的，所以其對(duì)應(yīng)的判定樹(shù)必定是一棵二叉排序樹(shù)。查找成功時(shí)的平均查找長(zhǎng)度 (n+1)/nlog2(n+1)1，當(dāng)n很大時(shí)，可近似用log2(n+1)1表示。(分塊查找)：是一種介于順序查找和二分查找之間的查找方法。 順序查找缺點(diǎn)是n較大時(shí)，查找成功約為(n+1)/2，失敗需要比較n+1次。 上述三種查找的時(shí)間復(fù)雜度分別是O(n)、O(log2n)和O(n的平方根)(二叉查找樹(shù))：或者是一棵空樹(shù)，或者具有下面性質(zhì)：a、若右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根節(jié)點(diǎn)的值。同樣一組關(guān)鍵字序列，由于其輸入順序不同，所得到的二叉排序樹(shù)也有所不同，含有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)不是唯一的。 二叉排序樹(shù)的刪除：被刪除結(jié)點(diǎn)為p，其父結(jié)點(diǎn)為f。s是p的右子樹(shù)中最左邊的結(jié)點(diǎn)且沒(méi)有左子樹(shù)。 一棵m(m≥3)階的B樹(shù)，或?yàn)榭諛?shù)，或?yàn)闈M足下列性質(zhì)的m叉樹(shù) a、每個(gè)結(jié)點(diǎn)至少包含下列信息域；b、每個(gè)結(jié)點(diǎn)至多有m棵子樹(shù)；c、若樹(shù)為非空，則根結(jié)點(diǎn)至少有1個(gè)關(guān)鍵字，至多有m1個(gè)關(guān)鍵字。+樹(shù)是一種文件組織的B樹(shù)的變形樹(shù)，通常有兩個(gè)頭指針root和sqt，前者指向根結(jié)點(diǎn)，后者指向關(guān)鍵字最小的葉子結(jié)點(diǎn)。具有相同散列地址的關(guān)鍵字稱為同義詞。直接地址法：計(jì)算簡(jiǎn)單，并且沒(méi)有沖突。這是一種最簡(jiǎn)單也最常用的方法。二次探查法：d+12，d12，d+22，d22拉鏈法：存儲(chǔ)結(jié)構(gòu)是鏈表時(shí)常用。，順序查找和二分查找所需要進(jìn)行的關(guān)鍵字僅取決于表長(zhǎng)，而散列表查找所需要進(jìn)行的比較次數(shù)和待查結(jié)點(diǎn)有關(guān)。 完美WORD格式編輯 。開(kāi)放定址法：裝填因子α≤1。有m個(gè)散列地址就有m個(gè)鏈表。：開(kāi)放定址法和拉鏈法。數(shù)字分析法：從中提取數(shù)字分布比較均勻的若干位作為散列地址。如何盡量避免沖突和沖突發(fā)生后如何解決沖突，就成了散列存儲(chǔ)的兩個(gè)關(guān)鍵問(wèn)題。，是一種由關(guān)鍵字到地址的直接轉(zhuǎn)換方法。d、每個(gè)非根結(jié)點(diǎn)中所含的關(guān)鍵字個(gè)數(shù)滿足：?m/2?1≤n≤m1，因?yàn)槊總€(gè)內(nèi)部結(jié)點(diǎn)的度數(shù)正好是關(guān)鍵字總數(shù)加1，所以處根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有?m/2?棵子樹(shù)，至多有m棵子樹(shù)。平衡二叉樹(shù)：既能滿足BST性質(zhì)又能保證二叉排序樹(shù)的深度在任何情況下均為O(log2n)。即p是左子樹(shù)則p的子樹(shù)變?yōu)閒的左子樹(shù)；c、若p既有左子樹(shù)又有右子樹(shù)，任選一種方法：(1)、用p的直接前驅(qū)結(jié)點(diǎn)代替p，即從p的左子樹(shù)中選擇值最大的結(jié)點(diǎn)s放在p的位置(用結(jié)點(diǎn)s的內(nèi)容替換結(jié)點(diǎn)p內(nèi)容)，然后刪除結(jié)點(diǎn)s。二叉排序樹(shù)的查找與給定值的比較次數(shù)不會(huì)超過(guò)樹(shù)的深度。c、左右子樹(shù)本身又各是一棵二叉排序樹(shù)。 分塊查找的優(yōu)點(diǎn)是，在表中插入或刪除一個(gè)記錄時(shí)，只要找到該記錄所屬的塊，就可以在該塊內(nèi)進(jìn)行插入或刪除操作，因?yàn)閴K內(nèi)記錄是無(wú)序的，所以插入或刪除比較容易，無(wú)需移動(dòng)大量記錄。 分塊查找的基本思想是：首先查找索引表，可用二分查找或順序查找，然后在確定的塊中進(jìn)行順序查找?？梢?jiàn)，二分查找的最壞性能和平均性能相當(dāng)接近。 從判定樹(shù)上可見(jiàn)，關(guān)鍵字比較的次數(shù)恰好為該結(jié)點(diǎn)在樹(shù)中的層數(shù)。查找過(guò)程是遞歸的。如果查找成功和不成功機(jī)會(huì)相等，那么平均查找長(zhǎng)度3(n+1)/4。第八章：查找，是數(shù)據(jù)處理中經(jīng)常使用的一種重要運(yùn)算。：本章除基數(shù)排序外，都是在順序表上實(shí)現(xiàn)的。箱排序只適用于關(guān)鍵字取值范圍較小的情況，否則所需箱子數(shù)目太多。：首先將待排序文件看成n個(gè)長(zhǎng)度為1的有序子文件，把這些子文件兩兩歸并，得到?n/2?個(gè)長(zhǎng)度為2的有序子文件，然后再將他們兩兩歸并，如此反復(fù)，直到得到一個(gè)長(zhǎng)度為n的有序文件，此稱為二路歸并排序。堆排序是一個(gè)不斷建堆的過(guò)程。初始情況是有序區(qū)為空，無(wú)序區(qū)中R[1..n]，第一趟從R[1..n]選擇最小記錄與R[1]交換?？焖倥判蚴沁f歸的，需要一個(gè)?？臻g，空間復(fù)雜度O(log2n)。比較和交換從