【Data Structure】串（String）

串（String）

串的基本概念：串是由零个或多个任意字符组成的字符序列。

一般记作：s=‘a1 a2 an’。

  • 其中s是串名，用单引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容；
  • ai(1<=i<=n)是一个任意字符，可以是字母、数字或其它字符，它称为串的元素，是构成串的基本单位，i 是它在整个串中的序号； n为串的长度，表示串中所包含的字符个数，当n=0 时，称为空串，通常记为Ф 。

注意：空串和空白串是有区别的，我们将仅由一个或多个空格 组成的串称为空白串（Blank String）。

子串（Substring）

串中任意个连续字符组成的子序列称为该串的子串；包含子串的串相应地称为主串； 通常将子串在主串中首次出现时的该子串的首字符对应 的主串中的序号，定义为子串在主串中的位置。

例如，设A和B分别为 A=‘This is a string’ B=‘is’ 则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的位置为3。 特别地，空串是任意串的子串，任意串是其自身的子串。

串的抽象数据类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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，返回值<0。
    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值相同的子串，则返回它在主串S中
                                 第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

串的存储结构

串的定长顺序存储表示

我们知道，顺序存储结构（顺序表）的底层实现用的是数组，根据创建方式的不同，数组又可分为静态数组和动态数组，因此顺序存储结构的具体实现其实有两种方式。

通常所说的数组都指的是静态数组，如 str[10]，静态数组的长度是固定的。与静态数组相对应的，还有动态数组，它使用 malloc 和 free 函数动态申请和释放空间，因此动态数组的长度是可变的。

这种存储结构又称为串的顺序存储结构，是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先确定。

使用定长顺序存储结构存储字符串时，需结合目标字符串的长度，预先申请足够大的内存空间。

例如，采用定长顺序存储结构存储 “data.biancheng.net”，通过目测得知此字符串长度为 18（不包含结束符 ‘\0’），因此我们申请的数组空间长度至少为 18。

1
2
3
4
5
6
7
//定长顺序存储结构定义为:
#define MAX_STRLEN 256 
typedef struct
{ 
    char str[MAX_STRLEN] ; 
    int length;
}

定长数组存在一个预定义的最大串长度，一般可以将实际的串长度值保存在数组的0下标位置，也可以是在存储数组的最后一个下标位置。“\0”来表示串值的终结。

img

串的堆分配存储表示

但是，这样定长数组存储串是有问题的，串的两串的连接Concat、新串的插入StrInsert，以及字符串的替换Replace，都有可能使得串序列的长度超过了数组的长度Max-Size。

于是对于串的顺序存储，有一些变化，串值的存储空间可在程序执行过程中动态分配而得。比如在计算机中存在一个自由存储区，叫做“堆”。这个堆可由C语言的动态分配函数malloc()和free()来管理。

特点是：仍然以一组地址连续的存储空间来存储字符串值，但其所需的存储空间是在程序执行过程中动态分配，故是动态的，变长的。

1
2
3
4
5
6
//串的堆式存储结构的类型定义
typedef struct
{ 
    char *ch; /* 若非空,按长度分配,否则为NULL */
    int length; /* 串的长度 */ 
}

串的链式存储表示

串的链式存储结构，与线性表的链式存储结构是相似的。但由于串结构的特殊性，结构中的每个元素数据是一个字符，如果也简单的应用链表存储串值，一个结点对应一个字符，就会存在很大的空间浪费。

因此，一个结点可以存放一个字符，也可以存放多个字符，最后一个结点若是未被占满时，可以用“#”或其他非串值字符补全。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//(1) 块结点的类型定义
#define BLOCK_SIZE 4
typedef struct Blstrtype
{ 
    char data[BLOCK_SIZE] ; 
    struct Blstrtype *next;
}BNODE ;
 
//(2) 块链串的类型定义 
typedef struct
{ 
    BNODE head; /* 头指针 */ 
    int Strlen ; /* 当前长度 */
}

例如，下图所示是用链表存储字符串 shujujiegou，该链表各个节点中可存储 1 个字符：

各节点仅存储 1 个数据元素的链表

同样，下图设置的链表各节点可存储 4 个字符：

各节点可存储 4 个数据元素的链表

从上图可以看到，使用链表存储字符串，其最后一个节点的数据域不一定会被字符串全部占满，对于这种情况，通常会用 ‘#’ 或其他特殊字符（能与字符串区分开就行）将最后一个节点填满。

一个结点存多少个字符才合适就变得很重要，这会直接影响着串处理的效率，需要根据实际情况做出选择。

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

模式匹配/ 字符串匹配算法

字符串匹配

字符串匹配问题的形式定义：

  • 文本（Text）是一个长度为 n 的数组 T[1..n]；
  • 模式（Pattern）是一个长度为 m 且 m≤n 的数组 P[1..m]；
  • T 和 P 中的元素都属于有限的字母表 Σ 表；
  • 如果 0≤s≤n-m，并且 T[s+1..s+m] = P[1..m]，即对 1≤j≤m，有 T[s+j] = P[j]，则说模式 P 在文本 T 中出现且位移为 s，且称 s 是一个有效位移（Valid Shift）。

img

比如上图中，目标是找出所有在文本 T = abcabaabcabac 中模式 P = abaa 的所有出现。该模式在此文本中仅出现一次，即在位移 s = 3 处，位移 s = 3 是有效位移。

常见的字符串匹配算法

解决字符串匹配的算法包括：朴素算法（Naive Algorithm）、Rabin-Karp 算法、有限自动机算法（Finite Automation）、 Knuth-Morris-Pratt 算法（即 KMP Algorithm）、Boyer-Moore 算法、Simon 算法、Colussi 算法、Galil-Giancarlo 算法、Apostolico-Crochemore 算法、Horspool 算法和 Sunday 算法等。

字符串匹配算法的步骤

字符串匹配算法通常分为两个步骤：预处理（Preprocessing）和匹配（Matching）。所以算法的总运行时间为预处理和匹配的时间的总和。

img

上图描述了常见字符串匹配算法的预处理和匹配时间。

Reference

扫一扫，分享到微信