c語(yǔ)言課件：棧和隊(duì)列.ppt

棧和隊(duì)列,棧 抽象數(shù)據(jù)類型棧的定義 棧的表示和實(shí)現(xiàn) 棧的應(yīng)用舉例 數(shù)制轉(zhuǎn)換 表達(dá)式求解 隊(duì)列,是限制僅在線性表的一端進(jìn)行插入和刪除運(yùn)算的線性表。,棧頂（TOP） 允許插入和刪除的一端。 棧底（bottom) 不允許插入和刪除的一端。 空棧 表中沒(méi)有元素。,棧(Stack),進(jìn)棧 最先插入的元素放在棧的底部。 退棧 最后插入的元素最先退棧。,棧的基本概念,棧:又稱為后進(jìn)先出的線性表（LIFO表，Last In First Out）一疊書或一疊盤子。,棧與子程序調(diào)用,調(diào)用子程序時(shí)，計(jì)算機(jī)將子程序要用到的參數(shù)及返回地址等信息存放在棧里 子程序返回時(shí)，從棧頂取回返回地址，轉(zhuǎn)回主調(diào)程序繼續(xù)運(yùn)行。 處理遞歸調(diào)用,順序棧,用數(shù)組定義（類似于順序表），將棧底位置設(shè)置在向量?jī)啥说娜我庖粋€(gè)端點(diǎn)；用top（整型量，棧頂指針）來(lái)指示棧當(dāng)前棧頂位置。 定義： typedef (type) Element;/*棧元素的數(shù)據(jù)類型*/ #define maxsize 100 /*棧初始的容量*/ typedef struct stack Element datamaxsize; int top; Stack; /*順序棧類型定義*/ Stack *s; /*s是順序棧類型指針*/,3 2 1 0,Top=-1空棧,順序棧：棧頂指針與棧中元素間的關(guān)系,順序棧,棧底位置固定在數(shù)組的低端，即： S-data0-表示棧底元素； 進(jìn)棧：S-TOP加1（正向增長(zhǎng)）。 退棧：S-TOP減1。 空棧： S-TOP TOP=maxsize-1 上溢：棧滿時(shí)再做進(jìn)棧運(yùn)算（一種出錯(cuò)狀態(tài)，應(yīng)設(shè)法避免）。,順序棧的幾種基本運(yùn)算,置空棧 判?？?進(jìn)棧 退棧 取棧頂元素,順序棧的幾種基本運(yùn)算,置空棧：Create(Stack &S),void Create(Stack &S) /*將順序棧S置為空*/ S.top=-1 ,順序棧的幾種基本運(yùn)算,判棧空：,Bool Empty(Stack /* Empty */,void Push(Stack /* Push */,順序棧的幾種基本運(yùn)算,進(jìn)棧：,/*若棧S非空，取出棧頂元素刪除*/ void Pop(Element ,退棧： Pop(S),順序棧的幾種基本運(yùn)算,/*取順序棧S的棧頂*/ Element Top(Stack ,取棧頂： Top(S),順序棧的幾種基本運(yùn)算,鏈棧,棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（當(dāng)順序棧的最大容量事先無(wú)法估計(jì)時(shí)，可采用鏈棧結(jié)構(gòu)）。,TOP,e1 next,棧頂,. .,鏈棧的定義： typedef struct cell* Position; typedef struct cell Element e1; Position next; Cell; typedef struct stack Position *top; Stack;,鏈棧的特點(diǎn),插入和刪除（進(jìn)棧/退棧）僅能在表頭位置上（棧頂）進(jìn)行。 鏈棧中的結(jié)點(diǎn)是動(dòng)態(tài)產(chǎn)生的，可不考慮上溢問(wèn)題。 不需附加頭結(jié)點(diǎn)，棧頂指針就是鏈表（即鏈棧）的頭指針。,void Push(Element e,Stack ,.,棧底,x,s.top,鏈棧進(jìn)棧運(yùn)算,鏈棧退棧運(yùn)算,void Pop(Element ,棧小結(jié),順序棧有發(fā)生上溢 的可能，而鏈棧通常不會(huì)發(fā)生棧滿（除非整個(gè)空間均被占滿） 只要滿足LIFO原則，均可采用棧結(jié)構(gòu)。 棧的應(yīng)用實(shí)例：遞歸調(diào)用。,棧的應(yīng)用舉例一數(shù)制轉(zhuǎn)換,十進(jìn)制N和其它進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問(wèn)題,其解決方法很多,其中一個(gè)簡(jiǎn)單算法基于下列原理: N=(n div d)*d + (n mod d),（185）10 =（ ？ ）8,（1 8 5）10 = （2 7 1）8,棧的應(yīng)用舉例一數(shù)制轉(zhuǎn)換,void conversion( ) /conversion Initstack(S); scanf(“%d”, ,棧的應(yīng)用舉例一數(shù)制轉(zhuǎn)換,棧的應(yīng)用舉例一算術(shù)表達(dá)式,建立2個(gè)棧：操作數(shù)棧及運(yùn)算符棧，初始為空 從左到右讀取表達(dá)式，如果讀到操作數(shù)則置入操作數(shù)棧中，若讀到運(yùn)算符時(shí)則置入運(yùn)算符棧。 當(dāng)讀到的運(yùn)算符優(yōu)先級(jí)比棧中的運(yùn)算符高，則存入棧 當(dāng)讀到的運(yùn)算符優(yōu)先級(jí)比堆棧中的運(yùn)算符低或相等，則取出該運(yùn)算符并從操作數(shù)棧取出相應(yīng)的操作數(shù)運(yùn)算，并將結(jié)果存回操作數(shù)棧；同時(shí)新運(yùn)算符入棧； 堆棧非空 從運(yùn)算符棧中取出一個(gè)運(yùn)算符 從操作數(shù)棧中取出所需操作數(shù) 計(jì)算其值后將結(jié)果存回操作數(shù)棧,例 計(jì)算 2+4-3*6,例 計(jì)算 2+4-3*6,棧的應(yīng)用舉例一算術(shù)表達(dá)式,隊(duì)列,只允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除，是一種先入先出的線性表（FIFO）。,隊(duì)列的基本概念,隊(duì)頭（head):允許刪除（出隊(duì)）的一端 隊(duì)尾（tail):允許插入的一端 空隊(duì)列：隊(duì)列中沒(méi)有元素 進(jìn)隊(duì)：隊(duì)的插入運(yùn)算，即插入新的隊(duì)尾元素 出隊(duì)：隊(duì)的刪除運(yùn)算，刪除隊(duì)首元素,隊(duì)列的基本運(yùn)算,入隊(duì) 出隊(duì) 取隊(duì)頭元素 置空隊(duì)列 判隊(duì)列是否為空,順序隊(duì)列,隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)，用一組連續(xù)的存儲(chǔ)單元依次存放隊(duì)列中的元素 順序隊(duì)列的類型說(shuō)明： typedef struct datatype datam; int head, tail; /*隊(duì)首、隊(duì)尾*/ queue; queue *sq;,B A,D C,3 2 1 0,sq-head sq-tail,sq-head,sq-tail,sq-head sq-tail,sq-tail,sq-head,空隊(duì)列,A、B相繼入隊(duì),A、B相繼出隊(duì),C、D相繼入隊(duì),順序隊(duì)列運(yùn)算時(shí)的頭、尾指針變化,順序隊(duì)列的約定和主要運(yùn)算,隊(duì)頭指針:head總是指向當(dāng)前隊(duì)頭元素 隊(duì)尾指針:tail指向當(dāng)前隊(duì)尾元素的下一個(gè)位置。 初始狀態(tài)：head=tail=0 入隊(duì)運(yùn)算：sq-tail+; /*尾指針加1 */ sq-datasq-tail=x; /* x入隊(duì) */ 出隊(duì)運(yùn)算：sq-head+; /* 頭指針加1 */,順序隊(duì)列的約定和主要運(yùn)算,隊(duì)列長(zhǎng)度：(sq-tail)-(sq-head) 隊(duì)空： (sq-tail)=(sq-head) 下溢： 隊(duì)空時(shí)再作出隊(duì)操作。 隊(duì)滿： (sq-tail)-(sq-head)=m 上溢： 隊(duì)滿時(shí)再作入隊(duì)操作。,順序隊(duì)列的上溢,隊(duì)上溢： 真上溢（r-f=m)：隊(duì)列真正滿時(shí)再入隊(duì)。 假上溢：r已指向數(shù)組尾端，但隊(duì)列前端仍有空位置。 解決假上溢的方法： 方法一：每次刪除隊(duì)頭一個(gè)元素后，把整個(gè)隊(duì)列往前移一個(gè)位置（造成時(shí)間浪費(fèi)）。 方法二：循環(huán)隊(duì)列,Setnull(queue *sq) sq-head0; sq-tail0; ,順序隊(duì)列置隊(duì)空,Bool Empty(queue *sq) if (sq-tail = sq-head) return (True); else return (False); ,順序隊(duì)列判隊(duì)空,datatype Front(queue *sq) datatype temp; if (Empty(sq) printf(“queue is emptyn”); return NULL; else temp= sq-data sq-head; return temp ; ,順序隊(duì)列取隊(duì)頭元素,Bool Enqueue(queue *sq, datatype x) if (sq-head= =(sq-tail+1)%m) printf(“queue is fulln”; return NULL); else sq-tail(sq-tail+1); sq-datasq-tailx; return(True); ,順序隊(duì)列入隊(duì),datetype Dequeue(queue *sq) if (Empty(sq) printf(“queue is emptyn”);return NULL; else sq-head(sq-head+1); return(sq-datasq-head); ,順序隊(duì)列出隊(duì),循環(huán)隊(duì)列 (Circular Queue),當(dāng)隊(duì)尾指針tail等于MaxSize時(shí)，無(wú)論有否空間，都無(wú)法再將數(shù)據(jù)存于隊(duì)列中 將所用的數(shù)組sq-datam設(shè)想為首尾相接的循環(huán)數(shù)組（即：data0連在datam-1之后)。,tail,head,循環(huán)隊(duì)列的進(jìn)隊(duì)和出隊(duì),空隊(duì)列,循環(huán)隊(duì)列 (Circular Queue),隊(duì)列入隊(duì)： 若尾指針 r 等于向量的上界，再入隊(duì)，令尾指針等于向量的下界，即：在循環(huán)意義下的尾指針的加1操作可描述為： if(sq-tail+1=m) sq-tail=0; else sq-tail+;,循環(huán)隊(duì)列 (Circular Queue),存儲(chǔ)隊(duì)列的數(shù)組被當(dāng)作首尾相接的表處理。 隊(duì)頭、隊(duì)尾指針加1時(shí)從maxSize -1直接進(jìn)到0，可用語(yǔ)言的取模(余數(shù))運(yùn)算實(shí)現(xiàn)。 隊(duì)頭指針進(jìn)1: head = (head + 1) % maxSize; 隊(duì)尾指針進(jìn)1: tail = (tail + 1) % maxSize; 隊(duì)列初始化：head =tail = 0; 隊(duì)空條件：head= = tail; 隊(duì)滿條件：(tail + 1) % maxSize = = head,Q-head,data next,隊(duì)頭,. .,Q-tail,隊(duì)尾,隊(duì)列的鏈接表示 鏈?zhǔn)疥?duì)列,隊(duì)頭在鏈頭，隊(duì)尾在鏈尾。 鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無(wú)隊(duì)滿問(wèn)題，但有隊(duì)空問(wèn)題。 隊(duì)空條件為 head = NULL,隊(duì)列的鏈接表示 鏈?zhǔn)疥?duì)列,typedef struct linklist *head,*tail; linkqueue;,鏈隊(duì)列結(jié)點(diǎn)類型定義,Setnull (linkqueue *q) q-headmalloc(sizeof(linklist); q-head-nextNULL; q-tailq-head; ,鏈隊(duì)列置隊(duì)空,int Empty(linkqueue *q) if ( q-head = q-tail ) return(True); else return(False); ,鏈隊(duì)列判隊(duì)空,datatype Front(linkqueue *q) if (Empty(q) printf(“queue is emptyn”); return NULL; else return(q-head-next-data); ,鏈隊(duì)列取隊(duì)頭結(jié)點(diǎn),Enqueue(linkqueue *q, datatype x) pmalloc(sizeof(linklist); p -data=x; p -next=null; q-tail-nextp; q-tailp; ,鏈隊(duì)列入隊(duì),datatype Dequeue(linkqueue *q, datatype e) linklist *p; if (Empty(q) printf(“queue is emptyn”); return NULL; else pq-head-next; ep-data; q-head-next= p-next free(p); return(p); ,鏈隊(duì)列出隊(duì),棧和隊(duì)列作業(yè)