數(shù)據(jù)結(jié)構(gòu)課件：第2章 線性表、堆棧和隊(duì)列

1、第二章 線性表、堆棧和隊(duì)列 2.1 線性表的定義和基本操作2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)2.4 復(fù)雜性分析2.5 堆棧2.6 隊(duì)列2.5 堆 棧2.5.1 堆棧的定義和主要操作2.5.2 順序棧2.5.3 鏈?zhǔn)綏?.5.4 順序棧與鏈?zhǔn)綏５谋容^2.5.5 堆棧的應(yīng)用1、堆棧的定義棧的定義：棧是插入和刪除只能在其一端進(jìn)行的線性表,并按后進(jìn)先出的原則進(jìn)行操作。棧頂：進(jìn)行插入、刪除的一端；棧底：另一端；空棧：表中沒有元素時(shí)。a5a3a2a1 a4進(jìn)棧出棧棧頂棧底例 線性表 (a1, a2, , a5)，進(jìn)棧出棧情況 棧的后進(jìn)先出性：可以對(duì)輸入序列部分或全局求逆；凡符合后進(jìn)先

2、出性，都可應(yīng)用棧，如十進(jìn)制數(shù)與其它數(shù)制的轉(zhuǎn)換、遞歸的實(shí)現(xiàn)、算數(shù)表達(dá)式求值等問題。棧的封閉性：除了棧頂元素外，其他元素不會(huì)被改變。因而，棧的封閉性非常好，使用起來非常安全。2、堆棧的基本操作（1）棧初始化（2）進(jìn)棧 Push（3）出棧 Pop（4）讀取棧頂元素 Peek（5）判?？?StackEmpty（6）判棧滿 StackFull （7）置空棧 2.5 堆 棧2.5.1 堆棧的定義和主要操作2.5.2 順序棧2.5.3 鏈?zhǔn)綏?.5.4 順序棧與鏈?zhǔn)綏５谋容^2.5.5 堆棧的應(yīng)用堆棧的順序存儲(chǔ) 使用數(shù)組存放棧元素，棧的規(guī)模必須小于或等于數(shù)組的規(guī)模，當(dāng)棧的規(guī)模等于數(shù)組的規(guī)模時(shí)，就不能再向棧中插

3、入元素。 棧頂所在數(shù)組元素的下標(biāo)： int top; 堆?？眨?top = -1 堆棧滿： top = MaxStackSize-1top1230-1top1230ACBtop1230ABtop1230Atop1230-1棧內(nèi)變化情況順序棧AStack的類定義template class AStack private: int size ;/ 數(shù)組的規(guī)模 T * stackArray ; / 存放堆棧元素的數(shù)組 int top ; / 棧頂所在數(shù)組元素的下標(biāo)public: AStack ( int MaxStackSize ) / 構(gòu)造函數(shù) size = MaxStackSize ; stac

4、kArray = new T MaxStackSize ; top = -1 ; AStack ( ) delete stackArray ; / 析構(gòu)函數(shù)bool Push ( const T& item ) ; / 向棧頂壓入一個(gè)元素bool Pop ( T & item ) ; / 從棧頂彈出一個(gè)元素bool Peek ( T & item ) const ; / 存取棧頂元素int IsEmpty ( void ) const return top = = -1 ; / 檢測(cè)棧是否為空int IsFull ( void ) const return top size-1 ; / 檢測(cè)棧

5、是否為滿void clear ( void ) top-1 ; / 清空棧 ;算法 Push (A, item) / 向順序棧A中壓入一個(gè)元素itemP1. 棧滿？ IF topsize-1 THEN (PRINT“棧滿無法壓入”. RETURN.)P2. 入棧 toptop1. / 更新棧頂元素的下標(biāo) Atopitem. / 壓入新棧頂元素 top1230-1top1230ABtop1230A堆棧變化情況top1230ACB算法 Pop (A. item) / 從順序棧A中彈出棧頂元素，并存放在變量item中P1. ?？眨?IF top -1 THEN (PRINT“?？諢o法彈出”. RET

6、URN.)P2. 出棧 itemAtop. / 保存棧頂元素值 toptop-1. / 更新棧頂元素的下標(biāo) top1230ACBtop1230ABtop1230-1top1230A堆棧變化情況算法 Peek (A, item) / 將順序棧A的棧頂元素存放在變量item中P1. ?？?？IF top -1 THEN (PRINT“?？铡? RETURN.)P2. 讀取棧頂元素 itemAtop. / 保存棧頂元素值 與pop的區(qū)別是什么？top top-12.5 堆 棧2.5.1 堆棧的定義和主要操作2.5.2 順序棧2.5.3 鏈?zhǔn)綏?.5.4 順序棧與鏈?zhǔn)綏５谋容^2.5.5 堆棧的應(yīng)用2.5

7、.3 堆棧的鏈?zhǔn)酱鎯?chǔ)用單鏈表實(shí)現(xiàn)堆棧要為每個(gè)棧元素分配一個(gè)額外的指針空間。首先考慮棧頂對(duì)應(yīng)鏈表的表頭還是表尾。因?yàn)槎褩Ｖ饕僮鳎ú迦?、刪除、存?。┑膶?duì)象是棧頂元素，若棧頂對(duì)應(yīng)表尾，則每次操作的時(shí)間復(fù)雜性為O(n) ；若棧頂對(duì)應(yīng)表頭，則每個(gè)操作的時(shí)間復(fù)雜性是O(1)，顯然，棧頂對(duì)應(yīng)表頭是合理的。另外，鏈?zhǔn)綏Ｖ胁恍枰谖唤Y(jié)點(diǎn)。 鏈?zhǔn)綏Stack的類定義template class LStackprivate : SLNode * top ;/ 棧頂指針指向表頭public : LStack ( ) top = NULL ; / 構(gòu)造函數(shù) LStack ( ) clear ( ) ; / 析構(gòu)函數(shù)

8、void clear ( ) ; / 清空棧bool Push ( const T& item ) ; / 向棧頂壓入一個(gè)元素bool Pop ( T & item ) ; / 從棧頂彈出一個(gè)元素bool Peek ( T & item ) const ; / 讀取棧頂元素int IsEmpty ( void ) const return top = = NULL ; / 檢測(cè)棧是否為空 ;算法 Push (item) / 向棧頂指針為top的鏈?zhǔn)綏Ｖ袎喝胍粋€(gè)元素item P1. 創(chuàng)建新結(jié)點(diǎn) sAVAIL. /為新結(jié)點(diǎn)申請(qǐng)空間 data(s) item. next(s) top. / 新結(jié)點(diǎn)的

9、數(shù)據(jù)域存放item，指針域存放原棧頂結(jié)點(diǎn)的地址信息P2. 更新棧頂指針 tops. / 更新棧頂指針，令其指向新入棧結(jié)點(diǎn)算法 Pop ( item) / 從棧頂指針為top的鏈?zhǔn)綏Ｖ袕棾鰲ｍ斣?，并存放在變量item中P1. ?？?？ IF top= NULL THEN (PRINT“?？諢o法彈出”. RETURN.)P2. 出棧 itemdata(top). / 保存棧頂結(jié)點(diǎn)的字段值 qnext(top). / 令指針q指向次棧頂結(jié)點(diǎn) AVAILtop. / 釋放棧頂結(jié)點(diǎn)的空間 topq./ 更新棧頂指針，令其指向q所指結(jié)點(diǎn) 算法 Peek ( item) / 將棧頂指針為top的鏈?zhǔn)綏５臈ｍ?/p>

10、元素存放在變量item中P1. ?？?？IF topNULL THEN (PRINT“?？铡? RETURN.)P2. 存取棧頂 itemdata(top). / 將棧頂結(jié)點(diǎn)的字段值保存在變量item中 2.5 堆 棧2.5.1 堆棧的定義和主要操作2.5.2 順序棧2.5.3 鏈?zhǔn)綏?.5.4 順序棧與鏈?zhǔn)綏５谋容^2.5.5 堆棧的應(yīng)用順序棧與鏈?zhǔn)綏５谋容^在空間復(fù)雜性上，順序棧必須初始就申請(qǐng)固定的空間，當(dāng)棧不滿時(shí)，必然造成空間的浪費(fèi)；鏈?zhǔn)綏Ｋ杩臻g是根據(jù)需要隨時(shí)申請(qǐng)的，其代價(jià)是為每個(gè)元素提供空間以存儲(chǔ)其next指針域。在時(shí)間復(fù)雜性上，對(duì)于針對(duì)棧頂?shù)幕静僮鳎▔喝?、彈出和棧頂元素存?。樞驐：?/p>

11、鏈?zhǔn)綏５臅r(shí)間復(fù)雜性均為O(1) . 2.5 堆 棧2.5.1 堆棧的定義和主要操作2.5.2 順序棧2.5.3 鏈?zhǔn)綏?.5.4 順序棧與鏈?zhǔn)綏５谋容^2.5.5 堆棧的應(yīng)用堆棧的應(yīng)用括號(hào)匹配 高級(jí)語言程序設(shè)計(jì)中的各種括號(hào)應(yīng)該匹配，例如：“(” 與 “)”匹配、“”與 “” 匹配、“”與 “” 匹配等。字符串a(chǎn)=(b*c+free( ) 中的括號(hào)就沒有匹配上，因?yàn)榇械谝粋€(gè)關(guān)括號(hào) “” 和最近的未匹配開括號(hào) “(” 不匹配。第二章 線性表、堆棧和隊(duì)列 2.1 線性表的定義和基本操作2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)2.3 線性表的鏈接存儲(chǔ)結(jié)構(gòu)2.4 復(fù)雜性分析2.5 堆棧2.6 隊(duì)列2.6 隊(duì)列2.6

12、.1 隊(duì)列的定義和主要操作2.6.2 順序隊(duì)列2.6.3 鏈?zhǔn)疥?duì)列1、隊(duì)列的定義隊(duì)列的定義：隊(duì)列是插入在一端進(jìn)行而刪除在其另一端進(jìn)行的線性表。按先進(jìn)先出的原則進(jìn)行操作。能進(jìn)行刪除的一端稱為隊(duì)首（front）；能進(jìn)行插入的一端稱為隊(duì)尾（rear）；沒有元素的隊(duì)列稱為空隊(duì)列。a1a2a3a4a5隊(duì)尾隊(duì)首入隊(duì)出隊(duì)隊(duì)列的先進(jìn)先出性：可以對(duì)輸入序列起緩沖作用；凡符合先進(jìn)先出性，都可應(yīng)用隊(duì)列，如操作系統(tǒng)中作業(yè)調(diào)度、圖的廣度優(yōu)先搜索等問題。隊(duì)列的封閉性：和棧類似，隊(duì)列的封閉性也非常好，使用起來非常安全。2、隊(duì)列的基本操作： (1）隊(duì)列初始化（2）入隊(duì) (插入）（3）出隊(duì)（刪除）（4）讀取隊(duì)首元素（5）判斷隊(duì)

13、列是否空 （6）確定隊(duì)列中元素個(gè)數(shù) （7）置空隊(duì)列 2.6 隊(duì)列2.6.1 隊(duì)列的定義和主要操作2.6.2 順序隊(duì)列2.6.3 鏈?zhǔn)疥?duì)列隊(duì)列的順序存儲(chǔ) 存放隊(duì)列元素的數(shù)組： T qlistMaxQSize front 隊(duì)首元素的數(shù)組下標(biāo) rear (要入隊(duì)元素的下標(biāo)) 隊(duì)尾元素的下標(biāo)加1 a1a2a3frontrear 例 等待處理某作業(yè)進(jìn)隊(duì)、出隊(duì)情況。 front=0rear=1a0012Maxsize-1a0進(jìn)隊(duì)012Maxsize-1front=0rear=0初始狀態(tài) 插入： rear=rear+1 front=0a0a1a2012Maxsize-1a1 a2進(jìn)隊(duì)rear=3front=

14、1a1a2012Maxsize-1a0出隊(duì)rear=3 刪除隊(duì)首元素的方法1：令front=front+1 front=3012Maxsize-1a1 a2出隊(duì)rear=3 012Maxsize-1rear=nfront=n-3an-3an-2 無法利用的空間x 刪除隊(duì)首元素方法2 :元素向前移動(dòng)，front總等于0 插入: rear=rear+1a2012Maxsize-1a0出隊(duì)front=0 rear=2a1front=0an-3an-2012Maxsize-1rear=3x front= n-3an-3an-2012Maxsize-1rear=n-1 循環(huán)隊(duì)列:很好的解決了存在的問題。

15、n-3rear= n-1an-3an-20.1.front=n-3n-2 插入元素 x：front=n-3an-3an-2012Maxsize-1rear=0 xn-3an-3rear=0an-20.1n-1.front=n-3n-2xrear順時(shí)針移動(dòng)一位rear = (rear+1) MOD MaxQSize刪除隊(duì)首元素： front順時(shí)針移動(dòng)一位front = (front+1) MOD MaxQSize;rear0front=9.1.CD刪除Crearfront=00.1.D 采用環(huán)狀模型來實(shí)現(xiàn)隊(duì)列,各數(shù)據(jù)成員的意義如下： front指定隊(duì)首位置，刪除一個(gè)元素就將front順 時(shí)針移動(dòng)

16、一位；rear指向元素要插入的位置，插入一個(gè)元素就將rear順時(shí)針移動(dòng)一位；count存放隊(duì)列中元素的個(gè)數(shù)，當(dāng)count等于MaxQSize時(shí)，不可再向隊(duì)列中插入元素。 隊(duì)空：count=0 隊(duì)滿：count=MaxQSize順序隊(duì)列類AQueue的類聲明template class AQueueprivate: int front ;/ 隊(duì)首所在數(shù)組元素下標(biāo) int rear ; / 新元素要插入的位置（下標(biāo)） int count ; / 隊(duì)列中元素個(gè)數(shù) T *QArray ; / 存放隊(duì)列元素的數(shù)組 int Size ;/ 存放隊(duì)列的數(shù)組規(guī)模public: AQueue ( int Max

17、QueueSize = 10 ) / 構(gòu)造函數(shù) AQueue ( void ) delete QArray ; / 析構(gòu)函數(shù)bool QInsert ( const T& item )/ 向隊(duì)尾插入元素itembool QDelete ( T & item ) ;/ 刪除隊(duì)首元素并將該元素值保存至itemvoid QClear ( void ) front = rear = count = 0 ; / 清空隊(duì)列T QFront ( void ) const ; / 存取隊(duì)首元素值bool isEmpty ( void ) const return count = = 0 ; / 檢測(cè)隊(duì)列是否為

18、空bool isFull ( void ) const return count = = Size ; / 檢測(cè)隊(duì)列是否為滿 ;算法QInsert (A, item) / 在隊(duì)列A中將元素item插入隊(duì)尾QI1. 隊(duì)列滿？IF countsize THEN (PRINT“隊(duì)列已滿無法插入”. RETURN. )QI2. 插入 Arear item. / 將新元素插入隊(duì)尾QI3. 更新 rearMOD(rear1, size). / 更新隊(duì)尾下標(biāo) countcount1. / 更新隊(duì)列長(zhǎng)度 算法QDelete (A. item) / 刪除隊(duì)列A的隊(duì)首元素，并將其元素值賦給變量itemQD1. 隊(duì)

19、列空？ IF count0 THEN (PRINT “隊(duì)列空無法刪除”. RETURN. )QD2. 出隊(duì) item Afront. / 將隊(duì)首元素保存至itemQD3. 更新 frontMOD(front1, size). / 更新隊(duì)首元素下標(biāo) countcount-1. / 更新隊(duì)列長(zhǎng)度 算法QFront (A, item) / 讀取隊(duì)列A的隊(duì)首元素值，并將其賦給變量itemQF1. 隊(duì)列空？ IF count0 THEN (PRINT “隊(duì)列空無法讀取”. RETURN. )QF2. 存取 item Afront. / 將隊(duì)首元素保存至item FR0123456aFR0123456(a

20、) 創(chuàng)建一個(gè)隊(duì)列(b) 插入元素 a隊(duì)列運(yùn)行示意圖47abcFR0123456FR0123456(c) 插入元素b、c(d) 取出元素 a、b、c48hidefgRF0123456hijdefgFR0123456(e) 插入元素d、e、f、g、h、i(f) 插入元素 j49FR0123456(g) 刪除所有元素502.6 隊(duì)列2.6.1 隊(duì)列的定義和主要操作2.6.2 順序隊(duì)列2.6.3 鏈?zhǔn)疥?duì)列隊(duì)列的鏈接存儲(chǔ)鏈?zhǔn)疥?duì)列的結(jié)構(gòu)：（a1, a2, , an) ana1a2frontrear鏈?zhǔn)疥?duì)列LQueue的類聲明template class LQueue private:SLNode * fr

21、ont, * rear ; / 指向隊(duì)首和隊(duì)尾的指針public:LQueue ( void ) front = rear = NULL; / 構(gòu)造函數(shù) LQueue ( void ) QClear ( ) ; / 析構(gòu)函數(shù) void QInsert ( const T& item ) ;/ 隊(duì)尾添加元素bool QDelete ( T& item ) ;/ 刪除隊(duì)首元素bool QFront ( T& item ) const ;/ 存取隊(duì)首元素值/ 檢測(cè)隊(duì)列狀態(tài)int IsEmpty ( void ) const return front = = NULL ; void QClear ( void ) ; / 清空隊(duì)列 ;算法QInsert (item) / 將元素item插入隊(duì)尾QI1. 創(chuàng)建新結(jié)點(diǎn) s AVAIL. data(s)item. next(s)NULL. / 為新結(jié)點(diǎn)申請(qǐng)空間，令其字段值為item，指針域?yàn)榭誕I2. 隊(duì)空？ IF frontNULL THEN fronts. /若隊(duì)列為空，令隊(duì)首指針指向s ELSE ne