【正文】 =2； 指針 hlink =3； 廣義表中所有表都帶有一個(gè)表頭結(jié)點(diǎn) 例： LS(5,(?x‘ ,‘y‘ ), ((?x‘)),2) utype ref/intinfo/charinfo/hlink tlink 類聲明定義： P111結(jié)點(diǎn)定義： class GenListNode { 數(shù)據(jù)成員 int utype。 GenListNode * tlink。 union { int ref。 引用計(jì)數(shù) , 當(dāng) utype=0 int intinfo。 當(dāng) utype=1 char charinfo。 當(dāng) utype=2 GenListNode * hlink。 當(dāng) utype=3 } value。 …… …… …… 例： 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。 while (temptlink !=NULL) temp=temptlink。 ① temptlink = elem1tlink。 ② elem1tlink=elem2。 ③ if (elem2utype ==0) elem2++。 ④ } …… …… elem1 elem2 ① temp ② ③ ▲ ④ 插入 遞歸算法 if (lst!=NULL) { q=new GenListNode( )。 //創(chuàng)建新結(jié)點(diǎn) q； qutype=lstutype。 //先拷標(biāo)志結(jié)點(diǎn) utype。 switch (lstutype) { //根據(jù) utype情況拷值域 value. case 0 : q=lst 。 break。 case 1 : q=lst 。 break。 case 2 : q=lst。 break。 case 3 : q=copy(lst)。 ① break。 } qtlink = Copy(lsttlink)。 ② //復(fù)制同下一結(jié)點(diǎn)； } P115 ( (a, b), ( (c, d), e )) 表 復(fù)制算法 q 求深度 P116 判斷兩個(gè)廣義表 s,t 是否相等（結(jié)構(gòu)，對(duì)應(yīng)成員值） P117 if 空表 相等 ,返回 1； if 兩個(gè)都是非空表且結(jié)點(diǎn)類型 (utype)相同 (兩個(gè)表對(duì)應(yīng)結(jié)點(diǎn) ) { 原子結(jié)點(diǎn) 值 : 類型 (utype)為 x=1 類型 (utype)為 2 x=1 子表 繼續(xù)分情況判斷（遞歸） 類型 (utype)為 3x=equal(s, t) 如果 x=1繼續(xù)比較同一層的下一個(gè)結(jié)點(diǎn)（遞歸） equal(stlink,ttlink) } return 0。 } utype intinfo/charinfo/hlink tlink int equal ( GenListNode *s, GenListNode *t ) { if (stlink)==NULL amp。amp。 ttlink==NULL) return 1。 if (stlink)!=NULL amp。amp。 ttlink!=NULL amp。amp。 stlinkutype= =ttlinkutype) { if (stlinkutype= = 1) if (stlink= =ttlink ) x=1。 else x=0。 else if (stlinkutype= = 2) if (stlink= =ttlink ) x=1。 else x=0。 else if (stlinkutype= = 3) x=equal(stlink, stlink) 。 if (x) return equal(stlink, ttlink)。 } return 0。 } …… …… S t S t 刪除 如果原子結(jié)點(diǎn)：值域中數(shù)據(jù)是 x刪除 , 繼續(xù)。 如果原子結(jié)點(diǎn)：值域中數(shù)據(jù)不是 x不刪除 如果子表結(jié)點(diǎn)：則從子表的表頭結(jié)點(diǎn)開始，繼續(xù)遞歸。 繼續(xù)同一層下一個(gè)結(jié)點(diǎn)。 void delvalue (GenListNode * ls, const value x) { if (lstlink!=NULL) { P=lstlink。 while (p!=NULL amp。amp。((putype= =1 amp。amp。 p= =x)|| (putype= =2 amp。amp。 p= =x)) { lstlink = ptlink。 delete p。 p=lstlink。} if (p!=NULL) { if ( putype= = 3) delvalue (p, x) 。 delvalue( p ,x)。 } } } …… l s P …… 從字符串 str1中摘取廣義表的第一個(gè)元素賦給 hstr1，剩下的元素賦給 str1. int Genlist :: sever(char * str1 , char * hstr1 ) { char ch=str1[0]。 int n=strlen (str1)。 ① int i=0, k=0。 while (in amp。amp。 (ch!=?,‘ || k!=0 )) { if (ch= = ?(? ) k++。 else (ch= =?)‘ ) k 。 i++。 ch=str1[i]。 } if (in) { strncpy (hstr1, str1,i1)。 strncpy (str1, str1+i , ni )。 return 1。 } else if (k!=0) return 0。 else { strcpy (hstr1,str1)。 str1=0。 return 1。 } } ? (2,(?b‘,7)), ( ), (?d‘) ‘ 建立鏈表 str1 ch=( 。 n=20 ① 第一次循環(huán)： k=1。 i=1。 ch=2 第二次循環(huán)： k=1。 i=2。 ch= ， 第三次循環(huán)： k=1。 i=3。 ch=( 第四次循環(huán)： k=2。 i=4。 ch= ‘ 第五次循環(huán)： k=2。 i=5。 ch=b …… …… 第九次循環(huán)： k=2。 i=9。 ch= ) 第十次循環(huán)： k=1。 i=10。 ch= ) 第十一次循環(huán)： k=0。 i=11。 ch= , 第十二次循環(huán)： hstr1=? (2,(?b‘,7)) ‘ 。 str1=?( ),(?d‘) ? ls= new GenListNode( ). lsutype = 0 。 ls =0。 if (strlen(s)= =0|| strcmp(s,‖( )‖)= =0 ) lstlink=NULL。 else { p=ls。 strncpy (sub , s+1, strlen (s) – 2)。① while ( strlen(sub)!=0 ) { p=ptlink= new GenListNode( )。 ② if ( sever(sub,hsub)) ③ { if (hsub[0] !=?(? amp。amp。 hsyb[0] !=?‘‘ ) { ④ putype=1。 p= atoi(hsub)。 } else if (hsub[0] !=?(? amp。amp。 hsub[0]= =?‘‘ ) { ⑤ putype=2。 p=hsub[1]。 } else { putype=3。 GreateList (p,hsub)。 } ⑥ } else return 0。 ⑦ } ptlink=NULL。 ⑧ }return 1。 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)) ‘ 。 sub=?( ),(?d‘) ? 3 ^ 掌握： ?遞歸的概念：什么是遞歸，種類，及遞歸求解方法 ?遞歸過程的機(jī)制與利用遞歸工作棧實(shí)現(xiàn)遞歸的方法 ?利用遞歸解決問題的分治法和回溯法 ?廣義表的定義及其實(shí)現(xiàn)方法 ?廣義表的遞歸算法 了解： ?迷宮問題的遞歸思路及利用棧實(shí)現(xiàn)的非遞歸解法 P121 P123： 52， 55， 56， 57 附加： 51， 53， 54， 58 習(xí)題 第六章 樹和二叉樹 熟練掌握 ： ? 二叉樹遍歷方法 ? 堆的定義，堆的建立，堆的插入與刪除、堆的向上和向下調(diào)整等算法以及用來實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的方法。 掌握： ? 二叉樹的概念，性質(zhì)及二叉樹的表示， ? 線索化二叉樹的特性及尋找某結(jié)點(diǎn)的前驅(qū)和后繼的方法 ? 樹與森林的實(shí)現(xiàn)，重點(diǎn)在用二叉樹的實(shí)現(xiàn) ? 森林與二叉樹的轉(zhuǎn)換；樹的遍歷算法 ? 二叉樹的計(jì)數(shù)方法及從二叉樹遍歷結(jié)果得到二叉樹的方法 ? 霍夫曼樹的實(shí)現(xiàn)方法、構(gòu)造霍夫曼編碼的方法及帶權(quán)路徑長度的計(jì)算 了解： ? 樹和森林定義和基本概念 二叉樹 二叉樹在樹結(jié)構(gòu)的應(yīng)用中起著非常重要的作用，因?yàn)閷?duì)二叉樹的許多操作算法簡單，而任何樹都可以與二叉樹相互轉(zhuǎn)換，這樣就解決了樹的存儲(chǔ)結(jié)構(gòu)及其運(yùn)算中存在的復(fù)雜性。 ?在二叉樹中在不存在度大于 2的結(jié)點(diǎn) ?而且有左右子樹之分 b c a (根結(jié)點(diǎn) ) (左子樹 ) ?由二叉樹的遞歸定義，二叉樹的三個(gè)基本組成單元是： 根結(jié)點(diǎn)、左子樹和右子樹 (右子樹 ) 二叉樹的定義 定義：二叉樹是由 n(n=0)個(gè)結(jié)點(diǎn)的有限集合構(gòu)成，此集合或者為空集，或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。 二叉樹結(jié)點(diǎn)的子樹要區(qū)分左子樹和右子樹，即使只有一棵子樹也要進(jìn)行區(qū)分，說明它是左子樹，還是右子樹。這是二叉樹與樹的最主要的差別。圖 5種