数据结构与算法(第三章)

《数据结构与算法(第三章)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法第三章字符串张铭赵海燕王腾蛟http://db.pku.edu.cn/mzhang/DS/北京大学信息科学与技术学院“数据结构与算法”教学小组©版权所有，转载或翻印必究主要内容¢3.1字符串抽象数据类型¢3.2字符串的存储结构和类定义¢3.3字符串运算的算法实现¢3.4字符串的模式匹配北京大学信息学院©版权所有，转载或翻印必究Page23.1字符串抽象数据类型¢3.1.1基本概念¢3.1.2String抽象数据类型北京大学信息学院©版权所有，转载或翻印必究Page33.1.1基本概念¢字符串，由0个或多个字符的顺序排列所组成的复合数据结构，简称“串”。¢串的

2、长度：一个字符串所包含的字符个数。¢空串：长度为零的串，它不包含任何字符内容。北京大学信息学院©版权所有，转载或翻印必究Page43.1.1.1字符串常数和变量¢字符串常数¢例如：""¢字符串变量北京大学信息学院©版权所有，转载或翻印必究Page53.1.1.2字符¢字符(char)：组成字符串的基本单位。¢在C和C＋＋中¢单字节（8bits）¢采用ASCII码对128个符号（字符集charset）进行编码北京大学信息学院©版权所有，转载或翻印必究Page63.1.1.3字符的编码顺序¢为了字符串间比较和运算的便利，字符编码表一般遵循约定俗成的“偏序编码规则”。¢字符

3、偏序：根据字符的自然含义，某些字符间两两可以比较次序。¢其实大多数情况下就是字典序¢中文字符串有些特例，例如“笔划”序北京大学信息学院©版权所有，转载或翻印必究Page73.1.1.4C++标准string¢标准字符串：将C++的函数库作为字符串数据类型的方案。¢例如：charS[M];¢串的结束标记：''¢''是ASCII码中8位BIT全0码，又称为NULL符。北京大学信息学院©版权所有，转载或翻印必究Page83.1.1.4C++标准string(续)¢1.串长函数intstrlen(char*s);¢2.串复制char*strcpy(ch

4、ar*s1,char*s2);¢3．串拼接char*strcat(char*s1,char*s2);¢4．串比较intstrcmp(char*s1,char*s2);北京大学信息学院©版权所有，转载或翻印必究Page93.1.1.4C++标准string(续)¢5．输入和输出函数¢6．定位函数char*strchr(char*s,charc);¢7．右定位函数char*strrchr(char*s,charc);北京大学信息学院©版权所有，转载或翻印必究Page103.1.1.4C++标准string(续)北京大学信息学院©版权所有，转载或翻印必究Page113.1.2S

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

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

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