第5周串第3讲-本周小结数据结构.pdf

1串的存储结构 顺序串 链串 1/9 不一定。不一定。需要根据需要情况而定。需要根据需要情况而定。 如果需要从某个节点出发前后查找，可以采用双链表。如果需要从某个节点出发前后查找，可以采用双链表。 如果需要快速查找尾节点，可以采用循环双链表。如果需要快速查找尾节点，可以采用循环双链表。 2/9 2串的算法设计 借鉴线性表的算法设计方法。借鉴线性表的算法设计方法。 顺序串顺序串 顺序表顺序表 链链 串串 单链表单链表 3/9 BF算法算法 KMP算法算法 为什么为什么KMP算法平均性能更高？算法平均性能更高？ 是不是任何情况下是不是任何情况下KMP算法都好于算法都好于BF算法？算法？ 4/9 假设串采用顺序结构存储。设计一个算法求串假设串采用顺序结构存储。设计一个算法求串 s中出现的第一个最长重复子串的下标和长度。中出现的第一个最长重复子串的下标和长度。 a a b a b c a b c d i 解：解：（i，len）记录当前重复子串，（）记录当前重复子串，（maxi，maxlen）记录第一个最）记录第一个最 长重复子串。长重复子串。 j i=0，len=1 i=1，len=2 i=2，len=1 i=3，len=3 maxi=0，maxlen=0 maxi=0，maxlen=1 maxi=1，maxlen=2 maxi=1，maxlen=2 maxi=3，maxlen=3 maxi=3，maxlen=3，即“，即“abc” 5/9 void maxsubstr(SqString s，SqString i=0; while (i<s.length)/从下标为从下标为i的字符开始的字符开始 j=i+1;/从从i的下一个位置开始找重复子串的下一个位置开始找重复子串 算法如下：算法如下： 6/9 while (jmaxlen)/将较大长度者赋给将较大长度者赋给maxi与与maxlen maxi=i; maxlen=len; j+=len; else j+; i+; /继续扫描第继续扫描第i字符之后的字符字符之后的字符 7/9 t.length=maxlen;/将最长重复子串赋给将最长重复子串赋给t for (i=0;i<maxlen;i+) t.datai=s.datamaxi+i; 8/9 9/9