《数据结构题集》答案第5章数组和广义表.docVIP

第五章 数组和广义表 5.18 void RSh(int A[n],int k)//把数组A的元素循环右移k位,只用一个辅助存储空间{??for(i=1;i=k;i++)????if(n%i==0k%i==0) p=i;//求n和k的最大公约数p??for(i=0;ip;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;im;i++)??{????for(min=A[i][0],j=0;jn;j++)??????if(A[i][j]min) min=A[i][j]; //求一行中的最小值????for(j=0;jn;j++)??????if(A[i][j]==min) //判断这个(些)最小值是否鞍点??????{????????for(flag=1,k=0;km;k++)??????????if(minA[k][j]) flag=0;????????if(flag)??????????printf(Found a saddle element!\nA[%d][%d]=%d,i,j,A[i][j]);??????}??}//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(min0) min=0;????max=ni?n:i; //当前数不能大于max????for(j=min;j=max;j++)????{??????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;imaxm;i++) //求出该项的系数在m维数组a中低下标优先的存储位置pos??{????pos*=n;????pos+=exps[i];??}??coef=*(a+pos); //取得该系数coef??if(!coef) return; //该项为0时无需输出