[c语言日寄]字符串的左旋与右旋

【作者主页】siy2333
【专栏介绍】⌈c语言日寄⌋：这是一个专注于C语言刷题的专栏，精选题目，搭配详细题解、拓展算法。从基础语法到复杂算法，题目涉及的知识点全面覆盖，助力你系统提升。无论你是初学者，还是进阶开发者，这里都能满足你的需求！
【食用方法】1.根据题目自行尝试 2.查看基础思路完善题解 3.学习拓展算法
【Gitee链接】资源保存在我的Gitee仓库：https://gitee.com/siy2333/study

前言

在C语言中，字符串操作是一个非常重要的主题，它不仅涉及到基础的字符处理，还涉及到算法设计和数据结构的运用。今天，我们通过一个有趣的题目——判断一个字符串是否为另一个字符串旋转后的字符串，来深入探讨字符串的左旋与右旋操作。这个问题不仅能帮助我们理解字符串的基本操作，还能锻炼我们的算法思维。接下来，我们将从题目引入、子功能介绍、注意事项、题目分析解答以及拓展应用五个方面展开讨论。

一、题目引入

在编程中，字符串的旋转操作是一种常见的问题。有以下题目：

写一个函数，判断一个字符串是否为另外一个字符串旋转之后的字符串。

例如：

• 给定s1 =AABCD 和 s2 = BCDAA，返回1
• 给定s1=abcd 和 s2=ACBD，返回0.

其中：

• AABCD左旋一个字符得到ABCDA
• AABCD左旋两个字符得到BCDAA
• AABCD右旋一个字符得到DAABC

这个问题看似简单，但背后涉及到字符串的拼接、比较以及内存管理等多方面的知识：不仅需要我们理解字符串的基本操作，还需要我们掌握如何高效地实现旋转操作以及如何判断两个字符串是否相等。接下来，我们将通过实现左旋和右旋的子功能来逐步解决这个问题。

二、子功能介绍

为了实现字符串的旋转操作，我们需要设计两个核心子功能：左旋和右旋。这两个功能将帮助我们对字符串进行操作，并为最终的判断提供支持。

1. 左旋操作

左旋操作是指将字符串的前 n 个字符移动到字符串的末尾。

例如，对于字符串 “AABCD”，左旋两个字符后得到 “BCDAA”。

左旋操作的实现需要以下步骤：
我们假设有一个数组a：

a. 创建一个临时数组来存储需要移动到末尾的前 n 个字符。

b. 将剩余的字符向前移动 n 个位置。

c. 将临时数组中的字符复制到字符串的末尾。

d. 释放临时数组占用的内存。

free(str_b);

以下是左旋操作的代码实现：

void left(char* str, const int n) {
    assert(str != NULL);
    int size = (int)strlen(str);
    assert(n > 0);
    assert(n <= size);

    // 创建临时数组
    char* str_b = (char*)malloc(sizeof(char) * n);
    if (str_b == NULL) {
        printf("内存不足");
        return;
    }

    // 另存前n个数
    for (int i = 0; i < n; i++) {
        str_b[i] = str[i];
    }

    // 把数往前推移n个
    for (int i = 0; i < size - n; i++) {
        str[i] = str[i + n];
    }

    // 将n赋值到目前数组后
    for (int i = 0; i < n; i++) {
        str[size - n + i] = str_b[i];
    }

    // 释放内存
    free(str_b);
    return;
}

2. 右旋操作

右旋操作与左旋操作类似，但方向相反。右旋操作是指将字符串的后 n 个字符移动到字符串的开头。

例如，对于字符串 “AABCD”，右旋一个字符后得到 “DAABC”。

同理：右旋操作的实现步骤如下：

• a. 创建一个临时数组来存储需要移动到开头的后 n 个字符。
• b. 将剩余的字符向后移动 n 个位置。
• c. 将临时数组中的字符复制到字符串的开头。
• d. 释放临时数组占用的内存。

以下是右旋操作的代码实现：

void right(char* str, const int n) {
    assert(str != NULL);
    int size = (int)strlen(str);
    assert(n > 0);
    assert(n <= size);

    // 创建临时数组
    char* str_b = (char*)malloc(sizeof(char) * n);
    if (str_b == NULL) {
        printf("内存不足");
        return;
    }

    // 另存后n个数
    for (int i = 0; i < n; i++) {
        str_b[i] = str[size - n + i];
    }

    // 把数往后推移n个
    for (int i = 0; i < size - n; i++) {
        str[size - 1 - i] = str[size - 1 - i - n];
    }

    // 将n赋值到目前数组前
    for (int i = 0; i < n; i++) {
        str[i] = str_b[i];
    }

    // 释放内存
    free(str_b);
    return;
}

通过这两个子功能，我们可以对字符串进行任意的左旋和右旋操作。接下来，我们将介绍在实现这些功能时需要注意的事项。

三、注意事项

在实现字符串的左旋和右旋操作时，需要注意以下几个问题：

1. 输入验证

在对字符串进行操作之前，必须确保输入的字符串指针不为空。此外，旋转的位数 n 必须大于 0 且小于等于字符串的长度。否则，可能会导致程序崩溃或未定义行为。

assert(str != NULL);
int size = (int)strlen(str);
assert(n > 0);
assert(n <= size);

2. 内存管理

在实现左旋和右旋操作时，我们使用了动态内存分配来存储临时数据。在操作完成后，必须释放这些动态分配的内存，以避免内存泄漏。

free(str_b);

3. 字符串比较

在判断两个字符串是否相等时，不能直接使用 == 运算符，因为这只会比较指针的地址，而不是字符串的内容。正确的做法是逐个字符比较，或者使用标准库函数 strcmp。

int i = 0;
while (str1[i] != '\0') {
    if (str1[i] != str2[i]) return 0;
    i++;
}
return 1;

4. 旋转次数优化

对于长度为 size 的字符串，最多只需要旋转 size - 1 次即可覆盖所有可能的旋转情况。因此，在判断字符串是否为旋转关系时，旋转次数应限制在 size - 1 以内。

5. 字符串复制

在对字符串进行操作时，需要特别注意字符串的结尾字符 \0。在复制字符串时，必须确保 \0 也被正确复制，以避免字符串截断或未定义行为。

四、题目分析解答

现在，我们已经介绍了左旋和右旋操作的实现，并讨论了需要注意的事项。接下来，我们将结合这些知识，解决题目中的问题：判断一个字符串是否为另一个字符串旋转后的字符串。

问题分析

题目要求判断字符串 s2 是否可以通过对字符串 s1 进行左旋或右旋操作得到。为了实现这一目标，我们需要：

1. 检查两个字符串的长度是否相等。如果长度不同，则直接返回 0。
2. 对 s1 进行左旋和右旋操作，分别生成所有可能的旋转字符串。
3. 比较每次旋转后的字符串是否与 s2 相等。如果找到匹配的字符串，则返回 1；否则，返回 0。

代码实现

#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdio.h>

void left(char* str, const int n);
void right(char* str, const int n);
_Bool check2(const char* str1, const char* str2);
_Bool check(const char* str1, const char* str2);

int main() {
    char str1[] = "1234567890";
    char str2[] = "9012345678";

    if (check(str1, str2)) printf("YES");
    else printf("NO");

    return 0;
}

void left(char* str, const int n) {
    assert(str != NULL);
    int size = (int)strlen(str);
    assert(n > 0);
    assert(n <= size);

    // 创建临时数组
    char* str_b = (char*)malloc(sizeof(char) * n);
    if (str_b == NULL) {
        printf("内存不足");
        return;
    }

    // 另存前n个数
    for (int i = 0; i < n; i++) {
        str_b[i] = str[i];
    }

    // 把数往前推移n个
    for (int i = 0; i < size - n; i++) {
        str[i] = str[i + n];
    }

    // 将n赋值到目前数组后
    for (int i = 0; i < n; i++) {
        str[size - n + i] = str_b[i];
    }

    // 释放内存
    free(str_b);
    return;
}

void right(char* str, const int n) {
    assert(str != NULL);
    int size = (int)strlen(str);
    assert(n > 0);
    assert(n <= size);

    // 创建临时数组
    char* str_b = (char*)malloc(sizeof(char) * n);
    if (str_b == NULL) {
        printf("内存不足");
        return;
    }

    // 另存后n个数
    for (int i = 0; i < n; i++) {
        str_b[i] = str[size - n + i];
    }

    // 把数往后推移n个
    for (int i = 0; i < size - n; i++) {
        str[size - 1 - i] = str[size - 1 - i - n];
    }

    // 将n赋值到目前数组前
    for (int i = 0; i < n; i++) {
        str[i] = str_b[i];
    }

    // 释放内存
    free(str_b);
    return;
}

_Bool check(const char* str1, const char* str2) {
    // 避免空指针
    assert(str1 != NULL);
    assert(str2 != NULL);

    // 获取字符串大小，检查字数是否相同
    int size1 = (int)strlen(str1);
    int size2 = (int)strlen(str2);
    if (size1 != size2) return 0;

    // 复制数组
    char* str2_ = (char*)malloc(sizeof(char) * (size1 + 1));
    if (str2_ == NULL) {
        printf("内存不足");
        return -1;
    }

    // 检查左旋
    for (int i = 1; i < size1; i++) {
        strcpy(str2_, str2);
        left(str2_, i);
        if (check2(str1, str2_)) { free(str2_); return 1; }
    }

    // 检查右旋
    for (int i = 1; i < size1; i++) {
        strcpy(str2_, str2);
        right(str2_, i);
        if (check2(str1, str2_)) { free(str2_); return 1; }
    }

    free(str2_);
    return 0;
}

_Bool check2(const char* str1, const char* str2) {
    assert(str1 != NULL);
    assert(str2 != NULL);

    int i = 0;
    while (str1[i] != '\0') {
        if (str1[i] != str2[i]) return 0;
        i++;
    }
    return 1;
}

代码分析

• 主函数：在主函数中，我们定义了两个字符串 str1 和 str2，并调用 check 函数判断它们是否为旋转关系。
• 左旋和右旋函数：这两个函数分别实现了字符串的左旋和右旋操作。它们通过临时数组存储需要移动的字符，并通过循环实现字符的移动。
• 检查函数：check 函数首先检查两个字符串的长度是否相等。如果长度不同，则直接返回 0。然后，它通过循环分别尝试左旋和右旋操作，并调用 check2 函数比较旋转后的字符串是否与目标字符串相等。
• 字符串比较函数：check2 函数逐个字符比较两个字符串是否相等。

通过以上实现，我们可以高效地判断两个字符串是否为旋转关系。

五、拓展应用

字符串的左旋和右旋操作不仅限于解决上述问题，它们在实际应用中还有许多其他用途。以下是一些拓展应用的例子：

1. 字符串加密
   在某些简单的加密算法中，可以通过对字符串进行多次旋转操作来实现加密。例如，将字符串左旋 3 个字符，再右旋 2 个字符，最后再左旋 1 个字符。解密时，只需按照相反的顺序进行旋转操作即可。
2. 字符串匹配
   在字符串匹配问题中，旋转操作可以用于生成所有可能的子串。例如，对于字符串 “ABCD”，通过旋转可以生成 “ABCD”、“BCDA”、“CDAB” 和 “DABC”。这些子串可以用于模式匹配算法中，提高匹配效率。
3. 环形队列
   在环形队列的实现中，可以使用字符串的旋转操作来模拟队列的入队和出队操作。通过左旋和右旋操作，可以高效地移动队列中的元素，而无需额外的内存分配。
4. 数据校验
   在数据传输中，可以通过对数据进行旋转操作并计算校验和，来验证数据的完整性和一致性。例如，将数据字符串左旋 5 个字符后计算校验和，接收方在接收到数据后，同样进行左旋 5 个字符并计算校验和，如果两者一致，则说明数据传输正确。
5. 游戏开发
   在游戏开发中，旋转操作可以用于生成迷宫、地图或其他复杂的图形结构。例如，通过旋转字符串数组，可以生成不同方向的迷宫路径，增加游戏的趣味性和挑战性。

总结

通过以上对字符串左旋与右旋操作的详细讨论，我们不仅解决了题目中的问题，还掌握了字符串操作的核心技巧。左旋和右旋操作在实际应用中具有广泛的应用场景，从简单的字符串处理到复杂的算法设计，它们都扮演着重要的角色。
如果你对其他C语言问题感兴趣，欢迎关注我的专栏，我会定期分享更多有趣的编程题目和技巧。感谢你的阅读，我们下次再见。关注窝，每三天至少更新一篇优质c语言题目详解~

[专栏链接QwQ] :⌈c语言日寄⌋CSDN
[关注博主ava]：siy2333
感谢观看~ 我们下次再见!!