5.1 串的基本概念 5.2 串的存储结构 5.3 串的基本运算 5.4 模式匹配 5.5 串在文本编辑中的应用

Presentation on theme: "5.1 串的基本概念 5.2 串的存储结构 5.3 串的基本运算 5.4 模式匹配 5.5 串在文本编辑中的应用"— Presentation transcript:

1 5.1 串的基本概念 5.2 串的存储结构 5.3 串的基本运算 5.4 模式匹配 5.5 串在文本编辑中的应用
第五章 串 5.1 串的基本概念 5.2 串的存储结构 5.3 串的基本运算 5.4 模式匹配 5.5 串在文本编辑中的应用

2 5.1 串的基本概念 串（String）：由零个或多个字符组成的有限连续序列，一般记为 S= ‘s1s2…s n ’
5.1 串的基本概念 串（String）：由零个或多个字符组成的有限连续序列，一般记为 S= ‘s1s2…s n ’ 空串（null string）：由零个字符组成的串 空格串：由一个或多个空格组成的串 子串：字符串中任意个连续的字符构成的子序列 主串：包含子串的字符串 位置：一个字符在序列中的序号称为该字符在串中的位置 两串相等：两个字符串的长度相等且各对应位置上的字符都相同

3 串变量：形如下面语句 S=‘12345’ 是一个合法的附值语句，其含义是把串值附给串变量，S是串变量名，字符序列12345是串值
事例：串a=‘BAO’, b=‘DING’,c=‘BAODING’，d=‘BAO□DING’，则： (1) a，b，c，d的串长分别为3，4，7, 8 (2) 串a，b都是串c，d的子串，其在主串c中的位置分别为1和4, 在主串d中的位置分别为1和5 (3) c不等于d

4 5.2 串的存储结构 串的静态存储结构 ：将串定义成字符型数组，串的存储空间分配在编译时完成，不能更改
5.2 串的存储结构 串的静态存储结构 ：将串定义成字符型数组，串的存储空间分配在编译时完成，不能更改 串的动态存储结构 ：串的存储空间在程序运行时动态分配 ，分为 链式存储结构 堆结构的存储方式

5 5.2.1 串的静态存储结构 串的顺序存储结构表示 #define MAXSTRLEN 256 /*定义串允许的最大字符个数*/
struct string { char ch_string[MAXSTRLEN]; /* MAXSTRLEN为串的最大长度*/ int len; /*串的实际长度*/ }SString

6 顺序存储结构的两种存储方式 紧凑格式：在存储单元中尽量的多存储字符
非紧凑格式 ：一个存储单元只存放字符串的一个字符，存储中多余的空间置空不用 事例：S=‘Love China’ 二者比较：紧凑格式空间利用率高，而非紧凑格式对串中字符的处理效率低。

7 串的静态存储结构的两个缺点： 需要预先定义一个串允许的最大字符个数，当该值估计过大时，存储密度就会降低，较多的空间就会被浪费掉
由于限定了串的最大字符个数，使串的某些操作 返回

8 5.2.2 串的动态存储结构 链式存储结构：包含字符域和指针域的结点链结结构 事例：S=‘Study Data Structures’
块链存储结构：每个节点存放若干个字符，提高空间利用率

9 堆结构的存储方式 ：系统将一个空间足够大、地址连续的存储空间作为串值的可利用空间；建立一个新串时，系统就从这个可利用空间中划分出一个大小和串长度相等的空间存储新串的串值；每个串的串值各自存储在一组地址连续的存储单元中 串的堆结构存储表示 typedef struct { char *ch; /*若是非空串，则按串长分配存储区，否则ch为NULL*/ int length; /*串长度*/ }HString;

10 算法5.1：堆结构的存储方式实现串插入操作 Status StrInsert(HString &S,int pos,HString T) {
if(pos<1||pos>S.length+1) return ERROR; /*pos的值不合法*/ if(T.length) /*T非空，则进行下列操作*/ { /*重新分配存储空间，插入T*/ if(!(S.ch=(char *) realloc(S.ch,(S.length+T.length)*sizeof(char)))) exit(OVERFLOW); for(i=s.length-1;i>=pos-1;--i) S.ch[i+T.length]=S.ch[i]; /*插入位置之后所有的元素后移*/

11 /*在pos位置插入串T*/ S.ch[pos-1..pos+T.length-2]=T.ch[0..T.length-1]; S.length+=T.length; /*修改串的长度*/ } //end if(T.length) return OK; }

12 该操作是将串S的值赋给串T，例如Assign(&t，s3)之后，t=‘student’
5.3 串的基本运算 串的基本运算 假设有以下串： s1=‘I am a student’ s2=‘child’ s3=‘student’ 基本运算 串赋值Assign(&T,S) 该操作是将串S的值赋给串T，例如Assign(&t，s3)之后，t=‘student’

13 串联接Concation（＆T，S1，S2）
该操作是由串S1联结串S2得到的串T,例如Concation(&t,s1, ‘ Yes or No’)后，t=‘I am a student Yes or No’ 求子串SubString（&Sub，S，pos，len） 将串S第pos个字符开始长度为len的字符序列复制到串Sub中,例如S=‘wybbshrshchzhyg’SubString(&Sub，S，8，6)=‘shchzh’ 串复制 StrCopy(&T,S) 由串S复制得到串T,例如StrCopy(&t，s1)后，t=‘I am a student’　

14 串比较StrCompare(S,T) 比较串S和T两个串的长度是否相等且各对应位置上的字符是否都相等，并返回相应的值，例如StrCompare(s2，s3)，其返回值为0（表示串不相等） 求串长StrLength(S) 该操作返回串S的实际长度，例StrLength(s2)，其值为5

15 5.3.2 实现串的基本运算的算法 串赋值Assign(&T,s) 算法5.2 typedef struct {
char *ch; /*若是非空串，则按串长分配存储区，否则ch为NULL*/ int length; /*表示串的长度*/ }HString

16 /*将串s的值赋给串T*/ status Assign( HString&T, char *s) { char c; if (T.ch)
free (T.ch); /*释放T的原有空间*/ for( i=0, c=s; c; ++i; ++c); /* 求s的长度i*/ if（! i） T.ch=Null; T.length=0; } else

17 { if ( ! ( T.ch =( char * ) malloc (i *sizeof (char )))) exit (overflow ); T.ch [0…i-1] = s [0…i-1]; T.length=i; }//end else return OK; }

18 串联接Concation（＆T，S1，S2） 产生三种情况：
(1) S1.len+S2.len≤MAXSTRLEN，得到串T为正确结果，如图5-5(a)所示； (2) S1.len<MAXSTRLEN，S1.len + S2.len >MAXSTRLEN，此时则需将串S2的一部分截断，得到的串T包含串S1和串S2的一部分子串，如图5-5(b)所示；

19 (3) S1.len =MAXSTRLEN，此时得到的结果等于S1的值, 如图5-5(c)所示

20 算法： #define MAXSTRLEN 256 /*定义串允许的最大字符个数*/ struct string {
char ch_string[MAXSTRLEN]; /* MAXSTRLEN为串的最大长度*/ int len; /*串的实际长度*/ } SString

21 /*将串S1,S2连接起来赋予串T*/ Struct String Concation(SString &T，SString S1，SString S2) { if(S1.len+S2.len<= MAXSTRLEN) /*正常连接,S2未截断*/ T.ch_string[1…S1.len]=S1.ch_string[1…S1.len]; T.ch_string[S1.len+1…S1.len+S2.len]=S2.ch_string[1...S2.len]; T.len=S1.len+S2.len; /*uncut 标志S2是否被截断，uncut值为TRUE时表示没有被截断*/ uncut=TRUE; } else

22 if(S1.len<MAXSTRLEN)
T.ch_string[1…S1.len]=S1.ch_string[1…S1.len]; T.ch_string[S1.len+1…MAXSTRLEN]=S2.ch_string[1…MAXSTRLEN- S1.len]; T.len =MAXSTRLEN; /*uncut 标志S2是否被截断，uncut值为FALSE时表示被截断*/ uncut=FALSE; } else { /*仅取S1*/ T.ch_string[1...MAXSTRLEN]=S1.ch_string[1...MAXSTRLEN]; T.len= MAXSTRLEN return uncut;

23 求子串SubString（&Sub，S，pos，len)
#define MAXSTRLEN /*定义串允许的最大字符个数*/ struct string { char ch_string[MAXSTRLEN]; /* MAXSTRLEN为串的最大长度*/ int len; /*串的实际长度*/ } SString

24 /*用Sub返回串S的第pos个字符起长度为len的子串*/
Struct string SubString(SString &Sub,SString S,int pos,int len) /*pos的允许范围是:1≤pos≤ S.len 并且0≤len≤S.len-pos+1*/ { if(pos<1||pos>S.len)||len<0||len>S.len-pos+1) return ERROR; Sub.ch_string[1..len]=S.ch_string[pos..pos+len-1]; Sub.len=len; return OK; }

25 串复制(StrCopy(&T,S)) #define MAXSTRLEN 256 /*定义串允许的最大字符个数*/
struct string { char ch_string[MAXSTRLEN]; /* MAXSTRLEN为串的最大长度*/ int len; /*串的实际长度*/ } SString /*由串S复制得到串T */ void StrCopy(SString T, SString S) { int i; for(i=0;i<S.len;i++) T[i]=S.ch_string[i]; /*复制S中所有有效字符*/ T[i]= ‘\0’; /*复制串结束符*/ T.len=S.len; }

26 串比较(StrCompare(S,T)) #define MAXSTRLEN 256 /*定义串允许的最大字符个数*/
struct string { char ch_string[MAXSTRLEN]; /* MAXSTRLEN为串的最大长度*/ int len; /*串的实际长度*/ } SString

27 /*比较串S1和串S2的大小，若串S1和串S2相等时，函数返回值为1，否则返回值为0*/
int StrCompare(SString S1, SString S2) { int i； if (S1.len != S2.len) /*两串长度不相等，返回值为0*/ return (0); else for (i = 0;i<S1.len ; i++) if (S1.ch_string[i]!=S2.ch_string[i]) /*第i个字符不相同，返回函数值为0*/ /*两串相等，返回函数值为1*/ return (1); }

28 求串长(StrLength(S)) int StrLength(string S) { int i; i=0;
while(S[i]!='\0') /*注意‘\0’不计入串长*/ i++; return i; /*i为字符串的实际长度*/ }

29 模式匹配 ：设s和t是给定的两个串，在串s中找到等于t的子串的过程
5.4 模式匹配 模式匹配 ：设s和t是给定的两个串，在串s中找到等于t的子串的过程

30 5.4.1 模式匹配的BF算法 算法思想：s中的第一个字符与t中的第一个字符进行比较，若不同，就将s 中的第二个字符与t中的第一个字符进行比较……，直到s的某一个字符和t的第一个字符相同；再将它们之后的字符进行比较，若也相同，则如此继续往下比较；依此类推，重复上述过程。最后，会出现两种情况： (1) 在s中找到和t相同的子串，则匹配成功 (2)将s的所有字符都检测完了，找不到与t相同的子串，则匹配失败

31 算法： #define MAXSTRLEN 256 /*定义串允许的最大字符个数*/ struct string {
char ch_string[MAXSTRLEN]; /* MAXSTRLEN为串的最大长度*/ int len; /*串的实际长度*/ } SString /*在主串s中定位查找子串t的BF模式匹配算法*/ int BFIndex (SString s, SString t) {/*i,j为串数组的指针，分别指示主串s和子串t当前待比较的字符位置*/ int i, j,v ; i=0; /*主串指针初始化*/ j=0; /*子串指针初始化*/

32 while (i < s.len && j< t.len )
{ if ( s.ch_string [i] =t.ch_string [j] ) /*继续匹配下一个字符*/ i++; j++; } else /*主串和子串指针回退重新开始下一次匹配*/ i=i-j+1 ; /*新一轮匹配开始，t0对应的s的开始比较位置*/ j=0 ; /*从子串的第一个字符进行新匹配*/

33 if (j >= t.len ) v = i – t .len ; /*v指向匹配成功的第一个字符*/ else v = -1 ; /*模式匹配不成功*/ return (v); } 时间复杂度：O(n×m) 事例：设目标串s=‘addada’，模式串t=‘ada’。s的长度为n(n=6)，t的长度为m(m=3)；用指针i指示目标串s的当前比较字符位置，用指针j指示模式串t的当前比较字符位置

34 匹配过程：

35 5.4.2 模式匹配的KMP算法 KMP算法的基本思想：设s为目标串，t为模式串，设i指针和j指针分别指示目标串和模式串中正待比较的字符，开始时，令i = 0，j = 0。如果si= tj，则使i和j的值分别增加1；反之，i不变，j的值退回到j = next[j]的位置（即模式串右滑），然后再对si和tj进行比较。依次类推，直到出现下列两种情况之一： （1）j值退回到某个j=next[j]时，有si= tj，则指针的值各增加1后，再继续匹配； （2）j值退回到j=-1，此时令指针的值各增加1，也即下一次对si+1和t0进行比较。

36 函数next[j]： (1) 当存在 ‘t0 t1…tk-1’=‘tj-ktj-k+1…tj-1’ (0<k<j)时：next[j] = max{k|0< k < j且‘t0 t1…tk-1’=‘tj-ktj-k+1…tj-1’ } (2) 当j = 0时，next[j] = -1 其他情况， next[j] = 0

37 KMP模式匹配算法 #define MAXSTRLEN 256 /*定义串允许的最大字符个数*/ struct string {
char ch_string[MAXSTRLEN]; /* MAXSTRLEN为串的最大长度*/ int len; /*串的实际长度*/ } SString /*数组Next为全局变量*/ int Next[MAXSTRLEN] /*在主串s中定位查找子串t的KMP算法*/ int KMPIndex ( SString s, SString t) int i, j, v ; i =0; /*主串指针初始化*/ j = 0; /*子串指针初始化*/

38 while (i < s.len && j < t.len )
{ /*主串和子串的指针值各增加1*/ if ( j == -1|| s.ch_string[i] == t.ch_string[j] i ++; j ++; } /*主串指针i不回退，子串指针j回退至Next[j]*/ else j = Next[j]; if ( j>= t.len ) v = i-t.len;/*v指向匹配成功的第一个字符*/ v = -1; /*模式匹配不成功*/ return (v);

39 (1)当j = 0 时，根据next[j]的定义可以得知，next[j]= -1
(2)设存在next[j] = k，即在模式串t中存在‘t0 t1…tk-1’=‘tj-k tj-k+1…tj-1’（0<k<j），k是满足‘t0 t1…tk-1’=‘tj-k tj-k+1…tj-1’等式的最大值,求next[j+1]的值分以下两种情况： 如果tk=tj ，则next[j+1] =next[j] + 1=k+1 如果tk !=tj ，则next[j+1] = k’+1=next[k] + 1

40 事例：求t=‘aaab’的next[j]值
求解过程如下： 当j = 0时，next[0] = -1 当j = 1时，next[1] = 0 当j = 2时，有t0=t1 =‘a’，所以有next[2] = 1 当j = 3时，有t0t1 = t1t2 =‘aa’，所以有next[3] = 2 即有

41 next[j]的算法 /*数组Next为全局变量*/ #define MAXSTRLEN 256 /*定义串允许的最大字符个数*/
struct string { char ch_string[MAXSTRLEN]; /* MAXSTRLEN为串的最大长度*/ int len; /*串的实际长度*/ } SString /*数组Next为全局变量*/ int Next[MAXSTRLEN] /*求模式串t的next值。所求值存于全局变量Next数组中*/ void GetNext (SString t) int j , k ; /*指针初始化*/ k = -1 ; j = 0 ; Next[0] = -1 ;

42 while (j < t.len –1 ) { if (k == -1 || t.ch_string[j] ==t.ch_string[k] ) j ++ ; k ++; Next [j] = k ; } else k = Next[k];

43 5.5 串在文本编辑中的应用 文本编辑：利用换页符和换行符把文本划分为若干页，每页有若干行；若把文本看作一个字符串，称为文本串，否则就是文本串的子串，行又是页的子串； 事例：有下列一段源程序： main() { float i,j,min; scanf(“%f,%f”,&i,&j); if (i>j ) min=j; else min=i; }

44 输入到内存后如图5-3所示 : 文本串的行表：

45 文本编辑过程: 首先，输入文本,并编辑程序将建立行表 插入一行时，既需在文本末尾的空闲工作区写出该行的串值，又要在行表中建立该行的信息
删除一行时，只要在行表中删除这个行号就等于从文本中抹去了这一行