数据结构：串（定义，基本操作，存储结构）

目录

1.串的定义

串，即

字符串

( String）是由零个或多个字符组成的有限序列。
一般记为s = ‘a1a2……an’ (n ≥0)
其中，S是

串名

，单引号括起来的字符序列是串的值;
ai可以是字母、数字或其他字符;
串中字符的个数n称为

串的长度

。
n = 0时的串称为

空串

，用

      ∅ 
     
    
   
     \emptyset 
    
   
 ∅表示。

①子串:串中任意个

连续

的字符组成的子序列。
②主串:包含子串的串。
③字符在主串中的位置:字符在串中的序号。
④子串在主串中的位置:子串的第一个字符在主串中的位置。

串是一种特殊的线性表，数据元素之间呈线性关系。
串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等)
串的基本操作，如增删改查等通常

以子串为操作对象

。

2.串的基本操作

①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。

3.字符集编码

每个字符在计算机中对应一个二进制数，比较字符的大小其实就是比较二进制数的大小。
常见的编码方式可以看博主的这篇博客：https://blog.csdn.net/qq_61888137/article/details/131026013

4.串的存储结构

1.顺序存储

①静态数组实现(

定长

顺序存储)
方案1：定义结构体，使用变量length记录数组长度。
方案2：char[0]记录数组的长度，优点:

字符的位序和数组下标相同

。
方案3：没有Length变量,以字符\0’表示结尾(对应ASCII码的0），缺点是需要遍历所有字符串获取长度。

②动态数组实现(

堆分配

存储)，用完需要手动free。

2.链式存储

①每个结点存储一个字符

②每个结点存多个字符，没有字符的位置用’#'或"\0’补足