数据结构-串

Chapter4String教学内容1、串的定义2、串的存储表示3、串的模式匹配算法串的值串的长度串的名4.1串的定义串（字符串）：是由0个或多个字符组成的有限序列。记为：s=“a1a2a3…ai…an”(n≥0)。字母、数字或其他字符必须有！作用：避免字符串与变量名或数的常量混淆。基本概念例：x=“123”x=123test=“test”作用：避免字符串与变量名或数的常量混淆。空串：不含任何字符的串，长度=0，用符号表示。空格串：仅由一个或多个空格组成的串。子串：由串中任意个连续的字符组成的子序列。主串：包含子串的串。位置：字符在序列中的序号。子串在主串中的位置：子串的首字符在主串中的位置。例：S=“JINAN”S1=“”S2=“NA”S=“JINAN”—S的子串。S4=“JAN”——非S的子串（非串S中的连续字符所组成）。在S中的位置：2在S中的位置：0串相等的条件：当两个串的长度相等且各个对应位置的字符都相等时才相等。例：S=“JINAN”S1=“JINAN”SS1空串是任意串的子串，任意串是其自身的子串。串的逻辑结构：和线性表极为相似。串的基本操作：和线性表有很大差别。区别：串的数据对象约定是字符集。线性表的基本操作：以“单个元素”为操作对象；串的基本操作：以“串的整体”作为操作对象。例：在串中查找某个子串；在串的某个位置上插入一个子串；删除一个子串等。串的抽象数据类型的定义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)初始条件：chars是字符串常量。操作结果：构造一个串值为chars的串。StrCopy(&T,S)初始条件：串S存在。操作结果：由串S复制得串T。DestroyString(&S)初始条件：串S存在。操作结果：串S被销毁。StrEmpty(S)初始条件：串S存在。操作结果：若S为空串，则返回TRUE，否则返回FALSE。StrCompare(S,T)初始条件：串S和T存在。操作结果：若ST，则返回值0；若S=T，则返回值=0；若ST，则返回值0。“串值大小”是按“词典次序”进行比较的，如：StrCompare(“data”,“stru”)0StrCompare(“cat”,“case”)0StrLength(S)初始条件：串S存在。操作结果：返回S的元素个数，称为串的长度。Concat(&T,S1,S2)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2连接而成的新串。SubString(&Sub,S,pos,len)初始条件：串S存在，0≤pos≤StrLength(S)-1且0≤len≤StrLength(S)–pos。操作结果：用Sub返回串S的第pos个字符起长度为len的子串。Index(S,T,pos)初始条件：串S和T存在，T是非空串，0≤pos≤StrLength(S)-1。操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。Replace(&S,T,V)初始条件：串S、T和V存在，T是非空串。操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。}ADTString假设S=“abcacabcaca”，T=“abca”，V=“ab”，则置换之后的S=“abcabca”，而不是“abbcaca”。例如：SubString(sub,commander,3,3)子串为“串”中的一个字符子序列求得sub=man;SubString(sub,commander,0,9)SubString(sub,commander,8,1)求得sub=r求得sub=commanderSubString(sub,commander,3,7)sub=?SubString(sub,beijing,6,2)=?sub=?SubString(student,5,0)=起始位置和子串长度之间存在约束关系长度为0的子串为“合法”串假设S=abcaabcaaabc,T=bcaIndex(S,T,0)=1;Index(S,T,3)=5;Index(S,T,8)=0;“子串在主串中的位置”意指子串中的第一个字符在主串中的位序。因为串是特殊的线性表，故其存储结构与线性表的存储结构类似，只不过组成串的结点是单个字符。4.2.1定长顺序存储表示定长顺序存储表示，也称为静态存储分配的顺序串。即用一组地址连续的存储单元依次存放串中的字符序列。4.2串的存储表示#defineMAXLEN255classString{protected:unsignedchardata[MAXLEN];intlen;//串的长度public:……..};串的实际长度可在这个预定义长度的范围内随意设定，超过预定义长度的串值则被舍去，称之为“截断”。定长顺序存储表示时串的操作的实现1、串连接Concat(&T,S1,S2)假设串T是由串S1连结串S2得到的，则只要进行相应的“串值复制”操作即可，需要时进行“截断”。串T值S1.len+S2.lenMAXLENS1.lenMAXLENS1.len+S2.lenMAXLENS1.len==MAXLEN结果正确结果S2被“截断”结果T=S1String&Concat(StringS1,StringS2){StringT;if(S1.len+S2.len=MAXLEN)//未截断{T.data[0...S1.len-1]=S1.data[0...S1.len-1];T.data[S1.len...S1.len+S2.len-1]=S2.data[0...S2.len-1];T.len=S1.len+S2.len;}elseif(S1.lenMAXLEN)//截断{T.data[0...S1.len-1]=S1.data[0...S1.len-1];T.data[S1.len...MAXLEN-1]=S2[0...MAXLEN－S1.len-1];T.len=MAXSTRLEN;}else//截断(仅取S1){T.data[0...MAXLEN-1]=S.data[0...MAXLEN-1];T.len=MAXLEN;}returnT;}//Concat定长顺序存储表示时串操作的缺点1、需事先预定义串的最大长度,这在程序运行前是很难估计的。2、由于定义了串的最大长度，使得串的某些操作受限（截尾），如串的连接、插入、置换等运算。克服办法：不限定最大长度——动态分配串值的存储空间。4.2.2堆分配存储表示堆存储结构的特点：仍以一组空间足够大的地址连续的存储单元依次存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配的。classString{protected:char*strval;intslen;//串的长度public:String(constchar*copy);………};（参考课本92页）这类串操作的实现算法为：1、为新生成的串分配一个存储空间；2、进行串值的复制。String::String()//操作结果：初始化串{slen=0;//串长度为0strval=NULL;//空串}String::~String()//操作结果：销毁串，释放串所占用空间{delete[]strval;//释放串strval}String::String(constchar*copy){length=strlen(copy);//串长strVal=newchar[slen+1];//分配存储空间strcpy(strval,copy);//复制串值}String::String(constString©){slen=copy.slen;//串长strval=newchar[slen+1];//分配存储空间strcpy(strval,copy.strval);//复制串值}String&String::Concat(String&s1,String&s2){delete[]strval;strval=newchar[s1.slen+s2.slen+1];//分配存储空间strcpy(strval,s1.strval);//复制第一个串strcat(strval,s2.strval);//连接第二个串slen=s1.slen+s2.slen;//串赋值return*this;}堆存储结构的优点：堆存储结构既有顺序存储结构的特点，处理（随机取子串）方便，操作中对串长又没有任何限制，更显灵活，因此在串处理的应用程序中常被采用。堆分配存储表示为高级程序设计语言所采用。4.2.3串的块链存储表示串值也可用单链表存储，称为链串。链串与单链表的差异只是它的结点数据域为单个字符。SABCDE^优点：便于插入和删除缺点：空间利用率低为了提高空间利用率，可使每个结点存放多个字符（这是顺序串和链串的综合(折衷)），称为块链结构。SABCDE#^存储密度=数据元素所占存储位实际分配的存储位实际应用时，可以根据问题所需来设置结点的大小。例如：在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即：同一行的串用定长结构（80个字符），行和行之间用指针相连接。4.3串的模式匹配算法设有主串s和子串t,子串t的定位就是要在主串s中找到一个与子串t相等的子串。通常把主串s称为目标串,把子串t称为模式串,因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串t；不成功则指目标串s中不存在模式串t。4.3.1简单算法从目标串s=s0s1…sn-1的第一个字符开始和模式串t=t0t1…tm-1中的第一个字符比较,若相等,则继续逐个比较后续字符；否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。依次类推,若从模式串s的第i个字符开始,每个字符依次和目标串t中的对应字符相等,则匹配成功,该算法返回i；否则,匹配失败,函数返回-1。例如,设目标串s=“cddcdc”,模式串t=“cdc”。s的长度为n(n=6),t的长度为m(m=3)。用指针i指示目标串s的当前比较字符位置,用指针j指示模式串t的当前比较字符位置，匹配过程如下所示第1次匹配s=cddcdci=2t=cdcj=2失败第2次匹配s=cddcdci=1t=cdcj=0失败第3次匹配s=cddcdci=2t=cdcj=0失败第4次匹配s=cddcdci=5t=cdcj=2成功intString::Index(constString&t){inti,j,k;for(i=0;islen;i++){//i记录当前匹配是从主串的开始位置for(j=i,k=0;data[j]==t.data[k]&&jslen;){j++;k++;}//注意j每次从i开始,有回溯if(k==t.slen)return(i);}return(-1);}算法1intString::Index(constString&t){inti=0,j=0,k=0;//记录匹配次数while(islen&&jt.slen&&kslen-t.slen+1){if(data[i]==t.data[j])//继续匹配下一个字符{i++;j++;}//主串和子串依次匹配下一个字符else//主串、子串指针回溯重新开始下一次匹配{i=i-j+1;//主串从下一个位置开始匹配j=0;k++;//子串从头开始匹配}}//返回匹配的第一个字符的下标if(j=t.slen)returni-t.slen;elsereturn-1;//模式匹配不成功}算法24.3.2KMP算法KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的,简称KMP算法。该算法较简单算法有较大改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。例