c語言課件：棧和隊列.ppt

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