唐國民版棧和隊(duì)列

1、 第三章第三章 棧和隊(duì)列棧和隊(duì)列定義：定義：限定只能在表的限定只能在表的進(jìn)行插進(jìn)行插入和刪除運(yùn)算的線性表。入和刪除運(yùn)算的線性表。在棧中在棧中 通常將表中允許進(jìn)行插入、刪除操通常將表中允許進(jìn)行插入、刪除操作的一端稱為作的一端稱為棧頂棧頂(Top)，同時(shí)表的另一，同時(shí)表的另一端被稱為端被稱為棧底棧底(Bottom)。棧頂?shù)漠?dāng)前位。棧頂?shù)漠?dāng)前位置是動(dòng)態(tài)變化的，它由一個(gè)稱為棧頂指置是動(dòng)態(tài)變化的，它由一個(gè)稱為棧頂指針的位置指示器指示。當(dāng)棧中沒有元素針的位置指示器指示。當(dāng)棧中沒有元素時(shí)稱為時(shí)稱為空棧空棧。棧的插入操作被形象地稱棧的插入操作被形象地稱為為進(jìn)棧進(jìn)?；蛉霔?，刪除操作稱為出?；蚧蛉霔?，刪除操作稱為

2、出?；蛲送藯?。棧的示意圖棧的示意圖ana2a1進(jìn)棧出棧棧頂棧底進(jìn)棧出棧(a) 棧的示意圖(b) 鐵路調(diào)序棧的表示與線性表相同，仍為一對一與線性表相同，仍為一對一( 1:1)( 1:1)關(guān)系。關(guān)系。用用或或存儲(chǔ)均可，但以順序棧更常見存儲(chǔ)均可，但以順序棧更常見只能在只能在運(yùn)算，且訪問結(jié)點(diǎn)時(shí)依照運(yùn)算，且訪問結(jié)點(diǎn)時(shí)依照（LIFOLIFO）或）或（FILOFILO）的原則。）的原則。關(guān)鍵是編寫關(guān)鍵是編寫和和函數(shù)，具體實(shí)現(xiàn)依順函數(shù)，具體實(shí)現(xiàn)依順序?；蜴湕５拇鎯?chǔ)結(jié)構(gòu)有別而不同。序?；蜴湕５拇鎯?chǔ)結(jié)構(gòu)有別而不同。 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) 運(yùn)算規(guī)則運(yùn)算規(guī)則 實(shí)現(xiàn)方式實(shí)現(xiàn)方式 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)基本操作基本操作 建棧、判

3、斷棧滿或?？?、入棧、出棧、建棧、判斷棧滿或?？?、入棧、出棧、讀棧頂元素值，等等。讀棧頂元素值，等等。 表尾表尾( (即即 a an n 端端) )稱為棧頂稱為棧頂 /top ; /top ; 表頭表頭( (即即 a a1 1 端端) )稱稱為棧底為棧底/base/base例如：例如： 棧棧 = (a1 , a2 , a3 , .,an-1 , an )插入元素到棧頂?shù)牟僮鳎Q為插入元素到棧頂?shù)牟僮?，稱為入入。從棧頂刪除最后一個(gè)元素的操作，稱為從棧頂刪除最后一個(gè)元素的操作，稱為出棧出棧。棧的物理表示法棧的物理表示法一、順序棧的存儲(chǔ)結(jié)構(gòu)和操作的實(shí)現(xiàn)一、順序棧的存儲(chǔ)結(jié)構(gòu)和操作的實(shí)現(xiàn) 順序棧順序棧:

4、:是利用一組地址連續(xù)的存儲(chǔ)單元依次存放從棧底到是利用一組地址連續(xù)的存儲(chǔ)單元依次存放從棧底到棧頂?shù)臄?shù)據(jù)元素。棧頂?shù)臄?shù)據(jù)元素。 a1 a2 an順序棧順序棧S ai0n棧的基本操作棧的基本操作 ClearStack(S)ClearStack(S)：棧棧S S已經(jīng)存在，清除棧已經(jīng)存在，清除棧S S中的所有元素中的所有元素將將S S置成空棧置成空棧。 InitStack( )InitStack( )： 初始化，構(gòu)造一個(gè)空棧初始化，構(gòu)造一個(gè)空棧S S StackEmpty(S)StackEmpty(S)：判斷棧判斷棧S S是否為空，若為空，則返回是否為空，若為空，則返回 truetrue；否則返回；否則

5、返回falsefalse GetTop(S)GetTop(S) ： 返回返回S S的棧頂元素，但不移動(dòng)棧頂指針的棧頂元素，但不移動(dòng)棧頂指針 也不改變棧頂元素的值也不改變棧頂元素的值 Push(S, x)Push(S, x) ：在在S的頂部插入的頂部插入(亦稱壓入亦稱壓入)元素元素x；若；若S棧未棧未滿，將滿，將x插入棧頂位置，若棧已滿，則返回插入棧頂位置，若棧已滿，則返回FALSE，表示，表示操作失敗，否則返回操作失敗，否則返回TRUE。 （入棧操作（入棧操作) ) Pop(S)Pop(S) ： 刪除刪除S S的棧頂元素并返回其值（出棧操作）的棧頂元素并返回其值（出棧操作）順序棧存儲(chǔ)結(jié)構(gòu)的描述

6、：順序棧存儲(chǔ)結(jié)構(gòu)的描述：/*設(shè)順序棧的最大長度為100，可依實(shí)現(xiàn)情況而修改*/structstruct datatype stackMaxsize;datatype stackMaxsize;int topint top/ /* *棧頂指針棧頂指針* */ / /* *順序棧類型定義順序棧類型定義* */ / /* *s s為順序棧類型變量的指針為順序棧類型變量的指針* */ /順序棧的幾種狀態(tài)以及在這些狀態(tài)下棧頂指針順序棧的幾種狀態(tài)以及在這些狀態(tài)下棧頂指針toptop和棧和棧中結(jié)點(diǎn)的關(guān)系中結(jié)點(diǎn)的關(guān)系 棧為空的條件棧為空的條件 ： top = = 0;top = = 0;棧滿的條件棧滿的條件

7、： top = = Maxsizetop = = Maxsize若入棧動(dòng)作使地址向高端增長，稱為若入棧動(dòng)作使地址向高端增長，稱為“向上生成向上生成”的棧；的棧；若入棧動(dòng)作使地址向低端增長，稱為若入棧動(dòng)作使地址向低端增長，稱為“向下生成向下生成”的棧的棧； 對于向上生成的堆棧對于向上生成的堆棧: :棧指針指向待壓入位置棧指針指向待壓入位置入棧入棧：棧指針：棧指針top top “先壓后加先壓后加” : S: Stop+top+=a=ai i出棧出棧：棧指針：棧指針top top “先減后彈先減后彈” : e=S: e=S- -top- -top 順序棧的基本操作順序棧的基本操作構(gòu)造一個(gè)空順序棧構(gòu)

8、造一個(gè)空順序棧 SeqStack * InitStack( ) SeqStack *S ;S=(SeqStack *)malloc(sizeof(SeqStack);if(!S) /*空間申請失敗空間申請失敗*/ printf(“空間不足空間不足”)；return NULL; else S-top=0; return S; 取順序棧棧頂元素取順序棧棧頂元素 datatype GetTop(SeqStack *S) if (S-top=0) printf(n棧是空的棧是空的!); return FALSE; else return S-stackS-top-1; 該函數(shù)返回一個(gè)該函數(shù)返回一個(gè)da

9、tatype類型的值類型的值判別空棧判別空棧int StackEmpty(SeqStack *S) if(S-top=0) return TRUE; else return FALSE; 順序棧的入棧操作順序棧的入棧操作例如用堆棧存放（例如用堆棧存放（A A，B B，C C，D D）AACBABAtop核心語句：核心語句：順序棧入棧函數(shù)順序棧入棧函數(shù)PUSHPUSH（）（）SeqStack*Push(SeqStack*S，datatype x) if(S-top=Maxsize) return NULL; else S-stackS-top=x; S-top+; return s; Push

10、(s,B);Push (s,C);Push (s,D);toptoptoptop低地址低地址LPush (s,A);高地址高地址MBCD順序棧出棧操作順序棧出棧操作例如從棧中取出例如從棧中取出 DCBAtoptopDCABDCBAtopDCBAtop低地址低地址L高地址高地址MD順序棧出棧函數(shù)順序棧出棧函數(shù)POP( )POP( )datatype pop( SeqStack *S) if(S-top= =0) printf(nThe sequence stack is empty!); return FALSE; S-top-; return S-stackS-top; 例例3.13.1 用用

11、mainmain函數(shù)以及函數(shù)以及displaydisplay函數(shù)，調(diào)試上述各種棧的基函數(shù)，調(diào)試上述各種棧的基本操作算法。本操作算法。 #define Maxsize 50 typedef int datatype; typedef struct datatype stackMaxsize; int top； SeqStack；void display(SeqStack *s) int t; t=s-top; if(s-top =0) printf(the stack is empty!n); else while(t!=0) t-; printf(%d-,s-stackt); main()in

12、t a6=3,7,4,12,31,15,i; SeqStack *p; p= InitStack(); for(i=0;itop=0; S-top=0; /*清空棧清空棧*/ else else push(s,c1); /*入棧入棧*/ Scanf( Scanf(“%c%c”,&c1);,&c1); display(s); 鏈鏈 棧棧二、鏈棧的存儲(chǔ)結(jié)構(gòu)及操作的實(shí)現(xiàn)二、鏈棧的存儲(chǔ)結(jié)構(gòu)及操作的實(shí)現(xiàn) 棧也可以用鏈?zhǔn)浇Y(jié)構(gòu)來表示，用鏈?zhǔn)浇Y(jié)構(gòu)棧也可以用鏈?zhǔn)浇Y(jié)構(gòu)來表示，用鏈?zhǔn)浇Y(jié)構(gòu)來表示的棧就是來表示的棧就是鏈棧鏈棧鏈棧的構(gòu)造方式鏈棧的構(gòu)造方式以頭指針為棧頂，以頭指針為棧頂，在頭指針處在頭指針

13、處插入或刪除插入或刪除. .鏈棧中每個(gè)結(jié)點(diǎn)由兩個(gè)域構(gòu)成：鏈棧中每個(gè)結(jié)點(diǎn)由兩個(gè)域構(gòu)成：datadata域和域和nextnext域，其定義為：域，其定義為：Typedef struct node datatype data; struct node * next; LinkStack; LinkStack *top; 將將x x入棧，修入棧，修改棧頂指針改棧頂指針: : P-next=top; P-next=top; top=p;top=p;鏈棧的入棧操作鏈棧的入棧操作LinkStack *Push(LinkStack *top，datatype x) LinkStack *p; p=(Links

14、tack*)malloc(sizeof(LinkStack); p-data=x; p-next=top; top=p; return top; 鏈棧入棧操作鏈棧入棧操作鏈棧的出棧操作鏈棧的出棧操作 LinkStack *pop( LinkStack *top) LinkStack *q; if(!top) /*說明指針top指向NULL*/ printf(“n鏈棧是空的!”); return NULL; q=top; top=top-next; free(q); return top; 鏈棧出棧操作鏈棧出棧操作1、數(shù)制轉(zhuǎn)換（十轉(zhuǎn)數(shù)制轉(zhuǎn)換（十轉(zhuǎn)N N） 設(shè)計(jì)思路：用棧暫存低位值設(shè)計(jì)思路：用棧暫

15、存低位值2、括號(hào)匹配問題括號(hào)匹配問題 設(shè)計(jì)思路：用棧暫存左括號(hào)設(shè)計(jì)思路：用棧暫存左括號(hào)3、子程序的調(diào)用子程序的調(diào)用 設(shè)計(jì)思路：用棧暫存指令地址設(shè)計(jì)思路：用棧暫存指令地址4、逆置一個(gè)單鏈表逆置一個(gè)單鏈表 設(shè)計(jì)思路：用棧暫存每一結(jié)點(diǎn)設(shè)計(jì)思路：用棧暫存每一結(jié)點(diǎn)例例3.2 3.2 將十進(jìn)制整數(shù)轉(zhuǎn)換成二至九之間的任一將十進(jìn)制整數(shù)轉(zhuǎn)換成二至九之間的任一進(jìn)制數(shù)輸出進(jìn)制數(shù)輸出 將一個(gè)十進(jìn)制數(shù)將一個(gè)十進(jìn)制數(shù)43274327轉(zhuǎn)換成八進(jìn)制數(shù)轉(zhuǎn)換成八進(jìn)制數(shù)(10347)(10347)8 8：N是十進(jìn)制數(shù)，要將是十進(jìn)制數(shù)，要將N轉(zhuǎn)換成轉(zhuǎn)換成r進(jìn)制數(shù)進(jìn)制數(shù)1、當(dāng)當(dāng)N0N0，將，將N%rN%r壓壓入棧入棧s s中，即余數(shù)進(jìn)

16、棧；中，即余數(shù)進(jìn)棧； 2、用用N/rN/r代替代替N N；3 3、若、若N N0 0，則重復(fù)上，則重復(fù)上兩步；若兩步；若N=0N=0，則將棧，則將棧s s的內(nèi)容依次出棧，所的內(nèi)容依次出棧，所得的結(jié)果即為所求。得的結(jié)果即為所求。解題思路如下：解題思路如下：void conversion(int N, int r) int x=N,y=r;SeqStack *s; /*是順序棧是順序棧*/ s=initStack( ); /*構(gòu)造一個(gè)順序棧構(gòu)造一個(gè)順序棧*/ while(N!=0) push(s, N %r ); / N=N/r ; printf(“n十進(jìn)制數(shù)十進(jìn)制數(shù)%d所對應(yīng)的所對應(yīng)的%d進(jìn)制數(shù)

17、進(jìn)制數(shù)是是:”，x,y);while(!StackEmpty(s) printf(“%d”,pop(s); printf(“n”); 例例3.5 3.5 利用一個(gè)順序棧將單鏈表（利用一個(gè)順序棧將單鏈表（a a1 1,a,a2 2, ,a,an n）（其）（其中中n=0n=0）逆置為（）逆置為（a an n,a,an-1n-1, ,，a a1 1）1 1、建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表、建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表headhead；2 2、輸出該單鏈表；、輸出該單鏈表；3 3、建立一個(gè)空棧、建立一個(gè)空棧s s（順序棧）；（順序棧）；4 4、依次將單鏈表的數(shù)據(jù)入棧；、依次將單鏈表的數(shù)據(jù)入棧；5 5、依次將單

18、鏈表的數(shù)據(jù)出棧，、依次將單鏈表的數(shù)據(jù)出棧，并逐個(gè)將出棧的數(shù)據(jù)存入單鏈并逐個(gè)將出棧的數(shù)據(jù)存入單鏈表的數(shù)據(jù)域（自前向后）表的數(shù)據(jù)域（自前向后）; ;6 6、再輸出單鏈表。、再輸出單鏈表。 解題思路如下：解題思路如下：linklist*backlinklist(linklist *head) /*利用順序棧逆置單鏈表利用順序棧逆置單鏈表head */linklist *p; /*工作指針工作指針*/ p=head-next; /*p指向單鏈表的第一個(gè)結(jié)點(diǎn)指向單鏈表的第一個(gè)結(jié)點(diǎn)*/ initstack( ); while(p) push(&s, p-data); p=p-next ; p=he

19、ad-next; while(!stackempty(s) /*將順序表的數(shù)據(jù)出棧將順序表的數(shù)據(jù)出棧*/ p-data=pop(&s); p=p-next; return (head); 兩個(gè)棧的共享技術(shù)兩個(gè)棧的共享技術(shù)： 它主要利用了棧它主要利用了?！皸５孜恢貌蛔儯鴹５孜恢貌蛔?，而棧頂位置動(dòng)態(tài)變化棧頂位置動(dòng)態(tài)變化”的特性。首先為兩個(gè)棧申請一個(gè)共享的的特性。首先為兩個(gè)棧申請一個(gè)共享的一維數(shù)組空間一維數(shù)組空間SM，將兩個(gè)棧的棧底分別放在一維數(shù)組，將兩個(gè)棧的棧底分別放在一維數(shù)組的兩端，分別是的兩端，分別是0， M-1。 由于兩個(gè)棧頂動(dòng)態(tài)變化，這樣可由于兩個(gè)棧頂動(dòng)態(tài)變化，這樣可以形成互補(bǔ)，

20、使得每個(gè)?？捎玫淖畲罂臻g與實(shí)際使用的需求以形成互補(bǔ)，使得每個(gè)?？捎玫淖畲罂臻g與實(shí)際使用的需求有關(guān)。由此可見，兩棧共享比兩個(gè)棧分別申請有關(guān)。由此可見，兩棧共享比兩個(gè)棧分別申請M/2的空間利的空間利用率高。用率高。 兩棧共享的數(shù)據(jù)結(jié)構(gòu)定義如下：兩棧共享的數(shù)據(jù)結(jié)構(gòu)定義如下： define M 100typedef struct StackElementType StackM; int top2; /*top0和top1分別為兩個(gè)棧頂指示器*/DqStack; 十月一前講到此十月一前講到此（圖） 共享?xiàng)?Stack:0M1top0top1(1) 初始化操作。初始化操作。 void InitStack(

21、DqStack *S) S-top0= -1; S-top1= M; int Push(DqStack *S, StackElementType x, int i)/*把數(shù)據(jù)元素把數(shù)據(jù)元素x壓入壓入i號(hào)堆棧號(hào)堆棧*/ if(S-top0+1=S-top1) /*棧已滿棧已滿*/ return(FALSE); switch(i) case 0: S-top0+; S-StackS-top0=x; break; case 1: S-top1-; S-StackS-top1=x; break; default: /*參數(shù)錯(cuò)誤參數(shù)錯(cuò)誤*/ return(FALSE) return(TRUE); int

22、 pop(DqStack *S, StackElementType *x, int i)/* 從從i 號(hào)堆棧中彈出棧頂元素并送到號(hào)堆棧中彈出棧頂元素并送到x中中 */ switch(i) /* 先出棧，后移棧頂指針先出棧，后移棧頂指針 */ case 0: if(S-top0= = -1) return(FALSE); *x=S-StackS-top0; S-top0-; break; case 1: if(S-top1= =M) return(FALSE); *x=S-StackS-top1; S-top1+; break; default: return(FALSE); return(TR

23、UE); (3) 共共享享?xiàng)５牡某龀鰲２俨僮髯魉闼惴?。法?隊(duì)列隊(duì)列 (Queue)是另一種限定性的是另一種限定性的線性表線性表，它只允許在表的一端插入元素，而在另一端它只允許在表的一端插入元素，而在另一端刪除元素刪除元素，所以隊(duì)列具有先進(jìn)先出先進(jìn)先出(Fist In Fist Out， 縮寫為FIFO)的特性。隊(duì)列的定義隊(duì)列的定義 在隊(duì)列中，允許插入的一端叫做在隊(duì)列中，允許插入的一端叫做隊(duì)尾隊(duì)尾(rear)，允許刪除的一端則稱為允許刪除的一端則稱為隊(duì)頭隊(duì)頭(front)。 假設(shè)隊(duì)列假設(shè)隊(duì)列為為q=(a1，a2，an)，那么，那么a1就是隊(duì)頭元素，就是隊(duì)頭元素，an則是隊(duì)尾元素。隊(duì)列中的元

24、素是按照則是隊(duì)尾元素。隊(duì)列中的元素是按照a1，a2，an的順序進(jìn)入的，的順序進(jìn)入的， 退出隊(duì)列也必須按照同樣的退出隊(duì)列也必須按照同樣的次序依次出隊(duì)，也就是說，只有在次序依次出隊(duì)，也就是說，只有在a1，a2，an-1都離開隊(duì)列之后，都離開隊(duì)列之后，an才能退出隊(duì)列。才能退出隊(duì)列。問：為什么要設(shè)計(jì)隊(duì)列？它有什么獨(dú)特用途？問：為什么要設(shè)計(jì)隊(duì)列？它有什么獨(dú)特用途？答：答： 1.1.離散事件的模擬（模擬事件發(fā)生的離散事件的模擬（模擬事件發(fā)生的先后順序先后順序, ,例如例如 CPUCPU芯片中的指令譯碼隊(duì)芯片中的指令譯碼隊(duì)列）；列）； 2.2.操作系統(tǒng)中的作業(yè)調(diào)度（一個(gè)操作系統(tǒng)中的作業(yè)調(diào)度（一個(gè)CPUCP

25、U執(zhí)行多個(gè)作業(yè)）；執(zhí)行多個(gè)作業(yè)）； 3.簡化程序設(shè)計(jì)。簡化程序設(shè)計(jì)。 與線性表相同，仍為一對一關(guān)系。與線性表相同，仍為一對一關(guān)系。順序隊(duì)順序隊(duì)或或鏈隊(duì)鏈隊(duì)，以，以循環(huán)順序隊(duì)循環(huán)順序隊(duì)更常見。更常見。只能在隊(duì)首和隊(duì)尾運(yùn)算，且訪問結(jié)點(diǎn)時(shí)依照只能在隊(duì)首和隊(duì)尾運(yùn)算，且訪問結(jié)點(diǎn)時(shí)依照先進(jìn)先出（FIFOFIFO）的原則。的原則。關(guān)鍵是掌握關(guān)鍵是掌握入隊(duì)入隊(duì)和和出隊(duì)出隊(duì)操作，具體實(shí)現(xiàn)依順操作，具體實(shí)現(xiàn)依順序隊(duì)或鏈隊(duì)的不同而不同。序隊(duì)或鏈隊(duì)的不同而不同。入隊(duì)或出隊(duì)，建空隊(duì)列，判隊(duì)空或隊(duì)滿等操作。入隊(duì)或出隊(duì)，建空隊(duì)列，判隊(duì)空或隊(duì)滿等操作。關(guān)鍵是掌握關(guān)鍵是掌握入隊(duì)入隊(duì)和和出隊(duì)出隊(duì)操作。操作。具體實(shí)現(xiàn)依具體實(shí)現(xiàn)依存

26、儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)（鏈隊(duì)鏈隊(duì)或或順序隊(duì)順序隊(duì)）的不同而不同。）的不同而不同。（1 1）InitQueue ( )InitQueue ( )： 構(gòu)造一個(gè)空隊(duì)列構(gòu)造一個(gè)空隊(duì)列Q Q（2 2）QueueEmpty (Q)QueueEmpty (Q)： 判斷隊(duì)列是否為空判斷隊(duì)列是否為空 （3 3）QueueLength (Q)QueueLength (Q)： 求隊(duì)列的長度求隊(duì)列的長度 （4 4）GetHead (Q)GetHead (Q)： 返回返回Q Q的隊(duì)頭元素，不改變隊(duì)列狀態(tài)的隊(duì)頭元素，不改變隊(duì)列狀態(tài) （5 5）EnQueue(QEnQueue(Q， x )x )： 插入元素插入元素x x為為Q Q

27、的新的隊(duì)尾元素的新的隊(duì)尾元素 （6 6）DeQueue(Q)DeQueue(Q)： 刪除刪除Q Q的隊(duì)頭元素的隊(duì)頭元素（7 7）ClearQueue(Q)ClearQueue(Q)：清除隊(duì)列：清除隊(duì)列Q Q中的所有元素中的所有元素 隊(duì)列隊(duì)列（QueueQueue）的邏輯表示的邏輯表示 假設(shè)隊(duì)列為Q=(a1，a2，an)，那么a1就是隊(duì)頭元素，an則是隊(duì)尾元素。隊(duì)列中的元素是按照a1，a2，an的順序進(jìn)入的， 退出隊(duì)列也必須按照同樣的次序依次出隊(duì)，也就是說，只有在a1，a2，an-1都離開隊(duì)列之后，an才能退出隊(duì)列。例如：隊(duì)列例如：隊(duì)列 Q= (a1 , a2 , a3 , .,an-1 , a

28、n )鏈隊(duì)列類型定義：鏈隊(duì)列類型定義： typedef struct Qnode *front ; /*隊(duì)頭指針*/ Qnode *rear ; /*隊(duì)尾指針*/ LinkQueue; 結(jié)點(diǎn)類型定義：結(jié)點(diǎn)類型定義： typedef Struct Qnode datatype data; /*數(shù)據(jù)域*/ Struct Qnode *next; /*指針域*/ Qnode; 隊(duì)列隊(duì)列（QueueQueue）的物理表示的物理表示鏈隊(duì)的幾種狀態(tài)示意圖：鏈隊(duì)的幾種狀態(tài)示意圖： 空鏈隊(duì)的特征？空鏈隊(duì)的特征？front=rearfront=rear 鏈隊(duì)會(huì)滿嗎？鏈隊(duì)會(huì)滿嗎？一般不會(huì)，因?yàn)閯h除時(shí)有一般不會(huì)，因

29、為刪除時(shí)有freefree動(dòng)作。除非內(nèi)存不足！動(dòng)作。除非內(nèi)存不足！(b)元素x入隊(duì)(d)元素x出隊(duì)入隊(duì)（尾部插入）：入隊(duì)（尾部插入）：rear-next=S; rear=S;rear-next=S; rear=S;出隊(duì)（頭部刪除）：出隊(duì)（頭部刪除）：front-next=S-next;front-next=S-next; 怎樣實(shí)現(xiàn)鏈隊(duì)的怎樣實(shí)現(xiàn)鏈隊(duì)的入隊(duì)和出隊(duì)入隊(duì)和出隊(duì)操作？操作？ 若設(shè)若設(shè)S S所指結(jié)點(diǎn)為入隊(duì)或出隊(duì)結(jié)點(diǎn)所指結(jié)點(diǎn)為入隊(duì)或出隊(duì)結(jié)點(diǎn)LinkQueue *InitQueue( ) LinkQueue *q; Qnode *p; q=(LinkQueue*)malloc(sizeof(

30、LinkQueue); p=(Qnode*)malloc(sizeof(Qnode); p-next=NULL; q-front =q-rear=p; return q;該函數(shù)返回一個(gè)指向隊(duì)頭的指針該函數(shù)返回一個(gè)指向隊(duì)頭的指針datatype GetHead(LinkQueue *Q) if(Q-front=Q-rear) printf(“n鏈隊(duì)列為空!”); return FALSE; return Q-front-next-data； void EnQueue(LinkQueue *Q，datatype x) Qnode *p; p = (Qnode*)malloc(sizeof(Qnod

31、e)； p-data = y； p-next = NULL； Q-rear-next = p； Q-rear=p； datatype DeQueue(LinkQueue *Q) Qnode *p; datatype x; if (Q-front = Q-rear) printf(隊(duì)列為空！隊(duì)列為空！); return FALSE; p = Q-front-next； x = p-data； Q-front-next = p-next； if(Q-rear = p) /*此時(shí)此時(shí)p出隊(duì)出隊(duì),則隊(duì)列為空則隊(duì)列為空*/ Q-rear=Q-front； free(p)； return x; 2、順序隊(duì)

32、列、順序隊(duì)列 順序隊(duì)列類型定義：順序隊(duì)列類型定義：#define MAXSIZE 100 / /* *最大隊(duì)列長度最大隊(duì)列長度* */ /typedef structtypedef structdatatype dataMAXSIZE； / /* * 存儲(chǔ)隊(duì)列的數(shù)據(jù)空間存儲(chǔ)隊(duì)列的數(shù)據(jù)空間* */ /int front； / /* *隊(duì)頭指針隊(duì)頭指針* */ /int rear； /*隊(duì)尾指針隊(duì)尾指針*/SeqQueue; 約定：約定：隊(duì)頭指針隊(duì)頭指針frontfront，若隊(duì)列不空，則指向隊(duì)頭元素，若隊(duì)列不空，則指向隊(duì)頭元素。 隊(duì)尾指針隊(duì)尾指針rearrear，若隊(duì)列不空，則指向隊(duì)尾元素的，若

33、隊(duì)列不空，則指向隊(duì)尾元素的 下一個(gè)位置下一個(gè)位置。順序隊(duì)的幾種狀態(tài)示意圖順序隊(duì)的幾種狀態(tài)示意圖頭指針始終指向隊(duì)頭元素，尾指針始終指向隊(duì)尾元素的下一個(gè)元素頭指針始終指向隊(duì)頭元素，尾指針始終指向隊(duì)尾元素的下一個(gè)元素為了防止出現(xiàn)假溢出，即在假溢出時(shí)，還能進(jìn)行入隊(duì)操作，我們采為了防止出現(xiàn)假溢出，即在假溢出時(shí)，還能進(jìn)行入隊(duì)操作，我們采取循環(huán)隊(duì)列。取循環(huán)隊(duì)列。循環(huán)隊(duì)列示意圖循環(huán)隊(duì)列示意圖在入隊(duì)時(shí)：在入隊(duì)時(shí)： 將數(shù)據(jù)區(qū)將數(shù)據(jù)區(qū)data0Maxsize-1看成是首尾相接的圓環(huán)看成是首尾相接的圓環(huán),當(dāng)當(dāng)入隊(duì)到入隊(duì)到Maxsize-1時(shí)時(shí),若隊(duì)頭元素的前面仍有空閑位置若隊(duì)頭元素的前面仍有空閑位置,下一個(gè)下一個(gè)地址

34、就應(yīng)翻轉(zhuǎn)為地址就應(yīng)翻轉(zhuǎn)為0,使使data0接在接在dataMaxsize-1之后之后, 通過通過求余運(yùn)算求余運(yùn)算rear=(rear+1)%Maxsize來求得。來求得。循環(huán)隊(duì)列的幾種狀態(tài)循環(huán)隊(duì)列的幾種狀態(tài)在循環(huán)隊(duì)列中當(dāng)采用在循環(huán)隊(duì)列中當(dāng)采用入隊(duì)操作入隊(duì)操作: : rear=(rear+1)%Maxsize出隊(duì)操作出隊(duì)操作: : front=(front+1)%Maxaize隊(duì)空條件隊(duì)空條件 : : front = = rearfront = = rear ( (初始化時(shí)：初始化時(shí)：front=rear)front=rear)隊(duì)滿條件隊(duì)滿條件： front=front=（rearrear)%N

35、)%N (N=maxsize) (N=maxsize)J2 J3J1 J4 J5frontrear 解決方案解決方案-人為人為浪費(fèi)一個(gè)單元浪費(fèi)一個(gè)單元： 即對大小為即對大小為MaxsizeMaxsize的數(shù)組，只允許存的數(shù)組，只允許存Maxsize-1Maxsize-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)。為此我們約定：為此我們約定：front和和rear二者之一指向?qū)嵲?，另一個(gè)指向二者之一指向?qū)嵲?，另一個(gè)指向空閑元素空閑元素(假設(shè)假設(shè)front指向隊(duì)頭元素，指向隊(duì)頭元素，rear指向隊(duì)尾元素的下一個(gè)指向隊(duì)尾元素的下一個(gè)位置，位置，即即rear 所指的單元始終為空所指的單元始終為空）。）。 隊(duì)列長度（即數(shù)據(jù)元素個(gè)

36、數(shù)）：隊(duì)列長度（即數(shù)據(jù)元素個(gè)數(shù)）：L=L=（N Nrearrearfrontfront）% N % N 循環(huán)隊(duì)列的基本操作實(shí)現(xiàn)循環(huán)隊(duì)列的基本操作實(shí)現(xiàn)1 1）初始化一個(gè)空隊(duì)列）初始化一個(gè)空隊(duì)列算法要求：生成一空隊(duì)列算法要求：生成一空隊(duì)列算法操作：為隊(duì)列分配基本容量空間算法操作：為隊(duì)列分配基本容量空間 設(shè)置隊(duì)列為設(shè)置隊(duì)列為空隊(duì)列空隊(duì)列，其特征即：，其特征即： front=rear=0front=rear=0（frontfront和和rearrear也可為任意單元編號(hào)，如也可為任意單元編號(hào)，如1 1，2 2，甚至甚至-1-1）以建隊(duì)、入隊(duì)和出隊(duì)三種基本操作為例以建隊(duì)、入隊(duì)和出隊(duì)三種基本操作為例建循環(huán)

37、隊(duì)的完整算法建循環(huán)隊(duì)的完整算法SeqQueue *initQueue( ) SeqQueue *q； q=(SeqQueue*)malloc(sizeof(SeqQueue)； /*開辟一個(gè)足夠大的存儲(chǔ)隊(duì)列的空間*/ q-front = q-rear = 0；/*將隊(duì)列頭尾指針置為零*/ return q； /*返回隊(duì)列的首地址*/ 算法說明：向循環(huán)隊(duì)列的隊(duì)尾插入一個(gè)元素算法說明：向循環(huán)隊(duì)列的隊(duì)尾插入一個(gè)元素分析分析：(1) (1) 插入前應(yīng)當(dāng)先判斷隊(duì)列是否滿？插入前應(yīng)當(dāng)先判斷隊(duì)列是否滿？ if ( q -rear + 1 ) % Maxsize )=q-front)if ( q -rear

38、+ 1 ) % Maxsize )=q-front) return false; return false;(2(2）插入元素值并修改尾指針）插入元素值并修改尾指針 q-data q-rear = x; q-data q-rear = x; q-rear = ( q -rear + 1 ) % Maxsize; q-rear = ( q -rear + 1 ) % Maxsize;循環(huán)隊(duì)列入隊(duì)操作循環(huán)隊(duì)列入隊(duì)操作int EnQueue(SeqQueue *q, datatype x)if(q-rear+1)MAXSIZE=q-front) printf(n循環(huán)隊(duì)列滿循環(huán)隊(duì)列滿!);return

39、 FALSE; q-dataq-rear = x； /*元素元素x入隊(duì)入隊(duì)*/ q-rear = (q-rear+1)%MAXSIZE; /*修改尾指針修改尾指針*/ return TRUE;循環(huán)隊(duì)列入隊(duì)操作循環(huán)隊(duì)列入隊(duì)操作循環(huán)隊(duì)列的出隊(duì)操作循環(huán)隊(duì)列的出隊(duì)操作算法說明：算法說明：刪除隊(duì)頭元素刪除隊(duì)頭元素, ,返回其值返回其值 x x并修改隊(duì)頭指針并修改隊(duì)頭指針 分分 析：析： （1 1） 在刪除前應(yīng)當(dāng)判斷隊(duì)列是否空？在刪除前應(yīng)當(dāng)判斷隊(duì)列是否空？ if (q-front = q-rear ) return false;if (q-front = q-rear ) return false; （2

40、 2）刪除動(dòng)作分析；）刪除動(dòng)作分析； 前面約定指針前面約定指針frontfront指向隊(duì)首元素的位置，故：指向隊(duì)首元素的位置，故： x= q-data q-front ; x= q-data q-front ; q-front = ( q-front + 1 ) % Maxsize; q-front = ( q-front + 1 ) % Maxsize; datatype DeQueue(SeqQueue *q) datatype x;if (q-front = = q-rear) printf(“n循環(huán)隊(duì)列空！循環(huán)隊(duì)列空！”); return FALSE; x = q-data q-fro

41、nt ；/ /* *出隊(duì)出隊(duì)* */ /q-front = (q-front+1)MAXSIZE；/ /* *修改隊(duì)頭指針修改隊(duì)頭指針* */ / return x；循環(huán)隊(duì)列出隊(duì)操作循環(huán)隊(duì)列出隊(duì)操作3.4 隊(duì)列的應(yīng)用隊(duì)列的應(yīng)用2 2、迷宮問題：尋找一條從迷宮入口到出口、迷宮問題：尋找一條從迷宮入口到出口的最短路徑的最短路徑 3 3、鍵盤輸入循環(huán)緩沖區(qū)問題鍵盤輸入循環(huán)緩沖區(qū)問題 例例3.7 打印楊輝三角形。打印楊輝三角形。 此問題是一個(gè)初等數(shù)學(xué)問題。系數(shù)表中的第此問題是一個(gè)初等數(shù)學(xué)問題。系數(shù)表中的第i i行有行有i+1i+1個(gè)個(gè)數(shù)，除了第數(shù)，除了第1 1個(gè)和最后一個(gè)數(shù)為個(gè)和最后一個(gè)數(shù)為1 1外，

42、其余的數(shù)則為上一行中外，其余的數(shù)則為上一行中位于其左、右的兩數(shù)之和。位于其左、右的兩數(shù)之和。（a+b）n的系數(shù)的系數(shù) 如果要計(jì)算并輸出二項(xiàng)系數(shù)表（即楊輝三角形）的如果要計(jì)算并輸出二項(xiàng)系數(shù)表（即楊輝三角形）的前前n n行的值，則所設(shè)循環(huán)隊(duì)列的最大空間應(yīng)為行的值，則所設(shè)循環(huán)隊(duì)列的最大空間應(yīng)為n+2n+2。假。假設(shè)隊(duì)列中已存有第設(shè)隊(duì)列中已存有第i i行的值，為計(jì)算方便，在行的值，為計(jì)算方便，在兩行之間兩行之間均加一個(gè)均加一個(gè)“0 0”作為行間的分隔符，則在計(jì)算第作為行間的分隔符，則在計(jì)算第i+1i+1行之行之前，頭指針正指向第前，頭指針正指向第i i行的行的“0 0”，而尾元素為第，而尾元素為第i+

43、1i+1行行的的“0 0”。由此，從左至右輸出第。由此，從左至右輸出第i i行的值，并將計(jì)算所行的值，并將計(jì)算所得的第得的第i+1i+1行的值插入隊(duì)列。行的值插入隊(duì)列。如第四行為： 0 1 4 6 4 1 第五行為： 0 1 5 10 10 5 1 分析第分析第 i i 行元素與第行元素與第 i+1i+1行元素的關(guān)系如圖所示行元素的關(guān)系如圖所示 ：在在i=2時(shí)時(shí),隊(duì)列的頭指針指向隊(duì)列的頭指針指向0，尾指針指向，尾指針指向1的下一位，我們看如何的下一位，我們看如何 由由第二行得到第三行的。第三行的第二行得到第三行的。第三行的0入隊(duì)入隊(duì)隊(duì)頭元素隊(duì)頭元素0出隊(duì)并送入出隊(duì)并送入s中中取隊(duì)頭元素取隊(duì)頭元

44、素1并送入并送入t中中s+t的值的值1入隊(duì)。入隊(duì)。這時(shí)隊(duì)列的隊(duì)頭指針指向這時(shí)隊(duì)列的隊(duì)頭指針指向1，隊(duì)尾指針指向第三行的第一個(gè)，隊(duì)尾指針指向第三行的第一個(gè)3的位置。重復(fù)三步就得到第的位置。重復(fù)三步就得到第三行；類推，我們由第三行又得到第四行；三行；類推，我們由第三行又得到第四行；frontrear楊輝三角形元素入隊(duì)順序161520156115101051146411331121111161520156115101051146411331121111000000 假設(shè)假設(shè)n=4n=4，i=3i=3，則輸出第，則輸出第3 3行元素并求解第行元素并求解第4 4行行元素值的循環(huán)執(zhí)行過程中隊(duì)列的變化狀態(tài)如

45、圖所元素值的循環(huán)執(zhí)行過程中隊(duì)列的變化狀態(tài)如圖所示示 ：void YangHui( int n )/*打印楊輝三角形的前打印楊輝三角形的前n行行*/ SeqQueue *q; int i, j,s,t; for(i=1;i=n;i+) printf( ); printf(1n); /*在中心位置輸出楊輝三角最頂端的在中心位置輸出楊輝三角最頂端的1*/ q=InitQueue(); /*設(shè)置容量為設(shè)置容量為n+2的空隊(duì)列的空隊(duì)列*/ EnQueue(q,0); /*添加行分隔符，添加行分隔符，即即0入隊(duì)入隊(duì)*/ EnQueue(q,1);EnQueue(q,1); /*第一行的值入隊(duì)第一行的值入隊(duì)

46、*/、出隊(duì)并保存出隊(duì)元素、出隊(duì)并保存出隊(duì)元素、取出、取出front所指元素并保存所指元素并保存、計(jì)算前兩步得到的元素值之、計(jì)算前兩步得到的元素值之和和并入隊(duì)并入隊(duì)重復(fù)這三步。（當(dāng)由第重復(fù)這三步。（當(dāng)由第i行求得第行求得第i+1行時(shí)，先入隊(duì)行時(shí)，先入隊(duì)）上圖的操作過程是：for(j=1;jn;j+) /*利用循環(huán)隊(duì)列輸出前利用循環(huán)隊(duì)列輸出前n-1行的值行的值*/for(i=1;in-j;i+) /*在輸出第在輸出第j行的首元素之間輸出行的首元素之間輸出n-j個(gè)空格個(gè)空格*/ printf( ); EnQueue(q,0); /*行分隔符行分隔符0入隊(duì)入隊(duì)*/ do /*輸出第輸出第j行并計(jì)算第行

47、并計(jì)算第j+1行行*/ s=DeQueue(q); /*刪除隊(duì)頭元素并賦給刪除隊(duì)頭元素并賦給s*/ t=GetHead(q); /*取隊(duì)頭元素給取隊(duì)頭元素給t*/ if(t) printf(%5 d,t); /*若不到行分隔符若不到行分隔符0，則輸出，則輸出t，再輸出一個(gè)空格，再輸出一個(gè)空格*/ else printf(n); /*否則輸出一個(gè)換行符否則輸出一個(gè)換行符*/ EnQueue(q,s+t); /*將第將第j+1行的對應(yīng)元素行的對應(yīng)元素s+t入隊(duì)入隊(duì)*/ while(t!=0); DeQueue(q); /* 刪除行分隔符刪除行分隔符 */ printf(%3d,DeQueue(q)

48、; /* 輸出第輸出第n行的第一個(gè)元素行的第一個(gè)元素 */ while(!QueueEmpty(q) /* 輸出第輸出第n行的其余元素行的其余元素 */ t=DeQueue(q); printf(“%5 d,t); 輸出楊輝三角形的最后一行（）第輸出楊輝三角形的最后一行（）第n n行行2 2、迷宮問題、迷宮問題： 尋找一條從迷宮入口到出口的最短路徑尋找一條從迷宮入口到出口的最短路徑 迷宮問題是實(shí)驗(yàn)心理學(xué)的一個(gè)經(jīng)典問題，心理學(xué)家把迷宮問題是實(shí)驗(yàn)心理學(xué)的一個(gè)經(jīng)典問題，心理學(xué)家把一只老鼠從一個(gè)無頂蓋的迷宮入口處趕進(jìn)迷宮，在迷宮的一只老鼠從一個(gè)無頂蓋的迷宮入口處趕進(jìn)迷宮，在迷宮的出口處設(shè)置了一塊奶酪，

49、吸引老鼠在迷宮中尋找通路以到出口處設(shè)置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達(dá)出口。對同一只老鼠重復(fù)進(jìn)行上述實(shí)驗(yàn)，一直到老鼠從達(dá)出口。對同一只老鼠重復(fù)進(jìn)行上述實(shí)驗(yàn)，一直到老鼠從入口到出口，而不走錯(cuò)一步。老鼠經(jīng)多次實(shí)驗(yàn)終于得到學(xué)入口到出口，而不走錯(cuò)一步。老鼠經(jīng)多次實(shí)驗(yàn)終于得到學(xué)習(xí)走通迷宮的路線。習(xí)走通迷宮的路線。 算法分析算法分析 如果用計(jì)算機(jī)來處理：求出一條從入口到出口的通路，或者得出如果用計(jì)算機(jī)來處理：求出一條從入口到出口的通路，或者得出沒有通路的結(jié)論。通常采用一種稱為沒有通路的結(jié)論。通常采用一種稱為回溯法回溯法的方法，即不斷試探且及的方法，即不斷試探且及時(shí)糾正錯(cuò)誤的搜索方法，這需要借助時(shí)

50、糾正錯(cuò)誤的搜索方法，這需要借助“棧?！眮韺?shí)現(xiàn)。此法在許多書中來實(shí)現(xiàn)。此法在許多書中都有介紹，在此不再贅述。都有介紹，在此不再贅述。 如果在一般走迷宮的方法上，更進(jìn)一步要求不論試探方位為何，如果在一般走迷宮的方法上，更進(jìn)一步要求不論試探方位為何，找出一條最短路徑，那該如何解決呢？其算法的基本思想是：從迷宮找出一條最短路徑，那該如何解決呢？其算法的基本思想是：從迷宮的入口的入口1111出發(fā)，向四周搜索，記下所有一步能到達(dá)的坐標(biāo)點(diǎn)；然出發(fā)，向四周搜索，記下所有一步能到達(dá)的坐標(biāo)點(diǎn)；然后依次從每一點(diǎn)出發(fā)，向四周搜索，記下所有從入口點(diǎn)出發(fā)，經(jīng)過兩后依次從每一點(diǎn)出發(fā)，向四周搜索，記下所有從入口點(diǎn)出發(fā)，經(jīng)過兩

51、步可以到達(dá)的坐標(biāo)點(diǎn)步可以到達(dá)的坐標(biāo)點(diǎn)依次進(jìn)行下去，一直到達(dá)迷宮的出口處依次進(jìn)行下去，一直到達(dá)迷宮的出口處mnmn。然后從出口處沿搜索路徑回溯直到入口點(diǎn)，這樣就找到了從入口到出然后從出口處沿搜索路徑回溯直到入口點(diǎn)，這樣就找到了從入口到出口的一條最短路徑?？诘囊粭l最短路徑。 0 1 1 1 0 1 1 11 0 1 0 1 0 1 00 1 0 0 1 1 1 10 1 1 1 0 1 1 11 0 0 1 1 0 0 10 1 1 0 0 1 1 0入口出口迷宮1 1 1 1 1 1 1 1 1 11 0 1 1 1 0 1 1 1 11 1 0 1 0 1 0 1 0 11 0 1 0 0 1

52、 1 1 1 11 0 1 1 1 0 1 1 1 11 1 0 0 1 1 0 0 1 11 0 1 1 0 0 1 1 0 11 1 1 1 1 1 1 1 1 1加哨兵后的迷宮 我們可以使用如下的數(shù)據(jù)結(jié)構(gòu)：我們可以使用如下的數(shù)據(jù)結(jié)構(gòu)：maze1.m,1.n表示表示迷宮，為了算法方便，在四周加上迷宮，為了算法方便，在四周加上“哨兵哨兵1”即變?yōu)榧醋優(yōu)閿?shù)組數(shù)組maze1.m+1,1.n+1，如右圖所示。用結(jié)構(gòu)數(shù)組，如右圖所示。用結(jié)構(gòu)數(shù)組move8中的兩個(gè)域中的兩個(gè)域dx，dy分別表示分別表示X，Y方向的移動(dòng)增方向的移動(dòng)增量量 方向方向下標(biāo)下標(biāo)dxdxdydy北北0 0-1-10 0東北東北1

53、 1-1-11 1東東2 20 01 1東南東南3 31 11 1南南4 41 10 0西南西南5 51 1-1-1西西6 60 0-1-1西北西北7 7-1-1-1-1各方向的移動(dòng)各方向的移動(dòng)增進(jìn)量表增進(jìn)量表,用一用一個(gè)結(jié)構(gòu)數(shù)組個(gè)結(jié)構(gòu)數(shù)組move8表示表示由于先到達(dá)的點(diǎn)要先向下搜索，故引進(jìn)一個(gè)由于先到達(dá)的點(diǎn)要先向下搜索，故引進(jìn)一個(gè)“先進(jìn)先出先進(jìn)先出”數(shù)數(shù)據(jù)結(jié)構(gòu)據(jù)結(jié)構(gòu)隊(duì)列隊(duì)列來保存已到達(dá)的點(diǎn)的坐標(biāo)。到達(dá)迷宮的出口來保存已到達(dá)的點(diǎn)的坐標(biāo)。到達(dá)迷宮的出口點(diǎn)點(diǎn)(m,n)(m,n)后，為了能夠從出口點(diǎn)沿搜索路徑回溯直至入口，對后，為了能夠從出口點(diǎn)沿搜索路徑回溯直至入口，對于每一點(diǎn)，在記下點(diǎn)的坐標(biāo)的同時(shí)

54、，還要記下到達(dá)該點(diǎn)的前于每一點(diǎn)，在記下點(diǎn)的坐標(biāo)的同時(shí)，還要記下到達(dá)該點(diǎn)的前驅(qū)點(diǎn)，因此，需用一個(gè)結(jié)構(gòu)數(shù)組驅(qū)點(diǎn)，因此，需用一個(gè)結(jié)構(gòu)數(shù)組sqnumsqnum作為隊(duì)列的存儲(chǔ)空間。作為隊(duì)列的存儲(chǔ)空間。因?yàn)槊詫m中每個(gè)點(diǎn)至多被訪問一次，所以因?yàn)槊詫m中每個(gè)點(diǎn)至多被訪問一次，所以numnum至多等于至多等于m m* *n n。sqsq的每一個(gè)結(jié)點(diǎn)有三個(gè)域：的每一個(gè)結(jié)點(diǎn)有三個(gè)域：x，y和和pre，其中，其中x,y分別為所到分別為所到達(dá)的點(diǎn)的坐標(biāo)，達(dá)的點(diǎn)的坐標(biāo)，pre為前驅(qū)點(diǎn)在為前驅(qū)點(diǎn)在sq中的下標(biāo)。除中的下標(biāo)。除sq外，還有外，還有隊(duì)頭、隊(duì)尾指針：隊(duì)頭、隊(duì)尾指針：front和和rear用來指向隊(duì)頭和隊(duì)尾元素。用來

55、指向隊(duì)頭和隊(duì)尾元素。 初始狀態(tài)是，隊(duì)列中只有一個(gè)元素初始狀態(tài)是，隊(duì)列中只有一個(gè)元素sq0 0，記錄的是入口，記錄的是入口點(diǎn)的坐標(biāo)（點(diǎn)的坐標(biāo)（,），因?yàn)樵擖c(diǎn)是出發(fā)點(diǎn)，因?yàn)樗鼪]有前），因?yàn)樵擖c(diǎn)是出發(fā)點(diǎn)，因?yàn)樗鼪]有前驅(qū)點(diǎn)，所以驅(qū)點(diǎn)，所以pre域?yàn)?，?duì)頭指針域?yàn)?，?duì)頭指針front和隊(duì)尾指針和隊(duì)尾指針rear均指向它。此后搜索時(shí)都是以均指向它。此后搜索時(shí)都是以front所指點(diǎn)為搜索的所指點(diǎn)為搜索的出發(fā)點(diǎn)，當(dāng)搜索到一個(gè)可到達(dá)的點(diǎn)時(shí)，就將該點(diǎn)的坐標(biāo)出發(fā)點(diǎn)，當(dāng)搜索到一個(gè)可到達(dá)的點(diǎn)時(shí)，就將該點(diǎn)的坐標(biāo)及及front所指點(diǎn)的位置入隊(duì)，不但記下了到達(dá)點(diǎn)的坐標(biāo)，所指點(diǎn)的位置入隊(duì)，不但記下了到達(dá)點(diǎn)的坐標(biāo)，還記下了它的前

56、驅(qū)點(diǎn)的下標(biāo)。若還記下了它的前驅(qū)點(diǎn)的下標(biāo)。若front所指點(diǎn)的個(gè)方向所指點(diǎn)的個(gè)方向搜索完畢，則出隊(duì)，繼續(xù)對下一點(diǎn)搜索。搜索過程中若搜索完畢，則出隊(duì)，繼續(xù)對下一點(diǎn)搜索。搜索過程中若遇到出口點(diǎn)，則表示成功，搜索結(jié)束，打印出迷宮的最遇到出口點(diǎn)，則表示成功，搜索結(jié)束，打印出迷宮的最短路徑，算法結(jié)束；如果當(dāng)前隊(duì)空，即表示沒有搜索點(diǎn)短路徑，算法結(jié)束；如果當(dāng)前隊(duì)空，即表示沒有搜索點(diǎn)了，則表明迷宮沒有通路，算法也結(jié)束。了，則表明迷宮沒有通路，算法也結(jié)束。 #include#define m 10#define n 15#define NUM m*ntypedef struct int x,y; /*x,y為到達(dá)

57、點(diǎn)的坐標(biāo)為到達(dá)點(diǎn)的坐標(biāo)*/ int pre; /*pre為（為（ x,y）的前驅(qū)點(diǎn)在數(shù)組）的前驅(qū)點(diǎn)在數(shù)組sq中的下標(biāo)中的下標(biāo)*/sqtype;int mazem+1n+1;typedef struct int dx; int dy; moved;void shortpath(int mazemn，movde move8) sqtype sqNUM;int front,rear；int x,y,i,j,v;front=rear=0;sq.x=1; sq.y=1; sq.pre=-1; /*選（選（1，1）點(diǎn)為入口點(diǎn)入隊(duì)）點(diǎn)為入口點(diǎn)入隊(duì)*/maze11=-1; /*表示該點(diǎn)搜索過了表示該點(diǎn)搜索過了,所以置成所以置成-1.該點(diǎn)是入口點(diǎn)原值為該點(diǎn)是入口點(diǎn)原值為0*/迷宮數(shù)組迷宮數(shù)組方向移動(dòng)增量數(shù)組方向移動(dòng)增量數(shù)組while (front=rear) /*隊(duì)列不空隊(duì)列不空*/x=sqf