【文章內(nèi)容簡(jiǎn)介】 eger。 {本算法求串t在串s中的第一次出現(xiàn)。 結(jié)果是：若t在s中 ，則給出串t的第一個(gè)字符在串s中的位置，若不存在，則返回0} j:=1。m:=length(s)。 n:=length(t)。 eq:=true。 WHILE (j=mn+1) AND eq DO IF equal(substr(s,j,n),t) THEN eq:=false ELSE j:=j+1；IF j=m+n1 THEN index:=j ELSE index:=0ENDF；{index} 【討論】 本題是用給定的基本操作，編寫其它操作的算法。這種類型題較多，必須嚴(yán)格按題的要求來做，不準(zhǔn)選擇具體存儲(chǔ)結(jié)構(gòu)。否則，即使全對(duì)，也很難得分。 2 2 設(shè)目標(biāo)為 t=’abcaabbabcabaacbacba’,模式串 p=’abcabaa’。(1)計(jì)算P的NEXTVAL函數(shù)值；(2)不寫出算法，只畫出利用KMP算法進(jìn)行模式匹配時(shí)每一趟的匹配過程；【解答】 （1）P的 NEXTVAL 函數(shù)值如下；j 1 2 3 4 5 6 7 _______________________________模式p a b c a b a anextval(j) 0 1 1 0 1 0 2 (2)a b c a a b b a b c a b a a c b a c b a a b c a b 第一趟匹配a b c 第二趟匹配a 第三趟匹配a b c a b a a 第四趟匹配成功【討論】 為寫NEXTVAL方便，可先寫出NEXT函數(shù)值，在由此求NEXTVAL.字符串s 滿足下式，其中HEAD 和 TAIL的定義同廣義表類似，如HEAD(‘XYZ’)=’X’,TAIL(‘XYZ’)=’YZ’,則S=concat(head(tail(s)),head(tail(tail(s))))=’dc’求字符串s?？晒┻x擇的答案是（A） abcd (B) acbd (C) acdb (D) adcb 正確答案是（D）。 第五章 數(shù)組和廣義表一、 內(nèi)容提要1， 1， 數(shù)組的邏輯結(jié)構(gòu)定義及存儲(chǔ)，2， 2， 稀疏矩陣（含特殊矩陣）的存儲(chǔ)及運(yùn)算。3， 3， 廣義表的定以及存儲(chǔ)。4， 4， 廣義表運(yùn)算的遞歸算法。二、學(xué)習(xí)重點(diǎn)1， 1， 數(shù)組（主要是二維）在以行序?yàn)橹鞯拇鎯?chǔ)中的地址計(jì)算方法。2， 2， 特殊矩陣在壓縮存儲(chǔ)時(shí)的下標(biāo)變換。3， 3， 稀疏矩陣的三元組表存儲(chǔ)結(jié)構(gòu)及矩陣移植的算法。4， 4， 稀疏矩陣的十字鏈表存儲(chǔ)方法及十字鏈表生成算法。5， 5， 廣義表的HEAD和TAIL 運(yùn)算。6， 6， 給定廣義表畫出其存儲(chǔ)結(jié)構(gòu)。7， 7， 從廣義表的遞歸算法，掌握如何編寫遞歸算法。三、例題解析字符串二維數(shù)組A[0..8,1..10] ，每個(gè)元素由6個(gè)字符組成，每個(gè)字符占一個(gè)存儲(chǔ)單元，則（1）存放A需要多少個(gè)字節(jié)？（2）A的第8列和第5行共占多少字節(jié)？(3) 按行序存儲(chǔ)時(shí)，A[8,5]和按列存儲(chǔ)時(shí)哪個(gè)元素時(shí)的地址相同？【解答】 （1） 540 （2） 108 （3） A[3,10]編寫算法，將自然數(shù)1n2按蛇形填入n x n矩陣中。 例如，（1—42）如右圖所示。 【分析】本題要求在N的方陣中填人N2個(gè)數(shù)，關(guān)鍵是控制下標(biāo)。設(shè)坐標(biāo)原點(diǎn)在矩陣的左上角，且i是向下增長(zhǎng)，j向右增長(zhǎng) 。原點(diǎn)的坐標(biāo)為（1，1）。 【算法】 PROC sqrmgc(VAR a:arr。n:integer)。 { 本算法將自然數(shù)1n2 按蛇形填入N X N 矩陣中,a是二維數(shù)組}i:=1。 j:=1。 k:=1。 WHILE (i=n) AND (j=n) DO [ WHILE (i=n) AND (j0) DO [ a[i,j]:=k。 i:=i+1。 j:=j1。 k:=k+1 ] IF j1 THEN IF i=n THEN j:=1 ELSE [j:=j+2。i:=n ] ELSE [i:=n。 j:=j+2] WHILE (i0) AND (j=N) DO [ a[i,j]:=k。 i:=i1。 j:=j+1。 k:=k+1 ] IF i1 THEN IF j=n THEN i:=1 ELSE [i:=i+2。j:=n ] ELSE [j:=n。 i:=i+2 ] ]ENDP。 {sqrmgc}求下列廣義表操作結(jié)果：(1) (1) HEAD(TAIL(HEAD(((a,b),(c,d))))(2) (2) TAIL(HEAD(TAIL(((a,b),(c,d))))【解答】 （1）b (2) (d)4 、利用廣義表的HEAD和TAIL操作，寫出如上題的表達(dá)式，把原子banana從下列廣義表中分離出來。（1） （1） L1=（apple,(pear),((banana)),(((orange)))）。（2） （2） L2=(apple,(pear,(banana),orange))?！窘獯稹?1) HEAD(HEAD(HEAD(TAIL(TAIL(L1))))) (2) HEAD(HEAD(TAIL(HEAD(TAIL(L1))))) 第六章 樹和二叉樹一 、內(nèi)容提要樹是復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，樹，二叉樹的遞歸定義，基本概念，術(shù)語。二叉樹的性質(zhì)，存儲(chǔ)結(jié)構(gòu)。二叉樹的遍歷算法（遞歸，非遞歸）。線索二叉樹樹的存儲(chǔ)結(jié)構(gòu)，樹、森林的遍歷及和二叉樹的相互轉(zhuǎn)換。二叉樹的應(yīng)用：表達(dá)式求值、判定問題及哈夫曼樹和哈夫曼編碼。二、學(xué)習(xí)重點(diǎn)（本章內(nèi)容是本課程的重點(diǎn)）二叉樹性質(zhì)及證明方法，并能把這種方法推廣到K叉樹。二叉樹遍歷的遞歸算法，本書中介紹了三種（先、中、后序）方法，另三種也應(yīng)會(huì)用。前序和中序的非遞歸遍歷。遍歷是基礎(chǔ)，由此導(dǎo)出許多實(shí)用的算法，如求二叉樹的高度、各結(jié)點(diǎn)的層次數(shù)、度為0、2的結(jié)點(diǎn)數(shù)，二叉樹的相似、全等、復(fù)制等等的算法。由二叉樹的遍歷的前序和中序序列或后序和中序序列可以唯一構(gòu)造一棵二叉樹，手工模擬及編寫算法。由前序和后序序列不能唯一確定一棵二叉樹。二叉樹線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)在相應(yīng)序列中的前驅(qū)和后繼之間的直接聯(lián)系。在何序（前、中、后）下進(jìn)行何種（全、前驅(qū)、后繼）線索化，并求某結(jié)點(diǎn)相應(yīng)的前驅(qū)和后繼。完全二叉樹的性質(zhì)，順序存儲(chǔ)結(jié)構(gòu)和二叉樹鏈表存儲(chǔ)結(jié)構(gòu)的相互轉(zhuǎn)換。樹的雙親表示法和孩子兄弟表示法間的相互轉(zhuǎn)換。樹、森林和二叉樹間的相互轉(zhuǎn)換（“連線”、“切線”和“旋轉(zhuǎn)”）。哈夫曼樹的定義、構(gòu)造及求哈夫曼編碼。三、例題及分析在二叉樹中查找其數(shù)據(jù)域?yàn)?x的結(jié)點(diǎn)。如存在，返回該結(jié)點(diǎn)指針，否則返回空指針。【分析】 可采用遞歸遍歷算法?！舅惴ā縋ROC search(bt:bitreptr。 x:datatype)。 {bt 是bitreptr型的二叉樹，x是待查找數(shù)據(jù)值,本算法遞歸遍歷二叉樹，在遍歷中進(jìn)行查找。算法中p是調(diào)用本過程的過程中定義的變量，初值為NIL，查找成功后，p指向數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)。found是初值為false的變量。從本過程返回后，測(cè)試found以確定是否查找成功。} IF (btNIL ) AND NOT found THEN [IF bt^.data=x THEN [ p:=bt。 found:=true ] search (bt^.lchild, x)。 search (bt^.rchild, x)。 ] ENDP。 {serch}【討論】本算法核心語句有三個(gè)（即第一個(gè)THEN后的語句：第一個(gè)語句是“訪問”根結(jié)點(diǎn). 后兩個(gè)語句是遞歸遍歷（相對(duì)位置不變）。在這三個(gè)語句中，由“訪問”語句所處位置不同（前、中、后），形成三種遞歸遍歷方法：前序、中序和后序。Found是為查到x就立即（不再遍歷未遍歷結(jié)點(diǎn)）而設(shè)立的。若要再考慮本算法的優(yōu)化，則在兩個(gè)調(diào)用語句中可加上 If (bt^.lchildNIL) AND NOT found 和 If (bt^.rchildNIL) AND NOT found 其優(yōu)點(diǎn)是在左（右）為空時(shí)不必再調(diào)用，且一旦找到x就立即退出。２．設(shè)二叉樹采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，試編寫算法求二叉樹的結(jié)點(diǎn)數(shù)?！痉治觥俊　　　∮?jì)算二叉樹結(jié)點(diǎn)數(shù)的數(shù)學(xué)模型如下：f(bt)=0 若bt=nilf(bt)=f(bt^.lchild) +f(bt^.rchild) +1 否則【算法】　　　　FUNC nodes(bt:bitreptr):integer。 IF bt=nil THEN nodes:=0 ELSE [ n1:=nodes(bt^.lchild) n2:=nodes(bt^.rchild) nodes:=ni+n2+1 ] ENDF {nodes}【討論】 二叉樹由根、左子樹、右子樹三部分組成，很多問題（如求葉子、度１、度２結(jié)點(diǎn)數(shù)），可分解到三部分求解，上面寫出數(shù)學(xué)遞歸模型是有普遍意義的。例如：（１）. 二叉樹相似：　　　　f(t1,t2)=true　　 若t1=t2=NIL f(t1,t2)=false　　　若t1,t2中只有一個(gè)為NIL f(t1,t2)=f(t1^.lchild, t2^.lchild) AND f(t1^.rchild,t2^.rchild) 　若t1,t2均不為NIL (2)求二叉樹的葉子結(jié)點(diǎn)數(shù)f(bt)=0 當(dāng)bt=nilf(bt)=1 當(dāng)bt左右子樹均為空f(bt)=f(bt^.lchild)+f(bt^.rchild) 否則（３）求二叉樹所有葉子結(jié)點(diǎn)的最大枝長(zhǎng)：　　　 0 　　　　　 若bt^.lchild=nil 且bt^.rchild=nil　　　 　　　　 maxl(bt^.lchild)+1 若bt^.rchild=nilmax= maxl(bt^.rchild+1) 若bt^.lchild=nil max(maxl(bt^.rchild+1) ,maxl(bt^.rchild))+1 否則 ３．打印二叉樹中結(jié)點(diǎn)x（假定存在）的所有祖先結(jié)點(diǎn)。　　【分析】在二叉樹的遞歸遍歷等算法中，只有后序遍歷才是最后訪問根結(jié)點(diǎn)，因此有可能保留從根結(jié)點(diǎn)到待查結(jié)點(diǎn)的蹤跡，這時(shí)可用棧，存放從根結(jié)點(diǎn)到x結(jié)點(diǎn)路徑中的各祖先結(jié)點(diǎn)。 【算法】PROC printansctr(bt:bitreptr。 x:datatype)。 {bt 是bitreptr型的二叉樹，x是待查找數(shù)據(jù)值,本算法輸出X結(jié)點(diǎn)的各祖先結(jié)點(diǎn)。S是工作棧，存放X的祖先結(jié)點(diǎn)。查到X后，依次輸出S中數(shù)據(jù)即可。} initstack(s)。 p:=bt。 push(s,p)。 WHILE NOT empty(s) DO [ WHILE NOT empty(s) AND (p^.datax) DO [ push(s,p)。 p