补充数据结构-字符串.ppt

补充数据结构 字符串 字符串定义 字符串简称为串 string 是n个 n 0 字符的一个有限序列 一般记为 S a0a1a2 an 1 其中 S是串名 可以是串变量名 也可以是串常量名 用双引号 作为分界符括起来的叫做串值 n是串的长度 即串中字符个数 不包括引号 也不包括串结束符 0 ai是串中的字符 0 i n 可以是ASCII码字符中可打印字符 通常是字母 数字等字符 i称为字符ai在串中的位置 从0开始 空串和空格串 空串 长度为零的串 除串结束符外 不包括任何其他字符 空格串 长度不为零 除串结束符外 还包括其他字符均为空格 串中任意多个连续的字符组成的子序列称为该串的 子串 包括该子串的串称为 主串 一般称子串的首字符 第0个字符 在主串的中的位置为子串在主串中的位置 例如 如果S software P war 则P是S的子串 P在S中的位置为4 主串和子串 空串是任意串的子串 任一串是它自身的子串 除它本身外 一个串的其他子串都是它的真子串 例如 串S car 其子串有 c a r ca ar car 共7个 其中真子串6个 结论 如果串长为n 则其子串个数为n n 1 2 1个 真子串个数为n n 1 2个 串是一种线性结构 既可以用顺序存储结构来存储 也可以用链表结构来存储 在C 中 关于串的表示及基本函数都采用顺序存储结构 采用顺序存储结构存储串时 存储串的数组名指出了串在内存中的首地址 C 中 在存储串的数组末尾添加一个ASCII编码值为0的空字符 标识符为NULL 作为串结束符 例如 charstr DataStructure str 字符串在内存中的存储结构 字符串的存储结构 1 求串的长度 2 把一个串的值赋给另一个串 3 把两个串连接形成另一个长度为两个串长度之和的新串 4 比较两个串的大小 5 在一个串中查找是否存在和另一个串相等的子串 6 在一个串中是否存在一个字符 7 截取子串形成一个新串 8 在一个串中插入一个另一个串 9 从一个串中删除一个子串 字符串的操作 如果两个字符串对应位置的字符都相等 且它们长度相等 则称这 两个字符串相等 字符串比较 字符串大小比较 比较字符串串对应位置上的字符的ASCII码的大小 在比较时 设置一个计数器 从0开始 一直循环到最短的那个字符串结束 一位一位进行比较 1 如果字符串1的第n位的ASCII码值等于字符串2的第n位的ASCII码值 则继续比较下一位 2 如果字符串1的第n位的ASCII码值大于字符串2的第n位的ASCII码值 则输出结果 1 表示字符串1 字符串2 3 如果字符串1的第n位的ASCII码值小于字符串2的第n位的ASCII码值 则输出结果 1 表示字符串1 字符串2 4 如果每一位的ASCII码值都相等 而且长度相同 则输出结果 0 表示字符串1 字符串2 5 如果字符串1是字符串2的前m位 例如abcd与abcdef比较 则字符串1 字符串2 字符串比较 串的逻辑结构与线性表极为相似 区别仅在于串的数据对象约束为字符 串的基本操作和线性表有很大差别 在串的基本操作中 通常以 串的整体 作为操作对象 串的特点 C 的串库 cstring 中提供了许多字符串操作函数 例如常用的有 1 串长度intstrlen char str 2 串拷贝char strcpy char str1 char str2 3 串连接char strcat char str1 char str2 4 串比较intstrcmp char str1 char str2 5 串中字符定位char strchr char str charch 常用的C 字符串函数 可以定义满足如下要求的类 用 完成串对象的连接 用关系运算符完成串对象的比较 可以查找子串 用 完成串的赋值 字符串类 String 及其实现 constintmaxLen 128 classString private char ch 串存放数组intcurLen 串的长度 作为字符串抽象数据类型的类定义 public String String constchar init String constString String String ch newchar maxLen 1 if ch cerr AllocationError n exit 1 curLen 0 ch 0 0 构造函数 初始化为空串 String String constchar init ch newchar maxLen 1 if ch cerr AllocationError n exit 1 curLen strlen init strcpy ch init 构造函数 用C 串来初始化 String String constString 拷贝构造函数 用串对象来初始化 String 当0 pos maxLen且0 len且pos len maxLen时 则在c串 this中从pos所指出的位置开始连续取len个字符组成子串返回 求子串 else if pos len 1 curLen len curLen pos temp curLen len for inti 0 j pos ich i ch j temp ch len 0 return temp String 串赋值 String 若length this length ob maxLen 则把串ob接在 this后面 串连接 char 取 this的第i个字符 比较操作符重载 booloperator constString 流操作符重载 istream 设有两个字符串T和pat 在串T中查找是否有与串pat相等的子串 称串T为 目标 Target 串pat称为 模式 Pattern 称查找模式在目标中的匹配位置的运算为模式匹配 Patternmatching Brute Force算法思想 从目标串T t0t1 tn 1 的第一个字符开始与模式串pat p0p1 pn 1 的第一个字符比较 若相等 则继续比较后续字符 否则 从目标串T的第二个字符开始重新与模式串pat的第一个字符比较 如此继续 若在目标串T中有一个与模式串相等的连续字符序列 则匹配成功 函数返回串pat的首字符在串T中的位置 否则 匹配失败 函数返回 1 Find 字符串的模式匹配 Brute Force算法 intString find String 模式匹配Brute Force算法演示 if p s p s 设模式pat有m个字符 而串T有n个字符 最好情况 若T的前m个字符与pat匹配 则在m次比较后就能找到匹配结果 因此 最好情况下算法的复杂度为O m 最坏情况 假设不进行比较最后一个字符之类的优化 且第一个字符总能匹配上 但却永远没有匹配上的模式 如下面这种情况 pat aab T aaaaaaaa m 3 n 8 此时模式 aab 的m m 3 个字符必须和T中的文本块一