数据结构课后习题与解析.docx

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

2、ign(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 ”。试利用联接、求子串和置换等操作，SI转换为T.6 S 和 T 是用结点大小为 1 的单链表存储的两个串， 设计一个算法将串 S 中首次与 T 匹配的子串逆 置。7 . S是用结点大小为4的单链表存储的串，分别编写算法在第k个字符后

3、插入串T,及从第k个字符 删除 len 个字符。以下算法用定长顺序串：（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 写算法，实现顺序串的基本

4、操作 StrReplace（&s,t,v） 。实习题1 已知串S和T,试以以下两种方式编写算法，求得所有包含在 S中而不包含在T中的字符构成 的新串R,以及新串R中每个字符在串S中第一次出现的位置。（1 ） 利用 CONCAT 、LEN 、SUB 和 EQUAL 四种基本运算来实现。（2） 以顺序串作为存储结构来实现。2 编写一个行编辑程序 EDLINE ，完成以下功能：n2 缺省时，到最后一行，（2） 删除若干行。 del n1-n2 ： n1、n2 说明同（ 1）。（3） 编辑第n行。edit n ：显示第n行的内容，另输入一行替换该行。（ 4 ） 插入一行。 ins n ：在第 n 行之

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

6、q);StrCat(StrCat(sub1,t),StrCat(sub2,q) sub1= I AM A GOOD WORKER4.2 编写算法，实现串的基本操作 StrReplace(S,T,V)答】算法如下：int strReplace(SString S,SString T, SString V)/* 用串 V 替换 S 中的所有子串 T */int pos,i;pos=strIndex(S,1,T);if(pos = = 0) return(0); while(pos!=0) switch(T.len-V.len)case 0:for(i=0;ichpos+i=V.chi; case

7、0:/* 求 S 中子串 T 第一次出现的位置 */* 用串 V 替换 S 中的所有子串 T */* 串 T 的长度等于串 V 的长度 */* 用 V 替换 T*/* 串 T 的长度大于串 V 的长度 */for(i=pos+t.ien;ilen;i-)/*将S中子串T后的所有字符S-chi-t.len+v.len=S-chi;前移 T.len-V.len 个位置 */for(i=0;ichpos+i=V.chi;S-len=S-len-T.len+V.len;case len-T.len+V.len)len-T.len+V.len;i=pos+T.len;i-) S-chi=S-chi-T.

8、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=pos+T.len; i-)S-chi=s-chi-T.len+V.lenS-chpos+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 的位置 */*wh

9、ile()*/return(1);/*StrReplace()*/附加题：用链式结构实现定位函数。【解答】typedef struct Node char data;struct 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

10、 & jnext; j+;if(j!=pos) return(0);while(p!=NULL & q!=NULL)Ppos=p;/*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

11、 。给出下列操作 的结果：StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1);StrIndex( s, A ,4); StrReplace( s, STUDENT ,q );StrCat(StrCat(sub1,t), StrCat(sub2,q);参考答案 StrLength(s)= 14; sub1= I AMA_; sub2= _; StrIndex (s, A ,4)6=;StrReplace( s, STUDENT ,q )= I AM A WORKER ;StrCat(StrCat(sub1,t), StrCat(s

12、ub2,q)= I AM A GOOD WORKER ;2.编写算法，实现串的基本操作 StrReplace(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)

13、*y ”。试利用联接、求子串和置换等操作，将 S 转换为 T.6 S 和 T 是用结点大小为 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 个字符到第 j 个字符之间的字符用 s2 串替 换。提示 ：（1）用静态顺序串 （2）先移位，后复制10 写算法，实现顺序串的基本操作 StrCompare（s,t） 。11 写算法，实现顺序串的基本操作 StrReplace（&s,t,v） 。提示：2) 被替换子串 后面的字符 左移或右移 (为替换子串 准备房间)3) 替换子串 入住(复制)(4) 重复上述，直到