數(shù)據(jù)結(jié)構(gòu)第03章

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)1 1第第3 3章章 堆棧和隊列堆棧和隊列主要知識點主要知識點堆棧堆棧堆棧應(yīng)用堆棧應(yīng)用隊列隊列優(yōu)先級隊列優(yōu)先級隊列數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)2 21.1. 定義定義是一種特殊的線性表，限定只能在表的是一種特殊的線性表，限定只能在表的進(jìn)行插入和刪除操作的線性表。進(jìn)行插入和刪除操作的線性表。特點特點：后進(jìn)先出后進(jìn)先出。堆棧中允許進(jìn)行插入和刪除操作的一堆棧中允許進(jìn)行插入和刪除操作的一端稱為端稱為棧頂棧頂，另一端稱為另一端稱為棧底棧底。3.1 3.1 堆堆 棧棧數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)3 3圖圖3-1 3-1

2、 火車調(diào)度模型火車調(diào)度模型（a a）車軌設(shè)置）車軌設(shè)置 （b b）駛?cè)耄側(cè)?（c c）駛出）駛出 堆棧的功能和火車調(diào)度裝置的功能類同，如圖堆棧的功能和火車調(diào)度裝置的功能類同，如圖3-13-1所示：所示：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)4 4與線性表相同，仍為一對一與線性表相同，仍為一對一( 1:1)關(guān)系關(guān)系。用用或或存儲均可，但以順序棧更常見存儲均可，但以順序棧更常見只能在只能在運算，且訪問結(jié)點時依照運算，且訪問結(jié)點時依照（LIFOLIFO）或）或（FILOFILO）的原則。）的原則。關(guān)鍵是編寫關(guān)鍵是編寫和和函數(shù)，具體實現(xiàn)依順函數(shù)，具體實現(xiàn)依順序?；蜴湕５拇鎯Y(jié)構(gòu)有別而不同。

3、序?；蜴湕５拇鎯Y(jié)構(gòu)有別而不同。3. 存儲結(jié)構(gòu)存儲結(jié)構(gòu)4. 運算規(guī)則運算規(guī)則5. 實現(xiàn)方式實現(xiàn)方式 2. 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)基本操作有基本操作有：建棧、判斷棧滿或?？?、入棧、出棧、建棧、判斷棧滿或?？?、入棧、出棧、讀棧頂元素值等等。讀棧頂元素值等等。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)5 5 是僅在是僅在表尾表尾進(jìn)行插入、刪除操作的線性表。進(jìn)行插入、刪除操作的線性表。表尾表尾(即即 an 端端)稱為稱為棧頂棧頂 /top ; 表頭表頭(即即 a1 端端)稱為稱為棧底棧底/base例如：例如： 棧棧 = (a , a2 , a3 , .,an-1 , an )插入元素到棧頂?shù)牟迦朐氐?/p>

4、棧頂?shù)牟僮?，稱為操作，稱為入棧入棧。從棧頂刪除最后一從棧頂刪除最后一個元素的操作，稱個元素的操作，稱為為出棧出棧。a an n稱為棧頂元素稱為棧頂元素a a0 0稱為棧底元素稱為棧底元素插入和刪除都只能在表插入和刪除都只能在表的一端（棧頂）進(jìn)行！的一端（棧頂）進(jìn)行！注：注：堆棧可以完成比較復(fù)雜的數(shù)據(jù)元素特定序列的轉(zhuǎn)換堆?？梢酝瓿杀容^復(fù)雜的數(shù)據(jù)元素特定序列的轉(zhuǎn)換任務(wù)，但它不能完成任何輸入輸出序列的轉(zhuǎn)換任務(wù)。任務(wù)，但它不能完成任何輸入輸出序列的轉(zhuǎn)換任務(wù)。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)6 6例例1 1：堆棧是什么？它與一般線性表有什么不同？：堆棧是什么？它與一般線性表有什么不同？

5、堆棧是一種特殊的線性表，它只能在表的堆棧是一種特殊的線性表，它只能在表的一端（即一端（即棧頂）棧頂）進(jìn)行插入和刪除運算。進(jìn)行插入和刪除運算。 與一般線性表的區(qū)別：僅在于與一般線性表的區(qū)別：僅在于不同。不同。邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)：1:1 邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)： 1:1 存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)：順序表表、鏈、鏈表表 存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)：順序棧棧、鏈、鏈棧棧運算規(guī)則：運算規(guī)則： 運算規(guī)則：運算規(guī)則：(LIFO)“進(jìn)進(jìn)”插入插入= =壓入壓入“出出”刪除刪除= =彈彈出出數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)7 7例例2 2 一個棧的輸入序列為一個棧的輸入序列為1,2,31,2,3，若在，若

6、在入棧的過程中允入棧的過程中允許出棧，許出棧，則可能得到的出棧序列是什么？則可能得到的出棧序列是什么？解：可以通過窮舉所有可能性來求解：可以通過窮舉所有可能性來求解： 1 1入入1 1出，出， 2 2入入2 2出，出，3 3入入3 3出，出， 即即123123； 1 1入入1 1出，出， 2 2、3 3入，入，3 3、2 2出，出， 即即132132； 1 1、2 2入，入，2 2出，出， 3 3入入3 3出，出， 即即231231； 1 1、2 2入，入，2 2、1 1出，出，3 3入入3 3出，出， 即即213213； 1 1、2 2、3 3入，入，3 3、2 2、1 1出，出， 即即32

7、1321；合計有合計有5 5種可能性。種可能性。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)8 8例例3 3 一個棧的輸入序列是一個棧的輸入序列是1234512345，若在，若在入棧的過入棧的過程中允許出棧程中允許出棧，則棧的輸出序列則棧的輸出序列4351243512可能實現(xiàn)嗎？可能實現(xiàn)嗎？1234512345的輸出呢？的輸出呢？解：解： 4351243512不可能實現(xiàn)，主要是其中的不可能實現(xiàn)，主要是其中的1212順序不能順序不能實現(xiàn)；實現(xiàn)； 1234512345的輸出可以實現(xiàn)，每壓入一數(shù)便立即彈的輸出可以實現(xiàn)，每壓入一數(shù)便立即彈出即可。出即可。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4

8、版版)9 9數(shù)據(jù)集合：數(shù)據(jù)集合：aa0 0, a, a1 1, , , a , an-1n-1 a ai i的的數(shù)據(jù)類型數(shù)據(jù)類型為為DataTypeDataType操作集合操作集合：(1)StackInitiate(S) (1)StackInitiate(S) 初始化堆棧初始化堆棧S S (2)StackNotEmpty(S) (2)StackNotEmpty(S) 堆棧堆棧S S非空否非空否 (3)StackPush(S,x) (3)StackPush(S,x) 入棧入棧 (4)StackPop(S,d) (4)StackPop(S,d) 出棧出棧 (5)StackTop(S,d) (5)S

9、tackTop(S,d) 取棧頂數(shù)據(jù)元素取棧頂數(shù)據(jù)元素 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)10101、順序（堆）棧順序（堆）棧 順序存儲結(jié)構(gòu)的堆棧。順序存儲結(jié)構(gòu)的堆棧。2 2、順序棧的存儲結(jié)構(gòu)、順序棧的存儲結(jié)構(gòu) 它是利用一組地址連續(xù)的存儲單元它是利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時設(shè)指針同時設(shè)指針toptop指示當(dāng)前棧頂位置。指示當(dāng)前棧頂位置。 a0 a1 an-1順序棧順序棧S ai棧底棧底棧頂棧頂數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)1111 其中：其中： stackstack：為：為順序堆棧存放數(shù)據(jù)元素的數(shù)

10、組；順序堆棧存放數(shù)據(jù)元素的數(shù)組； MaxStackSizeMaxStackSize：為為stackstack的最大存儲單元個數(shù)；的最大存儲單元個數(shù)； toptop：為：為堆棧的當(dāng)前棧頂位置。堆棧的當(dāng)前棧頂位置。用用C C語言定義為：語言定義為：typedef structtypedef struct DataType stackMaxStackSize DataType stackMaxStackSize; int int top; top;SeqStackSeqStack; ;a4a3a2a1a001234Top=5棧頂棧頂棧底棧底Stack MaxStackSize-1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用

11、使用C語言語言(第第4版版)1212 a0 a1 an-1順序棧順序棧S S a ai i問：順序表和順序棧的操作有何區(qū)別？問：順序表和順序棧的操作有何區(qū)別？表頭表頭表尾表尾低地址低地址高地址高地址寫入：寫入：Si= Si= a ai i讀出：讀出： e= Sie= Si壓入壓入( (SStop+top+=a=an n彈出彈出( ( e=Se=S-top-top 低地址低地址高地址高地址SiSi a0 a1 a ai i an-1 順序表順序表S S a an n以線性表以線性表S S= (a= (a0 0 , a , a1 , 1 , . , . , a an-2 , n-2 , a an-

12、1n-1) )為例為例棧底棧底棧頂棧頂前提：一定要前提：一定要棧頂指針棧頂指針棧頂棧頂數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)1313棧為空棧為空 的條件的條件 ： top=0;棧滿的條件棧滿的條件 ： top=MaxStackSize; a0 a1 an-1順序棧順序棧S ai低地址低地址高地址高地址 an棧底棧底棧頂棧頂入棧入?？谠E：堆棧指針口訣：堆棧指針top “先先壓后加壓后加” : SStop+top+=a=an n出棧出棧口訣：堆棧指針口訣：堆棧指針top “先先減后彈減后彈” : e=Se=S-top-top 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)1414問：為

13、什么要設(shè)計堆棧？它有什么獨特用途？問：為什么要設(shè)計堆棧？它有什么獨特用途？1.調(diào)用函數(shù)或子程序非它莫屬；調(diào)用函數(shù)或子程序非它莫屬；2.遞歸遞歸運算的有力工具；運算的有力工具；3.用于保護(hù)現(xiàn)場和恢復(fù)現(xiàn)場；用于保護(hù)現(xiàn)場和恢復(fù)現(xiàn)場；4.簡化了程序設(shè)計的問題簡化了程序設(shè)計的問題。下面用例子來幫助理解堆棧：下面用例子來幫助理解堆棧：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)1515void test(int *sum) int x;scanf(“%d”,&x);if(x=0)sum=0;else;sum+=x;printf(sum);斷點地址斷點地址入棧入棧例例1 1 閱讀下列遞歸過程，說

14、明其功能。閱讀下列遞歸過程，說明其功能。輸入輸入x10輸入輸入x50輸入輸入x2輸入輸入x3輸入輸入x4輸出輸出sum0輸出輸出sum0+x4輸出輸出sumx4+x3輸出輸出sum x4+x3 +x2輸出輸出sum x4+x3 +x2+x1注意：最先注意：最先輸入的數(shù)據(jù)輸入的數(shù)據(jù) x x1 1 最后才被最后才被累加累加程序功能：對鍵盤輸入數(shù)程序功能：對鍵盤輸入數(shù)據(jù)求和，直到輸入據(jù)求和，直到輸入0 0結(jié)束結(jié)束數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)16163 3、順序棧的操作實現(xiàn)、順序棧的操作實現(xiàn)(1) (1) 初始化棧初始化棧void StackInitiate(SeqStackvoi

15、d StackInitiate(SeqStack * *S)S)/ /* *初始化順序堆棧初始化順序堆棧S S* */ / S-top = 0; S-top = 0; / /* *定義初始棧頂下標(biāo)值定義初始棧頂下標(biāo)值* */ / 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)1717(2)(2)判棧非空否判棧非空否 int StackNotEmpty(SeqStack int StackNotEmpty(SeqStack S) S)/ /* *判順序堆棧判順序堆棧S S非空否，非空則返回非空否，非空則返回1 1，否則返回，否則返回0 0* */ / if(S.top = 0) if(S.to

16、p top = MaxStackSizeif(S-top = MaxStackSize) ) printf printf(堆棧已滿無法插入堆棧已滿無法插入! n);! n); return 0;return 0; else else S-stack S-stackS-topS-top = x; = x; S- S-top +;top +; return 1; return 1; 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)1919(4)(4)出棧出棧int StackPop(SeqStack int StackPop(SeqStack * *S, DataTypeS, DataType *

17、 *d)d)/ /* *彈出順序堆棧彈出順序堆棧S S的棧頂數(shù)據(jù)元素值到參數(shù)的棧頂數(shù)據(jù)元素值到參數(shù)d d ，出棧成功則返回，出棧成功則返回1 1，否則返回，否則返回0 0* */ / if(S-top top S-top -top -; ; * *d = S-stackd = S-stackS-topS-top; return 1; return 1; 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)2020(5)(5)取棧頂數(shù)據(jù)元素取棧頂數(shù)據(jù)元素int StackTop(SeqStack S, DataTypeint StackTop(SeqStack S, DataType * *d)d)

18、/ /* *取順序堆棧取順序堆棧S S的當(dāng)前棧頂數(shù)據(jù)元素值到參數(shù)的當(dāng)前棧頂數(shù)據(jù)元素值到參數(shù)d d ，成功則返回，成功則返回1 1，否則返回否則返回0 0* */ / if(S.top = 0) if(S.top stackS-top = x;S-stackS-top = x; S-top +;S-top +;toptoptoptoptoptoptoptop低地址低地址L L高地址高地址M MB BC CD D數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)2222例：從棧中取出例：從棧中取出 DCBAtoptopDCABDCBAtopDCBAtop低地址低地址L高地址高地址MD順序棧出棧函數(shù)的

19、核心語句：順序棧出棧函數(shù)的核心語句：S-top -;*d = S-stackS-top;注注：DataType *d； SeqStack *S；數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)2323測試主程序：測試主程序：任務(wù)：任務(wù)：建立一個建立一個順序堆棧順序堆棧，首先依次輸入數(shù)據(jù)元素，首先依次輸入數(shù)據(jù)元素1, 2, 3,.,10，然后，然后依次依次出棧堆棧中的數(shù)據(jù)元素并出棧堆棧中的數(shù)據(jù)元素并顯示。顯示。 假設(shè)該假設(shè)該順序堆棧順序堆棧的數(shù)據(jù)元素個數(shù)在最壞情況下不會超過的數(shù)據(jù)元素個數(shù)在最壞情況下不會超過100個。個。 #include stdio#include .h#define MaxS

20、tackSize #define MaxStackSize 100100typedef int DataTypetypedef int DataType; ;#include #include SeqStackSeqStack.h.h void main(void)void main(void) SeqStack myStackSeqStack myStack; ;intint i , x; i , x;數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)2424StackInitiate(&myStackStackInitiate(&myStack););for(i = 0; i

21、 10; i+)for(i = 0; i next = NULL;head)-next = NULL; （2 2）非空否）非空否StackNotEmptyStackNotEmpty(head)(head)int StackNotEmpty(LSNodeint StackNotEmpty(LSNode * *head)head) if(if(head-nexthead-next = NULL) return 0; = NULL) return 0;else return 1;else return 1; 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)2727(3) (3) 入棧入棧void S

22、tackPush(LSNode void StackPush(LSNode * *head, DataTypehead, DataType x) x) LSNode LSNode * *p;p;p = (LSNode p = (LSNode * *)malloc(sizeof(LSNode)malloc(sizeof(LSNode) ) p-data = x; p-data = x;p-next = head-nextp-next = head-next; ; / /* *新結(jié)點鏈入棧頂新結(jié)點鏈入棧頂* */ /head-next = p;head-next = p; / /* *新結(jié)點成為新

23、的棧頂新結(jié)點成為新的棧頂* */ / 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)2828(4) (4) 出棧出棧int StackPop(LSNode int StackPop(LSNode * *head, DataTypehead, DataType * *d)d) LSNodeLSNode * *p = head-next;p = head-next;if(p = NULL) if(p = NULL) printfprintf(堆棧已空出錯！堆棧已空出錯！););return 0;return 0; head-next = p-next;head-next = p-next;/ /

24、* *刪除原棧頂結(jié)點刪除原棧頂結(jié)點* */ /* *d = p-data; d = p-data; / /* *原棧頂結(jié)點元素賦予原棧頂結(jié)點元素賦予d d* */ /free(p); free(p); / /* *釋放原棧頂結(jié)點內(nèi)存空間釋放原棧頂結(jié)點內(nèi)存空間* */ /return 1;return 1; 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)2929（5 5）取棧頂數(shù)據(jù)元素）取棧頂數(shù)據(jù)元素StackTopStackTop(head, d)(head, d)int StackTop(LSNode int StackTop(LSNode * *head, DataTypehead, D

25、ataType * *d)d) LSNodeLSNode * *p = head-next;p = head-next;if(p = NULL) if(p = NULL) printfprintf(堆棧已空出錯！堆棧已空出錯！););return 0;return 0; * *d = p-data;d = p-data;return 1;return 1; 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)3030（6 6）撤消動態(tài)申請空間）撤消動態(tài)申請空間Destroy(Destroy(* *head)head)void Destroy(LSNodevoid Destroy(LSNode *

26、*head)head) LSNodeLSNode * *p, p, * *p1;p1;p = head;p = head;while(p != NULL)while(p != NULL) p1 = p;p1 = p;p = p-next;p = p-next;free(p1);free(p1); 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)31311)1) 在鏈棧中的頭結(jié)點對操作的實現(xiàn)影響不大，棧頂（表在鏈棧中的頭結(jié)點對操作的實現(xiàn)影響不大，棧頂（表頭）操作頻繁，頭）操作頻繁，可不設(shè)頭結(jié)點可不設(shè)頭結(jié)點鏈棧。鏈棧。2)2) 一般一般不會出現(xiàn)棧滿不會出現(xiàn)棧滿情況；除非沒有空間導(dǎo)致情況；除非沒有空

27、間導(dǎo)致mallocmalloc分分配失敗。配失敗。3)3) 鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，修改指針即可完成。修改指針即可完成。幾點說明幾點說明:數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)32321. 1. 括號匹配問題（書括號匹配問題（書P55P55） 假設(shè)一個算法表達(dá)式中包含圓括號、方括號和花括號假設(shè)一個算法表達(dá)式中包含圓括號、方括號和花括號三種類型的括號，編寫一個判別表達(dá)式中括號是否正確配三種類型的括號，編寫一個判別表達(dá)式中括號是否正確配對的函數(shù)，并設(shè)計一個測試主函數(shù)。對的函數(shù)，并設(shè)計一個測試主函數(shù)。 設(shè)計思路：用棧暫存左

28、括號設(shè)計思路：用棧暫存左括號 括號匹配有括號匹配有四種情況四種情況：（1 1）左右括號配對次序不正確；）左右括號配對次序不正確；（2 2）右括號多于左括號；）右括號多于左括號；（3 3）左括號多于右括號；）左括號多于右括號；（4 4）左右括號匹配正確。）左右括號匹配正確。3.2 堆棧應(yīng)用堆棧應(yīng)用數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)使用使用C語言語言(第第4版版)3333void ExpIsCorrect(char exp, intvoid ExpIsCorrect(char exp, int n) n)/判斷有判斷有n n個字符的字符串個字符的字符串expexp左右括號是否配對正確左右括號是否配對正確 SeqStack myStack SeqStack myStack; ; int int i; i;char c;char c; StackInitiate(&myStack Stack