数据结构--串

串的定义：串（string）是由零个或多个字符组成的有限序列，又名叫字符串。零个字符的串称为空串（null string）。

还有一些特别的字符串：

空格串：只包含空格的串。

子串与主串，串中任意个数的连续字符组成的子序列称为该串的子串，相应地，包含子串的串称为主串。

串有两种存储结构，静态和动态，静态的存储结构一般使用一组地址连续的存储单元来存储，例如数组。使用数组，就需要在初始分配一个固定长度的存储区域，这样就有可能使：两串的连接、新串的插入、以及字符串的替换的 *** 作，超过数组的长度。为了解决这个问题，可以动态分配串的存储空间，使用链表结构（一般情况下，对串的 *** 作基本上是从头到尾顺序扫描，因此无需使用双向链表）。

常用的串有7种基本 *** 作：

1赋值，2判等（串的比较是通过比较字符的ASCII来进行的），3求长，4链接，5求字串，6定位，7置换

下面来说说在静态存储方式下，链接，求子串，求子串位置的 *** 作

举个例子：

主串S：a b a b c a b c a c b a b，子串T：a b c m c

当i=3，S[i]=b，当j=3，T[j]=m，发现子串与主串不相等了，这时不用从i=1，j=0从头开始比较，根据此轮比较发现主串与子串0-2的字符是相等的，而且0-2的字符也不是重复的，所以T[0]也就无需在和S[1]，S[2]进行比较了，i可以直接向右滑动到3，继续同T进行比较，在整个匹配过程中，i的指针没有回溯，减少了运行时间。

你说的awk

index

如何测试一个字符串在另外一个字符串里？比如a="11"，b="11

22

33

44"，如何判断a是否存在与b中？这就需要用index()函数。我们讲一个例子：

文件a:

36

18

19

70

97

66

71

13

23

48

23

68

88

11

12

文件b:

97

19

18

36

18

28

71

53

24

33

48

13

66

25

55

12

11

75

36

23

19

要求文件a里对应文件b里的行，如果文件a里出现过的数字，在文件b里标记出来。

$

awk

'{getline

v<"a";for(i=1;i<=NF;i++)if(index(v,$i))$i="-"$i}1'

b

-97

-19

-18

-36

-18

28

71

53

24

33

-48

-13

-66

25

55

-12

-11

75

36

-23

19

[解析]

index(s,

t)

Returns

the

index

of

the

string

t

in

the

string

s

返回t字符串存在与s字符串中位置的正整数，不存在则返回0。

awk

'ARGIND==1{for(i=1;i<=NF;i++)a[FNR","$i];next}{for(i=1;i<=NF;i++){FNR","$i

in

a$i="-"$i:0}}1'

a

b

串，即字符串（String）是由零个或多个字符组成的有限序列。一般记为S = ‘a1a2······an' （n ≥0）其中，S是串名，单引号括起来的字符序列是串的值；ai可以是字母、数字或其他字符；串中字符的个数n称为串的长度。n = 0时的串称为空串（用∅表示）。

S=”HelloWorld!”

T=‘iPhone 11 Pro Max’

子串：串中任意个连续的字符组成的子序列。 Eg：’iPhone’，’Pro M’ 是串T 的子串。

主串：包含子串的串。 Eg：T 是子串’iPhone’的主串。

字符在主串中的位置：字符在串中的序号。 Eg：’1’在T中的位置是8(第一次出现)

子串在主串中的位置：子串的第一个字符在主串中的位置 。 Eg：’11 Pro’在 T 中的位置为8

串是一种特殊的线性表，数据元素之间呈线性关系。

串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）

串的基本 *** 作，如增删改查等通常以子串为 *** 作对象。

假设有串T=“”，S=”iPhone 11 Pro Max”，W=“Pro”

StrAssign(&T,chars)：赋值 *** 作。把串T赋值为chars。

StrCopy(&T,S)：复制 *** 作。由串S复制得到串T。

StrEmpty(S)：判空 *** 作。若S为空串，则返回TRUE，否则返回FALSE。

StrLength(S)：求串长。返回串S的元素个数。

ClearString(&S)：清空 *** 作。将S清为空串。

DestroyString(&S)：销毁串。将串S销毁（回收存储空间）。

Concat(&T,S1,S2)：串联接。用T返回由S1和S2联接而成的新串

SubString(&Sub,S,pos,len)：求子串。用Sub返回串S的第pos个字符起长度为len的子串。

Index(S,T)：定位 *** 作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的

位置；否则函数值为0。

StrCompare(S,T)：比较 *** 作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0。

串的模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置。

Index(S,T)：定位 *** 作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0。

若模式串长度为m，主串长度为n，则

匹配成功的最好时间复杂度：O(m)

匹配失败的最好时间复杂度：O(n-m+1) = O(n-m)≈O(n)

若模式串长度为m，主串长度为n，则直到匹配成功/匹配失败最多需要 (n-m+1)m 次比较

最坏时间复杂度：O(nm)

串的模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置。

朴素模式匹配算法（简单模式匹配算法）思想：

将主串中与模式串长度相同的子串搞出来，挨个与模式串对比

当子串与模式串某个对应字符不匹配时，就立即放弃当前子串，转而检索下一个子串

若模式串长度为m，主串长度为n，则直到匹配成功/匹配失败最多需要 (n-m+1)m 次比较

最坏时间复杂度：O(nm)

最坏情况：每个子串的前m-1个字符都和模式串匹配，只有第m个字符不匹配

比较好的情况：每个子串的第1个字符就与模式串不匹配

简单模式匹配算法的最坏情况：若模式串长度为m，主串长度为n，则直到匹配成功/匹配失败最多需要 nm 次比较最坏时间复杂度：O(nm)

朴素模式匹配算法的缺点：当某些子串与模式串能部分匹配时，主串的扫᧿指针 i 经常回溯，导致时间开销增加。

改进思路：主串指针不回溯，只有模式串指针回溯。

朴素模式匹配算法的缺点：当某些子串与模式串能部分匹配时，主串的扫描指针 i 经常回溯，导致时间开销增加。最坏时间复杂度O(nm)

KMP算法：当子串和模式串不匹配时，主串指针 i 不回溯，模式串指针 j=next[j]

算法平均时间复杂度：O(n+m)

如果不会经常出现子串与模式串部分匹配问题，那么KMP算法也没屌多少

next数组手算方法：当第j个字符匹配失败，由前 1~j-1 个字符组成的串记为S，则：next[j]=S的最长相等前后缀长度+1

特别地，next[1]=0

nextval数组的求法：

先算出next数组

先令nextval[1]=0

for (int j=2; j<=Tlength; j++) {

if(Tch[next[j]]==Tch[j])

nextval[j]=nextval[next[j]];

else

nextval[j]=next[j];

}

KMP算法优化：当子串和模式串不匹配时j=nextval[j];