《数据结构——用C语言描述》+课后题答案(3)

变右边的下标，从右到左进行。

5.2 设各维上下号为c1?d1，c2?d2，c3?d3，每个元素占l个单元。

LOC(aijk)=LOC(ac1c2c3)+[(i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2)*(d3-c3+1)+(k-c3)]*l 推广到n维数组！！（下界和上界）为（ci，di），其中1<=i<=n.则：其数据元素的存储位置为：

LOC（aj1j2….jn）=LOC（ac1c2…cn）+[（d2-c2+1） ?（dn-cn+1）(j1-c1)+(d3-c3+1) ?（dn-cn+1） n

(j2-c2)+?+(dn-cn+1)(jn-1-cn-1)+(jn-cn)]*l=LOC(ac1c2c3)+ ∑αi(ji-ci) i=1

n

其中αi∏（dk-ck+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* jn-1+ jn)*l

n

=LOC(a00…0)+ ∑αiji 其中：αi=l，α

5.3 (1) k=2*i+j ( 0<=k<3n-2 ) (2) i=(k+1)/3 ( 0<=k<3n-2 ) j=k-2*i

5.4

void saddlepoint(int a[m][n]);

// a是m行n列的二维数组,本算法求所有马鞍点

// b是一维数组,存放一行中可能的马鞍点的列值,k记相等值个数 // c是一维数组,存放某列可能马鞍点的行值,kk记相等值个数 {for(i=0;i

{min=a[i,0]; // 最小值初始化

b[0]=0; k=1; // b数组记最小值的列号，k记最小值的个数 for(j=1;j

if (a[i][j]

else if (a[i][j]==min) {b[k+1]=j; k++;} // 有相等的最小值 for (jj=0;jj

while (kk=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;i

{row[i]=a[i][0]; // 最小值初始化

i-1

=bi*αi ，1

for (j=1;j

if (a[i][j]

}

for (j=0;j

{col[j]=a[0,j]; // 最大值初始化

for (i=1;i

if (a[i][j]>col[j]) col[j]=a[i][j]; // 重新确定最大值 }

for (i=0;i

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..n-1] 记各列的最大值所在行号

min[0..m-1] 记各行的最小值所在列号

第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;i

for (j=0; j

{ if (A[i][j]>A[max[j]][j]) max[j]=i; // 重新确定第j列最大值的行号 if (A[i][j]

}

for (i=0;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).

5.5 （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）

5.6算法分析：两矩阵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=A->next;cb=B->next;

while(ca!=A&&cb!=B)

//设pa和pb为矩阵A和B想加时的工作指针 {pa=ca->right;pb=cb->right;}

if(pa==ca)ca=ca->next;//A表在该行无非0元素； else

if(pb==cb)cb=cb->next//B表在该行无非0元素； else if(pb->colcol)//B的非0元素插入A中； {j=pb->col;pt=chb[j];pre=pt// 取到表头指针； while(pt->down_colcol)

{pre=pt;pt=pt->down;}

pre->down=pt->down;//该结点从B表相应列摘下 i=pb->right;pt=chb[i];pre=pt;//取B表行表头指针 while(pt->right->rowrow {pre=pt;pt=pt->right;}

pre->right=pt->riht;//该结点从B表相应行链表中摘下。 Pbt=pb;pb=pb->right;//B表移至下一结点 //以下是将pbt插入A表的相应列链表中

j=pbt->col;pt=cha[j];pre=pt;

while(pt->down !=cha[j]&&pt->down->rowrow)

{pre=pt;pt=pt->down}

pre->down=pbt;pbt->down=pt;

//以下是将pbt插入A表相应行链表中

i=pbt->right;pt=cha[i];pre=pt;

while(pt->right !=cha[i]&&pt->right-colcol) {pre=pt;pt=pt->right;} pre->right=ptb;

ptb->right=pt;

}//end of “if (pb->colcol)

else if(pa->col=pb->col)//处理两表中行列相同的非0元素 {v=pa->data+pb->data; if(v !=0)

{pa->data+=pb->data;pa=pa->right;

将pb从行链表中删除；pb=pb->right; }

else{将pa,pb从链表中删除;然后 pa=pa->right; pb=pb->right; } 5.7 (1) head((p,h,w))=p

(2) tail((b,k,p,h))=(k,p,h) (3) head(((a,b),(c,d)))=(a,b) (4) tail(((a,b),(c,d)))=((c,d)) (5) head(tail(((a,b),(c,d)))=(c,d) (6) tail(head(((a,b),(c,d))))=(b)

5.8 (1) (2)

5.9(1)

第6章 树和二叉树（参考答案）

6.1

(1)根结点a

6.2

三个结点的树的形态： 三个结点的二叉树的形态：

（2） （3） （1） （1） （2） （4） （5）

6．3 设树的结点数是n，则

n=n0+n1+n2+??+nm+ (1) 设树的分支数为B，有

n=B+1

n=1n1+2n2+??+mnm+1 (2) 由（1）和（2）有：

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《数据结构——用C语言描述》+课后题答案(3)在线全文阅读。