数据结构讲义4

1、2021-10-171柳 青Email: School of Software , Yunnan University 数据结构数据结构(Data Structure)2021-10-172第四章第四章 串串v4.1 串类型的定义v4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示 4.2.3 串的块链存储表示v4.3 串的模式匹配算法2021-10-173一、串及其基本概念一、串及其基本概念 串的定义：串的定义：串串(String)(String)是零个或多个字符组成的有限序列。是零个或多个字符组成的有限序列。 一般记作一般记作S=“aS=“a1 1a a2 2

2、a a3 3a an n”，其中，其中S S是串名，双引号括起来的是串名，双引号括起来的字符序列是串值；字符序列是串值；a ai i(1in)(1in)可以是字母、数字或其它字符。可以是字母、数字或其它字符。 串的长度：串的长度：串中所包含的字符个数称为该串的长度。串中所包含的字符个数称为该串的长度。 空串：空串：长度为零的串称为空串长度为零的串称为空串(Empty String)(Empty String)，它不包含任，它不包含任何字符。何字符。 空格串：空格串：将仅由一个或多个空格组成的串称为空格串将仅由一个或多个空格组成的串称为空格串(Blank (Blank String)String

3、)。注意：空串和空格串的不同，例如。注意：空串和空格串的不同，例如“ ”“ ”和和“”“”分分别表示长度为别表示长度为1 1的空格串和长度为的空格串和长度为0 0的空串。的空串。4.1 4.1 串类型的定义串类型的定义2021-10-174v子串与主串：子串与主串：串中任意个连续字符组成的子序列称为该串的串中任意个连续字符组成的子序列称为该串的子串子串，包含子串的串相应地称为，包含子串的串相应地称为主串主串。通常将子串在主串中。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的子串在主串中的位置位置。 例如，

4、设例如，设A=“This is a string” B=“is”A=“This is a string” B=“is”则则B B是是A A的子的子串，串，A A为主串。为主串。B B在在A A中出现了两次，其中首次出现所对应的中出现了两次，其中首次出现所对应的主串位置是主串位置是3 3。因此，称。因此，称B B在在A A中的位置为中的位置为3 3。v相等：相等：当且仅当两个串的长度相等，并且每个对应位置的字当且仅当两个串的长度相等，并且每个对应位置的字符都相等时，称两个串相等。符都相等时，称两个串相等。 例如，例如，A=“BEIJING” B=“BEIJING”A=“BEIJING” B=“B

5、EIJING”，则串，则串A A与串与串B B相等。相等。v串常量和串变量：串常量和串变量：串常量和整常数、实常数一样，在程序中串常量和整常数、实常数一样，在程序中只能被引用但不能改变其值，即只能读不能写。串变量的值只能被引用但不能改变其值，即只能读不能写。串变量的值在程序中可以改变，即可以读也可以写。在程序中可以改变，即可以读也可以写。4.1 4.1 串类型的定义串类型的定义2021-10-175二、串的抽象数据定义二、串的抽象数据定义 ADT String 数据对象数据对象：D=ai| aiElemSet, i=1,2,n,n0 数据关系数据关系：R1=| ai-1, ai D, i=2,

6、n 基本操作基本操作： StrAssign( &T, chars ) /生成一个其值等于生成一个其值等于chars的串的串T。 StrCopy( &T, S) /由串由串S复制得串复制得串T。 Strcompare(S, T ) /若若ST则返回值则返回值0, S0,否则返回值否则返回值=0。 Concat(&T, S1, S2) /由由S1和和S2联结得到新串联结得到新串T 。 SubString(&Sub, S, pos, len) /取取S中中pos位置起始的长度为位置起始的长度为len的子串。的子串。 Index(S, T, pos) /返回串返回串T在在S中中pos位置之后第一次出现

7、的位置，或位置之后第一次出现的位置，或0。 ADT Stack4.1 4.1 串类型的定义串类型的定义2021-10-1764.1 串类型的定义串类型的定义三、串的基本操作三、串的基本操作 对于串的基本操作，许多高级语言均提供了相应的对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面仅介绍几种在运算或标准库函数来实现。下面仅介绍几种在C C语言中语言中常用的串运算。常用的串运算。定义下列几个变量：定义下列几个变量：char s120=“dirtreeformatchar s120=“dirtreeformat”,”, s220=“file.txt s220=“file.t

8、xt”;”;char s330,char s330,* *p;p;intint result; result;2021-10-1771 1 求串长求串长(length)(length) int strlen(char int strlen(char * *s); /s); /求串的长度求串的长度 例如：例如：printf(“%d”,strlen(s1); printf(“%d”,strlen(s1); 输出输出13132 2 串复制串复制(copy)(copy) char char * *strcopy(charstrcopy(char * *to,char to,char * *from);

9、from); 该函数将串该函数将串fromfrom复制到串复制到串toto中，并且返回一个指向串中，并且返回一个指向串toto的开的开 始处的指针。始处的指针。 例如：例如：strcopy(s3,s1); /s3=“dirtreeformatstrcopy(s3,s1); /s3=“dirtreeformat”3 3 联接联接(concatenation)(concatenation) char strcat(char char strcat(char * *to,char to,char * *from)from) 该函数将串该函数将串fromfrom复制到串复制到串toto的末尾，并且返回

10、一个指向串的末尾，并且返回一个指向串toto 的开始处的指针。的开始处的指针。 例如：例如：strcat(s3strcat(s3, “/”“/”) ) strcat(s3,s2); /s3=“dirtreeformat/file.txt strcat(s3,s2); /s3=“dirtreeformat/file.txt”4.1 4.1 串类型的定义串类型的定义2021-10-1784 4 串比较（串比较（compare)compare) int strcmp(char int strcmp(char * *s1,char s1,char * *s2);s2); 该函数该函数根据根据ASCII

11、ASCII码值码值比较串比较串s1s1和串和串s2s2的大小，当返回值小于的大小，当返回值小于0 0，等于，等于0 0或大于或大于0 0时分别表示时分别表示s1s2s1s2s1s2 例如：例如：result=strcmp(“baker”,“Bakerresult=strcmp(“baker”,“Baker”); /”); /result0result0 result=strcmp(“12”,“12”); / result=strcmp(“12”,“12”); /result=0result=0 result=strcmp(“Jos”,“Joseph result=strcmp(“Jos”,“J

12、oseph”); /”); /result0result05 5 字符定位字符定位(locate)(locate) char strchr(char char strchr(char * *s,char c);s,char c); 该函数是找该函数是找c c在字符串中第一次出现的位置，若找到则返回该在字符串中第一次出现的位置，若找到则返回该 位置，否则返回位置，否则返回NULLNULL。 例如：例如：p=strchr(s2,“.”); /pp=strchr(s2,“.”); /p指向指向“file”file”之后的之后的位置位置 if(p) strcopy(p,“.cpp”); /s2=“fi

13、le.cppif(p) strcopy(p,“.cpp”); /s2=“file.cpp”4.1 4.1 串类型的定义串类型的定义2021-10-179例例1 1、求子串、求子串 求子串的过程即为复制字符序列的过程，将串求子串的过程即为复制字符序列的过程，将串S S中的第中的第pospos个个字符开始长度为字符开始长度为lenlen的字符复制到串的字符复制到串T T中。中。 void substr(char void substr(char * *sub,char sub,char * *s,int pos,int lens,int pos,int len) ) if( posstrlen(s

14、)-1 | lenstrlen(s if( posstrlen(s)-1 | lenstrlen(s)-)-pos )pos ) error(“parameter error”) error(“parameter error”)； strncpystrncpy(sub,s+pos,len(sub,s+pos,len) )； 例例2 2、串的定位、串的定位index(char index(char * *s,char s,char * *t,intt,int pos) pos) 求串求串T T在主串在主串S S中第中第pospos个字符之后的位置。方法：从主串个字符之后的位置。方法：从主串S S

15、的第的第pospos个字符开始，取长度和串个字符开始，取长度和串T T相等的子串和相等的子串和T T比较，若相等，则求比较，若相等，则求得函数值为得函数值为pospos。否则子串位置增。否则子串位置增1 1继续与继续与T T比较，直至找到与比较，直至找到与T T相相等的子串或确定等的子串或确定S S中不存在和串中不存在和串T T相等的子串为止。相等的子串为止。4.1 4.1 串类型的定义串类型的定义2021-10-1710 int index(char *s, char *t, int pos) if( pos0 ) n = strlen( s ); m = strlen( t ); i =

16、pos; while( in-m+1 ) substr( sub, s, i, m ); if( strcompare( sub, t ) != 0 ) +i; else return( i ); return( 0 ); 4.1 4.1 串类型的定义串类型的定义2021-10-1711 定长顺序存储表示定长顺序存储表示, ,也称为静态存储分配的顺应表。它是用一组也称为静态存储分配的顺应表。它是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用是直接使用定长的字符数组定长的字符数组来定义，数组的上界预先给出：来定

17、义，数组的上界预先给出： #define maxstrlen#define maxstrlen 255 255 typedef typedef char SStringmaxstrlen+1; / char SStringmaxstrlen+1; / 0 0分量存放串长分量存放串长4.2 4.2 串的表示和实现串的表示和实现4.2.1 4.2.1 定长顺序存储表示定长顺序存储表示 Status SubString( SString &Sub, SString S, int pos, int len ) if( pos S0 | len S0-pos+1 ) return ERROR; Sub1

18、.len = Spos.pos+len-1; Sub0 = len; retrun OK; 2021-10-1712 Status Concat(SString &T, SString S1, SString S2) if( S10 + S20 = maxstrlen ) T1.S10 = S11.S10; TS10+1.S10+S20 = S21.S20; T0 = S10 + S20; return TRUE; else if ( S10 maxstrlen ) T1.S10 = S11.S10; TS10+1.maxstrlen = S21.maxstrlen-S10; T0 = max

19、strlen; return FALSE; else T0.maxstrlen = S10.maxstrlen; return FALSE; 4.2 4.2 串的表示和实现串的表示和实现2021-10-1713 以一组地址连续的存储单元存放串值字符序列，但它以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得，所以们的存储空间是在程序执行过程中动态分配而得，所以也称为动态存储分配的顺序表。在也称为动态存储分配的顺序表。在C C语言中，利用动态分语言中，利用动态分配和释放函数配和释放函数mallocmalloc()()和和free()free()来进行存储管理

20、，根据来进行存储管理，根据实际需要动态分配和释放字符数组空间。实际需要动态分配和释放字符数组空间。typedef structtypedef struct char char * *chch; ; int int length; length; HString HString; ;4.2.2 4.2.2 堆堆(Heap)(Heap)分配存储表示分配存储表示4.2 4.2 串的表示和实现串的表示和实现2021-10-1714 Status strassign(HString t, char *chars) /生成一个其值等于串常量生成一个其值等于串常量charschars的串的串t t if (

21、t.ch) free(t.ch); for (i=0, c=chars; c; +i, +c) ; / 求chars的长度 if (!i) t.ch=NULL; t.length=0; else if (!(t.ch=(char *)malloc(i*sizeof(char) exit(overflow); t.ch0.i-1 = chars0.i-1; t.length=i; 4.2 4.2 串的表示和实现串的表示和实现2021-10-1715 int strlen(HString s) return s.length; Status clearstring(HString s) if(s.

22、ch) free(s.ch); s.ch=NULL; s.length=0; int strcompare(HString s, HString t) for(i=0; is.length & i0 or 0 or 0 4.2 4.2 串的表示和实现串的表示和实现2021-10-1716 Status concat(HString t, HString s1, HString s2) if(t.ch) free(t.ch); if(!(t.ch=(char*)malloc(s1.length+s2.length)*sizeof(char) exit(overflow); t.ch0.s1.le

23、ngth-1=s1.ch0.s1.length-1; t.length=s1.length+s2.length; t.chs1.length.t.length-1=s2.ch0.s2.length-1; return OK; 4.2 4.2 串的表示和实现串的表示和实现2021-10-1717 Status substr(HString sub, HString s, int pos, int len) if( poss.length | lens.length-pos+1 ) return ERROR; if(sub.ch) free(sub.ch); if(!len) sub.ch=NUL

24、L; sub.length=0; else sub.ch=(char *)malloc(len*sizeof(char); sub.ch0.len-1=spos-1.pos+len-2; /从0开始 s.length=len; return OK; 4.2 4.2 串的表示和实现串的表示和实现2021-10-1718 顺序串上的插入和删除操作不方便，需要移动大量的字顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，可用单链表方式来存储串值，串的这种链式存符。因此，可用单链表方式来存储串值，串的这种链式存储储结构简称为结构简称为链串链串。 一个链串由头指针唯一确定。这种结构便于进行插入一

25、个链串由头指针唯一确定。这种结构便于进行插入和和删除运算，但存储空间利用率太低。删除运算，但存储空间利用率太低。A B C DE F G HI# # #headheadABCI4.2.3 4.2.3 串的块链存储表示串的块链存储表示4.2 4.2 串的表示和实现串的表示和实现2021-10-17194.3 4.3 串的模式匹配算法串的模式匹配算法Si-j+1 Si-j+2 Si-1 Si Si+1 P1 P2 Pj-1 Pj 失配位置失配位置 P1 P2 Pj-1 Pj 下次匹配位置下次匹配位置e.g: S=a b c a b c a b c d P= a b c a b c d a b c

26、a b c d 模式右移一位模式右移一位4.3.1 4.3.1 求子串位置的定位函数求子串位置的定位函数Index( )Index( )模式匹配：模式匹配：求子串（求子串（模式串模式串）在主串的位置。）在主串的位置。基本方法：基本方法：从指定位置开始逐个比较主串与模式串的字符，一从指定位置开始逐个比较主串与模式串的字符，一旦发现出现字符不匹配，则整个模式相对于原来的位置右移一旦发现出现字符不匹配，则整个模式相对于原来的位置右移一位。如下图所示：位。如下图所示：2021-10-1720最基本的模式匹配程序：最基本的模式匹配程序：int Index( SString S, SString T, i

27、nt pos ) / 在主串S的第POS个字符之后，寻找模式T的匹配位置 i = pos ; j = 1; while ( i = S0 & j T0 ) return i-T0 / T在S中的匹配起始位置 else return 0;4.3 4.3 串的模式匹配算法串的模式匹配算法演示2021-10-1721 S=aaaaaaaaab P=aab a、b不等不等模式右移一位模式右移一位 S=aaaaaaaaab P= aab a、b不等不等模式右移一位模式右移一位 S=aaaaaaaaab P= aab a、b不等不等模式右移一位模式右移一位 S=aaaaaaaaab P= aab a、b不

28、等不等模式右移一位模式右移一位 S=aaaaaaaaab P= aab S=aaaaaaaaab P= aab S=aaaaaaaaab P= aab S=aaaaaaaaab P= aab a、b不等不等模式右移一位模式右移一位 a、b不等不等模式右移一位模式右移一位 a、b不等不等模式右移一位模式右移一位 完全匹配完全匹配 n-m+1匹配起始位置匹配起始位置4.3 4.3 串的模式匹配算法串的模式匹配算法4.3.2 4.3.2 Knuth-Morris-Pratt 模式匹配算法（模式匹配算法（KMP 算法）算法） 说明基本模式匹配算法在最坏情况下时间复杂度为说明基本模式匹配算法在最坏情况下时间复杂度为 O（ n * m）的实的实例（例（n为主串长度，为主串长度，m为模式长度）。为模式长度）。每比较每比较m次，移动模式一次。最后次，移动模式一次。最后在主串的在主串的 n-m+1 找到找到子子串，比较串，比较 （n-m+1）* m 次次 。2021-10-1722 S = abcabcabcd P = abcabcd S = abcabcabcd P = abcabcd S = abcabcabcd P = abcabcd S = abcabcabcd P = abcabcd 失配点失配点右移一位，仍失配右移一位，仍失配又右移