中国科大数据结构-中科大继续教育学院

《数据结构》课程中国科学技术大学网络学院数据结构第四章字符串本章内容4.1串的基本概念4.2串的存储结构4.3串的基本运算的实现习题4中国科大《数据结构》4-34.1串的基本概念串(String)的概念：是由零个或多个字符组成的有限序列。记作：S=＂a1a2…an＂(n≥0)其中S是串名，用双引号括起来的字符序列为串值，引号是界限符，ai(1≤i≤n)是一个任意字符(字母、数字或其他字符)，它称为串的元素，是构成串的基本单位，串中所包含的字符个数n称为串的长度，当n=0时，称为空串。将串值括起来的双引号本身不属于串，它的作用是避免串与常数或与标识符混淆。例如，A=123是数字字符串，长度为3，它不同于整常数123。常将仅由一个或多个空格组成的串称为空白串。注意空串和空白串的不同，例如和分别表示长度为1的空白串和长度为0的空串。中国科大《数据结构》4-44.1串的基本概念子串的概念：串中任意连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符首次出现在主串中的位置来表示。例如，设有两个字符串C和D：C=＂Thisisastring.＂D=＂is＂则它们的长度分别为17、2；D是C的子串，C为主串。D在C中出现了两次，其中首次出现所对应的主串位置是3。因此，称D在C中的序号(或位置)为3。若两个串的长度相等且对应字符都相等，则称两个串是相等的。当两个串不相等时，可按“字典顺序”区分大小。中国科大《数据结构》4-54.1串的基本概念串也是线性表的一种，因此串的逻辑结构和线性表极为相似，区别仅在于串的数据对象限定为字符集。串的运算：1.串赋值StrAssign(&s,chars)：已知串常量chars，生成一个值等于chars的串s。2.求串长StrLength(s)：已知串s，返回串s的长度。3.串连接StrConcat(&s1,s2)：已知串s1,s2，在s1的后面连接s2的串值。4.求子串SubStr(s,i,len)：已知串s，返回从串s的第i个字符开始的长度为len的子串。5.串比较StrCmp(s1,s2)：已知串s1,s2，若s1==s2，操作返回值为0；若s1s2,返回值小于0；若s1s2,返回值大于0。中国科大《数据结构》4-64.1串的基本概念6.子串定位StrIndex(s,t)：已知串s,t，找子串t在主串s中首次出现的位置，即若t∈s，则操作返回t在s中首次出现的位置，否则返回值为－1。7.串插入StrInsert(&s,i,t)：已知串s,t，将串t插入到串s的第i个字符位置上。8.串删除StrDelete(&s,i,len)：已知串s，删除串s中从第i个字符开始的长度为len的子串。9.串替换StrRep(&s,t,r)：已知串s,t,r，用串r替换串s中出现的所有与串t相等的不重叠的子串。10.销毁串StrDestroy(&s)：已知串s，销毁串s。以上是串的一些基本操作。其中前５个操作是最为基本的，它们不能用其他的操作来合成，因此通常将这５个基本操作称为最小操作集，反之，其他操作可在这个最小操作集上实现。中国科大《数据结构》4-74.2串的存储结构4.2.1串的顺序存储顺序串：串的顺序存储结构简称为顺序串。与顺序表类似，顺序串是用一组地址连续的存储单元来存储串中的字符序列的。因此可用高级语言的字符数组来实现，按其存储分配的不同可将顺序串分为静态存储分配的顺序串和动态存储分配的顺序串两类。中国科大《数据结构》4-84.2串的存储结构1.静态存储分配的顺序串所谓静态存储分配，是指按预定义的大小为每一个串变量分配一个固定长度的存储区，即串值空间的大小在编译时刻就已确定，是静态的。所以串空间最大值为MAXSIZE时，最多只能放MAXSIZE-1个字符。其类型描述如下：#defineMAXSIZE256//该值依赖于应用，由用户定义typedefstruct{charch[MAXSIZE];//256个字符依次存储在ch[0]..ch[MAXSIZE－1]中intlen;}SString;//SString是顺序串类型，则串的最大长度不能超过255SStrings;//定义串变量s中国科大《数据结构》4-94.2串的存储结构在直接使用定长的字符数组存放串内容外，一般可使用一个不会出现在串中的特殊字符放在串值的末尾来表示串的结束。例如，C语言中以字符'\0'表示串值的终结。C语言中串的静态存储结构如下图所示：C语言中串的静态存储结构s0t1u2d3e4n5t6\07¡¡¡¡MAXSIZE-1s.ch[MAXSIZE]:s.Len=7中国科大《数据结构》4-104.2串的存储结构2.动态存储分配的顺序串(堆串)这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得的。系统将一个地址连续、容量很大的存储空间作为字符串的可用空间，每当建立一个新串时，系统就从这个空间中分配一个大小和字符串长度相同的空间存储新串的串值。假设以一维数组heap[MAXSIZE]表示可供字符串进行动态分配的存储空间，并设一整型变量free指向heap中未分配区域的开始地址。在程序执行过程中，当生成一个新串时，就从free指示的位置起为新串分配一个所需大小的存储空间，同时记录该串的相关信息。这种存储结构称为堆结构。动态分配存储空间的顺序串也叫堆串。堆串可定义如下：typedefstruct{intlength;intstart;}HeapString;中国科大《数据结构》4-114.2串的存储结构在C语言中，有一个称为“堆”的自由存储空间，并可利用malloc()和free()等动态存储管理函数，根据实际需要动态分配和释放字符数组空间，如下图所示。其类型可描述如下：typedefstruct{char*ch;//指示串的起始地址，可按实际的串长分配存储区intlen;}HString;HStrings;//定义一个串变量student\0s.chs.len7顺序串的动态存储结构中国科大《数据结构》4-124.2串的存储结构在程序中，可根据实际需求为这种类型的串变量动态分配存储空间，这样做非常有效、方便，只是在程序执行过程中要不断地生成新串和销毁旧串。中国科大《数据结构》4-134.2串的存储结构4.2.2串的链式存储顺序串上的插入和删除操作极不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串，如下图所示。abcdsef结点大小为1的链串s中国科大《数据结构》4-144.2串的存储结构链串的类型描述：typedefstructnode{charch;structnode*next;//next为指向结点的指针}LString;LStrings;//定义一个串变量s一个链串由头指针惟一确定。这种结构便于进行插入和删除运算，但存储空间利用率太低。中国科大《数据结构》4-154.2串的存储结构为了提高存储密度，可使每个结点存放多个字符。如图所示，通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。abcdefg#结点大小为4的链串中国科大《数据结构》4-164.2串的存储结构对于结点大小不为1的链串，其类型定义只需对上述的结点类型做简单的修改即可。#definenodesize80typedefstructnode{chardata[nodesize];structnode*next;}LString;虽然增大结点的数据域使得存储密度增大，但是做插入、删除运算时，需要考虑结点的分拆与合并，可能会引起大量字符的移动，给运算带来不便。中国科大《数据结构》4-174.2串的存储结构链串的插入abcxfg##yzde中国科大《数据结构》4-184.3串的基本运算的实现1.求子串运算(采用静态存储顺序串)intStrSub(SString*sub,SStrings,intpos,intlen)//用sub返回串s中序号pos开始的长度为len的子串{inti;if(pos0||poss.len||len1||lens.len-pos){sub-len=0;return(0);}//子串起始位置及长度是否合适else{for(i=0;ilen;i++)sub-ch[i]=s.ch[i+pos];sub-[len]='\0';//子串结束sub-len=len;return(1);}}中国科大《数据结构》4-194.3串的基本运算的实现2.定位运算(采用静态存储顺序串)串的定位运算也称为串的模式匹配，是一种重要的串运算。设s和t是给定的两个串，在主串s中找到等于子串t的过程称为模式匹配，如果在s中找到等于t的子串，则称匹配成功，函数返回t在s中的首次出现的存储位置(或序号)，否则匹配失败，返回－1。t也称为模式。【算法思想】首先将s0与t0进行比较，若不同，就将s1与t0进行比较……，直到s的某一个字符si和t0相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当s的某一个字符si与t的字符tj不同时，则s返回到本趟开始字符的下一个字符，即si－j+1，t返回到t0，继续开始下一趟的比较，重复上述过程。若t中的字符全部比较完，则说明本趟匹配成功，本趟的起始位置是i－j，否则，匹配失败。设主串s=“ababcabcacbab”，模式t=“abcac”，匹配过程如下图所示。ababcabcabcababc第一趟i＝3j＝3ababcabcabcaba第二趟i＝2j＝1ababcabcabcab第三趟i＝7j＝5abcacababcabcabcab第四趟i＝4j＝1aababcabcabcab第五趟i＝5j＝1aababcabcabcab第六趟i＝11j＝6abcac简单模式匹配的匹配过程中国科大《数据结构》4-214.3串的基本运算的实现模式匹配算法intStrIndex(SStrings,intpos,SStringt)//求串t在串s中的位置{inti,j;if(t.len==0)return(0);i=pos;j=0;while(is.len&&jt.len)//都没遇到结束符if(s.ch[i]==t.ch[j]){i++;j++;}//继续else{i=i-j+1;j=0;}//回溯if(j=t.len)return(i-j);//匹配成功，返回存储位置elsereturn(-1);}中国科大《数据结构》4-224.3串的基本运算的实现3．插入运算(采用动态存储串)StrInsert(HString*s,intpos,HStringt)//在串s的第pos个字符之前插入串t{char*temp;inti;if(pos0||poss-len)return(0);//pos不合理if(t.len)//t非空{temp=(char*)malloc((s-len+t.len)*sizeof(char));//临时变量，暂存插入后的结果if(temp==NULL)return(0);for(i=0;ipos;i++)temp[i]=s-ch[i];for(i=0;it.len;i++)temp[i+pos]=t.ch[i];for(i=pos;i=s-len;i++)temp[i+t.len]=s-ch[i];s-len+=t.len;free(s-ch);//释放原串ss-ch=temp;//s获得相加结果return(1);}}中国科大《数据结构》4-234.3串的基本运算的实现4．连接运算(采用动态存储串)StrCat(HString*s,HStringt)//将串t连接在串s的后面{char*temp;inti;temp=(char*)malloc((s-le