数据结构第4章串.

第4章串4.1串的基本概念4.1.1什么是串串（或字符串）是由零个或多个字符组成的有限序列。记作str=a1a2…an（n≥0），其中str是串名，用双引号括起来的字符序列为串值，引号是界限符，ai（1≤i≤n）是一个任意字符（字母、数字或其他字符），它称为串的元素，是构成串的基本单位，串中所包含的字符个数n称为串的长度，当n=0时，称为空串。一个串中任意连续的字符组成的子序列称为该串的子串，例如，a、ab、abc和abcd等都是abcde的子串。包含子串的串相应地称为主串。若两个串的长度相等且对应字符都相等，则称两个串是相等的。当两个串不相等时，可按“字典顺序”区分大小。【例4.1】设str是一个长度为n的串，其中的字符各不相同，则str中的所有子串个数是多少？解：对于这样的串str，有：空串是其子串，计1个每个字符构成的串是其子串，计n个每2个连续的字符构成的串是其子串，计n-1个每3个连续的字符构成的串是其子串，计n-2个…每n-1个连续的字符构成的串是其子串，计2个str是其自身的子串，计1个所有子串个数=1+n+(n-1)+…+2+1=n(n+1)/2+1。例如，str=software的子串个数=(8×9)/2+1=37。4.1.2串的抽象数据类型ADTString{数据对象：D={ai|1≤i≤n,n≥0,ai为char类型}数据关系：R={r}r={ai,ai+1|ai,ai+1∈D,i=1,…,n-1}基本运算：voidStrAssign(cstr)：由字符串常量cstr创建一个串，即生成其值等于cstr的串。voidStrCopy(t)：串复制，由串t复制产生一个串。intStrLength()：求串长，返回当前串中字符个数。StringConcat(t)：串连接，返回一个当前串和串t连接后的结果。StringSubStr(i,j)：求子串，返回当前串中从第i个字符开始的j个连续字符组成的子串。StringInsStr(i,s)：串插入，返回串s插入到当前串的第i个位置后的子串。StringDelStr(i,j)：串删除，返回当前串中删去从第i个字符开始的j个字符后的结果。StringRepStr(i,j,s)：串替换，返回用串s替换当前串中第i个字符开始的j个字符后的结果。DispStr()：串输出，输出当前串的所有元素值。}4.2串的存储结构4.2.1串的顺序存储结构－顺序串和顺序表一样，用一个data数组（大小为MaxSize）和一个整型变量length来表示一个顺序串，length表示data数组中实际字符的个数。设计顺序串类SqStringClass如下：constintMaxSize=100;classSqStringClass//顺序串类{char*data;//存放串中元素intlength;//串中字符个数public:SqStringClass();//构造函数~SqStringClass();//析构函数SqStringClass&operator=(char*cstr);//重载赋值运算符,SqStringClass&operator=(SqStringClass&t);//重载赋值运算符intStrLength();//求串长度SqStringClass&operator+(SqStringClass&t);//串连接SqStringClass&SubStr(inti,intj);//求子串SqStringClass&InsStr(inti,SqStringClass&s);//串插入SqStringClass&DelStr(inti,intj);//串删除SqStringClass&RepStr(inti,intj,SqStringClass&s);//串替换voidDispStr();//串输出};说明：在C++语言中提供了字符数组来存放字符串，以空字符'\0'标识字符串结束,并包含了前面列出的大部分串运算功能，本节主要是通过自已组织和实现串来介绍数据结构算法的一般设计方法。下面讨论在顺序串上实现串基本运算的算法。（1）顺序串的初始化和销毁顺序串的初始化和销毁分别通过构造函数和析构函数来实现，对应的算法如下：SqStringClass::SqStringClass()//构造函数{data=newchar[MaxSize];length=0;}SqStringClass::~SqStringClass()//析构函数{delete[]data;}（2）建立串StrAssign(cstr)由一个字符串常量cstr建立一个顺序串对象，即生成一个其值等于cstr的顺序串对象，这里采用重载“=”运算符实现的。对应的算法如下：SqStringClass&SqStringClass::operator=(char*cstr)//重载赋值运算符{inti;for(i=0;icstr[i]!='\0';i++)data[i]=cstr[i];length=i;return*this;}例如，cstr为C++的字符串abcdef，s为SqStringClass类对象，执行s=cstr的结果如图4.2所示（3）串复制StrCopy(t)将顺序串t复制给当前串对象，这里也是采用重载“=”运算符实现的。对应的算法如下：SqStringClass&SqStringClass::operator=(SqStringClass&t)//重载赋值运算符{inti;for(i=0;it.length;i++)data[i]=t.data[i];length=t.length;return*this;}（4）求串长度StrLength()返回当前顺序串中的字符个数。对应的算法如下：intSqStringClass::StrLength()//求串长度{returnlength;}（5）串连接Concat(t)将当前顺序串和串对象t的所有字符连接在一起形成新顺序串，并返回这个新串对象，并不改变当前串对象和串对象t的内容，这里采用重载“+”运算符实现的。对应的算法如下：SqStringClass&SqStringClass::operator+(SqStringClass&t)//串连接{staticSqStringClassnstr;//新建一个空串inti;nstr.length=length+t.length;for(i=0;ilength;i++)//将当前串data[0..str.length-1]→nstrnstr.data[i]=data[i];for(i=0;it.length;i++)//将t.data[0..t.length-1]→nstrnstr.data[length+i]=t.data[i];returnnstr;//返回新串nstr}例如，串对象s和t连接产生新串对象s1的结果如图4.3所示。（6）求子串SubStr(i,j)产生由当前顺序串中第i个字符开始的、连续j个字符组成的子顺序串，并返回这个子串对象。当参数i、j不正确时返回一个空串。对应的算法如下：SqStringClass&SqStringClass::SubStr(inti,intj)//求子串{staticSqStringClassnstr;//新建一个空串intk;if(i=0||ilength||j0||i+j-1length)returnnstr;//参数不正确时返回空串for(k=i-1;ki+j-1;k++)//将str.data[i..i+j-1]→nstrnstr.data[k-i+1]=data[k];nstr.length=j;returnnstr;//返回新建的顺序串}例如，由顺序串s产生子串t对象的结果如图4.4所示。（7）串插入InsStr(i,s)将顺序串s的所有字符插入到当前串对象的第i个位置中产生一个新顺序串，并返回这个新串对象。当参数不正确时返回一个空串对象。对应的算法如下：SqStringClass&SqStringClass::InsStr(inti,SqStringClass&s){intj;staticSqStringClassnstr;//新建一个空串if(i=0||ilength+1)//参数不正确时返回空串returnnstr;for(j=0;ji-1;j++)//将当前串data[0..i-2]→nstrnstr.data[j]=data[j];for(j=0;js.length;j++)//将s.data[0..s.length-1]→nstrnstr.data[i+j-1]=s.data[j];for(j=i-1;jlength;j++)//将当前串data[i-1..length-1]→nstrnstr.data[s.length+j]=data[j];nstr.length=length+s.length;returnnstr;//返回新建的顺序串}例如，将顺序串s插入到顺序串t中产生顺序串对象t1的结果如图4.5所示。（8）串删除DelStr(i,j)从当前顺序串中删去第i个字符开始的连续j个字符产生一个子顺序串，并返回这个子串对象。当参数不正确时返回一个空串对象。对应的算法如下：SqStringClass&SqStringClass::DelStr(inti,intj)//串删除{intk;staticSqStringClassnstr;//新建一个空串if(i=0||ilength||i+j-1length)//参数不正确时返回空串returnnstr;for(k=0;ki-1;k++)//将当前串data[0..i-2]→nstrnstr.data[k]=data[k];for(k=i+j-1;klength;k++)//将当前串data[i+j-1..length-1]→nstrnstr.data[k-j]=data[k];nstr.length=length-j;returnnstr;//返回新建的顺序串}例如，删除顺序串s中的一个子串产生顺序串对象t的结果如图4.6所示。（9）串替换RepStr(i,j,s)将当前顺序串中第i个字符开始的连续j个字符用串对象s替换而产生一个新顺序串，并返回这个新串对象。当参数不正确时返回一个空串。对应的算法如下：SqStringClass&SqStringClass::RepStr(inti,intj,SqStringClass&s){intk;staticSqStringClassnstr;//新建一个空串if(i=0||ilength||i+j-1length)//参数不正确时返回空串returnnstr;for(k=0;ki-1;k++)//将当前串data[0..i-2]→nstrnstr.data[k]=data[k];for(k=0;ks.length;k++)//将s.data[0..s.length-1]→nstrnstr.data[i+k-1]=s.data[k];for(k=i+j-1;klength;k++)//将当前串data[i+j-1..length-1]→nstrnstr.data[s.length+k-j]=data[k];nstr.length=length-j+s.length;returnnstr;//返回新建的顺序串}例如，将顺序串t中某个子串替换为串对象s产生t1串对象的结果如图4.7所示。（10）串输出DispStr()输出当前顺序串对象s的所有字符。对应的算法如下：voidSqStringClass::DispStr()//串输出{inti;for(i=0;ilength;i++)coutdata[i];coutendl;}【例4.2】设计一个算法StrEqueal(s,t)比较两个顺序串s、t是否相等。解：两个顺序串对象s、t相等的条件是它们的长度相等且所有对应位置上的字符均相同。对应的算法如下