第02章數(shù)據(jù)結(jié)構(gòu)課件

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

第2章線性表及其順序存儲(chǔ)

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

第2章線性表及其順序存儲(chǔ)

線性表是一種常用的數(shù)據(jù)結(jié)構(gòu)，本章介紹線性表

及其順序存儲(chǔ)，并對(duì)棧和隊(duì)列及它們的順序?qū)崿F(xiàn)給出

了詳細(xì)的設(shè)計(jì)描述。

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

第2章線性表及其順序存儲(chǔ)

線性表是一種常用的數(shù)據(jù)結(jié)構(gòu)，本章介紹線性表

及其順序存儲(chǔ)，并對(duì)棧和隊(duì)列及它們的順序?qū)崿F(xiàn)給出

了詳細(xì)的設(shè)計(jì)描述。

2.1線性表

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

第2章線性表及其順序存儲(chǔ)

線性表是一種常用的數(shù)據(jù)結(jié)構(gòu)，本章介紹線性表

及其順序存儲(chǔ)，并對(duì)棧和隊(duì)列及它們的順序?qū)崿F(xiàn)給出

了詳細(xì)的設(shè)計(jì)描述。

2.1線爨

線性表是一個(gè)線性結(jié)構(gòu)，它是一個(gè)含有n》0個(gè)

結(jié)點(diǎn)的有限序列，對(duì)于其中的結(jié)點(diǎn)，有且僅有一個(gè)

開(kāi)始結(jié)點(diǎn)沒(méi)有前驅(qū)但有一個(gè)后繼結(jié)點(diǎn)，有且僅有一

個(gè)終端結(jié)點(diǎn)沒(méi)有后繼但有一個(gè)前驅(qū)結(jié)點(diǎn)，其它的結(jié)

點(diǎn)都有且僅有一個(gè)前驅(qū)和一個(gè)后繼結(jié)點(diǎn)。一般地，

一個(gè)莪性表可以表示成一個(gè)線性序列：…卜已

其中均是開(kāi)始結(jié)點(diǎn)，心是終端結(jié)點(diǎn)。

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

2.21頁(yè)序表

221順序表

PEF文件使用"pdfFactoryPro"試用版本創(chuàng)建fincprint.comcn

2.21頁(yè)序表

221順序表

線性表采用順序存儲(chǔ)的方式存儲(chǔ)就稱之為順序表。

順序表是將表中的結(jié)點(diǎn)依次存放在計(jì)算機(jī)內(nèi)存中一組

地址連續(xù)的年儲(chǔ)單元中。

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

2.21頁(yè)序表

2.2.力頓序表

線性表采用順序存儲(chǔ)的方式存儲(chǔ)就稱之為順序表。

順序表是將表中的結(jié)點(diǎn)依次存放在計(jì)算機(jī)內(nèi)存中一組

地址連續(xù)的年儲(chǔ)單元中。

如順序表的每個(gè)結(jié)點(diǎn)占用len個(gè)內(nèi)存單元，用

location(kJ表示順序表中第i個(gè)結(jié)點(diǎn)(所占內(nèi)存空間的

第1個(gè)單元的地址。則有如下的關(guān)系

location(ki+1)=location(k)+len

location(kJ=location(k1)+(i-l)len

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

順序表的存儲(chǔ)結(jié)構(gòu)如下圖所示:

存儲(chǔ)結(jié)構(gòu)要體現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)，順序表的存儲(chǔ)

結(jié)構(gòu)中，內(nèi)存中物理地址相鄰的結(jié)點(diǎn)一定具有順序表

中的邏輯關(guān)系。

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

順序表類型的描述如下：

ADTsequence_list{

數(shù)據(jù)集合K:K={k]9k2,...,kn},n>0,K中的元素是datatype類型

數(shù)據(jù)關(guān)系R:R={r},r={<ki,ki+1>|i=l,2,...,n-l}

操作集合：

(1)voidinit_sequence_list(sequence_list*slt)順序表的初始化---置空表

(2)voidinsert_sequence_list(sequence_list*slt,datatypex)后部插入值為x結(jié)點(diǎn)

(3)voidprint_sequence_list(sequence_listsit)打印順序表的各結(jié)點(diǎn)值

(4)intis_empty_sequence_list(sequence_listsit)判斷順序表是否為空

(5)intfind_num_sequence_list(sequence_listsit,datatypex)查找值為x結(jié)點(diǎn)位置

(6)intget_data_pos(sequence_listsit,inti)取得順序表中第i個(gè)結(jié)點(diǎn)的值

(7)voidinsert_pos_sequence_list(sequence_list*slt,intposition,datatypex)

(8)voiddelete_pos_sequence_list(sequence_list*slt,intposition)

}ADTsequencelist;

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

222順序表的實(shí)現(xiàn)

用C語(yǔ)言中的數(shù)組存儲(chǔ)順序表。C語(yǔ)言中數(shù)組的下標(biāo)

是從0開(kāi)始的，即數(shù)組中下標(biāo)為0的元素對(duì)應(yīng)的是順序

表中的第1個(gè)結(jié)點(diǎn)，數(shù)組中下標(biāo)為i的元素對(duì)應(yīng)的是順序

表中的第i+1個(gè)結(jié)點(diǎn)。為了方便，將順序表中各結(jié)點(diǎn)的

序號(hào)改為和對(duì)應(yīng)數(shù)組元素的下標(biāo)序號(hào)一致，即將順序

表中各結(jié)點(diǎn)的序號(hào)從0開(kāi)始編號(hào)。這樣，一個(gè)長(zhǎng)度為n

的順序表可以表示為

{k。,k],k?,…,院_]}

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

順序表的存儲(chǔ)結(jié)構(gòu)的C語(yǔ)言描述如下:

?1>>2><1>

^>?*T**T**T**T*^>?*TW

/*順序表的頭文件，文件名sequlist.h*/

<l4?>|><1<?st*

/^TW^TW*T^*T^^TW

#defineMAXSIZE100

typedefintdatatype;

typedefstruct{

datatypea[MAXSIZE];

intsize;

}sequence_list;

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

順序表的幾個(gè)基本操作的具體實(shí)現(xiàn):

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

順序表的幾個(gè)基本操作的具體實(shí)現(xiàn):

K!>?1><1>K!>?x?

*Z^

順序表的初始化--置空表

/*文件名seqlinit.c,函數(shù)名init_sequence_list()

K|^^}><>!>?1>^|>^j>K|^<J>K!>^f>^|>^}>^}>^1>

*T^*T*

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

順序表的幾個(gè)基本操作的具體實(shí)現(xiàn):

K!>?1><1>K!>?x?

*Z^

順序表的初始化--置空表

/*文件名seqlinit.c,函數(shù)名init_sequence_list()*/

/v|><A??1>?X>

/*T**T*<Tw*T^

voidinit_sequence_list(sequence_list*slt)

slt->size=0;

)

算法2.1順序表的初始化一置空表

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

^j>^t>^f>^9>^f>^f>K!>?1>^j>^9^

rrw^TM*T*<TM*T^rrw<|^*r^

/*在順序表后部進(jìn)行插入操作*/

/*文件名seqlinse.c,函數(shù)名insert_sequence」ist()*/

*1^?1>?1><1^<1^<1^?1>??1^<}>^|>

<T>>TW*TW>TW*TW*TW<TW^T><TM>T*<T^rT><T>*TW<TW<T^*TW>TW*7^*TW*T>

voidinsert_sequence_list(sequence_list*slt,datatypex)

(

if(slt->size==MAXSIZE)

{printf("順序表是滿的!");exit(1);}

slt->size=slt->size+1;

slt->a[slt->size]=x;

)

算法2.2在順序表后部進(jìn)行插入操作

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

/^9>^1^^9^^f>^1>^9>^1^^f>?1^/

/>1^*1**1**J^<1^>1^^1**1**1^*1**TW*T**T**T*>T^*|>^W*T*/

*打印順序表的各結(jié)點(diǎn)值

/*文件名seqlprin.c,函數(shù)名print_sequence」ist()*/

//<i><i>^v>xt>/

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

/^9>^1^^9^^f>^1>^9>^1^^f>?1^/

/>1^*1**1**J^<1^>1^^1**1**1^*1**TW*T**T**T*>T^*|>^W*T*/

*打印順序表的各結(jié)點(diǎn)值

/*文件名seqlprin.c,函數(shù)名print_sequence」ist()*/

/^t>?t>^t><i><i>^v>^t>^t>^t>xt>?f>^t>^t>^t>^t>^t>^t>

//

voidprint_sequence_list(sequence_listsit)

(

inti;

if(!slt.size)printf("\n順序表是空的!”);

else

for(i=0;i<slt.size;i++)printf("%5d",slt.a[i]);

算法2.3打印順序表的各結(jié)點(diǎn)值

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

intis_empty_sequence_list(sequence_listsit)

return(slt.size==O?0:1);

)

算法2.4判斷順序表是否為空

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

^f>^1>?1^?1^^1>?1^^9>^J>^9>/

*TW*T**T^*TW*T**T**T**T**T*^T**T*^TM*TW*TW*T**T^>T^/

/*判斷順序表是否為空*/

/*文件名seqlempt.c,函數(shù)名is_empty_sequence_list()*/

/Sl^Sl^?1>^f>^|><f><A>//

intis_empty_sequence_list(sequence_listsit)

return(slt.size==O?0:1);

)

算法2.4判斷順序表是否為空

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

^f>^f>^{>KJ>*9^^f>^1>>]^^f>

^W*T**T*^W*1**T**T**TW*TW

查找順序表中值為X的結(jié)點(diǎn)位置*/

/*文件名seqlfind.c，函數(shù)名find_num_sequence_list()*/

/^f>K!>?kl><I>?I>^f><f^^f>K!>^|>?j>?f><1>^f>/

/*T^<T^/

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

^f>^f>^{>KJ>*9^^f>^1>>]^^f>

^W*T**T*^W*1**T**T**TW*TW

/*查找順序表中值為X的結(jié)點(diǎn)位置*/

/*文件名seqlfind.c,函數(shù)名find_num_sequence_list()*/

?f^^f>^|>?A?K|><I>^f>^9><f^<A?<X^*1>^I>^f>^f>?j>?f>/

/XT**T^*TM<T^/

intfind_num_sequence_list(sequence_listsit,datatypex)

(

inti=0;

while(slt.a[i]!=x&&i<slt.size)i++;

return(i<slt.size?i:-1);

}

算法2.5查找順序表中值為x的結(jié)點(diǎn)位置

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

^1^^|>^9^^9>^1>^f>^1>>1>^f>^1>^{>^1>

*TW*1**T*>1**1**1*>1^*1^*1**TW*1**TW*T**TW<J*<T**T*

取得順序表中第i個(gè)結(jié)點(diǎn)的值*

/*文件名seqlget.c,函數(shù)名get_data__pos_sequence_list()*/

//^1><1>?X?^*fT>*?X?^|>^f><1^^f>/

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

^9^^t>^9>>f^*1>^9>^9>^1>>f>^f>/

*TW*T*<T**T>*TW*T**TW*T**TW*T**T*^1**T^*T*/

/*取得順序表中第i個(gè)結(jié)點(diǎn)的值*/

/*文件名seqlget.c,函數(shù)名get_data_pos_sequence_list()*/

<1><X?^f>?X?^f>/

<T>#T^*T^<T^/

intget_data_pos(sequence_listsltjnti)

(

if(i<O||i>=slt.size)

{printf(”\n指定位置的結(jié)點(diǎn)不存在!)eWt(1);}

else

returnslt.a[i];

)

算法2.6取得順序表中第i個(gè)結(jié)點(diǎn)的值

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

順序表的插入運(yùn)算是將一個(gè)值為X的結(jié)點(diǎn)插入到順序

表的第i個(gè)位置O4i《n,即將x插入到3和I之間，如果

i=n,則表示插入到表的最后，一般地可表示為：

才由刖：{k。，,kj”kj,…，j}

插入后：{k0,k1?kg,x,kpk『i}

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

順序表的插入運(yùn)算是將一個(gè)值為X的結(jié)點(diǎn)插入到順序

表的第i個(gè)位置O4i《n,即將x插入到3和I之間，如果

i=n,則表示插入到表的最后，一般地可表示為：

才由刖：{k。，,kj”kj,…，j}

插入后：{k0,k1?kg,x,kpk『i}

插入過(guò)程的圖示見(jiàn)下圖：

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

順序表的插入運(yùn)算是將一個(gè)值為X的結(jié)點(diǎn)插入到順序

表的第i個(gè)位置O4i《n,即將x插入到3和I之間，如果

i=n,則表示插入到表的最后，一般地可表示為：

才由刖：{k。，,kj”kj,…，j}

插入后：{k0,k1?kg,x,kpk『i}

插入過(guò)程的圖示見(jiàn)下圖：

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

^f>^J>^1>^f>^9>^1>?1^>f>^t>

*TW*T**T**1^*T^*TW*T**T**T**T^*T**T**T^*TW*T*<|**T**T*

/*在順序表的position位置插入值為x的結(jié)點(diǎn)*/

/*文件名seqlinse.c,函數(shù)名insert_pos_sequence_list()*/

/<1^^jL>?1>?X??1>/

/*T^#TM/

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

voidinsert_pos_sequence_list(sequence_list*slt,int

position,datatypex)

{inti;

if(slt->size==MAXSIZE)

{printf(”\n順序表是滿的!沒(méi)法插入!”);exit⑴;}

if(position<0||position>slt->size)

{printf("\n指定的插入位置不存在!)exit。);}

for(i=slt->size;i>position;i-)slt->a[i]=slt->a[i-1];

slt->a[position]=x;

slt->size++;

)

算法2.7在順序表的pos由on位置插入值為x的結(jié)點(diǎn)

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

算法2.7中，所花費(fèi)的時(shí)間主要是元素后移操作，對(duì)

于在第i個(gè)位置上插入一個(gè)新的元素，需要移動(dòng)（n-i）

個(gè)元素，設(shè)在第i個(gè)位置上插入一個(gè)元素的概率為R,且

在任意一個(gè)位置上插入元素的概率相手，即

Po=Pi=P2=...=Pn=l/n+l,則在一個(gè)長(zhǎng)度為n的順序表中插

入一個(gè)元素所需的平均移動(dòng)次數(shù)為：

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

算法2.7中，所花費(fèi)的時(shí)間主要是元素后移操作，對(duì)

于在第i個(gè)位置上插入一個(gè)新的元素，需要移動(dòng)（n-i）

個(gè)元素，設(shè)在第i個(gè)位置上插入一個(gè)元素的概率為R,且

在任意一個(gè)位置上插入元素的概率相手，即

Po=Pi=P2=...=Pn=l/n+l,則在一個(gè)長(zhǎng)度為n的順序表中插

入一個(gè)元素所需的平均移動(dòng)次數(shù)為：

t小這，）=T義中檔

toto^+1〃+122

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

算法2.7中，所花費(fèi)的時(shí)間主要是元素后移操作，對(duì)

于在第i個(gè)位置上插入一個(gè)新的元素，需要移動(dòng)(n-i)

個(gè)元素，設(shè)在第i個(gè)位置上插入一個(gè)元素的概率為R,且

在任意一個(gè)位置上插入元素的概率相手，即

Po=Pi=P2=...=Pn=l/n+l,則在一個(gè)長(zhǎng)度為n的順序表中插

入一個(gè)元素所需的平均移動(dòng)次數(shù)為：

t小這，）=T義中檔

toto^+1〃+122

即在長(zhǎng)度為n的順序表中插入一個(gè)元素平均需要

移動(dòng)表中的一半元素。該算法的時(shí)間復(fù)雜度為0(n)。

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

順序表的刪除操作是指刪除順序表中的第i個(gè)結(jié)點(diǎn),

0<i<n-l5一般地可表示為：

刪除前：｛ko，k“

刪除后：｛k0,"…，kg,K+1,…，kn_J

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

順序表的刪除操作是指刪除順序表中的第i個(gè)結(jié)點(diǎn),

0<i<n-l5一般地可表示為：

刪除前：｛ko，k“

刪除后：｛k0,"…，kg,kj+1,kn_J

刪除過(guò)程的圖示見(jiàn)下圖：

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

順序表的刪除操作是指刪除順序表中的第i個(gè)結(jié)點(diǎn),

0<i<n-l5一般地可表示為：

刪除前：｛ko，k“

刪除后：｛k0,"…，kg,kj+1,kn_J

刪除過(guò)程的圖示見(jiàn)下圖：

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

刪除操作的具體實(shí)現(xiàn)見(jiàn)算法2.8

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

刪除操作的具體實(shí)現(xiàn)見(jiàn)算法2.8

/<1^^9>^9^^1>^}>/

/*1**1**TW*1*<1^^1**1**1**1**1^*1**1**T><Tw/

/*刪除順序表中第position位置的結(jié)點(diǎn)*/

/*文件名seqldele.c,函數(shù)名delete_pos_sequence_list()*/

/^|>^L??1><1>KI>?X><>1>/

/^TW<TM/

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

刪除操作的具體實(shí)現(xiàn)見(jiàn)算法2.8

voiddelete_pos_sequence_list(sequence_list*slt,intposition)

(

inti;

if(slt->size==O)

{printf(”\n順序表是空的!");exit⑴;}

if(position<0||position>=slt->size)

{printf(”\n指定的刪除位置不存在!");exit(1);}

for(i=position;i<slt->size-1;i-)slt->a[i]=slt->a[i+1];

slt->size-;

)

算法2.8刪除順序表中第pos田on位置的結(jié)點(diǎn)

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

要?jiǎng)h除順序表中的第i個(gè)結(jié)點(diǎn)，則需要稱動(dòng)（n-i-1）

個(gè)元素，設(shè)刪除表中第i個(gè)結(jié)點(diǎn)的概率為q〃且在表中每

一個(gè)位置刪除的概率相等，即：

q（）=qi=??尸qxi/n

則在一個(gè)長(zhǎng)度為n的順序表中刪除一個(gè)結(jié)點(diǎn)的平均

移動(dòng)次數(shù)為：

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

要?jiǎng)h除順序表中的第i個(gè)結(jié)點(diǎn)，則需要稱動(dòng)（n-i-1）

個(gè)元素，設(shè)刪除表中第i個(gè)結(jié)點(diǎn)的概率為q〃且在表中每

一個(gè)位置刪除的概率相等，即：

q（）=qi=??尸qxi/n

則在一個(gè)長(zhǎng)度為n的順序表中刪除一個(gè)結(jié)點(diǎn)的平均

移動(dòng)次數(shù)為：

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

要?jiǎng)h除順序表中的第i個(gè)結(jié)點(diǎn)，則需要稱動(dòng)（n-i-1）

個(gè)元素，設(shè)刪除表中第i個(gè)結(jié)點(diǎn)的概率為q〃且在表中每

一個(gè)位置刪除的概率相等，即：

q（）=qi=??尸qxi/n

則在一個(gè)長(zhǎng)度為n的順序表中刪除一個(gè)結(jié)點(diǎn)的平均

移動(dòng)次數(shù)為：

=之一("-I)=—x=---

z=o2=0nn22

這表明，在一個(gè)長(zhǎng)為n的順序表中刪除一個(gè)元素平

均需要移動(dòng)表中大約一半的元素。該算法的時(shí)間復(fù)雜

度為O（n）o

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

2.3棧

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

2.3棧

231棧

PIT文件使用"pdfFactoryPro"試用版本創(chuàng)建fincprint.comcn

2.3棧

231棧

棧是一種特殊的線性表，對(duì)于這種線性表規(guī)定它

的插入運(yùn)算和刪除運(yùn)算均在線性表的同一端進(jìn)行，進(jìn)

行插入和刪除的那一端稱為棧頂，另一端稱為棧底。

棧的插入操作和刪除操作也分別簡(jiǎn)稱進(jìn)棧和出棧。

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

2.3棧

231棧

棧是一種特殊的線性表，對(duì)于這種線性表規(guī)定它

的插入運(yùn)算和刪除運(yùn)算均在線性表的同一端進(jìn)行，進(jìn)

行插入和刪除的那一端稱為棧頂，另一端稱為棧底。

棧的插入操作和刪除操作也分別簡(jiǎn)稱進(jìn)棧和出棧。

如果棧中有n個(gè)結(jié)點(diǎn)

{k0,，k2,.?.，kn-i｝，

k0為棧底，kn.1是棧頂,

則棧中結(jié)點(diǎn)的進(jìn)棧順

序?yàn)椴?,1<2，…，kn」,

而出棧的順序?yàn)閗n【

kn.2,kvk0o如囪

所示。

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

2.3棧

231棧

棧是一種特殊的線性表，對(duì)于這種線性表規(guī)定它

的插入運(yùn)算和刪除運(yùn)算均在線性表的同一端進(jìn)行，進(jìn)

行插入和刪除的那一端稱為棧頂，另一端稱為棧底。

棧的插入操作和刪除操作也分別簡(jiǎn)稱進(jìn)棧和出棧。

如果棧中有n個(gè)結(jié)點(diǎn)

{k0,，k2,.?.，kn-i｝，

k0為棧底,是棧頂,

則棧中結(jié)點(diǎn)的進(jìn)棧順

序?yàn)椤?，kn」，

而出棧的順序?yàn)榛胈1,；

kn.2,kvk0o如囪

而示。!

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

2.3棧

231棧

棧是一種特殊的線性表，對(duì)于這種線性表規(guī)定它

的插入運(yùn)算和刪除運(yùn)算均在線性表的同一端進(jìn)行，進(jìn)

行插入和刪除的那一端稱為棧頂，另一端稱為棧底。

棧的插入操作和刪除操作也分別簡(jiǎn)稱進(jìn)棧和出棧。

如果棧中有n個(gè)結(jié)點(diǎn)

{k0,，k2,.?.，kn-i｝，

k0為棧底,是棧頂,

則棧中結(jié)點(diǎn)的進(jìn)棧順

序?yàn)椤?，kn」，

而出棧的順序?yàn)榛胈1,；

kn.2,kvk0o如囪

而示。!

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

2.3棧

231棧

棧是一種特殊的線性表，對(duì)于這種線性表規(guī)定它

的插入運(yùn)算和刪除運(yùn)算均在線性表的同一端進(jìn)行，進(jìn)

行插入和刪除的那一端稱為棧頂，另一端稱為棧底。

棧的插入操作和刪除操作也分別簡(jiǎn)稱進(jìn)棧和出棧。

如果棧中有個(gè)結(jié)點(diǎn)

n棧具有后

{k0,，k2,.?.，kn-i｝，進(jìn)先出或

為棧底，是棧頂,

k0kn.1先進(jìn)后出

則棧中結(jié)點(diǎn)的進(jìn)棧順(FILO,

序?yàn)椴?7I，卜2，…，kn」?FirstIn

而出棧的順序?yàn)樯譏LastOut)

k.,kk如囪

n2v0o：的性質(zhì)

1而示。!II____________________________.

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

棧類型的描述如下：

ADTsequence_stack{

數(shù)據(jù)集合K:K={kpk2,...,kn},n>0,K中的元素是datatype類型

數(shù)據(jù)關(guān)系R:R={r}

r={<ki,ki+1>|

操作集合：

(1)voidinit_sequence_stack(sequence_stack*st)(可頁(yè)序存儲(chǔ))

初始化

(2)intis_empty_stack(sequence_stackst)判斷棧(順序存儲(chǔ))

是否為空———

(3)voidprint_sequence_stack(sequence_stackst)打印棧(順

序存儲(chǔ))的意點(diǎn)、值——

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

(4)datatypeget_top(sequence_stackst)取得棧頂(順序存

貓)結(jié)點(diǎn)血

(5)voidpush(sequence_stack*st,datatypex)棧(順序存儲(chǔ))

的插入操作

(6)voidpop(sequence_stack*st)棧(順序存儲(chǔ))的刪除操

作

}ADTsequence_stack

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

2.3.2順序棧及其實(shí)現(xiàn)

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

2.3.2順序棧及其實(shí)現(xiàn)

棧的實(shí)現(xiàn)方式一般有兩種：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。

本小節(jié)將給出棧的順序存儲(chǔ)實(shí)現(xiàn)。

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

2.3.2順序棧及其實(shí)現(xiàn)

棧的實(shí)現(xiàn)方式一般有兩種：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。

本小節(jié)將給出棧的順序存儲(chǔ)實(shí)現(xiàn)。

棧的順序存儲(chǔ)方式就是在順序表的基礎(chǔ)上對(duì)插入

和刪除操作限制它們?cè)陧樞虮淼耐欢诉M(jìn)行，所以同

順序表一樣也可用一維數(shù)組表示。

一般地，可以設(shè)定一個(gè)足夠大的一維數(shù)組存儲(chǔ)棧,

數(shù)組中下標(biāo)為0的元素就是棧底，對(duì)于棧頂，可以設(shè)一

個(gè)指針top指示它。

為了方便，設(shè)定top所指的位置是下一個(gè)將要插入

的結(jié)點(diǎn)的存儲(chǔ)位置,這樣，當(dāng)top=0時(shí)就表示是一個(gè)空

的棧。一個(gè)棧的幾種狀態(tài)以及在這些狀態(tài)下棧頂指針

top和棧中結(jié)點(diǎn)的關(guān)系如下圖所示。

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

數(shù)組下標(biāo)數(shù)組下標(biāo)數(shù)組下標(biāo)

topf

MAXSIZE-1MAXSIZE.1kMAXSIZE-1

!!!!

2top—2kj2

1ki1ki1

topf0ko0ko0

(a)空棧⑻有兩個(gè)結(jié)點(diǎn)的棧(c)棧已滿

PEF文件使用"pdfFactoryPro”試用版本創(chuàng)建WAWfincprint.comcn

棧的順序存儲(chǔ)結(jié)構(gòu)的C語(yǔ)言描述如下: