1、 Data Structures: Chapter 3.1 Data Structures: Chapter 3.2 通常稱，棧和隊列是限定插入插入和刪除刪除只能在表的“端點端點”進(jìn)行的線性表。棧棧和和隊列隊列是兩種常用的是兩種常用的數(shù)據(jù)類型數(shù)據(jù)類型 Data Structures: Chapter 3.33.1 棧棧 棧棧是限定僅能在是限定僅能在表尾表尾一端進(jìn)行一端進(jìn)行插入插入、刪除刪除操作的操作的線性表線性表（a1, a2, . , ai -1, ai , ai+1, , an ）插入插入刪除刪除3.1.1 3.1.1 棧的棧的定義定義及基本及基本運算運算 一、什么是棧一、什么是棧 Dat

2、a Structures: Chapter 3.4棧的示意圖棧的示意圖出棧出棧進(jìn)棧進(jìn)棧棧的特點棧的特點后進(jìn)先出后進(jìn)先出(LIFO表表)第第1個進(jìn)棧的元素在個進(jìn)棧的元素在棧底棧底，最后一個進(jìn)棧的元素在最后一個進(jìn)棧的元素在棧頂棧頂，第第1個出棧的元素為個出棧的元素為棧頂元素棧頂元素，最后一個出棧的元素為最后一個出棧的元素為棧底元素棧底元素棧頂棧頂棧底棧底an na2 2a1 1二、棧的圖示二、棧的圖示 Data Structures: Chapter 3.5（1 1）初始化操作初始化操作 InitStack(InitStack(&S) S) 功能：功能：構(gòu)造一個空棧構(gòu)造一個空棧S S；（2

3、 2）銷毀棧操作銷毀棧操作 DestroyStack(DestroyStack(&S) S) 功能：功能：銷毀一個已存在的棧銷毀一個已存在的棧; ;（3 3）置空棧操作置空棧操作 ClearStack(ClearStack(&S) S) 功能功能：將棧：將棧S S置為空棧置為空棧; ;（4 4）取棧頂元素操作取棧頂元素操作 GetTop(S, GetTop(S, &e) e) 功能功能：取棧頂元素，并用：取棧頂元素，并用e e 返回返回; ;三、三、棧棧的基本操作（的基本操作（1） Data Structures: Chapter 3.6（5 5）進(jìn)棧操作進(jìn)棧操作 Pu

4、sh(Push(&S, e) S, e) 功能功能：元素：元素e e進(jìn)棧進(jìn)棧; ;（6 6）退棧操作退棧操作 Pop(Pop(&S, S, &e) e) 功能功能：棧頂元素退棧，并用：棧頂元素退棧，并用e e返回返回; ;（7 7）判空操作判空操作 StackEmpty(S) StackEmpty(S) 功能功能：若棧：若棧S S為空，返回為空，返回TrueTrue，否則返回，否則返回False; False; 三、三、棧棧的基本操作的基本操作（2） Data Structures: Chapter 3.7 棧的順序存儲結(jié)構(gòu)，也是利用一組連續(xù)的內(nèi)存單元依次存放自棧底到棧

5、頂?shù)臄?shù)據(jù)元素數(shù)據(jù)元素，棧頂元素棧頂元素的位置，的位置，由一個稱為棧頂指針棧頂指針的變量指示 。 棧的順序存貯結(jié)構(gòu)也稱為順序棧。順序棧。一、棧的順序存儲結(jié)構(gòu)一、棧的順序存儲結(jié)構(gòu)及及實現(xiàn)實現(xiàn) 3 3. .1 1.2 .2 棧的棧的順序順序表示與實現(xiàn)表示與實現(xiàn) 與線性表類似，棧也可以用順序結(jié)構(gòu)或鏈與線性表類似，棧也可以用順序結(jié)構(gòu)或鏈?zhǔn)浇Y(jié)構(gòu)存儲。式結(jié)構(gòu)存儲。 Data Structures: Chapter 3.8SqStack:結(jié)構(gòu)類型名；結(jié)構(gòu)類型名；SqStack類型的變量是結(jié)構(gòu)變量。類型的變量是結(jié)構(gòu)變量。base：稱為稱為棧底指針棧底指針，始終指向，始終指向棧底位置棧底位置；top：稱為稱為棧頂

6、指針棧頂指針，約定約定棧頂指針指向棧頂指針指向棧頂元素棧頂元素的的下一個位置下一個位置；Stacksize：用于存放當(dāng)前已分配的用于存放當(dāng)前已分配的棧棧的存儲空間的大?。坏拇鎯臻g的大?。?defineSTACK_INIT_SIZE100/棧存儲空間的初始分配量棧存儲空間的初始分配量#defineSTACKINCREMENT10/棧存儲空間的分配增量棧存儲空間的分配增量typedefstructSElemType *base;/?？臻g基址便于判斷棧是否為空棧空間基址便于判斷棧是否為空SElemType *top/棧頂指針棧頂指針intstacksize;/當(dāng)前分配的?？臻g大小當(dāng)前分配的?？臻g大

7、小/（以（以sizeof(SElemType)為單位）為單位）SqStack;順序棧的類型定義順序棧的類型定義 Data Structures: Chapter 3.9topbasebasetopbasetopbasetopAABCDEAB空?？諚?A進(jìn)棧進(jìn)棧 BCDE進(jìn)棧，進(jìn)棧，棧滿棧滿EDC出棧出棧順序棧的操作示例順序棧的操作示例P.58 Data Structures: Chapter 3.10順序棧的順序棧的圖示圖示anaiai-1a2a1 nn-1i-1i-210 100basetopstacksizeS Data Structures: Chapter 3.11 StatusIni

8、tStack(SqStack&S)/構(gòu)造一個空棧構(gòu)造一個空棧SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);/為順序棧動態(tài)分配存儲空間為順序棧動態(tài)分配存儲空間if(!S.base)exit(OVERFLOW);/存儲分配失敗存儲分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;/InitStack_Sq（1 1）初始化初始化操作操作順序棧的順序棧的基本操作的實現(xiàn)基本操作的實現(xiàn) Data Structures: Chapter 3.12StatusDetro

9、yStack(SqStack&S)/銷毀一個已存在的棧銷毀一個已存在的棧If(!S.base)returnERROR;/若棧未建立（尚未分配棧空間）若棧未建立（尚未分配?？臻g）free(S.base);/回收?？臻g回收?？臻gS.base=S.top=null;S.stacksize=0;returnOK;/DetroyStack_Sq（2 2） 銷毀銷毀棧操作棧操作 Data Structures: Chapter 3.13 StatusClearStack(SqStack&S)/將棧將棧S置為空棧置為空棧If(!S.base)returnERROR;/若棧未建立若棧未建立S.

10、top=S.base;returnOK;/ClearStack（3 3）置置空?？諚２僮鞑僮?Data Structures: Chapter 3.14StatusGetTop(SqStackS,SelemType&e)/若棧不空，則用若棧不空，則用e返回返回S的棧頂元素，并返回的棧頂元素，并返回OK；/否則返回否則返回ERRORif(S.top=S.base)returnERROR;/若棧為空若棧為空e=*(S.top-1);/取棧頂元素至取棧頂元素至ereturnOK;/GetTop_Sq（4 4） 取取棧頂棧頂元素操作元素操作 GetTop Data Structures: Ch

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

12、p+=e;/元素元素e插入棧頂，修改棧頂指針插入棧頂，修改棧頂指針returnOK;/Push（5 5） 進(jìn)棧操作進(jìn)棧操作 Push Data Structures: Chapter 3.16StatusPop(SqStack&S,SElemType&e)/若棧不空，則刪除若棧不空，則刪除S的棧頂元素，用的棧頂元素，用e返回其值，并返回返回其值，并返回OK；/否則返回否則返回ERRORif(S.top=S.base)returnERROR;/?？諚？誩=*-S.top;/刪除棧頂元素，并修改棧頂指針刪除棧頂元素，并修改棧頂指針returnOK;（6 6） 出棧操作出棧操作 Po

13、p Data Structures: Chapter 3.17棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)，棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)，也稱也稱鏈棧鏈棧，如右圖所示：如右圖所示：DatanextS棧頂棧頂棧底棧底an-1a1an3 3. .1 1. .3 3 棧棧的鏈?zhǔn)奖硎镜逆準(zhǔn)奖硎炯凹皩崿F(xiàn)實現(xiàn) Data Structures: Chapter 3.18鏈?zhǔn)綏D示鏈?zhǔn)綏D示說明：說明： 1. 1. 鏈棧鏈?？捎每捎镁€性鏈表線性鏈表表示；表示； 2 2. . 鏈棧的鏈棧的棧頂指針棧頂指針就是鏈表的就是鏈表的頭頭指針指針； 3 3. . 進(jìn)棧操作進(jìn)棧操作( (pushpush) )就是在該線性就是在該線性鏈表第一個元素結(jié)點之前插入一個

14、鏈表第一個元素結(jié)點之前插入一個新結(jié)點新結(jié)點. . 4. 4. 出棧操作出棧操作( (poppop) )就是刪除鏈表的就是刪除鏈表的第一個元素結(jié)點。第一個元素結(jié)點。DatanextS棧頂棧頂棧底棧底an-1a1an Data Structures: Chapter 3.193.2 3.2 棧棧的應(yīng)用舉例的應(yīng)用舉例例例1 1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 我們學(xué)習(xí)過各種數(shù)制的轉(zhuǎn)換問題。我們學(xué)習(xí)過各種數(shù)制的轉(zhuǎn)換問題。 十十-八進(jìn)制轉(zhuǎn)換八進(jìn)制轉(zhuǎn)換 十十-二進(jìn)制轉(zhuǎn)換等。二進(jìn)制轉(zhuǎn)換等。 下面我們設(shè)計一程序下面我們設(shè)計一程序, ,實現(xiàn)實現(xiàn)十十-八八進(jìn)制數(shù)的自動轉(zhuǎn)進(jìn)制數(shù)的自動轉(zhuǎn)換。該程序功能為：換。該程序功能為： 對于輸

15、入的任意一個對于輸入的任意一個非負(fù)非負(fù)十十進(jìn)制數(shù)，顯示輸出與其進(jìn)制數(shù)，顯示輸出與其等值的等值的八八進(jìn)制數(shù)。進(jìn)制數(shù)。 Data Structures: Chapter 3.20 我們這里介紹的方法基于下列原理：我們這里介紹的方法基于下列原理：N=(Ndiv8)10 8+Nmod8N：十進(jìn)制數(shù)十進(jìn)制數(shù)，div：整除運算整除運算，mod：求余運算求余運算；例：例：(1348)10=2 83+5 82+0 8+4=(2504)8NNdiv8Nmod8134816841682102125202 Data Structures: Chapter 3.21 由上述求解過程可以看出，在由上述求解過程可以看出，

16、在計算過程中計算過程中是是從低從低位到高位順序位到高位順序產(chǎn)生八進(jìn)制數(shù)的各個數(shù)位。產(chǎn)生八進(jìn)制數(shù)的各個數(shù)位。而而顯示時顯示時按照我們的習(xí)慣是從高位在前，低位在按照我們的習(xí)慣是從高位在前，低位在后，即按后，即按從高位到低位從高位到低位的順序輸出。的順序輸出。即后計算出的（高）位數(shù)先輸出，具有后進(jìn)先出即后計算出的（高）位數(shù)先輸出，具有后進(jìn)先出的特點。的特點。因此可將計算過程中得到的因此可將計算過程中得到的八進(jìn)制數(shù)八進(jìn)制數(shù)順序順序進(jìn)棧進(jìn)棧，按出棧序列按出棧序列打印輸出的數(shù)，就是對應(yīng)的八進(jìn)制數(shù)。打印輸出的數(shù)，就是對應(yīng)的八進(jìn)制數(shù)。 Data Structures: Chapter 3.22例如：例如：（1

17、348)10 = (2504)8 其運算過程如下： NNdiv8Nmod81348 168 4 168 21 0 21 2 5 2 0 2計算順序計算順序輸出順序輸出順序 Data Structures: Chapter 3.23voidconversion()/輸入任意一個非負(fù)輸入任意一個非負(fù)十十進(jìn)制整數(shù)，輸出與其等值的進(jìn)制整數(shù)，輸出與其等值的八八進(jìn)制數(shù)進(jìn)制數(shù)InitStack(S);/建空棧建空棧scanf(“%d”,&N);/輸入一個輸入一個非負(fù)十進(jìn)制整數(shù)非負(fù)十進(jìn)制整數(shù)while(N)/N不等于零不等于零循環(huán)循環(huán)Push(S,N%8);/余數(shù)余數(shù)N%8進(jìn)棧進(jìn)棧N=N/8;/輾轉(zhuǎn)相

18、除輾轉(zhuǎn)相除while(!StackEmpty(S)/輸出存放在棧中的八制數(shù)位輸出存放在棧中的八制數(shù)位。Pop(S,e);Printf(“%d”,e); Data Structures: Chapter 3.24例例2 括號匹配的檢驗括號匹配的檢驗假設(shè)在表達(dá)式中 （）或（ ）等為正確正確的格式， （ ）或（ ）或 ( )均為不正確不正確的格式。則 檢驗括號是否匹配是否匹配的方法可用 “期待的急迫程度”這個概念來描述。 Data Structures: Chapter 3.25分析可能出現(xiàn)的不匹配不匹配的情況:到來的右括弧非所“期待”的;例如：考慮下列括號序列： ( ) 1 2 3 4 5 6 7

19、 8到來的是“不速之客”;直到結(jié)束，也沒有到來所“期待”的括弧; Data Structures: Chapter 3.26算法的設(shè)計思想：算法的設(shè)計思想：（1）凡出現(xiàn)左括弧左括弧，則進(jìn)棧進(jìn)棧；（2）凡出現(xiàn)右括弧右括弧，首先檢查棧是否空 若?？諚？?，則表明該“右括弧右括弧”多余多余errorerror 否則和棧頂元素和棧頂元素比較， 若相匹配相匹配，則“左括弧出棧左括弧出?！?否則表明不匹配不匹配errorerror（3）表達(dá)式表達(dá)式檢驗檢驗結(jié)束時結(jié)束時， 若棧空?？?，則表明表達(dá)式中匹配正確匹配正確 否則表明“左括弧左括弧”有余有余errorerror Data Structures: Cha

20、pter 3.27Statusmatchpairs(SElemType str)SqStack*S;inttag=1;char*ch,e;/ e/ e存放出棧字符存放出棧字符/tag=1表示表達(dá)式中括號正確配對，表示表達(dá)式中括號正確配對，tag=0表示不配對表示不配對InitStack(&S);/初始化構(gòu)造一個空棧初始化構(gòu)造一個空棧Sch=str;while(*ch!=0)&(tag=1)switch(*ch)/ / 遇到遇到(，或或，將其入棧，將其入棧case(:case:case:Push(S,*ch);break; Data Structures: Chapter 3.2

21、8/遇到遇到)，或或，彈出棧頂字符，彈出棧頂字符case):Pop(S,&e);if(e!=()tag=0;break;/若棧頂不是對應(yīng)的若棧頂不是對應(yīng)的(，或或，則置，則置tag為為0；/endofswitchch+; /繼續(xù)判斷下一個字符繼續(xù)判斷下一個字符e=0;/將將e清空，以便存放下一次出棧的字符清空，以便存放下一次出棧的字符/endofwhile/如果棧為空且如果棧為空且tag為為1，則配對成功，則配對成功if(tag=1)&(S-top=S-base)printf(match!n);elseprintf(notmatch!n); Data Structures: C

22、hapter 3.29例3 行編輯程序問題如何實現(xiàn)？如何實現(xiàn)？ 是否是否每接受一個字符即存入存儲器每接受一個字符即存入存儲器 ? Data Structures: Chapter 3.30 設(shè)立一個設(shè)立一個輸入緩沖區(qū)輸入緩沖區(qū)，用以接受用，用以接受用戶輸入的一行字符，然后逐行存入用戶戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)數(shù)據(jù)區(qū); 并假設(shè)并假設(shè)“#”為為退格符退格符,“”為為退退行符行符。 在用戶在用戶輸入一行輸入一行的過程中，允許用的過程中，允許用戶輸入出差錯，并在發(fā)現(xiàn)有誤時可以及戶輸入出差錯，并在發(fā)現(xiàn)有誤時可以及時更正。時更正。合理的作法是： Data Structures: Chapte

23、r 3.31假設(shè)假設(shè)從終端從終端接受了這樣兩行字符：接受了這樣兩行字符： whli#ilr#e（s#*s) outputchar(*s=#+);則則實際有效實際有效的是下列兩行：的是下列兩行： while (*s) putchar(*s+); Data Structures: Chapter 3.32 while (ch != EOF & ch != n) switch (ch) case # : Pop(S, c); break; case : ClearStack(S); break; / 重置S為空棧 default : Push(S, ch); break; ch = getc

24、har( ); / 從終端接收下一個字符 ClearStack(S); / 重置S為空棧 if (ch != EOF) ch = getchar();while (ch != EOF) / EOF為全文結(jié)束符為全文結(jié)束符將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)； Data Structures: Chapter 3.33(1) (1) 問題的提出問題的提出 設(shè)計一個小計算器（設(shè)計一個小計算器（程序程序），希望從鍵），希望從鍵盤上輸入一個算術(shù)表達(dá)式（盤上輸入一個算術(shù)表達(dá)式（由運算符操作數(shù)由運算符操作數(shù)構(gòu)成的構(gòu)成的字符串字符串）后）后, ,在屏幕上顯示表達(dá)式的在屏幕上顯示表達(dá)式的求值結(jié)果。求值結(jié)

25、果。 例例4 表達(dá)式求值表達(dá)式求值 Data Structures: Chapter 3.34(2) (2) 表達(dá)式的構(gòu)成表達(dá)式的構(gòu)成 操作數(shù)操作數(shù)+ +運算符運算符+ +界符界符（如括號如括號）(3)(3) 表達(dá)式的求值：表達(dá)式的求值： 例例 5+6 5+6 (1+2)-4(1+2)-4 按照四則運算法則，上述表達(dá)式的計算過程為按照四則運算法則，上述表達(dá)式的計算過程為： 5+65+6 (1+2)-4(1+2)-4= =5+65+6 3-4 3-4 = = 5+18-4 5+18-4= = 23-4 23-4= =1919 表達(dá)式中運算符的運算順序為：表達(dá)式中運算符的運算順序為： + + ，

26、， + +， - - 如何確定運算符的如何確定運算符的運算順序運算順序？12341234 Data Structures: Chapter 3.35+ 2 1 -* */ /()#+-*/()# = = (4) (4) 算符間的優(yōu)先關(guān)系表算符間的優(yōu)先關(guān)系表注：注： 1 1 , ,2 2 是相鄰算符，是相鄰算符， 1 1在在左左， 2 2在在右右 1 1 2 2 表示表示1 1的的優(yōu)先權(quán)優(yōu)先權(quán)低于低于2 2 P.52P.52 Data Structures: Chapter 3.36( (5 5) ) 算符優(yōu)先算法算符優(yōu)先算法 分析表達(dá)式分析表達(dá)式5+45+4 (1+2)-6 (1+2)-6 計

27、算過程計算過程： 從左向右掃描表達(dá)式：從左向右掃描表達(dá)式：遇遇操作數(shù)操作數(shù)進(jìn)棧進(jìn)棧；遇遇運算符號運算符號 j與前面的剛掃描過的運算符與前面的剛掃描過的運算符 i比較比較若若 i j則則 j進(jìn)棧進(jìn)棧（已保存的運算符的優(yōu)先關(guān)系為已保存的運算符的優(yōu)先關(guān)系為 1 2 3 j則說明則說明 i是已掃描算符中優(yōu)先級最高者，是已掃描算符中優(yōu)先級最高者， j出棧，出棧，進(jìn)行運算；進(jìn)行運算；若若 i= j若若 i為為（， j為為）， j出棧，出棧，說明括號內(nèi)的式子已計算完；說明括號內(nèi)的式子已計算完；若若 i為為#，出棧，出棧，?？?，表達(dá)式計算完畢棧空，表達(dá)式計算完畢。5+4 (1+2)- 6 進(jìn)行運算的進(jìn)行運算的

28、算符算符 i i是當(dāng)前掃描過的運算符中是當(dāng)前掃描過的運算符中優(yōu)先級最高者優(yōu)先級最高者，可以利用可以利用兩個棧兩個棧分別保存掃描過程中遇到的分別保存掃描過程中遇到的操作數(shù)操作數(shù)和和運算符運算符。后面也許有優(yōu)先級后面也許有優(yōu)先級更大的算符更大的算符 Data Structures: Chapter 3.37 建立兩個工作棧。建立兩個工作棧。OPTR棧保存運算符；棧保存運算符；OPND棧棧-保存保存操作數(shù)或運算結(jié)果。操作數(shù)或運算結(jié)果。算法算法3.3operandTypeEvaluateExpression()/算術(shù)表達(dá)式求值的算符優(yōu)先算法。設(shè)算術(shù)表達(dá)式求值的算符優(yōu)先算法。設(shè)OPTR和和OPND/分別

29、為運算符棧和運算數(shù)棧，分別為運算符棧和運算數(shù)棧，OP為運算符集合為運算符集合。InitStack(OPTR);Push(OPTR,#);InitStack(OPND);c=getchar();While(c!=#|GetTop(OPTR)!=#)if(!In(c,OP)/In(c,OP)是判斷是判斷c是否為運算符的函數(shù)是否為運算符的函數(shù) Push(OPND,c);c=getchar();/不是運算符則進(jìn)不是運算符則進(jìn)數(shù)據(jù)棧數(shù)據(jù)棧OPNDelse Data Structures: Chapter 3.38續(xù)續(xù) switch(Precede(GetTop(OPTR),c)case:/棧頂算符優(yōu)先權(quán)

30、高棧頂算符優(yōu)先權(quán)高,出棧運算，并將運算結(jié)果入棧出棧運算，并將運算結(jié)果入棧OPNDPop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b);break;/switch/whilereturnGetTop(OPND);/EvaluateExpression Data Structures: Chapter 3.393.3 3.3 棧與遞歸棧與遞歸1 1什么是遞歸什么是遞歸 遞歸是一個很有用的工具，在數(shù)學(xué)和程序設(shè)計等許遞歸是一個很有用的工具，在數(shù)學(xué)和程序設(shè)計等許多領(lǐng)域中都用到了遞歸。多領(lǐng)域中都用到了遞歸。遞歸概念遞歸概念

31、：一個用一個用自己定義自己自己定義自己的定義的定義, ,稱為稱為遞歸定義遞歸定義。例例 n!= 1n!= 1* *2 2* *3 3* *4 4* * *(n-1)(n-1)* * n n n! n!遞歸定義遞歸定義 n!= 1 n!= 1 當(dāng)當(dāng) n=0 n=0 時時 n!= n!= n n(n-1)!(n-1)! 當(dāng)當(dāng) n0 n0 時時用用(n-1)!定義定義n! Data Structures: Chapter 3.40例例1編寫求解編寫求解階乘階乘n!的遞歸算法的遞歸算法 n!的遞歸定義的遞歸定義：基本項：基本項：n!=1當(dāng)當(dāng)n=1遞歸項：遞歸項：n!=n(n-1)!當(dāng)當(dāng)n1遞歸算法：遞

32、歸算法：intfact(intn)/算法功能是求解并返回算法功能是求解并返回n的階乘的階乘 If（n=1）return（1）；）；elsereturn（n*fact(n-1)）；）； Data Structures: Chapter 3.41例例2 2 編寫求解編寫求解HanoiHanoi塔問題的遞歸算法塔問題的遞歸算法 有有3個各為個各為X，Y，Z的塔座，在的塔座，在X項上有項上有n個大小不同，依個大小不同，依小到大編號為小到大編號為1，2，n的圓盤。的圓盤?，F(xiàn)要求將現(xiàn)要求將X上的上的n個圓盤移至個圓盤移至Z上，并仍以同樣順序疊放，上，并仍以同樣順序疊放，圓盤移動時必須圓盤移動時必須遵守下列

33、原則遵守下列原則：（1）每次）每次移動移動1個個盤子；盤子；（2）圓盤可以放在）圓盤可以放在X，Y，Z中的任一塔座上；中的任一塔座上；（3）任何時刻都）任何時刻都不能不能將較大的圓盤壓放在較小圓盤之上；將較大的圓盤壓放在較小圓盤之上； Data Structures: Chapter 3.42abc321 11213121例例:n=3時圓盤移動的過程如下圖所示時圓盤移動的過程如下圖所示：Y YX XZ Z Data Structures: Chapter 3.43 求解求解Hanoi塔問題的遞歸描述（定義）塔問題的遞歸描述（定義）基本項：基本項：n=1時，將時，將n號圓盤從號圓盤從X移至移至Z

34、；遞歸項：遞歸項：n1時，時，將將X上上1n-1號圓盤移至號圓盤移至Y；將將X上的上的n號圓盤從號圓盤從X移至移至Z;將將Y上上1n-1號圓盤從號圓盤從Y移至移至Z; 將規(guī)模為將規(guī)模為n n的問題的求的問題的求解歸結(jié)為規(guī)模為解歸結(jié)為規(guī)模為n-1n-1的的問題的求解問題的求解有了問題的遞歸定義，有了問題的遞歸定義，很容易寫出對應(yīng)的很容易寫出對應(yīng)的遞歸算法遞歸算法： Data Structures: Chapter 3.44voidhanoi(intn,charx,chary,charz)/將塔座將塔座x上按直徑由小到大，且自上而下編號為上按直徑由小到大，且自上而下編號為1至至n的的n個圓盤按規(guī)則

35、搬到個圓盤按規(guī)則搬到/塔座塔座z上，上，y可用作輔助塔座?？捎米鬏o助塔座。/搬動操作搬動操作move(x,n,z)可定義為可定義為(c是初值為是初值為0的全局變量，對搬動計數(shù)的全局變量，對搬動計數(shù))：/printf(“%d.Movedisk%dfrom%cto%cn”,+c,n,x,z);if(n=1)move(x,1,z);/將編號為將編號為1的圓盤從的圓盤從x移動移動zelsehanoi(n-1,x,z,y);/將將x上編號為上編號為1至至n-1的圓盤移到的圓盤移到y(tǒng),z作輔助塔作輔助塔move(x,n,z);/將編號為將編號為n的圓盤從的圓盤從x移到移到zhanoi(n-1,y,x,z)

36、；/將將y上編號為上編號為1至至n-1的圓盤移到的圓盤移到z,x作輔助塔作輔助塔算法算法3.5Hanoi塔問題塔問題 Data Structures: Chapter 3.453 3.4 .4 隊隊 列列3.4.13.4.1 隊列的定義及基本運算隊列的定義及基本運算 一一 什么是隊列什么是隊列 隊列隊列是限定僅能在是限定僅能在表頭表頭進(jìn)行進(jìn)行刪除刪除，表尾表尾進(jìn)行進(jìn)行插入插入的線性表。的線性表。（ a1, a2, . , ai -1, ai , ai+1, , an ）插入插入刪除刪除 Data Structures: Chapter 3.46說明：設(shè)說明：設(shè)（a1,a2,a3,.,an）為一

37、隊列為一隊列(1)表尾稱作表尾稱作隊尾隊尾，表頭稱為，表頭稱為隊頭隊頭；(2)a1為為隊頭隊頭元素，元素，an為為隊尾隊尾元素；元素；(3)在在表尾插入表尾插入元素操作，稱為元素操作，稱為入隊入隊操作；操作；在在表頭刪除表頭刪除元素的操作，稱為元素的操作，稱為出隊出隊操作；操作；(4)元素按元素按a1,a2,a3,.an順序入隊，順序入隊，第第1個個入隊入隊的元素為的元素為a1，最后一個入隊的元素是，最后一個入隊的元素是an；第第1個個出隊出隊的元素為的元素為a1,最后一個出隊的元素是最后一個出隊的元素是an(5)隊列具有隊列具有先進(jìn)先出先進(jìn)先出的特點，所以又稱為的特點，所以又稱為先進(jìn)先出先進(jìn)

38、先出表（表（FIFO表）表） Data Structures: Chapter 3.47二隊列的基本操作二隊列的基本操作（1）初始化操作）初始化操作InitQueue(&Q)功能：構(gòu)造一個空隊列功能：構(gòu)造一個空隊列Q；（2）銷毀操作銷毀操作DestroyQueue(&Q)功能：銷毀已存在隊列功能：銷毀已存在隊列Q；（3）置空操作置空操作ClearQueue(&Q)功能：功能：將隊列將隊列Q置為空隊列；置為空隊列；（4）判空操作）判空操作QueueEmpty(Q)功能：若隊列功能：若隊列Q為空，則返回為空，則返回True，否則返回否則返回False； Data Struc

39、tures: Chapter 3.48 （5）取隊頭元素操作取隊頭元素操作GetHead(Q,&e)功能：取隊頭元素，并用功能：取隊頭元素，并用e返回；返回；（6）入隊操作入隊操作EnQueue(&Q,e)功能：將元素功能：將元素e插入插入Q的隊尾；的隊尾； （7）出隊操作）出隊操作DeQueue(&Q,&e)功能：若隊列不空，則刪除功能：若隊列不空，則刪除Q的隊頭元素，用的隊頭元素，用e返回其值，并返回返回其值，并返回OK，否則返回否則返回ERROR； Data Structures: Chapter 3.493.4.3.4.2 2 隊列的順序表示和實現(xiàn)隊列的

40、順序表示和實現(xiàn) 一、一、 隊列的順序存貯結(jié)構(gòu)隊列的順序存貯結(jié)構(gòu)隊列的隊列的順序存儲順序存儲結(jié)構(gòu)是用一組結(jié)構(gòu)是用一組地址連續(xù)地址連續(xù)的存儲單的存儲單元依次存放隊列中的各個元素，并用指針元依次存放隊列中的各個元素，并用指針front指指向隊頭，指針向隊頭，指針rear指向隊尾指向隊尾 。Q.rearQ.frontJ1J2J3實際上，實際上，front指針始終指向隊指針始終指向隊頭元素，頭元素，rear指針實際上并不指針實際上并不是指向隊尾元素，而是指向隊是指向隊尾元素，而是指向隊尾元素的下一個位置。如圖：尾元素的下一個位置。如圖：隊列的順序存貯結(jié)構(gòu)圖示隊列的順序存貯結(jié)構(gòu)圖示 Data Struct

41、ures: Chapter 3.50#defineMAXSIZE100/最大隊列長度最大隊列長度typedefstructQElemType*base;/初始化時動態(tài)分配初始化時動態(tài)分配存儲空間的存儲空間的基址基址intfront;/隊頭指針，指向隊頭指針，指向隊頭元素隊頭元素intrear;/隊尾指針，指向隊尾指針，指向隊尾隊尾元素的元素的下一個位置下一個位置SqQueue;二、順序隊列的類型定義二、順序隊列的類型定義 Data Structures: Chapter 3.51順序隊列常常會出現(xiàn)順序隊列常常會出現(xiàn)“假溢出假溢出”現(xiàn)象，如現(xiàn)象，如圖所示。雖然隊列中圖所示。雖然隊列中還有一定的存

42、儲空間，還有一定的存儲空間，但因為但因為front指針與指針與rear指針均向同一個指針均向同一個方向移動，導(dǎo)致該隊方向移動，導(dǎo)致該隊列不能再進(jìn)行入隊操列不能再進(jìn)行入隊操作。作。rearfrontE ED DC C Data Structures: Chapter 3.52 為了避免“假溢出”，可以這樣規(guī)定，一旦 rear指針（或 front指針）指向了存儲空間的末尾位置，如果此時再進(jìn)行入隊（或出隊）操作，則將相應(yīng)的指針平移到數(shù)組的起始位置，即是將隊列假想為一個循環(huán)的環(huán)狀空間，我們稱之為循環(huán)循環(huán)隊列隊列。 Data Structures: Chapter 3.53三、循環(huán)隊列操作圖示front

43、rear空隊空隊front=rear是是隊空隊空標(biāo)志標(biāo)志3120MAXSIZE=4ArearfrontA進(jìn)隊進(jìn)隊B進(jìn)隊進(jìn)隊ABrearfrontC進(jìn)隊進(jìn)隊ArearfrontBC Data Structures: Chapter 3.54frontrear空隊空隊front=rear是隊空標(biāo)志是隊空標(biāo)志BCrearfront3120MAXSIZE=4A A 出隊出隊三、循環(huán)隊列操作圖示隊列中含有隊列中含有3個元素，個元素，rear已經(jīng)指向存儲空已經(jīng)指向存儲空間的末端，不能再向間的末端，不能再向上移動上移動ArearfrontBC Data Structures: Chapter 3.55fro

44、ntrear空隊空隊front=rear是隊空標(biāo)志是隊空標(biāo)志Crearfrontrearfront3120MAXSIZE=4BCB B 出隊出隊三、循環(huán)隊列操作圖示隊列中含有隊列中含有2個元素個元素 Data Structures: Chapter 3.56CrearfrontDMAXSIZE=4此刻此刻rear已經(jīng)指向存儲空間的末端已經(jīng)指向存儲空間的末端若再有元素進(jìn)隊列，則執(zhí)行語句：若再有元素進(jìn)隊列，則執(zhí)行語句： rear=(rear+1)% MAXSIZErearfrontC三、循環(huán)隊列操作圖示D元素進(jìn)隊列，執(zhí)行：元素進(jìn)隊列，執(zhí)行：rearrear=(rear+1)%=(rear+1)%

45、MAXSIZEMAXSIZE經(jīng)過計算，經(jīng)過計算，rear的值為的值為0 Data Structures: Chapter 3.57frontrear空隊空隊front=rear是隊空標(biāo)志是隊空標(biāo)志CCrearfrontrearfrontDE3120MAXSIZE=4DE進(jìn)隊進(jìn)隊三、循環(huán)隊列操作圖示Rear重新指向存儲重新指向存儲空間的起始位置，空間的起始位置，此刻隊列仍有存儲此刻隊列仍有存儲空間，可以進(jìn)行進(jìn)空間，可以進(jìn)行進(jìn)隊操作隊操作 Data Structures: Chapter 3.58frontrear空隊空隊front=rear是隊空標(biāo)志是隊空標(biāo)志CCrearfrontrearfro

46、ntDEF3120MAXSIZE=4 F進(jìn)隊進(jìn)隊，隊滿，隊滿隊滿隊滿與與隊空隊空條件混淆條件混淆ED三、循環(huán)隊列操作圖示 Data Structures: Chapter 3.59frontrear空隊空隊front=rear是隊空標(biāo)志是隊空標(biāo)志CrearfrontDEF3120MAXSIZE=4為了區(qū)分隊滿與隊空，規(guī)定為了區(qū)分隊滿與隊空，規(guī)定隊滿條件隊滿條件為為：(rear+1)%MAXQSIZE=front所以隊列中最多能包含的元素個數(shù)比實際所以隊列中最多能包含的元素個數(shù)比實際空間空間少一個少一個隊滿隊滿三、循環(huán)隊列操作圖示 Data Structures: Chapter 3.60出隊時

47、出隊時應(yīng)先判應(yīng)先判-隊是否隊是否空空?隊空隊空條件條件：Q.rear=Q.front 不空，則出隊。不空，則出隊。進(jìn)隊時進(jìn)隊時應(yīng)先判應(yīng)先判-隊是否隊是否滿滿?隊滿隊滿條件條件：(Q.rear+1)%MAXQSIZE)=Q.front 不滿，則進(jìn)隊不滿，則進(jìn)隊。 Data Structures: Chapter 3.61(1)初始化循環(huán)隊初始化循環(huán)隊StatusInitQueue(SqQueue&Q)Q.base=(QElemType*)malloc(MAXSIZE*sizeof(QElemType);if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;

48、returnOK;四、循環(huán)隊列基本操作的實現(xiàn)Q.base=newQElemTypeMAXSIXE; Data Structures: Chapter 3.62（2）進(jìn)隊操作進(jìn)隊操作StatusEnSqQueue(SqQueue&Q,QElemTypee)if(Q.rear+1)%MAXQSIZE)=Q.front)returnERROR;/隊滿隊滿Q.baseQ.rear=e;/ e 入隊入隊Q.rear=(Q.rear+1)%MAXQSIZE);/修改尾指針修改尾指針returnOK;/EnQueue;CrearfrontDE3120CrearfrontDEDrearfront再進(jìn)隊

49、再進(jìn)隊 滿滿（上溢）（上溢）再進(jìn)隊循環(huán)、再進(jìn)隊循環(huán)、滿滿再進(jìn)隊循環(huán)、再進(jìn)隊循環(huán)、不滿不滿DrearfrontSS進(jìn)隊進(jìn)隊 Data Structures: Chapter 3.63（3）出隊操作出隊操作P.76StatusDeSqQueue(SqQueue&Q,QElemType&e)if(Q.rear=Q.front)returnERROR;/隊空隊空e=Q.baseQ.front;/取隊首元素取隊首元素Q.front=(Q.front+1)%MAXQSIZE;/出隊出隊returnOK;CrearfrontE出隊出隊不循環(huán)不循環(huán)rearfrontE出隊出隊不循環(huán)不循環(huán)rea

50、rfront隊隊空空 Data Structures: Chapter 3.643.4.3.4.3 3 鏈隊列鏈隊列 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)和實現(xiàn)隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)和實現(xiàn)一、定義一、定義 用鏈表表示的隊列，稱為用鏈表表示的隊列，稱為鏈隊列鏈隊列Q.frontQ.rear空鏈隊列空鏈隊列J1J1Q.frontQ.rear J2J2 非空鏈隊列非空鏈隊列 Data Structures: Chapter 3.65二、鏈隊列的二、鏈隊列的類型定義類型定義typedefstructQNode/鏈隊列鏈隊列結(jié)點的類型結(jié)點的類型定義定義QElemTypedata;structQNode*next;QNode,

51、*QueuePtr;typedefstruct/鏈隊列鏈隊列表頭結(jié)點表頭結(jié)點的類型定義的類型定義QueuePtr*front;/隊頭指針，指向鏈表的隊頭指針，指向鏈表的頭結(jié)點頭結(jié)點QueuePtr*rear;/隊尾指針，指向隊尾指針，指向隊尾結(jié)點隊尾結(jié)點LinkQueue; Data Structures: Chapter 3.66 設(shè)設(shè)Q為為LinkQueue類型的變量，類型的變量，Q為鏈隊列的為鏈隊列的表頭結(jié)點表頭結(jié)點，用于，用于存儲隊列存儲隊列隊頭指針和隊尾指針隊頭指針和隊尾指針。鏈隊列的鏈隊列的表頭結(jié)點表頭結(jié)點鏈隊列的鏈隊列的頭結(jié)點頭結(jié)點空鏈隊列空鏈隊列J1J1Q.frontQ.rea

52、r J2J2 非空鏈隊列非空鏈隊列Q.frontQ.rear Data Structures: Chapter 3.67（1）初始化隊操作：初始化隊操作：InitQueue(LinkQueue&Q)StatusInitQueue(LinkQueue&Q)/建建一個空隊列一個空隊列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);/為為鏈隊列的鏈隊列的頭結(jié)點頭結(jié)點分配空間分配空間if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;returnOK;三、三、 鏈隊列基本操作的算法鏈隊列基本操作的算法Q.frontQ.rear空鏈隊列空鏈隊列 Data Structures: Chapter 3.68銷毀銷毀隊隊操作操作：DestroyQueue(LinkQueue&Q)StatusDestroyQueue(LinkQu