《數(shù)據(jù)結(jié)構(gòu)用C語言描述》第三章.jsp

棧隊(duì)列遞歸第三章棧和隊(duì)列棧(Stack)·

定義:是限定僅在表尾進(jìn)行插入或刪除操作的線性表?！?/p>

允許插入和刪除的一端稱為棧頂(top)，另一端稱為棧底(bottom)·

特點(diǎn)：后進(jìn)先出(LIFO)a1topbottomna....進(jìn)棧出棧棧的主要操作Push

(S,

x);Pop

(S);Top

(S);Setnull

(S);Empty

(S);//進(jìn)棧//出棧//取棧頂//置空棧//判棧空否StackFull(S);

//判棧滿否}棧的表示和實(shí)現(xiàn)空棧a

進(jìn)棧b

進(jìn)棧aa

b

topbasetopbasebase·

順序棧：棧的順序存儲結(jié)構(gòu)，利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元

素，指針top指向棧頂元素在順序棧中的下一個(gè)位置，base為棧底指針，指向棧底的位置。toptoptopa

b

e

d

ce

進(jìn)棧a

b

e

d

cf

進(jìn)棧溢出a

b

e出棧

d

cbasebasebasetop順序棧的類型表示:#define

maxsize

64typedef

char

datatype;typedef

struct{

//順序棧定義{

datatype data[maxsize]

;//棧頂指針int

top;}

seqstack；seqstack

*s

;·

判?？読nt

Empty

(seqstack

*S){

if(

S->top

>=0

)return

1

//判?？?空則返回1else return

0;//否則返回0}·

判棧滿int

StackFull

(seqstack

*S){return

1

;if(

S->top==maxsize

-1

)//判棧滿,滿則返回1else return

0;//否則返回0}順序棧的基本運(yùn)算:·初始化void

Setnull(seqstack

*S)

//置空棧{S->top

=

-1

;}·

入棧Seqstack

*Push

(seqstack

*S,

datatype

x)//插入元素x為新的棧頂元素return

null{

if

(S->top=

=maxsize

-

1){

printf

(“overflow”)

;}else{ S->top

+

+

;S->data[S->top

]

=

x

;}return

s

;}·

取棧頂元素Datatype

Top

(seqstack

*S

)//若棧空返回0,否則棧頂元素讀到x并返回{

if

(

Empty(S)

){

printf

(“stack

is

empty”)

;return

null;

}elsereturn

(S->data[S->top

]

);}出棧datatype

pop

(seqstack

*S

)//若?？辗祷?,否則棧頂元素退出到x并返回1{

if

(

Empty(S)

){

printf

(“

underflow

”)

;return

null;

}else{

S->top

--;return

(S->data[S->top

+1]

)

;}}鏈?zhǔn)綏?棧的鏈接表示鏈?zhǔn)綏o棧滿問題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^適合于多棧操作top鏈?zhǔn)綏?LinkStack)的定義//結(jié)點(diǎn)//鏈指針typedef

int

datatype;typedef

struct

node{

datatype

data;struct

node

*next;}

linkstack;linkstack

*top;鏈?zhǔn)綏２僮鲗?shí)現(xiàn)入棧Linkstack

*

Push

(

linkstack

*top,datatypex

){

linkstack

*p

;*p

=

malloc(

sizeof

(

linkstack)

);p->data

=

x;p->next

=

top;return

p;}·

出棧Linklist

*Pop

(

LinkStack

*S,

datatype

&x

){

linkstack

*p

;if

(

top

=

=

null

){printf

(“underflow”)

;

return

null;else{

p

=

top

;x

=

p->data;top

=

top

->next

;free

(p);return

top;}}棧的應(yīng)用舉例數(shù)制轉(zhuǎn)換行編輯程序迷宮求解表達(dá)式求值數(shù)制轉(zhuǎn)換N

=

(N

div

d)×d

+

N

mod

d例如：（1348)10

=(2504)8

，其運(yùn)算過程如下：N

N

div

8

N

mod

8134816841682102125202輸出順序計(jì)算順序void

conversion

(){

int

e

,N

;

seqstact

*S

;Setnull(S);scanf

("%d",&N);while

(N){

Push(S,

N

%

8);N

=N/8;}while

(!Empty(S)){

e

=

Pop(S);printf

(

"%d",

e

);

}}

//

conversion行編輯程序在用戶輸入一行的過程中，允許用戶輸入出差錯，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū);并假設(shè)

“#”為退格符，“@”為退行符。假設(shè)從終端接受兩行字符：

whli##ilr#e（s#*s)outcha@putchar(*s=#++);實(shí)際有效行為：

while(*s)putchar(*s++);Seqstack

*s

;Void

LineEdit(){

char

ch

;Setnull(s);

ch=getchar();while(ch!=EOF)

//EOF為全文結(jié)束符{switch

(ch){case

"#"

:

Pop(S);

break;case

"@":

Setnull(S);

break;//

重置S為空棧default

:

Push(S,

ch);

break;}ch=getchar();

//從終端接收下一個(gè)字符}·迷宮求解通常用的是“窮舉求解”的方法·迷宮路徑算法的基本思想

若當(dāng)前位置“可通”，則納入路徑，繼續(xù)前進(jìn);

若當(dāng)前位置“不可通”，則后退，換方向繼續(xù)探索;

若四周“均無通路”，則將當(dāng)前位置從路徑中刪除出去。設(shè)定當(dāng)前位置的初值為入口位置；

do｛若當(dāng)前位置可通，則｛將當(dāng)前位置插入棧頂；若該位置是出口位置，則算法結(jié)束；否則切換當(dāng)前位置的相鄰方塊為新的當(dāng)前位置；｝否則{………..｝｝while(棧不空）；若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當(dāng)前位置為:沿順時(shí)針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則｛刪去棧頂位置；//從路徑中刪去該通道塊若棧不空，則重新測試新的棧頂位置，

直至找到一個(gè)可通的相鄰塊或出棧至?？?｝限于二元運(yùn)算符的表達(dá)式定義:表達(dá)式::=(操作數(shù))+(運(yùn)算符)+(操作數(shù))操作數(shù)::=簡單變量|表達(dá)式簡單變量::=標(biāo)識符|無符號整數(shù)Exp=S1+OP+S2前綴表示法OP

+S1+S2中綴表示法S1+OP

+S2后綴表示法S1+S2+OP表達(dá)式求值例如:

Exp

=

a

b

+

(c

d

/

e)

f前綴式:中綴式:后綴式:+

a

b

c

/

d

e

f

a

b

+

c

d

/

e

f

a

b

c

d

e

/

f

+表達(dá)式標(biāo)識方法ca

b/de-

f+*

*后綴表達(dá)式求值先找運(yùn)算符，再找操作數(shù)例如：a

ba

b c

d

e

/

f

+d/ec-d/e(c-d/e)

f從原表達(dá)式求得后綴式方法設(shè)立暫存運(yùn)算符的棧;

設(shè)表達(dá)式的結(jié)束符為“#”,予設(shè)運(yùn)算符棧的棧底為“#”

若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式;

若當(dāng)前運(yùn)算符的優(yōu)先數(shù)高于棧頂運(yùn)算符，則進(jìn)棧;否則，退出棧頂運(yùn)算符發(fā)送給后綴式;

“(”對它之前后的運(yùn)算符起隔離作用，“)”為自左括弧開始的表達(dá)式的結(jié)束符。隊(duì)列

定義:只允許在表的一端進(jìn)行插入，而在另一端刪除元素的線性表。

在隊(duì)列中，允許插入的一端叫隊(duì)尾（rear），允許刪除的一端稱為對頭(front)。特點(diǎn)：先進(jìn)先出(FIFO)出隊(duì)列 入隊(duì)列a1

，a2，

a3，…，an隊(duì)頭隊(duì)尾鏈隊(duì)列：隊(duì)列的鏈?zhǔn)奖硎?/p>

鏈隊(duì)列中，有兩個(gè)分別指示隊(duì)頭和隊(duì)尾的指針。

鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無隊(duì)滿問題，但有隊(duì)空問題。data

nextfrontreardata

nextfrontrearx

^元素x入隊(duì)x

^y

^元素y入隊(duì)frontrearfrontrea

rfrontrearx

^y

^元素x出隊(duì)frontrear^^ 空隊(duì)列frontrearNULL空隊(duì)列鏈?zhǔn)疥?duì)列的定義typedef

int

datatype;typedef

struct

node{//隊(duì)列結(jié)點(diǎn)數(shù)據(jù)//結(jié)點(diǎn)鏈指針datatype

data;struct

node

*next;}

linklist;typedef

struct

{linklist

*rear,

*front;}

linkqueue;linkqueue

*q

;鏈隊(duì)列的主要操作·

初始化setnull

(

Linkqueue

*q){q->front

=

malloc(sizeof(linklist));q->rear

=

q->front

;

}·

隊(duì)空int

Empty

(

Linkqueue

*q

){

if

(q->front

==

q->rear)return

(true);else

return

(false)

;

}·

取隊(duì)頭元素int

*Front

(

Linkqueue

*q

){

if

(

Empty

(q)

) return

0;return

(q->front->next->data);}·

入隊(duì)int

Enqueue

(

Linkqueue

*q,

datatype

x

){linklist

*p

=

malloc(

sizeof

(

linklist

)

);p->data

=

x;

p->next

=

NULL;if

(

q->front

==

NULL

)//空,創(chuàng)建第一個(gè)結(jié)點(diǎn)q->front

=

q->rear

=

p;else

q->rear->next=p;//入隊(duì)q->rear

=p;return

1;}·

出隊(duì)datatype

Dequeue

(

Linkqueue

*q)//刪去隊(duì)頭結(jié)點(diǎn)，并返回隊(duì)頭元素的值return

0;//判隊(duì)空{(diào)

if

(

Empty

(q)

)else{

p

=

q->front;//新隊(duì)頭q->front=

q->front->next;free

(p);return

(q->front->data

);}循環(huán)隊(duì)列(Circular

queue)順序隊(duì)列—隊(duì)列的順序存儲表示。用一組地址連續(xù)的存儲單元依次存放從隊(duì)列頭到隊(duì)列尾的元素，指針front和rear分別指示隊(duì)頭元素和隊(duì)尾元素的位置。插入新的隊(duì)尾元素，尾指針增1,rear=rear+1，刪除隊(duì)頭元素，頭指針增1，front=front+1，

因此，在非空隊(duì)列中，頭指針始終指向隊(duì)列頭元素，而尾指針始終指向隊(duì)列尾元素的下一個(gè)位置。隊(duì)滿時(shí)再進(jìn)隊(duì)將溢出

解決辦法：將順序隊(duì)列臆造為一個(gè)環(huán)狀的空間，形成循環(huán)(環(huán)形)隊(duì)列隊(duì)列的進(jìn)隊(duì)和出隊(duì)frontrear

空隊(duì)列rearA,B,C,D進(jìn)隊(duì)A

B

C

DfrontfrontrearA,B出隊(duì)C

DrearC

D

E

F

GfrontE,F,G進(jìn)隊(duì)C

D

E

F

GfrontrearH進(jìn)隊(duì),溢出循環(huán)隊(duì)列(Circular

queue)01453

2循環(huán)隊(duì)列frontrear隊(duì)頭、隊(duì)尾指針加1，可用取模(余數(shù))運(yùn)算實(shí)現(xiàn)。隊(duì)頭指針進(jìn)1:front=(front+1)%maxsize;隊(duì)尾指針進(jìn)1:rear=(rear+1)%maxsize;隊(duì)列初始化：front=rear=0;隊(duì)空條件：front==rear;隊(duì)滿條件：(rear+1)%maxsize==front;6

7 Maxsize-1一般情況C0124567rearfrontEFABD

C3隊(duì)滿G

H空隊(duì)列56

70rearfront567A0front43

21rear4D3CB21C0124567隊(duì)滿(正確)frontrearABGFED

C3#define

maxsize

100Typedef

struct{datatype

data[maxsize];int

front;int

rear;}

Sequeue循環(huán)隊(duì)列的類型定義循環(huán)隊(duì)列操作的實(shí)現(xiàn)//構(gòu)造空隊(duì)列初始化隊(duì)列

Setnull(Sequeue

*q){

q->rear

=

q->front

=

0;}判隊(duì)空int

Empty

(

Seqqueue

*q

)

{return

(q->rear

==

q->front);}判隊(duì)滿int

queueFull

(

Sequeue

*q

){ return

(q->rear+1)

%

maxsize

==q->front);}入隊(duì)int

Enqueue

(

Seqqueue

*q,

queueData

x

)

{if

(

queueFull

(q)

) return

0;else

{

q->data[q->rear]

=

x;q->rear

=

(

q->rear+1)

%

MAXSIZE;return

1;}}出隊(duì)int

Dequeue

(

Seqqueue

*q,

queueData

&x

){

if

(

Empty

(q)

) return

0;else

{x

=

q->data[q->front];q->front

=

(

q->front+1)

%

MAXSIZE;return

1;

}

}取隊(duì)頭int

GetFront

(

Seqqueue

*q,

queueData

&x

){

if

(

queueEmpty

(q)

) return

0;x

=

q->data[(q->front)

%

MAXSIZE];return

1;}隊(duì)列應(yīng)用舉例—打印二項(xiàng)展開式(a+b)i

的系數(shù)楊輝三角形 (Pascal’s

triangle)分析第i行元素與第i+1行元素的關(guān)系目的是從前一行的數(shù)據(jù)可以計(jì)算下一行的數(shù)據(jù)從第i行數(shù)據(jù)計(jì)算并存放第i+1行數(shù)據(jù)//隊(duì)列初始化void

YANGVI

(

int

n

)

{queue

q;q.MakeEmpty

(

);q.Enqueue(1);q.Enqueue(1);//預(yù)放入第一行的兩個(gè)系數(shù)

int

s=0;//逐行處理for

(

int

i=1;

i<=n;

i++

)

{cout

<<

endl;q.Enqueue

(0);for(int

j=1;j<=i+2;j++){//處理第i行的i+2個(gè)系數(shù)int

t=q.Dequeue();//讀取系數(shù)q.Enqueue(s+t);//計(jì)算下一行系數(shù)，并進(jìn)隊(duì)列

s=t;if(j!=i+2)cout<<s<<‘’;//打印一個(gè)系數(shù)，第i+2個(gè)為0}}}遞歸

定義

若一個(gè)對象部分地包含它自己,

或用它自己給自己定義,

則稱這個(gè)對象是遞歸的；若一個(gè)過程直接地或間接地調(diào)用自己,則稱這個(gè)過程是遞歸的過程。三種遞歸情況定義是遞歸的數(shù)據(jù)結(jié)構(gòu)是遞歸的問題的解法是遞歸的定義是遞歸的求解階乘函數(shù)的遞歸算法long

Factorial

(

long

n

){

if

(

n

==

0

)else

returnreturn

1;n

*

Factorial

(n-1);}例1.階乘函數(shù)求解階乘n!的過程主程序main:fact(4)參數(shù)

4

計(jì)算

4*fact(3)

返回

24參數(shù)

3

計(jì)算

3*fact(2)

返回

6參數(shù)

2

計(jì)算

2*fact(1)

返回

2參數(shù)

1

計(jì)算

1*fact(0)

返回

1參數(shù)

0

直接定值=

1

返回

1遞參歸數(shù)調(diào)傳用遞結(jié)回果歸返求回值例2.計(jì)算斐波那契數(shù)列函數(shù)Fib(n)的定義如F0

=0,F1

=1,F2

=1,F3

=2,F4

=3,F5

=5遞歸算法long

Fib

(

long

n

){

if

(

n

<=

1

) return

n;else

return Fib

(n-1)

+

Fib

(n-2);}數(shù)據(jù)結(jié)構(gòu)是遞歸的例如單鏈表結(jié)構(gòu)只有一個(gè)結(jié)點(diǎn)的單鏈表f有若干結(jié)點(diǎn)的單鏈表f例1.搜索鏈表最后一個(gè)結(jié)點(diǎn)并打印其數(shù)值void

Search

(linklist

*f

){

if

(

f

->next

==

NULL

)printf

(“%d\n”,

f

->data

);elseSearch

(

f

->next

);}fffa0遞歸找鏈尾a1

a2

a3

a4f

f例2.在鏈表中尋找等于給定值的結(jié)點(diǎn),并打印其數(shù)值void

Search

(

linklist

*f,

datatype

x){

if

(

f

!=

NULL

)if

(

f

->

data

==

x

)printf

(“%d\n”,

f

->data

);else

Search

(

f

->

next,

x

);}ff遞歸找含x值的結(jié)點(diǎn)xf

f例如，漢諾塔(TowerofHanoi)問題的解法：如果n=1，則將這一個(gè)盤子直接從A柱移到C柱上。否則，執(zhí)行以下三步：①用C柱做過渡，將A柱上的(n-1)個(gè)盤子移到B柱上：②將A柱上最后一個(gè)盤子直接移到C柱上；③用A柱做過渡，將B柱上的(n-1)個(gè)盤子移到C柱上?！栴}的解法是遞歸的·算法void

Hanoi

(int

n,StringA,StringB,StringC)//解決漢諾塔問題的算法{

if

(

n

==

1

)printf

("

move

%s",A,

"

to

%s,C);else{

Hanoi

(

n-1,

A,

C,

B

);printf

("

move

%s",A,

"

to

%s,C);Hanoi

(

n-1,

B,

A,

C

);}}遞歸過程與遞歸工作棧遞歸過程在實(shí)現(xiàn)時(shí)，需要自己調(diào)用自己。層層向下遞歸，退出時(shí)的次序正好相反：遞歸調(diào)用n!

(n-1)!

(n-2)!

1!

0!=1返回次序主程序第一次調(diào)用遞歸過程為外部調(diào)用；遞歸過程每次遞歸調(diào)用自己為內(nèi)部調(diào)用。遞歸工作棧

每一次遞歸調(diào)用時(shí)，需要為過程中使用的參數(shù)、局部變量等另外分配存儲空間。

每層遞歸調(diào)用需分配的空間形成遞歸工作記錄，按后進(jìn)先出的棧組織。局部變量返回地址參

數(shù)活動記錄框架遞歸

工作記錄函數(shù)遞歸時(shí)的活動記錄……………….<下一條指令>Function(<參數(shù)表>)……………….<return>調(diào)用塊函數(shù)塊返回地址(下一條指令)局部變量參數(shù)long

Factorial

(

long

n

)

{int

temp;if

(

n

==

0

)

return

1;else

temp

=

n

*

Factorial

(n-1);RetLoc2return

temp;}void

main

(

)

{int

n;n

=

Factorial

(4);RetLoc1}計(jì)算Fact時(shí)活動記錄的內(nèi)容遞歸調(diào)用序列4

RetLoc1參數(shù)

返回地址

返回時(shí)的指令RetLoc1

return

4*6

//返回243RetLoc2RetLoc2return

3*2//返回62RetLoc2RetLoc2return

2*1//返回21RetLoc2RetLoc2return

1*1//返回10RetLoc2RetLoc2return

1//返回1遞歸過程改為非遞歸過程遞歸過程簡潔、易編、易懂遞歸過程效率低，重復(fù)計(jì)算多改為非遞歸過程的目的是提高效率

單向遞歸和尾遞歸可直接用迭代實(shí)現(xiàn)其非遞歸過程其他情形必須借助棧實(shí)現(xiàn)非遞歸過程計(jì)算斐波那契數(shù)列的函數(shù)Fib(n)的定義如F0

=0,F1

=1,F2

=1,F3

=2,F4

=3,F5

=5求解斐波那契數(shù)列的遞歸算法long

Fib

(

long

n

)

{if

(

n

<=

1

)

return

n;else

return

Fib

(n-1)

+

Fib

(n-2);}·斐波那契數(shù)列的遞歸調(diào)用樹Fib(4)Fib(3)

Fib(2)

Fib(2)

Fib(1)Fib(2)

Fib(1)

Fib(1)Fib(0)

Fib(1)

Fib(0)Fib(1)Fib(0)Fib(3)Fib(5)Fib(2)Fib(1)

Fib(0)Fib(3)Fib(2)

Fib(1)Fib(1)

Fib(0)Fib(4)棧結(jié)點(diǎn)n

tagtag=1,向左遞歸；tag=2,向右遞歸Fib(2)Fib(1)

Fib(0)Fib(3)Fib(2)

Fib(1)Fib(1)

Fib(0)Fib(4)213141n=1sum=0+1223141n=2-23141n=0sum=1+03241n=3-241n=1sum=1+142n=4-2Fib(2)Fib(1)

Fib(0)Fib(3)Fib(2)

Fib(1)Fib(1)

Fib(0)Fib(4)2142n=1sum=2+12242n=2-242n=0sum=3+0long

Fibnacci

(

long

n

)

{Stack<Node>

S;

Node

*w;

long

sum

=

0;//反復(fù)執(zhí)行直到所有終端結(jié)點(diǎn)數(shù)據(jù)累加完do

{while

(

n

>

1

)

{w->n

=

n;

w->tag

=

1;

S.push

(

w

);n--;}//向左遞歸到底,邊走邊進(jìn)棧sum

=

sum

+

n;//執(zhí)行求和while

(

!S.IsEmpty(

)

)

{w

=

S.getTop(

); S.Pop(

);if

(

w->tag

==

1

)

{//改為向右遞歸w->tag

=

2;

S.push

(

w

);//F(n)右側(cè)為F(n-2)n

=

w->n

–

2;break;}}}

while

(

!S.IsEmpty(

)

);return

sum;}·遞歸與回溯n皇后問題在n行n列的國際象棋棋盤上，若兩個(gè)皇后位于同一行、同一列、同一對角線上，則稱為它們?yōu)榛ハ喙?。n皇后問題是指找到這n個(gè)皇后的互不攻擊的布局。1#主對角線3#主對角線5#主對角線0#次對角線2#次對角線4#次對角線6#次對角線1#次對角線3#次對角線5#次對角線0#主對角線2#主對角線4#主對角線6#主對角線0

1

2

30123k

=

i+jk

=

n+i-j-1解題思路

安放第i行皇后時(shí)，需要在列的方向從0到n-1試探(j=0,…,n-1)在第j列安放一個(gè)皇后：如果在列、主對角線、次對角線方向有其它皇后，則出現(xiàn)攻擊，撤消在第j列安放的皇后。如果沒有出現(xiàn)攻擊，在第j列安放的皇后不動，遞歸安放第i+1行皇后。設(shè)置4個(gè)數(shù)組

col[n]：col[i]標(biāo)識第i列是否安放了皇后

md[2n-1]:md[k]標(biāo)識第k條主對角線是否安放了皇后

sd[2n-1]:sd[k]標(biāo)識第k條次對角線是否安放了皇后q[n]:q[i]記錄第i行皇后在第幾列void

queen(

int

i

)

{for(int

j=0;

j<n;

j++){

if(第i行第j列沒有攻擊){在第i行第j列安放皇后；if(i==n-1)輸出一個(gè)布局；else

queen(i+1);撤消第i行第j列的皇后；}}}void

queen(

int

i

)

{for

(

int

j

=

0;

j

<

n;

j++

)

{if

(

!col[j]

&&

!md[n+i-j-1]

&&

!sd[i+j]

){/*第i行第j列沒有攻擊*/col[j]=md[n+i-j-1]=sd[i+j]=1;q[i