4.2串的表示和实现-块链存储（续） 4.3串的模式匹配算法 存储密度的影响 。求子串位置的定位函数Index(S,T,pos) 存情密康小，运算处理方便，但存情占用量大 模式匹配(T:模式事) 。评价 基于堆分配存情的算法 。存储密度校低 int Index(HString S,HString T,int pos X 。块链使率的操作复杂化 1=p05】=1; while (i<=S.length &&j<=T.length X ,顺序映像的峡点 if s.ch(i]==T.ch[] /壁装比装后装李清 ·空间利用卓低 else ,空间不可扩光，使率的某业操作（联接、置换） 《1=k+2:1=1:》/川指附后通置斯开始匹现 变到限制 if (>T.length)return (i-T.length); ■插入、测除、里换操作带来的移动 else return O; 13/15 回 14/15 圈 4.4串操作应用举例 ▣文本编辑 ·处理规则：行插入/刷除，页插入/删 除， ,数据结构：页表、行表（行号，起始地址，长 度) 。建立词索引表 ·数据结构 ,词表一书名中的关健词集合 。关健词家引表 15/15 回回 33 13/15 4.2 串的表示和实现-块链存储(续) „ 存储密度的影响 存储密度小，运算处理方便，但存储占用量大 „ 评价 „ 存储密度较低 „ 块链使串的操作复杂化 „ 顺序映像的缺点 „ 空间利用率低 „ 空间不可扩充，使串的某些操作（联接、置换） 受到限制 „ 插入、删除、置换操作带来的移动 14/15 4.3 串的模式匹配算法 „ 求子串位置的定位函数 Index(S, T, pos) ——模式匹配(T:模式串) 基于堆分配存储的算法 int Index( HString S, HString T, int pos ){ i = pos; j = 1; while ( i<=S.length && j<=T.length ){ if ( S.ch[i]==T.ch[j] ) { i++; j++; } //继续比较后继字符 else { i = i- j+2; j = 1;} // 指针后退重新开始匹配 } if ( j>T.length) return (i – T.length); else return 0; } 15/15 4.4 串操作应用举例 „ 文本编辑 „ 处理规则：行插入/删除，页插入/删 除，…… „ 数据结构：页表、行表(行号，起始地址，长 度) „ 建立词索引表 „ 数据结构 „ 词表——书名中的关键词集合 „ 关键词索引表