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

一、字符串的存储结构

1.1 字符串的顺序存储

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

  1. 用 S[0] 作为记录串长的存储单元 (Pascal)
  • 缺点:限制了串的最大长度不能超过256
  1. 为存储串的长度,另辟一个存储的地方
  • 缺点:串的最大长度一般是静态给定的,不是动态申请 数组空间
  1. 用一个特殊的末尾标记 ‘\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 成立的所 有可能的条件(其中 + 为连接运算)

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

参考资料

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

这里是一个广告位,,感兴趣的都可以发邮件聊聊:tiehan@sina.cn
个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn