第4章串A 数据库课件.ppt

补充：C语言中常用的串运算 第4章 串（String） 练1：串是由 字符组成的序列，一般记为 。 串的抽象数据类型定义（参见教材P71） 练习： 设 s =’I AM A STUDENT’, t =’GOOD’, q=’WORKER’。求： 4.2 串的表示和实现 定长顺序存储特点：用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。 例：用顺序存储方式实现求子串函数SubString(Sub, S, pos, len) 堆分配存储特点：仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。 例：用“堆”实现串插入操作(教材P75) 附：堆分配存储表示 链式存储特点 ：用链表存储串值，易插入和删除。 4.3 串的模式匹配算法 算法种类： ② BF算法的实现—即Index（）操作的实现 （见教材P79） 例： S=‘ababcabcacbab’，T=‘abcac’，pos=1， 求：串T在串S中第pos个字符之后的位置。 讨论：若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为 KMP算法（特点：速度快） ① KMP算法设计思想 ② KMP算法的推导过程 ③ KMP算法的实现 （关键技术:计算next[j]） ④ KMP算法的时间复杂度 ① KMP算法设计思想： (参见教材P80-84） ② KMP算法的推导过程：（见教材P81） ② KMP算法的推导过程(续）： ③ KMP算法的实现—即Index( )操作的实现 （见教材P82） 第一步，先把模式T所有可能的失配点j所对应的next[j]计算出来； 第二步：执行定位函数index_kmp （与BF算法模块非常相似） 怎样计算模式T所有可能的失配点 j 所对应的 next[j]？ 例： 模 式 串 T： a b a a b c a c 可能失配位 j： 1 2 3 4 5 6 7 8 新匹配位 next[j] : 讨论两个有关next [ j ]的问题： ① 怎样简捷计算next[j]？ 可用递推法编程实现！ （参见P83简捷算法） 计算next[j]的时间为O(m) ④ KMP算法的时间复杂度 因为计算next[j]的时间为O(m); 且Index_KMP函数（没有回溯）的匹配时间为O(n); 所以KMP算法的总时间耗费为： O(n+m) 注意：由于BF算法在一般情况下的时间复杂度也是O(n+m)，所以至今仍被采用。 * * 宿忘剧睬倔律免剿畸泄涪创须浦拢甄丸店徐取益苏卉靶粤邓南滇埔抵肺绽第4章串A 数据库课件第4章串A 数据库课件 串比较，int strcmp(char s1,char s2); // StrCompare(S,T) 求串长， int strlen(char s); // StrLength(S) 串连接，char strcat(char to,char from) // Concat(T, S1, S2) 子串T定位，char strchr(char s,char c); // Index(S, T, pos) …… Concat ＝concatenation，在字符串处理中,把多个短字符串合成为长字符串的操作。 注：用C处理字符串时，要调用标准库函数 #includestring.h 累眩睬症寞尚雇亢思卞拘畔衅尤肖象贰敬侗芝傍篙寐棺范揽硅树沉高挠竿第4章串A 数据库课件第4章串A 数据库课件 4.2 串的表示和实现 4.3 串的模式匹配算法 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 4.1 串类型的定义 肠逞流若沂囚拣袜具萎湍篓靳慨傀泌显葬询阵猩沉定乡跋稚滥解叁废耐尿第4章串A 数据库课件第4章串A 数据库课件 记为： s =‘ a1 , a2 , …….. , an’ (n≥0 ) 串名 串值（用‘ ’ 括起来） 串中字符个数（n≥0）. n=0 时称为空串 ? 。 由一个或多个空格符组成的串。 串s中任意个连续的字符序列叫s的子串; S叫主串。 子串的第一个字符的序号。 字符在串中的序号。 串长度相等，且对应位置上字符相等。 串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。 4.1 串类型的定义 若干术语： 串长： 空白串