《数据结构习题解答》习题5解答

第2章数组 5-1字符串的替换操作 replace( String&s, String&t, String&v)是指:若t是s的子串,则用串ν替换 串t在串s中的所有出现:若t不是s的子串,则串s不变。例如,若串s为“ aabbabcbaabaaacbab”,串 t为bab”,串v为"abdc”,则执行 replace操作后,串s中的结果为 aababdccbaabaaacabdc”。试利用字 符串的基本运算实现这个替换操作。 【解答】 String String Replace( String & t String &v)i if(( int id =Find(t)=-1) ∥没有找到,当前字符串不改,返回 i cout include " string. h ∥s是输入字符串,数组A[]中记录字符串中有多少种不同的字符,C[卫中记录每 ∥一种字符的出现次数。这两个数组都应在调用程序中定义。k返回不同字符数。 h(); if( !len)i cout <<"The string is empty. "<<endl; k=0; return else A[0=s[0: C[0=1: k=1; /语句s是串的重载操作 for (i=1; i< len; i++)C[=0; 初始化 for(1=1; i< len; i++)i /检测串中所有字符* whle(j<k&&A=s[)j+;检查s是否已在A[]中* if (j==k)Akk]=s0; C[k]++ k++) /s[从未检测过*

第 2 章 数组 5 5-1 字符串的替换操作 replace (String &s, String &t, String &v)是指：若 t 是 s 的子串，则用串 v 替换 串 t 在串 s 中的所有出现；若 t 不是 s 的子串，则串 s 不变。例如，若串 s 为“aabbabcbaabaaacbab”，串 t 为“bab”，串 v 为“abdc”，则执行 replace 操作后，串 s 中的结果为“aababdccbaabaaacabdc”。试利用字 符串的基本运算实现这个替换操作。 【解答】 String & String :: Replace ( String & t, String &v) { if ( ( int id = Find ( t ) ) == -1 ) //没有找到，当前字符串不改，返回 { cout include "string.h" void frequency( String& s, char& A[ ], int& C[ ], int &k ) { // s 是输入字符串，数组 A[ ]中记录字符串中有多少种不同的字符，C[ ]中记录每 //一种字符的出现次数。这两个数组都应在调用程序中定义。k 返回不同字符数。 int i, j, len = s.length( ); if ( !len ) { cout << "The string is empty. " << endl; k = 0; return; } else { A[0] = s[0]; C[0] = 1; k = 1; /*语句 s[i]是串的重载操作*/ for ( i = 1; i < len; i++ ) C[i] = 0; /*初始化*/ for ( i = 1; i < len; i++ ) { /*检测串中所有字符*/ j = 0; while ( j < k && A[j] != s[i] ) j++; /*检查 s[i]是否已在 A[ ]中*/ if ( j == k ) { A[k] = s[i]; C[k]++; k++ } /*s[i]从未检测过*/

第2章数组 else C[l++ /s[已经检测过* 测试数据s=" cast cast sat at a tasal0 测试结果 【另一解答】 const int charnumber =128 /ASCI码字符集的大小*/ void frequency( String& S, int& C[& ∥s是输入字符串,数组C[]中记录每一种字符的出现次数。 for( int 1=0; i0)cout<"("<i<"):Ⅶ"<C<""; 5-3设串s为“aab”,串t为“ ababa”,串r为“ abclaab babcabaacbacba”,试分别计算它们的失效函数 f()的值。 【解答】 fO

第 2 章 数组 6 else C[j]++; /*s[i]已经检测过*/ } } } 测试数据 s = "cast cast sat at a tasa\0" A c a s t b C 2 7 4 5 5 【另一解答】 include include "string.h" const int charnumber = 128; /*ASCII 码字符集的大小*/ void frequency( String& s, int& C[ ] ) { // s 是输入字符串，数组 C[ ]中记录每一种字符的出现次数。 for ( int i = 0; i 0 ) cout << "( " << i << " ) : \t" << C[i] << "\t"; } 5-3 设串 s 为“aaab”，串 t 为“abcabaa”，串 r 为“abcaabbabcabaacbacba”，试分别计算它们的失效函数 f (j)的值。 【解答】 j 0 1 2 3 j 0 1 2 3 4 5 6 s a a a b t a b c a b a a f (j) -1 0 1 -1 f (j) -1 -1 -1 0 1 0 0 测试结果