數(shù)據(jù)結(jié)構(gòu)（Java語言實(shí)現(xiàn)） 課件 陳銳 第3、4章 棧和隊(duì)列；串、數(shù)組和廣義表

第3章棧和隊(duì)列結(jié)構(gòu)Java實(shí)據(jù)現(xiàn)數(shù)目錄CONTENTS3.1

棧的表示與實(shí)現(xiàn)3.2棧的應(yīng)用3.3棧與遞歸3.6小結(jié)3.4隊(duì)列的表示與實(shí)現(xiàn)3.5隊(duì)列的應(yīng)用案例3.1：數(shù)制轉(zhuǎn)換案例3.2：括號(hào)匹配的檢驗(yàn)案例3.3：表達(dá)式求值案例3.4：舞伴問題為什么要學(xué)習(xí)棧和隊(duì)列？案例3.5：回文判斷案例3.6：楊輝三角3.1棧的表示與實(shí)現(xiàn)3.1.1棧的定義唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其操作的著作。棧（Stack），也稱為堆棧，它是一種特殊的線性表，只允許在表的一端進(jìn)行插入和刪除操作。允許在表操作的一端稱為棧頂（Top），另一端稱為棧底（Bottom）。棧頂是動(dòng)態(tài)變化的，它由一個(gè)稱為棧頂指針（top）的變量指示。當(dāng)表中沒有元素時(shí)，稱為空棧。棧的插入操作稱為入?；蜻M(jìn)棧，刪除操作稱為出?；蛲藯?。3.1棧的表示與實(shí)現(xiàn)例1.圖3.2演示了元素A、B、C、D和E依次進(jìn)棧和出棧的過程。如果一個(gè)進(jìn)棧的序列由A、B、C組成，它的出棧序列有ABC、ACB、BAC、BCA和CBA五種可能，只有CAB是不可能的輸出序列。因?yàn)锳、B、C進(jìn)棧后，C出棧，接著就是B要出棧，C不可能A在B之前出棧，所以CAB是不可能出現(xiàn)的序列。Ａ．i

Ｂ．n-iＣ．n-i+1Ｄ．不確定例2.若一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為a1，a2，a3，…，an，若a1=n，則ai為Ｃ3.1棧的表示與實(shí)現(xiàn)例3.3若一個(gè)棧的輸入序列為P1、P2、P3、…、Pn，輸出序列為1、2、3、…、n，如果P3=1，則P1的值（）?？赡苁? B.一定是2 C.不可能是2 D.不可能是33.1棧的表示與實(shí)現(xiàn)3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力ADTStack{

數(shù)據(jù)對(duì)象：D={ai|ai∈ElemSet，i=1，2，…，n，n≥0}

數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1，ai∈D，i=2，3，…，n}

約定a1端為棧底，an端為棧頂。基本操作：（1）InitStack(&S)

初始條件：棧S不存在。操作結(jié)果：建立一個(gè)空棧S。（2）StackEmpty(S)

初始條件：棧S已存在。操作結(jié)果：若棧S為空，返回1，否則返回0。3.1.2棧的抽象數(shù)據(jù)類型3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力（3）GetTop(S,&e)

初始條件：棧S存在且非空。操作結(jié)果：返回棧S的棧頂元素給e。（4）PushStack(&S,x)

初始條件：棧S已存在。操作結(jié)果：將元素x插入到棧S中，使其成為新的棧頂元素。（5）PopStack(&S,&e)

初始條件：棧S存在且非空。操作結(jié)果：刪除棧S的棧頂元素，并用e返回其值。（6）StackLength(S)

初始條件：棧S已存在。操作結(jié)果：返回棧S的元素個(gè)數(shù)。（7）ClearStack(S)

初始條件：棧S已存在。操作結(jié)果：將棧S清為空棧。}ADTStack3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力3.1.3順序棧1.棧的順序存儲(chǔ)結(jié)構(gòu)采用順序存儲(chǔ)結(jié)構(gòu)的棧稱為順序棧。順序棧利用一組連續(xù)的存儲(chǔ)單元存放棧中的元素，存放順序依次從棧底到棧頂。publicclassSeqStack{inttop;finalintMAXSIZE=50;charstack[];}其中，stack[]用于存儲(chǔ)棧中的數(shù)據(jù)元素，top為棧頂指針，MAXSIZE為棧的最大容量。3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力將元素a、b、c、d、e、f、g、h依次進(jìn)棧，棧底元素為a，棧頂元素為h。約定棧頂指針top指向棧頂元素的下一個(gè)位置（而不是棧頂元素）。（1）初始時(shí)，棧為空，棧頂指針為0，即S.top=0。（2）?？諚l件為S.top==0，棧滿條件為S.top==MAXSIZE-1。（3）進(jìn)棧操作時(shí)，先將元素壓入棧中，即S.stack[S.top]=e，然后使棧頂指針加1，即S.top+=1。出棧操作時(shí)，先使棧頂指針減1，即S.top-=1，然后元素出棧，即e=S.stack[S.top]。（4）棧的長度即棧中元素的個(gè)數(shù)為S.top。3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力2.順序棧的基本運(yùn)算（1）初始化棧。SeqStack(){top=0;stack=newchar[MAXSIZE];}（2）判斷棧是否為空。publicbooleanStackEmpty(){if(top==0)returntrue;elsereturnfalse;}3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力（3）取棧頂元素。在取棧頂元素前，先判斷棧是否為空，如果棧為空，則拋出異常表示取棧頂元素失?。环駝t，將棧頂元素返回。publiccharGetTop()throwsException{if(StackEmpty()){System.out.println("棧為空，取棧頂元素失敗!");thrownewException("棧為空！");}elsereturnstack[top-1];}3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力（4）將元素e入棧。publicbooleanPushStack(chare){if(top>=MAXSIZE){System.out.println("棧已滿！");returnfalse;}else{stack[top]=e;top++;returntrue;}}3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力（5）將棧頂元素出棧。在將元素出棧前，需要先判斷棧是否為空。若棧為空，則拋出異常；若棧不為空，則先使棧頂指針減1，然后將棧頂元素返回。publiccharPopStack()throwsException{if(StackEmpty()){System.out.println("棧為空，不能進(jìn)行出棧操作!");thrownewException("棧為空!");}else{top--;charx=stack[top];returnx;}}3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力（6）求棧的長度。publicintStackLength(){returntop;}（7）清空棧。publicvoidClearStack(){top=0;}【例3-3】任意給定一個(gè)數(shù)學(xué)表達(dá)式如{5*(9-2)-[15-(8-3)/2]}+3*(6-4)，試設(shè)計(jì)一個(gè)算法判斷表達(dá)式的括號(hào)是否匹配?！痉治觥繖z驗(yàn)括號(hào)是否匹配可以設(shè)置一個(gè)棧，每讀入一個(gè)括號(hào)，如果是左括號(hào)，則直接進(jìn)棧。（1）如果讀入的是右括號(hào)：且與當(dāng)前棧頂?shù)淖罄ㄌ?hào)是同類型的，說明這一對(duì)括號(hào)是匹配的，則將棧頂?shù)淖罄ㄌ?hào)出棧，否則是不匹配。且棧已經(jīng)為空，說明缺少左括號(hào)，該括號(hào)序列不匹配。（2）如果輸入序列已經(jīng)讀完，而棧中仍然有等待匹配的左括號(hào)，說明缺少右括號(hào)，該括號(hào)序列不匹配。（3）如果讀入是數(shù)字字符，則不進(jìn)行處理，直接讀入下一個(gè)字符。publicstaticbooleanMatch(chare,charch){//判斷左右兩個(gè)括號(hào)是否為同類型，同類型則返回True，否則返回Falseif(e=='('&&ch==')')returntrue;elseif(e=='['&&ch==']')returntrue;elseif(e=='{'&&ch=='}')returntrue;elsereturnfalse;}3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力3.共享?xiàng)Ｊ褂庙樞驐?huì)因?yàn)闂？臻g的大小難以準(zhǔn)確估計(jì)，從而造成有的棧溢出，有的棧還有空閑。為了解決這個(gè)問題，可以讓多個(gè)棧共享一個(gè)足夠大的連續(xù)存儲(chǔ)空間，利用棧的動(dòng)態(tài)特性使?？臻g能夠互相補(bǔ)充，存儲(chǔ)空間得到有效利用，這就是棧的共享，這些棧被稱為共享?xiàng)！?.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力3.1.4鏈棧1.棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)方式的棧稱為鏈?；蜴?zhǔn)綏?。鏈棧采用帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)。

鏈棧結(jié)點(diǎn)的類描述如下：classLinkStackNode{intdata;LinkStackNodenext;LinkStackNode(intdata){this.data=data;this.next=next;}}3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力對(duì)于帶頭結(jié)點(diǎn)的鏈棧，初始化鏈棧時(shí)，有top.next=null，判斷棧空的條件為top.next==null。對(duì)于不帶頭結(jié)點(diǎn)的鏈棧，初始化鏈棧時(shí)，有top=null，判斷棧空的條件為top==null。3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)認(rèn)知能力（1）初始化鏈棧。初始化鏈棧由構(gòu)造方法LinkStack()實(shí)現(xiàn)，即初始化棧頂指針top。publicclassLinkStack{LinkStackNodetop;LinkStack(){top=newLinkStackNode(0);}}（2）判斷鏈棧是否為空。如果頭結(jié)點(diǎn)指針域?yàn)榭眨f明鏈棧為空，返回true；否則，返回false。publicbooleanStackEmpty(){if(top.next==null)returntrue;elsereturnfalse;}3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力（3）進(jìn)棧操作。先動(dòng)態(tài)生成一個(gè)結(jié)點(diǎn)，用pnode指向該結(jié)點(diǎn)，再將元素e值賦給pnode結(jié)點(diǎn)的數(shù)據(jù)域，然后將新結(jié)點(diǎn)插入到鏈表的第一個(gè)結(jié)點(diǎn)之前。把新結(jié)點(diǎn)插入到鏈表中分為兩個(gè)步驟：①pnode.next=top.next；②top.next=pnode。publicvoidPushStack(inte)

{

LinkStackNodepnode=newLinkStackNode(e);

pnode.next=top.next;

top.next=pnode;

}3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力（4）將棧頂元素出棧。先判斷棧是否為空，若棧為空，拋出異常表示出棧操作失??；否則，將棧頂元素值賦給x，釋放該結(jié)點(diǎn)空間，最后將棧頂元素返回。publicintPopStack()throwsException{

if(StackEmpty()){

System.out.println("棧為空，不能進(jìn)行出棧操作!");

thrownewException("棧為空，不能進(jìn)行出棧操作！");

}

else{

LinkStackNodepnode=top.next;

top.next=pnode.next;

intx=pnode.data;

returnx;

}

}3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力（5）取棧頂元素。在取棧頂元素前要判斷鏈棧是否為空，如果為空，則拋出異常；否則，將棧頂元素返回。取棧頂元素的算法實(shí)現(xiàn)如下。publicintGetTop()throwsException{if(StackEmpty()){System.out.println("棧為空，取棧頂元素失敗!");thrownewException("棧為空!");}elsereturntop.next.data;}3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力（6）求棧的長度。棧的長度就是鏈棧的元素個(gè)數(shù)。從棧頂元素開始，通過next域找到下一個(gè)結(jié)點(diǎn)，并使用變量len計(jì)數(shù)，直到棧底為止。publicintStackLength(){LinkStackNodep=top.next;intlen=0;while(p!=null){p=p.next;len=len+1;}returnlen;}3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力（7）創(chuàng)建鏈棧。publicvoidCreateStack(){System.out.print("請(qǐng)輸入要入棧的整數(shù)：");Scannerinput=newScanner(System.in);Strings=input.nextLine();String[]arr=s.split("");for(inti=0;i<arr.length;i++){LinkStackNodepnode=newLinkStackNode(Integer.parseInt(arr[i]));pnode.next=top.next;top.next=pnode;}}3.2棧的應(yīng)用學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力將十進(jìn)制數(shù)N轉(zhuǎn)換為x進(jìn)制數(shù)，可用輾轉(zhuǎn)相除法。（1）將N除以x，取其余數(shù)。（2）判斷商是否為零，如果為零，則結(jié)束程序；否則，將商送N，轉(zhuǎn)（1）繼續(xù)執(zhí)行。所得到的余數(shù)序列正好與x進(jìn)制數(shù)的數(shù)字序列相反，因此利用棧的后進(jìn)先出特性，先把得到的余數(shù)序列放入棧保存，最后依次出棧得到x進(jìn)制數(shù)字序列。01數(shù)制轉(zhuǎn)換例如，(5678)10=(13056)8，其運(yùn)算過程如下：3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力

publicstaticintcovert10to8(intx,intnum[]){LinkStackNodetop=null,p;while(x!=0){p=newLinkStackNode(x%8);p.next=top;top=p;x=x/8;}intk=0;while(top!=null){p=top;num[k++]=p.data;top=top.next;}returnk;}01數(shù)制轉(zhuǎn)換3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力設(shè)立一個(gè)輸入緩沖區(qū)，用來接受用戶輸入的一行字符，然后逐行存入數(shù)據(jù)區(qū)。如果用戶輸入出現(xiàn)錯(cuò)誤，發(fā)現(xiàn)輸入有誤時(shí)及時(shí)更正。例如，當(dāng)用戶發(fā)現(xiàn)剛剛鍵入的一個(gè)字符是錯(cuò)誤的時(shí)候，可以輸入一個(gè)退格符“#”，以表示前一個(gè)字符無效；如果發(fā)現(xiàn)當(dāng)前輸入的行內(nèi)差錯(cuò)較多時(shí)，則可以輸入一個(gè)退行符“@”，以表示當(dāng)前行中的字符均無效。02行編輯程序例如，假設(shè)從終端接受了兩行字符：whl#ike##le(s#*s)opintf@putchar(*s==##++)則實(shí)際有效的是下面的兩行：while(*s)putchar(*s++)3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力一個(gè)表達(dá)式由操作數(shù)（operand）、運(yùn)算符（operator）和分界符（delimiter）組成。操作數(shù)可以是常數(shù)，也可以是變量；運(yùn)算符可以是算術(shù)運(yùn)算符、關(guān)系運(yùn)算符和邏輯運(yùn)算符；分界符包括左右括號(hào)和表達(dá)式的結(jié)束符等。03算術(shù)表達(dá)式求值3.1棧的表示與實(shí)現(xiàn)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力將一個(gè)算術(shù)表達(dá)式的中綴形式轉(zhuǎn)化為相應(yīng)的后綴形式前，需要先了解算術(shù)四則運(yùn)算的規(guī)則。算術(shù)四則運(yùn)算的規(guī)則是：（1）先計(jì)算乘除，后計(jì)算加減。（2）先計(jì)算括號(hào)內(nèi)的表達(dá)式，后計(jì)算括號(hào)外的表達(dá)式。（3）同級(jí)別的運(yùn)算從左到右進(jìn)行計(jì)算。03算術(shù)表達(dá)式求值3.1棧的表示與實(shí)現(xiàn)在計(jì)算算術(shù)表達(dá)式的值時(shí)，需要先將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，然后求解表達(dá)式的值。1.將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式例如，一個(gè)算術(shù)表達(dá)式為：a-(b+c*d)/e對(duì)應(yīng)的后綴表達(dá)式為：abcd*+e/-后綴表達(dá)式具有以下兩個(gè)特點(diǎn)：（1）后綴表達(dá)式與中綴表達(dá)式的操作數(shù)出現(xiàn)順序相同，只是運(yùn)算符先后順序改變了。（2）后綴表達(dá)式不出現(xiàn)括號(hào)。3.1棧的表示與實(shí)現(xiàn)運(yùn)算符優(yōu)先關(guān)系表如表3.1所示。3.1棧的表示與實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法如下：（1）初始化棧，將“#”入棧。（2）如果當(dāng)前讀入的字符是操作數(shù)，則將該操作數(shù)輸出，并讀入下一字符。（3）如果當(dāng)前字符是運(yùn)算符，記作?2，則將?2與棧頂?shù)倪\(yùn)算符?1比較。如果棧頂?shù)倪\(yùn)算符?1優(yōu)先級(jí)小于當(dāng)前運(yùn)算符?2，則將當(dāng)前運(yùn)算符?2進(jìn)棧；如果棧頂?shù)倪\(yùn)算符?1優(yōu)先級(jí)大于當(dāng)前運(yùn)算符?2，則將棧頂運(yùn)算符?1出棧并將其作為后綴表達(dá)式輸出。然后繼續(xù)比較新的棧頂運(yùn)算符?1與當(dāng)前運(yùn)算符?2的優(yōu)先級(jí)，如果棧頂運(yùn)算符?1的優(yōu)先級(jí)與當(dāng)前運(yùn)算符?2相等，且?1為“(”、?2為“)”，則將?1出棧，繼續(xù)讀入下一個(gè)字符。（4）如果當(dāng)前運(yùn)算符?2的優(yōu)先級(jí)與棧頂運(yùn)算符?1相等，且?1和?2都為“#”，將?1出棧，棧為空。則中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，算法結(jié)束。3.1棧的表示與實(shí)現(xiàn)中綴表達(dá)式(8*(15-9)+6)/3轉(zhuǎn)換為后綴表達(dá)式的輸出過程如表3.-2所示。3.1棧的表示與實(shí)現(xiàn)后綴表達(dá)式的求值算法如下（假設(shè)棧頂運(yùn)算符為?1，當(dāng)前掃描的運(yùn)算符為?2）：（1）初始化S棧。（2）如果當(dāng)前讀入的字符是操作數(shù)，則將該操作數(shù)進(jìn)入S棧。（3）如果當(dāng)前字符是運(yùn)算符?，則將S棧退棧兩次，分別得到操作數(shù)x和y，對(duì)x和y進(jìn)行?運(yùn)算，即y?x，得到中間結(jié)果z，將z進(jìn)S棧。（4）重復(fù)執(zhí)行步驟（2）和（3），直到S為空。3.1棧的表示與實(shí)現(xiàn)6+(7-1)*3+9/2，中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式3.1棧的表示與實(shí)現(xiàn)根據(jù)得到的后綴表達(dá)式6+(7-1)*3+9/2#，利用棧求解表達(dá)式的值3.2棧與遞歸3.2.1遞歸遞歸是指在函數(shù)的定義中，在定義自己的同時(shí)又出現(xiàn)了對(duì)自身的調(diào)用。1.遞歸函數(shù)例如，n的階乘遞歸定義如下：deffact(n):#n的階乘

ifn==1:

return1

else:

returnn*fact(n-1)3.3棧與遞歸Ackermann函數(shù)定義如下：defAck(m,n):#Ackerman遞歸算法實(shí)現(xiàn)

ifm==0:returnn+1

elifn==0:returnAck(m-1,1)

else:returnAck(m-1,Ack(m,n-1))【例3-6】如果兔子在出生兩個(gè)月后就有繁殖能力，以后一對(duì)兔子每個(gè)月能生出一對(duì)兔子，假設(shè)所有兔子都不死，那么一年以后可以繁殖多少對(duì)兔子呢？經(jīng)過的月數(shù)123456789101112兔子對(duì)數(shù)1123581321345589144表3-3每月兔子的對(duì)數(shù)publicstaticintfib2(intn){if(n==0)//若是第0項(xiàng)

return0;//則返回0elseif(n==1)//若是第1項(xiàng)

return1;//則返回1else//其他情況

returnfib2(n-1)+fib2(n-2);//第三項(xiàng)為前兩項(xiàng)之和}當(dāng)n=4時(shí)，遞歸函數(shù)執(zhí)行過程3.3棧與遞歸2.遞歸調(diào)用過程n階漢諾塔問題。假設(shè)有三個(gè)塔座X、Y、Z，在塔座X上放置有n個(gè)直徑大小各不相同、從小到大編號(hào)為1、2、…、n的圓盤。要求圓盤移動(dòng)時(shí)必須遵循以下規(guī)則：（1）每次只能移動(dòng)一個(gè)圓盤。（2）圓盤可以放置在X、Y和Z中的任何一個(gè)塔座。（3）任何時(shí)候都不能將一個(gè)較大的圓盤放在較小的圓盤上。3.3棧與遞歸2.遞歸調(diào)用過程n階漢諾塔問題。3.3棧與遞歸publicstaticvoidHanoi(intn,StringA,StringB,StringC)//將塔座A上按照從小到大自上而下編號(hào)為1到n的圓盤按照規(guī)則搬到塔座C上，B作為輔助塔座{

if(n==1)

move(1,A,C);//將編號(hào)為1的圓盤從A移動(dòng)到C

else{

Hanoi(n-1,A,C,B);//將編號(hào)為1到n-1的圓盤從A移動(dòng)到B，C作為輔助塔座

move(n,A,C);//將編號(hào)為n的圓盤從A移動(dòng)到C

Hanoi(n-1,B,A,C);//將編號(hào)為1到n-1的圓盤從B移動(dòng)到C，A作為輔助塔座

}

}

publicstaticvoidmove(intn,StringtempA,StringtempB){System.out.println("moveplate"+n+"fromcolumn"+tempA+"tocolumn"+tempB);}3.3棧與遞歸在遞歸調(diào)用過程中，運(yùn)行被調(diào)用函數(shù)前系統(tǒng)要完成3件事情：（1）將所有參數(shù)和返回地址傳遞給被調(diào)用函數(shù)保存。（2）為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)空間。（3）將控制轉(zhuǎn)到被調(diào)用函數(shù)的入口。當(dāng)被調(diào)用函數(shù)執(zhí)行完畢，返回到調(diào)用函數(shù)之前，系統(tǒng)同樣需要完成3個(gè)任務(wù)：（1）保存被調(diào)用函數(shù)的執(zhí)行結(jié)果。（2）釋放被調(diào)用函數(shù)的數(shù)據(jù)存儲(chǔ)區(qū)。（3）將控制轉(zhuǎn)到調(diào)用函數(shù)的返回地址處。3.3棧與遞歸3.3.2消除遞歸遞歸的算法也完全可以轉(zhuǎn)換為非遞歸實(shí)現(xiàn)，這就是遞歸的消除。消除遞歸方法有兩種：一種是對(duì)于簡單的遞歸可以直接用迭代，通過循環(huán)結(jié)構(gòu)就可以消除；另一種方法是利用棧的方式實(shí)現(xiàn)。publicstaticlongfact(intn)//n的階乘的非遞歸算法實(shí)現(xiàn){

longf=1;

inti;

for(i=1;i<n+1;i++)//直接利用迭代消除遞歸

f=f*i;

returnf;

}3.3棧與遞歸利用棧消除遞歸

do{if(s[top][0]==1)//遞歸出口

{s[top][1]=1;System.out.println("n="+s[top][0]+",fact="+s[top][1]);}if(s[top][0]>1&&s[top][1]==0)//通過棧模擬遞歸的遞推過程，將問題依次入棧

{top=top+1;s[top][0]=s[top-1][0]-1;s[top][1]=0;//將結(jié)果置為0，還沒有返回結(jié)果

System.out.println("n="+s[top][0]+",fact="+s[top][1]);}if(s[top][1]!=0)//模擬遞歸的返回過程，將每一層調(diào)用的結(jié)果返回

{s[top-1][1]=s[top][1]*s[top-1][0];System.out.println("n="+s[top-1][0]+",fact="+s[top-1][1]);top=top-1;}}while(top>0);3.3棧與遞歸利用棧消除遞歸請(qǐng)輸入一個(gè)正整數(shù)(n<15)：5遞歸實(shí)現(xiàn)n的階乘:n!=120利用棧非遞歸實(shí)現(xiàn)n的階乘:n=4,fact=0n=3,fact=0n=2,fact=0n=1,fact=0n=1,fact=1n=2,fact=2n=3,fact=6n=4,fact=24n=5,fact=120n!=1203.3隊(duì)列3.3.1隊(duì)列的定義隊(duì)列（Queue）是一種先進(jìn)先出（FirstInFirstOut，縮寫為FIFO）的線性表，它只允許在表的一端插入元素，而在另一端刪除元素。其中，允許插入的一端叫作隊(duì)尾（rear），允許刪除的一端稱為隊(duì)頭（front）。假設(shè)隊(duì)列為q=（a1，a2，…，ai，…，an），那么a1就是隊(duì)頭元素，an則是隊(duì)尾元素。3.3隊(duì)列3.3.2隊(duì)列的抽象數(shù)據(jù)類型ADTQueue{

數(shù)據(jù)對(duì)象：D={ai|ai∈ElemSet，i=1，2，…，n，n≥0}

數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1，ai∈D，i=2，3，…，n}

約定a1端為隊(duì)列頭，an端為隊(duì)列尾?；静僮鳎海?）InitQueue(&Q)

初始條件：隊(duì)列Q不存在。操作結(jié)果：建立一個(gè)空隊(duì)列Q。（2）QueueEmpty(Q)

初始條件：隊(duì)列Q已存在。操作結(jié)果：若Q為空隊(duì)列，返回1，否則返回0。3.3隊(duì)列（3）EnQueue(&Q,e)

初始條件：隊(duì)列Q已存在。操作結(jié)果：插入元素e到隊(duì)列Q的隊(duì)尾。（4）DeQueue(&Q,&e)

初始條件：隊(duì)列Q已存在且為非空。操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。（5）Gethead(Q,&e)

初始條件：隊(duì)列Q已存在且為非空。操作結(jié)果：用e返回Q的隊(duì)頭元素。（6）ClearQueue(&Q)

初始條件：隊(duì)列Q已存在。操作結(jié)果：將隊(duì)列Q清為空隊(duì)列。}ADTQueue3.3隊(duì)列3.3.3順序隊(duì)列隊(duì)列有兩種存儲(chǔ)表示：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。采用順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列稱為順序隊(duì)列，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的隊(duì)列稱為鏈?zhǔn)疥?duì)列。1.順序隊(duì)列的表示順序隊(duì)列通常采用列表作為存儲(chǔ)結(jié)構(gòu)。3.3隊(duì)列為了方便描述，我們約定：初始化時(shí)，隊(duì)列為空，有front=rear=0，隊(duì)頭指針front和隊(duì)尾指針rear都指向隊(duì)列的第一個(gè)位置，如圖3.23所示。3.3隊(duì)列順序隊(duì)列的類型描述如下：publicclassSeQueue<T>{finalintQUEUESIZE=20;Ts[];intfront,rear;}3.3隊(duì)列2.順序隊(duì)列的“假溢出”3.3隊(duì)列3.4.4順序循環(huán)隊(duì)列1.順序循環(huán)隊(duì)列的構(gòu)造為了充分利用存儲(chǔ)空間，消除這種“假溢出”，當(dāng)隊(duì)尾指針rear（或隊(duì)頭指針front）到達(dá)存儲(chǔ)空間的最大值QUEUESIZE的時(shí)候，讓隊(duì)尾指針rear（或隊(duì)頭指針front）自動(dòng)轉(zhuǎn)化為存儲(chǔ)空間的最小值0。這樣，順序隊(duì)列的存儲(chǔ)空間就構(gòu)成一個(gè)邏輯上首尾相連的循環(huán)隊(duì)列。2.順序循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿（1）增加一個(gè)標(biāo)志位。（2）少用一個(gè)存儲(chǔ)空間。3.3隊(duì)列初始化隊(duì)列。publicclassSeQueue<T>{finalintQUEUESIZE=20;Ts[];intfront,rear;SeQueue(){//順序循環(huán)隊(duì)列的初始化

s=(T[])newObject[QUEUESIZE];front=0;//把隊(duì)頭指針置為0rear=0;//把隊(duì)尾指針置為0}3.3隊(duì)列②判斷隊(duì)列是否為空。若隊(duì)頭指針與隊(duì)尾指針相等，則隊(duì)列為空；否則隊(duì)列不為空。publicbooleanIsEmpty()//判斷順序循環(huán)隊(duì)列是否為空{(diào)if(front==rear)//當(dāng)順序循環(huán)隊(duì)列為空時(shí)

returntrue;//返回trueelse//否則

returnfalse;//返回false}3.3隊(duì)列③將元素x入隊(duì)。在將元素入隊(duì)（即把元素插入到隊(duì)尾）之前，先判斷隊(duì)列是否已滿。如果隊(duì)列未滿，則執(zhí)行插入運(yùn)算，然后隊(duì)尾指針加1把隊(duì)尾指針向后移動(dòng)。publicbooleanEnQueue(Tx)//元素e插入到順序循環(huán)隊(duì)列中，插入成功返回true，否則返回false{if((rear+1)%QUEUESIZE!=front)//在插入新元素前，判斷隊(duì)尾指針是否上溢

{s[rear]=x;//在隊(duì)尾插入元素erear=(rear+1)%QUEUESIZE;//將隊(duì)尾指針向后移動(dòng)一個(gè)位置

returntrue;}else{System.out.println("當(dāng)前隊(duì)列已滿!");returnfalse;}}3.3隊(duì)列④將隊(duì)頭元素出隊(duì)。在隊(duì)頭元素出隊(duì)（即刪除隊(duì)頭元素）之前，先判斷隊(duì)列是否為空。若隊(duì)列不空，則刪除隊(duì)頭元素，然后將隊(duì)頭指針向后移動(dòng)，使其指向下一個(gè)元素。publicTDeQueue()throwsException{//將隊(duì)頭元素出隊(duì)，并將該元素賦值給eif(front==rear)//若隊(duì)列是否為空

{System.out.println("隊(duì)列為空，出隊(duì)操作失?。?);thrownewException("隊(duì)列為空，不能進(jìn)行出隊(duì)操作");}else{Te=s[front];//將待出隊(duì)的元素賦值給efront=(front+1)%QUEUESIZE;//將隊(duì)頭指針向后移動(dòng)一個(gè)位置，指向新的隊(duì)頭

returne;//返回出隊(duì)的元素

}}

3.3隊(duì)列⑤取隊(duì)頭元素。先判斷順序循環(huán)隊(duì)列是否為空，如果隊(duì)列為空，則拋出異常表示取隊(duì)頭元素失敗；否則，取出隊(duì)頭元素返回，表示取隊(duì)頭元素成功。publicTGetHead()throwsException{//取隊(duì)頭元素，并將該元素返回

if(!IsEmpty())//若順序循環(huán)隊(duì)列不為空

return(T)s[front];//返回隊(duì)頭元素

else//否則

{System.out.println("隊(duì)列為空");thrownewException("隊(duì)列為空");}}

3.3隊(duì)列⑥獲取隊(duì)列的長度。publicintSeqLength(){return(rear-front+QUEUESIZE)%QUEUESIZE;}⑦隊(duì)列的創(chuàng)建。publicvoidCreateSeqQueue(){inti=0;System.out.println("請(qǐng)輸入元素（#作為輸入結(jié)束）:");Scannersc=newScanner(System.in);Integerdata=sc.nextInt();while(data!=-1){EnQueue(data);i++;data=sc.nextInt();}}

3.3隊(duì)列1.鏈?zhǔn)疥?duì)列的表示鏈?zhǔn)疥?duì)列通常用鏈表實(shí)現(xiàn)。一個(gè)鏈隊(duì)列顯然需要兩個(gè)分別指示隊(duì)頭和隊(duì)尾的指針（分別稱為隊(duì)頭指針和隊(duì)尾指針）才能唯一確定。這里，與單鏈表一樣，為了操作方便，給鏈隊(duì)列添加一個(gè)頭結(jié)點(diǎn)，并令隊(duì)頭指針front指向頭結(jié)點(diǎn)，用隊(duì)尾指針rear指向最后一個(gè)結(jié)點(diǎn)。一個(gè)不帶頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列和帶頭結(jié)點(diǎn)的鏈隊(duì)列分別如圖3-34、圖3-35所示。

3.3隊(duì)列鏈?zhǔn)疥?duì)列的結(jié)點(diǎn)類型描述如下：classQueueNode{chardata;QueueNodenext;QueueNode(chardata){this.data=data;this.next=null;}}

3.3隊(duì)列（2）鏈?zhǔn)窖h(huán)隊(duì)列將鏈?zhǔn)疥?duì)列的首尾相連就構(gòu)成了鏈?zhǔn)窖h(huán)隊(duì)列。在鏈?zhǔn)窖h(huán)隊(duì)列中，可以只設(shè)置隊(duì)尾指針，如圖3-40所示。當(dāng)隊(duì)列為空時(shí)，如圖3-41所示，隊(duì)列LQ為空的判斷條件為LQ.rear.next==LQ.rear。

3.3隊(duì)列（1）初始化隊(duì)列。先生成一個(gè)QueueNode類型的結(jié)點(diǎn)，然后讓front和rear分別指向該結(jié)點(diǎn)。publicclassLinkQueue{QueueNodefront,rear;LinkQueue()//初始化隊(duì)列

{QueueNodeQNode=newQueueNode('0');front=QNode;rear=QNode;}}。

3.3隊(duì)列（2）判斷隊(duì)列是否為空。publicbooleanQueueEmpty()//判斷鏈?zhǔn)疥?duì)列是否為空，隊(duì)列為空返回true，否則返回false{if(front==rear)//若鏈?zhǔn)疥?duì)列為空時(shí)

returntrue;//則返回trueelse//否則

returnfalse;//返回false}。

3.3隊(duì)列（3）將元素e入隊(duì)。先生成一個(gè)新結(jié)點(diǎn)pNode，再將e賦給該結(jié)點(diǎn)的數(shù)據(jù)域，使原隊(duì)尾元素結(jié)點(diǎn)的指針域指向新結(jié)點(diǎn)，最后讓隊(duì)尾指針指向新結(jié)點(diǎn)，從而將結(jié)點(diǎn)加入隊(duì)列中。

publicvoidEnQueue(chare)//將元素e入隊(duì){QueueNodepNode=newQueueNode(e);//生成一個(gè)新結(jié)點(diǎn),將元素值賦給結(jié)點(diǎn)的數(shù)據(jù)域

rear.next=pNode;//將原隊(duì)列的隊(duì)尾結(jié)點(diǎn)的指針指向新結(jié)點(diǎn)

rear=pNode;//將隊(duì)尾指針指向新結(jié)點(diǎn)

}3.3隊(duì)列（4）將隊(duì)頭元素出隊(duì)。刪除隊(duì)頭元素時(shí)，應(yīng)首先通過隊(duì)頭指針和隊(duì)尾指針是否相等判斷隊(duì)列是否已空。若隊(duì)列非空，則刪除隊(duì)頭元素，然后將指向隊(duì)頭元素的指針向后移動(dòng)，使其指向下一個(gè)元素。

publiccharDeQueue()throwsException//將鏈?zhǔn)疥?duì)列中的隊(duì)頭元素出隊(duì)返回該元素，若隊(duì)列為空，則拋出異常{if(QueueEmpty())//在出隊(duì)前，判斷鏈?zhǔn)疥?duì)列是否為空

{System.out.println("隊(duì)列為空,不能進(jìn)行出隊(duì)操作!");thrownewException("隊(duì)列為空，不能出隊(duì)操作");}else

{QueueNodepNode=front.next;//使pNode指向隊(duì)頭元素

front.next=pNode.next;//使頭結(jié)點(diǎn)的next指向pNode的下一個(gè)結(jié)點(diǎn)

if(pNode==rear)//如果要?jiǎng)h除的結(jié)點(diǎn)是隊(duì)尾，則使隊(duì)尾指針指向隊(duì)頭

rear=front;returnpNode.data;//返回出隊(duì)元素

}}3.3隊(duì)列（5）取隊(duì)頭元素。在取隊(duì)頭元素之前，先判斷鏈?zhǔn)疥?duì)列是否為空。

publicintgetHead()//取鏈?zhǔn)疥?duì)列中的隊(duì)頭元素{if(!QueueEmpty())//若鏈?zhǔn)疥?duì)列不為空

returnfront.next.data;//返回隊(duì)頭元素}3.3隊(duì)列【例3-11】編寫一個(gè)算法，判斷任意給定的字符序列是否為回文。所謂回文是指一個(gè)字符序列以中間字符為基準(zhǔn)兩邊字符完全相同，即順著看和倒著看是相同的字符序列。例如，字符序列“XYZMTATMZYX”為回文，而字符序列“回文，而字符序列不是回文。

Stringstr1=newString("XYZMTATMZYX");Stringstr2=newString("ABCBCAB");for(inti=0;i<str1.length();i++){LQ1.EnQueue(str1.charAt(i));LS1.PushStack(str1.charAt(i));}for(inti=0;i<str2.length();i++){LQ2.EnQueue(str2.charAt(i));LS2.PushStack(str2.charAt(i));

}System.out.println("字符序列1:"+str1);System.out.println("出隊(duì)序列出棧序列");while(!LS1.StackEmpty())//判斷堆棧1是否為空

{charq1=LQ1.DeQueue();//字符序列依次出隊(duì)，并把出隊(duì)元素賦值給qchars1=LS1.PopStack();//字符序列出棧，并把出棧元素賦值給sSystem.out.println(q1+":"+s1);if(q1!=s1){System.out.println("字符序列1不是回文！");return;}}3.4雙端隊(duì)列雙端隊(duì)列是一種特殊的隊(duì)列，它是在線性表的兩端對(duì)插入和刪除操作限制的線性表。雙端隊(duì)列可以在隊(duì)列的任何一端進(jìn)行插入和刪除操作，而一般的隊(duì)列要求在一端插入元素，在另一端刪除元素。如圖3.30所示。

元素a、b、c依次進(jìn)入右端的隊(duì)列，元素e、f依次進(jìn)入左端的隊(duì)列，如圖3-45所示。3.5隊(duì)列的應(yīng)用3.5.1隊(duì)列在楊輝三角中的應(yīng)用1.楊輝三角楊輝三角是一個(gè)由數(shù)字排列成的三角形數(shù)表，一個(gè)8階的楊輝三角圖形如圖3.41所示。

3.5隊(duì)列的應(yīng)用（1）在第8行中，第一個(gè)元素先入隊(duì)。假設(shè)隊(duì)列為Q，Q.queue[rear]=1、Q.rear=(Q.rear+1)%QUEUESIZE。（2）第8行中的中間6個(gè)元素需要通過第7行（已經(jīng)入隊(duì)）得到并入隊(duì)。Q.queue[rear]=Q.queue[front]+Q.queue[front+1]、Q.rear=(Q.rear+1)%QUEUESIZ、Q.front=(Q.front+1)%QUEUESIZE。（3）第7行最后一個(gè)元素出隊(duì)，Q.front=(Q.front+1)%QUEUESIZE。（4）第8行最后一個(gè)元素入隊(duì)，Q.queue[rear]=1、Q.rear=(Q.rear+1)%QUEUESIZE。

3.5隊(duì)列的應(yīng)用（1）在第8行中，第一個(gè)元素先入隊(duì)。假設(shè)隊(duì)列為Q，Q.queue[rear]=1、Q.rear=(Q.rear+1)%QUEUESIZE。（2）第8行中的中間6個(gè)元素需要通過第7行（已經(jīng)入隊(duì)）得到并入隊(duì)。Q.queue[rear]=Q.queue[front]+Q.queue[front+1]、Q.rear=(Q.rear+1)%QUEUESIZ、Q.front=(Q.front+1)%QUEUESIZE。（3）第7行最后一個(gè)元素出隊(duì)，Q.front=(Q.front+1)%QUEUESIZE。（4）第8行最后一個(gè)元素入隊(duì)，Q.queue[rear]=1、Q.rear=(Q.rear+1)%QUEUESIZE。

3.6小結(jié)棧是一種只允許在線性表的一端進(jìn)行插入和刪除操作的線性表。其中，允許插入和刪除的一端稱為棧頂，另一端稱為棧底。棧的特點(diǎn)是后進(jìn)先出，使棧在程序設(shè)計(jì)、編譯處理得到有效的利用。數(shù)制轉(zhuǎn)換、括號(hào)匹配、表達(dá)式求值等問題都是利用棧的后進(jìn)先出特性解決的。隊(duì)列只允許在線性表的一端進(jìn)行插入操作，在線性表的另一端進(jìn)行刪除操作。隊(duì)列也有兩種存儲(chǔ)方式：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。采用順序存儲(chǔ)結(jié)構(gòu)的棧稱為順序隊(duì)列，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧稱為鏈?zhǔn)疥?duì)列。順序隊(duì)列存在“假溢出”的問題，順序隊(duì)列的“假溢出”不是因?yàn)榇鎯?chǔ)空間不足而產(chǎn)生的，而是因?yàn)榻?jīng)過多次的出隊(duì)和入隊(duì)操作之后，存儲(chǔ)單元不能有效利用造成的。感謝聆聽主講：結(jié)構(gòu)Java實(shí)據(jù)現(xiàn)數(shù)第4章串、數(shù)組和廣義表結(jié)構(gòu)Java實(shí)據(jù)現(xiàn)數(shù)目錄CONTENTS4.1

串的定義和抽象數(shù)據(jù)類型4.2串的存儲(chǔ)表示4.3串的模式匹配4.6小結(jié)4.4數(shù)組的定義和抽象數(shù)據(jù)類型4.5廣義表4.1串的定義和抽象數(shù)據(jù)類型4.1.1什么是串串（String），也稱為字符串，是由零個(gè)或多個(gè)字符組成的有限序列。串是一種特殊的線性表，僅由字符組成。一般記作：S=”a1a2…an”。其中，S是串名，n是串的長度。用雙引號(hào)括起來的字符序列是串的值。ai(1≤i≤n)可以是字母、數(shù)字和其他字符。n=0時(shí)，串稱為空串。例如，有四個(gè)串a(chǎn)="tinghuauniversity"、b="tinghua"、c="university"、d="tinghuauniversity"。它們的長度分別為18、7、10、17，b和c是a和d的子串，b在a和d的位置都為1，c在a的位置是9，c在d的位置是8。4.1串的定義和抽象數(shù)據(jù)類型4.1.2串的抽象數(shù)據(jù)類型串的抽象數(shù)據(jù)類型定義了棧中的數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系及基本操作。棧的抽象數(shù)據(jù)類型定義如下：ADTString{數(shù)據(jù)對(duì)象：D={ai|ai∈CharacterSet，i=1，2，…，n，n≥0}數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1，ai∈D，i=2，3，…，n}基本操作：（1）StrAssign(&S,cstr)初始條件：cstr是字符串常量。操作結(jié)果：生成一個(gè)其值等于cstr的串S。（2）StrEmpty(S)初始條件：串S已存在。操作結(jié)果：如果是空串，則返回1，否則返回0。4.1串的定義和抽象數(shù)據(jù)類型（4）StrCopy(&T,S)初始條件：串S已存在。操作結(jié)果：由串S復(fù)制產(chǎn)生一個(gè)與S完全相同的另一個(gè)字符串T。（5）StrCompare(S,T)初始條件：串S和T已存在。操作結(jié)果：比較串S和T的每個(gè)字符的ASCII值的大小，如果S的值大于T，則返回1；如果S的值等于T，則返回0；如果S的值小于T，則返回-1。例如，StrCompare(S,T)=-1，因?yàn)榇甋和串T比較到第13個(gè)字符時(shí)，字符B的ASCII值小于字符S的ASCII值，所以返回-1。（6）StrInsert(&S,pos,T)初始條件：串S和T已存在，且1≤pos≤StrLength(S)+1。操作結(jié)果：在串S的pos個(gè)位置插入串T，如果插入成功，則返回1，否則返回0。例如，如果在串S中的第3個(gè)位置插入字符串"don’t"后，即StrInsert(S,3,"don’t")，串S="Idon’tcomefromBeijing"。4.1串的定義和抽象數(shù)據(jù)類型（7）StrDelete(&S,pos,len)初始條件：串S已存在，且1≤pos≤StrLength(S)-len+1。操作結(jié)果：如果在串S中刪除第pos個(gè)字符開始，長度為len的字符串。如果找到并刪除成功，則返回1，否則返回0。例如，如果在串S中的第13個(gè)位置刪除長度為7的字符串后，即StrDelete(S,13,7)，則S="Icomefrom"。（8）StrConcat(&T,S)初始條件：串S和T已存在。操作結(jié)果：將串S連接在串T的后面。如果連接成功，則返回1，否則返回0。例如，如果將串S連接在串T的后面，即StrCat(T,S)，則T="IcomefromShanghaiIcomefromBeijing"。（9）SubString(&Sub,S,pos,len)初始條件：串S已存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-len+1。操作結(jié)果：從串S中截取從第pos個(gè)字符開始，長度為len的連續(xù)字符，并賦值給Sub。如果截取成功，則返回1，否則返回0。例如，如果將串S中的第8個(gè)字符開始，長度為4的字符串賦值給Sub，即SubString(Sub,S,8,4)，則Sub="from"。4.1串的定義和抽象數(shù)據(jù)類型（10）StrReplace(&S,T,V)初始條件：串S、T和V已存在，且T為非空串。操作結(jié)果：如果在串S中存在子串T，則用V替換串S中的所有子串T。如果替換操作成功，則返回1，否則返回0。例如，如果將串S中的子串R替換為串V，即StrReplace(S,R,V)，則S="IcomefromChongqing"。（11）StrIndex(S,pos,T)初始條件：串S和T存在，T是非空串，且1≤len≤StrLength(S)。操作結(jié)果：如果主串S中存在與串T的值相等的子串，則返回子串T在主串S中，第pos個(gè)字符之后的第一次出現(xiàn)的位置，否則返回0。例如，在串S中的第4個(gè)字符開始查找，如果串S中存在與子串R相等的子串，則返回R在S中第一次出現(xiàn)的位置，即StrIndex(S,4,R)=13。4.2串的存儲(chǔ)表示4.2.1串的順序存儲(chǔ)結(jié)構(gòu)用Java中的字符串類型表示串，可通過一對(duì)雙引號(hào)括起來的字符表示字符串。例如：Stringstr=“HelloWorld!”;確定串的長度有兩種方法（1）使用String類中的length()方法獲得串的長度，（2）引入一個(gè)變量length來記錄串的長度。例如，串”HelloWorld!”在內(nèi)存中，用設(shè)置串的長度的方法的表示如圖4-2所示。publicclassSeqString//定義字符串結(jié)構(gòu)類型{finalintMAXSIZE=100;charstr[];intlength;SeqString(chars[]){str=newchar[MAXSIZE];for(inti=0;i<s.length;i++)str[i]=s[i];length=s.length;}}4.2串的存儲(chǔ)表示4.2.2串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在順序串中，對(duì)于串的插入操作、串的連接及串的替換操作，如果串的長度超過了MaxLen，串會(huì)被截?cái)嗵幚怼榱丝朔@些缺點(diǎn)，可以使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示的串進(jìn)行處理。4.2串的存儲(chǔ)表示塊鏈串類型定義如下：classChunk//串的結(jié)點(diǎn)類型定義{finalintChunkSize=4;charch[];Chunknext;

}classLinkString//鏈串的類型定義{Chunkhead,tail;intlength;}其中，head表示頭指針，指向鏈串的第一個(gè)結(jié)點(diǎn)。tail表示尾指針，指向鏈串的最后一個(gè)結(jié)點(diǎn)。length表示鏈串中字符的個(gè)數(shù)。4.3串的模式匹配4.3.1樸素模式匹配算法——模式匹配算法Brute-Force子串的定位操作串通常稱為模式匹配，是各種串處理系統(tǒng)中最重要的操作之一。設(shè)有主串S和子串T，如果在主串S中找到一個(gè)與子串T相等的串，則返回串T的第一個(gè)字符在串S中的位置。其中，主串S又稱為目標(biāo)串，子串T又稱為模式串。4.3串的模式匹配例如，主串S="abaababaddecab"，子串T="abad"，S的長度為n=13，T的長度為m=4。用變量i表示主串S中當(dāng)前正在比較字符的下標(biāo)，變量j表示子串T中當(dāng)前正在比較字符的下標(biāo)。模式匹配的過程如圖4-8所示。4.3串的模式匹配publicintB_FIndex(SeqStringS,SeqStringT,intpos){//在主串S中的第pos個(gè)位置開始查找模式串T，如果找到返回子串在主串的位置；否則，返回-1

inti=pos-1;intj=0;

count=0;

while(i<S.length&&j<T.length){

if(S.str[i]==T.str[j])//若串S和T字符相等，則繼續(xù)比較下一個(gè)字符

{

i+=1;j+=1;}

else//若對(duì)應(yīng)字符不相等，則從串S的下一個(gè)字符、T的第0個(gè)字符開始比較

{i=i-j+1;j=0;}

count++;

}

if(j>=T.length)//如果在S中找到串T，則返回子串T在主串S的位置

returni-j+1;

else

return-1;

}4.3串的模式匹配例如設(shè)主串S="aaaaaaaaaaaaab"，模式串T="aaab"。其中，n=14，m=4。因?yàn)槟Ｊ酱那?個(gè)字符是"aaa"，主串的前13個(gè)字符也是"aaa"，每趟比較模式串的最后一個(gè)字符與主串中的字符不相等，所以均需要將主串的指針回退，從主串的下一個(gè)字符開始與模式串的第一個(gè)字符重新比較。在整個(gè)匹配過程中，主串的指針需要回退9次，匹配不成功的比較次數(shù)是10*4，成功匹配的比較次數(shù)是4次，因此總的比較次數(shù)是10*4+4=11*4即(n-m+1)*m。Brute-Force匹配算法在最好的情況下，即主串的前m個(gè)字符剛好與模式串相等，時(shí)間復(fù)雜度為O(m)。在最壞的情況下，Brute-Force匹配算法的時(shí)間復(fù)雜度是O(n*m)。4.3串的模式匹配4.3.2KMP算法KMP算法是由D.E.Knuth、J.H.Morris、V.R.Pratt共同提出的，因此稱為KMP算法（Knuth-Morris-Pratt算法）。KMP算法在Brute-Force算法的基礎(chǔ)上有較大改進(jìn)4.3串的模式匹配從圖4-9中可以看出，KMP算法的匹配次數(shù)由原來的6次減少為4次。在第一次匹配的過程中，當(dāng)i=3、j=3，主串中的字符與子串中的字符不相等，Brute-Force算法從i=1、j=0開始比較。將主串的指針回退的比較是沒有必要的，在第一次比較遇到主串與子串中的字符不相等時(shí)，有S0=T0="a"，S1=T1="b"，S2=T2="a"，S3≠T3。因?yàn)镾1=T1且T0≠T1，所以S1≠T0，S1與T0不必比較。又因?yàn)镾2=T2且T0=T2，有S2=T0，所以從S3與T1開始比較。4.3串的模式匹配假設(shè)主串S="s0s1…sn-1"，T="t0t1…tm-1"。在模式匹配過程中，如果出現(xiàn)字符不匹配的情況，即當(dāng)Si≠Tj(0≤i<n,0≤j<m)時(shí)，有："si-jsi-j+1…si-1"="t0t1…tj-1"假設(shè)子串即模式串存在可重疊的真子串，即："t0t1…tk-1"="tj-ktj-k+1…tj-1"4.3串的模式匹配如果令next[j]=k，則next[j]表示：當(dāng)子串中的第j個(gè)字符與主串中的對(duì)應(yīng)的字符不相等時(shí)，下一次子串需要與主串中該字符進(jìn)行比較的字符的位置。子串即模式串中的next函數(shù)，定義如下：4.3串的模式匹配KMP算法的模式匹配過程：如果模式串T中存在真子串"t0t1…tk-1"="tj-ktj-k+1…tj-1"，當(dāng)模式串T與主串S的si不相等，則按照next[j]=k將模式串向右滑動(dòng)，從主串中的si與模式串的tk開始比較。如果si=tk，則主串與子串的指針各自增1，繼續(xù)比較下一個(gè)字符。如果si≠tk，則按照next[next[j]]將模式串繼續(xù)向右滑動(dòng)，將主串中的si與模式串中的next[next[j]]字符進(jìn)行比較。4.3串的模式匹配publicintKMP_Index(SeqStringS,SeqStringT,intpos,intnext[])//KMP模式匹配算法。利用模式串T的next函數(shù)在主串S中的第pos個(gè)位置開始查找模式串T，如果找到返回模式串在主串的位置；否則，返回-1{

inti=pos-1;

intj=0;count=0;

while(i<S.length&&j<T.length)

{

if(j==-1||S.str[i]==T.str[j])//如果j=-1或當(dāng)前字符相等，則繼續(xù)比較后面的字符

{

i+=1;j+=1;}

else//如果當(dāng)前字符不相等，則將模式串向右移動(dòng)

{j=next[j];//next保存next函數(shù)值

}

count++;

}

if(j>=T.length)//匹配成功，返回子串在主串中的位置