字符串的旋轉(zhuǎn)：

ABCD左旋一個字符為BCDA
ABCD左旋兩個字符為CDAB

ABCD右旋一個字符為DABC
ABCD右旋兩個字符為CDAB

這里只寫了左旋，右旋的原理和左旋一樣。

實現(xiàn)旋轉(zhuǎn)字符串：

1、暴力求解法：

思路：

假如只旋轉(zhuǎn)一個字符：

將第一個字符從字符串中 拿 出來，然后將后面的字符依次向前移動，最后再將 拿 出來的第一個字符串放到最后面；

要旋轉(zhuǎn)k個字符的話，只需用一個循環(huán)，以循環(huán)變量小于k作為循環(huán)條件即可。

 代碼及詳情如下：

#include<assert.h>
//1、暴力求解法：
void left_move(char* arr, int k) {
	int len = strlen(arr);
	assert(arr);    //斷言函數(shù)
	assert(k < len&& k >= 0);
 //將旋轉(zhuǎn)的第一個字符先存起來，然后將這個字符的后面的字符依次往前移，然后再把旋轉(zhuǎn)的字符放在最后
	for (int i = 0; i < k; i++) {//旋轉(zhuǎn)幾次就循環(huán)幾次
		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、三步翻轉(zhuǎn)法

思路：

將一個字符串分成兩部分：

 1.要旋轉(zhuǎn)的部分

 2.不旋轉(zhuǎn)的部分

先將要旋轉(zhuǎn)的部分給他逆序，然后再將不旋轉(zhuǎn)的部分給他逆序，最后所有該字符串逆序。

比如：

abcdef 要旋轉(zhuǎn)兩個字符--> ab cdef

1.先將旋轉(zhuǎn)部分ab逆序-->ba cdef

2.再將不旋轉(zhuǎn)部分逆序-->ba fedc

3.最后全部逆序-->cdefab

此時得到了旋轉(zhuǎn)后的結(jié)果

 代碼及詳情如下：

//逆序函數(shù)
//使用頭尾雙指針來實現(xiàn)
void inversion(char* left, char* right) {
	assert(left);
	assert(right);
 
	while (left < right) {
		char tmp = *left;
		*left = *right;
		*right = tmp;
		left++;
		right--;
	}
}
//三步翻轉(zhuǎn)法
void left_move(char* arr,int k) {
	assert(arr);
 
	int len = strlen(arr);//字符串長度，用來方便求尾指針
	//用頭尾指針來進行逆序
	//1、要旋轉(zhuǎn)部分的逆序
	inversion(arr, arr + k - 1);//arr是頭地址，arr+k-1是這部分的尾地址
	//2、不旋轉(zhuǎn)部分的逆序
	inversion(arr + k, arr + len - 1);
	//3、全部部分的逆序
	inversion(arr, arr + len - 1);
 
}

判斷一個字符串是否由另一個字符串旋轉(zhuǎn)而來

如：bcdea 是由 abcde 旋轉(zhuǎn)一個字符得到的。

1、暴力求解法：

思路：

arr1與arr2：
用arr1 的所有旋轉(zhuǎn)情況來和arr2 比較，如果其中有一種情況和arr2 相同，說明arr2 就是由arr1 旋轉(zhuǎn)得到的。

假如arr1=“abcd”，他的所有旋轉(zhuǎn)情況：

1、bcda；2、cdab；3、dabc；4、abcd。

arr2 只要和其中一種情況符合就是由arr1 旋轉(zhuǎn)而來的。

代碼及詳情如下：

//1、暴力求解法
/*將原字符串所有的旋轉(zhuǎn)可能都拿出來與另一字符串比較，若有相同的則yes*/
int is_left_move(char* arr1, char* arr2) {
	int len = strlen(arr1);    //用來作循環(huán)條件，因為最多要將每一個字符都旋轉(zhuǎn)一次
	for (int i = 0; i < len; i++) {
		left_move(arr1, 1);
//這里的數(shù)字代表旋轉(zhuǎn)字符的個數(shù)因為是一個一個字符旋轉(zhuǎn)，所以這里旋轉(zhuǎn)個數(shù)只能寫1，如果寫了2，那么第一次就會旋轉(zhuǎn)2字符然后會一直都旋轉(zhuǎn)兩字符
		if (strcmp(arr1, arr2) == 0)//每旋轉(zhuǎn)完一個字符就比較兩字符串
			return 1;
	}
	return 0;
}

2、優(yōu)化算法：

思路：

將arr1 復(fù)制份然后加在原arr1 的后面，此時的新arr1 包含了旋轉(zhuǎn)的所有情況，然后用雙指針來與arr2 進行比較。

例如arr1 =“abcd”，

將他“加倍”：arr1=“abcdabcd”；此時能找出他所有的翻轉(zhuǎn)情況。

然后創(chuàng)建三個指針：arr1的頭尾指針top1與rear1，arr2的頭指針top2；

用指針移動來逐個逐個比較每個字符，初始，三個指針都在各自字符串的第一個字符處，

比較*top1與*top2，直到相等時，top2才會繼續(xù)移動；

如果*top1==*top2，此時top1不移動了，讓rear1和top2繼續(xù)去移動比較，

如果*rear1一直和*top2相同，那么等rear1-top1==arr2長度時，說明arr2 全部被包含在新的arr1中，也就是說明arr2時arr1旋轉(zhuǎn)后的情況一種；

如果中途碰見一個不相同的字符，那么top1會刷新位置，指向rear1++的位置，然后繼續(xù)；

 代碼及詳情如下：

//2、優(yōu)化算法
//讓原來的字符串再加一個原來的字符串的函數(shù)
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++;
	}
}
/*上面這個是我自己寫的函數(shù)，但是c里面有該功能的庫函數(shù)
    strcat或者strncat，兩者略有區(qū)別，文末有區(qū)分*/
 
int is_left_move(char* arr1, char* arr2) {
	assert(arr1);
	assert(arr2);
 
	/*如果兩個字符串長度不相同那肯定不是由旋轉(zhuǎn)過來的*/
	if (strlen(arr1) != strlen(arr2))
		return 0;
 
	F(arr1);//讓原函數(shù)“翻倍”或者用strncat(arr1,arr1,strlen(arr1));
 
	char* top1 = arr1;//arr1的頭指針
	char* top2 = arr2;//arr2的頭指針
	char* rear1 = arr1;//arr1的尾指針
	/*當(dāng)arr2的第一個字符和arr1里的某一個字符相同時，top1就不動了，rear1與top2向后移動
	  當(dāng)rear1-top1即連續(xù)相同字符數(shù)等于arr2的長度時，說明arr2是由arr1旋轉(zhuǎn)過來的*/
 
	while (top2<arr2+strlen(arr2)) {//用arr2長度作循環(huán)條件
		if (*rear1 == *top2) {
			top2++;
			rear1++;
		}
		else {
			rear1++;
			top1=rear1;
		}
		if (rear1 - top1 == strlen(arr2))
			return 1;
	}
    return 0;
 
    //以上是我自己寫的函數(shù)來實現(xiàn)的，但c語言里也有一個現(xiàn)成的函數(shù)可以使用
    //用strstr函數(shù)，文末簡單介紹
}

關(guān)于用到的函數(shù)擴展：

1、assert

 斷言（assert）作為一種軟件調(diào)試的方法，提供了一種在代碼中進行正確性檢查的機制。

頭文件：<assert.h>

語法/原型：void assert( int expression );

主要作用：是對一個boolean表達式進行檢查，一個正確運行的程序必須保證這個Boolean表達式的值為true，若表達式的值為false,則說明程序已處于一種不正確的狀態(tài)下，系統(tǒng)需要提供警告信息并且退出程序。

在我的程序中直接用的assert(arr1)，也可以寫成 assert(arr1!=NULL),因為arr1是個指針，所以得判斷下這個指針是否為空。

2、strcmp

 strcmp() 函數(shù)用于對兩個字符串進行比較（區(qū)分大小寫）。

頭文件：string.h

語法/原型：int strcmp(const char* stri1，const char* str2);
參數(shù) str1 和 str2 是參與比較的兩個字符串。

strcmp() 會根據(jù) ASCII 編碼依次比較 str1 和 str2 的每一個字符，直到出現(xiàn)不到的字符，或者到達字符串末尾（遇見\0）。

返回值：
如果返回值 < 0，則表示 str1 小于 str2。
如果返回值 > 0，則表示 str1 大于str2 。
如果返回值 = 0，則表示 str1 等于 str2。

 3、strcat

strcat函數(shù)用于把一個字符串加在了前一個字符串的后面。
原型：extern char *strcat(char *dest,char *src);

頭文件：string.h

參數(shù)：

dest – 指向目標(biāo)數(shù)組
src – 要追加的字符串

例如：char arr1[30] = "abcdef";

           char arr2[] = "ghi";

如果用了strcat(arr1,arr2);

那么arr1就會變成："abcdefghi";

但是這個函數(shù)不能用來自己追加自己，也就是說禁止自娛自樂：strcat(arr1,arr1);

還有需要注意：arr1一定要有足夠的空間來存放arr2的字符串，否則會發(fā)生溢出情況。

 4、strncat

strncat函數(shù)用于把一個給定長度的字符串加在了前一個字符串的后面。

原型：char *strncat(char *dest, const char *src, size_t n)

頭文件：string.h

參數(shù)：

dest – 指向目標(biāo)數(shù)組額外的空字符。
src – 要追加的字符串
n – 要追加的最大字符數(shù)。

例如：char arr1[30] = "abcdef";

如果這樣用：strncat(arr1,arr1,6)；

那么arr1 == ”abcdefabcdef“；

所以在該程序中可以用這個函數(shù)來代替自己的函數(shù)。

5、strstr

strstr(str1,str2) 函數(shù)用于判斷字符串str2是否是str1的子串。如果是，則該函數(shù)返回str2在str1中首次出現(xiàn)的地址；否則，返回NULL。 

頭文件：string.h

比如：

如果str1包含有str2：char str2 = “cde”；
                                  char str1 = “abcde”；
則通過函數(shù)，將返回：strstr(str1,str2) = “cde”；

如果str1不包含有str2：char str2 = “cxef”；
                                     char str1 = “abcdefgh”；
則通過函數(shù)，將返回：strstr(str1,str2) = NULL；

所以在該程序中可以用strstr(arr1,arr2)來代替我寫的函數(shù)

函數(shù)沒有太詳細，主要是這里了解怎么用就行。

總結(jié)

到此這篇關(guān)于C語言字符串旋轉(zhuǎn)問題的文章就介紹到這了,更多相關(guān)C語言字符串旋轉(zhuǎn)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論