数据结构与算法（四）
张铭  主讲  采用教材：张铭，王腾蛟，赵海燕 编写 高等教育出版社，2008. 6 （“十一五”国家级规划教材）
张铭《数据结构与算法》
字符串
主要内容
目录页
主要内容•字符串基本概念
•字符串的存储结构
–字符串的顺序存储
–字符串类 class String 的存储结构•字符串运算的算法实现
–字符串运算的实现
–String 类的实现
•字符串的模式匹配
–朴素算法
–KMP 快速模式匹配
字符串的顺序存储
•对串长变化不大的字符串，有三种处理方案
1.用 S[0] 作为记录串长的存储单元 (Pascal)
–缺点：限制了串的最大长度不能超过256
2.为存储串的长度，另辟一个存储的地方
–缺点：串的最大长度一般是静态给定的，不是动态申请
数组空间
3.用一个特殊的末尾标记‘\0’  (C/C++)
–例如：C/C++ 语言的 string 函数库（＃include
<string.h>）采用这一存储结构
–‘\0’的 ASCII 字符表中编号为 0，等价于常量NULL、数字0、常量false
字符串类的存储结构private:  // 具体实现的字符串存储结构char *str; // 字符串的数据表示
int size;  // 串的当前长度
例如，
String s1 = "Hello";
private:字符串长度和字节
char  *str;
int  size;  // 值为5
……
字符串运算的算法实现•串长函数
–int strlen(char  *s);
•串复制
–char *strcpy(char  *s1, char*s2); •串拼接
–char *strcat(char  *s1, char  *s2); •串比较
–int  strcmp(char *s1, char *s2);

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。