《第4章 串》习题解答.doc 24页

'第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码值，直到不相等或有一个字符串结束为止，此时的情况有以下几种：-.23.- 第4章串存储与基本操作的实现（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返回正数，SLength_SS(S)+1)return0;/*判断位置和长度是否合理*/while(iT则返回正数,如果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);-.23.- 第4章串存储与基本操作的实现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的长度="<0)cout<<"s1>s2n";elseif(n==0)cout<<"s1=s2n";elsecout<<"s1>pos>>len;if(SubString_SS(sub,s3,pos,len))cout<<"sub="<>pos>>len;cout<<"输入替换串:n";cin.get();cin.getline(str1,sizeof(str1));StrAssign_SS(T,str1);if(Replace_SS(s3,pos,len,T))cout<<"替换结果为:ns3="<S.length+1)return(0);//如果位置不合理时返回0值Sub.ch=newchar[len+1];//动态分配子串的存储空间Sub.length=len;for(i=0;iS.length+1)return0;//位置不合理返回0值S1.length=S.length+H.length;S1.ch=newchar[S1.length+1];//重新分配空间for(i=0;iS.length+1)return(0);//长度或位置不合理-.23.- 第4章串存储与基本操作的实现S1.length=S.length+T.length-m;S1.ch=newchar[S1.length+1];//重新分配储存空间for(i=0;i0)cout<<"S1>S2n";elseif(n<0)cout<<"S1>pos>>len;if(SubString_HS(sub,S,pos,len))cout<<"sub="<>pos;cin.get();cout<<"输入要插入的子串V:n";cin.getline(ss1,sizeof(ss1));StrAssign_HS(V,ss1);if(StrInsert_HS(S,pos,V))cout<<"插入结果为s="<>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="<Length_SS(S)+1)return(0);while(S[i+j]&&T[j]){if(S[i+j]==T[j])j++;//若字符相等，则继续比较后续字符else{i++;j=0;}//若不相等，则重新开始新一轮比较}if(!T[j])return(i+1);//若匹配成功，则返回T首次出现的开始位置elsereturn(0);//若匹配不成功，则返回0}算法分析：在一般情况下，BF算法的时间复杂度为O(m+n)，其中m,n分别为串S和T的长度。但是在有些情况下，该算法的效率很低。例如：S=“aaaaaa……aaaaab”共有52个‘a’和1个‘b’,T=“aaaaaaab”共有7个‘a’和1个‘b’。由于每趟比较都是在最后一个字符出现不相等，此时需要将初始位置指针i回溯到i+1的位置上，并从模式的第一个字符开始重新比较。从图4.2所示的匹配过程可以直观地算出，初始位置指针i一共要回溯52-7=45次，总的比较次数为：8×(45+1)=368次。所以，在最坏的情况下BF算法的时间复杂度为O(m×n)。4.3.2模式匹配的KMP算法模式匹配的另一种算法是由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的，称之为克努特-莫里斯-普拉特操作，简称KMP算法，他是一种改进的模式匹配算法。此算法可使时间复杂度在O(m+n)的数量级上完成串的模式匹配操作。1．模式的next数组模式匹配的KMP算法是，每当一趟匹配比较过程中出现字符不相同的情况时，不需要回溯指针i,而是利用已经得到的“部分匹配”的结果将模式T向右“滑动”尽可能远的一段距离后，再继续进行比较。为此需要引入一个有关模式串T的整型数组next，其中第j个元素next[j-1]表示当模式串T中的第j个字符与主串S中相应字符匹配失败时，在模式T中需要重新和主串S中该字符进行比较的字符的下标值。-.23.- 第4章串存储与基本操作的实现next数组定义为：其中next[j]=k表明，存在整数k满足条件0n+1)return0;//位置不合理返回0值GetNext(T,next);//计算nextwhile(i=m)return(i-m+1);//匹配成功elsereturn(0);}voidmain(){SStringS,T;intpos,n;cout<<"输入主串S:n";cin>>S;cout<<"输入子串T:n";cin>>T;cout<<"输入位置pos:n";cin>>pos;if(n=Index_KMP(S,T,pos))cout<<"首次匹配地址为:"<Length_SS(S))return(0);while(S[i+j]&&T[j]){num++;if(S[i+j]==T[j])j++;//若字符相等，则继续比较后续字符else{i++;j=0;}//若不相等，则重新开始新一轮比较}if(!T[j])return(i+1);//若匹配成功，则返回T首次出现的开始位置elsereturn(0);//若匹配不成功，则返回0}-.23.- 第4章串存储与基本操作的实现（2）函数intIndexKMP(SStringS,SStringT,int&num)的功能是通过KMP算法返回串T在S中首次出现的位置，参数num表示匹配过程中字符元素的比较次数。intIndexKMP(SStringS,SStringT,int&num){inti=0,j=0;//i指向S中第一个比较字符，j指向T中第一个字符intm=Length_SS(T),n=Length_SS(S);int*next=newint[m];//定义模式T的next数组if(m>n)return0;//匹配不成功返回0值GetNext(T,next);//计算nextnum=0;while(i=m)return(i-m+1);//匹配成功elsereturn(0);}voidmain(){SStringS,T;intn1,n2,num1,num2;while(1){cout<<"inputstringS:n";cin.getline(S,sizeof(S));cout<<"inputstringT:n";cin.getline(T,sizeof(T));n1=IndexBF(S,T,num1);n2=IndexKMP(S,T,num2);cout<<"Index_BF:nn="<m)m=next[i];return(m);}voidMaxNext(SStringT,int&m,int&n){intlen=Length_SS(T),i,k,max;//len为串长int*next=newint[len+1];//动态分配next数组，长度=len+1char*p,*str=newchar[len+2];//动态分配串strfor(i=0;str[i]=T[i];i++);//复制T到str中str[i++]="#";//str中追加追加一个非零字符"#"str[i]="";GetNext(str,next);//计算str的next数组m=1;n=Max(next,len);p=str+1;k=len-1;for(i=2;in){m=i;n=max;}-.23.- 第4章串存储与基本操作的实现}}voidmain(){intn,m;SStringS;cout<<"inputstringS:";cin.getline(S,sizeof(S));cout<<"S="<S.length)k=S.length;for(i=k;i>0;i--){pos=1;while(SubString_HS(sub,T,pos++,i))if(m=IndexBF_SS(S.ch,sub.ch)){n=i;return;}}}voidmain(){chars1[255],s2[255];HStringS,T;intm,n;cout<<"inputstringS:";cin.getline(s1,255);cout<<"inputstringT:";cin.getline(s2,255);StrAssign_HS(S,s1);StrAssign_HS(T,s2);MaxSubs(S,T,m,n);cout<<"m="<