笔试面试4字符串的循环移位算法
字符串的循环移位是指将整个字符串左移或者后移n位。
例如:ab1234左移两位就是1234ab.
这个算法的实现是利用三次反转。
仔细观察发现,左移和后移后,1234和ab的顺序是不变的。
将1234和ab看成两个整体。
左移可以通过以下变换得到。
先将ab反转,得到ba1234;
然后反转另一部分,1234,得到ba4321;
最后将整个反转,就得到了1234ab,即左移两位后的字符串。
代码实现为:(限定n的值为合法值,即n>=0&&n<strlen(str))
#include <stdio.h> #include <conio.h> #include <string.h> //例如 123abc 左移两位变为 3abc12 //核心思想:将str看成两部分,12和3abc,利用三次反转完成左移 // 左移后,这两部分都是不变的。 //先将12反转,变为21; //反转3abc,变为cba3,这时候,源字符串变为了 21cba3 //这时候,再将整个串反转,变为了3abc21,完成左移 char *rotate_left(char *str,int n){//循环左移,str为原串,n为左移位数 if(str==NULL) return NULL; int len=strlen(str); int i;//C99 不允许在for内声明 for(i=0;i<n-1-i;i++){//reverse first part str[i]=str[i]^str[n-1-i]; str[n-1-i]=str[i]^str[n-1-i]; str[i]=str[i]^str[n-1-i]; } int j; for(i=0,j=n;j<len-1-i;j++,i++){//reverse second part str[j]=str[j]^str[len-1-i]; str[len-1-i]=str[j]^str[len-1-i]; str[j]=str[j]^str[len-1-i]; } int k; for(k=0;k<len-1-k;k++){//reverse all str[k]=str[k]^str[len-1-k]; str[len-1-k]=str[k]^str[len-1-k]; str[k]=str[k]^str[len-1-k]; } } int main() { char str1[]="hello";//不要写成 char *str="hello",因为这样的话得到的是字符串常量 char str2[]="thanks123"; char str3[]="carry"; printf("str1=%s\n",str1); rotate_left(str1,0); printf("rotate_left(str1,0);\n"); printf("str1=%s\n\n",str1); printf("str2=%s\n",str2); rotate_left(str2,3); printf("rotate_left(str2,3);\n"); printf("str2=%s\n\n",str2); printf("str3=%s\n",str3); printf("rotate_left(str3,5);\n"); rotate_left(str3,5); printf("str3=%s\n\n",str3); getch(); }
测试结果:
循环右移的思想是完全一样的。
#include <stdio.h> #include <conio.h> #include <string.h> char *rotate_right(char *str,int n){//循环左移,str为原串,n为右移位数 if(str==NULL) return NULL; int len=strlen(str); int i;//C99 不允许在for内声明 for(i=0;i<len-1-i-n;i++){//reverse first part str[i]=str[i]^str[len-n-i-1]; str[len-n-i-1]=str[i]^str[len-n-i-1]; str[i]=str[i]^str[len-n-i-1]; } int j; for(i=0,j=len-n;j<len-1-i;j++,i++){//reverse second part str[j]=str[j]^str[len-1-i]; str[len-1-i]=str[j]^str[len-1-i]; str[j]=str[j]^str[len-1-i]; } int k; for(k=0;k<len-1-k;k++){//reverse all str[k]=str[k]^str[len-1-k]; str[len-1-k]=str[k]^str[len-1-k]; str[k]=str[k]^str[len-1-k]; } } int main() { char str1[]="hello";//不要写成 char *str="hello",因为这样的话得到的是字符串常量 char str2[]="thanks123"; char str3[]="carry"; printf("str1=%s\n",str1); rotate_right(str1,0); printf("rotate_right(str1,0);\n"); printf("str1=%s\n\n",str1); printf("str2=%s\n",str2); rotate_right(str2,3); printf("rotate_right(str2,3);\n"); printf("str2=%s\n\n",str2); printf("str3=%s\n",str3); printf("rotate_right(str3,5);\n"); rotate_right(str3,5); printf("str3=%s\n\n",str3); getch(); }
测试结果:
——————————————————————————————————————————————————————————————————
//写的错误或者不好的地方请多多指导,可以在下面留言或者点击左上方邮件地址给我发邮件,指出我的错误以及不足,以便我修改,更好的分享给大家,谢谢。
转载请注明出处:http://blog.csdn.net/qq844352155
author:天下无双
Email:coderguang@gmail.com
2014-11-5
于GDUT
——————————————————————————————————————————————————————————————————