字符串旋轉的若干種算法 （待續）

題目描述:

對于一個字符串，和字符串中的某一位置，請設計一個算法，將包括i位置在內的左側部分移動到右邊，將右側部分移動到左邊。

給定字符串A和它的長度n以及特定位置p，請返回旋轉后的結果。

測試樣例：

"AbcdeFgh",8,4  （為了方便起見我把兩部分的起始元素用大寫字母表示）

返回："FghAbcde"

思路：

·方法一：將整個字符串左移或右移(p - 1)次

·方法二: 將要分成的前部分或后部分整體移動

·方法三：利用棧

如： 先將FGH放置到前面，變成"FghdeFGH" 。每次覆蓋原有元素的時候將原來的元素存入隊列中，上述步驟執行完畢后依次從隊列中出隊并放入對應的位置即可。

代碼如下：

string rotateString(string A, int n, int p)
{
	queue<char> que;
	int i = p;
	int tmp_i = 0;
	for (i = p; i < n; i++)
	{
		que.push(A[tmp_i]);
		A[tmp_i] = A[i];
		++tmp_i;
	}
	que.push(A[tmp_i]);
	while (!que.empty())
	{
		A[tmp_i] = que.front();
		que.pop();
		++tmp_i;
	}
	A[tmp_i] = '\0';
	return A;
}

·方法四: 三次交換

這是一種很巧妙的算法。下面舉例說明：

還是用測試用例中的那段字符串 "AbcdeFgh"

根據p的位置，可以分為兩部分 "Abcde" 和 "Fgh"

可以先對兩個字符串分別逆序（第一次 和 第二次交換），得到  "edcbAhgF"

然后對整個字符串進行逆序（第三次） 得到 "FghAbcde"

我在方法三中用到了棧，其實是跟該方法類似的思想，

不過這個方法比我自己的方法三不知道高到哪里去了 (◎﹏◎)

·方法五: 合并、并讀取 

合并時，對于string對象 直接用庫里已經重載好的 "+" 操作符即可

（如果要合并兩個C風格的字符串，則需要用strcat函數）

例如測試用例的字符串 合并后為 "AbcdeFghAbcdeFgh"

然后再將這個合并后的字符串的第(p + 1)個元素到 (p + 1 + n)個元素按順序放入原字符串中即可。

代碼如下：

string rotateString(string A, int n, int p)
{
	queue<char> que;
	int i = p;
	int tmp_i = 0;
	for (i = p; i < n; i++)
	{
		que.push(A[tmp_i]);
		A[tmp_i] = A[i];
		++tmp_i;
	}
	que.push(A[tmp_i]);
	while (!que.empty())
	{
		A[tmp_i] = que.front();
		que.pop();
		++tmp_i;
	}
	A[tmp_i] = '\0';
	return A;
}