hit数据结构PPT 2第2章线性表-2019

掌握线性表的逻辑结构 线性表的顺序存储结构和链式存储结构的描述方法 能够从时间和空间复杂性的角度综合比较两种存储结构的不同特点 掌握栈和队列 串和数组的概念 存储及操作 能够利用线性表解决实际应用问题 教学要求 2 1抽象数据型线性表 定义 线性表是由n n 0 个相同类型的元素组成的有序集合 记为 a1 a2 a3 ai 1 ai ai 1 an 其中 n为线性表中元素个数 称为线性表的长度 当n 0时 为空表 记为 ai为线性表中的元素 类型定义为ElementType a1为表中第1个元素 无前驱元素 an为表中最后一个元素 无后继元素 对于 ai 1 ai ai 1 1 i n 称ai 1为ai的直接前驱 ai 1为ai的直接后继 线性表是有限的 也是有序的 线性表LIST D R D ai ai Elementset i 1 2 n n 0 R H H ai 1 ai D i 2 n ADT操作 设L的型为LIST线性表实例 x的型为ElementType的元素实例 p为位置变量 所有操作描述为 Insert x p L Locate x L Retrieve p L Delete p L Previous p L Next p L MakeNull L First L End L 数学模型 例2 1 设计函数Deleval LIST 2 2线性表的实现 问题 确定数据结构 存储结构 实现型LIST 并在此基础上实现各个基本操作 存储结构的三种方式 连续的存储空间 数组 静态存储 非连续存储空间 指针 链表 动态存储 游标 连续存储空间 动态管理思想 静态链表 2 2 1指针和游标 指针 地址量 其值为另一存储空间的地址 游标 整型量 其值为数组的下标 用以表示指定元素的 地址 或 位置 2 2 2线性表的数组实现 类型定义 definemaxlength100Typedefstruct ElementTypedata maxlength intlast LIST 位置类型 typedefintPosition 线性表L LISTL ADT操作 VoidInsert ElementTypex Positionp LIST x q PositionLocate ElementTypex LISTL Positionq for q 1 q L last q if L data q x return q return L last 1 ElementTypeRetrieve Positionp LISTL if p L last error 指定元素不存在 elsereturn L data p VoidDelete Positionp LIST q PositionEnd LISTL return L last 1 PositionFirst LISTL return 1 PositionMakeNull LIST PositionPrevious Positionp LISTL if pL last error 前驱元素不存在 elsereturn p 1 PositionNext Positionp LISTL if p L last error 后继元素不存在 elsereturn p 1 思考题 1 数组反向数组元素首尾交换 实现逆向存储 2 数组合并现在给出两个数组A和B 其中 数组A 1 7 9 11 13 15 17 19 数组B 2 4 6 8 10 两个数组合并为数组C 按升序排列 4 在有序数组上的操作 如找给定的数字输入一个已经按升序排序过的数组和一个数字 在数组中查找两个数 使得它们的和正好是输入的那个数字 3 数组循环移位将一个含有n个元素的数组向右循环移动k位 要求时间复杂度是O n 且只能使用两个额外的变量 2 2 3线性表的指针实现 操作讨论 1 插入元素 p a 表头插入元素 b 中间插入元素 c 表尾插入元素 q NewNODE q data x q next p next p next q 或 temp p next P next NewNODE P next data x P next next temp 讨论表头结点的作用 操作讨论 2 删除元素 q p next P next q next Deleteq 或 q p next P next p next next Deleteq 讨论结点ai的位置p ADT操作 PositionEnd LIST Positionq q L while q next Null q q next return q VoidInsert ElementTypex Positionp LIST PositionLocate ElementTypex LISTL Positionp p L while p next Null if p next data x returnp elsep p next returnp ElementTypeRetrieve Positionp LISTL return p next data VoidDelete Positionp LIST PositionPrevious Positionp LISTL Positionq if p L next error 不存在前驱元素 else q L while q next p q q next returnq PositionNext Positionp LISTL Positionq if p next Null error 不存在后继元素 else q p next returnq PositionMakeNull LIST PositionFirst LISTL returnL 例2 2 线性表的遍历与元素个数统计 带表头结构 遍历 按照一定的原则或顺序 依次访问线性表中的每一个元素 且每个元素只能被访问一次 原则或顺序 从前向后 intList LISTheader Positionp intn 0 p header next while p visit p data n p p next return n 问题 如何实现按逆序输出链表中的每一个元素 例2 3 线性表的反向 即线性表的最后一个元素变成第一个元素 而第一个元素变成最后一个元素 P head next head next NULL q p next P next head next head next p p q 分析 第1步 第2步 q p next P next head next head next p p q q p next P next head next head next p p q While p q p next P next head next head next p p q 重复上述操作 把链表p的每一个结点依次插入到header的头节点之后 每次都形成一个新的第一个节点 直到p NULL为止 这个过程可以用下面循环完成 VoidRevers1 LIST O n 第3步 例2 4 按逆序遍历链表 实现逆序遍历移动指针的次数为 1 2 3 n n n 1 2逆序输出的时间复杂度为O n2 VoidReversList LISTp if p next ReversList p next visit p data O 调用 ReversList header next 例2 5 建立有序链表 P head while p next Null Insert x p L 建立有序链表算法 NODE Create Link NODE head p intx head NODE malloc sizeof NODE head next Null 表头结点scanf d 线性表静态存储与动态存储的比较 比较参数 表的容量 存取操作 时间 空间 链式存储灵活 易扩充顺序存取访问元素费时间实际长度 节省空间 顺序存储固定 不易扩充随机存取插入删除费时间估算表长度 浪费空间 思考题 1 单向链表环的问题如何判断一个单向链表是否有环 找到环的入口结点 2 线性链表 求倒数第K个数 3 线性链表 求中间位置的元素 4 单向链表交叉问题如何判断两个单向链表是否交叉 找到交叉结点 一分为二看链表 链表存在的三个问题 首先 每创建一个结点 都要进行一次系统调用分配一块空间 这会浪费一 定时间 其次 由于创建结点的时间不固定 会导致结点分配的空间不连续 容易形成离散的内存碎片 最后 由于内存不连续 所以链表的局部访问性较差 容易出现cache缺失 Cache 高速缓冲存储器总大小为32KB 路组相连 每组有8个line 每个line的大小64Byte 一共有32K 8 64 64个组 用户可设置 对链表的改进 内存池 单线程 只支持固定块大小的内存池 分配N块固定大小的连续内存 N块需要根据需求设定 每需要一个节点就从内存池中申请 get 一块空闲的块 用完之后再回收 free 到内存池中 内存池可以解决链表三个问题中的前两个 不能解决后一个 但是如果内存池较小可以缓解cache缺失的问题 2 2 4线性表的游标实现 元素 SPACE i data 型 为ElementType 基本 复合 下一元素位置 SPACE i next 型 为int类似指针链表 对游标实现的线性表仍设表头结点 SPACE 7 3 L M 9 available 线性表 线性表1 a b c L 7线性表2 d e M 3空闲表 available 9 q NewSpacestr q SPACE available next SPACE available next SPACE q next Deleteq SPACE q next SPACE available next SPACE available next q VoidInsert ElementTypex Positionp Spacestr SPACE Positionq q NewSpacestr SPACE q data x SPACE q next SPACE p next SPACE p next q VoidDelete Positionp Spacestr SPACE Positionq if SPACE p next 1 SPACE q SPACE p next SPACE p next SPACE q next Deleteq ADT操作 2 2 5双向链表 结点类型structDnodeType ElementTypedata DnodeType next previous typedefDnodeType DLIST typedefDnodeType Position 删除位置p的元素 p previous next p next p next previous p previous p header tail ADT操作 讨论 元素的位置 q p VoidInsert ElementTypex Positionp DLIST 2 2 6环形链表 对线性链表的改进 解决 单向操作 的问题 改进后的链表 能够从任意位置元素开始访问表中的每一个元素 单向环形链表 其结构与单向线性链表相同 用表尾指针标识链表 从而省去了表头结点 表头 R next 亦即表中的一个元素a1 R header ADT操作 在表左端插入结点Insert x First R R VoidLInsert ElementTypex LIST 在表右端插入结点Insert x End R R RInsert x R VoidRInsert ElementTypex LISTR LInsert x R R R next 从表左端删除结点Delete First R R LDelete R VoidLDelete LIST 双向环形链表的结构与双向连表结构相同 只是将表头元素的空previous域指向表尾 同时将表尾的空next域指向表头结点 从而形成向前和向后的两个环形链表 对链表的操作变得更加灵活 空双向环形链表 a1 R R Null 单一结点双向环形链表 R next R R previous R R header Header previous R R next header 双向环形链表 例2 6 设计算法 将一个单向环形链表反向 头元素变成尾元素 尾元素变成新的头元素 依次类推 r next R然后单独处理R 2 3栈 Stack 栈是线性表的一种特殊形式 是一种限定性数据结构 也就是在对线性表的操作加以限制后 形成的一种新的数据结构 定义 栈是限定只在表尾进行插入和删除操作的线性表 栈又称为后进先出 LastInFirstOut 的线性表 简称LIFO结构 栈举例 栈的基本操作 MakeNull S Top S Pop S Push x S Empty S 2 3 1栈的实现 1 顺序存储 顺序栈示意图 top 结构类型 typedefstruct ElementTypedata maxlength inttop STACK STACKS 栈的容量 maxlength 1 栈空 S top 0 栈满 S top maxlength 1 栈顶元素 S data S top ADT操作 VoidMakeNull STACK BooleanEmpty STACKS if S top 1 returnTRUEelsereturnFALSE ElementTypeTop STACKS ifEmpty S returnNull elsereturn S data S top ElementTypePop STACK VoidPush ElementTypex STACK 2 链式存储 采用由指针形成的线性链表来实现栈的存储 要考虑链表的哪一端实现元素的插入和删除比较方便 实现的方式如右图所示 其操作与线性链表的表头插入和删除元素相同 3 多个栈共用一个存储空间的讨论 IntIs Stack i Full STACKS intbot inttop inti 判断第i个栈是否满 满返回1 否则返回0 VoidMove Stack i STACK S int bot int top inti intdt 移动第i个栈 dt为位移量 CallB 主程序A CallC 程序B CallD 程序C i 程序D Begin End Da Da Db Dc Db Dc 栈 入栈 出栈 2 3 2栈的应用 1 栈和递归过程 A B C 栈 A B C 栈 A B C 栈 A的返回点 1 子程序A正在执行 2 A调用B B在执行 3 B调用C C在执行 先进先出的规则 在执行的任何点处 若一个程序要将控制返回到调用程序 则该程序一定是最末一个进入的 例2 8 间接递归3个程序A B C 其中A调用B B调用C 而C又递归调用B A B C 栈 A B C 栈 6 C返回到B 第一次调用 B在执行 C执行完毕 5 B返回到C C在执行对B的递归调用完毕 A B C 栈 7 B返回到A A在执行 非递归调用B完毕 A B C 栈 4 C递归调用B B在执行 子程序A CallA Da1 Da2 Da3 Dan 1 Dan Begin End 例2 9 直接递归 判断括号匹配算法 BooleanCorrect charext int 数组ext用于存储表达式 STACKS intj 0 MakeNull S while ext j 0 if exp j Push ext j S if ext j x Top S if x Pop S elsereturnFALSE j if Empty S returnFALSE elsereturnTRUE 例2 10 括号匹配问题 对表达式从左到右扫描 遇到左括号进栈 当遇到右括号时退栈 比较是否匹配 当表达式扫描完毕 若栈为空 说明嵌套正确 否则括号匹配错误 问题 是否有其它方法 例2 11 判断字符串是否中心对称 例如 xyzzyxxyzyx均属中心对称 判断字符串是否中心对称算法 BooleanIudge LIST head STACKS chare MakeNull S LIST p head while p Push p data S p p next p head while p e Top S Pop S if p data e p p next elsebreak if p returnTRUE elsereturnFALSE 例2 12 求阶乘的函数 2 递归算法longfact intn if n 0 n 1 return1 elsereturnn fact n 1 1 非递归算法longfact intn longf 2 inti for i 2 i n i f f i return f T n o n T n o n 分析递归求解n 的过程 递归过程与递归工作栈递归过程在实现时 需要自己直接或间接调用自己 层层向下递归 返回次序正好相反 递归过程与递归工作记录每一次递归调用时 需要为过程中使用的参数 局部变量和返回地址等另外分配存储空间 每层递归调用需分配的空间形成递归工作记录 按栈结构组织 即LIFO 递归函数的内部执行过程建栈 运行开始时 首先为递归调用建立一个工作栈 其结构包括值参 局部变量和返回地址 压栈 每次执行递归调用之前 把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈 出栈 每次递归调用结束后 将栈顶元素出栈 使相应的值参和局部变量恢复为调用前的值 然后转向返回地址指定的位置继续执行 例2 13 汉诺塔问题 递归的经典问题在世界刚被创建的时候有一座钻石宝塔 塔A 其上有64个金碟 所有碟子按从大到小的次序从塔底堆放至塔顶 紧挨着这座塔有另外两个钻石宝塔 塔B和塔C 从世界创始之日起 婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去 其间借助于塔B的帮助 每次只能移动一个碟子 任何时候都不能把一个碟子放在比它小的碟子上面 当牧师们完成任务时 世界末日也就到了 汉诺塔问题的递归求解 如果n 1 则将这一个盘子直接从塔A移到塔C上 否则 执行以下三步 将塔A上的n 1个碟子借助塔C先移到塔B上 把塔A上剩下的一个碟子移到塔C上 将n 1个碟子从塔B借助于塔A移到塔C上 设 函数 Hanoi intn charA charB charC 功能 将n个盘子从塔A移到塔C 塔B为临时 函数 Move A C 功能 将塔A上的1个盘子直接移到塔C 汉诺塔问题的递归求解 如n 1 则将这1个盘子直接从塔A移到塔C上 Move A C 否则 执行以下三步 1 将n 1个盘子从塔A移到塔B 塔C上 Hanoi n 1 A C B 2 把塔A上剩下的一个碟子移到塔C上 Move A C 3 将n 1个碟子从塔B借助于塔A移到塔C上 Hanoi n 1 B A C voidHanoi intn charA charB charC if n 1 Move A C else Hanoi n 1 A C B Move A C Hanoi n 1 B A C 递归函数的运行轨迹写出函数当前调用层执行的各语句 并用有向弧表示语句的执行次序 对函数的每个递归调用 写出对应的函数调用 从调用处画一条有向弧指向被调用函数入口 表示调用路线 从被调用函数末尾处画一条有向弧指向调用语句的下面 表示返回路线 在返回路线上标出本层调用所得的函数值 例2 14 数制转换计算机实现计算的基本问题 方法 除留余数法 对输入的任意非负十进制整数 打印输出与其等值的八进制数 voidmain STACKs NewStack cin n while n Push n 8 s n 8 while Empty s cout Top s Pop s 时间复杂度 85898余28737余1892余4811余381余10 5898 10 13412 8 2 迷宫求解 问题 010001100011111100011011100111011000011110011110111101101100110100101111111001101110100111011110011111111001101101111101110001101100000001111100011110010011111011110 一个迷宫可用上图所示方阵 m n 表示 0表示能通过 1表示不能通过 现假设耗子从左上角 1 1 进入迷宫 编写算法 寻求一条从右下角 m n 出去的路径 11 15 m n 出口 入口 迷宫示例 分析 迷宫可用二维数组Maze i j 1 i m 1 j n 表示 入口maze 1 1 0 耗子在任意位置可用 i j 坐标表示 位置 i j 周围有8个方向可以走通 分别记为 E SE S SW W NW N NE 如图所示 方向v按从正东开始且顺时针分别记为1 8 v 1 8 设二维数组move记下八个方位的增量 j i 从 i j 到 g h 且v 2 东南 则有 g i move v 1 i 1 h j move v 2 j 1 Vij说明101E211SE310S41 1SW50 1W6 1 1NW7 10N8 11NE 为避免时时监测边界状态 可把二维数组maze 1 m 1 n 扩大为maze 0 m 1 0 n 1 且令0行 0列 m 1行 n 1列的值均为1 出口 入口 迷宫示例 采用试探的方法 当到达某个位置且周围八个方向走不通时需要回退到上一个位置 并换一个方向继续试探 为解决回退问题 需设一个栈 当到达一个新位置时将 i j v 进栈 回退时退栈 每次换方向寻找新位置时 需测试该位置以前是否已经过 对已到达的位置 不能重复试探 为此设矩阵mark 其初值为0 一旦到达位置 i j 时 置mark i j 1 文字描述算法 耗子在 1 1 进入迷宫 并向正东 v 1 方向试探 检测下一方位 g h 若 g h m n 且maze m n 0 则耗子到达出口 输出走过的路径 程序结束 若 g h m n 但 g h 方位能走通且第一次经过 则记下这一步 并从 g h 出发 再向东试探下一步 否则仍在 i j 方位换一个方向试探 若 i j 方位周围8个方位阻塞或已经过 则需退一步 并换一个方位试探 若 i j 1 1 则到达入口 说明迷宫走不通 迷宫求解算法 VoidGETMAZE maze mark move S i j v 1 1 1 mark 1 1 1 s top 0 do g i move v 1 h j move v 2 if g m cout 路径不存在 3 表达式求值 高级语言中 采用类似自然语言的中缀表达式 但计算机对中缀表达式的处理是很困难的 而对后缀或前缀表达式则显得非常简单 后缀表达式的特点 在后缀表达式中 变量 操作数 出现的顺序与中缀表达式顺序相同 后缀表达式中不需要括弧定义计算顺序 而由运算 操作符 的位置来确定运算顺序 波兰逻辑学家J Lukasiewicz于1929年提出的一种表达式 将中缀表达式转换成后缀表达式 对中缀表达式从左至右依次扫描每一个字符 由于操作数的顺序保持不变 当遇到操作数时直接输出 为调整运算顺序 设立一个栈用以保存操作符 扫描到操作符时 将操作符压入栈中 进栈的原则是保持栈顶操作符的优先级要高于栈中其他操作符的优先级 否则 栈顶操作符依次退栈并输出 直到表达式结束 遇到 进栈 当遇到 时 退栈输出直到 为止 由后缀表达式计算表达式的值 对后缀表达式从左至右依次扫描 与 相反 遇到操作数时 将操作数进栈保留 当遇到操作符时 从栈中退出两个操作数并作相应运算 将计算结果进栈保留 直到表达式结束 栈中唯一元素即为表达式的值 2 4队列 Queue 队列是对线性表的插入和删除操作加以限定的另一种限定型数据结构 定义 将线性表的插入和删除操作分别限制在表的两端进行 和栈相反 队列是一种先进先出 FirstInFirstOut 简称FIFO结构 的线性表 ADT操作 MakeNull Q Front Q EnQueue x Q DeQueue Q Empty Q 2 4 1队列的指针实现 元素结构 structNODE ElementTypedata structNODE next 队列的 型 structQUEUE structNODE front structNODE rear ADT操作 VoidMakeNull QUEUE booleanEmpty Q QUEUE ElementTypeFront Q QUEUEQ returnQ front data VoidEnQueue ElementTypex QUEUE VoidDeQueue QUEUE 2 4 2队列的数组实现 队列的 型 structQUEUE ElementTypedata maxlength intfront intrear 随着不断有元素出队和进队 插入和删除 队列的状态由1变成2 此时an占据队列的最后一个位置 第n 1个元素无法进队 但实际上 前面部分位置空闲 假溢出 队列Q状态1 队头 队尾 front rear maxlength Q 队列Q状态2 队头 队尾 front rear maxlength Q 解决假溢出的方法有多种 一是通过不断移动元素位置 每当有元素出队列时 后面的元素前移一个位置 是队头元素始终占据队列的第一个位置 第二种方法是采用循环队列 Q rear Q rear 1 n Q front Q front 1 n 问题 如何解决循环队列中队空与队满状态相同 方法一 约定队列头指针在队列尾指针的下一位置上 方法二 另设一个标志位用以区别队空与队满两种状态 结论 两种方法的代价是相同的 VoidMakeNull QUEUE ADT操作 intAddone inti return i 1 maxlength ElementTypeFront QUEUEQ if Empty Q returnNull elsereturn Q data Q front booleanEmpty Q QUEUEQ if Addone Q rear Q front returnTRUE elsereturnFALSE VoidDeQueue QUEUEQ if Empty Q error 空队列 elseQ front Addone Q front VoidEnQueue ElementTypex QUEUEQ if Addone Addone Q rear Q front error 队列满 else Q rear Addone Q rear Q datas Q rear x 1 约瑟夫出圈问题n个人围成一圈 从第一个人开始报数 报到m的人出圈 剩下人继续开始从1报数 直到所有的人都出圈为止 2 舞伴问题假设在周末舞会上 男士们和女士们进入舞厅时 各自排成一队 跳舞开始时 依次从男队和女队的队头上各出一人配成舞伴 若两队初始人数不相同 则较长的那一队中未配对者等待下一轮舞曲 现要求写算法模拟上述舞伴配对问题 思考题 实验一多项式的代数运算 方案1 数组一 方案2 数组二 P x 3x14 2x8 1 P x 3x14 2x8 1 coeftypep N Struct coeftypecoef exptypeexp p N 结点类型 structPolyNode intcoef intexp polylink link typedefPolyNode PolyPointer 方案3 链表 a x 3x14 2x8 1b x 8x14 3x10 10 x6 1 p exp q exp a b c a b c 2 p expexp p p q q c x a x b x 11x14 3x10 2x8 10 x6 1 a b c 4 p expexp p a b c 5 p null q a b c 3 p exp q exp p q q p PolyPointerAttch intc inte PolyPointerd PolyPointerx x newPolyNode x coef c x exp e d link x returnx d charCompare intx inty charc if x y c elseif x y c elsec return c Attch intc inte PolyPointerd Compare intx inty x 当x y 当x y 当x y 表达式加法算法 PolyPointerPolyAdd PolyPointera PolyPointerb PolyPointerp q d c inty p a link q b link c newPolyNode d c while p NULL case d Attch q coef q exp d q q link break while p NULL d Attch p coef p exp d p p link while q NULL d Attch q coef q exp d q q link d link NULL p c c c link deletep returnc 2 5串 String 串是线性表的一种特殊形式 表中每个元素的类型为字符型 是一个有限的字符序列 串的基本形式可表示成 S a1a2a3 an 其中 charai 0 i n n 0 当n 0时 为空串 n为串的长度 C语言中串有两种实现方法 1 字符数组 如 charstr1 10 2 字符指针 如 char str2 ADT操作 stringNull booleanIsNull S VoidIn S a intLen S VoidConcatT S1 S2 stringSubstr S m n booleanIndex S S1 2 5 1抽象数据型串 例2 15 将串T插在串S中第i个字符之后Insert S T i VoidInsert STRING VoidDelete STRING 例2 16 从串S中将子串T删除Delete S T 2 5 2串的实现 1 串的顺序存储采用连续的存储空间 数组 自第一个元素开始 依次存储字符串中的每一个字符 charstr 10 Harbin 操作 Null IsNull In Len Concat Substr Index 2 串的链式存储构造线性链表 element类型为char 自第一个元素开始 依次存储字符串中的每一个字符 2 串的链式存储 续 structnode chardata node link typedefnode STRING1 STRING1str1 structnode chardata 4 node link typedefnode STRING2 STRING2str2 intIndex STRING1S S1 structnode p q i intt if S1 Null Index S S1 若S1是S的子串则返回S1首字符在S中的位置 否则返回0 ADT操作 3 模式匹配 朴素模式匹配算法 模式匹配 字符串匹配是计算机的基本任务之一 给定S S0S1 Sn 1 主串 和T T0T1 Tm 1 模式 在S中寻找T的过程称为模式匹配 如果匹配成功 返回T在S中的位置 如果匹配失败 返回 1 假设串采用顺序存储结构 朴素模式匹配算法 Brute Force算法 枚举法 回溯 从主串S的第一个字符开始和模式T的第一个字符进行比较 若相等 则继续比较两者的后续字符 否则 从主串S的第二个字符开始和模式T的第一个字符进行比较 重复上述过程 直到T中的字符全部比较完毕 说明本趟匹配成功 或S中字符全部比较完 则说明匹配失败 设主串S ababcabcacbab 模式串T abcac 第1趟匹配主串ababcabcacbabi 2模式串abcj 2匹配失败第2趟匹配主串ababcabcacbabi 1模式串abcj 0匹配失败第3趟匹配主串ababcabcacbabi 6模式串abcacj 4匹配失败第4趟匹配主串ababcabcacbabi 3模式串abcj 0匹配失败第5趟匹配主串ababcabcacbabi 4模式串abcj 0匹配失败第6趟匹配主串ababcabcacbabi 9 返回i lenT 1模式串abcacj 4匹配成功 特点 主串指针需回溯 i j 1 模式串指针需复位 j 0 BF算法实现的详细步骤 1 在串S和串T中设比较的起始下标i和j 2 循环直到S或T的所有字符均比较完 2 1如果S i T j 继续比较S和T的下一个字符 2 2否则 将i回溯 i i j 1 j复位 准备下一趟比较 3 如果T中所有字符均比较完 则匹配成功 返回主串起始比较下标 否则 匹配失败 返回 1 intStrMatch BF char S char T intpos 0 为主串S 模式T长度分别为lenS和lenT 且字符串采用顺序存储 i pos j 0 从第一个位置开始比较while ilenT returni lenT 1 elsereturn 1 匹配不成功 Brute Force算法的时间复杂度 主串S长n 模式串T长m 可能匹配成功的 主串 位置 0 n m 最好的情况下 模式串的第0个字符失配设匹配成功在S的第i个字符 则在前i趟匹配中共比较了i次 第i趟成功匹配共比较了m次 总共比较了 i m 次 所有匹配成功的可能共有n m 1种 所以在等概率情况下的平均比较次数 最好情况下算法的平均时间复杂度O n m 最坏的情况下 模式串的最后1个字符失配设匹配成功在S的第i个字符 则在前i趟匹配中共比较了i m次 第i趟成功匹配共比较了m次 总共比较了 i 1 m次 所有匹配成功的可能共有n m 1种 所以在等概率情况下的平均比较次数 最坏情况下的平均时间复杂度为O n m Cook于1970年证明的一个理论得到 任何一个可以使用被称为下推自动机的计算机抽象模型来解决的问题 也可以使用一个实际的计算机 更精确的说 使用一个随机存取机 在与问题规模对应的时间内解决 特别地 这个理论暗示存在着一个算法可以在大约m n的时间内解决模式匹配问题 D R Knuth和V R Pratt努力地重建了Cook的证明 由此创建了这个模式匹配算法 大概是同一时间 J H Morris在考虑设计一个文本编辑器的实际问题的过程中创建了差不多是同样的算法 克努特 莫里斯 普拉特 KMP算法 并不是所有的算法都是 灵光一现 中被发现的 而理论化的计算机科学确实在一些时候会应用到实际的应用中 斯蒂芬 库克 StephenA Cook 1961年从UniversityofMichigan获得其学士学位 于1962年和1966年从哈佛大学分别获得其硕士与博士学位 1966年到1970年 Stephen在加州Berkeley分校担任助理教授职务 1970年 Stephen加盟多伦多大学并工作直到现在 他是NP完全性理论的奠基人 1971年发表Cook定理奠定了NP完全理论的基础而获1982年图灵奖 Cook是对计算复杂性理论有突出贡献的计算机科学家之一 在1998年加盟苹果电脑担任全球业务高级副总裁之前 Cook先生曾任康柏 Compaq 企业材料副总裁 负责采购 管理康柏的产品存货 在这之前 Cook先生是IntelligentElectronics经销商部门的首席运营官 Cook先生还曾在IBM供职12年之久 他在IBM最近的职务为北美业务执行主管 负责IBM的PersonalComputerCompany在北美和拉美的制造和分销运作 2 5 2KMP算法 改进的模式匹配算法 为什么BF算法时间性能低 在每趟匹配不成功时存在大量回溯 没有利用已经部分匹配的结果 如何在匹配不成功时主串不回溯 主串不回溯 模式就需要向右滑动一段距离 如何确定模式的滑动距离 利用已经得到的 部分匹配 的结果 将模式向右 滑动 尽可能远的一段距离 next j 后 继续进行比较 字符串的前缀和后缀 主串ababcabcacbab 模式abcac 需要解决的问题 1 当匹配过程中产生 失配 si tj 时 模式串 向右滑动 可行的距离多远 2 当主串中第i个字符与模式中第j个字符 失配 时 主串中第i字符应与模式中哪个字符再比较 t abaababc t abaabcac 设 s s0s1s2 sn 1 t t0t1t2 tm 1 当si tj时 存在 t0t1 tj 1 si jsi j 1 si 1 若模式串t中存在可互相重叠的最大真子串满足 t0t1 tk 1 tj kti k 1 tj 1 0 k j 则下一次比较可直接从模式的第k 1个字符tk开始与目标串的第i 1个字符si相对应继续进行下一趟匹配 若模式串中不存在上述真子串 则下一次比较可直接从模式串的第1个字符t0开始与目标串s的第i 1个字符si相对应继续进行下一趟的匹配 如下例所示 当第一次搜索到S 5 和T 5 不等后 S下标不是回溯到1 T下标也不是回溯到开始 而是根据T中T 5 d 的模式函数值 next 5 2 直接比较S 5 和T 2 是否相等 因为相等 S和T的下标同时增加 因为又相等 S和T的下标又同时增加 最终在S中找到了T KMP匹配算法和简单匹配算法效率比较 一个极端的例子是 在S AAAAAA AAB 100个A 中查找T AAAAAAAAAB 简单匹配算法每次都是比较到T的结尾 发现字符不同 然后T的下标回溯到开始 S的下标也要回溯相同长度后增1 继续比较 如果使用KMP匹配算法 就不必回溯 时间复杂度从O m n 降为O m n KMP算法的核心思想 利用已经得到的部分匹配信息来进行后面的匹配过程 T 5 d 的模式函数值等于2 即 next 5 2 表示T 5 d 的前面有2个字符和开始的两个字符相同 且T 5 d 不等于开始的两个字符之后的第三个字符 T 2 c 如果开始的两个字符之后的第三个字符也为 d 那么 尽管T 5 d 的前面有2个字符和开始的两个字符相同 T 5 d 的模式函数值也不为2 而是为0 next函数 1 next 0 1 任何串的第一个字符的模式值规定为 1 2 next j 1 模式串t中下标为j的字符 如果与首字符相同 且j的前面的1 k个字符与开头的1 k个字符不等 或者相等但t k t j 1 k j如 t abCabCad 则next 6 1 因t 3 t 6 3 next j k 模式串t中下标为j的字符 如果j的前面k个字符与开头的k个字符相等 且tj tk 1 k j 即 t0t1t2 tk 1 tj ktj k 1tj k 2 tj 1 且tj tk 1 k j 4 next j 0 除 1 2 3 的其他情况 例2 17 求T abcac 的模式函数的值next 0 1根据 1 next 1 0根据 4 因 3 有1 k j 不能说 j 1 T j 1 T 0 next 2 0根据 4 因 3 有1 k j T 0 a T 1 b next 3 1根据 2 next 4 1根据 3 T 0 T 3 且T 1 T 4 若T abcab 为什么T 0 T 3 还会有next 4 0 因为T 1 T 4 根据 3 且T j T k 被划入 4 例2 18 求T ababcaabc 的模式函数的值next 0 1根据 1 next 1 0根据 4 next 2 1根据 2 next 3 0根据 3 虽T 0 T 2 但T 1 T 3 被划入 4 next 4 2根据 3 T 0 T 1 T 2 T 3 且T 2 T 4 next 5 1根据 2 next 6 1根据 3 T 0 T 5 且T 1 T 6 next 7 0根据 3 虽T 0 T 6 但T 1 T 7 被划入 4 next 8 2根据 3 T 0 T 1 T 6 T 7 且T 2 T 8 即 next 3 0 而不是 1 next 6 1 而不是 1 next 8 2 而不是 0 例2 19 求T abCabCad 的模式函数的值 next 5 0根据 3 虽T 0 T 1 T 3 T 4 但T 2 T 5 next 6 1根据 2 虽前面有abC abC 但T 3 T 6 next 7 4根据 3 前面有abCa abCa 且T 4 T 7 若T 4 T 7 即T adCadCad 则next 7 0 而不是 4 因为T 4 T 7 1 next n 1表示S m 和T 0 间接比较过了 不相等 下一次比较S m 1 和T 0 2 next n 0表示比较过程中产生了不相等 下一次比较S m 和T 0 3 next n k 0但k n 表示S m 的前k个字符与T中的 开始k个字符已经间接比较相等了 下一次比较S m 和T k 相等吗 4 其他值 next函数值究竟是什么含义 设在字符串S中查找模式串T 若S m T n 那么 取T n 的模式函数值next n voidGetNext constchar T intnext 求模式串T的next函数值intj 0 k 1 next 0 1 while T j 0 if k 1 T j T k j k if T j T k next j k elsenext j next k ifelsek next k while GetNext 求串T的模式值next n 的函数 intKMP char s char t intnext intindex 0 i 0 j 0 if s t t 0 0 s 0 0 return 1 空指针或空串 返回 1while s i 0 匹配失败 KMP KMP算法 2 6数组 ARRAY 2 6 1抽象数据型数组 数组是由下标 index 和值 value 组成的序对 index value 的集合 也可以定义为是由相同类型的数据元素组成有限序列 数组在内存中是采用一组连续的地址空间存储的 正是由于此种原因 才可以实现下标运算 所有数组都是一个一维向量 数组1 a1 a2 a3 ai an 数组2 a11 a1n a21 a2n aij am1 amn 1 i m 1 j n 数组3 a111 a11n a121 a12n aijk amn1 amnp 1 i m 1 j n 1 k p n维数组中含有 bi个数据元素 每个元素都受着n个关系的约束 在每个关系中 元素aj1j2 jn 0 ji bi 2 都有一个直接后继元素 i 1 n 因此 数组仍是一种特殊形式的线性表 对二维数组可以理解成一维数组 其每个元素又是一个一维数组 以此类推 所谓n维数组同样如此 操作 Create 建立一个空数组Retrieve array index 返回第index个元素Store array index value 在数组array中 为第index个元素赋值val