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

第4章串数据结构与算法

(C++版)(第2版)4.1串类型的定义一、串的定义n(n>=0)个字符的有限序列s="a1,a2,…,an"

串名:s

串值:ai(1≤i≤n)

串长:n二、串的基本术语空串n=0的串子串串中若干相邻字符组成的子序列主串包含子串的串空格串仅含有空格字符的串(n不为0)串相等设s1="a11,…,an1"s2="a12,…,an2"

若n1=n2且ai1=ai2（1≤i≤n1)

则s1=s21．voidCopy(CharString&target, constCharString&source)初始条件：串source已存在。操作结果：将串source复制得到一个串target。2．boolEmpty()const

初始条件：串已存在。

操作结果：如串为空，则返回true，否则返回false。

3．intLength()const

初始条件：串已存在。

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

初始条件：串存在，且0≤pos＜s.Length()，0≤len≤s.Length()–pos。

操作结果：返回从第pos个字符开始长度为len的子串。6．intIndex(constCharString&target, constCharString&pattern,intpos=0)初始条件：目标串target和模式串pattern都存在，模式串pattern非空，且0≤pos

target.Length()。操作结果：返回目标串target中第pos个字符后第一次出现的模式串pattern的位置。4.2字符串的实现在C++在头文件string中已含了一种安全的字符串实现由于这个库没有包含在一些较老的C++编译器中，因此本节将设计自已的安全的CharString类，使用面向对象技术来克服C风格的串中存在的问题。一、串类及串相关操作//串类classCharString{protected://串实现的数据成员: char*strVal; //串值

intlength; //串长 public://抽象数据类型方法声明及重载编译系统默认方法声明: CharString(); //构造函数

virtual~CharString(); //析构函数

CharString(constCharString&source);

//复制构造函数

CharString(constchar*source);

//从C风格串转换的构造函数 CharString(LinkList<char>&source);

//从线性表转换的构造函数

intLength()const; //求串长度

boolEmpty()const; //判断串是否为空

CharString&operator=(constCharString&source);

//重载赋值运算符

constchar*ToCStr()const;//将串转换成C风格串

constchar&operator[](inti)const;

//重载下标运算符};串相关操作CharStringRead(istream&input); //从输入流读入串CharStringRead(istream&input,char&terminalChar);

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

//将串source连接到串target的后面串相关操作char*CStrCopy(char*target,constchar*source); //C风格将串source复制到串targetvoidCopy(CharString&target, constCharString&source);

//将串source复制到串targetchar*CStrCopy(char*target,constchar*source,intn); //C风格将串source复制n个字符到串targetvoidCopy(CharString&target, constCharString&source,intn);

//将串source复制n个字符到串targetintIndex(constCharString&target, constCharString&pattern,intpos=0); //查找模式串pattern第一次在目标串target中从第

//pos个字符开始出现的位置CharStringSubString(constCharString&s, intpos,intlen);

//求串s的第pos个字符开始的长度为len的子串booloperator==(constCharString&first, constCharString&second); //重载关系运算符==booloperator<(constCharString&first, constCharString&second); //重载关系运算符<booloperator>(constCharString&first, constCharString&second); //重载关系运算符>booloperator<=(constCharString&first, constCharString&second); //重载关系运算符<=booloperator>=(constCharString&first, constCharString&second); //重载关系运算符>=booloperator!=(constCharString&first, constCharString&second); //重载关系运算符!=二、串类部分成员函数的实现1.串构造函数(1)CharString::CharString(constchar*source)//操作结果：从C风格串转换构造新串——转换构造函数{ length=strlen(source); //串长 strVal=newchar[length+1]; //分配存储空间

CStrCopy(strVal,source); //复制串值}2.串构造函数(2)CharString::CharString(LinkList<char>&source)//操作结果：从线性表转换构造新串——转换构造函数{ length=source.Length(); //串长

strVal=newchar[length+1];//分配存储空间

for(inti=0;i<length;i++) { //复制串值

source.GetElem(i+1,strVal[i]); } strVal[length]='\0'; //串值以'\0'结束 }3.将C++串转换为C语言串constchar*CharString::ToCStr()const//操作结果：将串转换成C风格串{ return(constchar*)strVal;

//串值类型转换}4.串比较实现booloperator==(constCharString&first, constCharString&second)//操作结果：重载关系运算符=={ returnstrcmp(first.ToCStr(),second.ToCStr())==0;}booloperator<(constCharString&first, constCharString&second)//操作结果：重载关系运算符<{ returnstrcmp(first.ToCStr(),second.ToCStr())<0;}5.进一步串操作示例voidConcat(CharString&target, constCharString&source)//操作结果：将串source连接到target串的后面{ constchar*cFirst=target.ToCStr() //指向第一个串 constchar*cSecond=source.ToCStr();

//指向第二个串 char*cTarget=newchar[strlen(cFirst)+ strlen(cSecond)+1]; //分配存储空间 CStrCopy(cTarget,cFirst); //复制第一个串 CStrConcat(cTarget,cSecond); //连接第二个串 target=cTarget; //串赋值 delete[]cTarget; //释放cTarget}三、补充:关于字符串函数strcpy()、strncpy()和strcat()在Code::Blocks20.03、DevC++5.11及VC6中，C中关于字符串的函数strcpy()、strncpy()和strcat()都能正常编译，但在版本比较新的VC，比如VC2022中，在上述几个函数调用时会出现类似如下的编译时错误。错误 C4996 'strcpy':Thisfunctionorvariablemaybeunsafe.Considerusingstrcpy_sinstead.Todisabledeprecation,use_CRT_SECURE_NO_WARNINGS.Seeonlinehelpfordetails.为什么会报这个错？因为微软认为strcpy()、strncpy()和strcat()函数不够安全，可以采用5种方法解决此问题。方法1：设置项目属性中“预处理器”中的“预处理器定义”。1、选择“项目”-->“属性”菜单，打开“属性页”对话框。2、在“预处理器定义”列表中选择“编辑”，在弹出的对话框中添加“_CRT_SECURE_NO_WARNINGS”。补例4.1测试方法1。//文件路径名:a4_1\main.cpp#include<iostream> //编译预处理命令#include<cstring> //“cstring”和“string.h” //为C头文件，包含字符串相关函数的声明usingnamespacestd; //使用命名空间stdintmain(){ chardest[100]="destination",src[100]= "source"; //定义变量

strcpy(dest,src); //调用strcpy()函数

cout<<"strcpy(dest,src):"<<"dest:"<<dest <<endl; //显示相关信息说明：补例4.1在DevC++5.11、Code::Blocks20.03、VC6.0及VC2022等环境中通过测试。

strncpy(dest,src,4); //调用strncpy()函数

dest[4]='\0'; //手动加上终止符

cout<<"strncpy(dest,src,4):"<<"dest:"<< dest<<endl; //显示相关信息

strcpy(dest,"Hello"); //复制串"Hello" strcpy(src,"world"); //复制串"world" strcat(dest,src); //调用strcat()函数

cout<<"strcat(dest,src):"<<"dest:"<<dest <<endl; //显示相关信息

return0; //返回值0,返回操作系统}程序运行时屏幕输出如下： strcpy(dest,src):dest:source strncpy(dest,src,4):dest:sour strcat(dest,src):dest:Helloworld方法2：在文件开头添加如下命令，禁止对代号为4996的警告。#pragmawarning(disable:4996)补例4.2测试方法2。//文件路径名:a4_2\main.cpp#include<iostream> //编译预处理命令#include<cstring> //“cstring”和“string.h” //为C头文件，包含字符串相关函数的声明usingnamespacestd; //使用命名空间std#pragmawarning(disable:4996) //在文件开头添 //加此命令，禁止对代号为4996的警告说明：补例4.2在DevC++5.11、Code::Blocks20.03、VC6.0及VC2022等环境中通过测试。intmain(){ chardest[100]="destination",src[100]= "source"; //定义变量

strcpy(dest,src); //调用strcpy()函数

cout<<"strcpy(dest,src):"<<"dest:"<<dest <<endl; //显示相关信息

strncpy(dest,src,4); //调用strncpy()函数

dest[4]='\0'; //手动加上终止符

cout<<"strncpy(dest,src,4):"<<"dest:"<< dest<<endl; //显示相关信息

strcpy(dest,"Hello"); //复制串"Hello" strcpy(src,"world"); //复制串"world" strcat(dest,src); //调用strcat()函数

cout<<"strcat(dest,src):"<<"dest:"<<dest <<endl; //显示相关信息

return0; //返回值0,返回操作系统}程序运行时屏幕输出如下： strcpy(dest,src):dest:source strncpy(dest,src,4):dest:sour strcat(dest,src):dest:Helloworld方法3：在文件中所有预处理命令之前加上如下命令，禁止相关安全类的警告。#define_CRT_SECURE_NO_WARNINGS补例4.3测试方法3。//文件路径名:a4_3\main.cpp#define_CRT_SECURE_NO_WARNINGS //在文 //件中所有预处理命令之前加上此命令，禁止相 //关安全类的警告#include<iostream> //编译预处理命令#include<cstring> //“cstring”和“string.h” //为C头文件，包含字符串相关函数的声明usingnamespacestd; //使用命名空间std说明：补例4.3在DevC++5.11、Code::Blocks20.03、VC6.0及VC2022等环境中通过测试。intmain(){ chardest[100]="destination",src[100]= "source"; //定义变量

strcpy(dest,src); //调用strcpy()函数

cout<<"strcpy(dest,src):"<<"dest:"<<dest <<endl; //显示相关信息

strncpy(dest,src,4); //调用strncpy()函数

dest[4]='\0'; //手动加上终止符

cout<<"strncpy(dest,src,4):"<<"dest:"<< dest<<endl; //显示相关信息

strcpy(dest,"Hello"); //复制串"Hello" strcpy(src,"world"); //复制串"world" strcat(dest,src); //调用strcat()函数

cout<<"strcat(dest,src):"<<"dest:"<<dest <<endl; //显示相关信息

return0; //返回值0,返回操作系统}程序运行时屏幕输出如下： strcpy(dest,src):dest:source strncpy(dest,src,4):dest:sour strcat(dest,src):dest:Helloworld方法4：用strcpy_s()、strncpy_s()和strcat_s()函数代替strcpy()、strncpy()和strcat()函数，strcpy_s()、strncpy_s()和strcat_s()函数声明如下errno_tstrcpy_s(char*dest,*size_tdestsz,constchar*src);errno_tstrncpy_s(char*dest，rsize_tdestsz，constchar*src，rsize_tcount);errno_tstrcat_s(char*dest,*size_tdestsz,constchar*src);关于errno_t及size_t的详细解读请读者查阅相关文档。补例4.4测试方法4。//文件路径名:a4_4\main.cpp#include<iostream> //编译预处理命令#include<cstring> //“cstring”和“string.h” //为C头文件，包含字符串相关函数的声明usingnamespacestd; //使用命名空间stdintmain(){ chardest[100]="destination",src[100]= "source"; //定义变量

strcpy_s(dest,strlen(src)+1,src);

//调用strcpy_s()函数

cout<<"strcpy_s(dest,strlen(src)+1,src):"<<"

dest:"<<dest<<endl; //显示相关信息说明：1、在DevC++5.11与VC6.0不支持strcpy_s()、strncpy_s()和strcat_s()等相关函数；2、补例4.4在Code::Blocks20.03及VC2022等环境中通过测试。

strncpy_s(dest,strlen(src)+1,src,4); //调用strncpy_s()函数

dest[4]='\0'; //手动加上终止符

cout<<"strncpy_s(dest,strlen(src)+1,src,4):" <<"dest:"<<dest<<endl;

//显示相关信息

strcpy_s(dest,strlen("Hello")+1,"Hello"); //复制串"Hello"

strcpy_s(src,strlen("world")+1,"world"); //复制串"world"

strcat_s(dest,strlen(dest)+strlen(src)+1,src);

//调用strcat_s()函数

cout<<"strcat_s(dest,strlen(dest)+strlen(src)+ 1,src):"<<"dest:"<<dest<<endl;

//显示相关信息

return0; //返回值0,返回操作系统}程序运行时屏幕输出如下： strcpy_s(dest,strlen(src)+1,src):dest:source strncpy_s(dest,strlen(src)+1,src,4):dest:sour strcat_s(dest,strlen(dest)+strlen(src)+1,src):dest:Helloworld方法5：采用自定义CStrCopy()、CStrConcat()函数代替strcpy()、strncpy()和strcat()函数，本书就采用这种方法。补例4.5测试方法5。//文件路径名:a4_5\main.cpp#include<iostream> //编译预处理命令#include<cstring> //“cstring”和“string.h” //为C头文件，包含字符串相关函数的声明usingnamespacestd; //使用命名空间std说明：补例4.5在DevC++5.11、Code::Blocks20.03、VC6.0及VC2022等环境中通过测试。char*CStrCopy(char*target,constchar*source)//操作结果：C风格将串source复制到串target{ char*tar=target; //暂存target while((*tar++=*source++)!='\0'); //逐个字符进行复制，直到'\0'为止

returntarget; //返回target}char*CStrCopy(char*target,constchar*source,intn)//操作结果：C风格将串source复制n个字符到串target{ intlen=(int)strlen(source)<n? (int)strlen(source):n; //目标串长

for(intpos=0;pos<len;pos++) target[pos]=source[pos];//逐个字符进行复制

target[len]='\0'; //串结束符

returntarget; //返回target}char*CStrConcat(char*target,constchar*source)//操作结果：C风格将串source连接到串target的后面{ char*tar=target+strlen(target); //tar指向target的结尾处

while((*tar++=*source++)!='\0'); //逐个字符连接到target的后面，直到'\0'为止

returntarget; //返回target}intmain(){ chardest[100]="destination",src[100]="source"; //定义变量

CStrCopy(dest,src); //调用CStrCopy()函数

cout<<"CStrCopy(dest,src):"<<"dest:"<<dest

<<endl; //显示相关信息

CStrCopy(dest,src,4); //调用CStrCopy()函数// dest[4]='\0'; //手动加上终止符,可省略

cout<<"CStrCopy(dest,src,4):"<<"dest:"<<

dest<<endl; //显示相关信息

CStrCopy(dest,"Hello"); //复制串"Hello"

CStrCopy(src,"world"); //复制串"world"

CStrConcat(dest,src); //调用CStrConcat()函数

cout<<"CStrConcat(dest,src):"<<"dest:"<<

dest<<endl; //显示相关信息

return0; //返回值0,返回操作系统}程序运行时屏幕输出如下： CStrCopy(dest,src):dest:source CStrCopy(dest,src,4):dest:sour CStrConcat(dest,src):dest:Helloworld4.3字符串

模式匹配算法//文件路径名:e4_1\alg.hintSimpleIndex(constCharString&targetStr, constCharString&patternStr,intpos=0)//操作结果:查找模式串patternStr第一次在目标串// targetStr中从第pos个字符开始出现的位置{

intstartPos=pos,curTargetStrPos=pos, curPatternStrPos=0; while(curTargetStrPos<targetStr.Length()&& curPatternStrPos<patternStr.Length())

{ if(targetStr[curTargetStrPos]== patternStr[curPatternStrPos]) { //继续比较后续字符 curTargetStrPos++; curPatternStrPos++; } else { //指针回退,重新开始新的匹配 curTargetStrPos=++startPos; curPatternStrPos=0; } }

if(curPatternStrPos>=patternStr.Length()) returnstartPos; //匹配成功 else return-1; //匹配失败}*4.4实例研究

——文本编辑一、文本编辑操作R：读取文本文件到缓冲区中，缓冲区中以前的任何内容将丢失，当前行是文件的第一行。W：将缓冲区的内容写入文本文件，当前行或缓冲区均不改变。I：插入单个新行，用户必须在恰当的提示符的响应中键入新行并提供其行号。D：删除当前行并移到下一行。F：从当前行开始，查找包含有用户请求的目标串的第一行。C：将用户请求的字符串修改成用户请求的替换字符串，仅在当前行中有效。Q：退出编辑器。H：显示解释所有命令的帮助消息，程序也接受?作为H的替代者。N：下一行，在缓冲区中进一行。P：上一行，在缓冲区中退一行。B：开始，到缓冲区的第一行。E：结束，到缓冲区的最后一行。G：到缓冲区中用户指定的行号。V：查看缓冲区的全部内容，显示到终端上。二、主程序主程序声明一个称为text的Editor对象并重复运行text的Editor方法，从用户处得到命令并处理这些命令。下面是得到的程序：intmain()//操作结果:读输入文件各行到文本缓存中，执行简单的行编辑,并写文本缓存到输出文件中{

charinfName[256],outfName[256]; cout<<"输入文件名(缺省:file_in.txt):"; CStrCopy(infName,Read(cin).ToCStr());

if(strlen(infName)==0) { //infName为空

CStrCopy(infName,"file_in.txt"); }

cout<<"输出文件名(缺省:file_out.txt):"; CStrCopy(outfName,Read(cin).ToCStr()); if(strlen(outfName)==0) { //outfName为空

CStrCopy(outfName,"file_out.txt"); } Editortext(infName,outfName); //定义文本对象

while(text.GetCommand()) { //接收并执行用户操作命令

text.RunCommand(); }

return0; //返回值0,返回操作系统}三、文本编辑类EditorEditor类包含以字符串（行）为数据元素的双向链表textBuffer//文本编辑类classEditor{private://文本编辑类的数据成员: DblLinkList<CharString>textBuffer;//文本缓存

intcurLineNo; //当前行号

ifstreaminfile; //输入文件

ofstreamoutfile; //输出文件

charuserCommand; //用户命令//辅助函数: boolUserSaysYes();

//用户肯定回答(yes)还是否定户否定(no) boolNextLine(); //转到下一行

boolPreviousLine(); //转到前一行

boolGotoLine(); //转到指定行

boolInsertLine(); //插入一行

boolChangeLine();

//替换当前行的指定文本串

voidReadFile(); //读入文本文件

voidWriteFile(); //写文本文件

voidFindCharString(); //查找串

voidView(); //查看(显示)缓冲区public://方法声明: Editor(charinfName[],charoutfName[]);

//构造函数

boolGetCommand();

//读取操作命令字符userCommand voidRunCommand(); //运行操作命令};四、接收用户操作命GetCommand()由于文本编辑器必须容忍无效输入，由于不能期望用户在输入大小写字母上达成一致，因此第一步就是将大写字母转换成小写字母boolEditor::GetCommand()//操作结果:读取操作命令字符userCommand，除非//userCommand为'q'，否则返回true{ CharStringcurLine; //当前行

if(curLineNo!=0) { //存在当前行

textBuffer.GetElem(curLineNo,curLine);

//取出当前行

cout<<curLineNo<<":" //显示行号

<<curLine.ToCStr()<<endl<<"?"; //显示当前行及问号? } else { //不存在当前行

cout<<"文件缓存空"<<endl<<"?"; }

cin>>userCommand;

//忽略空格并取得操作命令字符

userCommand=tolower(userCommand);

//转换为小字字母

while(cin.get()!='\n');

//忽略用户输入的其他字符

if(userCommand=='q') { //userCommand为'q'时返回false

returnfalse; } else { //userCommand不为'q'时返回true returntrue; }}五、执行命令RunCommand()方法RunCommand基本上是由一个大的switch语句组成，用switch完成每个命令的操作，并且具有处理用户选择和错误情况的处理voidEditor::RunCommand()//操作结果:运行操作命令{ switch(userCommand) { case'b': //转到第1行b(egin) if(textBuffer.Empty()) { //文本缓存空 cout<<"警告:文本缓存空"<<endl; } else { //文本缓存非空,转到第1行 curLineNo=1; } break; case'c': //替换当前行c(hange) if(textBuffer.Empty()) { cout<<"警告:文本缓存空"<<endl; } elseif(!ChangeLine()) { //替换失败 cout<<"警告:操作失败"<<endl; } break;

case'd': //删除当前行d(elelete) if(!textBuffer.Delete(curLineNo)) { //删除当前行失败 cout<<"错误:删除失败"<<endl; } break; case'e': //转到最后