数据结构严蔚敏习题册 答案

5.18

void RSh(int A[n],int k)//把数组A的元素循环右移k位,只用一个辅助存储空间 {

for(i=1;i<=k;i++)

if(n%i==0&&k%i==0) p=i;//求n和k的最大公约数p for(i=0;i

j=i;l=(i+n-k)%n;temp=A[i]; while(l!=i) {

A[j]=A[l];

j=l;l=(j+n-k)%n; }// 循环右移一步 A[j]=temp; }//for }//RSh

分析:要把A的元素循环右移k位,则A[0]移至A[k],A[k]移至A[2k]......直到最终回到A[0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以A[0],A[1],...A[p-1]为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p个\循环链\上面.举例如下: n=15,k=6,则p=3.

第一条链:A[0]->A[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0]. 第二条链:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1]. 第三条链:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2]. 恰好使所有元素都右移一次.

虽然未经数学证明,但作者相信上述规律应该是正确的. 5.19

void Get_Saddle(int A[m][n])//求矩阵A中的马鞍点 {

for(i=0;i

for(min=A[i][0],j=0;j

if(A[i][j]

if(A[i][j]==min) //判断这个(些)最小值是否鞍点 {

for(flag=1,k=0;k

printf(\ } }//for

}//Get_Saddle

5.20

int exps[MAXSIZE]; //exps数组用于存储某一项的各变元的指数 int maxm,n; //maxm指示变元总数,n指示一个变元的最高指数

void Print_Poly_Descend(int *a,int m)//按降幂顺序输出m元多项式的项，各项的系数已经按照题目要求存储于m维数组中，数组的头指针为a {

maxm=m;

for(i=m*n;i>=0;i--) //按降幂次序,可能出现的最高项次数为mn Get_All(a,m,i,0); //确定并输出所有次数为i的项 }//Print_Poly_Descend

void Get_All(int *a,int m,int i,int seq)//递归求出所有和为i的m个自然数 {

if(seq==maxm) Print_Nomial(a,exps); //已经求完时,输出该项 else {

min=i-(m-1)*n; //当前数不能小于min if(min<0) min=0;

max=n

exps[seq]=j; //依次取符合条件的数 Get_All(a,m-1,i-j,seq+1); //取下一个数 } }//else

exps[seq]=0; //返回 }//Get_All

void Print_Nomial(int *a,int exps[ ])//输出一个项,项的各变元的指数已经存储在数组exps中 {

pos=0;

for(i=0;i

pos*=n;

pos+=exps[i]; }

coef=*(a+pos); //取得该系数coef

if(!coef) return; //该项为0时无需输出

else if(coef>0) printf(\系数为正时打印加号 else if(coef<0) printf(\系数为负时打印减号

if(abs(coef)!=1) printf(\当系数的绝对值不为1时打印系数 for(i=0;i

if(exps[i]) //打印各变元及其系数 {

printf(\ printf(\

printf(\

if(exps[i]>1) printf(\系数为1时无需打印 }

}//Print_Nomial

分析:本算法的关键在于如何按照降幂顺序输出各项.这里采用了一个递归函数来找到所有满足和为i的m个自然数作为各变元的指数.只要先取第一个数为j,然后再找到所有满足和为i-j的m-1个自然数就行了.要注意j的取值范围必须使剩余m-1个自然数能够找到,所以不能小于i-(m-1)*maxn,也不能大于i.只要找到了一组符合条件的数,就可以在存储多项式系数的数组中确定对应的项的系数的位置,并且在系数不为0时输出对应的项.

5.21

void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix &C)//三元组表示的稀疏矩阵加法 {

C.mu=A.mu;C.nu=A.nu;C.tu=0; pa=1;pb=1;pc=1;

for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法 {

while(A.data[pa].i

while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素 {

if(A.data[pa].j==B.data[pb].j) {

ce=A.data[pa].e+B.data[pb].e; if(ce) //和不为0 {

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j; C.data[pc].e=ce; pa++;pb++;pc++; } }//if

else if(A.data[pa].j>B.data[pb].j) {

C.data[pc].i=x;

C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } else {

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e

pa++;pc++; }

}//while

while(A.data[pa]==x) //插入A中剩余的元素(第x行) {

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e pa++;pc++; }

while(B.data[pb]==x) //插入B中剩余的元素(第x行) {

C.data[pc].i=x;

C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } }//for C.tu=pc;

}//TSMatrix_Add 5.22

void TSMatrix_Addto(TSMatrix &A,TSMatrix B)//将三元组矩阵B加到A上 {

for(i=1;i<=A.tu;i++)

A.data[MAXSIZE-A.tu+i]=A.data[i];/把A的所有元素都移到尾部以腾出位置 pa=MAXSIZE-A.tu+1;pb=1;pc=1;

for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法 {

while(A.data[pa].i

while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素 {

if(A.data[pa].j==B.data[pb].j) {

ne=A.data[pa].e+B.data[pb].e; if(ne) //和不为0 {

A.data[pc].i=x;

A.data[pc].j=A.data[pa].j; A.data[pc].e=ne; pa++;pb++;pc++; } }//if

else if(A.data[pa].j>B.data[pb].j)