數據結構—用c語言描述課后習題答案(編輯修改稿)

　

【文章內容簡介】 strlen(D)=2（h） （h） index(B,D)=0（i） （i） index(C,”d”)=3（j） （j） insert(D,2,C)=”moldy”（k） （k） insert(B,1,A)=”mule”（l） （l） delete(B,2,2)=”me”（m） （m） delete(B,2,0)=”mule”（n） （n） replace(C,2,2,”k”)=”ok” 將S=“（xyz）*”轉為T=“（x+z）*y”S=concat(S, substr(S,3,1)) // ”(xyz)*y”S=replace(S,3,1,”+”) // ”(x+z)*y” char search(linkstring *X, linkstring *Y)// X和Y是用帶頭結點的結點大小為1的單鏈表表示的串，本算法查找X中 第一個不在Y中出現的字符。算法思想是先從X中取出一個字符，到Y中去查找，如找到，則在X中取下一字符，重復以上過程；若沒找到，則該字符為所求{ linkstring *p, *q,*pre。 // p,q為工作指針，pre控制循環 p=Xnext。 q=Ynext。 pre=p。 while (p amp。amp。 q) { ch=pdata。 // 取X中的字符 while (q amp。amp。 qdata!=ch) q=qnext。 // 和Y中字符比較 if (!q) return(ch)。 // 找到Y中沒有的字符 else { pre=pnext。 // 上一字符在Y中存在， p=pre。 // 取X中下一字符。 q=Ynext。 // 再從Y的第一個字符開始比較 }}return(null)。 // X中字符在Y中均存在 }// 算法結束 int strcmp(seqstring *S, seqstring *T)// S和T是指向兩個順序串的指針，本算法比較兩個串的大小，若S串大于T串，返回1；若S串等于T串，返回0；否則返回1 {int i=0。 while (sch[i]!=’\0’ amp。amp。 tch[i]!=’\0’) if (sch[i]tch[i]) return(1)。 else if (sch[i]tch[i]) return(1)。 else i++。 // 比較下一字符 if (sch[i]!=’\0’amp。amp。 tch[i]==0) return(1)。else if (sch[i]==’\0’amp。amp。 tch[i]!=0) return(1)。 else return(0)。}// 算法結束 linkstring *invert(linkstring *S, linkstring *T)// S和T是用帶頭結點的結點大小為1的單鏈表表示的串，S是主串，T是// 模式串。本算法是先模式匹配，查找T在S中的第一次出現。如模式匹// 配成功，則將S中的子串（T串）逆置。{linkstring *pre,*sp, *tp。 pre=S。 // pre是前驅指針，指向S中與T匹配時，T 中的前驅 sp=Snext。 tp=Tnext。//sp 和tp分別是S和T串上的工作指針 while (sp amp。amp。 tp)if (spdata==tpdata) // 相等時后移指針 {sp=spnext。 tp=tpnext。}else // 失配時主串回溯到下一個字符，子串再以第一個字符開始 {pre=prenext。 sp=prenext。 tp=Tnext。}if (tp!=null) return (null)。 // 匹配失敗，沒有逆置 else // 以下是T串逆置 {tp=prenext。 // tp是逆置的工作指針，現在指向待逆置的第一個字符prenext=sp。 // 將S中與T串匹配時的前驅指向匹配后的后繼 while (tp!=sp) { r=tpnext。 tpnext=prenext。 prenext=tp。 tp=r } }}// 算法結束 第五章 多維數組和廣義表（參考答案） A[2][3][2][3]A0000 , A0001 , A0002 A0010 , A0011 , A0012 A0100 , A0101 , A0102 A0110 , A0111 , A0112 A0200 , A0201 , A0202 A0210 , A0211 , A0212 將第一維的0變為1后，可列出另外18個元素。以行序為主（即行優先）時，先改變右邊的下標，從右到左進行。 設各維上下號為c1…d1，c2…d2，c3…d3，每個元素占l個單元。LOC(aijk)=LOC(ac1c2c3)+[(ic1)*(d2c2+1)*(d3c3+1)+(jc2)*(d3c3+1)+(kc3)]*l推廣到n維數組！！（下界和上界）為（ci，di），其中1=i=：其數據元素的存儲位置為：LOC（aj1j2….jn）=LOC（ac1c2…）+[（d2c2+1） …（dn+1）(j1c1)+(d3c3+1) …（dn+1） n(j2c2)+…+(dn+1)(jn11)+(jn)]*l=LOC(ac1c2c3)+ ∑αi(jici) i=1 n其中αi∏（dkck+1）（1=i=n） k=i+1若從c開始，c數組下標從0開始，各維長度為bi（1=i=n）則：LOC（aj1j2…jn）=LOC(a00…0)+(b2* b3*…* bn*j1+ b3* …* bn*+ j2…+ bn* jn1+ jn)*l n=LOC(a00…0)+ ∑αiji 其中：αi=l，αi1=bi*αi ，1i=n (1) k=2*i+j ( 0=k3n2 )(2) i=(k+1)/3 ( 0=k3n2 ) j=k2*ivoid saddlepoint(int a[m][n])。 // a是m行n列的二維數組,本算法求所有馬鞍點 // b是一維數組,存放一行中可能的馬鞍點的列值,k記相等值個數 // c是一維數組,存放某列可能馬鞍點的行值,kk記相等值個數 {for(i=0。im。i++) {min=a[i,0]。 // 最小值初始化 b[0]=0。 k=1。 // b數組記最小值的列號，k記最小值的個數 for(j=1。jn。j++) // 找每一行中的最小值 if (a[i][j]min) {b[0]=j。 min=a[i][j]。k=1。}// 重新確定最小值 else if (a[i][j]==min) {b[k+1]=j。 k++。} // 有相等的最小值 for (jj=0。jjk。k++) // 第i 行有k個相等的最小值 {j=b[jj]。 max=a[i][jj]。 kk=0。 // a[i][j]是否是馬鞍點 while (kkm amp。amp。 max=a[i][kk]) kk++。 if(kk=m)printf(“馬鞍點 i=%d,j=%d,a[i][j]=%d”,i,j,a[i][j])。 } // END OF for jj } // END OF for i 最壞時間復雜度為O(m*(n+n*m)). (最壞時所有元素相同，都是馬鞍點) 解法2: 若矩陣中元素值互不相同,則用一維數組row記下各行最小值，再用一維數組col記下各列最大值， 相等者為馬鞍點。for (i=0。im。i++) {row[i]=a[i][0]。 // 最小值初始化 for (j=1。jn。j++) // 找每一行中的最小值 if (a[i][j]row[i]) row[i]=a[i][j]。 // 重新確定最小值 }for (j=0。jn。j++) {col[j]=a[0,j]。 // 最大值初始化 for (i=1。im。i++) // 找每一列中的最大值 if (a[i][j]col[j]) col[j]=a[i][j]。 // 重新確定最大值 }for (i=0。im。i++) for (j=1。jn。j++)if(row[i]==col[j])printf(“馬鞍點 i=%d,j=%d,a[i][j]=%d”,i,j,a[i][j])。 時間復雜度O( (m*n)). 解法3: 設定兩個數組： max[0..n1] 記各列的最大值所在行號 min[0..m1] 記各行的最小值所在列號第j 列的最大值為A[max[j]][j],第i行的最小值是A[i][min[i]]void saddlepoint(int a[m][n])。 // a是m行n列的二維數組,本算法求所有馬鞍點 { int max[]=0,min[]=0。for(i=0。im。i++) for(i=0。 im。 i++) for (j=0。 jn。 k++) { if (A[i][j]A[max[j]][j]) max[j]=i。 // 重新確定第j列最大值的行號if (A[i][j]A[i][min[i]]) min[i]=j。 // 重新確定第i行最小值的列號 } for (i=0。im。i++) {j=min[i]。 // a[i][j]是否是馬鞍點 if( max[j]==i) printf(“馬鞍點 A[%d][%d]=%d”,i,j,a[i][j])。 } // END OF for jj } 時間復雜度為O(m*n+m). （1）三元組表（行號 0—5，列號 0—5）S=（（0，0，15），（0，3，22），（0，5，15），（1，1，11），（1，2，3），（2，3，6），（4，0，91），（5，2，28））（2）：兩矩陣A和B相加的結果是一矩陣C，其元素Cij有三種情況；（1）Cij=Aij（Bij =0）；（2）Cij=Bij（Aij =0）；（3）Cij=Aij+Bij 。在（3）種情況下，要看結果是否為0，C矩陣只有非零元素。Void matrixaddition(crosslist *A,*B)//稀疏矩陣A和B用十字鏈表存儲結構，本算法將稀疏矩陣B加到矩陣A上{ca=Anext。cb=Bnext。 while(ca!=Aamp。amp。cb!=B) //設pa和pb為矩陣A和B想加時的工作指針 {pa=caright。pb=cbright。} if(pa==ca)ca=canext。//A表在該行無非0元素； else if(pb==cb)cb=cbnext//B表在該行無非0元素； else if(pbcolpacol)//B的非0元素插入A中； {j=pbcol。pt=chb[j]。pre=pt// 取到表頭指針； while(ptdown_colpbcol) {pre=pt。pt=ptdown。} predown=ptdown。//該結點從B表相應列摘下 i=pbright。pt=chb[i]。pre=pt。//取B表行表頭指針 while(ptrightrowpbrow {pre=pt。pt=ptright。} preright=ptriht。//該結點從B表相應行鏈表中摘下。 Pbt=pb。pb=pbright。//B表移至下一結點 //以下是將pbt插入A表的相應列鏈表中