第三章棧和隊列兩種特殊的線性表回顧線性表 順序存儲的線性表 鏈表表示的線性表特點：插入和刪除操作可以在表的任何位置進行。A123n12nL問題棧（LIFO）——LastInFirstOut隊列（FIFO）——FirstInFirstOut問：對這些數(shù)據(jù)的操作與線性表有哪些相同和不同？答：都是線性結構的數(shù)據(jù)操作方式的差異134N2入口出口LIFO134N2出口入口FIFO3.1棧本節(jié)的主要內容：

1.棧的定義

2.堆棧的表示和實現(xiàn)

3.堆棧的操作方式

4.順序棧和鏈棧的定義及其操作1.棧的抽象數(shù)據(jù)類型定義火車站的調度情況

一個有終結點火車道，每節(jié)車廂進出該車道的規(guī)則應該是怎樣的呢？必須遵循LIFO

原則123進棧出棧棧：一個只能在棧頂進行插入和刪除的線性表，其特征為LIFO

空棧：不含元素的空表

遵循LIFO(lastinfirstout)的線性表。 思考：按此規(guī)則，如果進棧的車廂序列為1，2，3，而且兩側鐵道均為單向行駛道，那么它們出棧的順序會有幾種，分別是怎樣排列的?抽象數(shù)據(jù)類型：

ADTStack{數(shù)據(jù)對象，數(shù)據(jù)關系同線性表

基本操作：

InitStack(&S),DestroyStock(&S),

ClearStack(&S),StackEmpty(S),

StackLength(&S),GetTop(S),Push(&S,e),Pop(&S,&e),

StackTraverse(S,visit())}

棧的表示和實現(xiàn)棧的表示：（1）順序棧：棧的順序存儲

優(yōu)點：處理方便；缺點：數(shù)組大小固定，易造成內存資源的浪費。（2）鏈棧：棧的動態(tài)存儲

優(yōu)點:能動態(tài)改變鏈表的長度，有效利用內存資源；缺點：處理較為復雜。問：TOP的作用是什么？順序棧的表示和實現(xiàn)順序表示#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;

typedef

struct{

SElemType*base;

SElemType*top;

int

stacksize;}SqStack;

其中stacksize表示棧當前可以使用的最大容量。base為棧底，top為棧頂。棧頂指針指向棧頂元素的下一個位置（即下次壓棧時元素所放的位置）順序棧的結構top指向壓棧時下一個元素將要存放的位置。top減一指向彈棧時下一個元素的取值位置。?？盏臈l件：top=base棧滿的條件：top-base>=stacksizetoptopbase空棧base非空非滿棧topABCABCbase滿棧DE基本操作的實現(xiàn)：初始化棧StatusInitStack(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;}//InitStack壓棧:StatusPush(SqStack&S,SElemTypee){//元素e插入到棧中，成為新的棧頂

if(S.top-S.base>=S.stacksize)//棧滿

{newbase=(SElemType*)realloc

(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!newbase)exit(OVERFLOW);elseS.base=newbase;S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT;}//if*S.top++=e;returnOK;}//Push出棧:StatusPop(SqStack&S,SElemType&e){//從棧頂讀取數(shù)據(jù)放入e內，棧中下一元素所在位置成為新的棧頂

if（S.top==S.base）returnERROR;//?？?/p>

e=*--S.top;returnOK;}//Pop注意top的操作順序和值的變化。壓棧：valuetop;top++;

彈棧：top--;top->value;鏈棧的結構和表示定義棧結構Typedef

structstack_node{

Elemtypedata;

structstack_node*next;}LinkStack;LinkStack*stk;問：在這里為什么沒有用到top指針？這樣對棧結構的定義有否影響？1^728stk棧頂棧底鏈棧的操作入棧PUSH()StatusPUSH(LinkStack*stk,Elemtypex){

LinkStack*top; top=malloc(sizeof(LinkStack)); top->data=x; top->next=*stk; *stk=top;}問：在這里top指針的作用是什么？1^8stkxtop1^8stkxtop課堂練習：鏈棧的出棧操作取棧頂元素GETTOP()

3.2棧的應用舉例1.數(shù)制轉換10--〉2，逐步除二，得余取反序用算法實現(xiàn)求任意非負十進制數(shù)的八進制數(shù) 分析：每次除8，余數(shù)壓棧，結束后依次出棧即可

voidconversion(){//非負十進制數(shù)轉化為八進制數(shù)

InitStack(S);

scanf(“%d”,N);while(N){Push(S,N%8);N=N/8;}while（！StackEmpty(s)）{pop(s,e);printf(“%d”,e);}}//conversion2.括號匹配算法{}[]（）的配對問題。

[(5+(2-6)+10)+6]*2（正確）

[(5+(2-6)+10]+6)*2（╳）

((5+2-6)+10)+6)*2（╳）判斷的標準：

方法：見到左括號壓棧，見到右括號彈棧，并和彈出的數(shù)據(jù)配對。編寫算法：假設表達式結束符為#,試寫出判斷表達式是否正確的算法intMatchJudge(){//匹配返回1，不匹配返回0

InitStack(S);

scanf(“%c”,ch);while(ch!=“#”){if(ch==“(”||ch==“[”||ch==“{”)push(s,ch);if(ch==“)”||ch==“]”||ch==“}”）{ifStackEmpty(S)return0; pop(s,e);if(e與ch不匹配)return0;}

scanf(“%c”,ch);}//whileifStackEmpty(s)return1elsereturn0;}//MatchJudge算法：先乘除，后加減，括號先。（從左到右）算符優(yōu)先算法：利用運算優(yōu)先關系的規(guī)定來實現(xiàn)對表達式的編譯或解釋執(zhí)行。（算符優(yōu)先關系參看P53）比較兩個表達式的計算過程：4＋2×15－10/5和4＋2×(15－10)/5分析：如何利用棧實現(xiàn)計算過程？設置兩個工作棧：OPTR(運算符棧)和OPND(操作數(shù)棧)

OPND初始為空，OPTR棧底置“?！?依次讀入表達式中的字符： 操作數(shù)壓OPND棧； 運算符：與OPTR棧頂元素比較優(yōu)先級表達式求值問題OperandType

EvaluateExpression(){//算符優(yōu)先算法求表達式的值

InitStack(OPTR);Push(OPTR,‘＃’)；//OPTR運算符棧

InitStack(OPND);c=getchar();//OPND操作數(shù)棧

while(c!=‘#’||GetTop(OPTR)!=‘#’){ if(!In(c,OP)){Push(OPND,c);c=getchar()}//操作數(shù)入棧OPND elseswitch(Precede(GetTop(OPTR),c)){ case’<’://棧頂運算符優(yōu)先級低

Push(OPTR,c)；c=getchar();break; case’=’://去括號

Pop(OPTR,x);c=getchar();break; case’>’: //退棧并計算結果入棧 Pop(OPTR,theta); Pop(OPND,a);Pop(OPND,b); Push(OPND,Operate(a,theta,b));break; }//switch }//while returnGetTop(OPND);}//EvaluateExpression

表達式的前綴、中綴、后綴表示問題：對a+b的表示有：前綴+ab、中綴a+b、后綴ab+；各種表示方式對如a+b*c運算的優(yōu)先次序的表示： 前綴+a*bc,中綴a+b*c,后綴abc*+編譯中，需要將表達式化成前綴、后綴方式 例如#a+(b+(c/d-e))*f#轉化為后綴的表示方法結果：abcd/e-+f*+課堂練習：寫出a+(b+(c/d-e))*f的前綴、中綴、后綴表示。棧在遞歸調用中的作用遞歸函數(shù)：直接或間接調用自身的函數(shù)。遞歸的應用：遞歸定義的數(shù)學函數(shù)數(shù)據(jù)結構：二叉樹、廣義表，結構本生的遞歸性質用遞歸解決更簡單的問題，如Hanoi塔問題。遞歸調用是一種顯式的自嵌套調用，將大規(guī)模數(shù)據(jù)問題轉化為小規(guī)模數(shù)據(jù)問題，調用時遵循“后調用先返回”的原則。系統(tǒng)在遞歸的實現(xiàn)上實際使用了棧為潛在的工具。3.3棧與遞歸的實現(xiàn)例：漢諾塔問題有XYZ三塔座，X上插有n個直徑不同、由小到大的圓盤。要求借助Y將其全部移到Z上，按照原來的順序疊放。移動規(guī)則：每次移動一個；任何時刻都是小盤在上，大盤在下。分析：當n=1時，直接移動即可；當n>=2時，首先將上面的n-1個圓盤移至Y，第n個放到Z；然后的問題就是n-1個圓盤的問題提示：雖然n-1個圓盤的問題與n個圓盤的問題相同，但規(guī)模變小。XYZ算法：voidhanoi(intn,charx,chary,charz){ if(n==1) move(x,1,z); else{ hanoi(n-1,x,z,y) move(x,n,z); hanoi(n-1,y,x,z) }}問題：遞歸函數(shù)是如何執(zhí)行的，棧在其中的作用是什么？3.4

隊列

隊列：一個只能在隊首進行刪除、隊尾進行插入的線性表，其特征為FIFO(先進先出)。關鍵基本操作：出隊和入隊

抽象數(shù)據(jù)類型：

ADTStack{數(shù)據(jù)對象，數(shù)據(jù)關系同線性表

基本操作：

InitQueue(&Q),DestroyQueue(&Q),

ClearQueue(&Q),QueueEmpty(Q),

QueueLength(&S),GetHead(S),

EnQueue(&Q,e),DeQueue(&S,&e),

QueueTraverse(Q,visit())}隊列的表示和實現(xiàn)鏈式隊列

typedef

struct

Qnode{

QElemTypedata;

struct

Qnode*next;}Qnode,*QueuePtr;

typedef

struct{

QueuePtrfront;

QueuePtrrear;}LinkQueue;課堂練習：鏈隊列的操作入對列、出隊列Q.frontQ.rear^鏈隊列結構入隊列：在隊尾插入P=LinkQueue

malloc(sizeof(Qnode))P->next=NULL;Q.rear->next=p;Q.rear=P;出隊列：在隊頭刪除

r=Q.front->next; Q.front->next=r->next; free(r);Q.frontQ.rear^P順序隊列

#defineMAXQSIZE100

typedef

struct{

QElemType*base;

intfront;

intrear;}SqQueue;

其中base為連續(xù)空間首地址，front為隊首，rear為隊尾。為什么用循環(huán)隊列來實現(xiàn)順序隊列？rearfront空隊front非空非滿隊1rearABCC滿隊DECfront非空非滿隊2Drearrearfront順序隊列的結構——循環(huán)隊列：空隊：初始化隊列時，兩個指針rear＝front＝0入隊：隊尾插入元素，尾指針rear后移出隊：隊頭刪除元素，頭指針