堆棧堆棧的應(yīng)用隊(duì)列隊(duì)列的應(yīng)用課件

1、堆棧堆棧的應(yīng)用隊(duì)列隊(duì)列的應(yīng)用第三章 堆棧和隊(duì)列9/22/202213.1 棧 ( Stack )只允許在一端插入和刪除的順序表允許插入和刪除 的一端稱為棧頂 (top)，另一端稱 為棧底(bottom)特點(diǎn) 后進(jìn)先出 (LIFO)退棧進(jìn)棧9/22/20222進(jìn)棧示例 9/22/20223退棧示例9/22/20224棧的順序存儲(chǔ)結(jié)構(gòu)順序棧的定義typedef int datatype;#define maxsize 64typedef struct datatype datamaxsize; int top;seqstack; 9/22/20226棧的基本運(yùn)算置空棧SETNULL(seqstac

2、k *s) s-top-1;判?？読nt EMPTY(seqstack *s) if (s-top=0) return FALSE; else return TRUE;9/22/20227退棧datatype POP(seqstack *s) if (EMPTY(s) printf(“underflown”);return NULL; else s-top-; return(s-datas-top+1); 9/22/20229取棧頂datatype TOP(seqstack *s) if (EMPTY(s) printf(“underflown”);return NULL; else retu

3、rn(s-datas-top);9/22/202210兩個(gè)堆棧共享空間0maxsize-1lefttoprighttop9/22/202211棧的鏈接表示 鏈?zhǔn)綏ｆ準(zhǔn)綏o棧滿問題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^適合于多棧操作9/22/202212棧的鏈接存儲(chǔ)結(jié)構(gòu)鏈棧的結(jié)點(diǎn)定義typedef int datatype;typedef struct node datatype data; struct node *next; linkstack; 9/22/202213鏈棧的進(jìn)棧算法linkstack *PUSHLSTACK(linkstack *top, datatype

4、x) linkstack *p; pmalloc(sizeof(linkstack); p-datax; p-nexttop; return p;9/22/202214例：對(duì)于一個(gè)棧，給出輸入項(xiàng)A、B、C，如果輸入項(xiàng)序列由ABC組成，試給出所有可能的輸出序列。A進(jìn) A出 B進(jìn) B出 C進(jìn) C出 ABCA進(jìn) A出 B進(jìn) C進(jìn) C出 B出 ACBA進(jìn) B進(jìn) B出 A出 C進(jìn) C出 BACA進(jìn) B進(jìn) B出 C進(jìn) C出 A出 BCAA進(jìn) B進(jìn) C進(jìn) C出 B出 A出 CBA不可能產(chǎn)生輸出序列CAB9/22/202216棧的應(yīng)用舉例文字編輯器seqstack s;EDIT() char c; SETNU

5、LL(&s); cgetchar(); while (c!=*) if (c=#) POP(&s); else if (c=) SETNULL(&s); else PUSH(&s,c); cgetchar(); 9/22/202217棧的應(yīng)用表達(dá)式計(jì)算中綴表達(dá)式：A + ( B C / D) E后綴表達(dá)式：ABCD/E+ （逆波蘭表達(dá)式）后綴表達(dá)式特點(diǎn)1、與相應(yīng)的中綴表達(dá)式中的操作數(shù)次序相同2、沒有括號(hào)9/22/202219后綴表達(dá)式的處理過程操作順序后綴表達(dá)式ABCD/E+T1 C/DABT1E+T2 B T1AT2E+T3 T2 EAT3+T4 A + T3T49/22/202220ABC

6、DEABCT1ABT2AT39/22/202221中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式()#(#frontmaxsize-1; sq-rearmaxsize-1;9/22/202230順序隊(duì)列判隊(duì)空int EMPTY(sequeue *sq) if (sq-rear=sq-front) return(TRUE); else return(FALSE); 9/22/202231順序隊(duì)列取隊(duì)頭元素datatype FRONT(sequeue *sq) if (EMPTY(sq) printf(“queue is emptyn”); return NULL; else return (sq-front+1)%

7、maxsize);9/22/202232順序隊(duì)列入隊(duì)int ENQUEUE(sequeue *sq,datatype x) if (sq-front=(sq-rear+1)%maxsize) printf(“sequeue is fulln”;return NULL); else sq-rear(sq-rear+1)%maxsize; sq-datasq-rearx; return(TRUE); 9/22/202233順序隊(duì)列出隊(duì)datetype DEQUEUE(sequeue *sq) if (EMPTY(sq) printf(“queue is emptyn”);return NULL;

8、else sq-front(sq-front+1)%maxsize; return(sq-datasq-front); 9/22/202234存儲(chǔ)隊(duì)列的數(shù)組被當(dāng)作首尾相接的表處理。隊(duì)頭、隊(duì)尾指針加1時(shí)從maxSize -1直接進(jìn)到0，可用語言的取模(余數(shù))運(yùn)算實(shí)現(xiàn)。隊(duì)頭指針進(jìn)1: front = (front + 1) % maxSize; 隊(duì)尾指針進(jìn)1: rear = (rear + 1) % maxSize;隊(duì)列初始化：front = rear = 0;隊(duì)空條件：front = rear;隊(duì)滿條件：(rear + 1) % maxSize = front 循環(huán)隊(duì)列 (Circular Qu

9、eue)9/22/202235循環(huán)隊(duì)列的進(jìn)隊(duì)和出隊(duì)9/22/202236隊(duì)列的鏈接表示 鏈?zhǔn)疥?duì)列隊(duì)頭在鏈頭，隊(duì)尾在鏈尾。鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無隊(duì)滿問題，但有隊(duì)空問題。隊(duì)空條件為 front = NULL9/22/202237鏈隊(duì)列結(jié)點(diǎn)類型定義typedef struct node datatype data; struct node *next; linklist; typedef struct linklist *front,*rear; linkqueue;9/22/202238鏈隊(duì)列置隊(duì)空SETNULL(linkqueue *q) q-frontmalloc(sizeof(linklist)

10、; q-front-nextNULL; q-rearq-front; 9/22/202239鏈隊(duì)列判隊(duì)空int EMPTY(linkqueue *q) if q-front=q-rear) return(TRUE); else return(FALSE); 9/22/202240鏈隊(duì)列取隊(duì)頭結(jié)點(diǎn)datatype FRONT(linkqueue *q) if (EMPTY(q) printf(“queue is emptyn”); return NULL; else return(q-front-next-data); 9/22/202241鏈隊(duì)列入隊(duì)ENQUEUE(linkqueue *q,d

11、atatype x) q-rear-next(linklist *)malloc(sizeof(linklist); q-rearq-rear-next; q-rear-datax; q-rear-nextNULL; 9/22/202242鏈隊(duì)列出隊(duì)datatype DEQUEUE(linkqueue *q) linklist *s; if (EMPTY(q) printf(“queue is emptyn”);return NULL; else sq-front; q-frontq-front-next; free(s); return(q-front-data); 9/22/2022430

12、111011110101010010011110111001110011000011001101 2 3 4 5 6 7 8123456隊(duì)列的應(yīng)用舉例求迷宮的最短路徑9/22/202244zxzy1-102-1+130+14+1+15+106+1-170-18-1-1需要解決的問題1：如何從某一坐標(biāo)點(diǎn)出發(fā)搜索其四周的鄰點(diǎn)9/22/202245需要解決的問題2：如何存儲(chǔ)搜索路徑需要解決的問題3：如何防止重復(fù)到達(dá)某坐標(biāo)點(diǎn)步xypre11102221333243439/22/202246需要解決的問題4：如何輸出搜索路徑1121314151617181920 x1525656656y16631754

13、88pre08910101112141616隊(duì)列9/22/202247#define m 10#define n 15typedef struct int x,y; int pre; sqtype;sqtype sq400;int mgm+1n+1;int zx8, zy8;9/22/202248void mglj( ) int i, j, v, front, rear, find x, y; sq1.x1; sq1.y1; sq1.pre0; front1; rear1; find=0; maze11-1; while(front=rear & !find) xsqfront.x; ysqfront.y; for (v=1;v=8;v+) ix+zxv; jy+zyv; if (mgij= =0) rear+; sqrear.xi; sqrear.yj; sqrear.prefront