第3章+特殊线性表.ppt

1、第3章 特殊线性表栈、队列和串,本章的基本内容是：,三种特殊的线性表栈、队列、串,从数据结构角度看，栈和队列是操作受限的线性表，他们的逻辑结构相同。 串是重要的非数值处理对象，它是以字符作为数据元素的线性表。,特殊线性表栈,栈的逻辑结构,空栈：不含任何数据元素的栈。,（a1, a2, , an）,栈：限定仅在表尾进行插入和删除操作的线性表。,允许插入和删除的一端称为栈顶，另一端称为栈底。,a1,a2,a3,入栈,出栈,特殊线性表栈,插入：入栈、进栈、压栈 删除：出栈、弹栈,栈的示意图,栈的操作特性：后进先出,a1,a2,a3,入栈,出栈,特殊线性表栈,插入：入栈、进栈、压栈 删除：出栈、弹栈,

2、栈的示意图,例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？,特殊线性表栈,a,b,c,情况1：,栈的逻辑结构,特殊线性表栈,a,b,c,出栈序列：c,出栈序列：c、b,出栈序列：c、b、a,例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？,栈的逻辑结构,情况1：,特殊线性表栈,a,b,出栈序列：b,情况2：,例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？,栈的逻辑结构,特殊线性表栈,a,出栈序列：b,出栈序列：b、c,出栈序列： b、 c、a,c,注意：

3、栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。,例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？,栈的逻辑结构,情况2：,栈的抽象数据类型定义,特殊线性表栈,ADT Stack Data 栈中元素具有相同类型及后进先出特性， 相邻元素具有前驱和后继关系 Operation InitStack 前置条件：栈不存在 输入：无 功能：栈的初始化 输出：无 后置条件：构造一个空栈,DestroyStack 前置条件：栈已存在 输入：无 功能：销毁栈 输出：无 后置条件：释放栈所占用的存储空间 Push 前置条件：栈已存在 输

4、入：元素值x 功能：在栈顶插入一个元素x 输出：如果插入不成功，抛出异常 后置条件：如果插入成功，栈顶增加了一个元素,栈的抽象数据类型定义,特殊线性表栈,Pop 前置条件：栈已存在 输入：无 功能：删除栈顶元素 输出：如果删除成功，返回被删元素值，否则，抛出异常 后置条件：如果删除成功，栈减少了一个元素 GetTop 前置条件：栈已存在 输入：无 功能：读取当前的栈顶元素 输出：若栈不空，返回当前的栈顶元素值 后置条件：栈不变,栈的抽象数据类型定义,特殊线性表栈,Empty 前置条件：栈已存在 输入：无 功能：判断栈是否为空 输出：如果栈为空，返回1，否则，返回0 后置条件：栈不变 endAD

5、T,栈的抽象数据类型定义,特殊线性表栈,栈的顺序存储结构及实现,顺序栈栈的顺序存储结构,如何改造数组实现栈的顺序存储？,a1,确定用数组的哪一端表示栈底。,特殊线性表栈,附设指针top指示栈顶元素在数组中的位置。,出栈：top减1,进栈：top加1,栈空：top= -1,特殊线性表栈,a1,a2,a3,栈满：top= MAX_SIZE,栈的顺序存储结构及实现,顺序栈类的声明,const int MAX_SIZE=100; template class seqStack public: seqStack ( ) ; seqStack ( ); void Push ( T x ); T Pop (

6、 ); 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( );,时间复杂度？,两栈共享空间,解决方案2：,顺序栈单向延伸使用一个数组来存储两个栈,特殊线性表栈,在一个程序中需要同时使用具有相同数据类型的两个栈，如何顺序存储这两个栈？,会出现什么问题？如何解决？,两栈共享空间：使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。,特殊线性表栈,两栈共享空间,栈1的底固定在下标为0的一端； 栈2的底固定在下标为StackSize-1的一端。 top1和top2分别为栈1和栈2的栈顶指针； Stack_Size为整个数组空间的大小（图中用S表示）；,a1 a2 ai,

8、0 1 2 S-1,两栈共享空间,两栈共享空间,bj b2 b1,两栈共享空间,top1= -1,什么时候栈1为空？,a1 a2 ai,0 1 2 S-1,两栈共享空间,bj b2 b1,两栈共享空间,top1= -1,什么时候栈1为空？,a1 a2 ai,0 1 2 S-1,两栈共享空间,bj b2 b1,什么时候栈2为空？,top2= Stack_Size,两栈共享空间,top1= -1,什么时候栈1为空？,a1 a2 ai,0 1 2 S-1,两栈共享空间,bj b2 b1,什么时候栈2为空？,top2= Stack_Size,什么时候栈满？,top2= top1+1,const int

9、 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.1.1 top1加1; 2.1.2 在top1处填入x； 2.2 若在栈2插

10、入，则 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) ;,栈的链接存储结构及实现,链栈：栈的链接存储结构,特殊线性表栈,链栈需要加头结点吗？,如何改造链表实现栈的链接存储？,将哪一端作为栈顶？,将链头作为栈顶，方便

11、操作。,链栈不需要附设头结点。,栈的链接存储结构及实现,栈顶,栈底,链栈：栈的链接存储结构,特殊线性表栈,两种示意图在内存中对应同一种状态,栈顶,栈底,链 栈 的 类 声 明,template class LinkStack public: LinkStack( ); LinkStack( ); void Push(T x); T Pop( ); T GetTop( ); bool Empty( ); private: Node *top; ,特殊线性表栈,算法描述： template void LinkStack:Push(T x) s=new Node; s-data=x; s-next=

12、top; top=s; ,特殊线性表栈,an,an-1,a1,链栈的实现插入,操作接口： 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( );,an,an-1,a1,top+可以吗？,顺序栈和链栈的比较,时间性能：相同，都是常数时间O(1)。,空间性能： 顺序栈：有元素个数的限制和空间浪费的问题

13、。 链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。,特殊线性表栈,总之，当栈的使用过程中元素个数变化较大时，用链栈是适宜的，反之，应该采用顺序栈。,栈的应用举例递归,1 递归的定义,子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。,2 递归的基本思想,问题分解：把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题进一步分解成更小的小问题，直至每个小问题都可以直接解决。,3 递归的要素, 递归边界条件：确定递归到何时终止，也称为递归出口； 递归模式：大问题是如何分解为

14、小问题的，也称为递归体。,栈的应用举例递归,例1 阶乘函数,递归算法 int fact ( int n ) if ( n = 0 ) return 1; else return n * fact (n-1); ,栈的应用举例递归,求解阶乘 n! 的过程,计算 fact(4),递归调用,回归求值,栈的应用举例递归,递归过程与递归工作栈,递归过程在实现时，需要自己调用自己。 层层向下递归，返回次序正好相反： 递归调用 n! (n-1)! (n-2)! 1!=1 返回次序,栈的应用举例递归,递归的经典问题汉诺塔问题,在世界刚被创建的时候有一座钻石宝塔（塔A），其上有64个金碟。所有碟子按从大到小的次

15、序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。,栈的应用举例递归,汉诺塔问题的递归求解: 如果 n = 1，则将这一个盘子直接从 塔A移到塔 C 上。否则，执行以下三步： 将塔A上的n-1个碟子借助塔C先移到塔B上； 把塔A上剩下的一个碟子移到塔C上； 将n-1个碟子从塔B借助于塔A移到塔C上。,栈的应用举例递归,void Hanoi(int n, char A, char

16、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、值，然后转向返回地址指定的位置继续执行。,栈的应用举例递归, 写出函数当前调用层执行的各语句，并用有向弧表示语句的执行次序； 对函数的每个递归调用，写出对应的函数调用，从调用处画一条有向弧指向被调用函数入口，表示调用路线，从被调用函数末尾处画一条有向弧指向调用语句的下面，表示返回路线； 在返回路线上标出本层调用所得的函数值。,递归函数的运行轨迹,栈的应用举例递归,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),Move (C,B),Move (A,C),Hanio(2,B,A,C

18、),Hanio(1,B,C,A),Move (B,C),Hanio(1,A,B,C),Move (A,C),Move (B,A),特殊线性表队列,队列的逻辑结构,空队列：不含任何数据元素的队列。,队列：只允许在一端进行插入操作，而另一端进行删除操作的线性表。,允许插入（也称入队、进队）的一端称为队尾，允许删除（也称出队）的一端称为队头。,（a1, a2, , an）,队列的操作特性：先进先出,a1,a2,a3,入队,队尾,队头,出队,特殊线性表队列,队头,队列的逻辑结构,队列的抽象数据类型定义,ADT Queue Data 队列中元素具有相同类型及先进先出特性， 相邻元素具有前驱和后继关系 O

19、peration InitQueue 前置条件：队列不存在 输入：无 功能：初始化队列 输出：无 后置条件：创建一个空队列,特殊线性表队列,DestroyQueue 前置条件：队列已存在 输入：无 功能：销毁队列 输出：无 后置条件：释放队列所占用的存储空间 EnQueue 前置条件：队列已存在 输入：元素值x 功能：在队尾插入一个元素 输出：如果插入不成功，抛出异常 后置条件：如果插入成功，队尾增加了一个元素,队列的抽象数据类型定义,特殊线性表队列,DeQueue 前置条件：队列已存在 输入：无 功能：删除队头元素 输出：如果删除成功，返回被删元素值 后置条件：如果删除成功，队头减少了一个元

20、素 GetQueue 前置条件：队列已存在 输入：无 功能：读取队头元素 输出：若队列不空，返回队头元素 后置条件：队列不变,队列的抽象数据类型定义,特殊线性表队列,Empty 前置条件：队列已存在 输入：无 功能：判断队列是否为空 输出：如果队列为空，返回1，否则，返回0 后置条件：队列不变 endADT,队列的抽象数据类型定义,特殊线性表队列,队列的顺序存储结构及实现,顺序队列：队列的顺序存储结构,特殊线性表队列,如何改造数组实现队列的顺序存储？,例：a1a2a3a4依次入队,a1,a2,a3,a4,入队操作时间性能为O(1),特殊线性表队列,如何改造数组实现队列的顺序存储？,例：a1a2

21、依次出队,队列的顺序存储结构及实现,a1,a2,a3,a4,特殊线性表队列,如何改造数组实现队列的顺序存储？,例：a1a2依次出队,队列的顺序存储结构及实现,a2,a3,a4,特殊线性表队列,如何改造数组实现队列的顺序存储？,例：a1a2依次出队,队列的顺序存储结构及实现,a3,a4,出队操作时间性能为O(n),特殊线性表队列,队列的顺序存储结构及实现,如何改进出队的时间性能？,特殊线性表队列,队列的顺序存储结构及实现,例：a1a2a3a4依次入队,a1,a2,a3,a4,入队操作时间性能仍为O(1),例：a1a2依次出队,特殊线性表队列,队列的顺序存储结构及实现,a1,a2,a3,a4,出队

22、操作时间性能提高为O(1),例：a1a2依次出队,特殊线性表队列,队列的顺序存储结构及实现,a3,a4,队列的移动有什么特点？,例：a1a2依次出队,特殊线性表队列,队列的顺序存储结构及实现,a3,a4,假溢出：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。,特殊线性表队列,队列的顺序存储结构及实现,继续入队会出现什么情况？,a3,a4,a5,循环队列：将存储队列的数组头尾相接。,特殊线性表队列,队列的顺序存储结构及实现,如何解决假溢出？,0 1 2 3 4,入队,出队,a3,a4,a5,a6,特殊线性表队列,不存在物理的循环

23、结构，用软件方法实现。 求模：（41）mod 50,队列的顺序存储结构及实现,如何实现循环队列？,0 1 2 3 4,入队,出队,a3,a4,a6,如何判断循环队列队空？,特殊线性表队列,队空的临界状态,队列的顺序存储结构及实现,0 1 2 3 4,入队,出队,a3,如何判断循环队列队空？,特殊线性表队列,执行出队操作,队空：front=rear,队列的顺序存储结构及实现,0 1 2 3 4,入队,出队,a3,如何判断循环队列队满？,队满的临界状态,队列的顺序存储结构及实现,特殊线性表队列,0 1 2 3 4,入队,出队,a3,a4,a5,a6,如何判断循环队列队满？,执行入队操作,队满：fr

24、ont=rear,队列的顺序存储结构及实现,特殊线性表队列,0 1 2 3 4,入队,出队,a3,a4,a5,a6,a7,方法一：附设一个存储队列中元素个数的变量num，当num=0时队空，当num=QueueSize时为队满； 方法二：修改队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元； 方法三：设置标志flag，当front=rear且flag=0时为队空，当front=rear且flag=1时为队满。,如何确定不同的队空、队满的判定条件？ 为什么要将队空和队满的判定条件分开？,特殊线性表队列,队列的顺序存储结构及实现,队满的条件：(rear+1) mod QueueSize=f

25、ront,队列的顺序存储结构及实现,特殊线性表队列,循 环 队 列 类 的 声 明,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; ;,特殊线性表队列,template void CirQueue:EnQueue(T x) if (rear+1) % QueueSize

26、 =front) throw 上溢; rear=(rear+1) % QueueSize; datarear=x; ,特殊线性表队列,循环队列的实现入队,a3,a4,a5,0 1 2 3 4,入队,a4,a5,a6,出队,template T CirQueue:DeQueue( ) if (rear=front) throw 下溢; front=(front+1) % QueueSize; return datafront; ,特殊线性表队列,循环队列的实现出队,a3,template T CirQueue:GetQueue( ) if (rear=front) throw 下溢; i=(fr

27、ont+1) % QueueSize; return datai; ,特殊线性表队列,循环队列的实现读队头元素,0 1 2 3 4,入队,a4,a5,a6,出队,a3,队列的链接存储结构及实现,链队列：队列的链接存储结构,队头指针即为链表的头指针,特殊线性表队列,如何改造单链表实现队列的链接存储？,队列的链接存储结构及实现,特殊线性表队列,非空链队列,front,rear,空链队列,front,rear,链 队 列 类 的 声 明,template class LinkQueue public: LinkQueue( ); LinkQueue( ); void EnQueue(T x); T

28、DeQueue( ); T GetQueue( )； bool Empty( )； private: Node *front, *rear; ;,特殊线性表队列,操作接口： LinkQueue( );,算法描述： template LinkQueue:LinkQueue( ) front=new Node; front-next=NULL; rear=front; ,特殊线性表队列,链队列的实现构造函数,特殊线性表队列,链队列的实现入队,操作接口： void EnQueue(T x);,front,front,算法描述： s-next=NULL; rear-next=s; rear=s;,如何

29、没有头结点会怎样？,特殊线性表队列,链队列的实现入队,操作接口： void EnQueue(T x);,front,算法描述： s-next=NULL; rear-next=s; rear=s;,如何没有头结点会怎样？,特殊线性表队列,链队列的实现入队,操作接口： void EnQueue(T x);,front,front=rear=NULL,算法描述： s-next=NULL; rear=s; front=s;,如何没有头结点会怎样？,特殊线性表队列,链队列的实现入队,template void LinkQueue:EnQueue(T x) s=new Node; s-data=x; s-

30、next=NULL; rear-next=s; rear=s; ,特殊线性表队列,链队列的实现出队,front,rear,算法描述： p=front-next; front-next=p-next;,特殊线性表队列,链队列的实现出队,front,rear,考虑边界情况：队列中只有一个元素？,front,算法描述： 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

31、 (p-next=NULL) rear=front; delete p; return x; ,特殊线性表队列,链队列的实现出队,循环队列和链队列的比较,时间性能: 循环队列和链队列的基本操作都需要常数时间O (1)。,空间性能: 循环队列：必须预先确定一个固定的长度，所以有存储元素个数的限制和空间浪费的问题。 链队列：没有队列满的问题，只有当内存没有可用空间时才会出现队列满，但是每个元素都需要一个指针域，从而产生了结构性开销。,特殊线性表队列,特殊线性表串,串的逻辑结构,非空串通常记为： S= s1 s2 sn 其中：S是串名，双引号是定界符，双引号引起来的部分是串值 ，si（1in）是一个

32、任意字符。,串：零个或多个字符组成的有限序列。 串长度：串中所包含的字符个数。 空串：长度为0的串，记为： 。,特殊线性表串,串的逻辑结构,串的数据对象约束为某个字符集。,微机上常用的字符集是标准ASCII码，由 7 位二进制数表示一个字符，总共可以表示 128 个字符。扩展ASCII码由 8 位二进制数表示一个字符，总共可以表示 256 个字符，足够表示英语和一些特殊符号，但无法满足国际需要。Unicode由 16 位二进制数表示一个字符，总共可以表示 216个字符，即6万5千多个字符，能够表示世界上所有语言的所有字符，包括亚洲国家的表意字符。为了保持兼容性，Unicode字符集中的前256

33、个字符与扩展ASCII码完全相同。,S1=ab12cd S2=ab12 S3=ab13 S4=ab12 S5= S6= ,特殊线性表串,串的逻辑结构,子串：串中任意个连续的字符组成的子序列。 主串：包含子串的串。 子串的位置：子串的第一个字符在主串中的序号。,串的比较：通过组成串的字符之间的比较来进行的。,给定两个串：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=ab12c

34、d ，S2=ab12，S3=ab13,串的抽象数据类型定义, StrLength (s)：求串s的长度。 StrAssign (s1, s2)：赋值，将s2的值赋值给串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,

35、 i, t)：插入，将串t插入到串s中的第i个位置。 StrDelete (s, i, len)：删除，在串s中删除从第i个字符开始的连续len个字符。 StrRep (s, t, r)：替换，在串s中用串r替换所有与串t相等的子串。,特殊线性表串,串的操作通常以串的整体作为操作对象。,与其他数据结构相比，串的操作对象有什么特点？,串的抽象数据类型定义,求子串操作SubStr(s, i, len)示例,i = 3, len = 3,i = 7, len = 4,特殊线性表串,串的抽象数据类型定义,空串,串的存储结构,顺序串：用数组来存储串中的字符序列。,特殊线性表串,如何改造数组实现串的顺序存

36、储？,（1）非压缩形式。,串的存储结构,顺序串：用数组来存储串中的字符序列。,特殊线性表串,如何改造数组实现串的顺序存储？,（1）非压缩形式。,（2）压缩形式。,启示：时空权衡！,方案1：用一个变量来表示串的实际长度。,特殊线性表串,如何表示串的长度？,串的存储结构,特殊线性表串,方案1：用一个变量来表示串的实际长度。,串的存储结构,如何表示串的长度？,方案2：在串尾存储一个不会在串中出现的特殊字符作为串的终结符，表示串的结尾。,特殊线性表串,方案3：用数组的0号单元存放串的长度，从1号单元开始存放串值。,串的存储结构,如何表示串的长度？,方案2：在串尾存储一个不会在串中出现的特殊字符作为串的

37、终结符，表示串的结尾。,方案1：用一个变量来表示串的实际长度。,链接串：用链接存储结构来存储串。,（1）非压缩形式,特殊线性表串,串的存储结构,如何改造链表实现串的链接存储？,链接串：用链接存储结构来存储串。,（1）非压缩形式,（2）压缩形式,特殊线性表串,串的存储结构,如何改造链表实现串的链接存储？,启示：时空权衡！,模式匹配,模式匹配：给定主串S=s1s2sn和模式T=t1t2tm，在S中寻找T 的过程称为模式匹配。如果匹配成功，返回T 在S中的位置，如果匹配失败，返回0。,假设串采用顺序存储结构，串的长度存放在数组的0号单元，串值从1号单元开始存放。,特殊线性表串,基本思想：从主串S的第

38、一个字符开始和模式T 的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，从主串S的第二个字符开始和模式T 的第一个字符进行比较，重复上述过程，直到T 中的字符全部比较完毕，则说明本趟匹配成功；或S中字符全部比较完，则说明匹配失败。,特殊线性表串,模式匹配BF算法,模式匹配问题的特点： 算法的一次执行时间不容忽视：问题规模通常很大，常常需要在大量信息中进行匹配； 算法改进所取得的积累效益不容忽视：模式匹配操作经常被调用，执行频率高。,si ,主串S,模式T,tj,特殊线性表串,模式匹配BF算法,si ,主串S,模式T,i,特殊线性表串,模式匹配BF算法,si ,主串S,模式T,特殊线

39、性表串,模式匹配BF算法,例：主串S=ababcabcacbab，模式T=abcac,i=3，j=3失败； i回溯到2，j回溯到1,特殊线性表串,模式匹配BF算法,第 1 趟,a b c a c,例：主串S=ababcabcacbab，模式T=abcac,i=3，j=3失败； i回溯到2，j回溯到1,j,特殊线性表串,模式匹配BF算法,i,第 1 趟,a b c a c,例：主串S=ababcabcacbab，模式T=abcac,i=2，j=1失败 i回溯到3，j回溯到1,特殊线性表串,模式匹配BF算法,第 2 趟,a b c a c,例：主串S=ababcabcacbab，模式T=abcac

40、,i=2，j=1失败 i回溯到3，j回溯到1,特殊线性表串,模式匹配BF算法,第 2 趟,i,j,a b c a c,例：主串S=ababcabcacbab，模式T=abcac,a b c a c,i=7，j=5失败 i回溯到4，j回溯到1,特殊线性表串,模式匹配BF算法,第 3 趟,例：主串S=ababcabcacbab，模式T=abcac,a b c a c,i=7，j=5失败 i回溯到4，j回溯到1,特殊线性表串,模式匹配BF算法,第 3 趟,i,j,例：主串S=ababcabcacbab，模式T=abcac,a b c a c,i=4，j=1失败 i回溯到5，j回溯到1,特殊线性表串,

41、模式匹配BF算法,第 4 趟,例：主串S=ababcabcacbab，模式T=abcac,a b c a c,i=4，j=1失败 i回溯到5，j回溯到1,特殊线性表串,模式匹配BF算法,第 4 趟,i,j,例：主串S=ababcabcacbab，模式T=abcac,a b c a c,i=5，j=1失败 i回溯到6，j回溯到1,特殊线性表串,模式匹配BF算法,第 5 趟,例：主串S=ababcabcacbab，模式T=abcac,a b a b c a b c a c b a b,a b c a c,i=5，j=1失败 i回溯到6，j回溯到1,特殊线性表串,模式匹配BF算法,第 5 趟,i,j

42、,例：主串S=ababcabcacbab，模式T=abcac,a b a b c a b c a c b a b,a b c a c,i=11，j=6，T中全部字符都比较完毕，匹配成功。,特殊线性表串,模式匹配BF算法,第 6 趟,1. 在串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=

43、1; j=1; while (iT0) return (i-j+1); else return 0; ,特殊线性表串,模式匹配BF算法,特殊线性表串,模式匹配BF算法,设串S长度为n，串T长度为m，在匹配成功的情况下，考虑两种极端情况：, 最好：不成功的匹配都发生在串T的第一个字符。,例如：S=aaaaaaaaaabcdccccc T=bcd ,特殊线性表串,模式匹配BF算法,设串S长度为n，串T长度为m，在匹配成功的情况下，考虑两种极端情况：,最好情况：不成功的匹配都发生在串T的第1个字符。,设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了i-1次，第i趟成功的匹配共比较了m次，所

44、以总共比较了i-1+m次，所有匹配成功的可能情况共有n-m+1种，则：,特殊线性表串,模式匹配BF算法,设串S长度为n，串T长度为m，在匹配成功的情况下，考虑两种极端情况：,最坏情况：不成功的匹配都发生在串T的最后一个字符。,例如：S=aaaaaaaaaaabccccc T=aaab,特殊线性表串,模式匹配BF算法,设串S长度为n，串T长度为m，在匹配成功的情况下，考虑两种极端情况：,最坏情况：不成功的匹配都发生在串T的最后一个字符。,设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了(i-1)m次，第i趟成功的匹配共比较了m次，所以总共比较了im次，因此,特殊线性表串,模式匹配KMP

45、算法,为什么BF算法时间性能低？,在每趟匹配不成功时存在大量回溯，没有利用已经部分匹配的结果。,如何在匹配不成功时主串不回溯？,主串不回溯，模式就需要向右滑动一段距离。,如何确定模式的滑动距离？,i=3，j=3失败； s2=t2;t1t2 t1s2,特殊线性表串,模式匹配KMP算法,第 1 趟,a b c a c,i=3，j=3失败； s2=t2;t1t2 t1s2,特殊线性表串,模式匹配KMP算法,i,j,第 1 趟,a b c a c,a b c a c,第 3 趟,特殊线性表串,模式匹配KMP算法,a b c a c,第 3 趟,i=7，j=5失败s4=t2;t1t2 t1s4,特殊线性

46、表串,模式匹配KMP算法,a b c a c,第 3 趟,i=7，j=5失败s5=t3;t1t3 t1s5,特殊线性表串,模式匹配KMP算法,a b c a c,第 3 趟,i=7，j=5失败s5=t3;t1t3 t1s5,匹配成功,需要讨论两个问题： 如何由当前部分匹配结果确定模式向右滑动的新比较起点k？ 模式应该向右滑多远才是最高效率的?,结论： i可以不回溯，模式向右滑动到的新比较起点k ，并且k 仅与模式串T有关！,特殊线性表串,模式匹配KMP算法,请抓住部分匹配时的两个特征：,（1）设模式滑动到第k个字符，则T1Tk-1 Si-(k-1) Si-1,特殊线性表串,模式匹配KMP算法,请抓住部分匹配时的两个特征：,两式联立可得：T1Tk-1Tj-(k-1) Tj-1,（2）则Tj-(k