第四章 串教案(7页).doc

《第四章 串教案(7页).doc》由会员分享，可在线阅读，更多相关《第四章 串教案(7页).doc（7页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、-第四章 串教案本章主要讲授内容 1、串的定义和基本操作 2、串的顺序存储结构 3、串的链式存储结构 4、模式匹配算法及其改进算法 课时分配：1、2，两个学时，3两个学时, 4 四个学时，上机6个学时 重点、难点：模式匹配及其算法第一节串的定义和基本运算串是字符串的简称。它是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符，所以，人们经常又这样定义串：串是一个有穷字符序列。 串一般记作：s= a1a2.an (n30)其中，s是串的名称，用双引号（）括起来的字符序列是串的值；ai可以是字母、数字或其他字符；串中字符的数目n被称作串的长度。当n=0时，串中没

2、有任何字符，其串的长度为0，通常被称为空串。s1= s2= s1中没有字符，是一个空串；而s2中有两个空格字符，它的长度等于2，它是由空格字符组成的串，一般称此为空格串。概念：子串、主串：串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。例如，有下列四个串a，b，c，d：a= Welcome to Beijingb= Welcomec= Beid= welcometo子串的位置：子串在主串中第一次出现的第一个字符的位置。两个串相等：两个串的长度相等，并且各个对应的字符也都相同。例如，有下列四个串a，b，c，d：a= programb= Programc= pro

3、d= program 串的基本操作：（1） 创建串 StringAssign (s,string_constant)（2）判断串是否为空 StringEmpty(s) （3）计算串长度 Length(s) （4）串连接 Concat(s1,s2) （5）求子串 SubStr(s1,s2start,len)（6）串的定位 Index(s1,s2)例如1：将s2串插入到串s1的第i个字符后面。SubStr(s3,s1,1,i);SubStr(s4,s1,i+1,Length(s1)-i);Concat(s3,s2);Concat(s3,s4);StringAssign (s1,s3); 例如2：删

4、除串s中第i个字符开始的连续j个字符。SubStr(s1,s,1,i-1);SubStr(s2,s,i+j,Length(s)-i-j+1);Concat(s1,s2);StringAssign(s,s1); 第二节串的存储结构21顺序存储结构串的顺序存储结构与线性表的顺序存储类似，用一组连续的存储单元依次存储串中的字符序列。在C语言中，有两种实现方式：第一种是事先定义字符串的最大长度，字符串存储在一个定长的存储区中。类型定义如下所示：#define MAX_STRING 255/0号单元存放串的长度，字符从1号单元开始存放type unsigned char StringMAX_STRING

5、; 第二种是在程序执行过程中，利用标准函数malloc和free动态地分配或释放存储字符串的存储单元，并以一个特殊的字符作为字符串的结束标志，它的好处在于：可以根据具体情况，灵活地申请适当数目的存储空间，从而提高存储资源的利用率。类型定义如下所示： typedef structchar *str; int length;STRING;不同的定义形式，算法中的处理也略有不同。下面我们将给出在第二种顺序存储方式下串的几个基本操作的算法。（1） 串的赋值 int StringAssign(STRING*s,char *string_constant)if (s-str) free(s-str); /

6、若s已经存在，将它占据的空间释放掉for (len=0,ch=string_constant;ch;len+,ch+); /求string_constant串的长度if (!len) s-str=(char*)malloc(sizeof(char);s-str0=0; s-length=0; /空串else s-str=(char*)malloc(len+1)*sizeof(char); /分配空间if (!s-str) return ERROR;s-str0.len=string_constant0.len; /对应的字符赋值s-length=len; /赋予字符串长度return OK;

7、（2）判断串是否为空 int StringEmpty(STRING s)if (!s.length) return TRUE;else return FALSE;（3）求串的长度 int Length(STRING s)return s.length;（4）串连接 int Concat(STRING *s1,STRING s2)STRING s; StringAssign(&s,s1-str); /将s1原来的内容保留在s中len=Length(s1)+Length(s2); /计算s1和s2的长度之和free(s1-str); /释放s1原来占据的空间s1-str=(char*)malloc

8、(len+1)*sizeof(char); /重新为s1分配空间if (!s1) return ERROR;else /连接两个串的内容s1-str0.Length(s)-1=s.str0.Length(s)-1); s1-strLength(s).len+1=s2.str0.Length(s2);s1-length=len;free(s-str); /释放为临时串s分配的空间return OK;（5）求子串 int SubStr(STRING *s1,STRING s2,int start,int len)len2=Length(s2); /计算s2的长度if (startlen2|len2

9、len2-start+1) /判断start和len的合理性s1-str=(char*)malloc(sizoef(char);s1-str0=0;s1-length=0;return ERROR;s1-str=(char*)malloc(len+1)*sizeof(char);if (!s1.str) return ERROR;s1-str0.len-1=s2.strstart-1.start+len -2;s1-strlen=0;s1-length=len;return OK;（6）串的定位int Index(STRING s1,STRING s2)len1=Length(s1); len

10、2=Length(s2); /计算s1和s2的长度i=0; j=0; /设置两个扫描指针while (ilen1&jlen2) if (s1.stri=s2.strj) i+; j+; else i=i-j+1; j=0; /对应字符不相等时，重新比较if (j=len2) return i-len2+1;else return 0; 由于串中的字符个数不一定是每个结点存放字符个数的整倍数，所以，需要在最后一个结点的空缺位置上填充特殊的字符。这种存储形式优点是存储密度高于结点大小为1 的存储形式；不足之处是做插入、删除字符的操作时，可能会引起结点之间字符的移动，算法实现起来比较复杂。第三节串的

11、模式匹配算法子串定位运算又称为模式匹配(Pattern Matching)或串匹配(String Matching)，此运算的应用在非常广泛。例如，在文本编辑程序中，我们经常要查找某一特定单词在文本中出现的位置。显然，解此问题的有效算法能极大地提高文本编辑程序的响应性能。在串匹配中，一般将主串称为目标串，子串称之为模式串。设S为目标串，T为模式串，且不妨设：S=s0s1s2sn-1 T=t0t1tm-1 串的匹配实际上是对于合法的位置0in-m依次将目标串中的子串si.i+m-1和模式串t0.m-1进行比较，若si.i+m-1=t0.m-1，则称从位置i开始的匹配成功，亦称模式t在目标s中出现

12、；若si.i+m-1 t0.m-1，则称从位置i开始的匹配失败。上述的位置i又称为位移，当si.i+m-1=t0.m-1时，i称为有效位移；当si.i+m-1 t0.m-1时，i称为无效位移。这样，串匹配问题可简化为是找出某给定模式T在一给定目标T中首次出现的有效位移。串匹配的算法很多，这里我们只讨论一种最简单的称为朴素的串匹配算法。其基本思想是用一个循环来依次检查n-m+1个合法的位移i(0in-m)是否为有效位移，其算法段为：for(i=0;i=n-m;i+)if(Si.i+m-1=T0.m-1return i;下面以第二种定长的顺序串类型作为存储结构，给出具体的串匹配算法（Bf 算法）。

13、int index(sstring s,sstring t,int pos)int i,j,k;int m=s.length;int n=t.length;for(i=0;i=n-m;i+)j=0;k=i;while(jm & s.chk=t.chjk+;j+;if(j=m)return i;)return -1;显然，该算法在最坏情况下的时间复杂度为O(n-m)m)。改进的算法为KMP算法第一步，先把模式T所有可能的失配点j所对应的nextj计算出来；第二步：执行定位函数index_kmp （与BF算法模块非常相似）Int Index_KMP(SString S, SString T, in

14、t pos) i=pos; j=1; while ( i=S0 & jT0) return i-T0; /子串结束，说明匹配成功 else return0;/Index_KMP怎样计算模式T所有可能的失配点 j 所对应的 nextj？例： 模 式 串 T： a b a a b c a c 可能失配位 j： 1 2 3 4 5 6 7 8新匹配位 nextj :next j 0 当j1时nextj=max k |1kj 且T1Tk-1=Tj-(k-1) Tj-1 nextj=1 其他情况上例中：j=1时, next j 0；因为属于“j=1”;j=2时, next j 1；因为属于“其他情况”；

15、j=3时, k=2，只需查看T1=T2； j=4时, k=2，3，要查看T1=T3 和T1T2=T2 T3 j=5时, k=2，3，4，要查看T1=T4 、T1T2=T3T4 和T1T2T3=T2T3T4 以此类推，可得后续nextj值。KMP算法的时间复杂度回顾BF的最恶劣情况：S与T之间存在大量的部分匹配，比较总次数为： (n-m+1)*mO(n*m)而此时KMP的情况是：由于指针i无须回溯，比较次数仅为n,即使加上计算nextj时所用的比较次数m，比较总次数也仅为n+m=O(nm)，大大快于BF算法。注意：由于BF算法在一般情况下的时间复杂度也近似于O(n+m)，所以至今仍被采用。KMP

16、算法的用途：因为主串指针i不必回溯，所以从外存输入文件时可以做到边读入边查找，“流式”作业！作 业1两个串为 s1=bc cad cabcadf，s2=abc，试求两个串的长度，并判断s2串是否是s1串的子串；如果s2是s1的子串，请指出s2在s1中的起始位置。2. 设计一个算法，删去串s中从第i个字符开始的连续j个字符，说明算法所用的存储结构，并估计算法的执行时间。3. 若x和y是两个单链表表示的串，请设计一个算法，找出x中第一个不在y中出现的字符。4. 针对串的两种存储表示各写一算法，判断该字符串是否是回文（即正读与反读相同，如abcba是一个回文，而abc则不是）。5. 采用链接表示的方

17、法，改写快速模式匹配算法和求next数组的算法。并估计其时间代价。 6. 对下列串，求出它们的next数组：(a). ABCDEFGH(b). IIIIIIII(c). BABBABAB7. 对t=ababbaabaa，p=aab进行快速模式匹配，请画出匹配过程的图示。8. Ackerman函数的定义如下：请写出递归算法。9一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为：abcdefghijklmnopqrstuvwxyzngzqtcobmuhelkpdawxfyivrsj则字符串encrypt被加密为tkzwsdf。试写一算法将输入的文本串进行加密后输出；另写一算法，将输入的已加密文本串进行解密后输出 上 机 题1. 设计Bf 算法和KMP算法并上机调试。-第 7 页第四章 串