4 串
4 串
4 串
1.定义
数据结构中，字符串要单独用一种存储结构来存储，称为串存储结构。这里的串指的就是字符串。
严格意义上讲，串存储结构也是一种线性存储结构，因为字符串中的字符之间也具有"一对一"的逻辑关系。只不过，与之前所学的线性存储结构不同，串结构只用于存储字符类型的数据。
2.一些特殊的串
①空串：存储 0 个字符的串，例如 S = ""（双引号紧挨着）；
②空格串：只包含空格字符的串，例如 S = " "（双引号包含 1 个空格）；
③子串和主串：假设有两个串 a 和 b，如果 a 中可以找到几个连续字符组成的串与 b 完全相同，则称 a 是 b 的主串，b 是 a 的子串。
例如，若 a = "teeyo"，b = "yo"，由于 a 中也包含 "yo"，因此串 a 和串 b 是主串和子串的关系；子串在主串中的位置，指的是子串首个字符在主串中的位置。比如上例中，b在a中的位置是4.
3.串存储结构的具体实现
①定长顺序存储：实际上就是用普通数组（又称静态数组）存储。 char a[10] = "teeyo"；
②堆分配存储：用动态数组存储字符串；
③块链存储：用链表存储字符串；
①定长顺序存储结构，
可以简单地理解为采用 "固定长度的顺序存储结构" 来存储字符串，因此限定了其底层实现只能使用静态数组，需结合目标字符串的长度，预先申请足够大的内存空间。其实就是C/C++中的简单的char数组存储字符串。不在赘述。
②堆分配存储：
堆区的内存空间需要使用
C语言中： malloc 函数申请，并且在不用后要手动通过 free 函数将其释放。
C++中： new 分配动态内存， delete进行回收。
说白了就是建立动态char数组，也不再赘述了。其实C++中已经有string类了。
③块链存储：
指的是使用链表结构存储字符串。
单链表中的 "单" 强调的仅仅是链表各个节点只能有一个指针，并没有限制数据域中存储数据的具体个数。
因此在设计链表节点的结构时，可以令各节点存储多个数据。比如：
typedef struct char_node {
char a1;
char a2;
char a3;
char_node * next;
} node ;
也不赘述了
4.串模式匹配算法之 BF算法
串模式匹配算法，通俗地理解，是一种用来判断两个串之间是否具有"主串与子串"关系的算法。
普通模式匹配算法--BF算法，其实现过程没有任何技巧，就是简单粗暴地拿一个串同另一个串中的字符一一比对，得到最终结果。
假设有子串A， 主串B，那么实现匹配的算法为：
#include<iostream>
#include<cstring>
using namespace std;
int main() {
int match(char * B, char *A);
int result = match("teeyo", "yo");
cout << result << endl;
getchar();
return 0;
}
int match(char * B, char *A) {
int i = 0, j = 0;
while (i<strlen(B) && j<strlen(A)) {
if (B[i] == A[j]) {
i++;
j++;
}
else {
i = i - j + 1;//表示如果有一次不匹配，那么B开始的位置就向后增1
j = 0;//但是子串A还是要从头开始看
}
}
//跳出循环有两种可能，i=strlen(B)说明已经遍历完主串，匹配失败；j=strlen(A),说明子串遍历完成，在主串中成功匹配
if (j == strlen(A)) {
return i - j + 1;
}
//运行到此，为i==strlen(B)的情况
return -1;
}该算法最好情况下的时间复杂度 O(n)，n 表示 子串 A 的长度，即第一次匹配就成功。
BF 算法最坏情况的时间复杂度为 O(n*m)，n 为 子串 A 的长度，m 为主串 B 的长度。例如，串 B 为 xxxxxxxz"，而串 A 为 "xxz"，这种情况下，两个串每次匹配，都必须匹配至串 A 的最末尾才能判断匹配失败，因此运行了 n*m 次。