數(shù)據(jù)結(jié)構(gòu)與算法——c語言和java語言描述 ppt及答案和其他資源03棧和隊(duì)列

1、棧和隊(duì)列,棧的定義和基本運(yùn)算/ 順序棧/ 鏈棧/ 隊(duì)列的定義和基本運(yùn)算/順序隊(duì)列/鏈?zhǔn)疥?duì)列/實(shí)訓(xùn),唐懿芳,數(shù)據(jù)結(jié)構(gòu)與算法,,目錄,CONTENTS,,,棧的定義和基本運(yùn)算,1、棧的定義 2、棧的基本運(yùn)算,01,數(shù)據(jù)結(jié)構(gòu)與算法,第一節(jié)：棧的定義和基本運(yùn)算,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,生活中的棧與隊(duì)列棧和隊(duì)列是特殊的線性表?xiàng)Ｅc隊(duì)列的特征LIFO(Last In First Out)FIFO(First In First Out),棧

2、的定義,堆棧簡(jiǎn)稱為棧，是限定只能在表的一端進(jìn)行插入和刪除操作的線性表。在表中，允許插入和刪除的一端稱作“棧頂”，另一端稱作“棧底”。通常將元素插入棧頂?shù)牟俜Q作為“入?！保ㄟM(jìn)棧或壓棧），稱刪除棧頂元素的操作為“出棧”,棧底,棧頂,入棧,出棧,圖3.1 堆棧,,,,,a1,a2,an,…,,,第一節(jié)：棧的定義和基本運(yùn)算,棧的基本運(yùn)算,堆棧的基本運(yùn)算如下。(1)StackInit()初始化堆棧。(2)StackEmpty(s) 判

3、定棧s是否為空。(3)StackLength(s) 求堆棧s的長(zhǎng)度。(4)GetTop(s) 獲取棧頂元素的值。(5)Push(s, e) 將元素e進(jìn)棧。(6)Pop(s)，出棧（刪除棧頂元素）。,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,第一節(jié)：棧的定義和基本運(yùn)算,棧的存儲(chǔ)結(jié)構(gòu),兩種存儲(chǔ)結(jié)構(gòu)：(1)順序棧——采用順序結(jié)構(gòu)存儲(chǔ)(2)鏈?！捎面?zhǔn)浇Y(jié)構(gòu)存儲(chǔ),數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,,,順序棧,1、順序棧的存儲(chǔ)結(jié)構(gòu) 3、順序棧的案例2、順序棧的

4、基本運(yùn)算,02,數(shù)據(jù)結(jié)構(gòu)與算法,第二節(jié)：順序棧,順序棧的存儲(chǔ)結(jié)構(gòu),,MaxSize-1,#define MaxSize 堆?？赡苓_(dá)到的最大長(zhǎng)度typedef struct { ElementType elem[MaxSize]; 　int top; 　　　　/*棧頂位置*/} SeqStack;,棧底,棧頂,,,,,a0,a1,an-1,…,,備用空間,棧滿和棧空的條件是什么？,棧滿：top=Maxsize-1?？眨簍

5、op=-1,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,,SeqStack StackInit(){ SeqStack s;s.top=-1; return(s);},,順序棧的基本運(yùn)算,,初始化堆棧 StackInit(),,,int StackEmpty(SeqStack s){ return(s.top==-1);},,判定棧s是否為空StackEmpty(s),,,int StackLength(SeqStack s){retu

6、rn(s.top+1);},,求堆棧s的長(zhǎng)度StackLength(s),,,ElementType GetTop(SeqStack s){ if (StackEmpty(s)) /*空棧*/return(nil); return(s.elem[s.top]);},,獲取棧頂元素的值GetTop(s),,,void Push(SeqStack *s, ElementType e){ if (s->

7、;top== MaxSize-1) /*棧滿*/printf(“Full”); else { s->top++; s->elem[s->top]=e ; }},,進(jìn)棧Push(s, e),,,ElementType Pop(SeqStack *s){ if (s->top== -1) /*棧空*/return(nil); /* 返回空值*/ e

8、lse { e=s->elem[s->top]; s->top--; return (e); }},,出棧Pop(s),,第二節(jié)：順序棧,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,順序棧案例1,【例1】假設(shè)有兩個(gè)棧共享一個(gè)一維數(shù)組空間[0,MaxSize－1]，其中一個(gè)棧用數(shù)組的第0單元（元素）作為棧底，另一棧用數(shù)組的第MaxSize－1號(hào)單元（元素）作為棧底（即兩個(gè)堆棧從兩端向中間延伸），其對(duì)應(yīng)的類型描述如下：#

9、define MaxSize 堆棧可能達(dá)到的最大長(zhǎng)度typedef struct { ElementType elem[MaxSize]; 　 int top1, top2; 　　　　/*棧頂位置*/} ShareStack;,第二節(jié)：順序棧,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,順序棧案例2,,則棧1的棧頂表示為:s->top1，棧2的棧頂表示為:s->top2; 棧1的進(jìn)棧操作使得棧頂1右（后）移，即s->top1++，

10、棧2進(jìn) 棧操作使得棧頂2左（前）移，即s->top1--; 棧滿時(shí)兩個(gè)棧頂相鄰，即s->top1+1＝＝s->top2。,圖3.2 共享堆棧,,,,,,,,棧1,,,棧頂2,,a1,an,b1,bm,棧2,棧底1,,棧底2,0,…,MaxSize-1,,棧頂1,第二節(jié)：順序棧,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,順序棧案例3進(jìn)棧,,void Push(ShareStack *s, ElementType e, int i)

11、 /*將元素e壓入棧i(i=1,2)*/{ if (s->top1+1==s->top2) /*棧滿*/ printf(“Full”);else { if (i==1){ s->top1++; s->elem[s->top1]=e ;} else{ s->top2--; s->elem[s->top2]=e ;} }}

12、,第二節(jié)：順序棧,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,順序棧案例4出棧,,ElementType Pop(ShareStack *s, int i) /*棧i(i=1,2)出棧*/{ if (i==1) if (s->top1==-1) /*棧1空*/ return(nil); else { e=s->elem[s->top1]; s->top1--; return(

13、e); } if (i==2) if (s->top2== MaxSize) /*棧2空*/return(nil);else{ e=s->elem[s->top2]; s->top2++; return(e); }},第二節(jié)：順序棧,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,,,鏈棧,1、棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2、鏈棧的基本運(yùn)算,03,數(shù)據(jù)結(jié)構(gòu)與算法,第三節(jié)：鏈棧,鏈棧的存儲(chǔ)結(jié)構(gòu),,#define MAX_SIZ

14、E 100 //設(shè)置最大元素個(gè)數(shù)typedef int Elemtype;typedef struct snode { ElementType data; struct snode *next;}StackNode;typedef StackNode *LinkStack; / * LinkStack為指向StackNode 的指針類型* /,...,圖3.6 鏈棧,棧頂,,,,,,,,,,,a1,

15、an,an-1,棧底,data,next,Λ,s,,,,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,第三節(jié)：鏈棧,鏈棧的基本操作,,1．棧初始化棧的初始化實(shí)現(xiàn)比較簡(jiǎn)單，算法如下：LinkStack StackInit(){ LinkStacks=(LinkStack)malloc(sizeof(StackNode));s->next=0; return (s);}

16、 /* StackInit */2．判斷棧是否為空在判斷棧是否為空時(shí)，只需將棧頂指針s->next值與null相比即可，算法實(shí)現(xiàn)如下：int StackEmpty(LinkStack s){ return(s->next==NULL);} /* StackEmpt

17、y */,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,第三節(jié)：鏈棧,鏈棧的基本操作,,3．求棧的長(zhǎng)度int StackLength(LinkStack s){LinkStack p=s->next; int length=0;while (p) { length++; p=p->next; }return(length);}

18、 /* StackLength */4．進(jìn)棧操作//插入元素e為新的棧頂元素void Push(LinkStack s, int e){LinkStack p=(StackNode *)malloc(sizeof(StackNode));p->data=e;p->next=s->next; //如圖②把當(dāng)前的棧頂元素賦值給新結(jié)點(diǎn)的直接后繼s->next =p;

19、 //如圖③將新的結(jié)點(diǎn)p賦值給棧頂指針} /* Push*/,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,第三節(jié)：鏈棧,鏈棧的基本操作,,5．出棧操作//若棧不空，則刪除棧頂元素，用e返回值int Pop(LinkStack s){ if (StackEmpty(s))

20、 /*?？?/return(nil); /* 返回空值*/ else{ LinkStack p=s->next; /*如圖①將棧頂結(jié)點(diǎn)賦值給p*/int e=0; s->next= p->next; /*如圖②使得棧頂指針下移1位，指向后一結(jié)點(diǎn)*/ e=p->data; free(p);

21、 /*釋放結(jié)點(diǎn)p*/ return(e);}} /* Pop*/,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,第三節(jié)：鏈棧,鏈棧的基本操作,,6．獲取棧頂元素根據(jù)棧頂指針s，可以直接獲取最后入棧的元素。應(yīng)

22、該注意的是，在進(jìn)行讀取之前，也要進(jìn)行?？諜z查。相關(guān)的算法實(shí)現(xiàn)如下：int GetTop(LinkStack s){ if (StackEmpty(s)) return(nil); return(s->next->data);} /* GetTop*/,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,,,隊(duì)列,1、隊(duì)列的定義

23、 3、隊(duì)列的存儲(chǔ)結(jié)構(gòu)2、隊(duì)列的基本運(yùn)算,04,數(shù)據(jù)結(jié)構(gòu)與算法,第4節(jié)：隊(duì)列,隊(duì)列的定義,,隊(duì)列簡(jiǎn)稱為隊(duì)，是限定只能在表的一端作插入運(yùn)算、在另一端作刪除運(yùn)算的線性表；在表中，允許插入的一端稱作“隊(duì)尾”，允許刪除的另一端稱作“隊(duì)首”（或“隊(duì)頭”）；通常將元素插入隊(duì)尾的操作稱作為入隊(duì)列（或入隊(duì)），稱刪除隊(duì)首元素的操作為出隊(duì)列（或出隊(duì)）。,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,第4節(jié)：隊(duì)列,隊(duì)列的基本運(yùn)算,,,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,隊(duì)列的基本運(yùn)算如下。(1)

24、InitQueue() 初始化隊(duì)列。(2)QueueEmpty(q) 判定隊(duì)列q是否為空。(3)QueueLength(q) 求隊(duì)列q的長(zhǎng)度。 GetHead(q) 獲取隊(duì)列q隊(duì)首元素的值。(5)AddQueue (q, e) 將元素e入隊(duì)。(6)DeleteQueue (q) 刪除隊(duì)首元素。,第4節(jié)：隊(duì)列,隊(duì)列的存儲(chǔ)結(jié)構(gòu),,兩種結(jié)構(gòu)：(1)順序隊(duì)列——采用順序結(jié)構(gòu)存儲(chǔ)(2)鏈?zhǔn)疥?duì)

25、列——采用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ),數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,,,順序隊(duì)列,1、隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) 2、順序隊(duì)列的基本運(yùn)算,05,數(shù)據(jù)結(jié)構(gòu)與算法,第5節(jié)：順序隊(duì)列,隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)1,,#define MaxSize n 隊(duì)列可能達(dá)到的最大長(zhǎng)度ntypedef struct { ElementType elem[MaxSize]; 　int front, rear; 　　 /*隊(duì)首、隊(duì)尾指示器*/} Queue;,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,第5

26、節(jié)：順序隊(duì)列,隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)2,,,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,,,,,圖3.12 隊(duì)列操作,,,,,,,,,,,,,a,b,c,e,rear=4,,,,,,,d,front=-1,,,,,b,c,e,rear=4,,,,,,,d,front=0,,,,,front=rear=4,,,,,,front=rear=-1,,(a) 空隊(duì),(b) a,b,c,d,e入隊(duì),(c) 出隊(duì)1次,(d) 出隊(duì)4次,隊(duì)滿和隊(duì)空的條件是什么？,隊(duì)空：fron

27、t==rear隊(duì)滿：rear==Maxsize-1,?,第5節(jié)：順序隊(duì)列,隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)3,,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,當(dāng)rear=MaxSize-1時(shí),隊(duì)列為滿，如果再加入新元素，就會(huì)產(chǎn)生"溢出"。但是這種"溢出"并不是真正的溢出，在數(shù)組的前端還可能有空位置，所以這是一種假溢出。,,,,,,,b,c,e,rear=4,,,,,,,d,front=0,,,,,front=rear=4,,,,,,,

28、解決方法：循環(huán)隊(duì)列,第5節(jié)：順序隊(duì)列,隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)4,,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,為了能夠充分的使用數(shù)組中的存儲(chǔ)空間，把數(shù)組的前端和后端連接起來，形成一個(gè)環(huán)形的表，即把存儲(chǔ)隊(duì)列元素的表從邏輯上看成一個(gè)環(huán)，成為循環(huán)隊(duì)列（Circular Queue）。,front,,,,,front,rear,front,rear,a,,,front,rear,b,c,d,,,front,rear,a,b,c,d,,,front,rear,a,b,c,,,

29、rear,(a) 空隊(duì)列,(b) a入隊(duì)列,(c) b,c入隊(duì)列,(d) d入隊(duì)列（隊(duì)滿）,(e) 出隊(duì)1次,(f) 出隊(duì)3次（隊(duì)空）,隊(duì)頭指針進(jìn)1：front=(front+1)%MaxSize；隊(duì)尾指針進(jìn)1：rear=(rear+1)%MaxSize；,第5節(jié)：順序隊(duì)列,隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)4,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,以下是隊(duì)空的幾種情況：,初始化時(shí)：front=rear=0循環(huán)隊(duì)列為空的條件是：front==rear,,,fron

30、t,rear,(a) 空隊(duì)列,front,,,rear,(f) 出隊(duì)3次（隊(duì)空）,front=0Rear=0,front=4Rear=4,第5節(jié)：順序隊(duì)列,隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)4,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,循環(huán)隊(duì)列為滿的條件是：front==(rear+1) % MaxSize,,,front,rear,a,b,c,d,以下是隊(duì)滿的幾種情況：,front=0Rear=4,,,front,rear,a,b,c,d,front=3Rear=2

31、,,,front,rear,b,c,d,a,front=1Rear=0,第5節(jié)：順序隊(duì)列,順序隊(duì)列的基本運(yùn)算1,1）、初始化隊(duì)列 InitQueue()CirQueue InitQueue(){CirQueue q;q.front =q.rear =0;return(q);}2）、判定隊(duì)列q是否為空QueueEmpty(q)int QueueEmpty(CirQueue q){return(q.front

32、 ==q.rear );},數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,第5節(jié)：順序隊(duì)列,順序隊(duì)列的基本運(yùn)算2,3)、 求隊(duì)列q的長(zhǎng)度QueueLength(q)int QueueLength(CirQueue q){return ((q.rear +MaxSize-q.front )%MaxSize);},數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,,,front,rear,a,b,c,front=0Rear=3,,,front,rear,a,b,c,d,front=3Re

33、ar=2,第5節(jié)：順序隊(duì)列,順序隊(duì)列的基本運(yùn)算3,4) 、獲取隊(duì)列q隊(duì)首元素的值GetHead(q)ElementType GetHead(CirQueue q){if(QueueEmpty(q))return(-1);return(q.elem[(q.front+1)%MaxSize]);},數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,,,front,rear,,,front,rear,a,b,c,front=0Rear=3,,,fron

34、t,rear,a,b,d,front=4Rear=2,第5節(jié)：順序隊(duì)列,順序隊(duì)列的基本運(yùn)算4,5) 、AddQueue (q, e) 將元素e入隊(duì)void AddQueue(CirQueue *q,ElementType e){if(q->front ==(q->rear +1)%MaxSize)printf("\nfull");else { q->rear =(q

35、->rear +1)%MaxSize; q->elem [q->rear ]=e;}},數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,6) 、DeleteQueue (q) 刪除隊(duì)首元素ElementType DeleteQueue(CirQueue *q){ElementType e;if(q->front ==q->rear )return(-1);else{e=q->elem [

36、(q->front +1)%MaxSize];q->front=(q->front +1)%MaxSize;return(e);}},,,鏈?zhǔn)疥?duì)列,1、鏈?zhǔn)疥?duì)列的存儲(chǔ)結(jié)構(gòu) 2、鏈?zhǔn)疥?duì)列的基本運(yùn)算,06,數(shù)據(jù)結(jié)構(gòu)與算法,第6節(jié)：鏈?zhǔn)疥?duì)列,鏈?zhǔn)疥?duì)列的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,3.6.1 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),隊(duì)首指針front,圖3.16 鏈隊(duì)列,…,,隊(duì)尾指針rear,,,,Λ,,,,,a2,a1

37、,an,ΛΛ,頭結(jié)點(diǎn),,,隊(duì)首指針 front,隊(duì)尾指針 rear,(b) 非空鏈隊(duì)列,(a) 空鏈隊(duì)列,第6節(jié)：鏈?zhǔn)疥?duì)列,鏈?zhǔn)疥?duì)列的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,typedef struct Qnode{ ElementType data; //結(jié)點(diǎn)數(shù)據(jù)域 struct Qnode *next; //結(jié)點(diǎn)指針域}QueueNode; typedef struct{ QueueNod

38、e *front,*rear; //隊(duì)首和隊(duì)尾指針}LinkQueue;,第6節(jié)：鏈?zhǔn)疥?duì)列,鏈?zhǔn)疥?duì)列的基本操作,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,1．隊(duì)列初始化。隊(duì)列的初始化實(shí)現(xiàn)比較簡(jiǎn)單，算法如下：LinkQueue InitQueue(){QueueNode *p;LinkQueue q;p=(QueueNode *)malloc(sizeof(QueueNode));p->next=NULL;

39、 q.front =q.rear =p;return (q);},2. 判斷隊(duì)列是否為空int QueueEmpty(LinkQueue q){return (q.front ==q.rear);},第6節(jié)：鏈?zhǔn)疥?duì)列,鏈?zhǔn)疥?duì)列的基本操作,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,3．獲取隊(duì)首元素ElementType GetHead(LinkQueue q){if(QueueEmpty(q))return (nil);re

40、turn (q.front->next ->data );},第6節(jié)：鏈?zhǔn)疥?duì)列,鏈?zhǔn)疥?duì)列的基本操作,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,4. 入隊(duì)操作//插入元素e為q的新的隊(duì)尾元素void AddQueue(LinkQueue *q,ElementType e){QueueNode *p;p=(QueueNode *)malloc(sizeof(QueueNode)); if(!p)

41、 {printf(“存儲(chǔ)分配失敗!\n”);return;}p->data =e;p->next =NULL;q->rear ->next =p; //把擁有元素e新結(jié)點(diǎn)p賦值給原隊(duì)尾結(jié)點(diǎn)的后繼q->rear =p; //把當(dāng)前的p設(shè)置為隊(duì)尾結(jié)點(diǎn)，rear指向p},第6節(jié)：鏈?zhǔn)疥?duì)列,鏈?zhǔn)疥?duì)列的基本操作,數(shù)據(jù)結(jié)構(gòu)與運(yùn)算,5．出隊(duì)操作//若隊(duì)列不空

42、，刪除q的隊(duì)頭元素，用e返回其值ElementType DeleteQueue(LinkQueue *q){if(QueueEmpty(*q))return (-1);else{ElementType e;QueueNode *p;p=q->front->next; //將欲刪除的隊(duì)頭結(jié)點(diǎn)暫存給pq->front->next =p->n

43、ext ; //將原隊(duì)頭結(jié)點(diǎn)后繼賦值給頭結(jié)點(diǎn)后繼e=p->data ; //將欲刪除的隊(duì)頭結(jié)點(diǎn)的值賦值給eif(p==q->rear)q->rear =q->front ;free(p);return(e);}},,,本章實(shí)訓(xùn),07,數(shù)據(jù)結(jié)構(gòu)與算法,,,約瑟夫環(huán)的實(shí)現(xiàn)（P58）,,鏈?zhǔn)疥?duì)列分隊(duì)簡(jiǎn)單實(shí)現(xiàn),順序共享?xiàng)５暮?jiǎn)單實(shí)現(xiàn),,棧