资源描述：
《数据结构与算法第三章2013》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章字符串3.1字符串抽象数据类型3.2字符串的存储结构和类定义3.3字符串运算的算法实现3.4字符串的模式匹配3.1字符串抽象数据类型3.1.1基本概念3.1.2String抽象数据类型3.1.1基本概念字符串：由0个或多个字符的顺序排列所组成的复合数据结构，简称“串”。串的长度：一个字符串所包含的字符个数。空串：长度为零的串，它不包含任何字符内容。3.1.1.1字符串常数和变量字符串常数例如：""字符串变量3.1.1.2字符字符(char)：组成字符串的基本单位。在C和C＋＋中单字节（8bits）采用ASCII码对128个符号（字符集charset
2、）进行编码3.1.1.3字符的编码顺序为了字符串间比较和运算的便利，字符编码表一般遵循约定俗成的“偏序编码规则”。字符偏序：根据字符的自然含义，某些字符间两两可以比较次序。其实大多数情况下就是字典序中文字符串有些特例，例如“笔划”序3.1.1.4C++标准string标准字符串：将C++的函数库作为字符串数据类型的方案。例如：charS[M];串的结束标记：' '' '是ASCII码中8位BIT全0码，又称为NULL符。3.1.1.4C++标准string(续)1.串长函数intstrlen(char*s);2.串复制char*str
3、cpy(char*s1,char*s2);3．串拼接char*strcat(char*s1,char*s2);4．串比较intstrcmp(char*s1,char*s2);3.1.1.4C++标准string(续)5．输入和输出函数6．定位函数char*strchr(char*s,charc);7．右定位函数char*strrchr(char*s,charc);3.1.1.4C++标准string(续)3.1.2String抽象数据类型字符串类（classString）：不采用charS[M]的形式而采用一种动态变长的存储结构。classString//字
4、符串类//它的存储结构和实现方法使用了C++标准string(简称标准串),//为了区别,类String所派生创建的实例对象,简称‘本串’,或‘实例串’//在程序首,要#include和#include及//及#include，以及#include{//1.字符串的数据表示：//字符串S通常用顺序存放，用数组S[]存储，元素的类型为char//字符串为变长，使用变量size记录串的当前长度//2.使用变量访问字符串：//字符串变量能参与运算,例如S1+S2表示两个字符串首尾拼
5、接在一起//用数组str[]存储字符串，在内部可以用str[i]访问串的第i个字符,//3.字符串类的运算集：请参看下面的成员函数private:char*str;//私有的指针变量，用于指向存储向量str[size+1]intsize；//本串的当前实际长度public:String(char*s=“”);//创建一个空的字符串String(char*s);//创建新字符串，并将标准字符串s拷贝为初值String(constString©);//拷贝构造函数~String()//销毁本串，从计算机存储空间删去本串//下面是算子的定义，包括赋值算子＝
6、拼接算子＋和比较算子<等constString&operator=(constchar*s）；//赋值操作=，标准串s拷贝到本串constString&operator=(constString&s）;//赋值操作=，串s复制到本串Stringoperator＋(char*s）;//拼接算子＋，本串拼接标准串sStringoperator＋(String&s）；//拼接算子＋，本串拼接串sfriendStringoperator+(char*s1,String&s）；//友函数作为拼接算子+其返回值是一个实例串,等于标准串str拼接串s//‘关系’算子，用于
7、比较相等、大、小，例如booloperator<(char*s）;//比较大小,本串小于标准串s则返回非0booloperator<(String&s）;//比较大小，本串小于串s则返回非0friendbooloperator<(char*s1,String&s）；//友函数用于比较,//,标准串s1小于串s,则返回非0//‘输入输出’算子>>和<<以及读子串等，例如友函数friendistream&operator>>(isteream&istr,String&s）；friendostream&operator<<(osteream&ostr,String
8、&s）；//‘子串函数’：插入子串、寻找子串、提取子
