1、棧3.1棧的應用舉例3.2隊列3.3（1 1）掌握棧的定義、運算和存儲結構。）掌握棧的定義、運算和存儲結構。（2 2）掌握隊列的定義、運算和存儲結構）掌握隊列的定義、運算和存儲結構（3 3）掌握棧和隊列的實現方法，并能使用棧解決實際）掌握棧和隊列的實現方法，并能使用棧解決實際問題。問題。棧和隊列的特點，在兩種存儲結構上棧的基本操作的實棧和隊列的特點，在兩種存儲結構上棧的基本操作的實現，循環隊列和鏈隊列的基本運算。現，循環隊列和鏈隊列的基本運算。兩種存儲結構上棧的基本操作的算法實現，循環隊列兩種存儲結構上棧的基本操作的算法實現，循環隊列和鏈隊列的基本運算。和鏈隊列的基本運算。 是僅在是僅在表尾表

2、尾進行插入、刪除操作的線性表。進行插入、刪除操作的線性表。表尾表尾(即即 an 端端)稱為稱為棧頂棧頂 /top ; 表頭表頭(即即 a1 端端)稱為稱為棧底棧底/base例如：例如： 棧棧 = (a1 , a2 , a3 , .,an-1 , an )插入元素到棧頂的插入元素到棧頂的操作，稱為操作，稱為入棧入棧。從棧頂刪除最后一從棧頂刪除最后一個元素的操作，稱個元素的操作，稱為為出棧出棧。a an n稱為棧頂元素稱為棧頂元素a a1 1稱為棧底元素稱為棧底元素插入和刪除都只能在表插入和刪除都只能在表的一端（棧頂）進行！的一端（棧頂）進行！3.1 3.1 棧棧問題問題1 1：堆棧是什么？它與一

3、般線性表有什么不同？：堆棧是什么？它與一般線性表有什么不同？ 堆棧是一種特殊的線性表，它只能在表的堆棧是一種特殊的線性表，它只能在表的一端（即一端（即棧頂）進行插入和刪除運算。棧頂）進行插入和刪除運算。邏輯結構：邏輯結構：1:1 邏輯結構：邏輯結構： 1:1 存儲結構：順序表、鏈表存儲結構：順序表、鏈表 存儲結構：順序棧、鏈棧存儲結構：順序棧、鏈棧運算規則：隨機存取運算規則：隨機存取 運算規則：后進先出運算規則：后進先出(LIFO)“進進”插入插入= =壓入壓入=PUSH=PUSH（a an+1n+1) )“出出”刪除刪除= =彈出彈出=POP(a=POP(an n) ) a1 a2 an棧棧

4、S ai低地址低地址高地址高地址 an+1棧底棧底棧頂棧頂出棧出棧進棧進棧問題問題2 2：為什么要設計堆棧？它有什么獨特用途？：為什么要設計堆棧？它有什么獨特用途？1.調用函數或子程序非它莫屬；調用函數或子程序非它莫屬；2.遞歸運算的有力工具；遞歸運算的有力工具；3.用于保護現場和恢復現場；用于保護現場和恢復現場；4.簡化了程序設計的問題。簡化了程序設計的問題。下面用下面用3個例子來幫助理解堆棧：個例子來幫助理解堆棧：例例1.一個棧的輸入序列為一個棧的輸入序列為1,2,31,2,3，若在入棧的過程中允許出，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？棧，則可能得到的出棧序列是什么？答

5、：答： 可以通過窮舉所有可能性來求解：可以通過窮舉所有可能性來求解： 1 1入入1 1出，出， 2 2入入2 2出，出，3 3入入3 3出，出， 即即123123； 1 1入入1 1出，出， 2 2、3 3入，入，3 3、2 2出，出， 即即132132； 1 1、2 2入，入，2 2出，出， 3 3入入3 3出，出， 即即231231； 1 1、2 2入，入，2 2、1 1出，出，3 3入入3 3出，出， 即即213213； 1 1、2 2、3 3入，入，3 3、2 2、1 1出，出， 即即321321；合計有合計有5 5種可能性。種可能性。例1：例2：一個棧的輸入序列是一個棧的輸入序列是1

6、234512345，若在入棧的過程，若在入棧的過程中允許出棧，則棧的輸出序列中允許出棧，則棧的輸出序列4351243512可能實現嗎？可能實現嗎？1234512345的輸出呢？的輸出呢？答：答：4351243512不可能實現，主要是其中的不可能實現，主要是其中的1212順序不能實現；順序不能實現；1234512345的輸出可以實現，每壓入一數便立即彈出即。的輸出可以實現，每壓入一數便立即彈出即。 思考：有無通用的判別原則？思考：有無通用的判別原則？例2：設依次進入一個棧的元素序列為設依次進入一個棧的元素序列為c，a，b，d，則可，則可得到出棧的元素序列是：得到出棧的元素序列是： ）a，b，c，

7、d ）c，d，a，b ）b，c，d，a ）a，c，d，bA）、）、D）可以，）可以， B）、）、C）不行。）不行。討論：有無通用的判別原則？討論：有無通用的判別原則？有！若輸入序列有！若輸入序列 ,P,Pj jP Pk kP Pi i (P(Pj jPPk kPPi i) )，一定不存在這樣的輸出序列一定不存在這樣的輸出序列 ,P,Pi iP Pj jP Pk k 答：答：即對于輸入序列即對于輸入序列1，2，3，不存在輸出序列，不存在輸出序列3，1，2例3：棧的抽象數據類型定義棧的抽象數據類型定義 ADT Stack 數據對象：數據對象： D=ai| aiElemSet，1in， n0 數據關

8、系：數據關系： R1= | ai-1, ai D, 2in 約定約定 an端為棧頂，端為棧頂， a1端為棧底端為棧底 基本操作：基本操作： InitStack(&S) ; DestroyStack (&S); ClearStack(&S) ; StackEmpty(S); StackLength(S); GetTop(S, &e) ; /取棧取棧S的頂部元素。但不改變棧頂的位置的頂部元素。但不改變棧頂的位置 Push(&S, e)；/ 插入元素插入元素e為新的棧頂為新的棧頂 Pop(&S, &e) ；/刪除刪除S的棧頂元素，并用的棧頂元素

9、，并用e返回其值返回其值 StackTraverse(S,visit(); ADT Stack 3.1.2 3.1.2 棧的表示和實現棧的表示和實現 1. 順序棧順序棧棧的順序存儲結構棧的順序存儲結構basestackMaxSize 存放自棧底到棧頂的數據元素存放自棧底到棧頂的數據元素 top 附設棧頂指針附設棧頂指針top，來動態地指示棧頂元素棧中位置，來動態地指示棧頂元素棧中位置stacksize 當前棧的最大容量當前棧的最大容量define STACK_INIT_SIZE 100define STACKINCREMENT 10typedef struct SElemType *base;

10、 / 棧底指針棧底指針（始終指向棧底）（始終指向棧底） SElemType *top; / 棧頂指針棧頂指針 int stacksize; / 當前棧的最大容量當前棧的最大容量 SqStack; SqStack s;3.1.2 3.1.2 棧的表示和實現棧的表示和實現 s.tops.baseAs.bases. topBAEDCBA s.tops.bases.tops.bases.base 始終指向棧底始終指向棧底s.base=NULL 表示棧結構不存在表示棧結構不存在s.top=s.base 表示棧空表示棧空s.top 始終指向棧頂元素的下一個位置始終指向棧頂元素的下一個位置top-base=

11、top-base= =stacksizestacksize 棧滿的條件棧滿的條件s.top+ 插入元素插入元素 s.top- 刪除元素刪除元素3.1.2 3.1.2 棧的表示和實現棧的表示和實現 s.top順序棧基本操作的實現如下順序棧基本操作的實現如下:（1）初始化棧）初始化棧 構造一個空棧構造一個空棧 Status InitStack(SqStack &S) S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType); if(!S.base) return ERROR; S.top=S.base; S.stacksize=

12、STACK_INIT_SIZE; return OK; 3.1.2 3.1.2 棧的表示和實現棧的表示和實現 （2） 判棧空判棧空 Status StackEmpty(SqStack S) /*判棧判棧S為空棧時返回值為真，為空棧時返回值為真， 反之為假反之為假*/ return S.top=S.base; （3）判棧滿）判棧滿 Status StackFull(SqStack S) return (S.top -S.base)= S.stacksize); 3.1.2 3.1.2 棧的表示和實現棧的表示和實現 (4) 讀取棧頂元素讀取棧頂元素 Status GetTop（SqStack S,

13、 ElemType &e） /* 返回棧返回棧S的棧頂元素，的棧頂元素， 但棧頂指針保持不變但棧頂指針保持不變 */ if(S.top=S.base) /*棧為空棧為空*/ printf(“Stack is empty!”); return ERROR; e=*(S.top-1); return OK; 3.1.2 3.1.2 棧的表示和實現棧的表示和實現 (5) 入棧入棧Status Push(SqStack &S, SElemType e) if(S.top-S.base= S.stacksize) /追加存儲空間追加存儲空間 S.base=(ElemType *)real

14、loc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(ElemType); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT;*S.top+=e; return OK; /判滿判滿/棧頂指針棧頂指針賦值賦值, 后移后移3.1.2 3.1.2 棧的表示和實現棧的表示和實現 /上溢上溢(6) 出棧出棧 Status Pop(SqStack& S, SElemType &e) /* 將棧將棧S的棧頂元素彈出并返回的棧頂元素彈出并返

15、回 */ if(S.top=S.base) printf(“Stack is empty!”); return ERROR; e=*-S. top; return OK; /判空判空/修改棧頂指針修改棧頂指針3.1.2 3.1.2 棧的表示和實現棧的表示和實現 /下溢下溢棧的鏈式存貯結構棧的鏈式存貯結構,也稱為鏈棧，它是一種限制運算的鏈表，即規定鏈也稱為鏈棧，它是一種限制運算的鏈表，即規定鏈表中的插入和刪除運算只能在鏈表開頭進行。表中的插入和刪除運算只能在鏈表開頭進行。 頭 a1 a2 top 棧頂 棧底 an typedef struct SNode /define structure Li

16、nkStack SElemType data; struct SNode *next; SNode,*LinkStack 2. 鏈棧鏈棧棧的鏈式存儲結構棧的鏈式存儲結構3.1.2 3.1.2 棧的表示和實現棧的表示和實現 鏈棧基本操作的實現如下鏈棧基本操作的實現如下: :（1）棧初始化）棧初始化void inistack(LinkStack &top) top = ( LinkStack ) malloc ( sizeof ( SNode ) ); top-next=NULL; （2）進棧運算）進棧運算Status Push_L ( LinkStack ⊤ SElemT

17、ype e ) / 將元素將元素 e 插入到棧插入到棧 S 中，成為新的棧頂元素中，成為新的棧頂元素 q = ( LinkStack ) malloc ( sizeof ( SNode ) ); if ( ! q ) exit ( OVERFLOW ); / 存儲分配失敗存儲分配失敗 q-data = e; q-next = top-next; top-next = q; return OK; / Push_L / Push_L3.1.2 3.1.2 棧的表示和實現棧的表示和實現 （3）退棧運算）退棧運算Status Pop_L ( LinkStack &top, SElemType

18、&e ) / 如果棧如果棧 S 空，返回空，返回 ERROR ；如果棧；如果棧 S 不空，刪除不空，刪除 S 的棧頂元素，用的棧頂元素，用 e 返回其值，并返回返回其值，并返回 OK 。 if ( ! top-next ) return ERROR; / 如果棧如果棧 S 為空，則返回為空，則返回 ERROR e = top-next-data; / 取出棧頂元素的值取出棧頂元素的值 q = top-next; / q 指向棧頂元素指向棧頂元素 top-next = q-next; / top-next = q-next; / 刪除棧頂元素刪除棧頂元素 free (q); / free

19、 (q); / 釋放棧頂元素所占的空間釋放棧頂元素所占的空間 return OK;return OK; / Pop_L / Pop_L3.1.2 3.1.2 棧的表示和實現棧的表示和實現 （4）取棧頂元素）取棧頂元素Status GetTop_L ( LinkStack top, SElemType &e ) / 如果棧如果棧 S 空，返回空，返回 ERROR；如果棧；如果棧 S 不空，用不空，用 e 返回棧返回棧 S 的棧頂的棧頂元素，并返回元素，并返回 OK 。 if ( ! top-next ) return ERROR; / 如果棧如果棧 S 為空，則返回為空，則返回 ERRO

20、R else / 如果棧如果棧 S 不空，則返回棧頂元素不空，則返回棧頂元素 e = top-next-data;e = top-next-data; return OK; return OK; / else / else 結束結束 / GetTop_L / GetTop_L3.1.2 3.1.2 棧的表示和實現棧的表示和實現 （5）判棧空）判棧空int empty(LinkStack top) if(top-next=NULL) return(1); else return(0);3.1.2 3.1.2 棧的表示和實現棧的表示和實現 3.2.1 數制轉換數制轉換3.2 3.2 棧的應用舉例棧

21、的應用舉例 假設要將十進制數假設要將十進制數N轉換為轉換為d進制數：進制數： （如（如8進制）進制） 8 1348 余數余數 8 168 4 8 21 0 8 2 5 0 2 轉換結果：轉換結果：2504 - 后后得到的余數得到的余數先先輸出輸出void Conversion(int N)/*對于任意的一個非負十進制數N， 打印出與其等值的8進制數*/ Stack S; int x; /* S為順序棧或鏈棧 */ InitStack(&S); while(N0) x=N%8; Push(&S, x); /* 將轉換后的數字壓入棧S */ N=N/8; while(！StackE

22、mpty(S) Pop(&S,&x); printf(%d,x); 3.2 3.2 棧的應用舉例棧的應用舉例3.2.2 括號匹配問題括號匹配問題 假設表達式中包含三種括號：圓括號、方括號和花括號，它們可互相嵌套，假設表達式中包含三種括號：圓括號、方括號和花括號，它們可互相嵌套， 如如( ( ) )或或( ( ( ) ) )等均為正確的格式，等均為正確的格式， 而而 ) 或或 ( ) 或或( 均為不正確的格式。均為不正確的格式。 檢驗括號是否匹配的方法可用檢驗括號是否匹配的方法可用期待的急迫程度期待的急迫程度這個概念來描述。即這個概念來描述。即后后出出現的現的左括弧左括弧，它等待

23、與其匹配的，它等待與其匹配的右括弧右括弧出現的出現的急迫急迫心情要比心情要比先先出現的左出現的左括弧高。括弧高。 在檢驗算法中可設置一個棧，在檢驗算法中可設置一個棧， 每讀入一個括號：每讀入一個括號： 1）若是）若是左括號左括號，則直接入棧，則直接入棧， 等待相匹配的同類右括號；等待相匹配的同類右括號； 2）若讀入的是）若讀入的是右括號右括號， 且與當前棧頂的左括號同類型，則二者匹配，且與當前棧頂的左括號同類型，則二者匹配， 將將 棧頂的左括號出棧，棧頂的左括號出棧， 否則屬于不合法的情況。否則屬于不合法的情況。 3）如果輸入）如果輸入序列已讀盡序列已讀盡，而棧中，而棧中仍有仍有等待匹配的等待

24、匹配的左括號左括號，不合法，不合法 4）讀入了一個）讀入了一個右括號右括號，而棧中已，而棧中已無無等待匹配的等待匹配的左括號左括號，不合法，不合法另外：另外：先出現的右括號先需要左括號匹配先出現的右括號先需要左括號匹配 3.2 3.2 棧的應用舉例棧的應用舉例void BracketMatch(char *str) /* str中為輸入的字符串，中為輸入的字符串， 利用堆棧技術來檢查該字符串中的括號是利用堆棧技術來檢查該字符串中的括號是否匹配否匹配*/ Stack S; int i; char ch; InitStack(&S); for(i=0; stri! =0; i+) /*對字

25、符串中的字符逐一掃描對字符串中的字符逐一掃描*/ switch(stri) case (: case : case : Push(&S,stri); break; case ): case : case : if(IsEmpty(S) printf(n右括號多余右括號多余!); return; else GetTop(S,&ch); if(Match(ch,stri) /*用用Match判斷兩個括號是否匹配判斷兩個括號是否匹配*/ Pop(&S,&ch); /*已匹配的左括號出棧已匹配的左括號出棧*/ else printf(n對應的左右括號不同類對應的左右括號

26、不同類!); return; /*switch*/ /*for*/ if(IsEmpty(S) printf(n括號匹配括號匹配!); else printf(n左括號多余左括號多余!); 3.2.3 表達式求值表達式求值 ( 這是棧應用的典型例子這是棧應用的典型例子 )例如：編寫算法，用棧實現表達式例如：編寫算法，用棧實現表達式3*（7 2 ）求值。求值。一個算術表達式是由一個算術表達式是由操作數（操作數（x，y，z）和）和算符（算符（* ，/， + ，-，（，），（，），# ）組成）組成. a. 從左算到右從左算到右 b. 先乘除，后加減先乘除，后加減 c. 先括號內，后括號外先括號內，后

27、括號外3.2 3.2 棧的應用舉例棧的應用舉例運算規則運算規則（“算符優先法算符優先法”）：）：算符之間的優先關系算符之間的優先關系 3.2 3.2 棧的應用舉例棧的應用舉例1）首先置操作數棧）首先置操作數棧OPND為空棧，表達式的起始符為空棧，表達式的起始符#為運算符棧為運算符棧OPTR的的棧底元素；棧底元素；2）依次讀入表達式中的每個字符，）依次讀入表達式中的每個字符，若運算符是若運算符是# #且棧頂是且棧頂是# #，結束計算，返回，結束計算，返回OPND棧頂值。棧頂值。 if（是操作數）（是操作數） 則則PUSH（ OPND，操作數）；，操作數）； if（是運算符）（是運算符） 則與則與

28、OPTR棧頂元素進行比較，按優先級進行操棧頂元素進行比較，按優先級進行操作；作；為了實現算符優先算法，可以設定兩個工作棧，為了實現算符優先算法，可以設定兩個工作棧，OPND存放操作數或運算結果，存放操作數或運算結果， OPTR存放運算符號。存放運算符號。3）直到整個表達式求值完畢（當前讀入的字符和）直到整個表達式求值完畢（當前讀入的字符和OPTR棧的棧頂元素均棧的棧頂元素均為為# ）算法思想：算法思想：3.2 3.2 棧的應用舉例棧的應用舉例OperandType Eval( ) Initstack(&OPTR); push(&OPTR,#); Initstack (&

29、OPND); c=getchar() ; while (c!=# | GetTop(OPTR)!=#) if (!In(c,op) ) push(&OPND); c=getchar(); else /* c是一個算符是一個算符 */ r=Precede(GetTop(OPTR), c); /* 比較兩個算符的優先級比較兩個算符的優先級 */ switch( r ) case : pop(&OPTR,&op); pop(&OPND,&b); pop(&OPND,&a); value=Operate( a,op,b) ; push(&

30、OPND,value); break; /* else */ return (GetTop(OPND); 表達式求值算法：表達式求值算法：op操作符集合操作符集合Operate是相應運算是相應運算3.2 3.2 棧的應用舉例棧的應用舉例表達式求值過程的描述：表達式求值過程的描述：OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3) #*(7-2)#3#Push(optr,*)#,*3(7-2)#Push(optr,()#,*,(37-2)#Push(opnd,7)#,*,(3,7-2)#Push(optr,-)#,*,(,3,72)#Push(opnd,2)#,*,

31、(,3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)3*（7 2 ）3.2.4 棧與遞歸的實現棧與遞歸的實現 棧非常重要的一個應用是在程序設計語言中用來實現遞歸。棧非常重要的一個應用是在程序設計語言中用來實現遞歸。3.2 3.2 棧的應用舉例棧的應用舉例void print(int w)void print(int w) int i; int i; if ( w!=0) if ( w!=0) print(w-1); print(w-1); for(i=1;i=w;+i) for(i=1;i=w;+

32、i) printf(“%3d,”,w); printf(“%3d,”,w); printf(“n”); printf(“n”); return;return; 運行結果：1，2，2，3，3，3， 3.2 3.2 棧的應用舉例棧的應用舉例遞歸調用執行情況如下：遞歸調用執行情況如下：主程序主程序(1)print(w) w=3; 3print(2);（1）w=3 top(2) w2print(1)（2）w=2 （1）w=3 top(3) w1print(0);（3）w=1 （2）w=2 （1）w=3 top(4)w0（4）w=0 （3）w=1 （2）w=2 （1）w=3 topw(3) 輸出：輸出：

33、2, 2(2) 2(1) 3top(4)輸出輸出：1(3) 1(2) 2(1) 3top(2) 輸出：輸出：3, 3, 3 (1 ) 3top返回返回(3) 1(2) 2(1) 3top(4) 0結束結束(1)void print(int w)void print(int w) int i; int i; if ( w!=0) if ( w!=0) print(w-1); print(w-1); for(i=1;i=w;+i) for(i=1;i=w;+i) printf(“%3d,”,w); printf(“%3d,”,w); printf(“n”); printf(“n”); return

34、; return; 工作記錄工作記錄1.實參實參2.局部變量局部變量3.返回地址返回地址3.2 3.2 棧的應用舉例棧的應用舉例 Tower of HanoiTower of Hanoi問題問題 問題描述：有問題描述：有A,B,CA,B,C三個塔座，三個塔座，A A上套有上套有n n個直徑不同的圓個直徑不同的圓盤，按直徑從小到大疊放，形如寶塔盤，按直徑從小到大疊放，形如寶塔, ,編號編號1,2,31,2,3n n。要求將要求將n n個圓盤從個圓盤從A A移到移到C C，疊放順序不變，移動過程中遵疊放順序不變，移動過程中遵循下列原則：循下列原則： 每次只能移一個圓盤每次只能移一個圓盤 圓盤可在三

35、個塔座上任意移動圓盤可在三個塔座上任意移動 任何時刻，每個塔座上不能將大盤壓到小盤上任何時刻，每個塔座上不能將大盤壓到小盤上XYZ123 遞歸工作棧保存內容：形參遞歸工作棧保存內容：形參n,x,y,z和返回地址和返回地址 返回地址用行編號表示返回地址用行編號表示n x y z 返回地址 Tower of HanoiTower of Hanoi問題問題void hanoi (int n, char x, char y, char z) / 將塔座將塔座x上按直徑由小到大且至上而下編號為上按直徑由小到大且至上而下編號為1至至n/ 的的n個圓盤按規則搬到塔座個圓盤按規則搬到塔座z上，上，y可用作輔助

36、塔座。可用作輔助塔座。1 if (n=1)2 move(x, 1, z); / 將編號為的圓盤從將編號為的圓盤從x移到移到z3 else 4 hanoi(n-1, x, z, y); / 將將x上編號為至上編號為至n-1的的圓盤圓盤 /移到移到y, z作輔助塔作輔助塔5 move(x, n, z); / 將編號為將編號為n的圓盤從的圓盤從x移到移到z6 hanoi(n-1, y, x, z); / 將將y上編號為至上編號為至n-1的的 /圓盤移到圓盤移到z, x作輔助塔作輔助塔7 8 Tower of HanoiTower of Hanoi問題問題 main() int m; printf(I

37、nput number of disks”); scanf(%d,&m); printf(”Steps : %3d disks”,m); hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC1233 A B C 03 A B C 02 A C B 63 A B C 02 A C B 61 A B C 6ABC3

38、A B C 02 A C B 6 Tower of HanoiTower of Hanoi問題問題 main() int m; printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);

39、(8) (9) ABC3 A B C 02 A C B 61 C A B 8ABC3 A B C 02 A C B 63 A B C 03 A B C 02 A C B 6 Tower of HanoiTower of Hanoi問題問題 main() int m; printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x

40、,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 B A C 83 A B C 02 B A C 81 B C A 6ABC3 A B C 02 B A C 83 A B C 0 main() int m; printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char

41、 y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 B A C 81 A B C 8ABC3 A B C 02 B A C 83 A B C 0棧空3 A B C 02 B A C 8 Tower of HanoiTower of Hanoi問題問題遞歸問題的優點遞歸問題的優點 通過上面的例子可看出，遞歸既是強有力的數學方法，通過上面的例子可看出，遞歸既是強有力的數學方法， 也是程序設也是程

42、序設計中一個很有用的工具。其特點是對遞歸問題描述簡捷，結構清晰，程計中一個很有用的工具。其特點是對遞歸問題描述簡捷，結構清晰，程序的正確性容易證明。序的正確性容易證明。 遞歸算法求解問題的要素遞歸算法求解問題的要素 遞歸算法就是算法中有直接或間接調用算法本身的算法。遞歸算法就是算法中有直接或間接調用算法本身的算法。 遞歸算法遞歸算法的要點如下：的要點如下： (1) 問題具有類同自身的子問題的性質，問題具有類同自身的子問題的性質， 被定義項在定義中的應用具被定義項在定義中的應用具有更小的尺度。有更小的尺度。 (2) 被定義項在最小尺度上有直接解。被定義項在最小尺度上有直接解。 47 練習一下吧練

43、習一下吧1. 一個棧的輸入序列為123n，若輸出序列的第一個元素是n，輸出第i（1=i=n）個元素是（ ）。A. 不確定 B. n-i+1 C. i D. n-i2. 若一個棧的輸入序列為1,2,3,n，輸出序列的第一個元素是i，則第j個輸出元素是（ ）。 A. i-j-1 B. i-j C. j-i+1 D. 不確定的3. 若已知一個棧的入棧序列是1,2,3,n，其輸出序列為p1,p2,p3，pN,若pN是n，則pi是( )。 A. i B. n-i C. n-i+1 D. 不確定4. 有六個元素6，5，4，3，2，1 的順序進棧，問下列哪一個不是合法的出棧序列？（ ）A. 5 4 3 6

44、1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 棧：是一種只允許在一端進行插入和刪除的線性表，它是一種操作棧：是一種只允許在一端進行插入和刪除的線性表，它是一種操作受限的線性表。在表中只允許進行插入和刪除的一端稱為棧頂受限的線性表。在表中只允許進行插入和刪除的一端稱為棧頂（toptop），另一端稱為棧底），另一端稱為棧底(base)(base)。棧頂元素總是最后入棧的，因而。棧頂元素總是最后入棧的，因而是最先出棧；棧底元素總是最先入棧的，因而也是最后出棧。因此，是最先出棧；棧底元素總是最先入棧的，因而也是最后出棧。因此，棧也被稱為棧也被稱為“后

45、進先出后進先出”的線性表。的線性表。棧的順序存儲結構：利用一組地址連續的存儲單元依次存放自棧底棧的順序存儲結構：利用一組地址連續的存儲單元依次存放自棧底到棧頂的各個數據元素，稱為棧的順序存儲結構。到棧頂的各個數據元素，稱為棧的順序存儲結構。棧的鏈式存儲結構：棧的鏈式存儲結構就是用一組任意的存儲單元棧的鏈式存儲結構：棧的鏈式存儲結構就是用一組任意的存儲單元（可以是不連續的）存儲棧中的數據元素，這種結構的棧簡稱為鏈（可以是不連續的）存儲棧中的數據元素，這種結構的棧簡稱為鏈棧。在一個鏈棧中，棧底就是鏈表的最后一個結點，而棧頂是鏈表棧。在一個鏈棧中，棧底就是鏈表的最后一個結點，而棧頂是鏈表的第一個結點

46、。的第一個結點。 3.3 3.3 隊列隊列 3.3.1 3.3.1 抽象數據類型隊列的定義抽象數據類型隊列的定義 3.3.2 3.3.2 鏈隊列鏈隊列 3.3.3 3.3.3 循環隊列循環隊列1.抽象數據類型隊列的定義抽象數據類型隊列的定義 隊列隊列 (Queue)：簡稱隊，是另一種限定性的線性表，它：簡稱隊，是另一種限定性的線性表，它只允許在表的一端插入元素，而在另一端刪除元素只允許在表的一端插入元素，而在另一端刪除元素 刪除刪除 插入插入 假設假設q=（ a1 ，a2 ，a3 ， an ） 隊頭隊頭 (front) 隊尾隊尾(rear) 入隊順序：入隊順序： a1 ，a2 ，a3 ， an

47、 出隊順序：出隊順序： a1 ，a2 ，a3 ， an 先進先出表：先進先出表：FIFO結構結構 First In First Out出隊列出隊列 a1 ，a2 ，a3 ， an 入隊列入隊列3.3.1 3.3.1 隊列隊列例：購物排隊例：購物排隊 -新來的成員總是加入隊尾（不允許新來的成員總是加入隊尾（不允許“加塞加塞”） 每次離開的成員總是隊列頭上的（不允許中途離隊）每次離開的成員總是隊列頭上的（不允許中途離隊）例：解決主機與外部設備之間速度不匹配問題例：解決主機與外部設備之間速度不匹配問題例：操作系統中資源競爭例：操作系統中資源競爭3.3.1 3.3.1 隊列隊列 ADT Queue 數

48、據對象：數據對象： D=ai| aiElemSet，1in， n0 數據關系：數據關系： R1= | ai-1, ai D, 2in 約定約定 a1端為隊列頭，端為隊列頭， an端為隊列尾端為隊列尾 基本操作：基本操作： InitQueue(&Q) ; DestroyQueue (&Q) ; ClearQueue (&Q) ; QueueEmpty(Q); / 判空判空 隊列空隊列空: 返返TRUE 不空不空: 返返FALSE QueueLength(Q); GetHead（Q,&e）; / 取隊頭元素操作取隊頭元素操作, 用用e取得隊元素的值取得隊元素的值 E

49、nQueue(&Q，e); / 隊尾進隊操作隊尾進隊操作 DeQueue(&Q,&e)；/ 隊頭出隊操作隊頭出隊操作 QueueTraverse(Q,visit(); ADT Queue3.3.1 3.3.1 隊列隊列順序隊列順序隊列：用連續的空間區域存放一個隊列，設置兩個用連續的空間區域存放一個隊列，設置兩個指針分別指向隊頭和隊尾。指針分別指向隊頭和隊尾。 循環隊列循環隊列：為解決順序隊列中的假溢出現象而設置的頭：為解決順序隊列中的假溢出現象而設置的頭尾連接的隊列。尾連接的隊列。鏈式隊列鏈式隊列 ：每個元素定義成一個結點，含數據域與指針每個元素定義成一個結點，含數據域

50、與指針域（指向下一結點），并設頭尾指針。域（指向下一結點），并設頭尾指針。3.3.1 3.3.1 隊列隊列1. 鏈隊列的邏輯表示鏈隊列的邏輯表示 Q.frontQ.rear3.3.2 3.3.2 鏈隊列鏈隊列frontrearx元素元素x入隊入隊frontrearxy元素元素y入隊入隊frontrearxy元素元素x出隊出隊frontrear空隊列空隊列front=rear3.3.2 3.3.2 鏈隊列鏈隊列2. 鏈隊列的形式定義鏈隊列的形式定義typedef struct QNode QElemType data; /*數據域數據域*/ struct QNode * next; /*指針域指

51、針域*/ QNode, *QueuePtr; typedef struct QueuePtr front; QueuePtr rear; LinkQueue; 3.3.2 3.3.2 鏈隊列鏈隊列（1） 初始化操作初始化操作 Status InitQueue(LinkQueue &Q) /* 將將Q初始化為一個空的鏈隊列初始化為一個空的鏈隊列 */ Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if(!Q.front) exit(OVERFLOW); Q.front-next=NULL; return OK; 3. 鏈隊列的操作鏈隊列的操

52、作3.3.2 3.3.2 鏈隊列鏈隊列（2） 銷毀隊列操作銷毀隊列操作 Status DestroyQueue(LinkQueue &Q) while (Q.front) Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; return OK;3.3.2 3.3.2 鏈隊列鏈隊列（）（） 入隊操作入隊操作Status EnQueue(LinkQueue Q, QElemType e) /* 將數據元素將數據元素e插入到隊列插入到隊列Q中中 */ p=(QueuePtr) malloc(sizeof(QNode); if(! p) ex

53、it(OVERFLOW); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK; 3.3.2 3.3.2 鏈隊列鏈隊列（4） 出隊操作出隊操作 Status DeQueue(LinkQueue &Q, QElemType &e) /* 將隊列將隊列Q的隊頭元素出隊，的隊頭元素出隊， 并存放到并存放到e所指的存儲空間中所指的存儲空間中 */ if(Q.front=Q.rear)return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; /* 隊頭元素隊頭元

54、素p出隊出隊 */ if(Q.rear=p) /* 如果隊中只有一個元素如果隊中只有一個元素p， 則則p出隊后成為空隊出隊后成為空隊 */ Q.rear=Q.front; /給隊尾指針賦值給隊尾指針賦值 free(p); /* 釋放存儲空間釋放存儲空間 */ return OK; 3.3.2 3.3.2 鏈隊列鏈隊列3.3.3 3.3.3 循環隊列循環隊列隊列的順序表示和實現隊列的順序表示和實現Queue6543210rearfront(1) 空隊列543210rearfrontcbad(2) a、b、c、d依次入隊543210rearfrontd(3) a、b、c出隊543210rearfr

55、ontdef(4) e、f入 隊 用一組連續的存儲單元依次存放隊列的元素，并設兩個指針用一組連續的存儲單元依次存放隊列的元素，并設兩個指針front、rear分別指示隊頭和隊尾元素的位置。分別指示隊頭和隊尾元素的位置。 front：指向實際的隊頭；：指向實際的隊頭；rear：指向實際隊尾的下一位置。：指向實際隊尾的下一位置。 初態：初態： frontrear0；隊空：；隊空： frontrear;隊滿：隊滿： rearM; 入隊：入隊： qrear=x; rear rear+1; 出隊：出隊：x=qfront;front=front+1;隊列的類型定義：隊列的類型定義：#define MAXQ

56、SIZE 100 typedef struct QElemType *base; int front; /*頭指針指示器頭指針指示器*/ int rear ; /*尾指針指示器尾指針指示器*/ SqQueue; 3.3.3 3.3.3 循環隊列循環隊列隊列的順序表示和實現隊列的順序表示和實現 隨著入隊、出隊操作的進行，整個隊列會整體向后移動，這樣就出現了最后圖中的現象：隊尾指針雖然已經移到了最后，而隊列卻未真滿的“假溢出假溢出”現象，使得隊列的空間沒有得到有效的利用。3.3.3 3.3.3 循環隊列循環隊列隊列的順序表示和實現隊列的順序表示和實現存在的問題：存在的問題：設設 SqQueue Q

57、;SqQueue Q;當當Q.rear= MAXQSIZEQ.rear= MAXQSIZE， 隊列不滿，但入隊操作出錯隊列不滿，但入隊操作出錯-假溢出假溢出 （1）將隊中元素向隊頭移動）將隊中元素向隊頭移動 當移動數據較多時將會影響隊列的操作速度。當移動數據較多時將會影響隊列的操作速度。（2）采用循環隊列：）采用循環隊列：Q0接在接在QMAXQSIZE-1之后之后 一個更有效的方法是將隊列的數據區一個更有效的方法是將隊列的數據區Q0 . MAXQSIZE-1看成是首尾相看成是首尾相連的環，即將表示隊首的元素連的環，即將表示隊首的元素Q0與表示隊尾的元素與表示隊尾的元素QMAXQSIZE1連 接

58、 起 來 ， 形 成 一 個 環 形 表 ， 這 就 成 了 循 環 隊 列 。連 接 起 來 ， 形 成 一 個 環 形 表 ， 這 就 成 了 循 環 隊 列 。當當Q.rear=MAXQSIZE-1時再入隊，令時再入隊，令Q.rear=0, 則可以利用已被刪則可以利用已被刪除的元素空間。除的元素空間。01234567循環隊列循環隊列frontMaxsize-1問題：我們如何來解決問題：我們如何來解決“假溢出假溢出”現象？現象？3.3.3 3.3.3 循環隊列循環隊列隊列的順序表示和實現隊列的順序表示和實現問題問題根據等根據等式式front= =rearfront= =rear可以可以判別

59、隊滿和隊空？判別隊滿和隊空？ 隊空條件：隊空條件：Q.front=Q.rear 條件相同條件相同 隊滿條件：隊滿條件：Q.front=Q.rear012354rearfront(a) 空隊列012354e6e7e8e3e4e5012354(b) 隊列滿(b) 一般情況frontreare3e4e5frontrear腫么辦？腫么辦？3.3.3 3.3.3 循環隊列循環隊列隊列的順序表示和實現隊列的順序表示和實現兩種常用的方法：兩種常用的方法：（1 1）少用（損失）一個空間）少用（損失）一個空間, ,以尾指針加以尾指針加1 1等于頭指針作等于頭指針作為隊滿的標志。因此：當為隊滿的標志。因此：當fr

60、ont=rearfront=rear，表示循環隊列，表示循環隊列為空；當為空；當front=front=（rear+1rear+1）% MAXLEN% MAXLEN，表示循環隊列，表示循環隊列為滿。為滿。（2 2）在定義結構體時，附設一個存儲循環隊列中元素個）在定義結構體時，附設一個存儲循環隊列中元素個數的變量數的變量n n，當，當n=0n=0時表示隊空；當時表示隊空；當n=MAXLENn=MAXLEN時為隊時為隊滿。滿。3.3.3 3.3.3 循環隊列循環隊列隊列的順序表示和實現隊列的順序表示和實現循環隊列條件：循環隊列條件：隊頭、隊尾指針加1，可用取模(余數)運算實現。隊頭指針進1: front = (front+1) %maxsize;隊尾指針進1: rea