分析:本题基本思路与上题同.唯一的区别是,由于A,B互不相同,因此B不仅要向右错位,而且还要向左错位,以保证不漏掉一些情况.当B相对于A的位置不同时,需要匹配的区间的计算公式也各不相同,请读者自己画图以帮助理解.本算法的时间复杂度是o（strlrn（s）*strlen（t））。
第五章 数组和广义表
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 if(min 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;