资源描述：
《国家级精品课程数据结构与算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、国家级精品课程—《数据结构与算法》张铭、赵海燕、王腾蛟、宋国杰、高军http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/北京大学信息科学与技术学院“数据结构与算法”教学小组本章主笔：赵海燕版权所有，转载或翻印必究第4章字符串主要内容字符串基本概念字符串的存储结构字符串运算的算法实现字符串的模式匹配字符串基本概念字符编码字符编码顺序字符串抽象数据类型基本概念字符串，由0个或多个字符/符号的顺序排列所组成的复合数据结构，简称“串”（string）串的长度：一个字符串所包含的字符个数空串：长度为零的串，它不包含任何字符内
2、容特殊的线性表，即元素为字符的线性表n(≥0)个字符的有限序列，一般记作S:“c0c1c2…cn-1”其中，S是串名字“c0c1c2…cn-1”是串值ci是串中的字符n是串的长度（即字符个数），长度为0则为空串字符/符号字符(char)：组成字符串的基本单位取值依赖于字符集Σ（结点的有限集合）二进制字符集：Σ={0,1}生物信息中DNA字符集：Σ={A,C,G,T}英语语言：Σ={26个字符，标点符号，…}简体中文标准字符集GB2312：Σ={6763个汉字，标点符号，…}……字符编码ASCII编码单字节（8bits）对128个符号（字符集charset
3、）进行编码在C和C++中均采用其他编码方式ANSI编码（本地化，GB2312、BIG5、JIS等，不同ANSI编码间互不兼容）UNICODE（国际化，各种语言中的每一个字符具有唯一的数字编号，便于跨平台的文本转换）字符的编码顺序为了字符串间比较和运算的便利，字符编码表一般遵循约定俗成的“偏序编码规则”字符偏序：根据字符的自然含义，某些字符间两两可以比较次序字典序中文字符串有些特例，例如“笔划”序字符串长度理论上，一个字符串的长度是任意且有限的，但在实际的语言中总有一定的长度定长：具有一个固定的最大长度，所用内存量始终如一变长：根据实际需要伸缩。尽管命名为
4、变长，但实际长度也有限（取决于可用的内存量）子串假设s1，s2是两个串：s1=a0a1a2…an-1s2=b0b1b2…bm-1其中0≤m≤n,若存在整数i(0≤i≤n-m)，使得bj=ai+j,j=0,1,…,m-1同时成立，则称串s2是串s1的子串，或称s1包含串s2真子串：非空且不为自身的子串。空串是任意串的子串任意串S都是S本身的子串子串函数提取、插入、寻找、删除…字符串数据类型因语言而不同简单类型复合类型字符串常数和变量字符串常数（stringliteral）例如：“”,“a”，“student”…字符串变量C++的标准string标准字符
5、串：将C/C++的函数库作为字符串数据类型的方案例如：charS[M];定义了字符串变量e.g.,chars1[7]=“value”;串的结束标记：' '‘ ’是ASCII码中8位BIT全0码，又称为NULL符，专门用于结束标志字符串的实际长度为M-1注意：s1=s2C++标准string串长函数intstrlen(char*s);串复制char*strcpy(char*s1,char*s2);串拼接char*strcat(char*s1,char*s2);串比较(注意)intstrcmp(char*s1,char*s2);输入和
6、输出函数cin>>cout<<定位函数char*strchr(char*s,charc);右定位函数char*strrchr(char*s,charc);String抽象数据类型字符串类（classString）：适应字符串长度动态变化的复杂性不再以字符数组charS[M]的形式出现，而采用一种动态变长的存储结构C++String部分操作列表操作类别方法描述子串substr()返回一个串的子串拷贝/交换swap()交换两个串的内容copy()将一个串拷贝到另一个串中赋值assign()把一个串、一个字符、一个子串赋值给另一个串中=把一个串或一个字符赋值给
7、另一个串中插入/追加insert()在给定位置插入一个字符、多个字符或串+=将一个字符或串追加到另一个串后append()将一个或多个字符、或串追加在另一个串后拼接+通过将一个串放置在另一个串后面来构建新串查询find()找到并返回一个子序列的开始位置替换/清除replace()替换一个指定字符或一个串的字串clear()清除串中的所有字符统计size()返回串中字符的数目length()返回size()max_size()返回串允许的最大长度字符串的存储结构和实现字符串的顺序存储字符串类classString的存储结构C++标准串的运算实现String
8、类的运算实现字符串的顺序存储对于串长变化不大的字符串，可以有三种处理方案：（1）
