數(shù)據(jù)結(jié)構(gòu)第3章棧和隊列

棧和隊列1、棧和隊列的定義及特點；

2、棧的順序存儲表示；

3、隊列的順序存儲表示；隊列的鏈接存儲表示；

4、棧和隊列的應用舉例。教學內(nèi)容限定僅在表尾進行插入或刪除操作。3.1棧3.1.1抽象數(shù)據(jù)類型棧的定義棧的定義a1a2an-1an…棧頂(top)棧底(bottom)出棧進棧棧底元素

棧頂元素

棧：線性表

后進先出(LIFO結(jié)構(gòu))。棧的抽象數(shù)據(jù)類型的定義

ADTStack{數(shù)據(jù)對象：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

端為棧底?；静僮鳎篒nitStack(&S)

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

S。DestroyStack(&S)

初始條件：棧S已存在。

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

GetTop(S,&e)

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

操作結(jié)果：用e

返回S的棧頂元素。StackEmpty(S)

初始條件：棧S已存在。

操作結(jié)果：若棧S為空棧，則返回TRUE，否則FALSE。

StackLength(S)

初始條件：棧S已存在。

操作結(jié)果：返回S的元素個數(shù)，即棧的長度。

ClearStack(&S)

初始條件：棧S已存在。

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

Push(&S,e)

初始條件：棧S已存在。

操作結(jié)果：插入元素e

為新的棧頂元素。

Pop(&S,&e)

初始條件：棧S已存在且非空。操作結(jié)果：刪除S的棧頂元素，并用e

返回其值。

}ADTStack3.1.2棧的表示和實現(xiàn)

順序棧

順序棧：利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時附設(shè)指針top指示棧頂元素在順序棧中的位置。

topbaseAtopBtopCtopDtopEtop空棧

若再進行元素“出?！辈僮?，將產(chǎn)生“下溢”。

top棧滿

若再進行元素“入?！辈僮鳎瑢a(chǎn)生“上溢”。

#defineLIST_INIT_SIZE100//線性表存儲空間的初始分配量

#defineLISTINCREMENT10//線性表存儲空間的分配增量

typedef

struct{

ElemType*elem;//數(shù)組指針，指示線性表的基地址

intlength;//當前長度

int

listsize;//當前分配的存儲容量(以sizeof(ElemType)為單位)

}SqList;SelemType*base;//棧底指針，它始終指向棧底的位置。

SelemType*top;//棧頂指針。int

stacksize;//當前分配的?？墒褂玫淖畲蟠鎯θ萘?。

Sqstack;注：base的值為NULL，表明棧結(jié)構(gòu)不存在。

#defineSTACK_INIT_SIZE100//棧存儲空間的初始分配量

#defineSTACKINCREMENT10//棧存儲空間的分配增量

棧的基本操作在順序棧中的實現(xiàn)#definemaxs9;main(){int

stack[maxs];

inttop=0;

while(top<maxs){scanf(“%d”,&stack[top]);top++;}

inte;e=stack[top-1];

while(top>0)e=stack[top-1];top-=1;}InitStack

PushPoptop12toptoptop2topGetTop

21StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemtype));if(!S.base)exit(OVERFLOW);S.top=S.base;

S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStackStatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINcrement)*sizeof(SElemtype));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}//PushStatusGetTop(SqStackS,SElemType&e){if(S.top==S.base)returnERROR;e=*(S.top–1);returnOK;}//GetTop

StatusPop(SqStack&S,SElemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}//Pop棧頂指針鏈棧an注意:鏈棧中指針的方向an-1a1…^▲3.2棧的應用舉例

3.2.1數(shù)制轉(zhuǎn)換

十進制數(shù)N

和其他d

進制數(shù)M

的轉(zhuǎn)換是計算機實現(xiàn)計算的基本問題，其解決方法很多，其中一個簡單算法是逐次除以基數(shù)d

取余法，它基于下列原理：

N=(Ndivd)*d+Nmodd

具體作法為：首先用N

除以d，得到的余數(shù)是d

進制數(shù)M的最低位M0，接著以前一步得到的商作為被除數(shù)，再除以d，得到的余數(shù)是d

進制數(shù)M

的次最低位M1，依次類推，直到商為0時得到的余數(shù)是M

的最高位Ms（假定M

共有s+1位）。例：

(1348)10=(2504)8，其運算過程如下：

N

Ndiv8Nmod8134816841682102125202計算順序輸出順序bottomtop

4052top1348168void

conversion

(){

intstack[4];

inttop=0;

intN;

scanf(“%d”,N);while(N){

stack[top]=N%8;top++;N=N/8;}for(top=top-1;top>=0;top--)

printf(“%d”,stack[top]);}21top2top0top2504InitStack(S)Push(S,N%S)While(!Stackempty(S)){

Pop(S,e);

printf(“%d”,e);}3.2.2括號匹配的檢驗假設(shè)表達式中允許括號嵌套，則檢驗括號是否匹配的方法可用“期待的急迫程度”這個概念來描述。例：

[

(

[

]

[

]

)

]12345678bottomtop[([toptoptoptoptoptoptoptop[可能出現(xiàn)的不匹配的情況：盼來的右括號不是所“期待”的；到來的是“不速之客”（右括號多）；到結(jié)束也未盼來所“期待”的括號（左括號多）。算法的設(shè)計思想：1）凡出現(xiàn)左括號，則進棧；

2）凡出現(xiàn)右括號，首先檢查棧是否空。

若?？眨瑒t表明該“右括號”多余；

否則和棧頂元素比較，

若相匹配，則“左括號出?！?，

否則表明不匹配。

3）表達式檢驗結(jié)束時，

若?？?，則表明表達式中匹配正確，

否則表明“左括號”有多余的。

3.2.3行編輯程序功能：接受用戶從終端輸入的數(shù)據(jù)并存入用戶的數(shù)據(jù)區(qū)。

bottomtoptoptop接受一個字符即存入數(shù)據(jù)區(qū)。（差！難糾錯。）設(shè)一個輸入緩沖區(qū)，接受完一行字符后再存入用戶的數(shù)據(jù)區(qū)。（好！可及時糾錯。）做法

糾錯辦法

#

退格符，表示前一個字符無效。

@

退行符，表示整行字符均無效。

例：接受的字符為：

whli##ile

outch@putch

實際有效的為：

while

putch

whltopitoptoptopitopletoptopvoidLineEdit(){

InitStack(S);

ch=getchar();while(ch!=EOF){//EOF為全文結(jié)束符

while(ch!=EOF&&ch!='\n'){switch(ch){case'#':Pop(S,c);break;case‘@’:ClearStack(S);break;//重置S為空棧

default:Push(S,ch);break;}

ch=getchar();//從終端接收下一個字符

}

將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)；

ClearStack(S);//重置S為空棧

if(ch!=EOF)ch=getchar();}

DestroyStack(S);}3.2.4迷宮求解

出口入口

0123456789012345678911122232333424252616151431415152536364657585868788

窮舉求解求迷宮路徑算法的基本思想：

若當前位置“可通”，則納入路徑，繼續(xù)前進；

若當前位置“不可通”，則后退，換方向（按東南西北

的順序）繼續(xù)探索；

若四周“均無通路”，則將當前位置從路徑中刪除出去。3.2.5表達式求值

運算規(guī)則先乘除，后加減；從左算到右；先括號內(nèi)，后括號外；例：求表達式4+23-10/5

的值。計算順序為：4+23-10/5=4+6-10/5=10-10/5=10-2=8

操作數(shù)或結(jié)果運算符#4+2

3

610-10/582▲

“四染色”定理是計算機科學中著名定理之一，即可以用不多于四種顏色對地圖著色，使相鄰的行政區(qū)域不重色。補充：地圖四染色問題

算法思想：從第一號行政區(qū)開始逐一染色，每一個區(qū)域逐次用顏色1、2、3、4進行試探。若當前所取的色數(shù)與周圍已染色的行政區(qū)不重色，則用棧記下該行政區(qū)的色數(shù)，否則依次用下一色數(shù)進行試探；若出現(xiàn)用1至4色均與相鄰區(qū)域發(fā)生重色，則需退?；厮?，修改當前棧頂?shù)纳珨?shù)，再進行試探。直至所有行政區(qū)域都已分配合適的顏色。例：已知7個行政區(qū)域地圖，對其進行染色。12345671011111010000101001100101011010110101101100700000001234123456712234431(3)(1)(2)(4)(5)(6)(7)3243作業(yè)：3.1、3.2、3.3、3.4、3.18選擇題部分

1、若入棧序列是a,b,c,d,e，則不可能的出棧序列是（）。（A）

edcba（B）decba（C）dceab

（D）abcde

2、判定一個棧ST(最多元素為m0)為空的條件是（）。

（A）ST.top!=0（B）ST.top=0

（C）ST.top!=m0

（D）ST.top=m0

3、判定一個棧ST(最多元素為m0)為滿的條件是（）。

（A）ST.top!=0（B）ST.top=0

（C）ST.top!=m0

（D）ST.top=m0

3.3棧與遞歸的實現(xiàn)

遞歸：一個直接調(diào)用自己或通過一系列的調(diào)用語句間接地調(diào)用自己的函數(shù)，稱做遞歸函數(shù)。例：階乘函數(shù)相應的C語言函數(shù)是：floatfact(int

n){floats;if(n==0)

s=1;else

s=n*fact(n-1);return(s);}若求5!，則有main(){printf(“5!=%f\n”,fact(5));}

當在一個函數(shù)的運行期間調(diào)用另一個函數(shù)時，在運行該被調(diào)用函數(shù)之前，需先完成三件事：將實參等傳遞給被調(diào)用函數(shù)，保存返回地址（入棧）；

為被調(diào)用函數(shù)的局部變量分配存儲區(qū)；

將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應該完成：

保存被調(diào)函數(shù)的計算結(jié)果；

釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)；按被調(diào)函數(shù)保存的返回地址（出棧）將控制轉(zhuǎn)移到調(diào)用函數(shù)。多個函數(shù)嵌套調(diào)用的規(guī)則是：后調(diào)用先返回。此時的內(nèi)存管理實行“棧式管理”。floatfact(int

n){floats;if(n==0)

s=1;else

s=n*fact(n-1);return(s);}遞歸調(diào)用執(zhí)行過程：主函數(shù)main()Printf(fact(5))第一層調(diào)用n=5s=5*fact(4)第二層調(diào)用n=4s=4*fact(3)第三層調(diào)用n=3s=3*fact(2)第四層調(diào)用n=2s=2*fact(1)第五層調(diào)用n=1s=1*fact(0)fact(5)=120輸出s=120.00第六層調(diào)用n=0s=1fact(4)=24fact(3)=6fact(2)=2fact(1)=1fact(0)=1主a

5a4a3a2a1aprintf(“5!=%f\n”,fact(5));basefloatfact(int

n){floats;if(n==0)

s=1;else

s=n*fact(n-1);return(s);}floatfact(int

n){floats;if(n==0)

s=1;else

s=n*fact(n-1);return(s);}floatfact(int

n){floats;if(n==0)

s=1;else

s=n*fact(n-1);return(s);}floatfact(int

n){floats;if(n==0)

s=1;else

s=n*fact(n-1);return(s);}floatfact(int

n){floats;if(n==0)

s=1;else

s=n*fact(n-1);return(s);}n=5n=4n=3n=2n=1n=0限定在表的一端插入、另一端刪除。3.4隊列

3.4.1抽象數(shù)據(jù)類型隊列的定義隊列的定義隊列：線性表

(queue)先進先出(FIFO結(jié)構(gòu))。隊尾隊頭下圖是隊列的示意圖：

a1

a2

…

an出隊入隊隊頭隊尾當隊列中沒有元素時稱為空隊列。隊列的抽象數(shù)據(jù)類型的定義

ADTQueue{

數(shù)據(jù)對象：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

端為隊列頭，an

端為隊列尾?；静僮鳎?/p>

InitQueue(&Q)

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

DestroyQueue(&Q)

初始條件：隊列Q已存在。

操作結(jié)果：隊列Q被銷毀，不再存在。QueueEmpty(Q)

初始條件：隊列Q已存在。

操作結(jié)果：若Q為空隊列，則返回TRUE，否則返回FALSE。QueueLength(Q)

初始條件：隊列Q已存在。操作結(jié)果：返回Q的元素個數(shù)，即隊列的長度。GetHead(Q,&e)

初始條件：Q為非空隊列。操作結(jié)果：用e

返回Q的隊頭元素。

ClearQueue(&Q)

初始條件：隊列Q已存在。

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

EnQueue(&Q,e)

初始條件：隊列Q已存在。操作結(jié)果：插入元素e

為Q的新的隊尾元素。

DeQueue(&Q,&e)

初始條件：Q為非空隊列。

操作結(jié)果：刪除Q的隊頭元素，并用e

返回其值。}ADTQueue雙端隊列限定插入和刪除在表的兩端進行。雙端隊列：線性表

(double-endedqueue)先進先出(FIFO結(jié)構(gòu))。端點1端點2下圖是雙端隊列的示意圖：

a1

a2

…

an出隊入隊端點1端點2出隊入隊輸出受限的雙端隊列：一個端點可插入和刪除，另一個端點僅可插入。

輸入受限的雙端隊列：一個端點可插入和刪除，另一個端點僅可刪除。

▲3.4.2鏈隊列——隊列的鏈式表示和實現(xiàn)

鏈隊列：用鏈表表示的隊列。是限制僅在表頭刪除和表尾插入的單鏈表。一個鏈隊列由一個頭指針和一個尾指針唯一確定。

（因為僅有頭指針不便于在表尾做插入操作）。為了操作的方便，也給鏈隊列添加一個頭結(jié)點，因此，空隊列的判定條件是：頭指針和尾指針都指向頭結(jié)點?！膄rontrearrearfront∧…圖3-12鏈隊列示意圖隊頭隊尾用C語言定義鏈隊列結(jié)構(gòu)如下：typedef

struct

QNode

{QElemtypedata;

struct

QNode*next;}Qnode,*QueuePtr;//定義隊列的結(jié)點typedef

struct

{QueuePtr*front;//隊頭指針

QueuePtr*rear;//隊尾指針}LinkQueue;StatusInitQueue(LinkQueue&Q)

{//構(gòu)造一個空隊列Q

Q.front=Q.rear=(QueuPtr)malloc(sizeof(QNode));

if(!Q.front)exit(OVERFLOW);

//存儲分配失敗

Q.front->next=NULL;

returnOK;

}隊列的基本操作在鏈隊列中的實現(xiàn)：

隊列的初始化：

a1a2a3^Q.frontQ.rear銷毀隊列：

=null=nullStatusDestroQueue(LinkQueue&Q)

{while(Q.front){Q.rear=Q.front->next;

free(Q.front);

Q.front=Q.rear;}returnOK;

}∧rear…front∧x∧y插入操作在鏈隊列中的實現(xiàn)ppStatusEnQueue(LinkQueue&Q,QElemTypee)

{//插入元素e為Q的新的隊尾元素

p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->data=e;p->next=NULL;

Q.rear->next=p;

Q.rear=p;returnOK;

}StatusDeQueue(LinkQueue&Q,QElemType&e)

{if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;

Q.front->next=p->next;

if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;

}∧frontrearyx刪除操作在鏈隊列中的實現(xiàn)p▲p∧填空題部分

1、棧的特點是（），隊列的特點是（）。

2、線性表、棧和隊列都是（）結(jié)構(gòu)，可以在線性表的（）位置插入和刪除元素，棧只能在（）插入和刪除元素，隊列只能在（）插入元素和（）刪除元素。

3、設(shè)棧S和隊列Q的初始狀態(tài)皆為空，元素a1,a2,a3,a4,a5

和a6依次通過一個棧，一個元素出棧后即進入隊列Q，若

6個元素出隊列的順序是a3,a5,a4,a6,a2,a1則棧S至少應該容納(

)個元素。4、若隊列的入隊序列是1,2,3,4，則出隊序列是（）。（A）4,3,2,1（B）1,2,3,4（C）1,4,3,2（D）3,2,4,1作業(yè)3.11、3.123.4.3循環(huán)隊列－隊列的順序表示和實現(xiàn)是限制僅在表頭刪除和表尾插入的順序表。頭尾指針利用一組地址連續(xù)的存儲單元依次存放隊列中的數(shù)據(jù)元素。rearfrontrearfrontJ1

J2

J3

頭、尾指針和隊列元素之間的關(guān)系rearfrontJ3

rearfront在非空隊列里，頭指針始終指向隊頭元素尾指針始終指向隊尾元素的下一位置。因為：隊頭和隊尾的位置是變化的，所以：設(shè)頭、尾指針。

初始化時的初始值均應置為0。入隊，尾指針增1出隊，頭指針增1頭尾指針相等時隊列為空在順序隊列中，當尾指針已經(jīng)指向了隊列的最后一個位置的下一位置時，若再有元素入隊，就會發(fā)生“溢出”。

“假溢出”——隊列的存儲空間未滿，卻發(fā)生了溢出。rearfrontJ1

J2

J3

J4

rearfrontJ3

J4

(1)、平移元素：把元素平移到隊列的首部。效率低。解決“假溢出”的問題有兩種可行的方法：

(2)、將新元素插入到第一個位置上，構(gòu)成循環(huán)隊列，入隊和出隊仍按“先進先出”的原則進行。

操作效率、空間利用率高。rearfrontJ3

J4

frontrearJ3

J4

循環(huán)隊列的三種狀態(tài)：012345frontrear012345J5

J4

J3

frontrear012345J5

J4

J3

J6

J7

J8

front

rear注：僅憑front=rear不能判定隊列是空還是滿。解決辦法：

(1)、另設(shè)一個布爾變量以區(qū)別隊列的空和滿；(2)、少用一個元素的空間，約定入隊前測試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則認為隊滿；

(3)、使用一個計數(shù)器記錄隊列中元素的總數(shù)。#defineMAXQSIZE100//最大隊列長度

typedef

struct{

QElemType*base;//預分配存儲空間基址

intfront;//頭指針，若隊列不空，

//指向隊列頭元素

intrear;//尾指針，若隊列不空，

//指向隊列尾元素的下一個位置

}SqQueue;隊列的順序存儲結(jié)構(gòu)：循環(huán)意義下的加1操作可以描述為：

if(rear+1>MAXQSIZE)rear=0;elserear++;012345J5

J4

J3

rearfront利用模運算可簡化為：rear=(rear+1)%MAXQSIZE

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

(MAXQSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);//存儲分配失敗

Q.front=Q.rear=0;returnOK;}隊列的基本操作在循環(huán)隊列中的實現(xiàn)：

隊列的初始化：

StatusQueueLength(SqQueueQ){//返回隊列Q的元素個數(shù)

return(Q.rear-Q.front);}

StatusQueueLength(SqQueueQ){//返回隊列Q的元素個數(shù)

return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;}求循環(huán)隊列的長度

考慮到循環(huán)隊列frontrearJ3

J4

frontrearJ3

J1

J2

StatusEnQueue(SqQueue&Q,QElemTypee){//插入元素e為Q的新的隊尾元素

Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}StatusEnQueue(SqQueue&Q,QElemTypee){//插入元素e為Q的新的隊尾元素

if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;//隊列滿

Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}插入操作在循環(huán)隊列中的實現(xiàn)frontrearJ3

J4

J5

rear

StatusDeQueue(SqQueue&Q,ElemType&e){