數(shù)據(jù)結構C語言版第三章 棧和隊列課件

第三章棧和隊列本章學習兩種特殊的線性數(shù)據(jù)結構，它們特殊在定義的操作不同，即插入和刪除操作只能在線性表的兩端進行。只能在一端進行的——棧分別在兩端進行的——隊列棧的定義及邏輯結構棧的順序存儲結構及操作實現(xiàn)棧的鏈式存儲結構及操作實現(xiàn)棧的應用舉例隊列的定義及邏輯結構循環(huán)隊列存儲結構及操作實現(xiàn)隊列的鏈式存儲結構及操作實現(xiàn)內(nèi)容提要：目標、要求：

要求通過棧和隊列的結構特性、基本操作及兩種存儲結構上基本操作的實現(xiàn)掌握棧和隊列的不同點，面對不同的應用能夠進行正確的選擇和應用。重點、難點：棧的結構及特性，假溢出。循環(huán)隊列的基本操作實現(xiàn)、算法描述與算法分析方法。一、棧的邏輯結構1、棧(stack):是一種特殊的線性表(數(shù)據(jù)元素之間的關系是線性關系）、其插入、刪除只能在表的一端進行，另一端固定不動。3.1棧的邏輯結構及操作棧頂（top）：插入、刪除的一端棧底（bottom）：固定不動的一端入棧（push）:又稱壓入，即插入一個元素出棧（POP）:又稱彈出，即刪除一個元素3.1棧的邏輯結構及操作

假設棧S=(a1，a2，…，an)，則稱a1為棧底元素，an為棧頂元素。棧中元素按a1，a2，…，an的次序進棧，退棧的第一個元素應為棧頂元素。換句話說，棧的修改是按后進先出的原則進行的(如右圖(a)所示)。因此，棧又稱為后進先出(LastInFirstOut)的線性表(簡稱LIFO結構)，它的這個特點可用右圖(b)所示的鐵路調(diào)度站形象地表示?！璦1a2an進棧棧頂棧底(a)出棧進棧(b)出棧3.1棧的邏輯結構及操作2、棧特點：由于限制了插入刪除只能在一端進行，那么元素的操作順序有“先進后出”或“先進先出”的特點。(LastInFirstOut-LIFOFistInLastOut-FILO)3.1棧的邏輯結構及操作例題：假設有A,B,C,D四個元素，它們?nèi)霔５拇涡驗锳BCD,出棧次序任意，請問不可能得到下面哪些出棧次序？（1）ABCD（2）DBCA（3）CDBA（4）CBAD（5）ACBD（6）DBAC（7）ADCB（8）CABD（2）DBCA（6）DBAC（8）CABD3.1棧的邏輯結構及操作二、棧的ADT描述：ADTStack{

datastructure:D={ai|ai∈D0i=1,2,…….n>=0}R={N}N={<ai-1,ai>|ai-1,ai∈D0

,i=2,3,4,……..}D0是某個數(shù)據(jù)對象Operations:Initiate(s);Push(s);Pop(s);Get-top(s);Empty(s);Current-size(s);Clear(s);}ADTStack3.2棧的順序存儲表示及操作的實現(xiàn)basetopbasetopAABCEDbasetopABbasetop若base=null棧結構不存在若top初始值=base為空棧top=top+1入棧top=top-1出棧棧頂指針始終指向棧頂元素的下一位置3.2棧的順序存儲表示及操作的實現(xiàn)3、虛擬實現(xiàn)#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10Typedefstruct{SelemType*base;//在棧構造之前和銷毀之后，base=nullSelemType*top;//棧頂指針intstacksize;

}Sqstack;3.2棧的順序存儲表示及操作的實現(xiàn)二、棧順序存儲結構下各運算的虛擬實現(xiàn)棧采用順序存儲結構時，棧底在哪端，算法有區(qū)別，我們以棧底在地址低端為例來實現(xiàn)各種操作。1、初始化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;}O(1)3.2棧的順序存儲表示及操作的實現(xiàn)2、入棧//在棧頂插入新元素，要考慮上溢的處理

StatusPust(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;}*s.top=es.top=s.top+1O(1)3.2棧的順序存儲表示及操作的實現(xiàn)StatusPop(Sqstack&s,SElemTypee){if(s.top==s.base)

returnerror;

e=*--s.top;returnok;}s.top=s.top-1e=s.topO(1)3、出棧//若棧不空，則刪除s的棧頂元素，用e返回其值3.2棧的順序存儲表示及操作的實現(xiàn)StatusStackEmpty(Sqstacks){if(s.top==s.base)

returnture;elsereturnfalse;}時間復雜性O(1)4、判斷棧是否空3.3棧的單鏈式存儲表示及操作的實現(xiàn)一、棧的鏈式存儲結構1、存儲方式：同一般線性表的單鏈式存儲結構完全相同，但是應該確定鏈表的哪端對應于棧頂，如果鏈表尾作為棧頂，則入、出棧操作的時間復雜性為O(n)。∧an…a2a1Ltop如果鏈表頭作為棧頂，則入、出棧操作時間復雜性為O(1)，所以，把鏈表表頭作為棧頂?！腶1…an-1antop

3.3棧的單鏈式存儲表示及操作的實現(xiàn)datanext…∧棧底棧頂2、特點：減小溢出，提高空間利用率，只有系統(tǒng)沒有空間了，才會溢出。3.3棧的單鏈式存儲表示及操作的實現(xiàn)if(s→next==NULL)returnOVERFLOW;//下溢elsep=s→next;e=p→data;s→next=p→next;free(p);3、出棧//刪除棧頂元素，并用e返回其值時間復雜性O(1)ps∧3.3棧的單鏈式存儲表示及操作的實現(xiàn)if(s→next==NULL)returnOk;4、判斷棧是否空時間復雜性O(1)順序棧與鏈棧的比較：順序棧需要固定的長度，存在溢出問題，但鏈棧的每個元素都有指針域，增加了空間的開銷3.3棧的應用舉例1、數(shù)制轉換

十進制數(shù)N和其他d進制數(shù)的轉換是計算機實現(xiàn)計算的基本問題，其解決方法很多，其中一個簡單算法基于下列原理：N=(Ndivd)Xd+Nmodd(其中：div為整除運算，mod為求余運算)例如：(1348)10--(2504)8，其運算過程如下：NNdiv8Nmod8134816841682102l25202例把十進制數(shù)159轉換成八進制數(shù)(159)10=(237)81598198280237余7余3余2toptop7top73top7323.3棧的應用舉例——多進制輸出voidconversion()

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

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

{Pop(S,e);printf("%d',e);}}取余運算整除運算3.3棧的應用舉例當計算機接受了第一個括號后，它期待著與其匹配的第八個括號的出現(xiàn)，然而等來的卻是第二個括號，此時第一個括號“[”只能暫時靠邊，而迫切等待與第二個括號相匹配的、第七個括號“)”的出現(xiàn)，類似地，因等來的是第三個括號“[”，其期待匹配的程度較第二個括號更急迫，則第二個括號也只能靠邊，讓位于第三個括號，顯然第二個括號的期待急迫性高于第一個括號；在接受了第四個括號之后，第三個括號的期待得到滿足，消解之后，第二個括號的期待匹配就成為當前最急迫的任務了，……，依次類推?？梢?，這個處理過程恰與棧的特點相吻合。由此，在算法中設置一個棧，每讀入一個括號，若是右括號，則或者使置于棧頂?shù)淖罴逼鹊钠诖靡韵猓蛘呤遣缓戏ǖ那闆r；若是左括號，則作為一個新的更急迫的期待壓入棧中，自然使原有的在棧中的所有未消解的期待的急迫性都降了一級。另外，在算法的開始和結束時，棧都應該是空的。此算法作為習題完成。3.3棧的應用舉例#:退格符@:退行符\n:換行符EOF:結束符3.3棧的應用舉例3、行編輯程序設立一個輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行輸入用戶數(shù)據(jù)區(qū)。假設輸入這樣兩行字符：Whli##ilr#e(s#*s)outcha@putchar(*s=#++);則實際有效的是下列兩行：While(*s)Putchar(*s++)voidLineEdit(){InitStack(S);ch=getchar();while(ch!=EOF){while(ch!=EOF&&ch!='\n'){switch(ch){case'#':Pop(S,c);break;case'@':ClearStack(S);break;default:push(s,ch);}ch=getchar();}ClearStack(S);if(ch!=EOF)ch=getchar();}DestroyStack(S);}

3.3棧的應用舉例4、回文游戲：順讀與逆讀字符串一樣（不含空格）dadtop1.讀入字符串2.去掉空格（原串）3.壓入棧4.原串字符與出棧字符依次比較若不等，非回文若直到?？斩枷嗟龋匚淖址骸癿adamimadam”3.3棧的應用舉例

任何表達式都是由操作數(shù)(operand)、運算符(operator)和界限符(delimiter)組成的，我們稱它們?yōu)閱卧~。一般地，操作數(shù)既可以是常數(shù)也可以是被說明為變量或常量的標識符；為了簡單期間,表達式只含加、減、乘、除等四種運算符。我們把運算符和界限符統(tǒng)稱為算符，它們構成的集合命名為OP。根據(jù)上述三條運算規(guī)則，在運算的每一步中，任意兩個相繼出現(xiàn)的算符θ1和θ2之間的優(yōu)先關系至多是下面三種關系之一；

θ1<θ2θ1=θ2θ1>θ23.3棧的應用舉例5、表達式求值θ2θ1+-*/()#+>><<<>>_>><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=3.3棧的應用舉例3.3棧的應用舉例3.3棧的應用舉例——表達式求值

棧應用舉例-表達式求值operatetypeEvaluteExpression(){INITSTACK(OPTR);PUSH(OPTR,”#”);INITSTACK(OPND);c=getchar();GetTop(OPTR,&e);while(c!=“#”||e！=“#”）{if(!IN(c,OP)){PUSH(OPND,c);c=getchar();}elseswitch(precede(GetTop(OPTR,e),c)){case‘<’:PUSH(OPTR,c);c=getchar();break;case‘=‘:Pop(OPTR,c);c=getchar();break；case‘>‘:Pop(OPTR,t);Pop(OPND,b);Pop(OPND,a);PUSH(OPND,operate(a,t,b));}}returnGETTOP(OPND,e);}OPTR:存放操作符的棧OPND：存放操作數(shù)的棧θ1：棧頂?shù)牟僮鞣?：當前的操作符OP：操作符集合01234567890123456789出口入口3.3棧的應用舉例6、迷宮求解3.3棧的應用舉例通常用的是“窮舉求解”的方法11

112

222

232

133

134

424

125

126

416

315

314

43$$$$$$$$3.3棧的應用舉例求迷宮路徑算法的基本思想：1、若當前位置“可通”，則納入路徑，繼續(xù)前進2、若當前位置“不可通”，則后退，換向探索3、若四周均“不可通”，則從路徑中刪除3.3棧的應用舉例求迷宮中一條從入口到出口的路徑的算法：：設定當前位置的初值為入口位置；

do｛

若當前位置可通，

則｛將當前位置插入棧頂；

若該位置是出口位置，則算法結束；否則切換當前位置的東鄰方塊為新的當前位置；｝

否則{若棧不空且棧頂位置尚有其他方向未被探索，則設定新的當前位置為:沿順時針方向旋轉找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則｛刪去棧頂位置；//從路徑中刪去該通道塊

若棧不空，則重新測試新的棧頂位置，

直至找到一個可通的相鄰塊或出棧至?？?；｝

｝｝while(棧不空）；是否通？設當前值為入口位置將當前位值插入棧頂當前位值是出口？YY結束，退出NN當前位置向下移四個方向均試過？退出棧頂元素NY順時針旋轉切換到下一個位置

且?？?？無通路，退出Y置當前位置為新位置3.3棧的應用舉例TowerofHanoi問題每次只能移一個圓盤問題描述：有A,B,C三個塔座，A上套有n個直徑不同的圓盤，按直徑從小到大疊放，形如寶塔,編號1,2,3……n。要求將n個圓盤從A移到C，疊放順序不變，移動過程中遵循下列原則：圓盤可在三個塔座上任意移動任何時刻，每個塔座上不能將大盤壓到小盤上3.4棧與遞歸的實現(xiàn)——漢諾塔解決方法：n=1時，直接把圓盤從A移到Cn>1時，先把上面n-1個圓盤從A移到B,然后將n號盤從A移到C,再將n-1個盤從B移到C。即把求解n個圓盤的Hanoi問題轉化為求解n-1個圓盤的Hanoi問題，依次類推，直至轉化成只有一個圓盤的Hanoi問題算法：執(zhí)行情況：遞歸工作棧保存內(nèi)容：形參n,x,y,z和返回地址返回地址用行編號表示nxyz返回地址3.4棧與遞歸的實現(xiàn)——漢諾塔3.4棧與遞歸的實現(xiàn)——漢諾塔main(){intm;printf("Inputnumberofdisks”);scanf("%d",&m);printf(”Steps:%3ddisks”,m);hanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC1233ABC03ABC02ACB63ABC02ACB61ABC6ABC3ABC02ACB6本節(jié)內(nèi)容：隊列的邏輯結構定義及操作隊列的順序存儲表示及操作實現(xiàn)隊列的鏈式存儲表示及操作實現(xiàn)一、隊列的邏輯結構1、隊列(Queue):是一種特殊的線性表(數(shù)據(jù)元素之間的關系是線性關系）、其插入、刪除分別在表的兩端進行，一端只能插入，另一端只能刪除。3.5隊列的邏輯結構及操作隊首（front）：進行刪除的一端隊尾（rear）：進行插入的一端入隊:在隊尾插入一個元素出隊:在隊首刪除一個元素a1a2a3…an隊頭隊尾出隊列進隊列2、隊列的特點：由于限制了插入、刪除分別在兩端進行，那么元素的操作順序有“先進先出”或“后進后出”的特點。(Firstinfirstout——FIFOLastinlastout——LILO)

3.5隊列的邏輯結構及操作3、隊列的操作：（1）隊列初始化Iniqueue(Q):隊列置空。（2）入隊Enqueue(Q):即在隊尾插入一個元素。（3）出隊Dlqueue(Q):即在隊首刪除一個元素。（4）取隊首元素Gethead(Q):訪問隊首元素。（5）判斷隊列是否空Empty(Q):判斷隊列是否為空。（6）求隊列的大小Current_size(Q):求隊列中元素的個數(shù)。（7）隊列清空Clear(Q):將隊列清為空。3.5隊列的邏輯結構及操作二、隊列的ADT描述3.5隊列的邏輯結構及操作ADTQueue{DataStructure:D={ai|ai∈D0i=1,2,…….n>=0}R={N}N={<ai-1,ai>|ai-1,ai∈D0i=2,3,4…..

}D0是某個數(shù)據(jù)對象operations:Inqueue(Q):Enqueue(Q):Dlqueue(Q):Gethead(Q);Empty(Q);Current-size(Q);Clear(Q);}ADTQueue三、隊列的ADT應用舉例：3.5隊列的邏輯結構及操作打印機隊列管理：在一臺打印機共享使用時，任何時刻它只能處理一個用戶打印請求，打印任務的組織就用一個隊列來組織（先請求的，先處理）當用戶發(fā)出打印請求時，把打印任務入隊當打印機空閑時，從打印隊列中出隊一個任務當打印阻塞時，系統(tǒng)管理員可以清空隊列一、隊列的順序存儲結構：3.5隊列的順序存儲表示及操作實現(xiàn)1、存儲方式：同一般線性表的順序存儲結構完全相同，但是由于兩端操作，設有兩個指示器（rear和front）分別指示隊列的尾和首。特別約定頭指針始終指向隊列的頭元素，而尾指針指向隊列尾元素的下一位置frontreara1空隊列：rear=front=0入隊：rear=rear+1出隊：front=front+1隊列空：front=rear3.5隊列的順序存儲表示及操作實現(xiàn)Q.frontQ.rear01234空隊列Q.frontQ.reara101234Q.frontQ.reara301234Q.frontQ.reara401234a1,a2,a3相繼入隊列a1,a2,相繼被刪除a4,a5,相繼插入隊列，a3被刪除a2a3a5特點：簡單，方便，但易產(chǎn)生假溢出3.5隊列的順序存儲表示及操作實現(xiàn)二、隊列的結構定義//隊列的順序結構定義#defineMAXQSIZE100Typedefstruct{QElemTypebase[MAXQSIZE];//靜態(tài)數(shù)組

intfront;//隊列頭指針

intrear;//隊列尾指針}SqQueue;3.5隊列的順序存儲表示及操作實現(xiàn)三、隊列的簡單操作1、初始化Q.front=Q.rear=02、求隊長Q.rear-Q.front3.5隊列的順序存儲表示及操作實現(xiàn)3、判空intEmptyQueue(SqQueueQ){if(Q.front==Q.rear)return1;elsereturn0;}3.5隊列的順序存儲表示及操作實現(xiàn)4、入隊intInitQueue(SqQueueQ,QElemTypex){if(Q.rear==maxQsize){printf(“overflow”);return0;}Q.base[Q.rear]=x;Q.rear++;

return1;}3.5隊列的順序存儲表示及操作實現(xiàn)5、出隊intOutQueue(SqQueueQ,QElemTypex){if(EmptyQueue(Q)){printf(“underflow”);return0;}x=Q.base[Q.front];Q.front++;

return1;}3.5隊列的順序存儲表示及操作實現(xiàn)四、順序隊列存在的問題及解決Q.frontQ.reara4a5可以看出：當入隊一個元素時，可能出現(xiàn)假溢出現(xiàn)象即：不能入隊，但空間并沒有使用完！解決的方法：1、平移，把隊列中所有元素移到隊列開頭，效率低。2、使用動態(tài)數(shù)組，當產(chǎn)生假溢出或真溢出時，都重新分配更大的空間（不可取）3、使用環(huán)數(shù)組，即將順序存儲空間視為一個環(huán)空間。3.5隊列的順序存儲表示及操作實現(xiàn)五、循環(huán)隊列的表示及實現(xiàn)1、方式：將順序隊列臆造為一個環(huán)狀空間，如圖所示，稱之為循環(huán)隊列，指針和隊列元素之間的關系不變。Q.frontQ.reara4a5…0Maxsize-101Maxsize-1Q.frontQ.reara4a5這種循環(huán)的圈是一種邏輯的圈，在物理上還是一組連續(xù)的存儲單元，仍可利用數(shù)組實現(xiàn)當maxsize=12,那么rear最后指向11，當rear+1時，就會指向第0個元素3.5隊列的順序存儲表示及操作實現(xiàn)循環(huán)隊列可充分利用空間，但仍存在問題：我們知道：隊列為空時front=rear；右圖中，繼續(xù)入隊a7,a8,則front=rear即：隊列為空或隊列為滿時，都是fornt=rear,如何區(qū)分？reara1a2a3a4a5a6frontfronta1a2a3a4a5a6a7a8rear3.5隊列的順序存儲表示及操作實現(xiàn)兩種方法：（1）、設置標志位以區(qū)別隊列是“空”還是“滿”因出隊而相等，則為空因入隊而相等，則為滿reara1a2a3a4a5a6fronta7（2）、少用一個元素空間，約定rear+1==front時，就認為隊滿3.5隊列的順序存儲表示及操作實現(xiàn)2：//循環(huán)隊列…..隊列順序存儲結構的虛擬實現(xiàn)#defineMAXQSIZE100//最大隊列長度Typedefstruct{QElemType*base;//初始化的動態(tài)分配存儲空間intfront;//頭指針，若隊列不空，指向隊列頭元素intrear;//尾指針，若隊列不空，指向隊尾元素的下一位置}SqQueue;3.5隊列的順序存儲表示及操作實現(xiàn)//循環(huán)隊列的基本操作的算法描述StatusInitQueue(SqQueue&Q){//構造一個空隊列QQ.base=(QElemType*)malloc(MAXQSIZE)*sizeof(QElemType);if(!(Q.base))exit(OVERFLOW);Q.front=Q.rear=0;returnOK;}3.5隊列的順序存儲表示及操作實現(xiàn)//循環(huán)隊列的基本操作的算法描述IntQueueLength(SqQueueQ){//返回Q的元素個數(shù)，即隊列的長度return((Q.rear-Q.front+MAXQSIZE)%MAXQSIZE);}reara8a5a6fronta701234567rear<frontfrontreara1a4a3a201234567rear>front3.5隊列的順序存儲表示及操作實現(xiàn)StatusEnQueue(SqQueue&Q,QElemTypee){//插入元素e為Q的新隊尾元素if((Q.rear+1)%MAXSIZE==Q.front)returnerror;//隊滿Q.Base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;returnOK;}3.5隊列的順序存儲表示及操作實現(xiàn)intDeleteQueue(SqQueueQ,QueueElementType&x