C/C++左旋字符串實(shí)現(xiàn)代碼舉例

更新時(shí)間：2023年12月18日 11:17:03 作者：Zik----

在C/C++語言中沒有專門的字符串變量,通常用字符數(shù)組來存放字符串,下面這篇文章主要給大家介紹了關(guān)于C/C++左旋字符串實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下

題目

實(shí)現(xiàn)一個(gè)函數(shù)，可以左旋字符串中的k個(gè)字符。

例如：ABCD左旋一個(gè)字符得到BCDA ABCD左旋兩個(gè)字符得到CDAB。

設(shè)計(jì)循環(huán)使其可以旋1次，然后讓他執(zhí)行n次是一個(gè)最簡單的思路：

長度為5的情況下，旋轉(zhuǎn)6、11、16...次相當(dāng)于1次，7、12、17...次相當(dāng)于2次，以此類推。

void leftRound(char * src, int time)
{
	int i, j, tmp;
  int len = strlen(src);
  time %= len; 
	for (i = 0; i < time; i++) //執(zhí)行k次的單次平移
	{
		tmp = src[0];
		for(j = 0; j < len - 1; j++) //單次平移
		{
			src[j] = src[j + 1];
		}
		src[j] = tmp;
	}
}

改進(jìn)一：

一次一次轉(zhuǎn)比較麻煩，我們可以選擇拼接法，一次到位：

void leftRound(char * src, int time)
{
	int len = strlen(src);
	int pos = time % len; //斷開位置的下標(biāo)
	char tmp[256] = { 0 }; //更準(zhǔn)確的話可以選擇malloc len + 1個(gè)字節(jié)的空間來做這個(gè)tmp
	
	strcpy(tmp, src + pos); //先將后面的全部拷過來
	strncat(tmp, src, pos); //然后將前面幾個(gè)接上
	strcpy(src, tmp); //最后拷回去
}

改進(jìn)二：

這個(gè)方法要用到一個(gè)數(shù)組形成的輔助空間，讓人覺得有點(diǎn)不爽，還可以有更好的選擇，例如ABCDEFG，左旋3次后變成DEFGABC，有一個(gè)特殊的操作方式：

先將要左旋的前三個(gè)家伙逆序（CBADEFG），然后將后半段也逆序（CBAGFED），最后整體逆序（DEFGABC）即可。這樣只需要做數(shù)值交換即可，可以寫一個(gè)函數(shù)幫我們完成局部逆序，代碼如下：

void reverse_part(char *str, int start, int end) //將字符串從start到end這一段逆序
{
	int i, j;
	char tmp;

	for (i = start, j = end; i < j; i++, j--)
	{
		tmp = str[i];
		str[i] = str[j];
		str[j] = tmp;
	}
}

void leftRound(char * src, int time)
{
	int len = strlen(src);
	int pos = time % len;
	reverse_part(src, 0, pos - 1); //逆序前段
	reverse_part(src, pos, len - 1); //逆序后段
	reverse_part(src, 0, len - 1); //整體逆序
}

補(bǔ)充：右旋字符串

右旋字符串可以通過左旋字符串‘string.size()-k’步來實(shí)現(xiàn)。比如，對于字符串abcdefg和右旋2步，我們可以先計(jì)算需要左旋的步數(shù)為string.size()-2，然后再調(diào)用左旋函數(shù)即可。

以下為右旋字符串的C++實(shí)現(xiàn)代碼：

#include <iostream>
#include <string>

using namespace std;

// 翻轉(zhuǎn)字符串中[start, end]部分
void reverse(string& str, int start, int end) {
    while (start < end) {
        swap(str[start], str[end]);
        start++;
        end--;
    }    
}

// 字符串右旋k步
string rightRotateString(string str, int k) {
    int len = str.size();
    int left = len-k%len;   // 需要左旋的步數(shù)
    // 翻轉(zhuǎn)前l(fā)eft個(gè)字符和剩余字符
    reverse(str, 0, left-1);
    reverse(str, left, len-1);
    // 整個(gè)字符串翻轉(zhuǎn)
    reverse(str, 0, len-1);
    return str;
}

int main() {
    string str = "abcdefg";
    int k = 2;
    string res = rightRotateString(str, k);
    cout << "右旋 " << k << " 步后：" << res << endl;
    return 0;
}

在上述代碼中，我們定義了與左旋函數(shù)相同的翻轉(zhuǎn)函數(shù)，并實(shí)現(xiàn)了字符串的右旋函數(shù)rightRotateString。在函數(shù)中，我們先計(jì)算需要左旋的步數(shù)為string.size()-k，然后調(diào)用左旋函數(shù)即可。具體來說，我們分別翻轉(zhuǎn)前l(fā)eft個(gè)字符和剩余字符，然后再翻轉(zhuǎn)整個(gè)字符串。最后，我們將結(jié)果返回。在主函數(shù)中，我們使用字符串abcdefg，并右旋2步，輸出結(jié)果為fgabcde。