《第四章 串.ppt》由会员分享，可在线阅读，更多相关《第四章 串.ppt（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第4章章串串1.串及其基本运算串及其基本运算 2.串的顺序存储及基本运算串的顺序存储及基本运算3.串的堆存储结构串的堆存储结构4.串的链式存储结构串的链式存储结构5.文本编辑文本编辑串操作应用串操作应用【教学目的教学目的】掌握串的定义、逻辑结构、存储结构及操作掌握串的定义、逻辑结构、存储结构及操作实现以及串的应用实现以及串的应用【教学重点教学重点】串的顺序、链式、堆存储结构及串的操作的串的顺序、链式、堆存储结构及串的操作的实现实现【教学难点教学难点】串的模式匹配算法工作原理、经典的模式匹串的模式匹配算法工作原理、经典的模式匹配端法、配端法、KMP算法和改进的算法和改进的KMP算法算法4.1串
2、及其基本运算串及其基本运算 一、串的基本概念一、串的基本概念串串:是由零个或多个任意字符组成的有限序列。是由零个或多个任意字符组成的有限序列。一般记作：一般记作：s=“s1s2sn”s是是串名串名；“s1s2sn”为为串值串值，引号本身不属于串的内容；，引号本身不属于串的内容；si：串中的任一个，称为串中的任一个，称为串的元素串的元素，是构成串的基本单，是构成串的基本单位，位，i是它在整个串中的序号是它在整个串中的序号(位置位置);n为串的为串的长度长度，表示串中所包含的字符个数，表示串中所包含的字符个数当当n=0时，称为时，称为空串空串，通常记为，通常记为。子串与主串：子串与主串：串中任意连
3、续的字符组成的子序列称为该串中任意连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。串的子串。包含子串的串相应地称为主串。子串的位置：子串的位置：子串的第一个字符在主串中的序号称为子子串的第一个字符在主串中的序号称为子串的位置。串的位置。例：例：s1=“WelcometoBeijing”s2=“Welcome”s3=“Bei”s4=“Welcometo”s5=“Jing”串相等：串相等：当且仅当串值相等，即两个串的长度相等且对当且仅当串值相等，即两个串的长度相等且对应字符都相等。应字符都相等。二、串的基本操作二、串的基本操作1.求串长求串长StrLength(s)操作条件：串操
4、作条件：串s存在存在操作结果：求出串操作结果：求出串s中的字符的个数。中的字符的个数。2.串赋值串赋值StrAssign(s1,s2)操作条件：操作条件：s1是一个串变量，是一个串变量，s2或者是一个串常量，或者是一个串变量。或者是一个串常量，或者是一个串变量。操作结果：将操作结果：将s2的串值赋值给的串值赋值给s1，s1原来的值被覆盖掉。原来的值被覆盖掉。3.连接操作连接操作：StrConcat(s1,s2,s)或或StrConcat(s1,s2)操作条件：串操作条件：串s1,s2存在。存在。操作结果：两个串的联接就是将一个串的串值紧接着放在操作结果：两个串的联接就是将一个串的串值紧接着放在
5、另一个串的后面，连接成一个串。另一个串的后面，连接成一个串。4.求子串求子串SubStr(t,s,i,len)：操作条件：串操作条件：串s存在存在操作结果：产生一个新串操作结果：产生一个新串t。5.串比较串比较StrCmp(s1,s2)操作条件：串操作条件：串s1,s2存在。存在。操作结果：若操作结果：若s1=s2，操作返回值为，操作返回值为1；否则返回值为；否则返回值为0。6.子串定位子串定位StrIndex(s,t)或或StrIndex(s,t,p)操作条件：串操作条件：串s,t存在。存在。操作结果：若操作结果：若ts，则操作返回，则操作返回t在在s中首次出现的位置，中首次出现的位置，否则
6、返回值为否则返回值为-1。7.串插入串插入StrInsert(s,i,t)操作条件：串操作条件：串s,t存在，存在，1iStrLength(s)+1。操作结果：将串操作结果：将串t插入到串插入到串s的第的第i个字符位置上个字符位置上8.串删除串删除：StrDelete(s,i,len)操作条件：串操作条件：串s存在。存在。操作结果：删除串操作结果：删除串s中从第中从第i个字符开始的长度为个字符开始的长度为len的子的子串。串。9.串替换串替换StrRep(s,t,r)操作条件：串操作条件：串s,t,r存在，存在，t不为空。不为空。操作结果：用串操作结果：用串r替换串替换串s中出现的所有与串中出
7、现的所有与串t相等的不重相等的不重叠的子串。叠的子串。4.2串的顺序存储与操作串的顺序存储与操作 一、串的定长顺序存储一、串的定长顺序存储类似于顺序表，用一组地址连续的存储单元存储串值中类似于顺序表，用一组地址连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一个串变量的字符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如：分配一个固定长度的存储区，如：#defineMAXSIZE256charsMAXSIZE;则串的最大长度不能超过则串的最大长度不能超过256。如何标识实际长度？如何标识实际长度？1.类似顺序表，串描述如下：类似顺序表，串描述如下
8、：typedefstructchardataMAXSIZE;intLength;/*串的长度串的长度*/SeqString;定义一个串变量：定义一个串变量：SeqStrings;2、在串尾存储一个不会在串中出现的特殊字符作为串的终结、在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。比如符，以此表示串的结尾。比如C语言中处理定长串的方法就是语言中处理定长串的方法就是这样的，它是用这样的，它是用0来表示串的结束。这种存储方法不能直来表示串的结束。这种存储方法不能直接得到串的长度，是用判断当前字符是否是接得到串的长度，是用判断当前字符是否是0来确定串是来确定串是否结束，从而求
9、得串的长度。否结束，从而求得串的长度。charsMAXSIZE;012345678910.MAXSIZE-1abcdefghijk03、在串首存储串长。比如、在串首存储串长。比如Pascal语言中处理定长串的方法。语言中处理定长串的方法。charsMAXSIZE1;s0：存放串长：存放串长s1.ss0：存放串值：存放串值012345678910.MAXSIZE9abcdefghi.1、求串长、求串长intStrLength(chars)inti=0;while(si!=0)i+;returni;return(s0)2、串赋值、串赋值voidStrAssign(chars1,char*s2)in
10、ti;for(i=0;s2i!=0;i+)s1i=s2i;s1i=0;for(i=0;s2i!=0;i+)s1i+1=s2i;s10=i;串拷贝：串拷贝：for(i=0;iMAXSIZE-1)return0;for(j=0;s1j!=0;j+,i+)si=s1j;for(j=0;s2j!=0;j+,i+)si=s2j;si=0;return1;for(j=1,i=1;j=s10;j+,i+)si=s1j;for(j=1;j=s20;j+,i+)si=s2j;s0=s10+s20;4、求子串、求子串intSubStr(chart,chars,inti,intlen)/用用t返回串返回串s中第个中
11、第个i字符开始的长度为字符开始的长度为len的子串的子串intslen;slen=StrLength(s);if(islen|lenslen-i+1)printf(参数不对参数不对);return0;for(j=0;jlen;j+)tj=si-1+j;tj=0;return1;for(j=1;j=len;j+)tj=si-1+j;t0=len;5、串比较、串比较intStrCmp(chars1,chars2)/串串s1与串与串s2若相等则返回若相等则返回1，否则返回，否则返回0inti=0;while(s1i!=0&s2i!=0&s1i=s2i)i+;return(s1i=s2i);C：ret
12、urn(s1i-s2i);6、子串定位、子串定位StrIndex(s,t)：模式匹配：模式匹配串的模式匹配即子串定位是一种重要的串运算。串的模式匹配即子串定位是一种重要的串运算。设设s和和t是给定的两个串，在主串是给定的两个串，在主串s中找到等于子串中找到等于子串t的过程称为的过程称为模式匹配，如果在模式匹配，如果在s中找到等于中找到等于t的子串，则称匹配成功，函数的子串，则称匹配成功，函数返回返回t在在s中的首次出现的存储位置中的首次出现的存储位置(或序号或序号)，否则匹配失败，否则匹配失败，返回返回-1。t称为模式串，称为模式串，s称为主串。为了运算方便，设字符串称为主串。为了运算方便，设
13、字符串的长度存放在的长度存放在0号单元，串值从号单元，串值从1号单元存放，这样字符序号与号单元存放，这样字符序号与存储位置一致。存储位置一致。算法思想如下：算法思想如下：首先将首先将s1与与t1进行比较，若不同，就将进行比较，若不同，就将s2与与t1进行比进行比较较,.，直到，直到s的某一个字符的某一个字符si和和t1相同，再将它们之后的相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当字符进行比较，若也相同，则如此继续往下比较，当s的的某一个字符某一个字符si与与t的字符的字符tj不同时，则不同时，则s返回到本趟开始字符返回到本趟开始字符的下一个字符，即的下一个字符，即si-
14、j+2，t返回到返回到t1，继续开始下一趟的，继续开始下一趟的比较，重复上述过程。若比较，重复上述过程。若t中的字符全部比完，则说明本中的字符全部比完，则说明本趟匹配成功，本趟的起始位置是趟匹配成功，本趟的起始位置是i-j+1或或i-t0，否则，匹配，否则，匹配失败。失败。简单模式匹配过程简单模式匹配过程设主串设主串s=ababcabcacbab，模式，模式t=abcac，匹配过程，匹配过程:ababcabcacbababcacij依据这个思想，简单的模式匹配算法（依据这个思想，简单的模式匹配算法（BF）描述如下）描述如下:intStrIndex_BF(char*s,char*t)/从串从串s
15、的第一个字符开始找首次与串的第一个字符开始找首次与串t相等的子串相等的子串inti=1,j=1;while(i=s0&jt0)return(i-t0);/匹配成功，返回存储位置匹配成功，返回存储位置elsereturn1;简单的模式匹配算法（简单的模式匹配算法（BF）时间复杂度分析）时间复杂度分析:设串设串s长度为长度为n，串，串t长度为长度为m，在匹配成功的情况下，在匹配成功的情况下考虑两种极端情况：考虑两种极端情况：（1）在最好情况下，每趟不成功的匹配都发生在第一对字符）在最好情况下，每趟不成功的匹配都发生在第一对字符比较时：比较时：例如：例如：s=“aaaaaaaaaabc”t=bc设匹
16、配成功发生在设匹配成功发生在si处，则字符比较次数在前面处，则字符比较次数在前面i-1趟匹趟匹配中共比较了配中共比较了i-1次，第次，第i趟成功的匹配共比较了趟成功的匹配共比较了m次，所以总共次，所以总共比较了比较了i-1+m次，所有匹配成功的可能共有次，所有匹配成功的可能共有n-m+1种，设从种，设从si开开始与始与t串匹配成功的概率为串匹配成功的概率为pi，在等概率情况下，在等概率情况下pi=1/(n-m+1)，因此最好情况下平均比较的次数是：因此最好情况下平均比较的次数是：简单的模式匹配算法（简单的模式匹配算法（BF）时间复杂度分析）时间复杂度分析:设串设串s长度为长度为n，串，串t长度
17、为长度为m，在匹配成功的情况下，在匹配成功的情况下考虑两种极端情况：考虑两种极端情况：（2）在最坏情况下，每趟不成功的匹配都发生在在最坏情况下，每趟不成功的匹配都发生在t的最后一的最后一个字符：例如：个字符：例如：s=“aaaaaaaaaaab”t=aaab设匹配成功发生在设匹配成功发生在si处，则在前面处，则在前面i-1趟匹配中共比较了趟匹配中共比较了(i-1)*m次，第次，第i趟成功的匹配共比较了趟成功的匹配共比较了m次，所以总共比较了次，所以总共比较了i*m次，因此最坏的情况下平均比较的次数是：次，因此最坏的情况下平均比较的次数是：因此：因此：BF算法的时间复杂度为算法的时间复杂度为O（
18、mn）简单的模式匹配算法（简单的模式匹配算法（BF）说明）说明:上述算法中匹配是从上述算法中匹配是从s串的第一个字符开始的，有时算法要串的第一个字符开始的，有时算法要求从指定位置开始，这时算法的参数表中要加一个位置参数求从指定位置开始，这时算法的参数表中要加一个位置参数pos：StrIndex(shar*s,intpos,char*t)，比较的初始位置定位，比较的初始位置定位在在pos处也可以。上面的算法是处也可以。上面的算法是pos=1的情况。的情况。同理第五趟也是没有必要的，所以从第三趟之后可以直接到第同理第五趟也是没有必要的，所以从第三趟之后可以直接到第六趟，进一步分析第六趟中的第一对字
19、符六趟，进一步分析第六趟中的第一对字符s6和和t1的比较也是多的比较也是多余的，因为第三趟中已经比过了余的，因为第三趟中已经比过了s6和和t4，并且，并且s6=t4，而，而t1=t4，必有，必有s6=t1，因此第六趟的比较可以从第二对字符，因此第六趟的比较可以从第二对字符s7和和t2开开始进行，这就是说，第三趟匹配失败后，指针始进行，这就是说，第三趟匹配失败后，指针i不动，而是将不动，而是将模式串模式串t向右向右“滑动滑动”，用，用t2“对准对准”s7继续进行，依此类推。继续进行，依此类推。这样的处理方法指针这样的处理方法指针i是无回溯的。是无回溯的。一、改进的快速模式匹配算法（一、改进的快速
20、模式匹配算法（KMP）12345678910 11 12 13ababcabcacbababcac12345ij算法思想如下：分析算法思想如下：分析BF算法的执行过程算法的执行过程,造成造成BF算法速度慢算法速度慢的原因是回溯，即在某趟的匹配过程失败后，对于的原因是回溯，即在某趟的匹配过程失败后，对于s串要回到串要回到本趟开始字符的下一个字符，本趟开始字符的下一个字符，t串要回到第一个字符。而这些串要回到第一个字符。而这些回溯并不是必要的。在匹配过程中，在第三趟匹配过程中，回溯并不是必要的。在匹配过程中，在第三趟匹配过程中，s3s6和和t1t4是匹配成功的，是匹配成功的，s7t5匹配失败，因此
21、有了第四匹配失败，因此有了第四趟，其实这一趟是不必要的：由图可看出，因为在第三趟中趟，其实这一趟是不必要的：由图可看出，因为在第三趟中有有s4=t2，而，而t1t2，肯定有，肯定有t1s4。改进的快速模式匹配算法（改进的快速模式匹配算法（KMP）:综上所述，希望某趟在综上所述，希望某趟在si和和tj匹配失败后，指针匹配失败后，指针i不回溯，模不回溯，模式式t向右向右“滑动滑动”至某个位置上，使得至某个位置上，使得tk对准对准si继续向右进行。继续向右进行。显然，现在问题的关键是串显然，现在问题的关键是串t“滑动滑动”到哪个位置上？不妨设位到哪个位置上？不妨设位置为置为k，即，即si和和tj匹配
22、失败后，指针匹配失败后，指针i不动，模式不动，模式t向右向右“滑动滑动”，使使tk和和si对准继续向右进行比较，要满足这一假设，就要有如下对准继续向右进行比较，要满足这一假设，就要有如下关系成立：关系成立：“t1t2tk-1”=“si-k+1si-k+2si-1”(1)式左边是式左边是tk前面的前面的k-1个字符，右边是个字符，右边是si前面的前面的k-1个字符。个字符。而本趟匹配失败是在而本趟匹配失败是在si和和tj之处，已经得到的部分匹配结果是之处，已经得到的部分匹配结果是“t1t2tj-1”=“si-j+1si-j+2si-1”(2)因为因为kj，所以有：，所以有：“tj-k+1tj-k
23、+2tj-1”=“si-k+1si-k+2si-1”(3)左边是左边是tj前面的前面的k-1个字符，右边是个字符，右边是si前面的前面的k-1个字符，通过个字符，通过(1)和和(3)得到关系：得到关系：t1t2tk-1=tj-k+1tj-k+2tj-1”(4)改进的快速模式匹配算法（改进的快速模式匹配算法（KMP）:综上所述，希望某趟在综上所述，希望某趟在si和和tj匹配失败后，指针匹配失败后，指针i不回溯，模不回溯，模式式t向右向右“滑动滑动”至某个位置上，使得至某个位置上，使得tk对准对准si继续向右进行。继续向右进行。显然，现在问题的关键是串显然，现在问题的关键是串t“滑动滑动”到哪个位
24、置上？不妨设位到哪个位置上？不妨设位置为置为k，即，即si和和tj匹配失败后，指针匹配失败后，指针i不动，模式不动，模式t向右向右“滑动滑动”，使使tk和和si对准继续向右进行比较，要满足这一假设，就要有如下对准继续向右进行比较，要满足这一假设，就要有如下关系成立：关系成立：“t1t2tk-1”=“si-k+1si-k+2si-1”(1)式左边是式左边是tk前面的前面的k-1个字符，右边是个字符，右边是si前面的前面的k-1个字符。个字符。而本趟匹配失败是在而本趟匹配失败是在si和和tj之处，已经得到的部分匹配结果是之处，已经得到的部分匹配结果是“t1t2tj-1”=“si-j+1si-j+2
25、si-1”(2)因为因为kj，所以有：，所以有：“tj-k+1tj-k+2tj-1”=“si-k+1si-k+2si-1”(3)左边是左边是tj前面的前面的k-1个字符，右边是个字符，右边是si前面的前面的k-1个字符，通过个字符，通过(1)和和(3)得到关系：得到关系：t1t2tk-1=tj-k+1tj-k+2tj-1”(4)改进的快速模式匹配算法（改进的快速模式匹配算法（KMP）:结论：某趟在结论：某趟在si和和tj匹配失败后，如果模式串中有满匹配失败后，如果模式串中有满足关系足关系(4)的子串存在，即：的子串存在，即：模式中的前模式中的前k-1个字符与个字符与模式中模式中tj字符前面的字
26、符前面的k-1个字符相等时个字符相等时，模式，模式t就可以向就可以向右右“滑动滑动”至使至使tk和和si对准，继续向右进行比较即可。对准，继续向右进行比较即可。t1t2tk-1=tj-k+1tj-k+2tj-1”(4)KMP算法求解转为求模式串算法求解转为求模式串t的每个字符匹配失败时的每个字符匹配失败时的向右滑动多少的问题（即求的向右滑动多少的问题（即求nextj）KMP算法中算法中nextj的求法的求法:模式中的每一个模式中的每一个tj都对应一个都对应一个k值，由值，由(4)式可知，这个式可知，这个k值值仅依赖与模式仅依赖与模式t本身字符序列的构成，而与主串本身字符序列的构成，而与主串s无
27、关。用无关。用nextj表示表示tj对应的对应的k值。值。根据以上分析，根据以上分析，next函数有如下性质：函数有如下性质：nextj是一个整数，且是一个整数，且0nextjj为了使为了使t的右移不丢失任何匹配成功的可能，当存在多个的右移不丢失任何匹配成功的可能，当存在多个满足满足(4)式的式的k值时，应取最大的，这样向右值时，应取最大的，这样向右“滑动滑动”的距离最的距离最短，短，“滑动滑动”的字符为的字符为j-nextj个。个。如果在如果在tj前不存在满足前不存在满足(4)式的子串，此时若式的子串，此时若t1tj，则，则k=1;若若t1=tj，则，则k=0;这时这时“滑动滑动”的最远，为
28、的最远，为j-1个字符即用个字符即用t1和和sj+1继续比较。继续比较。因此，因此，next函数定义如下函数定义如下：KMP算法中算法中nextj的求法的求法:next函数函数：0当当j=1maxk|1=kj且且”t1t2tk-1”=“tj-k+1tj-k+2tj-1“1当不存在上面的当不存在上面的knextj=j1 2 3 4 5 6 7 8 9模式串模式串a b ca a b a b cnextj0 1 1 1 2 2 3 2 3KMP算法中算法中nextj的求法的求法:Next改进函数改进函数：0当当j=1maxk|1=kj且且”t1t2tk-1“=“tj-k+1tj-k+2tj-11当
29、不存在上面的当不存在上面的k且且t1tj0当不存在上面的当不存在上面的k且且t1=tjnextj=j1 2 3 4 5 6 7 8 9模式串模式串a b ca a b a b cnextj0 1 1 0 2 2 3 2 3KMP算法算法:在求得模式的在求得模式的next函数之后，匹配可如下进行：假设以指函数之后，匹配可如下进行：假设以指针针i和和j分别指示主串和模式中的比较字符，令分别指示主串和模式中的比较字符，令i的初值为的初值为pos，j的初值为的初值为1。若在匹配过程中。若在匹配过程中si=tj，则，则i和和j分别增，若分别增，若sitj匹匹配失败后，则配失败后，则i不变，不变，j退到退
30、到nextj位置再比较，若相等，则指位置再比较，若相等，则指针各自增，否则针各自增，否则j再退到下一个再退到下一个next值的位置，依此类推。直值的位置，依此类推。直至下列两种情况：一种是至下列两种情况：一种是j退到某个退到某个next值时字符比较相等，则值时字符比较相等，则i和和j分别增继续进行匹配分别增继续进行匹配;另一种是另一种是j退到值为零（即模式的退到值为零（即模式的第一个字符失配），则此时第一个字符失配），则此时i和和j也要分别增，表明从主串的也要分别增，表明从主串的下一个字符起和模式重新开始匹配。下一个字符起和模式重新开始匹配。设主串设主串s=aabcbabcaabcaababc
31、，子串，子串t=abcaababc，第一趟第一趟第二趟第二趟第三趟第三趟第四趟第四趟KMP算法算法:intStrIndex_KMP(char*s,char*t,intpos)/*从串从串s的第的第pos个字符开始找首次与串个字符开始找首次与串t相等的子串相等的子串*/inti=pos,j=1;while(i=s0&jt0)returni-t0;/*匹配成功，返回存储位置匹配成功，返回存储位置*/elsereturn1;4.3串的堆存储结构串的堆存储结构 堆存储结构的基本思想是：用一组地址连续的存储堆存储结构的基本思想是：用一组地址连续的存储单元来存放串值，只不过这段空间是动态分配的。单元来存放
32、串值，只不过这段空间是动态分配的。typedefstructchar*ch;/若是非空串若是非空串,则按串长分配存储区则按串长分配存储区,否则否则ch为为NULLintlength;/串长度串长度HString；1.串赋值串赋值intStrAssign(HString*s,char*t)inti,j;if(s-ch)free(s-ch);for(i=0;ti!=0;+i);if(!i)s-ch=NULL;s-length=0;elses-ch=(char*)malloc(i*sizeof(char);for(j=0;jchj=tj;s-length=i;return1;2.串比较串比较intS
33、trCompare(HString*s1,HString*s2)inti;for(i=0;ilength&ilength;+i)if(s1-chi!=s2-chi)return(s1-chi-s2-chi);returns1-length-s2-length;3.清空串清空串intStrClear(HString*s)if(s-ch)free(s-ch);s-ch=NULL;s-length=0;return1;4.串连接串连接intStrConcat(HString*s1,HString*s2,HString*s)inti,j;if(s-ch)free(s-ch);s-ch=(char*)m
34、alloc(s1-length+s2-length)*sizeof(char);for(i=0;ilength;i+)s-chi=s1-chi;for(j=0;jlength;i+)s-chi+j=s2-chj;s-length=s1-length+s2-length;return1;5.求子串求子串intStrSub(HString*t,HString*s,inti,intlen)intj;if(is-length|lenS-length-i+1)return0;if(!len)t-ch=NULL;t-length=0;elset-ch=(char*)malloc(len*sizeof(ch
35、ar);for(j=0;jchj=S-chi-1+j;t-length=len;return1;6.串插入串插入intStrInsert(HString*s,inti;HString*t)intj;if(is-length+1)return0;if(t-length)s-ch=(char*)realloc(s-ch,(s-length+t-length)*sizeof(char);for(j=S-length-1;j=i-1;j-)S-chj+t-length=S-chj;for(j=0;jlength;j+)S-chi-1+j=t-chj;S-length+=t-length;return1
36、;4.4串的链式存储结构串的链式存储结构 和线性表的链式存储结构相类似，也可以用链表方式存储串和线性表的链式存储结构相类似，也可以用链表方式存储串值。由于串结构的特殊性，即结构中的每个数据元素是一个字值。由于串结构的特殊性，即结构中的每个数据元素是一个字符，用链表存储串值时，存在一个符，用链表存储串值时，存在一个“结点大小结点大小”的问题，也就的问题，也就是每个结点可以存放一个字符，也可以存放多个字符。例如，是每个结点可以存放一个字符，也可以存放多个字符。例如，图图4.9(a)是结点大小为是结点大小为4(即每个结点存放四个字符即每个结点存放四个字符)的链表，图的链表，图4.9(b)是结点大小为
37、是结点大小为1的链表。当结点大小大于的链表。当结点大小大于1时，由于串长时，由于串长不一定是结点大小的整倍数，链表中的最后一个结点不一定全不一定是结点大小的整倍数，链表中的最后一个结点不一定全被串值占满，此时补上被串值占满，此时补上“#”或其它的非串值字符（通常或其它的非串值字符（通常“#”不属于串的字符集，是一个特殊的符号）不属于串的字符集，是一个特殊的符号）.串的应用文本编辑串的应用文本编辑 串的应用十分广泛，例如文本编辑程序、关键字串的应用十分广泛，例如文本编辑程序、关键字检索程序等。下面用一个实例说明字符串的存储及插检索程序等。下面用一个实例说明字符串的存储及插入、删除等基本操作在文本
38、编辑中的实际应用。入、删除等基本操作在文本编辑中的实际应用。文本编辑的实质就是利用串的基本操作，完成对文本编辑的实质就是利用串的基本操作，完成对文本的添加、删除和修改等操作，其实也就是修改字文本的添加、删除和修改等操作，其实也就是修改字符数据的形式和格式。虽然各种文本编辑程序的功能符数据的形式和格式。虽然各种文本编辑程序的功能强弱不同，但是其基本操作是一致的，一般都包括串强弱不同，但是其基本操作是一致的，一般都包括串的查找、插入和删除等基本运算。因此，对用户来说的查找、插入和删除等基本运算。因此，对用户来说若能利用计算机系统提供的文本编辑程序，则可以方若能利用计算机系统提供的文本编辑程序，则可
39、以方便地完成各种修改工作。便地完成各种修改工作。为了编辑的方便，用户可以利用换页符和换行符为了编辑的方便，用户可以利用换页符和换行符把文本划分为若干页，每页有若干行（当然，也可不把文本划分为若干页，每页有若干行（当然，也可不分页而把文本直接划分成若干行）。分页而把文本直接划分成若干行）。串的应用文本编辑串的应用文本编辑 串的应用十分广泛，例如文本编辑程序、关键字检索串的应用十分广泛，例如文本编辑程序、关键字检索程序等。下面用一个实例说明字符串的存储及插入、删除程序等。下面用一个实例说明字符串的存储及插入、删除等基本操作在文本编辑中的实际应用。等基本操作在文本编辑中的实际应用。文本编辑的实质就是
40、利用串的基本操作，完成对文本文本编辑的实质就是利用串的基本操作，完成对文本的添加、删除和修改等操作，其实也就是修改字符数据的的添加、删除和修改等操作，其实也就是修改字符数据的形式和格式。虽然各种文本编辑程序的功能强弱不同，但形式和格式。虽然各种文本编辑程序的功能强弱不同，但是其基本操作是一致的，一般都包括串的查找、插入和删是其基本操作是一致的，一般都包括串的查找、插入和删除等基本运算。因此，对用户来说若能利用计算机系统提除等基本运算。因此，对用户来说若能利用计算机系统提供的文本编辑程序，则可以方便地完成各种修改工作。供的文本编辑程序，则可以方便地完成各种修改工作。为了编辑的方便，用户可以利用换页符和换行符把文为了编辑的方便，用户可以利用换页符和换行符把文本划分为若干页，每页有若干行（当然，也可不分页而把本划分为若干页，每页有若干行（当然，也可不分页而把文本直接划分成若干行）。文本直接划分成若干行）。