2014/47 §4.2串的存储结构 串是特殊线性表，节点是单个字符，故有特殊技巧 §4.2串的存储结构 1静态存佛分配的原序审 2动态存储分配的顺序串 直接用定长字符向量来表示，上界预先给定 用C的nalloci和ree动态申请和释放向量空间，有两 #define MaxStrSize256/用户定义 种形式： Typedef char SeqString[MaxStrSizel: ①typedef char*string;C中串库相当于使用此类 SeqString S:S是可客纳255个字符的顺序率 /似定义 ◆终结符：心是串终结符，放在串值尾部 ②ypedef struct{ ◆率长具性：若不设终结符 char*ch;若串非空，则按率实际长度分配，否则为NULL typedef struct{ char chMaxStrSize:/可容纳256字符 int length; int length; Hstring SeqString §4.2串的存储结构 S4.3串的模式匹配算法（串定位运算） 3.链串 1.朴素的定位算法（串匹配） 块链存储 主串：目标串（正文串Target,Text) 子串：模式（串）（子串，Pattern) ◆结点大小 大小为1：s乙a□g囚 设T=“t6l1tn” P=“pp1p”(0m匹n)通常m<Kn 大小为3：8乙abc日e0四 应用：文本编辑，基因匹配等 女存储密度d d-数据大小结点大小 S4.3串的模式匹配算法 843串的模式匹配算法 ◆思想： 有效位移：若T正.i计m-1=P0m-1小，则称为有效 位移 对合法的位置0≤≤-m(合法位移)，依次将目标 无效位移：若Ti.i计m-1≠P0m-1,则称为无效 串中的子串T正.i+m-1和模式串P0.m-1进行比较 位移 若Tii+m-1=P0.m-lj即：“ttm"=“pwp1pal" ·总结：朴素的串匹配算法是对合法位移检查其是否 为有效位移 则称从位置开始的匹配成功： 有时需在T中找到所有有效位移 否则，存在菜个0≤m-1,使"'≠p',则称从位量i 通常找首次出现的有效位移 开始的匹配失败 22014/4/7 2 §4.2 串的存储结构 串是特殊线性表，节点是单个字符，故有特殊技巧 1. 静态存储分配的顺序串 直接用定长字符向量来表示，上界预先给定 #define MaxStrSize 256 //用户定义 Typedef char SeqString[MaxStrSize]; 是可容纳 个字符的顺序串 7 SeqString S; //S是可容纳255个字符的顺序串  终结符：‘\0’是串终结符，放在串值尾部  串长属性：若不设终结符 typedef struct { char ch[MaxStrSize]; //可容纳256字符 int length; }SeqString §4.2 串的存储结构 2. 动态存储分配的顺序串 用C的malloc和free动态申请和释放向量空间，有两 种形式： ① typedef char *string; //C中串库相当于使用此类 //似定义 8 ② typedef struct { char *ch; //若串非空，则按串实际长度分配，否则为NULL int length； }Hstring §4.2 串的存储结构 3.链串 块链存储 结点大小 大小为1 9 ： 大小为3： 存储密度d d=数据大小/结点大小 §4.3 串的模式匹配算法（串定位运算） 1. 朴素的定位算法（串匹配） 主串：目标串（正文串Target，Text） 子串：模式（串）（子串，Pattern） 设T=“t0t1 …tn-1” 10 0 P=“p0p1 …pm-1” （0≤m≤n） 通常m<<n 应用：文本编辑，基因匹配等 §4.3 串的模式匹配算法 思想： 对合法的位置0≤i≤n-m（合法位移），依次将目标 串中的子串T[i..i+m-1]和模式串P[0..m-1]进行比较 若T[ i i 1] P[0 1] 即 “ 11 若T[ i .. i+m-1]=P[0 .. m-1](即：“ti ti+1…ti+m-1”=“p0p1 …pm-1”) 则称从位置i开始的匹配成功； 否则，存在某个0≤j≤m-1，使‘ti+j’≠‘pj ’，则称从位置i 开始的匹配失败 §4.3 串的模式匹配算法 有效位移：若T[i..i+m-1]=P[0..m-1]，则i称为有效 位移 无效位移：若T[i..i+m-1]≠P[0..m-1]，则i称为无效 位移 总结：朴素的串匹配算法是对合法位移检查其是否 12 为有效位移 有时需在T中找到所有有效位移 通常找首次出现的有效位移