棧的順序存儲(chǔ)結(jié)構(gòu)順序棧

《棧的順序存儲(chǔ)結(jié)構(gòu)順序棧》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、3．2棧的順序存儲(chǔ)結(jié)構(gòu)---順序棧棧的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱順序棧，它是運(yùn)算受限的順序表。順序棧的存儲(chǔ)結(jié)構(gòu)是：利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置。3．2．1順序棧的類型定義類似于順序表，用一維數(shù)組描述順序棧中的數(shù)據(jù)元素的存儲(chǔ)區(qū)域，并預(yù)設(shè)一個(gè)數(shù)組的最大空間。描述順序棧的通常的習(xí)慣做法是以top=0表示空棧，鑒于C語(yǔ)言中數(shù)組的下標(biāo)約定是從0開始，則當(dāng)以C作描述語(yǔ)言時(shí)，如此設(shè)定會(huì)帶來(lái)很大不便；另一方面，由于棧在使用過程中所需最大空間的大小很難估計(jì)，因

2、此，一般來(lái)說(shuō)，在初始化設(shè)空棧時(shí)不應(yīng)限定棧的最大容量。一個(gè)較合理的做法是：先為棧分配一個(gè)基本容量，然后在應(yīng)用過程中，當(dāng)棧的空間不夠使用時(shí)再逐段擴(kuò)大。為此，可設(shè)定兩個(gè)常量：STACKCSL（存儲(chǔ)空間初始分配量）和STACKZL（存儲(chǔ)空間分配增量）。下面給出順序棧的類型定義：#include"stdlib.h"#defineSTACKCSL64/*順序棧存儲(chǔ)空間初始分配量*/#defineSTACKZL8/*順序棧存儲(chǔ)空間分配增量*/typedefintElemType;/*棧元素的數(shù)據(jù)類型定義，它可以是任意的，

3、具體問題時(shí)只需根據(jù)需要修改本定義語(yǔ)句即可*/typedefstruct{ElemType*top;/*棧頂指針*/ElemType*bottom;/*棧底指針*/intstacksize;/*當(dāng)前已分配的存儲(chǔ)空間，以棧元素為單位*/}seqstack;/*順序棧類型定義*/seqstack*seqs;/*seqs是順序棧類型指針*/其中，stacksize指示棧的當(dāng)前可使用的最大容量，初始化棧時(shí)，stacksize的值等于STACKCSL，以后根據(jù)需要按分配增量STACKZL增長(zhǎng)。bottom是棧底指針，在

4、順序棧中，它始終指向棧底的位置，如果bottom的值等于NULL，就意味著棧結(jié)構(gòu)不存在。top是棧頂指針，其初值指向棧底，也就是說(shuō)top=bottom可作為?？盏臉?biāo)記。每當(dāng)插入新的棧頂元素時(shí)，指針top增1；刪除棧頂元素時(shí)，指針top減一。所以，非空棧中的棧頂指針始終在棧頂元素的下一個(gè)位置上。圖3.2表示了棧頂指針top和順序棧中數(shù)據(jù)元素之間的對(duì)應(yīng)關(guān)系。┋┋185┋┋8513/13┋┋　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　top　　　　　　　　　　　　

5、　　　　　　　　　　　　　　　　　　　　　　　　　　top　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　top　　　　　　　　　　　　　　　　　　　　　　　　　　　bottom　　　　　bottom　　　　　bottom　　　　　　　　　(a)空棧(b)元素5、8、1進(jìn)棧(c)元素1出棧top┋┋485┋34859┋┋485toptoptopbottombottombottom(d)元素4、3進(jìn)棧(e)元素3

6、出棧（f）棧滿圖3.2棧頂指針與數(shù)據(jù)元素的關(guān)系3．2．2基本運(yùn)算的實(shí)現(xiàn)上述順序棧的類型定義以及本小節(jié)將介紹的基本運(yùn)算操作均放在文件“seqstack.c”中，使用時(shí)需要用命令：#include"seqstack.c"將其包含到具體的應(yīng)用程序中去。由于順序棧的插入、刪除只在棧頂進(jìn)行，因此順序棧的基本操作比順序表要簡(jiǎn)單得多。在順序棧上可以實(shí)現(xiàn)初始化棧、進(jìn)棧、出棧、判?？铡⑷ｍ斣氐葞追N基本運(yùn)算，具體算法如下：1．初始化棧該算法用于建立一個(gè)容量為STACKCSL13/13的空順序棧ss。建立時(shí)首先使用mallo

7、c函數(shù)進(jìn)行內(nèi)存儲(chǔ)區(qū)的分配，并將所分配的存儲(chǔ)區(qū)的起始地址賦給棧底指針bottom。如果bottom不為空，說(shuō)明分配成功，否則說(shuō)明分配失敗。成功時(shí)進(jìn)行置空棧的操作，失敗則退出。具體算法如下：算法3.1voidinitstack(seqstack*ss)/*初始化一個(gè)順序棧ss*/{ss->bottom=(ElemType*)malloc(STACKCSL*sizeof(ElemType));if(!ss->bottom){printf(“初始化棧失敗”);return;};ss->top=ss->bottom;

8、ss->stacksize=STACKCSL;printf("初始化棧成功！");}2.進(jìn)棧該算法用于向順序棧ss的棧頂插入一個(gè)元素x。算法首先判斷棧是否已滿，如果棧不滿，就直接進(jìn)行插入操作，否則就使用realloc函數(shù)為該順序棧再多分配增量STACKZL個(gè)元素的存儲(chǔ)空間。如果分配成功，則修改棧頂指針top的位置和棧的容量stacksize，然后將元素x插入在棧頂位置。具體算法如下：算法3.2Voidpush(s