工学第三章串.pptx

第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表栈、队列和串栈、队列和串栈、队列和串栈、队列和串本章的基本内容是：本章的基本内容是：栈和队列的定义及操作特性；栈和队列的定义及操作特性；栈和队列的两种存储方法和基本运栈和队列的两种存储方法和基本运算的实现；算的实现；串的基本概念和操作；串的基本概念和操作；串的常用存储方法；串的常用存储方法；串的模式匹配算法。串的模式匹配算法。第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串3.3.1 串的逻辑结构串的逻辑结构1.串的定义串的定义串是零个或多个字符组成的有限序列串是零个或多个字符组成的有限序列。空格串空格串：只包含空格的串。：只包含空格的串。串的长度串的长度：串中所包含的字符个数。：串中所包含的字符个数。空串空串：长度为：长度为0的串。的串。空串记作空串记作“”；非空串通常记作非空串通常记作：S=“s1 s2 sn”其其中中：S是是串串名名；双双引引号号是是定定界界符符；双双引引号号引引起起来来的部分是串的部分是串值值。si（1in）是一个任意字符是一个任意字符。第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串子串：子串：串中任意个连续的字符组成的子序列。串中任意个连续的字符组成的子序列。主串：包主串：包含子串的串含子串的串。子串在主串中的位置：子串的第一个字符在主串子串在主串中的位置：子串的第一个字符在主串中的序号中的序号。S1=ab12cd S2=“ab12 S3=S4=“”串的长度？串的长度？第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串理解串的定义有以下要点：理解串的定义有以下要点：(1)s(1)si i(1in)(1in)是一个抽象符号，代表任意字符。是一个抽象符号，代表任意字符。(2)s(2)si i在串中出现的序号在串中出现的序号i i称为该字符在串中的位置称为该字符在串中的位置(3)(3)有限性：组成串的字符个数是有限的。有限性：组成串的字符个数是有限的。(4)(4)顺序性：相邻字符之间具有前驱后继关系。顺序性：相邻字符之间具有前驱后继关系。(5)(5)元元素素的的特特殊殊性性：数数据据元元素素是是字字符符。注注意意不不是是符符号，串的数据元素均取自某个字符集。号，串的数据元素均取自某个字符集。第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串串的数据对象约束为某个字符集。串的数据对象约束为某个字符集。微机上常用的字符集是标准微机上常用的字符集是标准ASCII码，由码，由 7 位二进制数表位二进制数表示一个字符，总共可以表示示一个字符，总共可以表示 128 个字符。扩展个字符。扩展ASCII码由码由 8 位二进制数表示一个字符，总共可以表示位二进制数表示一个字符，总共可以表示 256 个字符，个字符，足够表示英语和一些特殊符号，但无法满足国际需要。足够表示英语和一些特殊符号，但无法满足国际需要。Unicode由由 16 位二进制数表示一个字符，总共可以表示位二进制数表示一个字符，总共可以表示 216个字符，即个字符，即6万万5千多个字符，能够表示世界上所有语千多个字符，能够表示世界上所有语言的所有字符，包括亚洲国家的表意字符。为了保持兼言的所有字符，包括亚洲国家的表意字符。为了保持兼容性，容性，Unicode字符集中的前字符集中的前256个字符与扩展个字符与扩展ASCII码完码完全相同。全相同。第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串2.串的比较串的比较 串的比较是通过组成串的串的比较是通过组成串的字符字符之间的比较来进行的。之间的比较来进行的。给定两个串：给定两个串：X=x1x2xn Y=y1y2ym则当则当n=m且且x1=y1，xn=ym时，称时，称X=Y；当下列条件之一成立时，称当下列条件之一成立时，称XY：nm，且且xi=yi（i=1，2，n）；）；存存在在某某个个kmin(m，n)，使使得得xi=yi（i=1，2，k-1），），xkyk。在在计计算算机机中中，字字符符编编码码通通常常用用ASCII码码，字字符符的的比比较较就就是是ASCII码之间的比较。码之间的比较。3.串的抽象数据类型定义串的抽象数据类型定义串的基本操作通常以串的基本操作通常以“串的整体串的整体”作为操作对象。作为操作对象。第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串 StrLength(s)：求串求串s的长度。的长度。StrAssign(s1，s2)：串串赋赋值值，将将s2的的串串值值赋赋值值给给串串s1。StrConcat(s1，s2，s)：串串的的连连接接，将将串串s2放放在在串串s1的后面连接成一个新串的后面连接成一个新串s。SubStr(s，i，len)：求求子子串串，返返回回从从串串s的的第第i个个字符开始取长为字符开始取长为 len 的子串。的子串。第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串 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(s，t，r)：串串替替换换，在在串串s中中用用串串r替替换换所所有与串有与串t相等的子串。相等的子串。第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串SubStr(s，i，len)求子串求子串算法示例算法示例i n f i n i t yi=3,len=3f i ni n f i n i t yi=6,len=4i t y超出超出从串从串s中第中第i 个字符起连续取个字符起连续取 长为长为len 个字符个字符,形成子形成子串并返回。串并返回。第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串3.3.2 串的存储结构串的存储结构 1.串的顺序存储结构串的顺序存储结构定义定义：串的顺序存储结构是用数组来存储串中的串的顺序存储结构是用数组来存储串中的字符序列。字符序列。在在串串的的顺顺序序存存储储中中，如如何何标标识识一一个个串串的的实实际际长度？长度？用数组来存放串，其存储结构与顺序表相同，但串的操作是用数组来存放串，其存储结构与顺序表相同，但串的操作是把串作为一个整体，从而有其与顺序表不同的操作特性。把串作为一个整体，从而有其与顺序表不同的操作特性。0 1 2 3 4 5 6 7 8 MaxSize-1a b c d e f g h i 空空 闲闲 9串的顺序存储方式串的顺序存储方式1第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串用一个变量来表示串的实际长度用一个变量来表示串的实际长度 方案一在在串串尾尾存存储储一一个个不不会会在在串串中中出出现现的的特特殊殊字符作为串的终结符，字符作为串的终结符，表示串的结尾。表示串的结尾。方案二用用数数组组的的0号号单单元元存存放放串串的的长长度度，串串值值从从1号单元开始存放。号单元开始存放。方案三0 1 2 3 4 5 6 7 8 9 MaxSize-1a b c d e f g h i 0 空空 闲闲串的顺序存储方式串的顺序存储方式20 1 2 3 4 5 6 7 8 9 MaxSize-19 a b c d e f g h i 空空 闲闲串的顺序存储方式串的顺序存储方式3第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串2.串的链接存储结构串的链接存储结构（1 1）非压缩形式。）非压缩形式。（2）压缩形式。）压缩形式。一个结点只存储一个字符。一个结点只存储一个字符。令一个结点存储多个令一个结点存储多个字符。字符。优缺点？优缺点？非压缩形式：操作方便，但存储率低；非压缩形式：操作方便，但存储率低；压压缩缩形形式式：存存储储率率高高，但但操操作作复复杂杂。因因为为它它是是一一种种顺顺序序和和链链接接相相结结合合的的结结构构，实实质质上上是是将将字字符符序序列列分分成成若若干干等等长长的的组组，每每个个组组占占用用一一个个结结点点，当当要要改改变变串串长长的的时时候候，可能涉及到结点的增加和删除问题。可能涉及到结点的增加和删除问题。a b c d e f ga eb fc gd第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串3.3.3 3.3.3 模式匹配模式匹配 定义：给定两个串定义：给定两个串S=“s1s2sn”和和T=“t1t2tm”，在主在主串串S中寻找子串中寻找子串T的过程称的过程称为为模式匹配模式匹配。T称为模式称为模式。如果匹配成功，返回如果匹配成功，返回T在在S中的位置，如果匹配失败，中的位置，如果匹配失败，返回返回0。假设串采用顺序存储结构，串的长度存放在数组的假设串采用顺序存储结构，串的长度存放在数组的0号单元，串值从号单元，串值从1号单元开始存放。下面我们介绍号单元开始存放。下面我们介绍两种串的模式匹配算法。两种串的模式匹配算法。第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串朴素的模式匹配算法朴素的模式匹配算法 该算法简称该算法简称BF算法。算法。基本思想基本思想是：从主串是：从主串S的第一个字符开始和模式的第一个字符开始和模式T的第一个的第一个字符进行比较，若相等，则继续比较两者的后续字符；否字符进行比较，若相等，则继续比较两者的后续字符；否则，从主串则，从主串S的第二个字符开始和模式的第二个字符开始和模式T的第一个字符进行的第一个字符进行比较，重复上述过程，若比较，重复上述过程，若T中的字符全部比较完毕，则说明中的字符全部比较完毕，则说明本趟匹配成功；否则匹配失败。本趟匹配成功；否则匹配失败。模式匹配问题的特点：模式匹配问题的特点：算法的一次执行时间不容忽视：问题规模通常很算法的一次执行时间不容忽视：问题规模通常很大，常常需要在大量信息中进行匹配；大，常常需要在大量信息中进行匹配；算法改进所取得的积累效益不容忽视：模式匹配算法改进所取得的积累效益不容忽视：模式匹配操作经常被调用，执行频率高。操作经常被调用，执行频率高。si si tj模式模式T主串主串Sij 回溯回溯i 回溯回溯jBF算法的基本思想图解算法的基本思想图解本趟匹配开始位置本趟匹配开始位置第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串 si 主串主串S模式模式Tji tjBF算法的基本思想图解算法的基本思想图解第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串 si 主串主串Si tj模式模式Tj tjBF算法的基本思想图解算法的基本思想图解第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串1.在串在串S和串和串T中设比较的起始下标中设比较的起始下标i和和j；2.循循环环直直到到S中中所所剩剩字字符符个个数数小小于于T的的长长度度或或T的的所所有字符均比较完有字符均比较完 2.1 如如果果Si=Tj，继继续续比比较较S和和T的的下下一一个个字字符符；否则否则 2.2 将将i和和j回溯，准备下一趟比较；回溯，准备下一趟比较；3.如如果果T中中所所有有字字符符均均比比较较完完，则则匹匹配配成成功功，返返回回匹匹配配的的起起始始比比较较下下标标；否否则则，匹匹配配失失败败，返返回回0；BF算法用伪代码算法用伪代码:第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串int BF(char S,char T)i=1;j=1;/设置比较的起始下标设置比较的起始下标 while(i=S0)&(jT0)return(i-j+1);/返回本趟匹配返回本趟匹配 else return 0;/的起始下标的起始下标 /S0、T0分别存放串分别存放串S和串和串T的长度的长度BF C+算算法法int BF(char S,char T)i=1;j=1;start=1;while(i=S0&jT0)return start;else return 0;第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串设设主主串串s=“ababcabcacbab”，模模式式t=“abcac”，BF算算法的匹配过程如图法的匹配过程如图：a b a b c a b c a c b a ba b c 结结论论：i=3，j=3失失败败；i回溯到回溯到2，j回溯到回溯到1第第1趟趟ijijijij第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串a b a b c a b c a c b a baijij第第2趟趟i=2，j=1失败失败i回溯到回溯到3，j回溯到回溯到1第第3趟趟a b a b c a b c a c b a ba b c a ci=7，j=5失败失败i回溯到回溯到4，j回溯到回溯到1ijijijijijji第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串第第4趟趟a b a b c a b c a c b a baiji=4，j=1失败失败i回溯到回溯到5，j回溯到回溯到1ji第第5趟趟a b a b c a b c a c b a bijajii=5，j=1失败失败i回溯到回溯到6，j回溯到回溯到1 第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串第第6趟趟a b a b c a b c a c b a b a b c a ci=11，j=6，t中中全全部部字字符符都都比比较较完完毕毕，匹匹配成功。配成功。ijijijijij第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串若若n n为主串长度，为主串长度，m m为子串长度，则串的为子串长度，则串的BFBF匹配算法匹配算法最坏的情况下需要比较字符的总次数为最坏的情况下需要比较字符的总次数为(n-m+1)*mO(n*m)BF算法的时间复杂度算法的时间复杂度最好的情况是：最好的情况是：一配就中！只比较了一配就中！只比较了m m次，即次，即O(n+m)O(n+m)。不成功的匹配都发生在串不成功的匹配都发生在串T的第一个字符。的第一个字符。最坏的情况是：最坏的情况是：主串前面主串前面n-mn-m个位置都个位置都部分匹配部分匹配到子到子串的最后一位，即这串的最后一位，即这n-mn-m位比较了位比较了m m次，别忘了最后次，别忘了最后m m位也各比较了一次，还要加上位也各比较了一次，还要加上m m！所以总次数为：所以总次数为：(n n-m-m)*)*m m+m m(n n-m m+1 1)*)*m m 不成功的匹配都发生在串不成功的匹配都发生在串T的的最后一个字符。最后一个字符。第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串能否加快模式串的滑动速度？能否加快模式串的滑动速度？能！利用已部分匹配过的信息使主串能！利用已部分匹配过的信息使主串S S的指针的指针i i不不必回溯，最坏情况也能达到必回溯，最坏情况也能达到O(n+m)O(n+m)为什么为什么BF算法时间性能低？算法时间性能低？在每趟匹配不成功时存在大量在每趟匹配不成功时存在大量回溯回溯，没有利用已经，没有利用已经部分匹配的结果。部分匹配的结果。如何在匹配不成功时主串不回溯？如何在匹配不成功时主串不回溯？主串不回溯，模式就需要向右滑动一段距离。主串不回溯，模式就需要向右滑动一段距离。如何确定模式的滑动距离？如何确定模式的滑动距离？第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串2KMP算法算法 KMPKMP算法设计思想算法设计思想 KMPKMP算法的推导过程算法的推导过程 KMPKMP算法的实现算法的实现 （关键技术关键技术:计算计算nextjnextj）KMP KMP算法的时间复杂度算法的时间复杂度第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串 KMPKMP算法设计思想：算法设计思想：尽量利用已经尽量利用已经部分匹配部分匹配的结果信息，尽量让的结果信息，尽量让i i不要回溯，加快不要回溯，加快模式串的滑动速度。模式串的滑动速度。例：例：S=a b a b c a b c a c b a bT=T=a b c a cS=a b a b c a b c a c b a bT=T=a b c a cS=a b a b c a b c a c b a bT=T=a b c a cKMPKMP最终的返回值应为最终的返回值应为i=6i=6需要讨论两个问题：需要讨论两个问题：如何由如何由当前部分匹配结果当前部分匹配结果确定模式向右滑动的新比较起点确定模式向右滑动的新比较起点k k？模式应该向右滑多远才是高效率的模式应该向右滑多远才是高效率的?i ii ii ik kk k a b aa b ck ki ii i奇妙的结果：奇妙的结果：奇妙的结果：奇妙的结果：k k 仅与模式串仅与模式串仅与模式串仅与模式串T T有关有关有关有关！KMP算法的推导过程：算法的推导过程：请抓住部分匹配时的两个特征：请抓住部分匹配时的两个特征：两式联立可得：两式联立可得：T T1 1TTk-1k-1=T=Tj-(k-1)j-(k-1)T Tj-1j-1 S=a b a b c a b c a c b a bT=T=a b c a ci ik k则则T T的的k-1k-11 1位位S S前前i-1i-1i-1i-1i-(k-1)i-(k-1)i-(k-1)i-(k-1)位位 设目前打算与设目前打算与T的第的第k字符开始比较字符开始比较(1)(1)(2)(2)T T1 1TTk-1k-1 则则T T的的j-1j-1j-(k-1)j-(k-1)位位 S S前前i-1i-1i-1i-1i-(k-1)i-(k-1)i-(k-1)i-(k-1)位位i ik kj jS=a b a b c a b c a c b a bT=T=a b c a c T Tj-(k-1)j-(k-1)j-(k-1)j-(k-1)T Tj-1j-1 截取一段，但截取一段，但截取一段，但截取一段，但k k有限制，有限制，有限制，有限制，11kjkjk k是追求的新起点是追求的新起点是追求的新起点是追求的新起点加速的前提：加速的前提：T T首与首与T Tj-1j-1处有相同子串处有相同子串注意：注意：j 为当前已知的失配位置，我们的目标是计算新起点为当前已知的失配位置，我们的目标是计算新起点 k。式中仅剩一个未知数式中仅剩一个未知数k，理论上已可解！理论上已可解！根据模式串根据模式串T的规律：的规律：T T1 1TTk k-1 1=T=Tj-(k-1)j-(k-1)j-(k-1)j-(k-1)T Tj-1j-1 由当前失配位置由当前失配位置j(已知已知)，可以，可以归纳归纳出计算新起点出计算新起点 k的表达式。的表达式。next j 0 当当j1时时 /不比较不比较max k|1kj 且且T1Tk-1=Tj-(k-1)j-(k-1)Tj-1 1 其他情况其他情况讨论：讨论：讨论：讨论：（1）next j 的物理意义是什么？的物理意义是什么？（2）next j 具体怎么求？具体怎么求？即即KMP算法的实现算法的实现令令k=next j（k 与与j 显然具有函数关系），则显然具有函数关系），则取取T T首与首与T Tj-1j-1处最大的相同子串处最大的相同子串新起点新起点 k k怎么求？怎么求？（1）next j 有何物理意义？有何物理意义？nextjnextjnextjnextj函数表征着模式函数表征着模式函数表征着模式函数表征着模式T T T T中最大相同首子串和尾子串（真中最大相同首子串和尾子串（真中最大相同首子串和尾子串（真中最大相同首子串和尾子串（真子串）的长度。子串）的长度。子串）的长度。子串）的长度。可见，模式中可见，模式中相似部分越多，则相似部分越多，则nextjnextj函数越大函数越大，它既，它既表示表示模式模式T字符之间的相关度越高，也表示字符之间的相关度越高，也表示j j位置以前与主串位置以前与主串部部分匹配分匹配的字符数越多。的字符数越多。即：即：nextjnextj越大，模式串向右滑动得越远越大，模式串向右滑动得越远，与主串进行，与主串进行比较的次数越少，时间复杂度就越低（时间效率）。比较的次数越少，时间复杂度就越低（时间效率）。next j max k|1k1j1时，时，NextjNextj的值为：模式串的位置的值为：模式串的位置从从1 1到到j-1j-1构成的串中所出现的构成的串中所出现的首尾相同的子串首尾相同的子串的最大长度的最大长度加加1 1。无首尾相同的子串时无首尾相同的子串时NextjNextj的值为的值为1 1。/Nextj=1Nextj=1表示从模式串头部开始进行字符比较表示从模式串头部开始进行字符比较（2）next j 怎么计算？怎么计算？怎样计算模式怎样计算模式怎样计算模式怎样计算模式T T所有可能的失配点所有可能的失配点所有可能的失配点所有可能的失配点 j j 所对应的所对应的所对应的所对应的 nextj？从两头往中间比较从两头往中间比较 模模 式式 串串 T：a b a a b c a c 可能失配位可能失配位 j：1 2 3 4 5 6 7 8新匹配位新匹配位k=nextj:next j 0 当当j1时时max k|1kj 且且T1Tk-1=Tj-(k-1)j-(k-1)Tj-1 1 其他情况其他情况0 12 2 3 1 2讨论：讨论：j=1时时,next j 0；/属于属于“j=1”情况情况;j=2时时,next j 1；/找不到找不到1kj的的k，属于属于“其他情况其他情况”；刚才已归纳：刚才已归纳：j=3时时,k=2，只需查看只需查看T1=T2 2成立否，成立否，No则属于其他情则属于其他情况况 j=4时时,k=2，3，要查看要查看T T1 1=T T3 3 及及T T1 1T T2 2=T T2 2 T T3 3 是否成立是否成立j=5时时,k=2，3，4，要查看要查看T1=T4 4，T1T2=T3 3T4 和和 T1T2T3 3=T2 2T3 3T4是否成立是否成立以此类推，可得后续以此类推，可得后续nextj值。值。nextjnextj与与s s无关，无关，可以预先计算可以预先计算例：例：1第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串1.在串在串S和串和串T中分别设比较的起始下标中分别设比较的起始下标i和和j；2.循环直到循环直到S中所剩字符长度小于中所剩字符长度小于T的长度或的长度或T中所有中所有字符均比较完毕字符均比较完毕 2.1 如如果果Si=Tj，继继续续比比较较S和和T的的下下一一个个字字符符；否则否则 2.2 将将j向右滑动到向右滑动到nextj位置，即位置，即j=nextj；2.3 如果如果j=0，则将则将i和和j分别加分别加1，准备下一趟比较；，准备下一趟比较；3.如果如果T中所有字符均比较完毕，则返回匹配的起始中所有字符均比较完毕，则返回匹配的起始下标；否则返回下标；否则返回0；KMP算法用伪代码描述算法用伪代码描述 void GetNext(char T,int next)next1=0;j=1;k=0;while(jT0)if(k=0)|(Tj=Tk)j+;k+;nextj=k;else k=nextk;第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串求模式串求模式串T的的next函数值算法函数值算法第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串求求nextnext数组的算法只需将模式扫描一遍，数组的算法只需将模式扫描一遍，设模式串的长度为设模式串的长度为m m，则算法的时间复杂，则算法的时间复杂度为度为O(m)O(m)。而。而KMPKMP算法的时间复杂度为算法的时间复杂度为O(n+m)O(n+m)。KMPKMP算法与算法与BFBF算法相比，增加了算法相比，增加了很大的难度，我们主要学习该算法的设很大的难度，我们主要学习该算法的设计技巧。计技巧。第第3章章 特殊线性表特殊线性表串串a b a b c a b c a c b a ba b c ijijij第一趟，第一趟，i=3，j=3失败，失败，i不动不动next3=1，j滑动到滑动到1的位置的位置第第3章章 特殊线性表特殊线性表串串a b a b c a b c a c b a ba b c a cijijijijij第二趟第二趟i=7，j=5失败，失败，i不动不动 next5=2，j滑动到滑动到2的位置的位置第第3章章 特殊线性表特殊线性表串串a b a b c a b c a c b a b a b c a cijijijijij第三趟，第三趟，i=11，j=6，T中全部字符都比较完毕，匹配成功中全部字符都比较完毕，匹配成功第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表特殊线性表特殊线性表 栈栈队队 列列 串串栈的定义栈的定义操作特性操作特性ADT定义定义队列定义队列定义操作特性操作特性ADT定义定义串的定义串的定义基本概念基本概念ADT定义定义顺顺序序栈栈链链栈栈循循环环队队列列链链队队列列顺顺序序存存储储链链接接存存储储逻辑结构逻辑结构存储结构存储结构逻辑结构逻辑结构逻辑结构逻辑结构存储结构存储结构存储结构存储结构比比 较较模式匹配模式匹配比较比较比较比较基本操作的实现基本操作的实现时间性能时间性能基本操作的实现基本操作的实现时间性能时间性能第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表1938年出生，年出生，25岁毕业于加州理工学院岁毕业于加州理工学院数学系，博士，留校任教，数学系，博士，留校任教，28岁时任副岁时任副教授。教授。30岁时，加盟斯坦福大学计算机岁时，加盟斯坦福大学计算机系，任正教授。从系，任正教授。从31岁起，开始出版他岁起，开始出版他的历史性经典巨著：的历史性经典巨著：The Art of Computer Programming。他计划共写他计划共写7卷，然而出版三卷之后，已震惊世界，卷，然而出版三卷之后，已震惊世界，使他获得计算机科学界的最高荣誉使他获得计算机科学界的最高荣誉Turing Award，此时，他年仅此时，他年仅36岁。他岁。他有一个奇妙的承诺：在他定期进行的讲有一个奇妙的承诺：在他定期进行的讲座中，会不断提出一些新的难题。如果座中，会不断提出一些新的难题。如果有人能在给定的期限内解出任何一道难有人能在给定的期限内解出任何一道难题，他将为那个人的博士论文签名题，他将为那个人的博士论文签名(大约大约相当于名誉导师吧相当于名誉导师吧)！不知道世界之大，！不知道世界之大，有没有哪位后起之秀能获得这样的殊誉有没有哪位后起之秀能获得这样的殊誉？