个元素大小的附加存储,元素移动或交换次数为Om) 解 分析:要把A的元素循环右移k位,则A[移至Ak]Ak]移至A[2k]…直到最终回到A0然而这并没有全 部解决问题,因为有可能有的元素在此过程中始终没有被访问过而是被跳了过去分析可知当n和k的最大 公约数为p时,只要分别以A[O]A[]AIp-为起点执行上述算法,就可以保证每一个元素都被且仅被右移 次,从而满足题目要求也就是说,A的所有元素分别处在p个"循环链"上面举例如下 =15k=6,则p=3 第一条链:A]->A[6]A6]->A[12]A12}>A[31A[3>A[9A[9}>A[0“顺便”移动了A[6]、A[2]… 第二条链:A[]->A门7,A[7]->A[3]A[13->A[4]A4}>A[10]A[10}>A[] 第三条链:A[2]->A[8]A[8]->A[41A[4}>A[5A[5>A[1A[->A[2] 恰好使所有元素都右移一次 虽然未经数学证明,但作者相信上述规律应该是正确的程序如下: void rSh(int A[m,intk)∥/把数组A的元素循环右移k位,只用一个辅助存储空间 for(i=l; <=k; 1++) ifn%=0&&k%i=0)p=i/求n和k的最大公约数p for(=0;i<p;i++) j=i; I=(i+k)%n, temp=A[O] lle(l=i) Altemps temp=All A[=A亦l j=;=(+k)%n, ∥循环右移一步 Ai=temp i//fo i//RSh 附加题:利用C的库函数 strlen, strep(或 strncpy)写一个算法 void StrDelete(char *S,int t, int m),删 除串S中从位置开始的连续的m个字符。若i≥ strlen(S),则没有字符被删除;若计m≥ strlen(S),则将 S中从位置i开始直至末尾的字符均被删去。 提示: strlen是求串长 ength)函数: int strlen( char s);//求串的长度 strcpy是串复制copy)函数:char* strcpy( char to, char from;/该函数将串from复制到串 to中,并且返回一个指向串to的开始处的指针。5 个元素大小的附加存储，元素移动或交换次数为 O(n) 解： 分析:要把 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[6]、A[12]… 第二条链: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]. 恰好使所有元素都右移一次. 虽然未经数学证明,但作者相信上述规律应该是正确的. 程序如下： 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<p;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 附加题： 利用 C 的库函数 strlen, strcpy（或 strncpy）写一个算法 void StrDelete(char *S,int t,int m) ，删 除串 S 中从位置 i 开始的连续的 m 个字符。若 i≥strlen(S)，则没有字符被删除；若 i+m≥strlen(S)，则将 S 中从位置 i 开始直至末尾的字符均被删去。 提示：strlen 是求串长(length)函数：int strlen(char s); //求串的长度 strcpy 是串复制(copy)函数：char *strcpy(char to,char from); //该函数将串 from 复制到串 to 中，并且返回一个指向串 to 的开始处的指针