数据结构(严蔚敏)课件第4章

第四章串【课前思考】1.串就是线性表的结论是否正确？从数据结构的观点来说，串是一种特殊的线性表;但就数据类型而言，串不是线性表。2.串和线性表的主要差别是什么？希望你带着这个问题开始这一章的学习，并能在学完这一章的内容之后能得出正确的结论。【学习目标】1.理解“串”类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。2.理解串类型的各种存储表示方法。3.理解串匹配的各种算法。【重点和难点】相对于其它各个知识点而言，本章非整个课程的重点，鉴于串已是多数高级语言中已经实现的数据类型，因此本章重点仅在于了解串类型定义中各基本操作的定义以及串的实现方法，并学会利用这些基本操作来实现串的其它操作。本章的难点是理解实现串匹配的KMP算法的思想，但它不属本章学习的基本要求，更不是重点学习内容。【知识点】串的类型定义、串的存储表示、串匹配、KMP算法【学习指南】虽然目前各常用的高级语言中都已经实现了串类型，但由于它是通过软件实现的，因此作为一个软件工作者还是应该了解串的实现方法。本章没有必须完成的算法设计题，如果有兴趣可以试试以下几个题:4.10，4.11，4.13，4.17，4.18，4.23，4.28,4.30。其中前6个是练习串的基本操作的应用，后2个是和KMP算法相关的练习。4.1串类型的定义4.2串的表示和实现4.3串的模式匹配算法4.1串的类型定义一、基本概念1．串的定义串(string)是由零个或多个字符组成的有限序列，记作s='a1a2…an'，其中s为串的名字，用成对的单引号括起来的字符序列为串的值，但两边的引号不算串值，不包含在串中。ai(1≤i≤n)可以是字母、数字或其它字符。n为串中字符的个数，称为串的长度。2．空串不含任何字符的串称为空串，它的长度n=0，记为s=''。3．空格串含有一个或多个空格的串，称为空格串，它的长度n为空格的个数，一般用符号“ø”表示空串。串是有限长的字符序列，由一对单引号相括，如:astring4．子串、主串通常将字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。若一个串是另一个串中连续的一段，则这个串称为另一个串的子串，而另一个串相对于该串称为主串。例如,串s1=“abcdefg”，s2=“fabcdefghxyz”，则s1为s2的子串，s2相对于s1为主串。另外，空串是任意串的子串，任意串是自身的子串。若一个串的长度为n，则它的子串数目为+1，真子串个数为(除串本身以外的子串都称为真子串)。当且仅当两个串的值相等时,称这两个串是相等的，即只有当两个串的长度相等,并且每个对应位置的字符都相等时才相等。2)1(nn2)1(nn二、串的抽象数据类型的定义如下：ADTString{数据对象：D＝{ai|ai∈CharacterSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}基本操作：StrAssign(&T,chars)StrCopy(&T,S)DestroyString(&S)StrEmpty(S)StrCompare(S,T)StrLength(S)Concat(&T,S1,S2)SubString(&Sub,S,pos,len)Index(S,T,pos)Replace(&S,T,V)StrInsert(&S,pos,T)StrDelete(&S,pos,len)ClearString(&S)}ADTStringStrAssign(&T,chars)初始条件：chars是字符串常量。操作结果：把chars赋为T的值。StrCopy(&T,S)初始条件：串S存在。操作结果：由串S复制得串T。DestroyString(&S)初始条件：串S存在。操作结果：串S被销毁。StrEmpty(S)初始条件：串S存在。操作结果：若S为空串，则返回TRUE，否则返回FALSE。表示空串，空串的长度为零。StrCompare(S,T)初始条件：串S和T存在。操作结果：若ST，则返回值0；若ST，则返回值0；若ST，则返回值0。例如：StrCompare(data,state)0StrCompare(cat,case)0StrLength(S)初始条件：串S存在。操作结果：返回S的元素个数，称为串的长度。Concat(&T,S1,S2)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的新串。例如：Concate(T,man,kind)求得T=mankindSubString(&Sub,S,pos,len)初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。操作结果：用Sub返回串S的第pos个字符起长度为len的子串。例如：SubString(sub,commander,4,3)求得sub=man；SubString(sub,commander,1,9)求得sub=commander；SubString(sub,commander,9,1)求得sub=r；子串为“串”中的一个字符子序列SubString(sub,commander,4,7)sub=?SubString(sub,beijing,7,2)=?sub=?SubString(student,5,0)=起始位置和子串长度之间存在约束关系长度为0的子串为“合法”串Index(S,T,pos)初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。假设S=abcaabcaaabc,T=bcaIndex(S,T,1)=2；Index(S,T,2)=6；Index(S,T,8)=0；“子串在主串中的位置”意指子串中的第一个字符在主串中的位序。Replace(&S,T,V)初始条件：串S,T和V均已存在，且T是非空串。操作结果：用V替换主串S中出现的所有与（模式串）T相等的不重叠的子串。例如：假设S=abcaabcaaabca，T=bca若V=x，则经置换后得到S=axaxaax若V=bc，则经置换后得到S=abcabcaabcStrInsert(&S,pos,T)初始条件：串S和T存在，1≤pos≤StrLength(S)＋1。操作结果：在串S的第pos个字符之前插入串T。例如：S=chater，T=rac，则执行StrInsert(S,4,T)之后得到S=characterStrDelete(&S,pos,len)初始条件：串S存在1≤pos≤StrLength(S)-len+1。操作结果：从串S中删除第pos个字符起长度为len的子串。ClearString(&S)初始条件：串S存在。操作结果：将S清为空串。对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。gets(str)输入一个串；puts(str)输出一个串；strcat(str1,str2)串联接函数；strcpy(str1,str2,k)串复制函数；strcmp(str1,str2)串比较函数；strlen(str)求串长函数；例如：C语言函数库中提供下列串处理函数：在上述抽象数据类型定义的13种操作中，串赋值StrAssign、串复制Strcopy、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等六种操作构成串类型的最小操作子集。即：这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串销毁DestroyString外）可在这个最小操作子集上实现。例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。StrCompare(SubString(S,i,StrLength(T)),T)?0S串T串T串iposn-m+1算法的基本思想为：intIndex(StringS,StringT,intpos){//T为非空串。若主串S中第pos个字符之后存在与T相等的子串，则返回第一个这样的子串在S中的位置，否则返回0if(pos0){n=StrLength(S);m=StrLength(T);i=pos;while(i=n-m+1){SubString(sub,S,i,m);if(StrCompare(sub,T)!=0)++i;elsereturni;}//while}//ifreturn0;//S中不存在与T相等的子串}//Index又如串的置换函数：Replace(&S,T,V)S串T串V串V串pospossubinews串sub串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。4.2串的表示和实现一、串的定长顺序存储表示二、串的堆分配存储表示三、串的块链存储表示一、串的定长顺序存储表示与前面所讲的线性表的顺序存储结构类似,用一组地址连续的存储单元存储串的字符序列。常常将定长顺序串设计成一种结构类型,串的存储分配是在编译时完成的。#defineMAXSTRLEN255//用户可在255以内定义最大串长typedefunsignedcharSstring[MAXSTRLEN+1];//0号单元存放串的长度或：typedefstruct{/*串结构定义*/charch[MAXLEN］;intlen;}SString;按这种串的表示方法实现的串的运算时，其基本操作为“字符序列的复制”。串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断”。特点:StatusConcat(SStringS1,SStringS2,SString&T){//用T返回由S1和S2联接而成的新串。若未截断,则返回TRUE，否则FALSE。returnuncut;}//Concat例如：串的联接算法中需分三种情况处理：T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];T[0]=S1[0]+S2[0];uncut=TRUE;}if(S1[0]+S2[0]=MAXSTRLEN){//未截断elseif(S1[0]MAXSTRSIZE){//截断else{//截断(仅取S1)T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN－S1[0]];T[0]=MAXSTRLEN;uncut=FALSE;}T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];//T[0]==S1[0]==MAXSTRLENuncut=FALSE;}(1)串插入函数。StrInsert(s,pos,t)/*在串s中序号为pos的字符之前插入串t*/SString*s,t;intpos;{inti;if(pos0||poss-len)return(0);/*插入位置不合法*/if(s-len+t.len=MAXSTRLEN){/*插入后串长≤MAXSTRLEN*/for(i=s-len+t.len-1;i=t.len+pos;i--)s-ch［i］=s-ch［i-t.len］;for(i=0;it.len;i++)s-ch［i+pos］=t.ch［i］;s-len=s-len+t.len;}定长顺序存储的操作