【正文】 ）8. 順序存儲和鏈?zhǔn)酱鎯Φ膮^(qū)別和優(yōu)缺點(diǎn)？ 順序存儲時(shí)，邏輯上相鄰的數(shù)據(jù)元素，其物理存放地址也相鄰?！　℃?zhǔn)酱鎯r(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。缺點(diǎn)是存儲密度小，存儲空間利用率低。◆ 若線性表的長度變化不大，且其主要操作是查找，則采用順序表；◆ 若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。因?yàn)椤?數(shù)組中各元素具有統(tǒng)一的類型；② 數(shù)組元素的下標(biāo)一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。10. 三元素組表中的每個(gè)結(jié)點(diǎn)對應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的 行下標(biāo) 、列下標(biāo) 和 元素值 。解：介紹3種存儲形式。char V[30]。 V[0]=39。 for( i=1。 i++ ) V[i]=V[i1]+1。 for( i=0。 i++ ) printf( %c, v[i] )。}void main(void) //主函數(shù)，字母線性表的生成和輸出{ n=26。 display( )?！?從數(shù)據(jù)結(jié)構(gòu)角度來講，棧和隊(duì)列也是線性表，其操作是線性表操作的子集，屬操作受限的線性表?！?棧的定義及操作。 插入元素到棧頂?shù)牟僮鳎Q為入棧。 對于向上生成的堆棧: 入棧口訣：堆棧指針top “先壓后加” : S[top++]=an+1 出?？谠E：堆棧指針top “先減后彈” : e=S[top]◆ 棧的順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)，及在這兩種結(jié)構(gòu)下實(shí)現(xiàn)棧的操作。}順序棧出棧函數(shù)POP()status Pop( ){ if(top=L) { 下溢 }else { e=s[top]。} }◆ 隊(duì)列的定義及操作，隊(duì)列的刪除在一端（隊(duì)尾），而插入則在隊(duì)列的另一端（隊(duì)頭）。隊(duì)列：只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。 //元素 Struct QNode *next。鏈隊(duì)列類型定義： typedef struct { QueuePtr front 。 //隊(duì)尾指針 } LinkQueue。除非內(nèi)存不足?、? 入隊(duì)（尾部插入）：rearnext=S。 出隊(duì)（頭部刪除）：frontnext=pnext。 //隊(duì)列的基址 int front。 //隊(duì)尾指針 }SqQueue建隊(duì)核心語句：q . base=(QElemType *)malloc(sizeof (QElemType ）* QUEUE_MAXSIZE。q ) //初始化空循環(huán)隊(duì)列 q{ q . base=(QElemType *)malloc(sizeof(QElemType）* QUEUE_MAXSIZE)。//內(nèi)存分配失敗，退出程序 ==0。 } //InitQueue。q, QElemType e){//向循環(huán)隊(duì)列 q 的隊(duì)尾加入一個(gè)元素 e if ( (+1) % QUEUE_MAXSIZE = = ) return ERROR 。 [ ] = e。 }// EnQueue。q, QElemType amp。//隊(duì)列空 =(+1) % QUEUE_MAXSIZE 。 return OK。補(bǔ)充重點(diǎn)：1. 為什么要設(shè)計(jì)堆棧？它有什么獨(dú)特用途？① 調(diào)用函數(shù)或子程序非它莫屬；② 遞歸運(yùn)算的有力工具；③ 用于保護(hù)現(xiàn)場和恢復(fù)現(xiàn)場；④ 簡化了程序設(shè)計(jì)的問題。3. 什么叫“假溢出” ？如何解決？答：在順序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”。，若約定隊(duì)首指針指向隊(duì)首元素的前一個(gè)位置。、棧、隊(duì)的異同點(diǎn)：相同點(diǎn)：邏輯結(jié)構(gòu)相同，都是線性的；都可以用順序存儲或鏈表存儲；棧和隊(duì)列是兩種特殊的線性表，即受限的線性表（只是對插入、刪除運(yùn)算加以限制）。② 用途不同，線性表比較通用；堆棧用于函數(shù)調(diào)用、遞歸和簡化設(shè)計(jì)等；隊(duì)列用于離散事件模擬、OS作業(yè)調(diào)度和簡化設(shè)計(jì)等。：◆ 串是數(shù)據(jù)元素為字符的線性表，串的定義及操作。串比較：int strcmp(char *s1,char *s2)。 串連接：char strcat(char *to,char *from) 子串T定位：char strchr(char *s,char *c)。模式匹配算法：算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位）定位問題稱為串的模式匹配，典型函數(shù)為Index(S,T,pos)BF算法的實(shí)現(xiàn)—即編寫Index(S, T, pos)函數(shù)BF算法設(shè)計(jì)思想：將主串S的第pos個(gè)字符和模式T的第1個(gè)字符比較， 若相等，繼續(xù)逐個(gè)比較后續(xù)字符；若不等，從主串S的下一字符（pos+1）起，重新與T第一個(gè)字符比較。返回值為S中與T匹配的子序列第一個(gè)字符的序號，即匹配成功。Int Index_BP(SString S, SString T, int pos) { //返回子串T在主串S中第pos個(gè)字符之后的位置。 j=1。amp。 } //則繼續(xù)比較后續(xù)字符 else {i=ij+2。} //若不相等，指針后退重新開始匹配 } if(jT[0]) return iT[0]。 //否則屬于iS[0]情況，i先到尾就不正常} //Index_BP補(bǔ)充重點(diǎn)：？答：有區(qū)別。” 第6章 樹和二叉樹內(nèi)容提要：樹：由一個(gè)或多個(gè)(n≥0)結(jié)點(diǎn)組成的有限集合T，有且僅有一個(gè)結(jié)點(diǎn)稱為根（root），當(dāng)n1時(shí)，其余的結(jié)點(diǎn)分為m(m≥0)個(gè)互不相交的有限集合T1,T2，…，Tm。二叉樹：是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。性質(zhì)1: 在二叉樹的第i層上至多有2i1個(gè)結(jié)點(diǎn)（i0）。性質(zhì)3: 對于任何一棵二叉樹，若2度的結(jié)點(diǎn)數(shù)有n2個(gè)，則葉子數(shù)（n0）必定為n2＋1 性質(zhì)4: 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度必為 235。 二叉樹的存儲結(jié)構(gòu)：一、順序存儲結(jié)構(gòu)按二叉樹的結(jié)點(diǎn)“自上而下、從左至右”編號，用一組連續(xù)的存儲單元存儲。不是完全二叉樹：一律轉(zhuǎn)為完全二叉樹！方法很簡單，將各層空缺處統(tǒng)統(tǒng)補(bǔ)上“虛結(jié)點(diǎn)”，其內(nèi)容為空。一般從根結(jié)點(diǎn)開始存儲。指按照某種次序訪問二叉樹的所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)僅訪問一次，得到一個(gè)線性序列。 回顧2：二叉樹怎樣還原為樹？ 要點(diǎn)：逆操作，把所有右孩子變?yōu)樾值埽?討論1：森林如何轉(zhuǎn)為二叉樹？ 法一：① 各森林先各自轉(zhuǎn)為二叉樹；② 依次連到前一個(gè)二叉樹的右子樹上。存儲的過程就是樹轉(zhuǎn)換為二叉樹的過程！樹、森林的遍歷：① 先根遍歷：訪問根結(jié)點(diǎn)；依次先根遍歷根結(jié)點(diǎn)的每棵子樹。討論：樹若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否一樣？1. 樹的先根遍歷與二叉樹的先序遍歷相同； 2. 樹的后根遍歷相當(dāng)于二叉樹的中序遍歷；3. 樹沒有中序遍歷，因?yàn)樽訕錈o左右之分。② 中序遍歷若森林為空，返回；中根遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林；訪問第一棵樹的根結(jié)點(diǎn)；中根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。Huffman樹：最優(yōu)二叉樹（帶權(quán)路徑長度最短的樹）Huffman編碼：不等長編碼。構(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)，其左右子樹均空。(3) 在F 中刪去這兩棵樹，同時(shí)將新得到的二叉樹加入 F中。這棵樹便是Huffman樹?！?二叉樹遍歷，遍歷是基礎(chǔ)，由此導(dǎo)出許多實(shí)用的算法，如求二叉樹的高度、各結(jié)點(diǎn)的層次數(shù)、度為0、2的結(jié)點(diǎn)數(shù)。由前序和后序序列不能唯一確定一棵二叉樹?！?樹、森林和二叉樹間的相互轉(zhuǎn)換。補(bǔ)充：？答：滿二叉樹是葉子一個(gè)也不少的樹，而完全二叉樹雖然前k1層是滿的，但最底層卻允許在右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)。2. Huffman樹有什么用？最小冗余編碼、信息高效傳輸?shù)?章 圖內(nèi)容提要： 圖：記為 G＝( V, E ) 其中：V 是G 的頂點(diǎn)集合，是有窮非空集； E 是G 的邊集合，是有窮集。(數(shù)組)表示法① 建立一個(gè)頂點(diǎn)表和一個(gè)鄰接矩陣② 設(shè)圖 A = (V, E) 有 n 個(gè)頂點(diǎn)，則圖的鄰接矩陣是一個(gè)二維數(shù)組 [n][n]。鄰接矩陣法優(yōu)點(diǎn)：容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否