第章 数组 (Array)北京科技大学

1、“串串”（StringString）是字符串的简称）是字符串的简称，它也是一种，它也是一种特殊的线性表特殊的线性表，由它组，由它组成的线性表的数据元素最为简单，仅成的线性表的数据元素最为简单，仅为单个字符为单个字符1234 (1)(1)串是由零个或多个字符组成的串是由零个或多个字符组成的有序序列有序序列。 (2)(2)值为空格的字符串值为空格的字符串不同不同于空串。于空串。 (3)(3)值为单个字符的字符串值为单个字符的字符串不同不同于单个字符。于单个字符。 (4)(4)一个串中任意多个连续的字符组成的子序一个串中任意多个连续的字符组成的子序 列称为该串的列称为该串的子串子串。包含该子串的串称

2、为。包含该子串的串称为 主串主串。(5) (5) 子串在主串中的位置指的是该子串的第一个子串在主串中的位置指的是该子串的第一个 字符在主串中的位置。字符在主串中的位置。(6) (6) 两个两个串相等串相等指两个串中的字符序列一一对应指两个串中的字符序列一一对应(7) (7) 一个串的一个串的长度长度指的是串中所包含的字符个数指的是串中所包含的字符个数(8) (8) 在在C C语言中语言中, ,串是由双引号括起来的，双引号串是由双引号括起来的，双引号 本身不是串的组成部分。本身不是串的组成部分。举例举例S1 = “I am a student”S2 = “child”S3 = “a”S4 = “

3、student”S5 = “student ” S1S1是是S3S3和和S4S4的主串，子串的主串，子串S3S3在在S1S1中的位中的位置为置为3 3，子串，子串S4S4在在S1S1中的位置为中的位置为8 8。S4S4的长度的长度是是7 7，S5S5的长度是的长度是8 8，S4S4和和S5S5不相等，不相等，S5S5不是不是S1S1的子串。的子串。12341.串的顺序存储结构串的顺序存储结构2.串的链式存储结构串的链式存储结构3.串的索引存储结构串的索引存储结构 串的顺序存储结构简称为串的顺序存储结构简称为顺序串顺序串。顺序。顺序串中的字符被顺序地存放在内存的一片相邻串中的字符被顺序地存放在内

4、存的一片相邻的单元中。的单元中。 在在C C语言中，用一个特定的、不会出现在语言中，用一个特定的、不会出现在串中的字符作为串的终结符，这就是串中的字符作为串的终结符，这就是00This is a string00Maxsize-1串的顺序存储形式串的顺序存储形式#define maxsize 32typedef struct char chmaxsize;int curlen; seqstring;链串的定义与单链表类似，串链串的定义与单链表类似，串的链接存储形式为的链接存储形式为typedef struct linknode char data;struct linknode *next;

5、linkstring;abcdefga b c de f g 0a b c xf g 0 0y z d e结点大小为结点大小为1 1的链串的链串结点大小为结点大小为4 4的链串的链串结点大小为结点大小为4 4的链串在第三个字符后插入的链串在第三个字符后插入“xyz”xyz” 该方法是用串变量的名字作为关键字该方法是用串变量的名字作为关键字组织名字表，该表中存储的是串名和串值之组织名字表，该表中存储的是串名和串值之间的对应关系。名字表一般是顺序存放的。间的对应关系。名字表一般是顺序存放的。s17s23. a b c d e fg b c d .带长度的名字表带长度的名字表name length

6、stadrname length stadr串的索引存储形式带长度的名字表串的索引存储形式带长度的名字表typedef struct char namemaxsize;int length;char *stadr; lnodes17s23. a b c d e fg b c d .带长度的名字表带长度的名字表name length stadrname length stadrs1s2. a b c d e fg b c d .带末指针的名字表带末指针的名字表name enadr stadrname enadr stadr串的索引存储形式带末指针的名字表串的索引存储形式带末指针的名字表typed

7、ef struct char namemaxsize;char *stadr,*enadr; enode;s10s21bcd0. a b c d e fg 0带特征位的名字表带特征位的名字表 name tag stadr name tag stadr/value/value.串的索引存储形式带特征位的名字表串的索引存储形式带特征位的名字表typedef struct char namemaxsize;union char *stadr; char value4; uval; cedure. var i:integer在索引存储表示下，在索引存储表示下

8、， 串值空间的动态分配示意串值空间的动态分配示意name length stadrname length stadr0 14 free0 14 free1234(1) (1) 赋值赋值(2) (2) 联接联接(3) (3) 求串长求串长(4) (4) 求子串求子串(5) (5) 比较串的大小比较串的大小(6) (6) 插入插入(7) (7) 删除删除(8) (8) 子串定位子串定位(9) (9) 置换置换程序程序12341.求子串位置的定位函数求子串位置的定位函数2.简单的模式匹配简单的模式匹配3.无回溯的模式匹配无回溯的模式匹配(KMP算法算法) 子串的定位操作通常称为串的子串的定位操作通常

9、称为串的模式匹配模式匹配，它是串处理系统中最重要的操作之一，其操作它是串处理系统中最重要的操作之一，其操作记为记为Index(S,TIndex(S,T) )；其中；其中S=“sS=“s0 0s s1 1s sn-1n-1”为为主主串串，T=“tT=“t0 0t t1 1t tm-1m-1”为为子串子串（模式模式） 其意义是，若在其意义是，若在S S中存在一个与中存在一个与T T相等的子相等的子串，则称匹配成功，函数返回串，则称匹配成功，函数返回T T在在S S中首次出现中首次出现的开始位置；否则，称为匹配失败，函数返回的开始位置；否则，称为匹配失败，函数返回值为值为-1.-1.基本思想：基本思

10、想： 从主串从主串S S的第一个字符和子串的第一个字符和子串T T的第一个字的第一个字符开始比较，若相等，则比较它们的下一个字符开始比较，若相等，则比较它们的下一个字符；若不等，则不论前边已经有几个字符相符；若不等，则不论前边已经有几个字符相等，子串等，子串T T都要从第一个字符开始与主串都要从第一个字符开始与主串S S的第的第二个字符重新比较；依次类推，直到子串二个字符重新比较；依次类推，直到子串T T的每的每个字符依次和主串个字符依次和主串S S的一个连续的字符序列相的一个连续的字符序列相等，则模式匹配成功等，则模式匹配成功 i=2 i=2 第一次匹配第一次匹配 s = c d d c d

11、 e s = c d d c d e 失败失败 t = c d et = c d e j=2 j=2 i=1i=1第二次匹配第二次匹配 s = c d d c d e s = c d d c d e 失败失败 t = c d et = c d e j=0 j=0 i=2i=2第三次匹配第三次匹配 s = c d d c d e s = c d d c d e 失败失败 t = c d et = c d e j=0 j=0 i=6i=6第四次匹配第四次匹配 s = c d d c d e s = c d d c d e 成功成功 t = c d e t = c d e 返回返回i-ji-j=3=

12、3 j=3 j=3 简单模式匹配算法简单模式匹配算法int Index(seqstring *S,seqstring *T) int i=0,j=0; while (icurlen)&(jcurlen)if (S-chi=T-chj) i+; j+;elsei=i-j+1; j=0; if (j=T-curlen) return(i-T-curlen); else return(-1); 链串上的子串定位运算链串上的子串定位运算linkstring *INDEXL(linkstring *S,linkstring *T) linkstring *first,*sptr,*tptr; f

13、irst=S; sptr=first; tptr=T; while (sptr&tptr) if (sptr-data=tptr-data) sptr=sptr-next; tptr=tptr-next; else first=first-next; sptr=first; tptr=T; if (tptr=NULL) return(first); else return(NULL) 算法分析算法分析 在最坏情况下，第在最坏情况下，第i i趟匹配成功，前面趟匹配成功，前面i-1i-1趟的不成功的匹配中，每趟比较了趟的不成功的匹配中，每趟比较了m m次，第次，第i i趟成功时也比较了趟成

14、功时也比较了m m次，所以共比次，所以共比较了较了i i m m次。因此在最坏情况下，平均次。因此在最坏情况下，平均比较次数是：比较次数是：由于由于nmnm，故上述的时间复杂度为，故上述的时间复杂度为O(mO(mn)n)2/ )2()1/()(1111mnmimnmmiPmnimnii 分析简单匹配算法可以发现，算法中出分析简单匹配算法可以发现，算法中出现的主串指针回朔并非一定必要。现的主串指针回朔并非一定必要。第一次匹配第一次匹配 a c a b a a b a a b c a c a a b ca c a b a a b a a b c a c a a b c a b a a b c a

15、c a b a a b c a c第二次匹配第二次匹配 a c a b a a b a a b c a c a a b ca c a b a a b a a b c a c a a b c a b a a b c a c a b a a b c a c第三次匹配第三次匹配 a c a b a a b a a b c a c a a b ca c a b a a b a a b c a c a a b c a b a a b c a c a b a a b c a c第四次匹配第四次匹配 a c a b a a b a a b c a c a a b ca c a b a a b a a b c

16、 a c a a b c a b a a b c a c a b a a b c a c 可见，一旦可见，一旦s si i和和t tj j比较不相等，主串比较不相等，主串s s的指针不一定要回朔，主串的指针不一定要回朔，主串s si i（或（或s si+1i+1）可）可直接与直接与t tk k（0=kj0=kj）比较，）比较，k k的决定与主串的决定与主串s s并无关系，而只与模式串并无关系，而只与模式串t t本身的构成有本身的构成有关，即从模式串关，即从模式串t t本身就可求出本身就可求出k k值。值。 讨论一般情况，设讨论一般情况，设s=“ss=“s0 0s s1 1.s.sn-1n-1”

17、，t=“tt=“t0 0t t1 1.t.tm-1m-1”。假定：。假定：0 1111. .ki k i kit ttsss 若模式串中存在可互相重叠的真子串若模式串中存在可互相重叠的真子串, ,使得使得：0 1111. .kj k j kjt ttttt （1 1）说明模式串的子串说明模式串的子串“t t0 0t t1 1.t.tk-1k-1”已已和主串和主串 “ “s si-ki-ks si-k+1i-k+1.s.si-1i-1”匹配，下一次可匹配，下一次可直接比较直接比较s si i和和t tk k；（2 2）说明在说明在“t t0 0t t1 1.t.tk-1k-1”中不存在任何中不存

18、在任何以以t t0 0为首字符子串与为首字符子串与“s si-ki-ks si-k+1i-k+1.s.si-1i-1”中中以以s si-1i-1为末字符的匹配子串，下一次可直接为末字符的匹配子串，下一次可直接比较比较s si i和和t t0 0。（1 1）（2 2）定义定义nextjnextj如下：如下：10.,0|max11110jkjkjkttttttjkkjnext且其它情况当j=0时由此定义可推出由此定义可推出nextnext的函数值：的函数值：j j 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 模式串模式串nextjnextj a b a a b c a c a

19、b a a b c a c-1 0 0 1 1 2 0 1-1 0 0 1 1 2 0 1int Nextmaxsize;int KMPIndex(seqstring *S,seqstring *T) int i, j, v; i = 0; j = 0; while( i curlen & j curlen) if ( i = -1 | | S-chi =T-chj) i+; j+; else j = Nextj; if ( j=T-curlen ) v = i T-curlen; else v = -1; return( v );可以用递推的方法推出可以用递推的方法推出nextnex

20、t的值。当的值。当j j时，时，nextj=-1;nextj=-1;设设nextj=knextj=k，即，即t t中存在中存在.11110ikikiktttttt 以下求以下求nextj+1nextj+1，分两种情况讨论：，分两种情况讨论：1 1、若、若t tk k=t=tj j，则表明模式串，则表明模式串t t中有：中有：.11110jikikikktttttttt且不可能存在某个且不可能存在某个k kk k满足上式，因此满足上式，因此nextj+1 = nextj+1 = k+1;nextj+1 = nextj+1 = k+1;其中其中k k为满足等式的最大值。为满足等式的最大值。2 2、

21、若、若t tk kttj j，此时可把求，此时可把求nextj+1nextj+1值的问值的问题看作是一个模式匹配问题，即把模式串题看作是一个模式匹配问题，即把模式串tt向右滑动至向右滑动至k=nextkk=nextk（0kkj0kkj），若，若t tk k=t=tj j，则说明在主串，则说明在主串t t中第中第j+1j+1个字个字符之前存在一个长度为符之前存在一个长度为kk的子串满足：的子串满足：.110jkikiktttttt也就是说，也就是说，nextj+1 = k+1 = nextj+1 = k+1 = nextk+1;nextk+1;此时若此时若t tk kttj j，则将模式串，则将

22、模式串tt继续右滑至继续右滑至k”=nextkk”=nextk。以次类推，直到某次匹配成。以次类推，直到某次匹配成功或匹配失败。设功或匹配失败。设k kl l次右滑匹配失败，则有次右滑匹配失败，则有nextknextkl-1l-1=-1=-1，则有：，则有： nextj+1=nextknextj+1=nextkl-1l-1+1=-1+1=0+1=-1+1=0举例：现有如图所示的字符串。举例：现有如图所示的字符串。j j 0 1 2 3 4 5 6 70 1 2 3 4 5 6 7模式串模式串nextjnextj a b a a b c a c a b a a b c a c-1 0 0 1 1 2 0 1-1 0 0 1 1 2 0 1 已求得前已求得前6 6个字符的个字符的nextnext