【正文】 圖 5種基本形。 二叉樹(shù)結(jié)點(diǎn)的子樹(shù)要區(qū)分左子樹(shù)和右子樹(shù)，即使只有一棵子樹(shù)也要進(jìn)行區(qū)分，說(shuō)明它是左子樹(shù)，還是右子樹(shù)。 掌握： ? 二叉樹(shù)的概念，性質(zhì)及二叉樹(shù)的表示， ? 線索化二叉樹(shù)的特性及尋找某結(jié)點(diǎn)的前驅(qū)和后繼的方法 ? 樹(shù)與森林的實(shí)現(xiàn)，重點(diǎn)在用二叉樹(shù)的實(shí)現(xiàn) ? 森林與二叉樹(shù)的轉(zhuǎn)換；樹(shù)的遍歷算法 ? 二叉樹(shù)的計(jì)數(shù)方法及從二叉樹(shù)遍歷結(jié)果得到二叉樹(shù)的方法 ? 霍夫曼樹(shù)的實(shí)現(xiàn)方法、構(gòu)造霍夫曼編碼的方法及帶權(quán)路徑長(zhǎng)度的計(jì)算 了解： ? 樹(shù)和森林定義和基本概念 二叉樹(shù) 二叉樹(shù)在樹(shù)結(jié)構(gòu)的應(yīng)用中起著非常重要的作用，因?yàn)閷?duì)二叉樹(shù)的許多操作算法簡(jiǎn)單，而任何樹(shù)都可以與二叉樹(shù)相互轉(zhuǎn)換，這樣就解決了樹(shù)的存儲(chǔ)結(jié)構(gòu)及其運(yùn)算中存在的復(fù)雜性。 s=?( (2,(?b‘,7)), ( ), (?d‘) )‘ ① sub=? (2,(?b‘,7)), ( ), (?d‘)‘ 0 0 ls 3 P ② P 0 0 ⑥ ls 1 2 ② P ③ hsub=? (2,(?b‘,7)) ‘ 。 ⑦ } ptlink=NULL。 GreateList (p,hsub)。 p=hsub[1]。amp。 p= atoi(hsub)。amp。① while ( strlen(sub)!=0 ) { p=ptlink= new GenListNode( )。 else { p=ls。 ls =0。 ch= , 第十二次循環(huán)： hstr1=? (2,(?b‘,7)) ‘ 。 ch= ) 第十一次循環(huán)： k=0。 ch= ) 第十次循環(huán)： k=1。 ch=b …… …… 第九次循環(huán)： k=2。 ch= ‘ 第五次循環(huán)： k=2。 ch=( 第四次循環(huán)： k=2。 ch= ， 第三次循環(huán)： k=1。 ch=2 第二次循環(huán)： k=1。 n=20 ① 第一次循環(huán)： k=1。 return 1。 else { strcpy (hstr1,str1)。 return 1。 } if (in) { strncpy (hstr1, str1,i1)。 i++。 (ch!=?,‘ || k!=0 )) { if (ch= = ?(? ) k++。 while (in amp。 int n=strlen (str1)。 delvalue( p ,x)。 p=lstlink。 p= =x)) { lstlink = ptlink。 p= =x)|| (putype= =2 amp。((putype= =1 amp。 while (p!=NULL amp。 繼續(xù)同一層下一個(gè)結(jié)點(diǎn)。 } …… …… S t S t 刪除 如果原子結(jié)點(diǎn)：值域中數(shù)據(jù)是 x刪除 , 繼續(xù)。 if (x) return equal(stlink, ttlink)。 else x=0。 else x=0。amp。amp。 ttlink==NULL) return 1。 } utype intinfo/charinfo/hlink tlink int equal ( GenListNode *s, GenListNode *t ) { if (stlink)==NULL amp。 } qtlink = Copy(lsttlink)。 case 3 : q=copy(lst)。 case 2 : q=lst。 case 1 : q=lst 。 switch (lstutype) { //根據(jù) utype情況拷值域 value. case 0 : q=lst 。 //創(chuàng)建新結(jié)點(diǎn) q； qutype=lstutype。 ③ if (elem2utype ==0) elem2++。 ① temptlink = elem1tlink。 …… …… …… 例： Lsutype Lstlink Ls / Ls / Ls / Ls A() B(6,2) C( ?a‘ , ( 5, 3, ?x‘)) D(B, C, A) (B, D) F( 4, F) void GenList::setNext ( GenListNode * elem1, GenListNode * elem2) { GenListNode *temp=elem2。 當(dāng) utype=2 GenListNode * hlink。 引用計(jì)數(shù) , 當(dāng) utype=0 int intinfo。 GenListNode * tlink。 其中第一個(gè)元素 a0為 表頭 ，其后組成的 表 (a1,a2,… ,an1)稱為 表尾 。 廣義表 是 n(n=0)個(gè)元素 a0 ， a1,a2,… ,an1的有限序列 , 記作 :LS=（ a0,a1,… ,an1) LS是廣義表的名字，其中 ai或者是原子項(xiàng)，或者是一個(gè) 子表 n為它的 長(zhǎng)度 (即元素個(gè)數(shù) )。 } 遞歸調(diào)用語(yǔ)句只有一個(gè)，而且是放在最后 ——尾遞歸 一般從遞歸過(guò)程改為非遞歸過(guò)程的方法是先根據(jù)遞歸算法 畫出程序流程圖，然后 建立循環(huán)結(jié)構(gòu) 。 f1=f2。 i++) { f2 =f1 +f0。 for (i=2。 ( ) long Fib(long n) { if (n=1) return n。 } 用棧求解 P100 101 (w)。 0、 8…… long Fib(long n) { if (n=1) return n。 對(duì)于一個(gè)較為復(fù)雜的問(wèn)題，如果能夠分解成幾個(gè)相對(duì)簡(jiǎn)單的 且解法相同或類似的子問(wèn)題來(lái)求解 ——分治法 遞歸和遞歸工作棧 P98 在遞歸調(diào)用時(shí)，必須做好參數(shù)保存，參數(shù)傳遞工作 —— 利用遞歸工作棧來(lái)處理。 else return n*Factorial(n1)。 //往前移 count — —。 j count。 count++。 //后移一位 j — —。amp。 （可理解為從大到小排列的順序隊(duì)列） 順序存儲(chǔ) 入隊(duì)： j=count1。 delete p。 rear front 出隊(duì)： p=front。 rear link=p。 隊(duì)滿： (rear+1) % maxSize=front。 elements[rear]=item 出隊(duì)： front=(front+1)%MaxSize。 隊(duì)空： rear=front。 elements[rear]=item 出隊(duì)： front+1。 隊(duì)中元素按 a1， a2， a3， … an的次序入隊(duì)，出隊(duì)按 先進(jìn)先出 的原則進(jìn)行的 ,因此 a1， a2， a3， … an的次序出隊(duì)。 FIFO front 和 rear的初始值地隊(duì)列初始化時(shí)均應(yīng)置為 1。它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。 Delete p Push 進(jìn)棧 P=new StackNodeType(item,top) p Top=p。 鏈?zhǔn)綏５念惗x： 數(shù)據(jù)成員： StackNodeType * top。 top …… top X ① X …… maxSize 鏈?zhǔn)綏?——（鏈?zhǔn)?存儲(chǔ) ） 用單鏈表表示棧時(shí)棧頂指針指向單鏈表的表頭， 初始時(shí)為 NULL 結(jié)點(diǎn)類定義： Type data。 top 。 ① elements[top]=x。 成員函數(shù)： GetTop( ) ——取棧頂元素 IsEmpty( )——判斷?？?(top==1) IsFull( ) —— 判斷棧滿 (top==maxSize1） MakeEmpty( )—— 清空棧 √ void Push( ) —— 元素進(jìn)棧 (判斷棧滿 ) √ int Pop( ) —— 元素出棧 (判斷?？?) 順序棧 ——（數(shù)組存儲(chǔ)） assert (!IsFull() )。 Type *elements。 棧中元素按 a1， a2， a3， … an的次序進(jìn)棧，退棧按后進(jìn)先出的原則進(jìn)行的 ,因此 an …… a3 a2 a1的次序出棧。 棧 LIFO 進(jìn)棧： top+1。 current current X p ① ② ③ ④ X X 刪除第 1個(gè)結(jié)點(diǎn)？ ——不用分情況 習(xí)題 P68： 3 3 36 習(xí)題： P41 習(xí)題： 23 、 2 2 214 返回 退出 第四章 棧與隊(duì)列 熟練掌握 ： ? 棧的定義、特性 ? 棧的抽象數(shù)據(jù)類型、順序表示、鏈表表示及相應(yīng)操作 （特別注意?？蘸蜅M的條件） ? 隊(duì)列的定義、特性 ? 隊(duì)列的抽象數(shù)據(jù)類型、順序表示、鏈表表示及相應(yīng)操作 （特別是循環(huán)隊(duì)列中隊(duì)頭與隊(duì)尾指針的變化情況） 掌握 ： ? 優(yōu)先隊(duì)列的定義、特性 ? 優(yōu)先隊(duì)列的的抽象數(shù)據(jù)類型 ? 優(yōu)先隊(duì)列的插入與刪除算法 了解：在表達(dá)式計(jì)算時(shí)棧的使用， 主要 是中綴表示改為后綴表示的方法思路 棧的定義及基本運(yùn)算 棧 (Stack)是限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表， 通常稱插入、刪除的這一端為 棧頂 (Top)， 另一端為 棧底 (Bottom)。 ③ p →lLink →rLink=current。 ① current=current →rL ink。 ④ current=p。② current →rL ink=p。 q=current →rL ink。 //重置 h } 雙向鏈表 P61 ?結(jié)點(diǎn)定義： lLink data rLink 指向前驅(qū)結(jié)點(diǎn) 數(shù)據(jù) 指向后繼結(jié)點(diǎn) /// …… first ?雙向鏈表 a0 a1 an 雙向鏈表 搜索 、 插入與刪除 算法 ?搜索 算法 P63 ?插入 算法 （ 插在當(dāng)前結(jié)點(diǎn)之后） 原表為空： current=new DblNodeType (value, first, first)。 //插入 head鏈前端 } h = head→ link。 //摘下 h鏈頭結(jié)點(diǎn) p→ link = head→ link。 while (h != NULL ) { p = h。 //指針前移 } h→ link = pr。 h = p。 while ( p != NULL ) { h→ link = pr。 【 解答 1】 templateclass Type void ListType :: Inverse ( ) { if ( h == NULL ) return。試設(shè)計(jì)一個(gè)算法，通過(guò)遍歷一趟鏈表，將鏈表中所有結(jié)點(diǎn)