數(shù)據(jù)結(jié)構(gòu)及算法-鏈表及棧課件

3.1棧

3.2棧的應(yīng)用舉例

3.3隊(duì)列第3章棧和隊(duì)列

重點(diǎn):

(1)棧、隊(duì)列的定義、特點(diǎn)、性質(zhì)和應(yīng)用；(2)ADT棧、ADT隊(duì)列的設(shè)計(jì)和實(shí)現(xiàn)以及基本操作及相關(guān)算法。

難點(diǎn):

(1)循環(huán)隊(duì)列中對(duì)邊界條件的處理；(2)分析棧和隊(duì)列在表達(dá)式求值、括號(hào)匹配、數(shù)制轉(zhuǎn)換、迷宮求解中的應(yīng)用實(shí)例，提高利用棧和隊(duì)列解決實(shí)際問題的應(yīng)用水平。本章重點(diǎn)難點(diǎn)

3.1棧

3.2棧的應(yīng)用舉例

3.3隊(duì)列第3章棧和隊(duì)列

3.1棧

3.1.1抽象數(shù)據(jù)類型棧的定義

3.1.2棧的表示和實(shí)現(xiàn)3.1.1抽象數(shù)據(jù)類型棧的定義棧的定義棧(Stack)是一種特殊的線性表，其插入和刪除操作均在表的一端進(jìn)行，是一種運(yùn)算受限的線性表。棧頂(top)是棧中允許插入和刪除的一端。棧底(bottom)是棧頂?shù)牧硪欢?。棧的術(shù)語棧的特點(diǎn)棧的示意圖后進(jìn)先出(LastInFirstOut，簡(jiǎn)稱LIFO)。又稱棧為后進(jìn)先出表(簡(jiǎn)稱LIFO結(jié)構(gòu))。an……a2a1棧底棧頂入棧出棧3.1.1抽象數(shù)據(jù)類型棧的定義

ADTStack{

數(shù)據(jù)對(duì)象：數(shù)據(jù)關(guān)系：

抽象數(shù)據(jù)類型?；静僮鳎?/p>

}ADTStackR1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}約定an

端為棧頂，a1端為棧底。D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}見下頁3.1.1抽象數(shù)據(jù)類型棧的定義InitStack(&S)//初始化棧DestroyStack(&S)//銷毀棧ClearStack(&S)//清空棧StackEmpty(S)//判?？誗tackLength(S)//求棧長(zhǎng)度GetTop(S,&e)//取棧頂元素Push(&S,e)//入棧Pop(&S,&e)//出棧StackTravers(S,visit())//遍歷棧棧的基本操作3.1.1抽象數(shù)據(jù)類型棧的定義

3.1棧

3.1.1抽象數(shù)據(jù)類型棧的定義

3.1.2棧的表示和實(shí)現(xiàn)3.1.2棧的表示和實(shí)現(xiàn)

//-----棧的順序存儲(chǔ)表示-----#defineSTACK_INIT_SIZE100;//存儲(chǔ)空間初始分配量#defineSTACKINCREMENT10;//存儲(chǔ)空間分配增量typedefstruct{

SElemType*base;

//棧底指針

SElemType*top;

//棧頂指針

intstacksize;

//當(dāng)前可使用最大容量

}SqStack;SqStackS;順序棧的C語言實(shí)現(xiàn)3.1.2棧的表示和實(shí)現(xiàn)棧初始化過程演示(1)給棧S申請(qǐng)棧空間(2)設(shè)置基地址S.base和棧頂?shù)刂稴.topS.topS.base(3)設(shè)置棧容量S.stacksize=STACK_INIT_SIZE

StatusInitStack(SqStack&S){

//構(gòu)造一個(gè)空棧SS.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存儲(chǔ)分配失敗

S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}3.1.2棧的表示和實(shí)現(xiàn)棧初始化算法3.1.2棧的表示和實(shí)現(xiàn)入棧操作演示(1)如果棧滿，給棧增加容量abcdef(2)將數(shù)據(jù)存入棧頂位置，棧頂后移一位S.topS.baseeS.top

StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){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;}3.1.2棧的表示和實(shí)現(xiàn)入棧操作演示3.1.2棧的表示和實(shí)現(xiàn)DestroyStack(&S)//銷毀棧ClearStack(&S)//清空棧StackEmpty(S)//判?？誗tackLength(S)//求棧長(zhǎng)度GetTop(S,&e)//取棧頂元素Pop(&S,&e)//出棧StackTravers(S,visit())//遍歷棧其它棧操作討論

TypedefstructSNode{

ElemTypedata;

//數(shù)據(jù)域

structSnode*next;

//鏈域}SNode,*LinkStack;3.1.2棧的表示和實(shí)現(xiàn)鏈棧的C語言類型定義鏈棧的實(shí)現(xiàn)與鏈表的實(shí)現(xiàn)基本相同，頭結(jié)點(diǎn)作為棧頂位置。LinkStack*top;

//棧頂指針I(yè)nitStack(&S)//初始化棧DestroyStack(&S)//銷毀棧ClearStack(&S)//清空棧StackEmpty(S)//判棧空StackLength(S)//求棧長(zhǎng)度GetTop(S,&e)//取棧頂元素Push(&S,e)//入棧Pop(&S,&e)//出棧StackTravers(S,visit())//遍歷棧討論鏈?；静僮鞯膶?shí)現(xiàn)3.1.2棧的表示和實(shí)現(xiàn)3.2棧的應(yīng)用舉例3.2.1數(shù)制轉(zhuǎn)換3.2.2括號(hào)匹配的檢驗(yàn)3.2.3行編輯程序問題3.2.4迷宮求解3.2.5表達(dá)式求值3.2.1數(shù)制轉(zhuǎn)換任何X進(jìn)制數(shù)N轉(zhuǎn)換成Y進(jìn)制數(shù)其結(jié)果都是要化成如下形式。進(jìn)制轉(zhuǎn)換原理：轉(zhuǎn)換的過程就是通過取余運(yùn)算求出a0,a1,…,an，而先求出的是個(gè)位，十位…，與我們寫數(shù)的習(xí)慣先從高位寫正好相反，通過棧先進(jìn)后出的特點(diǎn)，很容易實(shí)現(xiàn)倒過來的過程。過程如下：

NNdiv8Nmod8

13481684

168210

2125

202輸出順序計(jì)算順序3.2.1數(shù)制轉(zhuǎn)換例將10進(jìn)制1346轉(zhuǎn)換成8進(jìn)制voidconversion(){

InitStack(S);

scanf("%d",N);while(N){

Push(S,N%8);N=N/8;}while(!StackEmpty(S)){

Pop(S,e);printf("%d",e);}}//conversion3.2.1數(shù)制轉(zhuǎn)換10進(jìn)制數(shù)N轉(zhuǎn)換成8進(jìn)制的算法

一個(gè)表達(dá)式中，包含三種括號(hào)“(”和“)”，“[”和“]”和“{”和“}”，這三種括號(hào)可以按任意的合法次序使用。設(shè)計(jì)算法檢驗(yàn)表達(dá)式中所使用括號(hào)的合法性。3.2.2括號(hào)匹配的檢驗(yàn)問題描述

討論：如果第一次遇到的右括號(hào)是“]”，那么前面出現(xiàn)的左括號(hào)有什么特點(diǎn)。問題討論

結(jié)論：如果第一次遇到的右括號(hào)是“]”，那么前面出現(xiàn)的左括號(hào)最后一個(gè)必然是“[”，否則不合法。算法過程3.2.2括號(hào)匹配的檢驗(yàn)當(dāng)遇到左括號(hào)時(shí)，進(jìn)棧，遇到右括號(hào)時(shí)出棧；(2)當(dāng)遇到某一個(gè)右括號(hào)時(shí)，棧已空，說明到目前為止，右括號(hào)多于左括號(hào)；(3)從棧中彈出的左括號(hào)與當(dāng)前檢驗(yàn)的右括號(hào)類型不同，說明出現(xiàn)了括號(hào)交叉情況；(4)算術(shù)表達(dá)式輸入完畢，但棧中還有沒有匹配的左括號(hào)，說明左括號(hào)多于右括號(hào)。Statuscheck(){charch;InitStack(S);while((ch=getchar())!=‘#'){switch(ch){

case(ch=='('||ch=='['||ch=='{'):Push(S,ch);break;case(ch==')'):if(StackEmpty(S))retrunFALSE;else{Pop(S,e);if(e!='(')returnFALSE;}break;括號(hào)匹配檢驗(yàn)算法3.2.2括號(hào)匹配的檢驗(yàn)case(ch==‘]'):if(StackEmpty(S))retrunFALSE;else{Pop(S,e);if(e!=‘[')returnFALSE;}break;…………default:break;

}

}if(StackEmpty(S))returnTRUE;elsereturnFALSE;}括號(hào)匹配檢驗(yàn)算法3.2.2括號(hào)匹配的檢驗(yàn)3.2.3行編輯程序問題設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，并假設(shè)“#”為退格符，“@”為退行符。在用戶輸入一行的過程中，允許用戶輸入出差錯(cuò)，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。解決辦法問題描述假設(shè)從終端接受了這樣兩行字符：

whli##ilr#e（s#*s)

outcha@putchar(*s=#++);則實(shí)際有效的是下列兩行：

while(*s)putchar(*s++);例3.2.3行編輯程序問題

DestroyStack(S);}voidLineEdit(){//利用字符棧S，從終端接收一行并傳送至調(diào)//用過程的數(shù)據(jù)區(qū)

InitStack(S);ch=getchar();………….3.2.3行編輯程序問題行編輯問題算法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();//從終端接收下一個(gè)字符

ClearStack(S);//重置S為空棧if(ch!=EOF)ch=getchar();棧中字符傳送至調(diào)用過程的數(shù)據(jù)區(qū)；3.2.3行編輯程序問題行編輯問題算法入口出口3.2.4迷宮求解如圖表示一個(gè)迷宮，有一個(gè)入口，一個(gè)出口，從一個(gè)位置可以向4個(gè)方向(東、南、西、北)走，白方塊表示通道，藍(lán)方塊表示墻，求從入口到出口的路徑。問題描述12345678123456783.2.4迷宮求解求解方法“窮舉求解”方法：從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個(gè)方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，需要一個(gè)后進(jìn)先出的結(jié)構(gòu)來保存從入口到當(dāng)前位置的路徑。因此，求解迷宮通路算法需要應(yīng)用“棧”來保存當(dāng)前路徑。3.2.4迷宮求解四周墻壁解決辦法如圖012345678901234567891234567812345678當(dāng)前位置：在搜索過程中某一時(shí)刻所在圖中某個(gè)方塊位置。當(dāng)前位置可通：未承走到過的通道塊，該方塊既不在當(dāng)前路徑上，也不是曾經(jīng)納入過路徑的通道塊。3.2.4迷宮求解01234567890123456789下一位置：當(dāng)前位置四周4個(gè)方向(東、南、西、北)上相鄰的方塊。當(dāng)前位置(3,3)(3,2)(2,2)(1,2)(1,1)當(dāng)前路徑3.2.4迷宮求解算法思想(1)若當(dāng)前位置“可通”，則納入“當(dāng)前路徑”，并繼續(xù)朝“下一位置”探索，即切換“下一位置”為“當(dāng)前位置”，如此重復(fù)直至到達(dá)出口；(2)若當(dāng)前位置“不可通”，則應(yīng)順著“來向”退回到“前一通道塊”，然后朝著除了“來向”之外的其他方向繼續(xù)探索；(3)若該通道塊的四周4個(gè)方塊均“不可通”，則應(yīng)從“當(dāng)前路徑”上刪除該通道塊。設(shè)定當(dāng)前位置的初值為入口位置；

do｛若當(dāng)前位置可通，則｛將當(dāng)前位置插入棧頂；若該位置是出口位置，則算法結(jié)束；否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；}否則{…………….}｝while(棧不空）；迷宮路徑求解算法3.2.4迷宮求解若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當(dāng)前位置為:沿順時(shí)針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則

{刪去棧頂位置；若棧不空，則重新測(cè)試新的棧頂位置，直至找到一個(gè)可通的相鄰塊或出棧至棧空；}若?？眨瑒t表明迷宮沒有通路。迷宮路徑求解算法3.2.4迷宮求解012345678901234567893.2.4迷宮求解求解過程示例3.2.5表達(dá)式求值一個(gè)表達(dá)式由操作數(shù)(operand)、運(yùn)算符(operator)、界限符(delimiter)組成。寫出“算符優(yōu)先法”求值的算法。問題描述例求3*(2+3*5)+6的值設(shè)置兩個(gè)棧，一個(gè)存操作數(shù)，棧名為OPND，一個(gè)存操作符，棧名為OPTR棧。

(1)首先置操作數(shù)棧為空，表達(dá)式起始符#為運(yùn)算符棧的棧底元素；

(2)依次讀入表達(dá)式中每個(gè)字符，若是操作數(shù)則進(jìn)OPND棧，若是運(yùn)算符則和OPTR棧的棧頂運(yùn)算符比較優(yōu)先權(quán)后作相應(yīng)操作，直到整個(gè)表達(dá)式操作完畢。3.2.5表達(dá)式求值算法求解過程

(1)若棧頂運(yùn)算符小于輸入運(yùn)算符，輸入運(yùn)算符進(jìn)棧OPTR；

(2)若棧頂運(yùn)算符等于輸入運(yùn)算符（只有棧頂是“（”，輸入是“）”，或者棧頂是“#”，輸入是“#）”兩種情況，分別去除一對(duì)括號(hào)，或結(jié)束。

(3)若棧頂運(yùn)算符大于輸入運(yùn)算符，彈出棧頂運(yùn)算符，從OPND中彈出兩個(gè)操作數(shù)與彈出運(yùn)算符計(jì)算后再存入OPND棧，繼續(xù)。3.2.5表達(dá)式求值算法求解過程OperandTypeEvaluateExpression(){initStack(OPTR);Push(OPTR,’#’);initStack(OPND);c=getchar();while(c!=‘#’)||GetTop(OPTR)!=‘#’){

if(!In(c,OP)){Push((OPND,c);c=getchar();}elseswitch(Precede(GetTop(OPTR),c)){3.2.5表達(dá)式求值表達(dá)式求值算法case‘<‘:Push(OPTR,c);c=getchar();break;case‘=’:Pop(OPTR,x);c=getchar;break;3.2.5表達(dá)式求值

case‘>’:Pop(OPTR,theta);Pop(OPND,a);Pop(OPND,b);Push(OPND,Operate(a,theta,b));break;}//switch語句結(jié)束}//while語句結(jié)束return(GetTop(OPND));}//算法結(jié)束表達(dá)式求值算法

3.1棧

3.2棧的應(yīng)用舉例

3.3隊(duì)列第3章棧和隊(duì)列隊(duì)列的定義3.4.1

抽象數(shù)據(jù)類型隊(duì)列的定義隊(duì)列(Queue)——是一種運(yùn)算受限的特殊的線性表，它只允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除。隊(duì)尾(rear)是隊(duì)列中允許插入的一端。隊(duì)頭(front)是隊(duì)列中允許刪除的一端。隊(duì)列的術(shù)語隊(duì)列的特點(diǎn)隊(duì)列示意圖3.4.1

抽象數(shù)據(jù)類型隊(duì)列的定義a1a2a3……an隊(duì)頭隊(duì)尾出隊(duì)出隊(duì)

先進(jìn)先出(FirstInFirstOut，簡(jiǎn)稱FIFO)。又稱隊(duì)列為先進(jìn)先出表。

ADTQueue{

數(shù)據(jù)對(duì)象：數(shù)據(jù)關(guān)系：

抽象數(shù)據(jù)類型?；静僮鳎?/p>

}ADTQueue見下頁3.1.1抽象數(shù)據(jù)類型棧的定義D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}約定其中a1

端為隊(duì)列頭，an

端為隊(duì)列尾InitQueue(&Q)//初始化隊(duì)列DestroyQueue(&Q)//銷毀隊(duì)列QueueEmpty(Q)//判隊(duì)列是否空QueueLength(Q)//求隊(duì)列長(zhǎng)度GetHead(Q,&e)//取隊(duì)頭元素ClearQueue(&Q)//清空隊(duì)列EnQueue(&Q,e)//入隊(duì)列DeQueue(&Q,&e)//出隊(duì)列QueueTravers(Q,visit())//遍歷隊(duì)列隊(duì)列的基本操作3.1.1抽象數(shù)據(jù)類型棧的定義3.4.2鏈隊(duì)列

typedefstructQNode{//結(jié)點(diǎn)類型

QElemTypedata;structQNode*next;}QNode,*QueuePtr;鏈隊(duì)列結(jié)點(diǎn)實(shí)現(xiàn)typedefstruct{//鏈隊(duì)列類型

QueuePtrfront;//隊(duì)頭指針

QueuePtrrear;//隊(duì)尾指針}LinkQueue;鏈隊(duì)列數(shù)據(jù)類型實(shí)現(xiàn)Q.frontQ.rear帶頭結(jié)點(diǎn)的鏈隊(duì)列示意圖3.4.2鏈隊(duì)列^頭結(jié)點(diǎn)空隊(duì)列a1a2……anQ.frontQ.rear

StatusInitQueue(LinkQueue&Q){

//構(gòu)造一個(gè)空隊(duì)列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);

//存儲(chǔ)分配失敗

Q.front->next=NULL;returnOK;}3.4.2鏈隊(duì)列帶頭結(jié)點(diǎn)的鏈隊(duì)列初始化

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

p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);//存儲(chǔ)分配失敗

p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}3.4.2鏈隊(duì)列帶頭結(jié)點(diǎn)的鏈隊(duì)列入隊(duì)算法

StatusDeQueue(LinkQueue&Q,QElemType&e){//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，

//用e返回其值，并返回OK；否則返回ERRORif(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;}3.4.2鏈隊(duì)列帶頭結(jié)點(diǎn)的鏈隊(duì)列出隊(duì)算法DestroyQueue(&Q)//銷毀隊(duì)列QueueEmpty(Q)//判隊(duì)列是否空QueueLength(Q)//求隊(duì)列長(zhǎng)度GetHead(Q,&e)//取隊(duì)頭元素ClearQueue(&Q)//清空隊(duì)列QueueTravers(Q,visit())//遍歷隊(duì)列3.4.2鏈隊(duì)列帶頭結(jié)點(diǎn)的鏈隊(duì)列其它操作討論3.4.3循環(huán)隊(duì)列

循環(huán)隊(duì)列屬于順序隊(duì)列的一種，討論在采用一般順序隊(duì)列時(shí)出現(xiàn)的問題。

順序隊(duì)列討論43210空隊(duì)列AA入隊(duì)BAB入隊(duì)EDCBAC,D,E相繼入隊(duì)Sq.rearSq.frontSq.rearSq.frontSq.rearSq.frontSq.rearSq.frontEDCBA隊(duì)列滿EDCBA被刪除(出隊(duì))EDCB被刪除討論結(jié)論：在采用一般順序隊(duì)列時(shí)出現(xiàn)假上溢現(xiàn)象？C,D,E相繼被刪除順序隊(duì)列討論3.4.3循環(huán)隊(duì)列43210Sq.rearSq.frontSq.frontSq.rearSq.rearSq.frontSq.frontSq.rear循環(huán)隊(duì)列示意圖3.4.3循環(huán)隊(duì)列01234CDESq.frontSq.rear01234CDESq.frontSq.rearFF入隊(duì)01234CDESq.frontSq.rearFGG入隊(duì)3.4.3循環(huán)隊(duì)列#defineMAXQSIZE100//最大隊(duì)列長(zhǎng)度

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

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

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

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

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

}SqQueue;SqQueueSq;鏈隊(duì)列數(shù)據(jù)類型實(shí)現(xiàn)循環(huán)隊(duì)列是順序隊(duì)列的一種特例，它是把順序隊(duì)列構(gòu)造成一個(gè)首尾相連的循環(huán)表。指針和隊(duì)列元素之間關(guān)系不變。3.4.3循環(huán)隊(duì)列循環(huán)隊(duì)列的定義01maxsize-1Sq.frontSq.rear……3.4.3循環(huán)隊(duì)列循環(huán)隊(duì)列空狀態(tài)和滿狀態(tài)的討論討論結(jié)論：循環(huán)隊(duì)列空狀態(tài)和滿狀態(tài)都滿足Q.front=Q.rear01234CDESq.frontSq.rearFG滿隊(duì)列01234Sq.frontSq.rear空隊(duì)列(1)另設(shè)一個(gè)標(biāo)志區(qū)別隊(duì)列是空還是滿；3.4.3循環(huán)隊(duì)列循環(huán)隊(duì)列空狀態(tài)和滿狀態(tài)的判別

例如：設(shè)一個(gè)變量count用來記錄隊(duì)列中元素個(gè)數(shù)，當(dāng)count==0時(shí)隊(duì)列為空，當(dāng)count=MAXQSIZE時(shí)隊(duì)列為滿。(2)隊(duì)滿條件：以隊(duì)頭指針在隊(duì)列尾指針的下一位置作為隊(duì)列呈滿狀態(tài)的標(biāo)志，犧牲一個(gè)存儲(chǔ)空間；3.4.3