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