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

第3章限定性線性表—棧和隊(duì)列3.1棧3.2棧的應(yīng)用舉例3.3棧與遞歸的實(shí)現(xiàn)3.4隊(duì)列第3章限定性線性表—棧和隊(duì)列3.1棧13.1棧3.1.1棧的定義棧作為一種限定性線性表，是將線性表的插入和刪除運(yùn)算限制為僅在表尾進(jìn)行，通常將表中允許進(jìn)行插入、刪除操作的一端稱為棧頂(Top)，因此棧頂?shù)漠?dāng)前位置是動(dòng)態(tài)變化的，它由一個(gè)稱為棧頂指針的位置指示器指示。同時(shí)表的另一端被稱為棧底(Bottom)。當(dāng)棧中沒(méi)有元素時(shí)稱為空棧。棧的插入操作被形象地稱為進(jìn)?；蛉霔?，刪除操作稱為出棧或退棧。

3.1棧3.1.1棧的定義2設(shè)S=(a1,a2,…,an)表示棧，則a1為棧底元素，an

為棧頂元素。棧是一種后進(jìn)先出（LastInFirstOut）的線性表（簡(jiǎn)稱LIFO結(jié)構(gòu)）。圖3.1棧設(shè)S=(a1,a2,…,an)表示棧，則a1為棧底元素，an3棧只能對(duì)棧頂元素進(jìn)行插入和刪除操作。例：若輸入A，B，C，D，同時(shí)在插入的時(shí)候也可能進(jìn)行刪除操作。可能的輸出序列為：B，A，C，D;

C、D、A、B；D，A，C，B；C、A、D、B；D，C，A，B；C、B、D、A；B，C，A，D；A，C，B，D；棧只能對(duì)棧頂元素進(jìn)行插入和刪除操作。4ADTStack{

數(shù)據(jù)元素：可以是任意類型的數(shù)據(jù)，但必須屬于同一個(gè)數(shù)據(jù)對(duì)象。數(shù)據(jù)關(guān)系：棧中數(shù)據(jù)元素之間是線性關(guān)系。基本操作：（1）InitStack(&S)

初始條件：S為未初始化的棧。操作結(jié)果：將S初始化為空棧。（2）ClearStack(&S)

初始條件：棧S已經(jīng)存在。操作結(jié)果：將棧S置成空棧。ADTStack{5

（3）StackEmpty(S)

初始條件：棧S已經(jīng)存在。操作結(jié)果：若S為空棧，則函數(shù)值為TRUE，否則FALSE

（4）Push(&S,e)

初始條件：棧S已經(jīng)存在。操作結(jié)果：在S的頂部插入(亦稱壓入)元素e；（3）StackEmpty(S)6

（5）Pop(&S,&e)

初始條件：棧S已經(jīng)存在。操作結(jié)果：刪除(亦稱彈出)棧S的頂部元素，并用e帶回該值。（6）GetTop(S,&e)

初始條件：棧S已經(jīng)存在。操作結(jié)果：取棧S的頂部元素。與Pop(&S,e)不同之處在于GetTop(S,&e)不改變棧頂?shù)奈恢?。?）Pop(&S,&e)73.1.2棧的表示和實(shí)現(xiàn)1.順序棧順序棧是用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧，即利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)由于棧的操作的特殊性，還必須附設(shè)一個(gè)位置指針top（棧頂指針）來(lái)動(dòng)態(tài)地指示棧頂元素在順序棧中的位置。通常以top=0表示空棧。順序棧的存儲(chǔ)結(jié)構(gòu)可以用C語(yǔ)言中的一維數(shù)組來(lái)表示。棧的順序存儲(chǔ)結(jié)構(gòu)定義如下：3.1.2棧的表示和實(shí)現(xiàn)1.順序棧8＃defineTRUE1＃defineFALSE0typedefstruct{SElemType*base;SElemType*top;intstacksize;//棧可使用的最大容量}SqStack;

按初始分配量進(jìn)行第一次存儲(chǔ)分配，base為棧底指針，始終指向棧底。top為棧頂指針，初值指向棧底，每插入一個(gè)元素，top增1；每刪除一個(gè)元素，top減1，top始終在棧頂元素的下一個(gè)位置上。

＃defineTRUE19圖3.2順序棧中的進(jìn)棧和出棧43210432104321043210圖3.2順序棧中的進(jìn)棧和出棧444410順序?；静僮鞯膶?shí)現(xiàn)如下:(1)初始化。StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}順序棧基本操作的實(shí)現(xiàn)如下:StatusInitStac11(2)取棧頂元素StatusGetTop(SqStackS,SElemType&e){if(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}(2)取棧頂元素12(3)入棧。StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}(3)入棧。13(4)出棧StatusPop(SqStack&S,SelemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}(4)出棧142.鏈棧圖3.4鏈棧示意圖鏈?zhǔn)綏o(wú)棧滿問(wèn)題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^適合于多棧操作2.鏈棧圖3.4鏈棧示意圖鏈?zhǔn)綏o(wú)棧滿問(wèn)題，空間可152.鏈棧

圖3.4鏈棧示意圖棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)際上就是一個(gè)單鏈表，叫做鏈棧。插入和刪除操作只能在鏈棧的棧頂進(jìn)行。

棧頂指針Top應(yīng)該在鏈表的哪一頭？

鏈?zhǔn)綏５臈ｍ斣阪滎^插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏o(wú)棧滿問(wèn)題，空間可擴(kuò)充適合于多棧操作2.鏈棧圖3.4鏈棧示意圖棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)162.鏈棧/*

鏈棧結(jié)構(gòu)

*/

typedef

struct

StackNode

{

SElemType

data;

//節(jié)點(diǎn)數(shù)據(jù)域

struct

StackNode

*next;//節(jié)點(diǎn)指針域

}StackNode,*LinkStackPtr;

//節(jié)點(diǎn)指針

typedef

struct

LinkStack

{

LinkStackPtr

top;

//棧頂指針

int

count;

//棧中元素個(gè)數(shù)}LinkStack;

2.鏈棧/*

鏈棧結(jié)構(gòu)

*/

172.鏈棧//棧的初始化操作Status

InitStack(LinkStack

*S)

{

S->top

=

(LinkStackPtr)malloc(sizeof(StackNode));

if(!S->top)

return

ERROR;

S->top

=

NULL;

S->count

=

0;

return

OK;

}

2.鏈棧//棧的初始化操作182.鏈棧/*

把S置為空棧

*/

Status

ClearStack(LinkStack

*S)

{

LinkStackPtr

p,q;

p

=

S->top;

while(p)

{

q

=

p;

p

=

p->next;

free(q);

}

S->count=0;

return

OK;

}

2.鏈棧/*

把S置為空棧

*/

192.鏈棧/*

若棧S為空棧，則返回TRUE，否則返回FALSE

*/

Status

IsEmptyStack(LinkStack

S)

{

if

(S.count

==

0)

{

return

TRUE;

}

else

{

return

FALSE;

}

}

2.鏈棧/*

若棧S為空棧，則返回TRUE，否則返回FA202.鏈棧/*

若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR

*/

Status

GetTopElem(LinkStack

S,SElemType

*e)

{

if

(S.top

==

NULL)

{

return

ERROR;

}

else

{

*e

=

S.top->data;

}

return

OK;

}

2.鏈棧/*

若棧不空，則用e返回S的棧頂元素，并返回O212.鏈棧Status

Push(LinkStack

*S,SElemType

e)

{

LinkStackPtr

s=(LinkStackPtr)malloc(sizeof(StackNode));

if

(!s)

{

return

ERROR;

}

s->data

=

e;

s->next

=

S->top

S->top

=

s;

S->count++;

return

OK;

}

2.鏈棧Status

Push(LinkStack

*S222.鏈棧/*

若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR

*/

Status

Pop(LinkStack

*S,SElemType

*e)

{

LinkStackPtr

p;

if(IsEmptyStack(*S))

{

return

ERROR;

}

*e

=

S->top->data;

p

=

S->top;

S->top

=

S->top->next

free(p);

S->count--;

return

OK;

}

2.鏈棧/*

若棧不空，則刪除S的棧頂元素，用e返回其值233.2棧的應(yīng)用舉例1.數(shù)制轉(zhuǎn)換假設(shè)要將十進(jìn)制數(shù)N轉(zhuǎn)換為d進(jìn)制數(shù)，一個(gè)簡(jiǎn)單的轉(zhuǎn)換算法是重復(fù)下述兩步，直到N等于零：X=Nmodd(其中mod為求余運(yùn)算)N=Ndivd(其中div為整除運(yùn)算)3.2棧的應(yīng)用舉例1.數(shù)制轉(zhuǎn)換24如(1348)10=(2504)8

NN/8N%8134816841682102125202如(1348)10=(2504)8NN/8N%8125voidconversion(){ InitStack(S); scanf(“%d”,&N); while(N) { Push(s,N%8); N=N/8; } while(!StackEmpty(s)){ Pop(S,e); printf(“%d”,e); }}voidconversion()262.括號(hào)匹配問(wèn)題假設(shè)表達(dá)式中包含三種括號(hào)：圓括號(hào)、方括號(hào)和花括號(hào)，它們可互相嵌套，如([{}]([]))或({([][()])})等均為正確的格式，而{[]})}或{[()]或([]}均為不正確的格式。在檢驗(yàn)算法中可設(shè)置一個(gè)空棧。讀入字符直到文件尾。如果字符是一個(gè)左括號(hào)，則直接入棧。如果字符是一個(gè)右括號(hào)，那么若棧為空，則報(bào)錯(cuò)；若棧不為空，則將棧頂元素出棧。如果出棧的符號(hào)不是對(duì)應(yīng)的左括號(hào)，則報(bào)錯(cuò)。在文件尾，如果棧非空則報(bào)錯(cuò)。2.括號(hào)匹配問(wèn)題273.表達(dá)式求值

表達(dá)式求值是高級(jí)語(yǔ)言編譯中的一個(gè)基本問(wèn)題，是棧的典型應(yīng)用實(shí)例。任何一個(gè)表達(dá)式都是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成的。操作數(shù)既可以是常數(shù)，也可以是被說(shuō)明為變量或常量的標(biāo)識(shí)符；運(yùn)算符可以分為算術(shù)運(yùn)算符、關(guān)系運(yùn)算符和邏輯運(yùn)算符三類；基本界限符有左右括號(hào)和表達(dá)式結(jié)束符等。3.表達(dá)式求值表達(dá)式求值是高級(jí)語(yǔ)言編譯中的28[例]算術(shù)表達(dá)式5+6/2-3*4。正確理解：

5+6/2-3*4=5+3-3*4=8-3*4=8-12=-4由兩類對(duì)象構(gòu)成的：（1）操作數(shù)，如2、3、4（2）運(yùn)算符號(hào)，如+、-、*、/不同運(yùn)算符號(hào)優(yōu)先級(jí)不一樣[例]算術(shù)表達(dá)式5+6/2-3*4。正確理解：29后綴表達(dá)式

中綴表達(dá)式：運(yùn)算符號(hào)位于兩個(gè)運(yùn)算數(shù)之間。如a+b*

c-

d/

e后綴表達(dá)式：運(yùn)算符號(hào)位于兩個(gè)運(yùn)算數(shù)之后。如abc*+

de/-〖例〗62/

3-

42*+

=?

后綴表達(dá)式求值策略：從左向右“掃描”，逐個(gè)處理運(yùn)算數(shù)和運(yùn)算符號(hào)。1.遇到運(yùn)算數(shù)怎么辦？如何“記住”目前還不未參與運(yùn)算的數(shù)？2.遇到運(yùn)算符號(hào)怎么辦？對(duì)應(yīng)的運(yùn)算數(shù)是什么？啟示：需要有種存儲(chǔ)方法，能順序存儲(chǔ)運(yùn)算數(shù)，并在需要時(shí)“倒序”輸出！后綴表達(dá)式中綴表達(dá)式：運(yùn)算符號(hào)位于兩個(gè)運(yùn)算數(shù)之間。如a30對(duì)象:6(運(yùn)算數(shù))〖例〗62/

3-

42*+

=?

對(duì)象:2(運(yùn)算數(shù))對(duì)象:/

(運(yùn)算符)對(duì)象:3(運(yùn)算數(shù))

對(duì)象:-

(運(yùn)算符)

對(duì)象:4(運(yùn)算數(shù))

對(duì)象:2(運(yùn)算數(shù))

對(duì)象:*

(運(yùn)算符)對(duì)象:+

(運(yùn)算符)

Pop:8top62toptop2

6

/=33333-=0042top24*=8880+=88T(N)=O(N)8對(duì)象:6(運(yùn)算數(shù))〖例〗62/3-4231中綴表達(dá)式求值

基本策略：將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，然后求值

如何將中綴表達(dá)式轉(zhuǎn)換為后綴？觀察一個(gè)簡(jiǎn)單例子：3+4*5-6345*+6–1.運(yùn)算數(shù)相對(duì)順序不變2.運(yùn)算符號(hào)順序發(fā)生改變需要存儲(chǔ)“等待中”的運(yùn)算符號(hào)要將當(dāng)前運(yùn)算符號(hào)與“等待中”的最后一個(gè)運(yùn)算符號(hào)比較有括號(hào)怎么辦？棧中綴表達(dá)式求值有括號(hào)怎么辦？棧32〖例〗3*

(4+5

)/

6

=?345+*6/top輸出:3輸入對(duì)象:3(操作數(shù))

輸入對(duì)象:*

(乘法)輸入對(duì)象:((左括號(hào))輸入對(duì)象:4(操作數(shù))輸入對(duì)象:+

(加法)輸入對(duì)象:5(操作數(shù))輸入對(duì)象:)(右括號(hào))輸入對(duì)象:/

(除法)輸入對(duì)象:6(操作數(shù))(4+5T(N)=O(N)*+*/6/〖例〗3*(4+5)/6=?34533中綴表達(dá)式如何轉(zhuǎn)換為后綴表達(dá)式從頭到尾讀取中綴表達(dá)式的每個(gè)對(duì)象，對(duì)不同對(duì)象按不同的情況處理。①運(yùn)算數(shù)：直接輸出；②左括號(hào)：壓入棧；③右括號(hào)：將棧頂?shù)倪\(yùn)算符彈出并輸出，直到遇到左括號(hào)（出棧，不輸出）；④運(yùn)算符：?若優(yōu)先級(jí)大于棧頂運(yùn)算符時(shí)，則把它壓棧；?若優(yōu)先級(jí)小于等于棧頂運(yùn)算符時(shí)，將棧頂運(yùn)算符彈出并輸出；再比較新的棧頂運(yùn)算符，直到該運(yùn)算符大于棧頂運(yùn)算符優(yōu)先級(jí)為止，然后將該運(yùn)算符壓棧；⑤若各對(duì)象處理完畢，則把棧中存留的運(yùn)算符一并輸出。中綴表達(dá)式如何轉(zhuǎn)換為后綴表達(dá)式從頭到尾讀取中綴表達(dá)式的341）無(wú)括號(hào)算術(shù)表達(dá)式求值

表達(dá)式計(jì)算程序設(shè)計(jì)語(yǔ)言中都有計(jì)算表達(dá)式的問(wèn)題，這是語(yǔ)言編譯中的典型問(wèn)題。

(1)表達(dá)式形式：由運(yùn)算對(duì)象、運(yùn)算符及必要的表達(dá)式括號(hào)組成；

(2)表達(dá)式運(yùn)算：運(yùn)算時(shí)要有一個(gè)正確的運(yùn)算形式順序。由于某些運(yùn)算符可能具有比別的運(yùn)算符更高的優(yōu)先級(jí)，因此表達(dá)式不可能嚴(yán)格的從左到右進(jìn)行運(yùn)算，見(jiàn)圖3.5。1）無(wú)括號(hào)算術(shù)表達(dá)式求值表達(dá)式計(jì)算35圖3.5表達(dá)式運(yùn)算及運(yùn)算符優(yōu)先級(jí)圖3.5表達(dá)式運(yùn)算及運(yùn)算符優(yōu)先級(jí)36圖3.6無(wú)括號(hào)算術(shù)表達(dá)式的處理過(guò)程圖3.6無(wú)括號(hào)算術(shù)表達(dá)式的處理過(guò)程372）算術(shù)表達(dá)式處理規(guī)則

(1)規(guī)定優(yōu)先級(jí)表。

(2)設(shè)置兩個(gè)棧：OVS(運(yùn)算數(shù)棧)和OPTR(運(yùn)算符棧)。

(3)自左向右掃描，遇操作數(shù)進(jìn)OVS，遇操作符則與OPTR棧頂優(yōu)先數(shù)比較：當(dāng)前操作符>OPTR棧頂,當(dāng)前操作符進(jìn)OPTR棧；當(dāng)前操作符≤OPTR棧頂，OVS棧頂、次頂和OPTR棧頂，退棧形成運(yùn)算T(i)，T(i)進(jìn)OVS棧。例：實(shí)現(xiàn)A/B*C+D*E＃的運(yùn)算過(guò)程時(shí)棧區(qū)變化情況。2）算術(shù)表達(dá)式處理規(guī)則38棧的其他應(yīng)用：

函數(shù)調(diào)用及遞歸實(shí)現(xiàn)深度優(yōu)先搜索回溯算法……棧的其他應(yīng)用：393.3棧與遞歸的實(shí)現(xiàn)

棧非常重要的一個(gè)應(yīng)用是在程序設(shè)計(jì)語(yǔ)言中用來(lái)實(shí)現(xiàn)遞歸。遞歸是指在定義自身的同時(shí)又出現(xiàn)了對(duì)自身的調(diào)用。如果一個(gè)函數(shù)在其定義體內(nèi)直接調(diào)用自己，則稱其為直接遞歸函數(shù)；如果一個(gè)函數(shù)經(jīng)過(guò)一系列的中間調(diào)用語(yǔ)句，通過(guò)其它函數(shù)間接調(diào)用自己，則稱其為間接遞歸函數(shù)。3.3棧與遞歸的實(shí)現(xiàn)棧非常重要的一個(gè)40遞歸過(guò)程的實(shí)現(xiàn)一個(gè)函數(shù)調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行被調(diào)用函數(shù)之前，系統(tǒng)做的工作有：

(1)保留本層參數(shù)與返回地址（將所有的實(shí)參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存）；

(2)給下層參數(shù)賦值（為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū)）；

(3)將程序轉(zhuǎn)移到被調(diào)函數(shù)的入口。遞歸過(guò)程的實(shí)現(xiàn)41

而從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，系統(tǒng)也應(yīng)完成三件工作：

(1)保存被調(diào)函數(shù)的計(jì)算結(jié)果；

(2)恢復(fù)上層參數(shù)（釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)）；

(3)依照被調(diào)函數(shù)保存的返回地址，將控制轉(zhuǎn)移回調(diào)用函數(shù)。當(dāng)多個(gè)函數(shù)調(diào)用時(shí)按后調(diào)用先返回的原則。

而從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，系統(tǒng)也應(yīng)完成三42

系統(tǒng)將整個(gè)程序運(yùn)行時(shí)所需的數(shù)據(jù)空間安排在一個(gè)棧中，每次調(diào)用一個(gè)函數(shù)時(shí)就為它在棧頂分配一個(gè)存儲(chǔ)區(qū)，當(dāng)一個(gè)函數(shù)返回時(shí)就釋放它的存儲(chǔ)區(qū)，當(dāng)前正在運(yùn)行的函數(shù)所有數(shù)據(jù)必在棧頂。voidfirst(int,int);voidfirst(ints,intt)voidsecond(int); {voidmain() inti;{ ……intm,n; sencond(i);

…… 2:first(m,n); ……1: }

…… voidsecond(intd) {} intx,y;

…… }

系統(tǒng)將整個(gè)程序運(yùn)行時(shí)所需的數(shù)據(jù)空間安排在一個(gè)棧中，432)遞歸結(jié)構(gòu)

例：n階Hanoi塔問(wèn)題：假設(shè)有三個(gè)分別命名為X、Y和Z的塔座，在塔座X上插有n個(gè)直徑大小各不相同、依小到大編號(hào)為1，2,…，n的圓盤?，F(xiàn)要求將X軸上的n個(gè)圓盤移至塔座Z上并仍按同樣順序疊排，圓盤移動(dòng)時(shí)必須遵循下列原則：

(1)每次只能移動(dòng)一個(gè)圓盤；

(2)圓盤可以插在X、Y和Z中的任何一個(gè)塔座上；

(3)任何時(shí)刻都不能將一個(gè)較大的圓盤壓在較小的圓盤之上。2)遞歸結(jié)構(gòu)例：n階Hanoi塔問(wèn)題：假44

如何實(shí)現(xiàn)移動(dòng)圓盤的操作呢？當(dāng)n=1時(shí)，問(wèn)題比較簡(jiǎn)單，只要將編號(hào)為1的圓盤從塔座X直接移動(dòng)到塔座Z上即可；當(dāng)n>1時(shí)，需利用塔座Y作輔助塔座，若能設(shè)法將壓在編號(hào)為n的圓盤上的n-1個(gè)圓盤從塔座X(依照上述原則)移至塔座Y上，則可先將編號(hào)為n的圓盤從塔座X移至塔座Z上，然后再將塔座Y上的n-1個(gè)圓盤(依照上述原則)移至塔座Z上。而如何將n-1個(gè)圓盤從一個(gè)塔座移至另一個(gè)塔座問(wèn)題是一個(gè)和原問(wèn)題具有相同特征屬性的問(wèn)題，只是問(wèn)題的規(guī)模小個(gè)1，因此可以用同樣方法求解。由此可得如下算法所示的求解n階Hanoi塔問(wèn)題的函數(shù)。如何實(shí)現(xiàn)移動(dòng)圓盤的操作呢？當(dāng)n=1時(shí)，問(wèn)題比較45voidhanoi(intn,charx,chary,charz)/*將塔座X上按直徑由小到大且至上而下編號(hào)為1至n的n個(gè)圓盤按規(guī)則搬到塔座Z上，Y可用作輔助塔座*/1{2if(n==1)3move(x,1,z);/*將編號(hào)為1的圓盤從X移動(dòng)Z*/4else{5hanoi(n-1,x,z,y);/*將X上編號(hào)為1至n-1的圓盤移到Y(jié),Z作輔助塔*/6move(x,n,z);/*將編號(hào)為n的圓盤從X移到Z*/7hanoi(n-1,y,x,z);/*將Y上編號(hào)為1至n-1的圓盤移動(dòng)到Z，X作輔助塔*/8}9}voidhanoi(intn,charx,chary46

下面給出三個(gè)盤子搬動(dòng)時(shí)hanoi(3,A,B,C)遞歸調(diào)用過(guò)程，如圖3.8所示。hanoi(2,A,C,B):hanoi(1,A,B,C)move(A->C)1號(hào)搬到Cmove(A->B) 2號(hào)搬到Bhanoi(1,C,A,B)move(C->B)1號(hào)搬到Bmove(A->C) 3號(hào)搬到Chanoi(2,B,A,C):hanoi(1,B,C,A)move(B->A) 1號(hào)搬到Amove(B->C)2號(hào)搬到Chanoi(1,A,B,C)move(A->C) 1號(hào)搬到C下面給出三個(gè)盤子搬動(dòng)時(shí)hanoi(3,A,47圖3.8Hanoi塔的遞歸函數(shù)運(yùn)行示意圖圖3.8Hanoi塔的遞歸函數(shù)運(yùn)行示意圖483)遞歸問(wèn)題的優(yōu)點(diǎn)通過(guò)上面的例子可看出，遞歸既是強(qiáng)有力的數(shù)學(xué)方法，也是程序設(shè)計(jì)中一個(gè)很有用的工具。其特點(diǎn)是對(duì)遞歸問(wèn)題描述簡(jiǎn)捷，結(jié)構(gòu)清晰，程序的正確性容易證明。

4)遞歸算法求解問(wèn)題的要素遞歸算法就是算法中有直接或間接調(diào)用算法本身的算法。遞歸算法的要點(diǎn)如下：

(1)問(wèn)題具有類同自身的子問(wèn)題的性質(zhì)，被定義項(xiàng)在定義中的應(yīng)用具有更小的尺度。

(2)被定義項(xiàng)在最小尺度上有直接解。3)遞歸問(wèn)題的優(yōu)點(diǎn)49

設(shè)計(jì)遞歸算法的方法是：

(1)尋找方法，將問(wèn)題化為原問(wèn)題的子問(wèn)題求解（例n!=n*(n-1)!）。

(2)設(shè)計(jì)遞歸出口，確定遞歸終止條件(例求解n!時(shí)，當(dāng)n=1時(shí)，n!=1)。設(shè)計(jì)遞歸算法的方法是：50

2.遞歸算法到非遞歸算法轉(zhuǎn)換遞歸算法具有兩個(gè)特性：

(1)遞歸算法是一種分而治之、把復(fù)雜問(wèn)題分解為簡(jiǎn)單問(wèn)題的求解問(wèn)題方法，對(duì)求解某些復(fù)雜問(wèn)題，遞歸算法的分析方法是有效的。（2）遞歸算法的時(shí)間效率低。2.遞歸算法到非遞歸算法轉(zhuǎn)換511)消除遞歸的原因其一：有利于提高算法時(shí)空性能，因?yàn)檫f歸執(zhí)行時(shí)需要系統(tǒng)提供隱式棧實(shí)現(xiàn)遞歸，效率低且費(fèi)時(shí)。其二：無(wú)應(yīng)用遞歸語(yǔ)句的語(yǔ)言設(shè)施環(huán)境條件，有些計(jì)算機(jī)語(yǔ)言不支持遞歸功能，如FORTRAN語(yǔ)言中無(wú)遞歸機(jī)制。其三：遞歸算法是一次執(zhí)行完，這在處理有些問(wèn)題時(shí)不合適，也存在一個(gè)把遞歸算法轉(zhuǎn)化為非遞歸算法的需求。1)消除遞歸的原因522)簡(jiǎn)單遞歸（尾遞歸和單向遞歸）消除在簡(jiǎn)單情況下，將遞歸算法可簡(jiǎn)化為線性序列執(zhí)行，可直接轉(zhuǎn)換為循環(huán)實(shí)現(xiàn)。遞歸進(jìn)層三件事：保存本層參數(shù)、返回地址;

傳遞參數(shù)，分配局部數(shù)據(jù)空間;

控制轉(zhuǎn)移。遞歸退層三件事：恢復(fù)上層； 傳遞結(jié)果； 轉(zhuǎn)斷點(diǎn)執(zhí)行。2)簡(jiǎn)單遞歸（尾遞歸和單向遞歸）消除遞53

尾遞歸是指遞歸調(diào)用語(yǔ)句只有一個(gè)，而且是處于算法的最后。我們以階乘問(wèn)題的遞歸算法Fact(n)為例討論尾遞歸算法的運(yùn)行過(guò)程。為討論方便，我們列出階乘問(wèn)題的遞歸算法Fact(n)，并簡(jiǎn)化掉參數(shù)n的出錯(cuò)檢查語(yǔ)句，改寫遞歸調(diào)用語(yǔ)句的位置在最后，算法如下：longFact(intn){if(n==0)return1;returnn*Fact(n-1);}尾遞歸是指遞歸調(diào)用語(yǔ)句只有一個(gè)，而且是處于54圖3.9遞歸調(diào)用變化情況示意圖3.9遞歸調(diào)用變化情況示意55圖3.10f(3)遞歸調(diào)用流程變化示意圖3.10f(3)遞歸調(diào)用流程變化示意56

由圖3.10可看出，整個(gè)計(jì)算包括自上而下遞歸調(diào)用進(jìn)層和自下而上遞歸返回退層兩個(gè)階段，所有遞歸調(diào)用直接或間接依賴f(0)，所以整個(gè)階段分兩步，計(jì)算順序在第二階段，先計(jì)算f(0)→f(1)→…→f(n)，工作變量y記錄中間結(jié)果。由圖3.10可看出，整個(gè)計(jì)算包括自上而下遞歸57循環(huán)結(jié)構(gòu)的階乘問(wèn)題算法Fact(n)如下：longFact(intn){intfac=1;for(inti=1;i<=n;i++)/*依次計(jì)算f(1)，…，f(n)*/fac=fac*i;/*f(i)=f(i)*i*/returnfac;}循環(huán)結(jié)構(gòu)的階乘問(wèn)題算法Fact(n)如下：longFac58

單向遞歸的一個(gè)典型例子是我們討論過(guò)的計(jì)算斐波那契數(shù)列的算法Fib(n)。其中，遞歸調(diào)用語(yǔ)句Fib(n-1)和Fib(n-2)只與主調(diào)用函數(shù)Fib(n)有關(guān)，相互之間參數(shù)無(wú)關(guān)，并且這些遞歸調(diào)用語(yǔ)句也和尾遞歸一樣處于算法的最后。例：斐波那契數(shù)列單向遞歸的一個(gè)典型例子是我們討論過(guò)的計(jì)算斐波那59斐波那契數(shù)列的遞歸算法Fib(n)如下，F(xiàn)ib(intn){if（n==0||n==1）returnn;/*遞歸出口*/elsereturnFib(n-1)+Fib(n-2);/*遞歸調(diào)用*/}斐波那契數(shù)列的遞歸算法Fib(n)如下，F(xiàn)ib(int60圖3.11Fib(5)遞歸調(diào)用過(guò)程示意圖3.11Fib(5)遞歸調(diào)用過(guò)程示意61圖3.12Fib(5)循環(huán)調(diào)用過(guò)程示意圖圖3.12Fib(5)循環(huán)調(diào)用過(guò)程示意圖62intFib(intn){intx,y,z;if（n==0||n==1）returnn;/*計(jì)算Fib(0),Fib(1)*/else{intx=0,y=1,z;/*x=Fib(0),y=Fib(1)*/for(i=2;i<=n;i++){z=y;/*z=Fib(i-1)*/y=x+y;/*y=Fib(i-1)+Fib(i-2)，求Fib(i)，形成第i項(xiàng)*/x=z;/*x=Fib(i-1)*/}}returny;}intFib(intn)633.4隊(duì)列3.4.1隊(duì)列的定義隊(duì)列

(Queue)是另一種限定性的線性表，它只允許在表的一端插入元素，而在另一端刪除元素，所以隊(duì)列具有先進(jìn)先出(FistInFistOut，縮寫為FIFO)的特性。在隊(duì)列中，允許插入的一端叫做隊(duì)尾(rear)，允許刪除的一端則稱為隊(duì)頭(front)。假設(shè)隊(duì)列為q=(a1，a2，…，an)，那么a1就是隊(duì)頭元素，an則是隊(duì)尾元素。隊(duì)列中的元素是按照a1、a2、…、an的順序進(jìn)入的，退出隊(duì)列也必須按照同樣的次序依次出隊(duì)，也就是說(shuō)，只有在a1、a2、…、an-1都離開(kāi)隊(duì)列之后，an才能退出隊(duì)列。3.4隊(duì)列3.4.1隊(duì)列的定義64

數(shù)據(jù)元素：可以是任意類型的數(shù)據(jù)，但必須屬于同一個(gè)數(shù)據(jù)對(duì)象。

關(guān)系：隊(duì)列中數(shù)據(jù)元素之間是線性關(guān)系?；静僮鳎海?）InitQueue(&Q)：初始化操作。設(shè)置一個(gè)空隊(duì)列。（2）QueueEmpty(Q)：判空操作。若隊(duì)列為空，則返回TRUE，否則返回FALSE。（3）EnQueue(&Q，e)：進(jìn)隊(duì)操作。在隊(duì)列Q的隊(duì)尾插入e。數(shù)據(jù)元素：可以是任意類型的數(shù)據(jù)，但必須屬于同65

（4）DeQueue(&Q,&e)：出隊(duì)操作。使隊(duì)列Q的隊(duì)頭元素出隊(duì)，并用e帶回其值。（5）ClearQueue(&Q)：隊(duì)列置空操作。將隊(duì)列Q置為空隊(duì)列。（6）DestroyQueue(&Q)：隊(duì)列銷毀操作。釋放隊(duì)列的空間。（4）DeQueue(&Q,&e)：出隊(duì)操作。使663.4.2隊(duì)列的表示和實(shí)現(xiàn)1.鏈隊(duì)列圖3.13鏈隊(duì)列3.4.2隊(duì)列的表示和實(shí)現(xiàn)1.鏈隊(duì)列圖3.13鏈67鏈隊(duì)列可以定義如下：＃defineTRUE1＃defineFALSE0typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;鏈隊(duì)列可以定義如下：＃defineTRUE168（1）初始化操作StatusInitQueue(LinkQueue&Q){Q.front=Q.rear=(Queueptr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;returnOK;}（1）初始化操作69（2）銷毀隊(duì)列StatusDestroyQueue(LinkQueue&Q){while(Q.front){ Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear;}returnOK;}（2）銷毀隊(duì)列70（3）入隊(duì)操作StatusEnQueue(LinkQueue&Q,QelemTypee){p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}（3）入隊(duì)操作71（4）出隊(duì)操作StatusDeQueue(LinkQueue&Q,QelemType&e){if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}（4）出隊(duì)操作722.循環(huán)隊(duì)列圖3.14隊(duì)列的基本操作2.循環(huán)隊(duì)列圖3.14隊(duì)列的基本操作73圖3.15循環(huán)隊(duì)列圖3.15循環(huán)隊(duì)列74如何區(qū)分隊(duì)列“空”和“滿”另設(shè)一個(gè)標(biāo)志位以區(qū)分隊(duì)列是空還是滿；少用一個(gè)元素空間，當(dāng)隊(duì)列頭指針在隊(duì)列尾指針的下一個(gè)位置上時(shí)為“滿”。當(dāng)Q.front=Q.rear時(shí)隊(duì)空；Q.rear+1=Q.front時(shí)隊(duì)滿循環(huán)隊(duì)列滿足條件

(Q.rear+1)%MAXQSIZE==Q.front隊(duì)滿

如何區(qū)分隊(duì)列“空”和“滿”75循環(huán)隊(duì)列的類型定義：#defineMAXQSIZE100/*隊(duì)列的最大長(zhǎng)度*/typedefstruct{QElemType*base;/*隊(duì)列的元素空間*/intfront;/*頭指針指示器*

intrear; /*尾指針指示器*/}SqQueue;

循環(huán)隊(duì)列的類型定義：76（1）初始化操作StatusInitQueue(SqQueue&Q){Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;returnOK;}（1）初始化操作77（2）入隊(duì)操作StatusEnQueue(SqQueue&Q,QElemTypee){if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}（2）入隊(duì)操作78（3）出隊(duì)操作

StatusDeQueue(SqQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}（3）出隊(duì)操作79(4)求隊(duì)列長(zhǎng)度intQueueLength(SqQueueQ){return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;}(4)求隊(duì)列長(zhǎng)度80（1）設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)閍,b,c。問(wèn)經(jīng)過(guò)棧操作后可以得到哪些輸出序列？（2）設(shè)有一個(gè)循環(huán)隊(duì)列S，空間大小為MAX，隊(duì)頭和隊(duì)尾的指針?lè)謩e為front和rear，隊(duì)列為空的條件是什么？隊(duì)列為滿的條件是什么？插入一個(gè)元素，指針的變化是什么?刪除一個(gè)元素指針的變化是什么?（1）設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)閍,b,c。問(wèn)經(jīng)過(guò)棧操81（3）設(shè)Q是一個(gè)初始分配空間為7的順序隊(duì)列，初始狀態(tài)為front=rear=0，請(qǐng)畫出做完下列操作后隊(duì)列的頭尾，指針的狀態(tài)變化情況，若不能入隊(duì)，請(qǐng)指出其元素，并說(shuō)明理由。a,b,c,d入隊(duì)a,b,c出隊(duì)i,j,k,l,m入隊(duì)d,i出隊(duì)n,o,p,q,r入隊(duì)（3）設(shè)Q是一個(gè)初始分配空間為7的順序隊(duì)列，初始狀態(tài)為fro82（4）假設(shè)Q初始分配空間為6的循環(huán)隊(duì)列，初始狀態(tài)為front=rear=0，請(qǐng)畫出做完下列操作后隊(duì)列的頭尾，指針的狀態(tài)變化情況，若不能入對(duì)，請(qǐng)指出其元素，并說(shuō)明理由。d,e,b,g,h入隊(duì)d,e出隊(duì)i,j,k,l,m入隊(duì)出隊(duì)n,o,p,q,r入隊(duì)b（4）假設(shè)Q初始分配空間為6的循環(huán)隊(duì)列，初始狀態(tài)為front83回憶：什么是數(shù)據(jù)結(jié)構(gòu)？答：數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。什么是數(shù)據(jù)？答：對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中，并被計(jì)算機(jī)處理的符號(hào)的總稱。什么是數(shù)據(jù)元素：答：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。回憶：84回憶：基本的數(shù)據(jù)邏輯結(jié)構(gòu)都有哪幾種？答：集合，線性結(jié)構(gòu)，樹(shù)形結(jié)構(gòu)、網(wǎng)狀結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)分為哪幾種？答：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。算法的5個(gè)特性是什么？答：有窮性、確定性、可行性、輸入和輸出。算法設(shè)計(jì)的要求？

答：正確性、可讀性、健壯性、效率與低存儲(chǔ)量需求?；貞洠?5為什么順序表的插入和刪除操作必須移動(dòng)元素？平均需要移動(dòng)多少個(gè)元素？

答：線性表的順序存儲(chǔ)是用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素，元素在內(nèi)存的物理存儲(chǔ)次序與它們?cè)诰€性表中的邏輯次序相同，順序表中插入時(shí)，該位置后面的元素都向后移動(dòng)一位，不然無(wú)法實(shí)現(xiàn)插入功能。順序表中刪除時(shí)，該位置后面的元素都向前移動(dòng)一位，從而刪除一個(gè)元素。

平均需要移動(dòng)一半的元素。棧和隊(duì)列相對(duì)于線性表有什么特點(diǎn)：為什么順序表的插入和刪除操作必須移動(dòng)元素？平均需要移動(dòng)多少個(gè)86棧和隊(duì)列相對(duì)于線性表有什么特點(diǎn)：答：棧具有后進(jìn)先出的特點(diǎn)，只能在棧頂進(jìn)行插入和刪除操作。隊(duì)列具有先進(jìn)先出的特點(diǎn)，只能在隊(duì)頭刪除元素，在隊(duì)尾插入元素。判斷棧S和隊(duì)列L為空的條件是什么：答：S.top==S.base。L.front==L.rear。循環(huán)隊(duì)列L為滿的條件是什么？答：(Q.rear+1)%MAXQSIZE==Q.front棧和隊(duì)列相對(duì)于線性表有什么特點(diǎn)：87第3章限定性線性表—棧和隊(duì)列3.1棧3.2棧的應(yīng)用舉例3.3棧與遞歸的實(shí)現(xiàn)3.4隊(duì)列第3章限定性線性表—棧和隊(duì)列3.1棧883.1棧3.1.1棧的定義棧作為一種限定性線性表，是將線性表的插入和刪除運(yùn)算限制為僅在表尾進(jìn)行，通常將表中允許進(jìn)行插入、刪除操作的一端稱為棧頂(Top)，因此棧頂?shù)漠?dāng)前位置是動(dòng)態(tài)變化的，它由一個(gè)稱為棧頂指針的位置指示器指示。同時(shí)表的另一端被稱為棧底(Bottom)。當(dāng)棧中沒(méi)有元素時(shí)稱為空棧。棧的插入操作被形象地稱為進(jìn)?；蛉霔?，刪除操作稱為出?；蛲藯?。

3.1棧3.1.1棧的定義89設(shè)S=(a1,a2,…,an)表示棧，則a1為棧底元素，an

為棧頂元素。棧是一種后進(jìn)先出（LastInFirstOut）的線性表（簡(jiǎn)稱LIFO結(jié)構(gòu)）。圖3.1棧設(shè)S=(a1,a2,…,an)表示棧，則a1為棧底元素，an90棧只能對(duì)棧頂元素進(jìn)行插入和刪除操作。例：若輸入A，B，C，D，同時(shí)在插入的時(shí)候也可能進(jìn)行刪除操作。可能的輸出序列為：B，A，C，D;

C、D、A、B；D，A，C，B；C、A、D、B；D，C，A，B；C、B、D、A；B，C，A，D；A，C，B，D；棧只能對(duì)棧頂元素進(jìn)行插入和刪除操作。91ADTStack{

數(shù)據(jù)元素：可以是任意類型的數(shù)據(jù)，但必須屬于同一個(gè)數(shù)據(jù)對(duì)象。數(shù)據(jù)關(guān)系：棧中數(shù)據(jù)元素之間是線性關(guān)系?；静僮鳎海?）InitStack(&S)

初始條件：S為未初始化的棧。操作結(jié)果：將S初始化為空棧。（2）ClearStack(&S)

初始條件：棧S已經(jīng)存在。操作結(jié)果：將棧S置成空棧。ADTStack{92

（3）StackEmpty(S)

初始條件：棧S已經(jīng)存在。操作結(jié)果：若S為空棧，則函數(shù)值為TRUE，否則FALSE

（4）Push(&S,e)

初始條件：棧S已經(jīng)存在。操作結(jié)果：在S的頂部插入(亦稱壓入)元素e；（3）StackEmpty(S)93

（5）Pop(&S,&e)

初始條件：棧S已經(jīng)存在。操作結(jié)果：刪除(亦稱彈出)棧S的頂部元素，并用e帶回該值。（6）GetTop(S,&e)

初始條件：棧S已經(jīng)存在。操作結(jié)果：取棧S的頂部元素。與Pop(&S,e)不同之處在于GetTop(S,&e)不改變棧頂?shù)奈恢谩＃?）Pop(&S,&e)943.1.2棧的表示和實(shí)現(xiàn)1.順序棧順序棧是用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧，即利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)由于棧的操作的特殊性，還必須附設(shè)一個(gè)位置指針top（棧頂指針）來(lái)動(dòng)態(tài)地指示棧頂元素在順序棧中的位置。通常以top=0表示空棧。順序棧的存儲(chǔ)結(jié)構(gòu)可以用C語(yǔ)言中的一維數(shù)組來(lái)表示。棧的順序存儲(chǔ)結(jié)構(gòu)定義如下：3.1.2棧的表示和實(shí)現(xiàn)1.順序棧95＃defineTRUE1＃defineFALSE0typedefstruct{SElemType*base;SElemType*top;intstacksize;//?？墒褂玫淖畲笕萘縸SqStack;

按初始分配量進(jìn)行第一次存儲(chǔ)分配，base為棧底指針，始終指向棧底。top為棧頂指針，初值指向棧底，每插入一個(gè)元素，top增1；每刪除一個(gè)元素，top減1，top始終在棧頂元素的下一個(gè)位置上。

＃defineTRUE196圖3.2順序棧中的進(jìn)棧和出棧43210432104321043210圖3.2順序棧中的進(jìn)棧和出棧444497順序?；静僮鞯膶?shí)現(xiàn)如下:(1)初始化。StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}順序?；静僮鞯膶?shí)現(xiàn)如下:StatusInitStac98(2)取棧頂元素StatusGetTop(SqStackS,SElemType&e){if(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}(2)取棧頂元素99(3)入棧。StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}(3)入棧。100(4)出棧StatusPop(SqStack&S,SelemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}(4)出棧1012.鏈棧圖3.4鏈棧示意圖鏈?zhǔn)綏o(wú)棧滿問(wèn)題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^適合于多棧操作2.鏈棧圖3.4鏈棧示意圖鏈?zhǔn)綏o(wú)棧滿問(wèn)題，空間可1022.鏈棧

圖3.4鏈棧示意圖棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)際上就是一個(gè)單鏈表，叫做鏈棧。插入和刪除操作只能在鏈棧的棧頂進(jìn)行。

棧頂指針Top應(yīng)該在鏈表的哪一頭？

鏈?zhǔn)綏５臈ｍ斣阪滎^插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏o(wú)棧滿問(wèn)題，空間可擴(kuò)充適合于多棧操作2.鏈棧圖3.4鏈棧示意圖棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1032.鏈棧/*

鏈棧結(jié)構(gòu)

*/

typedef

struct

StackNode

{

SElemType

data;

//節(jié)點(diǎn)數(shù)據(jù)域

struct

StackNode

*next;//節(jié)點(diǎn)指針域

}StackNode,*LinkStackPtr;

//節(jié)點(diǎn)指針

typedef

struct

LinkStack

{

LinkStackPtr

top;

//棧頂指針

int

count;

//棧中元素個(gè)數(shù)}LinkStack;

2.鏈棧/*

鏈棧結(jié)構(gòu)

*/

1042.鏈棧//棧的初始化操作Status

InitStack(LinkStack

*S)

{

S->top

=

(LinkStackPtr)malloc(sizeof(StackNode));

if(!S->top)

return

ERROR;

S->top

=

NULL;

S->count

=

0;

return

OK;

}

2.鏈棧//棧的初始化操作1052.鏈棧/*

把S置為空棧

*/

Status

ClearStack(LinkStack

*S)

{

LinkStackPtr

p,q;

p

=

S->top;

while(p)

{

q

=

p;

p

=

p->next;

free(q);

}

S->count=0;

return

OK;

}

2.鏈棧/*

把S置為空棧

*/

1062.鏈棧/*

若棧S為空棧，則返回TRUE，否則返回FALSE

*/

Status

IsEmptyStack(LinkStack

S)

{

if

(S.count

==

0)

{

return

TRUE;

}

else

{

return

FALSE;

}

}

2.鏈棧/*

若棧S為空棧，則返回TRUE，否則返回FA1072.鏈棧/*

若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR

*/

Status

GetTopElem(LinkStack

S,SElemType

*e)

{

if

(S.top

==

NULL)

{

return

ERROR;

}

else

{

*e

=

S.top->data;

}

return

OK;

}

2.鏈棧/*

若棧不空，則用e返回S的棧頂元素，并返回O1082.鏈棧Status

Push(LinkStack

*S,SElemType

e)

{

LinkStackPtr

s=(LinkStackPtr)malloc(sizeof(StackNode));

if

(!s)

{

return

ERROR;

}

s->data

=

e;

s->next

=

S->top

S->top

=

s;

S->count++;

return

OK;

}

2.鏈棧Status

Push(LinkStack

*S1092.鏈棧/*

若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR

*/

Status

Pop(LinkStack

*S,SElemType

*e)

{

LinkStackPtr

p;

if(IsEmptyStack(*S))

{

return

ERROR;

}

*e

=

S->top->data;

p

=

S->top;

S->top

=

S->top->next

free(p);

S->count--;

return

OK;

}

2.鏈棧/*

若棧不空，則刪除S的棧頂元素，用e返回其值1103.2棧的應(yīng)用舉例1.數(shù)制轉(zhuǎn)換假設(shè)要將十進(jìn)制數(shù)N轉(zhuǎn)換為d進(jìn)制數(shù)，一個(gè)簡(jiǎn)單的轉(zhuǎn)換算法是重復(fù)下述兩步，直到N等于零：X=Nmodd(其中mod為求余運(yùn)算)N=Ndivd(其中div為整除運(yùn)算)3.2棧的應(yīng)用舉例1.數(shù)制轉(zhuǎn)換111如(1348)10=(2504)8

NN/8N%8134816841682102125202如(1348)10=(2504)8NN/8N%81112voidconversion(){ InitStack(S); scanf(“%d”,&N); while(N) { Push(s,N%8); N=N/8; } while(!StackEmpty(s)){ Pop(S,e); printf(“%d”,e); }}voidconversion()1132.括號(hào)匹配問(wèn)題假設(shè)表達(dá)式中包含三種括號(hào)：圓括號(hào)、方括號(hào)和花括號(hào)，它們可互相嵌套，如([{}]([]))或({([][()])})等均為正確的格式，而{[]})}或{[()]或([]}均為不正確的格式。在檢驗(yàn)算法中可設(shè)置一個(gè)空棧。讀入字符直到文件尾。如果字符是一個(gè)左括號(hào)，則直接入棧。如果字符是一個(gè)右括號(hào)，那么若棧為空，則報(bào)錯(cuò)；若棧不為空，則將棧頂元素出棧。如果出棧的符號(hào)不是對(duì)應(yīng)的左括號(hào)，則報(bào)錯(cuò)。在文件尾，如果棧非空則報(bào)錯(cuò)。2.括號(hào)匹配問(wèn)題1143.表達(dá)式求值

表達(dá)式求值是高級(jí)語(yǔ)言編譯中的一個(gè)基本問(wèn)題，是棧的典型應(yīng)用實(shí)例。任何一個(gè)表達(dá)式都是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成的。操作數(shù)既可以是常數(shù)，也可以是被說(shuō)明為變量或常量的標(biāo)識(shí)符；運(yùn)算符可以分為算術(shù)運(yùn)算符、關(guān)系運(yùn)算符和邏輯運(yùn)算符三類；基本界限符有左右括號(hào)和表達(dá)式結(jié)束符等。3.表達(dá)式求值表達(dá)式求值是高級(jí)語(yǔ)言編譯中的115[例]算術(shù)表達(dá)式5+6/2-3*4。正確理解：

5+6/2-3*4=5+3-3*4=8-3*4=8-12=-4由兩類對(duì)象構(gòu)成的：（1）操作數(shù)，如2、3、4（2）運(yùn)算符號(hào)，如+、-、*、/不同運(yùn)算符號(hào)優(yōu)先級(jí)不一樣[例]算術(shù)表達(dá)式5+6/2-3*4。正確理解：116后綴表達(dá)式

中綴表達(dá)式：運(yùn)算符號(hào)位于兩個(gè)運(yùn)算數(shù)之間。如a+b*

c-

d/

e后綴表達(dá)式：運(yùn)算符號(hào)位于兩個(gè)運(yùn)算數(shù)之后。如abc*+

de/-〖例〗62/

3-

42*+

=?

后綴表達(dá)式求值策略：從左向右“掃描”，逐個(gè)處理運(yùn)算數(shù)和運(yùn)算符號(hào)。1.遇到運(yùn)算數(shù)怎么辦？如何“記住”目前還不未參與運(yùn)算的數(shù)？2.遇到運(yùn)算符號(hào)怎么辦？對(duì)應(yīng)的運(yùn)算數(shù)是什么？啟示：需要有種存儲(chǔ)方法，能順序存儲(chǔ)運(yùn)算數(shù)，并在需要時(shí)“倒序”輸出！后綴表達(dá)式中綴表達(dá)式：運(yùn)算符號(hào)位于兩個(gè)運(yùn)算數(shù)之間。如a117對(duì)象:6(運(yùn)算數(shù))〖例〗62/

3-

42*+

=?

對(duì)象:2(運(yùn)算數(shù))對(duì)象:/

(運(yùn)算符)對(duì)象:3(運(yùn)算數(shù))

對(duì)象:-

(運(yùn)算符)

對(duì)象:4(運(yùn)算數(shù))

對(duì)象:2(運(yùn)算數(shù))

對(duì)象:*

(運(yùn)算符)對(duì)象:+

(運(yùn)算符)

Pop:8top62toptop2

6

/=33333-=0042top24*=8880+=88T(N)=O(N)8對(duì)象:6(運(yùn)算數(shù))〖例〗62/3-42118中綴表達(dá)式求值

基本策略：將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，然后求值

如何將中綴表達(dá)式轉(zhuǎn)換為后綴？觀察一個(gè)簡(jiǎn)單例子：3+4*5-6345*+6–1.運(yùn)算數(shù)相對(duì)順序不變2.運(yùn)算符號(hào)順序發(fā)生改變需要存儲(chǔ)“等待中”的運(yùn)算符號(hào)要將當(dāng)前運(yùn)算符號(hào)與“等待中”的最后一個(gè)運(yùn)算符號(hào)比較有括號(hào)怎么辦？棧中綴表達(dá)式求值有括號(hào)怎么辦？棧119〖例〗3*

(4+5

)/

6

=?345+*6/top輸出:3輸入對(duì)象:3(操作數(shù))

輸入對(duì)象:*

(乘法)輸入對(duì)象:((左括號(hào))輸入對(duì)象:4(操作數(shù))輸入對(duì)象:+

(加法)輸入對(duì)象:5(操作數(shù))輸入對(duì)象:)(右括號(hào))輸入對(duì)象:/

(除法)輸入對(duì)象:6(操作數(shù))(4+5T(N)=O(N)*+*/6/〖例〗3*(4+5)/6=?345120中綴表達(dá)式如何轉(zhuǎn)換為后綴表達(dá)式從頭到尾讀取中綴表達(dá)式的每個(gè)對(duì)象，對(duì)不同對(duì)象按不同的情況處理。①運(yùn)算數(shù)：直接輸出；②左括號(hào)：壓入棧；③右括號(hào)：將棧頂?shù)倪\(yùn)算符彈出并輸出，直到遇到左括號(hào)（出棧，不輸出）；④運(yùn)算符：?若優(yōu)先級(jí)大于棧頂運(yùn)算符時(shí)，則把它壓棧；?若優(yōu)先級(jí)小于等于棧頂運(yùn)算符時(shí)，將棧頂運(yùn)算符彈出并輸出；再比較新的棧頂運(yùn)算符，直到該運(yùn)算符大于棧頂運(yùn)算符優(yōu)先級(jí)為止，然后將該運(yùn)算符壓棧；⑤若各對(duì)象處理完畢，則把棧中存留的運(yùn)算符一并輸出。中綴表達(dá)式如何轉(zhuǎn)換為后綴表達(dá)式從頭到尾讀取中綴表達(dá)式的1211）無(wú)括號(hào)算術(shù)表達(dá)式求值

表達(dá)式計(jì)算程序設(shè)計(jì)語(yǔ)言中都有計(jì)算表達(dá)式的問(wèn)題，這是語(yǔ)言編譯中的典型問(wèn)題。

(1)表達(dá)式形式：由運(yùn)算對(duì)象、運(yùn)算符及必要的表達(dá)式括號(hào)組成；