【正文】 二、所有頂點(diǎn)間的最短路徑—用Floyd（弗洛伊德）算法一、單源最短路徑 (Dijkstra算法)一頂點(diǎn)到其余各頂點(diǎn)（v0→j）目的： 設(shè)一有向圖G=（V, E），已知各邊的權(quán)值，以某指定點(diǎn)v0為源點(diǎn)，求從v0到圖的其余各點(diǎn)的最短路徑。 ② 生成樹：是一個(gè)極小連通子圖，它含有圖中全部n個(gè)頂點(diǎn)，但只有n1條邊。2. 區(qū)別：對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點(diǎn)編號一致），但鄰接表不唯一（鏈接次序與頂點(diǎn)編號無關(guān)）。 for( i=。然后將各子表中的最大關(guān)鍵字構(gòu)成一個(gè)索引表，表中還要包含每個(gè)子表的起始地址（即頭指針）。t) { //K為待查關(guān)鍵字，t為根結(jié)點(diǎn)指針 p=t。 //若K比葉子大，掛右邊 }return OK}③ 二叉排序樹的刪除操作如何實(shí)現(xiàn)？如何刪除一個(gè)結(jié)點(diǎn)？假設(shè)：*p表示被刪結(jié)點(diǎn)的指針； PL和PR 分別表示*P的左、右孩子指針；*f表示*p的雙親結(jié)點(diǎn)指針；并假定*p是*f的左孩子；則可能有三種情況： *p有兩棵子樹時(shí)，如何進(jìn)行刪除操作？設(shè)刪除前的中序遍歷序列為：…. PL s p PR f //顯然p的直接前驅(qū)是s ，s是*p左子樹最右下方的結(jié)點(diǎn)希望刪除p后，其它元素的相對位置不變。平衡旋轉(zhuǎn)可以歸納為四類：學(xué)習(xí)重點(diǎn)：◆ 平衡二叉樹的概念，應(yīng)熟練掌握手工繪制平衡二叉樹。簡言之，邊插入邊排序，保證子序列中隨時(shí)都是排好序的。 j=i1 。優(yōu)點(diǎn)：在排序過程中不移動元素，只修改指針?！?交換排序（冒泡排序、快速排序）。◆ 選擇排序（簡單選擇排序、樹形選擇排序、堆排序）。 if( i!=j ) r[i] 171。 個(gè)較小者之間再進(jìn)行兩兩比較，…，如此重復(fù)，直到選出最小關(guān)鍵字的記錄為止。優(yōu)點(diǎn)：對小文件效果不明顯，但對大文件有效。2. “快速排序”是否真的比任何排序算法都快？ ——基本上是，因?yàn)槊刻丝梢源_定的數(shù)據(jù)元素是呈指數(shù)增加的。僅在第二個(gè)for循環(huán)中交換記錄時(shí)用到一個(gè)臨時(shí)變量temp。然后在這 233。 i。此時(shí)便為有序序列了。5） 希爾（shell）排序基本思想：先將整個(gè)待排記錄序列分割成若干子序列,分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對全體記錄進(jìn)行一次直接插入排序。時(shí)間效率：雖然比較次數(shù)大大減少，可惜移動次數(shù)并未減少， 所以排序效率仍為O(n2) 。 i =。◆ 插入排序（直接插入、折半插入，索引表插入、希爾插入排序）。ASL=∑ Pi. Ci，要求被查文件：采用順序存貯結(jié)構(gòu)、記錄按關(guān)鍵字遞增有序：① 查找過程與順序結(jié)構(gòu)有序表中的折半查找相似，查找效率高；② 中序遍歷此二叉樹，將會得到一個(gè)關(guān)鍵字的有序序列（即實(shí)現(xiàn)了排序運(yùn)算）；③ 如果查找不成功，能夠方便地將被查元素插入到二叉樹的葉子結(jié)點(diǎn)上，而且插入或刪除時(shí)只需修改指針而不需移動元素。◆ 查找的ASL◆ 二叉排序樹的形態(tài)取決于元素的輸入順序。如果在一棵AVL樹中插入一個(gè)新結(jié)點(diǎn)，就有可能造成失衡，此時(shí)必須重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)平衡。 //若t為空，則插入的結(jié)點(diǎn)s作為根結(jié)點(diǎn)K qdata: qL_child=s。② 二叉排序樹的插入與刪除思路：查找不成功，生成一個(gè)新結(jié)點(diǎn)s，插入到二叉排序樹中；查找成功則返回。 二、折半查找（二分或?qū)Ψ植檎遥? 若關(guān)鍵字不在表中，怎樣得知并及時(shí)停止查找？ 典型標(biāo)志是：當(dāng)查找范圍的上界≤下界時(shí)停止查找。 針對靜態(tài)查找表的查找算法主要有:順序查找、折半查找、分塊查找 一、順序查找（線性查找） 技巧：把待查關(guān)鍵字key存入表頭或表尾（俗稱“哨兵”），這樣可以加快執(zhí)行速度?！?從單源點(diǎn)到其他頂點(diǎn)，以及各個(gè)頂點(diǎn)間的最短路徑問題，掌握熟練手工模擬。 如果圖中任意一對頂點(diǎn)都是連通的, 則稱此圖是連通圖。Prime算法特點(diǎn): 將頂點(diǎn)歸并，與邊數(shù)無關(guān)，適于稠密網(wǎng)。圖常用的遍歷：一、深度優(yōu)先搜索；二、廣度優(yōu)先搜索 深度優(yōu)先搜索（遍歷）步驟：① 訪問起始點(diǎn) v。注：在有向圖的鄰接矩陣中， 第i行含義：以結(jié)點(diǎn)vi為尾的弧(即出度邊）； 第i列含義：以結(jié)點(diǎn)vi為頭的弧(即入度邊）。◆ 哈夫曼樹的定義、構(gòu)造及求哈夫曼編碼。(4) 重復(fù)(2) 和(3) , 直到 F 只含一棵樹為止。① 先序遍歷若森林為空，返回；訪問森林中第一棵樹的根結(jié)點(diǎn)；先根遍歷第一棵樹的根結(jié)點(diǎn)的子樹森林；先根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。優(yōu)點(diǎn)：①不浪費(fèi)空間；②插入、刪除方便 ◆ 二叉樹的遍歷。性質(zhì)2: 深度為k的二叉樹至多有2k1個(gè)結(jié)點(diǎn)（k0）。空串(Null String)是指長度為零的串；而空白串(Blank String),是指包含一個(gè)或多個(gè)空白字符‘ ’(空格鍵)的字符串.2. “空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串稱為S的真子串。 while ( i=S[0] amp。串有三種機(jī)內(nèi)表示方法：模式匹配算法第四章 串內(nèi)容提要 ？它有什么獨(dú)特用途？① 離散事件的模擬（模擬事件發(fā)生的先后順序,例如 CPU芯片中的指令譯碼隊(duì)列）；② 操作系統(tǒng)中的作業(yè)調(diào)度（一個(gè)CPU執(zhí)行多個(gè)作業(yè)）；③ 簡化程序設(shè)計(jì)。3） 出隊(duì)操作Status DeQueue ( SqQueue amp。 //置空隊(duì)列 return OK。2. 順序隊(duì)順序隊(duì)類型定義：define QUEUEMAXSIZE 100 //最大隊(duì)列長度 typedef struct { QElemType *base。 //指向下一結(jié)點(diǎn)的指針 }Qnode , * QueuePtr 。 順序棧入棧函數(shù)PUSH（）status Push(ElemType e) { if(topM){上溢} else s[top++]=e。}第3章 棧和隊(duì)列內(nèi)容提要： }void display( ) //字母線性表的顯示，即讀表操作{ int i。法1：用線性表表示： （( 1,2,12) ，(1,3,9)， (3,1,3)， (3,5,14)， (4,3,24)， (5,2,18) ，(6,1,15)， (6,4,7)）法2：用十字鏈表表示用途：方便稀疏矩陣的加減運(yùn)算方法：每個(gè)非0元素占用5個(gè)域法3：用三元組矩陣表示：稀疏矩陣壓縮存儲的缺點(diǎn)：將失去隨機(jī)存取功能代碼：（a，b，c，…，z），寫出在順序結(jié)構(gòu)上生成和顯示該表的C語言程序。◆ 順序表適宜于做查找這樣的靜態(tài)操作；◆ 鏈表宜于做插入、刪除這樣的動態(tài)操作。7. 鏈表的運(yùn)算效率分析：（1）查找 因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為 O(n)。◆ 數(shù)組（主要是二維）在以行序/列序?yàn)橹鞯拇鎯χ械牡刂酚?jì)算方法。設(shè)一般的二維數(shù)組是A[c1..d1, c2..d2]，則行優(yōu)先存儲時(shí)的地址公式為：二維數(shù)組列優(yōu)先存儲的通式為：◆ 稀疏矩陣（含特殊矩陣）的存儲及運(yùn)算。 pprior = s 。 }return p。 p=pnext。for( i=1。}node。（n+1）＝n/2≈O(n) 3) 刪除——?jiǎng)h除線性表的第i個(gè)位置上的元素 實(shí)現(xiàn)步驟： ①將第i+1 至第n 位的元素向前移動一個(gè)位置； ②表長減1。 核心語句: V[i]=x。時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性學(xué)習(xí)重點(diǎn)：◆ 數(shù)據(jù)結(jié)構(gòu)的“三要素”：邏輯結(jié)構(gòu)、物理（存儲）結(jié)構(gòu)及在這種結(jié)構(gòu)上所定義的操作（運(yùn)算） 。數(shù)據(jù)元素——是數(shù)據(jù)的基本單位，具有完整確定的實(shí)際意義。數(shù)據(jù)——所有能被計(jì)算機(jī)識別、存儲和處理的符號的集合。①正確性、②可讀性、③健壯性、④效率與低存儲量需求◆ 算法分析。數(shù)據(jù)結(jié)構(gòu)的基本運(yùn)算：修改、插入、刪除、查找、排序1) 修改——通過數(shù)組的下標(biāo)便可訪問某個(gè)特定元素并修改之。 插入時(shí)的平均移動次數(shù)為：n(n+1)/2247。 struct node *next。 //m=sizeof(node) 前面已求出p=head。 while (p) //當(dāng)指針不空時(shí)循環(huán)（僅限于無頭結(jié)點(diǎn)的情況） { printf(%c,pdata)。 j++。 sprior = p prior 。 在二維數(shù)組中，我們既可以規(guī)定按行存儲，也 可以規(guī)定按列存儲?！?掌握通過畫出結(jié)點(diǎn)圖來進(jìn)行鏈表（單鏈表、循環(huán)鏈表等）的生成、插入、刪除、遍歷等操作。(x)—— 計(jì)算變量x的長度（字節(jié)數(shù)）； malloc(m) — 開辟m字節(jié)長度的地址空間，并返回這段空間的首地址； free(p) —— 釋放指針p所指變量的存儲空間，即徹底刪除一個(gè)變量。缺點(diǎn)是存儲密度小，存儲空間利用率低。解：介紹3種存儲形式。 i++ ) V[i]=V[i1]+1。 display( )。 對于向上生成的堆棧: