串+数组.pptVIP

文本编辑程序中设立页指针、行指针和字符指针分别指向当前操作的页、行和字符。若在某行内插入或删除若干字符，则要修改行表中该行的长度。若该行的长度超出了分配给它的存储空间，则要为该行重新分配存储空间，同时还要修改该行的起始地址。若要插入或删除一行，就要涉及行表的插入或删除。若被删除的行是所在页的起始行，要修改页表中相应页的起始行号为下一行行号。 行、页表按行、页号递增顺序存储，因此插入和删除运算需移动操作位置以后的全部表项。由于访问是以页表和行表作为索引的，所以在做行和页的删除操作时，可以只对行表和页表做相应的修改，不必删除所涉及的字符。 第五章 数组和广义表 * 数据结构 * 模式匹配——KMP算法 为什么BF算法时间性能低？ 在每趟匹配不成功时存在大量回溯，没有利用已经部分匹配的结果。 如何在匹配不成功时主串不回溯？ 主串不回溯，模式就需要向右滑动一段距离。 如何确定模式的滑动距离？ i=3，j=3失败； s2=t2;t1≠t2 ∴t1≠s2 模式匹配——KMP算法 a b a b c a b c a c b a b i j 第 1 趟 a b c a c a b a b c a b c a c b a b 第 2 趟 a b c a c i=3，j=3失败； s2=t2;t1≠t2 ∴t1≠s2 模式匹配——KMP算法 a b a b c a b c a c b a b i j 第 1 趟 a b c a c a b a b c a b c a c b a b a b c a c 第 3 趟 模式匹配——KMP算法 a b a b c a b c a c b a b a b c a c 第 3 趟 i j i=7，j=5失败s4=t2;t1≠t2 ∴t1≠s4 a b a b c a b c a c b a b a b c a c 第 4 趟 模式匹配——KMP算法 a b a b c a b c a c b a b a b c a c 第 3 趟 i j i=7，j=5失败s5=t3;t1≠t3 ∴t1≠s5 a b a b c a b c a c b a b a b c a c 第 5 趟 模式匹配——KMP算法 a b a b c a b c a c b a b a b c a c 第 3 趟 i j i=7，j=5失败s5=t3;t1≠t3 ∴t1≠s5 a b a b c a b c a c b a b a b c a c 第 6 趟 匹配成功 需要讨论两个问题： ①如何由当前部分匹配结果确定模式向右滑动的新比较起点k？ ②模式应该向右滑多远才是最高效率的? 结论： i可以不回溯，模式向右滑动到的新比较起点k ，并且k 仅与模式串T有关！ 模式匹配——KMP算法 请抓住部分匹配时的两个特征： （1）设模式滑动到第k个字符，则T1～Tk-1 ＝Si-(k-1) ～ Si-1 S=a b a b c a b c a c b a b T=a b c a c i k j S=a b a b c a b c a c b a b T=a b c a c i k 模式匹配——KMP算法 请抓住部分匹配时的两个特征： 两式联立可得：T1～Tk-1＝Tj-(k-1) ～Tj-1 （2）则Tj-(k-1) ～ Tj-1 ＝Si-(k-1) ～ Si-1 S=a b a b c a b c a c b a b T=a b c a c i k j i S=a b a b c a b c a c b a b T=a b c a c j k 模式匹配——KMP算法 （1）设模式滑动到第k个字符，则T1～Tk-1 ＝Si-(k-1) ～ Si-1 T1…Tk-1＝Tj-(k-1) …Tj-1说明了什么？ （1） k 与 j 具有函数关系，由当前失配位置 j ，可以计算出滑动位置 k（即比较的新起