第3章-特殊線性表課件

1、第3章 特殊線性表?xiàng)?、?duì)列和串本章的基本內(nèi)容是：三種特殊的線性表?xiàng)?、?duì)列、串從數(shù)據(jù)結(jié)構(gòu)角度看，棧和隊(duì)列是操作受限的線性表，他們的邏輯結(jié)構(gòu)相同。串是重要的非數(shù)值處理對象，它是以字符作為數(shù)據(jù)元素的線性表。 特殊線性表?xiàng)５倪壿嫿Y(jié)構(gòu)空棧：不含任何數(shù)據(jù)元素的棧。 （a1, a2, , an）棧：限定僅在表尾進(jìn)行插入和刪除操作的線性表。棧頂棧底允許插入和刪除的一端稱為棧頂，另一端稱為棧底。 a1a2a3入棧出棧棧底棧頂 特殊線性表?xiàng)２迦耄喝霔?、進(jìn)棧、壓棧刪除：出棧、彈棧棧頂棧頂棧的示意圖棧的操作特性：后進(jìn)先出a1a2a3入棧出棧棧底棧頂 特殊線性表?xiàng)２迦耄喝霔?、進(jìn)棧、壓棧刪除：出棧、彈棧棧頂棧的示意圖例

2、：有三個元素按a、b、c的次序依次進(jìn)棧，且每個元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？ 特殊線性表?xiàng)５讞ｍ攁b棧頂c棧頂 情況1：棧的邏輯結(jié)構(gòu) 特殊線性表?xiàng)５讞ｍ攁b棧頂c棧頂出棧序列：c出棧序列：c、b出棧序列：c、b、a例：有三個元素按a、b、c的次序依次進(jìn)棧，且每個元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu) 情況1： 特殊線性表?xiàng)５讞ｍ攁b棧頂出棧序列：b 情況2：例：有三個元素按a、b、c的次序依次進(jìn)棧，且每個元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu) 特殊線性表?xiàng)５譨出棧序列：b出棧序列：b、c出棧序列： b、 c、ac棧頂棧頂注意：棧只

3、是對表插入和刪除操作的位置進(jìn)行了限制，并沒有限定插入和刪除操作進(jìn)行的時間。例：有三個元素按a、b、c的次序依次進(jìn)棧，且每個元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu) 情況2：棧的抽象數(shù)據(jù)類型定義 特殊線性表?xiàng)DT StackData 棧中元素具有相同類型及后進(jìn)先出特性， 相鄰元素具有前驅(qū)和后繼關(guān)系Operation InitStack 前置條件：棧不存在 輸入：無 功能：棧的初始化 輸出：無 后置條件：構(gòu)造一個空棧 DestroyStack 前置條件：棧已存在 輸入：無 功能：銷毀棧 輸出：無 后置條件：釋放棧所占用的存儲空間Push 前置條件：棧已存在 輸入：元素值x 功能

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

5、性表?xiàng)５捻樞虼鎯Y(jié)構(gòu)及實(shí)現(xiàn) 順序棧棧的順序存儲結(jié)構(gòu)如何改造數(shù)組實(shí)現(xiàn)棧的順序存儲？ 0 1 2 3 4 5 6 7 8a1確定用數(shù)組的哪一端表示棧底。 特殊線性表?xiàng)８皆O(shè)指針top指示棧頂元素在數(shù)組中的位置。 top出棧：top減1進(jìn)棧：top加1?？眨簍op= -1 0 1 2 3 4 5 6 7 8 特殊線性表?xiàng)1topa2topa3top棧滿：top= MAX_SIZE棧的順序存儲結(jié)構(gòu)及實(shí)現(xiàn) 順序棧類的聲明const int MAX_SIZE=100;template class seqStack public: seqStack ( ) ; seqStack ( ); void Pus

6、h ( T x ); T Pop ( ); T GetTop ( ); bool Empty ( ); private: T dataMAX_SIZE; int top; 特殊線性表?xiàng)ｍ樞驐５膶?shí)現(xiàn)入棧template void seqStack:Push ( T x) if (top=MAX_SIZE-1) throw “溢出”; top+; datatop=x; 特殊線性表?xiàng)２僮鹘涌冢?void Push( T x );時間復(fù)雜度？順序棧的實(shí)現(xiàn)出棧template T seqStack: Pop ( ) if (top=-1) throw “溢出”; x=datatop-; return x

7、; 特殊線性表?xiàng)２僮鹘涌冢?T Pop( );時間復(fù)雜度？兩棧共享空間 解決方案1：直接解決：為每個棧開辟一個數(shù)組空間。 解決方案2： 順序棧單向延伸使用一個數(shù)組來存儲兩個棧 特殊線性表?xiàng)Ｔ谝粋€程序中需要同時使用具有相同數(shù)據(jù)類型的兩個棧，如何順序存儲這兩個棧？會出現(xiàn)什么問題？如何解決？兩棧共享空間：使用一個數(shù)組來存儲兩個棧，讓一個棧的棧底為該數(shù)組的始端，另一個棧的棧底為該數(shù)組的末端，兩個棧從各自的端點(diǎn)向中間延伸。 特殊線性表?xiàng)蓷９蚕砜臻g 棧1的底固定在下標(biāo)為0的一端；棧2的底固定在下標(biāo)為StackSize-1的一端。 top1和top2分別為棧1和棧2的棧頂指針；Stack_Size為整個數(shù)

8、組空間的大?。▓D中用S表示）；a1 a2 aitop10 1 2 S-1兩棧共享空間兩棧共享空間 top2bj b2 b1棧1底棧2底兩棧共享空間top1= -1什么時候棧1為空？a1 a2 aitop10 1 2 S-1兩棧共享空間 top2bj b2 b1top1兩棧共享空間top1= -1什么時候棧1為空？a1 a2 aitop10 1 2 S-1兩棧共享空間 top2bj b2 b1什么時候棧2為空？top2top2= Stack_Size兩棧共享空間top1= -1什么時候棧1為空？a1 a2 aitop10 1 2 S-1兩棧共享空間 top2bj b2 b1什么時候棧2為空？to

9、p2= Stack_Size什么時候棧滿？top2= top1+1const int Stack_Size=100; template class 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; ;兩棧共享空間類的聲明兩棧共享空間1. 如果棧滿，則拋出上溢異常；2. 判斷是插在棧1還是棧2； 2.1 若在棧1插入，則 2.

10、1.1 top1加1; 2.1.2 在top1處填入x； 2.2 若在棧2插入，則 2.2.1 top2減1; 2.2.2 在top2處填入x；兩棧共享空間兩棧共享空間的實(shí)現(xiàn)插入 操作接口：void Push(int i, T x) ;1. 若是在棧1刪除，則 1.1 若棧1為空棧，拋出下溢異常； 1.2 刪除并返回棧1的棧頂元素；2. 若是在棧2刪除，則 2.1 若棧2為空棧，拋出下溢異常； 2.2 刪除并返回棧2的棧頂元素；兩棧共享空間兩棧共享空間的實(shí)現(xiàn)刪除 操作接口：T Pop(int i) ;棧的鏈接存儲結(jié)構(gòu)及實(shí)現(xiàn) 鏈棧：棧的鏈接存儲結(jié)構(gòu) 特殊線性表?xiàng)irsta1a2anai鏈棧需要

11、加頭結(jié)點(diǎn)嗎？如何改造鏈表實(shí)現(xiàn)棧的鏈接存儲？將哪一端作為棧頂？將鏈頭作為棧頂，方便操作。鏈棧不需要附設(shè)頭結(jié)點(diǎn)。棧的鏈接存儲結(jié)構(gòu)及實(shí)現(xiàn) 棧頂棧底鏈棧：棧的鏈接存儲結(jié)構(gòu) 特殊線性表?xiàng)opanan-1a1firsta1a2anai兩種示意圖在內(nèi)存中對應(yīng)同一種狀態(tài)topa1an-1an棧頂棧底鏈棧的類聲明template class LinkStack public: LinkStack( ); LinkStack( ); void Push(T x); T Pop( ); T GetTop( ); bool Empty( ); private: Node *top; 特殊線性表?xiàng)Ｋ惴枋觯簍empl

12、ate void LinkStack:Push(T x) s=new Node; s-data=x; s-next=top; top=s; 特殊線性表?xiàng)opanan-1a1鏈棧的實(shí)現(xiàn)插入 xstop操作接口： void Push(T x); 為什么沒有判斷棧滿 ？算法描述：template T LinkStack:Pop( ) if (top=NULL) throw 下溢; x=top-data; p=top; top=top-next; delete p; return x; 特殊線性表?xiàng)ｆ湕５膶?shí)現(xiàn)插入操作接口： T Pop( ); topanan-1a1topp top+可以嗎？順序棧和

13、鏈棧的比較時間性能：相同，都是常數(shù)時間O(1)。空間性能：順序棧：有元素個數(shù)的限制和空間浪費(fèi)的問題。鏈棧：沒有棧滿的問題，只有當(dāng)內(nèi)存沒有可用空間時才會出現(xiàn)棧滿，但是每個元素都需要一個指針域，從而產(chǎn)生了結(jié)構(gòu)性開銷。 特殊線性表?xiàng)？傊?dāng)棧的使用過程中元素個數(shù)變化較大時，用鏈棧是適宜的，反之，應(yīng)該采用順序棧。棧的應(yīng)用舉例遞歸1 遞歸的定義子程序（或函數(shù)）直接調(diào)用自己或通過一系列調(diào)用語句間接調(diào)用自己，是一種描述問題和解決問題的基本方法。 2 遞歸的基本思想問題分解：把一個不能或不好解決的大問題轉(zhuǎn)化為一個或幾個小問題，再把這些小問題進(jìn)一步分解成更小的小問題，直至每個小問題都可以直接解決。 3 遞歸的要

14、素 遞歸邊界條件：確定遞歸到何時終止，也稱為遞歸出口； 遞歸模式：大問題是如何分解為小問題的，也稱為遞歸體。 棧的應(yīng)用舉例遞歸例1 階乘函數(shù)遞歸算法int fact ( int n ) if ( n = 0 ) return 1; else return n * fact (n-1);-*=時當(dāng)時當(dāng) )!1( 1!n1n1nnn棧的應(yīng)用舉例遞歸求解階乘 n! 的過程計(jì)算 fact(4)計(jì)算 4*fact(3)計(jì)算 3*fact(2)計(jì)算 2*fact(1)計(jì)算 fact(1)遞歸調(diào)用回歸求值返回 24返回 6返回 2返回1棧的應(yīng)用舉例遞歸遞歸過程與遞歸工作棧遞歸過程在實(shí)現(xiàn)時，需要自己調(diào)用自己。

15、層層向下遞歸，返回次序正好相反： 遞歸調(diào)用 n! (n-1)! (n-2)! 1!=1 返回次序棧的應(yīng)用舉例遞歸遞歸的經(jīng)典問題漢諾塔問題 在世界剛被創(chuàng)建的時候有一座鉆石寶塔（塔A），其上有64個金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩個鉆石寶塔（塔B和塔C）。從世界創(chuàng)始之日起，婆羅門的牧師們就一直在試圖把塔A上的碟子移動到塔C上去，其間借助于塔B的幫助。每次只能移動一個碟子，任何時候都不能把一個碟子放在比它小的碟子上面。當(dāng)牧師們完成任務(wù)時，世界末日也就到了。棧的應(yīng)用舉例遞歸漢諾塔問題的遞歸求解:如果 n = 1，則將這一個盤子直接從 塔A移到塔 C 上。否則，執(zhí)行以

16、下三步： 將塔A上的n-1個碟子借助塔C先移到塔B上； 把塔A上剩下的一個碟子移到塔C上； 將n-1個碟子從塔B借助于塔A移到塔C上。 棧的應(yīng)用舉例遞歸 void Hanoi(int n, char A, char B, char C) if (n=1) Move(A, C); else Hanoi(n-1, A, C, B); Move(A, C); Hanoi(n-1, B, A, C); 棧的應(yīng)用舉例遞歸遞歸函數(shù)的內(nèi)部執(zhí)行過程每一次遞歸調(diào)用時，需要為過程中使用的參數(shù)、局部變量等另外分配存儲空間。每層遞歸調(diào)用需分配的空間形成遞歸工作記錄，按后進(jìn)先出的棧組織。 局部變量返回地址值 參活動記錄

17、框架遞歸工作記錄 運(yùn)行開始時，首先為遞歸調(diào)用建立一個工作棧，其結(jié)構(gòu)包括值參、局部變量和返回地址； 每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址壓棧； 每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的值參和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行。棧的應(yīng)用舉例遞歸 寫出函數(shù)當(dāng)前調(diào)用層執(zhí)行的各語句，并用有向弧表示語句的執(zhí)行次序； 對函數(shù)的每個遞歸調(diào)用，寫出對應(yīng)的函數(shù)調(diào)用，從調(diào)用處畫一條有向弧指向被調(diào)用函數(shù)入口，表示調(diào)用路線，從被調(diào)用函數(shù)末尾處畫一條有向弧指向調(diào)用語句的下面，表示返回路線； 在返回路線上標(biāo)出本層調(diào)用所得的函數(shù)值。 遞歸函數(shù)的運(yùn)行軌跡棧的

18、應(yīng)用舉例遞歸Hanio(3,A,B,C)Hanio(2,A,C,B)Hanio(1,A,B,C)Move (A,C)Move (A,B)Hanio(1,C,A,B)Hanio(1,A,B,C)Hanio(2,A,C,B)Move (C,B)Hanio(1,C,A,B)Move (A,C)Hanio(2,B,A,C)Hanio(1,B,C,A)Move (B,C)Hanio(1,A,B,C)Hanio(1,B,C,A)Move (A,C)Hanio(2,B,A,C)Move (B,A)Hanio(1,A,B,C)結(jié)束特殊線性表隊(duì)列隊(duì)列的邏輯結(jié)構(gòu)空隊(duì)列：不含任何數(shù)據(jù)元素的隊(duì)列。 隊(duì)列：只允許在一端

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

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

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

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

23、儲結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)出隊(duì)a1a2a3a4rearfrontfrontfront出隊(duì)操作時間性能提高為O(1)例：a1a2依次出隊(duì)特殊線性表隊(duì)列隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)出隊(duì)a3a4rearfront隊(duì)列的移動有什么特點(diǎn)？例：a1a2依次出隊(duì)特殊線性表隊(duì)列隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)出隊(duì)a3a4rearfront整個隊(duì)列向數(shù)組下標(biāo)較大方向移動單向移動性假溢出：當(dāng)元素被插入到數(shù)組中下標(biāo)最大的位置上之后，隊(duì)列的空間就用盡了，盡管此時數(shù)組的低端還有空閑空間，這種現(xiàn)象叫做假溢出。特殊線性表隊(duì)列隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn) 繼續(xù)入隊(duì)會出現(xiàn)什么情況

24、？0 1 2 3 4 入隊(duì)出隊(duì)a3a4rearfronta5rear循環(huán)隊(duì)列：將存儲隊(duì)列的數(shù)組頭尾相接。特殊線性表隊(duì)列隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn) 如何解決假溢出？0 1 2 3 4 入隊(duì)出隊(duì)a3a4fronta5rearreara6特殊線性表隊(duì)列不存在物理的循環(huán)結(jié)構(gòu)，用軟件方法實(shí)現(xiàn)。求模：（41）mod 50隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn) 如何實(shí)現(xiàn)循環(huán)隊(duì)列？0 1 2 3 4 入隊(duì)出隊(duì)a3a4frontreara6如何判斷循環(huán)隊(duì)列隊(duì)空？特殊線性表隊(duì)列隊(duì)空的臨界狀態(tài)隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)出隊(duì)a3rearfront如何判斷循環(huán)隊(duì)列隊(duì)空？特殊線性表隊(duì)列執(zhí)行出隊(duì)操作隊(duì)空：front

25、=rear隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)出隊(duì)a3frontrearfront如何判斷循環(huán)隊(duì)列隊(duì)滿？隊(duì)滿的臨界狀態(tài)隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn) 特殊線性表隊(duì)列0 1 2 3 4 入隊(duì)出隊(duì)a3a4fronta5reara6如何判斷循環(huán)隊(duì)列隊(duì)滿？執(zhí)行入隊(duì)操作隊(duì)滿：front=rear隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn) 特殊線性表隊(duì)列0 1 2 3 4 入隊(duì)出隊(duì)a3a4fronta5reara6reara7方法一：附設(shè)一個存儲隊(duì)列中元素個數(shù)的變量num，當(dāng)num=0時隊(duì)空，當(dāng)num=QueueSize時為隊(duì)滿；方法二：修改隊(duì)滿條件，浪費(fèi)一個元素空間，隊(duì)滿時數(shù)組中只有一個空閑單元；方法三：設(shè)置標(biāo)志

26、flag，當(dāng)front=rear且flag=0時為隊(duì)空，當(dāng)front=rear且flag=1時為隊(duì)滿。如何確定不同的隊(duì)空、隊(duì)滿的判定條件？為什么要將隊(duì)空和隊(duì)滿的判定條件分開？特殊線性表隊(duì)列隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn) 隊(duì)滿的條件：(rear+1) mod QueueSize=front隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn) 特殊線性表隊(duì)列0 1 2 3 4 入隊(duì)rearfronta3a4fronta5reara6出隊(duì)循環(huán)隊(duì)列類的聲明const int QueueSize=100; template class CirQueue public: CirQueue( )； CirQueue( )； void EnQ

27、ueue(T x); T DeQueue( ); T GetQueue( ); bool Empty( )； private: T dataQueueSize; int front, rear;特殊線性表隊(duì)列template void CirQueue:EnQueue(T x) if (rear+1) % QueueSize =front) throw 上溢; rear=(rear+1) % QueueSize; datarear=x; 特殊線性表隊(duì)列循環(huán)隊(duì)列的實(shí)現(xiàn)入隊(duì)0 1 2 3 4 入隊(duì)出隊(duì)a3a4rearfronta5rear0 1 2 3 4 入隊(duì)a4a5a6出隊(duì)template T

28、 CirQueue:DeQueue( ) if (rear=front) throw 下溢; front=(front+1) % QueueSize; return datafront; 特殊線性表隊(duì)列循環(huán)隊(duì)列的實(shí)現(xiàn)出隊(duì)frontrearfronta3template T CirQueue:GetQueue( ) if (rear=front) throw 下溢; i=(front+1) % QueueSize; return datai;特殊線性表隊(duì)列循環(huán)隊(duì)列的實(shí)現(xiàn)讀隊(duì)頭元素0 1 2 3 4 入隊(duì)a4a5a6出隊(duì)frontreara3 i隊(duì)列的鏈接存儲結(jié)構(gòu)及實(shí)現(xiàn) 鏈隊(duì)列：隊(duì)列的鏈接存儲結(jié)構(gòu)

29、 隊(duì)頭指針即為鏈表的頭指針特殊線性表隊(duì)列firsta1a2an如何改造單鏈表實(shí)現(xiàn)隊(duì)列的鏈接存儲？rearfront隊(duì)列的鏈接存儲結(jié)構(gòu)及實(shí)現(xiàn) 特殊線性表隊(duì)列非空鏈隊(duì)列fronta1a2anrear空鏈隊(duì)列frontrear鏈隊(duì)列類的聲明template class LinkQueue public: LinkQueue( ); LinkQueue( ); void EnQueue(T x); T DeQueue( ); T GetQueue( )； bool Empty( )； private: Node *front, *rear;特殊線性表隊(duì)列操作接口： LinkQueue( ); 算法描述

30、：template LinkQueue:LinkQueue( ) front=new Node; front-next=NULL; rear=front;特殊線性表隊(duì)列鏈隊(duì)列的實(shí)現(xiàn)構(gòu)造函數(shù)frontrear xs特殊線性表隊(duì)列鏈隊(duì)列的實(shí)現(xiàn)入隊(duì)操作接口： void EnQueue(T x);fronta1anrearrearfront xsrearrear算法描述：s-next=NULL;rear-next=s; rear=s;如何沒有頭結(jié)點(diǎn)會怎樣？ xs特殊線性表隊(duì)列鏈隊(duì)列的實(shí)現(xiàn)入隊(duì)操作接口： void EnQueue(T x);fronta2anrearrear算法描述：s-next=NUL

31、L;rear-next=s; rear=s;如何沒有頭結(jié)點(diǎn)會怎樣？a1 xs特殊線性表隊(duì)列鏈隊(duì)列的實(shí)現(xiàn)入隊(duì)操作接口： void EnQueue(T x);fronta2anrearrearfront=rear=NULL xsrear算法描述：s-next=NULL;rear=s; front=s;如何沒有頭結(jié)點(diǎn)會怎樣？a1front特殊線性表隊(duì)列鏈隊(duì)列的實(shí)現(xiàn)入隊(duì)template void LinkQueue:EnQueue(T x) s=new Node; s-data=x; s-next=NULL; rear-next=s; rear=s;特殊線性表隊(duì)列鏈隊(duì)列的實(shí)現(xiàn)出隊(duì)fronta1a2an

32、rearp算法描述：p=front-next; front-next=p-next;特殊線性表隊(duì)列鏈隊(duì)列的實(shí)現(xiàn)出隊(duì)fronta1a2anrearp考慮邊界情況：隊(duì)列中只有一個元素？fronta1prearrear算法描述：if (p-next=NULL) rear=front;如何判斷邊界情況？template T LinkQueue:DeQueue( ) if (rear=front) throw 下溢; p=front-next; x=p-data; front-next=p-next; if (p-next=NULL) rear=front; delete p; return x;特殊線

33、性表隊(duì)列鏈隊(duì)列的實(shí)現(xiàn)出隊(duì)循環(huán)隊(duì)列和鏈隊(duì)列的比較時間性能:循環(huán)隊(duì)列和鏈隊(duì)列的基本操作都需要常數(shù)時間O (1)。 空間性能:循環(huán)隊(duì)列：必須預(yù)先確定一個固定的長度，所以有存儲元素個數(shù)的限制和空間浪費(fèi)的問題。鏈隊(duì)列：沒有隊(duì)列滿的問題，只有當(dāng)內(nèi)存沒有可用空間時才會出現(xiàn)隊(duì)列滿，但是每個元素都需要一個指針域，從而產(chǎn)生了結(jié)構(gòu)性開銷。特殊線性表隊(duì)列特殊線性表串串的邏輯結(jié)構(gòu)非空串通常記為： S= s1 s2 sn 其中：S是串名，雙引號是定界符，雙引號引起來的部分是串值 ，si（1in）是一個任意字符。串：零個或多個字符組成的有限序列。串長度：串中所包含的字符個數(shù)?？沾洪L度為0的串，記為： 。特殊線性表串串的邏

34、輯結(jié)構(gòu)串的數(shù)據(jù)對象約束為某個字符集。微機(jī)上常用的字符集是標(biāo)準(zhǔn)ASCII碼，由 7 位二進(jìn)制數(shù)表示一個字符，總共可以表示 128 個字符。擴(kuò)展ASCII碼由 8 位二進(jìn)制數(shù)表示一個字符，總共可以表示 256 個字符，足夠表示英語和一些特殊符號，但無法滿足國際需要。Unicode由 16 位二進(jìn)制數(shù)表示一個字符，總共可以表示 216個字符，即6萬5千多個字符，能夠表示世界上所有語言的所有字符，包括亞洲國家的表意字符。為了保持兼容性，Unicode字符集中的前256個字符與擴(kuò)展ASCII碼完全相同。 S1=ab12cd S2=ab12 S3=ab13S4=ab12S5= S6= 特殊線性表串串的邏輯

35、結(jié)構(gòu)子串：串中任意個連續(xù)的字符組成的子序列。主串：包含子串的串。子串的位置：子串的第一個字符在主串中的序號。串的比較：通過組成串的字符之間的比較來進(jìn)行的。 給定兩個串：X=x1x2xn和Y=y1y2ym，則：1. 當(dāng)n=m且x1=y1，xn=ym時，稱X=Y；2. 當(dāng)下列條件之一成立時，稱XY： nm且xi=yi（1 in）；存在kmin(m,n)，使得xi=yi(1ik-1)且xkyk。 特殊線性表串串的邏輯結(jié)構(gòu)例：S1=ab12cd ，S2=ab12，S3=ab13串的抽象數(shù)據(jù)類型定義 StrLength (s)：求串s的長度。 StrAssign (s1, s2)：賦值，將s2的值賦值給

36、串s1。 StrConcat (s1, s2, s)：連接，將串s2放在串s1的后面連接成一個新串s。 SubStr (s, i, len)：求子串，返回從串s的第i個字符開始取長為 len 的子串。 StrCmp (s1, s2)：串比較，若s1=s2，返回0；若s1s2, 返回1。 StrIndex (s, t)：定位，返回子串t在主串s中首次出現(xiàn)的位置。若t不是s的子串，則返回0。特殊線性表串 StrInsert (s, i, t)：插入，將串t插入到串s中的第i個位置。 StrDelete (s, i, len)：刪除，在串s中刪除從第i個字符開始的連續(xù)len個字符。 StrRep (

37、s, t, r)：替換，在串s中用串r替換所有與串t相等的子串。特殊線性表串串的操作通常以串的整體作為操作對象。 與其他數(shù)據(jù)結(jié)構(gòu)相比，串的操作對象有什么特點(diǎn)？串的抽象數(shù)據(jù)類型定義求子串操作SubStr(s, i, len)示例a b c d e f g ei = 3, len = 3i = 7, len = 4特殊線性表串串的抽象數(shù)據(jù)類型定義c d ea b c d e f g eg e空串串的存儲結(jié)構(gòu) 順序串：用數(shù)組來存儲串中的字符序列。特殊線性表串如何改造數(shù)組實(shí)現(xiàn)串的順序存儲？（1）非壓縮形式。 a b c d e f g串的存儲結(jié)構(gòu) 順序串：用數(shù)組來存儲串中的字符序列。特殊線性表串如何改

38、造數(shù)組實(shí)現(xiàn)串的順序存儲？（1）非壓縮形式。 （2）壓縮形式。 a eb fc gd啟示：時空權(quán)衡！方案1：用一個變量來表示串的實(shí)際長度。 特殊線性表串如何表示串的長度？串的存儲結(jié)構(gòu) 0 1 2 3 4 5 6 Max-1 a b c d e f g9空 閑特殊線性表串方案1：用一個變量來表示串的實(shí)際長度。 串的存儲結(jié)構(gòu) 如何表示串的長度？0 1 2 3 4 5 6 7 Max-1 a b c d e f g 0空 閑方案2：在串尾存儲一個不會在串中出現(xiàn)的特殊字符作為串的終結(jié)符，表示串的結(jié)尾。 特殊線性表串方案3：用數(shù)組的0號單元存放串的長度，從1號單元開始存放串值。串的存儲結(jié)構(gòu) 如何表示串的長

39、度？方案2：在串尾存儲一個不會在串中出現(xiàn)的特殊字符作為串的終結(jié)符，表示串的結(jié)尾。 方案1：用一個變量來表示串的實(shí)際長度。 0 1 2 3 4 5 6 7 Max-1 9 a b c d e f g空 閑鏈接串：用鏈接存儲結(jié)構(gòu)來存儲串。（1）非壓縮形式 特殊線性表串串的存儲結(jié)構(gòu) 如何改造鏈表實(shí)現(xiàn)串的鏈接存儲？first a b g鏈接串：用鏈接存儲結(jié)構(gòu)來存儲串。（1）非壓縮形式 （2）壓縮形式 特殊線性表串串的存儲結(jié)構(gòu) 如何改造鏈表實(shí)現(xiàn)串的鏈接存儲？e f gfirsta b c d啟示：時空權(quán)衡！模式匹配 模式匹配：給定主串S=s1s2sn和模式T=t1t2tm，在S中尋找T 的過程稱為模式匹

40、配。如果匹配成功，返回T 在S中的位置，如果匹配失敗，返回0。假設(shè)串采用順序存儲結(jié)構(gòu)，串的長度存放在數(shù)組的0號單元，串值從1號單元開始存放。特殊線性表串基本思想：從主串S的第一個字符開始和模式T 的第一個字符進(jìn)行比較，若相等，則繼續(xù)比較兩者的后續(xù)字符；否則，從主串S的第二個字符開始和模式T 的第一個字符進(jìn)行比較，重復(fù)上述過程，直到T 中的字符全部比較完畢，則說明本趟匹配成功；或S中字符全部比較完，則說明匹配失敗。特殊線性表串模式匹配BF算法 模式匹配問題的特點(diǎn)： 算法的一次執(zhí)行時間不容忽視：問題規(guī)模通常很大，常常需要在大量信息中進(jìn)行匹配； 算法改進(jìn)所取得的積累效益不容忽視：模式匹配操作經(jīng)常被調(diào)

41、用，執(zhí)行頻率高。 si 主串S模式T tjji特殊線性表串模式匹配BF算法 回溯i 回溯j si 主串S模式Tji特殊線性表串模式匹配BF算法 tj si 主串S模式Tji特殊線性表串模式匹配BF算法 tj例：主串S=ababcabcacbab，模式T=abcaca b a b c a b c a c b a bi=3，j=3失??；i回溯到2，j回溯到1ij特殊線性表串模式匹配BF算法 ijij第 1趟a b c a c 例：主串S=ababcabcacbab，模式T=abcaca b a b c a b c a c b a bi=3，j=3失??；i回溯到2，j回溯到1j特殊線性表串模式匹配B

42、F算法 i第 1趟a b c a c 例：主串S=ababcabcacbab，模式T=abcaca b a b c a b c a c b a bi=2，j=1失敗i回溯到3，j回溯到1特殊線性表串模式匹配BF算法 第 2趟ija b c a c 例：主串S=ababcabcacbab，模式T=abcaca b a b c a b c a c b a bi=2，j=1失敗i回溯到3，j回溯到1特殊線性表串模式匹配BF算法 第 2趟ija b c a c 例：主串S=ababcabcacbab，模式T=abcaca b a b c a b c a c b a ba b c a c i=7，j=5

43、失敗i回溯到4，j回溯到1特殊線性表串模式匹配BF算法 第 3趟ijijijijij例：主串S=ababcabcacbab，模式T=abcaca b a b c a b c a c b a ba b c a c i=7，j=5失敗i回溯到4，j回溯到1特殊線性表串模式匹配BF算法 第 3趟ij例：主串S=ababcabcacbab，模式T=abcaca b a b c a b c a c b a ba b c a c i=4，j=1失敗i回溯到5，j回溯到1特殊線性表串模式匹配BF算法 第 4趟ij例：主串S=ababcabcacbab，模式T=abcaca b a b c a b c a c

44、 b a ba b c a c i=4，j=1失敗i回溯到5，j回溯到1特殊線性表串模式匹配BF算法 第 4趟ij例：主串S=ababcabcacbab，模式T=abcaca b a b c a b c a c b a ba b c a c i=5，j=1失敗i回溯到6，j回溯到1特殊線性表串模式匹配BF算法 第 5趟ij例：主串S=ababcabcacbab，模式T=abcaca b a b c a b c a c b a ba b c a c i=5，j=1失敗i回溯到6，j回溯到1特殊線性表串模式匹配BF算法 第 5趟ij例：主串S=ababcabcacbab，模式T=abcaca b

45、a b c a b c a c b a ba b c a c i=11，j=6，T中全部字符都比較完畢，匹配成功。特殊線性表串模式匹配BF算法 第 6趟ijijijijij1. 在串S和串T中設(shè)比較的起始下標(biāo)i和j；2. 循環(huán)直到S或T的所有字符均比較完； 2.1 如果Si=Tj，繼續(xù)比較S和T的下一個字符； 2.2 否則，將i和j回溯，準(zhǔn)備下一趟比較；3. 如果T中所有字符均比較完，則匹配成功，返回匹配的起始比較下標(biāo)；否則，匹配失敗，返回0；特殊線性表串模式匹配BF算法 int BF(char S , char T ) i=1; j=1; while (i=S0&jT0) return (i

46、-j+1); else return 0;特殊線性表串模式匹配BF算法 int BF(char S , char T ) i=1; j=1;start=1; while (i=S0&jT0) return start; else return 0;特殊線性表串模式匹配BF算法 設(shè)串S長度為n，串T長度為m，在匹配成功的情況下，考慮兩種極端情況： 最好：不成功的匹配都發(fā)生在串T的第一個字符。 例如：S=aaaaaaaaaabcdccccc T=bcd 特殊線性表串模式匹配BF算法 設(shè)串S長度為n，串T長度為m，在匹配成功的情況下，考慮兩種極端情況： 最好情況：不成功的匹配都發(fā)生在串T的第1個字符

47、。 設(shè)匹配成功發(fā)生在si處，則在i-1趟不成功的匹配中共比較了i-1次，第i趟成功的匹配共比較了m次，所以總共比較了i-1+m次，所有匹配成功的可能情況共有n-m+1種，則： )(2)()1(11mnOmnmipmnii+=+=+-+-=特殊線性表串模式匹配BF算法 設(shè)串S長度為n，串T長度為m，在匹配成功的情況下，考慮兩種極端情況： 最壞情況：不成功的匹配都發(fā)生在串T的最后一個字符。 例如：S=aaaaaaaaaaabccccc T=aaab 特殊線性表串模式匹配BF算法 設(shè)串S長度為n，串T長度為m，在匹配成功的情況下，考慮兩種極端情況： 最壞情況：不成功的匹配都發(fā)生在串T的最后一個字符。

48、 設(shè)匹配成功發(fā)生在si處，則在i-1趟不成功的匹配中共比較了(i-1)m次，第i趟成功的匹配共比較了m次，所以總共比較了im次，因此 特殊線性表串模式匹配KMP算法 為什么BF算法時間性能低？在每趟匹配不成功時存在大量回溯，沒有利用已經(jīng)部分匹配的結(jié)果。如何在匹配不成功時主串不回溯？主串不回溯，模式就需要向右滑動一段距離。如何確定模式的滑動距離？i=3，j=3失??； s2=t2;t1t2t1s2特殊線性表串模式匹配KMP算法 a b a b c a b c a c b a bij第 1趟a b c a c a b a b c a b c a c b a b第 2趟a b c a c i=3，j=

49、3失??； s2=t2;t1t2t1s2特殊線性表串模式匹配KMP算法 a b a b c a b c a c b a bij第 1趟a b c a c a b a b c a b c a c b a ba b c a c 第 3趟特殊線性表串模式匹配KMP算法 a b a b c a b c a c b a ba b c a c 第 3趟iji=7，j=5失敗s4=t2;t1t2t1s4a b a b c a b c a c b a ba b c a c 第 4趟特殊線性表串模式匹配KMP算法 a b a b c a b c a c b a ba b c a c 第 3趟iji=7，j=5失敗s5=t3;t1t3t1s5a b a b c a b c a c b a ba b c a c 第 5趟特殊線性表串模式匹配KMP算法 a b a b c a b c a c b a ba b c a c 第 3趟iji=7，j=5失敗s5=t3;t1t3t1s5a b a b c a b c a c b a ba