1、第3章 特殊線性表棧、隊列和串本章的基本內容是：三種特殊的線性表棧、隊列、串從數(shù)據(jù)結構角度看，棧和隊列是操作受限的線性表，他們的邏輯結構相同。串是重要的非數(shù)值處理對象，它是以字符作為數(shù)據(jù)元素的線性表。 1 特殊線性表棧棧的邏輯結構空棧：不含任何數(shù)據(jù)元素的棧。 （a1, a2, , an）棧：限定僅在表尾進行插入和刪除操作的線性表。棧頂棧底允許插入和刪除的一端稱為棧頂，另一端稱為棧底。 2a1a2a3入棧出棧棧底棧頂 特殊線性表棧插入：入棧、進棧、壓棧刪除：出棧、彈棧棧頂棧頂棧的示意圖3棧的操作特性：后進先出a1a2a3入棧出棧棧底棧頂 特殊線性表棧插入：入棧、進棧、壓棧刪除：出棧、彈棧棧頂棧的

2、示意圖4例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？ 特殊線性表棧棧底棧頂ab棧頂c棧頂 情況1：棧的邏輯結構5 特殊線性表棧棧底棧頂ab棧頂c棧頂出棧序列：c出棧序列：c、b出棧序列：c、b、a例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧的邏輯結構 情況1：6 特殊線性表棧棧底棧頂ab棧頂出棧序列：b 情況2：例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧的邏輯結構7 特殊線性表棧棧底a出棧序列：b出棧序列：b、c出棧序列： b、 c、ac棧

3、頂棧頂注意：棧只是對表插入和刪除操作的位置進行了限制，并沒有限定插入和刪除操作進行的時間。例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧的邏輯結構 情況2：8例題解析習題2（1）（3）9棧的抽象數(shù)據(jù)類型定義 特殊線性表棧ADT StackData 棧中元素具有相同類型及后進先出特性， 相鄰元素具有前驅和后繼關系Operation InitStack 前置條件：棧不存在 輸入：無 功能：棧的初始化 輸出：無 后置條件：構造一個空棧 10DestroyStack 前置條件：棧已存在 輸入：無 功能：銷毀棧 輸出：無 后置條件：釋放棧所占用的存儲空間

4、Push 前置條件：棧已存在 輸入：元素值x 功能：在棧頂插入一個元素x 輸出：如果插入不成功，拋出異常 后置條件：如果插入成功，棧頂增加了一個元素棧的抽象數(shù)據(jù)類型定義 特殊線性表棧11Pop 前置條件：棧已存在 輸入：無 功能：刪除棧頂元素 輸出：如果刪除成功，返回被刪元素值，否則，拋出異常 后置條件：如果刪除成功，棧減少了一個元素GetTop 前置條件：棧已存在 輸入：無 功能：讀取當前的棧頂元素 輸出：若棧不空，返回當前的棧頂元素值 后置條件：棧不變棧的抽象數(shù)據(jù)類型定義 特殊線性表棧12Empty 前置條件：棧已存在 輸入：無 功能：判斷棧是否為空 輸出：如果棧為空，返回1，否則，返回0

5、 后置條件：棧不變endADT棧的抽象數(shù)據(jù)類型定義 特殊線性表棧13棧的順序存儲結構及實現(xiàn) 順序棧棧的順序存儲結構如何改造數(shù)組實現(xiàn)棧的順序存儲？ 0 1 2 3 4 5 6 7 8a1確定用數(shù)組的哪一端表示棧底。 特殊線性表棧附設指針top指示棧頂元素在數(shù)組中的位置。 top14出棧：top減1進棧：top加1?？眨簍op= -1 0 1 2 3 4 5 6 7 8 特殊線性表棧a1topa2topa3top棧滿：top= MAX_SIZE-1棧的順序存儲結構及實現(xiàn) 15 順序棧類的聲明const int MAX_SIZE=100;template class seqStack public:

6、 seqStack ( ) ; seqStack ( ); void Push ( T x ); T Pop ( ); T GetTop ( ); bool Empty ( ); private: T dataMAX_SIZE; int top; 特殊線性表棧16順序棧的實現(xiàn)入棧template void seqStack:Push ( T x) if (top=MAX_SIZE-1) throw “溢出”; top+; datatop=x; 特殊線性表棧操作接口： void Push( T x );時間復雜度？17順序棧的實現(xiàn)出棧template T seqStack: Pop ( ) if

7、 (top=-1) throw “溢出”; x=datatop-; return x; 特殊線性表棧操作接口： T Pop( );時間復雜度？18進制轉換 void Dec_to_Ocx(int a,int d) int div,x; SeqStack s; while(a!=0) div=a%d; s.Push(div); a=a/d; cout轉換后的數(shù)為：; while(!s.Empty() x=s.GetTop(); coutx; s.Pop(); coutendl; 19兩棧共享空間 解決方案1：直接解決：為每個棧開辟一個數(shù)組空間。 解決方案2： 順序棧單向延伸使用一個數(shù)組來存儲兩個

8、棧 特殊線性表棧在一個程序中需要同時使用具有相同數(shù)據(jù)類型的兩個棧，如何順序存儲這兩個棧？會出現(xiàn)什么問題？如何解決？20兩棧共享空間：使用一個數(shù)組來存儲兩個棧，讓一個棧的棧底為該數(shù)組的始端，另一個棧的棧底為該數(shù)組的末端，兩個棧從各自的端點向中間延伸。 特殊線性表棧兩棧共享空間 21棧1的底固定在下標為0的一端；棧2的底固定在下標為StackSize-1的一端。 top1和top2分別為棧1和棧2的棧頂指針；Stack_Size為整個數(shù)組空間的大?。▓D中用S表示）；a1 a2 aitop10 1 2 S-1兩棧共享空間兩棧共享空間 top2bj b2 b1棧1底棧2底22兩棧共享空間top1= -

9、1什么時候棧1為空？a1 a2 aitop10 1 2 S-1兩棧共享空間 top2bj b2 b1top123兩棧共享空間top1= -1什么時候棧1為空？a1 a2 aitop10 1 2 S-1兩棧共享空間 top2bj b2 b1什么時候棧2為空？top2top2= Stack_Size24兩棧共享空間top1= -1什么時候棧1為空？a1 a2 aitop10 1 2 S-1兩棧共享空間 top2bj b2 b1什么時候棧2為空？top2= Stack_Size什么時候棧滿？top2= top1+125const int Stack_Size=100; template class

10、BothStack public: BothStack( ); BothStack( ); void Push(int i, T x); T Pop(int i); T GetTop(int i); bool Empty(int i); private: T dataStack_Size; int top1, top2; ;兩棧共享空間類的聲明兩棧共享空間261. 如果棧滿，則拋出上溢異常；2. 判斷是插在棧1還是棧2； 2.1 若在棧1插入，則 2.1.1 top1加1; 2.1.2 在top1處填入x； 2.2 若在棧2插入，則 2.2.1 top2減1; 2.2.2 在top2處填入x；

11、兩棧共享空間兩棧共享空間的實現(xiàn)插入 操作接口：void Push(int i, T x) ;271. 若是在棧1刪除，則 1.1 若棧1為空棧，拋出下溢異常； 1.2 刪除并返回棧1的棧頂元素；2. 若是在棧2刪除，則 2.1 若棧2為空棧，拋出下溢異常； 2.2 刪除并返回棧2的棧頂元素；兩棧共享空間兩棧共享空間的實現(xiàn)刪除 操作接口：T Pop(int i) ;28括號匹配問題int Bracket_Test(char *str)/判別表達式中三種括號是否匹配SeqStack s;char *p,c;for(p=str;*p;p+)if(*p=(|*p=|*p=)s.Push(*p);els

12、e if(*p=)|*p=|*p=) if(s.Empty() return 0; c=s.Pop(); if(*p=)&c!=() return 0; if(*p=&c!=) return 0;if(*p=&c!=) return 0; /必須與當前棧頂括號匹配/forif(!s.Empty() return 0; return 1;29棧的鏈接存儲結構及實現(xiàn) 鏈棧：棧的鏈接存儲結構 特殊線性表棧firsta1a2anai鏈棧需要加頭結點嗎？如何改造鏈表實現(xiàn)棧的鏈接存儲？將哪一端作為棧頂？將鏈頭作為棧頂，方便操作。鏈棧不需要附設頭結點。30棧的鏈接存儲結構及實現(xiàn) 棧頂棧底鏈棧：棧的鏈接存儲結

13、構 特殊線性表棧topanan-1a1firsta1a2anai兩種示意圖在內存中對應同一種狀態(tài)topa1an-1an棧頂棧底31鏈棧的類聲明template class LinkStack public: LinkStack( ); LinkStack( ); void Push(T x); T Pop( ); T GetTop( ); bool Empty( ); private: Node *top; 特殊線性表棧32算法描述：template void LinkStack:Push(T x) s=new Node; s-data=x; s-next=top; top=s; 特殊線性表棧

14、topanan-1a1鏈棧的實現(xiàn)插入 xstop操作接口： void Push(T x); 為什么沒有判斷棧滿 ？33算法描述：template T LinkStack:Pop( ) if (top=NULL) throw 下溢; x=top-data; p=top; top=top-next; delete p; return x; 特殊線性表棧鏈棧的實現(xiàn)插入操作接口： T Pop( ); topanan-1a1topp top+可以嗎？34順序棧和鏈棧的比較時間性能：相同，都是常數(shù)時間O(1)?？臻g性能：順序棧：有元素個數(shù)的限制和空間浪費的問題。鏈棧：沒有棧滿的問題，只有當內存沒有可用空間

15、時才會出現(xiàn)棧滿，但是每個元素都需要一個指針域，從而產生了結構性開銷。 特殊線性表?？傊敆５氖褂眠^程中元素個數(shù)變化較大時，用鏈棧是適宜的，反之，應該采用順序棧。35棧的應用舉例遞歸1 遞歸的定義子程序（或函數(shù)）直接調用自己或通過一系列調用語句間接調用自己，是一種描述問題和解決問題的基本方法。 2 遞歸的基本思想問題分解：把一個不能或不好解決的大問題轉化為一個或幾個小問題，再把這些小問題進一步分解成更小的小問題，直至每個小問題都可以直接解決。 363 遞歸的要素 遞歸邊界條件：確定遞歸到何時終止，也稱為遞歸出口； 遞歸模式：大問題是如何分解為小問題的，也稱為遞歸體。 棧的應用舉例遞歸37例1

16、階乘函數(shù)遞歸算法int fact ( int n ) if ( n = 0 ) return 1; else return n * fact (n-1);-*=時當時當)!1(1!n1n1nnn棧的應用舉例遞歸38求解階乘 n! 的過程計算 fact(4)計算 4*fact(3)計算 3*fact(2)計算 2*fact(1)計算 fact(1)遞歸調用回歸求值返回 24返回 6返回 2返回1棧的應用舉例遞歸39遞歸過程與遞歸工作棧遞歸過程在實現(xiàn)時，需要自己調用自己。層層向下遞歸，返回次序正好相反： 遞歸調用 n! (n-1)! (n-2)! 1!=1 返回次序棧的應用舉例遞歸40遞歸函數(shù)的內

17、部執(zhí)行過程每一次遞歸調用時，需要為過程中使用的參數(shù)、局部變量等另外分配存儲空間。每層遞歸調用需分配的空間形成遞歸工作記錄，按后進先出的棧組織。 局部變量返回地址值 參活動記錄框架遞歸工作記錄 運行開始時，首先為遞歸調用建立一個工作棧，其結構包括值參、局部變量和返回地址； 每次執(zhí)行遞歸調用之前，把遞歸函數(shù)的值參和局部變量的當前值以及調用后的返回地址壓棧； 每次遞歸調用結束后，將棧頂元素出棧，使相應的值參和局部變量恢復為調用前的值，然后轉向返回地址指定的位置繼續(xù)執(zhí)行。棧的應用舉例遞歸41特殊線性表隊列隊列的邏輯結構空隊列：不含任何數(shù)據(jù)元素的隊列。 隊列：只允許在一端進行插入操作，而另一端進行刪除操

18、作的線性表。允許插入（也稱入隊、進隊）的一端稱為隊尾，允許刪除（也稱出隊）的一端稱為隊頭。 （a1, a2, , an）隊尾隊頭42隊列的操作特性：先進先出a1a2a3入隊隊尾隊頭出隊特殊線性表隊列隊頭隊列的邏輯結構43隊列的抽象數(shù)據(jù)類型定義 ADT Queue Data 隊列中元素具有相同類型及先進先出特性， 相鄰元素具有前驅和后繼關系Operation InitQueue 前置條件：隊列不存在 輸入：無 功能：初始化隊列 輸出：無 后置條件：創(chuàng)建一個空隊列特殊線性表隊列44 DestroyQueue 前置條件：隊列已存在 輸入：無 功能：銷毀隊列 輸出：無 后置條件：釋放隊列所占用的存儲空

19、間 EnQueue 前置條件：隊列已存在 輸入：元素值x 功能：在隊尾插入一個元素 輸出：如果插入不成功，拋出異常 后置條件：如果插入成功，隊尾增加了一個元素隊列的抽象數(shù)據(jù)類型定義 特殊線性表隊列45 DeQueue 前置條件：隊列已存在 輸入：無 功能：刪除隊頭元素 輸出：如果刪除成功，返回被刪元素值 后置條件：如果刪除成功，隊頭減少了一個元素 GetQueue 前置條件：隊列已存在 輸入：無 功能：讀取隊頭元素 輸出：若隊列不空，返回隊頭元素 后置條件：隊列不變隊列的抽象數(shù)據(jù)類型定義 特殊線性表隊列46Empty 前置條件：隊列已存在 輸入：無 功能：判斷隊列是否為空 輸出：如果隊列為空，

20、返回1，否則，返回0 后置條件：隊列不變endADT隊列的抽象數(shù)據(jù)類型定義 特殊線性表隊列470 1 2 3 4 入隊出隊隊列的順序存儲結構及實現(xiàn) 順序隊列：隊列的順序存儲結構特殊線性表隊列如何改造數(shù)組實現(xiàn)隊列的順序存儲？例：a1a2a3a4依次入隊a1a2a3a4rearrearrearrear入隊操作時間性能為O(1)48特殊線性表隊列如何改造數(shù)組實現(xiàn)隊列的順序存儲？例：a1a2依次出隊隊列的順序存儲結構及實現(xiàn) 0 1 2 3 4 入隊出隊a1a2a3a4rear49特殊線性表隊列如何改造數(shù)組實現(xiàn)隊列的順序存儲？例：a1a2依次出隊隊列的順序存儲結構及實現(xiàn) 0 1 2 3 4 入隊出隊a2

21、a3a4rear50特殊線性表隊列如何改造數(shù)組實現(xiàn)隊列的順序存儲？例：a1a2依次出隊隊列的順序存儲結構及實現(xiàn) 0 1 2 3 4 入隊出隊a3a4rear出隊操作時間性能為O(n)51特殊線性表隊列隊列的順序存儲結構及實現(xiàn) 如何改進出隊的時間性能？放寬隊列的所有元素必須存儲在數(shù)組的前n個單元這一條件 ，只要求隊列的元素存儲在數(shù)組中連續(xù)的位置。設置隊頭、隊尾兩個指針 隊頭指針：front指向隊頭元素的前一個位置 隊尾指針：rear 指向隊尾元素52特殊線性表隊列隊列的順序存儲結構及實現(xiàn) 0 1 2 3 4 入隊出隊例：a1a2a3a4依次入隊a1a2a3a4rearrearrearrear入隊

22、操作時間性能仍為O(1)front rear53例：a1a2依次出隊特殊線性表隊列隊列的順序存儲結構及實現(xiàn) 0 1 2 3 4 入隊出隊a1a2a3a4rearfrontfrontfront出隊操作時間性能提高為O(1)54例：a1a2依次出隊特殊線性表隊列隊列的順序存儲結構及實現(xiàn) 0 1 2 3 4 入隊出隊a3a4rearfront隊列的移動有什么特點？55例：a1a2依次出隊特殊線性表隊列隊列的順序存儲結構及實現(xiàn) 0 1 2 3 4 入隊出隊a3a4rearfront整個隊列向數(shù)組下標較大方向移動單向移動性56假溢出：當元素被插入到數(shù)組中下標最大的位置上之后，隊列的空間就用盡了，盡管此時

23、數(shù)組的低端還有空閑空間，這種現(xiàn)象叫做假溢出。特殊線性表隊列隊列的順序存儲結構及實現(xiàn) 繼續(xù)入隊會出現(xiàn)什么情況？0 1 2 3 4 入隊出隊a3a4rearfronta5rear57循環(huán)隊列：將存儲隊列的數(shù)組頭尾相接。特殊線性表隊列隊列的順序存儲結構及實現(xiàn) 如何解決假溢出？0 1 2 3 4 入隊出隊a3a4fronta5rearreara658特殊線性表隊列不存在物理的循環(huán)結構，用軟件方法實現(xiàn)。求模：（41）mod 50隊列的順序存儲結構及實現(xiàn) 如何實現(xiàn)循環(huán)隊列？0 1 2 3 4 入隊出隊a3a4frontreara659如何判斷循環(huán)隊列隊空？特殊線性表隊列隊空的臨界狀態(tài)隊列的順序存儲結構及實

24、現(xiàn) 0 1 2 3 4 入隊出隊a3rearfront60如何判斷循環(huán)隊列隊空？特殊線性表隊列執(zhí)行出隊操作隊空：front=rear隊列的順序存儲結構及實現(xiàn) 0 1 2 3 4 入隊出隊a3frontrearfront61如何判斷循環(huán)隊列隊滿？隊滿的臨界狀態(tài)隊列的順序存儲結構及實現(xiàn) 特殊線性表隊列0 1 2 3 4 入隊出隊a3a4fronta5reara662如何判斷循環(huán)隊列隊滿？執(zhí)行入隊操作隊滿：front=rear隊列的順序存儲結構及實現(xiàn) 特殊線性表隊列0 1 2 3 4 入隊出隊a3a4fronta5reara6reara763方法一：附設一個存儲隊列中元素個數(shù)的變量num，當num=

25、0時隊空，當num=QueueSize時為隊滿；方法二：修改隊滿條件，浪費一個元素空間，隊滿時數(shù)組中只有一個空閑單元；方法三：設置標志flag，當front=rear且flag=0時為隊空，當front=rear且flag=1時為隊滿。如何確定不同的隊空、隊滿的判定條件？為什么要將隊空和隊滿的判定條件分開？特殊線性表隊列隊列的順序存儲結構及實現(xiàn) 64隊滿的條件：(rear+1) mod QueueSize=front隊列的順序存儲結構及實現(xiàn) 特殊線性表隊列0 1 2 3 4 入隊rearfronta3a4fronta5reara6出隊65數(shù)組用來表示一個循環(huán)隊列，為當前隊列頭元素的前一位置，為

26、隊尾元素的位置，假定隊列中元素的個數(shù)小于，計算隊列中元素的公式為（）rf; （）（nfr）% n; （）nrf; （）（nrf）% n66循環(huán)隊列類的聲明const int QueueSize=100; template class CirQueue public: CirQueue( )； CirQueue( )； void EnQueue(T x); T DeQueue( ); T GetQueue( ); bool Empty( )； private: T dataQueueSize; int front, rear;特殊線性表隊列67template void CirQueue:EnQ

27、ueue(T x) if (rear+1) % QueueSize =front) throw 上溢; rear=(rear+1) % QueueSize; datarear=x; 特殊線性表隊列循環(huán)隊列的實現(xiàn)入隊0 1 2 3 4 入隊出隊a3a4rearfronta5rear680 1 2 3 4 入隊a4a5a6出隊template T CirQueue:DeQueue( ) if (rear=front) throw 下溢; front=(front+1) % QueueSize; return datafront; 特殊線性表隊列循環(huán)隊列的實現(xiàn)出隊frontrearfronta369

28、template T CirQueue:GetQueue( ) if (rear=front) throw 下溢; i=(front+1) % QueueSize; return datai;特殊線性表隊列循環(huán)隊列的實現(xiàn)讀隊頭元素0 1 2 3 4 入隊a4a5a6出隊frontreara3 i70隊列的鏈接存儲結構及實現(xiàn) 鏈隊列：隊列的鏈接存儲結構 隊頭指針即為鏈表的頭指針特殊線性表隊列firsta1a2an如何改造單鏈表實現(xiàn)隊列的鏈接存儲？rearfront71隊列的鏈接存儲結構及實現(xiàn) 特殊線性表隊列非空鏈隊列fronta1a2anrear空鏈隊列frontrear72鏈隊列類的聲明tem

29、plate class LinkQueue public: LinkQueue( ); LinkQueue( ); void EnQueue(T x); T DeQueue( ); T GetQueue( )； bool Empty( )； private: Node *front, *rear;特殊線性表隊列73操作接口： LinkQueue( ); 算法描述：template LinkQueue:LinkQueue( ) front=new Node; front-next=NULL; rear=front;特殊線性表隊列鏈隊列的實現(xiàn)構造函數(shù)frontrear74 xs特殊線性表隊列鏈隊列的實現(xiàn)入隊操作接口： void EnQueue(T x);fronta1anrearrearfront xsrearrear算法描述：s-next=NULL;rear-next=s; rear=s;如何沒有頭結點會怎樣？75 xs特殊線性表隊列鏈隊列的實現(xiàn)入隊操作接口： void EnQueue(T x);fronta2anrearrear算法描述：s-next=NULL;rear-next=s; rear=s;如何沒有頭結點會怎樣？a176 x