彩色PDF讲义(3)

《彩色PDF讲义(3)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构与算法第三章字符串张铭http://db.pku.edu.cn/mzhang/DS/北京大学信息科学与技术学院“数据结构与算法”教学小组©版权所有，转载或翻印必究主要内容¢3.1字符串抽象数据类型¢3.2字符串的存储结构和类定义¢3.3字符串运算的算法实现¢3.4字符串的模式匹配backnext北京大学信息学院张铭编写©版权所有，转载或翻印必究Page23.1字符串抽象数据类型¢3.1.1基本概念¢3.1.2String抽象数据类型backnext北京大学信息学院张铭编写©版权所有，转载或翻印必究Page33.1.1基本概念¢字

2、符串，由0个或多个字符的顺序排列所组成的复合数据结构，简称“串”。¢串的长度：一个字符串所包含的字符个数。¢空串：长度为零的串，它不包含任何字符内容。backnext北京大学信息学院张铭编写©版权所有，转载或翻印必究Page43.1.1.1字符串常数和变量¢字符串常数¢例如：""¢字符串变量backnext北京大学信息学院张铭编写©版权所有，转载或翻印必究Page53.1.1.2字符¢字符(char)：组成字符串的基本单位。¢在C和C＋＋中¢单字节（8bits）¢采用ASCII码对128个符号（字符集charset）进行编码back

3、next北京大学信息学院张铭编写©版权所有，转载或翻印必究Page63.1.1.4C++标准string¢标准字符串：将C++的函数库作为字符串数据类型的方案。¢例如：charS[M];¢串的结束标记：''¢''是ASCII码中8位BIT全0码，又称为NULL符。backnext北京大学信息学院张铭编写©版权所有，转载或翻印必究Page73.1.1.4C++标准string(续)¢1.串长函数intstrlen(char*s);¢2.串复制char*strcpy(char*s1,char*s2);¢3．串拼接

4、char*strcat(char*s1,char*s2);¢4．串比较intstrcmp(char*s1,char*s2);backnext北京大学信息学院张铭编写©版权所有，转载或翻印必究Page83.1.1.4C++标准string(续)¢5．输入和输出函数¢6．定位函数char*strchr(char*s,charc);¢7．右定位函数char*strrchr(char*s,charc);backnext北京大学信息学院张铭编写©版权所有，转载或翻印必究Page93.1.2String抽象数据类型¢字符串类（classString

5、）：¢不采用charS[M]的形式¢而采用一种动态变长的存储结构。backnext北京大学信息学院张铭编写©版权所有，转载或翻印必究Page10classString//字符串类//它的存储结构和实现方法使用了C++标准string(简称标准串),//为了区别,类String所派生创建的实例对象,简称‘本串’,或‘实例串’3.1.2String抽象数据类型(续)//在程序首,要#include和#include及//及#include，以及#include

6、>{//1.字符串的数据表示：//字符串S通常用顺序存放，用数组S[]存储，元素的类型为char//字符串为变长，使用变量size记录串的当前长度//2.使用变量访问字符串：//字符串变量能参与运算,例如S1+S2表示两个字符串首尾拼接在一起//用数组str[]存储字符串，在内部可以用str[i]访问串的第i个字符,back//3.字符串类的运算集：请参看下面的成员函数next北京大学信息学院张铭编写©版权所有，转载或翻印必究Page11private:char*str;//私有的指针变量，用于指向存储向量str[size+1]ints

7、ize；//本串的当前实际长度public:String(char*s='');//创建一个空的字符串String(char*s);//创建新字符串，并将标准字符串s拷贝为初值~String()//销毁本串，从计算机存储空间删去本串//下面是函数的定义，包括赋值函数＝拼接函数＋和比较函数<等String&operator=(char*s）；//赋值操作=，标准串s拷贝到本串String&operator=(String&s）;//赋值操作=，串s复制到本串Stringoperator＋(char*s）;//拼接函数＋，本串拼接标准串sS

8、tringoperator＋(String&s）；//拼接函数＋，本串拼接串sfriendStringoperator+(char*s1,String&s）；//友函数作为拼接函数+其返回值是一个实例串,等