数据结构与算法（C++版）课件第4章 串.ppt
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,an1n1 s s2 2=a a1212,a,an2n2 若若 n1=n2n1=n2且且a ai1i1=a=ai2i2（1 1i in1)n1)则则 s s1 1=s=s2 21void Copy(CharString&target,const CharString&source)初始条件：串初始条件：串source已存在。已存在。操作结果：将串操作结果：将串source复制得到一个串复制得到一个串target。4void Concat(CharString&target,const CharString&source)初始条件：串初始条件：串target和和source已存在。已存在。操作结果：将串操作结果：将串source联接到串联接到串target的后面。的后面。6int Index(const CharString&target,const CharString&pattern,int pos=0)初始条件：目标串初始条件：目标串target和模式串和模式串pattern都都存在，模式串存在，模式串pattern非空，且非空，且0 pos target.Length()。操作结果：返回目标串操作结果：返回目标串target中第中第pos个字符个字符后第一次出现的模式串后第一次出现的模式串pattern的位置。的位置。length=strlen(source);/串长串长strVal=new charlength+1;/分配存储空间分配存储空间 CStrCopy(strVal,source);/复制串值复制串值CharString:CharString(LinkList&source)/操作结果：从线性表转换构造新串操作结果：从线性表转换构造新串转换构造函数转换构造函数length=source.Length();/串长串长strVal=new charlength+1;/分配存储空间分配存储空间 for(int i=0;i “属性属性”菜单，打开菜单，打开“属性页属性页”对话框。对话框。2、在、在“预处理器定义预处理器定义”列表中选择列表中选择“编辑编辑”，在弹出的，在弹出的对话框中添加对话框中添加“_CRT_SECURE_NO_WARNINGS”。补例补例4.1 测试方法测试方法1。/文件路径名文件路径名:a4_1main.cpp#include/编译预处理命令编译预处理命令#include/“cstring”和和“string.h”/为为C头文件，包含字符串相关函数的声明头文件，包含字符串相关函数的声明using namespace std;/使用命名空间使用命名空间std int main()char dest100=destination,src100=source;/定义变量定义变量strcpy(dest,src);/调用调用strcpy()函数函数cout strcpy(dest,src):dest:dest endl;/显示相关信息显示相关信息strncpy(dest,src,4);/调用调用strncpy()函数函数dest4=0;/手动加上终止符手动加上终止符cout strncpy(dest,src,4):dest:dest endl;/显示相关信息显示相关信息strcpy(dest,Hello);/复制串复制串Hello strcpy(src,world);/复制串复制串worldstrcat(dest,src);/调用调用strcat()函数函数cout strcat(dest,src):dest:dest endl;/显示相关信息显示相关信息return 0;/返回值返回值0,返回操作系统返回操作系统程序运行时屏幕输出如下：程序运行时屏幕输出如下：strcpy(dest,src):dest:sourcestrncpy(dest,src,4):dest:sourstrcat(dest,src):dest:Hello world补例补例4.2 测试方法测试方法2。/文件路径名文件路径名:a4_2main.cpp#include/编译预处理命令编译预处理命令#include/“cstring”和和“string.h”/为为C头文件，包含字符串相关函数的声明头文件，包含字符串相关函数的声明using namespace std;/使用命名空间使用命名空间std#pragma warning(disable:4996)/在文件开头添在文件开头添/加此命令，禁止对代号为加此命令，禁止对代号为4996的警告的警告int main()char dest100=destination,src100=source;/定义变量定义变量strcpy(dest,src);/调用调用strcpy()函数函数cout strcpy(dest,src):dest:dest endl;/显示相关信息显示相关信息strncpy(dest,src,4);/调用调用strncpy()函数函数dest4=0;/手动加上终止符手动加上终止符cout strncpy(dest,src,4):dest:dest endl;/显示相关信息显示相关信息strcpy(dest,Hello);/复制串复制串Hello strcpy(src,world);/复制串复制串worldstrcat(dest,src);/调用调用strcat()函数函数cout strcat(dest,src):dest:dest endl;/显示相关信息显示相关信息return 0;/返回值返回值0,返回操作系统返回操作系统程序运行时屏幕输出如下：程序运行时屏幕输出如下：strcpy(dest,src):dest:sourcestrncpy(dest,src,4):dest:sourstrcat(dest,src):dest:Hello world补例补例4.3 测试方法测试方法3。/文件路径名文件路径名:a4_3main.cpp#define _CRT_SECURE_NO_WARNINGS/在文在文/件中所有预处理命令之前加上此命令，禁止相件中所有预处理命令之前加上此命令，禁止相/关安全类的警告关安全类的警告#include/编译预处理命令编译预处理命令#include/“cstring”和和“string.h”/为为C头文件，包含字符串相关函数的声明头文件，包含字符串相关函数的声明using namespace std;/使用命名空间使用命名空间stdint main()char dest100=destination,src100=source;/定义变量定义变量strcpy(dest,src);/调用调用strcpy()函数函数cout strcpy(dest,src):dest:dest endl;/显示相关信息显示相关信息strncpy(dest,src,4);/调用调用strncpy()函数函数dest4=0;/手动加上终止符手动加上终止符cout strncpy(dest,src,4):dest:dest endl;/显示相关信息显示相关信息strcpy(dest,Hello);/复制串复制串Hello strcpy(src,world);/复制串复制串worldstrcat(dest,src);/调用调用strcat()函数函数cout strcat(dest,src):dest:dest endl;/显示相关信息显示相关信息return 0;/返回值返回值0,返回操作系统返回操作系统程序运行时屏幕输出如下：程序运行时屏幕输出如下：strcpy(dest,src):dest:sourcestrncpy(dest,src,4):dest:sourstrcat(dest,src):dest:Hello world补例补例4.4 测试方法测试方法4。/文件路径名文件路径名:a4_4main.cpp#include/编译预处理命令编译预处理命令#include/“cstring”和和“string.h”/为为C头文件，包含字符串相关函数的声明头文件，包含字符串相关函数的声明using namespace std;/使用命名空间使用命名空间stdint main()char dest100=destination,src100=source;/定义变量定义变量strcpy_s(dest,strlen(src)+1,src);/调用调用strcpy_s()函数函数cout strcpy_s(dest,strlen(src)+1,src):dest:dest endl;/显示相关信息显示相关信息strncpy_s(dest,strlen(src)+1,src,4);/调用调用strncpy_s()函数函数dest4=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);/复制串复制串worldstrcat_s(dest,strlen(dest)+strlen(src)+1,src);/调用调用strcat_s()函数函数cout strcat_s(dest,strlen(dest)+strlen(src)+1,src):dest:dest endl;/显示相关信息显示相关信息return 0;/返回值返回值0,返回操作系统返回操作系统程序运行时屏幕输出如下：程序运行时屏幕输出如下：strcpy_s(dest,strlen(src)+1,src):dest:sourcestrncpy_s(dest,strlen(src)+1,src,4):dest:sourstrcat_s(dest,strlen(dest)+strlen(src)+1,src):dest:Hello world补例补例4.5 测试方法测试方法5。/文件路径名文件路径名:a4_5main.cpp#include/编译预处理命令编译预处理命令#include/“cstring”和和“string.h”/为为C头文件，包含字符串相关函数的声明头文件，包含字符串相关函数的声明using namespace std;/使用命名空间使用命名空间stdchar*CStrCopy(char*target,const char*source)/操作结果：操作结果：C风格将串风格将串source复制到串复制到串targetchar*tar=target;/暂存暂存targetwhile(*tar+=*source+)!=0);/逐个字符进行复制，直到逐个字符进行复制，直到0为止为止return target;/返回返回targetchar*CStrCopy(char*target,const char*source,int n)/操作结果：操作结果：C风格将串风格将串source复制复制n个字符到串个字符到串target int len=(int)strlen(source)n?(int)strlen(source):n;/目标串长目标串长for(int pos=0;pos len;pos+)targetpos=sourcepos;/逐个字符进行复制逐个字符进行复制targetlen=0;/串结束符串结束符return target;/返回返回targetchar*CStrConcat(char*target,const char*source)/操作结果：操作结果：C风格将串风格将串source连接到串连接到串target的后面的后面char*tar=target+strlen(target);/tar指向指向target的结尾处的结尾处while(*tar+=*source+)!=0);/逐个字符连接到逐个字符连接到target的后面，直到的后面，直到0为为止止return target;/返回返回targetint main()char dest100=destination,src100=source;/定义变量定义变量CStrCopy(dest,src);/调用调用CStrCopy()函数函数cout CStrCopy(dest,src):dest:dest endl;/显示相关信息显示相关信息CStrCopy(dest,src,4);/调用调用CStrCopy()函数函数/dest4=0;/手动加上终止符手动加上终止符,可省略可省略cout CStrCopy(dest,src,4):dest:dest endl;/显示相关信息显示相关信息CStrCopy(dest,Hello);/复制串复制串Hello CStrCopy(src,world);/复制串复制串worldCStrConcat(dest,src);/调用调用CStrConcat()函数函数cout CStrConcat(dest,src):dest:dest endl;/显示相关信息显示相关信息return 0;/返回值返回值0,返回操作系统返回操作系统程序运行时屏幕输出如下：程序运行时屏幕输出如下：CStrCopy(dest,src):dest:sourceCStrCopy(dest,src,4):dest:sourCStrConcat(dest,src):dest:Hello world第1趟TPaabbaaabbab第2趟TPaabbaaabbab第3趟TPaabbaaabbab第4趟TPaabbaaabbab/文件路径名文件路径名:e4_1alg.h int SimpleIndex(const CharString&targetStr,const CharString&patternStr,int pos=0)/操作结果操作结果:查找模式串查找模式串patternStr第一次在目标串第一次在目标串/targetStr中从第中从第pos个字符开始出现的位置个字符开始出现的位置int startPos=pos,curTargetStrPos=pos,curPatternStrPos=0;while(curTargetStrPos targetStr.Length()&curPatternStrPos=patternStr.Length()return startPos;/匹配成功匹配成功else return-1;/匹配失败匹配失败R：读取文本文件到缓冲区中，缓冲区中以前的任何内：读取文本文件到缓冲区中，缓冲区中以前的任何内容将丢失，当前行是文件的第一行。容将丢失，当前行是文件的第一行。W：将缓冲区的内容写入文本文件，当前行或缓冲区均：将缓冲区的内容写入文本文件，当前行或缓冲区均不改变。不改变。I：插入单个新行，用户必须在恰当的提示符的响应中键：插入单个新行，用户必须在恰当的提示符的响应中键入新行并提供其行号。入新行并提供其行号。D：删除当前行并移到下一行。：删除当前行并移到下一行。F：从当前行开始，查找包含有用户请求的目标串的第：从当前行开始，查找包含有用户请求的目标串的第一行。一行。C：将用户请求的字符串修改成用户请求的替换字符串，：将用户请求的字符串修改成用户请求的替换字符串，仅在当前行中有效。仅在当前行中有效。Q：退出编辑器。：退出编辑器。H：显示解释所有命令的帮助消息，程序也接受：显示解释所有命令的帮助消息，程序也接受?作为作为H的替代者。的替代者。N：下一行，在缓冲区中进一行。：下一行，在缓冲区中进一行。P：上一行，在缓冲区中退一行。：上一行，在缓冲区中退一行。B：开始，到缓冲区的第一行。：开始，到缓冲区的第一行。E：结束，到缓冲区的最后一行。：结束，到缓冲区的最后一行。G：到缓冲区中用户指定的行号。：到缓冲区中用户指定的行号。V：查看缓冲区的全部内容，显示到终端上。：查看缓冲区的全部内容，显示到终端上。bool UserSaysYes();/用户肯定回答用户肯定回答(yes)还是否定户否定还是否定户否定(no)cin userCommandvoid Editor: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;else if(!ChangeLine()/替换失败替换失败cout 警告警告:操作失败操作失败 endl;break;case d:/删除当前行删除当前行d(elelete)if(!textBuffer.Delete(curLineNo)/删除当前行失败删除当前行失败cout 错误错误:删除失败删除失败 endl;break;case e:/转到最后一行转到最后一行e(nd)if(textBuffer.Empty()cout 警告警告:文本缓存空文本缓存空 endl;else/转到最后第一行转到最后第一行curLineNo=textBuffer.Length();break;case f:/从当前行开始查找指定文本从当前行开始查找指定文本f(ind)if(textBuffer.Empty()cout 警告警告:文本缓存空文本缓存空 endl;else/从当前行开始查找指定文本从当前行开始查找指定文本FindString();break;case g:/转到指定行转到指定行g(o)if(!GotoLine()/转到指定行失败转到指定行失败cout 错误错误:操作失败操作失败 endl;break;case?:/获得帮助获得帮助?case h:/获得帮助获得帮助h(elp)cout 有效命令有效命令:b(egin)c(hange)endl d(el)e(nd)f(ind)g(o)h(elp)endl i(nsert)n(ext)p(rior)endl q(uit)r(ead)v(iew)w(rite)endl;break;case i:/插入指定行插入指定行i(nsert)if(!InsertLine()cout 错误错误:操作失败操作失败 endl;break;case n:/转到下一行转到下一行n(ext)if(!NextLine()/无下一行无下一行cout 错误错误:操作失败操作失败 endl;break;case p:/转到前一行转到前一行p(rior)if(!PreviousLine()/无前一行无前一行cout 错误错误:操作失败操作失败 endl;break;case r:/读入文本件读入文本件r(ead)ReadFile();break;case v:/显示文本显示文本v(iew)View();break;case w:/写文本缓存到输出文件中写文本缓存到输出文件中w(rite)if(textBuffer.Empty()/文本缓存空文本缓存空cout 警告警告:文本缓存空文本缓存空 endl;else/写文本缓存到输出文件中写文本缓存到输出文件中WriteFile();break;default:cout 输入输入h或或?获得帮助或输入有效命令字符获得帮助或输入有效命令字符:endl;
