当前位置:文档之家› c语言字符串左旋转

c语言字符串左旋转

假设原数组序列为abcd1234,要求变换成的数组序列为1234abcd,即循环右移了4 位。

比较之后,不难看出,其中有两段的顺序是不变的:1234 和abcd,可把这两段看成两个整
体。

右移K 位的过程就是把数组的两部分交换一下。

变换的过程通过以下步骤完成:
逆序排列abcd:abcd1234 →dcba1234;
逆序排列1234:dcba1234 →dcba4321;
全部逆序:dcba4321 →1234abcd。

伪代码可以参考清单2-35。

//代码清单2-35
Reverse(int* arr, int b, int e)
{
for(; b < e; b++, e--)
{
int temp = arr[e];
arr[e] = arr[b];
arr[b] = temp;
}
}
RightShift(int* arr, int N, int k)
{
K %= N;
Reverse(arr, 0, N – K - 1);
Reverse(arr, N - K, N - 1);
8
Reverse(arr, 0, N - 1);
}
这样,我们就可以在线性时间内实现右移操作了。

就拿abcdef 这个例子来说(非常简短的三句,请细看,一看就懂):
1、首先分为俩部分,X:abc,Y:def;
2、X->X^T,abc->cba,Y->Y^T,def->fed。

3、(X^TY^T)^T=YX,cbafed->defabc,即整个翻转。

#include <cstdio>
5. #include <cstring>
6.
7. void rotate(char *start, char *end)
8. {
9. while(start != NULL && end !=NULL && start<end)
10. {
11. char temp=*start;
12. *start=*end;
13. *end=temp;
14. start++;
15. end--;
13
16. }
17.
18. }
19.
20. void leftrotate(char *p,int m)
21. {
22. if(p==NULL)
23. return ;
24. int len=strlen(p);
25. if(m>0&&m<=len)
26. {
27. char *xfirst,*xend;
28. char *yfirst,*yend;
29. xfirst=p;
30. xend=p+m-1;
31. yfirst=p+m;
32. yend=p+len-1;
33. rotate(xfirst,xend);
34. rotate(yfirst,yend);
35. rotate(p,p+len-1);
36. }
37. }
38.
39. int main(void)
40. {
41. char str[]="abcdefghij";
42. leftrotate(str,3);
43. printf("%s/n",str);
44. return 0;
45. }。

相关主题