《第四讲串的表示和实现研究报告》由会员分享，可在线阅读，更多相关《第四讲串的表示和实现研究报告（57页珍藏版）》请在金锄头文库上搜索。
1、4.1 串的抽象数据类型的定义,4.2 串的表示和实现,4.3串的模式匹配算法,4.1 串的抽象数据类型的定义如下：,ADT String ,数据对象：,D ai |aiCharacterSet, i=1,2,.,n, n0 ,数据关系：,R1 | ai-1, ai D, i=2,.,n ,串是有限长的字符序列，由一对单引号相括，如: a string,基本操作：,StrAssign ( m = StrLength(T); i = pos; while ( i = n-m+1) SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ;
2、 else return i ; / while / if return 0; / S中不存在与T相等的子串 / Index,又如串的置换函数：,S 串,T 串,V 串,V 串,pos,pos,sub,i,news 串,sub,串的逻辑结构和线性表极为相似，区别 仅在于串的数据对象约束为字符集。,串的基本操作和线性表有很大差别。,在线性表的基本操作中，大多以“单个元素”作为操作对象； 在串的基本操作中，通常以“串的整体”作为操作对象。,在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。,4.2 串的表示和实
3、现,一、串的定长顺序存储表示,二、串的堆分配存储表示,三、串的块链存储表示,#define MAXSTRLEN 255 / 用户可在255以内定义最大串长 typedef unsigned char Sstring MAXSTRLEN + 1; / 0号单元存放串的长度,一、串的定长顺序存储表示,按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列的复制”。,串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为 “截断” 。,特点:,Status Concat(SString S1, SString S2, SString / Concat,例如：串的联
4、接算法中需分三种情况处理：,T1.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 = MAXSTR
5、LEN uncut = FALSE; ,typedef struct char *ch; / 若是非空串，则按串长分配存储区， / 否则ch为NULL int length; / 串长度 HString;,二、串的堆分配存储表示,通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc( )和free( )进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。 C语言中的串以0为结束符， 串长是一个隐含值。,串连接操作实现的算法为： 先为新生成的串分配一个存储空间，然后 进行串的复制。,Status Concat(HString / Con
6、cat,Status SubString(HString / SubString, ,Sub.ch = (char *)malloc(len*sizeof(char); Sub.ch0.len-1 = Spos-1.pos+len-2; Sub.length = len;,三、串的块链存储表示,用链表来存储串值，由于串的数据元素是一个字符，它只有 8 位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。,存储密度 =,数据元素所占存储位,实际分配的存储位,#define CHUNKSIZE 80 / 可由用户定义的块大小 typedef struct Chunk /
7、结点结构 char chCUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串的链表结构 Chunk *head, *tail; / 串的头和尾指针 int curlen; / 串的当前长度 LString;,例如: 在文本编辑程序中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即: 同一行的串用定长结构(80个字符), 行和行之间用指针相联接。,实际应用时，可以根据问题所需来设置结点的大小。,这是串的一种重要操作，很多 软件，若有“编辑”菜单项的话， 则其中必有“查找”子菜单项。,4.3串的模式匹配算法,初始条件：串
8、S和T存在，T是非空串， 1posStrLength(S)。 操作结果：若主串S中存在和串T值相 同的子串返回它在主串S中 第pos个字符之后第一次出 现的位置；否则函数 值为0。,首先，回忆一下串匹配(查找)的定义:,INDEX (S, T, pos),下面讨论以定长顺序结构 表示串时的几种算法。,一、简单算法,二、首尾匹配算法,三、KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法,第一趟匹配 a b a b c a b c a c b a b,i=1,t = a b c a c,Subch!=t,第二趟匹配 a b a b c a b c a c b a b
9、,i=2,第三趟匹配 a b a b c a b c a c b a b,i=3,第四趟匹配 a b a b c a b c a c b a b,i=4,第五趟匹配 a b a b c a b c a c b a b,i=5,第六趟匹配 a b a b c a b c a c b a b,i=6,t = a b c a c,匹配成功,Subch!=t,t = a b c a c,t = a b c a c,Subch!=t,Subch!=t,Subch!=t,t = a b c a c,t = a b c a c,int Index(SString S, SString T, int pos)
10、 / 返回子串T在主串S中第pos个字符之后的位置。若不存在， / 则函数值为0。其中，T非空，1posStrLength(S)。 i = pos; j = 1; while (i T0) return i-T0; else return 0; / Index,一、简单算法,先比较模式串的第一个字符， 再比较模式串的最后一个字符， 最后比较模式串中从第二个到 第n-1个字符。,二、首尾匹配算法,int Index_FL(SString S, SString T, int pos) sLength = S0; tLength = T0; i = pos; patStartChar = T1; p
11、atEndChar = TtLength; while (i = sLength tLength + 1) if (Si != patStartChar) +i; /重新查找匹配起始点 else if (Si+tLength-1 != patEndChar) +i; / 模式串的“尾字符”不匹配 else return 0; ,/ 检查中间字符的匹配情况,k = 1; j = 2; while ( j tLength / 重新开始下一次的匹配检测,KMP算法的时间复杂度可以达到O(m+n),当 Si Tj 时， 已经得到的结果： Si-j+1.i-1 = T1.j-1 若已知 T1.k-1 =
12、 Tj-k+1.j-1 则有 Si-k+1.i-1 = T1.k-1,三、KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法,定义：模式串的next函数,int Index_KMP(SString S, SString T, int pos) / 1posStrLength(S) i = pos; j = 1; while (i T0) return i-T0; / 匹配成功 else return 0; / Index_KMP,这实际上也是一个匹配的过程， 不同在于：主串和模式串是同一个串,求next函数值的过程是一个递推过程，分析如下:,已知：next1 =
13、0；,假设：nextj = k；又 Tj = Tk,则： nextj+1 = k+1,若： Tj Tk 则需往前回朔，检查 Tj = T ？,void get_next(SString / get_next,还有一种特殊情况需要考虑： 例如： S = aaabaaabaaabaaabaaab T = aaaab,nextvalj=00004,nextj=01234,void get_nextval(SString / get_nextval,1. 熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。,2. 熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。,3. 了解串的堆存储结构以及在其上实现串操作的基本方法。,本章学习要点,4. 理解串匹配的KMP算法，熟悉NEXT函数的定义，学会手工计算给定模式串的NEXT函数值和改进的NEXT函数值。,5. 了解串操作的应用方法和特点。,
