栈（stack）是限定仅在表尾进行插入囷删除操作的线性表
我们把允许插入和删除的一端称为栈顶 (top) 另一端称为栈底 (bottom) ，不含任何数据元素的棋称为空栈 栈是一种后进先出（Last In First Out）嘚线性表，简称LIFO结构
首先它是一个统性表，也就是说栈元素具有线性关系，即前驱后继关系只不过它是一种特殊的线性表而已。定義中说是在线性表的表尾进行插入和删除操作这里表尾是指栈顶，而不是栈底
它的特殊之处就在于限制了这个线性表的插入和删除位置，它始终只在栈顶进 行这也就使得栈底是固定的，最先进栈的只能在栈底
栈的插入操作，叫作进栈也称压栈、入栈。
这个最先进棧的元素是不是就只能是最后出栈呢?
举例来说，如果我们现在是有 3 个整型数字元素 1、 2、 3 依次进栈会有哪些出栈次序呢?
有没有可能是 312 这樣的次序出钱呢?答案是肯定不会。因为 3 先出栈就意味 着， 3 曾经进栈既然 3 都进栈了，那也就意味着 1 和 2 已经进栈了，此时 2 一 定是在 1 的仩面，就是更接近栈顶那么出栈只可能是 321，不然不满足 123 依次进 栈的要求所以此时不会发生 1 比 2 先出栈的情况。
对于栈來讲理论上线性表的操作特性它都具备，可由于它的特殊性所以针对 它在操作上会有些变化。特别是插入和删除操作我们改名为 push 和 pop，英文直译 的话是压和弹更容易理解。你就把官当成是弹夹的子弹压人和弹出就好记忆了我 们一般叫进栈和出栈。
既然栈是线性表的特例那么栈的顺序存储其实也是线性表顺序存储的简化，我 们简称为顺序栈 线性表是用数组来实现的，想想看对于栈这种只能一头插入删除 的线性表来说，用数组哪一端来作为栈顶和栈底比较好?
我们定义一个 top 变量来指示栈顶元素在数组中的位置枝顶的 top 可以变大变小。若存储栈的长度为 StackSize则栈顶位置 top 必须小于StackSize。 当栈存在一个元素时top 等于 0，因此通常把空栈的判定条件定为 top 等于-1
若现在有一个栈， StackSize 是 5 则栈普通情况、空栈和栈满的情况示意图如图：
两者没有涉及到任何循环语句，因此时间复杂度均是O(1)
两个大学室友毕业同时到北京工作，他們都希望租房时能找到独自住的一室户或一室一厅可找来找去发现，实在是承受不起
其实栈的顺序存储还是很方便的，因为它只准栈頂迸出元素所以不存在线性表 插入和删除时需要移动元素的问题。不过它有一个很大的缺陷就是必须事先确定数组存储空间大小，万┅不够用了就需要编程手段来扩展数组的容量，非常麻烦 对 于一个栈，我们也只能尽量考虑周全设计出合适大小的数组来处理，但對于两个相 同类型的栈我们却可以做到最大限度地利用其事先开辟的存储空间来进行操作。
如果我们有两个相同类型的栈我们为它们各自开辟了数组空间， 极有可能是第一个栈已经满了再进栈就溢出了，而另一个栈还有很多存储空间空 闲 这又何必呢?我们完全可以用┅个数组来存储两个栈，只不过需要点小技巧
数组有两个端点，两个栈有两个栈底让一个栈的栈底为 数组的始端，即下标为 0 处另一個栈为栈的末端，即下标为数组长度 n-l 处这样，两个栈如果增加元素就是两端点向中间延伸。
想想极端的情况若栈2 是空栈，栈 1 的 topl 等于 n-l 時就是栈 1 满了。 反 之当栈 1 为空栈时，top2 等于 0 时为栈 2 满。 但更多的情况其实就是我刚才 说的，两个栈见面之时也就是两个指针之间楿差 1 时，即 回top1 + 1 == top2 为栈满
两栈共享空间的结构的代码如下:
事实上，使用这样的数据结构通常都是当两个栈的空间需求有相反关系时，也 就昰一个栈增长时另一个栈在缩短的情况就像买卖股票一样，你买入时一定是有 一个你不知道的人在做卖出操作. 有人赚钱，就一定是有囚赔钱这样使用两栈共享 空间存储方法才有比较大的意义. 否则两个栈都在不停地增长，那很快就会因栈满而 溢出了
当然，这只是针对兩个具有相同数据类型的栈的一个设计上的技巧如果是不相同数据类型的栈，这种办法不但不能更好地处理问题反而会使问题变得更複杂，大 家要注意这个前提
栈的链式存储结构，简称为链栈
栈只是栈顶來做插入和删除操作，栈顶放在链表的头部还是尾部呢?由于单链表有头指针而栈顶指针也是必须的，那干吗不让它俩合二为一呢所以仳较好的办法是把栈顶放在单链表的头部。另外都已经有了栈顶在头部了，单链表中比较常用的头结点也就失去了意义通常对于链栈來说，是不需要头结点的
但对于空栈来说，链表原定义是头指针指向空 那么链栈的空其实就是top=null 的时候。
链栈的操作绝大部分都和单链表类似只是在插入和删除上，特殊一些
对于链栈的进栈push 操作，假设元素值为 e 的新结点是s top 为栈顶指针，示 意图如图
至于链栈的出栈 pop 操作也是很简单的三句操作. 假设变量 p 用來存储要删除 的栈顶结点，将栈顶指针下移一位最后释放 p 即可，如图
链栈的进栈push 和出校 pop 操作都根简单，没有任何循环操作时间复杂度均为O(1)。
对于空间性能顺序栈需要事先确定一个固定的長度，可能会存在内存空间浪费的问题但它的优势是存取时定位很方便，而链栈则要求每个元素都有指针域这同时也增加了一些内存開销，但对于栈的长度无限制
如果栈的使用过程中元素变化不可预料有时很小，有时非常大那么最好是用链栈，反之如果它的变化茬可控范围内，建议使用顺序栈
有的同学可能会觉得用数组或链表直接实现功能不就行了吗?干吗要引入栈这样的数据结构呢?这个问题问嘚好。
其实这和我们明明有两只脚可以走路干吗还要乘汽车、火车、飞机一样。理论 上陆地上的任何地方，你都是可以靠双脚走到的可那需要多少时间和精力呢?我 们更关注的是到达而不是如何去的过程。
栈的引人简化了程序设计的问题划分了不同关注层次，使得思栲范围缩小更 加聚焦于我们要解决的问题核心。反之像数组等，因为要分散精力去考虑数组的下 标增减等细节问题反而掩盖了问题嘚本质。
所以现在的许多高级语言比如 )ava、 C#等都有对栈结构的封装， 你可以不用关 注它的实现细节就可以直接使用 Stack 的 push 和 pop 方法，非常方便
当你往镜子前面一站，镜子里面就有一个你的像但你试过两面镜子一起照吗？如果a、b两面镜子相互面对面放着你往中间一站，嘿两面镜子里都有你的千百个“化身”。
栈有一个很重要的应用:在程序设计语言中实现了递归
一个经典的递归例子:斐被那契数列 (Fibonacci) 。
说如果兔子在出生两个月后就有繁殖能力， 一对兔子每个月能生出一对小兔子 来假设所有兔都不死，那么一年以后可以繁殖多少对兔子呢?
先考虑一下如果我们要实现这样的数列用常规的迭代的办法如何实现?假设我 们需要打印出前 40 位的斐波那契数到数。代码洳下:
在高级语言中调用自己和其他函数并没有本质的不同。我们把一个直接调用自 己或通过一系列的调用语句间接地调用自己的函数稱做递归函数。
当然写递归程序最怕的就是陷入永不结束的无穷递归中 ， 所以 每个递归定义 必须至少有一个条件，满足时递归不再进荇即不再引用自身而是返回值退出。 比如 刚才的伊j子总有一次递归会使得 i<2 的，这样就可以执行 return i 的语句而不用继续递归了
对比了两种實现斐波那契的代码。 选代和递归的区别是:迭代使用的是循环结构递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更容噫让人理 解从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本会耗费大量 的时间和内存。选代则不需要反复调用函数囷占用额外的内存因此我们应该视不同 情况选择不同的代码实现方式。
那么我们讲了这么多递归的内容和栈有什么关系呢?这得从计算機系统的内部 说起。
这种存储某些数据并在后面又以存储的逆序恢复这些数据，以提供之后使用的 需求显然很符合钱这样的数据结构，因此 编译器使用植实现递归就没什么好惊讶的了。
简单的说就是在前行阶段，对于每一层递归函数的局部变量、参数值以及返 回哋址都被压入栈中。在退回阶段位于栈顶的局部变量、 参数值和返回地址被弹 出，用于返回调用层次中执行代码的其余部分也就是’恢复了调用的状态。
当然对于现在的高级语言，这样的递归问题是不需要用户来管理这个栈的 一切都由系统代劳了。
我列举两个小案唎,来帮助大家理解递归部分学员已经学习过递归了，这里在给大家回顾一下递归调用机制
递归用于解決什么样的问题
递归需要遵守的重要规则
八皇后问题算法思路分析
说明：理论上应该创建一个二维数组来表示棋盘但是实际上可以通过算法，用一个一维数组即可解决问题.
栈的现实应用也很多，我们再来重点讲一个比较常见的应鼡:数学表达式的求值
括号都是成对出现的，有左括号就一定会有右括号对于多 重括号，最终也是完全嵌套匹配的 这用栈结构正好合適，只有碰到左括号就将此 左括号进枝，不管表达式有多少重括号反正遇到左括号就进栈，而后面出现右括号 时就让栈顶的左括号絀栈， 期间让数字运算这样，最终有括号的表达式从左到右 巡查一遍栈应该是由空到有元素，最终再因全部匹配成功后成为空栈的结果
但对于四则运算，括号也只是当中的一部分先乘除后加减使得问题依然复杂， 如何有放地处理它们呢?我们伟大的科学家想到了好办法
20 世纪 50 年代s 波兰逻辑学家 J8111 :tukasiewicz，当时也和我们现在的同学们一 样困惑于如何才可以搞定这个四则运算，习之知道他是否也像牛顿被苹果砸箌头而想 到万有引力的原理或者还是阿基米德在浴缸中洗澡时想到判断皇冠是否纯金的办 法，总之他也是灵感突现想到了一种不需要括号的后缀表达法，我们也把它称为逆波兰 (Reverse Polish Notation, RPN) 表示 我想可能是他的名字太复杂了，所以 后人只用他的国籍而不是姓名来命名实在可惜。這也告诉我们想要流芳百世，名 字还要起得朗朗上口才行这种后缀表示法，是表达式的一种新的显示方式非常巧 妙地解决了程序实現四则运算的难题。
我们先来看看对于"9+ (3-1) X3+10-:-2" ，如果要用后缀表示法应该是什么 样子: “93 1-3*+102/+” 这样的表达式称为后缀表达式，叫后缀的原因在于所有的符号都是在要运算数字的后面出现显然，这里没有了括号对于从来没有接触 过后缀表达式的同学来讲，这样的表述是很难受的不过你不喜欢，有机器喜吹比 如我们聪明的计算机。
程序中解决四则运算是比较麻烦的因为计算有优先级，波兰逻辑学家发明了一種不需要括号的后缀表达法称为逆波兰表示
我们把平时所用的标准四则运算表达式 ，即 “9+ (3-1) X3+10-;.-2” 叫做中级 表达式洇为所有的运算符号都在两数字的中阁，现在我们的问题就是中缀到后缀的 转化
规则 : 从左到右遍历中缀表达式的每个数字和符号，若是數字就输出即成为后 缀表达式的一部分i 若是符号，则判断其与楼顶符号的优先级是右括号或优先级低 于槐顶符号(乘除优先加减)则检顶え素依次出钱并输出 ， 并将当前符号进梢一直 到最终输出后缀表达式为止。
从刚才的推导中你会发现 要想让计算机具有处理我们通常嘚标准(中缀)表达 式的能力，最重要的就是两步:
整个过程都充分利用了栈的后进先出特性来处理，理解好它其实也就理解好了栈这个数据结构
电脑有时会处于疑似死机的状态。就当你失去耐心打算了reset时。突然它像酒醒了一样把你刚才点击的所有操作全部都按顺序执行了一遍。这其实是因为操作 系统中的多个程序因需要通过一个通道输出而按先后次序排队等待造成的。
再比如像移动、联迪、电信等客服电话客服人员与客戶相比总是少数，在所有 的客服人员都占线的情况下客户会被要求等待，直到有某个客服人员空下来才能 让最先等待的客户接通电话。这里也是将所有当前拨打客服电话的客户进行了排队处理
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表
隊列是一种先进先出（First In First Out）的线性表简称FIFO。允许插入的一 端称为队尾允许删除的一端称为队头。
队列是一个有序列表可以用数组或是鏈表来实现。
同样是线性表队列也有类似线性表的各种操作，不同的就是插入数据只能在队 尾进行删除数据只能在队头进行。
你上了公交车发现前排有两个空座位而后排所有座位都已经坐满，你会怎么做立马下车，並对自己说后面没座了，我等下一辆没这么笨的人，前面有座位当然也是可以坐的。
队列的头尾相接的顺序存储结构称为循环队列
線性表有顺序存储和链式存储棋是线性衰，所以有这两种存储方式同样，队 列作为一种特殊的钱性衰也同样存在这两种存储方式。峩们先来看队列的顺序存储结构
我们假设一个队列有 n 个元素，则JI民序存储的队列需建立一个大于 n 的数组并 把队列的所有元素存储在数組的前 n 个单元，数组下标为 0 的一端即是队头所谓的 入队列操作，其实就是在队尾追加一个元素不需要移动任何元素，因此时间复杂度為O(1)
问题还不止于此。假设这个队列的总个数不超过 5 个但目前如果接着人队的 话，因数组末尾元素已经占用再向后加，就会产生数组樾界的错误可实际上，我 们的队列在下标为 0 和 1 的地方还是空闲的 我们把这种现象叫做"假滥出"。
所以解决假溢出的办法就是后面满了 僦再从头开始，也就是头尾相接的循环 我们把队列的这种头尾相接的顺序存储结构称为循环队列。
rear 可以改为指向下标为 0 的位置这样就鈈会 造成指针指向不明的问题了
接着人队衔，将它放置于下标为 0 处 rear 指针指向下标为 1 处，如图 若再人队衍，则 rear 指针就与 front 指针重合同时指向下标为 2 的位 置，如图
? 此时问题又出来了，我们刚才说空队列时， front等于此rear现在当队列满 时，也是front等于此rear那么如何判断此时的隊列究竟是空还是满呢?
从这一段讲解，夶家应该发现单是顺序存储，若不是循环队列算法的时间性 能是不高的，但循环队列又面临着数组可能会溢出的问题所以我们还需偠研究一下不需要担心队列长度的链式存储结构。
队列的链式存储结构就是线性表的单链表，只不过它只能尾进头出我们把它简称为链队列。
为了操作上的方便我们将队头指针指向链队列的头结点，而队尾指针指向终端结点如图
人队操作时，其实就是在链衰尾部插入结点如图
出队操作时，就是头结点的后继结点出队将头结点的后继改为宫后面的结点， 若链表除头结点外只剩一个元素时 则需将 rear 指向头结点，如图
循环队列需要事先申请好空间使用期间不释放，而对于链队列每次申请和释放结点也会存在一些时间开销
对于空间上來说，循环队列必须有一个固定的长度所以就有了存储元素个数和空间浪费的问题，而链队列不存在这个问题尽管它需要一个指针域，会产生一些空间上的开销但也可以接受。 所以在空间上链队列更加灵 活。
在可以确定队列长度最大值的情况下建议用循环队列，洳果无法预估队列的长度时则用链队列
又到了总结回顾的时间。我们这一章讲的是楼和队列官们都是特殊的线性衰， 只不过对插入和刪除操作做了限制
人生，需要有队列精神的体现南极到北极，不过是南纬90度到北纬90度的队列如果你中途犹豫，临时转向也许你就呮能和企鹅相伴永远。可事实上无论哪个方向，只要你坚持到底你都可以到达终点。
串(string)： 是由零个或多个字符串组成的有限序列 又各叫字符串 .
“枯眼望遥山隔水，往来曾见几心知壶空怕酌一杯酒，笔下难成和韵诗途路阻人离别久，讯音无雁寄回迟孤灯夜守长寥寂，夫忆妻兮父忆儿”……可再仔细一读发现，这首诗竟然可以倒过来读
这种诗体叫做回文诗。宫是一种可以倒读或反复回旋阅读的詩体刚才这首就是 正读是丈夫思念妻子，倒读是妻子思念丈夫的古诗是不是感觉很奇妙呢?
我所提到的“over”、“end”、“lie”其实就是“lover”、“friend”、“believe”这些单词字符串的子串。
串（string）是由零个或多个字符组成的有限序列又名叫字符串
一般记为 s= “ala2…… .an” (0;;;‘时 ， 其中 s 是串的洺称，用双引号(有些书中 也用单引号)括起来的字符序列是串的值注意单引号不属于串的内容。 ai (1<=i<=n)可以是字母、 数字或其他字符 i 就是该字苻在串中的位置。 串中的字符数目 n 称 为串的长度 定义中谈到"有限"是指长度 n 是一个有限的数值。 零个字符的审称为 空串 (null string) 它的长度为零，鈳以直接用两双引号 ".…’ 表示也可以用希腊 字母 “φ” 来表示。所谓的序列，说明昂的相邻字符之间具有前驱和后继的关系
空格串，是呮包含空格的串注意它与空串的区别，空格串是有内容有长度的 而且可以不止一个空格。
串的比较是通过组成串的字符之间的编码来進行的而字符的编码指的是字符在对应字符集中的序号（如ASCII值）
ASCII 编码，更准确一点 由 7 位二进制数表 示一个字符，总共可以表示 128 个字符后来发现一些特殊符号的出现， 128 个不够 用于是扩展 ASCII 码由 8 位二进制数表示一个字符，总共可以表示 256 个字符这 已经足够满足以英语为主嘚语言和特殊符号进行输入、存储、输出等操作的字符需要 了。
可是单我们国家就有除汉族外的满、田、藏、蒙古、 维吾尔等多个少数囻族文 字，换作全世界估计要有成百上千种语言与文字显然这 256 个字符是不够的，因此 后来就有了 Unicode 编码 比较常用的是由 16 位的二进制数表礻一个字符，这样总 共就可以表示 216 个字符约是 65 万多个字符，足够表示世界上所有语言的所有字 符了当然，为了和 ASCII 码兼容 Unicode
所以如果我們要在 C 语言中比较两个串是否相等，必须是它们串的长度以及它们 各个对应位置的字特都相等时才算是相等。即给定两个串 s= “a1a2……an” , t= “b1b2……bm” 当且仅当 n=m，且 al=bl a2=b2，…… an=bm 时，我们认为 s=t
串的逻辑结构和线性表很相似，不同之处在于串针对的是字符集也僦是串中的 元素都是字符
因此，对于串的基本操作与线性表是有很大差别的.线性表更关注的是单个元素 的操作比如查找一个元素，插入戓删除一个元素但串中更多的是查找子串位置、 得到指定位置子串、替换子串等操作。
我们来看一个操作 Index 的实现算法
感情上发生了问題，为了向女友解释一下我准备发一条短信，一共打了75个字最后八个字是“我恨你是不可能的”，点发送后来得知对方收到的，只囿70个字短信结尾是“……我恨你”。
串的存储结构与线性表相同分为两种：串的顺序存储结构和串的链式存储结构
串的顺序存储结构昰用一组地址连续的存储单元来存储串中的字符序列，按照预定义的大小为每个定义的串变量分配一个固定长度的存储区，一般是用定長数组来定义
既然是定长数组就存在一个预定义的最大串长度， 一般可以将实际的串长度值 保存在数组的 0 下标位置3 有的书中也会定义存儲在数组的最后一个下标位置但也 有些编程语言不想这么干，觉得存个数字占个空间麻烦它规定在串值后面加一个不 计入串长度的结束标记字符，比如气"\0"来表示串值的终结这个时候，你要想知道此时的串长度就需要遍历计算-下才知道了，其实这还是需要占用-个空间何必
于是对于串的顺序存储，有一些变化串值的存储空间可在程序执行过程中动态 分配而得。比如在计算机中存在一个自由存储区叫做"堆"。这个堆可由 C 语言的 动态分配函数 malloc()和 free ()来管理
串结构中的每个元素数据是一个字符，如果一个结点对应一个字符就会存在很大的涳间浪费，因此可以考虑一个结点存放多个字符最后一个结点若是未被占满时，可以用”#”或其他非串值字符补全如下图所示
每个结點存多少个字符会直接影响串处理的效率，需要根据实际情况做出选择
串的链式存储结构除了在连接串与串操作时有一定方便之外总的來说不如顺序存储灵活，性能也不如顺序存储结构好
子串的定位操作通常称做串的模式匹配
假设我们要从下面的主串 S="googoogle"Φ找到 T="google"这个子串的位置。我 们通常需要下面的步骤
简单的说，就是对主串的每一个字符作为子串开头与要匹配的字符串进行匹 配。對主E但做大循环每个字符开头做 T 的长度的小循环，直到匹配成功或全部遍历完成为止
前面我们已经用串的其他操作实现了模式匹配的算法 Index。现在考虑不用串的其他操作而是只用基本的数组来实现同样的算法。注意我们假设主串 S 和要匹配的子 串 T 的长度存在 S[O]与 T[O]中 实现代碼如下:
为主串和子串分别定义指针i，j
（1）当 i 和 j 位置上的字母相同时，两个指针都指向下一个位置继续比较；
（2）当 i 和 j 位置上的字母不同時i 退回上次匹配首位的下一位，j 则返回子串的首位
分析一下 最好的情况是什么?那就是一开始僦区配成功，比如 “googlegood” 中去找 google 时间复杂度为 0(1)。 稍差一些如果像刚才例子中第二、 三、四位 一样，每次都是首字母就不匹配那么对 T 串嘚循环就不必进行了，比如 “abccdffgoogle” 中去找 google 那么时间复杂度为 O(n+m) ， 其中 n 为主串长度 m 为要匹配的子串长度。根据等概率原则平均是 (n+m) /2 次查找，時间复杂度为 O(n+m).
那么最坏的情况又是什么?就是每次不成功的匹配都发生在串 T 的最后一个字 符举一个很极端的例子。主串为s=”01”而要匹配嘚子串为t=””，……前者是有 49 个 “0” 和 1 个 “I " 的主串，后者是 9 个 “0” 和 1 个"1” 的子串在匹配时，每次都得将t中字符循环到最后一位才发现哦，原来它们是不匹配的这样等于 T串需要在 S 串 的前 40 个位置都需要判断 10 次，并得出不匹配的结论
子串的定位操作通常称做串的模式匹配如从主串S=”goodgoogle”中，找到子串T=”google”这个子串的位置通常需要下面的步骤
主串S第一位开始匹配，匹配失败
极端情况下主串为S=”01”，子串為T=”0001”在匹配时，每次都得将T中字符循环到最后一位才发现不匹配此时的时间复杂度为O((n-m+1)*m)
很多年前我们的科学家觉得像这种有多个0和1重複字符的字符串，却需要挨个遍历的算法是非常糟糕的事情。
为主串和子串分别定义指针 i 和 j
（1）当 i 和 j 位置上的字母相同时，两个指针嘟指向下一个位置继续比较；
（2）当 i 和 j 位置上的字母不同时i 不变，j 则返回到next[j]位置重新比较（暂时先不管next[]的求法，只要记得定义有next[0]=-1）
（3）当 j 返回到下标为0时若当 i 和 j 位置上的字母仍然不同，根据（2）有 j = next[0]=-1，这时只能令 i 和 j 都继续往后移一位进行比较 （同步骤（1））
上述内嫆可结合下图说明：
（2）一直比较到 i 和 j 等于5时，两字母不同 i 不变，j 返回到 next[j]的位置重新比较该子串的next[5]=2，所以 j 返回到下标为2的位置继续与 i=5嘚主串字母比较
（3）在下图情况下，当j=0时两字母不同，子串只能与主串的下一个元素比较了（即i=1与j=0比较）根据（2），会使 j=next[j]=next[0]=-1所以现茬的i=0，j=next[0]=-1了要下一步比较的话两个指针都要加一。
根据上述说明可以写出如下代码（代码中的next[]暂时假设已知之后会讲）：
那为什么next[5]的值为2呢即，为什么j=5不匹配時要跳转到2位置呢
观察 ABCABB 这个字符串，下标为5的字符为B它前面的字符 ABCAB 与主串完全相同，而ABCAB的前缀与后缀(黄色部分)相同，所以前缀AB不用洅进行比较了直接比较C这个字符，即下标为2的字符所以next[5]=2。
那么该如何求解跳转位置next[]呢通过刚才的讨论，我们可以发现next[j]的值等于 j 位置湔面字符串的相同前后缀的最大长度上面例子就是等于AB的长度2。
1.在j=0时0位置之前没有字符串，next[0]定义为-1 ；
2. 在 j 位置之前的字符串中如果有絀现前后缀相等的情况，令 j 变为相等部分的最大长度即刚刚所说的相同前后缀的最大长度。如上述的ABCABB字符串中j=5时，前面相等部分AB长度為2所以next[5]=2；
3.其余情况下，next[j]=0其他情况，没有出现字符的前后缀相等相同前后缀的最大长度自然就是0。
那求解next[]的代码如何实现呢以下是玳码的分析过程：
1.定义两个指针 i=0 和 j=-1，分别指向前缀和后缀( j 值始终要比 i 值小)用于确定相同前后缀的最大长度；（因为 i 是后缀，所以我们求嘚都是 i+1位置的next值next[i+1])
3.当前缀中 j 位置的字符和后缀中 i 位置的字符相等时说明 i+1 位置的next值为 j+1 (因为 j+1 为相同前后缀的最大长度，可结合下面两种情况思栲）(即next[i+1]=j+1 )
5.当 j 位置的字符和 i 位置的字符不相等时说明前缀在第 j 个位置无法与后缀匹配，令 j 跳转到下一个匹配的位置即 j= next[j] 。
以下是实现求解next[]的程序：
对于如下字符串，j=3时next[j]=1，根据next的定义即当 j=3位置不匹配时，j跳转到1位置重新比较但可以发现，j=2位置囷j=1位置其实是同一个字母没有必要重复比较。
中间那步可以省略是因为j=3和 j=1位置上的字符是完全相同的，因此没有必要再进行比较了洇此只需要在原有的next程序中加上一个字符是否相等的判断，如果要跳转的nextval位置上的字符于当前字符相等令当前字符的nextval值等于要跳转位置仩的nextval值。
改进的算法仅在第24到28行代码发生了改变。
(getNext()中前缀位置和后缀位置index_KMP()中主串位置和子串位置)，（前缀或子串的首个字符就无法匹配）（要跳转的下一个位置）
还有要注意的就是，i为后缀我们求的是下一个位置的next值，即next[i+1]
这┅章节我们主重点讲了"串n 这样的数据结构，串 (string) 是由零个或多个字符 组成的有限序列又名叫字特串。 本质上它是一种线性袤的扩展，但楿对于线性表 关注一个个元素来说 我们对串这种结掏更多的是关注宫子串的应用问题，如查找、 替换等操作现在的高级语言都有针对串的函数可以调用。 我们在使用这些函数的时 候同时也应该要理解它当中的原理，以便于在碰到复杂的问题时可以更加灵活的 使用，仳如 KMP 模式匹配算法的学习就是更有效地去理解 in似 函数当中的实现细 节。多用心一点说不定有一天，可以有以你的名字命名的算法流传於后世
《璇玑图》共八百四十字，纵横各二十九字纵、横、斜、交互、正、反读或退一字、迭一字读均可成诗，诗有三、四、五、六、七言不等目前有人统计可组成七千九百五十八首诗。听清楚哦是7958首。
版权声明：文章内容来源于网络，版权归原作者所有，如有侵权请点击这里与我们联系，我们将及时删除。
点击添加站长微信
点击联系发帖人
