出版社
串的存储结构（ 4.1.2 串的存储结构（续）
⑵ 堆存储结构
数据结构C语言描述
这种存储方法仍然以一组地址连续的存储单元存放串的字符 序列，但它们的存储空间是在程序执行过程中动态分配的。系统 序列，但它们的存储空间是在程序执行过程中动态分配的。 将一个地址连续、容量很大的存储空间作为字符串的可用空间， 将一个地址连续、容量很大的存储空间作为字符串的可用空间， 每当建立一个新串时，系统就从这个空间中分配一个大小和字符 每当建立一个新串时， 串长度相同的空间存储新串的串值。 串长度相同的空间存储新串的串值。 在C语言中，存在一个称之为“堆”的自由存储区，并由C语 语言中，存在一个称之为“ 的自由存储区，并由C 言的动态分配函数malloc() free()来管理 利用函数malloc() malloc()和 来管理。 言的动态分配函数malloc()和free()来管理。利用函数malloc() 为每个新产生的串分配一块实际串长所需的存储空间， 为每个新产生的串分配一块实际串长所需的存储空间，若分配成 则返回一个指向起始地址的指针，作为串的基址，同时， 功，则返回一个指向起始地址的指针，作为串的基址，同时，为 了以后处理方便，约定串长也作为存储结构的一部分。 了以后处理方便，约定串长也作为存储结构的一部分。
出版社
MAXLEN
256
<最大串长> 最大串长>
typedef struct
/*串的实际长度* /*串的实际长度*/ 串的实际长度
串的存储结构（ 4.1.2 串的存储结构（续）
数据结构C语言描述
串的实际长度可在这预定义长度的范围内随意， 串的实际长度可在这预定义长度的范围内随意， 超过预定义长度的串值则被舍去，称之为“截断” 超过预定义长度的串值则被舍去，称之为“截断”。 对串长有两种表示方法： 对串长有两种表示方法：一是如上述定义描述的那 以分量存放串的实际长度； 样，以分量存放串的实际长度；二是在串值后面加 一个不计入串长的结束标记字符， 如在有的 C 语言 一个不计入串长的结束标记字符 ， 如在有的C 中以〞 表示串值的终结。此时的串长为隐含值, 中以〞\0〞表示串值的终结 。此时的串长为隐含值, 显然不便于进行某些串操作。 显然不便于进行某些串操作。这时数据类型可以定 义如下： 义如下： typedef char *Sstring1;
出版社
串的存储结构（ 4.1.2 串的存储结构（续）
⑴ 串的顺序存储结构
数据结构C语言描述
串的顺序存储就是把串设计成一种静态结构类型， 串的顺序存储就是把串设计成一种静态结构类型，串的存储分 配是在编译时完成的， 配是在编译时完成的，串中的字符依次存放在一组连续的存 储空间中，也就是用向量来存储串。 储空间中，也就是用向量来存储串。 串的顺序存储结构如下： 串的顺序存储结构如下： #define { ch[MAXLEN+1 char ch[MAXLEN+1]； length； int length； }SString;
(4) StrCompare(S,T)：串的比较。已知串S和T,若S>T，则返回值1；若S=T， ：串的比较。已知串 和 若 ，则返回值 ； ， 数据结构C语言描述 则返回值=0； 则返回值 ；若S<T，则返回值 。 ，则返回值-1。 (5) StrLength(S)求串 的长度。已知串 ，函数返回 串的长度。 求串S的长度 串的长度。 求串 的长度。已知串S，函数返回S串的长度 (6) StrClear(*S)：串S存在，将S清为空串。 存在， 清为空串。 ： 存在 清为空串 (7) Concat(*T,S1,S2)：已知串 和S2，用T返回由 和S2联接而成的新串。 返回由S1和 联接而成的新串 联接而成的新串。 ：已知串S1和 ， 返回由 (8) SubString(*Sub,S,pos,len)：求子串。已知串 ，1≤pos≤StrLength(S)且 ：求子串。已知串S， 且 0≤len≤StrLength(S)-pos+1。用Sub返回串 的第 个字符起长度为 的子串。 返回串S的第 个字符起长度为len的子串 。 返回串 的第pos个字符起长度为 的子串。 (9) StrIndex(S,T,pos)：串的定位。已知串 和T（非空）， ：串的定位。已知串S和 （非空）， 1≤pos≤StrLength(S)。若串 中存在和串 相同的子串，则返回它在主串 中第 中存在和串T相同的子串 。若串S中存在和串 相同的子串，则返回它在主串S中第 pos个字符之后第一次出现的位置；否则函数值返回 。 个字符之后第一次出现的位置； 个字符之后第一次出现的位置 否则函数值返回0。 (10) Replace(*S,T,V)：串的置换。已知串S，T和V，T是非空串，用V替换主 ：串的置换。已知串 ， 和 ， 是非空串， 替换主 是非空串 中出现的所有与T相等的不重叠的子串 串S中出现的所有与 相等的不重叠的子串。 中出现的所有与 相等的不重叠的子串。 (11) StrInsert(*S,pos,T)：串的插入。已知串 和T，1≤pos≤StrLength(S)+1。 ：串的插入。已知串S和 ， 。 在串S的第 个字符之前插入串T。 的第pos个字符之前插入串 在串 的第 个字符之前插入串 。 (12) StrDelete(*S,pos,len)串的删除。已知串 ，1≤pos≤StrLength(S)-len+1，在 串的删除。 串的删除 已知串S， ， 中删除第pos个字符起长度为 的子串。 串S中删除第 个字符起长度为 的子串。 中删除第 个字符起长度为len的子串 (13) StrDestroy (*S)已知串 ，将S销毁释放内存空间。 已知串S， 销毁释放内存空间。 已知串 销毁释放内存空间 }ADT String 出版社
出版社
串的存储结构（ 4.1.2 串的存储结构（续） typedef struct { char int
数据结构C语言描述
*ch；/*若是非空串 则按串长分配存储区，否则ch 若是非空串， ch为 *ch；/*若是非空串，则按串长分配存储区，否则ch为NULL length； length； /* 串长度 */
*/
}HString； }HString； 这种存储结构表示时的串操作仍是基于“ 这种存储结构表示时的串操作仍是基于“字符 序列的复制”进行的。 序列的复制”进行的。
出版社
串的存储结构（ 4.1.2 串的存储结构（续）
⑶ 串的块链存储表示
数据结构C语言描述
由于串也是一种线性表，因此也可以采用链式存储。 由于串也是一种线性表，因此也可以采用链式存储。由 于串的特殊性(每个元素只有一个字符) 在具体实现时， 于串的特殊性(每个元素只有一个字符)，在具体实现时，每 个结点既可以存放一个字符，也可以存放多个字符。 个结点既可以存放一个字符，也可以存放多个字符。每个结 点称为块，整个链表称为块链结构，为了便于操作， 点称为块，整个链表称为块链结构，为了便于操作，再增加 一个尾指针。结点大小为数据域中存放字符的个数。 一个尾指针。结点大小为数据域中存放字符的个数。 例如， 4.1(a)是结点大小为4(即每个结点存放4 例如，图4.1(a)是结点大小为4(即每个结点存放4个字 是结点大小为4(即每个结点存放 的链表， 4.1(b)是结点大小为 的链表。 是结点大小为1 符)的链表，图4.1(b)是结点大小为1的链表。当结点大小大 由于串长不一定是结点大小的整倍数， 于1时，由于串长不一定是结点大小的整倍数，则链表中的 最后一个结点不一定全被串值占满，此时通常补上〞 最后一个结点不一定全被串值占满，此时通常补上〞#〞或 其他的非串值字符(通常“ 不属于串的字符集 不属于串的字符集， 其他的非串值字符(通常“#”不属于串的字符集，是一个特 殊的符号) 殊的符号)。
出版社
串的基本概念（ 4.1.1 串的基本概念（续）

数据结构C语言描述
当两个串的长度相等，并且各个对应位置的字符都相同时，称这两个串相等。 当两个串的长度相等， 并且各个对应位置的字符都相同时，称这两个串相等。 串的数据对象是字符集合，一系列连续的字符就组成一个串。学习线性表后， 串的数据对象是字符集合，一系列连续的字符就组成一个串。学习线性表后， 也许你会觉得串也是一种线性表，串的逻辑结构和线性表极为相似， 也许你会觉得串也是一种线性表，串的逻辑结构和线性表极为相似，但由 于串有某些特征而不同线性表（ 于串有某些特征而不同线性表（操作的对象不是单个数据元素而是若干个 元素—既子串 既子串） 故独立讨论。 元素 既子串），故独立讨论。 串的抽象数据类型定义如下： 串的抽象数据类型定义如下： ADT String{ 数据对象： 数据对象：D={ai|ai∈CharacterSet,i=1,2,...,n, n≥0} ∈ 数据关系： 数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n} ∈ 基本操作： 基本操作： (1) StrAssign(*T,charconstant)：串赋值。charconstant是字符串常量， 是字符串常量， ：串赋值。 是字符串常量 生成一个其值等于charconstant的串 。 的串T。 生成一个其值等于 的串 (2) StrCopy(*T,S)：串复制。已知串 ，将串 的内容复制到串 中。 的内容复制到串T中 ：串复制。已知串S，将串S的内容复制到串 (3) StrEmpty(S)：判断串 是否为空，若S为空，则返回真 是否为空， 为空， ：判断串S是否为空 为空 则返回真TRUE，否则 ， 返回 FALSE。 。 出版社
4.1.2 串的存储结构
数据结构C语言描述
线性表有顺序和链式存储结构、对于串都是适 用的。但任何一种存储结构对于串的不同运算并非 都是十分有效的。对于串的插入和删除操作，顺序 存储结构是不方便的，而链式存储结构则显得方便 些。如果访问串中单个字符。对链表来说是不困难 的；当要访问一组连续的字符时，则用链式存储结 构要比用顺序存储结构麻烦。所以应针对不同的应 用来选择串的存储结构。另外，串的存储结构和具 体的计算机的编址方式也有密切的关系。因此，选 用串的存储方式要考虑的因素是较多的，下面作一 些大致的分析。