C/C++ 实现字符串左旋与旋转判断详解

林见深

发布时间：2026-10-16| 3人浏览过

原创

在 C/C++ 编程中，字符串旋转是考察数组操作与指针理解的经典题目。本文详细介绍两种实现字符串左旋的方法：直观的暴力移位与高效的“三步翻转”算法，并分享判断两字符串旋转关系的技巧——通过字符串追加结合 strstr 函数进行子串匹配。

字符串左旋实现

我们需要实现一个函数，将字符串向左循环移动 k 个字符。例如：

ABCD 左旋 1 个字符得到 BCDA
ABCD 左旋 2 个字符得到 CDAB

为了实现良好的交互体验，我们通常允许用户动态输入字符串和旋转次数，而非使用固定写死的字符数组。

第 1 步：理解暴力移位法

暴力移位的逻辑最为直接：每次将字符串的第一个字符移动到末尾，重复执行 k 次即可。

目的：通过单步移动模拟整体旋转。
动作：保存首元素，将其余元素向前覆盖一位，最后将保存的首元素填至末尾。
注意：scanf 读取整数后会遗留换行符，后续若用 gets 或 fgets 读字符串，必须先清空缓冲区，否则空行会被误读为输入。

#include<stdio.h>
#include<string.h>

// 字符串左旋函数（暴力移位）
char* turn_left(char* arr, int num)
{
	int len = strlen(arr);
	int i = 0;
	// 左旋多少次就循环几次
	for (i = 0; i < num; i++)
	{
		int j = 0;
		char tmp = arr[0]; // 保存首字符
		// 所有字符前移一位
		for (j = 0; j < len - 1; j++)
		{			
			arr[j] = arr[j + 1];			
		}
		arr[len-1] = tmp; // 首字符放到最后一位
	}
	return arr;
}

int main()
{
	char arr[100] = {0};
	int num = 0;
	while (1)
	{
		printf("请输入想要旋转的字符串:>");
		gets(arr);
		printf("请输入想要左旋数:>");
		scanf("%d", &num);
		getchar(); // 清除 scanf 留下的 \n
		printf("左旋字符串为:%s\n", turn_left(arr, num));
	}
	return 0;
}

第 2 步：掌握高效的三步翻转法

对于较大的字符串，暴力移位的时间复杂度较高。我们可以利用三次逆序来实现线性时间的旋转。其原理基于字符串翻转的对称性：

逆序左边部分：将前 k 个字符逆序。
逆序右边部分：将剩余字符逆序。
逆序整体：将整个字符串再次逆序。

此外，需注意处理旋转次数 num 大于字符串长度的情况，通过取模运算 num % len 确保索引有效。

#include<stdio.h>
#include<string.h>
#include<assert.h>

// 辅助函数：逆序字符串指定区间
void reverse(char* head, char* tail)
{
	assert(head && tail);
	char tmp = 0;
	char* ptmp = &tmp;
	while (head < tail)
	{
		tmp = *head;
		*head = *tail;
		*tail = tmp;
		head++;
		tail--;
	}
}

// 字符串左旋函数（三步翻转法）
char* turn_left(char* arr, int num)
{
	assert(arr);
	int len = strlen(arr);
	if (len)
	{
		int n = num % len; // 防止越界
		reverse(arr, &arr[n - 1]);          // 逆序前 n 个
		reverse(&arr[n], &arr[len - 1]);    // 逆序剩余部分
		reverse(arr, &arr[len - 1]);        // 逆序整个字符串
		return arr;
	}
	else
	{
		return arr;
	}
}

int main()
{
	char arr[100] = {0};
	int num = 0;
	while (1)
	{
		printf("请输入想要旋转的字符串:>");
		gets(arr);
		printf("请输入想要左旋数:>");
		scanf("%d", &num);
		getchar();
		printf("左旋字符串为:%s\n", turn_left(arr, num));
	}
	return 0;
}

判断字符串是否旋转

给定两个字符串，判断其中一个是否是另一个经过旋转得到的。例如：

s1 = ABCD, s2 = CDAB → 是旋转字符串
s1 = ABCD, s2 = ACBD → 不是旋转字符串

第 3 步：使用字符串追加与子串匹配

这道题有一个非常巧妙的解法：如果一个字符串是另一个字符串的旋转结果，那么它一定是 “原字符串 + 原字符串” 的子串。

准备条件：首先检查两个字符串长度是否一致，长度不同直接返回 false。
操作入口：将源字符串 str1 追加到自身后面（即 str1 = str1 + str1）。
具体动作：使用 strstr(str1, str2) 判断目标字符串 str2 是否存在于拼接后的 str1 中。
完成状态：如果找到子串，说明存在旋转关系；否则不存在。

这种方法利用了标准库函数，既简洁又高效，避免了手动遍历比较的繁琐。

#include<stdio.h>
#include<string.h>
#include<assert.h>

int is_left_move(char* str1, char* str2)
{	
	assert(str1 && str2);
	int len1 = strlen(str1);
	int len2 = strlen(str2);
	
	// 长度不同肯定不是旋转字符串
	if (len1 != len2)
		return 0;
	
	// 确保空间足够，这里演示思路，实际需保证内存不溢出
	// strncat(str1, str1, len1); 
	// 更严谨的做法是使用动态分配或大数组，此处仅展示逻辑
	// 在实际面试或工程中，建议先将str2追加到str1副本中
	char tempStr[100];
	strcpy(tempStr, str1);
	strncat(tempStr, str1, len1);
	
	// 判断 str2 是否是 tempStr 的子串
	if (strstr(tempStr, str2) != NULL)
		return 1;
	else
		return 0;
}

int main()
{
	char arr1[50] = {0};
	char arr2[50] = {0};
	while (1)
	{
		printf("请输入字符串:>");
		gets(arr1);
		printf("请输入需判断的旋转字符串:>");
		gets(arr2);
		int ret = is_left_move(arr1, arr2);
		if (ret == 1)
		{
			printf("是旋转字符串\n");
		}
		else
		{
			printf("不是旋转字符串\n");
		}
	}	
	return 0;
}