数据结构–串的定义和基本操作

注:数据结构三要素――逻辑结构、数据的运算、存储结构（物理结构)

$存储结构不同，运算的实现方式不同$

串的定义

$串$，即$字符串(String）$是由零个或多个$字符$组成的有限序列。一般记为s =‘a1a2……a,’ (n ≥0)
其中，S是$串名$，单引号括起来的字符序列是串的值;a;可以是字母、数字或其他字符;串中字符的个数n称为$串的长度$。n =0时的串称为空串（用$\varnothing$表示）。

Eg:
S = "2023/7/2"
T = 'Succeed in the postgraduate entrance examination'

$注:有的地方用双引号（如Java、C)有的地方用单引号（如Python)$

子串:串中任意个$连续的$字符组成的子序列。
主串:包含子串的串。
字符在主串中的位置:字符在串中的序号。
子串在主串中的位置:子串的第一个字符在主串中的位置。
$注意:位序从1开始而不是从0开始$

空串v.s空格串:
M='' M是空串
N=' ' N是由三个空格字符组成的空格串，每个空格字符占1B

串v.S线性表

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

串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等)
串的基本操作，如增删改查等$通常以子串为操作对象$

$通常以“子串”为增删改查的操作对象$

$人类的语言通常要多个字符组成的序列才有现实意义$

串的基本操作

假设有串T=“”，S=“iPhone 11 Pro Max?””，W="Pro"StrAssign(&T,chars):赋值操作。把串T赋值为chars。StrCopy(&T,S):复制操作。由串s复制得到串干。
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。

Eg:
执行基本操作Concat(&T, S,W)后，T="iPhone 11 Pro Max?Pro”
执行基本操作 SubString(&T ,S, 4,6)后，T=“one 11”
执行基本操作Index(s, W)后，返回值为11

串的比较操作

StrCompare(S,T):比较操作。若S>T，则返回值>0;若S=T，则返回值=O;若S<T，则返回值<0。

规则：

从第一个字符开始往后依次对比,先出现更大字符的串就更大
长串的前缀与短串相同时，长串更大
只有两个串完全相同时，才相等

字符集编码

$y=f(x)字符集:函数定义域编码:函数映射规则fy:对应的二进制数$
任何数据存到计算机中一定是二进制数。
需要确定一个字符和二进制数的对应规则这就是“编码”
“字符集”:
英文字符-—ASCII字符集
中英文―—Unicode字符集

$基于同一个字符集,可以有多种编码方案,如:UTF-8，UTF-16$

注:采用不同的编码方式，每个字符所占空间不同，考研中只需默认每个字符占1B即可

拓展:乱码问题

编码规则不同导致

知识点回顾与重要考点