《CH4 串 数据结构PPT（课件）》由会员分享，可在线阅读，更多相关《CH4 串 数据结构PPT（课件）（61页珍藏版）》请在金锄头文库上搜索。
1、4.1 4.1 串的类型定义串的类型定义4.2 4.2 串的表示和实现串的表示和实现4.3 4.3 串的模式匹配算法串的模式匹配算法串串(String)是零个或多个字符组成的有限序列。一般记作 S= “a1a2a3an”，其中 S 是串名，双引号括起来的字符序列是串值；ai(1in) 可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度长度。长度为零的串称为 空串空串(Empty String)，它不包含任何字符。4.1 串类型的定义一、串的基本概念注意：注意：空串和空格串不同，如“ ”和“”分别表示长度为1的空格串和长度为0的空串（）。特别地，特别地，空串是任意串的子串，任意串是其
2、自身的子串。串中任意个连续字符组成的子序列称为该串的子串子串，包含子串的串相应地称为主串主串。通常将子串在主串中首次出现时，该子串的首字符在主串中对应的序号，定义为子串在主串中的位置子串在主串中的位置（或序号）。例如：例如：A = “This is a string This is a string ”，B = “is is ”则 B 是 A 的子串，A 为主串。B 在 A 中出现了两次，其中首次出现所对应的主串位置是 3 。因此，B 在 A 中的位置为 3 。二、串的抽象数据类型定义如下：ADT String 数据对象： D ai |aiCharacterSet,i=1,2,.,n, n0
3、数据关系：R1 | ai-1, ai D,i=2,.,n 基本操作：StrAssign ( / S中不存在与T相等的子串 / Indexn = StrLength(S); m = StrLength(T); i = pos; while ( i S0 | lens0-pos+1）return ERROR；Sub1len=Spospos+len-1；Sub0=len；return OK；/SubString例2. 求子串 SubString( / 若是非空串，则按串实际长度分配/存储区，否则 ch 为NULLint length; / 串长度 HString;二、串的堆分配存储表示以一组地址连续
4、的存储单元存放串值字符序列， 但它们的存储空间是在程序执行过程中动态分配而得 。通常，C语言中提供的串类型就是以这种存储方式 实现的。系统利用函数malloc( ) 和 free( ) 进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。C C语言中的串以一个空字符为结束符，串长是一语言中的串以一个空字符为结束符，串长是一个隐含值。个隐含值。这类串操作实现的算法为:先为新生成的串分配一个存储空间，然后进行串值的复制。Status Concat(HString / 释放旧空间if (!(T.ch =new charS1.length+S2.length)exi
5、t (OVERFLOW);T.length = S1.length + S2.length;T.ch0S1.length-1 = S1.ch0S1.length-1;T.chS1.lengthT.length-1 = S2.ch0S2.length-1;return OK; / ConcatStatus SubString(HString if (Sub.ch) free (Sub.ch); / 释放旧空间if (!len) Sub.ch = NULL; Sub.length = 0; / 空子串else / 完整子串return OK; / SubString if(!(Sub.ch = n
6、ew charlen)return ERROR;Sub.ch0len-1 = S.chpos-1pos+len-2;Sub.length = len;三、串的块链存储表示可用链表来存储串值，由于串的每个数据元素是一个字符，因此用链表存 储时，通常一个结点中存放的不是一个 字符，而是一个子串。存储密度 = 数据元素所占存储空间 实际分配的存储空间为了提高存储密度，可使每个结点存放多为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于义为结点的大小，显然，当结点大小大于 1 1时时，串的长度不一定正
7、好是结点的整数倍，因此，串的长度不一定正好是结点的整数倍，因此要用特殊字符要用特殊字符( (如如#) #) ，来填充最后一个结点，来填充最后一个结点，以表示串的结束。以表示串的结束。A B C D E F G H I # # # headAheadB C I H#define CHUNKSIZE 80 / 可由用户定义的块大小typedef struct Chunk / 结点结构char chCUNKSIZE;struct Chunk *next; Chunk;typedef struct / 串的链表结构Chunk *head, *tail; / 串的头和尾指针int curlen; / 串
8、的当前长度 LString;例如: 在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串， 构成一个结点。即: 同一行的串用定长结构 (80个字符), 行和行之间用指针相联接。实际应用时，可以根据问题所需来设置结点的大小。这是串的一种重要操作，很多软件，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。4.3串的模式匹配算法初始条件：串 S 和 T 存在，T 是非空串，1posStrLength(S)。 首先，回忆一下查找(串匹配)操作的定义:INDEX (S, T, pos)操作结果：若主串 S 中存在和串 T 值相同的子串,则返回它在主串 S 中第 pos 个字符之后第一次出现
9、的位置; 否则函数值为0。int Index (String S, String T, int pos) / T为非空串。若主串S中第pos个字符之后存在与 T相等的子串，则返回第一个这样的子串在S中的 位置，否则返回0if (pos 0) n = StrLength(S); m = StrLength(T); i = pos;while ( i m (j=m+1)ijijijinjT 串一、简单算法j=1i=i-j+2返回？匹配不成功！:(i-m)int Index(SString S, SString T, int pos) / 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函
10、数值为0。/ 其中，T非空，1posStrLength(S)。i = pos; j = 1;while (i T0) return i-T0;else return 0; / IndexKMP算法的时间复杂度可以达到O(m+n)二、KMP(D.E.Knuth, J.H.Morris,V.R.Pratt) 算法每当一趟匹配过程中出现字符比较不等时，不需回溯 i 指针，而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。当 Si p3 ，next3=1，继续 考察 p6 与 p1 ：p6 p1 ，next1=0，则next7=1，从头开始比较。void ge
11、t_next(SString next1 = 0; j = 0;while (i T0) if (j = 0 | Ti = Tj)+i; +j; nexti = j; else j = nextj; / get_next还有一种特殊情况需要考虑：例如：S = aaabaaabaaabaaabaaabT = aaaabnextj= 01234 nextvalj= 00004 (调整后的next值)若 pj = pnextj,则Nextj= NextNextjvoid get_nextval(SString nextval1 = 0; j = 0;while (i T0) if (j = 0 | Ti = Tj) +i; +j;if (Ti != Tj) nexti = j;else nextvali = nextvalj;else j = nextvalj; / get_nextval作作 业业1、已知主串t=abcaabbabcabaacbacabcaabbabcabaacbacb ba，模式串p=abcabaaabcabaa，要求：(1)计算模式p的next值；2、编写算法实现串的基本操作，strReplace（&s，t，v）
