第4章 串 4.1 串的基本概念 4.2 串的存储结构 4.3 串的模式匹配.

Presentation on theme: "第4章 串 4.1 串的基本概念 4.2 串的存储结构 4.3 串的模式匹配."— Presentation transcript:

1 第4章 串 4.1 串的基本概念 4.2 串的存储结构 4.3 串的模式匹配

2 4.1 串的基本概念 字符串: 空串: 串的长度: 串的表示： 空格串： 简称为串，是由零个或多个字符组成的有穷序列
含零个字符的串，用Ф表示 串的长度: 串中所含字符的个数 串的表示： “a1a2…an” 其中，最外边的双引号本身不是串的内容,它们是串的标志，以便将串与标识符(如变量名等)加以区别 ai(1≤i≤n)代表一个字符 空格串： 只包含空格的串，空格用□表示

3 两个串相等： 子串： 当且仅当两个串的长度相等并且各个对应位置上的字符都相同 一个串中任意个连续字符组成的子序列 含空串，但不含串本身
例如，“a”、“ab”、“abc”和“abcd”等都是“abcde”的子串（有的教材将本身作为子串）

4 讨论: “abcde”有多少个子串? 解: 空串数:1 含1个字符的子串数:5 含2个字符的子串数:4 含3个字符的子串数:3
解: 空串数:1 含1个字符的子串数:5 含2个字符的子串数:4 含3个字符的子串数:3 含4个字符的子串数:2 共有 =15个子串。

5 串的基本运算 (1) StrAssign(&s,cstr):将一个字符串常量赋给串s，即生成一个其值等于cstr的串s。
(2) StrCopy(&s,t):串复制，将串t赋给串s。 (3) StrEqual(s,t):判串相等，若两个串s与t相等则返回真；否则返回假。 (4) StrLength(s):求串长，返回串s中字符个数。

6 (5)Concat(s,t):串连接，返回由两个串s和t连接在一起形成的新串。
(6)SubStr(s,i,j):求子串，返回串s中从第i(1≤i≤n)个字符开始的、由连续j个字符组成的子串。 (7)InsStr(s1,i,s2):将串s2插入到串s1的第i(1≤i≤n+1)个字符中，即将s2的第一个字符作为s1的第i个字符，并返回产生的新串。

7 (8)DelStr(s,i,j):从串s中删去从第i(1≤i≤n)个字符开始的长度为j的子串，并返回产生的新串。
(9)RepStr(s,i,j,t):替换，在串s中，将第i(1≤i≤n)个字符开始的j个字符构成的子串用串t替换，并返回产生的新串。 (10) DispStr(s):串输出，输出串s的所有元素值。

8 子串定位：Index(S,T) 初始条件：串 S 和 T 存在，且 T 是非空串
子串在主串中的位置：子串中的第一个字符在主串中的“位序”。 【例】a= ’Welcome to Beijing’ b= ’Welcome’ c= ’Bei’ d= ’Bei’ 长度分别为18、7、3、3； b、c、d都是a的子串；b在a中的位置是1， c在a中的位置是12；c和d两串相等

9 子串定位：Index(S,T) 【算法思想】 【算法设计】 int Index (String S, String T) {
在主串S中取从第i个字符起，长度和串T相等的子串与串T比较，若相等，则求得函数值为i，否则i值增1，直至串S中不存在和串T相等的子串为止。 【算法设计】 int Index (String S, String T) { return 0; // S中不存在与T相等的子串 } // 算法结束 n = StringLength(S); m = StringLength(T); i = 1; while ( i <= n-m+1) { } // while StrCopy( sub,SubStr(S,i,m) ); if ( StrEqual(sub,T) != 0 ) ++i ; else return i ;

10 总 结 串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。 串的基本操作和线性表有很大差别：
在线性表的基本操作中，大多以“单个元素”作为操作对象； 而在串的基本操作中，通常以“串的整体”作为操作对象。

11 4.2 串的存储结构 串的顺序存储结构 用一组地址连续的存储单元依次存放串中的字符序列，称为顺序串。 串的链式存储结构 链串

12 4.2.1 串的顺序存储结构----顺序串 顺序存储采用一般顺序表的存储结构，其类型定义如下: typedef struct
{ char data[MaxSize]; int length; } SqString; data域存储字符串；length域存储字符串的当前长度； MaxSize常量表示允许存储字符串的最大长度； C语言中每个字符串以‘\0’标志结束。 SqString s;

13 串的顺序存储结构 定长顺序存储表示：事先定义字符串的最大长度
#define MAX_STRING ∥用户可能达到的最大串长 typedef unsigned char String[MAX_STRING+1]; ∥0号单元存放串的长度，字符从1号单元开始存放 “堆”分配存储表示：在程序执行过程中，利用标准函数malloc和free动态地分配或释放存储字符串的存储单元，并以一个特殊的字符（例如’\0’）作为字符串的结束标志 称串值共享的存储空间为“堆” typedef struct { char *str; //若是非空串，则按串长分配存储区，否则str为NULL int length; //串长度，不包括’\0’ }HString;

14 (1) StrAssign(s,cstr) 将一个字符串常量赋给串s，即生成一个其值等于cstr的串s。 void StrAssign(SqString &s,char cstr[]) { int i; for (i=0;cstr[i]!='\0';i++) s.data[i]=cstr[i]; s.length=i; }

15 (2) StrCopy(s,t) 将串t复制给串s。
void StrCopy(SqString &s,SqString t) //s为引用型参数 { int i; for (i=0;i<t.length;i++) s.data[i]=t.data[i]; s.length=t.length; }

16 (3) StrEqual(s,t) 判断两个串是否相等：若两个串s与t相等返回真(1)；否则返回假(0)。 {
bool StrEqual(SqString s,SqString t) { bool same=true; int i; if (s.length!=t.length) same=false; //长度不相等时返回0 else for (i=0;i<s.length;i++) if (s.data[i]!=t.data[i]) { same=false; break; } return same; }

17 (4) StrLength(s) int StrLength(SqString s) { return s.length; }

18 (5) Concat(s,t) 串连接：返回由两个串s和t连接在一起形成的新串。 SqString Concat(SqString s,SqString t) { SqString str; int i; str.length=s.length+t.length; for(i=0;i<s.length;i++) str.data[i]=s.data[i]; for(i=0;i<t.length;i++) str.data[s.length+i]=t.data[i]; return str; }

19

20 求子串：返回串s中从第i(1≤i≤n)个字符开始的、由连续j个字符组成的子串。参数不正确时返回一个空串。
(6) SubStr(s,i,j) 求子串：返回串s中从第i(1≤i≤n)个字符开始的、由连续j个字符组成的子串。参数不正确时返回一个空串。 SqString SubStr(SqString s,int i,int j) { SqString str; int k; str.length=0; if (i<=0 || i>s.length || j<0 || i+j-1>s.length) { printf("参数不正确\n"); return str; /*参数不正确时返回空串*/ } for (k=i-1;k<i+j-1;k++) str.data[k-i+1]=s.data[k]; str.length=j; return str; 考虑其他写法？

21 将串s2插入到串s1的第i (1≤i≤n+1)个字符中，即将s2的第一个字符作为s1的第i个字符，并返回产生的新串。
(7) InsStr(s1,i,s2) 将串s2插入到串s1的第i (1≤i≤n+1)个字符中，即将s2的第一个字符作为s1的第i个字符，并返回产生的新串。 SqString InsStr(SqString s1,int i,SqString s2) { int j; SqString str; str.length=0; if (i<=0 || i>s1.length+1) /*参数不正确时返回空串*/ { printf("参数不正确\n"); return str; } for (j=0;j<i-1;j++) /*s1.data[0..i-2]=>str*/ str.data[j]=s1.data[j]; for (j=0;j<s2.length;j++) /*s2.data[0..s2.length-1]=>str*/ str.data[i+j-1]=s2.data[j]; for (j=i-1;j<s1.length;j++) str.data[s2.length+j]=s1.data[j]; str.length=s1.length+s2.length;

22 (8) DelStr(s,i,j) 从串s中删去第i(1≤i≤StrLength(s))个字符开始的长度为j的子串，并返回产生的新串。
SqString DelStr(SqString s,int i,int j) { int k; SqString str; str.length=0; if (i<=0 || i>s.length || i+j>s.length+1) //参数不正确时返回空串 { printf("参数不正确\n"); return str; } for (k=0;k<i-1;k++) /*s.data[0..i-2]=>str*/ str.data[k]=s.data[k]; for (k=i+j-1;k<s.length;k++) str.data[k-j]=s.data[k]; str.length=s.length-j;

23 (9) RepStr(s,i,j,t) （略） 在串s中，将第i(1≤i≤StrLength(s))个字符开始的j个字符构成的子串用串t替换，并返回产生的新串。 SqString RepStr(SqString s,int i,int j,SqString t) { int k; SqString str; str.len=0; if (i<=0 || i>s.length || i+j-1>s.length) /*参数不正确*/ { printf("参数不正确\n"); return str; } for (k=0;k<i-1;k++) /*s.data[0.i-2]=>str*/ str.data[k]=s.data[k]; for (k=0;k<t.length;k++) /*t.data[0..t.length-1]=>str*/ str.data[i+k-1]=t.data[k]; for (k=i+j-1;k<s.length;k++) /*s.data[i+j-1..s.length-1]=>str*/ str.data[t.length+k-j]=s.data[k]; str.length=s.length-j+t.length;

24 (10) DispStr(s) 输出串s的所有元素值。 void DispStr(SqString s) { int i;
if (s.length>0) { for (i=0;i<s.length;i++) printf("%c",s.data[i]); printf("\n"); }

25 例4.1 设计顺序串上实现串比较运算Strcmp(s,t)的算法。
解：【算法思想】 （1）比较s和t两个串共同长度范围内的对应字符: ① 若s的字符＞t的字符，返回1； ② 若s的字符＜t的字符，返回-1； ③ 若s的字符=t的字符，按上述规则继续比较。 （2）当（1）中对应字符均相同时，比较s和t的长度: ① 两者相等时，返回0； ② s的长度＞t的长度，返回1； ③ s的长度＜t的长度，返回-1。

26 int Strcmp(SqString s,SqString t)
{ int i,comlen; if (s.length<t.length) comlen=s.length; //求s和t的共同长度 else comlen=t.length; for (i=0;i<comlen;i++) //在共同长度内逐个字符比较 if (s.data[i]>t.data[i]) return 1; else if (s.data[i]<t.data[i]) return -1; if (s.length==t.length) //s==t return 0; else if (s.length>t.length) //s>t else return -1; //s<t }

27 4.2.2 串的链式存储结构----链串 用单链表形式存储串，称为链式串或链串。
以下两图分别表示了同一个串“ABCDEFGHIJKLMN”的结点大小为4（存储密度大）和1（存储密度小）的链式存储结构。 结点大小为4的链串 结点大小为1的链串

28 链串的结点类型定义如下： 结点大小越大，则存储密度越大；
但存储密度越大，一些操作（如插入、删除、替换等）有所不便，且可能引起大量字符移动，因此它适合于在串基本保持静态使用方式时采用； 结点大小越小，运算处理越方便，但存储密度下降。 A B M N ∧ … s 链串的结点类型定义如下： typedef struct snode { char data; struct snode *next; } LiString;

29 块链运算：插入 He is a student. He is a bright student. H e i s a s t u d e n
# # ٨ He is a bright student.

30 块链运算：插入 H e i s a b r i g d e n t . # ٨ h t s t u

31 将一个字符串常量cstr赋给串s，即生成一个其值等于cstr的串s。以下采用尾插法建立链串。
(1) StrAssign(s,cstr) 将一个字符串常量cstr赋给串s，即生成一个其值等于cstr的串s。以下采用尾插法建立链串。 void StrAssign(LiString *&s,char cstr[]) { int i; LiString *r,*p; /*r始终指向尾结点*/ s=(LiString *)malloc(sizeof(LiString)); r=s; for (i=0; cstr[i]!='\0';i++) { p=(LiString *)malloc(sizeof(LiString)); p->data=cstr[i]; r->next=p; r=p; } r->next=NULL;

32 (2) StrCopy(s,t) 将串t复制给串s。以下采用尾插法建立复制后的链串s。
void StrCopy(LiString *&s,LiString *t) { LiString *p=t->next,*q,*r; s=(LiString *)malloc(sizeof(LiString)); r=s; /*r始终指向尾结点*/ while (p!=NULL) /*将t的所有结点复制到s*/ { q=(LiString *)malloc(sizeof(LiString)); q->data=p->data; r->next=q; r=q; p=p->next; } r->next=NULL;

33 (3) StrEqual(s,t) 判断两个串是否相等:若两个串s与t相等则返回真(1)；否则返回假(0)。
bool StrEqual(LiString *s,LiString *t) { LiString *p=s->next,*q=t->next; while (p!=NULL && q!=NULL && p->data==q->data) { p=p->next; q=q->next; } if (p==NULL && q==NULL) return true; else return false; }

34 int StrLength(LiString *s)
(4) StrLength(s) 求串长:返回串s中字符个数。 int StrLength(LiString *s) { int i=0; LiString *p=s->next; while (p!=NULL) { i++; p=p->next; } return i;

35 返回由两个串s和t连接在一起形成的新串。 LiString *Concat(LiString *s,LiString *t)
(5) Concat(s,t) 返回由两个串s和t连接在一起形成的新串。 LiString *Concat(LiString *s,LiString *t) { LiString *str,*p=s->next,*q,*r; str=(LiString *)malloc(sizeof(LiString)); r=str; while (p!=NULL) /*将s的所有结点复制到str*/ { q=(LiString *)malloc(sizeof(LiString)); q->data=p->data; r->next=q;r=q; p=p->next; }

36 p=t->next; while (p!=NULL) /*将t的所有结点复制到str*/
{ q=(LiString *)malloc(sizeof(LiString)); q->data=p->data; r->next=q;r=q; p=p->next; } r->next=NULL; return str;

37 返回串s中从第i(1≤i≤StrLength(s))个字符开始的、由连续j个字符组成的子串。
(6) SubStr(s,i,j) 返回串s中从第i(1≤i≤StrLength(s))个字符开始的、由连续j个字符组成的子串。 LiString *SubStr(LiString *s,int i,int j) { int k; LiString *str,*p=s->next,*q,*r; str=(LiString *)malloc(sizeof(LiString)); r=str; if (i<=0 || i>StrLength(s) || j<0 || i+j-1>StrLength(s)) { printf("参数不正确\n"); return str; /*参数不正确时返回空串*/ }

38 for (k=0;k<i-1;k++) /*找第i个结点，由p指向它*/
p=p->next; for (k=1;k<=j;k++) /*s[i]开始的j个结点=>str*/ { q=(LiString *)malloc(sizeof(LiString)); q->data=p->data; r->next=q; r=q; } r->next=NULL; return str;

39 (10) DispStr(s) 输出串s的所有元素值。 void DispStr(LiString *s)
{ LiString *p=s->next; while (p!=NULL) { printf("%c",p->data); p=p->next; } printf("\n");

40 例4.3 在链串中，设计一个算法把最先出现的子串"ab"改为"xyz"。
【算法思想】 在串s中找到最先出现的子串“ab”，p指向data域值为‘a’的结点，其后为data域值为‘b’的结点。将它们的data域值分别改为‘x’和‘z’，再创建一个data域值为‘y’的结点，将其插入到*p之后。

41 void Repl(LiString *&s)
{ LiString *p=s->next,*q; int find=0; while (p->next!=NULL && find==0) //查找'ab'子串 { if (p->data=='a' && p->next->data=='b')//找到子串 { p->data='x'; p->next->data='z'; //替换为xyz q=(LiString *)malloc(sizeof(LiString)); q->data='y';q->next=p->next;p->next=q; find=1; } else p=p->next;

42

43 4.3 串的模式匹配 设有主串s和子串t，子串t的定位就是要在主串s中找到一个与子串t相等的子串。
模式匹配成功是指在目标串s中找到一个模式串t；不成功则指目标串s中不存在模式串t。

44 4.3.1 Brute-Force算法 Brute-Force简称为BF算法，亦称简单匹配算法 其基本思路是:
从目标串s=“s0s1…sn-1”的第一个字符开始和模式串t=“t0t1…tm-1”中的第一个字符比较，若相等，则继续逐个比较后续字符；否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。 依次类推，若从模式串s的第i个字符开始，每个字符依次和目标串t中的对应字符相等，则匹配成功，该算法返回i；否则，匹配失败，函数返回-1。

45 目标串s=“cddcdc”，模式串t=“cdc”
用指针i指示目标串s的当前比较字符位置，用指针j指示模式串t的当前比较字符位置。

46 int index(SqString s,SqString t)
{ int i=0,j=0; while (i<s.length && j<t.length) { if (s.data[i]==t.data[j]) /*继续匹配下一个字符*/ { i++; j++; } /*主串和子串依次匹配下一个字符*/ else /*主串、子串指针回溯重新开始下一次匹配*/ { i=i-j+1; /*主串从下一个位置开始匹配*/ j=0; /*子串从头开始匹配*/ } if (j>=t.length) k=i-t.length; //返回匹配的第一个字符的下标 else k=-1; /*模式匹配不成功*/ return k;

47 结 论 算法简单，易于理解，但效率不高。 该算法存在着指针的“回溯”，回溯次数越多，效率越低。 如：S=000000000000001
T=00001 算法的时间复杂度为O(n*m) 算法简单，易于理解，但效率不高。 该算法存在着指针的“回溯”，回溯次数越多，效率越低。

48 首尾模式匹配 基本思想：先比较模式串的第一个字符，再比较模式串的最后一个字符，最后比较模式串中从第二个到第n－1个字符。
例如目标串S=’ababcabcaaabcbaabc’，模式串T为’abcba’ 目标串: a b a b c a b c a a a b c b a a b c 模式串: a a ( 2 次) a a a ( 1+2 次) a a a b c b a ( 2+5 次) a a a a ( 2+2 次) a a ( 2次) a b c b a (5 次) 首尾模式匹配算法减少了一定量的比较，但是并未真正的消除回溯

49 首尾模式匹配算法 int Index_FL(SqString s, SqString t) { ∥返回子串t在主串s中的位置。若不存在，则
sLength=s.length; tLength=t.length; i=0; patStartChar=t.data[0]; ∥模式串的第一个字符 patEndChar=t.data[tLength-1]; ∥最后一个字符

50 while(i<=sLength – tLength+1) ∥i从0开始
{ if(s.data[i]!=patStartChar) ++i; ∥重新查找匹配起始点 else if(s.data[i+tLength-1]!=patEndChar) ++i; ∥模式串的“尾字符”不匹配，重新查找匹配起始点 else { ∥检查中间字符的匹配情况 k=1; j=1; while(j<tLength && s.data[i+k]==t.data[j]) { ++k; ++j; } ∥while if (j==tLength-1) return i; else ++i; ∥重新开始下一次的匹配检测 }∥if }∥while return 0; }∥Index_FL

51 4.3.2 KMP算法 该算法较BF算法有较大改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。
三个人的名字： D. K. Knuth J. H. Morris V. R. Pratt KMP算法 该算法较BF算法有较大改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。 真子串(P113)：模式串t存在某个k(0＜k＜j)，使得“t0t1…tk ” = “ tj-ktj-k+1…tj ”成立。 真子串是模式串中隐藏的信息，利用它来提高模式匹配的效率。 【举例】 t= “abab”, 其中t0t1＝t2t3 【所以】 “ab”是真子串。

52 设主串s=“s0s1…sn-1”，模式t=“t0t1…tm-1”，在进行第i趟匹配时，出现以下情况：
这时，应有 "t0t1…tj-1"="si-jsi-j+1…si-1" 接下来，如何确定 t 中哪个字符和si进行比较？把该字符记为tk，显然k<j； 则有 “si-ksi-k+1…si-1”= “t0t1…tk-1” 故而有 “tj-ktj-k+1…tj-1”= “t0t1…tk-1”

53 下一次可直接比较si和tk 将这里的k记为next[j]

54 max{k|0<k<j,且“t0t1…tk-1”=“tj-ktj-k+1…tj-1” }
定义next[j]函数如下: max{k|0<k<j,且“t0t1…tk-1”=“tj-ktj-k+1…tj-1” } 当此集合非空时 当j=0时 其他情况 next[j]= 举例：t=“abab”对应的next数组如下: j 1 2 3 t[j] a b next[j] -1

55 由模式串t求出next值的算法 void GetNext(SqString t,int next[]) { int j,k;
j=0;k=-1;next[0]=-1; while (j<t.length-1) { if (k==-1 || t.data[j]==t.data[k]) /*k为-1或比较的字符相等时*/ { j++; k++; next[j]=k; } else k=next[k]; 实际上是一个简单的模式匹配算法，只不过目标串和模式串是同一个串 j和k分别代表目标串和模式串的工作指针

56 int KMPIndex(SqString s,SqString t)
{ int next[MaxSize],i=0,j=0,v; GetNext(t,next); while (i<s.length && j<t.length) { if (j==-1 || s.data[i]==t.data[j]) { i++; j++; } /*i,j各增1*/ else j=next[j]; /*i不变,j后退*/ } if (j>=t.length) v=i-t.length; //返回匹配模式串的首字符下标 else v=-1; /*返回不匹配标志*/ return v;

57 KMP算法举例 j 1 2 3 4 t[j] a b next[j] -1

58 next函数的改进 将next[j]修正为nextval[j]：
t[j] a a a a b next[j] nextval[j] 将next[j]修正为nextval[j]： 比较t.data[j]和t.data[k],若不等,则 nextval[j]=next[j];若相等nextval[j]=nextval[k]; 若next[j]=k，当si 与tj失配且tj=tk时，下一步不需将主串中的si 和tk 比较，而是直接与tnext[k] 进行比较即可

59 本章小结 (1) 理解串和一般线性表之间的差异。 (2)重点掌握在顺序串上和链串上实现串的基本运算算法。 (3) 掌握串的模式匹配算法。
(4) 灵活运用串这种数据结构解决一些综合应用问题。

60 作 业 教材P119 练习题4 习题4.2、4.3(1) 学习指导 第4章 P 、4 P