C語言字符串旋轉問題的深入講解
字符串的旋轉：
ABCD左旋一個字符為BCDA
ABCD左旋兩個字符為CDAB
ABCD右旋一個字符為DABC
ABCD右旋兩個字符為CDAB
這裡隻寫瞭左旋，右旋的原理和左旋一樣。
實現旋轉字符串：
1、暴力求解法：
思路：
假如隻旋轉一個字符：
將第一個字符從字符串中 拿 出來，然後將後面的字符依次向前移動，最後再將 拿 出來的第一個字符串放到最後面；
要旋轉k個字符的話，隻需用一個循環，以循環變量小於k作為循環條件即可。
代碼及詳情如下：
#include<assert.h>
//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
此時得到瞭旋轉後的結果
代碼及詳情如下：
//逆序函數
//使用頭尾雙指針來實現
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++的位置，然後繼續；
代碼及詳情如下：
//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<arr2+strlen(arr2)) {//用arr2長度作循環條件
if (*rear1 == *top2) {
top2++;
rear1++;
}
else {
rear1++;
top1=rear1;
}
if (rear1 - top1 == strlen(arr2))
return 1;
}
return 0;
//以上是我自己寫的函數來實現的，但c語言裡也有一個現成的函數可以使用
//用strstr函數，文末簡單介紹
}
關於用到的函數擴展：
1、assert
斷言（assert）作為一種軟件調試的方法，提供瞭一種在代碼中進行正確性檢查的機制。
頭文件：<assert.h>
語法/原型：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語言字符串旋轉內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！