數(shù)據(jù)結(jié)構(gòu)課后習題及解析

1、第四章習題 1. 設(shè) s=l AM A STUDENT, t= GOO q= WORKER 給出下列操作的結(jié)果： 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. 編寫算法，實現(xiàn)串的基本操作 StrReplace(S,T,V) 。 3. 假設(shè)以塊鏈結(jié)構(gòu)表示串，塊的大小為 1，且附設(shè)頭結(jié)點。 試編寫算法，實現(xiàn)串的下列基本操作： StrAsign(S,char

2、s) ； StrCopy(S,T) ； StrCompare(S,T) ； StrLength(S) ； StrCat(S,T) ； SubString(Sub,S,pos,len) 。 4 敘述以下每對術(shù)語的區(qū)別：空串和空格串；串變量和串常量；主串和子串；串變量的名字和串變 量的值。 5. 已知：S=”(xyz)* ” ,T= ”(x+z)*y ”。試利用聯(lián)接、求子串和置換等操作，將 S轉(zhuǎn)換為T. 6. S和T是用結(jié)點大小為1的單鏈表存儲的兩個串，設(shè)計一個算法將串S中首次不T匹配的子串逆置。 7. S是用結(jié)點大小為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. 寫一個函數(shù)將順序串s1中的第i個字符到第j個字符之間的字符用s2串替換 10 寫算法，實現(xiàn)順序串的基本操作 StrCompare（s,t） 11 寫算法，實現(xiàn)順序串的基本操作 StrReplace（&a

4、mp;s,t,v） 實習題 1. 已知串S和T,試以以下兩種方式編寫算法，求得所有包含在 S中而丌包含在T中的字符構(gòu)成的 新串R,以及新串R中每個字符在串S中第一次出現(xiàn)的位置。 （1） 利用CONCATLEN SUB和EQUA四種基本運算來實現(xiàn)。 （ 2） 以順序串作為存儲結(jié)構(gòu)來實現(xiàn)。 2. 編寫一個行編輯程序EDLINE完成以下功能： （1） 顯示若干行：list n 1-n2:顯示第n1行到第n2行，n1缺省時，從第一行開始, n2 缺省時，到最后一行， （2） 刪除若干行。 del n1-n2 ： n1 、 n2 說明同（ 1）。 （3） 編輯第 n 行。 edit n ：顯示第 n 行

5、的內(nèi)容，另輸入一行替換該行。 （ 4） 插入一行。 ins n ：在第 n 行之前插入一行。 （ 5） 字符替換。 replace str1,str2, n1-n2 ：在 n1 到 n2 行之間用 str2 替換 str1 3. 設(shè)計一個文學研究輔助程序，統(tǒng)計小說中特定單詞出現(xiàn)的頻率和位置。 第四章答案 4.1 設(shè) s= I AM A STUDENT t= GOOD q= WORKER。給出下列操作的結(jié)果: 【解答】 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 編寫算法，實現(xiàn)串的基本操作 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 第一次出現(xiàn)的位置 */ 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()*/ 附加題：用鏈式結(jié)構(gòu)實現(xiàn)定位函數(shù)。 解答】typedef struct Node char data; stru

10、ct Node *next; Node,*Lstring; int strIndex(Lstring S, int pos, Lstring T) /*從串 S 的 pos 序號起，串 T 第一次出現(xiàn)的位置 */ 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. 設(shè) s= I AM A STUDENT , t=GOOD , q=WORKER 。給出下列操作的結(jié)果： 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. 編寫算法，實現(xiàn)串的基本操作 StrReplac

13、e(S,T,V) 。 3. 假設(shè)以塊鏈結(jié)構(gòu)表示串，塊的大小為 1，且附設(shè)頭結(jié)點 試編寫算法，實現(xiàn)串的下列基本操作： StrAsign(S,chars) ； StrCopy(S,T) ； StrCompare(S,T) ； StrLength(S) ； StrCat(S,T) ； SubString(Sub,S,pos,len) 。 說明：用單鏈表實現(xiàn)。 4 敘述以下每對術(shù)語的區(qū)別：空串和空格串；串變量和串常量；主串和子串； 串變量的名字和串變量的值。 5 已知： S=”(xyz)* ”,T= ”(x+z)*y ”。試利用聯(lián)接、求子串和置換等操作，將 S 轉(zhuǎn)換為 T. 6 S 和 T 是用結(jié)點大

14、小為 1 的單鏈表存儲的兩個串， 設(shè)計一個算法將串 S 中首 次不 T 匹配的子串逆置。 7 S 是用結(jié)點大小為 4 的單鏈表存儲的串 ,分別編寫算法在第 k 個字符后插入串 T,及從第k 個字符刪除 len 個字符。 以下算法用定長順序串： 8 寫下列算法： ( 1) 將順序串 r 中所有值為 ch1 的字符換成 ch2 的字符。 ( 2) 將順序串 r 中所有字符按照相反的次序仍存放在 r 中。 ( 3) 從順序串 r 中刪除其值等于 ch 的所有字符。 4) 從順序串 r1 中第 index 個字符起求出首次不串 r2 相同的子串的起始位置 5） 從順序串 r 中刪除所有不串 r1 相同的子串。 9 寫一個函數(shù)將順序串 s1 中的第 i