【4.2】字符串存储和算法实现
一、字符串的存储结构
1.1 字符串的顺序存储
对串长变化不大的字符串,有三种处理方案
- 用 S[0] 作为记录串长的存储单元 (Pascal)
- 缺点:限制了串的最大长度不能超过256
- 为存储串的长度,另辟一个存储的地方
- 缺点:串的最大长度一般是静态给定的,不是动态申请 数组空间
- 用一个特殊的末尾标记 ‘\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
个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn