C语言编程 字符串的旋转（左旋右旋及判断）

C语言编程 字符串的旋转（左旋右旋及判断）

此前不太熟悉这种类型的题目，特此做一个合计的方法总结。
包括字符串中字符的左旋(右旋)，和判断一个字符串是否是由另一个字符串旋转(左旋或者右旋)而来。

一.字符串的左旋(右旋)

由于左旋和右旋思路一致，这里仅介绍左旋方法。
这种题目有两种思路：
1.首字符的后置以及其余元素的往前推置，循环重复此过程K次(k为左旋字符个数)。

eg：
字符串为“ABCDEF”，要旋转2个字符，
首先保存首字符到一个变量，然后把其余变量全部提前一位置放，即为“BCDEF ”(此处注意，最后的终止符不要提前，留出一个空位)
再把用来保存的变量给字符串最后一个位置(除外)，即为“BCDEFA”
再做一次此过程即为“CDEFGA ”——》“CDEFGAB”

源代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void Exchange(char *str, int k)
{int i,m;char temp;char *sta;for (i = 0; i < k; i++){sta = str;temp = *str;//保存首字符for (m = 0; m <= (int)strlen(str)-1; m++)//元素提前放置{*sta = *(sta + 1);sta++;}*(str+strlen(str)) = temp;//将首字符放置最后}
}int main()
{int leng;printf("请输入要左旋几个字符n");scanf("%d", &leng);char str[] = "ABCDEFG";Exchange(str,leng);printf("%sn", str);system("pause");return 0;
}

2.三步旋转法
这种方法是由观察得来，旋转后的字符串有此规律：
旋转前“ABCDEFG”
旋转后“CDEFGAB”
将旋转后的字符逆置得
“CDEFGBA”
将未旋转的字符逆置得
“GFEDCBA”
再将全部字符逆置就得到了原来的字符串“ABCDEFG”
原字符串旋转时反向操作即可

源代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void reverse(char *left, char *right)//逆置函数
{char temp;while (left < right){temp = *left;*left = *right;*right = temp;left++; right--;}
}
void Exchange(char *str, int leng)//三步逆置
{reverse(str, str + leng-1);reverse(str + leng, str+strlen(str)-1);reverse(str, str + strlen(str) - 1);
}
int main()
{int leng;printf("请输入要左旋几个字符n");scanf("%d", &leng);char str[] = "ABCDEFG";Exchange(str,leng);printf("%sn", str);system("pause");return 0;
}

二.判断一个字符串是否是由另一个字符串旋转而来
1.第一种思路是不借助字符串库函数，将需要判断的字符串按照三步逆置法判断是否和原字符串相同，但是这种方法效率较差，而且时间复杂度高。

源代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void reverse(char *left,char *right)
{char temp;while (left < right){temp = *left;*left = *right;*right = temp;left++; right--;}
}
int judgeStr(char str1[],char str2[],char str3[])
{int i,m=0,sum=0,s;char *sta ;char *fina ;int length = strlen(str1);for (i = 0; i <(int)strlen(str2); i++){str3[i] = str2[i];}for (i = 0; i <= (int)strlen(str1) - 1; i++){sta = str3;fina = str3 + strlen(str1) - 1;reverse(sta, sta + i);reverse(sta + i + 1, fina);reverse(sta, fina);for (; m < (int)strlen(str1); m++){if (str1[m] != str3[m]){sum++;break;}}for (s = 0; s<(int)strlen(str2); s++){str3[s] = str2[s];}if (sum == 4){return 0;}}return 1;
}
int main(void)
{char str1[] = "ABCDE";char str2[] = "BCDEA";char str3[] = "BACDE";char stra[] = "AAAAA";int judge;judge = judgeStr(str1, str2,stra);if (judge == 1){printf("str2是由str1旋转得来的n");}else{printf("str2不是由str1旋转得来的n");}judge = judgeStr(str1, str3,stra);if (judge == 1){printf("str3是由str1旋转得来的n");}else{printf("str3不是由str1旋转得来的n");}system("pause");return 0;
}

2.使用字符串库函数解决
使用此方法需要注意到一个规律：
一个字符串后面再接一个和自身相同的字符串后，此字符串中就出现了所有旋转可以得到的结果。

eg：
A B C D A B C D，其中有所有的“ABCD”旋转结果，BCDA(2~5)，CDAB(3~6)，DABC(4~7)。

所以做法就是利用库函数将原字符串拼接一个自身，再在字符串中查找需要判断的字符串即可。

源代码：

#include<stdio.h>
#include<string.h>
int judge(char *str1, char *str2)
{strncat(str1, str1, strlen(str1));//原字符串拼接本身char *result = strstr(str3, str2);//查找目标字符串if (result == NULL){return -1;}else{return 0;}
}
int main()
{char str1[] = "ABCDE";char str2[] = "CDEAB";char str3[] = "DEBAC";int result = judge(str1, str2);if (result == -1){printf("str2不是由str1旋转得到n");}else{printf("str2是由str1旋转得到n");}result = judge(str1, str3);if (result == -1){printf("str3不是由str1旋转得到n");}else{printf("str3是由str1旋转得到n");}system("pause");return 0;
}