数据结构课后习题及解析

1、第四章习题 1. 设 s=l AM A STUDENT, t= GOO q= WORKER 给出下列操作的结果： StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1); Strlndex(s, A,4); StrReplace(s, STUDENT,q); StrCat(StrCat(sub1,t), StrCat(sub2,q); 2. 编写算法，实现串的基本操作 StrReplace(S,T,V) 。 3. 假设以块链结构表示串，块的大小为 1，且附设头结点。 试编写算法，实现串的下列基本操作： StrAsign(S,char

2、s) ； StrCopy(S,T) ； StrCompare(S,T) ； StrLength(S) ； StrCat(S,T) ； SubString(Sub,S,pos,len) 。 4 叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变 量的值。 5. 已知：S=”(xyz)* ” ,T= ”(x+z)*y ”。试利用联接、求子串和置换等操作，将 S转换为T. 6. S和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次不T匹配的子串逆置。 7. S是用结点大小为4的单链表存储的串，分别编写算法在第k个字符后插入串T,及从第k个字符 删除

3、len 个字符。 以下算法用定长顺序串： 8. 编写下列算法： (1) 将顺序串r中所有值为ch1的字符换成ch2的字符。 (2) 将顺序串 r 中所有字符按照相反的次序仍存放在 r 中。 (3) 从顺序串r中删除其值等于ch的所有字符。 (4) 从顺序串 r1 中第 index 个字符起求出首次不串 r2 相同的子串的起始位置。 (5) 从顺序串 r 中删除所有不串 r1 相同的子串。 9. 写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换 10 写算法，实现顺序串的基本操作 StrCompare（s,t） 11 写算法，实现顺序串的基本操作 StrReplace（&a

4、mp;s,t,v） 实习题 1. 已知串S和T,试以以下两种方式编写算法，求得所有包含在 S中而丌包含在T中的字符构成的 新串R,以及新串R中每个字符在串S中第一次出现的位置。 （1） 利用CONCATLEN SUB和EQUA四种基本运算来实现。 （ 2） 以顺序串作为存储结构来实现。 2. 编写一个行编辑程序EDLINE完成以下功能： （1） 显示若干行：list n 1-n2:显示第n1行到第n2行，n1缺省时，从第一行开始, n2 缺省时，到最后一行， （2） 删除若干行。 del n1-n2 ： n1 、 n2 说明同（ 1）。 （3） 编辑第 n 行。 edit n ：显示第 n 行

5、的内容，另输入一行替换该行。 （ 4） 插入一行。 ins n ：在第 n 行之前插入一行。 （ 5） 字符替换。 replace str1,str2, n1-n2 ：在 n1 到 n2 行之间用 str2 替换 str1 3. 设计一个文学研究辅助程序，统计小说中特定单词出现的频率和位置。 第四章答案 4.1 设 s= I AM A STUDENT t= GOOD q= WORKER。给出下列操作的结果: 【解答】 StrLength(s)=14; SubString(sub1,s,1,7) sub1= I AM A ; SubString(sub2,s,7,1) sub2= ; StrIn

6、dex(s,4, A )=6; StrReplace(s, STUDENT ,q); s= I AM A WORKER;StrCat(StrCat(sub1,t),StrCat(sub2,q) sub1=I AM A GOOD WORKER 。 4.2 编写算法，实现串的基本操作 StrReplace(S,T,V) 【解答】算法如下： int strReplace(SString S,SString T, SString V) /*用串 V 替换 S 中的所有子串 T */ int pos,i; pos=strIndex(S,1,T); /* 求 S 中子串 T 第一次出现的位置 */ if(

7、pos = = 0) return(0); while(pos!=0) /*用串 V 替换 S 中的所有子串 T */ switch(T.len-V.len) case 0: for(i=0;ichpos+i=V.chi; case 0: /*将 S 中子串 T 后的所有字符 前移 T.len-V.len 个位置 */ /* 用 V 替换 T*/ /*串 T 的长度小于串 V 的长度*/ if(S-len-T.len+V.len)= MAXLEN /*插入后串长小于 MAXLEN*/ /*将 S 中子串 T 后的所有字符后移 V.len-T.len 个位置*/ /*串 T 的长度等于串 V 的

8、长度 */ /* 用 V 替换 T*/ /*串 T 的长度大于串 V 的长度*/ for(i=pos+t.ien;ilen;i-) S-chi-t.len+v.len=S-chi; for(i=0;ichpos+i=V.chi; S-len=S-len-T.len+V.len; case len-T.len+V.len;i=pos+T.len;i-) S-chi=S-chi-T.len+V.len; for(i=0;ichpos+i=V.chi; S-len=S-len-T.len+V.len; else /* 替换后串长 MAXLEN, 但串 V 可以全部替换 */ if(pos+V.len

9、=pos+T.len; i-) S-chi=s-chi-T.len+V.len for(i=0;ichpos+i=V.chi; S-len=MAXLEN; else /* 串 V 的部分字符要舍弃 */ for(i=0;ichi+pos=V.chi; S-len=MAXLEN; /*switch()*/ pos=StrIndex(S,pos+V.len,T); /* 求 S 中下一个子串 T 的位置 */ /*while()*/ return(1); /*StrReplace()*/ 附加题：用链式结构实现定位函数。 解答】typedef struct Node char data; stru

10、ct Node *next; Node,*Lstring; int strIndex(Lstring S, int pos, Lstring T) /*从串 S 的 pos 序号起，串 T 第一次出现的位置 */ Node *p, *q, *Ppos; int i=0 ， ,j=0; if(T-next= =NULL | S-next = =NULL) return(0); p=S-next; q=T-next; while(p!=NULL & jnext; j+; if(j!=pos) return(0); while(p!=NULL & q!=NULL) Ppos=p; /

11、*Ppos 指向当前匹配的起始字符 */ if(p-data = = q-data) p=p-next; q=q-next; else /* 从 Ppos 指向字符的下一个字符起从新匹配 */ p=Ppos-next; q=T-head-next; i+; if(q= =NULL) return(pos+i); /* 匹配成功 */ else return(0); /*失败 */ 第 4 章 串 习题 1. 设 s= I AM A STUDENT , t=GOOD , q=WORKER 。给出下列操作的结果： StrLength(s); SubString(sub1,s,1,7); SubSt

12、ring(sub2,s,7,1); StrIndex( s, A,4)S;trReplace( s, STUDENT ,q); StrCat(StrCat(sub1,t), StrCat(sub2,q); 参考答案 StrLength(s)= 14; sub1= I AM A_; sub2= _; StrIndex (s, A,64;)= StrReplace( s, STUDENT ,q)= I AM A WORKER; StrCat(StrCat(sub1,t), StrCat(sub2,q)= I AM A GOOD WORKER ; 2. 编写算法，实现串的基本操作 StrReplac

13、e(S,T,V) 。 3. 假设以块链结构表示串，块的大小为 1，且附设头结点 试编写算法，实现串的下列基本操作： StrAsign(S,chars) ； StrCopy(S,T) ； StrCompare(S,T) ； StrLength(S) ； StrCat(S,T) ； SubString(Sub,S,pos,len) 。 说明：用单链表实现。 4 叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串； 串变量的名字和串变量的值。 5 已知： S=”(xyz)* ”,T= ”(x+z)*y ”。试利用联接、求子串和置换等操作，将 S 转换为 T. 6 S 和 T 是用结点大

14、小为 1 的单链表存储的两个串， 设计一个算法将串 S 中首 次不 T 匹配的子串逆置。 7 S 是用结点大小为 4 的单链表存储的串 ,分别编写算法在第 k 个字符后插入串 T,及从第k 个字符删除 len 个字符。 以下算法用定长顺序串： 8 写下列算法： ( 1) 将顺序串 r 中所有值为 ch1 的字符换成 ch2 的字符。 ( 2) 将顺序串 r 中所有字符按照相反的次序仍存放在 r 中。 ( 3) 从顺序串 r 中删除其值等于 ch 的所有字符。 4) 从顺序串 r1 中第 index 个字符起求出首次不串 r2 相同的子串的起始位置 5） 从顺序串 r 中删除所有不串 r1 相同的子串。 9 写一个函数将顺序串 s1 中的第 i