《【大学数据结构课件】串.ppt》由会员分享，可在线阅读，更多相关《【大学数据结构课件】串.ppt（12页珍藏版）》请在金锄头文库上搜索。
1、内容提要 5 1串及其操作串的定义串的基本操作5 2串的表示和实现顺序存储表示串的块链存储表示5 3串的模式匹配算法求子串位置的定位函数模式匹配的一种改进算法5 4串操作应用举例文本编辑建立词索引表 5 1串及其操作 1 串的逻辑结构定义串 String 或字符串 是由零个或多个字符组成的有限序列 一般记为 s a1a2 an n 0 其中 s是串的名 用单引号括起来的字符序列是串的值 ai 1 i n 可以是字母 数字或其他字符 串中字符的数目n称为串的长度 零个字符的串称为空串 nullstring 它的长度为零 空串与空格串的区别 子串 串中任意个连续字符构成的子序列串相等 当且仅当这两
2、个串的值相等 也就是说 只有当两个串的长度相等 并且各个对应位置的字符串都相等时才相等 串及其操作 cont d 2 串的基本操作串的基本操作 赋值复制比较求长度串连接子串定位取子串串插入串删除串替换 5 2串的表示和实现 1 字符串的存储表示 1 顺序存储利用静态数组存放字符串 2 堆分配存储利用动态分配的内存存放字符串 3 链式存储块链结构 defineN5 N决定存储密度typedefstructstrnode charsdata N structstrnode next STRNODE 串的表示和实现 cont d 3 链式存储块链结构 defineN5 N决定存储密度typedefs
3、tructstrnode charsdata N structstrnode next STRNODE 串的表示和实现 cont d 2 字符串基本操作的实现 1 串的联接利用截尾法进行处理 2 求两个串的最长公共子串 串的表示和实现 cont d 2 求两个串的最长公共子串 5 3串的模式匹配算法 1 字符串模式匹配 普通算法 算法思想 每当一趟匹配过程中出现字符比较不等时 不需回溯i指针 而是利用已经得到的 部分匹配 的结果将模式向右 滑动 进可能远的一段距离后 继续进行比较 串的模式匹配算法 cont d 2 字符串模式匹配的KMP算法 算法思想 1 对于象 1234abcd 这样的模式
4、串 KMP算法与普通算法没有什么不同 但对于 123a123b 这样的模式串 KMP的算法就尽显优势 也就是说 如果模式串本身包含有自身重复子串 KMP算法会更快 2 与普通算法相比 KMP算法在比较失败时 并没有一切推倒重来 而是巧妙利用的模式串 包含重复子串 的特征 减少了比较的次数 串的模式匹配算法 cont d 3 用大写字母表示子串 小写字母表示串中的字符 假设当比较操作进行到主串S的下标j处时 比较失败 这是模式串T的当前字符的下标时k 并且T 0 k P T m P T k T m T k 也就是说 比较失败之前的模式串具有重复子串 这时我们可以将S看成是S XPaP S j 面
5、要做的不是将beginpos 推倒重来 而是直接将T m 与S j 进行比较 这种操作称为模式串的滑动 每当比较失败就滑动一次 这样可以有效减少比较次数 4 关键一点是滑动到哪里比较合适 也就是说 如何确定m的值 m被称为k的next值 5 如果已知k的next值是m k 1的next值如何求 这是解决问题的突破口 因为我们已知0的next值是 1 1的next值是0 能者为之 2 字符串模式匹配的KMP算法 串的模式匹配算法 cont d 2 字符串模式匹配的KMP算法 0当j 1时next j Max k 1 k j且 p1 pk 1 pjj k 1 pjj 1 当此集合不空时1其他情况
6、j12345678 模式串abaabcacnext j 01122312 5 4串操作应用举例 1 文本编辑文本编辑程序是一个面向用户的系统服务程序 广泛用于源程序的输入和修改 甚至用于报刊和书籍的编辑排版以及办公室的公文书信的起草和润色 文本编辑的实质是修改字符数据的形式或格式 各种文本编辑程序的功能强弱不同 但是其基本操作是一致的 一般都包括串的查找 插入和删除等基本操作 文本编辑程序的设计 用户可以利用换页符和换行符把文本划分为若干页 每页有若干行 可以把文本看承是一个字符串 称为文本串 页则是文本串的子串 行又是页的子串 2 建立词索引表信息检索是计算机应用的重要领域之一 主要操作是在大量的存放在磁盘上的信息中查询一个特定的信息 为了提高效率 一个重要的问题是建立一个好的索引系统
