DS03棧和隊列_第1頁
DS03棧和隊列_第2頁
DS03棧和隊列_第3頁
DS03棧和隊列_第4頁
DS03棧和隊列_第5頁
已閱讀5頁,還剩70頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領

文檔簡介

1、 第三章第三章 棧和隊列棧和隊列定義:定義: 限定只能在表的限定只能在表的進行插進行插入和刪除運算的線性表。入和刪除運算的線性表。在棧中在棧中 通常將表中允許進行插入、刪除操通常將表中允許進行插入、刪除操作的一端稱為作的一端稱為棧頂棧頂(Top),同時表的另一,同時表的另一端被稱為端被稱為棧底棧底(Bottom)。棧頂?shù)漠斍拔?。棧頂?shù)漠斍拔恢檬莿討B(tài)變化的,它由一個稱為棧頂指置是動態(tài)變化的,它由一個稱為棧頂指針的位置指示器指示。當棧中沒有元素針的位置指示器指示。當棧中沒有元素時稱為時稱為空??諚?。棧的插入操作被形象地稱棧的插入操作被形象地稱為為進棧進?;蛉霔?,刪除操作稱為出?;蚧蛉霔#瑒h除操作稱

2、為出棧或退退棧棧。棧的示意圖棧的示意圖ana2a1進棧出棧棧頂棧底進棧出棧(a) 棧的示意圖(b) 鐵路調(diào)序棧的表示與線性表相同,仍為一對一與線性表相同,仍為一對一( 1:1)( 1:1)關系。關系。用用或或存儲均可,但以順序棧更常見存儲均可,但以順序棧更常見只能在只能在運算,且訪問結(jié)點時依照運算,且訪問結(jié)點時依照(LIFOLIFO)或)或(FILOFILO)的原則。)的原則。關鍵是編寫關鍵是編寫和和函數(shù),具體實現(xiàn)依順函數(shù),具體實現(xiàn)依順序棧或鏈棧的存儲結(jié)構(gòu)有別而不同。序棧或鏈棧的存儲結(jié)構(gòu)有別而不同。 存儲結(jié)構(gòu)存儲結(jié)構(gòu) 運算規(guī)則運算規(guī)則 實現(xiàn)方式實現(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ù)牟僮?,稱為插入元素到棧頂?shù)牟僮鳎Q為入入。從棧頂刪除最后一個元素的操作,稱為從棧頂刪除最后一個元素的操作,稱為出棧出棧。a an n稱為棧頂元素稱為棧頂元素a a1 1稱為棧底元素稱為棧底元素插入和刪除都只能在表插入和刪除都只能

4、在表的一端(棧頂)進行!的一端(棧頂)進行!棧的物理表示法棧的物理表示法一、順序棧的存儲結(jié)構(gòu)和操作的實現(xiàn)一、順序棧的存儲結(jié)構(gòu)和操作的實現(xiàn) 順序棧順序棧: :是利用一組地址連續(xù)的存儲單元依次存放從棧底到是利用一組地址連續(xù)的存儲單元依次存放從棧底到棧頂?shù)臄?shù)據(jù)元素。棧頂?shù)臄?shù)據(jù)元素。 a1 a2 an順序棧順序棧S ai0n+1棧底棧底棧頂棧頂壓入壓入( (SS+=a=a彈出彈出( ( - 棧的基本操作棧的基本操作 ClearStack(S)ClearStack(S):棧棧S S已經(jīng)存在,清除棧已經(jīng)存在,清除棧S S中的所有元素中的所有元素將將S S置成空棧置成空棧。 InitStack( )Init

5、Stack( ): 初始化,構(gòu)造一個空棧初始化,構(gòu)造一個空棧S S StackEmpty(S)StackEmpty(S):判斷棧判斷棧S S是否為空,若為空,則返回是否為空,若為空,則返回 truetrue;否則返回;否則返回falsefalse GetTop(S)GetTop(S) : 返回返回S S的棧頂元素,但不移動棧頂指針的棧頂元素,但不移動棧頂指針 也不改變棧頂元素的值也不改變棧頂元素的值 Push(S, x)Push(S, x) :在在S的頂部插入的頂部插入(亦稱壓入亦稱壓入)元素元素x;若;若S棧未棧未滿,將滿,將x插入棧頂位置,若棧已滿,則返回插入棧頂位置,若棧已滿,則返回FA

6、LSE,表示,表示操作失敗,否則返回操作失敗,否則返回TRUE。 (入棧操作(入棧操作) ) Pop(S)Pop(S) : 刪除刪除S S的棧頂元素并返回其值(出棧操作)的棧頂元素并返回其值(出棧操作)順序棧存儲結(jié)構(gòu)的描述:順序棧存儲結(jié)構(gòu)的描述:/*設順序棧的最大長度為100,可依實現(xiàn)情況而修改*/structstruct datatype stackMaxsize;datatype stackMaxsize;int topint top/ /* *棧頂指針棧頂指針* */ / /* *順序棧類型定義順序棧類型定義* */ / /* *s s為順序棧類型變量的指針為順序棧類型變量的指針* */

7、 /順序棧的幾種狀態(tài)以及在這些狀態(tài)下棧頂指針順序棧的幾種狀態(tài)以及在這些狀態(tài)下棧頂指針toptop和棧和棧中結(jié)點的關系中結(jié)點的關系 棧為空的條件棧為空的條件 : top = = 0; top = = 0;棧滿的條件棧滿的條件 : top = = Maxsize top = = Maxsize若入棧動作使地址向高端增長,稱為若入棧動作使地址向高端增長,稱為“向上生成向上生成”的棧;的棧;若入棧動作使地址向低端增長,稱為若入棧動作使地址向低端增長,稱為“向下生成向下生成”的棧的棧; 對于向上生成的堆棧對于向上生成的堆棧: :棧指針指向待壓入位置棧指針指向待壓入位置入棧入棧:棧指針:棧指針top “t

8、op “先壓后加先壓后加” ” : S: Stop+top+=a=ai i出棧出棧:棧指針:棧指針top “top “先減后彈先減后彈” ” : e=S: e=S- -top- -top 順序棧的基本操作順序棧的基本操作構(gòu)造一個空順序棧構(gòu)造一個空順序棧 SeqStack * InitStack( ) SeqStack *S ;S=(SeqStack *)malloc(sizeof(SeqStack);if(!S) /*空間申請失敗空間申請失敗*/ printf(“空間不足空間不足”);return NULL; else S-top=0; return S; 取順序棧棧頂元素取順序棧棧頂元素 d

9、atatype GetTop(SeqStack *S) if (S-top=0) printf(n棧是空的棧是空的!); return FALSE; else return S-stackS-top-1; 該函數(shù)返回一個該函數(shù)返回一個datatype類型的值類型的值判別空棧判別空棧int StackEmpty(SeqStack *S) if(S-top=0) return TRUE; else return FALSE; 順序棧的入棧操作順序棧的入棧操作例如用堆棧存放(例如用堆棧存放(A A,B B,C C,D D)AACBABAtop核心語句:核心語句:順序棧入棧函數(shù)順序棧入棧函數(shù)PUSHP

10、USH()()SeqStack*Push(SeqStack*S,datatype x) if(S-top=Maxsize) return NULL; else S-stackS-top=x; S-top+; return s; Push (s,B);Push (s,C);Push (s,D);toptoptoptop低地址低地址LPush (s,A);高地址高地址MBCD順序棧出棧操作順序棧出棧操作例如從棧中取出例如從棧中取出 DCBAtoptopDCABDCBAtopDCBAtop低地址低地址L高地址高地址MD核心語句:核心語句:pop ( );順序棧出棧函數(shù)順序棧出棧函數(shù)POP( )POP

11、( )datatype pop( SeqStack *S) if(S-top= =0) printf(nThe sequence stack is empty!); return FALSE; S-top-; return S-stackS-top; pop ( );printf( pop ( ) );例例3.13.1 用用mainmain函數(shù)以及函數(shù)以及displaydisplay函數(shù),調(diào)試上述各種棧的基函數(shù),調(diào)試上述各種棧的基本操作算法。本操作算法。 #define Maxsize 50 typedef int datatype; typedef struct datatype stack

12、Maxsize; 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()int a6=3,7,4,12,31,15,i; SeqStack *p; p= InitStack(); for(i=0;itop=0; S-top=0; /*清空棧清空棧*/ else else /*c1是

13、普通字符是普通字符*/ push(s,c1); /*入棧入棧*/ Scanf(“%c”,&c1); Scanf(“%c”,&c1); display(s); /*輸出棧輸出棧s的所有元素值的所有元素值*/ 鏈鏈 棧棧二、鏈棧的存儲結(jié)構(gòu)及操作的實現(xiàn)二、鏈棧的存儲結(jié)構(gòu)及操作的實現(xiàn) 棧也可以用鏈式結(jié)構(gòu)來表示,用鏈式棧也可以用鏈式結(jié)構(gòu)來表示,用鏈式結(jié)構(gòu)來表示的棧就是結(jié)構(gòu)來表示的棧就是鏈棧鏈棧鏈棧的構(gòu)造方式鏈棧的構(gòu)造方式以頭指針為棧頂,以頭指針為棧頂,在頭指針處在頭指針處插入或刪除插入或刪除. .一般情況下,頭結(jié)點即為第一個結(jié)點一般情況下,頭結(jié)點即為第一個結(jié)點棧頂棧頂棧底棧底 a1 a2an-1 ann

14、extdata 鏈棧中每個結(jié)點由兩個域構(gòu)成:鏈棧中每個結(jié)點由兩個域構(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=(Linkstack*)

15、malloc(sizeof(LinkStack); p-data=x; p-next=top; top=p; return top; 鏈棧入棧操作鏈棧入棧操作棧頂指針指向新申請結(jié)點的地址修改棧頂指針鏈棧的出棧操作鏈棧的出棧操作a an n出棧,使工作指針出棧,使工作指針q q指向要出棧結(jié)點,然指向要出棧結(jié)點,然后修改棧頂指針后修改棧頂指針: :top=top-nexttop=top-next LinkStack *pop( LinkStack *top) LinkStack *q; if(!top) /*說明指針top指向NULL*/ printf(“n鏈棧是空的!”); return NUL

16、L; q=top; top=top-next; free(q); return top; 鏈棧出棧操作鏈棧出棧操作1、數(shù)制轉(zhuǎn)換(十轉(zhuǎn)數(shù)制轉(zhuǎn)換(十轉(zhuǎn)N N) 設計思路:用棧暫存低位值設計思路:用棧暫存低位值2、括號匹配問題括號匹配問題 設計思路:用棧暫存左括號設計思路:用棧暫存左括號3、子程序的調(diào)用子程序的調(diào)用 設計思路:用棧暫存指令地址設計思路:用棧暫存指令地址4、逆置一個單鏈表逆置一個單鏈表 設計思路:用棧暫存每一結(jié)點設計思路:用棧暫存每一結(jié)點例例3.2 3.2 將十進制整數(shù)轉(zhuǎn)換成二至九之間的任一將十進制整數(shù)轉(zhuǎn)換成二至九之間的任一進制數(shù)輸出進制數(shù)輸出 將一個十進制數(shù)將一個十進制數(shù)432743

17、27轉(zhuǎn)換成八進制數(shù)轉(zhuǎn)換成八進制數(shù)(10347)(10347)8 8:N是十進制數(shù),要將是十進制數(shù),要將N轉(zhuǎn)換轉(zhuǎn)換成成r進制數(shù)進制數(shù)1、當、當N0,將,將N%r壓入棧壓入棧s中,即余數(shù)進棧;中,即余數(shù)進棧; 2、用、用N/r代替代替N;3、若、若N0,則重復上兩步;,則重復上兩步;若若N=0,則將棧,則將棧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òu)造一

18、個順序棧*/ while(N!=0) push(s, N %r ); /*將將N%r入棧入棧*/ N=N/r ; printf(“n十進制數(shù)十進制數(shù)%d所對應的所對應的%d進制數(shù)進制數(shù)是是:”,x,y);while(!StackEmpty(s) /*棧非空時,出棧棧非空時,出棧*/ printf(“%d”,pop(s); printf(“n”); 例例3.5 3.5 利用一個順序棧將單鏈表(利用一個順序棧將單鏈表(a a1 1,a,a2 2,a,an n)(其中(其中n=0n=0)逆置為()逆置為(a an n,a,an-1n-1,,a a1 1)1 1、建立一個帶頭結(jié)點的單鏈表、建立一個帶頭

19、結(jié)點的單鏈表headhead;2 2、輸出該單鏈表;、輸出該單鏈表;3 3、建立一個空棧、建立一個空棧s s(順序棧);(順序棧);4 4、依次將單鏈表的數(shù)據(jù)入棧;、依次將單鏈表的數(shù)據(jù)入棧;5 5、依次將單鏈表的數(shù)據(jù)出棧,、依次將單鏈表的數(shù)據(jù)出棧,并逐個將出棧的數(shù)據(jù)存入單鏈表并逐個將出棧的數(shù)據(jù)存入單鏈表的數(shù)據(jù)域(自前向后)的數(shù)據(jù)域(自前向后); ;6 6、再輸出單鏈表。、再輸出單鏈表。 解題思路如下:解題思路如下:linklist*backlinklist(linklist *head) /*利用順序棧逆置單鏈表利用順序棧逆置單鏈表head */linklist *p; /*工作指針工作指針*

20、/ p=head-next; /*p指向單鏈表的第一個結(jié)點指向單鏈表的第一個結(jié)點*/ initstack( ); / /* *初始化一個順序棧初始化一個順序棧s,ss,s是結(jié)構(gòu)體類型是結(jié)構(gòu)體類型* */ / while(p) push(&s, p-data); p=p-next ; p=head-next; while(!stackempty(s) /*將順序表的數(shù)據(jù)出棧將順序表的數(shù)據(jù)出棧*/ /*將出棧后的數(shù)據(jù)存入單鏈表將出棧后的數(shù)據(jù)存入單鏈表headhead中中*/ p-data=pop(&s); p=p-next; return (head); 隊列隊列 (Queue)是另一種限定性的是

21、另一種限定性的線性表線性表,它只允許在表的一端插入元素,而在另一端它只允許在表的一端插入元素,而在另一端刪除元素刪除元素,所以隊列具有先進先出先進先出(Fist In Fist Out, 縮寫為FIFO)的特性。隊列的定義隊列的定義 在隊列中,允許插入的一端叫做在隊列中,允許插入的一端叫做隊尾隊尾(rear),允許刪除的一端則稱為允許刪除的一端則稱為隊頭隊頭(front)。 假設隊列假設隊列為為q=(a1,a2,an),那么,那么a1就是隊頭元素,就是隊頭元素,an則是隊尾元素。隊列中的元素是按照則是隊尾元素。隊列中的元素是按照a1,a2,an的順序進入的,的順序進入的, 退出隊列也必須按退出

22、隊列也必須按照同樣的次序依次出隊,也就是說,只有在照同樣的次序依次出隊,也就是說,只有在a1,a2,an-1都離開隊列之后,都離開隊列之后,an才能退出隊列。才能退出隊列。問:為什么要設計隊列?它有什么獨特用途?問:為什么要設計隊列?它有什么獨特用途? 離散事件的模擬(模擬事件發(fā)生的先后順離散事件的模擬(模擬事件發(fā)生的先后順序序, ,例如例如 CPUCPU芯片中的指令譯碼隊列);芯片中的指令譯碼隊列); 操作系統(tǒng)中的作業(yè)調(diào)度(一個操作系統(tǒng)中的作業(yè)調(diào)度(一個CPUCPU執(zhí)行多個執(zhí)行多個作業(yè));作業(yè)); 與線性表相同,仍為一對一關系。與線性表相同,仍為一對一關系。順序隊順序隊或或鏈隊鏈隊,以,以循

23、環(huán)順序隊循環(huán)順序隊更常見。更常見。只能在隊首和隊尾運算,且訪問結(jié)點時依照只能在隊首和隊尾運算,且訪問結(jié)點時依照先進先出(FIFOFIFO)的原則。的原則。關鍵是掌握關鍵是掌握入隊入隊和和出隊出隊操作,具體實現(xiàn)依順操作,具體實現(xiàn)依順序隊或鏈隊的不同而不同。序隊或鏈隊的不同而不同。入隊或出隊,建空隊列,判隊空或隊滿等操作。入隊或出隊,建空隊列,判隊空或隊滿等操作。關鍵是掌握關鍵是掌握入隊入隊和和出隊出隊操作。操作。具體實現(xiàn)依具體實現(xiàn)依存儲結(jié)構(gòu)存儲結(jié)構(gòu)(鏈隊鏈隊或或順序隊順序隊)的不同而不同。)的不同而不同。(1 1)InitQueue ( )InitQueue ( ): 構(gòu)造一個空隊列構(gòu)造一個空隊

24、列Q Q(2 2)QueueEmpty (Q)QueueEmpty (Q): 判斷隊列是否為空判斷隊列是否為空 (3 3)QueueLength (Q)QueueLength (Q): 求隊列的長度求隊列的長度 (4 4)GetHead (Q)GetHead (Q): 返回返回Q Q的隊頭元素,不改變隊列狀態(tài)的隊頭元素,不改變隊列狀態(tài) (5 5)EnQueue(QEnQueue(Q, x )x ): 插入元素插入元素x x為為Q Q的新的隊尾元素的新的隊尾元素 (6 6)DeQueue(Q)DeQueue(Q): 刪除刪除Q Q的隊頭元素的隊頭元素(7 7)ClearQueue(Q)Clear

25、Queue(Q):清除隊列:清除隊列Q Q中的所有元素中的所有元素 隊列隊列(QueueQueue)的邏輯表示的邏輯表示 假設隊列為Q=(a1,a2,an),那么a1就是隊頭元素,an則是隊尾元素。隊列中的元素是按照a1,a2,an的順序進入的, 退出隊列也必須按照同樣的次序依次出隊,也就是說,只有在a1,a2,an-1都離開隊列之后,an才能退出隊列。例如:隊列例如:隊列 Q= (a1 , a2 , a3 , .,an-1 , an )隊首隊首隊尾隊尾鏈隊列類型定義:鏈隊列類型定義: typedef struct Qnode *front ; /*隊頭指針*/ Qnode *rear ; /

26、*隊尾指針*/ LinkQueue; 結(jié)點類型定義:結(jié)點類型定義: typedef Struct Qnode datatype data; /*數(shù)據(jù)域*/ Struct Qnode *next; /*指針域*/ Qnode; 隊列隊列(QueueQueue)的物理表示的物理表示鏈隊的幾種狀態(tài)示意圖:鏈隊的幾種狀態(tài)示意圖: 空鏈隊的特征?空鏈隊的特征?front=rearfront=rear 鏈隊會滿嗎?鏈隊會滿嗎?一般不會,因為刪除時有一般不會,因為刪除時有freefree動作。除非內(nèi)存不足!動作。除非內(nèi)存不足!(b)元素x入隊(d)元素x出隊此時,front= =rear修改rear指針修改

27、頭結(jié)點的指針域入隊(尾部插入):入隊(尾部插入):rear-next=S; rear=S;rear-next=S; rear=S;出隊(頭部刪除):出隊(頭部刪除):front-next=S-next;front-next=S-next; 怎樣實現(xiàn)鏈隊的怎樣實現(xiàn)鏈隊的入隊和出隊入隊和出隊操作?操作? 若設若設S S所指結(jié)點為入隊或出隊結(jié)點所指結(jié)點為入隊或出隊結(jié)點LinkQueue *InitQueue( ) LinkQueue *q; Qnode *p; q=(LinkQueue*)malloc(sizeof(LinkQueue); p=(Qnode*)malloc(sizeof(Qnode)

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

29、 = p; Q-rear=p; datatype DeQueue(LinkQueue *Q) Qnode *p; datatype x; if (Q-front = Q-rear) printf(隊列為空!隊列為空!); return FALSE; p = Q-front-next; x = p-data; Q-front-next = p-next; if(Q-rear = p) /*此時此時p出隊出隊,則隊列為空則隊列為空*/ Q-rear=Q-front; free(p); return x; 2、順序隊列、順序隊列 順序隊列類型定義:順序隊列類型定義:#define MAXSIZE 1

30、00 /*最大隊列長度最大隊列長度*/typedef structdatatype dataMAXSIZE; /* 存儲隊列的數(shù)據(jù)空間存儲隊列的數(shù)據(jù)空間*/int front; /*隊頭指針隊頭指針*/int rear; /*隊尾指針隊尾指針*/SeqQueue; 約定:約定:隊頭指針隊頭指針front,若隊列不空,則指向隊頭元素,若隊列不空,則指向隊頭元素。隊尾指針隊尾指針rear,若隊列不空,則指向隊尾元素的下一個,若隊列不空,則指向隊尾元素的下一個位置位置。順序隊的幾種狀態(tài)示意圖順序隊的幾種狀態(tài)示意圖 頭指針始終指向隊頭元素,尾指針始終指向隊尾元素的下一個頭指針始終指向隊頭元素,尾指針始

31、終指向隊尾元素的下一個元素元素 為了防止出現(xiàn)假溢出,即在假溢出時,還能進行入隊操作,我為了防止出現(xiàn)假溢出,即在假溢出時,還能進行入隊操作,我們采取循環(huán)隊列。們采取循環(huán)隊列。循環(huán)隊列示意圖循環(huán)隊列示意圖在入隊時:在入隊時: 將數(shù)據(jù)區(qū)將數(shù)據(jù)區(qū)data0Maxsize-1看成是首尾相接的圓環(huán)看成是首尾相接的圓環(huán),當當入隊到入隊到Maxsize-1時時,若隊頭元素的前面仍有空閑位置若隊頭元素的前面仍有空閑位置,下一個下一個地址就應翻轉(zhuǎn)為地址就應翻轉(zhuǎn)為0,使使data0接在接在dataMaxsize-1之后之后在出隊時:在出隊時:隊頭指針也要采用front=(front+1)%Maxaize通過求余運算

32、通過求余運算rear=(rear+1)%Maxsize來求得。來求得。循環(huán)隊列的幾種狀態(tài)循環(huán)隊列的幾種狀態(tài)在循環(huán)隊列中當采用在循環(huán)隊列中當采用入隊操作入隊操作: : rear=(rear+1)%Maxsize出隊操作出隊操作: : front=(front+1)%Maxaize就會出現(xiàn)新問題:就會出現(xiàn)新問題:空隊和隊滿時都有空隊和隊滿時都有front=rear; 那么又如何判斷隊空和隊滿?那么又如何判斷隊空和隊滿?隊空條件隊空條件 : : front = = rearfront = = rear ( (初始化時:初始化時:front=rear)front=rear)隊滿條件隊滿條件: fron

33、t=front=(rearrear)%N)%N (N=maxsize) (N=maxsize)J2 J3J1 J4 J5frontrear 解決方案解決方案-人為人為浪費一個單元浪費一個單元: 即對大小為即對大小為MaxsizeMaxsize的數(shù)組,只允許存的數(shù)組,只允許存Maxsize-1Maxsize-1個結(jié)點個結(jié)點。為此我們約定:為此我們約定:front和和rear二者之一指向?qū)嵲?,另一個指向二者之一指向?qū)嵲?,另一個指向空閑元素空閑元素(假設假設front指向隊頭元素,指向隊頭元素,rear指向隊尾元素的下一個指向隊尾元素的下一個位置,位置,即即rear 所指的單元始終為空所指的單元

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

35、以建隊、入隊和出隊三種基本操作為例建循環(huán)隊的完整算法建循環(huán)隊的完整算法SeqQueue *initQueue( ) SeqQueue *q; q=(SeqQueue*)malloc(sizeof(SeqQueue); /*開辟一個足夠大的存儲隊列的空間*/ q-front = q-rear = 0;/*將隊列頭尾指針置為零*/ return q; /*返回隊列的首地址*/ 順序存儲算法說明:向循環(huán)隊列的隊尾插入一個元素算法說明:向循環(huán)隊列的隊尾插入一個元素分析分析:(1) (1) 插入前應當先判斷隊列是否滿?插入前應當先判斷隊列是否滿? if ( q -rear + 1 ) % Maxsize

36、 )=q-front)if ( q -rear + 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)隊列入隊操作循環(huán)隊列入隊操作隊列尺寸隊列尺寸int EnQueue(SeqQueue *q, datatype x)if(q-rear+1)MAXSIZE=q-fr

37、ont) printf(n循環(huán)隊列滿循環(huán)隊列滿!);return FALSE; q-dataq-rear = x; /*元素元素x入隊入隊*/ q-rear = (q-rear+1)%MAXSIZE; /*修改尾指針修改尾指針*/ return TRUE;循環(huán)隊列入隊操作循環(huán)隊列入隊操作循環(huán)隊列的出隊操作循環(huán)隊列的出隊操作算法說明:算法說明:刪除隊頭元素刪除隊頭元素, ,返回其值返回其值 x x并修改隊頭指針并修改隊頭指針 分分 析:析: (1 1) 在刪除前應當判斷隊列是否空?在刪除前應當判斷隊列是否空? if (q-front = q-rear ) return false;if (q-f

38、ront = q-rear ) return false; (2 2)刪除動作分析;)刪除動作分析; 前面約定指針前面約定指針frontfront指向隊首元素的位置,故:指向隊首元素的位置,故: x= q-data q-front ; x= q-data q-front ; q-front = ( q-front + 1 ) % Maxsize; q-front = ( q-front + 1 ) % Maxsize; frontfront指針在元素出隊后再加指針在元素出隊后再加datatype DeQueue(SeqQueue *q) datatype x;if (q-front = = q

39、-rear) printf(“n循環(huán)隊列空!循環(huán)隊列空!”); return FALSE; x = q-data q-front ;/ /* *出隊出隊* */ /q-front = (q-front+1)MAXSIZE;/ /* *修改隊頭指針修改隊頭指針* */ / return x;循環(huán)隊列出隊操作循環(huán)隊列出隊操作3.4 隊列的應用隊列的應用2 2、迷宮問題:尋找一條從迷宮入口到出口、迷宮問題:尋找一條從迷宮入口到出口的最短路徑的最短路徑 例例3.7 打印楊輝三角形。打印楊輝三角形。 此問題是一個初等數(shù)學問題。系數(shù)表中的第此問題是一個初等數(shù)學問題。系數(shù)表中的第i i行有行有i+1i+1個

40、個數(shù),除了第數(shù),除了第1 1個和最后一個數(shù)為個和最后一個數(shù)為1 1外,其余的數(shù)則為上一行中外,其余的數(shù)則為上一行中位于其左、右的兩數(shù)之和。位于其左、右的兩數(shù)之和。(a+b)n的系數(shù)的系數(shù) 如果要計算并輸出二項系數(shù)表(即楊輝三角形)如果要計算并輸出二項系數(shù)表(即楊輝三角形)的前的前n n行的值,則所設循環(huán)隊列的最大空間應為行的值,則所設循環(huán)隊列的最大空間應為n+2n+2。如第四行為: 0 1 4 6 4 1第五行為: 0 1 5 10 10 5 1 假設隊列中已存有第假設隊列中已存有第i行的值,為計算方便,在行的值,為計算方便,在兩行之兩行之間均加一個間均加一個“0”作為行間的分隔符,則在計算第

41、作為行間的分隔符,則在計算第i+1行之前,行之前,頭指針正指向第頭指針正指向第i行的行的“0”,而尾元素為第,而尾元素為第i+1行的行的“0”。由。由此,從左至右輸出第此,從左至右輸出第i行的值,并將計算所得的第行的值,并將計算所得的第i+1行的值行的值插入隊列。插入隊列。分析第分析第 i i 行元素與第行元素與第 i+1i+1行元素的關系如圖所示行元素的關系如圖所示 :在在i=2時時,隊列的頭指針指向隊列的頭指針指向0,尾指針指向,尾指針指向1的下一位,的下一位,我們看如何我們看如何 由第二行得到第三行的。由第二行得到第三行的。第三行的第三行的0入隊入隊隊頭元素隊頭元素0出隊并送入出隊并送入

42、s中中取隊頭元素取隊頭元素1并送入并送入t中中s+t的值的值1入隊。入隊。frontrear這時隊列的隊頭指針指向這時隊列的隊頭指針指向1,隊尾指針指向第三行的第一個,隊尾指針指向第三行的第一個3的位置。的位置。重復重復三步就得到第三行;類推,我們由第三行又得到第四行三步就得到第三行;類推,我們由第三行又得到第四行從第從第 2行數(shù)據(jù)計算并存放第行數(shù)據(jù)計算并存放第 3 行數(shù)據(jù)行數(shù)據(jù)0 在運算的任一時刻在運算的任一時刻,要產(chǎn)生下一個入隊的元要產(chǎn)生下一個入隊的元素素,均是隊頭方向的兩元均是隊頭方向的兩元素相加后入隊素相加后入隊.楊輝三角形元素入隊順序1615201561151010511464113

43、31121111161520156115101051146411331121111000000 假設假設n=4n=4,i=3i=3,則輸出第,則輸出第3 3行元素并求解第行元素并求解第4 4行行元素值的循環(huán)執(zhí)行過程中隊列的變化狀態(tài)如圖所元素值的循環(huán)執(zhí)行過程中隊列的變化狀態(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=InitQu

44、eue(); /*設置容量為設置容量為n+2的空隊列的空隊列*/ EnQueue(q,0); /*添加行分隔符,添加行分隔符,即即0入隊入隊*/ EnQueue(q,1);EnQueue(q,1); /*第一行的值入隊第一行的值入隊*/、出隊并保存出隊元素、出隊并保存出隊元素、取出、取出front所指元素并保存所指元素并保存、計算前兩步得到的元素值之、計算前兩步得到的元素值之和和并入隊并入隊重復這三步。(當由第重復這三步。(當由第i行求得第行求得第i+1行時,先入隊行時,先入隊)上圖的操作過程是:for(j=1;jn;j+) /*利用循環(huán)隊列輸出前利用循環(huán)隊列輸出前n-1行的值行的值*/for

45、(i=1;i 0n 0時時n!n!2 遞歸函數(shù):一個直接調(diào)用自己或通過一系列調(diào)用間接調(diào)遞歸函數(shù):一個直接調(diào)用自己或通過一系列調(diào)用間接調(diào)用自己的函數(shù)稱為遞歸函數(shù)。用自己的函數(shù)稱為遞歸函數(shù)。 A( ) A( ) ; B( ) C( ) C( ); B( ); A 直接調(diào)用自己B間接調(diào)用自己3遞歸算法的編寫遞歸算法的編寫1)將問題用遞歸的方式描述)將問題用遞歸的方式描述2)根據(jù)問題的遞歸描述編寫遞歸算法)根據(jù)問題的遞歸描述編寫遞歸算法 例例 n!的遞歸定義的遞歸定義 基本項:基本項: n!=1 當當 n=0,1 遞歸項:遞歸項: n!=n (n-1)! 當當 n 0遞歸算法的編寫和執(zhí)行過程遞歸算法的編寫和執(zhí)行過程問題的遞歸描述(定義)問題的遞歸描述(定義) 遞歸定義包括兩項遞歸定義包括兩項 基本項(終止項):描述遞歸

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論