第3講堆棧、隊(duì)列和字符串

Stack、Queue&String棧和隊(duì)列是限定插入和刪除只能在表的“端點(diǎn)”進(jìn)行的線(xiàn)性表。

線(xiàn)性表?xiàng)ｊ?duì)列Insert(L,

i,x)Insert(S,n+1,x)Insert(Q,n+1,x)

1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)

1≤i≤n棧和隊(duì)列是兩種常用的數(shù)據(jù)類(lèi)型Section1

Stack

只允許在一端插入和刪除的線(xiàn)性表允許插入和刪除的一端稱(chēng)為棧頂

(top)，另一端稱(chēng)為棧底(bottom)特點(diǎn)后進(jìn)先出(LIFO)棧(Stack)退棧進(jìn)棧a0an-1an-2topbottom棧的抽象數(shù)據(jù)類(lèi)型定義ADTStack

{

數(shù)據(jù)對(duì)象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

約定an

端為棧頂，a1端為棧底?；静僮鳎?/p>

}ADTStackInitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&x)Push(&S,x)Pop(&S,&x)

InitStack(&S)

操作結(jié)果：構(gòu)造一個(gè)空棧

S。

DestroyStack(&S)

初始條件：棧S已存在。

操作結(jié)果：棧S被銷(xiāo)毀。

StackEmpty(S)

初始條件：棧S已存在。

操作結(jié)果：若棧S為空棧，

則返回TRUE，

否則FALE。

StackLength(S)

初始條件：棧S已存在。

操作結(jié)果：返回S的元素

個(gè)數(shù)，即棧的

長(zhǎng)度。

GetTop(S,&x)

初始條件：棧S已存在且非空。

操作結(jié)果：用x返回S的棧頂

元素。a1a2an……

ClearStack(&S)

初始條件：棧S已存在。

操作結(jié)果：將S清為空棧。

Push(&S,x)

初始條件：棧S已存在。

操作結(jié)果：插入元素x為新

的棧頂元素。

a1a2anx……Pop(&S,&x)

初始條件：棧S已存在且非

空。

操作結(jié)果：刪除S的棧頂元

素，并用x返回

其值。a1a2anan-1

……

棧的數(shù)組表示

—順序棧

//-----棧的順序存儲(chǔ)表示

-----

#defineSTACK_INIT_SIZE100;

#defineSTACKINCREMENT10;

typedefstruct{

SElemType

*base;

SElemType

*top;

intstacksize;

}

SqStack;

類(lèi)似于線(xiàn)性表的順序映象實(shí)現(xiàn)，指向表尾的指針可以作為棧頂指針。

StatusInitStack(SqStack&S){//構(gòu)造一個(gè)空棧SS.base=newElemType[STACK_INIT_SIZE];if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}

StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){//棧滿(mǎn)，追加存儲(chǔ)空間

S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*

sizeof(ElemType));

if(!S.base)exit(OVERFLOW);//存儲(chǔ)分配失敗

S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

returnOK;}StatusPop(SqStack&S,SElemType&e){//若棧不空，則刪除S的棧頂元素，

//用e返回其值，并返回OK；

//否則返回ERROR

if

(S.top

==

S.base)

returnERROR;

e=*--S.top;

returnOK;}template<classType>classStack{private:int

top;

Type*elements;

intmaxSize;public:Stack(ints

=10);~Stack(){delete[]elements;

}

intPush(Typex);

intPop(Type

&x);intGetTop(Type

&x);

voidMakeEmpty(){top=-1;

}

intIsEmpty()const{returntop==-1;

}

intIsFull()const{returntop==maxSize-1;

} }template<classType>Stack<Type>::Stack(ints){top=-1;maxSize=s;elements=newType[maxSize]; }

top空棧toptoptoptoptopa進(jìn)棧b進(jìn)棧aababcdee進(jìn)棧abcdef進(jìn)棧溢出abdee退棧ctopc退棧b退棧abaa退?？諚opabdd退棧ctopabctoptoptemplate<classType>intStack<Type>::Push(Typex){

if(IsFull())

return0;elements[++top]=x;return1;}template<classType>intstack<Type>::Pop(Type&x){if(IsEmpty())return0;x=elements[top--];return1;}

template<classType>intstack<Type>::GetTop(Type&x){if(IsEmpty())

return0;x=elements[top];return1;}第一個(gè)例子：反轉(zhuǎn)表#include"sq_stack.h"voidmain()/*Pre:Theusersuppliesanintegernandndecimalnumbers.Post:Thenumbersareprintedinreverseorder.Uses:TheSTLclassstackanditsmethods*/{intn;doubleitem;stack<double>numbers;//declaresastackofnumberscout<<"Typeinanintegernfollowednnumbers."<<endl<<"Thenumberswillbeprintedinreverseorder."<<endl;cin>>n;for(inti=0;i<n;i++){

cin>>item;numbers.push(item);}cout<<endl<<endl;while(!numbers.empty()){cout<<numbers.top()<<"";numbers.pop();}cout<<endl;}棧的鏈接表示—鏈?zhǔn)綏ｆ準(zhǔn)綏o(wú)棧滿(mǎn)問(wèn)題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^top鏈?zhǔn)綏?LinkedStack)類(lèi)的定義template<classType>classStack;template<classType>classStackNode{friendclassStack<Type>;private:

Typedata;StackNode<Type>*link;public:StackNode(Typed,StackNode<Type>

*l=NULL){ data=d;link=l;

}};template<classType>classStack{private:StackNode<Type>*top;public:Stack(){top=NULL}~Stack();

voidPush(Typex);

intPop(Type&x);

intGetTop(Type&x);

voidMakeEmpty();//實(shí)現(xiàn)與~Stack()同

intIsEmpty(){returntop==NULL;

}}template<classType>Stack<Type>::~Stack(){StackNode<Type>*p;

while(top!=NULL)

{p=top;top=top->link;

deletep;

}}template<classType>voidStack<Type>::Push(Typex){top=newStackNode<Type>(x,top);}template<classType>intStack<Type>::Pop(Type&x){if(IsEmpty())return

0; StackNode<Type>*p=top;top=top->link;x=p->data;

deletep;

return1;}

template<classType>intStack<Type>::GetTop(Type&x){if(IsEmpty())return0;x=top->data;return1;}

表達(dá)式求值一個(gè)表達(dá)式由操作數(shù)(亦稱(chēng)運(yùn)算對(duì)象)、操作符

(亦稱(chēng)運(yùn)算符)和分界符組成。算術(shù)表達(dá)式有三種表示：中綴(infix)表示

<操作數(shù)><操作符><操作數(shù)>，如A+B；前綴(prefix)表示

<操作符><操作數(shù)><操作數(shù)>，如+AB；后綴(postfix)表示

<操作數(shù)><操作數(shù)><操作符>，如AB+；表達(dá)式的中綴表示

表達(dá)式中相鄰兩個(gè)操作符的計(jì)算次序?yàn)椋簝?yōu)先級(jí)高的先計(jì)算；優(yōu)先級(jí)相同的自左向右計(jì)算；當(dāng)使用括號(hào)時(shí)從最內(nèi)層括號(hào)開(kāi)始計(jì)算。C++中操作符的優(yōu)先級(jí)

優(yōu)先級(jí)

操作符

1 單目+、-、！

2 *、/、% 3 +、-

4 <、<=、>、>=5==、!= 6 && 7 || 一般表達(dá)式的操作符有4種類(lèi)型：算術(shù)操作符如雙目操作符（+、-、*、/和%）以及單目操作符（+、-）。關(guān)系操作符包括<、<=、==、!=、>=、>。這些操作符主要用于比較。邏輯操作符如與(&&)、或(||)、非(!)。括號(hào)‘(’和‘)’它們的作用是改變運(yùn)算順序。

中綴表達(dá)式中各個(gè)算術(shù)操作符的優(yōu)先級(jí)isp叫做棧內(nèi)(instackpriority)優(yōu)先數(shù)icp叫做棧外(incomingpriority)優(yōu)先數(shù)。操作符優(yōu)先數(shù)相等的情況只出現(xiàn)在括號(hào)配對(duì)或棧底的‘=’號(hào)與輸入流最后的‘=’號(hào)配對(duì)時(shí)。上面討論的+、-為雙目運(yùn)算符，如為單目運(yùn)算符，編程實(shí)現(xiàn)時(shí)，可在前面加上0而轉(zhuǎn)化為雙目運(yùn)算符。如在+、-的前一個(gè)字符(跳過(guò)空格,當(dāng)前一個(gè)字符不是運(yùn)算符時(shí)用‘0’表示)為‘=’或‘(’，則為單目運(yùn)算符。中綴算術(shù)表達(dá)式求值中綴算術(shù)表達(dá)式求值使用兩個(gè)棧，操作符棧OPTR(operator)，操作數(shù)棧OPND(operand)，對(duì)中綴表達(dá)式求值的一般規(guī)則：(1)建立并初始化OPTR棧和OPND棧，然后在OPTR棧中壓入一個(gè)‘=’。(2)從輸入流獲取一字符ch,并跳過(guò)空格及回車(chē)。(3)取出OPTR的棧頂OPTR_top。(4)當(dāng)OPTR_top!=‘=’或ch!=‘=’時(shí),循環(huán)執(zhí)行以下工作,否則結(jié)束算法。此時(shí)在OPND棧的棧頂?shù)玫竭\(yùn)算結(jié)果。

while(OPTR_top!=‘=’

||ch!=‘=’){

①若ch不是操作符，則將字符放回輸入流(cin.putback)，讀操作數(shù)newoperand并進(jìn)OPND棧，并讀入下一字符(跳過(guò)空格及回車(chē))送入ch；②若ch是操作符，比較icp(ch)的優(yōu)先級(jí)和isp(OPTR_top)的優(yōu)先級(jí)：

若isp(OPTR_top)<icp(ch)，則ch進(jìn)OPTR棧，從中綴表達(dá)式取下一字符(跳過(guò)空格及回車(chē))送入ch；

若isp(OPTR_top)>icp(ch)，則從OPND棧退出a2和a1，從OPTR棧退出θ,形成運(yùn)算指令(a1)θ(a2)，結(jié)果進(jìn)OPND棧；

若isp(OPTR_top)==icp(ch)且ch==

“)”，則從OPTR棧退出棧頂?shù)摹?”，對(duì)消括號(hào)，然后從中綴表達(dá)式取下一字符送入ch。

③取出OPTR的棧頂OPTR_top。}2023/2/5443．2棧的應(yīng)用舉例

例1數(shù)制轉(zhuǎn)換問(wèn)題

輾轉(zhuǎn)相除法如圖所示：

算法描述：

#defineLength10voidconversion(intN，intr){intS[Length],top;//定義一個(gè)順序棧

intx;top=-1;//初始化棧

while(N){S[++top]=N%r;//余數(shù)入棧

N=N/r;

//商作為被除數(shù)繼續(xù)

}while(top!=-1)

//出棧輸出

{x=s[top--];printf(“%d”,x);}}算法描述#defineLength10voidconversion(intN，intr){

intS[Length],top;//定義一個(gè)順序棧

intx;top=-1;//初始化

while(N)

{

S[++top]=N%r;

//余數(shù)入棧

N=N/r;//商作為被除數(shù)繼續(xù)

}

while(top!=-1)//出棧輸出

{

x=s[top--];

printf(“%d”,x);}}例2檢查一個(gè)表達(dá)式中的括號(hào)是否配對(duì)#defineSTRLEN255Boolcheak()

{charS[STRLEN];//初始化字符棧

inttop=-1;

charch=’#’

while(ch!=’\n’)//重復(fù)從鍵盤(pán)讀字符，直到讀到回車(chē)換行符

{scanf(“%c”,&ch);

switch(ch)//根據(jù)讀入字符的不同情況分別處理

{case’(’:

{S[++top=ch;break;}

例2續(xù)case’[’://ch是’(’或’[’時(shí)，入棧

{S[++top=ch;break;}case’)’://處理ch=’)’時(shí)的情況

{if(S[top]==’(’)top--;

elseif(S[top]==’[’)returnERROR;break;

}case’]’://處理ch=’]’時(shí)的情況

{if(S[top]==’[’)top--;

elseif(S[top]==’(’)returnERROR;break;

}}if(top<0)returnTRUE;//?？諘r(shí)返回真，否則返回假

elsereturnERROR;}//算法結(jié)束例3表達(dá)式求值算法

OperandTypeExpressionEvaluate()//從鍵盤(pán)輸入中綴表達(dá)式，計(jì)算其值InitStack(OPTR);Push(OPTR,‘#’);//初始化運(yùn)算符棧InitStack(OPND);//初始化操作數(shù)ch=getchar();while(ch!=‘#‘&&GetTop(OPTR)!=‘#‘)//逐個(gè)讀字符ch且不等于#

{if(!in(ch,OP))

Push(OPND,ch);//不是運(yùn)算符入操作數(shù)棧

else{switch()//是運(yùn)算符時(shí)分別做不同處理

{case‘<‘: //ch的優(yōu)先級(jí)高于棧頂運(yùn)算符的優(yōu)先級(jí)

{Push(OPTR,ch);break;}例3續(xù)case‘=’://ch的優(yōu)先級(jí)等于棧頂運(yùn)算符的優(yōu)先級(jí)

{Pop(OPTR,c);breck;}case‘>’://ch的優(yōu)先級(jí)低于棧頂運(yùn)算符的優(yōu)先級(jí)

{Pop(OPTR,theta);

Pop(OPND,x);Pop(OPND,y);//彈出兩個(gè)操作數(shù)Push(OPND,Operate(x,theta,y);//計(jì)算、入操作數(shù)棧

}ch=getchar();//讀下一個(gè)字符ch

}

Pop(OPND,x);returnx;//返回結(jié)果

}//算法結(jié)束2023/2/550例4、后綴表達(dá)式求值。

OperandTypeexprEvaluatel(charA[])

//本函數(shù)返回由后綴表達(dá)式A表示的表達(dá)式運(yùn)算結(jié)果{InitStack(S);ch=*A++;while(ch!=’#’){if(!In(ch,OP)Push(S,ch);//讀入的字符是操作數(shù)時(shí)入棧

else//是運(yùn)算符，取出兩個(gè)操作數(shù)

{Pop(S,x);Pop(S,y);switch(ch)//對(duì)兩個(gè)操作數(shù)進(jìn)行相應(yīng)計(jì)算

{case’+’

：c=a+b;break;case’-’

：c=a-b;break;case’*’：c=a*b;break;case’/’：c=a/b;break;case’%’：c=a%b;break;}

Push(S,c);//計(jì)算結(jié)果入棧

}ch=*A++;

//讀下一個(gè)字符

}Pop(S,c);returnc;

//

返回結(jié)果

}

//算法結(jié)束2023/2/551例5、利用棧實(shí)現(xiàn)遞歸函數(shù)計(jì)算n!

設(shè)f(n)=n!,求f(n)可以遞歸地定義為：

f(n)=1

n=0時(shí)//遞歸終止條件

f（n）=n*f(n-1)n>0時(shí)//遞歸步驟遞歸函數(shù)：

intfact(intn) {if(n==0)return1; elsereturn(n*fact(n-1)); }2023/2/552例:利用迭代實(shí)現(xiàn)遞歸函數(shù)計(jì)算n!

Intfact(intn,stack<int>&s){While(n>1)s.puch(n--)Intresult=1;Intval;While(s.pop(val))result=result*val;Return}2023/2/553例6

漢諾塔問(wèn)題算法

voidhanoi(intn,charx,chary,charz)//將x柱上n個(gè)盤(pán)子借助y柱移到z柱上

{if(n==1)move(x,1,z);//將x柱上編號(hào)為1的盤(pán)子移動(dòng)到z柱上

else{hanio(n-1,x,z,y);//將x柱上的n-1個(gè)盤(pán)子移動(dòng)到y(tǒng)柱上

move(x,n,z);//將x柱上編號(hào)為n的盤(pán)子移動(dòng)到z上

hanio(n-1,y,x,z);//將y柱上的n-1個(gè)盤(pán)子移動(dòng)到z柱上

}}Section2

Queue隊(duì)列(

Queue)定義隊(duì)列是只允許在一端刪除，在另一端插入的順序表允許刪除的一端叫做隊(duì)頭(front)，允許插入的一端叫做隊(duì)尾(rear)。特性先進(jìn)先出(FIFO,FirstInFirstOut)a0

a1

a2

an-1frontrearADTQueue{

數(shù)據(jù)對(duì)象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

約定其中a1

端為隊(duì)列頭，an

端為隊(duì)列尾基本操作：隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義}

ADTQueue隊(duì)列的基本操作：InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&x)ClearQueue(&Q)DeQueue(&Q,&x)EnQueue(&Q,x)InitQueue(&Q)

操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。

DestroyQueue(&Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：隊(duì)列Q被銷(xiāo)毀，

不再存在。

QueueEmpty(Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：若Q為空隊(duì)列，則

返回TRUE，否則

返回FALSE。

QueueLength(Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：返回Q的元素個(gè)

數(shù)，即隊(duì)列的長(zhǎng)

度。

GetHead(Q,&x)

初始條件：Q為非空隊(duì)列。

操作結(jié)果：用x返回Q的隊(duì)頭

元素。a1a2an……

ClearQueue(&Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：將Q清為空隊(duì)列。

EnQueue(&Q,x)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：插入元素x為Q的

新的隊(duì)尾元素。a1a2anx……

DeQueue(&Q,&x)

初始條件：Q為非空隊(duì)列。

操作結(jié)果：刪除Q的隊(duì)頭元

素，并用x返回

其值。a1a2an……

循環(huán)隊(duì)列

(CircularQueue)隊(duì)列的進(jìn)隊(duì)和出隊(duì)(C語(yǔ)言版)

frontrear空隊(duì)列frontrearA進(jìn)隊(duì)AfrontrearB進(jìn)隊(duì)ABfrontrearC,D進(jìn)隊(duì)ABCDfrontrearA退隊(duì)BCDfrontrearB退隊(duì)CDfrontrearE,F,G進(jìn)隊(duì)CDEFGCDEFGfrontrearH進(jìn)隊(duì),溢出隊(duì)列的進(jìn)隊(duì)和出隊(duì)原則

進(jìn)隊(duì)時(shí)將新元素按

rear指示位置加入再將隊(duì)尾指針先進(jìn)一rear=rear+1。

出隊(duì)時(shí)將下標(biāo)為

front的元素取出,再將隊(duì)頭指針先進(jìn)一front=front+1。

隊(duì)滿(mǎn)時(shí)再進(jìn)隊(duì)將溢出出錯(cuò)；隊(duì)空時(shí)再出隊(duì)將隊(duì)空處理。解決辦法之一：將隊(duì)列元素存放數(shù)組首尾相接，形成循環(huán)(環(huán)形)隊(duì)列。

01234567front01234567front01234567frontrearAABCrearrear空隊(duì)列A進(jìn)隊(duì)B,C進(jìn)隊(duì)0123456701234567A退隊(duì)B退隊(duì)01234567D,E,F,G,H,I進(jìn)隊(duì)frontBCrearAfrontBCrearfrontCrearDEFGHI隊(duì)列存放數(shù)組被當(dāng)作首尾相接的表處理。隊(duì)頭、隊(duì)尾指針加1時(shí)從maxSize-1直接進(jìn)到0，可用語(yǔ)言的取模(余數(shù))運(yùn)算實(shí)現(xiàn)。隊(duì)頭指針進(jìn)1:front=(front+1)%maxSize;隊(duì)尾指針進(jìn)1:rear=(rear+1)%maxSize;隊(duì)列初始化：front=rear=0;隊(duì)空條件：front

==

rear;隊(duì)滿(mǎn)條件：(rear+1)%maxSize==front

循環(huán)隊(duì)列(CircularQueue)#defineMAXQSIZE100//最大隊(duì)列長(zhǎng)度

typedefstruct{

QElemType*base;//動(dòng)態(tài)分配存儲(chǔ)空間

intfront;//頭指針，若隊(duì)列不空，

//指向隊(duì)列頭元素

intrear;//尾指針，若隊(duì)列不空，指向

//隊(duì)列尾元素的下一個(gè)位置

}SqQueue;循環(huán)隊(duì)列——順序映象

StatusInitQueue(SqQueue&Q){//構(gòu)造一個(gè)空隊(duì)列QQ.base=(ElemType*)malloc

(MAXQSIZE*sizeof(ElemType));

if(!Q.base)exit(OVERFLOW);//存儲(chǔ)分配失敗

Q.front=Q.rear=0;

returnOK;

}StatusEnQueue(SqQueue&Q,ElemTypee){//插入元素e為Q的新的隊(duì)尾元素

if((Q.rear+1)%MAXQSIZE==Q.front)

returnERROR;//隊(duì)列滿(mǎn)

Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;

returnOK;}

StatusDeQueue(SqQueue&Q,ElemType&e){

//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，

//用e返回其值，并返回OK;否則返回ERRORif(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];

Q.front=(Q.front+1)%MAXQSIZE;

returnOK;}隊(duì)列的進(jìn)隊(duì)和出隊(duì)(C++語(yǔ)言版)

frontrear空隊(duì)列frontrearA進(jìn)隊(duì)AfrontrearB進(jìn)隊(duì)ABfrontrearC,D進(jìn)隊(duì)ABCDfrontrearA退隊(duì)BCDfrontrearB退隊(duì)CDfrontrearE,F,G進(jìn)隊(duì)CDEFGCDEFGfrontrearH進(jìn)隊(duì),溢出隊(duì)列的進(jìn)隊(duì)和出隊(duì)原則

進(jìn)隊(duì)時(shí)隊(duì)尾指針先進(jìn)一rear=rear+1，

再將新元素按

rear指示位置加入。

出隊(duì)時(shí)隊(duì)頭指針先進(jìn)一front=front+1，再將下標(biāo)為

front的元素取出。

隊(duì)滿(mǎn)時(shí)再進(jìn)隊(duì)將溢出出錯(cuò)；隊(duì)空時(shí)再出隊(duì)將隊(duì)空處理。解決辦法之一：將隊(duì)列元素存放數(shù)組首尾相接，形成循環(huán)(環(huán)形)隊(duì)列。

隊(duì)列存放數(shù)組被當(dāng)作首尾相接的表處理。隊(duì)頭、隊(duì)尾指針加1時(shí)從maxSize-1直接進(jìn)到0，可用語(yǔ)言的取模(余數(shù))運(yùn)算實(shí)現(xiàn)。隊(duì)頭指針進(jìn)1:front=(front+1)%maxSize;隊(duì)尾指針進(jìn)1:rear=(rear+1)%maxSize;隊(duì)列初始化：front=rear=0;隊(duì)空條件：front

==

rear;隊(duì)滿(mǎn)條件：(rear+1)%maxSize==front

循環(huán)隊(duì)列(CircularQueue)01234567front01234567front01234567frontrearAABCrearrear空隊(duì)列A進(jìn)隊(duì)B,C進(jìn)隊(duì)0123456701234567A退隊(duì)B退隊(duì)01234567D,E,F,G,H進(jìn)隊(duì)frontBCrearAfrontBCrearfrontCrearDEFGHtemplate<classType>classQueue{ private:

intrear,front;

Type*elements;

intmaxSize;public:Queue(intsz=10);~Queue(){delete[]elements;

}

intEnQueue(Typex);

intDeQueue(Type&x);

intGetFront(Type&x);

voidMakeEmpty(){

front=rear;

}

intIsEmpty()const

{returnfront==rear;}

intIsFull()const{return(rear+1)%maxSize==front;}

intLength()const{return(rear-front+maxSize)%maxSize;}}template<classType>Queue<Type>::Queue(intsz){front=0;rear=0;maxSize=sz;elements=newType[maxSize]; }template<classType>intQueue<Type>::EnQueue(Typex){if(IsFull())return0;

rear=(rear+1)%MaxSize; elements[rear]=x;return1; }template<classType>intQueue<Type>::DeQueue(Type&x){if(IsEmpty())return

0; front=(front+1)%MaxSize;

x=elements[front];

return1;}template<classType>intQueue<Type>::GetFront(Type&x){if(IsEmpty())return0; x=elements[(front+1)%MaxSize];Return1;}隊(duì)列的鏈接表示—鏈?zhǔn)疥?duì)列

(C++語(yǔ)言版)

隊(duì)頭在鏈頭，隊(duì)尾在鏈尾。鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無(wú)隊(duì)滿(mǎn)問(wèn)題，但有隊(duì)空問(wèn)題。隊(duì)空條件為front==NULLfrontreartemplate<classType>classQueue;template<classType>classQueueNode{ friendclassQueue<Type>;private:

Typedata; QueueNode<Type>*link;public:QueueNode(Typed,QueueNode<Type>*l=NULL){data=d;link=l;}};

template<classType>classQueue{private:

QueueNode<Type>*front,*rear;public:Queue(){rear=NULL;front=NULL;}

~Queue();

voidEnQueue(Typex);intDeQueue(Type&x);

intGetFront(Type&x);

voidMakeEmpty();//實(shí)現(xiàn)與~Queue()同

intIsEmpty()const

{returnfront==NULL;

}

};

template<classType>Queue<Type>::~Queue(){QueueNode<Type>*p;

while(front!=NULL){p=front;front=front->link;

deletep;}}template<classType>voidQueue<Type>::EnQueue(Typex){if(front==NULL)front=rear=newQueueNode<Type>(x);

else{rear->link=newQueueNode<Type>(x);

rear=rear->link;

}}template<classType>intQueue<Type>::DeQueue(Type

&x){

if(IsEmpty())return0;QueueNode<Type>*p=front; front=front->link;x=p->data;

deletep;

return1; }template<classType>intQueue<Type>::GetFront(Type

&x){if(IsEmpty())return0; x=front->data;return1;}

顯示楊輝三角形的算法VoidyanghuiTriangle(intn){//結(jié)果顯示三角形的第1行—第n行l(wèi)inkQueue<int>q;ints,t;q.InQueue(1);q.InQueue(1);

//存儲(chǔ)第1行的兩個(gè)元素的值

cout<<1<<“\t”<<1;

//顯示第1行for(inti=2;i<=n;

i++){//依次顯示三角形的第2行到第n行

cout<<endl;

q.InQueue(1);

//第i行的第1個(gè)元素值為1cout<<1<<“\t”

//顯示第i行的第1個(gè)元素

q.OutQueue(s);

//取第i-1行的第1個(gè)元素

顯示楊輝三角形的算法（續(xù)）for(intj=2;j<=i;j++){

q.OutQueue(t);

//取第i-1行的第j個(gè)元素q.InQueue(s+t);

//s+t為第i行第j個(gè)元素的值

cout<<s+t<<“\t”;

//顯示第i行第j個(gè)元素的值

s=t:}q.InQueue(1);//第i行第i+1個(gè)元素的值為1

cout<<1;

//顯示第i行第i+1個(gè)元素的值}

cout<<endl;

}

Section3

String串的定義n(n>=0)個(gè)字符的有限序列S=‘a(chǎn)1,a2,……,an’

串名:s

串值:ai(1<=i<=n)

串長(zhǎng):n術(shù)語(yǔ)空串n=0的串子串串中若干相鄰字符組成的子序列主串包含子串的串空格串僅含有空格字符的串(n不為0)串相等設(shè)s1=‘a(chǎn)11,…,an1’s2=‘a(chǎn)12,…,an2’

若n1=n2且ai1=ai2（1<=i<=n1)

則s1=s2

串的抽象數(shù)據(jù)類(lèi)型ADTString{

數(shù)據(jù)對(duì)象：D＝{ai|ai∈CharacterSet,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}基本操作:

StrAssign(&T,chars)

StrCopy(&T,S)

DestroyString(&S)

StrEmpty(S)

StrCompare(S,T)

StrLength(S)

Concat(&T,S1,S2)SubString(&Sub,S,pos,len)Index(S,T,pos)Replace(&S,T,V)StrInsert(&S,pos,T)StrDelete(&S,pos,len)ClearString(&S)}ADTString

StrAssign(&T,chars)

初始條件：chars是字符串常量

操作結(jié)果：把chars賦為T(mén)的值

StrCopy(&T,S)

初始條件：串S存在

操作結(jié)果：由串S復(fù)制得串T

DestroyString(&S)

初始條件：串S存在

操作結(jié)果：串S被銷(xiāo)毀

StrEmpty(S)

始條件：串S存在

操作結(jié)果：若S為空串，則返回

TRUE，否則返回

FALSE

表示空串，空串的長(zhǎng)度為零

StrCompare(S,T)

初始條件：串S和T存在

操作結(jié)果：若ST，則返回值

0

若ST，則返回值

0

若ST，則返回值

0例如：StrCompare(data,state)<0StrCompare(cat,case)>0

StrLength(S)

初始條件：串S存在

操作結(jié)果：返回S的元素個(gè)數(shù)，

稱(chēng)為串的長(zhǎng)度

Concat(&T,S1,S2)

初始條件：串S1和S2存在

操作結(jié)果：用T返回由S1和S2

聯(lián)接而成的新串例如：

Concate(T,man,kind)

求得T=mankind

SubString(&Sub,S,pos,len)初始條件：

串S存在，1≤pos≤StrLength(S)

且0≤len≤StrLength(S)-pos+1操作結(jié)果：

用Sub返回串S的第pos個(gè)字符起長(zhǎng)度為len的子串例如：

SubString(sub,commander,4,3)

求得sub=manSubString(sub,commander,1,9)求得sub=commanderSubString(sub,commander,9,1)求得sub=r子串為“串”中的一個(gè)字符子序列SubString(sub,commander,4,7)sub=?SubString(sub,beijing,7,2)=?sub=?SubString(student,5,0)=起始位置和子串長(zhǎng)度之間存在約束關(guān)系長(zhǎng)度為0的子串為“合法”串

Index(S,T,pos)

初始條件：串S和T存在，T是非空串，

1≤pos≤StrLength(S)

操作結(jié)果：若主串S中存在和串T值

相同的子串,則返回它在主

串S中第pos個(gè)

字符之后第一次出現(xiàn)的位

置；否則函數(shù)值為0

假設(shè)S=abcaabcaaabc,T=bca

Index(S,T,1)=2Index(S,T,3)=6Index(S,T,8)=0

“子串在主串中的位置”意指子串中的第一個(gè)字符在主串中的位序Replace(&S,T,V)

初始條件：串S,T和V均已存在，

且T是非空串

操作結(jié)果：用V替換主串S中出現(xiàn)

的所有與（模式串）T

相等的不重疊的子串假設(shè)S=abcaabcaaabca，T=bca若V=

x，則經(jīng)置換后得到

S=axaxaax若V=bc，則經(jīng)置換后得到

S=abcabcaabc

StrInsert(&S,pos,T)

初始條件：串S和T存在，

1≤pos≤StrLength(S)＋1

操作結(jié)果：在串S的第pos個(gè)字符之前插入串T例如：S=chater，T=rac，則執(zhí)行StrInsert(S,4,T)之后得到

S=character

StrDelete(&S,pos,len)

初始條件：串S存在

1≤pos≤StrLength(S)-len+1

操作結(jié)果：從串S中刪除第pos個(gè)字符

起長(zhǎng)度為len的子串

ClearString(&S)

初始條件：串S存在

操作結(jié)果：將S清為空串

對(duì)于串的基本操作集可以有不同的定義方法，在使用高級(jí)程序設(shè)計(jì)語(yǔ)言中的串類(lèi)型時(shí)，應(yīng)以該語(yǔ)言的參考手冊(cè)為準(zhǔn)。

gets(str)輸入一個(gè)串；

puts(str)

輸出一個(gè)串；

strcat(str1,str2)串聯(lián)接函數(shù)；

strcpy(str1,str2,k)串復(fù)制函數(shù)；

strcmp(str1,str2)串比較函數(shù)；

strlen(str)求串長(zhǎng)函數(shù)；例如：C語(yǔ)言函數(shù)庫(kù)中提供下列串處理函數(shù)：在上述抽象數(shù)據(jù)類(lèi)型定義的13種操作中串賦值StrAssign、等六種操作串復(fù)制Strcopy、構(gòu)成串類(lèi)型串比較StrCompare、的最小操作求串長(zhǎng)StrLength、子集串聯(lián)接Concat求子串SubString

例如，可利用串比較、求串長(zhǎng)和求子串等操作實(shí)現(xiàn)定位函數(shù)Index(S,T,pos)。

StrCompare(SubString(S,i,StrLength(T)),T)?

0

S串T串

T串iposn-m+1算法的基本思想為：intIndex(StringS,StringT,intpos){

//T為非空串。若主串S中第pos個(gè)字符之后存在與T相等的子串，則返回第一個(gè)這樣的子串在S中的位置，否則返回0

if(pos>0){n=StrLength(S);m=StrLength(T);i=pos;

while(i<=n-m+1){

SubString(sub,S,i,m);

if(StrCompare(sub,T)!=0)++i;

else

returni;

}//while

}//if

return0;//S中不存在與T相等的子串}//Index

串的邏輯結(jié)構(gòu)和線(xiàn)性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對(duì)象約束為字符集。

串的基本操作和線(xiàn)性表有很大差別。

在線(xiàn)性表的基本操作中，大多以“單個(gè)元素”作為操作對(duì)象；在串的基本操作中，通常以“串的整體”作為操作對(duì)象。

在程序設(shè)計(jì)語(yǔ)言中，串只是作為輸入或輸出的常量出現(xiàn)，則只需存儲(chǔ)此串的串值，即字符序列即可。但在多數(shù)非數(shù)值處理的程序中，串也以變量的形式出現(xiàn)。串的表示和實(shí)現(xiàn)一、串的定長(zhǎng)順序存儲(chǔ)表示二、串的堆分配存儲(chǔ)表示三、串的塊鏈存儲(chǔ)表示

#defineMAXSTRLEN255//用戶(hù)可在255以?xún)?nèi)定義最大串長(zhǎng)

typedef

unsignedcharSstring[MAXSTRLEN+1];//0號(hào)單元存放串的長(zhǎng)度一、串的定長(zhǎng)順序存儲(chǔ)表示

按這種串的表示方法實(shí)現(xiàn)的串的運(yùn)算時(shí)，其基本操作為

“字符序列的復(fù)制”。

串的實(shí)際長(zhǎng)度可在這個(gè)予定義長(zhǎng)度的范圍內(nèi)隨意設(shè)定，超過(guò)予定義長(zhǎng)度的串值則被舍去，稱(chēng)之為“截?cái)唷薄Ｌ攸c(diǎn):

typedefstruct{char*ch;

//若是非空串，則按串長(zhǎng)分配存儲(chǔ)區(qū)，

//否則ch為NULL

intlength;//串長(zhǎng)度

}HString;二、串的堆分配存儲(chǔ)表示

通常，C語(yǔ)言中提供的串類(lèi)型就是以這種存儲(chǔ)方式實(shí)現(xiàn)的。系統(tǒng)利用函數(shù)malloc()和free()進(jìn)行串值空間的動(dòng)態(tài)管理，為每一個(gè)新產(chǎn)生的串分配一個(gè)存儲(chǔ)區(qū)，稱(chēng)串值共享的存儲(chǔ)空間為“堆”。

C語(yǔ)言中的串以一個(gè)空字符為結(jié)束符，串長(zhǎng)是一個(gè)隱含值。

這類(lèi)串操作實(shí)現(xiàn)的算法為：先為新生成的串分配一個(gè)存儲(chǔ)空間，然后進(jìn)行串值的復(fù)制。三、串的塊鏈存儲(chǔ)表示也可用鏈表來(lái)存儲(chǔ)串值，由于串的數(shù)據(jù)元素是一個(gè)字符，它只有8位二進(jìn)制數(shù)，因此用鏈表存儲(chǔ)時(shí)，通常一個(gè)結(jié)點(diǎn)中存放的不是一個(gè)字符，而是一個(gè)子串。存儲(chǔ)密度

=數(shù)據(jù)元素所占存儲(chǔ)位實(shí)際分配的存儲(chǔ)位

#defineCHUNKSIZE80

//可由用戶(hù)定義的塊大小

typedefstructChunk{

//

結(jié)點(diǎn)結(jié)構(gòu)

charch[CUNKSIZE];

structChunk*next;

}Chunk;

typedefstruct{//串的鏈表結(jié)構(gòu)

Chunk*head,*tail;//串的頭和尾指針

intcurlen;//串的當(dāng)前長(zhǎng)度

}LString;

這是串的一種重要操作，很多軟件，若有“編輯”菜單項(xiàng)的話(huà)，則其中必有“查找”子菜單項(xiàng)。串的模式匹配算法初始條件：串S和T存在，T是非空串，

1≤pos≤StrLength(S)。操作結(jié)果：若主串S中存在和串T值相同的子串返回它在主串S中第pos個(gè)字符之后第一次出

現(xiàn)的位置；否則函數(shù)值為0。首先，回憶一下串匹配(查找)的定義:INDEX(S,T,pos)

下面討論以定長(zhǎng)順序結(jié)構(gòu)表示串時(shí)的幾種算法。一、簡(jiǎn)單算法二、首尾匹配算法三、KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法intIndex(SStringS,SStringT,intpos){

//返回子串T在主串S中第pos個(gè)字符之后的位置。若不存在，

//則函數(shù)值為0。其中，T非空，1≤pos≤StrLength(S)。

i=pos;j=1;

while(i<=S[0]&&j<=T[0]){

if(S[i]==T[j]){++i;++j;}//繼續(xù)比較后繼字符

else

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

//指針后退重新開(kāi)始匹配

}

if(j>T[0])returni-T[0];

elsereturn0;}//Index一、