大话数据结构05-串

本文最后更新于：2020年9月28日 上午

代办

  • [ ] KMP算法的代码实现

5.1 开场白

回文诗

枯眼望遥山隔水，往来曾见几心知？

壶空怕酌一杯酒，笔下难成和韵诗。

途路阻人离别久，讯音无雁寄回迟。

孤灯夜守长寥寂，夫忆妻兮父忆儿。

5.2 串的定义

串（string）是由零个或多个字符组成的有限序列，又名叫字符串

  • 空串(null string)：零个字符的串
  • 序列，说明串的相邻字符之间具有前驱和后继的关系。
  • 空格串：只包含空格的串
  • 子串：串中任意个数的连续字符组成的子序列
  • 主串：包含子串的串
  • 子串在主串中的位置就是子串的第一个字符在主串中的序号。

5.3 串的比较

串的比较是通过组成串的字符之间的编码来进行，字符的编码指的是字符在对应字符集中的序号

  • 标准的ASCII编码：由7位二进制数表示一个字符，总共可以表示128个字符
  • 扩展的ASCII码：由8位二进制数表示一个字符，总共可以表示256个字符
  • Unicode编码：由16位的二进制数表示一个字符，前256个字符与ASCII码完全相同

1. 判定两个串的大小

给定两个串：$s=a_1a_2…a_n，t=b_1b_2…b_m$，当满足以下条件之一时，s<t

  • n<m，且$a_i=b_i(i=1,2,…n)$

例如当s=”hap”，t=”happy”，就有s<t。因为t 比 s 多出两个字母

  • 存在某个k<=min(m,n)，使得$a_i=b_i(i=1,2,…k-1),a_k<b_k$

例如s=”happen”，t=”happy”，因为两串的前4个字母均相同，而两串第5个字母（k值）,字母e的ASCII码是101，而字母y的ASCII码是121，显然e<y，所以s<t

5.4 串的抽象数据类型

  • 线性表更关注的是单个元素的操作，比如查找一个元素，插入或删除一个元素
  • 串中更多的是查找子串位置、得到指定位置子串、替换子串等操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ADT 串（String）
Data
	串中元素仅由一个字符组成，相邻元素具有前驱和后继关系。
Operation
	StrAssign(T, *chars); 生成一个其值等于字符串常量 chars 的串 T。
	StrCopy(T, S); 串 S 存在，由串 S 复制得到串 T。
	ClearString(S); 串 S 存在，将串清空
	StringEmpty(S); 若串 S 为空，返回 true 否则返回 false
	StrLength(S); 返回串 S 的元素个数，即串的长度
	StrCompare(S, T); 若 S>T, 返回值>0， 若 S=T, 返回0，若 S < T
	Concat(T, S1, S2); 用 T 返回由 S1 和 S2 链接而成的新串
	SubString(Sub, s, pos, len); 串 S 存在，1 <= pos <= StrLength(S), 且 0<=len<=StrLength(S)-pos+1, 用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。
	Index(S, T, pos); 若 S 和 T 存在，T 是非空串，1<=pos<=StrLength(S)。若主串 S 中存在和 T 值相同的子串，则返回它在主串中第 pos 个字符之后第一次出现的位置，否则返回0 
	Replace(S, T, V); 串 S T 和 V 存在，T 是非空串，用 V 替换主串 S 中出现的所有与 T 相等的不重叠的子串。 
	StrInsert(S, pos, T); 串 S 和 T 存在，1<=pos<=StrLength(S)+1。在串 S 的第 pos 个字符之前插入串 T
	StrDelete(S, pos, len); 串 S 存在，1<=pos<=StrLength(S)-len+1。从串 S 中删除第 pos 个字符起长度为 len 的字符串
endADT

5.5 串的存储结构

1. 串的顺序存储结构

  • 在串值后面加一个不计入串长度的结束标记字符，”\0”表示串值的终结
  • 计算机中存在一个自由存储区，叫做“堆”。这个堆可由 c 语言的动态分配函数 malloc() 和 free() 来管理

2. 串的链式存储结构

串的链式存储结构除了在连接串与串操作时有一定方便之外，总的来说不如顺序存储灵活，性能也不如顺序存储结构好

5.6 朴素的模式匹配算法

子串的定位操作通常称做串的模式匹配

  • 最好的情况：“googlegoof”中去找“google”一开始就匹配成功，时间复杂度为O(1)
  • 稍差一些：”abcdefgoogle”中去找 “google”，时间复杂度为O(n+m)，n 为主串长度，m 为要匹配的子串长度

  • 根据等概率原则，平均是(n+m)/2 次查找，时间复杂度为O(n+m)

  • 最坏的情况，每次不成功的匹配都发生在串 T 的最后一个字符，”00000000001”中去找”0001”，最坏情况的时间复杂度为O((n-m+1)*m)

5.7 KMP模式匹配算法

  • j 值的变化与主串没什么关系，关键取决于T串的结构中是否有重复
  • j 值得多少取决于当前字符之前的串得前后缀得相似度
  • 整个算法的时间复杂度为O(n+m)
  • KMP 算法仅当模式与主串之间存在许多“部分匹配”的情况下才体现出它的优势，否则两者差异并不明显