數(shù)據(jù)結構萬健版第3章其他線性結構

第3章其它線性結構

棧

隊列

串

數(shù)組

廣義表

3.1棧

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

操作的特殊的線性表。

（退棧、彈

當棧中沒有任何元素時稱為空棧。

3.1棧

由于棧的插入和刪除操作總是在棧頂進行，所

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

為后進先出(LastInFirstOut)的線性表，簡稱

LIFO表。

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

1,3,2

則可能的輸出序列有233

哪些？2,3,1

3,2,1

3.1棧

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

棧的存儲結構及操作實現(xiàn)歪

棧的應用舉例

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

ADTStackl：fl

(

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

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

基本操作：

Init(&S)

操作結果：構造一個空的棧S

Destroy(&S)

初始條件：棧S已存在

操作結果：銷毀棧S

Clear(&S)

初始條件：棧S已存在

操作結果：將棧S清空

Empty(S)

初始條件：棧S已存在。

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

Length(S)

初始條件：棧S已存在。

操作結果：返回棧S的長度。

Top(S)

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

操作結果：返回棧頂元素的值。

Push(&S,e)

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

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

Pop(&S)

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

操作結果：刪除棧頂元素。

3.1.2棧的存儲結構及操作久^.

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

表的存儲結構同樣適用于棧，故棧也可以采用順序

存儲結構和鏈式存儲結構。

順序棧

鏈棧

豕

棧的順序存儲表示一順序一

?棧的順序存儲表示順序棧

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

棧的第1?個元素存放在"1下標位置O

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

始時，棧為空，置top=0;入棧時，top加1;出棧時，top

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

在棧頂元素的后一個下標位置。

>

top

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

順序棧類定義

template<classElemType>II聲明一個類模板

classSqStack//順序棧類

public:

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

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

voidClear();//清空棧

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

intLength()const;//求長度

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

voidPush(constElemType&e);//入棧

voidPop();//出棧

private:

ElemType*m_base;//基地址指針

intm_top;//棧頂指針

intm_size;//向量空間大小

);

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

1.棧初始化

//構造函數(shù)，分配m個結點的順序空間，構造一個空的順序棧

template<classElemType>

SqStack<ElemType>::SqStack(intm)

(

m_top=0;

m_base=newElemType[m];

msize=m;

mbasemtopmsize

（棧底）（棧頂）一

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

2.銷毀棧

//析構函數(shù)，將棧結構銷毀

template<classElemType>

SqStack<ElemType>::~SqStack()

(

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

)

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

3.清空棧

//清空棧

template<classElemType>

voidSqStack<ElemType>::Clear()

m_top-0;

}

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

4.判?？?/p>

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

template<classElemType>

boolSqStack<ElemType>::Empty()const

returnm_top==0;

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

5.求長度

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

template<classElemType>

intSqStack<ElemType>::Length()const

{

returnm_top;

}

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

6.取棧頂元素的值

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

template<classElemType>

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

{

returnm_base[m_top-1];

)

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

7.入棧

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

template<classElemType>

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

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

ElemType*newbase;

newbase=newElemType[msize+10];//擴大10個元素空間

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

newbase[j]=m_base[j];

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

m_base=newbase;//重置基地址

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

mbase[mtop++]

mbasemtopmtop

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

8.出棧

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

template<classElemType>

voidSqStack<ElemType>::Pop()

(

aia2an

I

mbasemtopmtop

_______W|

對于順序棧，應注意：

?入棧時，應首先判斷棧是否已滿。若棧滿，則需要

先擴展空間。

?出棧和取棧頂元素時，必須保證棧不空。若?？?，

則不能進行相應操作，否則會導致異常錯誤。

在上述順序棧的基本操作中，它們的時間復雜度均為

0(1)。

棧的鏈式存儲表示—鏈梭

可用不帶頭結點的單鏈表來表示鏈棧。當?？杖找?/p>

top指向棧頂元素結點；而當棧為空時，top為空指

針。

BCDA

鏈棧類定義

template〈classElemType>

structLinkNode//鏈棧結點

{

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;

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

1.棧初始化

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

template〈classElemType>

Linkstack<ElemType>::Linkstack()

top=NULL;

)

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

2.銷毀棧

//將棧結構銷毀

template<classElemType>

Linkstack<ElemType>::~Linkstack()

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

)

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

3.清空棧

//將棧清空

template<classElemType>

voidLinkstack<ElemType>::Clear()

LinkNode<ElemType>*p;

while(top){//依次釋放鏈表中的所有結點

p=top;

top=top->next;

deletep;

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

4.判棧空

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

template<classElemType>

boolLinkstack<ElemType>::Empty()const

returntop—NULL;

)

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

5.求長度

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

template<classElemType>

intLinkStack<ElemType>::Length()const

(

inti=0;

LinkNode<ElemType>*p=top;

while(p){//對鏈表中的結點計數(shù)

i++；

p=p->next;

}

returni;

}/

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

6.取棧頂元素的值

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

template<classElemType>

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

(

returntop->data;

)

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

7人棧

//入棧

template<classElemType>

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

LinkNode<ElemType>*p;

p=newLinkNode<ElemType>;

p->data=e;

p->next=top;//新結點插在鏈表的頭部

top=p;

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

8.出棧

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

template<classElemType>

voidLinkstack<ElemType>::Pop()

LinkNode<ElemType〉*p=top;//刪除并釋放第'~~個結點

top=top->next;

deletep;

鏈棧

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

new運算符動態(tài)分配的，因此，正常情況下，不會

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

可供分配。

在鏈棧的操作中，棧的銷毀、清空、求長度操作的

時間復雜度為因為需要對鏈表的每一個元素

結點進行處理。其余操作的時間復雜度為。(1)。

3.1.3棧的應用舉例

回文判斷

迷宮問題

表達式求值

遞歸和漢諾塔問題

3.1.3棧的應用舉例

【例3.1】回文判斷

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

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

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

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

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

檢查其是否回文。

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

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

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

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

公若直到?？彰恳粚Ρ容^的字符都相同，則該串是回文。

停請見教程P.55

3.L3棧的應用舉例迷信

【例3.2】迷宮問題

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

路）。

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

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

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

/111111111

ZX

OO1OOOIO11001000101

001000100100100010o

000011011100001101?

0111001011011100101

0001000001000100()00

0100010101010001010

()111100101011110010

110001011111000101

\110000000/111000000

、111111111

圖（A）迷宮地圖

圖（B）加設圍墻后的迷宮地圖

迷宮問題

在迷宮中行進時必須遵循三個原則：

1.每一步只走一格；

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

3.走過的路不會再走第二次。

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

還必須判斷下一步應該往哪個方向走，可以選擇的方向有4個,

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

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

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

走過且能通過，則前進一步進入下一位置；否則試探下一個方

向。若所有的方向均沒有通路，則羽1該點標為死胡同并沿原路

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

'dW可走返回到入口。

迷宮問題

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

一個方向探索前進，需要用一個棧來保存當前所走線

路沿途的每一個位置的坐標以及從該位置前進的方向，

而棧頂?shù)奈恢帽闶钱斍暗奈恢?。當?shù)竭_出口時，棧中

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

一步到達的位置用序號（從1開始）編排，稱為足跡。

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

出一'條路徑。

程序請見教程P.57

3.L3棧的應用舉例表立,紹

【例3.3】表達式求值

求一個表達式的值是程序設計語言編譯程序中的一

個基本問題，實現(xiàn)表達式的求值是棧的一個典型應

用。

在這里，僅討論最基本的算術四則運算：+（加）、

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

先計算的括號。

表達式可定義為（“：：二”為定義符）：

表達式：：=〈運算數(shù)〉〈運算符〉〈運算數(shù)〉

運算數(shù)：：=無符號整數(shù)|表達式|（表達式）

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

表達式求值■I

算術四則運算的規(guī)則為：^登

(1)先乘除、后加減；

(2)同級運算時先左后右；

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

算法設置了兩個棧：

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

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

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

表達式求值

假設表達式語法正確，并以“廿結束。算術表達式求恒乩再展如僧:

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

2.讀入一個元素；

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

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

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

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

?若opl<op2,貝（將op2壓入運算符棧，讀入下一個元素；

?若opl=op2,則刪除運算符棧的棧頂運算符，讀入下一個元素;

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

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

為0,則報錯并結束算法）的值并將結果壓入運算數(shù)棧。

直到opl和op2均為“廿。

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

3的崎序請見教程P.62

表達式求值

算法的計算過程舉例：

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

4/2=2

6-2=4

4*3=12

運算符棧5+12=17

3.1.3棧的應用舉例一遞歸禾

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

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

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

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

設置一個工作棧，當執(zhí)行調(diào)用語句時，系統(tǒng)先把有關當前

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

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

當被調(diào)函數(shù)執(zhí)行完后，再從棧中彈出一個活動記錄，根據(jù)

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

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

原則來處理。

遞歸和漢諾塔1

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

r入棧s入棧t入棧

工作棧工作棧工作棧

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

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

遞歸和漢諾塔

【例3.4】漢諾塔問題

傳說婆羅門圣殿(TempleofBrahman)里有一個塔臺，臺

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

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

移到C柱上。

移動的規(guī)則是：

1.一次只能移動一個圓盤；

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

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

漢諾塔問題

用計算機來完成這個任務可以很方便地用G

設A柱上最初有4個圓盤，求解的方法是：

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

執(zhí)行以下3步：

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

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

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

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

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

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

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

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

n

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

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

B柱

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

n

A柱B柱C柱

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

漢諾塔問題

遞歸算法如下：

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

〃b用作輔助柱

voidhanoi(intn,chara,charb,charc)

{//——(1)

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

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

else//——(4)

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

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

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

}//——(8)

》〃一一⑼

漢諾塔問題

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

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

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

(返向地址,n,xb,c1

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

?1,2,4,5

5.因通用用而進入卜一層.

口.、?、"*,<AUL

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

一1.工4.、同上

iu工a1汗語句5進入F星遞曠1

，.1

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

F1.-A

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

1.1.4X<AlX誨旬6?

二

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

一

6.7丹，《LC.

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

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

乙1.

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

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

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

同上

tuXa.<的語F6.

■1Ci.工t*

￡

r***

??44二

kU.31MA

I

二s!il

—

二

第

二i?

目回

二

秋返

二?，

領

、人

二

川

爐一

g1痔

：第

W

出

；

退.

，

！

m:-3x，98

二6

三w用句

二

烹語語

主

1中的京

%

T?M9日

a叵TwT值

>,

依-

1JI11J1金

1,?

6K

A*cn，：6

?9浦*?

9ri