数据结构课件习题4

题4.25,题4.28,题4.30,题4.12,题4.29,题4.20,题4.13,S 串,T 串,V 串,V 串,pos,pos,sub,i,news 串,sub,题4.12,利用已知串的五种基本操作实现串的置换操作。,StringType Replace (StringType S, StringType T, StringType V ) / T为非空串。若主串S中存在与 T相等的子串，则均以串V替换之。 / 本算法返回被置换后的新串。 n = StrLength(S); m = StrLength(T); i = pos = 1; StrAssign(news, ); while ( i = n-m+1) SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ; else / while S中不再存在与T相等的子串 / Replace, , ,news = Concat(news, SubString(S, pos, i-pos); news = Concat(news, V); i = pos = i + m; / pos指示查询的起始位置; i指示子串的起始位置,news = Concat(news, SubString(S, pos, n-pos+1); return news;,/ else,/ 结尾处理,从串S中删除所有和串T相同的子串。,此题的操作等同于“以空串置换串S中所有和串T相同的子串。”,显然，算法的目标是构造如上所画的一个新串。,题4.13,StringType Delete (StringType S, StringType T) / T为非空串。若主串S中存在与 T相等的子串，则删除之。 / 本算法返回被删后的 S串。 n = StrLength(S); m = StrLength(T); i = pos = 1; StrAssign(news, ); while ( i = n-m+1) SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ; else / while S中不再存在与T相等的子串 / Delete, , ,news = Concat(news, SubString(S, pos, i-pos); i = pos = i + m;,news = Concat(news, SubString(S, pos, n-pos+1); return news;,/ else,/ 结尾处理,从串 S 中删除所有和串 T 相同的子串。,此题的基本思想和题 4.13 相同，所不同的是要求在在串的定长存储表示中实现。,算法的目标是构造如上所画的一个新串。,题4.20,pos,k,算法的基本思想为：,SS0+1S0+k-pos = Spos k-1,删除之前的 S 串,删除之后的 S 串,具体写算法时，上述串的赋值是对单个字符进行的，因为在查询过程中，一旦指针 i“回退”，则说明上一次搜索的起始位置的字符肯定不会被删除。详细算法见下页。,void del_sub(SString S, SString T) k=0; i=1; / k指示新串的当前长度，i指示S串中当前匹配的字符 while (i T0) /重新开始一轮匹配，并保存“前一字符” i:=i-j+2; S+k:=Si-1; / while while (i = S0 ) +k; Skk+S0-i+1:=SiS0; / 保存剩余串 S0 = k+S0-i+1; ,题4.25,解此题的基本思想和题4.12相同，但需要在串的堆存储结构中实现。,由于堆存储结构是按串的实际长度分配空间，则首先需知道置换之后的串的长度。 因此解此题的基本步骤为: 1) 找出所有和 T串相同的子串，并记下它们的起始位置; 2) 计算置换之后的 S 串的长度; 3) 为置换后的串分配空间并逐段复制求得新的 S 串;,void repl(HString / if / repl,void repl(HString /while if ( Y.length != 0 ) ,n = S.length; S.length += Y.length*(T.length-V.length); ns.ch = new charS.length+1; k=1; i=0; spos=0; while(kY.length) tpos=Y.elemk-1; len=tpos-spos; ns.chii+len = S.chspostpos; i+=len+1; ns.chii+V.length-1 = V.ch0V.length-1; spos = Y.elemk+T.length; i+=V.length; k+; ns.chiS.length-1 = S.chsposn-1; S.ch = ns.ch;,T,V,spos,tpos,i,i+len,tpos=Y.elemk-1; len=tpos-spos;,i+=len+1;,spos = Y.elemk+T.length; i+=V.length;,i,spos,i,void get_next(Lstring T) p = T.head; q = NULL; p-next = NULL; while (p) if ( !q | p-ch = q-ch ) p = p-succ; if (!q) q = T.head; else q = q-succ; if ( p-ch = q-ch ) p-next = q-next; else p-next = q; else q = q-next; ,题4.28,Link index_L(Lstring S, Lstring T) p = S.head; q = T.head; while ( p else , / 回退找起始位置,题4.29,p = p-next; q = T.head; while ( q-succ ) p = p-next; q = q-succ; return p;,求串S中出现的第一个最长重复子串及其位置。,所谓“重复子串”指的是， SubString(S, i, len) = SubString(S, j, len) 1 ij StrLength(S)， 1 len StrLength(S)-j+1,例如: S=aaaaaaa的最长重复子串为 T=aaaaaa,题4.30,一种比较直观的做法是: 在串 S 中取子串 SubString( S, i, len ) 和子串 SubString( S, i+1, StrLength(S)-i ) 相匹配。 假设 S 串的长度为 n, 则 len 的变化范围是从 n-1 到 1 , i 的变化范围是从 1 到 n - len 最坏情况下的时间复杂度为 O(n3)。,分析:,此题可有多种解法。,另一种作法是，利用 next 函数的特性， 可以使算法的时间复杂度减为 O(n2)。,因为 nextj0 表明: 在第 j 个字符之前存在一个长度为 nextj-1 的重复子串。,由此，算法的基本思想为:求各子串 pati=SubString(S,i,StrLength(S)-i+1) 的next 函数值，i=1, 2, , StrLength(S)- 1 并从中求最大值,例如: S=abaabaaabaaaab,Pat1= abaabaaabaaaab next值 0 1 1 22 3 4 52 3 4 5 2 2,Pat2= baabaaabaaaab next值 0 1 1 12 3 4 12 3 4 1 1,Pat3= aabaaabaaaab next值 0 1 2 12 3 3 45 6 7 3,Pat4= abaaabaaaab next值 0 1 1 22 2 3 4 56 2,i=1; maxl=0; n=S0;,while(n-i+1maxl) maxk=MaxNext(SubString(S, i ,n-i+1);,if (maxk!=nextn | Sn!=Si+maxk-1) maxk-;,if (maxkmaxl) maxl=maxk; spos=i; ,i+; ,算法的基本思想为: 求 pati = SubString( S, i, n-i+1 ) i=1,2,n-1 的