數(shù)據(jù)結(jié)構(gòu) 第三章棧隊(duì)列

1、第三章第三章 棧和隊(duì)列棧和隊(duì)列 本章介紹在程序設(shè)計(jì)中常用的兩種數(shù)據(jù)結(jié)構(gòu)本章介紹在程序設(shè)計(jì)中常用的兩種數(shù)據(jù)結(jié)構(gòu) 棧和隊(duì)列棧和隊(duì)列 第三章第三章 棧和隊(duì)列棧和隊(duì)列 3.1 3.1 棧棧 3.2 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例 3.3 3.3 棧與遞歸棧與遞歸 3.4 3.4 隊(duì)列隊(duì)列 3.1 3.1 棧棧3.13.1 .1 .1 棧的概念棧的概念3.13.1 .2 .2 棧的順序存儲(chǔ)和實(shí)現(xiàn)棧的順序存儲(chǔ)和實(shí)現(xiàn)3.13.1 .3 .3 棧的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)棧的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)3.1 棧棧棧是限定僅能在表尾一端進(jìn)行插入、刪除操作的線性表?xiàng)Ｊ窍薅▋H能在表尾一端進(jìn)行插入、刪除操作的線性表（a1, a2, .

2、, ai -1, ai , ai+1, , an ）插入插入刪除刪除3.1.1棧的定義和抽象數(shù)據(jù)類型棧的定義和抽象數(shù)據(jù)類型一一 什么是棧什么是棧說明：設(shè)（說明：設(shè)（a1, a2, a3, , an ） 是一個(gè)棧是一個(gè)棧 1）表尾稱為棧頂，表頭稱為棧底）表尾稱為棧頂，表頭稱為棧底 ，即，即a1為棧底元素，為棧底元素，an為為 棧頂元素；棧頂元素； 2）在表尾插入元素的）在表尾插入元素的 操作稱進(jìn)棧操作，在表尾刪除元素操作稱進(jìn)棧操作，在表尾刪除元素 的操作稱為出棧操作的操作稱為出棧操作; 3）元素按）元素按a1, a2, a3, , an 的次序進(jìn)棧的次序進(jìn)棧, 第一個(gè)進(jìn)棧的元素第一個(gè)進(jìn)棧的元素

3、一定在棧底，最后一個(gè)進(jìn)棧的元素一定在棧頂一定在棧底，最后一個(gè)進(jìn)棧的元素一定在棧頂, 第一個(gè)第一個(gè) 出棧的元素為棧頂元素；出棧的元素為棧頂元素； 4）棧的元素具有后進(jìn)先出的特點(diǎn)）棧的元素具有后進(jìn)先出的特點(diǎn),所以棧又稱為后進(jìn)先出所以棧又稱為后進(jìn)先出 表（表（LIFO表）；表）； 5）由于進(jìn)棧、出棧操作總是在棧頂一端進(jìn)行，通常設(shè)置稱）由于進(jìn)棧、出棧操作總是在棧頂一端進(jìn)行，通常設(shè)置稱 為棧頂指針的變量為棧頂指針的變量(Top)指示棧頂?shù)奈恢?。指示棧頂?shù)奈恢谩５椎讞ｍ旐敚╝1, a2, . , ai -1, ai , ai+1, , an ）進(jìn)棧進(jìn)棧出棧出棧棧的示意圖棧的示意圖出棧出棧進(jìn)棧進(jìn)棧棧的

4、特點(diǎn)棧的特點(diǎn)后進(jìn)先出后進(jìn)先出第一個(gè)進(jìn)棧的元素在棧底，第一個(gè)進(jìn)棧的元素在棧底，最后一個(gè)進(jìn)棧的元素在棧頂，最后一個(gè)進(jìn)棧的元素在棧頂，第一個(gè)出棧的元素為棧頂元素，第一個(gè)出棧的元素為棧頂元素，最后一個(gè)出棧的元素為棧底元素最后一個(gè)出棧的元素為棧底元素棧頂棧頂棧底棧底a an na a2 2a a1 1二二 棧的基本操作棧的基本操作 1） 初始化操作初始化操作InitStack(&S) 功能：構(gòu)造一個(gè)空棧功能：構(gòu)造一個(gè)空棧S； 2） 銷毀棧操作銷毀棧操作DestroyStack(&S) 功能：銷毀一個(gè)已存在的棧功能：銷毀一個(gè)已存在的棧; 3） 置空棧操作置空棧操作ClearStack(&a

5、mp;S) 功能：將棧功能：將棧S置為空棧置為空棧; 4） 取棧頂元素操作取棧頂元素操作GetTop(S, &e) 功能：取棧頂元素，并用功能：取棧頂元素，并用e 返回返回; 5）進(jìn)棧操作）進(jìn)棧操作Push(&S, e) 功能：元素功能：元素e進(jìn)棧進(jìn)棧; 6）退棧操作）退棧操作Pop(&S, &e) 功能：棧頂元素退棧，并用功能：棧頂元素退棧，并用e返回返回; 7）判空操作）判空操作StackEmpty(S) 功能：若棧功能：若棧S為空，則返回為空，則返回True，否則返回否則返回False;toptopbasebasebasebasetoptopbasebas

6、etoptopbasebasetoptopA AA AB BC CD DE EA AB B 棧操作圖示棧操作圖示空棧空棧 A A進(jìn)棧進(jìn)棧 B C D E B C D E 進(jìn)棧進(jìn)棧E D C E D C 出棧出棧 棧的順序存儲(chǔ)結(jié)構(gòu)也是利用一組連續(xù)的內(nèi)存單元棧的順序存儲(chǔ)結(jié)構(gòu)也是利用一組連續(xù)的內(nèi)存單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，棧頂元素的位依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，棧頂元素的位置由一個(gè)稱為棧頂指針的變量指示置由一個(gè)稱為棧頂指針的變量指示 。 棧的順序存貯結(jié)構(gòu)也稱為順序棧。棧的順序存貯結(jié)構(gòu)也稱為順序棧。3.1.2 棧的順序存儲(chǔ)和實(shí)現(xiàn)棧的順序存儲(chǔ)和實(shí)現(xiàn) 與線性表類似，棧也可以用順序結(jié)構(gòu)或鏈?zhǔn)浇Y(jié)

7、構(gòu)存儲(chǔ)。與線性表類似，棧也可以用順序結(jié)構(gòu)或鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)。一、棧的順序存儲(chǔ)結(jié)構(gòu)一、棧的順序存儲(chǔ)結(jié)構(gòu) 1 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)SqStack：結(jié)構(gòu)類型名；結(jié)構(gòu)類型名；SqStack類型的變量是結(jié)構(gòu)變量，它的三個(gè)域類型的變量是結(jié)構(gòu)變量，它的三個(gè)域 分別是：分別是： base：稱為棧底指針，指向棧底位置；稱為棧底指針，指向棧底位置； top： 稱為棧頂指針，約定棧頂指針指向棧頂元素的下（后面）一稱為棧頂指針，約定棧頂指針指向棧頂元素的下（后面）一 個(gè)位置；個(gè)位置； Stacksize：用于存放當(dāng)前分配（存放用于存放當(dāng)前分配（存放棧棧元素）的存儲(chǔ)空間的大小；元素）的存儲(chǔ)空間的大小；# #define

8、 STACK_INIT_SIZE 100 / define STACK_INIT_SIZE 100 / 棧存儲(chǔ)空間的初始分配量棧存儲(chǔ)空間的初始分配量# #define STACKINCREMENT 10 / define STACKINCREMENT 10 / 棧存儲(chǔ)空間的分配增量棧存儲(chǔ)空間的分配增量typedeftypedef structstruct SElemTypeSElemType * *base; /base; /棧空間基址棧空間基址SElemTypeSElemType * *top /top /棧頂指針棧頂指針intint stacksizestacksize; /; /當(dāng)前分配

9、的?？臻g大小當(dāng)前分配的?？臻g大小 / /（以（以sizeof(SElemTypesizeof(SElemType) )為單位）為單位） SqStackSqStack; ;2 順序棧的類型定義順序棧的類型定義3 順序棧的圖示順序棧的圖示a an na ai ia ai-1i-1a a2 2a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE n nn-1n-1i-1i-1i-2i-2 1 1 0 0當(dāng)棧用順序結(jié)構(gòu)存儲(chǔ)時(shí)，當(dāng)棧用順序結(jié)構(gòu)存儲(chǔ)時(shí)，棧的基本操作如建空棧、棧的基本操作如建空棧、進(jìn)棧

10、、出棧等操作如何實(shí)現(xiàn)？進(jìn)棧、出棧等操作如何實(shí)現(xiàn)？二二 順序?；静僮鞯乃惴樞驐；静僮鞯乃惴?）初始化操作）初始化操作InitStack_Sq(SqStack &S) 參數(shù)：參數(shù)：S是存放棧的結(jié)構(gòu)變量；是存放棧的結(jié)構(gòu)變量； 功能：建一個(gè)空棧功能：建一個(gè)空棧S； 算法算法Status InitStack_Sq(SqStack &S) /構(gòu)造一個(gè)空棧構(gòu)造一個(gè)空棧S S.base=(SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType); /為順序棧動(dòng)態(tài)分配存儲(chǔ)空間為順序棧動(dòng)態(tài)分配存儲(chǔ)空間 if (! S. base) exi

11、t(OVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;/InitStack_Sq n nn-1n-1i-1i-1i-2i-2 1 1 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE初始化操作圖示初始化操作圖示 初始化操作圖示初始化操作圖示算法算法Status DetroyStack_Sq ( SqStack &S) If (!S.base) return ERROR; / 若

12、棧未建立（尚未分配棧空間）若棧未建立（尚未分配?？臻g） free (S.base); / 回收棧空間回收棧空間 S.base = S.top = null; S.stacksize = 0; return OK;/ DetroyStack_Sq2） 銷毀棧操作銷毀棧操作 DestroyStack_Sq(SqStackSqStack &S &S ) 功能：銷毀一個(gè)已存在的棧功能：銷毀一個(gè)已存在的棧;S.top =nullS.top =nullS.stacksizeS.stacksizeS.base =nullS.base =null 0 0 n nn-1n-1i-1i-1i-2i

13、-2 1 1 0 0a an na ai ia ai-1i-1a a2 2a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE 銷毀前 銷毀后銷毀棧操作圖示3）置空棧操作置空棧操作ClearStack_Sq(SqStack &S) 功能：將棧功能：將棧S置為空棧置為空棧 算法算法 Status ClearStack_Sq ( SqStack &S) If (!S.base) return ERROR; / 若棧未建立（尚未分配?？臻g）若棧未建立（尚未分配棧空間） S.to

14、p = S.base ; return OK; / ClearStack_Sq n nn-1n-1i-1i-1i-2i-2 1 1 0 0a an na ai ia ai-1i-1a a2 2a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE n nn-1n-1i-1i-1i-2i-2 1 1 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZEa an na ai ia ai-1i-

15、1a a2 2a a1 1置空棧操作圖示置空棧操作圖示S.base=S.topS.base=S.top表明棧為空表明棧為空置空前置空前置空后置空后 算法算法Status GetTop_Sq(SqStack S, SelemType &e) / 若棧不空，則用若棧不空，則用e返回返回S的棧頂元素，并返回的棧頂元素，并返回OK；否則返回否則返回ERROR if (S.top= =S.base) return ERROR; /若棧為空若棧為空 e = * (S.top-1); return OK;/GetTop_Sq4） 取棧頂元素操作取棧頂元素操作GetTop_Sq(SqStack S,

16、SElemType &e) 功能：取棧頂元素，并用功能：取棧頂元素，并用e返回返回; n nn-1n-1i-1i-1i-2i-2 1 1 0 0a an na ai ia ai-1i-1a a2 2a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZEe ea an n 取棧頂元素操作圖示取棧頂元素操作圖示n+1n+1n nn-1n-1i-1i-1i-2i-2 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZ

17、ESTACK_INIT_SIZEe ea an na ai ia ai-1i-1a a1 15）進(jìn)棧操作進(jìn)棧操作Push(SqStackSqStack &S, &S, SElemTypeSElemType e e) 功能：元素功能：元素e 進(jìn)棧進(jìn)棧; 進(jìn)棧操作主要步驟：進(jìn)棧操作主要步驟： 1）S是否已滿，是否已滿， 若若棧棧滿，重新分配存儲(chǔ)空間；滿，重新分配存儲(chǔ)空間； 2）將元素將元素e 寫入棧頂；寫入棧頂； 3）修改棧頂指針，使棧頂指針指向棧頂元素）修改棧頂指針，使棧頂指針指向棧頂元素 的下（后面）一個(gè)位置；的下（后面）一個(gè)位置； n nn-1n-1i-1i-1i-2i-2

18、0 0n+1n+1n nn-1n-1i-1i-1i-2i-2 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZEe ea an na ai ia ai-1i-1a a1 1a an na ai ia ai-1i-1a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE e 進(jìn)棧前進(jìn)棧前 e 進(jìn)棧后進(jìn)棧后 進(jìn)棧操作圖示進(jìn)棧操作圖示進(jìn)棧操作算法：進(jìn)棧操作算法：Status Push(SqSt

19、ack &S, SElemType e) /將元素將元素e插入棧成為新的棧頂元素插入棧成為新的棧頂元素 if (S.top-S.base=S.stacksize) /棧滿，追加存儲(chǔ)空間棧滿，追加存儲(chǔ)空間 S.base= (SElemType * )realloc(S.base, (S.stacksize +STACKINCREMENT) *sizeof(ElemType); if (! S. base) exit(OVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+

20、=e; /元素元素e 插入棧頂，修改棧頂指針插入棧頂，修改棧頂指針 return OK;/Push6）出）出棧操作棧操作Pop(SqStack &S, SElemType &e )功能：棧頂元素退棧，并用功能：棧頂元素退棧，并用e 返回返回;出棧操作基本步驟出棧操作基本步驟算法算法Status Pop(SqStack &S, SElemType &e) /若棧不空，則刪除若棧不空，則刪除S的棧頂元素，用的棧頂元素，用e 返回其值，并返回返回其值，并返回OK； /否則返回否則返回ERROR if (S.top= = S.base) return ERROR; /棧

21、空，返回棧空，返回ERROR e = * -S.top; /刪除棧頂元素，用刪除棧頂元素，用e 返回其值，并修改棧頂指針返回其值，并修改棧頂指針 return OK;/PopS.topS.topS.stacksizeS.stacksizeS.baseS.base n nn-1n-1i-1i-1i-2i-2 0 0a an na ai ia ai-1i-1a a1 1STACK_INIT_SIZESTACK_INIT_SIZE 出棧操作前出棧操作前出棧操作圖示出棧操作圖示 出棧操作后出棧操作后n nn-1n-1i-1i-1i-2i-2 0 0S.topS.topS.stacksizeS.stac

22、ksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZEa an-1n-1a ai ia ai-1i-1a a1 1e ea an n 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也稱鏈棧，棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也稱鏈棧，如圖所示：如圖所示：Data nextData nextS S棧頂棧頂棧底棧底a an-1n-1a a1 1a an n3.1.3 3.1.3 棧的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)棧的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)說明說明 1）鏈?zhǔn)綏？捎镁€性鏈表表示；）鏈?zhǔn)綏？捎镁€性鏈表表示； 2）鏈?zhǔn)綏５臈ｍ斨羔樉褪擎湵淼念^指針；）鏈?zhǔn)綏５臈ｍ斨羔樉褪擎湵淼念^指針； 3）進(jìn)棧操作就是在該線性鏈表第一個(gè)元素）進(jìn)棧操作

23、就是在該線性鏈表第一個(gè)元素 結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)，出棧操作就是結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)，出棧操作就是 刪除鏈表的第一個(gè)元素結(jié)點(diǎn)。刪除鏈表的第一個(gè)元素結(jié)點(diǎn)。 在前面學(xué)習(xí)了線性鏈表的插入刪除操作在前面學(xué)習(xí)了線性鏈表的插入刪除操作算法，不難寫出鏈?zhǔn)綏３跏蓟⑦M(jìn)棧、出棧算法，不難寫出鏈?zhǔn)綏３跏蓟?、進(jìn)棧、出棧等操作的算法。大家不妨試一試。等操作的算法。大家不妨試一試。鏈?zhǔn)綏D示鏈?zhǔn)綏D示Data nextData nextS S棧頂棧頂棧底棧底a an-1n-1a a1 1a an n 小小 結(jié)結(jié) 1 棧是限定僅能在表尾一端進(jìn)行插入、刪除棧是限定僅能在表尾一端進(jìn)行插入、刪除 操作的線性表；操作的線性表；

24、 2 棧的元素具有后進(jìn)先出的特點(diǎn)；棧的元素具有后進(jìn)先出的特點(diǎn)； 3 棧頂元素的位置由一個(gè)稱為棧頂指針的變棧頂元素的位置由一個(gè)稱為棧頂指針的變 指示，進(jìn)棧、出棧操作要修改棧頂指針；指示，進(jìn)棧、出棧操作要修改棧頂指針； 3.2 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例 棧結(jié)構(gòu)具有后進(jìn)先出的特征，使棧成為程序設(shè)計(jì)中的有棧結(jié)構(gòu)具有后進(jìn)先出的特征，使棧成為程序設(shè)計(jì)中的有用工具，本節(jié)介紹棧的幾個(gè)簡單應(yīng)用的實(shí)例。用工具，本節(jié)介紹棧的幾個(gè)簡單應(yīng)用的實(shí)例。例例1 1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 1 1）問題）問題 在計(jì)算機(jī)基礎(chǔ)課中，我們學(xué)習(xí)過各種數(shù)制的轉(zhuǎn)換問在計(jì)算機(jī)基礎(chǔ)課中，我們學(xué)習(xí)過各種數(shù)制的轉(zhuǎn)換問題。十題。十八進(jìn)制轉(zhuǎn)換、十八

25、進(jìn)制轉(zhuǎn)換、十二進(jìn)制轉(zhuǎn)換等。下面我們二進(jìn)制轉(zhuǎn)換等。下面我們設(shè)計(jì)一程序?qū)崿F(xiàn)十進(jìn)制數(shù)到八進(jìn)制數(shù)的自動(dòng)轉(zhuǎn)換。即該程設(shè)計(jì)一程序?qū)崿F(xiàn)十進(jìn)制數(shù)到八進(jìn)制數(shù)的自動(dòng)轉(zhuǎn)換。即該程序功能為：對于輸入的任意一個(gè)非負(fù)十進(jìn)制數(shù)，顯示輸出序功能為：對于輸入的任意一個(gè)非負(fù)十進(jìn)制數(shù)，顯示輸出與其等值的八進(jìn)制數(shù)。與其等值的八進(jìn)制數(shù)。 2 2） 求解方法求解方法 這個(gè)問題的求解方法有很多，我們這里介紹的方法基于這個(gè)問題的求解方法有很多，我們這里介紹的方法基于下列原理：下列原理： N = (Ndiv8)10 8+N mod 8 N：十進(jìn)制數(shù)，十進(jìn)制數(shù)，div：整除運(yùn)算，整除運(yùn)算，mod：求余運(yùn)算；求余運(yùn)算； (1348)10 = 2

26、83+5 82+0 8+4 = (2504)8 N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 由上述求解過程可以看出，在計(jì)算過程中是從低位到高位由上述求解過程可以看出，在計(jì)算過程中是從低位到高位順序產(chǎn)生八進(jìn)制數(shù)的各個(gè)數(shù)位，而顯示時(shí)按照我們的習(xí)慣是從順序產(chǎn)生八進(jìn)制數(shù)的各個(gè)數(shù)位，而顯示時(shí)按照我們的習(xí)慣是從高位在前，低位在后，即按從高位到低位的順序輸出高位在前，低位在后，即按從高位到低位的順序輸出, , 即后計(jì)即后計(jì)算出的（高）位數(shù)先輸出，具有后進(jìn)先出的特點(diǎn)，因此可將計(jì)算出的（高）位數(shù)先輸出，具有后進(jìn)先出的特點(diǎn)，因此可將計(jì)算過程中得到的八進(jìn)制數(shù)

27、順序進(jìn)棧，出棧序列打印輸出的就是算過程中得到的八進(jìn)制數(shù)順序進(jìn)棧，出棧序列打印輸出的就是對應(yīng)的八進(jìn)制數(shù)。對應(yīng)的八進(jìn)制數(shù)。3 3）算法算法void conversion( ) /對于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)對于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù) InitStack(S); /建空棧建空棧 scanf(“%d”, N); /輸入一個(gè)輸入一個(gè)非負(fù)十進(jìn)制整數(shù)非負(fù)十進(jìn)制整數(shù) while(N) / N不等于零不等于零循環(huán)循環(huán) Push(S, N % 8); / N/8第一個(gè)余數(shù)進(jìn)棧第一個(gè)余數(shù)進(jìn)棧 N=N/8; /整除運(yùn)算整除運(yùn)算 while(! Stac

28、kEmpty) /輸出存放在棧中的八制數(shù)位。輸出存放在棧中的八制數(shù)位。 Pop(S, e); Printf(“%d”, e); /conversion 算法算法3.1例例2 括號(hào)匹配的檢驗(yàn)括號(hào)匹配的檢驗(yàn)假設(shè)在表達(dá)式中假設(shè)在表達(dá)式中（）或（）或（ ）等為正確的格式，等為正確的格式，（ ）或（）或（ ）或）或 （）（）)均為不正確的格式。均為不正確的格式。算法的設(shè)計(jì)思想：算法的設(shè)計(jì)思想：1 1）凡出現(xiàn)左括弧，則進(jìn)棧；）凡出現(xiàn)左括弧，則進(jìn)棧；2 2）凡出現(xiàn)右括弧，首先檢查棧是否空）凡出現(xiàn)右括弧，首先檢查棧是否空 若?？眨瑒t表明該若?？眨瑒t表明該“右括弧右括弧”多余，多余， 否則和棧頂元素比較，否則和

29、棧頂元素比較， 若相匹配，則若相匹配，則“左括弧出棧左括弧出?！?” ， 否則表明不匹配。否則表明不匹配。3 3）表達(dá)式檢驗(yàn)結(jié)束時(shí)，）表達(dá)式檢驗(yàn)結(jié)束時(shí)， 若?？眨瑒t表明表達(dá)式中匹配正確，若?？?，則表明表達(dá)式中匹配正確， 否則表明否則表明“左括弧左括弧”有余。有余。出口例例3 3 迷宮求解迷宮求解入口入口求迷宮路徑算法的基本思想是：求迷宮路徑算法的基本思想是：若當(dāng)前位置若當(dāng)前位置“可通可通”，則納入路徑，繼續(xù)前進(jìn)，則納入路徑，繼續(xù)前進(jìn); ;若當(dāng)前位置若當(dāng)前位置“不可通不可通”，則后退，換方向繼續(xù)探索，則后退，換方向繼續(xù)探索;若四周若四周“均無通路均無通路”，則將當(dāng)前位置從路徑中刪除出，則將當(dāng)前位

30、置從路徑中刪除出去。去。設(shè)定初值為入口位置設(shè)定初值為入口位置, ,以正東為起始方向以正東為起始方向； dodo if( if(當(dāng)前位置可通當(dāng)前位置可通) ) 則將當(dāng)前位置插入棧頂；則將當(dāng)前位置插入棧頂； if(if(該位置是出口位置該位置是出口位置) ) exit(0)exit(0)； else else 按順時(shí)針下一方向?yàn)樾碌漠?dāng)前位置；按順時(shí)針下一方向?yàn)樾碌漠?dāng)前位置； elseelse* * while(while(棧不空）；棧不空）；求迷宮中一條從入口到出口的路徑的算法：求迷宮中一條從入口到出口的路徑的算法：若?？?，則表明迷宮沒有通路。若?？?，則表明迷宮沒有通路。else * if if(

31、 (棧不空棧不空&棧頂位置尚有其他方向未被探索棧頂位置尚有其他方向未被探索) ) 新的當(dāng)前位置為新的當(dāng)前位置為: : 沿順時(shí)針方向旋轉(zhuǎn)沿順時(shí)針方向旋轉(zhuǎn) 找到的棧頂位置的下一相鄰塊；找到的棧頂位置的下一相鄰塊； if if( (棧不空棧不空&棧頂位置的四周均不可通棧頂位置的四周均不可通) ) 刪去棧頂位置；刪去棧頂位置；/ / 從路徑中刪去該通道塊從路徑中刪去該通道塊 若棧不空，則重新測試新的棧頂位置，若棧不空，則重新測試新的棧頂位置， 直至找到一個(gè)可通的相鄰塊或出棧至?？?；直至找到一個(gè)可通的相鄰塊或出棧至?？?； /else例例4 表達(dá)式求值表達(dá)式求值1）問題的提出）問題的提出

32、假若我們想在計(jì)算機(jī)上設(shè)計(jì)一個(gè)小計(jì)算器（程序），其假若我們想在計(jì)算機(jī)上設(shè)計(jì)一個(gè)小計(jì)算器（程序），其功能為：從鍵盤上輸入一個(gè)算術(shù)表達(dá)式（由運(yùn)算符操作數(shù)構(gòu)成功能為：從鍵盤上輸入一個(gè)算術(shù)表達(dá)式（由運(yùn)算符操作數(shù)構(gòu)成的字符串）的字符串）,在屏幕上顯示輸出表達(dá)式的求值結(jié)果。在屏幕上顯示輸出表達(dá)式的求值結(jié)果。 顯然這個(gè)小計(jì)算器程序應(yīng)該對你鍵入的表達(dá)式進(jìn)行求值。顯然這個(gè)小計(jì)算器程序應(yīng)該對你鍵入的表達(dá)式進(jìn)行求值。在該程序中如何對鍵入的表達(dá)式求值呢？在該程序中如何對鍵入的表達(dá)式求值呢？ 又如，高級(jí)語言中都有表達(dá)式，例賦值語句：變量又如，高級(jí)語言中都有表達(dá)式，例賦值語句：變量=表達(dá)表達(dá)式；該語句的執(zhí)行過程為：先求出表

33、達(dá)式的值，式；該語句的執(zhí)行過程為：先求出表達(dá)式的值， 然后將其值然后將其值賦給賦值號(hào)左邊的變量。這個(gè)表達(dá)式的值是如何求出的？賦給賦值號(hào)左邊的變量。這個(gè)表達(dá)式的值是如何求出的？ 下面我們就來設(shè)計(jì)一個(gè)表達(dá)式求值算法。下面我們就來設(shè)計(jì)一個(gè)表達(dá)式求值算法。2 2）表達(dá)式的構(gòu)成）表達(dá)式的構(gòu)成 操作數(shù)操作數(shù)+ +運(yùn)算符運(yùn)算符+ +界限符（如括號(hào)）界限符（如括號(hào)）3 3）表達(dá)式的求值：）表達(dá)式的求值： 例例 5+6 5+6 (1+2)- 4(1+2)- 4 按照四則運(yùn)算法則，上述表達(dá)式的計(jì)算過程為：按照四則運(yùn)算法則，上述表達(dá)式的計(jì)算過程為： 5+ 6 5+ 6 (1+2)- 4=5+6 (1+2)- 4=5

34、+6 3-4 = 5+18-4= 23-4=193-4 = 5+18-4= 23-4=19 表達(dá)式中運(yùn)算符的運(yùn)算順序?yàn)椋罕磉_(dá)式中運(yùn)算符的運(yùn)算順序?yàn)椋?+ + ， ， + +， - - ， 如何確定運(yùn)算符的運(yùn)算順序？如何確定運(yùn)算符的運(yùn)算順序？1 12 23 34 41 12 23 34 44） 算符優(yōu)先關(guān)系表算符優(yōu)先關(guān)系表 表達(dá)式中任何相鄰運(yùn)算符表達(dá)式中任何相鄰運(yùn)算符 1、 2的優(yōu)先關(guān)系有：的優(yōu)先關(guān)系有： 1 2： 1的優(yōu)先級(jí)高于的優(yōu)先級(jí)高于 2 由四則運(yùn)算法則，可得到如下的算符優(yōu)先關(guān)系表：由四則運(yùn)算法則，可得到如下的算符優(yōu)先關(guān)系表：+ 21 - -* */ /( () )# #+ - + -

35、* * / ( ) # / ( ) # = = = 算符間的優(yōu)先關(guān)系表算符間的優(yōu)先關(guān)系表注：注： 1 2是相鄰算符，是相鄰算符， 1在左，在左， 2在右在右5 5 ) ) 算符優(yōu)先算法算符優(yōu)先算法 我們再來分析一下表達(dá)式我們再來分析一下表達(dá)式5+45+4 (1+2)-6 (1+2)-6 計(jì)算過程：計(jì)算過程： 從左向右掃描表達(dá)式：從左向右掃描表達(dá)式： 遇操作數(shù)遇操作數(shù)保存；保存； 遇運(yùn)算符號(hào)遇運(yùn)算符號(hào) j與前面的剛掃描過的運(yùn)算符與前面的剛掃描過的運(yùn)算符 i比較比較 若若 i j 則保存則保存 j，（，（ 因此已保存的運(yùn)算符的優(yōu)先關(guān)系為因此已保存的運(yùn)算符的優(yōu)先關(guān)系為 1 2 3 j 則說明則說明

36、i是已掃描的運(yùn)算符中優(yōu)先級(jí)最高者，可進(jìn)行運(yùn)算；是已掃描的運(yùn)算符中優(yōu)先級(jí)最高者，可進(jìn)行運(yùn)算； 若若 i = j 則則 i為（，為（， j 為為 ），說明括號(hào)內(nèi)的式子已計(jì)算完，需要消去括號(hào)；），說明括號(hào)內(nèi)的式子已計(jì)算完，需要消去括號(hào)； 5+4 (1+2)- 6我們可以利用兩個(gè)棧分別保存掃描過程中遇到的操作數(shù)和運(yùn)算符。我們可以利用兩個(gè)棧分別保存掃描過程中遇到的操作數(shù)和運(yùn)算符。后面也許有優(yōu)先級(jí)后面也許有優(yōu)先級(jí)更大的算符更大的算符表達(dá)式求值示意圖：表達(dá)式求值示意圖：5+65+6 (1+2)-4 (1+2)-4 toptopbasebaseOPTROPTR棧棧# #OPNDOPND棧棧toptopbase

37、base5 5toptoptoptop+ +toptop6 6toptoptoptop( (toptop1 1toptop+ +toptop2 2toptoptoptoptoptoptoptop3 3toptoptoptoptoptoptoptoptoptop1818toptoptoptoptoptoptoptop2323toptop- -toptop4 4toptoptoptoptoptoptoptop1919toptoptoptoptoptop5 5讀入表達(dá)式過程：讀入表達(dá)式過程：+ +6 6( (1 1+ +2 2) )- -4 4# #=19=191+2=36 63=183=185+1

38、8=235+18=2323-4=1923-4=19 在算符優(yōu)先算法中，建立了兩個(gè)工作棧。一個(gè)是在算符優(yōu)先算法中，建立了兩個(gè)工作棧。一個(gè)是OPTR棧，用以保存運(yùn)算符棧，用以保存運(yùn)算符一個(gè)是一個(gè)是OPND棧，用以保存操作數(shù)或運(yùn)算結(jié)果。棧，用以保存操作數(shù)或運(yùn)算結(jié)果。 operandType EvaluateExpression( ) /算術(shù)表達(dá)式求值的算符優(yōu)先算法。設(shè)算術(shù)表達(dá)式求值的算符優(yōu)先算法。設(shè)OPTR和和OPND分別為運(yùn)算符棧和分別為運(yùn)算符棧和 /運(yùn)算數(shù)棧，運(yùn)算數(shù)棧，OP為運(yùn)算符集合。為運(yùn)算符集合。 InitStack(OPTR); Push (OPTR, #); InitStack(OPND

39、); c=qetchar( ); While(c!= # | GetTop(OPTR)!=#) if (! In (c, OP) Push(OPND, c); c=getchar( ) /不是運(yùn)算符則進(jìn)棧不是運(yùn)算符則進(jìn)棧 else / In(c, OP)判斷判斷c是否是否 /是運(yùn)算符的函數(shù)是運(yùn)算符的函數(shù) 續(xù)續(xù) switch (Precede(GetTop(OPTR), c) case : /新輸入的算符新輸入的算符c優(yōu)先級(jí)低，即棧頂算符優(yōu)先權(quán)高，優(yōu)先級(jí)低，即棧頂算符優(yōu)先權(quán)高， /出棧并將運(yùn)算結(jié)果入棧出棧并將運(yùn)算結(jié)果入棧OPND Pop(OPTR, theta); Pop(OPND, b); P

40、op(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch /while return GetTop(OPND);/EvaluateExpression第三章第三章 習(xí)題一習(xí)題一習(xí)題五習(xí)題五1 P21-23 1 P21-23 3.1, 3.2, 3.7 3.1, 3.2, 3.72 2 編編寫鏈?zhǔn)綏＿M(jìn)棧、出棧操作的算法，并畫出鏈?zhǔn)綏＿M(jìn)棧操作寫鏈?zhǔn)綏＿M(jìn)棧、出棧操作的算法，并畫出鏈?zhǔn)綏＿M(jìn)棧操作前、進(jìn)棧操作后的圖示前、進(jìn)棧操作后的圖示 習(xí)題取自習(xí)題取自數(shù)據(jù)結(jié)構(gòu)題集數(shù)據(jù)結(jié)構(gòu)題集 C C語言版語言版 嚴(yán)尉敏等編嚴(yán)尉敏等編 清華大學(xué)出版社清華

41、大學(xué)出版社3.3 棧與遞歸棧與遞歸 由上看到：應(yīng)用中如果處理數(shù)據(jù)處理過程具有后進(jìn)先出的特性，可由上看到：應(yīng)用中如果處理數(shù)據(jù)處理過程具有后進(jìn)先出的特性，可利用棧來實(shí)現(xiàn)數(shù)據(jù)處理過程。下面我們將看到可以用棧來實(shí)現(xiàn)遞歸。利用棧來實(shí)現(xiàn)數(shù)據(jù)處理過程。下面我們將看到可以用棧來實(shí)現(xiàn)遞歸。1什么是遞歸什么是遞歸 遞歸是一個(gè)很有用的工具，在數(shù)學(xué)和程序設(shè)計(jì)等許多領(lǐng)域中都用到遞歸是一個(gè)很有用的工具，在數(shù)學(xué)和程序設(shè)計(jì)等許多領(lǐng)域中都用到了遞歸。了遞歸。遞歸定義：簡單地說，一個(gè)用自己定義自己的概念遞歸定義：簡單地說，一個(gè)用自己定義自己的概念,稱為遞歸定義。稱為遞歸定義。例例 n!= 1 2 3 4 (n-1) n n!遞歸

42、定義遞歸定義 n!= 1 當(dāng)當(dāng) n=1時(shí)時(shí) n!= n (n-1)! 當(dāng)當(dāng)n 1時(shí)時(shí)用用(n-1)!(n-1)!定義定義n!n!2 遞歸函數(shù)：一個(gè)直接調(diào)用自己或通過一系列調(diào)用間接調(diào)用自己的函數(shù)稱遞歸函數(shù)：一個(gè)直接調(diào)用自己或通過一系列調(diào)用間接調(diào)用自己的函數(shù)稱 為遞歸函數(shù)。為遞歸函數(shù)。 A（ ） A( ) ; B( ) C( ) C( ); B( ); A 直接調(diào)用自己直接調(diào)用自己B間接調(diào)用自己間接調(diào)用自己遞歸是程序設(shè)計(jì)中的有用工具，下面舉例說明遞歸算法的編寫和執(zhí)行過程。遞歸是程序設(shè)計(jì)中的有用工具，下面舉例說明遞歸算法的編寫和執(zhí)行過程。2遞歸算法的編寫遞歸算法的編寫1）將問題用遞歸的方式描述（定義

43、）將問題用遞歸的方式描述（定義）2）根據(jù)問題的遞歸描述（定義）編寫遞歸算法）根據(jù)問題的遞歸描述（定義）編寫遞歸算法 問題的遞歸描述（定義）問題的遞歸描述（定義） 遞歸定義包括兩項(xiàng)遞歸定義包括兩項(xiàng) 基本項(xiàng)（終止項(xiàng)）：描述遞歸終止時(shí)問題的求解；基本項(xiàng)（終止項(xiàng)）：描述遞歸終止時(shí)問題的求解； 遞歸項(xiàng)：將問題分解為與原問題性質(zhì)相同，但規(guī)模較小的問題；遞歸項(xiàng)：將問題分解為與原問題性質(zhì)相同，但規(guī)模較小的問題； 例例 n!的遞歸定義的遞歸定義 基本項(xiàng)：基本項(xiàng)： n!=1 當(dāng)當(dāng) n=1 遞歸項(xiàng)：遞歸項(xiàng)： n!=n (n-1)! 當(dāng)當(dāng) n 1用用(n-1)!(n-1)!定義定義n!n!例例1 編寫求解編寫求解 階

44、乘階乘n! 的遞歸算法的遞歸算法首先給出階乘首先給出階乘n! 的遞歸定義的遞歸定義 n!的遞歸定義的遞歸定義 基本項(xiàng)：基本項(xiàng)： n!=1 當(dāng)當(dāng) n=1 遞歸項(xiàng)：遞歸項(xiàng)： n!=n (n-1)! 當(dāng)當(dāng) n 1 有了問題的遞歸定義，很容易寫出對應(yīng)的遞歸算法：有了問題的遞歸定義，很容易寫出對應(yīng)的遞歸算法：int fact (int n) /算法功能是求解并返回算法功能是求解并返回n的階乘的階乘 if（n=1） return（1）；）； else return（n*fact (n-1)）；）；/fact 例例2. 編寫求解編寫求解Hanci塔問題的遞歸算法塔問題的遞歸算法 有三個(gè)各為有三個(gè)各為X，Y，

45、Z的塔座，在的塔座，在X項(xiàng)有項(xiàng)有n個(gè)大小不同，依個(gè)大小不同，依小到大編號(hào)為小到大編號(hào)為1，2n的圓盤。的圓盤。 現(xiàn)要求將現(xiàn)要求將X上的上的n個(gè)圓盤移個(gè)圓盤移至至Z上，并仍以同樣順序疊放，上，并仍以同樣順序疊放， 圓盤移動(dòng)時(shí)必須遵守下列原圓盤移動(dòng)時(shí)必須遵守下列原則：則：1）每次移動(dòng)一個(gè)盤子；）每次移動(dòng)一個(gè)盤子；2）圓盤可以放在）圓盤可以放在X，Y，Z中的中的任一塔座上；任一塔座上；3）任何時(shí)刻都不能將較大的圓盤壓放在較小圓盤之上；）任何時(shí)刻都不能將較大的圓盤壓放在較小圓盤之上；例例 n=3時(shí)時(shí)圓盤移動(dòng)的過程如下圖所示圓盤移動(dòng)的過程如下圖所示：a ab bc c3 32 21 1 1 11 12

46、21 13 31 12 21 1Y YX XZ Z首先給出首先給出求解求解Hanci塔問題塔問題 的遞歸描述（定義）的遞歸描述（定義） 基本項(xiàng)：基本項(xiàng)： n=1時(shí)，將時(shí)，將n號(hào)圓盤從號(hào)圓盤從X移至移至Z； 遞歸項(xiàng)：遞歸項(xiàng)： n1時(shí)，時(shí)， 將將X上上1n-1號(hào)圓盤移至號(hào)圓盤移至Y； 將將X上的上的n號(hào)圓盤從號(hào)圓盤從X移至移至Z; 將將Y上上1n-1號(hào)圓盤從號(hào)圓盤從Y移至移至Z; 將規(guī)模為將規(guī)模為n n的問題的問題的求解歸結(jié)為規(guī)模的求解歸結(jié)為規(guī)模為為n-1n-1的問題的求的問題的求解解有了問題的遞歸定義，很容易寫出對應(yīng)的遞歸算法：有了問題的遞歸定義，很容易寫出對應(yīng)的遞歸算法：void hanoi

47、(int n, char x, char y, char z) /將塔座將塔座x上按直徑由小到大且自上而下編號(hào)為上按直徑由小到大且自上而下編號(hào)為1至至n的的n個(gè)圓盤按規(guī)則搬到個(gè)圓盤按規(guī)則搬到 /塔座塔座z上，上，y可用作輔助塔座。可用作輔助塔座。 /搬動(dòng)操作搬動(dòng)操作move(x, n, z),將編號(hào)為將編號(hào)為 n的圓盤從的圓盤從x移到移到z /printf(“%d Move disk %di from %c to %cn”, +c, n, x, z); if (n= =1) move(x,1,z); /將編號(hào)為將編號(hào)為1的圓盤從的圓盤從x移動(dòng)移動(dòng)z else hanoi(n-1, x, z,

48、y); /將將x上編號(hào)為上編號(hào)為1至至n-1的圓盤移到的圓盤移到y(tǒng), z作輔助塔作輔助塔 move(x, n, z); /將編號(hào)為將編號(hào)為 n的圓盤從的圓盤從x移到移到z hanoi(n-1, y, x, z)； /將將y上編號(hào)為上編號(hào)為1至至n-1的圓盤移到的圓盤移到z，x作輔助塔作輔助塔 算法算法3.5 Hanci塔問題塔問題 3 遞歸函數(shù)的實(shí)現(xiàn)遞歸函數(shù)的實(shí)現(xiàn) 在遞歸函數(shù)的執(zhí)行中，在遞歸函數(shù)的執(zhí)行中， 需多次自己調(diào)用自己，遞歸函數(shù)是如何執(zhí)行的？需多次自己調(diào)用自己，遞歸函數(shù)是如何執(zhí)行的？先看一般函數(shù)的調(diào)用機(jī)制如何實(shí)現(xiàn)的。先看一般函數(shù)的調(diào)用機(jī)制如何實(shí)現(xiàn)的。 A( )A( )B( );B( );

49、 C( )C( ) B( )B( )C( );C( ); 調(diào)用調(diào)用調(diào)用調(diào)用返回返回返回返回函數(shù)調(diào)用順序函數(shù)調(diào)用順序 A B CA B C函數(shù)返回順序函數(shù)返回順序 C B AC B A后調(diào)用的函數(shù)先返回后調(diào)用的函數(shù)先返回 函數(shù)調(diào)用機(jī)制可通過棧來實(shí)現(xiàn)函數(shù)調(diào)用機(jī)制可通過棧來實(shí)現(xiàn)我們看一下我們看一下n=3 n=3 階乘函數(shù)階乘函數(shù)fact(n)fact(n)的執(zhí)行過程的執(zhí)行過程Main( ) Main( ) intint n=3,y; n=3,y;L y= fact(n);L y= fact(n); 調(diào)調(diào)用用調(diào)用調(diào)用調(diào)調(diào)用用int fact (n) if（n=1） return（1）；）； else

50、L1 return（n*fact (n-1)）；）；/factn=3n=3int fact (int n) if（n=1） return（1）；）； else L1 return（n*fact (n-1)）；）；/factn=2n=2int fact (int n) if（n=1） return（1）；）； else L1 return（n*fact (n-1)）；）；/factn=1n=1L 3L 3L1 1L1 1L1 2L1 2返返回回1 1返回返回2 2返返回回6 6返回地址返回地址 實(shí)參實(shí)參 注意遞歸調(diào)用中注意遞歸調(diào)用中 棧的變化棧的變化 3.4 3.4 隊(duì)列隊(duì)列3.43.4 .1

51、.1 隊(duì)列隊(duì)列的概念的概念3.43.4 .2 .2 循環(huán)隊(duì)列循環(huán)隊(duì)列 隊(duì)列隊(duì)列的順序存儲(chǔ)和實(shí)現(xiàn)的順序存儲(chǔ)和實(shí)現(xiàn)3.43.4 .3 .3 隊(duì)列隊(duì)列的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn)1 1 理解掌握隊(duì)列的結(jié)構(gòu)特征和操作特點(diǎn)；理解掌握隊(duì)列的結(jié)構(gòu)特征和操作特點(diǎn)；2 2 掌握隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，及如何用掌握隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，及如何用C C語言描述語言描述 它們的類型定義；它們的類型定義；3 3 掌握在兩種存儲(chǔ)結(jié)構(gòu)下，隊(duì)列的基本操作的算法；重點(diǎn)掌握掌握在兩種存儲(chǔ)結(jié)構(gòu)下，隊(duì)列的基本操作的算法；重點(diǎn)掌握 循環(huán)隊(duì)列的入隊(duì)、出隊(duì)算法，循環(huán)隊(duì)列隊(duì)空、隊(duì)滿的判別條件；循環(huán)隊(duì)

52、列的入隊(duì)、出隊(duì)算法，循環(huán)隊(duì)列隊(duì)空、隊(duì)滿的判別條件；4 4 理解隊(duì)列先進(jìn)先出的特點(diǎn)及在程序設(shè)計(jì)中的應(yīng)用；理解隊(duì)列先進(jìn)先出的特點(diǎn)及在程序設(shè)計(jì)中的應(yīng)用；基本內(nèi)容基本內(nèi)容1 1 隊(duì)列的概念，隊(duì)列的基本操作；隊(duì)列的概念，隊(duì)列的基本操作；2 2 隊(duì)列的兩類存儲(chǔ)結(jié)構(gòu)和它們的類型定義；隊(duì)列的兩類存儲(chǔ)結(jié)構(gòu)和它們的類型定義；3 3 在隊(duì)列的存儲(chǔ)結(jié)構(gòu)下，隊(duì)列的基本操作的算法；在隊(duì)列的存儲(chǔ)結(jié)構(gòu)下，隊(duì)列的基本操作的算法；4 4 隊(duì)列在程序設(shè)計(jì)中的應(yīng)用。隊(duì)列在程序設(shè)計(jì)中的應(yīng)用。3 34 4 隊(duì)列隊(duì)列3.4.1隊(duì)列的定義和抽象數(shù)據(jù)類型隊(duì)列的定義和抽象數(shù)據(jù)類型一一 什么是隊(duì)列什么是隊(duì)列隊(duì)列是限定僅能在表頭進(jìn)行刪除，表尾進(jìn)行插

53、入的線隊(duì)列是限定僅能在表頭進(jìn)行刪除，表尾進(jìn)行插入的線性表性表（a1, a2, . , ai -1, ai , ai+1, , an ）插入插入刪除刪除說明：設(shè)（說明：設(shè)（a1,a2 , a3 , . , an ）為一隊(duì)列為一隊(duì)列 1）表尾稱作隊(duì)尾，表頭稱為隊(duì)頭；）表尾稱作隊(duì)尾，表頭稱為隊(duì)頭； 2）a1為隊(duì)頭元素，為隊(duì)頭元素，an為隊(duì)尾元素；為隊(duì)尾元素； 3）在表尾插入元素操作，稱為入隊(duì)操作；在表頭刪除元素）在表尾插入元素操作，稱為入隊(duì)操作；在表頭刪除元素 的操作，稱為出隊(duì)操作；的操作，稱為出隊(duì)操作； 4）元素按）元素按a1,a2, a3, . an 順序入隊(duì)，第一個(gè)入隊(duì)的元素為順序入隊(duì)，第一個(gè)

54、入隊(duì)的元素為a1 最后一個(gè)入隊(duì)的元素是最后一個(gè)入隊(duì)的元素是an 第一個(gè)出隊(duì)的元素為第一個(gè)出隊(duì)的元素為a1 ； 5）隊(duì)列具有先進(jìn)先出的特點(diǎn)，所以又稱為先進(jìn)先出表隊(duì)列具有先進(jìn)先出的特點(diǎn)，所以又稱為先進(jìn)先出表 （FIFO表）表） a a1 1 a a2 2 a a3 3 a an n入隊(duì)列入隊(duì)列隊(duì)隊(duì)頭頭隊(duì)隊(duì)尾尾出隊(duì)列出隊(duì)列隊(duì)列的示意圖隊(duì)列的示意圖隊(duì)列的特點(diǎn)隊(duì)列的特點(diǎn)先進(jìn)先出先進(jìn)先出第一個(gè)入隊(duì)的元素在隊(duì)頭，第一個(gè)入隊(duì)的元素在隊(duì)頭，最后一個(gè)入隊(duì)的元素在隊(duì)尾，最后一個(gè)入隊(duì)的元素在隊(duì)尾，第一個(gè)出隊(duì)的元素為隊(duì)頭元素，第一個(gè)出隊(duì)的元素為隊(duì)頭元素，最后一個(gè)出隊(duì)的元素為隊(duì)尾元素最后一個(gè)出隊(duì)的元素為隊(duì)尾元素 隊(duì)列類似

55、于日常的排隊(duì)，新來的人站在隊(duì)尾，隊(duì)頭的隊(duì)列類似于日常的排隊(duì)，新來的人站在隊(duì)尾，隊(duì)頭的人進(jìn)行事務(wù)處理后離隊(duì)。人進(jìn)行事務(wù)處理后離隊(duì)。 隊(duì)列通常設(shè)置兩個(gè)變量分別指示隊(duì)頭元素位置和隊(duì)尾隊(duì)列通常設(shè)置兩個(gè)變量分別指示隊(duì)頭元素位置和隊(duì)尾元素的位置，這兩個(gè)變量分別稱為隊(duì)頭指針、隊(duì)尾指針；元素的位置，這兩個(gè)變量分別稱為隊(duì)頭指針、隊(duì)尾指針；二二 隊(duì)列的基本操作隊(duì)列的基本操作1）初始化操作）初始化操作InitQueue( &Q) 功能：構(gòu)造一個(gè)空隊(duì)列功能：構(gòu)造一個(gè)空隊(duì)列Q；2）銷毀操作銷毀操作DestroyQueue( &Q) 功能：銷毀已存在隊(duì)列功能：銷毀已存在隊(duì)列Q；3）置空操作置空操作Clea

56、rQueue(&Q) 功能：功能： 將隊(duì)列將隊(duì)列Q置為空隊(duì)列置為空隊(duì)列 ；4）判空操作）判空操作QueueEmpty(Q) 功能：若隊(duì)列功能：若隊(duì)列Q為空，則返回為空，則返回True，否則返回否則返回False；5）取隊(duì)頭元素操作取隊(duì)頭元素操作GetHead(Q,&e) 功能：取隊(duì)頭元素，并用功能：取隊(duì)頭元素，并用e返回；返回；6）入隊(duì)操作入隊(duì)操作EnQueue( &Q, e ) 功能：將元素功能：將元素e插入插入Q的隊(duì)尾；的隊(duì)尾；7）出隊(duì)操作）出隊(duì)操作DeQueue( &Q, &e) 功能：若隊(duì)列不空，則刪除功能：若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用的隊(duì)

57、頭元素，用e返回其值，并返回返回其值，并返回OK，否則返回否則返回ERROR；3.4.2 循環(huán)隊(duì)列循環(huán)隊(duì)列隊(duì)列的順序存儲(chǔ)和實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)和實(shí)現(xiàn)一一 隊(duì)列的順序存貯結(jié)構(gòu)隊(duì)列的順序存貯結(jié)構(gòu) 1 隊(duì)列的順序存貯結(jié)構(gòu)隊(duì)列的順序存貯結(jié)構(gòu) 和順序棧類似，在隊(duì)列的順序存貯結(jié)構(gòu)中除了和順序棧類似，在隊(duì)列的順序存貯結(jié)構(gòu)中除了用一組連續(xù)存儲(chǔ)單元依次存儲(chǔ)從隊(duì)頭到隊(duì)尾的數(shù)據(jù)用一組連續(xù)存儲(chǔ)單元依次存儲(chǔ)從隊(duì)頭到隊(duì)尾的數(shù)據(jù)元素外，還需附加兩個(gè)變量，一個(gè)稱為隊(duì)頭指針，元素外，還需附加兩個(gè)變量，一個(gè)稱為隊(duì)頭指針，指示隊(duì)頭元素的位置；一個(gè)稱為隊(duì)尾指針，指示隊(duì)指示隊(duì)頭元素的位置；一個(gè)稱為隊(duì)尾指針，指示隊(duì)尾元素的位置。尾元素的位

58、置。Q.rearQ.rearQ.frontQ.frontJ1J1J2J2J3J3隊(duì)列的順序存貯結(jié)構(gòu)圖示隊(duì)列的順序存貯結(jié)構(gòu)圖示MAXSIZE：最大隊(duì)列空間，可根據(jù)實(shí)際應(yīng)用確定；最大隊(duì)列空間，可根據(jù)實(shí)際應(yīng)用確定； SqQueue：結(jié)構(gòu)類型名；結(jié)構(gòu)類型名； SqQueue 類型的變量是結(jié)構(gòu)變量。它的三個(gè)域分別是：類型的變量是結(jié)構(gòu)變量。它的三個(gè)域分別是： base：隊(duì)列存儲(chǔ)空間基址；隊(duì)列存儲(chǔ)空間基址； front：隊(duì)頭指針，若隊(duì)列不空，指向隊(duì)頭元素；隊(duì)頭指針，若隊(duì)列不空，指向隊(duì)頭元素； rear：隊(duì)尾指針，若隊(duì)列不空，指向隊(duì)尾元素的下一位置；隊(duì)尾指針，若隊(duì)列不空，指向隊(duì)尾元素的下一位置；# #defi

59、ne MAXSIZE 100 / define MAXSIZE 100 / 最大隊(duì)列長度最大隊(duì)列長度typedeftypedef structstruct QElemTypeQElemType * *base; /base; /初始化時(shí)動(dòng)態(tài)分配初始化時(shí)動(dòng)態(tài)分配存儲(chǔ)空間的基址存儲(chǔ)空間的基址 intint front; / front; /隊(duì)頭指針，指向隊(duì)頭元素隊(duì)頭指針，指向隊(duì)頭元素 intint rear; / rear; /隊(duì)尾指針，指向隊(duì)尾元素的下一個(gè)位置隊(duì)尾指針，指向隊(duì)尾元素的下一個(gè)位置 SqQueueSqQueue; ;2順序隊(duì)列的類型定義順序隊(duì)列的類型定義Q.rearQ.rearQ.f

60、rontQ.frontJ1J1J2J2J3J3Q.rearQ.rearQ.frontQ.frontJ3J3（a)a)空隊(duì)列空隊(duì)列(b)J1,J2(b)J1,J2和和J3J3相繼入隊(duì)列相繼入隊(duì)列(c)J1(c)J1和和J2J2相相繼出隊(duì)繼出隊(duì)( (d)J4,J5d)J4,J5和和J6J6相繼入相繼入隊(duì)之后隊(duì)之后, ,J3J3出隊(duì)出隊(duì)Q.rearQ.rearQ.frontQ.front0 01 12 23 34 45 5隊(duì)頭指針隊(duì)尾指針和隊(duì)列中元素之間的關(guān)系圖示隊(duì)頭指針隊(duì)尾指針和隊(duì)列中元素之間的關(guān)系圖示 設(shè)設(shè)Q為為SqQueue類型的變量，用于存儲(chǔ)隊(duì)列。設(shè)為隊(duì)列類型的變量，用于存儲(chǔ)隊(duì)列。設(shè)為隊(duì)列Q分配空間大小分配空間大小為為MAXSIZE=6，初始建隊(duì)時(shí)，令初始建隊(duì)時(shí)，令Q.front=Q.rear=0;Q.rearQ.rearQ.frontQ.frontJ6J6J5J5J4J43 . 循環(huán)隊(duì)列循環(huán)隊(duì)列 從圖從圖示示（d）中