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

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

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

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

5、性表棧棧的順序存儲結構及實現 順序棧棧的順序存儲結構如何改造數組實現棧的順序存儲？ 0 1 2 3 4 5 6 7 8a1確定用數組的哪一端表示棧底。 特殊線性表棧附設指針top指示棧頂元素在數組中的位置。 top出棧：top減1進棧：top加1棧空：top= -1 0 1 2 3 4 5 6 7 8 特殊線性表棧a1topa2topa3top棧滿：top= MAX_SIZE棧的順序存儲結構及實現 順序棧類的聲明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; 特殊線性表棧順序棧的實現入棧template void seqStack:Push ( T x) if (top=MAX_SIZE-1) throw “溢出”; top+; datatop=x; 特殊線性表棧操作接口： void Push( T x );時間復雜度？順序棧的實現出棧template T seqStack: Pop ( ) if (top=-1) throw “溢出”; x=datatop-; return x

7、; 特殊線性表棧操作接口： T Pop( );時間復雜度？兩棧共享空間 解決方案1：直接解決：為每個棧開辟一個數組空間。 解決方案2： 順序棧單向延伸使用一個數組來存儲兩個棧 特殊線性表棧在一個程序中需要同時使用具有相同數據類型的兩個棧，如何順序存儲這兩個棧？會出現什么問題？如何解決？兩棧共享空間：使用一個數組來存儲兩個棧，讓一個棧的棧底為該數組的始端，另一個棧的棧底為該數組的末端，兩個棧從各自的端點向中間延伸。 特殊線性表棧兩棧共享空間 棧1的底固定在下標為0的一端；棧2的底固定在下標為StackSize-1的一端。 top1和top2分別為棧1和棧2的棧頂指針；Stack_Size為整個數

8、組空間的大小（圖中用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；兩棧共享空間兩棧共享空間的實現插入 操作接口：void Push(int i, T x) ;1. 若是在棧1刪除，則 1.1 若棧1為空棧，拋出下溢異常； 1.2 刪除并返回棧1的棧頂元素；2. 若是在棧2刪除，則 2.1 若棧2為空棧，拋出下溢異常； 2.2 刪除并返回棧2的棧頂元素；兩棧共享空間兩棧共享空間的實現刪除 操作接口：T Pop(int i) ;棧的鏈接存儲結構及實現 鏈棧：棧的鏈接存儲結構 特殊線性表棧firsta1a2anai鏈棧需要

11、加頭結點嗎？如何改造鏈表實現棧的鏈接存儲？將哪一端作為棧頂？將鏈頭作為棧頂，方便操作。鏈棧不需要附設頭結點。棧的鏈接存儲結構及實現 棧頂棧底鏈棧：棧的鏈接存儲結構 特殊線性表棧topanan-1a1firsta1a2anai兩種示意圖在內存中對應同一種狀態topa1an-1an棧頂棧底鏈棧的類聲明template class LinkStack public: LinkStack( ); LinkStack( ); void Push(T x); T Pop( ); T GetTop( ); bool Empty( ); private: Node *top; 特殊線性表棧算法描述：templ

12、ate void LinkStack:Push(T x) s=new Node; s-data=x; s-next=top; top=s; 特殊線性表棧topanan-1a1鏈棧的實現插入 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; 特殊線性表棧鏈棧的實現插入操作接口： T Pop( ); topanan-1a1topp top+可以嗎？順序棧和

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

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

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

16、下三步： 將塔A上的n-1個碟子借助塔C先移到塔B上； 把塔A上剩下的一個碟子移到塔C上； 將n-1個碟子從塔B借助于塔A移到塔C上。 棧的應用舉例遞歸 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); 棧的應用舉例遞歸遞歸函數的內部執行過程每一次遞歸調用時，需要為過程中使用的參數、局部變量等另外分配存儲空間。每層遞歸調用需分配的空間形成遞歸工作記錄，按后進先出的棧組織。 局部變量返回地址值 參活動記錄

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

18、應用舉例遞歸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)結束特殊線性表隊列隊列的邏輯結構空隊列：不含任何數據元素的隊列。 隊列：只允許在一端

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

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

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

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

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

24、？0 1 2 3 4 入隊出隊a3a4rearfronta5rear循環隊列：將存儲隊列的數組頭尾相接。特殊線性表隊列隊列的順序存儲結構及實現 如何解決假溢出？0 1 2 3 4 入隊出隊a3a4fronta5rearreara6特殊線性表隊列不存在物理的循環結構，用軟件方法實現。求模：（41）mod 50隊列的順序存儲結構及實現 如何實現循環隊列？0 1 2 3 4 入隊出隊a3a4frontreara6如何判斷循環隊列隊空？特殊線性表隊列隊空的臨界狀態隊列的順序存儲結構及實現 0 1 2 3 4 入隊出隊a3rearfront如何判斷循環隊列隊空？特殊線性表隊列執行出隊操作隊空：front

25、=rear隊列的順序存儲結構及實現 0 1 2 3 4 入隊出隊a3frontrearfront如何判斷循環隊列隊滿？隊滿的臨界狀態隊列的順序存儲結構及實現 特殊線性表隊列0 1 2 3 4 入隊出隊a3a4fronta5reara6如何判斷循環隊列隊滿？執行入隊操作隊滿：front=rear隊列的順序存儲結構及實現 特殊線性表隊列0 1 2 3 4 入隊出隊a3a4fronta5reara6reara7方法一：附設一個存儲隊列中元素個數的變量num，當num=0時隊空，當num=QueueSize時為隊滿；方法二：修改隊滿條件，浪費一個元素空間，隊滿時數組中只有一個空閑單元；方法三：設置標志

26、flag，當front=rear且flag=0時為隊空，當front=rear且flag=1時為隊滿。如何確定不同的隊空、隊滿的判定條件？為什么要將隊空和隊滿的判定條件分開？特殊線性表隊列隊列的順序存儲結構及實現 隊滿的條件：(rear+1) mod QueueSize=front隊列的順序存儲結構及實現 特殊線性表隊列0 1 2 3 4 入隊rearfronta3a4fronta5reara6出隊循環隊列類的聲明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;特殊線性表隊列template void CirQueue:EnQueue(T x) if (rear+1) % QueueSize =front) throw 上溢; rear=(rear+1) % QueueSize; datarear=x; 特殊線性表隊列循環隊列的實現入隊0 1 2 3 4 入隊出隊a3a4rearfronta5rear0 1 2 3 4 入隊a4a5a6出隊template T

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

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

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

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

32、rearp算法描述：p=front-next; front-next=p-next;特殊線性表隊列鏈隊列的實現出隊fronta1a2anrearp考慮邊界情況：隊列中只有一個元素？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、性表隊列鏈隊列的實現出隊循環隊列和鏈隊列的比較時間性能:循環隊列和鏈隊列的基本操作都需要常數時間O (1)。 空間性能:循環隊列：必須預先確定一個固定的長度，所以有存儲元素個數的限制和空間浪費的問題。鏈隊列：沒有隊列滿的問題，只有當內存沒有可用空間時才會出現隊列滿，但是每個元素都需要一個指針域，從而產生了結構性開銷。特殊線性表隊列特殊線性表串串的邏輯結構非空串通常記為： S= s1 s2 sn 其中：S是串名，雙引號是定界符，雙引號引起來的部分是串值 ，si（1in）是一個任意字符。串：零個或多個字符組成的有限序列。串長度：串中所包含的字符個數。空串：長度為0的串，記為： 。特殊線性表串串的邏

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

35、結構子串：串中任意個連續的字符組成的子序列。主串：包含子串的串。子串的位置：子串的第一個字符在主串中的序號。串的比較：通過組成串的字符之間的比較來進行的。 給定兩個串：X=x1x2xn和Y=y1y2ym，則：1. 當n=m且x1=y1，xn=ym時，稱X=Y；2. 當下列條件之一成立時，稱XY： nm且xi=yi（1 in）；存在kmin(m,n)，使得xi=yi(1ik-1)且xkyk。 特殊線性表串串的邏輯結構例：S1=ab12cd ，S2=ab12，S3=ab13串的抽象數據類型定義 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中首次出現的位置。若t不是s的子串，則返回0。特殊線性表串 StrInsert (s, i, t)：插入，將串t插入到串s中的第i個位置。 StrDelete (s, i, len)：刪除，在串s中刪除從第i個字符開始的連續len個字符。 StrRep (

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

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

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

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

41、用，執行頻率高。 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中設比較的起始下標i和j；2. 循環直到S或T的所有字符均比較完； 2.1 如果Si=Tj，繼續比較S和T的下一個字符； 2.2 否則，將i和j回溯，準備下一趟比較；3. 如果T中所有字符均比較完，則匹配成功，返回匹配的起始比較下標；否則，匹配失敗，返回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算法 設串S長度為n，串T長度為m，在匹配成功的情況下，考慮兩種極端情況： 最好：不成功的匹配都發生在串T的第一個字符。 例如：S=aaaaaaaaaabcdccccc T=bcd 特殊線性表串模式匹配BF算法 設串S長度為n，串T長度為m，在匹配成功的情況下，考慮兩種極端情況： 最好情況：不成功的匹配都發生在串T的第1個字符

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

48、 設匹配成功發生在si處，則在i-1趟不成功的匹配中共比較了(i-1)m次，第i趟成功的匹配共比較了m次，所以總共比較了im次，因此 特殊線性表串模式匹配KMP算法 為什么BF算法時間性能低？在每趟匹配不成功時存在大量回溯，沒有利用已經部分匹配的結果。如何在匹配不成功時主串不回溯？主串不回溯，模式就需要向右滑動一段距離。如何確定模式的滑動距離？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