《第4章串》习题解答解读.docx
《《第4章串》习题解答解读.docx》由会员分享，可在线阅读，更多相关《《第4章串》习题解答解读.docx（39页珍藏版）》请在冰点文库上搜索。
《第4章串》习题解答解读
第四章串存储与基本操作的实现
本章学习要点
◆熟悉串的相关概念以及串与线性表的关系
◆重点掌握串的定长存储、堆分配存储的表示方法与基本操作的实现
◆了解串的各种存储结构，能根据需要合理选用串的存储结构解决实际问题
“串”（string），是字符串的简称，它是一种特殊的线性表，其特殊性在于组成线性表的数据元素是单个字符。
字符串在计算机处理实际问题中使用非常广泛，比如人名、地名、商品名、设备名等均为字符串。
同样在文字编辑、自然语言理解和翻译、源程序的编辑和修改等方面，都离不开对字符串的处理。
4.1串的基本概念
4.1.1串的概念
1．串的定义
串（string）是由n个字符组成的有限序列，记为：
S=”a0a1a2…an-1”（n≥0）。
其中，S是串的名字，字符序列a0a1a2…an-1是串的值，ai（0≤i≤n-1）可以是字母、数字或其他字符元素；由于在C语言系统中数组元素的下标是从0开始的，所以串中所含元素的序号等于该元素的下标值加1；串中所含字符的个数n称为该串的长度，长度为0的字符串称为空串（nullstring）。
从串的定义可以看出，串实际上是数据元素为字符的特殊的线性表。
例如：
（1）A=“X123”（长度为4的串）
（2）B=“12345654321”（长度为11的串）
（3）C=“BeiJing”（长度为8的串）
（4）D=“”（长度为0的空串）
（5）E=“Thisisastring”（长度为16的串）
（6）F=“isa”（长度为6的串）
2．子串、主串和位置
串中任意连续的字符组成的子序列称为该串的子串；相应地，包含子串的串称为主串。
串中的字符在串序列中的序号称为该字符在该串中的位置；子串的第一个字符在主串中的位置称为子串在主串中的位置。
显然，串为其自身的子串，并规定空串为任何串的子串。
显然，在不考虑空子串的情况下，一个长度为n的字符串具有n（n+1）/2个子串。
例如：
在上例的（6）中串F就是（5）中串E的子串，且子串F在主串E中的位置是5。
由于空格符也是一个字符，所以在串G=“abcdefghne”中包含有子串“cdef”,而串“cdef”不是串G的子串。
串G中第一个字符‘e’的位置是6，第二个字符‘e’的位置是11。
3．串的比较
如果两个串的长度相等且对应位置上的字符相同，则称这两个串相等。
两个串A、B的比较过程是：
从前往后逐个比较对应位置上的字符的ASCII码值，直到不相等或有一个字符串结束为止，此时的情况有以下几种：
（1）两个串同时结束，表示A等于B；
（2）A中字符的ASCII码值大于B中相应位置上字符的ASCII码值或B串结束，表示A大于B；
（3）B中字符的ASCII码值大于A中相应位置上字符的ASCII码值或A串结束，表示A小于B。
例如：
“abc”=“abc”，“abc”<“abcd”，“abxy”>“abcdefg”，“132”>“123456”，“ABab”<“abAB”，“3+2”>“2+3”。
4．空格串
由一个或多个空格字符组成的串称为空格串，空格串的长度为串中所含空格字符的个数。
在串操作中不要将空格串和空串混淆。
4.1.2串的基本操作
尽管串的定义和线性表极为相似，但是串的基本操作和线性表有很大差别。
在线性表的基本操作中，大多以单个元素作为操作对象，比如对线性表的查找、访问、插入、删除和排序等；而在串的基本操作中，通常以串整体或串的一部分（子串）作为操作对象，比如子串的查找、截取子串、删除一个子串、插入子串和子串替换等操作。
串的基本操作主要有：
（1）初始化串StrAssign（&T,chars）由字符串常量chars生成字符串T的操作。
（2）串复制StrCopy（&T,S）由串S复制生成串T的操作。
（3）串比较StrCompare（S,T）若S=T返回0，S>T返回正数，S（4）求串长度StrLength（S）返回串S的长度。
（5）串连接Concat（&T,S1,S2）将串S1和S2连接起来生成串T的操作。
（6）求子串SubString（&Sub,S,pos,len）以串S中pos位置开始的len个字符生成子串Sub的操作。
（7）串查找Index（S,T,pos）返回子串T在S中pos个字符以后出现的位置。
（8）串替换Replace（&S,T,V）将串S中所有不重叠子串T替换为串V的操作。
（9）串插入StrInsert（&S,pos,T）在串S中第pos个字符前插入串T的操作。
（10）删除子串StrDelete（&S,pos,len）删除串S中第pos个字符开始的len个字符的操作。
4.2串的存储表示与实现
既然串是线性表的特例，所以线性表的两种存储结构对于串也是适用的。
在应用中具体选用何种存储结构与串的操作有关，比如对串进行插入和删除操作运算时选用链存储结构较好，对串进行查找和求子串运算时选用顺序存储结构较好。
本章主要介绍串的3种存储表示方法：
（1）串的定长顺序存储表示法
（2）串的堆分配存储表示法
（3）串的块链式存储表示法
4.2.1串的定长顺序存储表示
串的定长顺序存储表示是用一组地址连续的存储单元来存储串中的字符序列。
在串的定长顺序存储表示中，按照预定义的大小，为每个定长的串变量分配一个固定长度的存储区，所以可以用定长字符数组来表示。
1．定长顺序存储结构
在C++运行环境中，定长顺序结构定义为：
#include"iostream.h"
#include"stdio.h"
#defineMAXLEN255//定义串的最大长度为255
typedefcharSString[MAXLEN+1];//定义定长顺序存储类型SString
2．基本操作的C++程序实现
（1）求串长度操作intLength_SS（SStringS）
操作返回串S中所含字符的个数，即串的长度；如果S为空串则返回0。
intLength_SS（SStringS）
{inti=0;
while（S[i]）i++;
return（i）;
}
（2）串连接操作intConcat_SS（SString&T,SStringS1,SStringS2）
该操作将串S1、S2连接生成串T，如果在连接过程中产生了截断（即S1的长度加上S2的长度大于MAXLEN）则返回0，否则返回1。
intConcat_SS（SString&T,SStringS1,SStringS2）
{
inti,j,k;
i=j=k=0;
while（T[i++]=S1[j++]）;
i--;
while（iT[i]=0;
if（（i==MAXLEN）&&S2[k]）return（0）;/*判断是否产生截断*/
elsereturn
（1）;
}
（3）求子串操作intSubString_SS（SString&Sub,SStringS,intpos,intlen）
该操作截取串S中从第pos个字符开始的连续的len个字符生成子串Sub，如果位置pos和长度len合理则返回1，否则返回0.
intSubString_SS（SString&Sub,SStringS,intpos,intlen）
{
inti=0;
if（pos<1||len<0||pos+len>Length_SS（S）+1）return0;/*判断位置和长度是否合理*/
while（iSub[i]='\0';
return1;
}
（4）初始化串操作intStrAssign_SS（SString&T,char*s）
该操作用字符数组s，初始化定长顺序串T。
如果不产生截断（长度合理）返回1，否则返回0。
intStrAssign_SS（SString&T,char*s）
{
inti=0;
while（iT[i]=0;
if（（i==MAXLEN）&&s[i]）return0;/*判断是否产生截断*/
elsereturn1;
}
（5）串复制操作voidStrCopy_SS（SString&T,SStringS）
该操作将定长顺序串S，复制到定长顺序串T。
voidStrCopy_SS（SString&T,SStringS）
{inti=0;
while（T[i]=s[i]）i++;
}
（6）串比较操作intStrCompare_SS（SStringS,SStringT）
该操作比较顺序串S、T的大小，如果S>T则返回正数,如果S=T则返回0,否则返回负数。
intStrCompare_SS（SStringS,SStringT）
{
inti=0;
while（S[i]&&T[i]&&（S[i]==T[i]））i++;
return（int）（S[i]-T[i]）;
}
（7）串的替换操作intReplace_SS（SString&S,intn,intm,SStringT）
该操作将串S中从第n个字符开始的连续的m个字符替换成串T中的字符，如果n和m的选取合理则返回1，否则返回0。
intReplace_SS（SString&S,intn,intm,SStringT）
{
SStringS1;
intlen=Length_SS（T）;
inti=n-1,j=0,k=n+m-1;
/*i为开始替换位置，j指向第一个替换字符，k为剩余字符的开始位置*/
if（n<1||m<0||n+m>Length_SS（S）+1||Length_SS（S）+len-m>MAXLEN）return（0）;
/*判断位置是否合理*/
StrCopy_SS（S1,S）;/*将剩余部分复制到S1中*/
while（S[i++]=T[j++]）;/*替换S中指定部分的字符*/
i--;
while（S[i++]=S1[k++]）;/*将剩余部分复制到S中*/
return
（1）;
}
（8）主函数演示程序main（）
voidmain_SS（）
{
SStrings1,s2,s3,sub,T;
charstr1[100],str2[100];
intl1,l2,l3,pos,len,n;
while
（1）
{
cout<<"
（1）串初始化操作：
\n输入两个字符串:
\n";
cin.getline（str1,sizeof（str1））;
/*表示从键盘输入一个可以含有空格字符的长度小于100的字符串到str1中，语句“cin>>str1”不能输入空格字符（空格符表示输入结束）且对串的长度不做检查。
*/
cin.getline（str2,sizeof（str2））;
StrAssign_SS（s1,str1）;
StrAssign_SS（s2,str2）;
l1=Length_SS（s1）;
l2=Length_SS（s2）;
cout<<"
（2）求串长操作：
\ns1的长度="<n=StrCompare_SS（s1,s2）;
cout<<"（3）串比较操作：
\n比较结果为:
";
if（n>0）cout<<"s1>s2\n";
elseif（n==0）cout<<"s1=s2\n";
elsecout<<"s1Concat_SS（s3,s1,s2）;
cout<<"（4）串连接操作：
\ns1+s2="<l3=Length_SS（s3）;
cout<<"s1+s2的长度="<cout<<"（5）求子串操作：
\n输入开始位置和串长（poslen）:
\n";
cin>>pos>>len;
if（SubString_SS（sub,s3,pos,len））cout<<"sub="<elsecout<<"位置不正确\n";
cout<<"（6）串替换操作：
\n输入替换的位置和字符数（poslen）:
";
cin>>pos>>len;
cout<<"输入替换串:
\n";cin.get（）;
cin.getline（str1,sizeof（str1））;
StrAssign_SS（T,str1）;
if（Replace_SS（s3,pos,len,T））cout<<"替换结果为:
\ns3="<elsecout<<"替换不成功!
\n";
}
}（程序运行过程略）
3．定长顺序存储的特点
对于定长顺序存储的串在基本操作方面主要有以下特点：
（1）对于求串长度和串的复制操作而言，其时间复杂度依赖于字符串的长度；
（2）在串删除和串插入操作时必须移动大量的字符；
（3）如果在串输入、串连接、串插入和串替换操作中串值的长度超过MAXLEN，则按约定采取“截尾”法处理，这将导致操作结果的不合理。
4.2.2串的堆分配存储表示
由于串操作基本上是以串整体的形式参与，在应用程序中串变量的长度相差较大，并且在操作中串值长度的变化也比较大。
因此，事先为串变量设置固定大小空间的数组不尽合理。
用堆分配存储表示串的方法是：
在程序执行过程中，根据串变量值的大小，在堆空间中动态分配一个连续的地址空间来存储串变量中的字符，这样既可以避免产生串操作中的“截断”现象又能合理使用内存空间资源。
1．串的堆分配存储结构
在C++运行环境中，堆分配存储结构定义为
structHString
{char*ch;//串变量中字符数组的首地址
intlength;//串的长度
};
2．在堆分配存储结构中串基本操作的C++程序实现
（1）串的赋值操作voidStrAssign_HS（HString&T,charstr[]）
该操作由字符串常量str生成一个HString型串T。
voidStrAssign_HS（HString&T,charstr[]）
{intlen=0,i;
while（str[len]）len++;//计算串的长度
T.length=len;
if（!
len）T.ch=NULL;//对空串进行初始化
else
{T.ch=newchar[len+1];//在堆内存中分配相应大小的存储空间
for（i=0;T.ch[i]=str[i];i++）;//将数据从str复制到T.ch中
}
}
（2）求串长的操作intLength_HS（HStringS）
该操作返回串S的长度，如果S为空串则返回0。
intLength_HS（HStringS）{return（S.length）;}
（3）串的比较操作intStrComp_HS（HStringS,HStringT）
该操作比较串S、T的大小。
intStrComp_HS（HStringS,HStringT）
{inti;
for（i=0;iif（S.ch[i]!
=T.ch[i]）break;
return（（int）（S.ch[i]-T.ch[i]））;
}
（4）串的清空操作voidClearString_HS（HString&S）
该操作清空串S所占的堆空间。
voidClearString_HS（HString&S）
{if（S.ch）
{delete[]S.ch;
S.ch=NULL;
S.length=0;
}
}
（5）串的连接操作voidConcat_HS（HString&T,HStringS1,HStringS2）
该操作计算串S1、S2的连接串T。
voidConcat_HS（HString&T,HStringS1,HStringS2）
{
inti,j,k;
T.length=S1.length+S2.length;
i=j=k=0;
T.ch=newchar[T.length+1];//分配链接串的储存空间
while（T.ch[i++]=S1.ch[j++]）;//将S1复制到T
i--;
while（T.ch[i++]=S2.ch[k++]）;//将S2连接到T的末尾
}
（6）求子串的算法intSubString_HS（HString&Sub,HStringS,intpos,intlen）
该操作求串S中pos个字符开始的len个字符组成的子串Sub，如果位置合理返回1否则返回0。
intSubString_HS（HString&Sub,HStringS,intpos,intlen）
{
inti;
if（pos<1||len<1||pos+len>S.length+1）return（0）;//如果位置不合理时返回0值
Sub.ch=newchar[len+1];//动态分配子串的存储空间
Sub.length=len;
for（i=0;iSub.ch[i]=0;
return
（1）;
}
（7）串插入操作的算法intStrInsert_HS（HString&S,intpos,HStringH）
该操作在串S的第pos个字符前面插入字符串H，如果位置合理返回1，否则返回0。
intStrInsert_HS（HString&S,intpos,HStringH）
{
inti,j,k;
HStringS1;
if（pos<1||pos>S.length+1）return0;//位置不合理返回0值
S1.length=S.length+H.length;
S1.ch=newchar[S1.length+1];//重新分配空间
for（i=0;ik=i;
for（j=0;jwhile（S1.ch[i++]=S.ch[k++]）;//取S中剩余的内容
delete[]S.ch;
S=S1;
return1;
}
（8）串替换操作的算法intReplace_HS（HString&S,intn,intm,HStringT）
该操作将串S中第n个字符开始的m个字符替换为串T，如果位置n和字符数m合理返回1否则返回0。
intReplace_HS（HString&S,intn,intm,HStringT）
{
inti,j,k=n+m-1;
HStringS1;
if（n<1||m<0||n+m>S.length+1）return（0）;//长度或位置不合理
S1.length=S.length+T.length-m;
S1.ch=newchar[S1.length+1];//重新分配储存空间
for（i=0;ifor（j=0;jwhile（S1.ch[i++]=S.ch[k++]）;//取S中剩余的部分
delete[]S.ch;
S=S1;
return
（1）;
}
（9）主函数演示程序main（）
voidmain_HS（）
{
HStringS1,S2,S,sub,V,T;
SStringss1,ss2;
intn,pos,len;
while
（1）
{
cout<<"
（1）串初始化操作：
\n输入两个字符串:
\n";
cin.getline（ss1,sizeof（ss1））;
cin.getline（ss2,sizeof（ss2））;
StrAssign_HS（S1,ss1）;
StrAssign_HS（S2,ss2）;
cout<<"
（2）求串长操作：
\nlen1="<cout<<"len2="<cout<<"（3）串比较操作：
\n比较大小的结果为：
";
n=StrComp_HS（S1,S2）;
if（n>0）cout<<"S1>S2\n";
elseif（n<0）cout<<"S1elsecout<<"S1==S2\n";
Concat_HS（S,S1,S2）;
cout<<"（4）串连接操作：
\n:
s1+s2="<cout<<"length="<cout<<"（5）取子串操作：
\n输入取子串的位置和长度（poslen）:
\n";
cin>>pos>>len;
if（SubString_HS（sub,S,pos,len））cout<<"sub="<elsecout<<"位置不对!
\n";
cout<<"（6）串插入操作：
\n请输入插入位置:
";cin>>pos;cin.get（）;
cout<<"输入要插入的子串V:
\n";cin.getline（ss1,sizeof（ss1））;
StrAssign_HS（V,ss1）;
if（StrInsert_HS（S,pos,V））cout<<"插入结果为s="<elsecout<<"位置不对!
\n";
cout<<"（7）串替换操作；\n输入替换子串的位置和长度（poslen）:
\n";
cin>>pos>>len;cin.get（）;
cout<<"输入替换串T:
\n";cin.getline（ss1,sizeof（ss1））;
StrAssign_HS（T,ss1）;
if（Replace_HS（S,pos,len,T））cout<<"结果为s="<elsecout<<"位置不对!
\n";
}
}
3．堆分配存储表示的特点
从以上串基本操作的算法可以看出，堆分配存储结构的串既有顺序存储结构的特点，处理方便，同时在操作中对串的长度又没有任何限制，更显灵活，因此该存储结构在有关字符串处理的应用程序中常被采用。
4.2.3串的块链式存储表示
1．块链式存储的概念
和线性表的链式存储结构类似，可以采用链表方式存储串。
由于串中
升级会员 