C语言数据结构回文判断

回文是指正反读都一样的字符串，比如“level”、“racecar”等等。判断一个字符串是否是回文可以使用栈或者双指针来实现。

1. 使用栈

将字符串的每个字符依次入栈，再依次弹出字符并与原字符串比较。如果所有字符弹出后与原字符串相同，则该字符串是回文。

下面是使用栈实现回文判断的代码：

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

typedef struct Stack {
    char data;
    struct Stack* next;
} Stack;

Stack* createStack() {
    Stack* s = (Stack*)malloc(sizeof(Stack));
    s->next = NULL;
    return s;
}

void push(Stack* s, char data) {
    Stack* node = (Stack*)malloc(sizeof(Stack));
    node->data = data;
    node->next = s->next;
    s->next = node;
}

char pop(Stack* s) {
    if (s->next == NULL) {
        return '\0';
    }
    Stack* node = s->next;
    s->next = node->next;
    char data = node->data;
    free(node);
    return data;
}

int isPalindrome(char* str) {
    int len = strlen(str);
    Stack* s = createStack();
    for (int i = 0; i < len; i++) {
        push(s, str[i]);
    }
    for (int i = 0; i < len; i++) {
        if (pop(s) != str[i]) {
            return 0;
        }
    }
    return 1;
}

int main() {
    char str[100];
    printf("Enter a string: ");
    scanf("%s", str);
    if (isPalindrome(str)) {
        printf("%s is a palindrome.\n", str);
    } else {
        printf("%s is not a palindrome.\n", str);
    }
    return 0;
}

2. 使用双指针

定义两个指针分别指向字符串的首尾，然后分别向中间移动，每次比较两个指针所指的字符是否相同。如果所有字符都相同，则该字符串是回文。

下面是使用双指针实现回文判断的代码：

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

int isPalindrome(char* str) {
    int len = strlen(str);
    int left = 0;
    int right = len - 1;
    while (left < right) {
        if (str[left] != str[right]) {
            return 0;
        }
        left++;
        right--;
    }
    return 1;
}

int main() {
    char str[100];
    printf("Enter a string: ");
    scanf("%s", str);
    if (isPalindrome(str)) {
        printf("%s is a palindrome.\n", str);
    } else {
        printf("%s is not a palindrome.\n", str);
    }
    return 0;
}