《第4章 串n.ppt》由会员分享，可在线阅读，更多相关《第4章 串n.ppt（70页珍藏版）》请在三一文库上搜索。
1、第四章 串,4.1 串类型的定义,4.2 串的表示和实现,4.3 串的模式匹配算法(选学内容）,4.1 串类型的定义,串（字符串）：是由 0 个或多个字符组成的有限序列。 通常记为：s = a1 a2 a3 ai an ( n0 )。,字母、数字或其他字符,必须有！,不属于串！,作用：避免字符串与变量名或数的常量混淆。,基本概念,例：x = 123 x = 123,test =test,作用：避免字符串与变量名或数的常量混淆。,空串：不含任何字符的串，长度 = 0，用符号 表示。,空格串：仅由一个或多个空格组成的串。,子串：由串中任意个连续的字符组成的子序列。,主串：包含子串的串。,位置：字符
2、在序列中的序号。 子串在主串中的位置：子串的首字符在主串中的位置。,例：S=JINAN S1= S2=NA S=JINAN, 均为 S 的子串。,S4=JAN, 非 S 的子串 （非串 S 中的连续字符所组成）。,在 S 中的位置：3,在 S 中的位置：1,串相等的条件：当两个串的长度相等且各个对应位置 的字符都相等时才相等。,例：S=JINAN S1=JI NAN S S1,空串是任意串的子串，任意串是其自身的子串。,串的逻辑结构：和线性表极为相似。,串的基本操作：和线性表有很大差别。,区别：串的数据对象约定是字符集。,线性表的基本操作：大多以“单个元素”作为操作对象；,串的基本操作：通常以
3、“串的整体”作为操作对象。,例：在串中查找某个子串； 在串的某个位置上插入一个子串； 删除一个子串等。,4.1 串的抽象数据类型的定义如下：,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,
4、 S, pos, len),Index (S, T, pos),Replace (&S, T, V),StrInsert (&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) 初始条件
5、：串S存在。 操作结果：若 S 为空串，则返回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 和 S2 存在。 操作结果：用 T 返回由 S1 和 S2 联接而成的新串。,例如： Concate( T, man, k
6、ind) 求得 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( sub, commander, 1, 9) 求得 sub = commander； SubString( sub, commander, 9, 1) 求得 sub = r；,子串
7、为“串” 中的一个字符子序列,SubString(sub, commander, 4, 7) sub = ?,SubString(sub, beijing, 7, 2) = ? sub = ?,SubString(student, 5, 0) = ,起始位置和子串长度之间存在约束关系,长度为 0 的子串为“合法”串,Index(S,T,pos) 初始条件：串S和T存在，T是非空串， 1posStrLength(S)。 操作结果： 若主串 S 中存在和串 T 值相同 的子串, 则返回它在主串 S 中第pos个 字符之后第一次出现的位置； 否则函数值为0。,假设 S = abcaabcaaabc,
8、 T = bca,Index(S, T, 1) = 2；,Index(S, T, 3) = 6；,Index(S, T, 8) = 0；,“子串在主串中的位置”意指子串 中的第一个字符在主串中的位序。,Replace(&S,T,V) 初始条件：串S, T和 V 均已存在, 且 T 是非空串. 操作结果：用V替换主串S中出现 的所有与（模式串）T 相等的不重叠的子串。,例如：,假设 S = abcaabcaaabca，T = bca,若 V = x， 则经置换后得到 S = axaxaax,若 V = bc， 则经置换后得到 S = abcabcaabc,StrInsert (&S, pos,
9、T) 初始条件：串S和T存在， 1posStrLength(S)1。 操作结果：在串S的第pos个字符之前 插入串T。,例如：S = chater，T = rac， 则执行 StrInsert(S, 4, T)之后得到 S = character,StrDelete (&S, pos, len) 初始条件：串S存在 1posStrLength(S)-len+1。 操作结果：从串S中删除第pos个字符 起长度为len的子串。,ClearString(&S) 初始条件：串S存在。 操作结果：将S清为空串。,对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考
10、手册为准。,gets(str) 输入一个串； puts(str) 输出一个串； strcat(str1, str2) 串联接函数； strcpy(str1, str2, k) 串复制函数； strcmp(str1, str2) 串比较函数； strlen(str) 求串长函数；,例如：C语言函数库中提供下列串处理函数：,在上述抽象数据类型定义的13种操作中， 串赋值StrAssign、串复制Strcopy、 串比较StrCompare、求串长StrLength、 串联接Concat以及求子串SubString 等六种操作构成串类型的最小操作子集。 即：这些操作不可能利用其他串操作来实现， 反之
11、，其他串操作（除串清除ClearString和串 销毁DestroyString外）可在这个最小操作子 集上实现。,例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。,StrCompare(SubString(S, i, StrLength(T),T ) ? 0,S 串,T 串,T 串,i,pos,n-m+1,算法的基本思想为：,int Index (String S, String T, int pos) / T为非空串。若主串S中第pos个字符之后存在与 T相等的子串，则返回第一个 这样的子串在S中的位置，否则返回0 if (pos 0) n = StrLe
12、ngth(S); m = StrLength(T); i = pos; while ( i = n-m+1) SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ; else return i ; / while / if return 0; / S中不存在与T相等的子串 / Index,又如串的置换函数：,S 串,T 串,V 串,V 串,pos,pos,sub,i,news 串,sub,串的逻辑结构和线性表极为相似，区别 仅在于串的数据对象约束为字符集。,串的基本操作和线性表有很大差别。,在线性表的基本操作中，大多以“单个元素”作
13、为操作对象； 在串的基本操作中，通常以“串的整体”作为操作对象。,在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。,4.2 串的表示和实现,一、串的定长顺序存储表示,二、串的堆分配存储表示,三、串的块链存储表示,一、串的定长顺序存储表示,定长顺序存储表示，也称为静态存储分配的顺序串。即用一组地址连续的存储单元依次存放串中的字符序列。,#define MAXSTRLEN 255 / 用户可在255以内定义最大串长 typedef unsigned char Sstring MAXSTRLEN + 1; /
14、0号单元存放串的长度,一、串的定长顺序存储表示,按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列的复制”。,串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为 “截断” 。,特点:,例：串 “This is a dog.” 的长度的表示方法：,串长的表示方法,在串的存贮区首地址 显式地记录串的长度。,在串之后加结束标志。,如：PASCAL 语言。,如：C 使用 “0”。,显式,隐式,定长顺序存储表示时串的操作的实现,假设串 T 是由串 S1 联结串 S2 得到的，则只要进行相应的“串值复制”操作即可，需要时进行“截断”。,串 T 值,S10+S20
15、 MAXSTRLEN,S10 MAXSTRLEN,S10 = MAXSTRLEN,结果正确,结果 S2 被“截断”,结果 T=S1,例如：串的联接算法中需分三种情况处理：,Status Concat(SString / Concat,T1S10 = S11S10; TS10+1S10+S20 = S21S20; T0 = S10+S20; uncut = TRUE; ,if (S10+S20 = MAXSTRLEN) / 未截断,else if (S10 MAXSTRSIZE) / 截断,else / 截断(仅取S1),T1S10 = S11S10; TS10+1MAXSTRLEN = S21
16、MAXSTRLENS10; T0 = MAXSTRLEN; uncut = FALSE; ,T0MAXSTRLEN = S10MAXSTRLEN; / T0 = S10 = MAXSTRLEN uncut = FALSE; ,2、求子串 SubString(&Sub, S, pos, len),求子串的过程即为复制字符序列的过程，将串 S中的第 pos 个字符开始的长度为 len 的字符串复制到串 Sub 中。,注：1)、不会出现“截断”的情况。 2)、可能出现“参数非法”的情况，应返回 ERROR。,Status SubString(SString / SubString,求子串 SubSt
17、ring 算法描述,定长顺序存储表示时串操作的缺点,1、需事先预定义串的最大长度，这在程序运行前是很难估计的。,2、由于定义了串的最大长度，使得串的某些操作受限（截尾），如串的联接、插入、置换等运算。,克服办法：不限定最大长度 动态分配串值的存储空间。,二、串的堆分配存储表示,堆存储结构的特点：仍以一组空间足够大的、地址连续的存储单元依次存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配的。,typedef struct char *ch; / 若是非空串，则按串长分配存储区， / 否则ch为NULL int length; / 串长度 HString;,二、串的堆分配存储表示,通常
18、，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc( )和free( )进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。 C语言中的串以一个空字符为结束符， 串长是一个隐含值。,串插入操作 StrInsert(&S, pos, T) 的实现算法为： 1、为串 S 重新分配大小等于串 S 和串 T 长度之和的存储空间； 2、进行串值的复制。,这类串操作实现的算法为： 先为新生成的串分配一个存储空间，然后 进行串值的复制。,Status StrInsert (Hstring /StrInsert,例：S=ABCDE T=XY pos=4
19、,A B C D E,A B C D E,S.ch,E,D,typedef struct char *ch; int length; HString;,X Y,X Y,Status Concat(HString / Concat,Status SubString(HString / SubString, ,Sub.ch = (char *)malloc(len*sizeof(char); Sub.ch0len-1 = Spos-1pos+len-2; Sub.length = len;,三、串的块链存储表示,串值也可用单链表存储，简称为链串。 链串与单链表的差异只是它的结点数据域为单个字符。,
20、S,S,优点：便于插入和删除 缺点：空间利用率低,三、串的块链存储表示,也可用链表来存储串值，由于串的数据元素是一个字符，它只有 8 位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。,存储密度 =,数据元素所占存储位,实际分配的存储位,S,#define CHUNKSIZE 80 / 可由用户定义的块大小 typedef struct Chunk / 结点结构 char chCUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串的链表结构 Chunk *head, *tail; / 串的头和尾指针 int c
21、urlen; / 串的当前长度 LString;,例如: 在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即: 同一行的串用定长结构(80个字符), 行和行之间用指针相联接。,实际应用时，可以根据问题所需来设置结点的大小。,这是串的一种重要操作，很多 软件，若有“编辑”菜单项的话， 则其中必有“查找”子菜单项。,4.3 串的模式匹配算法,初始条件：串S和T存在，T是非空串， 1posStrLength(S)。 操作结果：若主串S中存在和串T值相 同的子串返回它在主串S中 第pos个字符之后第一次出 现的位置；否则函数 值为0。,首先，回忆一下串匹配(查找)的定义:
22、,INDEX (S, T, pos),下面讨论以定长顺序结构 表示串时的几种算法。,一、简单算法,二、首尾匹配算法,三、KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法,int Index(SString S, SString T, int pos) / 返回子串T在主串S中第pos个字符之后的位置。若不存在， / 则函数值为0。其中，T非空，1posStrLength(S)。 i = pos; j = 1; while (i T0) return i-T0; else return 0; / Index,一、简单算法,先比较模式串的第一个字符， 再比较模式串的
23、最后一个字符， 最后比较模式串中从第二个到 第n-1个字符。,二、首尾匹配算法,int Index_FL(SString S, SString T, int pos) sLength = S0; tLength = T0; i = pos; patStartChar = T1; patEndChar = TtLength; while (i = sLength tLength + 1) if (Si != patStartChar) +i; /重新查找匹配起始点 else if (Si+tLength-1 != patEndChar) +i; / 模式串的“尾字符”不匹配 else retur
24、n 0; ,/ 检查中间字符的匹配情况,k = 1; j = 2; while ( j tLength / 重新开始下一次的匹配检测,KMP算法的时间复杂度可以达到O(m+n),当 Si Tj 时， 已经得到的结果： Si-j+1i-1 = T1j-1 若已知 T1k-1 = Tj-k+1j-1 则有 Si-k+1i-1 = T1k-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;
25、j = 1; while (i T0) return i-T0; / 匹配成功 else return 0; / Index_KMP,这实际上也是一个匹配的过程， 不同在于：主串和模式串是同一个串,求next函数值的过程是一个递推过程，分析如下:,已知：next1 = 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. 了解串的堆存储结构以及在其上实现串操作的基本方法。,本章学习要点,