數(shù)據(jù)結(jié)構(gòu)棧和隊列.ppt

1、數(shù)據(jù)結(jié)構(gòu),教學(xué)目標(biāo),【知識目標(biāo)】 掌握棧的定義及基本運算 掌握順序棧、鏈?；具\算的實現(xiàn)算法 掌握隊列的定義及基本運算 掌握循環(huán)隊列、鏈隊列基本運算的實現(xiàn)算法 【能力目標(biāo)】 具有恰當(dāng)?shù)倪x擇?；蜿犃凶鳛閿?shù)據(jù)的邏輯結(jié)構(gòu)，順序棧（隊列）、鏈棧（隊列）作為數(shù)據(jù)的存儲結(jié)構(gòu)的能力 具有應(yīng)用棧、隊列解決實際問題的能力,引例描述數(shù)制轉(zhuǎn)換,將十進(jìn)制數(shù)F轉(zhuǎn)換為B進(jìn)制數(shù)。輸入任意一個十進(jìn)制數(shù)，可以是整數(shù)，也可以是小數(shù)，輸出對應(yīng)進(jìn)制的數(shù)。,演示執(zhí)行,一、棧的定義及基本操作 1.定義 棧（Stack）是限制僅在表的一端進(jìn)行插入和刪除運算的線性表。向棧中插入元素稱為進(jìn)（入）棧，從棧中刪除元素稱為出（退）棧。 通常插入、刪

2、除的這一端稱為棧頂（Stack Top），由于元素的進(jìn)棧和退棧，使得棧頂?shù)奈恢媒?jīng)常是變動的，因此需要用一個整型量Top指示棧頂?shù)奈恢?，通常稱Top 為棧頂指針；另一端稱為棧底。當(dāng)表中沒有元素時稱為空棧，即Top=-1。 棧為后進(jìn)先出（Last In First Out）的線性表，簡稱為LIFO表。,3.1 棧,知識儲備,2棧的基本運算 （1）置空棧：InitStack (S) 構(gòu)造一個空棧S。 （2）判?？眨篠tackEmpty (S) 若S為空棧，則返回1，否則返回0。 （3）判棧滿：StackFull (S) 若S為滿棧，則返回1，否則返回0。 （4）進(jìn)棧：Push(S，x) 若棧S不滿，

3、則將元素x插入S的棧頂。 （5）退棧：Pop (S) 若棧S非空，則將S的棧頂元素刪去，并返回該元素。 （6）取棧頂元素：StackTop (S) 若棧S非空，則返回棧頂元素，但不改變棧的狀態(tài)。,二、順序棧及基本操作的實現(xiàn) 1順序棧（Sequence Stack） 棧的順序存儲結(jié)構(gòu)簡稱為順序棧，它是運算受限的順序表。 2順序棧的描述 #define StackSize 100 /假定棧空間最多為100個元素 typedef char DataType;/假定棧元素的類型為字符類型 typedef struct DataType dataStackSize;/棧元素定義 int top;/棧指針

4、定義 SeqStack; SeqStack *S;/棧定義,注意： 有元素x進(jìn)棧時，需要先將S-top加1，然后再將元素進(jìn)棧，即依次完成下列操作：+S-top;S-dataS- top=x;； 當(dāng)棧頂元素做退棧操作后，需要將S-top減1，即完成操作：S-top-;； 條件S-top=StackSize-1表示棧滿；S-top=-1表示?？?； 當(dāng)棧滿時，再做進(jìn)棧運算所產(chǎn)生的空間溢出現(xiàn)象稱為上溢。上溢是一種出錯狀態(tài)，應(yīng)設(shè)法避免； 當(dāng)?？諘r，做退棧運算所產(chǎn)生的溢出現(xiàn)象稱為下溢。,3順序棧上基本運算的算法 （1）置?？?（2）判?？?如果棧S為空，則S-top=-1，此時應(yīng)該返回1，而關(guān)系表達(dá)式S-

5、top=-1的值為1；如果棧S為非空，則S-top!=-1，此時應(yīng)該返回0，而關(guān)系表達(dá)式S-top=-1的值為0，因此，無論怎樣只需返回S-top=-1的值。 （3）判棧滿 與判?？盏牡览硐嗤?，只需返回S-top=StackSize-1。 （4）進(jìn)棧 （5）出棧 （6）取棧頂元素,（1）置?？?void InitStack(SeqStack *S) /將順序棧置空 S-top=-1; ,（2）判?？?int StackEmpty(SeqStack *S) /判棧空 return S-top=-1; ,（3）判棧滿 int StackFull(SeqStack *S) /判棧滿 return S

6、-top=StackSize-1; ,（4）進(jìn)棧 int Push(SeqStack *S,DataType x) /進(jìn)棧 if (StackFull(S) puts(棧滿); return 0; S-data+S-top=x; return 1; ,（5）出棧 int Pop(SeqStack *S, DataType *x) /出棧 if(StackEmpty(S) puts(?？?; return 0; *x=S-dataS-top-; return 1; ,（6）取棧頂元素 int StackTop(SeqStack *S, DataType *x) if(StackEmpty(S)

7、puts(?？?; return 0; *x=S-dataS-top; return 1; ,【例3-1】元素a1，a2，a3，a4依次進(jìn)入順序棧，則下列不可能的出棧序列是 Aa4, a3, a2, a1Ba3, a2, a4, a1 Ca3, a4, a2, a1Da3, a1, a4, a2 分析：對于A，由于元素a1，a2，a3，a4依次進(jìn)棧，而a4先出棧，說明a1，a2，a3已經(jīng)入棧，所以出棧順序只能是a4，a3，a2，a1，因此A是正確的出棧序列；對于B，C，D，由于都是a3先出棧，說明a1，a2已經(jīng)入棧，所以a1，a2的相對位置一定是不變的，這就是a2一定在a1之前出棧，比較上述三

8、個答案，只有D中的a1出現(xiàn)在a2的前面，這顯然是錯誤的。因此，答案為D。,【課堂實踐3-1】 設(shè)計一個選擇菜單，根據(jù)用戶的選擇決定對順序棧進(jìn)行置空棧、進(jìn)棧、退棧、取棧頂元素和退出程序的操作。,做 一 做,三、鏈棧及基本操作的實現(xiàn) 1鏈棧（Linked Stack） 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧，棧頂指針就是鏈表的頭指針。 2鏈棧的描述 typedef char DataType;/假定棧元素的類型為字符類型 typedef struct stacknode /結(jié)點的描述 DataType data; struct stacknode *next; StackNode; typedef struct

9、 /棧的描述 StackNode *top; /棧頂指針 LinkStack;,注意： LinkStack結(jié)構(gòu)類型的定義是為了方便在函數(shù)體中修改top指針本身； 若要記錄棧中元素個數(shù)，可將元素個數(shù)屬性作為LinkStack類型中的成員定義； 條件S-top= NULL表示空棧，鏈棧沒有棧滿的情況。 3鏈棧上基本運算的算法 （1）置?？?（2）判棧空 （3）進(jìn)棧 （4）出棧 （5）取棧頂元素,（1）置?？?void InitStack(LinkStack *S) /將鏈棧置空 S-top=NULL; ,（2）判?？?int StackEmpty(LinkStack *S) return S-to

10、p=NULL; ,（3）進(jìn)棧 int Push(LinkStack *S,DataType x) /將元素x插入鏈棧頭部 StackNode *p=(StackNode *)malloc(sizeof(StackNode); if(p=NULL) puts (內(nèi)存申請不成功!);return 0; p-data=x; p-next=S-top;/將新結(jié)點*p插入鏈棧頭部 S-top=p; /棧頂指針指向新結(jié)點 return 1; ,（4）出棧 int Pop(LinkStack *S, DataType *x) /出棧 StackNode *p=S-top;/保存棧頂指針 if(StackEm

11、pty(S) puts(?？?; return 0; *x=p-data; /保存棧頂結(jié)點數(shù)據(jù) S-top=p-next; /將棧頂結(jié)點從鏈上摘下 free(p); return 1; ,（5）取棧頂元素 int StackTop(LinkStack *S, DataType *x) /取棧頂元素 if(StackEmpty(S) puts(?？?; return 0; *x =S-top-data; return 1; ,【課堂實踐3-2】 設(shè)計一個選擇菜單，根據(jù)用戶的選擇決定對鏈棧進(jìn)行置空棧、進(jìn)棧、出棧、取棧頂元素和退出程序的操作。,做 一 做,3.2 隊列 一、隊列的定義及基本操作 1隊

12、列的定義 隊列（Queue）是只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的運算受限的線性表。向隊列中插入元素稱為入隊，從隊列中刪除元素稱為出隊。 (1)允許刪除的一端稱為隊頭（Front）。 (2)允許插入的一端稱為隊尾（Rear）。 (3)當(dāng)隊列中沒有元素時稱為空隊列。 (4)隊列亦稱作先進(jìn)先出（First In First Out）的線性表，簡稱為FIFO表。,2隊列的基本運算 （1）置空隊：InitQueue (Q)構(gòu)造一個空隊列Q。 （2）判隊空：QueueEmpty (Q)若隊列Q為空，則返回1，否則返回0。 （3）判隊滿：QueueFull (Q)若隊列Q為滿，則返回1，否則返回0。

13、 （4）入隊：EnQueue(Q，x)若隊列Q非滿，則將元素x插入Q的隊尾。 （5）出隊：DeQueue (Q)若隊列Q非空，則刪去Q的隊頭元素，并返回該元素。 08順序隊列操作.swf （6） 取隊頭元素：QueueFront (Q)若隊列Q非空，則返回隊頭元素，但不改變隊列Q的狀態(tài)。,二、順序隊列及基本操作 1順序隊列（Sequence Queue） 隊列的順序存儲結(jié)構(gòu)稱為順序隊列，它是運算受限的順序表。 2順序隊列的表示 （1）和順序表一樣，順序隊列用一個數(shù)組（向量空間）來存放當(dāng)前隊列中的元素。 （2）由于隨著入隊和出隊操作的變化，隊列的隊頭和隊尾的位置是變動的，所以應(yīng)設(shè)置兩個整型量fr

14、ont和rear分別指示隊頭和隊尾在向量空間中的位置，它們的初值在隊列初始化時均應(yīng)置為0。通常稱front為隊頭指針，稱rear為隊尾指針。,3順序隊列的基本操作 （1）入隊：入隊時將新元素插入rear所指的位置，然后將rear加1。 （2）出隊：出隊時刪去front所指的元素，然后將front加1并返回被刪元素。 注意： （1）當(dāng)頭尾指針相等時，隊列為空。 （2）在非空隊列里，隊頭指針始終指向隊頭元素，尾指針始終指向隊尾元素的下一位置。,4順序隊列中的溢出現(xiàn)象 （1）“下溢”現(xiàn)象：當(dāng)隊列為空時，做出隊操作產(chǎn)生的溢出現(xiàn)象。 （2）“真上溢”現(xiàn)象：當(dāng)隊列滿時，做入隊操作產(chǎn)生空間溢出的現(xiàn)象?！罢嫔?/p>

15、溢”是一種出錯狀態(tài)，應(yīng)設(shè)法避免。 （3）“假上溢”現(xiàn)象：由于入隊和出隊操作中，頭尾指針只增加不減少，致使被刪元素的空間永遠(yuǎn)無法重新利用。當(dāng)隊列中實際元素個數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模時，也可能由于尾指針已超越向量空間的上界而不能做入隊操作。該現(xiàn)象稱為“假上溢”現(xiàn)象。 5解決“假上溢”現(xiàn)象的方法 （1）當(dāng)出現(xiàn)“假上溢”現(xiàn)象時，把所有的元素向低位移動，使得空位從低位區(qū)移向高位區(qū)，顯然這種方法很浪費時間。 （2）把隊列的向量空間的元素位置0Queuesize-1看成一個首尾相接的環(huán)形，當(dāng)進(jìn)隊的隊尾指針等于最大容量，即rear=Queuesize時，使rear=0。,三、循環(huán)隊列 1循環(huán)隊列（Cirula

16、r Queue） 把向量空間的元素位置首尾相接的順序隊列稱為循環(huán)隊列。 2循環(huán)隊列頭尾指針的操作 循環(huán)隊列Q進(jìn)行出隊、入隊操作時，頭尾指針仍要加1。當(dāng)頭尾指針指向向量上界（QueueSize-1）時，其加1操作的結(jié)果是指向向量的下界0。這種循環(huán)意義下的加1操作可以描述為： （1）利用選擇結(jié)構(gòu) （2）利用模運算 我們將采用此方法實現(xiàn)循環(huán)意義下的隊頭、隊尾指針的加1操作。,（1）利用選擇結(jié)構(gòu) if(i+1=QueueSize)/i為Q-front或Q-rear i=0; else i+;,（2）利用模運算 i=(i+1)%QueueSize;/i為Q-front或Q-rear,3循環(huán)隊列邊界條件的

17、處理方法 由于循環(huán)隊列Q中，無法通過條件Q-front= Q-rear來判別隊列是“空”還是“滿”。解決這個問題的方法至少有三種： （1）另設(shè)一標(biāo)志變量flag以區(qū)別隊列的空和滿，比如當(dāng)條件Q-front= Q-rear成立，且 flag 為0時表示隊列空，而為1時表示隊列滿。 （2）少用一個元素的空間。約定入隊前，測試尾指針在循環(huán)意義下加1后是否等于隊頭指針，若相等則認(rèn)為隊滿，此時隊空的條件是Q-front= Q-rear，隊滿的條件是(Q-rear+1)%QueueSize= Q-front。 （3）使用一個計數(shù)器count記錄隊列中元素的總數(shù)，當(dāng)Q-count =0時表示隊列空；當(dāng)Q-c

18、ount =QueueSize時表示隊列滿。 我們將使用此方法。,4循環(huán)隊列的描述 #define QueueSize 100 /定義隊列最大容量 typedef char DataType; /定義隊列元素類型 typedef struct cirqueue DataType dataQueueSize;/隊列元素定義 int front;/隊頭指針定義 int rear;/隊尾指針定義 int count;/計數(shù)器定義 CirQueue; CirQueue *Q; /定義循環(huán)隊列Q,5循環(huán)隊列的基本運算的算法 （1） 置隊空 （2）判隊空 （3）判隊滿 （4）入隊 （5）出隊 （6）取隊頭

19、元素,（1） 置隊空 void InitQueue(CirQueue *Q) Q-front=Q-rear=0; Q-count=0;/計數(shù)器置0 ,（2）判隊空 int QueueEmpty(CirQueue *Q) return Q-count=0; /隊列無元素為空 ,（3）判隊滿 int QueueFull(CirQueue *Q) return Q-count=QueueSize; ,（4）入隊 int EnQueue(CirQueue *Q,DataType x) if(QueueFull(Q) puts(隊滿); return 0; Q-count +;/隊列元素個數(shù)加1 Q-d

20、ataQ-rear=x;/新元素插入隊尾 Q-rear=(Q-rear+1)%QueueSize;/循環(huán)意義下將尾指針加1 return 1; ,（5）出隊 int DeQueue(CirQueue *Q ,DataType *x) if(QueueEmpty(Q) puts(隊空); return 0; *x=Q-dataQ-front; Q-count-;/隊列元素個數(shù)減1 Q-front=(Q-front+1)%QueueSize;/循環(huán)意義下的頭指針加1 return 1; ,（6）取隊頭元素 int QueueFront(CirQueue *Q ,DataType *x) if(Qu

21、eueEmpty(Q) puts(隊空); return 0; *x=Q-dataQ-front; return 1; ,【課堂實踐3-3】 設(shè)計一個選擇菜單，根據(jù)用戶的選擇決定對循環(huán)隊列進(jìn)行置空隊、進(jìn)隊、退隊、取隊頭元素和退出程序的操作。,做 一 做,四、鏈隊列及基本操作的實現(xiàn) 1鏈隊列（Linked Queue） 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈隊列，它是限制僅在表頭刪除和表尾插入的單鏈表。由于需要在表尾進(jìn)行插入操作，所以為操作方便除頭指針外有必要再增加一個指向尾結(jié)點的指針。 2鏈隊列的描述 設(shè)Q是LinkQueue類型的指針變量，則Q是指向鏈隊列的指針，隊頭指針、隊尾指可分別表示為Q-front

22、、Q- rear。 設(shè)p是QueueNode類型的指針變量，則p是指向鏈隊列某結(jié)點的指針，該結(jié)點的數(shù)據(jù)域可表示為p -data，該結(jié)點的指針域可表示為p - next。 鏈隊列如圖3-5：,2鏈隊列的描述 typedef char DataType; /定義隊列元素類型 typedef struct queuenode /隊列中結(jié)點的類型 DataType data; struct queuenode *next; QueueNode; typedef struct QueueNode *front;/隊頭指針 QueueNode *rear; /隊尾指針 LinkQueue; LinkQue

23、ue *Q; /定義鏈隊列Q,3鏈隊列的基本運算 由于鏈隊列結(jié)點的存儲空間是動態(tài)分配的，所以無須考慮判隊滿的運算。 （1）置隊空 （2）判隊空 （3）入隊 （4）出隊 （5）取隊頭元素 注意：在出隊算法中，一般只需修改隊頭指針。但當(dāng)原隊中只有一個結(jié)點時，該結(jié)點既是隊頭也是隊尾，故刪去此結(jié)點時亦需修改尾指針，且刪去此結(jié)點后隊列變空。,（1）置隊空 void InitQueue(LinkQueue *Q) Q-front=Q-rear=NULL; ,（2）判隊空 int QueueEmpty(LinkQueue *Q) return Q-front=NULL; ,（3）入隊 int EnQueue

24、(LinkQueue *Q,DataType x) /將元素x插入鏈隊列尾部 QueueNode *p; p=(QueueNode *)malloc(sizeof(QueueNode); if(p=NULL) puts (空間申請失敗!);return 0; p-data=x; p-next=NULL; if(QueueEmpty(Q) Q-front=Q-rear=p;/將x插入空隊列 else /x插入非空隊列的尾 Q-rear-next=p;/*p鏈到原隊尾結(jié)點后 Q-rear=p;/隊尾指針指向新的尾 return 1; ,（4）出隊 int DeQueue(LinkQueue *Q,

25、 DataType *x) QueueNode *p; if(QueueEmpty(Q) puts(隊空); return 0; p=Q-front;/指向隊頭結(jié)點 *x=p-data;/保存隊頭結(jié)點的數(shù)據(jù) Q-front=p-next;/將對頭結(jié)點從鏈上摘下 if(Q-rear=p） Q-rear=NULL; free(p);/釋放被刪隊頭結(jié)點 return 1; ,（5）取隊頭元素 int QueueFront(LinkQueue *Q, DataType *x) if(QueueEmpty(Q) puts(隊空); return 0; *x=Q-front-data; return 1;

26、 ,【課堂實踐3-4】 設(shè)計一個選擇菜單，根據(jù)用戶的選擇決定對鏈隊列進(jìn)行置空隊、進(jìn)隊、退隊、取隊頭元素和退出程序的操作。,做 一 做,引例分析與實現(xiàn),1引例分析 十進(jìn)制數(shù)F可分解為F=N+M，其中N為十進(jìn)制整數(shù)，M為十進(jìn)制純小數(shù)轉(zhuǎn)換為B進(jìn)制數(shù)，分為十進(jìn)制整數(shù)轉(zhuǎn)換為B進(jìn)制整數(shù)和十進(jìn)制純小數(shù)轉(zhuǎn)換為B進(jìn)制純小數(shù)數(shù)兩部分。 （1）將十進(jìn)制整數(shù)轉(zhuǎn)換為B進(jìn)制整數(shù) 將十進(jìn)制整數(shù)轉(zhuǎn)換為B進(jìn)制整數(shù)，通常采用的方法是“B除取余法”。 【示例】將365轉(zhuǎn)換為16進(jìn)制數(shù) 采用16除取余法，如圖3-6。 得365轉(zhuǎn)換為16進(jìn)制數(shù)為16D。,算法思路：定義一個指向鏈棧的指針S，通過函數(shù)malloc確定S的指向，并對鏈棧進(jìn)行初始化，當(dāng)N=0時，輸出一個0，當(dāng)N!=0時，重復(fù)進(jìn)行將N被B除的余數(shù)N%B入棧S，并將所得的商N/B作為被除數(shù)，即將N/B賦給N，直到N的值為0，這樣，得到的余數(shù)已經(jīng)全部入棧S；只要棧S不空，作出棧操作，并輸出，如果出棧元素大于等于10，通過加87輸出對應(yīng)字符（基數(shù)大于10的大于等于10的數(shù)碼用對應(yīng)字母來表示）。,引例分析與實現(xiàn),（2）將十進(jìn)制純小數(shù)轉(zhuǎn)換為B進(jìn)制純小數(shù) 將十進(jìn)制純小數(shù)轉(zhuǎn)換為B進(jìn)制純小數(shù)，通常采用的方法是“B乘取整法