【文章內(nèi)容簡(jiǎn)介】 ，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”。解決假溢出的途徑———采用循環(huán)隊(duì)列。，若約定隊(duì)首指針指向隊(duì)首元素的前一個(gè)位置。那么，從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先 移動(dòng)隊(duì)首位置 ，后 取出元素。、棧、隊(duì)的異同點(diǎn)：相同點(diǎn)：邏輯結(jié)構(gòu)相同，都是線(xiàn)性的；都可以用順序存儲(chǔ)或鏈表存儲(chǔ)；棧和隊(duì)列是兩種特殊的線(xiàn)性表，即受限的線(xiàn)性表（只是對(duì)插入、刪除運(yùn)算加以限制）。不同點(diǎn)：① 運(yùn)算規(guī)則不同：線(xiàn)性表為隨機(jī)存??；而棧是只允許在一端進(jìn)行插入和刪除運(yùn)算，因而是后進(jìn)先出表LIFO；隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表FIFO。② 用途不同，線(xiàn)性表比較通用；堆棧用于函數(shù)調(diào)用、遞歸和簡(jiǎn)化設(shè)計(jì)等；隊(duì)列用于離散事件模擬、OS作業(yè)調(diào)度和簡(jiǎn)化設(shè)計(jì)等。第四章 串內(nèi)容提要：◆ 串是數(shù)據(jù)元素為字符的線(xiàn)性表，串的定義及操作。串即字符串，是由零個(gè)或多個(gè)字符組成的有限序列，是數(shù)據(jù)元素為單個(gè)字符的特殊線(xiàn)性表。串比較：int strcmp(char *s1,char *s2)。 求串長(zhǎng)：int strlen(char *s)。 串連接：char strcat(char *to,char *from) 子串T定位：char strchr(char *s,char *c)。 ◆ 串的存儲(chǔ)結(jié)構(gòu)，因串是數(shù)據(jù)元素為字符的線(xiàn)性表，所以存在“結(jié)點(diǎn)大小”的問(wèn)題。模式匹配算法串有三種機(jī)內(nèi)表示方法：模式匹配算法：算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位）定位問(wèn)題稱(chēng)為串的模式匹配，典型函數(shù)為Index(S,T,pos)BF算法的實(shí)現(xiàn)—即編寫(xiě)Index(S, T, pos)函數(shù)BF算法設(shè)計(jì)思想：將主串S的第pos個(gè)字符和模式T的第1個(gè)字符比較， 若相等，繼續(xù)逐個(gè)比較后續(xù)字符；若不等，從主串S的下一字符（pos+1）起，重新與T第一個(gè)字符比較。 直到主串S的一個(gè)連續(xù)子串字符序列與模式T相等。返回值為S中與T匹配的子序列第一個(gè)字符的序號(hào)，即匹配成功。否則，匹配失敗，返回值 0。Int Index_BP(SString S, SString T, int pos) { //返回子串T在主串S中第pos個(gè)字符之后的位置。若不存在，則函數(shù)值為0. // 其中，T非空，1≤pos≤StrLength(S) i=pos。 j=1。 while ( i=S[0] amp。amp。 j=T[0] ) //如果i,j二指針在正常長(zhǎng)度范圍， { if (S[i] = = T[j] ) {++i, ++j。 } //則繼續(xù)比較后續(xù)字符 else {i=ij+2。 j=1。} //若不相等，指針后退重新開(kāi)始匹配 } if(jT[0]) return iT[0]。 //T子串指針j正常到尾，說(shuō)明匹配成功， else return 0。 //否則屬于iS[0]情況，i先到尾就不正常} //Index_BP補(bǔ)充重點(diǎn)：？答：有區(qū)別?？沾?Null String)是指長(zhǎng)度為零的串；而空白串(Blank String),是指包含一個(gè)或多個(gè)空白字符‘ ’(空格鍵)的字符串.2. “空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串稱(chēng)為S的真子串?！?第6章 樹(shù)和二叉樹(shù)內(nèi)容提要：◆ 樹(shù)是復(fù)雜的非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，樹(shù)，二叉樹(shù)的遞歸定義，基本概念，術(shù)語(yǔ)。樹(shù)：由一個(gè)或多個(gè)(n≥0)結(jié)點(diǎn)組成的有限集合T，有且僅有一個(gè)結(jié)點(diǎn)稱(chēng)為根（root），當(dāng)n1時(shí)，其余的結(jié)點(diǎn)分為m(m≥0)個(gè)互不相交的有限集合T1,T2，…，Tm。每個(gè)集合本身又是棵樹(shù)，被稱(chēng)作這個(gè)根的子樹(shù) 。二叉樹(shù)：是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。術(shù)語(yǔ)：P88◆ 二叉樹(shù)的性質(zhì)，存儲(chǔ)結(jié)構(gòu)。性質(zhì)1: 在二叉樹(shù)的第i層上至多有2i1個(gè)結(jié)點(diǎn)（i0）。性質(zhì)2: 深度為k的二叉樹(shù)至多有2k1個(gè)結(jié)點(diǎn)（k0）。性質(zhì)3: 對(duì)于任何一棵二叉樹(shù)，若2度的結(jié)點(diǎn)數(shù)有n2個(gè)，則葉子數(shù)（n0）必定為n2＋1 性質(zhì)4: 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度必為 235。 性質(zhì)5: 對(duì)完全二叉樹(shù)，若從上至下、從左至右編號(hào)，則編號(hào)為i 的結(jié)點(diǎn)，其左孩子編號(hào)必為2i，其右孩子編號(hào)為2i＋1；其雙親的編號(hào)必為i/2（i＝1 時(shí)為根,除外）。 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)：一、順序存儲(chǔ)結(jié)構(gòu)按二叉樹(shù)的結(jié)點(diǎn)“自上而下、從左至右”編號(hào)，用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)。若是完全/滿(mǎn)二叉樹(shù)則可以做到唯一復(fù)原。不是完全二叉樹(shù)：一律轉(zhuǎn)為完全二叉樹(shù)！方法很簡(jiǎn)單，將各層空缺處統(tǒng)統(tǒng)補(bǔ)上“虛結(jié)點(diǎn)”，其內(nèi)容為空。缺點(diǎn)：①浪費(fèi)空間；②插入、刪除不便 二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用二叉鏈表即可方便表示。一般從根結(jié)點(diǎn)開(kāi)始存儲(chǔ)。優(yōu)點(diǎn)：①不浪費(fèi)空間；②插入、刪除方便 ◆ 二叉樹(shù)的遍歷。指按照某種次序訪(fǎng)問(wèn)二叉樹(shù)的所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)僅訪(fǎng)問(wèn)一次，得到一個(gè)線(xiàn)性序列。遍歷規(guī)則———二叉樹(shù)由根、左子樹(shù)、右子樹(shù)構(gòu)成，定義為D、 L、R若限定先左后右，則有三種實(shí)現(xiàn)方案： DLR LDR LRD先序遍歷 中序遍歷 后序遍歷 ◆ 樹(shù)的存儲(chǔ)結(jié)構(gòu)，樹(shù)、森林的遍歷及和二叉樹(shù)的相互轉(zhuǎn)換。 回顧2：二叉樹(shù)怎樣還原為樹(shù)？ 要點(diǎn)：逆操作，把所有右孩子變?yōu)樾值埽?討論1：森林如何轉(zhuǎn)為二叉樹(shù)？ 法一：① 各森林先各自轉(zhuǎn)為二叉樹(shù)；② 依次連到前一個(gè)二叉樹(shù)的右子樹(shù)上。 法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹(shù) 討論2：二叉樹(shù)如何還原為森林？ 要點(diǎn)：把最右邊的子樹(shù)變?yōu)樯郑溆嘤易訕?shù)變?yōu)樾值軜?shù)和森林的存儲(chǔ)方式：樹(shù)有三種常用存儲(chǔ)方式：①雙親表示法 ②孩子表示法 ③孩子—兄弟表示法問(wèn)：樹(shù)→二叉樹(shù)的“連線(xiàn)—抹線(xiàn)—旋轉(zhuǎn)” 如何由計(jì)算機(jī)自動(dòng)實(shí)現(xiàn)？答：用“左孩子右兄弟”表示法來(lái)存儲(chǔ)即可。存儲(chǔ)的過(guò)程就是樹(shù)轉(zhuǎn)換為二叉樹(shù)的過(guò)程！樹(shù)、森林的遍歷：① 先根遍歷：訪(fǎng)問(wèn)根結(jié)點(diǎn)；依次先根遍歷根結(jié)點(diǎn)的每棵子樹(shù)。② 后根遍歷：依次后根遍歷根結(jié)點(diǎn)的每棵子樹(shù)；訪(fǎng)問(wèn)根結(jié)點(diǎn)。討論：樹(shù)若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否一樣？1. 樹(shù)的先根遍歷與二叉樹(shù)的先序遍歷相同； 2. 樹(shù)的后根遍歷相當(dāng)于二叉樹(shù)的中序遍歷；3. 樹(shù)沒(méi)有中序遍歷，因?yàn)樽訕?shù)無(wú)左右之分。① 先序遍歷若森林為空，返回；訪(fǎng)問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；先根遍歷第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林；先根遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林。② 中序遍歷若森林為空，返回；中根遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林；訪(fǎng)問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)；中根遍歷除去第一棵樹(shù)之后剩余的樹(shù)構(gòu)成的森林?！?二叉樹(shù)的應(yīng)用：哈夫曼樹(shù)和哈夫曼編碼。Huffman樹(shù)：最優(yōu)二叉樹(shù)（帶權(quán)路徑長(zhǎng)度最短的樹(shù)）Huffman編碼：不等長(zhǎng)編碼。樹(shù)的帶權(quán)路徑長(zhǎng)度：（樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和）構(gòu)造Huffman樹(shù)的基本思想：權(quán)值大的結(jié)點(diǎn)用短路徑，權(quán)值小的結(jié)點(diǎn)用長(zhǎng)路徑。構(gòu)造Huffman樹(shù)的步驟（即Huffman算法）：(1) 由給定的 n 個(gè)權(quán)值{ w1, w2, …, wn }構(gòu)成n棵二叉樹(shù)的集合F = { T1, T2, …, Tn } （即森林） ，其中每棵二叉樹(shù) Ti 中只有一個(gè)帶權(quán)為 wi 的根結(jié)點(diǎn)，其左右子樹(shù)均空。(2) 在F 中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù) 做為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，且讓新二叉樹(shù)根結(jié)點(diǎn)的權(quán)值等于其左右子樹(shù)的根結(jié)點(diǎn)權(quán)值之和。(3) 在F 中刪去這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入 F中。(4) 重復(fù)(2) 和(3) , 直到 F 只含一棵樹(shù)為止。這棵樹(shù)便是Huffman樹(shù)。具體操作步驟：學(xué)習(xí)重點(diǎn)：（本章內(nèi)容是本課程的重點(diǎn)）◆ 二叉樹(shù)性質(zhì)及證明方法，并能把這種方法推廣到K叉樹(shù)?！?二叉樹(shù)遍歷，遍歷是基礎(chǔ)，由此導(dǎo)出許多實(shí)用的算法，如求二叉樹(shù)的高度、各結(jié)點(diǎn)的層次數(shù)、度為0、2的結(jié)點(diǎn)數(shù)?！?由二叉樹(shù)遍歷的前序和中序序列或后序和中序序列可以唯一構(gòu)造一棵二叉樹(shù)。由前序和后序序列不能唯一確定一棵二叉樹(shù)。 ◆ 完全二叉樹(shù)的性質(zhì)?！?樹(shù)、森林和二叉樹(shù)間的相互轉(zhuǎn)換?！?哈夫曼樹(shù)的定義、構(gòu)造及求哈夫曼編碼。補(bǔ)充：？答：滿(mǎn)二叉樹(shù)是葉子一個(gè)也不少的樹(shù)，而完全二叉樹(shù)雖然前k1層是滿(mǎn)的，但最底層卻允許在右邊缺少連續(xù)若干個(gè)結(jié)點(diǎn)。滿(mǎn)二叉樹(shù)是完全二叉樹(shù)的一個(gè)特例。2. Huffman樹(shù)有什么用？最小冗余編碼、信息高效傳輸?shù)?章 圖內(nèi)容提要：◆ 圖的定義，概念、術(shù)語(yǔ)及基本操作。 圖：記為 G＝( V, E ) 其中：V 是G 的頂點(diǎn)集合，是有窮非空集； E 是G 的邊集合，是有窮集。 術(shù)語(yǔ)：見(jiàn)課件◆ 圖的存儲(chǔ)結(jié)構(gòu)。(數(shù)組)表示法① 建立一個(gè)頂點(diǎn)