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

1、第四章習題第四章習題1.設s=’IAMASTUDENT’t=’GOOD’q=’WKER’。給出下列操作的結(jié)果：StrLength(s)SubString(sub1s17)SubString(sub2s71)StrIndex(s’A’4)StrReplace(s’STUDENT’q)StrCat(StrCat(sub1t)StrCat(sub2q))2.編寫算法，實現(xiàn)串的基本操作StrReplace(STV)。3.假設以塊鏈結(jié)構(gòu)表示串，塊

2、的大小為1，且附設頭結(jié)點。試編寫算法，實現(xiàn)串的下列基本操作：StrAsign(Ss)；StrCopy(ST)；StrCompare(ST)；StrLength(S)；StrCat(ST)；SubString(SubSposlen)。4敘述以下每對術(shù)語的區(qū)別：空串和空格串；串變量和串常量；主串和子串；串變量的名字和串變量的值。5已知：S=”(xyz)”T=”(xz)y”。試利用聯(lián)接、求子串和置換等操作，將S轉(zhuǎn)換為T.6S和T是用結(jié)點大小為

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

4、置。（5）從順序串r中刪除所有與串r1相同的子串。9寫一個函數(shù)將順序串s1中的第i個字符到第j個字符之間的字符用s2串替換。10寫算法，實現(xiàn)順序串的基本操作StrCompare(st)。4.2編寫算法，實現(xiàn)串的基本操作StrReplace(STV)。【解答】算法如下：intstrReplace(SStringSSStringTSStringV)用串V替換S中的所有子串Tintposipos=strIndex(S1T)求S中子串T第一次出

5、現(xiàn)的位置if(pos==0)return(0)while(pos!=0)用串V替換S中的所有子串Tswitch(T.lenV.len)case0:串T的長度等于串V的長度f(i=0ich[posi]=V.ch[i]case0:串T的長度大于串V的長度f(i=post.ienileni)將S中子串T后的所有字符Sch[it.lenv.len]=Sch[i]前移T.lenV.len個位置f(i=0ich[posi]=V.ch[i]Slen=