第4章习题答案

习题4

1.名词解释：串、空串、空格串、子串。

解：串是有限的字符序列，从数据结构角度讲，串属于线性结构。与线性表的不同之处在于串的元素是字符。

空串是不含任何字符的串，其长度为0。

空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。 串中任意连续的若干字符组成的子序列称为该串的子串。

'\"“ababcaabcbcaa”“caab”“bcb”2.已知三个字符串分别为S，S，S。利用串的基本

“caabcbcaacaa”运算得到结果串为S，要求写出得到结果串S3所用的函数及执行算法。

'\"“caabcbcaa”“caa”解：串S可看作由以下两部分组成：和，设这两部分分别叫串s1和s2，

'\"要设法从S、S、S中得到这两部分，然后使用连接操作连接s1和s2得到S。

i=index();//

s1=substr(S,i,length(S)-i+1);//取出串s1

'\"'\"“bcb”“caa”j=index(S,S);//求串S在串S中的起始位置，S串中后是

s2=substr(S,j+3,length(S)-j-2);//形成串s2

\"\"S'\"=concat(s1,s2);

3.已知字符串S1中存放一段英文，写出算法format(S1,S2,S3,n)，将其按给定的长度n格式化成两端对齐的字符串S2，其多余的字符存入S3。

解：题目要求将字符串S1拆分成字符串S2和S3，要求字符串S2“按给定长度n格式化为两端对齐的字符串”，即长度为n且首尾字符不能为空格字符。算法从左到右扫描字符串S1，找到第一个非空格字符，计数到n，第n个拷入字符串S2的字符不能为空格，然后将余下字符复制到字符串S3中。

void format(char *S1,char *S2,char *S3,int n){ char *p=S1,*q=S2; int i=0;

while(*p!= '\\0'&&*p==' ')p++;//滤掉S1左端空格

if(*p== '\\0'){printf(\"字符串S1为空串或空格串\\n\");exit(0);}

while(*p!= '\\0'&&ip--;//p指针也后退

while(*p!= '\\0'&&*p==' ')p++;//往后查找一个非空格字符作为串S2的尾字符

1

第4章 串

}

q=S3;p++;//将S1串其余部分送字符串S3 while(*p!= '\\0'){*q=*p;q++;p++;} *q= '\\0';//置串S3结束标记 }

4.假设采用定长顺序存储结构表示串，编写算法，求串S的含不同字符的总数和每个字符的个数。 解：typedef struct { char ch; int num;

}mytype;

void StrAnalyze(SString S){//统计串S中字符的种类和个数 int i,j; char c;

mytype T[100]; //用结构数组T存储统计结果 for(i=1;i<=S[0]+1;i++)T[i-1].ch='\\0'; for(i=1;i<=S[0];i++){

c=S[i];j=0;

if(*p== '\\0'){printf(\"串S1没有%d个两端对齐的字符串\\n\*q=*p;//字符串S2最后一个非空字符 *(++q)= '\\0';//S2字符串结束标记

while(T[j].ch&&T[j].ch!=c)j++; //查找当前字符c是否已记录过 if(T[j].ch) T[j].num++; else {T[j].ch=c;T[j].num=1;}

}//for

for(j=0;T[j].ch;j++)

printf(\"%c: %d\\n\

}//StrAnalyze

5.假设采用定长顺序存储结构表示串，编写算法，从串S中删除所有和串T相同的子串。 解：

void SubString_Delete(SString &s,SString t,int &num){//从串s中删除所有与t相同的子串,num为删除次数

int i,j,k;

for(i=1;i<=s[0]-t[0]+1;i++){

for(j=1;j<=t[0]&&s[i+j-1]==t[j];j++);

2

第4章 串

if(j>t[0]){//找到了与t匹配的子串 }

for(k=i;k<=s[0]-t[0];k++)s[k]=s[k+t[0]]; //左移删除 s[0]-=t[0];num++;

}//for

}//Delete_SubString

6.编写算法，实现堆存储结构的串的置换操作Replace(&S,T,V)。 解：

void HString_Replace(HString &S,HString T,HString V,int & num){//堆结构串上的置换操作,返回置换次数

int i,j,k,m;

for(i=0;i<=S.length-T.length;i++){

for(j=i,k=0;kif(T.length==V.length)

for(m=1;m<=T.length;m++) S.ch[i+m-1]=V.ch[m-1]; //新子串长度与原子串相同时:直接替换

else if(T.length=i+T.length;m--)

S.ch[m+V.length-T.length]=S.ch[m];

for(m=0;m}

else{ //新子串长度小于原子串时:先将后部左移 }

S.length+=V.length-T.length; i+=V.length;num++;

for(m=i+V.length;mS.ch[m]=S.ch[m-V.length+T.length];

for(m=0;m}//if

}//for

}//HString_Replace

7.编写算法，实现堆存储结构的串基本操作Concat(&S,S1,S2)。 解：

3

第4章 串

void HString_Concat(HString s1,HString s2,HString &t) {//将堆结构表示的串s1和s2连接为新串t

int i,j;

if(t.ch) free(t.ch);

t.ch=new char[s1.length+s2.length];

for(i=1;i<=s1.length;i++) t.ch[i-1]=s1.ch[i-1]; for(j=1;j<=s2.length;j++,i++) t.ch[i-1]=s2.ch[j-1]; t.length=s1.length+s2.length; }//HString_Concat

8.假设以块链结构表示串，试编写判别给定字符串是否具有对称性的算法，并要求算法的时间复杂度为O(StrLength(S))。

解：

int LString_Palindrome(LString L) {//判断以块链结构存储的串L是否为回文序列,是则返回1,否则返回0

InitStack(S);

p=S.head;i=0;k=1; //i指示元素在块中的下标,k指示元素在整个序列中的序号(从1开始) for(k=1;k<=S.curlen;k++){

if(k<=S.curlen/2) Push(S,p->ch[i]); //将前半段的字符入串 else if(k>(S.curlen+1)/2){

Pop(S,c); //将后半段的字符与栈中的元素相匹配 if(p->ch[i]!=c) return 0; //失配 }

if(++i==CHUNKSIZE) { //转到下一个元素,当为块中最后一个元素时,转到下一块 p=p->next; i=0; } }//for

return 1; //成功匹配 }//LString_Palindrome

“abcabaa”“abcaabbabcabaacbacba”9.令S，T，试分别求出它们的next函数值和nextval函数值。

解：

4

第4章 串

j 串S next[j] nextval[j] 1 2 3 4 5 6 7 a b c a b a a 0 1 1 1 2 3 2 0 1 1 0 1 3 2

j 串T next[j] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 a b c a a b b a b c 0 1 1 1 2 2 3 1 2 3 a 4 0 b 5 5 a 3 3 a 2 2 c 2 2 b 1 1 a 1 0 c 2 2 b 1 1 a 1 0 nextval[j] 0 1 1 0 2 1 3 0 1 1

“adbadabbaabadabbadada”“adabbadada”10.已知主串S，模式串T，写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程。

解：

j 串T nextval[j] 1 2 3 4 5 6 7 8 9 10 a d a b b a d a d 0 1 0 2 1 0 1 0 4 a 0 匹配过程略。

5