【正文】 ◆ 在“最好”和“最差”情況下，排序性能的分析，是否是穩(wěn)定排序的結(jié)論，時(shí)間效率和空間效率。2. 怎樣建堆？步驟：從最后一個(gè)非終端結(jié)點(diǎn)開始往前逐步調(diào)整，讓每個(gè)雙親大于（或小于）子女，直到根結(jié)點(diǎn)為止。 首先對(duì) n 個(gè)記錄的關(guān)鍵字進(jìn)行兩兩比較，得到 233?！紫龋趎個(gè)記錄中選擇最小者放到r[1]位置；然后，從剩余的n1個(gè)記錄中選擇最小者放到r[2]位置；…如此進(jìn)行下去，直到全部有序?yàn)橹埂?yōu)點(diǎn)：每趟結(jié)束時(shí)，不僅能擠出一個(gè)最大值到最后面位置，還能同時(shí)部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結(jié)束排序。② 空間效率肯定低，因?yàn)樵鲩_了指針分量（但在運(yùn)算過程中沒有用到更多的輔助單元）。 } //只要子表元素比哨兵大就不斷后移[j+1]= [0]。 其他情況下也要考慮移動(dòng)元素的次數(shù)。內(nèi)部排序內(nèi)容提要：◆ 排序的定義，排序可以看作是線性表的一種操作 排序:將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。 ？查找方法取決于表中數(shù)據(jù)的排列方式。本章列舉了三種方法（靜態(tài)查找表，動(dòng)態(tài)查找表）實(shí)現(xiàn)查找表的運(yùn)算。法2：直接令*s代替*p // *s為*p左子樹最右下方的結(jié)點(diǎn)二叉排序樹的④ 平衡二叉樹的定義：又稱AVL樹，即它或者是一顆空樹，或者是它的左子樹和右子樹都是平衡二叉樹，且左子樹與右子樹的深度之差的絕對(duì)值不超過1。 s L_child=NULL。特點(diǎn)：表結(jié)構(gòu)在查找過程中動(dòng)態(tài)生成。 return i。是元素間約束力最差的數(shù)據(jù)結(jié)構(gòu)：元素間的關(guān)系是元素僅共在同一個(gè)集合中。這兩種存儲(chǔ)結(jié)構(gòu)對(duì)有向圖和無向圖均適用◆ 圖的遍歷是圖的各種算法的基礎(chǔ)，應(yīng)熟練掌握?qǐng)D的深度、廣度優(yōu)先遍歷。學(xué)習(xí)重點(diǎn)： 圖是應(yīng)用最廣泛的一種數(shù)據(jù)結(jié)構(gòu)，本章也是這門課程的重點(diǎn)。U，v0206。鄰接表的優(yōu)點(diǎn)：空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；鄰接表的缺點(diǎn)：判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對(duì)應(yīng)的單鏈表，沒有鄰接矩陣方便。 圖：記為 G＝( V, E ) 其中：V 是G 的頂點(diǎn)集合，是有窮非空集； E 是G 的邊集合，是有窮集。由前序和后序序列不能唯一確定一棵二叉樹。構(gòu)造Huffman樹的步驟（即Huffman算法）：(1) 由給定的 n 個(gè)權(quán)值{ w1, w2, …, wn }構(gòu)成n棵二叉樹的集合F = { T1, T2, …, Tn } （即森林） ，其中每棵二叉樹 Ti 中只有一個(gè)帶權(quán)為 wi 的根結(jié)點(diǎn)，其左右子樹均空。存儲(chǔ)的過程就是樹轉(zhuǎn)換為二叉樹的過程！樹、森林的遍歷：① 先根遍歷：訪問根結(jié)點(diǎn)；依次先根遍歷根結(jié)點(diǎn)的每棵子樹。不是完全二叉樹：一律轉(zhuǎn)為完全二叉樹！方法很簡單，將各層空缺處統(tǒng)統(tǒng)補(bǔ)上“虛結(jié)點(diǎn)”，其內(nèi)容為空。二叉樹：是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。} //若不相等，指針后退重新開始匹配 } if(jT[0]) return iT[0]。Int Index_BP(SString S, SString T, int pos) { //返回子串T在主串S中第pos個(gè)字符之后的位置。 串連接：char strcat(char *to,char *from) 子串T定位：char strchr(char *s,char *c)。、棧、隊(duì)的異同點(diǎn)：相同點(diǎn)：邏輯結(jié)構(gòu)相同，都是線性的；都可以用順序存儲(chǔ)或鏈表存儲(chǔ)；棧和隊(duì)列是兩種特殊的線性表，即受限的線性表（只是對(duì)插入、刪除運(yùn)算加以限制）。 return OK。 [ ] = e。q ) //初始化空循環(huán)隊(duì)列 q{ q . base=(QElemType *)malloc(sizeof(QElemType）* QUEUE_MAXSIZE)。除非內(nèi)存不足！③ 入隊(duì)（尾部插入）：rearnext=S。隊(duì)列：只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。 插入元素到棧頂?shù)牟僮鳎Q為入棧。}void main(void) //主函數(shù)，字母線性表的生成和輸出{ n=26。 for( i=1。10. 三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的 行下標(biāo) 、列下標(biāo) 和 元素值 。　　鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。4. 如何表示空表？（1）無頭結(jié)點(diǎn)時(shí)，當(dāng)頭指針的值為空時(shí)表示空表；（2）有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表示空表?！?鏈表操作中應(yīng)注意不要使鏈意外“斷開”。 ◆ 數(shù)組的邏輯結(jié)構(gòu)定義及存儲(chǔ)數(shù)組： 由一組名字相同、下標(biāo)不同的變量構(gòu)成N維數(shù)組的特點(diǎn)：n個(gè)下標(biāo)，每個(gè)元素受到n個(gè)關(guān)系約束一個(gè)n維數(shù)組可以看成是由若干個(gè)n－1維數(shù)組組成的線性表。 ppriornext = s 。amp。 //最后一個(gè)元素要單獨(dú)處理pnext=NULL 。要一個(gè)個(gè)慢慢鏈入{ int i。 順序表刪除一元素的時(shí)間效率為:T（n)=(n1)/2 ≈O(n) 順序表插入、刪除算法的平均空間復(fù)雜度為O(1)單鏈表：（1）用單鏈表結(jié)構(gòu)來存放26個(gè)英文字母組成的線性表（a，b，c，…，z）,請(qǐng)寫出C語言程序。 a[ i ]=x。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu): 其結(jié)點(diǎn)在存儲(chǔ)器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。算法——是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，是一系列輸入轉(zhuǎn)換為輸出的計(jì)算步驟。針對(duì)非數(shù)值計(jì)算的程序設(shè)計(jì)問題，研究計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作。數(shù)據(jù)結(jié)構(gòu)——是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，表示為： Data_Structure=（D, R）數(shù)據(jù)類型——是一個(gè)值的集合和定義在該值上的一組操作的總稱。第2章 線性表內(nèi)容提要：◆ 線性表的邏輯結(jié)構(gòu)定義，對(duì)線性表定義的操作。 注意：事先應(yīng)判斷: 插入位置i 是否合法?表是否已滿? 應(yīng)當(dāng)符合條件： 1≤i≤n+1 或 i=[1, n+1] 核心語句：for (j=n。 j=n。 //一般需要3個(gè)指針變量int n 。 i++) //因尾結(jié)點(diǎn)要特殊處理，故i≠26{ pdata=i+‘a(chǎn)’1。 Linklist *p。Step 2：pnext=s ；6. 單鏈表的刪除刪除動(dòng)作的核心語句（要借助輔助指針變量q）：q = pnext。 p priornext = pnext ?！?線性表的邏輯結(jié)構(gòu)，指線性表的數(shù)據(jù)元素間存在著線性關(guān)系?！?稀疏矩陣的十字鏈表存儲(chǔ)方法。但是，如果要在單鏈表中進(jìn)行前插或刪除操作，因?yàn)橐獜念^查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度將是 O(n)。9. 判斷：“數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)要簡單”，對(duì)嗎？答：對(duì)的。void build() //字母線性表的生成，即建表操作{ int i。 i=n1。但從數(shù)據(jù)類型的角度看，它們是和線性表大不相同的重要抽象數(shù)據(jù)類型。 return(e)。 //隊(duì)首指針 QueuePtr rear 。 //隊(duì)首指針 int rear。2） 入隊(duì)操作Status EnQueue(SqQueue amp。e) {//若隊(duì)列不空，刪除循環(huán)隊(duì)列q的隊(duì)頭元素， //由 e 返回其值，并返回OK if ( = = ) return ERROR。解決假溢出的途徑———采用循環(huán)隊(duì)列。串即字符串，是由零個(gè)或多個(gè)字符組成的有限序列，是數(shù)據(jù)元素為單個(gè)字符的特殊線性表。 直到主串S的一個(gè)連續(xù)子串字符序列與模式T相等。 j=T[0] ) //如果i,j二指針在正常長度范圍， { if (S[i] = = T[j] ) {++i, ++j?！?樹是復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，樹，二叉樹的遞歸定義，基本概念，術(shù)語。 性質(zhì)5: 對(duì)完全二叉樹，若從上至下、從左至右編號(hào)，則編號(hào)為i 的結(jié)點(diǎn)，其左孩子編號(hào)必為2i，其右孩子編號(hào)為2i＋1；其雙親的編號(hào)必為i/2（i＝1 時(shí)為根,除外）。遍歷規(guī)則———二叉樹由根、左子樹、右子樹構(gòu)成，定義為D、 L、R若限定先左后右，則有三種實(shí)現(xiàn)方案： DLR LDR LRD先序遍歷 中序遍歷 后序遍歷 ◆ 樹的存儲(chǔ)結(jié)構(gòu)，樹、森林的遍歷及和二叉樹的相互轉(zhuǎn)換?！?二叉樹的應(yīng)用：哈夫曼樹和哈夫曼編碼。具體操作步驟：學(xué)習(xí)重點(diǎn)：（本章內(nèi)容是本課程的重點(diǎn)）◆ 二叉樹性質(zhì)及證明方法，并能把這種方法推廣到K叉樹。滿二叉樹是完全二叉樹的一個(gè)特例。鄰接矩陣法缺點(diǎn)：n個(gè)頂點(diǎn)需要n*n個(gè)單元存儲(chǔ)邊(弧)?；舅枷耄骸聵涞南刃虮闅v過程。兩種常見的最短路徑問題：一、 單源最短路徑—用Dijkstra（迪杰斯特拉）算法