1、機電工程學院機電工程學院程藝苑程藝苑數據結構數據結構教學內容教學內容 緒論緒論第第1 1章章 線性表線性表第第2 2章章 棧和隊列棧和隊列第第3 3章章 串串第第4 4章章 數組和廣義表數組和廣義表第第5 5章章 樹和二叉樹樹和二叉樹第第6 6章章 圖圖第第7 7章章 查找查找第第8 8章章 排序排序第第9 9章章3 3.1 .1 棧棧3 3.2 .2 棧的應用舉例棧的應用舉例3 3.3 .3 隊列隊列第第3章章 棧和隊列棧和隊列棧和隊列是兩種應用非常廣泛的數據結構棧和隊列是兩種應用非常廣泛的數據結構，它，它們都來自線性表數據結構，們都來自線性表數據結構，都是都是“操作受限操作受限”的線的線性

2、表性表。與線性表相比，它們的插入和刪除操作受更與線性表相比，它們的插入和刪除操作受更多的約束和限定，故又稱為多的約束和限定，故又稱為限定性的線性表結構限定性的線性表結構。u線性表允許在表內線性表允許在表內任一位置任一位置進行插入和刪除；進行插入和刪除；u棧只允許在棧只允許在表尾一端表尾一端進行插入和刪除；進行插入和刪除；u隊列只允許在隊列只允許在表尾一端表尾一端進行進行插入插入，在，在表頭一端表頭一端進行進行刪除刪除。3.1 棧棧3.1.1 棧的基本概念棧的基本概念1 棧的概念棧的概念u棧棧(Stack)：是限制在表的一端進行插入和刪除是限制在表的一端進行插入和刪除操作的線性表。操作的線性表。

3、u也稱為后進先出也稱為后進先出LIFO (Last In First Out)或先進或先進后出后出FILO (First In Last Out)線性線性表。表。 l 設棧S=(a1，a2，an)，則a1稱為棧底元素，an為棧頂元素。 棧中元素按a1，a2，an的次序進棧，出棧的第一個元素應為棧頂元素。即棧的修改是按后進先出的原則進行的。a1a2aian basetop進棧（進棧（push）出棧出棧(pop)u棧頂棧頂(Top)：允許進行插入、刪除操作的一端，又允許進行插入、刪除操作的一端，又稱為稱為表尾表尾。用棧頂指針。用棧頂指針(top)來指示棧頂元素來指示棧頂元素。u棧底棧底(Base)

4、：是固定端，又稱為是固定端，又稱為表頭表頭。u空棧空棧：當表中沒有元素時稱為空棧當表中沒有元素時稱為空棧 例例1：家里吃飯的碗，通常在洗干凈后一個一個家里吃飯的碗，通常在洗干凈后一個一個地落在一起存放，在使用時，若一個一個地拿，地落在一起存放，在使用時，若一個一個地拿，一定最先拿走最上面的那只碗，而最后拿出最下一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。面的那只碗。 例例2：在建筑工地上，使用的磚塊從底往上一層在建筑工地上，使用的磚塊從底往上一層一層地碼放，在使用時，將從最上面一層一層地一層地碼放，在使用時，將從最上面一層一層地拿取。拿取。ADT Stack數據對象：數據對象：D =

5、 ai|aiElemSet, i=1,2,n，n0 數據關系：數據關系：R =|ai-1，aiD, i=2,3,n 基本操作：基本操作：InitStack(&S) 操作結果：構造一個空棧操作結果：構造一個空棧 S S。DestroyStack(&S)初始條件：棧初始條件：棧 S S 已存在。已存在。操作結果：棧操作結果：棧 S S 被銷毀。被銷毀。2 棧的抽象數據類型定義棧的抽象數據類型定義 ClearStack(&S)初始條件：棧初始條件：棧 S S 已存在。已存在。操作結果：將操作結果：將 S S 清為空棧。清為空棧。StackEmpty(S)初始條件：棧初始條件：

6、棧 S S 已存在。已存在。操作結果：若棧操作結果：若棧 S S 為空棧，則返回為空棧，則返回TRUETRUE，否則返回，否則返回 FALSEFALSE。StackLength(S)初始條件：棧初始條件：棧 S S 已存在。已存在。操作結果：返回棧操作結果：返回棧 S S 中元素個數，即棧的長度。中元素個數，即棧的長度。 GetTop(S, &e)初始條件：棧初始條件：棧 S S 已存在且非空。已存在且非空。操作結果：用操作結果：用 e e 返回返回S S的棧頂元素。的棧頂元素。 Push(&S, e)初始條件：棧初始條件：棧 S S 已存在。已存在。操作結果：插入元素操作結果

7、：插入元素 e e 為新的棧頂元素。為新的棧頂元素。Pop(&S, &e)初始條件：棧初始條件：棧 S S 已存在且非空。已存在且非空。操作結果：刪除操作結果：刪除 S S 的棧頂元素，并用的棧頂元素，并用 e e 返回其值。返回其值。 StackTraverse(S, visit( )初始條件：棧初始條件：棧 S S 已存在且非空，已存在且非空，visit( )visit( )為元素的為元素的訪問函數。訪問函數。操作結果：從棧底到棧頂依次對操作結果：從棧底到棧頂依次對S S的每個元素調用函的每個元素調用函數數visit( )visit( )，一旦，一旦visit( )visi

8、t( )失敗，則操作失敗。失敗，則操作失敗。 ADT Stack 和線性表類似，棧也有兩種存儲方法：和線性表類似，棧也有兩種存儲方法：棧的順序存儲結構棧的順序存儲結構順序棧；順序棧；棧的鏈式存儲結構棧的鏈式存儲結構鏈棧。鏈棧。3.1.2 棧的表示和實現棧的表示和實現u順序棧，順序棧，即棧的順序存儲結構，是利用即棧的順序存儲結構，是利用一組地址一組地址連續的存儲單元連續的存儲單元依次存放自棧底到棧頂的數據元素。依次存放自棧底到棧頂的數據元素。u設置指針設置指針toptop指向棧頂元素在順序棧中的位置，通指向棧頂元素在順序棧中的位置，通常習慣做法是以常習慣做法是以top=0top=0表示空棧表示空

9、棧。u棧在使用的過程中所需最大空間的大小很難估計，棧在使用的過程中所需最大空間的大小很難估計，一般初始化設空棧時不限定棧的最大容量。一般初始化設空棧時不限定棧的最大容量。u一般先分配一個基本容量，然后應用過程中，棧一般先分配一個基本容量，然后應用過程中，棧的空間不夠使用時再逐段擴大。的空間不夠使用時再逐段擴大。3.1.2.1 棧的順序存儲表示棧的順序存儲表示順序棧的結構定義：順序棧的結構定義：#define STACK_INIT_SIZE 100; #define STACK_INIT_SIZE 100; / / 存儲空間初始分配量存儲空間初始分配量 #define STACKINCREMEN

10、T 10; #define STACKINCREMENT 10; / / 存儲空間分配增量存儲空間分配增量 typedeftypedef structstruct SElemTypeSElemType * *base; base; / / 存儲空間基址存儲空間基址 SElemTypeSElemType * *top; top; / / 棧頂指針棧頂指針intint stacksizestacksize; ; / / 當前已分配的存儲空間當前已分配的存儲空間 SqStackSqStack; ; StacksizeStacksize：棧的當前可使用的最大容量；：棧的當前可使用的最大容量；BaseB

11、ase：棧底指針，順序棧中始終指向棧底位置，：棧底指針，順序棧中始終指向棧底位置，basebase的的值為值為NULLNULL，則表明棧結構不存在；，則表明棧結構不存在；TopTop：棧頂指針，初值指向棧底，：棧頂指針，初值指向棧底，當當top=basetop=base時，可以以時，可以以作為棧空的標記作為棧空的標記。非空棧中非空棧中toptop指針始終在棧頂元素的下一指針始終在棧頂元素的下一個位置個位置。top=0123450棧空棧空棧頂指針棧頂指針top,指向實際棧頂指向實際棧頂后的空位置，初值為后的空位置，初值為0top123450進棧進棧Atop出棧出棧棧滿棧滿BCDEF設數組大小為設

12、數組大小為Mtop=0,棧空，此時出棧，則棧空，此時出棧，則下溢下溢（underflow)top=M,棧滿，此時入棧，則棧滿，此時入棧，則上溢上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop棧空棧空進棧：進棧：top加加1出棧：出棧：top減減1順序棧的基本操作：順序棧的基本操作：void InitStack (SqStack &S); /構造一個空棧構造一個空棧S。void DestroyStack (SqStack &S); /銷毀棧銷毀棧S，S 不再存在。不再存在。void ClearStack (SqSt

13、ack &S); /將將 S 置為空棧。置為空棧。bool StackEmpty (SqStack S); /若棧若棧 S 為空棧。為空棧。int StackLength (SqStack S); /返回返回S的元素個數，即棧的長度。的元素個數，即棧的長度。bool GetTop (SqStack S, SElemType &e); /若棧不空，則用若棧不空，則用 e 返回返回S的的棧頂元素，并返回棧頂元素，并返回TRUE；否則返回；否則返回 FALSE。bool Push (SqStack &S, SElemType e); /若棧的存儲空間不滿，則插入若棧的存儲空間

14、不滿，則插入元素元素 e ，并返回，并返回 TRUE；否則返回；否則返回FALSE。bool Pop (SqStack &S, SElemType &e); /若棧不空，則刪除若棧不空，則刪除S的棧頂元的棧頂元素，用素，用e返回其值，并返回返回其值，并返回TRUE；否則返回；否則返回FALSE。void StackTraverse(SqStack S, Status (*visit()； /依次對依次對S的每個元的每個元素調用函數素調用函數 visit( )，一旦，一旦 visit( )失敗，操作失敗。失敗，操作失敗。1 1 棧的初始化棧的初始化Status InitStack

15、 (SqStack &S) / 構造一個空棧構造一個空棧 SS.base=(SElemType *)malloc (STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) exit(OVERFLOW); / 存儲分配失敗存儲分配失敗S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK; /InitStack 2 2 取棧頂元素取棧頂元素 Status GetTop (SqStack S, SElemType &e) / 若棧不空，則用若棧不空，則用 e 返回返回S的棧頂元素，并返回的棧頂

16、元素，并返回OKif (S.top = S.base ) return ERROR; / 空棧空棧e = *(S.top-1); / 返回非空棧中棧頂元素返回非空棧中棧頂元素return OK; /GetTop注意：注意： top top棧頂指針始終在棧頂元素的下一個位置上。棧頂指針始終在棧頂元素的下一個位置上。3壓棧(元素進棧)lStatus Push (SqStack &S, SElemType e) / 插入元素 e 為新的棧頂元素lif(S.top-S.base=S.stacksize) /棧滿，追加存儲空間lS.base=(SElemType *)realloc(S.base

17、,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);l if(!S.base) exit(OVERFLOW);/ 存儲分配失敗lS.top=S.base+S.stacksize;lS.stacksize +=STACKINCREMENT;l*(S.top+) = e; / 插入新的元素lreturn OK;l /Push4 彈棧(元素出棧)lStatus Pop (Stack &S, ElemType &e) / 棧不空，刪除S的棧頂元素，用e返回其值，并返回 OK；否則返回 ERRORlif (S.top = S.base) ret

18、urn ERROR;/空棧le = *(-S.top); /返回非空棧中棧頂元素lreturn OK;l /Pop棧的棧的鏈式存儲結構鏈式存儲結構稱為鏈棧，是運算受限的單鏈表。其插入稱為鏈棧，是運算受限的單鏈表。其插入和刪除操作只能在表頭位置上進行。因此，鏈棧沒有必要像和刪除操作只能在表頭位置上進行。因此，鏈棧沒有必要像單鏈表那樣附加頭結點，棧頂指針單鏈表那樣附加頭結點，棧頂指針top就是鏈表的頭指針。就是鏈表的頭指針。3.1.2.2 3.1.2.2 棧的鏈式存儲表示棧的鏈式存儲表示空棧空棧top 非空棧非空棧top a4 a3 a1 a2鏈棧的鏈棧的結點類型說明如下：結點類型說明如下：typ

19、edef struct Stack_Node ElemType data ; struct Stack_Node *next ; Stack_Node ;入棧算法入棧算法 .棧底棧底toptopxp出棧算法出棧算法top .棧底棧底topq空間性能：空間性能：順序棧：順序棧：有元素個數的限制和空間浪費的問題。有元素個數的限制和空間浪費的問題。鏈棧：鏈棧：沒有棧滿的問題，只有當內存沒有可用沒有棧滿的問題，只有當內存沒有可用空間時才會出現棧滿，但是每個元素都需要一個空間時才會出現棧滿，但是每個元素都需要一個指針域，從而產生了結構性開銷。指針域，從而產生了結構性開銷。總之，當棧的使用過程中總之，當棧

20、的使用過程中元素個數變化較大元素個數變化較大時，時，用鏈棧是適宜的，反之，應該采用順序棧。用鏈棧是適宜的，反之，應該采用順序棧。順序棧和鏈棧的比較順序棧和鏈棧的比較：3.2 棧的應用棧的應用 由于棧具有的由于棧具有的“后進先出后進先出”的固有特性，因此，棧成的固有特性，因此，棧成為程序設計中常用的工具和數據結構。以下是幾個棧應用的為程序設計中常用的工具和數據結構。以下是幾個棧應用的例子。例子。1 數制轉換數制轉換2 括號匹配問題括號匹配問題3 表達式求值表達式求值4 棧與遞歸調用的實現棧與遞歸調用的實現3.2.1 數制轉換數制轉換 十進制整數十進制整數N向其它進制數向其它進制數d(二二、八八、

21、十六十六) )的轉換是計算機實現計算的基本問題。的轉換是計算機實現計算的基本問題。該轉換法則對應于一個簡單算法原理該轉換法則對應于一個簡單算法原理: :N = (N div d)d + N mod d其中：其中：div為整除運算為整除運算, ,mod為求余運算。為求余運算。例如：例如：（1348)1348)1010 = (2504) = (2504)8 8 ，其運算過程如下：，其運算過程如下： 采用順序棧的方式實現任意一個非負十進制整數轉換為與采用順序棧的方式實現任意一個非負十進制整數轉換為與其等值的八進制數。其等值的八進制數。 void conversion () /算法算法3.1InitS

22、tack(S); / 構造空棧構造空棧scanf(“%d”,N);/ 輸入一個十進制數輸入一個十進制數while(N) Push(S,N%8);/ “余數余數”入棧入棧 N = N/8;/ 非零非零“商商”繼續運算繼續運算 while (!StackEmpty(s)/ 和和“求余求余”所得相逆的順序輸出八進制的各位數所得相逆的順序輸出八進制的各位數Pop(S,e);printf(“%d”,e); / while / conversion3.2.2 括號匹配問題括號匹配問題 在文字處理軟件或編譯程序設計時，常常需要檢查一在文字處理軟件或編譯程序設計時，常常需要檢查一個字符串或一個表達式中的括號是

23、否相匹配個字符串或一個表達式中的括號是否相匹配?匹配思想：匹配思想：從左至右掃描一個字符串從左至右掃描一個字符串(或表達式或表達式)，則，則每個右每個右括號將與最近遇到的那個左括號相匹配括號將與最近遇到的那個左括號相匹配。則可以在從左至右。則可以在從左至右掃描過程中把所遇到的左括號存放到堆棧中。每當遇到一個掃描過程中把所遇到的左括號存放到堆棧中。每當遇到一個右括號時，就將它與棧頂的左括號右括號時，就將它與棧頂的左括號(如果存在如果存在)相匹配，同時相匹配，同時從棧頂刪除該左括號。從棧頂刪除該左括號。算法思想：算法思想：設置一個棧，當讀到左括號時，左括號進棧。當設置一個棧，當讀到左括號時，左括號

24、進棧。當讀到右括號時，則從棧中彈出一個元素，與讀到的左括號進讀到右括號時，則從棧中彈出一個元素，與讀到的左括號進行匹配，若匹配成功，繼續讀入；否則匹配失敗，返回行匹配，若匹配成功，繼續讀入；否則匹配失敗，返回FLASE。283.2.3 表達式求值表達式求值l表達式的組成表達式的組成操作數操作數(operand)(operand)：常數、變量。常數、變量。運算符運算符(operator)(operator)：算術運算符、關系運算符和邏輯運算符。算術運算符、關系運算符和邏輯運算符。界限符界限符(delimiter) (delimiter) ：左右括弧和表達式結束符。左右括弧和表達式結束符。l算術運

25、算的規則算術運算的規則先乘除后加減先乘除后加減先左后右先左后右先括弧內后括弧外先括弧內后括弧外例如：例如：4+24+2* *3-10/5=4+6-10/53-10/5=4+6-10/5 =10-10/5 =10-10/5 =10-2 =10-2 =8 =8算法的思想：算法的思想：設置兩個工作棧設置兩個工作棧l運算符棧運算符棧OPTROPTR，運算符棧的棧底為表達式的起始符運算符棧的棧底為表達式的起始符# #。l操作數棧操作數棧OPNDOPND，操作數棧為空棧。操作數棧為空棧。依次讀入表達式中的每個字符依次讀入表達式中的每個字符l若是若是操作數則進操作數則進OPNDOPND棧棧；l若是若是運算符

26、，則和運算符，則和OPTROPTR中的棧頂元素做比較再操作中的棧頂元素做比較再操作。若若運算符優先級高于運算符優先級高于OPTROPTR中的棧頂元素中的棧頂元素，則運算符入棧；則運算符入棧；若若運算符優先級低于運算符優先級低于OPTROPTR中的棧頂元素中的棧頂元素，則從則從OPNDOPND棧頂彈出兩棧頂彈出兩個操作數，與個操作數，與OPTROPTR中的棧頂元素做運算，并將運算結果入中的棧頂元素做運算，并將運算結果入OPNDOPND；若若運算符優先級等于運算符優先級等于OPTROPTR中的棧頂元素中的棧頂元素，則將則將OPTROPTR中的棧頂元中的棧頂元素出棧。素出棧。直至直至表達式求置完畢表

27、達式求置完畢。計算計算 2+4-3*6操作數操作數運算符運算符-12操作數操作數運算符運算符24#+操作數操作數運算符運算符6#-操作數操作數運算符運算符6#36*-操作數操作數運算符運算符6#18-3.2.4 棧與遞歸調用的實現棧與遞歸調用的實現 棧的另一個重要應用是在程序設計語言中實現遞歸調用。棧的另一個重要應用是在程序設計語言中實現遞歸調用。 遞歸調用：遞歸調用：一個函數一個函數( (或過程或過程) )直接或間接地調用自己本身，直接或間接地調用自己本身，簡稱遞歸簡稱遞歸(Recursive)。 遞歸遞歸是程序設計中的一個強有力的工具。因為遞歸函數結是程序設計中的一個強有力的工具。因為遞歸

28、函數結構清晰，程序易讀，正確性很容易得到證明。構清晰，程序易讀，正確性很容易得到證明。 例如：求例如：求n!Fact(n)=1 當當n=0時時 終止條件終止條件n*fact(n-1) 當當n0時時 遞推規則遞推規則l當一個函數在運行期間調用另一個函數時，在運行該被當一個函數在運行期間調用另一個函數時，在運行該被調用函數之前，需先完成三件事：調用函數之前，需先完成三件事：將所有的將所有的實在參數、返回地址實在參數、返回地址等信息傳遞給等信息傳遞給被調用函數保存被調用函數保存；為被調用函數的為被調用函數的局部變量分配存儲區局部變量分配存儲區；將控制轉移到被調用函數的入口將控制轉移到被調用函數的入口

29、。l而從被調用函數返回調用函數之前，應該完成：而從被調用函數返回調用函數之前，應該完成：保存保存被調函數的被調函數的計算結果計算結果；釋放釋放被調函數的被調函數的數據區數據區；依照被調函數保存的返回地址將依照被調函數保存的返回地址將控制轉移到調用函數控制轉移到調用函數。l由于函數的運行規則是：后調用先返回，因此各函數占由于函數的運行規則是：后調用先返回，因此各函數占有的存儲管理應實行有的存儲管理應實行 棧式管理棧式管理 。r主程序主程序srrrs子過程子過程1rst子過程子過程2rst子過程子過程3 有有A,B,C三個塔座，三個塔座，A上套有上套有n個直徑不同的圓盤，按直徑從小到大疊個直徑不同

30、的圓盤，按直徑從小到大疊放，形如寶塔放，形如寶塔,編號編號1,2,3n。要求將要求將n個圓盤從個圓盤從A移到移到C，疊放順序疊放順序不變，移動過程中遵循下列原則：不變，移動過程中遵循下列原則：v每次只能移一個圓盤；每次只能移一個圓盤；v圓盤可在三個塔座上任意移動；圓盤可在三個塔座上任意移動；v任何時刻，每個塔座上不能將大盤壓到小盤上。任何時刻，每個塔座上不能將大盤壓到小盤上。Tower of HanoiTower of Hanoi問題問題l問題描述問題描述ABCl解決方法：解決方法：n=1n=1時，直接把圓盤從時，直接把圓盤從A A移到移到C C。n1n1時時l把上面把上面n-1n-1個圓盤從

31、個圓盤從A A移到移到B Bl然后將然后將n n號盤從號盤從A A移到移到C Cl將將n-1n-1個盤從個盤從B B移到移到C C。即把求解即把求解n n個圓盤的個圓盤的HanoiHanoi問題轉化為求解問題轉化為求解n-1n-1個圓盤的個圓盤的HanoiHanoi問題，依次類推，直至轉化成只有一個圓盤的問題，依次類推，直至轉化成只有一個圓盤的HanoiHanoi問題。問題。ABC1 1 隊列的基本概念隊列的基本概念 隊列隊列(Queue)：也是運算受限的線性表。是一種也是運算受限的線性表。是一種先進先進先出先出(First In First Out ，簡稱，簡稱FIFO)的線性表。只允許在的

32、線性表。只允許在表的一端進行插入，而在另一端進行刪除表的一端進行插入，而在另一端進行刪除。u 隊首隊首(front) ：允許進行刪除的一端稱為隊首。允許進行刪除的一端稱為隊首。u 隊尾隊尾(rear) ：允許進行插入的一端稱為隊尾。允許進行插入的一端稱為隊尾。3.3 隊隊 列列3.3.1 隊列及其基本概念隊列及其基本概念例例1 1：到醫院看病，首先需要到掛號處掛號，然到醫院看病，首先需要到掛號處掛號，然后，按號碼順序救診。后，按號碼順序救診。例例2 2：乘坐公共汽車，應該在車站排隊，車來后，乘坐公共汽車，應該在車站排隊，車來后，按順序上車。按順序上車。例例3 3：在在WindowsWindow

33、s這類多任務的操作系統環境中，這類多任務的操作系統環境中，每個應用程序響應一系列的每個應用程序響應一系列的“消息消息”，像用戶點，像用戶點擊鼠標；拖動窗口這些操作都會導致向應用程序擊鼠標；拖動窗口這些操作都會導致向應用程序發送消息。為此，系統將為每個應用程序創建一發送消息。為此，系統將為每個應用程序創建一個隊列，用來存放發送給該應用程序的所有消息，個隊列，用來存放發送給該應用程序的所有消息，應用程序的處理過程就是不斷地從隊列中讀取消應用程序的處理過程就是不斷地從隊列中讀取消息，并依次給予響應。息，并依次給予響應。 隊列中沒有元素時稱為空隊列。在空隊列中依次加入元素a1, a2, , an之后，

34、a1是隊首元素，an是隊尾元素。顯然退出隊列的次序也只能是a1, a2, , an ，即隊列的修改是依先進先出的原則進行的。a1 , a2 , , an出隊出隊入隊入隊隊尾隊尾rear隊首隊首front2 隊列的抽象數據類型定義隊列的抽象數據類型定義ADT Queue 數據對象：數據對象：D = ai|aiElemSet, i=1, 2, , n, n = 0 數據關系：數據關系：R = | ai-1, aiD, i=2,3,n 約定約定a1端為隊首，端為隊首，an端為隊尾。端為隊尾。基本操作：基本操作： InitQueueInitQueue(&Q)(&Q) 操作結果：構造一個

35、空隊列操作結果：構造一個空隊列 Q Q。 DestroyQueueDestroyQueue(&Q)(&Q) 初始條件：隊列初始條件：隊列 Q Q 已存在。已存在。 操作結果：隊列操作結果：隊列 Q Q 被銷毀，不再存在。被銷毀，不再存在。 ClearQueueClearQueue(&Q)(&Q) 初始條件：隊列初始條件：隊列 Q Q 已存在。已存在。 操作結果：將操作結果：將 Q Q 清為空隊列。清為空隊列。 QueueEmptyQueueEmpty(Q)(Q)初始條件：隊列初始條件：隊列 Q Q 已存在。已存在。操作結果：若操作結果：若 Q Q 為空隊列，則返

36、回為空隊列，則返回TRUETRUE，否則返回，否則返回 FALSEFALSE。QueueLengthQueueLength(Q)(Q)初始條件：隊列初始條件：隊列 Q Q 已存在。已存在。操作結果：返回操作結果：返回 Q Q 的元素個數，即隊列的長度。的元素個數，即隊列的長度。 GetHeadGetHead( (Q,&eQ,&e) )初始條件：初始條件：Q Q 為非空隊列。為非空隊列。操作結果：用操作結果：用 e e 返回返回Q Q的隊頭元素。的隊頭元素。 EnQueueEnQueue(&(&Q,eQ,e) )初始條件：隊列初始條件：隊列 Q Q 已存在。已存在

37、。操作結果：插入元素操作結果：插入元素 e e 為為 Q Q 的新的隊尾元素。的新的隊尾元素。DeQueueDeQueue(&(&Q,&eQ,&e) )初始條件：初始條件：Q Q 為非空隊列。為非空隊列。操作結果：刪除操作結果：刪除 Q Q 的隊頭元素，并用的隊頭元素，并用 e e 返回其值。返回其值。QueueTraverseQueueTraverse( (Q,visitQ,visit( )( )初始條件：隊列初始條件：隊列 Q Q 已存在且非空，已存在且非空，visit( )visit( )為元素的訪為元素的訪 問函數。問函數。操作結果：依次對操作結果：依次

38、對 Q Q 的每個元素調用函數的每個元素調用函數 visit( )visit( )， 一旦一旦 visit( ) visit( ) 失敗則操作失敗。失敗則操作失敗。 ADT Queue ADT Queue1 隊列的鏈式存儲表示隊列的鏈式存儲表示 隊列的鏈式存儲結構簡稱為隊列的鏈式存儲結構簡稱為鏈隊列鏈隊列，它是限制僅在表，它是限制僅在表頭進行刪除操作和表尾進行插入操作的單鏈表。頭進行刪除操作和表尾進行插入操作的單鏈表。 需要兩類不同的結點需要兩類不同的結點：數據元素結點數據元素結點，隊列的隊首指隊列的隊首指針和隊尾指針的結點針和隊尾指針的結點。3.3.2 隊列的鏈式表示和實現隊列的鏈式表示和實

39、現數據元素結點數據元素結點data指針結點指針結點front rear數據結點類型定義：數據結點類型定義：typedef struct QNodeQelemType data ;struct QNode *next ;QNode, *QueuePtr;指針結點類型定義：指針結點類型定義：typedef struct link_queue QNode *front ； QNode *rear ;Link_Queue ;隊頭隊頭隊尾隊尾Q.frontQ.reardata next2鏈隊運算及指針變化 鏈隊的操作實際上是單鏈表的操作，只不過是刪除在表頭進行，插入在表尾進行。插入、刪除時分別修改不同的

40、指針。鏈隊運算及指針變化如圖所示。(a) 空隊列空隊列front rear(b) x入隊入隊 x front rear(c) y再入隊再入隊 y front rear x(d) x出隊出隊 y xfront rear3 鏈隊列的基本操作鏈隊列的基本操作 鏈隊列的初始化鏈隊列的初始化Status InitQueue (LinkQueue &Q) / 構造一個空隊列構造一個空隊列 Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit(OVERFOLW);/ 存儲分配失敗存儲分配失敗 Q.front-next=

41、NULL; return OK; 鏈隊列的入隊操作鏈隊列的入隊操作 在已知隊列的隊尾插入一個元素在已知隊列的隊尾插入一個元素e e ，即修改隊，即修改隊尾指針尾指針( (Q.rearQ.rear) )。Status EnQueue(LinkQueue &Q, QElemType e)/ 在當前隊列的尾元素之后，插入元素在當前隊列的尾元素之后，插入元素 e 為新的隊列尾元素為新的隊列尾元素p=(QueuePtr)malloc(sizeof(QNode);if (!p) exit(OVERFLOW);/ 存儲分配失敗存儲分配失敗p-data=e; p-next = NULL;Q.rear-

42、next=p;/ 修改尾結點的指針修改尾結點的指針Q.rear=p; / 移動隊尾指針移動隊尾指針 鏈隊列的出隊操作鏈隊列的出隊操作Status DeQueue(LinkQueue &Q, QElemType &e)/ / 若隊列不空，則刪除隊列若隊列不空，則刪除隊列 Q Q 的隊頭元素，用的隊頭元素，用 e e 返回其值，并返返回其值，并返回回OKOK；否則返回；否則返回ERRORERRORif(Q.front=Q.rear) return ERROR;/ / 鏈隊列空鏈隊列空p = Q.front-next;e = p-data;/ / 返回被刪元素的值返回被刪元素的值Q.

43、front-next=p-next; / / 修改隊頭結點指針修改隊頭結點指針if(Q.rear=p) Q.rear=Q.front; free(p);/ / 釋放被刪結點釋放被刪結點return OK; / DeQueue3.3.3 隊列的順序表示和實現隊列的順序表示和實現 利用一組利用一組連續的存儲單元連續的存儲單元(一維數組一維數組) 依次存放從隊首依次存放從隊首到隊尾的各個元素，稱為到隊尾的各個元素，稱為順序隊列順序隊列。靜態順序隊列靜態順序隊列，其類型定義如下：，其類型定義如下：#define MAX_QUEUE_SIZE 100typedef struct queue ElemTy

44、pe Queue_arrayMAX_QUEUE_SIZE ;int front ;int rear ;SqQueue;3.3.2.1 隊列的順序隊列的順序存儲結構存儲結構設立一個設立一個隊首指針隊首指針front ，一個，一個隊尾指針隊尾指針rear ，分，分別指向隊首和隊尾元素別指向隊首和隊尾元素。 初始化：初始化：front=rear=0。 入隊入隊：將新元素插入將新元素插入rear所指的位置，然后所指的位置，然后rear加加1。 出隊出隊：刪去刪去front所指的元素，然后所指的元素，然后front加加1并返回被并返回被刪元素。刪元素。 隊列為空隊列為空：front=rear。 隊滿：隊

45、滿：rear=MAX_QUEUE_SIZE-1或或front=rear。 在非空隊列里，隊首指針始終指向隊頭元素，而隊尾指針始終指向隊尾元素的下一位置。 順序隊列中存在“假溢出”現象。因為在入隊和出隊操作中，頭、尾指針只增加不減小，致使被刪除元素的空間永遠無法重新利用。因此，盡管隊列中實際元素個數可能遠遠小于數組大小，但可能由于尾指針巳超出向量空間的上界而不能做入隊。操作。該現象稱為假溢出。如圖所示是數組大小為5的順序隊列中隊首、隊尾指針和隊列中元素的變化情況：(a) 空隊列空隊列Q.frontQ.rear(b) 入隊入隊3個元素個元素a3a2a1Q.frontQ.rear(c) 出隊出隊3個

46、元素個元素Q.frontQ.rear(d) 入隊入隊2個元素個元素a5a4Q.frontQ.rear3.3.2.2 循環隊列循環隊列 為充分利用向量空間，克服上述為充分利用向量空間，克服上述“假溢出假溢出”現象的方法現象的方法是：將為隊列分配的向量空間看成為一個是：將為隊列分配的向量空間看成為一個首尾相接的圓環首尾相接的圓環，并稱這種隊列為并稱這種隊列為循環隊列循環隊列(Circular Queue)。 在循環隊列中進行出隊、入隊操作時，隊首、隊尾指針在循環隊列中進行出隊、入隊操作時，隊首、隊尾指針仍要加仍要加1，朝前移動。只不過當隊首、隊尾指針指向向量上，朝前移動。只不過當隊首、隊尾指針指向

47、向量上界界(MAX_QUEUE_SIZE-1)時，其加時，其加1操作的結果是指向向量操作的結果是指向向量的下界的下界0。這種循環意義下的加這種循環意義下的加1操作可以描述為：操作可以描述為：if (i+1=MAX_QUEUE_SIZE) i=0;else i+ ;其中：其中： i代表隊首指針代表隊首指針(front)或隊尾指針或隊尾指針(rear)用模運算可簡化為：i=(i+1)%MAX_QUEUE_SIZE ;l 顯然，為循環隊列所分配的空間可以被充分利用，除非向量空間真的被隊列元素全部占用，否則不會上溢。因此，真正實用的順序隊列是循環隊列。 例 ： 設 有 循 環 隊 列 Q U 0 ，

48、5 ， 其 初 始 狀 態 是front=rear=0，各種操作后隊列的頭、尾指針的狀態變化情況如下圖所示。 123450(a) 空隊列空隊列frontrear123450(b) d, e, b, g入入隊隊frontdebgrear123450(c) d, e出隊出隊bgfrontrearl 入隊時尾指針向前追趕頭指針，出隊時頭指針向前追趕尾指針，故隊空和隊滿時頭尾指針均相等。因此，無法通過front=rear來判斷隊列“空”還是“滿”。解決此問題的方法是：約定入隊前，測試尾指針在循環意義下加1后是否等于頭指針，若相等則認為隊滿。即： rear所指的單元始終為空。 循環隊列為空：front=

49、rear 。 循環隊列滿：(rear+1)%MAX_QUEUE_SIZE =front。123450(d) i, j, k入入隊隊bgfrontijkrear123450(e) b, g出隊出隊ijkrearfront123450(f) r, p, s, t入隊入隊ijkfrontrprear循環隊列的基本操作1 循環隊列的初始化：Status InitQueue (SqQueue &Q)/ 構造一個空隊列 QQ.base = (QElemType *)malloc(MAXQSIZE*sizeof(QElemType); / 為循環隊列分配存儲空間if (!Q.base) exit(OVERFLOW);/ 存儲分配失敗Q.front = Q.rear = 0;return OK; / InitQueue2 求隊列的長度求隊列的長度int QueueLength (SqQueue Q)/ 返回隊列返回隊列Q中元素個數，即隊列的長度中元素個數，即隊列的長度 return (Q.rear-Q.front+MAXQSIZE) % MAXQSIZE); 3 入隊操作入隊操作Status EnQueue (Sq