《数据结构与算法分析第四章字符串.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法分析第四章字符串.ppt（73页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Chapter 4String串的定义串的定义n(n=0)n(n=0)个字符的有限序列个字符的有限序列S=a1,a2,anS=a1,a2,an 串名串名:s:s 串值串值:ai(1=i=n):ai(1=i=n)串长串长:n:n术术 语语空空 串串n=0n=0的串的串子子 串串中若干相邻字符组成的子序列串串中若干相邻字符组成的子序列主主 串包含子串的串串包含子串的串空格串仅含有空格字符的串空格串仅含有空格字符的串(n(n不为不为0)0)串相等设串相等设 s1=a11,an1s1=a11,an1 s2=a12,an2 s2=a12,an2 若若 n1=n2n1=n2且且ai1=ai2ai1=ai2
2、（1=i=n1)1=i=n1)则则 s1=s2s1=s2 串的抽象数据类型串的抽象数据类型ADT String 数据对象数据对象：D ai|aiCharacterSet,i=1,2,.,n,n0 数据关系数据关系：R1|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)StrIns
3、ert(&S,pos,T)StrDelete(&S,pos,len)ClearString(&S)ADT String StrAssign(&T,chars)初始条件：初始条件：chars 是字符串常量是字符串常量 操作结果：把操作结果：把 chars 赋为赋为 T 的值的值 StrCopy(&T,S)初始条件：串初始条件：串 S 存在存在 操作结果：由串操作结果：由串 S 复制得串复制得串 T DestroyString(&S)初始条件：串初始条件：串 S 存在存在 操作结果：串操作结果：串 S 被销毁被销毁 StrEmpty(S)始始条条件件：串串S存存在在操操作作结结果果：若若 S 为为
4、空空串串，则则返返回回 TRUE，否否 则则 返返 回回 FALSE 表示空串，空串的长度为零表示空串，空串的长度为零StrCompare(S,T)初初 始始 条条 件件：串串 S和和 T存存 在在操操作作结结果果：若若S T，则则返返回回值值 0 若若S T，则则返返回回值值 0 若若S T，则返回值，则返回值 0例如：例如：StrCompare(data,state)0 StrLength(S)初初 始始 条条 件件：串串 S 存存 在在 操操作作结结果果：返返回回 S 的的元元素素个个数数，称为串的长度称为串的长度 Concat(&T,S1,S2)初初 始始 条条 件件：串串 S1 和和
5、 S2 存存 在在 操操作作结结果果：用用 T 返返回回由由 S1 和和 S2 联接而成的新串联接而成的新串例如：例如：Concate(T,man,kind)求得求得 T=mankind SubString(&Sub,S,pos,len)初始条件：初始条件：串串 S 存在，存在，1posStrLength(S)且且0lenStrLength(S)-pos+1操作结果：操作结果：用用 Sub 返回串返回串 S 的第的第 pos 个字符个字符 起长度为起长度为 len 的子串的子串例如：例如：SubString(sub,commander,4,3)求得求得 sub=man SubString(su
6、b,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是是非非空空串串，1posSt
7、rLength(S)操操作作结结果果：若若主主串串 S 中中存存在在和和串串 T 值值 相相同同的的子子串串,则则返返回回它它在在主主 串串S中中第第pos个个 字字符符之之后后第第一一次次出出现现的的位位 置；否则函数值为置；否则函数值为0假设假设 S=abcaabcaaabc,T=bca Index(S,T,1)=2Index(S,T,3)=6Index(S,T,8)=0“子串在主串中的位置子串在主串中的位置”意指子串意指子串中的第一个字符在主串中的位序中的第一个字符在主串中的位序Replace(&S,T,V)初始条件：串初始条件：串S,T和和 V 均已存在，均已存在，且且 T 是非空串是
8、非空串操作结果：用操作结果：用V替换主串替换主串S中出现中出现 的所有与（模式串）的所有与（模式串）T 相等的不重叠的子串相等的不重叠的子串假设假设 S=abcaabcaaabca，T=bca 若若 V=x，则经置换后得到则经置换后得到 S=axaxaax 若若 V=bc，则经置换后得到则经置换后得到 S=abcabcaabc StrInsert(&S,pos,T)初始条件：串初始条件：串S和和T存在，存在，1posStrLength(S)1操作结果：在串操作结果：在串S的第的第pos个字符之前个字符之前 插入串插入串T例如：例如：S=chater，T=rac，则执行则执行 StrInsert
9、(S,4,T)之后得到之后得到 S=character StrDelete(&S,pos,len)初始条件：串初始条件：串S存在存在 1posStrLength(S)-len+1操作结果：从串操作结果：从串S中删除第中删除第pos个字符个字符 起长度为起长度为len的子串的子串 ClearString(&S)初初 始始 条条 件件：串串 S存存 在在 操操 作作 结结 果果：将将 S清清 为为 空空 串串在上述抽象数据类型定义的在上述抽象数据类型定义的1313种操作中种操作中 串赋值串赋值StrAssignStrAssign、等六种操作等六种操作 串复制串复制StrcopyStrcopy、构成
10、串类型构成串类型 串比较串比较StrCompareStrCompare、的最小操作的最小操作 求串长求串长StrLengthStrLength、子集子集 串联接串联接ConcatConcat 求子串求子串SubStringSubString即：即：这些操作不可能利用其他串操作来实现，这些操作不可能利用其他串操作来实现，反之，其他串操作反之，其他串操作(除串清除除串清除ClearString和串销毁和串销毁DestroyString外）可在这个最外）可在这个最小操作子集上实现小操作子集上实现StrCompare(SubString(S,i,StrLength(T),T)?0例如，可利用例如，可利
11、用串比较串比较、求串长和求子、求串长和求子串等操作实现定位函数串等操作实现定位函数Index(S,T,pos)。S串T串T串iposn-m+1算法的基本思想为：算法的基本思想为：int Index(String S,String T,int pos)/T为非空串。若主串为非空串。若主串S中第中第pos个字符个字符之后存在与之后存在与 T相等的子串，则返回第相等的子串，则返回第一个这样的子串在一个这样的子串在S中的位置，否则返中的位置，否则返回回0 if(pos 0)n=StrLength(S);m=StrLength(T);i=pos;while(i=n-m+1)SubString(sub,S
12、,i,m);if(StrCompare(sub,T)!=0)+i;else return i;/while /if return 0;/S中不存在与中不存在与T相等的子串相等的子串/Index又如串的置换函数：S串T串V串V串pospossubinews串sub串的逻辑结构和线性表极为相似，串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集区别仅在于串的数据对象约束为字符集串的基本操作和线性表有很大差别串的基本操作和线性表有很大差别在线性表的基本操作中，大多以在线性表的基本操作中，大多以“单个元素单个元素”作为操作对象作为操作对象 在串的基本操作中，通常以在串的基本操作中，通常以
13、“串的串的整体整体”作为操作对象作为操作对象在程序设计语言中，串只是作为在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变多数非数值处理的程序中，串也以变量的形式出现量的形式出现串的表示和实现串的表示和实现串的存储结构串的存储结构对串的存储方式取决于我们对串所进行的运算，如果在程序设计语言中，串的运算只是作为输入或输出的常量出现，则此时只需存储该串的字符序列，这就是串值的存储。此外，一个字符序列还可赋给一个串变量，操作运算时通过串变量名访问串值。实现串名到串
14、值的访问，在C+语言中可以有两种方式：一是可以将串定义为字符型数组，数组名就是串名，串的存储空间分配在编译时完成，程序运行时不能更改。这种方式为串的静态存储结构。另一种是定义字符指针变量，存储串值的首地址，通过字符指针变量名访问串值，串的存储空间分配是在程序运行时动态分配的，这种方式称为串的动态存储结构。串值的存储串值的存储我们称串是一种特殊的线性表，因此串的存储结构表示也有两种方法：静态存储采用顺序存储结构，动态存储采用的是链式存储和堆存储结构。1串的静态存储结构串的静态存储结构类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。由于一个字符只占1个字节，而现在大多数计算
15、机的存储器地址是采用的字编址，一个字（即一个存储单元）占多个字节，因此顺序存储结构方式有两种：（1）紧缩格式：即一个字节存储一个字符。这种存储方式可以在一个存储单元中存放多个字符，充分地利用了存储空间。但在串的操作运算时，若要分离某一部分字符时，则变得非常麻烦。datastructure0图4-1串值的紧缩格式存储图4-1所示是以4个字节为一个存储单元的存储结构，每个存储单元可以存放4个字符。对于给定的串s=datastructure，在C+语言中采用字符0作串值的结束符。串s的串值连同结束符的长度共15，只需4个存储单元。串值的紧缩格式存储由上述讨论可知，串的顺序存储结构有两大不足之处：一是
16、需事先预定义串的最大长度，这在程序运行前是很难估计的。二是由于定义了串的最大长度，使得串的某些操作受限，如串的联接运算等。（2）非紧缩格式：这种方式是以一个存储单元为单位，每个存储单元仅存放一个字符。这种存储方式的空间利用率较低，如一个存储单元有4个字节，则空间利用率仅为25%。但这种存储方式中不需要分离字符，因而程序处理字符的速度高。2串的动态存储结构串的动态存储结构我们知道，串的各种运算与串的存储结构有着很大的关系，在随机取子串时，顺序存储方式操作起来比较方便，而对串进行插入、删除等操作时，就会变得很复杂。因此，有必要采用串的动态存储方式。串的动态存储方式采用链式存储结构和堆存储结构两种形
17、式：（1）链式存储结构串的链式存储结构中每个结点包含字符域和结点链接指针域，字符域用于存放字符，指针域用于存放指向下一个结点的指针，因此，串可用单链表表示。用单链表存放串，每个结点仅存储一个字符，因此，每个结点的指针域所占空间比字符域所占空间要大得多。为了提高空间的利用率，我们可以使每个结点存放多个字符，称为块链结构每个结点存放4个字符。（2）堆存储结构堆存储结构的特点是，仍以一组空间足够大的、地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配的。每当产生一个新串时，系统就从剩余空间的起始处为串值分配一个长度和串值长度相等的存储空间。串名的存储映象串名的存储映象串名
18、的存储映象就是建立了串名和串值之间的对应关系的一个符号表。在这个表中的项目可以依据实际需要来设置，以能方便地存取串值为原则。如：s1=datas2=structure若符号表中每行包含有串名、串值的始地址、尾地址，也可以不设尾地址，而设置串和长度值。对于链式存储串值的方式，如果要建立串变量的符号表，则只需要存入一个链表的表头指针即可。串的定长顺序存储表示串的定长顺序存储表示串的堆分配存储表示串的堆分配存储表示串的块链存储表示串的块链存储表示#define MAXSTRLEN 255 /用户可在用户可在255以内定义最大串长以内定义最大串长 typedef unsigned char Sstri
19、ng MAXSTRLEN+1;/0号单元存放串的长度号单元存放串的长度串的定长顺序存储表示串的定长顺序存储表示按这种串的表示方法实现的串的按这种串的表示方法实现的串的运算时，其基本操作为运算时，其基本操作为“字符序列字符序列的复制的复制”串的实际长度可在这个予定义长串的实际长度可在这个予定义长度的范围内随意设定，超过予定义度的范围内随意设定，超过予定义长度的串值则被舍去，称之为长度的串值则被舍去，称之为“截断截断”特点特点:例例 如如串的联接算法中串的联接算法中需分三种情况处理需分三种情况处理Concat(SString S1,SString S2,SString&T)return uncut
20、;/ConcatT1.S10=S11.S10;TS10+1.S10+S20=S21.S20;T0=S10+S20;uncut=TRUE;if(S10+S20=MAXSTRLEN)/未截断未截断 else if(S10 MAXSTRSIZE)/截断截断 else /截断截断(仅取仅取S1)T1.S10=S11.S10;TS10+1.MAXSTRLEN=S21.MAXSTRLENS10;T0=MAXSTRLEN;uncut=FALSE;T0.MAXSTRLEN=S10.MAXSTRLEN;T0=S10=MAXSTRLEN;uncut=FALSE;clsss String char*ch;/若是非空
21、串，则按串长分若是非空串，则按串长分 /配存储区，否则配存储区，否则ch为为NULL int length;/串长度串长度 串的堆分配存储表示串的堆分配存储表示Concat(String&S,String S1,String S2)/用用S返回由返回由S1和和S2联接而成的新串联接而成的新串if(S.ch)delete S.ch;/释放旧空间释放旧空间 if(!(S.ch=newcharS1.length+S2.length)exit(OVERFLOW);S.length=S1.length+S2.length;S.ch 0.S1.length-1 =S1.ch 0.S1.length-1;S
22、.ch S1.length.S.length-1 =S2.ch 0.S2.length-1;return OK;/ConcatSubString(String&Sub,String S,int pos,int len)/用用Sub返回串返回串S的第的第pos个字符起长度个字符起长度 为为len的子串的子串if(pos S.length|len S.length-pos+1)return ERROR;if(Sub.ch)delete Sub.ch;/释放旧空间释放旧空间 if(!len)/空子串空子串 Sub.ch=NULL;Sub.length=0;else Sub.ch=new charle
23、n;Sub.ch0.len-1=Spos-1.pos+len-2;Sub.length=len;/完整子串完整子串 return OK;/SubString串的块链存储表示串的块链存储表示也可用链表来存储串值，由于串的数据也可用链表来存储串值，由于串的数据元素是一个字符，它只有元素是一个字符，它只有8 位二进制数，位二进制数，因此用链表存储时，通常一个结点中存因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串放的不是一个字符，而是一个子串存储密度存储密度=数据元素所占存储位数据元素所占存储位实际分配的存储位实际分配的存储位例如例如:在编辑系统中，整个文本编在编辑系统中，整个文本编
24、辑区可以看成是一个串，每一行是一辑区可以看成是一个串，每一行是一个子串，构成一个结点。即个子串，构成一个结点。即:同一行的同一行的串用定长结构串用定长结构(80个字符个字符),行和行之间行和行之间用指针相联接用指针相联接实际应用时，可以根据问题所需来实际应用时，可以根据问题所需来设置结点的大小设置结点的大小这是串的一种重要操作，很多这是串的一种重要操作，很多 软件，若有软件，若有“编辑编辑”菜单项的话，菜单项的话，则其中必有则其中必有“查找查找”子菜单项子菜单项 串的模式匹配算法串的模式匹配算法简单算法简单算法首尾匹配算法首尾匹配算法KMP(D.E.Knuth,V.R.Pratt,KMP(D.
25、E.Knuth,V.R.Pratt,J.H.Morris)J.H.Morris)算法算法int Index(SString S,SString T,int pos)/返回子串返回子串T在主串在主串S中第中第pos个字符个字符 /之后的位置。若不存在，则函数值之后的位置。若不存在，则函数值 /为为0。其中，。其中，T非空，非空，/1posStrLength(S)i=pos;j=1;简单算法简单算法while(i=S0&j T0)return i-T0;else return 0;/Index串的模式匹配F定义定义 在串中寻找子串（第一在串中寻找子串（第一个字符）在串中的位置个字符）在串中的位置F
26、词汇词汇 在模式匹配中，子串称在模式匹配中，子串称为模式，串称为目标。为模式，串称为目标。F示例示例 目标目标 T:“Beijing”T:“Beijing”模式模式 P:“jin”P:“jin”匹配结果匹配结果=3 第第1趟趟 T a b b a b a 穷举的模穷举的模式式 P a b a 匹配过程匹配过程 第第2趟趟 T a b b a b a P a b a 第第3 3趟趟 T a b b a b a P a b a第第4趟趟 T a b b a b a P a b a int String:Find(String&pat)const /穷举的模式匹配穷举的模式匹配 char*p=pat
27、.ch,*s=ch;int i=0;if(*p&*s)/当两串未检测完当两串未检测完while(i 0，则目标指针不变，模式指针回，则目标指针不变，模式指针回到到 pf(j-1)+1。若设若设模式模式P=p0 p1pm-2 pm-1示例示例：确定失效函数：确定失效函数 f(j)运用运用KMP算法的匹配过程算法的匹配过程第第1 1趟趟 目标目标 a c a b a a b a a b c a c a a b c 模式模式 a b a a b c a c j=1 j=f(j-1)+1=0第第2趟趟 目标目标 a c a b a a b a a b c a c a a b c 模式模式 a b a
28、a b c a c j=5 j=f(j-1)+1=2第第3 3趟趟 目标目标 a c a b a a b a a b c a c a a b c 模式模式 (a b)a a b c a c intString:fastFind(String pat)const /带失效函数的KMP匹配算法intposP=0,posT=0;intlengthP=pat.curLen,lengthT=curLen;while(posP lengthP&posT lengthT)if(pat.chposP=chposT)posP+;posT+;/相等继续比较相等继续比较 else if(posP=0)posT+;/
29、不相等不相等else posP=pat.f posP-1+1;if(posP lengthP)return-1;elsereturnposT-lengthP;计算失效函数计算失效函数 f j 的方法的方法首先确定首先确定f 0=-1，再利用，再利用f j求求f j+1。其中其中,f(1)j =f j,f(m)j =f f(m-1)j f 0=-1;j=1时时,f 0+1=0,p0 p1,f 1=-1;j=2时时,f 1+1=0,p0=p2,f 2=f 1+1=0;j=3时时,f 2+1=1,p1 p3,f 1+1=0,p0=p3,f 3=f 1+1=0;j=4时时,f 3+1=1,p1=p4,
30、f 4=f 3+1=1;voidString:fail()/计算失效函数intlengthP=curLen;f 0=-1;/直接赋值直接赋值for(int j=1;j=0)i=f i;/递推递推if(*(ch+j)=*(ch+i+1)f j=i+1;elsef j=-1;文本编辑文本编辑文本编辑是串的一个很典型的应用。它被广泛用于各种源程序的输入和修改，也被应用于信函、报刊、公文、书籍的输入、修改和排版。文本编辑的实质就是修改字符数据的形式或格式。在各种文本编辑程序中，它们把用户输入的所有文本都作为一个字符串。尽管各种文本编辑程序的功能可能有强有弱，但是它们的基本的操作都是一致的，一般包括串的
31、输入、查找、修改、删除、输出等。例如有下列一段源程序：main()inta,b,c;scanf(%d,%d,&a,&b);c=a+b;printf(“%d”,c);我们把这个源程序看成是一个文本，为了编辑的方便，总是利用换行符把文本划分为若干行，还可以利用换页符将文本组成若干页，这样整个文本就是一个字符串，简称为文本串，其中的页为文本串的子串，行又是页的子串。将它们按顺序方式存入计算机内存中，图中表回车符。在输入程序的同时，文本编辑程序先为文本串建立相应的页表和行表，即建立各子串的存储映象。串值存放在文本工作区，而将页号和该页中的起始行号存放在页表中，行号、串值的存储起始地址和串的长度记录在行
32、表，由于使用了行表和页表，因此新的一页或一行可存放在文本工作区的任何一个自由区中，页表中的页号和行表中的行号是按递增的顺序排列的，如表4-3所示。设程序的行号从110开始。下面我们就来讨论文本的编辑。（1）插入一行时，首先在文本末尾的空闲工作区写入该行的串值，然后，在行表中建立该行的信息，插入后，必须保证行表中行号从小到大的顺序。若插入行145，则行表中从150开始的各行信息必须向下平移一行。（2）删除一行时，则只要在行表中删除该行的行号，后面的行号向前平移。若删除的行是页的起始行，则还要修改相应页的起始行号（改为下一行）。（3）修改文本时，在文本编辑程序中设立了页指针，行指针和字符指针，分别
33、指示当前操作的页、行和字符。若在当前行内插入或删除若干字符，则要修改行表中当前行的长度。如果该行的长度超出了分配给它的存储空间，则应为该行重新分配存储空间，同时还要修改该行的起始位置。对页表的维护与行表类似，在此不再叙述，有兴趣的同学可设计其中的算法。本章小结本章小结本章主要介绍了如下一些基本概念：串：串：串（或字符串）（String）是由零个或多个字符组成的有限序列。主主串串和和子子串串：一个串的任意个连续的字符组成的子序列称为该串的子串，包含该子串的串称为主串。串串的的静静态态存存储储结结构构：类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列的存储方式称为串的顺序存储
34、结构。堆堆存存储储结结构构：用一组空间足够大的、地址连续的存储单元存放串值字符序列，但其存储空间在程序执行过程中能动态分配的存储方式称为堆存储结构。串串的的链链式式存存储储结结构构：类似于线性表的链式存储结构，采用链表方式存储串值字符序列的存储方式称为串的顺序存储结构。串串名名的的存存储储映映象象：串名的存储映象就是建立串名和串值之间的对应关系的一个符号表。除上述基本概念以外，学生还应该了解串的基本运算（字符串拷贝（赋值、字符串的联接、求字符串的长度、子串的查询、字符串的比较）、串的静态存储结构的表示、串的链式存储结构的表示、串的堆存储结构的表示，能在各种存储结构方式中求字符串的长度、能在各种存储结构方式中利用C语言提供的串函数进行操作。73Thankyouverymuch!