【正文】 TwoWayStack=RECORD {雙棧共享一向量空間} elem:ARRAY[1..m] OF elemtype。 top:ARRAY[0..1] OF 0..m+1。 {兩個棧頂指針} END。 PROC inistack(VAR tws:TwoWayStack)。 {初始化} {初始化雙向棧tws為空} [0]:=0。 { 左端棧指針} [1]:=m+1。 { 右端棧指針}ENDP。 {inistack} PROC PUSH(VAR tws:TwoWayStack。i:0..1。 x:elemtype。VAR ofw:boolean)。 {若雙向棧tws不滿,則將x插入到i端,成功時ofw為true,失敗為false} IF([1][0])1 THEN {棧未滿} CASE i OF 0:[0]:=[0]+1。[[0]]:=x。ofw:=true 1:[1]:=[1]1。[[1]]:=x。ofw:=true ENDC ELSE ofw:=false。( 棧滿) ENDP。 {push}PROC POP(VAR tws:TwoWayStack。i:0..1。VAR x:elemtype。VAR underflow:boolean)。 {若雙向棧tws非空,則將i端退棧,棧空時underflow為true} CASE i OF 0:IF [0]=0 {?？諁 THEN[underflow:=true。return(underflow)] ELSE[ [0]:=[0]1。 x:=[[0]+1]。 {彈出元素} ]。 1:IF [1]=m+1 {棧空} THEN[underflow:=true。return(underflow)] ELSE[ [1]:=[1]+1。 x:=[[1]1]。 {彈出元素} ]。ENDCENDP。 {pop }【討論】 上面算法中用0和1代表兩端，且按操作在哪端來分兩種情況進行討論，邏輯清楚。也可用一個公式表示插入（進棧）和刪除（退棧）指針位置。例如，插入時top=top+12*i,刪除時top=top1+2*i。表達簡潔，但不如上面清楚易讀。2． 2．將中綴表達式轉(zhuǎn)換成后綴表達式，并進行表達式求值。PROC trnssufix(VAR exp2:string。s:stack。 exp1:string)。 ｛本算法將中綴表達式exp1轉(zhuǎn)為后綴表達式exp2,使用運算符棧s｝｛算法基本思想是依次從中綴表達式讀入字符w： 若w是變量，直接送入結(jié)果表達式，若w是運算符，則與棧頂運算符比較，若級別高，則進棧； 若低，則棧頂元素退棧，并送入結(jié)果表達式，再取棧頂運算符比較，重復(fù)以上步驟；若w＝’)’,則棧元素依次退棧，并送入結(jié)果表達式，直至＇)＇退棧｝ initstring(exp2)。 initstack(s)。push(s,’’)。 op:=[39。+39。,39。39。,39。*39。,39。/39。,39。(39。,39。)39。,39。39。]。 {操作符集合} read(w)。 　WHILE NOT ((w=39。39。) AND (GETTOP(OPTR)=39。39。)) DO IF NOT (w IN op) THEN ［ insert(exp2,w)。 read(w)?。荨? ELSE CASE precede(GETTOP(s),w) OF 39。39。: [ PUSH(S,w)。 read(w) ]。 39。=39。: IF w=’)’ THEN {遇右括號后，運算符退棧并送結(jié)果表達式，　　　　　　　　　　　　　　　　　　直至左括號} [ x:=POP(S)。 WHILE x’(‘ DO [insert(exp2,x)。x:=POP(S)] read(w) ]。 39。39。: [ b:=POP(S)。 insert(exp2,b)]。 END。ENDP。PROC sufixeval(VAR exp2:string。s:stack。 VAR sn:stack)。 ｛本算法對后綴表達式exp2求值，使用運算符棧s和操作數(shù)棧sn｝｛算法基本思想是逐字符從左到右順序讀入后綴表達式。若讀入的字符w是數(shù)，則直接壓入棧 sn中；若w是運算符，則與棧頂運算符比較，若級別高，則進棧；否則，從運算數(shù)棧彈出兩個操作數(shù)，和從運算符棧彈出的一個運算符進行相應(yīng)運算，結(jié)果存入操作數(shù)棧中。w運算符再與棧頂運算符比較優(yōu)先級。直至后綴表達式處理完畢。這時sn棧中只剩一個數(shù)，即表達式結(jié)果。｝ initstring(sn)。 initstack(s)。 op:=[39。+39。,39。39。,39。*39。,39。/39。,39。(39。,39。)39。,39。39。]。 {操作符集合} read(w)。 {從左到右順序讀入后綴表達式 } 　WHILE NOT empty(exp2) DO IF NOT (w IN op) THEN ［ PUSH(sn,w)。 read(w)　］。 ELSE CASE precede(GETTOP(s),w) OF 39。39。: [ PUSH(s,w)。 read(w) ]。 39。39。: [ a:=POP(sn)。b:=POP(sn)。 theta:=POP(s)。 PUSH(sn,operate(a theta b)) ]。 END。ENDP。 { sufixeval}用設(shè)標記來判定循環(huán)隊列滿，編寫入隊和出隊的算法。 {本算法用設(shè)標記tag的辦法，解決循環(huán)隊列隊滿和隊列空的判斷問題,tag=0表示隊列空，tag=1表示隊列不空} TYPE cyclicqueue=RECORD {設(shè)頭　尾指針和標志域的循環(huán)隊列} elem:=ARRAY[0..m1] OF elemtype。 rear,front:0..m1 tag:0..1?！　。盀榭?，１為非空｝ END。 PROC INITQUEDE(VAR cq:cyclicqueue)?！　。跏蓟? :=0。:=:=0。 ENDP。PROC ENQUEUE(VAR cq:cyclicqueue。 x: elemtype)?！　　　　。鹀q是由頭尾指針和標志域的循環(huán)隊列，本算法是入隊操作，若隊列不滿，｝　　　　?。麆t將x插入到隊尾｝ IF (=1) AND (=) THEN return(false) {隊滿} ELSE[:=(+1) MOD m。 ():=r。 IF =0 THEN :=1 {由空變不空標記} ] ENDP。PROC DELQUEUE(VAR cq:cyclicqueue)。　　　　?。鹀q是由頭尾指針和標志域的循環(huán)隊列，本算法是出隊操作，若隊列非空｝　　　　?。麆t將隊頭元素出隊｝ IF =0 THEN return(false) {隊空} ELSE[:=(+1) MOD m。 IF = THEN :=0 {隊空} ] ENDP。 CONST m=maxlen?！　。犃虚L度｝ TYPE cyclicqueue=RECORD　　　?。辉O(shè)尾指針和隊列長度的循環(huán)隊列｝ elem: ARRAY[0..m1] OF elemtype。 rear: 0..m1。 length: 0..m。　?。犃虚L度｝ END。 PROC INIT_queue(VAR q:cyclicqueue)?！　。跏蓟? :=0。 :=0。ENDP。FUNC add_queue(VAR q:cyclicqueue。x:elemtype):boolean?！　　　。鹮是由尾指針和長度標志的循環(huán)隊列，本算法是入隊操作，若隊列不滿，｝　　　?。麑插入到隊尾｝ IF =m THEN add_queue:=false {隊列滿} ELSE [ :=(+1) mod m。 []:=x。 。=+1。 add_queue:=true {入隊成功} ] ENDF。FUNC dd_queue(VAR q:cyclicqueue。 x。elemtype):boolean。　　　　?。鹮是由尾指針和長度標志的循環(huán)隊列，本算法是出隊操作，若隊列不空，｝　　　　　｛將將隊頭元素出列，并賦給x，隊長度減１｝ IF =0 THEN dd_queue:=false {隊空} ELSE [front。=(+1+m) mod m x:=[front] := ] ENDF。第四章 串一、內(nèi)容提要 是數(shù)據(jù)元素為字符的線性表，串的定義及操作。 的基本操作，編制算法求串的其它操作。 的存儲結(jié)構(gòu)，因串是數(shù)據(jù)元素為字符的線性表，所以存在“結(jié)點大小“的問題。靜態(tài)和動態(tài)（塊鏈結(jié)構(gòu)，堆結(jié)構(gòu)）存儲的優(yōu)缺點。 樸素模式匹配算法及改進（KMP）算法。二、學(xué)習(xí)重點 串的基本操作，編寫串的其他操作（如index,replace等）。在串的模式匹配中，求匹配串的nextval 函數(shù)值。盡管樸素的模式匹配的時間復(fù)雜度是O(m*n), KMP算法是O(m+n),但在一般情況下，前者實際執(zhí)行時間近似O(m+n),因此至今仍被采用。KMP算法僅在主串與模式串存在許多“部分匹配”時才顯得比前者塊的多，其主要優(yōu)點是主串不回嗍。 串操作在存儲結(jié)構(gòu)下的實現(xiàn)。三、例題解析利用串的如下基本運算create(s),assign(s,t),length(s),substr(s,start,len),concat(s1,s2),編寫操作replace的算法PROC replace(VAR s:string。 t,v:string)。 {本算法實現(xiàn)串的置換操作，用串v置換串s中所有非重疊的t串。} i:=INDEX(s,t)。 {判s中有無t} IF i0 THEN [ CREATE (temp, ‘’)。 {t為臨時串變量，存放部分結(jié)果} m:=LENGTH(t)。 n:=LENGTH(s)。 WHILE i0 DO [ ASSIGN (temp,CONCAT(temp,SUBSTR(s,1,i1),v))。 {用v替換t形成部分結(jié)果} ASSIGN (s,SUBSTR(s, i+m, nim+1))。 {t串以后形成新s串} n:= n(i1)m。 i:=INDEX(s,t)。 ] ASSIGN (s,CONCAT(temp,s))。 {將剩余s連接臨時串t再賦給s} ] ENDP。FUNC index(s1:string。 t:string):int