跳转至

BB1-回文串判断

[[CB1-判断带头结点的单链表是否为回文结构]]

1.判断带头结点的单链表是否为回文结构

代码实现

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 判断字符串是否为回文（使用双指针法）
 * @param str 输入字符串
 * @return 是回文返回true，不是回文返回false
 */
bool is_true(char str[]) {
    // 边界条件检查：空字符串或单字符认为是回文
    if (str == NULL) {
        return false;
    }

    int N = strlen(str);  // C语言内置函数，计算字符串长度

    // 使用双指针从两端向中间比较
    for (int i = 0; i < N / 2; i++) {
        // 比较对称位置的字符
        if (str[i] != str[N - i - 1]) {
            return false;  // 发现不匹配，不是回文
        }
    }

    return true;  // 所有对称位置字符都匹配，是回文
}
C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 优化版本：使用双指针技术（更直观）
 * @param str 输入字符串
 * @return 是回文返回true，不是回文返回false
 */
bool is_palindrome_two_pointers(char str[]) {
    if (str == NULL) {
        return false;
    }

    int left = 0;           // 左指针
    int right = strlen(str) - 1;  // 右指针

    // 双指针向中间移动，比较对应字符
    while (left < right) {
        if (str[left] != str[right]) {
            return false;  // 发现不匹配
        }
        left++;   // 左指针右移
        right--;  // 右指针左移
    }

    return true;  // 所有字符都匹配
}
C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 忽略大小写和非字母数字字符的回文判断
 * @param str 输入字符串
 * @return 是回文返回true，不是回文返回false
 */
bool is_palindrome_alphanumeric(char str[]) {
    if (str == NULL) {
        return false;
    }

    int left = 0;
    int right = strlen(str) - 1;

    while (left < right) {
        // 跳过左边的非字母数字字符
        while (left < right && !isalnum(str[left])) {
            left++;
        }

        // 跳过右边的非字母数字字符
        while (left < right && !isalnum(str[right])) {
            right--;
        }

        // 比较字符（忽略大小写）
        if (tolower(str[left]) != tolower(str[right])) {
            return false;
        }

        left++;
        right--;
    }

    return true;
}
C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 递归版本的回文判断
 * @param str 输入字符串
 * @param start 起始位置
 * @param end 结束位置
 * @return 是回文返回true，不是回文返回false
 */
bool is_palindrome_recursive_helper(char str[], int start, int end) {
    // 基础情况：指针相遇或交错
    if (start >= end) {
        return true;
    }

    // 比较当前字符
    if (str[start] != str[end]) {
        return false;
    }

    // 递归检查内部字符
    return is_palindrome_recursive_helper(str, start + 1, end - 1);
}

bool is_palindrome_recursive(char str[]) {
    if (str == NULL) {
        return false;
    }

    return is_palindrome_recursive_helper(str, 0, strlen(str) - 1);
}

算法执行流程图解

基本版本执行过程：

Text Only
1
2
3
4
5
6
7
8
字符串："abcba"  长度N=5

比较过程：
i=0: str[0]='a' vs str[4]='a' → 相等
i=1: str[1]='b' vs str[3]='b' → 相等
i=2: i < N/2=2.5 不成立，循环结束

结果：返回true

双指针版本执行过程：

Text Only
1
2
3
4
5
6
7
8
9
字符串："racecar"

执行过程：
left=0, right=6: 'r' vs 'r' → 相等，left=1, right=5
left=1, right=5: 'a' vs 'a' → 相等，left=2, right=4  
left=2, right=4: 'c' vs 'c' → 相等，left=3, right=3
left=3, right=3: left < right 不成立，循环结束

结果：返回true

复杂字符串处理：

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
字符串："A man, a plan, a canal: Panama"

处理过程：
原始：A man, a plan, a canal: Panama
处理：Amanaplanacanalpanama

双指针比较：
left=0, right=20: 'A' vs 'a' → 忽略大小写后相等
left=1, right=19: 'm' vs 'm' → 相等
...以此类推

算法比较图解

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
原字符串：r a c e c a r
索引：     0 1 2 3 4 5 6

方法1（原始）：i < N/2
i=0: 比较 str[0] 和 str[6]
i=1: 比较 str[1] 和 str[5]  
i=2: 比较 str[2] 和 str[4]
i=3: 3 < 3.5 不成立，结束

方法2（双指针）：
left=0, right=6 → 比较后 left=1, right=5
left=1, right=5 → 比较后 left=2, right=4
left=2, right=4 → 比较后 left=3, right=3
left < right 不成立，结束

复杂度分析

时间复杂度：O(n)

  • 比较次数：最多需要比较n/2对字符
  • 字符串长度计算：O(n)（strlen函数）
  • 总体时间复杂度：O(n)

空间复杂度：O(1)

  • 辅助变量：只使用常数个变量（i, left, right等）
  • 无额外存储：不需要额外的数据结构
  • 总体空间复杂度：O(1)

算法优化版本

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 优化版本：提前终止和边界优化
 */
bool is_palindrome_optimized(char str[]) {
    if (str == NULL) return false;

    int len = strlen(str);
    if (len <= 1) return true;  // 空串或单字符

    int left = 0;
    int right = len - 1;

    while (left < right) {
        // 提前终止：发现不匹配立即返回
        if (str[left] != str[right]) {
            return false;
        }
        left++;
        right--;
    }

    return true;
}

/**
 * SIMD优化版本（理论）：
 * 可以使用SIMD指令并行比较多个字符
 * 但实际效果有限，因为字符串长度通常不长
 */

性能测试对比

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 性能测试函数
void performance_test() {
    char* test_strings[] = {
        "a",
        "aa",
        "aba",
        "abba",
        "racecar",
        "A man, a plan, a canal: Panama",
        "race a car",
        "hello world"
    };

    int num_tests = sizeof(test_strings) / sizeof(test_strings[0]);

    for (int i = 0; i < num_tests; i++) {
        clock_t start = clock();

        // 测试原始方法
        for (int j = 0; j < 1000000; j++) {
            is_true(test_strings[i]);
        }

        clock_t time1 = clock() - start;

        // 测试双指针方法
        start = clock();
        for (int j = 0; j < 1000000; j++) {
            is_palindrome_two_pointers(test_strings[i]);
        }

        clock_t time2 = clock() - start;

        printf("字符串: %s\n", test_strings[i]);
        printf("原始方法: %ld\n", time1);
        printf("双指针方法: %ld\n", time2);
        printf("-------------------\n");
    }
}

错误处理完善版本

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 安全版本：添加完整的错误处理
 */
bool is_palindrome_safe(char str[]) {
    // 参数验证
    if (str == NULL) {
        printf("错误：输入字符串为空指针\n");
        return false;
    }

    // 空字符串处理
    if (str[0] == '\0') {
        return true;  // 空字符串认为是回文
    }

    int len = strlen(str);

    // 长度检查
    if (len < 0) {
        printf("错误：字符串长度异常\n");
        return false;
    }

    // 双指针比较
    int left = 0;
    int right = len - 1;

    while (left < right) {
        if (str[left] != str[right]) {
            return false;
        }
        left++;
        right--;
    }

    return true;
}

实际应用场景

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 应用示例：回文检测器
 */
void palindrome_detector() {
    char input[1000];

    printf("回文检测器\n");
    printf("输入字符串（输入'quit'退出）：\n");

    while (1) {
        printf("> ");
        if (fgets(input, sizeof(input), stdin) != NULL) {
            // 移除换行符
            input[strcspn(input, "\n")] = 0;

            if (strcmp(input, "quit") == 0) {
                break;
            }

            if (is_palindrome_alphanumeric(input)) {
                printf("是回文！\n");
            } else {
                printf("不是回文。\n");
            }
        }
    }
}

算法特点

核心思想： 利用字符串的对称性，从两端向中间比较对应位置的字符。

关键技术： 1. 对称比较：比较str[i]和str[N-i-1] 2. 双指针：left和right指针相向移动 3. 提前终止：发现不匹配立即返回

优势： - 时间效率高：O(n)时间复杂度 - 空间效率高：O(1)空间复杂度 - 实现简单：逻辑清晰，易于理解 - 适用广泛：支持各种类型的回文检测

应用场景： - 文本处理和验证 - 密码学中的回文检测 - 生物信息学（DNA序列分析） - 游戏开发（回文游戏） - 数据验证

扩展应用： - 数字回文检测 - 链表回文检测 - 树结构回文检测 - 多语言回文支持

这种回文检测算法是字符串处理中的基础算法，在实际开发中应用广泛，具有很高的实用价值。