【正文】 有邊（?。?、找頂點(diǎn)的鄰接點(diǎn)等等。空間效率為O(n2)。鄰接表的優(yōu)點(diǎn)：空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；鄰接表的缺點(diǎn)：判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對應(yīng)的單鏈表，沒有鄰接矩陣方便。 遍歷定義：從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊，訪遍圖中所有的頂點(diǎn)，且使每個頂點(diǎn)僅被訪問一次，就叫做圖的遍歷，它是圖的基本運(yùn)算。② 若v的第1個鄰接點(diǎn)沒訪問過，深度遍歷此鄰接點(diǎn)；③ 若當(dāng)前鄰接點(diǎn)已訪問過，再找v的第2個鄰接點(diǎn)重新遍歷。廣度優(yōu)先搜索（遍歷）步驟：① 在訪問了起始點(diǎn)v之后，依次訪問 v的鄰接點(diǎn)；② 然后再依次（順序）訪問這些點(diǎn)（下一層）中未被訪問過的鄰接點(diǎn)；③ 直到所有頂點(diǎn)都被訪問過為止。U，v0206。 求MST最常用的是以下兩種：Kruskal（克魯斯卡爾）算法、Prim（普里姆）算法 Kruskal算法特點(diǎn)：將邊歸并，適于求稀疏網(wǎng)的最小生成樹。 在帶權(quán)有向圖中A點(diǎn)（源點(diǎn)）到達(dá)B點(diǎn)（終點(diǎn)）的多條路徑中，尋找一條各邊權(quán)值之和最小的路徑，即最短路徑。限定各邊上的權(quán)值大于或等于0。學(xué)習(xí)重點(diǎn)： 圖是應(yīng)用最廣泛的一種數(shù)據(jù)結(jié)構(gòu)，本章也是這門課程的重點(diǎn)。 ① 連通圖：在無向圖中, 若從頂點(diǎn)v1到頂點(diǎn)v2有路徑, 則稱頂點(diǎn)v1與v2是連通的。 非連通圖的極大連通子圖叫做連通分量。 ③ 鄰接點(diǎn)：若 (u, v) 是 E(G) 中的一條邊，則稱 u 與 v 互為鄰接頂點(diǎn)。這兩種存儲結(jié)構(gòu)對有向圖和無向圖均適用◆ 圖的遍歷是圖的各種算法的基礎(chǔ)，應(yīng)熟練掌握圖的深度、廣度優(yōu)先遍歷。 應(yīng)熟練掌握prim和kruscal算法，特別是手工分步模擬生成樹的生成過程。 補(bǔ)充：1. 問：當(dāng)有向圖中僅1個頂點(diǎn)的入度為0,其余頂點(diǎn)的入度均為1，此時是何形狀？答：是樹！而且是一棵有向樹?。亨徑颖砼c鄰接矩陣有什么異同之處？1. 聯(lián)系：鄰接表中每個鏈表對應(yīng)于鄰接矩陣中的一行， 鏈表中結(jié)點(diǎn)個數(shù)等于一行中非零元素的個數(shù)。3. 用途：鄰接矩陣多用于稠密圖的存儲而鄰接表多用于稀疏圖的存儲3. 若對連通圖進(jìn)行遍歷，得到的是生成樹 若對非連通圖進(jìn)行遍歷，得到的是生成森林。是元素間約束力最差的數(shù)據(jù)結(jié)構(gòu)：元素間的關(guān)系是元素僅共在同一個集合中。◆ 靜態(tài)查找表：順序表，有序表等。int Search_Seq( SSTable ST , KeyType key ){[0].key =key。 [ i ].key!=key。 return i。缺點(diǎn)： ASL 太大，時間效率太低。ASL的含義是“平均每個數(shù)據(jù)的查找時間”，而前式是n個數(shù)據(jù)查找時間的總和，所以： 三、分塊查找（索引順序查找）思路：先讓數(shù)據(jù)分塊有序，即分成若干子表，要求每個子表中的數(shù)據(jù)元素值都比后一塊中的數(shù)值?。ǖ颖韮?nèi)部未必有序）。特點(diǎn)：塊間有序，塊內(nèi)無序。特點(diǎn)：表結(jié)構(gòu)在查找過程中動態(tài)生成。① 二叉排序樹的定義或是一棵空樹；或者是具有如下性質(zhì)的非空二叉樹： （1）左子樹的所有結(jié)點(diǎn)均小于根的值； （2）右子樹的所有結(jié)點(diǎn)均大于根的值； （3）它的左右子樹也分別為二叉排序樹。SearchBST (K, amp。 //p為查找過程中進(jìn)行掃描的指針 while（p!=NULL）{ case { K= pdata: {查找成功，return } K pdata : {q=p；p=pL_child } //繼續(xù)向左搜索 K pdata : {q=p；p=pR_child } //繼續(xù)向右搜索 } } //查找不成功則插入到二叉排序樹中s =(BiTree)malloc(sizeof(BiTNode))。 s L_child=NULL。 //查找不成功，生成一個新結(jié)點(diǎn)s，插入到二叉排序樹葉子處case { t=NULL： t=s。 //若K比葉子小，掛左邊K qdata: qR_child=s。有兩種解決方法：法1：令*p的左子樹為 *f的左子樹，*p的右子樹接為*s的右子樹； //即 fL=PL 。法2：直接令*s代替*p // *s為*p左子樹最右下方的結(jié)點(diǎn)二叉排序樹的④ 平衡二叉樹的定義：又稱AVL樹，即它或者是一顆空樹，或者是它的左子樹和右子樹都是平衡二叉樹，且左子樹與右子樹的深度之差的絕對值不超過1。平衡二叉樹的特點(diǎn)：任一結(jié)點(diǎn)的平衡因子只能取：0 或 1。我們稱調(diào)整平衡過程為平衡旋轉(zhuǎn)?！?查找表是稱為集合的數(shù)據(jù)結(jié)構(gòu)。本章列舉了三種方法（靜態(tài)查找表，動態(tài)查找表）實現(xiàn)查找表的運(yùn)算。有序表的平均查找長度不超過樹的深度。按中序遍歷可得到結(jié)點(diǎn)的有序序列，應(yīng)熟練掌握其建立、查找，插入和刪除算法。補(bǔ)充：？ 給定一個值K，在含有n個記錄的文件中進(jìn)行搜索，尋找一個關(guān)鍵字值等于K的記錄，如找到則輸出該記錄，否則輸出查找不成功的信息。 ？查找方法取決于表中數(shù)據(jù)的排列方式。稱為平均查找長度ASL。第9章 內(nèi)部排序內(nèi)容提要：◆ 排序的定義，排序可以看作是線性表的一種操作 排序:將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。 穩(wěn)定性——若兩個記錄A和B的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。插入排序的基本思想是：每步將一個待排序的對象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對象的適當(dāng)位置上，直到對象全部插入為止。1) 直接插入排序 在已形成的有序表中線性查找，并在適當(dāng)位置插入，把原來位置上的元素向后順移。 其他情況下也要考慮移動元素的次數(shù)。L ) { //對順序表L作直接插入排序 for ( i = 2。 i++) //假定第一個記錄有序{ [0]= [i]。 //先將待插入的元素放入“哨兵”位置 while（L[0] .keyL[j].key){ [j+1]= [j]。 } //只要子表元素比哨兵大就不斷后移[j+1]= [0]。優(yōu)點(diǎn)：比較次數(shù)大大減少，全部元素比較次數(shù)僅為O(nlog2n)。空間效率：仍為 O（1）穩(wěn) 定 性： 穩(wěn)定若記錄是鏈表結(jié)構(gòu)，用直接插入排序行否？答：行，而且無需移動元素，時間效率更高！但請注意：單鏈表結(jié)構(gòu)無法實現(xiàn)“折半查找”3） 表插入排序基本思想：在順序存儲結(jié)構(gòu)中，給每個記錄增開一個指針分量，在排序過程中將指針內(nèi)容逐個修改為已經(jīng)整理（排序）過的后繼記錄地址。此方法具有鏈表排序和地址排序的特點(diǎn)表插入排序算法分析：① 無需移動記錄，只需修改指針值。② 空間效率肯定低，因為增開了指針分量（但在運(yùn)算過程中沒有用到更多的輔助單元）。注：此算法得到的只是一個有序鏈表，查找記錄時只能滿足順序查找方式。優(yōu)點(diǎn)：讓關(guān)鍵字值小的元素能很快前移，且序列若基本有序時，再用直接插入排序處理，時間效率會高很多。 交換排序的基本思想是：兩兩比較待排序記錄的關(guān)鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序為止。優(yōu)點(diǎn)：每趟結(jié)束時，不僅能擠出一個最大值到最后面位置，還能同時部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結(jié)束排序。2） 快速排序基本思想：從待排序列中任取一個元素 (例如取第一個) 作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個子表；然后再對各子表重新選擇中心元素并依此規(guī)則調(diào)整，直到每個子表的元素只剩一個。優(yōu)點(diǎn)：因為每趟可以確定不止一個元素的位置，而且呈指數(shù)增加，所以特別快！ 前提：順序存儲結(jié)構(gòu) 時間效率：O(nlog2n) —因為每趟確定的元素呈指數(shù)增加空間效率：O（log2n）—因為遞歸要用棧(存每層low，high和pivot)穩(wěn) 定 性： 不 穩(wěn) 定 —因為有跳躍式交換。選擇排序的基本思想是：每一趟在后面ni 個待排記錄中選取關(guān)鍵字最小的記錄作為有序序列中的第i 個記錄?！紫龋趎個記錄中選擇最小者放到r[1]位置；然后，從剩余的n1個記錄中選擇最小者放到r[2]位置；…如此進(jìn)行下去，直到全部有序為止。L ) { for (i=1。 ++i){ j = SelectMinKey(L,i)。r[j]。 首先對 n 個記錄的關(guān)鍵字進(jìn)行兩兩比較，得到 233。 個優(yōu)勝者(關(guān)鍵字小者)，作為第一步比較的結(jié)果保留下來。n/2249。優(yōu)點(diǎn)：減少比較次數(shù)，加快排序速度缺點(diǎn)：空間效率低3） 堆排序：設(shè)有n個元素的序列 k1，k2，…，kn，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時，稱之為堆。2. 怎樣建堆？步驟：從最后一個非終端結(jié)點(diǎn)開始往前逐步調(diào)整，讓每個雙親大于（或小于）子女，直到根結(jié)點(diǎn)為止。因為整個排序過程中需要調(diào)用n1次HeapAdjust( )算法，而算法本身耗時為log2n；空間效率：O(1)。穩(wěn)定性： 不穩(wěn)定。學(xué)習(xí)要點(diǎn)：◆ 在“最好”和“最差”情況下，排序性能的分析，是否是穩(wěn)定排序的結(jié)論，時間效率和空間效率。補(bǔ)充：？時間效率——排序速度（即排序所花費(fèi)的全部比較次數(shù)）空間效率——占內(nèi)存輔助空間的大小穩(wěn)定性——若兩個記錄A和B的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。