锐客网

  1. 首页 > it技术 > >

C语言|C语言——字符串旋转问题

算法c语言c++

字符串的旋转：
ABCD左旋一个字符为BCDA
ABCD左旋两个字符为CDAB
ABCD右旋一个字符为DABC
ABCD右旋两个字符为CDAB
这里只写了左旋，右旋的原理和左旋一样。
目录
实现旋转字符串：
1、暴力求解法：
2、三步翻转法
判断一个字符串是否由另一个字符串旋转而来
1、暴力求解法：
2、优化算法：
关于用到的函数扩展：
1、assert（断言函数）
2、strcmp（字符串比较函数）
3、strcat（字符串追加函数）
4、strncat（字符串追加函数）
5、strstr（判断是否子串函数）
实现旋转字符串： 1、暴力求解法： 思路：

假如只旋转一个字符：
将第一个字符从字符串中 拿 出来，然后将后面的字符依次向前移动，最后再将 拿 出来的第一个字符串放到最后面；
要旋转k个字符的话，只需用一个循环，以循环变量小于k作为循环条件即可。
C语言|C语言——字符串旋转问题
文章图片
代码及详情如下：
#include //1、暴力求解法： void left_move(char* arr, int k) { int len = strlen(arr); assert(arr); //断言函数 assert(k < len&& k >= 0); //将旋转的第一个字符先存起来，然后将这个字符的后面的字符依次往前移，然后再把旋转的字符放在最后 for (int i = 0; i < k; i++) {//旋转几次就循环几次 char tmp = arr[0]; //*arr for (int j = 0; j < len-1; j++) { arr[j] = arr[j + 1]; //*(arr+j)=*(arr+j+1); } arr[len - 1] = tmp; //最后将拿出来的字符放进最后一个位置 } }

2、三步翻转法 思路：
将一个字符串分成两部分：
1.要旋转的部分
2.不旋转的部分
先将要旋转的部分给他逆序，然后再将不旋转的部分给他逆序，最后所有该字符串逆序。
比如：
abcdef 要旋转两个字符--> ab cdef
1.先将旋转部分ab逆序-->ba cdef
2.再将不旋转部分逆序-->ba fedc
3.最后全部逆序-->cdefab
此时得到了旋转后的结果
C语言|C语言——字符串旋转问题
文章图片
代码及详情如下：
//逆序函数 //使用头尾双指针来实现 void inversion(char* left, char* right) { assert(left); assert(right); while (left < right) { char tmp = *left; *left = *right; *right = tmp; left++; right--; } } //三步翻转法 void left_move(char* arr,int k) { assert(arr); int len = strlen(arr); //字符串长度，用来方便求尾指针 //用头尾指针来进行逆序 //1、要旋转部分的逆序 inversion(arr, arr + k - 1); //arr是头地址，arr+k-1是这部分的尾地址 //2、不旋转部分的逆序 inversion(arr + k, arr + len - 1); //3、全部部分的逆序 inversion(arr, arr + len - 1); }

判断一个字符串是否由另一个字符串旋转而来 如：bcdea 是由 abcde 旋转一个字符得到的。
1、暴力求解法： 思路：
arr1与arr2：
用arr1 的所有旋转情况来和arr2 比较，如果其中有一种情况和arr2 相同，说明arr2 就是由arr1 旋转得到的。
假如arr1=“abcd”，他的所有旋转情况：
1、bcda；2、cdab；3、dabc；4、abcd。
arr2 只要和其中一种情况符合就是由arr1 旋转而来的。
代码及详情如下：
//1、暴力求解法 /*将原字符串所有的旋转可能都拿出来与另一字符串比较，若有相同的则yes*/ int is_left_move(char* arr1, char* arr2) { int len = strlen(arr1); //用来作循环条件，因为最多要将每一个字符都旋转一次 for (int i = 0; i < len; i++) { left_move(arr1, 1); //这里的数字代表旋转字符的个数因为是一个一个字符旋转，所以这里旋转个数只能写1，如果写了2，那么第一次就会旋转2字符然后会一直都旋转两字符 if (strcmp(arr1, arr2) == 0)//每旋转完一个字符就比较两字符串 return 1; } return 0; }

2、优化算法： 思路：
将arr1 复制份然后加在原arr1 的后面，此时的新arr1 包含了旋转的所有情况，然后用双指针来与arr2 进行比较。
例如arr1 =“abcd”，
将他“加倍”：arr1=“abcdabcd”；此时能找出他所有的翻转情况。
然后创建三个指针：arr1的头尾指针top1与rear1，arr2的头指针top2；
用指针移动来逐个逐个比较每个字符，初始，三个指针都在各自字符串的第一个字符处，
比较*top1与*top2，直到相等时，top2才会继续移动；
如果*top1==*top2，此时top1不移动了，让rear1和top2继续去移动比较，
如果*rear1一直和*top2相同，那么等rear1-top1==arr2长度时，说明arr2 全部被包含在新的arr1中，也就是说明arr2时arr1旋转后的情况一种；
如果中途碰见一个不相同的字符，那么top1会刷新位置，指向rear1++的位置，然后继续；
C语言|C语言——字符串旋转问题
文章图片

C语言|C语言——字符串旋转问题
文章图片
代码及详情如下：
//2、优化算法 //让原来的字符串再加一个原来的字符串的函数 void F(char* arr1) { int len = strlen(arr1); char* top = arr1; char* rear = arr1 + len; for (int i = 0; i < len; i++) { *rear = *top; top++; rear++; } } /*上面这个是我自己写的函数，但是c里面有该功能的库函数 strcat或者strncat，两者略有区别，文末有区分*/int is_left_move(char* arr1, char* arr2) { assert(arr1); assert(arr2); /*如果两个字符串长度不相同那肯定不是由旋转过来的*/ if (strlen(arr1) != strlen(arr2)) return 0; F(arr1); //让原函数“翻倍”或者用strncat(arr1,arr1,strlen(arr1)); char* top1 = arr1; //arr1的头指针 char* top2 = arr2; //arr2的头指针 char* rear1 = arr1; //arr1的尾指针 /*当arr2的第一个字符和arr1里的某一个字符相同时，top1就不动了，rear1与top2向后移动 当rear1-top1即连续相同字符数等于arr2的长度时，说明arr2是由arr1旋转过来的*/ while (top2

关于用到的函数扩展： 1、assert
断言（assert）作为一种软件调试的方法，提供了一种在代码中进行正确性检查的机制。
头文件：
语法/原型：void assert( int expression );
主要作用：是对一个boolean表达式进行检查，一个正确运行的程序必须保证这个Boolean表达式的值为true，若表达式的值为false,则说明程序已处于一种不正确的状态下，系统需要提供警告信息并且退出程序。
在我的程序中直接用的assert(arr1)，也可以写成 assert(arr1!=NULL),因为arr1是个指针，所以得判断下这个指针是否为空。
2、strcmp
strcmp() 函数用于对两个字符串进行比较（区分大小写）。
头文件：string.h
语法/原型：int strcmp(const char* stri1，const char* str2);
参数 str1 和 str2 是参与比较的两个字符串。
strcmp() 会根据 ASCII 编码依次比较 str1 和 str2 的每一个字符，直到出现不到的字符，或者到达字符串末尾（遇见\0）。
返回值：
如果返回值 < 0，则表示 str1 小于 str2。
如果返回值 > 0，则表示 str1 大于str2 。
如果返回值 = 0，则表示 str1 等于 str2。
3、strcat
strcat函数用于把一个字符串加在了前一个字符串的后面。
原型：extern char *strcat(char *dest,char *src);
头文件：string.h
参数：
  • dest – 指向目标数组
  • src – 要追加的字符串
例如：char arr1[30] = "abcdef";
char arr2[] = "ghi";
如果用了strcat(arr1,arr2);
那么arr1就会变成："abcdefghi";
但是这个函数不能用来自己追加自己，也就是说禁止自娱自乐：strcat(arr1,arr1);
还有需要注意：arr1一定要有足够的空间来存放arr2的字符串，否则会发生溢出情况。
4、strncat
strncat函数用于把一个给定长度的字符串加在了前一个字符串的后面。
原型：char *strncat(char *dest, const char *src, size_t n)
头文件：string.h
参数：
  • dest – 指向目标数组额外的空字符。
  • src – 要追加的字符串
  • n – 要追加的最大字符数。
例如：char arr1[30] = "abcdef";
如果这样用：strncat(arr1,arr1,6)；
那么arr1 == ”abcdefabcdef“；
所以在该程序中可以用这个函数来代替自己的函数。
5、strstr
strstr(str1,str2) 函数用于判断字符串str2是否是str1的子串。如果是，则该函数返回str2在str1中首次出现的地址；否则，返回NULL。
头文件：string.h
比如：
如果str1包含有str2：char str2 = “cde”；
char str1 = “abcde”；
则通过函数，将返回：strstr(str1,str2) = “cde”；
如果str1不包含有str2：char str2 = “cxef”；
char str1 = “abcdefgh”；
则通过函数，将返回：strstr(str1,str2) = NULL；
所以在该程序中可以用strstr(arr1,arr2)来代替我写的函数
函数没有太详细，主要是这里了解怎么用就行。
数据结构串得顺序存储方式：
【C语言|C语言——字符串旋转问题】https://blog.csdn.net/weixin_46263870/article/details/120433327

    推荐阅读


    上一篇：c语言|C语言——字符串分类统计

    下一篇：c语言将指针指向字符串,C语言基础——字符串指针（指向字符串的指针）