[工學]數(shù)據(jù)結(jié)構(gòu)--第三章課件

1、福州大學至誠學院3.1 棧3.1.1抽象數(shù)據(jù)類型棧的定義3.1.2棧的表示與實現(xiàn)3.2 棧的應用舉例3.2.1 數(shù)制轉(zhuǎn)換3.2.2 括號配對問題3.2.4 迷宮求解*3.3 棧和遞歸的實現(xiàn)3.4 隊列3.4.1 抽象數(shù)據(jù)類型隊列的定義3.4.2 鏈隊列 - 隊列的鏈式表示與實現(xiàn)3.4.3 循環(huán)隊列 - 隊列的順序表示與實現(xiàn)第三章 棧和隊列福州大學至誠學院題目：將十進制數(shù)N轉(zhuǎn)換為其他進制數(shù)輸出基本原理：N=(n div d)*d + n mod d“div”是整除運算，mod為求余運算。數(shù)制轉(zhuǎn)換福州大學至誠學院toptop4top40top405 例如：(1348)10=(2504)8，其運算過

2、程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2計算順序輸出順序top4052福州大學至誠學院棧棧的定義：操作受限制的線性表，只能在線性表的一端進行插入和刪除運算。棧S=(a1，a2，a3，an)按照按a1an的次序進棧，如圖：棧頂Top：插入、刪除的這一端。棧底Bottom:不做任何操作的另一端?？諚＃罕碇袥]有元素。LIFO：棧的修改是按后進先出的原則進行的。福州大學至誠學院棧的抽象數(shù)據(jù)類型定義ADT Stack 數(shù)據(jù)對象：D = ai | ai屬于Elemset, (i=1,2,n, n0) 數(shù)據(jù)關系：R1 = ai-1,ai|

3、ai-1,ai屬于D,(i=2,3,n) 約定an為棧頂, a1為棧底。 基本操作： InitStack(&S); DestroyStack(&S); ClearStack(&S); StackEmpty(S); StackLength(S) ; GetTop(S,&e); Push(&S,e); Pop(&S,&e); StackTraverse(S,visit () ADT Stack福州大學至誠學院棧的基本操作InitStack(&S) 操作結(jié)果:構(gòu)造一個空的棧S。DestroyStack(&S)初始條件: 棧S已經(jīng)存在。 操作結(jié)果: 銷毀棧S。福州大學至誠學院棧的基本操作StackEm

4、pty(S)初始條件: 棧S已經(jīng)存在。操作結(jié)果: 若棧S為空棧，則返回TURE;否則返回FALSE。StackLength(S)初始條件: 棧S已經(jīng)存在。 操作結(jié)果: 返回棧S中的數(shù)據(jù)元素個數(shù)。GetTop(S,&e)初始條件: 棧S已經(jīng)存在且非空。操作結(jié)果: 用e返回棧S中棧頂元素的值。福州大學至誠學院StackTraverse(S,visit ()初始條件: 棧S已經(jīng)存在且非空。操作結(jié)果: 從棧底到棧頂依次對S的每個元素調(diào)用函數(shù)visit ()。一旦visit ()失敗，則操作失敗。福州大學至誠學院棧的基本操作Push(&S,e) 初始條件: 棧S已經(jīng)存在。操作結(jié)果: 插入元素e為新的棧頂

5、元素。Pop(&S,&e)初始條件: 棧S已經(jīng)存在且非空。操作結(jié)果: 刪除S的棧頂元素并用e返回其值。ClearStack(&S)初始條件: 棧S已經(jīng)存在。操作結(jié)果: 將棧S重置為空棧。福州大學至誠學院棧的順序表示與實現(xiàn)-(順序棧)#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct SElemType *base; /*在棧構(gòu)造之前和銷毀之后，base的值為NULL*/ SElemType *top; /*棧頂指針*/ int stacksize; /*當前已分配的存儲空間，以元素為單位*/SqStack;福州大

6、學至誠學院順序棧示意圖*base*topstacksize初始空棧*top = *base; stacksize = STACK_INIT_SIZE*base*topstacksize.a1.aian順序棧空棧的棧頂指針指向棧底 非空棧中的棧頂指針始終在棧頂元素的下一個位置福州大學至誠學院top123450進棧A棧滿BCDEF設數(shù)組維數(shù)為Mtop=base,?？?，此時出棧，則下溢（underflow)top=M,棧滿，此時入棧則上溢（overflow)toptoptoptoptop123450空棧topbasebasetop出棧toptop?？誦ase棧底指針base,始終指向棧底位置；棧頂指

7、針top,其初值指向棧底，始終在棧頂元素的下一個位置123450ABtop福州大學至誠學院順序棧的操作實現(xiàn)-InitStack/構(gòu)造一個空的棧SStatus InitStack(SqStack *s) s-base=( SElemType *)malloc (STACK_INIT_SIZE * sizeof(SElemType); if(!s - base) return(OVERFLOW); s-top=s-base; s-stacksize = STACK_INIT_SIZE; return OK; 福州大學至誠學院順序棧的操作實現(xiàn)-GetTop/返回棧S中棧頂元素Status GetTo

8、p(SqStack s, SElemType *e) if (s.top = s.base)return ERROR; *e = *(s.top-1); return OK; se*base*topstacksize.a1.aian*e = *(s.top-1);福州大學至誠學院*base*topstacksize.a1.aians*base*topstacksize.a1.aians棧滿時，追加存儲空間e*s-top+ = e;順序棧的操作實現(xiàn)Push/插入元素e為新的棧頂元素福州大學至誠學院status Push( SqStack *s, SElemType e ) if (s-top s

9、-base = s-stacksize)temp=(SElemType*)realloc (s-base,(s-stacksize+STACKINCREMENT) *sizeof(SElemType); if (!temp) return(OVERFLOW); s-base = temp; s-top = s-base + s-stacksize; s-stacksize += STACKINCREMENT; *s-top+ = e; return OK;福州大學至誠學院順序棧的操作實現(xiàn)-刪除S的棧頂元素status Pop(SqStack *s, SElemType *e) if (s-to

10、p = s-base)return ERROR; *e = * -s-top; return OK; *base*topstacksize.a1.aianse*e = * -s-top;福州大學至誠學院棧的鏈式表示鏈棧:棧的鏈式存儲結(jié)構(gòu)稱為鏈棧，它是運算是受限的單鏈表，插入和刪除操作僅限制在表頭位置上進行.由于只能在鏈表頭部進行操作，故鏈表沒有必要附加頭結(jié)點。指向棧頂表元素的指針就是鏈表的頭指針，鏈式棧無棧滿的問題，空間可擴充a(n)a(n-1)a(1)棧頂棧底top福州大學至誠學院棧的鏈式表示typedef struct snode *slink ;typedef struct snode

11、stackItem data;slink next ; stackNode ;typedef struct lstack slink top ; / 棧頂結(jié)點指針 int stackSize ; Lstack ;福州大學至誠學院 .棧底toptopxptop .棧底topqp-next=top ; top=p q=top ; top=top-next 福州大學至誠學院作業(yè)：設將整數(shù)1、2、3、4依次進棧，但只要出棧時棧非空，則可將出棧操作按任何次序夾入其中，請回答下有問題： （1）若入棧次序為push(1)，pop()，push(2），push(3)，pop()，pop( )，push(4)，

12、pop( )，則出棧的數(shù)字序列為什么？ （2）請分析1、2、3、4的24種排列中，哪些序列可以通過相應的入出棧得到。 福州大學至誠學院題目：將十進制數(shù)N轉(zhuǎn)換為其他進制數(shù)輸出基本原理：N=(n div d)*d + n mod d“div”是整除運算，mod為求余運算。棧的應用舉例-數(shù)制轉(zhuǎn)換福州大學至誠學院toptop4top40top405 例如：(1348)10=(2504)8，其運算過程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2計算順序輸出順序top4052福州大學至誠學院棧的應用舉例void conversion() in

13、t n ; SqStack s ; InitStack(&s); scanf(“%d”,&n); while(n) Push(&s, n%8); n = n/8; while(!StackEmpty(s) Pop(&s,&e); printf(“%d”,e); 福州大學至誠學院假設在表達式中檢測括號是否匹配(x*(x+y)-z)(x+y)*z)(Stack)malloc(sizeof(*S)棧的應用舉例-括號匹配的檢測（）或（ ）等為正確的格式，（ ）或（ ）或 （）)均為不正確的格式?；驹恚杭僭O表達式中允許括號嵌套，則檢測括號是否匹配可用，“期待的迫切程度”這個概念來描述，每個右括號應與

14、最近遇到的尚未匹配的左括號相匹配。福州大學至誠學院分析可能出現(xiàn)的不匹配的情況:到來的右括弧并非是所“期待”的；例如：考慮下列括號序列： ( ) 1 2 3 4 5 6 7 8直到結(jié)束，也沒有到來所“期待”的括??；到來的是不速之客；福州大學至誠學院算法的設計思想：1）凡出現(xiàn)左括弧，則進棧；2）凡出現(xiàn)右括弧，首先檢查棧是否空 若?？?，則表明該“右括弧”多余， 否則和棧頂元素比較， 若相匹配，則“左括弧出?！?， 否則表明不匹配。3）表達式檢驗結(jié)束時， 若?？?，則表明表達式中匹配正確， 否則表明“左括弧”有余。福州大學至誠學院void Parenthis(char *expr)int i,n;Sta

15、ck s = StackInit();n = strlen(expr);for(i=0;in;i+)if(expri=() Push(i,s);else if(expri=) if(StackEmpty(s)printf(“位置%d處的右括號不匹配n”,i); else Pop(s); /彈出最近遇到的左括號福州大學至誠學院while(!StackEmpty(s) printf(“位置%d處的右括號不匹配n”, Pop(s);福州大學至誠學院棧的應用舉例-迷宮求解福州大學至誠學院求迷宮路徑算法的基本思想是（窮舉求解法）：若當前位置“可通”,則納入路徑,繼續(xù)前進;若當前位置“不可通”，則后退,換

16、方向繼續(xù)探索;若四周“均無通路”，則將當前位置從路徑中刪除出去。需要用一個后進先出的結(jié)構(gòu)來保存從入口到當前位置的路徑，保證在任何位置上都能沿著原路退回。福州大學至誠學院算法思想設定當前位置的初值為入口位置;do 若當前位置可通, 則 將當前位置插入棧頂; 若該位置是出口位置、則結(jié)束; 否則切換當前位置的東鄰方塊為新的當前位置; 否則 若棧不空且棧頂位置尚有其它方向未經(jīng)探索, 則設定新的當前位置為順時針方向旋轉(zhuǎn)找到的棧頂 位置的下一相鄰塊; 若棧不空但棧頂位置的四周均不可通, 則 刪去棧頂位置; 若棧不空,則重新測試新的棧頂位置, 直至找到一個可通的相鄰塊或出棧至空棧; while (棧不空);

17、福州大學至誠學院迷宮求解的算法實現(xiàn)typedef struct int ord; /通道塊在路徑上的序號PosType seat; /通道塊在迷宮中的坐標位置int di; /從此通道走向下一通道的方向SElemType;福州大學至誠學院Status MazePath (MazeType maze, PosType start, PosType end) InitStack(s); curpos = start; curstep = 1; do if(Pass(curpos) / 當前位置可通 FootPrint(curpos); / 留下足跡 e = (curstep, curpos,1);

18、 Push(s,e); / 加入路徑 if(curpos = end) return (TRUE); / 到達終點(出口) curpos = NextPos(curpos,1); / 下一個位置是當前位置的東鄰方塊 curstep + ; / 探索下一步 福州大學至誠學院else / 當前位置不能通過 if(!StackEmpty(s) Pop(s,e); While(e.di=4 & !StackEmpty(s) MarkPrint(e.seat); / 留下不能通過的足跡 Pop(s,e); / 退回一步 if(e.di - * / ( # =Precede:判定運算符棧的棧頂運算符1與讀

19、入的運算符2之間的優(yōu)先關系的函數(shù)Operate: 進行二元運算ab的函數(shù).算術表達式求值OperandType EvaluateExpression() InitStack(OPTR); Push(OPTR, #); InitStack(OPND); c = getchar(); While( c!=# | GetTop(OPTR)!=# ) / 不是運算符則進棧 if( !In(c,OP) ) Push(OPND,c); c = getchar(); else switch(Precede(GetTop(OPTR),c) case : / 退棧并將運算結(jié)果入棧 Pop(OPTR,theta)

20、; Pop(OPND,b); Pop(OPND,a); Push(OPND, Operate(a,theta,b); break; default: printf(“Expression error!”); return(ERROR); / switch / else / while return GetTop(OPND); 對算術表達式3*(7-2)求值步驟 OPTR棧 OPND棧 輸入字符 主要操作1 # 3 * ( 7 - 2 ) # Push(OPND,3)2 # 3 * ( 7 - 2 ) # Push(OPTR,*)3 # * 3 ( 7 - 2 ) # Push(OPTR,()4

21、 # * ( 3 7 - 2 ) # Push(OPND,7)5 # * ( 3 7 - 2 ) # Push(OPTR,-)6 # * ( - 3 7 2 ) # Push(OPND,2)7 # * ( - 3 7 2 ) # Operate(7,-,2)8 # * ( 3 5 ) # POP(OPTR)9 # * 3 5 # Operate(3,*,5)10 # 15 # Return(GetTop(OPND)福州大學至誠學院棧的應用舉例函數(shù)調(diào)用當在一個函數(shù)的運行期間調(diào)用另一函數(shù)時，在運行被調(diào)用函數(shù)之前，系統(tǒng)需要(1)將所有的實參、返回地址等信息傳遞給被調(diào)用函數(shù)保存; (2)為被調(diào)用函數(shù)的

22、局部變量分配存儲區(qū); (3) 將控制轉(zhuǎn)移到被調(diào)函數(shù)的入口從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，系統(tǒng)需要完成以下工作(1)保存被調(diào)函數(shù)的計算結(jié)果;(2)釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū);(3)依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。福州大學至誠學院當有多個函數(shù)構(gòu)成嵌套調(diào)用時，按照后調(diào)用先返回的原則，函數(shù)之間的信息傳遞和控制轉(zhuǎn)移通過“棧”來實現(xiàn)，系統(tǒng)將整個程序運行時所需的數(shù)據(jù)空間安排在一個棧中，每當調(diào)用一個函數(shù)時，為該函數(shù)在棧頂分配一個存儲區(qū)，每當一個函數(shù)退出時，就釋放它的存儲區(qū)，則當前正在運行的函數(shù)的數(shù)據(jù)區(qū)必在棧頂。福州大學至誠學院遞歸:直接或間接調(diào)用自身的算法稱為遞歸算法，用函數(shù)自身給出定義的函數(shù)稱為遞歸

23、函數(shù)。遞歸函數(shù)的執(zhí)行過程：在遞歸函數(shù)的執(zhí)行函數(shù)中，需多次進行自我調(diào)用。調(diào)用函數(shù)和被調(diào)用函數(shù)之間的鏈接和信息交換需通過棧來進行。遞歸函數(shù)的運行過程類似于多個函數(shù)的嵌套調(diào)用，只是調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個函數(shù)。因此，和每次調(diào)用相關的一個重要概念時遞歸函數(shù)運行的層次。假設調(diào)用該遞歸函數(shù)的主函數(shù)時第0層，則從主函數(shù)調(diào)用遞歸函數(shù)為進入第1層，從第i層遞歸調(diào)用本函數(shù)為進入“下一層”，即第i+1層，反之，退出第i層遞歸應返回上一層，即第i-1層。為保證遞歸函數(shù)正確執(zhí)行，系統(tǒng)設立一個“遞歸工作?！弊鳛檎麄€遞歸函數(shù)運行期間使用的數(shù)據(jù)存儲區(qū)。每一層遞歸所需信息構(gòu)成一個“工作記錄”，其中包括所有的實參、所有的局部

24、變量以及上一層的返回地址，每進入一層遞歸，就產(chǎn)生一個新的工作記錄壓入棧頂，每退出一層遞歸，就從棧頂彈出一個工作記錄。福州大學至誠學院遞歸問題舉例 Hanoi塔問題：設a,b,c是三個塔座，開始時在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小疊在一起，各圓盤從小到大編號為1,2,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座c上，并按同樣順序疊置。移動圓盤需遵循如下規(guī)則：每次只能移動一個圓盤任何時刻都不能允許將較大的圓盤壓在較小的圓盤上在滿足移動規(guī)則(1)和(2)的前提下，可將圓盤移至a,b,c中任一塔座上。 福州大學至誠學院void main() hanoi(3,a,b,c); / 將n個棋

25、盤從x移到zvoid hanoi (int n, char x, char y, char z )1 2 if(n=1)3 move(x,1,z);4 else 5 hanoi(n-1,x,z,y); /將編號1.n-1的圓盤從x移到y(tǒng),利用z作為輔助圓盤 /將編號為n的圓盤從x移到z6 move(x,n,z); /將編號1.n-1的圓盤從y移到z,利用x為輔助圓盤7 hanoi(n-1,y,x,z);8 9 福州大學至誠學院福州大學至誠學院福州大學至誠學院福州大學至誠學院隊列隊列（Queue）:僅在隊尾進行插入和隊頭進行刪除操作的線性表，先進先出線性表(FIFO) 隊頭（front）: 線性

26、表的表頭端，即可刪除端。隊尾（rear）: 線性表的表尾端，即可插入端。隊頭隊尾.a1a2a3an-1an入隊列(Enqueue)出隊列(Dequeque)福州大學至誠學院抽象數(shù)據(jù)類型隊列的定義ADT Queue 數(shù)據(jù)對象：D=ai|ai屬于Elemset,(i=1,2,n, n0) 數(shù)據(jù)關系：R1=ai-1,ai|ai-1,ai屬于D,(i=2,3,n) 約定an為隊尾, a1為隊頭。 基本操作： InitQueue(&Q); DestroyQueue (&Q); ClearQueue (& Q); QueueEmpty(Q); QueueLength(Q) ; GetHead(Q,&e);

27、 EnQueue (&Q,e); DeQueue (&Q,&e); QueueTraverse(Q,visit () ADT Queue隊列福州大學至誠學院隊列的基本操作(之一)InitQueue (&Q) 操作結(jié)果:構(gòu)造一個空的隊列Q。DestroyQueue (&Q) 初始條件: 隊列Q已經(jīng)存在。操作結(jié)果: 銷毀隊列Q。ClearQueue (&Q) 初始條件: 隊列Q已經(jīng)存在。 操作結(jié)果: 將隊列Q重置為空隊列。福州大學至誠學院隊列的基本操作(之二)QueueEmpty(Q)初始條件:隊列Q已經(jīng)存在。操作結(jié)果:若隊列Q為空隊列,則返回TURE;否則返回FALSE。QueueLength(

28、Q)初始條件:隊列Q已經(jīng)存在。操作結(jié)果:返回隊列Q中的數(shù)據(jù)元素個數(shù),即隊列Q的長度。GetHead(Q,&e)初始條件:隊列Q已經(jīng)存在且非空。操作結(jié)果:用e返回隊列Q中隊頭元素的值。福州大學至誠學院隊列的基本操作(之三)EnQueue (&Q,e)初始條件: 隊列Q已經(jīng)存在。操作結(jié)果: 插入元素e為新的隊尾元素。DeQueue (&Q,&e)初始條件: 隊列Q已經(jīng)存在且非空。操作結(jié)果: 刪除隊列Q 的隊頭元素并用e返回其值。QueueTraverse(Q,visit ()初始條件: 隊列Q已經(jīng)存在且非空。操作結(jié)果: 從隊頭到隊尾依次對隊列Q的每個元素調(diào)用函數(shù)visit ()。一旦visit (

29、)失敗，則操作失敗。福州大學至誠學院鏈隊列-隊列的鏈式表示與實現(xiàn)鏈隊列：隊列的鏈式存儲結(jié)構(gòu)簡稱為鏈隊列，它是限制僅在表頭刪除和表尾插入的單鏈表。顯然僅有單鏈表的頭指針(front)不便于在表尾做插入操作，為此再增加一個尾指針(rear)，指向鏈表的最后一個結(jié)點。鏈隊列無隊列滿的問題，空間可擴充。a1anQ.frontQ.rearQ.frontQ.rear空隊列福州大學至誠學院typedef struct QNode QElemType data; struct QNode *next; Qnode, *QueuePtr;typedef struct QueuePtr front; / 隊頭指針

30、 QueuePtr rear; / 隊尾指針 LinkQueue;data*nextfrontrearfrontx入隊xfrontreary入隊xyfrontreary出隊Q.rear - next=pQ.rear=pp= Q.front - nextQ.front - next = p - next free(p)prearrearpfrontrearx出隊xyIf(Q.rear =p) Q.rear =Q.front福州大學至誠學院鏈隊列的操作實現(xiàn)InitQueue/構(gòu)造一個空的隊列QStatus InitQueue(LinkQueue &Q) Q.rear=(QueuePtr)mallo

31、c(sizeof(QNode) ); Q.front = Q.rear; if(!Q.front) return(OVERFLOW); Q.front - next = NULL; return OK; / InitQueue福州大學至誠學院鏈隊列的操作實現(xiàn) DestroyQueue/銷毀隊列QStatus DestroyQueue(LinkQueue &Q) while(Q.front ) Q.rear = Q.front - next; free(Q.front); Q.front = Q.rear; return OK;福州大學至誠學院鏈隊列的操作實現(xiàn) EnQueue/插入元素e為新的隊

32、尾元素Status EnQueue(LinkQueue &Q, QelemType e) p = ( QueuePtr )malloc(sizeof(QNode); if(!p) return(OVERFLOW); p-data = e; p - next = NULL; Q.rear -next = p; Q.rear = p; return OK;福州大學至誠學院鏈隊列的操作實現(xiàn)DeQueue/刪除隊列Q 的隊頭元素并用e返回其值Status DeQueue(LinkQueue &Q, QelemType &e) if(Q.front = Q.rear) retrun ERROR; p =

33、 Q.front - next; e = p-data; Q.front-next = p-next; if(Q.rear = p) Q.rear = Q.front ; free(p); return OK;福州大學至誠學院循環(huán)隊列隊列的順序表示和實現(xiàn) #define MAXQSIZE 100 /最大隊列長度 typedef struct QElemType *base; / 動態(tài)分配存儲空間 int front; / 頭指針，若隊列不空，指向隊列頭元素 int rear; / 尾指針,若隊列不空指向 隊列尾元素的下一個位置 SqQueue;福州大學至誠學院123450空隊列rear=0 f

34、ront=0J1J2J3rearrear123450J4,J5,J6入隊J4J5J6frontrearrear123450frontJ1,J1,J3入隊rear123450J1,J2,J3出隊J1J2J3frontfrontfrontfront存在問題：當front=0,rear=M時再有元素入隊發(fā)生溢出真溢出當front0,rear=M時再有元素入隊發(fā)生溢出假溢出rear福州大學至誠學院解決方案隊首固定，每次出隊剩余元素向下移動浪費時間循環(huán)隊列 基本思想：把隊列設想成環(huán)形，讓sq0接在sqM-1之后，若rear+1=M,則令rear=0;實現(xiàn)：利用“?！边\算入隊: baserear=x; rear=(rear+1)%M; 出隊：x=basefront; front=(front+1)%M; 隊滿、隊空判定條件福州大學至誠學院012345rearfrontJ5J6J7012345rearfrontJ4J9J8J4,J5,J6出隊J7,J8,J9入隊隊空：front=rear隊滿：front=rearJ5J6012345rearfront初始狀態(tài)J4福州大學至誠學院解決方