數(shù)據(jù)結(jié)構(gòu)萬健版第3章其他線性結(jié)構(gòu)

第3章其它線性結(jié)構(gòu)

棧

隊(duì)列

串

數(shù)組

廣義表

3.1棧

棧（Stack）是只允許在表的同一端進(jìn)行插云梟刪爵*

操作的特殊的線性表。

（退棧、彈

當(dāng)棧中沒有任何元素時(shí)稱為空棧。

3.1棧

由于棧的插入和刪除操作總是在棧頂進(jìn)行，所

以，后進(jìn)去的元素一定先出來。因而，棧又被稱

為后進(jìn)先出(LastInFirstOut)的線性表，簡(jiǎn)稱

LIFO表。

思考：若輸入序列是1,2,3,1,2,3

1,3,2

則可能的輸出序列有233

哪些？2,3,1

3,2,1

3.1棧

棧的抽象數(shù)據(jù)類型定義1A

棧的存儲(chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)歪

棧的應(yīng)用舉例

3.1.1棧的抽象數(shù)據(jù)類型定刈|

ADTStackl：fl

(

數(shù)據(jù)對(duì)象：D={a工|CElemType,1=1,2,...,n,n>Q)

數(shù)據(jù)關(guān)系：RI={〈a—,a/|a±_ir1=2,3,...,n}

基本操作：

Init(&S)

操作結(jié)果：構(gòu)造一個(gè)空的棧S

Destroy(&S)

初始條件：棧S已存在

操作結(jié)果：銷毀棧S

Clear(&S)

初始條件：棧S已存在

操作結(jié)果：將棧S清空

Empty(S)

初始條件：棧S已存在。

操作結(jié)果：若S為空棧，則返回true,否則返回false。

Length(S)

初始條件：棧S已存在。

操作結(jié)果：返回棧S的長(zhǎng)度。

Top(S)

初始條件：棧S已存在，且S非空。

操作結(jié)果：返回棧頂元素的值。

Push(&S,e)

初始條件：棧S已存在，且S未滿。

操作結(jié)果：插入新的元素e到棧頂。

Pop(&S)

初始條件：棧S已存在，月6非空。

操作結(jié)果：刪除棧頂元素。

3.1.2棧的存儲(chǔ)結(jié)構(gòu)及操作久^.

棧是一種操作受限的特殊的線性表。榴彳

表的存儲(chǔ)結(jié)構(gòu)同樣適用于棧，故棧也可以采用順序

存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

順序棧

鏈棧

豕

棧的順序存儲(chǔ)表示一順序一

?棧的順序存儲(chǔ)表示順序棧

用一維數(shù)組來模擬連續(xù)的存儲(chǔ)空間。修0下標(biāo)端設(shè)為棧底,

棧的第1?個(gè)元素存放在"1下標(biāo)位置O

設(shè)置一個(gè)棧頂指針(或稱指示器)top來指示棧頂位置。初

始時(shí)，棧為空，置top=0;入棧時(shí)，top加1;出棧時(shí)，top

減1;當(dāng)棧滿時(shí)，top等于數(shù)組空間大小。因此，top總是指

在棧頂元素的后一個(gè)下標(biāo)位置。

>

top

(b)Z入棧(c)BCDE入棧(d)EQC出棧

順序棧類定義

template<classElemType>II聲明一個(gè)類模板

classSqStack//順序棧類

public:

SqStack(intm);//構(gòu)造函數(shù)

~SqStack();//析構(gòu)函數(shù)

voidClear();//清空棧

boolEmpty()const;//判?？?/p>

intLength()const;//求長(zhǎng)度

ElemType&Top()const;//取棧頂元素

voidPush(constElemType&e);//入棧

voidPop();//出棧

private:

ElemType*m_base;//基地址指針

intm_top;//棧頂指針

intm_size;//向量空間大小

);

順序棧的基本操作的實(shí)現(xiàn),

1.棧初始化

//構(gòu)造函數(shù)，分配m個(gè)結(jié)點(diǎn)的順序空間，構(gòu)造一個(gè)空的順序棧

template<classElemType>

SqStack<ElemType>::SqStack(intm)

(

m_top=0;

m_base=newElemType[m];

msize=m;

mbasemtopmsize

（棧底）（棧頂）一

順序棧的基本操作的實(shí)現(xiàn)J

2.銷毀棧

//析構(gòu)函數(shù)，將棧結(jié)構(gòu)銷毀

template<classElemType>

SqStack<ElemType>::~SqStack()

(

if(m_base!=NULL)delete[]m_base;

)

順序棧的基本操作的實(shí)現(xiàn)J

3.清空棧

//清空棧

template<classElemType>

voidSqStack<ElemType>::Clear()

m_top-0;

}

順序棧的基本操作的實(shí)現(xiàn)J

4.判棧空

//若棧為空，貝U返回true,否貝I」返回false

template<classElemType>

boolSqStack<ElemType>::Empty()const

returnm_top==0;

順序棧的基本操作的實(shí)現(xiàn)J

5.求長(zhǎng)度

//求棧中元素的個(gè)數(shù)

template<classElemType>

intSqStack<ElemType>::Length()const

{

returnm_top;

}

順序棧的基本操作的實(shí)現(xiàn)J

6.取棧頂元素的值

//取棧頂元素的值。先決條件是棧不空

template<classElemType>

ElemType&SqStack<ElemType>::Top()const

{

returnm_base[m_top-1];

)

順序棧的基本操作的實(shí)現(xiàn)I

7.入棧

//入棧，若棧滿，則先擴(kuò)展空間。插入一到棧頂

template<classElemType>

voidSqStack<ElemType>::Push(constElemType&一)

if(m_top>=m_size){//若棧滿，則擴(kuò)展空間

ElemType*newbase;

newbase=newElemType[msize+10];//擴(kuò)大10個(gè)元素空間

for(intj0;j<mtop;j++)//復(fù)制元素到新空間

newbase[j]=m_base[j];

delete[]m_base;//釋放原空間

m_base=newbase;//重置基地址

msize+=10;--------

mbase[mtop++]

mbasemtopmtop

順序棧的基本操作的實(shí)現(xiàn)J

8.出棧

//出棧，彈出棧頂元素。先決條件是棧不空

template<classElemType>

voidSqStack<ElemType>::Pop()

(

aia2an

I

mbasemtopmtop

_______W|

對(duì)于順序棧，應(yīng)注意：

?入棧時(shí)，應(yīng)首先判斷棧是否已滿。若棧滿，則需要

先擴(kuò)展空間。

?出棧和取棧頂元素時(shí)，必須保證棧不空。若?？眨?/p>

則不能進(jìn)行相應(yīng)操作，否則會(huì)導(dǎo)致異常錯(cuò)誤。

在上述順序棧的基本操作中，它們的時(shí)間復(fù)雜度均為

0(1)。

棧的鏈?zhǔn)酱鎯?chǔ)表示—鏈梭

可用不帶頭結(jié)點(diǎn)的單鏈表來表示鏈棧。當(dāng)?？杖找?/p>

top指向棧頂元素結(jié)點(diǎn)；而當(dāng)棧為空時(shí)，top為空指

針。

BCDA

鏈棧類定義

template〈classElemType>

structLinkNode//鏈棧結(jié)點(diǎn)

{

ElemTypedata;

LinkNode<ElemType>*next;

}；

template<classElemType〉/鏈棧類

classLinkstack

(

public:

Linkstack();

~LinkStack();

voidClear();

boolEmpty()const;

intLength()const;

ElemType&Top()const;

voidPush(constElemType

voidPop();

private:

LinkNode<ElemType>*top;

鏈棧的基本操作的實(shí)現(xiàn)

1.棧初始化

//構(gòu)造函數(shù)，構(gòu)造一個(gè)空的鏈棧

template〈classElemType>

Linkstack<ElemType>::Linkstack()

top=NULL;

)

鏈棧的基本操作的實(shí)現(xiàn)

2.銷毀棧

//將棧結(jié)構(gòu)銷毀

template<classElemType>

Linkstack<ElemType>::~Linkstack()

Clear();//成員函數(shù)C1一ar()的功能是釋放鏈棧中的所有結(jié)點(diǎn)

)

鏈棧的基本操作的實(shí)現(xiàn)

3.清空棧

//將棧清空

template<classElemType>

voidLinkstack<ElemType>::Clear()

LinkNode<ElemType>*p;

while(top){//依次釋放鏈表中的所有結(jié)點(diǎn)

p=top;

top=top->next;

deletep;

鏈棧的基本操作的實(shí)現(xiàn)

4.判棧空

//若棧為空，貝|返回tru一，否則返回false

template<classElemType>

boolLinkstack<ElemType>::Empty()const

returntop—NULL;

)

鏈棧的基本操作的實(shí)現(xiàn)

5.求長(zhǎng)度

//返回棧中元素個(gè)數(shù)

template<classElemType>

intLinkStack<ElemType>::Length()const

(

inti=0;

LinkNode<ElemType>*p=top;

while(p){//對(duì)鏈表中的結(jié)點(diǎn)計(jì)數(shù)

i++；

p=p->next;

}

returni;

}/

鏈棧的基本操作的實(shí)現(xiàn)

6.取棧頂元素的值

//取棧頂元素的值。先決條件是棧不空

template<classElemType>

ElemType&Linkstack<ElemType>::Top()const

(

returntop->data;

)

鏈棧的基本操作的實(shí)現(xiàn)

7人棧

//入棧

template<classElemType>

voidLinkstack<ElemType>::Push(constElemType&一)

LinkNode<ElemType>*p;

p=newLinkNode<ElemType>;

p->data=e;

p->next=top;//新結(jié)點(diǎn)插在鏈表的頭部

top=p;

鏈棧的基本操作的實(shí)現(xiàn)

8.出棧

//出棧。先決條件是棧不空

template<classElemType>

voidLinkstack<ElemType>::Pop()

LinkNode<ElemType〉*p=top;//刪除并釋放第'~~個(gè)結(jié)點(diǎn)

top=top->next;

deletep;

鏈棧

在鏈棧中，由于元素的存儲(chǔ)空間是在需要硒;逗?

new運(yùn)算符動(dòng)態(tài)分配的，因此，正常情況下，不會(huì)

出現(xiàn)棧滿的情形，除非內(nèi)存中沒有空閑的存儲(chǔ)空間

可供分配。

在鏈棧的操作中，棧的銷毀、清空、求長(zhǎng)度操作的

時(shí)間復(fù)雜度為因?yàn)樾枰獙?duì)鏈表的每一個(gè)元素

結(jié)點(diǎn)進(jìn)行處理。其余操作的時(shí)間復(fù)雜度為。(1)。

3.1.3棧的應(yīng)用舉例

回文判斷

迷宮問題

表達(dá)式求值

遞歸和漢諾塔問題

3.1.3棧的應(yīng)用舉例

【例3.1】回文判斷

所謂回文，是指一個(gè)字符串的字符序列（不包括空

格）順讀和逆讀是一樣的。

例如："dad'\"munT、"noon"、"wasitacatisaw"

都是回文，而“good"，"soso"則不是。

本例讀入一個(gè)字符串，過濾字符串中的空格，然后

檢查其是否回文。

一可以用棧來處理。對(duì)去掉了空格的串通過兩遍掃描來檢查

其是否回文。第一遍掃描，將每個(gè)字符壓入棧，形成一個(gè)逆

序的串。第二遍掃描，將原串中的每一個(gè)字符與從棧中彈出

的字符作比較，若字符不同，則結(jié)束處理，該串不是回文。

公若直到?？彰恳粚?duì)比較的字符都相同，則該串是回文。

停請(qǐng)見教程P.55

3.L3棧的應(yīng)用舉例迷信

【例3.2】迷宮問題

找出一條從迷宮的入口到出口的通路（如果存在通

路）。

用一個(gè)二維數(shù)組模擬迷宮地圖，如圖（A）所示，。表示可以通

行，1表示墻壁，無法通過。為了方便處理邊界，可以在迷

宮的四周加設(shè)圍墻，如圖（B）所示。

/111111111

ZX

OO1OOOIO11001000101

001000100100100010o

000011011100001101?

0111001011011100101

0001000001000100()00

0100010101010001010

()111100101011110010

110001011111000101

\110000000/111000000

、111111111

圖（A）迷宮地圖

圖（B）加設(shè)圍墻后的迷宮地圖

迷宮問題

在迷宮中行進(jìn)時(shí)必須遵循三個(gè)原則：

1.每一步只走一格；

2.遇到死胡同時(shí)退回一步，看是否有其他的路可以走；

3.走過的路不會(huì)再走第二次。

為此，程序在搜索迷宮出口的過程中不但要記錄走過的路徑，

還必須判斷下一步應(yīng)該往哪個(gè)方向走，可以選擇的方向有4個(gè),

分別為東（右）、南（下）、西（左）、北（上）。

用回溯法來求解迷宮問題：

首先從入口出發(fā)，按東南西北的次序依次向下一步探索，若未

走過且能通過，則前進(jìn)一步進(jìn)入下一位置；否則試探下一個(gè)方

向。若所有的方向均沒有通路，則羽1該點(diǎn)標(biāo)為死胡同并沿原路

圭到前一步，再換下一個(gè)方向繼續(xù)試探。直到找到一條通路,

'dW可走返回到入口。

迷宮問題

在求解過程中，為了能夠退回到前一步以便碰續(xù)向車彳

一個(gè)方向探索前進(jìn)，需要用一個(gè)棧來保存當(dāng)前所走線

路沿途的每一個(gè)位置的坐標(biāo)以及從該位置前進(jìn)的方向，

而棧頂?shù)奈恢帽闶钱?dāng)前的位置。當(dāng)?shù)竭_(dá)出口時(shí)，棧中

從底到頂即為一條由入口到出口的通路。路徑上的每

一步到達(dá)的位置用序號(hào)（從1開始）編排，稱為足跡。

若存在從入口到出口的路徑，則程序以足跡的形式輸

出一'條路徑。

程序請(qǐng)見教程P.57

3.L3棧的應(yīng)用舉例表立,紹

【例3.3】表達(dá)式求值

求一個(gè)表達(dá)式的值是程序設(shè)計(jì)語(yǔ)言編譯程序中的一

個(gè)基本問題，實(shí)現(xiàn)表達(dá)式的求值是棧的一個(gè)典型應(yīng)

用。

在這里，僅討論最基本的算術(shù)四則運(yùn)算：+（加）、

-（減）、*（乘）、/（除），以及為了強(qiáng)調(diào)優(yōu)

先計(jì)算的括號(hào)。

表達(dá)式可定義為（“：：二”為定義符）：

表達(dá)式：：=〈運(yùn)算數(shù)〉〈運(yùn)算符〉〈運(yùn)算數(shù)〉

運(yùn)算數(shù)：：=無符號(hào)整數(shù)|表達(dá)式|（表達(dá)式）

我符：：=+I-I*I/I（I）I=

表達(dá)式求值■I

算術(shù)四則運(yùn)算的規(guī)則為：^登

(1)先乘除、后加減；

(2)同級(jí)運(yùn)算時(shí)先左后右；

(3)先括號(hào)內(nèi)，后括號(hào)外。

算法設(shè)置了兩個(gè)棧：

⑴運(yùn)算數(shù)棧(OPRD)：存放處理表達(dá)式過程中的操作數(shù)。

⑵運(yùn)算符棧(OPTR)：存放處理表達(dá)式過程中的運(yùn)算符。

在此，把一個(gè)運(yùn)算數(shù)或一個(gè)運(yùn)算符均稱為一個(gè)元素。

表達(dá)式求值

假設(shè)表達(dá)式語(yǔ)法正確，并以“廿結(jié)束。算術(shù)表達(dá)式求恒乩再展如僧:

1.初始化運(yùn)算數(shù)棧和運(yùn)算符棧；將運(yùn)算符“廿壓入運(yùn)算符棧；*

2.讀入一個(gè)元素；

3.當(dāng)元素不為“廿或運(yùn)算符棧頂不為“二”時(shí)，循環(huán)執(zhí)行：

?若元素是一個(gè)運(yùn)算數(shù)，則將其壓入運(yùn)算數(shù)棧，讀入下一個(gè)元素；

?若元素是運(yùn)算符（op2）,則將運(yùn)算符棧的棧頂運(yùn)算符（opl）之比較

優(yōu)先級(jí)（運(yùn)算符間的優(yōu)先關(guān)系見P.62表3.1）:

?若opl<op2,貝（將op2壓入運(yùn)算符棧，讀入下一個(gè)元素；

?若opl=op2,則刪除運(yùn)算符棧的棧頂運(yùn)算符，讀入下一個(gè)元素;

?若opl>op2,則從運(yùn)算符棧彈出運(yùn)算符給op,并先后從運(yùn)算數(shù)棧

中彈出兩個(gè)運(yùn)算數(shù)給y和x,計(jì)算x<op>y（如果是除運(yùn)算且除數(shù)

為0,則報(bào)錯(cuò)并結(jié)束算法）的值并將結(jié)果壓入運(yùn)算數(shù)棧。

直到opl和op2均為“廿。

自磋算數(shù)棧的棧頂元素就是求得的表達(dá)式的值。

3的崎序請(qǐng)見教程P.62

表達(dá)式求值

算法的計(jì)算過程舉例：

5+(6-4/2)*3二

4/2=2

6-2=4

4*3=12

運(yùn)算符棧5+12=17

3.1.3棧的應(yīng)用舉例一遞歸禾

在各種程序設(shè)計(jì)語(yǔ)言中都有子程序（或稱函數(shù):調(diào)用

功能。而子程序也可以調(diào)用其它的子程序，甚至可以直接凌d

間接地調(diào)用自身（即遞歸）。

函數(shù)的調(diào)用和返回是利用棧來完成的。系統(tǒng)為運(yùn)行的程序

設(shè)置一個(gè)工作棧，當(dāng)執(zhí)行調(diào)用語(yǔ)句時(shí)，系統(tǒng)先把有關(guān)當(dāng)前

函數(shù)的必要信息（包括返回地址、實(shí)參、局部變量等信息）

組成一個(gè)活動(dòng)記錄，保存到棧中，然后才去執(zhí)行被調(diào)函數(shù)。

當(dāng)被調(diào)函數(shù)執(zhí)行完后，再?gòu)臈Ｖ袕棾鲆粋€(gè)活動(dòng)記錄，根據(jù)

其中的返回地址，將控制轉(zhuǎn)移回調(diào)用函數(shù)，并恢復(fù)當(dāng)前信

息。當(dāng)有多個(gè)函數(shù)嵌套調(diào)用時(shí)，按照“后調(diào)用先返回”的

原則來處理。

遞歸和漢諾塔1

以下是函數(shù)調(diào)用和返回時(shí)工作棧的變化示意囪:

r入棧s入棧t入棧

工作棧工作棧工作棧

一個(gè)遞歸函數(shù)的運(yùn)行過程類似于多個(gè)函數(shù)的嵌套調(diào)用，只是

函數(shù)和被調(diào)函數(shù)是同一個(gè)函數(shù)。

遞歸和漢諾塔

【例3.4】漢諾塔問題

傳說婆羅門圣殿(TempleofBrahman)里有一個(gè)塔臺(tái)，臺(tái)

上立有3根鉆石柱子A,B和C,在A柱上插了64個(gè)金圓盤，每

一個(gè)圓盤都比其下面的略小一些。教士們需要招1A柱上的圓盤

移到C柱上。

移動(dòng)的規(guī)則是：

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

2.圓盤可以移到A、B和C中的任一個(gè)柱子上;

3.任何時(shí)候大盤都不能放到小盤的上面。

漢諾塔問題

用計(jì)算機(jī)來完成這個(gè)任務(wù)可以很方便地用G

設(shè)A柱上最初有4個(gè)圓盤，求解的方法是：

如果刀二1,則將這個(gè)圓盤直接從A柱移到C柱。否則，

執(zhí)行以下3步：

1.先將A柱的上面4-1個(gè)圓盤移到B柱；

2.將A柱上最大的圓盤移到C柱；

3.修B柱上的X-1個(gè)圓盤移到C柱。

這樣，問題就變成了將刀-1個(gè)圓盤從B柱移到C柱了。

這個(gè)問題與刀個(gè)圓盤的問題具有相同的特性，只是問

題規(guī)模減小了1,因此可以用同樣的方法求解。

A柱B柱C柱A柱B柱C柱

(a)初始狀態(tài)(b)將A柱上面3個(gè)盤移到B柱

n

A柱B柱C柱A柱B柱C柱

(c)將A柱1個(gè)盤移到C柱(d)將B柱上面2個(gè)盤移到A柱

B柱

將B柱的1個(gè)盤移到C柱(f)將A柱上面1個(gè)盤移到B柱

n

A柱B柱C柱

(h)將B柱的1個(gè)盤移到C柱

漢諾塔問題

遞歸算法如下：

〃將a柱上按直徑自上而下，由小到大編號(hào)為1至n的n個(gè)圓盤按規(guī)則搬到c柱上。

〃b用作輔助柱

voidhanoi(intn,chara,charb,charc)

{//——(1)

if(n=1)//——(2)

move(l,a,c);〃將編號(hào)為1的圓盤從a移到c---(3)

else//——(4)

hanoi(n-1,a,c,b);〃將a上編號(hào)為1至n-1的圓盤移到b,c作輔助柱-一(5)

move(n,a,c);〃將編號(hào)為n的圓盤從a移到c---(6)

hanoi(n-1,b,a,c);〃將b上編號(hào)為1至n-1的圓盤移到c,a作輔助柱■?一(7)

}//——(8)

》〃一一⑼

漢諾塔問題

以hanoi(3,a,b,c)為例,遞歸函數(shù)haR口

中遞歸工作棧的變化情況為:

通n層次執(zhí)行語(yǔ)E唾U1】作棧狀志塔與四席的女態(tài)說明

(返向地址,n,xb,c1

A■<山上端數(shù)進(jìn)入韜一層.執(zhí)仃到詁句

?1,2,4,5

5.因通用用而進(jìn)入卜一層.

口.、?、"*,<AUL

中第人的語(yǔ)句5世人第一二?執(zhí)

一1.工4.、同上

iu工a1汗語(yǔ)句5進(jìn)入F星遞曠1

，.1

fi我(語(yǔ)句3,將1母置由&移蜘,1；

F1.-A

31.2,3.D講句七目出第三層.返回不一層的

1.1.4X<AlX誨旬6?

二

A/.執(zhí)斤語(yǔ)句3指2號(hào)/RU傳至h,白

一

6.7丹，《LC.

[u.1二占語(yǔ)句7送入F一層遹仃.

A■「執(zhí)行誨句3,將1匕*5a移至b?

乙1.

31.X3.,?田法向9退出第二二層，返回第層

k：l.1.A.X<XAI的善句8.

山的句9追小第層,遑回差層

同上

tuXa.<的語(yǔ)F6.

■1Ci.工t*

￡

r***

??44二

kU.31MA

I

二s!il

—

二

第

二i?

目回

二

秋返

二?，

領(lǐng)

、人

二

川

爐一

g1痔

：第

W

出

；

退.

，

！

m:-3x，98

二6

三w用句

二

烹語(yǔ)語(yǔ)

主

1中的京

%

T?M9日

a叵TwT值

>,

依-

1JI11J1金

1,?

6K

A*cn，：6

?9浦*?

9ri