数据结构-王红梅-第4章 字符串和多维数组

《数据结构-王红梅-第4章 字符串和多维数组》由会员分享，可在线阅读，更多相关《数据结构-王红梅-第4章 字符串和多维数组（80页珍藏版）》请在金锄头文库上搜索。

1、数据结构 C 版 第2版 清华大学出版社 第 4 章 字符串和多维数组 本章的基本内容是 字符串 在程序设计语言中大都有串变量的概 念 而且实现了基本的串操作 本章重点讨论串 的存储结构及模式匹配算法 数组 在程序设计语言中大都提供了数组作为 构造数据类型 本章重点讨论数组以及特殊矩阵 的存储与寻址 数据结构 C 版 第2版 清华大学出版社 线性表 具有相同类型的数据元素的有限序列 限制插入 删除位置 栈 仅在表的一端进行插入和删除操作 队列 在一端进行插入操作 而另一端进行删除操作 第 4 章 字符串和多维数组 数据结构 C 版 第2版 清华大学出版社 线性表 具有相同类型的数据元素的有限序

2、列 将元素类型扩充为线性表 多维 数组 线性表中的数据元素可以是线性表 第 4 章 字符串和多维数组 将元素类型限制为字符 串 零个或多个字符组成的有限序列 数据结构 C 版 第2版 清华大学出版社 4 1 字符串 串的逻辑结构 p 非空串通常记为 S s1 s2 sn 其中 S是串名 双引号是定界符 双引号引起来的 部分是串值 si 1 i n 是一个任意字符 p 串 零个或多个字符组成的有限序列 p 串长度 串中所包含的字符个数 p 空串 长度为0的串 记为 数据结构 C 版 第2版 清华大学出版社 S1 ab12cd S2 ab12 S3 ab13 S4 ab12 S5 S6 串的逻辑结

3、构 p子串 串中任意个连续的字符组成的子序列 p主串 包含子串的串 p子串的位置 子串的第一个字符在主串中的序号 4 1 字符串 数据结构 C 版 第2版 清华大学出版社 串的逻辑结构 p 串的数据对象约束为某个字符集 p 微机上常用的字符集是标准ASCII码 由 7 位二进制数 表示一个字符 总共可以表示 128 个字符 p 扩展ASCII码由 8 位二进制数表示一个字符 总共可以 表示 256 个字符 足够表示英语和一些特殊符号 但无 法满足国际需要 p Unicode由 16 位二进制数表示一个字符 总共可以表 示 216个字符 能够表示世界上所有语言的所有字符 包 括亚洲国家的表意字符

4、 为了保持兼容性 Unicode字符 集中的前256个字符与扩展ASCII码完全相同 4 1 字符串 数据结构 C 版 第2版 清华大学出版社 串的比较 通过组成串的字符之间的比较来进行的 给定两个串 X x1x2 xn 和Y y1y2 ym 则 1 当n m且x1 y1 xn ym时 称X Y 2 当下列条件之一成立时 称X Y n m且xi yi 1 i n 存在k min m n 使得xi yi 1 i k 1 且xk yk 串的逻辑结构 例 S1 ab12cd S2 ab12 S3 ab13 4 1 字符串 数据结构 C 版 第2版 清华大学出版社 方案1 用一个变量来表示串的实际长度

5、 如何表示串的长度 串的存储结构 0 1 2 3 4 5 6 Max 1 a b c d e f g9空 闲 4 1 字符串 数据结构 C 版 第2版 清华大学出版社 方案1 用一个变量来表示串的实际长度 串的存储结构 如何表示串的长度 0 1 2 3 4 5 6 7 Max 1 a b c d e f g 0空 闲 方案2 在串尾存储一个不会在串中出现的特殊字符 作为串的终结符 表示串的结尾 4 1 字符串 数据结构 C 版 第2版 清华大学出版社 方案3 用数组的0号单元存放串的长度 从1号单 元开始存放串值 串的存储结构 如何表示串的长度 方案2 在串尾存储一个不会在串中出现的特殊字符

6、作为串的终结符 表示串的结尾 方案1 用一个变量来表示串的实际长度 0 1 2 3 4 5 6 7 Max 1 9 a b c d e f g空 闲 4 1 字符串 数据结构 C 版 第2版 清华大学出版社 模式匹配 模式匹配 给定主串S s1s2 sn 和模式T t1t2 tm 在S中寻找T 的过程称为模式匹配 如果匹配成功 返 回T 在S中的位置 如果匹配失败 返回0 算法的一次执行时间不容忽视 问题规模通常很 大 常常需要在大量信息中进行匹配 算法改进所取得的积累效益不容忽视 模式匹配 操作经常被调用 执行频率高 模式匹配问题有什么特点 4 1 字符串 数据结构 C 版 第2版 清华大学

7、出版社 在下面的讨论中 为了和C 语言中的字符数组保 持一致 采用第 2 种顺序存储方法 即从数组下标 0开始存放字符 并且在串尾存储终结符 0 0 1 2 3 4 5 6 7 Max 1 a b c d e f g 0空 闲 4 1 字符串 模式匹配 数据结构 C 版 第2版 清华大学出版社 基本思想 从主串S的第一个字符开始和模式T 的第 一个字符进行比较 若相等 则继续比较两者的后续 字符 否则 从主串S的第二个字符开始和模式T 的 第一个字符进行比较 重复上述过程 直到T 中的字 符全部比较完毕 则说明本趟匹配成功 或S中字符 全部比较完 则说明匹配失败 模式匹配 BF算法 4 1 字

8、符串 数据结构 C 版 第2版 清华大学出版社 si 主串S 模式T tj j i 模式匹配 BF算法 回溯 i 回溯 j 4 1 字符串 数据结构 C 版 第2版 清华大学出版社 si 主串S 模式T j i 模式匹配 BF算法 tj 4 1 字符串 数据结构 C 版 第2版 清华大学出版社 例 主串S ababcabcacbab 模式T abcac a b a b c a b c a c b a b i 2 j 2失败 i回溯到1 j回溯到0 i j 模式匹配 BF算法 i j i j 第 1 趟 a b c a c 4 1 字符串 数据结构 C 版 第2版 清华大学出版社 例 主串S a

9、babcabcacbab 模式T abcac a b a b c a b c a c b a b j 模式匹配 BF算法 i 第 1 趟 a b c a c 4 1 字符串 i 2 j 2失败 i回溯到1 j回溯到0 数据结构 C 版 第2版 清华大学出版社 例 主串S ababcabcacbab 模式T abcac a b a b c a b c a c b a b i 1 j 0失败 i回溯到2 j回溯到0 模式匹配 BF算法 第 2 趟 i j a b c a c 4 1 字符串 数据结构 C 版 第2版 清华大学出版社 例 主串S ababcabcacbab 模式T abcac a b

10、 a b c a b c a c b a b 模式匹配 BF算法 第 2 趟 i j a b c a c 4 1 字符串 i 1 j 0失败 i回溯到2 j回溯到0 数据结构 C 版 第2版 清华大学出版社 例 主串S ababcabcacbab 模式T abcac a b a b c a b c a c b a b a b c a c i 6 j 4失败 i回溯到3 j回溯到0 模式匹配 BF算法 第 3 趟 i j i j i j i j i j 4 1 字符串 数据结构 C 版 第2版 清华大学出版社 例 主串S ababcabcacbab 模式T abcac a b a b c a b

11、 c a c b a b a b c a c 模式匹配 BF算法 第 3 趟 i j 4 1 字符串 i 6 j 4失败 i回溯到3 j回溯到0 数据结构 C 版 第2版 清华大学出版社 例 主串S ababcabcacbab 模式T abcac a b a b c a b c a c b a b a b c a c i 3 j 0失败 i回溯到4 j回溯到0 模式匹配 BF算法 第 4 趟 i j 4 1 字符串 数据结构 C 版 第2版 清华大学出版社 例 主串S ababcabcacbab 模式T abcac a b a b c a b c a c b a b a b c a c 模式匹

12、配 BF算法 第 4 趟 i j 4 1 字符串 i 3 j 0失败 i回溯到4 j回溯到0 数据结构 C 版 第2版 清华大学出版社 例 主串S ababcabcacbab 模式T abcac a b a b c a b c a c b a b a b c a c i 4 j 0失败 i回溯到5 j回溯到0 模式匹配 BF算法 第 5 趟 i j 4 1 字符串 数据结构 C 版 第2版 清华大学出版社 例 主串S ababcabcacbab 模式T abcac a b a b c a b c a c b a b a b c a c 模式匹配 BF算法 第 5 趟 i j 4 1 字符串 i

13、 4 j 0失败 i回溯到5 j回溯到0 数据结构 C 版 第2版 清华大学出版社 例 主串S ababcabcacbab 模式T abcac a b a b c a b c a c b a b a b c a c i 10 j 5 T中全部 字符都比较完毕 匹配成功 模式匹配 BF算法 第 6 趟 i j i j i j i j i j 4 1 字符串 数据结构 C 版 第2版 清华大学出版社 1 在串S和串T中设比较的起始下标i和j 2 循环直到S或T的所有字符均比较完 2 1 如果S i T j 继续比较S和T的下一个字符 2 2 否则 将i和j回溯 准备下一趟比较 3 如果T中所有字符

14、均比较完 则匹配成功 返回 匹配的起始比较下标 否则 匹配失败 返回0 模式匹配 BF算法 4 1 字符串 数据结构 C 版 第2版 清华大学出版社 int BF char S char T i 0 j 0 while S 0 0 j else i i j 1 j 0 if T j 0 return i j 1 else return 0 模式匹配 BF算法 int BF char S char T i 0 j 0 start 0 while S 0 0 j else start i start j 0 if T j 0 return start else return 0 4 1 字符串 数

15、据结构 C 版 第2版 清华大学出版社 模式匹配 BF算法 设串S长度为n 串T长度为m 在匹配成功的情况 下 考虑两种极端情况 例如 S aaaaaaaaaabcdccccc T bcd 4 1 字符串 最好情况 不成功的匹配都发生在串T的第1个字符 数据结构 C 版 第2版 清华大学出版社 模式匹配 BF算法 设串S长度为n 串T长度为m 在匹配成功的情况 下 考虑两种极端情况 最好情况 不成功的匹配都发生在串T的第1个字符 设匹配成功发生在si处 则在i 1趟不成功的匹配中共 比较了i 1次 第i趟成功的匹配共比较了m次 所以 总共比较了i 1 m次 所有匹配成功的可能情况共有n m 1

16、种 则 2 1 1 1 mnO mn mi p mn i i 4 1 字符串 数据结构 C 版 第2版 清华大学出版社 模式匹配 BF算法 设串S长度为n 串T长度为m 在匹配成功的情况 下 考虑两种极端情况 最坏情况 不成功的匹配都发生在串T的最后一个字符 例如 S aaaaaaaaaaabccccc T aaab 4 1 字符串 数据结构 C 版 第2版 清华大学出版社 模式匹配 BF算法 设串S长度为n 串T长度为m 在匹配成功的情况 下 考虑两种极端情况 最坏情况 不成功的匹配都发生在串T的最后一个字符 设匹配成功发生在si处 则在i 1趟不成功的匹配中共 比较了 i 1 m次 第i趟成功的匹配共比较了m次 所以总共比较了i m次 因此 4 1 字符串 数据结构 C 版 第2版 清华大学出版社 模式匹配 KMP算法 为什么BF算法时间性能低 在每趟匹配不成功时存在大量回溯 没有利用已经 部分匹配的结果 如何在匹配不成功时主串不回溯 主串不回溯 模式就需要向右滑动一段距离 如何确定模式的滑动距离 4 1 字符串 数据结构 C 版 第2版 清华大学出版社 i 2 j 2失败 s 1