数据结构ch04学习教案

1、数据结构数据结构(sh j ji u) ch04第一页，共36页。 在计算机的应用中，非数值处理问题的应用越来越多。如在汇在计算机的应用中，非数值处理问题的应用越来越多。如在汇编程序和编译程序中，源程序和目标程序都是作为一种字符串数据编程序和编译程序中，源程序和目标程序都是作为一种字符串数据进行处理的。在事务处理系统中，用户的姓名和地址及货物的名称、进行处理的。在事务处理系统中，用户的姓名和地址及货物的名称、规格等也是字符串数据。规格等也是字符串数据。 字符串一般简称为串，可以将它看作是一种特殊的线性表，这字符串一般简称为串，可以将它看作是一种特殊的线性表，这种线性表的数据元素的类型总是字符型

2、的，字符串的数据对象约束种线性表的数据元素的类型总是字符型的，字符串的数据对象约束为字符集。为字符集。 在线性表的基本操作中，大多以在线性表的基本操作中，大多以“单个元素单个元素”作为操作对象，作为操作对象，而在串中，则是以而在串中，则是以“串的整体串的整体”或一部分作为操作对象。因此或一部分作为操作对象。因此(ync)，线性表和串的操作有很大的不同。，线性表和串的操作有很大的不同。 本章主要讨论串的基本概念、存储结构和一些基本的串处理操本章主要讨论串的基本概念、存储结构和一些基本的串处理操作。作。第1页/共36页第二页，共36页。 串是一种特殊的线性表，它的数据对象是字符集合。串是一种特殊的

3、线性表，它的数据对象是字符集合。 4.1.1 4.1.1 串的定义串的定义 串（或字符串）是由零个或多个字符组成的有限序列。一般记作：串（或字符串）是由零个或多个字符组成的有限序列。一般记作： s= s=c0c1c2cn-1c0c1c2cn-1 (n0) (n0) 其中其中(qzhng)(qzhng)：s s为串名，用双引号括起来的字符序列是串的值；为串名，用双引号括起来的字符序列是串的值；ci(0in-1)ci(0in-1)可以是字母、数字或其它字符；双引号为串值的定界符，不是串的一部分；字符串字符的数目可以是字母、数字或其它字符；双引号为串值的定界符，不是串的一部分；字符串字符的数目n n

4、称为串的长度。称为串的长度。 零个字符的串称为空串，通常以两个相邻的双引号来表示空串零个字符的串称为空串，通常以两个相邻的双引号来表示空串 如：如：s=s=，它的长度为零；，它的长度为零； 仅由空格组成的的串称为空格串仅由空格组成的的串称为空格串 如：如：s=s= ；4.1 串及其运算串及其运算(yn sun)第2页/共36页第三页，共36页。 若串中含有空格，在计算串长时，空格应计入若串中含有空格，在计算串长时，空格应计入(j r)串的长度中串的长度中 如：如：s=Im a student的长度为的长度为13。 注意：在注意：在C语言中，用单引号引起来的单个字符与单个字符的串是不同的，语言中

5、，用单引号引起来的单个字符与单个字符的串是不同的， 如如s1=a与与s2=a两者是不同的，两者是不同的，s1表示字符，表示字符，s2表示字符串。表示字符串。 当两个串的长度相等且各对应位置上的字符都相同时，这两个串是相等的。当两个串的长度相等且各对应位置上的字符都相同时，这两个串是相等的。 串中任意个连续字符组成的序列称为该串的子串。包含子串的串被称为主串。串中任意个连续字符组成的序列称为该串的子串。包含子串的串被称为主串。 例如，例如，com、om、a和和man都是都是commander的子串。子串在主的子串。子串在主串中的位置是指子串中第一个字符在主串中的位置序号。如子串串中的位置是指子串

6、中第一个字符在主串中的位置序号。如子串man在主串在主串commander中的位置为中的位置为4。 第3页/共36页第四页，共36页。 串是一种简单的数据结构，它的逻辑(lu j)结构与线性表十分相似，区别仅在于串的数据对象是字符集。 串的基本运算与线性表的基本运算有很大差别。通常在串的基本运算中，以“串的整体”作为操作对象；而在线性表的基本运算中，大多以“单个元素”作为操作对象。 4.1.2 串的基本运算串的基本运算 串的常用基本运算主要有：串的常用基本运算主要有：1Strassign(s,chars)功能：赋值运算功能：赋值运算 将串常量将串常量chars的值赋给串变量的值赋给串变量s。例

7、如例如(lr)：执行：执行strassign(s，abcd)运算之后，运算之后，s的值为的值为abcd。第4页/共36页第五页，共36页。2Assign(s,t)功能：赋值运算。将串变量功能：赋值运算。将串变量t的值赋给串变量的值赋给串变量s。例如：例如：t=abcd，则执行，则执行Assign(s,t)运算之后，运算之后，s的值为的值为abcd。3Equal(s,t)功能：判相等运算。若功能：判相等运算。若s与与t的值相等则运算结果的值相等则运算结果(ji gu)为为1，否，否则为则为0。4Length (s) 功能：求串长运算。求串功能：求串长运算。求串 s序列中字符的个数，即串的长度。序

8、列中字符的个数，即串的长度。5Concat (s,t)功能：联接运算。将串功能：联接运算。将串t的第一个字符紧接在串的第一个字符紧接在串 s的最后一个字符的最后一个字符之后，联接得到一个新串。例如之后，联接得到一个新串。例如s=man,t=kind，则执行，则执行Concat (s,t)运算后得到的新串为运算后得到的新串为mankind。 第5页/共36页第六页，共36页。 6Insert (s,pos, t)功能：插入运算，当1pos Length (s)+1时，在串 s的第 pos 个字符之前插入串 t。7Delete (s,pos,len)功能：删除运算。当1posLength(s)且0

9、lenLength (s)-pos+1时，从串s中删去从第pos个字符起长度为len的子串。 8Replace (s,pos,len,t)功能：置换运算。当1posLength (s)且0lenLength(s)-pos+1时，用串t替换串s中从第 pos 个字符起长度为len的子串。 对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。 下面(xi mian)仅介绍几种在C语言中常用的串运算，其它的串操作见文件。第6页/共36页第七页，共36页。 定义下列几个变量： char s120=“dirtreeformat”, s220=“file.mem”; char s330,*

10、p; int result; (1)求串长(length) int strlen(char s); /求串的长度 例如：printf(“%d”,strlen(s1); 输出13 （2）串复制(copy) char *strcpy(char to,char from); 该函数将串from复制到串to中，并且返回一个指向(zh xin)串to的开始处的指针。 例如：strcpy(s3,s1); /s3=“dirtreeformat” 第7页/共36页第八页，共36页。 (3)联接(concatenation) char strcat(char to,char from) 该函数将串from复制到

11、串to的末尾，并且返回一个指向串to的开始处的指针。 例1、求子串 求子串的过程(guchng)即为复制字符序列的过程(guchng)，将串S中的第pos个字符开始长度为len的字符复制到串T中。 void substr(string sub,string s,int pos,int len) if(posstrlen(s)-1 | len0) n=strlen(s); m=strlen(t); i=pos; while(in-m+1) substr(sub,s,i,m); if(strcmp(sub,t) !=0) +i; else return(i); return(0); 第9页/共36

12、页第十页，共36页。4.2 串的存储串的存储(cn ch)结构结构 串是一种特殊的线性表，其存储结构与线性表的存储结构类似，只不过组成串的结点是单个字符。串的存储结构表示有两种方法：静态存储和动态(dngti)存储 静态存储采用顺序存储结构，动态(dngti)存储采用的是链式存储和堆存储结构。4.2.1 串的顺序存储结构及其基本运算的实现 1顺序存储结构 （静态） 串的顺序存储结构是采用与其逻辑结构相对应的存储结构，将串中的各个字符按顺序依次存放在一组地址连续的存储单元里，逻辑上相邻的字符在内存中也相邻。 第10页/共36页第十一页，共36页。 类似于线性表的顺序存储结构，用一组地址连续的存储

13、单元存储类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。串值的字符序列。 这是一种静态这是一种静态(jngti)存储结构，串值的存储分配是在编译时完成的存储结构，串值的存储分配是在编译时完成的。因此，需要预先定义串的存储空间大小。如果定义的空间过大，则会。因此，需要预先定义串的存储空间大小。如果定义的空间过大，则会造成空间浪费；如果定义的空间过小，则会限制串的某些运算，如联接造成空间浪费；如果定义的空间过小，则会限制串的某些运算，如联接、置换运算等。、置换运算等。 2基本运算在顺序存储结构上的实现基本运算在顺序存储结构上的实现在顺序存储结构中，串的类型定义描述如下：在顺

14、序存储结构中，串的类型定义描述如下：#define MaxLen ; /定义能处理的最大的串长度定义能处理的最大的串长度 typedef struct char strMaxLen; /定义可容纳定义可容纳MaxLen个字符的字符数组个字符的字符数组 int curlen; /定义当前实际串长度定义当前实际串长度 string; 第11页/共36页第十二页，共36页。以下给出采用以下给出采用(ciyng)顺序存储结构时串的联接运算。顺序存储结构时串的联接运算。（1）Concat (s,t)string Concat(string s,string t) / 将串将串t的第一个字符紧接在串的第一

15、个字符紧接在串 s 的最后一个字符之后的最后一个字符之后 string ch; int i; ch. curlen=s. curlen+t. curlen; / 将将s. str0s.strs.curlen-1复制到复制到ch for(i=0;is.curlen;i+) ch.stri=s.stri; / 将将t. str0t. strt.curlen-1复制到复制到ch for(i=0;it，则输出正数；，则输出正数；如果如果st，则输出负数。，则输出负数。算法如下：算法如下：int strcmp(string s,string t) int i, st_len; if(s. cur1en

16、t. cur1en) /求取求取s和和t长度短者长度短者 st_len=s.cur1en; else 第13页/共36页第十四页，共36页。else st_len=t. cur1en; for(i=0;(ist_len)&(s.stri=t. stri); i+); if(i=st_len) if(s. cur1en=t.cur1en) /s=t return 0; else if (s. cur1ent. cur1en) /st return 1; else return s. stri-t. stri; /st或或st第14页/共36页第十五页，共36页。4.2.2 串的链式存储结

17、构及其基本运算的实现串的链式存储结构及其基本运算的实现 1链式存储结构链式存储结构 顺序串上的插入和删除操作不方便，需要顺序串上的插入和删除操作不方便，需要(xyo)移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。 用单链表存放串，每个结点仅存储一个字符，如图用单链表存放串，每个结点仅存储一个字符，如图4-1所示，因此，每个结点的指针域所占空间比字符域所占空间要大得多。为了提高空间的利用率，我们可以使每个结点存放多个字符，称为块链结构，如图所示，因此，每个结点的指针域所占空间

18、比字符域所占空间要大得多。为了提高空间的利用率，我们可以使每个结点存放多个字符，称为块链结构，如图4-2所示每个结点存放所示每个结点存放4个字符。个字符。 第15页/共36页第十六页，共36页。图图4-1 结点大小为结点大小为1的链式存储的链式存储(cn ch)结构结构 A B C DE F G HI J K LM N # #sMB BAN .s图图4-2 结点大小结点大小(dxio)为为4的链式存储结的链式存储结构构第16页/共36页第十七页，共36页。 2 2基本运算在链式存储结构上的实现基本运算在链式存储结构上的实现 链式存储结构的链式存储结构的C C语言定义如下：语言定义如下：#def

19、ine CHUNKSIZE #define CHUNKSIZE ; / ; /定义结点的大小定义结点的大小 typedef struct Chunk / typedef struct Chunk /结点结构结点结构 char strCHUNKSIZE; char strCHUNKSIZE; struct Chunk struct Chunk * *next;next; Lstring; Lstring; 一个链串由头指针唯一确定一个链串由头指针唯一确定(qudng)(qudng)。 这种结构便于进行插入和删除运算，但存储空间利用率太低。这种结构便于进行插入和删除运算，但存储空间利用率太低。 为

20、了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于 1 1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。第17页/共36页第十八页，共36页。 对于结点大小不为对于结点大小不为1 1的链串，其类型定为义只需对上述的链串，其类型定为义只需对上述(shngsh)(shngsh)的结的结点类型做简单

21、的修改即可，如结点大小为点类型做简单的修改即可，如结点大小为4 4的定义为：的定义为： #define nodesize 80 #define nodesize 80 typedef struct node typedef struct node char data4; char data4; struct node struct node * *next;next; lstring; lstring; 采用链式存储结构（结点大小为采用链式存储结构（结点大小为1 1），实现串的联接、求子串以及串的），实现串的联接、求子串以及串的置换基本运算见教科书置换基本运算见教科书 P83 P83 。第18

22、页/共36页第十九页，共36页。 4.2.3 串的堆分配存储结构及其基本运算的实现串的堆分配存储结构及其基本运算的实现 1堆分配存储结构堆分配存储结构 堆存储结构的特点是，仍以一组空间足够大的、地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配的。所以也称为堆存储结构的特点是，仍以一组空间足够大的、地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配的。所以也称为(chn wi)动态存储分配的顺序表。每当产生一个新串时，系统就从剩余空间的起始处为串值分配一个长度和串值长度相等的存储空间。动态存储分配的顺序表。每当产生一个新串时，系统就从剩余

23、空间的起始处为串值分配一个长度和串值长度相等的存储空间。 在在C语言中，存在一个称为语言中，存在一个称为(chn wi)“堆堆”的自由空间，由动态分配函数的自由空间，由动态分配函数malloc()分配一块实际串长所需的存储空间，如果分配成功，则返回这段空间的起始地址，作为串的基址。由分配一块实际串长所需的存储空间，如果分配成功，则返回这段空间的起始地址，作为串的基址。由free()释放串不再需要的空间。释放串不再需要的空间。 第19页/共36页第二十页，共36页。 2基本运算在堆分配基本运算在堆分配(fnpi)存储结构上的实现存储结构上的实现 在在C和和C+语言中可利用语言中可利用malloc

24、和和free两个函数实现动态存储分配两个函数实现动态存储分配(fnpi)。函数。函数malloc为每个新产生的串分配为每个新产生的串分配(fnpi)一块实际所需大小的空间，若分配一块实际所需大小的空间，若分配(fnpi)成功，则返回一个指向该空间起始地址的指针，作为新串的基址。另外为了便于串的运算，在存储结构中包含串的长度。成功，则返回一个指向该空间起始地址的指针，作为新串的基址。另外为了便于串的运算，在存储结构中包含串的长度。C语言对堆分配语言对堆分配(fnpi)存储结构的定义如下：存储结构的定义如下：typedef struct char *str; int curlen; Hstring

25、; 第20页/共36页第二十一页，共36页。堆分配存储中求子串和串的联接运算：堆分配存储中求子串和串的联接运算： （1 1）SubStr (s, pos, len)SubStr (s, pos, len)Hstring SubStr(Hstring &sub,Hstring s,int pos,int len)Hstring SubStr(Hstring &sub,Hstring s,int pos,int len) / /用用subsub返回串返回串s s的第的第pospos个字符起长度为个字符起长度为lenlen的子串的子串 int i; int i; if (poss.c

26、urlen-1|len0|pos+len- if (poss.curlen-1|lens.curlen) ls.curlen) return error; / return error; /参数不正确参数不正确(zhngqu)(zhngqu)时返回错误提示时返回错误提示 if (sub.str) free(sub.str); / if (sub.str) free(sub.str); /释放旧空间释放旧空间 if (! len) / if (! len) /空子串空子串 sub.str=NULL; sub.str=NULL; sub.curlen=0; sub.curlen=0; else e

27、lse sub.str=(char sub.str=(char* *)malloc(len)malloc(len* *sizeof(char);sizeof(char); for(i=0;ilen;i+) / for(i=0;ilen;i+) /非空子串非空子串 sub.stri=s.strpos+i; sub.stri=s.strpos+i; sub.curlen =len; sub.curlen =len; return ok;第21页/共36页第二十二页，共36页。 （2）Concat (s,t) Hstring Concat(HString &s，HString s1，HStr

28、ing s2) / 联接串联接串s1和串和串s2形成形成(xngchng)新串新串s,并返回并返回 int i; if(s.str) free(s.str); /释放旧空间释放旧空间 if(!(s.str=(char*)malloc(s1.curlen+s2.curlen)*sizeof(char) exit(overflow); for(i=0;is1.curlen;i+) /非空子串非空子串 s.stri=s1.stri; for(i=0;is2.curlen;i+) /非空子串非空子串 s.strs1.curlen+i=s2.stri； s.curlen=s1.curlen+s2.cur

29、len; return ok; 第22页/共36页第二十三页，共36页。4.3 串的串的模式匹配模式匹配 模式匹配：子串定位运算称为模式匹配模式匹配：子串定位运算称为模式匹配(Pattern (Pattern Matching)Matching)或串匹配或串匹配(String Matching)(String Matching)。 模式匹配成功是指在目标串模式匹配成功是指在目标串s s中找到一个模式串中找到一个模式串t t； 模式匹配不成功则指目标串模式匹配不成功则指目标串s s中不存在模式串中不存在模式串t t。 此运算的应用非常广泛。例如，在文本编辑程序中，此运算的应用非常广泛。例如，在文

30、本编辑程序中，经常要查找某一特定单词在文本中出现的位置。显然，经常要查找某一特定单词在文本中出现的位置。显然，解此问题的有效算法能极大地提高文本编辑程序的响应解此问题的有效算法能极大地提高文本编辑程序的响应性能。性能。 本节主要讨论两种串的模式匹配算法，都采用顺序存储本节主要讨论两种串的模式匹配算法，都采用顺序存储结构结构(jigu)(jigu)。 在串匹配中，一般将主串称为目标串，子串称之为在串匹配中，一般将主串称为目标串，子串称之为模式串。设模式串。设S S为目标串，为目标串，T T为模式串，设：为模式串，设： S=“s0s1s2sn-1” T=“t0t1tm-1” S=“s0s1s2sn

31、-1” T=“t0t1tm-1” 第23页/共36页第二十四页，共36页。 4.3.1 Brute-Force算法 Brute-Force算法的基本思想是：从目标串s 的第一个字符起和模式串t的第一个字符进行比较，若相等，则继续逐个比较后续字符，否则从串s 的第二个字符起再重新和串t进行比较。依此类推，直至串t 中的每个字符依次和串s的一个连续的字符序列相等，则称模式匹配成功(chnggng)，此时串t的第一个字符在串s 中的位置就是t 在s中的位置，否则模式匹配不成功(chnggng)。 假设s=“cddcdc”，t=“cdc”，则模式匹配过程下图所示： 第1次匹配 s=cddcdc i=2

32、 失败 t=cdc j=2 第2次匹配 s=cddcdc i=1 失败 t=cdc j=0 第3次匹配 s=cddcdc i=2 失败 t=cdc j=0 第4次匹配 s=cddcdc i=5 成功 t=cdc j=2第24页/共36页第二十五页，共36页。Brute-Force算法的算法的C语言描述如下：语言描述如下：int Index(string s,string t)int i,j;i=0; /指向串指向串s的第的第1个字符个字符j=0; /指向串指向串t的第的第1个字符个字符while(is.curlen)&(j=t.curlen) return(i-t.curlen); /

33、匹配成功，返回模式串匹配成功，返回模式串t在串在串s中的起始位置中的起始位置 else return 0; /匹配失败返回匹配失败返回0 第25页/共36页第二十六页，共36页。 一般情况下，上述算法的实际执行效率一般情况下，上述算法的实际执行效率(xio l)(xio l)与字符与字符 t. str0 t. str0在在串串s s中是否频繁出现有密切关系，例如，中是否频繁出现有密切关系，例如，s s 是一般的英文文稿，是一般的英文文稿，t t =“hello”=“hello”，s s中有中有5% 5% 的字母是的字母是“h”“h”，则在上述算法执行过程中，对于，则在上述算法执行过程中，对于9

34、5% 95% 的情况可以只进行一次对应位的比较就将的情况可以只进行一次对应位的比较就将t t向右移动一位，时间复杂度下降向右移动一位，时间复杂度下降为为O (s.curlen)O (s.curlen)，这时算法接近最好情况。，这时算法接近最好情况。 然而，在有些情况下，该算法效率然而，在有些情况下，该算法效率(xio l)(xio l)却很低。如当却很低。如当 s=aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab s=aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab， t=“aaaaaab“ t=“aaaa

35、aab“ 每次都是在模式串的最后位置上字符不匹配每次都是在模式串的最后位置上字符不匹配 即即 t.curlen s.curlen t.curlen s.curlen时，该算法效率时，该算法效率(xio l)(xio l)却很低。由于通常却很低。由于通常有有t.curlen s.curlent.curlen s.curlen，因此最坏情况的时间复杂度为，因此最坏情况的时间复杂度为O(s.curlenO(s.curlen* *t.curlen)t.curlen)。 第26页/共36页第二十七页，共36页。 4.3.2 KMP 算法 由D.E.Knuth、J.H.Morris和V.R.Pratt共同

36、(gngtng)提出了一个改进算法，消除了Brute-Force算法中串s指针的回溯，完成串的模式匹配。时间复杂度为O(s.curlen+t.curlen)，这就是Knuth-Morris-Pratt算法，简称KMP 算法。 为了进一步讨论KMP算法，让我们首先讨论一个例子。假设s=“abacabab”，t=“abab”，第一次匹配过程如下图所示： 第1次匹配 s=abacabab i=3 失败 t=abab j=3第27页/共36页第二十八页，共36页。 此时不必从i=l，j=0重新开始第二次匹配。 因为(yn wi)t.str0t.str1，s.str1=t.str1，必有s.str1t.

37、str0，又因t.str0= t.str2，s.str2= t.str2，所以必有s.str2= t.str0。 因此，第二次匹配可直接从i=3，j=1开始。 进一步分析，t.str1= t.str3，s.str3 t.str3，必定s.str3 t.str1，所以第二次匹配也不必进行，可以直接进行第三次匹配，即i=3，j=0。 由此可见，当s.stri和t.strj比较不相等时，串s的指针i不必回溯。 第28页/共36页第二十九页，共36页。KMP算法算法(sun f)的基本思想：的基本思想： 设目标串为设目标串为s，模式串为，模式串为t i、j 分别为指示分别为指示s和和t的指针，的指针，

38、i、j的初值均为的初值均为0。 若有若有 si = tj，则，则i和和j分别增分别增1；否则，；否则，i不变，不变，j退回至退回至j=nextj的位置的位置 ( 也也可理解为串可理解为串s不动，模式串不动，模式串t向右移动到向右移动到si与与tnextj对齐对齐 )； 比较比较 si 和和 tj。若相等则指针各增。若相等则指针各增1；否则；否则 j 再退回到下一个再退回到下一个j=nextj 的的位置位置( 即模式串继续向右移动即模式串继续向右移动 )，再比较，再比较 si 和和 tj 。 依次类推，直到下列两种情况之一：依次类推，直到下列两种情况之一： 1)j 退回到某个退回到某个j=nex

39、tj时有时有 si = tj，则指针各增，则指针各增1，继续匹配；，继续匹配； 2)j 退回至退回至 j=-1，此时令指针各增，此时令指针各增l，即下一次比较，即下一次比较 si+1和和 t0 。 第29页/共36页第三十页，共36页。 KMP算法的描述如下：#define MaxLen /定义最大串存储空间int Index_KPM(string s,string t)int i,j,nextMaxLen;GetNext(t，next); /先求得模式串的next函数(hnsh)值i=0; /指向串s的第1个字符j=0; /指向串t的第1个字符while(is.curlen)&(j=

40、t.curlen) return (i-t.curlen); /匹配成功 else return(0); /匹配失败 第30页/共36页第三十一页，共36页。4.4 串的应用串的应用(yngyng) 文本编辑是串的一个很典型的应用。它被广泛用于各种源程序的输入和修改，也被应用于信函、报刊、公文、书籍(shj)的输入、修改和排版。文本编辑的实质就是修改字符数据的形式或格式。在各种文本编辑程序中，它们把用户输入的所有文本都作为一个字符串。尽管各种文本编辑程序的功能可能有强有弱，但是它们的基本的操作都是一致的，一般包括串的输入、查找、修改、删除、输出等。 为了编辑方便起见，用户可以通过换页符和换行符将文本划分为若干页或