本章介绍了 串 的 逻辑结构 存储结构 及 串上的基本运算 由于在高级语言中已经提供了较全善的串处理功能因此本章的 重点 是掌握在串上实现的模式匹配算法同时这也是本章的 难点 但是从全书来讲这属于较简单的一章内容
串及其运算( 领会 )(这些内容比较容易理解不用死记)
串 就是 字符串 是一种 特殊 的 线性表 它的每个结点仅由 一个字符 组成
空串 是指 长度为零 的串也就是串中不包含任何字符(结点)
空白串 指串中 包含 一个或多个 空格 字符的串不同与空串它的结点就是一个空格字符
在一个串中任意个连续字符组成的子序列称为该串的 子串 包含子串的串就称为 主串 子串在主串中的序号就是指子串在主串中首次出现的位置如A=I love you B=love则B在A中的序号为注意空格也是字符
空串 是 任意串 的 子串 任意串 是他 自身的 子串
串分为两种 串常量 和 串变量 串常量在程序中不能改变串变量则可以
关于串的基本运算基本上在C语言中已经学过主要有
求串长strlen(char *s)
串复制strcpy(char *tochar *from)
串联接strcat(char *tochar *from)
串比较charcmp(char *schar *s)
和字符定位strchr(char *s char c)等
这些基本运算通过练习来掌握
串的存储结构( 简单应用 )
串 是 特殊的线性表 (结点是字符)所以串的存储结构与线性表的存储结构类似
串的顺序存储结构简称为 顺序串 顺序串又可按存储分配的不同分为 静态存储分配的顺序串 和 动态存储分配的顺序串
静态 的意思可简单地理解为一个确定的存储空间它的长度是不可变的如直接使用定长的字符数组来定义一个串它的优点是涉及串长的操作速度快因为它的最大长度是不变的
动态存储分配 就是在定义串时不分配存储空间直到需要使用时按所需串的长度分配存储单元给它并且在运行中还可以根据需要变化串的长度这就是动态分配不过这样的串仍是顺序存储的也就是说指针指向串的首地址后面的结点是连续存储的
串的链式存储 就是用 单链表 的方式存储串值串的这种链式存储结构简称为 链串 链串与单链表的差异只是它的结点数据域为单个字符这种存储结构方便于串的插入和删除操作但是空间利用率不高因为存放每一个字符要搭配一个指向下一字符的地址而地址所占空间是比较大的为了解决这种存储密度过低的状况可以让一个结点存储多个字符事实上这是顺序串和链串的综合(折衷)
本章的 重点 和 难点 就是串运算的实现特别是顺序串上子串定位的运算
子串定位运算 又称串的 模式匹配 或 串匹配 就是在主串中查找出子串出现的位置 这在应用中非常广泛比如文本编辑中的查找和替换用到的就是子串定位运算的算法
在 串匹配 中将 主串 称为 目标(串) 子串 称为 模式(串 )我们这样想象子串就如同一个模板(样本)用它在目标上对比从头往后比较凡是遇到一模一样的那么一段就算找到一个位置了(我们就说 从这个位置开始的 匹配成功 )用很专业的很酷的话说就是 模式在目标中出现 (我想起了警匪片里的对话)如果这个模板对应的目标串中有不一样的字符出现那么这个位置就 匹配失败
当我们用这个模子依次从目标的头部往后移移动到的位置就叫 位移 如果每次向右移动格那么每次的位移就加上
每次移动后要看看模板里的字符和目标中相应的字符是否相等如果都相同这次位移就叫 有效位移 (其实就是从这个位置开始的 匹配成功 )
另外有一个 合法位移 和 不合法位移 的概念就是说移动一个位置后如果模板的最后一个字符还没有超出目标串中最后一个字符时这个位移就是合法位移如果超出了那么就没有比较的意义了这时就是不合法位移
这是比较容易理解的 串匹配问题 就是找出给定模式串P在给定目标串T中 首次出现的 有效位移 或者是全部 有效位移
具体的串匹配算法也不是很难理解就是用两个循环外循环用于进行模式的位移内循环进行模板内每个字符的比较(判断是否有效位移)关于串匹配的时间复杂度在最坏的情况下就是目标串和模式串分别是 a ^n b 和 a ^m b 的形式就是说每一次合法位移后在内循环中都要比较m个字符才知道是不是有效位移(前面的字符都是一样的)所以最坏的情况下时间复杂度是O((nm+)m)假如m与n同阶的话则它是O(n^)
链串上的子串定位运算的不同之处就是位移是结点地址而不是整数理解一下算法即可
真正的应用主要还是要掌握 串的基本算法 并用它们构造出可以 解决具体问题的 简单算法
第四章 串 复习要点
本章复习要点是
串是一种特殊的线性表它的结点仅由一个字符组成
空串与空白串的区别空串是长度为零的串空白串是指由一个或多个空格组成的串
串运算的实现中子串定位运算又称串的模式匹配或串匹配
串匹配中一般将主串称为目标(串)子串称为模式(串)
本章可能出的题型多半为选择填空等
