堆棧堆棧的應(yīng)用隊(duì)列隊(duì)列的應(yīng).ppt

2019/6/26,1,堆棧 堆棧的應(yīng)用 隊(duì)列 隊(duì)列的應(yīng)用,第三章 堆棧和隊(duì)列,2019/6/26,2,3.1 棧 ( Stack ),只允許在一端插入和刪除的順序表 允許插入和刪除 的一端稱為棧頂 (top)，另一端稱 為棧底(bottom) 特點(diǎn) 后進(jìn)先出 (LIFO),退棧,進(jìn)棧,2019/6/26,3,進(jìn)棧示例,2019/6/26,4,退棧示例,2019/6/26,5,棧的基本操作,1、初始化 2、進(jìn)棧 3、退棧 4、取棧頂元素 5、判棧是否非空 6、置?？?2019/6/26,6,棧的順序存儲結(jié)構(gòu),順序棧的定義 typedef int datatype; #define maxsize 64 typedef struct datatype datamaxsize; int top; seqstack;,2019/6/26,7,棧的基本運(yùn)算 置空棧 SETNULL(seqstack *s) s-top-1; 判棧空 int EMPTY(seqstack *s) if (s-top=0) return FALSE; else return TRUE; ,2019/6/26,8,進(jìn)棧 seqstack *PUSH(seqstack *s,datatype x) if (s-top=maxsize-1) printf(“overflown”);return NULL; else s-top+; s-datas-topx; return s; ,2019/6/26,9,退棧 datatype POP(seqstack *s) if (EMPTY(s) printf(“underflown”);return NULL; else s-top-; return(s-datas-top+1); ,2019/6/26,10,取棧頂 datatype TOP(seqstack *s) if (EMPTY(s) printf(“underflown”);return NULL; else return(s-datas-top); ,2019/6/26,11,兩個堆棧共享空間,0,maxsize-1,lefttop,righttop,2019/6/26,12,棧的鏈接表示 鏈?zhǔn)綏?鏈?zhǔn)綏o棧滿問題，空間可擴(kuò)充 插入與刪除僅在棧頂處執(zhí)行 鏈?zhǔn)綏５臈ｍ斣阪滎^ 適合于多棧操作,2019/6/26,13,棧的鏈接存儲結(jié)構(gòu),鏈棧的結(jié)點(diǎn)定義 typedef int datatype; typedef struct node datatype data; struct node *next; linkstack;,2019/6/26,14,鏈棧的進(jìn)棧算法 linkstack *PUSHLSTACK(linkstack *top, datatype x) linkstack *p; pmalloc(sizeof(linkstack); p-datax; p-nexttop; return p; ,2019/6/26,15,鏈棧的出棧算法 linkstack *POPLSTACK(linkstack *top, datatype *datap) linkstack *p; if (top=NULL) printf(“under flown”); return NULL; else *dataptop-data; ptop; toptop-next; free(p); return top; ,2019/6/26,16,例： 對于一個棧，給出輸入項(xiàng)A、B、C，如果輸入項(xiàng)序列 由ABC組成，試給出所有可能的輸出序列。 A進(jìn) A出 B進(jìn) B出 C進(jìn) C出 ABC A進(jìn) A出 B進(jìn) C進(jìn) C出 B出 ACB A進(jìn) B進(jìn) B出 A出 C進(jìn) C出 BAC A進(jìn) B進(jìn) B出 C進(jìn) C出 A出 BCA A進(jìn) B進(jìn) C進(jìn) C出 B出 A出 CBA 不可能產(chǎn)生輸出序列CAB,2019/6/26,17,棧的應(yīng)用舉例文字編輯器 seqstack s; EDIT() char c; SETNULL( ,2019/6/26,18,棧的應(yīng)用遞歸函數(shù) int FACT(int n) if (n=1) return(1); else return(n*FACT(n-1); ,2019/6/26,19,棧的應(yīng)用表達(dá)式計(jì)算,中綴表達(dá)式：A + ( B C / D) E 后綴表達(dá)式：ABCD/E+ （逆波蘭表達(dá)式） 后綴表達(dá)式特點(diǎn) 1、與相應(yīng)的中綴表達(dá)式中的操作數(shù)次序相同 2、沒有括號,2019/6/26,20,后綴表達(dá)式的處理過程,2019/6/26,21,A,B,C,D,E,A,B,C,T1,A,B,T2,A,T3,2019/6/26,22,中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式,當(dāng)前運(yùn)算符,棧頂運(yùn)算符,2019/6/26,23,中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的處理規(guī)則,1、如為操作數(shù)，直接輸出到隊(duì)列； 2、若當(dāng)前運(yùn)算符為“（”，則直接入棧； 2、如當(dāng)前運(yùn)算符高于棧頂運(yùn)算符，入棧； 3、如當(dāng)前運(yùn)算符低于棧頂運(yùn)算符，棧頂運(yùn)算符退棧， 并輸出到隊(duì)列，當(dāng)前運(yùn)算符再與棧頂運(yùn)算符比較； 4、如當(dāng)前運(yùn)算符為“）”，則將棧中“（”以后的字符依 次彈出存入輸出到隊(duì)列，然后將“）”彈出退棧。繼 續(xù)讀下一符號； 5、如當(dāng)前運(yùn)算符等于棧頂運(yùn)算符，且棧頂運(yùn)算符為 “#”，當(dāng)前運(yùn)算符也為“#”，則棧頂運(yùn)算符退棧， 處理結(jié)束；,2019/6/26,24,2019/6/26,25,2019/6/26,26,隊(duì)列 ( Queue ),定義 隊(duì)列是只允許在一端刪除，在另一端插入的順序表 允許刪除的一端叫做隊(duì)頭(front)，允許插入的一端叫做隊(duì)尾(rear)。 特性 先進(jìn)先出(FIFO, First In First Out),2019/6/26,27,隊(duì)列的進(jìn)隊(duì)和出隊(duì),進(jìn)隊(duì)時(shí)隊(duì)尾指針先進(jìn)一 rear = rear + 1，再將新 元素按 rear 指示位置加入。 出隊(duì)時(shí)隊(duì)頭指針先進(jìn)一 front = front + 1，再將 下標(biāo)為 front 的元素取出。 隊(duì)滿時(shí)再進(jìn)隊(duì)將溢出出錯；隊(duì)空時(shí)再出隊(duì)將隊(duì) 空處理。,2019/6/26,28,順序隊(duì)列的指針說明 typedef struc datatype datamaxsize; int front,rear; sequeue;,2019/6/26,29,隊(duì)列的基本操作,1、置空隊(duì)列 2、判定隊(duì)列是否為空 3、取隊(duì)列頭元素 4、將新元素插入隊(duì)尾 5、隊(duì)列頭元素出隊(duì),2019/6/26,30,順序隊(duì)列置隊(duì)空 SETNULL(sequeue *sq) sq-frontmaxsize-1; sq-rearmaxsize-1; ,2019/6/26,31,順序隊(duì)列判隊(duì)空 int EMPTY(sequeue *sq) if (sq-rear=sq-front) return(TRUE); else return(FALSE); ,2019/6/26,32,順序隊(duì)列取隊(duì)頭元素 datatype FRONT(sequeue *sq) if (EMPTY(sq) printf(“queue is emptyn”); return NULL; else return (sq-front+1)%maxsize); ,2019/6/26,33,順序隊(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); ,2019/6/26,34,順序隊(duì)列出隊(duì) datetype DEQUEUE(sequeue *sq) if (EMPTY(sq) printf(“queue is emptyn”);return NULL; else sq-front(sq-front+1)%maxsize; return(sq-datasq-front); ,2019/6/26,35,存儲隊(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 Queue),2019/6/26,36,循環(huán)隊(duì)列的進(jìn)隊(duì)和出隊(duì),2019/6/26,37,隊(duì)列的鏈接表示 鏈?zhǔn)疥?duì)列,隊(duì)頭在鏈頭，隊(duì)尾在鏈尾。 鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無隊(duì)滿問題，但有隊(duì)空問題。 隊(duì)空條件為 front = NULL,2019/6/26,38,鏈隊(duì)列結(jié)點(diǎn)類型定義 typedef struct node datatype data; struct node *next; linklist; typedef struct linklist *front,*rear; linkqueue;,2019/6/26,39,鏈隊(duì)列置隊(duì)空 SETNULL(linkqueue *q) q-frontmalloc(sizeof(linklist); q-front-nextNULL; q-rearq-front; ,2019/6/26,40,鏈隊(duì)列判隊(duì)空 int EMPTY(linkqueue *q) if q-front=q-rear) return(TRUE); else return(FALSE); ,2019/6/26,41,鏈隊(duì)列取隊(duì)頭結(jié)點(diǎn) datatype FRONT(linkqueue *q) if (EMPTY(q) printf(“queue is emptyn”); return NULL; else return(q-front-next-data); ,2019/6/26,42,鏈隊(duì)列入隊(duì) ENQUEUE(linkqueue *q,datatype x) q-rear-next(linklist *)malloc(sizeof(linklist); q-rearq-rear-next; q-rear-datax; q-rear-nextNULL; ,2019/6/26,43,鏈隊(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); ,2019/6/26,44,1 2 3 4 5 6 7 8,1 2 3 4 5 6,隊(duì)列的應(yīng)用舉例求迷宮的最短路徑,2019/6/26,45,需要解決的問題1：如何從某一坐標(biāo)點(diǎn)出發(fā)搜索其四周的鄰點(diǎn),2019/6/26,46,需要解決的問題2：如何存儲搜索路徑,需要解決的問題3：如何防止重復(fù)到達(dá)某坐標(biāo)點(diǎn),2019/6/26,47,需要解決的問題4：如何輸出搜索路徑,隊(duì)列,2019/6/26,48,#define m 10 #define n 15 typedef struct int x,y; int pre; sqtype; sqtype sq400;,int mgm+1n+1; int zx8, zy8;,2019/6/2