数据结构课件_第七讲(串).ppt

《数据结构课件_第七讲(串).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构大话《数据结构》崔基哲2012年1算法和数据结构算法和数据结构2第一章绪论第二章算法第三章线性表第四章栈和队列第五章串第六章树第七章图第八章查找第九章排序算法和数据结构4串羊肉串一(串)葡萄Lover,friend,Lover也有OverFriend也有endBelieve也有lie第五章：串我画蓝江水悠悠，爱晚亭上枫叶愁。秋月溶溶照佛寺，香烟袅袅绕经楼。我亦当年不出户，为天下惜此人物。秀应本州计入洛，莲沼水从双涧入。5.2串的定义5.3串的比较5.4串的抽象数据类型5.5串的存储结构5.6朴素的模式匹

2、配算法5.7KMP模式匹配算法5.8本章总结：算法和数据结构6串（或称字符串）是由零个或多个字符组成的有穷序列。一般记作：s=＂a0a1a2…an-1＂（n≥0）。用双引号括起来的字符序列是串值，双引号是串标志，串中所含字符个数n称为该串的长度（或串长）。含零个字符的串称为空串，用Φ表示。字符在序列中的序号为该字符在串中的位置。串中任意个连续字符组成的子序列称为该串的子串。包含子串的串相应地被称为主串。C语言中，存储串时，每个字符在内存占用一个字节，并用特殊字符“”标记串结束。注意：空格串与空串是不相同的。空

3、串的长度为0，空格串的长度为串中空格字符的个数。串的定义串的比较ASCII编码128(7位)->特殊字符->256个字符(8位)Unicode编码(中文，韩文，日文等)16位数，约2^16,65万个字符排序问题大小问题串的抽象数据类型5.5串的存储结构1串的顺序存储2串的链式存储串的顺序存储顺序存储实现：在顺序串中，每个字符依次存放在一组连续的存储单元中。串的顺序存储有两种方法：一种是每个存储单元只存一个字符，称为非紧缩格式。第二种，在每个存储单元中存放多个字符，称为紧缩格式。处理字符的速度高，空间利用率低节省存

4、储空间，处理字符速度低顺序串的类型定义描述如下：#definemaxlenmaxsize//maxsize为给定的最大长度structstring{charch[maxlen];//maxlen为数组中存储空间的最大数量intlen;};串的链式存储链串与一般的链表类似，链串中的一个结点可以存储一个或多个字符。链串结点大小的选择将直接影响到串处理的效率。存储密度=串值所占存储容量/实际分配存储容量链串的类型定义如下：typedefstructLnode{chardata;//存放字符structLnode*nex

5、t;}*Linkstring;朴素的模式匹配算法论文查询，索引，关键词崔基哲清华大学的教授哈尔滨工业大学的教授朝鲜军队的上海开公司的/LG电子研究所所长等等…(张三，李四)Brute—Force算法：思想：从目标串s=“s0s1…sn－1”的第一个字符开始和模式串t=“t0t1…tm－1”中的第一个字符比较，若相等，则继续比较后面的字符；否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。依次类推，若存在一个每个字符依次与目标串中的对应字符相等的连续字符序列，则匹配成功，函数返回t中的第一个字符在s

6、中的位置；否则，匹配失败，函数返回0。KMP算法思想：设s为目标串，t为模式串，并设i指针和j指针分别指示目标串和模式串中正待比较的字符，令i和j的初值均为0。若有si=tj，则i和j分别增1；否则，i不变，j退回到j=next[j]的位置（即模式串右滑），比较si和tj，若相等则指针各增1，否则j再退回到下一个j=next[j]的位置（即模式串继续右滑），再比较si和tj。依次类推，直到下列两种情况之一：第一种情况是j退回到某个j=next[j]时有si=tj，则指针各增1后继续匹配；另一种情况是j退回到j=-

7、1时，此时令指针各增1，即下一次比较si+1和t0。基本操作在顺序结构上的实现操作一：strcopy（s，t）操作二：strequal（s，t）操作三：strlength（s）操作四：strconcat（s，t）操作五：strsub（s，i，j）操作六：strdelsub（s，i，j）操作七：strins（s1，i，s2）操作八：strrep（s，i，j，t）操作一：strcopy（s，t）串拷贝分析：将t所指串中的内容拷贝到s串中。实现算法：voidstrcopy(string&s,stringt){inti;

8、for(i=0;i