【4.2】字符串存储和算法实现

一、字符串的存储结构

1.1 字符串的顺序存储

对串长变化不大的字符串，有三种处理方案

1. 用 S[0] 作为记录串长的存储单元 (Pascal)

• 缺点:限制了串的最大长度不能超过256

2. 为存储串的长度，另辟一个存储的地方

• 缺点:串的最大长度一般是静态给定的，不是动态申请 数组空间

3. 用一个特殊的末尾标记 ‘\0’ (C/C++)

• 例如:C/C++ 语言的 string 函数库 (#include <string.h>)采用这一存储结构
• ‘\0’ 的 ASCII 字符表中编号为 0，等价于常量 、 数字 、常量false

1.2 字符串类的存储结构

private: // 具体实现的字符串存储结构
char *str; // 字符串的数据表示
int  size; // 串的当前长度

例如：

String s1 = "Hello"

二、字符串运算的算法实现

串长函数  int strlen(char *s);
串复制   char *strcpy(char *s1, char*s2);
串拼接   char *strcat(char *s1, char *s2);
串比较   int strcmp(char *s1, char *s2);

串运算的实现：

更简便的算法

三、思考

String抽取子串

s2 = s1.Substr(6, 5) ;

设 S1, S2 为串，请给出使 S1+S2 == S2+S1 成立的所 有可能的条件(其中 + 为连接运算)

设计一个算法来实现字符串逆序存储，要求不另设串存 储空间

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾