数据结构与算法（C++版）课件第4章 串.ppt

《数据结构与算法（C++版）课件第4章 串.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法（C++版）课件第4章 串.ppt（69页珍藏版）》请在汇文网上搜索。

1、第第4章章串串数据结构与算法数据结构与算法(C+版版)(第第2版版)4.1串类型的定义串类型的定义一、串的定义一、串的定义n(n=0)n(n=0)个字符的有限序列个字符的有限序列s=s=a a1 1,a,a2 2,a,an n 串名串名:s:s 串值串值:a:ai i(1i n)(1i n)串长串长:n:n二、串的基本术语二、串的基本术语空空 串串n=0n=0的串的串子子 串串串中若干相邻字符组成的子序列串中若干相邻字符组成的子序列主主 串串包含子串的串包含子串的串空格串空格串仅含有空格字符的串仅含有空格字符的串(n(n不为不为0)0)串相等串相等设设 s s1 1=a a1111,a,an1

2、n1 s s2 2=a a1212,a,an2n2 若若 n1=n2n1=n2且且a ai1i1=a=ai2i2（1 1i in1)n1)则则 s s1 1=s=s2 21voidCopy(CharString&target,constCharString&source)初始条件：串初始条件：串source已存在。已存在。操作结果：将串操作结果：将串source复制得到一个串复制得到一个串target。2boolEmpty()const初始条件：串已存在。初始条件：串已存在。操作结果：如串为空，则返回操作结果：如串为空，则返回true，否则返，否则返回回false。3intLength()co

3、nst初始条件：串已存在。初始条件：串已存在。操作结果：返回串的长度，即串中的字符个操作结果：返回串的长度，即串中的字符个数。数。三、串的基本术语三、串的基本术语4voidConcat(CharString&target,constCharString&source)初始条件：串初始条件：串target和和source已存在。已存在。操作结果：将串操作结果：将串source联接到串联接到串target的后面。的后面。5CharStringSubString(constCharString&s,intpos,intlen)初始条件：串存在，且初始条件：串存在，且0poss.Length()，0l

4、ens.Length()pos。操作结果：返回从第操作结果：返回从第pos个字符开始长度为个字符开始长度为len的子串。的子串。6intIndex(constCharString&target,constCharString&pattern,intpos=0)初始条件：目标串初始条件：目标串target和模式串和模式串pattern都都存在，模式串存在，模式串pattern非空，且非空，且0pos target.Length()。操作结果：返回目标串操作结果：返回目标串target中第中第pos个字符个字符后第一次出现的模式串后第一次出现的模式串pattern的位置。的位置。4.2字符串的实现

5、字符串的实现在在C+在头文件在头文件string中已含了一种中已含了一种安全的字符串实现安全的字符串实现由于这个库没有包含在一些较老的由于这个库没有包含在一些较老的C+编译器中，因此本节将设计自已编译器中，因此本节将设计自已的安全的的安全的CharString类，使用面向对类，使用面向对象技术来克服象技术来克服C风格的串中存在的问风格的串中存在的问题。题。一、串类及串相关操作一、串类及串相关操作/串类串类串类串类classCharStringclassCharString protected:protected:/串实现的数据成员串实现的数据成员串实现的数据成员串实现的数据成员:char*st

6、rVal;char*strVal;/串值串值串值串值intlength;intlength;/串长串长串长串长public:public:/抽象数据类型方法声明及重载编译系统默认方法声明抽象数据类型方法声明及重载编译系统默认方法声明抽象数据类型方法声明及重载编译系统默认方法声明抽象数据类型方法声明及重载编译系统默认方法声明:CharString();CharString();/构造函数构造函数构造函数构造函数 virtualCharString();virtualCharString();/析构函数析构函数析构函数析构函数CharString(constCharString&source);C

7、harString(constCharString&source);/复制构造函数复制构造函数复制构造函数复制构造函数CharString(constchar*source);CharString(constchar*source);/从从从从C C风格串转换的构造函数风格串转换的构造函数风格串转换的构造函数风格串转换的构造函数CharString(LinkList&source);CharString(LinkList&source);/从线性表转换的构造函数从线性表转换的构造函数从线性表转换的构造函数从线性表转换的构造函数intLength()const;intLength()const;

8、/求串长度求串长度求串长度求串长度boolEmpty()const;boolEmpty()const;/判断串是否为空判断串是否为空判断串是否为空判断串是否为空CharString&operator=(constCharStringCharString&operator=(constCharString&source);&source);/重载赋值运算符重载赋值运算符重载赋值运算符重载赋值运算符constchar*ToCStr()const;constchar*ToCStr()const;/将串转换成将串转换成将串转换成将串转换成C C风格串风格串风格串风格串constchar&operato

9、r(inti)const;constchar&operator(inti)const;/重载下标运算符重载下标运算符重载下标运算符重载下标运算符;串相关操作串相关操作串相关操作串相关操作CharStringRead(istream&input);CharStringRead(istream&input);/从输入流读入串从输入流读入串从输入流读入串从输入流读入串CharStringRead(istream&input,char&terminalChar);CharStringRead(istream&input,char&terminalChar);/从输入流读入串从输入流读入串从输入流读入串

10、从输入流读入串,用用用用terminalCharterminalChar返回串结束字符返回串结束字符返回串结束字符返回串结束字符voidWrite(constCharString&s);voidWrite(constCharString&s);/输出串输出串输出串输出串char*CStrConcat(char*target,constchar*source);char*CStrConcat(char*target,constchar*source);/C/C风格将串风格将串风格将串风格将串sourcesource连接到串连接到串连接到串连接到串targettarget的后面的后面的后面的后面v

11、oidConcat(CharString&target,voidConcat(CharString&target,constCharString&source);constCharString&source);/将串将串将串将串sourcesource连接到串连接到串连接到串连接到串targettarget的后面的后面的后面的后面串相关操作串相关操作串相关操作串相关操作char*CStrCopy(char*target,constchar*source);char*CStrCopy(char*target,constchar*source);/C/C风格将串风格将串风格将串风格将串source

12、source复制到串复制到串复制到串复制到串targettargetvoidCopy(CharString&target,voidCopy(CharString&target,constCharString&source);constCharString&source);/将串将串将串将串sourcesource复制到串复制到串复制到串复制到串targettargetchar*CStrCopy(char*target,constchar*source,intn);char*CStrCopy(char*target,constchar*source,intn);/C/C风格将串风格将串风格将串风

13、格将串sourcesource复制复制复制复制n n个字符到串个字符到串个字符到串个字符到串targettargetvoidCopy(CharString&target,voidCopy(CharString&target,constCharString&source,intn);constCharString&source,intn);/将串将串将串将串sourcesource复制复制复制复制n n个字符到串个字符到串个字符到串个字符到串targettargetintIndex(constCharString&target,intIndex(constCharString&target,co

14、nstCharString&pattern,intpos=0);constCharString&pattern,intpos=0);/查找模式串查找模式串查找模式串查找模式串patternpattern第一次在目标串第一次在目标串第一次在目标串第一次在目标串targettarget中从第中从第中从第中从第/pos/pos个字符开始出现的位置个字符开始出现的位置个字符开始出现的位置个字符开始出现的位置CharStringSubString(constCharString&s,CharStringSubString(constCharString&s,intpos,intlen);intpos,i

15、ntlen);/求串求串求串求串s s的第的第的第的第pospos个字符开始的长度为个字符开始的长度为个字符开始的长度为个字符开始的长度为lenlen的子串的子串的子串的子串booloperator=(constCharString&first,booloperator=(constCharString&first,constCharString&second);constCharString&second);/重载关系运算符重载关系运算符重载关系运算符重载关系运算符=booloperator(constCharString&first,booloperator(constCharString

16、&first,constCharString&second);constCharString&second);/重载关系运算符重载关系运算符重载关系运算符重载关系运算符(constCharString&first,booloperator(constCharString&first,constCharString&second);constCharString&second);/重载关系运算符重载关系运算符重载关系运算符重载关系运算符 booloperator=(constCharString&first,booloperator=(constCharString&first,constCha

17、rString&second);constCharString&second);/重载关系运算符重载关系运算符重载关系运算符重载关系运算符=(constCharString&first,booloperator=(constCharString&first,constCharString&second);constCharString&second);/重载关系运算符重载关系运算符重载关系运算符重载关系运算符=booloperator!=(constCharString&first,booloperator!=(constCharString&first,constCharString&sec

18、ond);constCharString&second);/重载关系运算符重载关系运算符重载关系运算符重载关系运算符!=!=二、串类部分成员函数的实现二、串类部分成员函数的实现1.串构造函数串构造函数(1)CharString:CharString(constchar*source)CharString:CharString(constchar*source)/操作结果：从操作结果：从操作结果：从操作结果：从C C风格串转换构造新串风格串转换构造新串风格串转换构造新串风格串转换构造新串转换构造函数转换构造函数转换构造函数转换构造函数 length=strlen(source);/串长串长str

19、Val=newcharlength+1;/分配存储空间分配存储空间CStrCopy(strVal,source);/复制串值复制串值 2.2.串构造函数串构造函数(2)(2)CharString:CharString(LinkList&source)/操作结果：从线性表转换构造新串操作结果：从线性表转换构造新串转换构造函数转换构造函数length=source.Length();/串长串长strVal=newcharlength+1;/分配存储空间分配存储空间for(inti=0;ilength;i+)/复制串值复制串值source.GetElem(i+1,strVali);strVallen

20、gth=0;/串值以串值以0结束结束3.将将C+串转换为串转换为C语言串语言串constchar*CharString:ToCStr()constconstchar*CharString:ToCStr()const/操作结果：将串转换成操作结果：将串转换成操作结果：将串转换成操作结果：将串转换成C C风格串风格串风格串风格串 return(constchar*)strVal;return(constchar*)strVal;/串值类型转换串值类型转换串值类型转换串值类型转换 4.串比较实现串比较实现booloperator=(constCharString&first,booloperator

21、=(constCharString&first,constCharString&second)constCharString&second)/操作结果：重载关系运算符操作结果：重载关系运算符操作结果：重载关系运算符操作结果：重载关系运算符=returnstrcmp(first.ToCStr(),second.ToCStr()=returnstrcmp(first.ToCStr(),second.ToCStr()=0;0;booloperator(constCharString&first,booloperator(constCharString&first,constCharString&se

22、cond)constCharString&second)/操作结果：重载关系运算符操作结果：重载关系运算符操作结果：重载关系运算符操作结果：重载关系运算符 returnstrcmp(first.ToCStr(),second.ToCStr()0;returnstrcmp(first.ToCStr(),second.ToCStr()“属性属性”菜单，打开菜单，打开“属性页属性页”对话框。对话框。2、在、在“预处理器定义预处理器定义”列表中选择列表中选择“编辑编辑”，在弹出的，在弹出的对话框中添加对话框中添加“_CRT_SECURE_NO_WARNINGS”。补例补例4.1测试方法测试方法1。/文

23、件路径名文件路径名:a4_1main.cpp#include/编译预处理命令编译预处理命令#include/“cstring”和和“string.h”/为为C头文件，包含字符串相关函数的声明头文件，包含字符串相关函数的声明usingnamespacestd;/使用命名空间使用命名空间stdintmain()chardest100=destination,src100=source;/定义变量定义变量strcpy(dest,src);/调用调用strcpy()函数函数coutstrcpy(dest,src):dest:destendl;/显示相关信息显示相关信息说明：说明：说明：说明：补例补例补

24、例补例4.14.1在在在在DevC+5.11DevC+5.11、Code:Blocks20.03Code:Blocks20.03、VC6.0VC6.0及及及及VC2022VC2022等环境中通过测试。等环境中通过测试。等环境中通过测试。等环境中通过测试。strncpy(dest,src,4);/调用调用strncpy()函数函数dest4=0;/手动加上终止符手动加上终止符coutstrncpy(dest,src,4):dest:destendl;/显示相关信息显示相关信息strcpy(dest,Hello);/复制串复制串Hellostrcpy(src,world);/复制串复制串world

25、strcat(dest,src);/调用调用strcat()函数函数coutstrcat(dest,src):dest:destendl;/显示相关信息显示相关信息return0;/返回值返回值0,返回操作系统返回操作系统程序运行时屏幕输出如下：程序运行时屏幕输出如下：strcpy(dest,src):dest:sourcestrncpy(dest,src,4):dest:sourstrcat(dest,src):dest:Helloworld方法方法2：在文件开头添加如下命：在文件开头添加如下命令，禁止对代号为令，禁止对代号为4996的警告。的警告。#pragmawarning(disabl

26、e:4996)补例补例4.2测试方法测试方法2。/文件路径名文件路径名:a4_2main.cpp#include/编译预处理命令编译预处理命令#include/“cstring”和和“string.h”/为为C头文件，包含字符串相关函数的声明头文件，包含字符串相关函数的声明usingnamespacestd;/使用命名空间使用命名空间std#pragmawarning(disable:4996)/在文件开头添在文件开头添/加此命令，禁止对代号为加此命令，禁止对代号为4996的警告的警告说明：说明：说明：说明：补例补例补例补例4.24.2在在在在DevC+5.11DevC+5.11、Code:B

27、locks20.03Code:Blocks20.03、VC6.0VC6.0及及及及VC2022VC2022等环境中通过测试。等环境中通过测试。等环境中通过测试。等环境中通过测试。intmain()chardest100=destination,src100=source;/定义变量定义变量strcpy(dest,src);/调用调用strcpy()函数函数coutstrcpy(dest,src):dest:destendl;/显示相关信息显示相关信息strncpy(dest,src,4);/调用调用strncpy()函数函数dest4=0;/手动加上终止符手动加上终止符coutstrncpy(

28、dest,src,4):dest:destendl;/显示相关信息显示相关信息strcpy(dest,Hello);/复制串复制串Hellostrcpy(src,world);/复制串复制串worldstrcat(dest,src);/调用调用strcat()函数函数coutstrcat(dest,src):dest:destendl;/显示相关信息显示相关信息return0;/返回值返回值0,返回操作系统返回操作系统程序运行时屏幕输出如下：程序运行时屏幕输出如下：strcpy(dest,src):dest:sourcestrncpy(dest,src,4):dest:sourstrcat(d

29、est,src):dest:Helloworld方法方法3：在文件中所有预处理命：在文件中所有预处理命令之前加上如下命令，禁止相关令之前加上如下命令，禁止相关安全类的警告。安全类的警告。#define_CRT_SECURE_NO_WARNINGS补例补例4.3测试方法测试方法3。/文件路径名文件路径名:a4_3main.cpp#define_CRT_SECURE_NO_WARNINGS/在文在文/件中所有预处理命令之前加上此命令，禁止相件中所有预处理命令之前加上此命令，禁止相/关安全类的警告关安全类的警告#include/编译预处理命令编译预处理命令#include/“cstring”和和“s

30、tring.h”/为为C头文件，包含字符串相关函数的声明头文件，包含字符串相关函数的声明usingnamespacestd;/使用命名空间使用命名空间std说明：说明：说明：说明：补例补例补例补例4.34.3在在在在DevC+5.11DevC+5.11、Code:Blocks20.03Code:Blocks20.03、VC6.0VC6.0及及及及VC2022VC2022等环境中通过测试。等环境中通过测试。等环境中通过测试。等环境中通过测试。intmain()chardest100=destination,src100=source;/定义变量定义变量strcpy(dest,src);/调用调用

31、strcpy()函数函数coutstrcpy(dest,src):dest:destendl;/显示相关信息显示相关信息strncpy(dest,src,4);/调用调用strncpy()函数函数dest4=0;/手动加上终止符手动加上终止符coutstrncpy(dest,src,4):dest:destendl;/显示相关信息显示相关信息strcpy(dest,Hello);/复制串复制串Hellostrcpy(src,world);/复制串复制串worldstrcat(dest,src);/调用调用strcat()函数函数coutstrcat(dest,src):dest:destend

32、l;/显示相关信息显示相关信息return0;/返回值返回值0,返回操作系统返回操作系统程序运行时屏幕输出如下：程序运行时屏幕输出如下：strcpy(dest,src):dest:sourcestrncpy(dest,src,4):dest:sourstrcat(dest,src):dest:Helloworld方法方法4：用：用strcpy_s()、strncpy_s()和和strcat_s()函数代替函数代替strcpy()、strncpy()和和strcat()函数，函数，strcpy_s()、strncpy_s()和和strcat_s()函数声明如下函数声明如下errno_tstrcp

33、y_s(char*dest,*size_tdestsz,constcharerrno_tstrcpy_s(char*dest,*size_tdestsz,constchar*src);*src);errno_tstrncpy_s(char*desterrno_tstrncpy_s(char*dest，rsize_tdestszrsize_tdestsz，constconstchar*srcchar*src，rsize_tcount);rsize_tcount);errno_tstrcat_s(char*dest,*size_tdestsz,constcharerrno_tstrcat_s(char*dest,*size_tdestsz,constchar*src);*src);关于关于errno_t及及size_t的详细解读请读者查阅的详细解读请读者查阅相关文档。相关文档。补例补例4.4测