《數(shù)據(jù)結(jié)構(gòu)》課件1第3章 棧與隊列

3.1棧的類型定義3.3棧的應(yīng)用舉例3.2棧類型的實現(xiàn)3.4隊列的類型定義3.5隊列類型的實現(xiàn)總目錄知識點：重點：難點：2、在順序棧、循環(huán)隊列上基本操作的實現(xiàn)。1、棧與隊列的特點；棧的應(yīng)用順序棧、鏈棧、循環(huán)隊列、鏈隊列

通常稱，棧和隊列是限定插入和刪除只能在表的“端點”進行的線性表。

線性表棧隊列Insert(L,

i,x)

Insert(S,

n+1,x)Insert(Q,

n+1,x)

1≤i≤n+1

Delete(L,

i)Delete(S,

n)Delete(Q,

1)

1≤i≤n

棧和隊列是兩種操作受限的線性表，是兩種常用的數(shù)據(jù)類型1.棧是限制僅在表尾進行插入和刪除操作的特

殊線性表，限制操作的表尾端稱為“棧頂”,

另一端稱為“棧底”3.1

棧的類型定義一、棧的邏輯結(jié)構(gòu)定義及特性2.棧是“后進先出”的線性表（LIFO）或“先進后出”的線性表（FILO）a1a2a3…an棧底棧頂進出

如下圖所示的鐵路調(diào)度站形象地表示棧的“后進先出”特點。

思考題：

設(shè)有編號為1，2，3，4的四輛列車，順序進一個棧式結(jié)構(gòu)的站臺，具體寫出這四輛列車開出車站的所有可能的順序。解答：四輛車出站的所有可能順序為：1）1、2、3、4；2）1、2、4、33）1、3、2、4；4）1、3、4、25）1、4、3、2；6）2、1、3、47）2、1、4、3；8）2、3、4、19）2、3、1、4；10）2、4、3、111）3、2、1、4；12）3、2、4、113）3、4、2、1；14）4、3、2、1ADTStack

{

數(shù)據(jù)對象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

約定an

端為棧頂，a1端為棧底。基本操作：

}ADTStack二、棧的抽象數(shù)據(jù)類型定義1、構(gòu)造空棧操作：DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())2、判?？詹僮鳎篒nitStack(&S)3、取棧頂元素操作：4、進棧（插入）操作：5、出棧（刪除）操作：6、置?？詹僮鳎?、求棧中元素個數(shù)操作：8、棧銷毀操作：9、棧遍歷操作：最常用的操作

GetTop(S,&e)

初始條件：棧S已存在且非空。操作結(jié)果：用e返回S的棧頂元素。a1a2an……Push(&S,e)

初始條件：棧S已存在。

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

a1a2ane……Pop(&S,&e)

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

操作結(jié)果：刪除S的棧頂元素，并用e返回其值。a1a2anan-1

……順序棧鏈棧3.2

棧類型的實現(xiàn)//-----棧的順序存儲表示

-----

#defineSTACK_INIT_SIZE100;//存儲空間初始分配量

#defineSTACKINCREMENT10;//存儲空間分配增量

typedefstruct{

SElemType

*base;//棧底指針

SElemType

*top;//棧頂指針

intstacksize;

}

SqStack;SqStacks;

類似于線性表的順序映象實現(xiàn)，指向表尾的指針可以作為棧頂指針。一.順序棧?？諚l件：棧滿條件：

s.tops.base空棧DCBAs.tops.base當stacksize=4時是滿棧s.top=s.base

s.top-s.base=s.stacksize二.順序?；静僮鞯膶崿F(xiàn)1.構(gòu)造一個空棧操作：InitStack(&S)：操作思路：1）用malloc標準函數(shù)分配一個適當大小的連續(xù)空間；2）使其滿足空棧條件。S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType))s.top=s.base3）確定其它值s.stacksize=STACK_INIT_SIZE

StatusInitStack(SqStack&S){//構(gòu)造一個空棧S}S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!S.base)exit(OVERFLOW);//存儲分配失敗

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;P47statusStackempty(SqStackS)

{

}2、判棧空操作：

StackEmpty(S)if(S.top==S.base)returnTRUE;

elsereturnFALSE;要求：若棧S為空，則返回TRUE值，否則返回

FALSE值。算法：（同學(xué)先自己做）3.壓（進或入）棧操作push(&s,e)：要求：將元素e插入到棧頂，作為新的棧頂元素。操作步驟：1）若棧滿，則追加空間,若追加成功則修正有關(guān)棧的值，若追加失敗則結(jié)束操作。2）將新元素e壓棧，棧頂指針后移。S.base=(SElemtype*)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType))；S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMEN;*S.top++=e*S.top=e;S.top=s.top+1;a1a2ane……

StatusPush(SqStack&S,SElemTypee){}if(S.top-S.base>=S.stacksize){//棧滿，追加存儲空間

S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));

if(!S.base)exit(OVERFLOW);//存儲分配失敗

S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}//if*S.top++=e;returnOK;P474.退（出）棧操作pop(&S,&e)：要求：將棧頂元素刪除，并用e保留其值。操作步驟：1）若?？?，則結(jié)束操作。2)若棧不空，則刪除棧頂元素，并用e返回其值If(S.top=S.base)returnERRORe=*--S.tops.top=s.top-1;e=*s.top;a1a2an……an-1es.topStatusPop(SqStack&S,SElemType&e){//若棧不空，則刪除S的棧頂元素，

//用e返回其值，并返回OK；

//否則返回ERROR}if

(S.top

==

S.base)

returnERROR;e=*--S.top;

returnOK;P475.取棧頂元素操作GetTop(S,&e)：要求：讀取棧頂元素并用e保留其值。操作步驟：1）若?？?，則結(jié)束操作。2)否則讀取棧頂元素，并用e返回其值If(S.top==S.base)returnERRORe=*（S.top-1）a1a2an……an-1s.topeanStatusGetTop(SqStackS,SElemType&e){//若棧不空，則刪除S的棧頂元素，

//用e返回其值，并返回OK；

//否則返回ERROR}if

(S.top

==

S.base)

returnERROR;

e=*(S.top-1);

returnOK;P47

棧的鏈式存儲結(jié)構(gòu)稱為鏈棧，是運算受限的單鏈表，其插入和刪除操作僅限制在鏈表的表頭位置上進行，故鏈棧沒有必要象單鏈表一樣附加頭結(jié)點，棧頂指針即為鏈表的頭指針。二.鏈棧棧頂指針∧a1an注意:鏈棧中指針的方向an-1棧底

//-----棧的鏈式存儲表示

-----

typedefstruckSNODE{SElemTypedata;structSNODE*next;}SNODE,*Linkstack;

Linkstacks;注意：若輸入的數(shù)據(jù)是順序輸入a1,a2,...,an，則建鏈棧時一般用頭插法,2.鏈棧的其它操作與鏈表的操作類似（因棧是線性表的特例）.作業(yè)11.分別寫出對鏈棧的入棧和出棧操作的算法。

*2.P24/3.15

鏈棧的結(jié)點類型定義如下：TypedefstructSNODE{SElemTypedata;structSNODE*next;}SNODE，*Linkstack;1)鏈棧的入棧push(&top,x)的函數(shù)如下：statuspush(Linkstack&top,SElemTypex)

//在棧頂指針為top的鏈棧中插入一個值為x的結(jié)點{p=(node*)malloc(sizeof(node));if(p)//分配空間失敗returnERROR;p->data=x;//產(chǎn)生一個值為x的新結(jié)點

p->next=top;top=p;//將p插入到棧頂

returnOK;}解答：2）鏈棧的出棧pop(&top,&e)函數(shù)如下：statuspop(Linkstack&top,SElemType&e)//將棧頂指針為top的鏈棧的棧頂元素出棧，并通過參數(shù)e返回{if(top==NULL)//如果?？?/p>

returnERROR;e=top->data;//將棧頂元素值存入e中p=top;//p指向棧頂結(jié)點top=top->next;//修改指針，使棧頂結(jié)點從棧中脫離出來free(p);

//釋放空間returnOK；}2、設(shè)共享棧的結(jié)構(gòu)圖如下：a1a2……

an…

bm……

b2b1C的元素序號12……n……….m-1m棧1底棧1頂棧2頂棧2底top1top2兩棧的最多元素個數(shù)為m，假設(shè)top1是棧1的棧頂指針，top2是棧2的棧頂指針，分別指向棧頂元素注意：當top2=top1+1時，棧滿；當top1=0時，棧1空；當top2=m+1時,棧2空.inttop1,top2,m,c[m+1];

//將其說明成全局變量Voidpush(x,i)Inti;elemtypex;{if(top2==top1+1)print(“overflow”);elseif(i==1)//對第一個棧進行入棧操作

{top1++;c[top1]=x;}else//對第二個棧進行入棧操作

{top2--;c[top2]=x;}}根據(jù)上述原理得到如下函數(shù)：函數(shù)pop如下：Voidpop(i)inti;{if(i==1)//對第一個棧進行出棧操作

if(top1==0)print(“棧1為空\n”）;elsetop1--;else//對第二個棧進行出棧操作

top2++;}*補充實驗1：

假設(shè)一個算術(shù)表達式中只包含圓括號，編寫一個判別表達式是否正確配對的函數(shù)correct(exp,tag);其中，exp為字符串類型的變量，表示被判別的表達式，tag為標志變量，標志是否正確配對。解：引進一個順序棧S，存放未配對的括號思想：掃描到‘（‘時，則入棧;當掃描到’）’時,

檢查當前棧頂元素是否是對應(yīng)的‘（’,

若是則退棧，否則，若棧為空及棧頂元素不是對應(yīng)的‘（’，都屬不配對;當整個算術(shù)表達式檢查完畢時棧為空，表示括號正確配對；否則也屬不配對。實現(xiàn)本題功能的函數(shù)如下：#definemaxsize100

//maxsize為算術(shù)表達式中最多字符個數(shù)

typedefstruct{charelem[maxsize];inttop;}stack;correct(charexp[maxsize],intflag){stackS//定義了一個順序棧SS.top=0,i=0;flag=1;//標識是否配對

while(exp[i]==‘\0’&&flag){if(exp[i]==‘(‘)//遇‘（’，則入棧

S.elem[top++]=exp[i];if(exp[i]==‘)’)//遇‘）’，則判斷棧頂情況

if(S.top==0)flag=0;elseif(s[top-1]==‘(‘)S.top--;elseflag=0;i++;}if(S.top>0)flag=0;//若棧不空，則不配對}例一、數(shù)制轉(zhuǎn)換例二、括號匹配的檢驗例三、行編輯程序問題例四、迷宮求解例五、表達式求值例六、實現(xiàn)遞歸3.3

棧的應(yīng)用舉例

NNdiv8Nmod8

13481684

168210

2125

202計算順序輸出順序例如：（1348)10=(2504)8

，其運算過程如下：

例一、數(shù)制轉(zhuǎn)換

（十進制數(shù)N到d進制數(shù)的轉(zhuǎn)換）

動畫播放(3-2-1)voidconversion(){InitStack(S);

scanf("%d",N);

while(N){

Push(S,N%8);//“余數(shù)”入棧

N=N/8;//“非零商”繼續(xù)運算

}

while(!StackEmpty(S)){

Pop(S,e);

printf("%d",e);

}}//conversionP48/算法3.1假設(shè)在表達式中（［］（））或［（［］［］）］等為正確的格式，［（］）或（［（）]或[（）］)均為不正確的格式。則檢驗括號是否匹配的方法可用“期待的急迫程度”這個概念來描述。例二、括號匹配的檢驗

分析可能出現(xiàn)的不匹配的情況:到來的右括弧并非是所“期待”的；例如：考慮下列括號序列：

[([][])]12345678到來的是“不速之客”；直到結(jié)束，也沒有到來所“期待”的括弧。這三種情況對應(yīng)到棧的操作即為：

1．和棧頂?shù)淖罄ɑ〔幌嗥ヅ洌?/p>

2．棧中并沒有左括弧等在那里

3．棧中還有左括弧沒有等到和它相匹配的右括弧。

算法的設(shè)計思想：1）凡出現(xiàn)左括弧，則進棧；2）凡出現(xiàn)右括弧，首先檢查棧是否空若棧空，則表明該“右括弧”多余，否則和棧頂元素比較，若相匹配，則“左括弧出?！?/p>

，否則表明不匹配。3）表達式檢驗結(jié)束時，若?？?，則表明表達式中匹配正確，否則表明“左括弧”有余。Statusmatching(string&exp){

intstate=1,i=0;

while(i<Length(exp)&&state){

switchofexp[i]{

case

左括弧:{Push(S,exp[i]);i++;break;}

case”)”:{

if(NOTStackEmpty(S)&&GetTop(S)==“(“{Pop(S,e);i++;}

else{state=0;}

break;}……}

if(StackEmpty(S)&&state)returnOK;…...如何實現(xiàn)？“每接受一個字符即存入存儲器”?

并不恰當！例三、行編輯程序問題

設(shè)立一個輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，現(xiàn)假設(shè)“#”為退格符，“@”為退行符。合理的作法是：假設(shè)從終端接受了這樣兩行字符：

whli##ilr#e（s#*s)

outcha@putchar(*s=#++);則實際有效的是下列兩行：

while(*s)

putchar(*s++);

while(ch!=EOF&&ch!='\n'){

switch(ch){

case'#':Pop(S,c);break;

case'@':ClearStack(S);break;//重置S為空棧

default

:Push(S,ch);break;

}ch=getchar();//從終端接收下一個字符

}ClearStack(S);//重置S為空棧

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

while(ch!=EOF){//EOF為全文結(jié)束符}將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)；P50/算法3.2通常用的是“窮舉求解”的方法例四、迷宮求解動畫3-3-1動畫3-3-2求迷宮路徑算法的基本思想是：若當前位置“可通”，則納入路徑，并繼續(xù)朝“下一位置”探索

若當前位置“不可通”，則應(yīng)順著“來的方向”退回到“前一通道塊”，然后朝著除"來向"之外的其他方向繼續(xù)探索；若四周“均無通路”，則將當前位置從路徑中刪除出去。設(shè)定當前位置的初值為入口位置；

do｛

若當前位置可通，

則｛將當前位置壓入棧頂；

若該位置是出口位置，則算法結(jié)束；

否則切換當前位置的東鄰方塊為新的當前位置；

｝

否則{

｝｝while(棧不空）；求迷宮中一條路徑的偽碼算法：

…

…詳見P52/算法3.2若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當前位置為:沿順時針方向旋轉(zhuǎn)

找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則｛刪去棧頂位置；//從路徑中刪去該通道塊

若棧不空，則重新測試新的棧頂位置，

直至找到一個可通的相鄰塊或出棧至棧空；｝若?？?，則表明迷宮沒有通路。

限于二元運算符的表達式定義:

表達式::=(操作數(shù))+(運算符)+(操作數(shù))

操作數(shù)::=簡單變量|表達式簡單變量::=標識符|無符號整數(shù)例五、表達式求值

在計算機中,表達式的三種標識方法：設(shè)

Exp=S1+

OP

+S2則稱

OP

+S1+S2

為前綴表示法

S1+

OP

+S2

為中綴表示法

S1+S2+

OP

為后綴表示法

例如:Exp=a

b

+

(c

d/e)

f前綴式:+

ab

c/def中綴式:a

b

+

c

d/e

f后綴式:ab

cde/

f

+結(jié)論:1）操作數(shù)之間的相對次序不變;2）運算符的相對次序不同;3）中綴式丟失了括弧信息，致使運算的次序不確定;4)前綴式的運算規(guī)則為:連續(xù)出現(xiàn)的兩個操作數(shù)和在它們之前且緊靠它們的運算符構(gòu)成一個最小表達式;5)后綴式的運算規(guī)則為:

運算符在式中出現(xiàn)的順序恰為表達式的運算順序;

每個運算符和在它之前出現(xiàn)

且緊靠它的兩個操作數(shù)構(gòu)成一個最小表達式。動畫3-3-4如何從后綴式求值？先找運算符，再找操作數(shù)例如：

ab

cde/

f

+a

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

f動畫3-3-6如何從原表達式求得后綴式？

每個運算符的運算次序要由它之后的一個運算符來定;在后綴式中，優(yōu)先數(shù)高的運算符領(lǐng)先于優(yōu)先數(shù)低的運算符。分析“原表達式”和“后綴式”中的運算符:原表達式:a+b

c

d/e

f

后綴式:abc

+de/f

為此我們先引進一個運算符的“優(yōu)先數(shù)”的概念。給每個運算符賦以一個優(yōu)先數(shù)的值，如下所列：

運算符#(+-X/**

優(yōu)先數(shù)-1011223

從原表達式求得后綴式的規(guī)律為：1)設(shè)立運算符棧；2)設(shè)表達式的結(jié)束符為“#”，

予設(shè)運算符棧的棧底為“#”；3)若當前字符是操作數(shù)，則直接發(fā)送給后綴式。4)若當前字符為運算符時，當其優(yōu)先數(shù)高于棧頂運算符，則進棧；5)否則，退出棧頂運算符發(fā)送給后綴式；

6)遇到左括號“（”時，將其壓進運算符棧；遇到右括號“）”時，當棧頂符號不是左括號時，反復(fù)將棧頂符號彈出送給后綴式。7)掃描到“#”時，將運算符棧頂符號依次彈出送給后綴表達式，直到棧頂為“#”號，轉(zhuǎn)換結(jié)束。

動畫3-3-7如：3*（7-2）#轉(zhuǎn)換成后綴表達式372-*的過程為：步驟后綴表達式運算符棧原表達式說明

1#3*（7-2）#23*(7-2)#*>#3#*(7-2)#4#*(7-2)#537#*(-2)#->(637#*(-2)#7372#*(-)#遇）

8372-#*(#)遇(9372-#*#10372-*##結(jié)束voidtransform(charsuffix[],charexp[]){InitStack(S);Push(S,

#

);p=exp;ch=*p;

while(!StackEmpty(S)){if(!IN(ch,OP))Pass(Suffix,ch);else{}

if(ch!=

#

){p++;ch=*p;}else{Pop(S,ch);Pass(Suffix,ch);}

}//while}//CrtExptree……switch(ch){

case

(

:Push(S,ch);break;

case

)

:

Pop(S,c);

while(c!=

(

)

{Pass(Suffix,c);Pop(S,c)}

break;

defult:while(Gettop(S,c)&&(precede(c,ch)))

{Pass(Suffix,c);Pop(S,c);}

if(ch!=

#

)Push(S,ch);

break;

}

//switch例六、實現(xiàn)遞歸

在程序設(shè)計中，經(jīng)常會碰到多個函數(shù)的嵌套調(diào)用。和匯編程序設(shè)計中主程序和子程序之間的鏈接和信息交換相類似，在高級語言編制的程序中，調(diào)用函數(shù)和被調(diào)用函數(shù)之間的鏈接和信息交換也是由編譯程序通過棧來實施的。將所有的實在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存；為被調(diào)用函數(shù)的局部變量分配存儲區(qū)；將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。

當在一個函數(shù)的運行期間調(diào)用另一個函數(shù)時，在運行該被調(diào)用函數(shù)之前，

需先完成三項任務(wù)：保存被調(diào)函數(shù)的計算結(jié)果；釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)；依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成下列三項任務(wù)：多個函數(shù)嵌套調(diào)用的規(guī)則是：此時的內(nèi)存管理實行“棧式管理”后調(diào)用先返回！例如：voidmain(){voida(){voidb(){………a();b();……}//main}//a}//bMain的數(shù)據(jù)區(qū)函數(shù)a的數(shù)據(jù)區(qū)函數(shù)b的數(shù)據(jù)區(qū)

再看P56遞歸工作棧：遞歸過程執(zhí)行過程中占用的數(shù)據(jù)區(qū)。遞歸工作記錄：每一層的遞歸參數(shù)合成一個記錄。當前活動記錄：棧頂記錄指示當前層的執(zhí)行情況。當前環(huán)境指針：遞歸工作棧的棧頂指針。遞歸函數(shù)執(zhí)行的過程可視為同一函數(shù)進行嵌套調(diào)用，例如：voidhanoi(intn,charx,chary,charz){//將塔座x上按直徑由小到大且至上而下編號為1至n//的n個圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。1if(n==1)2move(x,1,z);//將編號為１的圓盤從x移到z3else{4hanoi(n-1,x,z,y);//將x上編號為１至n-1的

//圓盤移到y(tǒng),z作輔助塔5move(x,n,z);//將編號為n的圓盤從x移到z6hanoi(n-1,y,x,z);//將y上編號為１至n-1的

//圓盤移到z,x作輔助塔7}8}漢諾塔問題61bca03abc返址nxyz62acb61abcvoidhanoi(intn,charx,chary,charz)1{2if(n==1)3move(x,1,z);4else{5hanoi(n-1,x,z,y);6move(x,n,z);7hanoi(n-1,y,x,z);8}9}運行見P57-58頁的圖3.7

81cab

漢諾塔問題動畫播放一、隊列的邏輯結(jié)構(gòu)定義及特性1.隊列是只允許在表的一端進行插入，而在表的另一端進行刪除操作的一種特殊線性表。允許插入的一端稱為“隊尾”，允許刪除的一端稱為“隊頭（首）”。2.隊列是“先進先出”（FIFO）或“后進后出”（LILO）的線性表a1a2a3…an隊首隊尾入隊出隊3.4隊列的類型定義ADTQueue{

數(shù)據(jù)對象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

約定其中a1

端為隊列頭，an

端為隊列尾基本操作：}

ADTQueue二、隊列的抽象數(shù)據(jù)類型定義1、構(gòu)造空隊列操作：DestroyQueue(&Q)ClearQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)EnQueue(&Q,e)DeQueue(&Q,&e)QueueTraverse(Q,visit())2、判隊空操作：InitQueue(&Q)3、取隊頭元素操作：4、入隊（插入）操作：5、出隊（刪除）操作：6、置隊空操作：7、求隊列長度操作：8、銷毀隊列操作：9、隊列遍歷操作：最常用的操作GetHead(Q,&e)

初始條件：Q為非空隊列。

操作結(jié)果：用e返回Q的隊頭元素。a1a2an……eEnQueue(&Q,e)

初始條件：隊列Q已存在。

操作結(jié)果：插入元素e為Q的新的隊尾元素。a1a2ane……

DeQueue(&Q,&e)

初始條件：Q為非空隊列。

操作結(jié)果：刪除Q的隊頭元素，并用e返回其值。a1a2an……

鏈隊列——鏈式映象順序與循環(huán)隊列

——順序映象3.5

隊列類型的實現(xiàn)鏈隊列一.鏈隊列(鏈式映象)的結(jié)構(gòu)描述二.鏈隊列基本操作的實現(xiàn)

typedefstructQNode{//結(jié)點類型

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;typedefstruct{//鏈隊列類型

QueuePtrfront;//隊頭指針

QueuePtrrear;//隊尾指針}LinkQueue;LinkQueueQ;一.鏈隊列(鏈式映象)的結(jié)構(gòu)描述a1∧an…Q.frontQ.rearQ.frontQ.rear∧空隊列鏈隊的隊空條件：Q.front=Q.rear1.構(gòu)造一個空隊列InitQueue(&Q)：操作思路：1）用malloc標準函數(shù)分配一個適當大小的空間作為隊列的頭結(jié)點，并使隊頭、隊尾指針指向它；2）若分配空間成功則置頭結(jié)點的指針域為空，否則結(jié)束算法。Q.front=Q.rear=(QueuePtr)malloc(sizeof(Qnode));Q.front->next=NULL;二.鏈隊列基本操作的實現(xiàn)P62

StatusInitQueue(LinkQueue&Q){//構(gòu)造一個空隊列Q

returnOK;}Q.front=Q.rear=(QueuePtr)malloc(sizeof(Qnode));

//分配隊的表頭結(jié)點空間，并使隊頭、隊尾指針指向它。if(!Q.front)exit(OVERFLOW);//存儲分配失敗Q.front->next=NULL;P622、鏈隊列的插入操作：EnQueue(Q,e)：1）產(chǎn)生新的結(jié)點e，并使p指針指向它；2）將新結(jié)點插入鏈隊的尾部（修改鏈）。p=(QueuePtr)malloc(sizeof(QNode));P->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;操作思路：要求：∧an…Q.frontQ.rear插入元素e為Q的新的隊尾元素e∧pP62

StatusEnQueue(LinkQueue&Q,QElemTypee){//插入元素e為Q的新的隊尾元素returnOK;}p=(QueuePtr)malloc(sizeof(QNode));

if(!p)exit(OVERFLOW);//存儲分配失敗

p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;P623、鏈隊列的刪除操作：DeQueue(&Q，&e)：1）若隊列空，則結(jié)束算法；2）若隊列非空，則將隊頭元素刪除，并用e保留其值。if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;操作思路：要求：刪除隊首元素，并用e保留其值；∧an…Q.frontQ.reara1a2P4)釋放空間：free(p);算法如下：3)若刪除的是隊尾元素，則修改隊尾指針I(yè)f(Q.rear==p)Q.rear=Q.front;

StatusDeQueue(LinkQueue&Q,QElemType&e){//若隊列不空，則刪除Q的隊頭元素，

//用e返回其值，并返回OK；否則返回ERROR

}if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);

returnOK;P62一、順序與循環(huán)隊列的結(jié)構(gòu)描述順序與循環(huán)隊列二、循環(huán)隊列基本操作的實現(xiàn)#defineMAXQSIZE100//最大隊列長度

typedefstruct{QElemType*base;//動態(tài)分配存儲空間

intfront;//頭指針，若隊列不空，

//指向隊列頭元素

intrear;//尾指針，若隊列不空，指向

//隊列尾元素的下一個位置

}SqQueue;QElemTypedata[MAXQSIZE];靜態(tài)存儲空間一、順序與循環(huán)隊列的結(jié)構(gòu)描述SqQueueQ;Q.baseQ.frontQ.rear

空隊列Q.baseQ.frontQ.rear序號值：012345Q.front=Q.rearQ.rear=MAXQSIZE假溢出現(xiàn)象入隊EnQueue(&Q,e):

Q.base[Q.rear++]=e;出隊DeQueue(&Q,e):e=Q.base[Q.front++];順序隊空條件：順序隊滿條件：ea1a2a3a4a5循環(huán)隊列：

將順序隊列看成是首尾相聯(lián)的隊列。3-3-13假設(shè)：MAXQSIZE=6054321Q.frontQ.reara1a2a3a4a5循環(huán)隊空條件：循環(huán)隊滿條件：Q.front=Q.rearQ.front=Q.rear隊空與隊滿的條件相同，無法判斷，怎么辦？a62、少用一個元素空間：如下圖循環(huán)隊空條件：循環(huán)隊滿條件：Q.front=Q.rear（Q.rear+1）%MAXQSIZE=Q.front1、設(shè)一個標志位以區(qū)分隊列是“空”，還是“滿”；處理方法有兩種：054321Q.frontQ.reara1a2a3a4a5空1.構(gòu)造一個空循環(huán)隊列InitQ