第3章棧和隊(duì)列

1、第第3章章 棧和隊(duì)列棧和隊(duì)列 3.1 棧棧 3.2 隊(duì)列隊(duì)列 本章小結(jié)本章小結(jié) 棧棧是一種只能在一端進(jìn)行插入或刪除操作的線性表。是一種只能在一端進(jìn)行插入或刪除操作的線性表。表中允許進(jìn)行插入、刪除操作的一端稱為表中允許進(jìn)行插入、刪除操作的一端稱為棧頂棧頂。 棧頂?shù)漠?dāng)前位置是動(dòng)態(tài)的，棧頂?shù)漠?dāng)前位置由一個(gè)稱棧頂?shù)漠?dāng)前位置是動(dòng)態(tài)的，棧頂?shù)漠?dāng)前位置由一個(gè)稱為棧頂指針的位置指示器指示。表的另一端稱為為棧頂指針的位置指示器指示。表的另一端稱為棧底棧底。 當(dāng)棧中沒有數(shù)據(jù)元素時(shí)，稱為空棧。當(dāng)棧中沒有數(shù)據(jù)元素時(shí)，稱為空棧。 棧的插入操作通常稱為進(jìn)?；蛉霔?，棧的刪除操作通棧的插入操作通常稱為進(jìn)?；蛉霔?，棧的刪除操作

2、通常稱為退?；虺鰲！３７Q為退?；虺鰲！?.1.1 棧的定義棧的定義 3.1 棧棧 棧頂棧頂棧底棧底出棧出棧進(jìn)棧進(jìn)棧棧示意圖棧示意圖棧的主要特點(diǎn)是棧的主要特點(diǎn)是“后進(jìn)先出后進(jìn)先出”，即后進(jìn)棧的元素先出，即后進(jìn)棧的元素先出棧。棧也稱為后進(jìn)先出表。棧。棧也稱為后進(jìn)先出表。思考題：思考題：棧和線性表有什么不同？棧和線性表有什么不同？ 例例3.1 設(shè)有設(shè)有4個(gè)元素個(gè)元素a、b、c、d進(jìn)棧，給出它們所有可進(jìn)棧，給出它們所有可能的出棧次序。能的出棧次序。 解：解：所有可能的出棧次序如下所有可能的出棧次序如下: abcd abdc acbd acdb adcb bacd badc bcad bcda bdca

3、 cbad cbda cdba dcbadcba 例例3.2 設(shè)一個(gè)棧的輸入序列為設(shè)一個(gè)棧的輸入序列為A,B,C,D，則借助一個(gè)棧，則借助一個(gè)棧所得到的輸出序列不可能是所得到的輸出序列不可能是 。(A) A,B,C,D(B) D,C,B,A (C) A,C,D,B(D) D,A,B,C 解：解：可以簡(jiǎn)單地推算，得容易得出可以簡(jiǎn)單地推算，得容易得出D,A,B,C是不可能的，是不可能的，因?yàn)橐驗(yàn)镈先出來，說明先出來，說明A,B,C,D均在棧中，按照入棧順序，在均在棧中，按照入棧順序，在棧中順序應(yīng)為棧中順序應(yīng)為D,C,B,A，出棧的順序只能是，出棧的順序只能是D,C,B,A。所以。所以本題答案為本題

4、答案為D。 例例3.3 已知一個(gè)棧的進(jìn)棧序列是已知一個(gè)棧的進(jìn)棧序列是1,2,3,n，其輸出序列是，其輸出序列是p1,p2,pn，若，若p1=n，則，則pi的值的值 。(A) i (B) n- -i (C) n- -i+1 (D) 不確定不確定 解：解：當(dāng)當(dāng)p1=n時(shí)，輸出序列必是時(shí)，輸出序列必是n,n- -1,3,2,1，則有，則有: p2=n-1, p3=n-2, , pn=1推導(dǎo)出推導(dǎo)出pi=n- -i+1,所以本題答案為所以本題答案為C。 例例3.4 設(shè)設(shè)n個(gè)元素進(jìn)棧序列是個(gè)元素進(jìn)棧序列是1,2,3,n，其輸出序列是，其輸出序列是p1,p2,pn，若，若p1=3，則，則p2的值的值 。(

5、A) 一定是一定是2(B) 一定是一定是1(C) 不可能是不可能是1 (D) 以上都不對(duì)以上都不對(duì) 解：解：當(dāng)當(dāng)p1=3時(shí)，說明時(shí)，說明1,2,3先進(jìn)棧，立即出棧先進(jìn)棧，立即出棧3，然后可，然后可能出棧，即為能出棧，即為2，也可能，也可能4或后面的元素進(jìn)棧，再出棧。因此，或后面的元素進(jìn)棧，再出棧。因此，p2可能是可能是2，也可能是，也可能是4,n，但一定不能是，但一定不能是1。所以本題答。所以本題答案為案為C。213.4棧的幾種基本運(yùn)算如下棧的幾種基本運(yùn)算如下: InitStack(&s)：初始化棧。構(gòu)造一個(gè)空棧初始化棧。構(gòu)造一個(gè)空棧s。 DestroyStack(&s)：銷毀

6、棧。釋放棧銷毀棧。釋放棧s占用的存儲(chǔ)空間。占用的存儲(chǔ)空間。 StackEmpty(s)：判斷棧是否為空判斷棧是否為空:若棧若棧s為空，則返回為空，則返回真；否則返回假。真；否則返回假。 Push(&S,e)：進(jìn)棧。將元素進(jìn)棧。將元素e插入到棧插入到棧s中作為棧頂元中作為棧頂元素。素。 Pop(&s,&e)：出棧。從棧出棧。從棧s中退出棧頂元素，并將其中退出棧頂元素，并將其值賦給值賦給e。 GetTop(s,&e)：取棧頂元素。返回當(dāng)前的棧頂元素，取棧頂元素。返回當(dāng)前的棧頂元素，并將其值賦給并將其值賦給e。3.1.2 棧的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)棧的順序存儲(chǔ)結(jié)

7、構(gòu)及其基本運(yùn)算實(shí)現(xiàn) 假設(shè)棧的元素個(gè)數(shù)最大不超過正整數(shù)假設(shè)棧的元素個(gè)數(shù)最大不超過正整數(shù)MaxSize，所有的元，所有的元素都具有同一數(shù)據(jù)類型素都具有同一數(shù)據(jù)類型ElemType，則可用下列方式來定義棧，則可用下列方式來定義棧類型類型SqStack: typedef struct ElemType dataMaxSize； int top；/棧頂指針棧頂指針 SqStack；順序棧順序棧4要素：要素： ?？諚l件棧空條件：top=-1 棧滿條件：棧滿條件：top=MaxSize-1 進(jìn)棧進(jìn)棧e操作：操作：top+; 將將e放在放在top處處 退棧操作：退棧操作：從從top處取出元素處取出元素e; t

8、op-;例如：例如： 在順序棧中實(shí)現(xiàn)棧的基本運(yùn)算算法。在順序棧中實(shí)現(xiàn)棧的基本運(yùn)算算法。 （1）初始化棧）初始化棧initStack(&s) 建立一個(gè)新的空棧建立一個(gè)新的空棧s,s,實(shí)際上是將棧頂指針指向?qū)嶋H上是將棧頂指針指向-1-1即可。對(duì)應(yīng)算即可。對(duì)應(yīng)算法如下法如下: : void InitStack(SqStack *&s) s=(SqStack *)malloc(sizeof(SqStack); s-top=-1; （2）銷毀棧）銷毀棧ClearStack(&s) 釋放棧釋放棧s占用的存儲(chǔ)空間。對(duì)應(yīng)算法如下占用的存儲(chǔ)空間。對(duì)應(yīng)算法如下: void DestroyS

9、tack(SqStack *&s)free(s); （3）判斷棧是否為空）判斷棧是否為空StackEmpty(s) 棧棧S為空的條件是為空的條件是s- -top=-=-1。對(duì)應(yīng)算法如下。對(duì)應(yīng)算法如下: bool StackEmpty(SqStack *s)return(s-top=-1); （4）進(jìn)棧）進(jìn)棧Push(&s,e) 在棧不滿的條件下，先將棧指針增在棧不滿的條件下，先將棧指針增1，然后在該位置上插入，然后在該位置上插入元素元素e。對(duì)應(yīng)算法如下。對(duì)應(yīng)算法如下: bool Push(SqStack *&s,ElemType e) if (s-top=MaxSize

10、-1) /棧滿的情況，即棧上溢出棧滿的情況，即棧上溢出return false; s-top+; /棧頂指針增棧頂指針增1 s-datas-top=e; /元素元素e放在棧頂指針處放在棧頂指針處 return true; （5）出棧）出棧Pop(&s,&e) 在棧不為空的條件下，先將棧頂元素賦給在棧不為空的條件下，先將棧頂元素賦給e，然后將棧指，然后將棧指針減針減1。對(duì)應(yīng)算法如下。對(duì)應(yīng)算法如下: bool Pop(SqStack *&s,ElemType &e) if (s-top=-1)/棧為空的情況，即棧下溢出棧為空的情況，即棧下溢出return false

11、; e=s-datas-top;/取棧頂指針元素的元素取棧頂指針元素的元素 s-top-;/棧頂指針減棧頂指針減1 return true; （6）取棧頂元素）取棧頂元素GetTop(s) 在棧不為空的條件下，將棧頂元素賦給在棧不為空的條件下，將棧頂元素賦給e。對(duì)應(yīng)算法如下。對(duì)應(yīng)算法如下:bool GetTop(SqStack *s,ElemType &e) if (s-top=-1)/棧為空的情況，即棧下溢出棧為空的情況，即棧下溢出 return false; e=s-datas-top;/取棧頂指針元素的元素取棧頂指針元素的元素 return true; 例例3.4 編寫一個(gè)算法利

12、用順序棧判斷一個(gè)字符串是否是對(duì)編寫一個(gè)算法利用順序棧判斷一個(gè)字符串是否是對(duì)稱串。所謂稱串。所謂對(duì)稱串對(duì)稱串是指從左向右讀和從右向左讀的序列相同。是指從左向右讀和從右向左讀的序列相同。解：解：對(duì)于字符串對(duì)于字符串str，先將其所有元素進(jìn)棧。然后從頭開始，先將其所有元素進(jìn)棧。然后從頭開始掃描掃描str，并出棧元素，將兩者進(jìn)行比較，若不相同則返回，并出棧元素，將兩者進(jìn)行比較，若不相同則返回false。當(dāng)當(dāng)str掃描完畢仍沒有返回時(shí)返回掃描完畢仍沒有返回時(shí)返回true。實(shí)際上，從頭開始掃描。實(shí)際上，從頭開始掃描str是從左向右讀，出棧序列是從右向左讀，兩者相等說明該串是從左向右讀，出棧序列是從右向左讀

13、，兩者相等說明該串是對(duì)稱串。是對(duì)稱串。bool symmetry(ElemType str) int i; ElemType e; SqStack *st; InitStack(st);/初始化棧初始化棧 for (i=0;stri!=0;i+) /將串所有元素進(jìn)棧將串所有元素進(jìn)棧Push(st,stri);/元素進(jìn)棧元素進(jìn)棧 for (i=0;stri!=0;i+) Pop(st,e); /退棧元素退棧元素eif (stri!=e) /若若e與當(dāng)前串元素不同則不是對(duì)稱串與當(dāng)前串元素不同則不是對(duì)稱串 DestroyStack(st);/銷毀棧銷毀棧 return false; DestroyS

14、tack(st); /銷毀棧銷毀棧 return true;3.1.3 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn) 采用鏈?zhǔn)酱鎯?chǔ)的棧稱為鏈棧采用鏈?zhǔn)酱鎯?chǔ)的棧稱為鏈棧,這里采用單鏈表實(shí)現(xiàn)。這里采用單鏈表實(shí)現(xiàn)。 鏈棧的優(yōu)點(diǎn)是不存在棧滿上溢的情況。這里規(guī)定棧的所鏈棧的優(yōu)點(diǎn)是不存在棧滿上溢的情況。這里規(guī)定棧的所有操作都是在單鏈表的表頭進(jìn)行的，用帶頭節(jié)點(diǎn)的單鏈表有操作都是在單鏈表的表頭進(jìn)行的，用帶頭節(jié)點(diǎn)的單鏈表表示鏈棧，第一個(gè)數(shù)據(jù)節(jié)點(diǎn)是棧頂節(jié)點(diǎn)表示鏈棧，第一個(gè)數(shù)據(jù)節(jié)點(diǎn)是棧頂節(jié)點(diǎn),最后一個(gè)節(jié)點(diǎn)是棧最后一個(gè)節(jié)點(diǎn)是棧底節(jié)點(diǎn)。底節(jié)點(diǎn)。棧中元素自棧頂?shù)綏５滓来问菞Ｖ性刈詶ｍ數(shù)綏５滓来问?/p>

15、a1、a2、an。鏈棧示意圖鏈棧示意圖鏈棧的鏈棧的4要素：要素： ?？諚l件：?？諚l件：s-next=NULL 棧滿條件：棧滿條件：不考慮不考慮 進(jìn)棧進(jìn)棧e操作：操作：將包含將包含e的節(jié)點(diǎn)插入到頭節(jié)點(diǎn)之后的節(jié)點(diǎn)插入到頭節(jié)點(diǎn)之后 退棧操作：退棧操作：取出頭節(jié)點(diǎn)之后節(jié)點(diǎn)的元素并刪除之取出頭節(jié)點(diǎn)之后節(jié)點(diǎn)的元素并刪除之 映射 s a1 an a2 棧底節(jié)點(diǎn) 棧頂節(jié)點(diǎn) 頭節(jié)點(diǎn) 棧 a1,a2,ai,an 鏈棧中數(shù)據(jù)節(jié)點(diǎn)的類型鏈棧中數(shù)據(jù)節(jié)點(diǎn)的類型LiStack定義如下定義如下: typedef struct linknode ElemType data;/數(shù)據(jù)域數(shù)據(jù)域 struct linknode *ne

16、xt;/指針域指針域 LiStack;在鏈棧中，棧的基本運(yùn)算算法如下。在鏈棧中，棧的基本運(yùn)算算法如下。 （1）初始化棧）初始化棧initStack(&s) 建立一個(gè)空棧建立一個(gè)空棧s。實(shí)際上是創(chuàng)建鏈棧的頭節(jié)點(diǎn)。實(shí)際上是創(chuàng)建鏈棧的頭節(jié)點(diǎn),并將其并將其next域置為域置為NULL。對(duì)應(yīng)算法如下。對(duì)應(yīng)算法如下: svoid InitStack(LiStack *&s) s=(LiStack *)malloc(sizeof(LiStack); s-next=NULL; （2）銷毀棧）銷毀棧ClearStack(&s) 釋放棧釋放棧s s占用的全部存儲(chǔ)空間。對(duì)應(yīng)算法如下占用的全部

17、存儲(chǔ)空間。對(duì)應(yīng)算法如下: : void DestroyStack(LiStack *&s)LiStack *p=s,*q=s-next; while (q!=NULL) free(p);p=q;q=p-next; free(p); /此時(shí)此時(shí)p指向尾節(jié)點(diǎn)指向尾節(jié)點(diǎn),釋放其空間釋放其空間sa1a2anpq （3）判斷棧是否為空）判斷棧是否為空StackEmpty(s) 棧棧S為空的條件是為空的條件是s-next=NULL，即單鏈表中沒有數(shù)據(jù)，即單鏈表中沒有數(shù)據(jù)節(jié)點(diǎn)。對(duì)應(yīng)算法如下節(jié)點(diǎn)。對(duì)應(yīng)算法如下: sbool StackEmpty(LiStack *s) return(s-next=NU

18、LL); （4）進(jìn)棧）進(jìn)棧Push(&s,e) 將新數(shù)據(jù)節(jié)點(diǎn)插入到頭節(jié)點(diǎn)之后。對(duì)應(yīng)算法如下將新數(shù)據(jù)節(jié)點(diǎn)插入到頭節(jié)點(diǎn)之后。對(duì)應(yīng)算法如下: void Push(LiStack *&s,ElemType e) LiStack *p; p=(LiStack *)malloc(sizeof(LiStack); p-data=e;/新建元素新建元素e對(duì)應(yīng)的節(jié)點(diǎn)對(duì)應(yīng)的節(jié)點(diǎn)*p p-next=s-next;/插入插入*p節(jié)點(diǎn)作為開始節(jié)點(diǎn)節(jié)點(diǎn)作為開始節(jié)點(diǎn) s-next=p;sa1a2anpe （5）出棧）出棧Pop(&s,&e) 在棧不為空的條件下，將頭節(jié)點(diǎn)后繼數(shù)據(jù)節(jié)點(diǎn)的數(shù)據(jù)域賦

19、在棧不為空的條件下，將頭節(jié)點(diǎn)后繼數(shù)據(jù)節(jié)點(diǎn)的數(shù)據(jù)域賦給給e，然后將其刪除。對(duì)應(yīng)算法如下，然后將其刪除。對(duì)應(yīng)算法如下: bool Pop(LiStack *&s,ElemType &e) LiStack *p; if (s-next=NULL)/棧空的情況?？盏那闆rreturn false; p=s-next;/p指向開始節(jié)點(diǎn)指向開始節(jié)點(diǎn) e=p-data; s-next=p-next;/刪除刪除*p節(jié)點(diǎn)節(jié)點(diǎn) free(p);/釋放釋放*p節(jié)點(diǎn)節(jié)點(diǎn) return true;sa1a2an （6）取棧頂元素）取棧頂元素GetTop(s,e) 在棧不為空的條件下，將頭節(jié)點(diǎn)后繼數(shù)據(jù)節(jié)點(diǎn)的

20、數(shù)據(jù)域賦給在棧不為空的條件下，將頭節(jié)點(diǎn)后繼數(shù)據(jù)節(jié)點(diǎn)的數(shù)據(jù)域賦給e。對(duì)應(yīng)算法如下對(duì)應(yīng)算法如下: bool GetTop(LiStack *s,ElemType &e) if (s-next=NULL)/?？盏那闆r?？盏那闆rreturn false; e=s-next-data; return true;sa1a2an 例例3.5 編寫一個(gè)算法判斷輸入的表達(dá)式中括號(hào)是否配編寫一個(gè)算法判斷輸入的表達(dá)式中括號(hào)是否配對(duì)（假設(shè)只含有左、右圓括號(hào)）。對(duì)（假設(shè)只含有左、右圓括號(hào)）。 解解:該算法在表達(dá)式括號(hào)配對(duì)時(shí)返回該算法在表達(dá)式括號(hào)配對(duì)時(shí)返回true，否則返回，否則返回false。設(shè)置一個(gè)順序棧。設(shè)

21、置一個(gè)順序棧St，掃描表達(dá)式，掃描表達(dá)式exp，遇到左括號(hào)時(shí)，遇到左括號(hào)時(shí)進(jìn)棧；遇到右括號(hào)時(shí)：若棧頂為左括號(hào)，則出棧，否則返進(jìn)棧；遇到右括號(hào)時(shí)：若棧頂為左括號(hào)，則出棧，否則返回回false。當(dāng)表達(dá)式掃描完畢，棧為空時(shí)返回。當(dāng)表達(dá)式掃描完畢，棧為空時(shí)返回true；否則返；否則返回回false。bool Match(char exp,int n) int i=0; char e; bool match=true; SqStack *st; InitStack(st); /初始化棧初始化棧 while (in & match) /掃描掃描exp中所有字符中所有字符 if (expi=() /

22、當(dāng)前字符為左括號(hào)當(dāng)前字符為左括號(hào),將其進(jìn)棧將其進(jìn)棧 Push(st,expi);else if (expi=) /當(dāng)前字符為右括號(hào)當(dāng)前字符為右括號(hào) if (GetTop(st,e)=true) if (e!=() /棧頂元素不為棧頂元素不為(時(shí)表示不匹配時(shí)表示不匹配 match=false;else Pop(st,e); /將棧頂元素出棧將棧頂元素出棧 else match=false; /無法取棧頂元素時(shí)表示不匹配無法取棧頂元素時(shí)表示不匹配i+; /繼續(xù)處理其他字符繼續(xù)處理其他字符 if (!StackEmpty(st) /棧不空時(shí)表示不匹配棧不空時(shí)表示不匹配match=false; Des

23、troyStack(st); /銷毀棧銷毀棧 return match; 問題描述問題描述 1. 表達(dá)式求值表達(dá)式求值3.1.4 棧的應(yīng)用棧的應(yīng)用 這里限定的表達(dá)式求值問題是：用戶輸入一個(gè)包這里限定的表達(dá)式求值問題是：用戶輸入一個(gè)包含含“+”、“-”、“*”、“/”、正整數(shù)和圓括號(hào)的合法數(shù)、正整數(shù)和圓括號(hào)的合法數(shù)學(xué)表達(dá)式，計(jì)算該表達(dá)式的運(yùn)算結(jié)果。學(xué)表達(dá)式，計(jì)算該表達(dá)式的運(yùn)算結(jié)果。 數(shù)據(jù)組織數(shù)據(jù)組織 算術(shù)表達(dá)式算術(shù)表達(dá)式exp采用字符數(shù)組表示，其中只含有采用字符數(shù)組表示，其中只含有“+”、“-”、“*”、“/”、正整數(shù)和圓括號(hào)。、正整數(shù)和圓括號(hào)。為了方便，假設(shè)該表達(dá)式都是合法的數(shù)學(xué)表達(dá)式，例為了

24、方便，假設(shè)該表達(dá)式都是合法的數(shù)學(xué)表達(dá)式，例如，如，exp=1+2*(4+12)；在設(shè)計(jì)相關(guān)算法中用到棧，這里；在設(shè)計(jì)相關(guān)算法中用到棧，這里采用采用順序棧存儲(chǔ)結(jié)構(gòu)順序棧存儲(chǔ)結(jié)構(gòu)。 在程序語言中，運(yùn)算符位于兩個(gè)操作數(shù)中間的表達(dá)式稱在程序語言中，運(yùn)算符位于兩個(gè)操作數(shù)中間的表達(dá)式稱為為中綴表達(dá)式中綴表達(dá)式。例如：。例如： 1+2*3 就是一個(gè)中綴表達(dá)式就是一個(gè)中綴表達(dá)式,中綴表達(dá)式是最常用的一種表達(dá)式中綴表達(dá)式是最常用的一種表達(dá)式方式。對(duì)中綴表達(dá)式的運(yùn)算一般遵循方式。對(duì)中綴表達(dá)式的運(yùn)算一般遵循“先乘除，后加減，從先乘除，后加減，從左到右計(jì)算，先括號(hào)內(nèi)，后括號(hào)外左到右計(jì)算，先括號(hào)內(nèi)，后括號(hào)外”的規(guī)則。因

25、此中綴表達(dá)的規(guī)則。因此中綴表達(dá)式不僅要依賴運(yùn)算符優(yōu)先級(jí)式不僅要依賴運(yùn)算符優(yōu)先級(jí),而且還要處理括號(hào)。而且還要處理括號(hào)。 設(shè)計(jì)運(yùn)算算法設(shè)計(jì)運(yùn)算算法 表達(dá)式的三種標(biāo)識(shí)方法：表達(dá)式的三種標(biāo)識(shí)方法：設(shè)設(shè) Exp = S1 + OP + S2 則稱則稱 OP + S1 + S2 為前綴表示法為前綴表示法 S1 + OP + S2 為中綴表示法為中綴表示法 S1 + S2 + OP 為后綴表示法為后綴表示法 例如例如: Exp = a b + (c d / e) f 前綴式前綴式: + a b c / d e f 中綴式中綴式: a b + c d / e f 后綴式后綴式: a b c d e / f +

26、 經(jīng)過分析，表達(dá)式的三種表示法有以下特點(diǎn)經(jīng)過分析，表達(dá)式的三種表示法有以下特點(diǎn): 操作數(shù)之間的相對(duì)次序不變；操作數(shù)之間的相對(duì)次序不變； 運(yùn)算符的相對(duì)次序不同；運(yùn)算符的相對(duì)次序不同； 若中綴式丟失括號(hào)信息，則運(yùn)算的次序不確定若中綴式丟失括號(hào)信息，則運(yùn)算的次序不確定; 后綴表達(dá)式中已考慮了運(yùn)算符的優(yōu)先級(jí)，沒有括號(hào)，后綴表達(dá)式中已考慮了運(yùn)算符的優(yōu)先級(jí)，沒有括號(hào)，只有操作數(shù)和運(yùn)算符。只有操作數(shù)和運(yùn)算符。算術(shù)表達(dá)式求值過程是：算術(shù)表達(dá)式求值過程是： STEP 1：先將算術(shù)表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。先將算術(shù)表達(dá)式轉(zhuǎn)換成后綴表達(dá)式。 STEP 2：然后對(duì)該后綴表達(dá)式求值。然后對(duì)該后綴表達(dá)式求值。a + b c

27、 d / e f 0exppostexp+a b cd ef運(yùn)算符棧運(yùn)算符棧chchchchchch -/ Step1假設(shè)用假設(shè)用exp字符數(shù)組存儲(chǔ)滿足前面條件的算術(shù)表達(dá)式，其字符數(shù)組存儲(chǔ)滿足前面條件的算術(shù)表達(dá)式，其對(duì)應(yīng)后綴表達(dá)式存放在字符數(shù)組對(duì)應(yīng)后綴表達(dá)式存放在字符數(shù)組postexp中。在將算術(shù)表達(dá)式中。在將算術(shù)表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的過程中用一個(gè)字符數(shù)組轉(zhuǎn)換成后綴表達(dá)式的過程中用一個(gè)字符數(shù)組op作為棧。作為棧。運(yùn)算符運(yùn)算符=(+-*/)左：左：lpri(ch)0133556右：右：rpri(ch)0622441運(yùn)算符的優(yōu)先級(jí)運(yùn)算符的優(yōu)先級(jí) 123：左運(yùn)算符在棧中，應(yīng)和：左運(yùn)算符在棧中，應(yīng)和

28、棧頂運(yùn)算符比較，先出棧先運(yùn)算，后棧頂運(yùn)算符比較，先出棧先運(yùn)算，后出棧后運(yùn)算。出棧后運(yùn)算。在棧中的運(yùn)算符呈現(xiàn)的優(yōu)先級(jí)在棧中的運(yùn)算符呈現(xiàn)的優(yōu)先級(jí)中綴表達(dá)式中綴表達(dá)式exp后綴后綴表達(dá)式表達(dá)式postexp exp：sopch exp：ch sop 左運(yùn)算符 右運(yùn)算符 = 優(yōu)先級(jí)比較 op 棧 初始化運(yùn)算符棧初始化運(yùn)算符棧op;將將=進(jìn)棧進(jìn)棧;從從exp讀取字符讀取字符ch;while (ch!=0) if (ch不為運(yùn)算符不為運(yùn)算符)將后續(xù)的所有數(shù)字均依次存放到將后續(xù)的所有數(shù)字均依次存放到postexp中中,并以字符并以字符#標(biāo)志數(shù)值串結(jié)束標(biāo)志數(shù)值串結(jié)束; else switch(Precede(

29、op棧頂運(yùn)算符棧頂運(yùn)算符,ch) case : /棧頂運(yùn)算符應(yīng)先執(zhí)行棧頂運(yùn)算符應(yīng)先執(zhí)行,所以出棧并存放到所以出棧并存放到postexp中中 退棧運(yùn)算符并將其存放到退棧運(yùn)算符并將其存放到postexp中中; break; 若字符串若字符串exp掃描完畢掃描完畢,則將運(yùn)算符棧則將運(yùn)算符棧op中中=之前的所有運(yùn)算符依次出棧并存放到之前的所有運(yùn)算符依次出棧并存放到postexp中。最后得到后綴表達(dá)式中。最后得到后綴表達(dá)式postexp; 對(duì)于表達(dá)式對(duì)于表達(dá)式“(56-20)/(4+2)”,其轉(zhuǎn)換成后綴表達(dá)式的過程其轉(zhuǎn)換成后綴表達(dá)式的過程 如下：如下：exp操作過程操作過程oppostexp先將先將=進(jìn)

30、棧進(jìn)棧=(56-20)/(4+2)遇到遇到ch為為“(”,將此括號(hào)進(jìn)棧將此括號(hào)進(jìn)棧op。( 56-20)/(4+2)遇到遇到ch為數(shù)字為數(shù)字,將將56存入存入postexp中中,并插入一個(gè)字符并插入一個(gè)字符“#”。(56#-20)/(4+2)遇到遇到ch為為“-”,由于由于op中中“(”以前沒以前沒有字符有字符,則直接將則直接將ch進(jìn)棧進(jìn)棧op中。中。(-56#20)/(4+2)遇到遇到ch為數(shù)字為數(shù)字,將將20#存入數(shù)組存入數(shù)組exp中。中。(-56#20#exp操作過程操作過程oppostexp)/(4+2)遇到遇到ch為為“)”,則將棧則將棧op中中“(”以前的以前的字符依次出棧并存入字

31、符依次出棧并存入postexp中中,然后將然后將“(”刪除。刪除。 56#20#-/(4+2)遇到遇到ch為為“/”,將將將將ch進(jìn)棧進(jìn)棧op中。中。/56#20#-(4+2)遇到遇到ch為為“(”,將此括號(hào)進(jìn)棧將此括號(hào)進(jìn)棧op中。中。/(56#20#-4+2)遇到遇到ch為數(shù)字為數(shù)字,將將4#存入數(shù)組存入數(shù)組postexp中。中。/(56#20#-4#exp操作過程操作過程oppostexp+2)遇到遇到ch為為“+”,由于由于op棧頂運(yùn)算符為棧頂運(yùn)算符為“(”,則直接將則直接將ch進(jìn)棧進(jìn)棧op中。中。/(+56#20#-4#2)遇到遇到ch為數(shù)字為數(shù)字,將將2#存入存入postexp中。中

32、。/(+56#20#-4#2#)遇到遇到ch為為“)”,則將棧則將棧op中中“(”以前的字以前的字符依次出棧并存放到符依次出棧并存放到postexp中中,然后將然后將“(”出棧。出棧。/56#20#-4#2#+ str掃描完畢掃描完畢,則將棧則將棧op中的所有運(yùn)算符依中的所有運(yùn)算符依次彈出并存放到次彈出并存放到postexp中中,得到后綴表達(dá)得到后綴表達(dá)式。式。 56#20#-4#2#+/struct /設(shè)定運(yùn)算符優(yōu)先級(jí)設(shè)定運(yùn)算符優(yōu)先級(jí)char ch; /運(yùn)算符運(yùn)算符 int pri; /優(yōu)先級(jí)優(yōu)先級(jí) lpri=,0,(,1,*,5,/,5,+,3, -,3,),6, rpri=,0,(,6,

33、*,4,/,4,+,2, -,2,),1;int leftpri(char op) /求左運(yùn)算符求左運(yùn)算符op的優(yōu)先級(jí)的優(yōu)先級(jí) int i; for (i=0;iMaxOp;i+)if (lprii.ch=op) return lprii.pri;int rightpri(char op) /求右運(yùn)算符求右運(yùn)算符op的優(yōu)先級(jí)的優(yōu)先級(jí) int i; for (i=0;iMaxOp;i+)if (rprii.ch=op) return rprii.pri;將算術(shù)表達(dá)式將算術(shù)表達(dá)式exp轉(zhuǎn)換成后綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式postexp:bool InOp(char ch) /判斷判斷ch是否為運(yùn)算符是

34、否為運(yùn)算符 if (ch=( | ch=) | ch=+ | ch=- | ch=* | ch=/)return true; elsereturn false;int Precede(char op1,char op2) /op1和和op2運(yùn)算符優(yōu)先級(jí)的運(yùn)算符優(yōu)先級(jí)的比較結(jié)果比較結(jié)果 if (leftpri(op1)=rightpri(op2)return 0; else if (leftpri(op1)=0 & *exp=0 & ch(xe,ye) int i,j,k,di,find; StType st;/定義棧定義棧st st.top=-1;/初始化棧頂指針初始化棧頂指針

35、 st.top+;/初始方塊進(jìn)棧初始方塊進(jìn)棧 st.datast.top.i=xi; st.datast.top.j=yi; st.datast.top.di=-1; mgxiyi=-1; while (st.top-1)/棧不空時(shí)循環(huán)棧不空時(shí)循環(huán) i=st.datast.top.i;j=st.datast.top.j;di=st.datast.top.di;/取棧頂方塊取棧頂方塊if (i=xe & j=ye)/找到了出口找到了出口,輸出路徑輸出路徑 printf(迷宮路徑如下迷宮路徑如下:n); for (k=0;k=st.top;k+) printf(t(%d,%d),st.da

36、tak.i,st.datak.j); if (k+1)%5=0)/每輸出每每輸出每5個(gè)方塊后換一行個(gè)方塊后換一行printf(n); printf(n); return true;/找到一條路徑后返回找到一條路徑后返回true find=0; while (difront=q-rear=-1;（2）銷毀隊(duì)列）銷毀隊(duì)列DestroyQueue(q)釋放隊(duì)列釋放隊(duì)列q占用的存儲(chǔ)空間。占用的存儲(chǔ)空間。void DestroyQueue(SqQueue *&q) free(q);（3）判斷隊(duì)列是否為空）判斷隊(duì)列是否為空QueueEmpty(q) 若隊(duì)列若隊(duì)列q滿足滿足q-front=q-rea

37、r條件，則返回條件，則返回true；否則；否則返回返回false。bool QueueEmpty(SqQueue *q) return(q-front=q-rear);（4）進(jìn)隊(duì)列）進(jìn)隊(duì)列enQueue(q,e) 在隊(duì)列不滿的條件下，先將隊(duì)尾指針在隊(duì)列不滿的條件下，先將隊(duì)尾指針rear循環(huán)增循環(huán)增1，然后將，然后將元素添加到該位置。元素添加到該位置。bool enQueue(SqQueue *&q,ElemType e) if (q-rear=MaxSize-1)/隊(duì)滿上溢出隊(duì)滿上溢出return false;q-rear+;q-dataq-rear=e;return true;（5）

38、出隊(duì)列）出隊(duì)列deQueue(q,e) 在隊(duì)列在隊(duì)列q不為空的條件下，將隊(duì)首指針不為空的條件下，將隊(duì)首指針front循環(huán)增循環(huán)增1，并，并將該位置的元素值賦給將該位置的元素值賦給e。bool deQueue(SqQueue *&q,ElemType &e) if (q-front=q-rear)/隊(duì)空下溢出隊(duì)空下溢出return false; q-front+; e=q-dataq-front; return true; 用用rear=MaxSize-1作為隊(duì)滿的條件有缺陷。可能隊(duì)列為空，作為隊(duì)滿的條件有缺陷?？赡荜?duì)列為空，但仍滿足該條件。這時(shí)進(jìn)隊(duì)時(shí)出現(xiàn)但仍滿足該條件。這時(shí)進(jìn)隊(duì)

39、時(shí)出現(xiàn)“上溢出上溢出”，這種溢出并不，這種溢出并不是真正的溢出，在是真正的溢出，在data數(shù)組中存在可以存放元素的空位置，所數(shù)組中存在可以存放元素的空位置，所以這是一種以這是一種假溢出假溢出。 為了能夠充分地使用數(shù)組中的存儲(chǔ)空間為了能夠充分地使用數(shù)組中的存儲(chǔ)空間,把數(shù)組的前端和后把數(shù)組的前端和后端連接起來，形成一個(gè)環(huán)形的順序表，即把存儲(chǔ)隊(duì)列元素的表端連接起來，形成一個(gè)環(huán)形的順序表，即把存儲(chǔ)隊(duì)列元素的表從邏輯上看成一個(gè)環(huán)，稱為從邏輯上看成一個(gè)環(huán)，稱為環(huán)形隊(duì)列或循環(huán)隊(duì)列環(huán)形隊(duì)列或循環(huán)隊(duì)列。2. 環(huán)形隊(duì)中實(shí)現(xiàn)隊(duì)列的基本運(yùn)算環(huán)形隊(duì)中實(shí)現(xiàn)隊(duì)列的基本運(yùn)算環(huán)形隊(duì)的進(jìn)隊(duì)和出隊(duì)操作示意圖環(huán)形隊(duì)的進(jìn)隊(duì)和出隊(duì)操作示

40、意圖隊(duì)空條件隊(duì)空條件：front=rear隊(duì)滿條件隊(duì)滿條件：(rear+1)%MaxSize=front進(jìn)隊(duì)進(jìn)隊(duì)e操作操作：rear=(rear+1)%MaxSize; 將將e放在放在rear處處出隊(duì)操作出隊(duì)操作：front=(front+1)%MaxSize;取出取出front處元素處元素e; 環(huán)形隊(duì)列的四要素：環(huán)形隊(duì)列的四要素： 在環(huán)形隊(duì)列中，實(shí)現(xiàn)隊(duì)列的基本運(yùn)算算法如下。在環(huán)形隊(duì)列中，實(shí)現(xiàn)隊(duì)列的基本運(yùn)算算法如下。（1）初始化隊(duì)列）初始化隊(duì)列InitQueue(q) 構(gòu)造一個(gè)空隊(duì)列構(gòu)造一個(gè)空隊(duì)列q。將。將front和和rear指針均設(shè)置成初始狀指針均設(shè)置成初始狀態(tài)即態(tài)即0值。值。void I

41、nitQueue(SqQueue *&q) q=(SqQueue *)malloc (sizeof(SqQueue); q-front=q-rear=0; （2）銷毀隊(duì)列）銷毀隊(duì)列ClearQueue(&q) 釋放隊(duì)列釋放隊(duì)列q占用的存儲(chǔ)空間。對(duì)應(yīng)算法如下占用的存儲(chǔ)空間。對(duì)應(yīng)算法如下: void DestroyQueue(SqQueue *&q)free(q);（3）判斷隊(duì)列是否為空）判斷隊(duì)列是否為空QueueEmpty(q) 若隊(duì)列若隊(duì)列q滿足滿足q-front=q-rear條件，則返回條件，則返回true；否則；否則返回返回false。bool QueueEmpty

42、(SqQueue *q) return(q-front=q-rear);（4）進(jìn)隊(duì)列）進(jìn)隊(duì)列enQueue(q,e) 在隊(duì)列不滿的條件下，先將隊(duì)尾指針在隊(duì)列不滿的條件下，先將隊(duì)尾指針rear循環(huán)增循環(huán)增1，然后，然后將元素添加到該位置。將元素添加到該位置。bool enQueue(SqQueue *&q,ElemType e) if (q-rear+1)%MaxSize=q-front) /隊(duì)滿上溢出隊(duì)滿上溢出return false; q-rear=(q-rear+1)%MaxSize; q-dataq-rear=e; return true;（5）出隊(duì)列）出隊(duì)列deQueue(q,

43、e)在隊(duì)列在隊(duì)列q不為空的條件下，將隊(duì)首指針不為空的條件下，將隊(duì)首指針front循環(huán)增循環(huán)增1，并將該，并將該位置的元素值賦給位置的元素值賦給e。bool deQueue(SqQueue *&q,ElemType &e) if (q-front=q-rear)/隊(duì)空下溢出隊(duì)空下溢出return false; q-front=(q-front+1)%MaxSize; e=q-dataq-front; return true; 例例3.7 對(duì)于環(huán)形隊(duì)列來說，如果知道隊(duì)頭指針和隊(duì)列中元對(duì)于環(huán)形隊(duì)列來說，如果知道隊(duì)頭指針和隊(duì)列中元素個(gè)數(shù)，則可以計(jì)算出隊(duì)尾指針。也就是說，可以用隊(duì)列中元素

44、個(gè)數(shù)，則可以計(jì)算出隊(duì)尾指針。也就是說，可以用隊(duì)列中元素個(gè)數(shù)代替隊(duì)尾指針。設(shè)計(jì)出這種環(huán)形隊(duì)列的初始化、入隊(duì)、素個(gè)數(shù)代替隊(duì)尾指針。設(shè)計(jì)出這種環(huán)形隊(duì)列的初始化、入隊(duì)、出隊(duì)和判空算法。出隊(duì)和判空算法。已知已知front、rear，求隊(duì)中元素個(gè)數(shù)：，求隊(duì)中元素個(gè)數(shù)：count=(rear-front+MaxSize)%MaxSize已知已知front、count，求，求rear：rear=(front+rear)%MaxSize已知已知rear、count，求，求front：front=(rear-count+MaxSize)%MaxSizecount=4count=3MaxSize5解：解：依題意設(shè)計(jì)

45、的環(huán)形隊(duì)列類型如下：依題意設(shè)計(jì)的環(huán)形隊(duì)列類型如下：typedef struct ElemType dataMaxSize; int front;/隊(duì)頭指針隊(duì)頭指針 int count;/隊(duì)列中元素個(gè)數(shù)隊(duì)列中元素個(gè)數(shù) QuType;環(huán)形隊(duì)列的四要素：環(huán)形隊(duì)列的四要素：隊(duì)空條件：隊(duì)空條件：count0隊(duì)滿條件：隊(duì)滿條件：countMaxSize進(jìn)隊(duì)進(jìn)隊(duì)e操作：操作：rear=(rear+1)%MaxSize; 將將e放在放在rear處處出隊(duì)操作：出隊(duì)操作：front=(front+1)%MaxSize;取出取出front處元素處元素e; 這樣的環(huán)形隊(duì)列中最多可放置這樣的環(huán)形隊(duì)列中最多可放置MaxS

46、ize個(gè)元素。個(gè)元素。由由front和和count求出求出對(duì)應(yīng)的算法如下：對(duì)應(yīng)的算法如下：void InitQueue(QuType *&qu)/初始化隊(duì)運(yùn)算算法初始化隊(duì)運(yùn)算算法 qu=(QuType *)malloc(sizeof(QuType); qu-front=0; qu-count=0;bool EnQueue(QuType *&qu,ElemType x) /進(jìn)隊(duì)運(yùn)算算法進(jìn)隊(duì)運(yùn)算算法 int rear; /臨時(shí)隊(duì)尾指針臨時(shí)隊(duì)尾指針 if (qu-count=MaxSize)/隊(duì)滿上溢出隊(duì)滿上溢出return false; else rear=(qu-front+qu

47、-count)%MaxSize; /求隊(duì)尾位置求隊(duì)尾位置rear=(rear+1)%MaxSize;/隊(duì)尾循環(huán)增隊(duì)尾循環(huán)增1qu-datarear=x;qu-count+;/元素個(gè)數(shù)增元素個(gè)數(shù)增1return true; bool DeQueue(QuType *&qu,ElemType &x) /出隊(duì)運(yùn)算算法出隊(duì)運(yùn)算算法 if (qu-count=0) /隊(duì)空下溢出隊(duì)空下溢出return false; else qu-front=(qu-front+1)%MaxSize; /隊(duì)頭循環(huán)增隊(duì)頭循環(huán)增1x=qu-dataqu-front;qu-count-; /元素個(gè)數(shù)減元素個(gè)數(shù)減

48、1return true; bool QueueEmpty(QuType *qu) /判隊(duì)空運(yùn)算算法判隊(duì)空運(yùn)算算法 return(qu-count=0); 鏈隊(duì)組成鏈隊(duì)組成: （1）存儲(chǔ)隊(duì)列元素的單鏈表）存儲(chǔ)隊(duì)列元素的單鏈表 （2） 指向隊(duì)頭和隊(duì)尾指針的鏈隊(duì)頭節(jié)點(diǎn)指向隊(duì)頭和隊(duì)尾指針的鏈隊(duì)頭節(jié)點(diǎn) 3.2.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn) 映射 q a1 an a2 隊(duì)尾節(jié)點(diǎn) 隊(duì)頭節(jié)點(diǎn) 鏈隊(duì)節(jié)點(diǎn) 隊(duì)列 a1,a2,ai,an front rear q (a)(a)鏈隊(duì)初態(tài)鏈隊(duì)初態(tài) front rear q (b)(b)入隊(duì)入隊(duì) 3 3 個(gè)元素個(gè)元素 a

49、b c front rear q (c)(c)出隊(duì)出隊(duì) 1 1 個(gè)元素個(gè)元素 b c 鏈列的入隊(duì)和出隊(duì)操作示意圖鏈列的入隊(duì)和出隊(duì)操作示意圖隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾單鏈表中數(shù)據(jù)節(jié)點(diǎn)類型單鏈表中數(shù)據(jù)節(jié)點(diǎn)類型QNode定義如下定義如下:typedef struct qnode ElemType data; /數(shù)據(jù)元素?cái)?shù)據(jù)元素 struct qnode *next; QNode;鏈隊(duì)中頭節(jié)點(diǎn)類型鏈隊(duì)中頭節(jié)點(diǎn)類型LiQueue定義如下定義如下:typedef struct QNode *front;/指向單鏈表隊(duì)頭節(jié)點(diǎn)指向單鏈表隊(duì)頭節(jié)點(diǎn) QNode *rear; /指向單鏈表隊(duì)尾節(jié)點(diǎn)指向單鏈表隊(duì)尾節(jié)點(diǎn) LiQu

50、eue; 隊(duì)空條件：隊(duì)空條件：front=rear=NULL隊(duì)滿條件：隊(duì)滿條件：不考慮不考慮進(jìn)隊(duì)進(jìn)隊(duì)e操作：操作：將包含將包含e的節(jié)點(diǎn)插入到單鏈表表尾的節(jié)點(diǎn)插入到單鏈表表尾出隊(duì)操作：出隊(duì)操作：刪除單鏈表首數(shù)據(jù)節(jié)點(diǎn)刪除單鏈表首數(shù)據(jù)節(jié)點(diǎn)鏈隊(duì)的鏈隊(duì)的4 4要素：要素： qfrontrear初始時(shí)初始時(shí)qa1an隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾 在鏈隊(duì)存儲(chǔ)中在鏈隊(duì)存儲(chǔ)中,隊(duì)列的基本運(yùn)算算法如下。隊(duì)列的基本運(yùn)算算法如下。 （1）初始化隊(duì)列）初始化隊(duì)列InitQueue(q) 構(gòu)造一個(gè)空隊(duì)列，即只創(chuàng)建一個(gè)鏈隊(duì)頭節(jié)點(diǎn)，其構(gòu)造一個(gè)空隊(duì)列，即只創(chuàng)建一個(gè)鏈隊(duì)頭節(jié)點(diǎn)，其front和和rear域均置為域均置為NULL，不創(chuàng)建數(shù)據(jù)元素

51、節(jié)點(diǎn)。對(duì)應(yīng)算法，不創(chuàng)建數(shù)據(jù)元素節(jié)點(diǎn)。對(duì)應(yīng)算法如下如下:void InitQueue(LiQueue *&q) q=(LiQueue *)malloc(sizeof(LiQueue); q-front=q-rear=NULL; qfrontrear （2）銷毀隊(duì)列）銷毀隊(duì)列DestroyQueue(q) 釋放隊(duì)列占用的存儲(chǔ)空間釋放隊(duì)列占用的存儲(chǔ)空間,包括包括鏈隊(duì)頭節(jié)點(diǎn)和所有數(shù)據(jù)節(jié)點(diǎn)鏈隊(duì)頭節(jié)點(diǎn)和所有數(shù)據(jù)節(jié)點(diǎn)的存儲(chǔ)空間。對(duì)應(yīng)算法如下的存儲(chǔ)空間。對(duì)應(yīng)算法如下: void DestroyQueue(LiQueue *&q) QNode *p=q-front,*r; /p指向隊(duì)頭數(shù)據(jù)節(jié)點(diǎn)指

52、向隊(duì)頭數(shù)據(jù)節(jié)點(diǎn) if (p!=NULL) /釋放數(shù)據(jù)節(jié)點(diǎn)占用空間釋放數(shù)據(jù)節(jié)點(diǎn)占用空間 r=p-next;while (r!=NULL) free(p); p=r;r=p-next; free(p); free(q); /釋放鏈隊(duì)節(jié)點(diǎn)占用空間釋放鏈隊(duì)節(jié)點(diǎn)占用空間qa1ana2pr （3）判斷隊(duì)列是否為空）判斷隊(duì)列是否為空QueueEmpty(q) 若鏈隊(duì)節(jié)點(diǎn)的若鏈隊(duì)節(jié)點(diǎn)的rear域值為域值為NULL，表示隊(duì)列為空，返回，表示隊(duì)列為空，返回true；否則返回；否則返回false。對(duì)應(yīng)算法如下。對(duì)應(yīng)算法如下: bool QueueEmpty(LiQueue *q)return(q-rear=NULL

53、); （4） 入隊(duì)入隊(duì)enQueue(q,e) 創(chuàng)建創(chuàng)建data域?yàn)橛驗(yàn)閑的數(shù)據(jù)節(jié)點(diǎn)的數(shù)據(jù)節(jié)點(diǎn)*s。 若原隊(duì)列為空，則將鏈隊(duì)節(jié)點(diǎn)的兩個(gè)域均指向若原隊(duì)列為空，則將鏈隊(duì)節(jié)點(diǎn)的兩個(gè)域均指向*s節(jié)點(diǎn)，節(jié)點(diǎn)，否則將否則將*s鏈到單鏈表的末尾，并讓鏈隊(duì)節(jié)點(diǎn)的鏈到單鏈表的末尾，并讓鏈隊(duì)節(jié)點(diǎn)的rear域指向域指向它。對(duì)應(yīng)算法如下它。對(duì)應(yīng)算法如下:void enQueue(LiQueue *&q,ElemType e) QNode *p; p=(QNode *)malloc(sizeof(QNode); p-data=e; p-next=NULL; if (q-rear=NULL) /若鏈隊(duì)為空若鏈隊(duì)為

54、空,新節(jié)點(diǎn)是隊(duì)首節(jié)點(diǎn)又是隊(duì)尾節(jié)點(diǎn)新節(jié)點(diǎn)是隊(duì)首節(jié)點(diǎn)又是隊(duì)尾節(jié)點(diǎn)q-front=q-rear=p; else q-rear-next=p;/將將*p節(jié)點(diǎn)鏈到隊(duì)尾節(jié)點(diǎn)鏈到隊(duì)尾,并將并將rear指向它指向它q-rear=p; qa1ana2pe （5）出隊(duì)）出隊(duì)deQueue(q,e) 若原隊(duì)列不為空，則將第一個(gè)數(shù)據(jù)節(jié)點(diǎn)的若原隊(duì)列不為空，則將第一個(gè)數(shù)據(jù)節(jié)點(diǎn)的data域值賦給域值賦給e,并刪除之。并刪除之。 若出隊(duì)之前隊(duì)列中只有一個(gè)節(jié)點(diǎn)，則需將鏈隊(duì)節(jié)點(diǎn)的兩若出隊(duì)之前隊(duì)列中只有一個(gè)節(jié)點(diǎn)，則需將鏈隊(duì)節(jié)點(diǎn)的兩個(gè)域均置為個(gè)域均置為NULL，表示隊(duì)列已為空。對(duì)應(yīng)的算法如下，表示隊(duì)列已為空。對(duì)應(yīng)的算法如下:bool

55、 deQueue(LiQueue *&q,ElemType &e) QNode *t; if (q-rear=NULL) return false; /隊(duì)列為空隊(duì)列為空 t=q-front; /t指向第一個(gè)數(shù)據(jù)節(jié)點(diǎn)指向第一個(gè)數(shù)據(jù)節(jié)點(diǎn) if (q-front=q-rear) /隊(duì)列中只有一個(gè)節(jié)點(diǎn)時(shí)隊(duì)列中只有一個(gè)節(jié)點(diǎn)時(shí)q-front=q-rear=NULL; else /隊(duì)列中有多個(gè)節(jié)點(diǎn)時(shí)隊(duì)列中有多個(gè)節(jié)點(diǎn)時(shí)q-front=q-front-next; e=t-data; free(t); return true;qa1ana2t 例例3.8 采用一個(gè)不帶頭節(jié)點(diǎn)只有一個(gè)尾節(jié)點(diǎn)指針采用一

56、個(gè)不帶頭節(jié)點(diǎn)只有一個(gè)尾節(jié)點(diǎn)指針rear的循的循環(huán)單鏈表存儲(chǔ)隊(duì)列，設(shè)計(jì)隊(duì)列的初始化、進(jìn)隊(duì)和出隊(duì)算法。環(huán)單鏈表存儲(chǔ)隊(duì)列，設(shè)計(jì)隊(duì)列的初始化、進(jìn)隊(duì)和出隊(duì)算法。reara1ana2隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾這樣的鏈隊(duì)通過尾節(jié)點(diǎn)指針這樣的鏈隊(duì)通過尾節(jié)點(diǎn)指針rear唯一標(biāo)識(shí)。唯一標(biāo)識(shí)。隊(duì)空條件：隊(duì)空條件：rear=NULL隊(duì)滿條件：隊(duì)滿條件：不考慮不考慮進(jìn)隊(duì)進(jìn)隊(duì)e操作：操作：將包含將包含e的節(jié)點(diǎn)插入到單鏈表表尾的節(jié)點(diǎn)插入到單鏈表表尾出隊(duì)操作：出隊(duì)操作：刪除單鏈表首節(jié)點(diǎn)刪除單鏈表首節(jié)點(diǎn)鏈隊(duì)的鏈隊(duì)的4 4要素：要素：void initQueue(LinkList *&rear)/初始化隊(duì)運(yùn)算算法初始化隊(duì)運(yùn)算算法r

57、ear=NULL;bool queueEmpty(LinkList *rear) /判隊(duì)空運(yùn)算算法判隊(duì)空運(yùn)算算法 return(rear=NULL);void enQueue(LinkList *&rear,ElemType x)/進(jìn)隊(duì)運(yùn)算算法進(jìn)隊(duì)運(yùn)算算法 LinkList *p; p=(LinkList *)malloc(sizeof(LinkList);/創(chuàng)建新節(jié)點(diǎn)創(chuàng)建新節(jié)點(diǎn) p-data=x; if (rear=NULL)/原鏈隊(duì)為空原鏈隊(duì)為空 p-next=p;/構(gòu)成循環(huán)鏈表構(gòu)成循環(huán)鏈表rear=p; else p-next=rear-next;/將將*p節(jié)點(diǎn)插入到節(jié)點(diǎn)插入到*

58、rear節(jié)點(diǎn)之后節(jié)點(diǎn)之后rear-next=p;rear=p; /讓讓rear指向這個(gè)新插入的節(jié)點(diǎn)指向這個(gè)新插入的節(jié)點(diǎn) reara1ana2隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾pxbool deQueue(LinkList *&rear,ElemType &x) /出隊(duì)運(yùn)算算法出隊(duì)運(yùn)算算法 LinkList *q; if (rear=NULL) return false;/隊(duì)空隊(duì)空 else if (rear-next=rear)/原隊(duì)中只有一個(gè)節(jié)點(diǎn)原隊(duì)中只有一個(gè)節(jié)點(diǎn) x=rear-data;free(rear);rear=NULL; else /原隊(duì)中有兩個(gè)或以上的節(jié)點(diǎn)原隊(duì)中有兩個(gè)或以上的節(jié)點(diǎn)

59、q=rear-next;x=q-data;rear-next=q-next;free(q); return true;reara1ana2隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾3.2.4 隊(duì)列的應(yīng)用隊(duì)列的應(yīng)用采用隊(duì)列求解迷宮問題采用隊(duì)列求解迷宮問題 使用一個(gè)隊(duì)列使用一個(gè)隊(duì)列qu記錄走過的方塊，該隊(duì)列的結(jié)構(gòu)如下記錄走過的方塊，該隊(duì)列的結(jié)構(gòu)如下: typedef struct int i,j; /方塊的位置方塊的位置 int pre; /本路徑中上一方塊在隊(duì)列中的下標(biāo)本路徑中上一方塊在隊(duì)列中的下標(biāo) Box;/方塊類型方塊類型typedef struct Box dataMaxSize; int front,rear;/

60、隊(duì)頭指針和隊(duì)尾指針隊(duì)頭指針和隊(duì)尾指針 QuType;/定義順序隊(duì)類型定義順序隊(duì)類型 這里使用的隊(duì)列這里使用的隊(duì)列qu不是環(huán)形隊(duì)列（因?yàn)橐贸鲫?duì)的元素不是環(huán)形隊(duì)列（因?yàn)橐贸鲫?duì)的元素找路徑），因此在出隊(duì)時(shí)，不會(huì)將出隊(duì)元素真正從隊(duì)列中刪除，找路徑），因此在出隊(duì)時(shí)，不會(huì)將出隊(duì)元素真正從隊(duì)列中刪除，因?yàn)橐盟敵雎窂?。因?yàn)橐盟敵雎窂健? 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 938 8 8 3434 8 7 3030 8 6 2727 8 5 2424 7 5 2222 6 5 2020 6 4 1717 6 3 1313 5 3 1010 5 2 88 5 1 66 4 1 44 3 1 22 2 1 0隊(duì)列中的位置隊(duì)列中的位置從隊(duì)列中可推出出口到入從隊(duì)列中可推出出口到入口的（即逆向）路徑口的（即逆向）路徑 （1）首先將）首先將(1,1)入隊(duì)入隊(duì); （2）在隊(duì)列）在隊(duì)列qu不為空時(shí)循環(huán)：出隊(duì)一次（由于不是環(huán)形隊(duì)不為空時(shí)循環(huán)：出隊(duì)一次（由于不是環(huán)形隊(duì)列，該出隊(duì)元素仍在隊(duì)列中），稱該出隊(duì)的方塊為當(dāng)前方塊，列，該出隊(duì)元素仍在隊(duì)列中），稱該出隊(duì)的方塊為當(dāng)前方塊，fro