《数据结构：第4章 串》由会员分享，可在线阅读，更多相关《数据结构：第4章 串（82页珍藏版）》请在金锄头文库上搜索。
1、第第4 4章章 串串 4.1 4.1 串的基本概念串的基本概念4.2 4.2 串的存储结构串的存储结构 本章小结本章小结4.3 4.3 串的模式匹配串的模式匹配 串串(或或字字符符串串),是是由由零零个个或或多多个个字字符符组组成成的的有有穷穷序列。含零个字符的串称为空串序列。含零个字符的串称为空串,用用表示。表示。 串中所含字符的个数称为该串中所含字符的个数称为该串的长度串的长度(或串长或串长)。 通通常常将将一一个个串串表表示示成成a1a2an的的形形式式。其其中中,最最外外边边的的双双引引号号本本身身不不是是串串的的内内容容,它它们们是是串串的的标标志志,以以便便将将串串与与标标识识符符
2、(如如变变量量名名等等)加加以以区区别别。每每个个ai(1in)代表一个字符。代表一个字符。4.1 4.1 串的基本概念串的基本概念 当当且且仅仅当当两两个个串串的的长长度度相相等等并并且且各各个个对对应应位位置置上上的字符都相同时的字符都相同时,这两个串才是相等的。这两个串才是相等的。 一一个个串串中中任任意意个个连连续续字字符符组组成成的的子子序序列列(含含空空串串)称称为为该该串串的的子子串串。例例如如,“a”、“ab”、“abc”和和“abcd”等都是等都是“abcde”的子串。的子串。 串的基本运算如下串的基本运算如下: (1)StrAssign(&s, chars):将将一一个个字
3、字符符串串常常量量赋给串赋给串s,即生成一个其值等于即生成一个其值等于chars的串的串s。 (2)StrCopy(&s, t):串复制串复制:将串将串t赋给串赋给串s。 (3)StrEqual(s, t):判判串串相相等等:若若两两个个串串s与与t相相等则返回真；否则返回假。等则返回真；否则返回假。 (4)StrLength(s):求串长求串长:返回串返回串s中字符个数。中字符个数。 (5)Concat(s, t):串串连连接接:返返回回由由两两个个串串s和和t连接在一起形成的新串。连接在一起形成的新串。 (6)SubStr(s, i, j):求求子子串串:返返回回串串s中中从从第第i(1i
4、StrLength(s)个个字字符符开开始始的的、由由连连续续j个个字符组成的子串。字符组成的子串。 (7)InsStr(s1, i, s2):将将串串s2插插入入到到串串s1的的第第i(1iStrLength(s)+1)个个字字符符中中,即即将将s2的的第一个字符作为第一个字符作为s1的第的第i个字符个字符,并返回产生的新串。并返回产生的新串。 (8)DelStr(s, i, j):从从 串串 s中中 删删 去去 从从 第第i(1iStrLength(s)个个字字符符开开始始的的长长度度为为j的的子串子串,并返回产生的新串。并返回产生的新串。 (9)RepStr(s, i, j, t):替替
5、换换:在在串串s中中,将将第第i(1iStrLength(s)个个字字符符开开始始的的j个个字字符符构构成的子串用串成的子串用串t替换替换,并返回产生的新串。并返回产生的新串。 (10)DispStr(s):串串输输出出:输输出出串串s的的所所有有元元素值。素值。4.2.1 4.2.1 串的顺序存储及其基本操作实现串的顺序存储及其基本操作实现 串串是是一一种种特特殊殊的的线线性性表表,在在非非紧紧缩缩格格式式中中,它它的的每每个个结结点点仅仅由由一一个个字字符符组组成成,因因此此存存储储串串的的方方法法也也就就是是存存储储线线性性表表的的一一般般方方法法。存存储储串串最最常常用用的的方方式式是
6、是采采用用顺顺序序存存储储,即即把把串串的的字字符符顺顺序序地地存存储储在在内内存存一一片片相相邻邻的的空空间间,这称为这称为顺序串顺序串。4.2 4.2 串的存储结构串的存储结构 顺顺序序存存储储采采用用一一般般顺顺序序表表的的存存储储结结构构,其其类类型型定定义义如下如下: #define MaxSize 100 typedef struct char dataMaxSize; int length; SqString; 其其中中,data域域用用来来存存储储字字符符串串,length域域用用来来存存储储字字符符串串的的当当前前长长度度,MaxSize常常量量表表示示允允许许所所存存储储字
7、字符符串串的的最最大大长长度度。在在C语语言言中中每每个个字字符符串串以以0标标志结束。志结束。 顺序串中实现串的基本运算如下顺序串中实现串的基本运算如下: (1)StrAssign(s,cstr) 将将一一个个字字符符串串常常量量赋赋给给串串s,即即生生成成一一个个其其值值等等于于cstr的串的串s。 void StrAssign(SqString &s, char cstr ) int i; for (i=0;cstri!=0;i+) s.datai=cstri; s.length=i; (2)StrCopy(s,t) 将串将串t复制给串复制给串s。void StrCopy(SqStrin
8、g &s, SqString t) /*引用型参数引用型参数*/ int i; for (i=0;it.length;i+) s.datai=t.datai; s.length=t.length; (3)StrEqual(s,t) 判判断断两两个个串串是是否否相相等等:若若两两个个串串s与与t相相等等返返回回真真(1)；否则返回假；否则返回假(0)。int StrEqual(SqString s, SqString t) int same=1, i; if (s.length!=t.length) same=0; /*长度不相等时返回长度不相等时返回0*/ else for (i=0;is.l
9、ength;i+) if (s.datai!=t.datai) /*有对应字符不相同时返回有对应字符不相同时返回0*/ same=0; break; return same; (4)Strlength(s)求串长求串长:返回串返回串s中字符个数。中字符个数。int StrLength(SqString s) return s.length; (5)Concat(s,t) 返回由两个串返回由两个串s和和t连接在一起形成的新串。连接在一起形成的新串。SqString Concat(SqString s, SqString t) SqString str; int i; str.length=s.l
10、ength+t.length; for (i=0;is.length;i+) /* 将将s.data0s.datas.length-1复制到复制到str */ str.datai=s.datai; for (i=0;it.length;i+) /* 将将t.data0t.datat.length-1复制到复制到str */ str.datas.length+i=t.datai; return str; (6)SubStr(s,i,j) 返返回回串串s中中从从第第i(1iStrLength(s)个个字字符符开始的、由连续开始的、由连续j个字符组成的子串。个字符组成的子串。SqString Sub
11、Str(SqString s, int i, int j) SqString str; int k; str.length=0; if (is.length | js.length) return str; /*参数不正确时返回空串参数不正确时返回空串*/for (k=i-1;kstr*/ str.datak-i+1=s.datak; str.length=j; return str; (7)InsStr(s1, i, s2) 将将串串s2插插入入到到串串s1的的第第i个个字字符符中中,即即将将s2的的第第一个字符作为一个字符作为s1的第的第i个字符个字符,并返回产生的新串。并返回产生的新串。
12、SqString InsStr(SqString s1, int i, SqString s2) int j;SqString str; str.length=0; if (is1.length+1) /*参数不正确时返回空串参数不正确时返回空串*/ return str; for (j=0;jstr*/ str.dataj=s1.dataj; for (j=0;jstr */ str.datai+j-1=s2.dataj; for (j=i-1;jstr */ str.datas2.length+j=s1.dataj; str.length=s1.length+s2.length; retu
13、rn str; (8) DelStr(s, i, j) 从从串串s中中删删去去第第i(1iStrLength(s)个个字字符符开开始的长度为始的长度为j的子串的子串,并返回产生的新串。并返回产生的新串。SqString DelStr(SqString s, int i, int j) int k; SqString str; str.length=0; if (is.length | i+js.length+1) /*参参数数不不正正确确时时返返回回空串空串*/ return str; for (k=0;kstr*/ str.datak=s.datak; for (k=i+j-1;kstr *
14、/ str.chk-j=s.chk; str.length=s.length-j; return str; (9) RepStr(s, i, j, t) 在在串串s中中,将将第第i(1iStrLength(s)个个字字符符开开始的始的j个字符构成的子串用串个字符构成的子串用串t替换替换,并返回产生的新串。并返回产生的新串。SqString RepStr(SqString s, int i, int j, SqString t) int k; SqString str; str.length=0; if (is.length | i+j-1s.length) /*参参数数不不正正确确时时返返回回
15、空串空串*/ return str; for (k=0;kstr*/ str.datak=s.datak; for (k=0;k str*/ str.datai+k-1=t.datak; for (k=i+j-1;kstr */ str.datat.length+k-j=s.datak; str.length=s.length-j+t.length; return str; (10) DispStr(s)输出串输出串s的所有元素值。的所有元素值。void DispStr(SqString s) int i; if (s.length0) for (i=0;is.length;i+) print
16、f(%c, s.datai); printf(n); 例例 4.1 设设 计计 顺顺 序序 串串 上上 实实 现现 串串 比比 较较 运运 算算Strcmp(s,t)的算法。的算法。 解解:本例的算法思路如下本例的算法思路如下: (1)比较比较s和和t两个串共同长度范围内的对应字符两个串共同长度范围内的对应字符: 若若s的字符的字符t的字符的字符,返回返回-1； 若若s的字符的字符t的字符的字符,返回返回1； 若若s的字符的字符=t的字符的字符,按上述规则继续比较。按上述规则继续比较。 (2)当当(1)中中对对应应字字符符均均相相同同时时,比比较较s1和和s2的的长长度度: 两者相等时两者相等
17、时,返回返回0； s的长度的长度t的长度的长度,返回返回1； s的长度的长度t的长度的长度,返回返回-1。 int Strcmp(SqString s, SqString t) int i,comlen; if (s.lengtht.length) comlen=s.length;/*求求s和和t的共同长度的共同长度*/ else comlen=t.length; for (i=0;icomlen;i+) /*逐个字符比较逐个字符比较*/ if (s.datait.datai) return 1; if (s.length=t.length) /*s=t*/ return 0; else if
18、 (s.lengtht.length) /*st*/ 4.2.2 4.2.2 串的链式存储及其基本操作实现串的链式存储及其基本操作实现 也也可可以以采采用用链链式式方方式式存存储储串串,即即用用单单链链表表形形式式存存储串。这称为链式串或链串。储串。这称为链式串或链串。 链串中的结点类型定义链串中的结点类型定义: typedef struct snode char data; struct snode *next; LiString ; 其其中中data域域用用来来存存储储组组成成字字符符串串的的字字符符,next域域用用来来指指向向下下一一个个结结点点。每每个个字字符符对对应应一一个个结结点
19、点,一一个个这这样样的的链链表表存存储储一一个个字字符符串串。下下图图所所示示是是一一个个结结点大小为点大小为1的链串。的链串。链串示意图链串示意图 下下面面讨讨论论在在链链串串上上实实现现串串基基本本运运算算的的算算法法。(只只讲讲1,2) (1)StrAssign(s,t) 将将一一个个字字符符串串常常量量t赋赋给给串串s,即即生生成成一一个个其其值值等等于于t的串的串s。以下采用尾插法建立链串。以下采用尾插法建立链串。void StrAssign(LiString *&s, char t ) int i; LiString *r,*p;/*r始终指向尾结点始终指向尾结点*/ s=(LiS
20、tring *)malloc(sizeof(LiString); s-next=NULL;r=s; for (i=0;ti!=0;i+) p=(LiString *)malloc(sizeof(LiString); p-data=ti;r-next=p;r=p;r-next=NULL; (2)StrCopy(s,t) 将将串串t复复制制给给串串s。以以下下采采用用尾尾插插法法建建立立复复制制后后的的链链串串s。 void StrCopy(LiString *&s,LiString *t) LiString *p=t-next,*q,*r; s=(LiString *)malloc(sizeof
21、(LiString); s-next=NULL;s-next=NULL;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; 4.3 4.3 串的模式匹配串的模式匹配 设有主串设有主串s和子串和子串t,子串子串t的定位就是要在主串的定位就是要在主串s中找到一个与子串中找到一个与子串t相等的子串。通常把相等的子串。通常把主串主串s称为称为目标串
22、目标串,把子串把子串t称为模式串称为模式串,因此定位也称作因此定位也称作模式匹模式匹配配。模式匹配成功是指在目标串。模式匹配成功是指在目标串s中找到一个模式串中找到一个模式串t；不成功则指目标串；不成功则指目标串s中不存在模式串中不存在模式串t。 例：例：s=“abcdefghij”, t=“fghi”Index(s,t)=64.3.1 Brute-Force4.3.1 Brute-Force算法算法 Brute-Force简称为简称为BF算法算法,亦称亦称简单匹配算简单匹配算法法,其基本思路是其基本思路是: 从目标串从目标串s=s0s1sn-1的第一个字符开始的第一个字符开始和模式串和模式串
23、t=t0t1tm-1中的第一个字符比较中的第一个字符比较,若相若相等等,则继续逐个比较后续字符；否则从目标串则继续逐个比较后续字符；否则从目标串s的第的第二个字符开始重新与模式串二个字符开始重新与模式串t的第一个字符进行比较。的第一个字符进行比较。依次类推依次类推,若从模式串若从模式串s的第的第i个字符开始个字符开始,每个字符依每个字符依次和目标串次和目标串t中的对应字符相等中的对应字符相等,则匹配成功则匹配成功,该算法该算法返回返回i；否则；否则,匹配失败匹配失败,函数返回函数返回-1。 目标串目标串s=“cddcdc”,模式串模式串t=“cdc”存储在存储在顺序顺序串串时的时的BF模式匹配
24、过程如下所示。模式匹配过程如下所示。 用指针用指针i指示目标串指示目标串s的当前比较字符位置的当前比较字符位置,用指针用指针j指示模式串指示模式串t的当前比较字符位置。的当前比较字符位置。data.lenS:cddcdc601234data.lent:cdc301234i=0j=0data.lenS:cddcdc601234data.lent:cdc301234i=1j=1data.lenS:cddcdc601234data.lent:cdc301234i=2j=2当i=2, j=2时，匹配不成功。此时，ii - j+1 , j0 即即 i=1, j=0data.lenS:cddcdc6012
25、34data.lent:cdc301234i=1j=0当i=2, j=2时，匹配不成功。此时，ii - j+1 , j0 即即 i=1, j=0当i=1, j=0时，匹配不成功。此时，ii - j+1 , j0 即即 i=2, j=0data.lenS:cddcdc601234data.lent:cdc301234i=2j=0当i=2, j=0时，匹配不成功。此时，ii - j+1 , j0 即即 i=3, j=0data.lenS:cddcdc601234data.lent:cdc301234i=3j=0当i=3, j=0时，对应字符相等，ii +1 , jj+1 即即 i=4, j=1da
26、ta.lenS:cddcdc601234data.lent:cdc301234i=4j=1当i=4, j=1时，对应字符相等， ii +1 , jj+1 即即 i=5, j=2data.lenS:cddcdc601234data.lent:cdc301234i=5j=2当i=5, j=2时，对应字符相等， ii +1 , jj+1 即即 i=6, j=3data.lenS:cddcdc601234data.lent:cdc301234i=6j=3当i=6, j=3时，匹配成功，匹配成功，此时，此时，j=t.len, i - t.len 就是匹配的起始位置就是匹配的起始位置int index(S
27、qString s, SqString t) int i=0,j=0,k; while (is.len & j=t.length) k=i-t.length; /*返回匹配的第一个字符的下标返回匹配的第一个字符的下标*/ else k= -1; /*模式匹配不成功模式匹配不成功*/ return k; 这个算法简单这个算法简单,易于理解易于理解,但效率不高但效率不高,主要原因主要原因是是:主串指针主串指针i在若干个字符序列比较相等后在若干个字符序列比较相等后,若有一若有一个字符比较不相等个字符比较不相等,仍需回溯仍需回溯(即即i=i-j+1)。该算法。该算法在最好情况下的时间复杂度为在最好情况
28、下的时间复杂度为O(m),即主串的前即主串的前m个字符正好等于模式串的个字符正好等于模式串的m个字符。个字符。在最坏情况下的在最坏情况下的时间复杂度为时间复杂度为O(n*m)。 最坏情况：最坏情况： O(m*n)O(m*n)例：检查模式串：例：检查模式串：“0000000100000001”是否在以下主串中：是否在以下主串中：匹配过程中，指针回溯次数匹配过程中，指针回溯次数n-m+1, 每次需比较每次需比较m次次“00000000000000000000000000000000000000000000000000000000000001” 4.3.2 KMP 4.3.2 KMP算法算法 KMP
29、算法是算法是D.E.Knuth、J.H.Morris和和V.R.Pratt共同提出的共同提出的,简称简称KMP算法。该算法较算法。该算法较BF算法有较大改进算法有较大改进,主要是消除了主串指针的回溯主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。从而使算法效率有了某种程度的提高。 例例: 主串主串s=“s0s1.si.sn-1” 模式串模式串t=“t0t1. tj.tm-1”设设s=“abababa”,t=“ababc”,第一次匹配过程如下所示。第一次匹配过程如下所示。 此时此时不必不必从从i=1(i=i-j+1=1), j=0重新开始第二次匹配。因重新开始第二次匹配。因t0t1
30、,s1=t1,必有必有s1t0,又因又因t0 =t2,s2=t2,所以必有所以必有s2=t0。 s3=t1。因此。因此,第二次匹配可直接从第二次匹配可直接从i=4, j=2开始。开始。 现在我们讨论一般情况。现在我们讨论一般情况。 设设s=“s0s1sn-1”,t=“t0t1tm-1”,当当sitj (0in-m,0jm)时时, 存在存在: t0t1tj-1=si-jsi-j+1si-1 (4.1)若模式串中存在的若模式串中存在的真子串真子串满足满足: t0t1tk-1=tj-ktj-k+1tj-1 (0kj) (4.2) 由由(4.1)式式说说明明模模式式串串中中的的子子串串t0t1tk-1
31、已已和和主主串串si-ksi-k+1si-1匹匹配配,下下一一次次可可直直接接比比较较si和和tk,若若不不存存在在(4.2)式式,则则结结合合(4.1)式式说说明明在在t0t1tj-1中中不不存存在在任任何何以以t0为为首首字字符符子子串串与与si-j+1si-j+2si-1中以中以si-1为末字符的匹配子串为末字符的匹配子串,下一次可直接比较下一次可直接比较si和和t0。s=“s0s1 si-j. si-j+k-1si-j+ksi-k-1si-ksi-1 sisn-1” | . | | . | | . | | t=t0 tk-1 tk tj-k-1tj-ktj-1 tjtm-1 ijs=“
32、s0s1 si-j.si-j+k-1si-j+ksi-k-1si-ksi-1 sisn-1” | | t=t0 tk-1 tk j=k i不变不变 若若t0 tk-1 = tj-ktj-1 为此为此, 定义定义nextj函数函数如下如下: maxk|0kj,且且“t0t1tk-1”=“tj-ktj-k+1tj-1” 当此集合非空时当此集合非空时 -1 当当j=0时时 0 其他情况其他情况nextj=j0123tjababnextj-1001t=t=“abababab”对应的对应的nextnext数组如下数组如下: 为此为此, 定义定义nextj函数函数如下如下: maxk|0kj,且且“t0t
33、1tk-1”=“tj-ktj-k+1tj-1” 当此集合非空时当此集合非空时 -1 当当j=0时时 0 其他情况其他情况nextj=j01234tjababcnextj-10012t=t=“ababcababc”对应的对应的nextnext数组如下数组如下:j012345tjaaaabanextj-101230t=t=“aaaabaaaaaba”对应的对应的nextnext数组如下数组如下:next0=-1, next1=0,next0=-1, next1=0,当当nextj=knextj=k时，求时，求nextj+1=? nextj+1=? t=“t0 tk-1 tk tj-k-1 tj-k
34、.tj-1 tj. 有有 t0 tk-1 = tj-k.tj-1若若 tk = tj , 则有则有 t0 tk-1 tk = tj-k.tj-1 tjt=“t0 tk-1 tk . tj-k.tj-1 tj tj+1. ”则则 nextj+1=k+1next0=-1, next1=0,next0=-1, next1=0,当当nextj=knextj=k时，求时，求nextj+1=? nextj+1=? t=“t0 tk-1 tk tj-k-1 tj-k.tj-1 tj. 有有 t0 tk-1 = tj-k.tj-1若若 tk tj , 设设 nextj+1 = d已知已知 t0 . tk-1
35、= tj-k.tj-1t= “t0 td-1 . tk-1 . ti-k . tj-d+1.tj-1 tj tj+1. ”则则 t0.td-1=tj-d+1.tj , 有有 t0.td-2=tj-d+1.tj-1 和和td-1=tjt= “t0 td-2 td-1 .tk-1 . ti-k . tj-d+1.tj-1 tj tj+1. ”而而 tj-d+1.tj-1=tk-d+1.tk-1所以，所以，t0.td-2=tk-d+1.tk-1 td-1=tj则则 nextk=d-1 ， td-1=tj 即即 k=nextj , d=nextk+1, 若若td-1=tj ， 则则 nextj+1=d
36、 由模式串由模式串t求出求出next值的算法如下值的算法如下:void GetNext(SqString t, int next ) int j,k; j=0;k= -1; next0=-1; while (jt.length-1) if (k=-1 | | t.chj=t.chk) /*k为为-1或比较的字符相等时或比较的字符相等时*/ j+;k+; nextj=k; else k=nextk; int KMPIndex(SqString s,SqString t) /*KMP算法算法*/ int nextMaxSize,i=0,j=0,v; GetNext(t,next); while (
37、is.length & j=t.length) v=i-t.length; /返回匹配模式串的首字符下标返回匹配模式串的首字符下标 else v=-1; /*返回不匹配标志返回不匹配标志*/ return v; 设设主主串串s的的长长度度为为n,子子串串t长长度度为为m,在在KMP算算法法中中求求next数数组组的的时时间间复复杂杂度度为为O(m),在在后后面面的的匹匹配配中中因因主主串串s的的下下标标不不减减即即不不回回溯溯,比比较较次次数数可可记记为为n,所以所以KMP算法总的时间复杂度为算法总的时间复杂度为O(n+m)。 例如例如,设目标串设目标串s=“aaabaaaab”,模式串模式串
38、t=“aaaab”。s的长度为的长度为n(n=9),t的长度为的长度为m(m=5)。用指针。用指针i指示目标串指示目标串s的当前比较字符的当前比较字符位置位置,用指针用指针j指示模式串指示模式串t的当前比较字符位置。的当前比较字符位置。KMP模式匹配过程如下所示。模式匹配过程如下所示。j01234tjaaaabnextj-10123j01234tjaaaabnextj-10123j01234tjaaaabnextj-10123j01234tjaaaabnextj-10123j01234tjaaaabnextj-10123 上述定义的上述定义的next在某些情况下尚有缺陷。例在某些情况下尚有缺陷
39、。例如如,模式模式“aaaab”在和主串在和主串“aaabaaaab”匹配时匹配时,当当i=3, j=3时时, s.ch3t.ch3,由由nextj的指的指示还需进行示还需进行i=3、j=2,i=3、j=1,i=3、j=0等三等三次比较。实际上次比较。实际上,因为因为模式中的模式中的第第1、2、3个字符和个字符和第第4个字符都相等个字符都相等,因此因此,不需要再和主串中第不需要再和主串中第4个字符个字符相比较相比较,而可以而可以将模式一次向右滑动将模式一次向右滑动4个字符的位置个字符的位置直直接进行接进行i=4,j=0时的字符比较。时的字符比较。 这就是说这就是说,若按上述定义得到若按上述定义
40、得到nextj=k,而模式中而模式中pj=pk,则为主串中字符则为主串中字符si和和pj比较不等比较不等时时,不需要再和不需要再和pk进行比较进行比较,而直接和而直接和pnextk进进行比较行比较,换句话说换句话说,此时的此时的nextj应和应和nextk相同相同。为此将。为此将nextj修正为修正为nextvalj。 j01234tjaaaabnextj-10123nextvalj-1-1-1-13由模式串由模式串t求出求出nextval值值:void GetNextval(SqString t,int nextval) int j=0,k=-1; nextval0=-1; while (j
41、t.length) if (k= -1 | t.chj=t.chk) j+;k+; if (t.chj!=t.chk) nextvalj=k; else nextvalj=nextvalk; else k=nextvalk; 本章小结本章小结 本章基本学习要点如下本章基本学习要点如下: (1)理解串和一般线性表之间的差异。理解串和一般线性表之间的差异。 (2)重重点点掌掌握握在在顺顺序序串串上上和和链链串串上上实实现现串串的的基基本运算算法。本运算算法。 (3)掌握串的模式匹配算法。掌握串的模式匹配算法。 (4)灵灵活活运运用用串串这这种种数数据据结结构构解解决决一一些些综综合合应应用问题。用问题。练习题练习题 教材中教材中p111的习题的习题2和和3。上机实验题上机实验题 教材中教材中p112的实验题的实验题4。
