【大学数据结构课件】串

1、内容提要,5.1 串及其操作 串的定义 串的基本操作 5.2 串的表示和实现 顺序存储表示 串的块链存储表示 5.3 串的模式匹配算法 求子串位置的定位函数 模式匹配的一种改进算法 5.4串操作应用举例 文本编辑 建立词索引表,5.1 串及其操作,1、串的逻辑结构定义 串(String)(或字符串)：是由零个或多个字符组成的有限序列。一般记为：s=a1a2an (n0) 其中，s是串的名，用单引号括起来的字符序列是串的值；ai(1 i n)可以是字母、数字或其他字符；串中字符的数目n称为串的长度。零个字符的串称为空串(null string)，它的长度为零。（空串与空格串的区别） 子串：串中任

2、意个连续字符构成的子序列 串相等：当且仅当这两个串的值相等。也就是说，只有当两个串的长度相等，并且各个对应位置的字符串都相等时才相等。,串及其操作(contd),2. 串的基本操作 串的基本操作： 赋值 复制 比较 求长度 串连接 子串定位 取子串 串插入 串删除 串替换,5.2 串的表示和实现,1、字符串的存储表示 (1)顺序存储 利用静态数组存放字符串 (2)堆分配存储 利用动态分配的内存存放字符串 (3)链式存储 块链结构：#define N 5 /N决定存储密度 typedef struct strnode char sdataN; struct strnode *next; STRN

3、ODE;,串的表示和实现(contd),(3)链式存储 块链结构：#define N 5 /N决定存储密度 typedef struct strnode char sdataN; struct strnode *next; STRNODE;,串的表示和实现(contd),2、字符串基本操作的实现 (1)串的联接 利用截尾法进行处理 (2) 求两个串的最长公共子串,串的表示和实现(contd),(2)求两个串的最长公共子串,5.3 串的模式匹配算法,1、字符串模式匹配,普通算法,算法思想： 每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动

4、”进可能远的一段距离后，继续进行比较。,串的模式匹配算法(contd),2. 字符串模式匹配的KMP算法,算法思想： (1)对于象1234abcd这样的模式串，KMP算法与普通算法没有什么不同，但对于123a123b这样的模式串，KMP的算法就尽显优势。也就是说，如果模式串本身包含有自身重复子串，KMP算法会更快。 (2)与普通算法相比，KMP算法在比较失败时，并没有一切推倒重来，而是巧妙利用的模式串“包含重复子串”的特征，减少了比较的次数。,串的模式匹配算法(contd),(3)用大写字母表示子串，小写字母表示串中的字符，假设当比较操作进行到主串S的下标j处时，比较失败。这是模式串T的当前字

5、符的下标时k，并且T0.k=P(Tm)P(Tk),Tm!=Tk, 也就是说，比较失败之前的模式串具有重复子串。这时我们可以将S看成是S=XPaP(Sj)。 面要做的不是将beginpos+，推倒重来，而是直接将Tm与Sj进行比较。这种操作称为模式串的滑动。每当比较失败就滑动一次，这样可以有效减少比较次数。,(4)关键一点是滑动到哪里比较合适，也就是说，如何确定m的值。m被称为k的next值。 (5)如果已知k的next值是m，k+1的next值如何求？这是解决问题的突破口，因为我们已知0的next值是1，1的next值是0.,能者为之,2. 字符串模式匹配的KMP算法,串的模式匹配算法(con

6、td),2. 字符串模式匹配的KMP算法,0 当 j=1时 nextj= Maxk|1kj且p1pk-1=pjj-k+1pjj-1 当此集合不空时 1 其他情况,j 1 2 3 4 5 6 7 8,模式串 a b a a b c a c nextj 0 1 1 2 2 3 1 2,5.4 串操作应用举例,1、文本编辑 文本编辑程序是一个面向用户的系统服务程序，广泛用于源程序的输入和修改，甚至用于报刊和书籍的编辑排版以及办公室的公文书信的起草和润色。 文本编辑的实质是修改字符数据的形式或格式。 各种文本编辑程序的功能强弱不同，但是其基本操作是一致的，一般都包括串的查找、插入和删除等基本操作。 文本编辑程序的设计：用户可以利用换页符和换行符把文本划分为若干页，每页有若干行。可以把文本看承是一个字符串，称为文本串，页则是文本