算法与数据结构第4章 串

第4章串4.1串的基本概念4.2串的存储结构本章小结4.3串的模式匹配串(或字符串),是由零个或多个字符组成的有穷序列。含零个字符的串称为空串,用Ф表示。串中所含字符的个数称为该串的长度(或串长)。通常将一个串表示成a1a2…an的形式。其中,最外边的双引号本身不是串的内容,它们是串的标志,以便将串与标识符(如变量名等)加以区别。每个ai(1≤i≤n)代表一个字符。4.1串的基本概念当且仅当两个串的长度相等并且各个对应位置上的字符都相同时,这两个串才是相等的。一个串中任意个连续字符组成的子序列(含空串,但不含串本身)称为该串的子串。例如,“a”、“ab”、“abc”和“abcd”等都是“abcde”的子串（真子串是指不包含自身的所有子串）。思考题：串和线性表有什么异同？例4.1问题:“abcde”有多少个真子串?解:空串数:1含1个字符的子串数:5含2个字符的子串数:4含3个字符的子串数:3含4个字符的子串数:2共有1+2+3+4+5=15个子串。串的基本运算如下:(1)StrAssign(&s,chars):将一个字符串常量赋给串s,即生成一个其值等于chars的串s。(2)StrCopy(&s,t):串复制:将串t赋给串s。(3)StrEqual(s,t):判串相等:若两个串s与t相等则返回真；否则返回假。(4)StrLength(s):求串长:返回串s中字符个数。(5)Concat(s,t):串连接:返回由两个串s和t连接在一起形成的新串。(6)SubStr(s,i,j):求子串:返回串s中从第i(1≤i≤StrLength(s))个字符开始的、由连续j个字符组成的子串。(7)InsStr(s1,i,s2):将串s2插入到串s1的第i(1≤i≤StrLength(s)+1)个字符中,即将s2的第一个字符作为s1的第i个字符,并返回产生的新串。(8)DelStr(s,i,j):从串s中删去从第i(1≤i≤StrLength(s))个字符开始的长度为j的子串,并返回产生的新串。(9)RepStr(s,i,j,t):替换:在串s中,将第i(1≤i≤StrLength(s))个字符开始的j个字符构成的子串用串t替换,并返回产生的新串。(10)DispStr(s):串输出:输出串s的所有元素值。4.2.1串的顺序存储及其基本操作实现串是一种特殊的线性表,在非紧缩格式中,它的每个结点仅由一个字符组成,因此存储串的方法也就是存储线性表的一般方法。存储串最常用的方式是采用顺序存储,即把串的字符顺序地存储在内存一片相邻的空间,这称为顺序串。4.2串的存储结构顺序存储采用一般顺序表的存储结构,其类型定义如下:#defineMaxSize100typedefstruct{chardata[MaxSize];intlength;}SqString;其中,data域用来存储字符串,length域用来存储字符串的当前长度,MaxSize常量表示允许所存储字符串的最大长度。在C语言中每个字符串以'\0'标志结束。顺序串中实现串的基本运算如下:(1)StrAssign(str,cstr)将一个字符串常量赋给串str,即生成一个其值等于cstr的串s。voidStrAssign(SqString&str,charcstr[]){inti;for(i=0;cstr[i]!='\0';i++)str.data[i]=cstr[i];str.length=i;}(2)StrCopy(s,t)将串t复制给串s。voidStrCopy(SqString&s,SqStringt)//引用型参数{inti;for(i=0;it.length;i++)s.data[i]=t.data[i];s.length=t.length;}(3)StrEqual(s,t)判断两个串是否相等:若两个串s与t相等返回真(1)；否则返回假(0)。intStrEqual(SqStrings,SqStringt){intsame=1,i;if(s.length!=t.length)same=0;//长度不相等时返回0elsefor(i=0;is.length;i++)if(s.data[i]!=t.data[i])//有一个对应字符不同时返回0{same=0;break;}returnsame;}(4)StrLength(s)求串长:返回串s中字符个数。intStrLength(SqStrings){returns.length;}(5)Concat(s,t)返回由两个串s和t连接在一起形成的新串。SqStringConcat(SqStrings,SqStringt){SqStringstr;inti;str.length=s.length+t.length;for(i=0;is.length;i++)str.data[i]=s.data[i];for(i=0;it.length;i++)str.data[s.length+i]=t.data[i];returnstr;}(6)SubStr(s,i,j)返回串s中从第i(1≤i≤StrLength(s))个字符开始的、由连续j个字符组成的子串。SqStringSubStr(SqStrings,inti,intj){SqStringstr;intk;str.length=0;if(i=0||is.length||j0||i+j-1s.length){printf(参数不正确\n);returnstr;//参数不正确时返回空串}for(k=i-1;ki+j-1;k++)str.data[k-i+1]=s.data[k];str.length=j;returnstr;}(7)InsStr(s1,i,s2)将串s2插入到串s1的第i个字符中,即将s2的第一个字符作为s1的第i个字符,并返回产生的新串。SqStringInsStr(SqStrings1,inti,SqStrings2){intj;SqStringstr;str.length=0;if(i=0||is1.length+1){printf(参数不正确\n);returns1;}for(j=0;ji-1;j++)str.data[j]=s1.data[j];for(j=0;js2.length;j++)str.data[i+j-1]=s2.data[j];for(j=i-1;js1.length;j++)str.data[s2.length+j]=s1.data[j];str.length=s1.length+s2.length;returnstr;}(8)DelStr(s,i,j)从串s中删去第i(1≤i≤StrLength(s))个字符开始的长度为j的子串,并返回产生的新串。SqStringDelStr(SqStrings,inti,intj){intk;SqStringstr;str.length=0;if(i=0||is.length||i+js.length+1)//参数不正确时返回空串{printf(参数不正确\n);returnstr;}for(k=0;ki-1;k++)str.data[k]=s.data[k];for(k=i+j-1;ks.length;k++)str.data[k-j]=s.data[k];str.length=s.length-j;returnstr;}(9)RepStr(s,i,j,t)在串s中,将第i(1≤i≤StrLength(s))个字符开始的j个字符构成的子串用串t替换,并返回产生的新串。SqStringRepStr(SqStrings,inti,intj,SqStringt){intk;SqStringstr;str.length=0;if(i=0||is.length||i+j-1s.length)//参数不正确时返回空串{printf(参数不正确\n);returnstr;}for(k=0;ki-1;k++)str.data[k]=s.data[k];for(k=0;kt.length;k++)str.data[i+k-1]=t.data[k];for(k=i+j-1;ks.length;k++)str.data[t.length+k-j]=s.data[k];str.length=s.length-j+t.length;returnstr;}(10)DispStr(s)输出串s的所有元素值。voidDispStr(SqStrings){inti;if(s.length0){for(i=0;is.length;i++)printf(%c,s.data[i]);printf(\n);}}例4.2设计顺序串上实现串比较运算Strcmp(s,t)的算法。解:本例的算法思路如下:(1)比较s和t两个串共同长度范围内的对应字符:①若s的字符＜t的字符,返回1；②若s的字符＞t的字符,返回-1；③若s的字符=t的字符,按上述规则继续比较。(2)当(1)中对应字符均相同时,比较s1和s2的长度:①两者相等时,返回0；②s的长度＞t的长度,返回1；③s的长度＜t的长度,返回-1。intStrcmp(SqStrings,SqStringt){inti,comlen;if(s.lengtht.length)comlen=s.length;elsecomlen=t.length;//求s和t的共同长度for(i=0;icomlen;i++)//逐个字符比较if(s.data[i]t.data[i])return-1;elseif(s.data[i]t.data[i])return1;if(s.length==t.length)//s==treturn0;elseif(s.lengtht.length)//streturn-1;elsereturn1;//st}4.2.2串的链式存储及其基本操作实现也可以采用链式方式存储串,即用单链表形式存储串。这称为链式串或链串。链串中的结点类型定义:typedefstructsnode{chardata;structsnode*next;}LiString;其中data域用来存储组成字符串的字符,next域用来指向下一个结点。每个字符对应一个结点,一个这样的链表存储一个字符串。下图所示是一个结点大小为1的链串。ABMN∧…s链串示意图下面讨论在链串上实现串基本运算的算法。(1)StrAssign(s,t)将一个字符串常量t赋给串s,即生成一个其值等于t的串s。以下采用尾插法建立链串。voidStrAssign(LiString*&s,chart[]){inti;LiString*r,*p;//r始终指向尾结点s=(LiString*)malloc(sizeof(LiString));r=s;for(i=0;t[i]!='\0';i++){p=(LiString*)malloc(sizeof(LiString));p-data=t[i];r-next=p;r=p;}r-next=NULL;}(2)StrCopy(s,t)将串t复制给串s。以下采用尾插法建立复制后的链串s。voidStrCopy(LiString*&s,LiString*t){LiString*p=t-next,*q,*r;s=(LiString*)malloc(sizeof(LiString));r=s;//r始终指向尾结点while(p!=NULL)//将t的所有结点复制到s{q=(LiString*)malloc(sizeof(LiString));q-data=p-data;r-next=q;r=q;p=p-next;}r-next=NULL;}(3)StrEqual(s,t)判断两个串是否相等:若两个串s与t相等则返回真(1)；否则返回假(0)。intStrEqual(LiString*s,LiString*t){LiString*p=s-next