严蔚敏《数据结构(c语言版)习题集》算法设计题第五章答案

严蔚敏《数据结构(c语言版)习题集》算法设计题第五章答案  

　　第五章 数组和广义表

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

　　{

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

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

　　for(i= ;i

　　{

　　j=i;l=(i+k)%n;temp=A[i];

　　while(l!=i)

　　{

　　A[j]=temp;

　　temp=A[l];

　　A[l]=A[j];

　　j=l;l=(j+k)%n;

　　}// 循环右移一步

　　A[i]=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 ;i++)

　　{

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

　　if(A[i][j] )>

　　for(j=0;j ;j++)

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

　　{

　　for(flag=1,k=0;k ;k++)

　　if(min

　　if(flag)

　　printf("Found a saddle element!nA[%d][%d]=%d",i,j,A[i][j]);

　　}

　　}//for

　　}//Get_Saddle

　　5.20

　　本题难度极大,故仅探讨一下思路.这一题的难点在于,在多项式的元数m未知的情况下,如何按照降幂次序输出各项.可以考虑采取类似于层序遍历的思想,从最高次的项开始,依次对其每一元的次数减一,入一个队列.附设访问标志visited以避免重复.

　　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(B.data[pb].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(B.data[pb].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)

　　{

　　A.data[pc].i=x;

　　A.data[pc].j=B.data[pb].j;

　　A.data[pc].e=B.data[pb].e;

　　pb++;pc++;

　　}

　　else

　　{

　　A.data[pc].i=x;

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

　　A.data[pc].e=A.data[pa].e

　　pa++;pc++;

　　}

　　}//while

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

　　{

　　A.data[pc].i=x;

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

　　A.data[pc].e=A.data[pa].e

　　pa++;pc++;

　　}

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

　　{

　　A.data[pc].i=x;

　　A.data[pc].j=B.data[pb].j;

　　A.data[pc].e=B.data[pb].e;

　　pb++;pc++;

　　}

　　}//for

　　A.tu=pc;

　　for(i=A.tu;i ;i++)>

　　}//TSMatrix_Addto

　　5.23

　　typedef struct{

　　int j;

　　int e;

　　} DSElem;

　　typedef struct{

　　DSElem data[MAXSIZE];

　　int cpot[MAXROW];//这个向量存储每一行在二元组中的起始位置

　　int mu,nu,tu;

　　} DSMatrix; //二元组矩阵类型

　　Status DSMatrix_Locate(DSMatrix A,int i,int j,int &e)//求二元组矩阵的元素A[i][j]的值e

　　{

　　for(s=cpot[i];s [i+1]&&a.data[s].j!=j;s++);>

　　if(A.data[s].i==i&&A.data[s].j==j) //找到了元素A[i][j]

　　{

　　e=A.data[s];

　　return OK;

　　}

　　return ERROR;

　　}//DSMatrix_Locate

　　5.24

　　typedef struct{

　　int seq; //该元素在以行为主序排列时的序号

　　int e;

　　} SElem;

　　typedef struct{

　　SElem data[MAXSIZE];

　　int mu,nu,tu;

　　} SMatrix; //单下标二元组矩阵类型

　　Status SMatrix_Locate(SMatrix A,int i,int j,int &e)//求单下标二元组矩阵的元素A[i][j]的值e

　　{

　　s=i*A.nu+j+1;p=1;

　　while(A.data[p].seq )>

　　if(A.data[p].seq==s) //找到了元素A[i][j]

　　{

　　e=A.data[p].e;

　　return OK;

　　}

　　return ERROR;

　　}//SMatrix_Locate

　　5.25

　　typedef enum{0,1} bool;

　　typedef struct{

　　int mu,nu;

　　int elem[MAXSIZE];

　　bool map[mu][nu];

　　} BMMatrix; //用位图表示的矩阵类型

　　void BMMatrix_Add(BMMatrix A,BMMatrix B,BMMatrix &C)//位图矩阵的加法

　　{

　　C.mu=A.mu;C.nu=A.nu;

　　pa=1;pb=1;pc=1;

　　for(i=0;i

　　for(j=0;j

　　{

　　if(A.map[i][j]&&B.map[i][j]&&(A.elem[pa]+B.elem[pb]))//结果不为0

　　{

　　C.elem[pc]=A.elem[pa]+B.elem[pb];

　　C.map[i][j]=1;

　　pa++;pb++;pc++;

　　}

　　else if(A.map[i][j]&&!B.map[i][j])

　　{

　　C.elem[pc]=A.elem[pa];

　　C.map[i][j]=1;

　　pa++;pc++;

　　}

　　else if(!A.map[i][j]&&B.map[i][j])

　　{

　　C.elem[pc]=B.elem[pb];

　　C.map[i][j]=1;