编写一个算法函数,使用链栈或队列,判定给定的字符序列是否为回文,并验证。c语言
时间: 2024-10-15 09:22:14 浏览: 52
python简单算法04:判断一个字符串是否为回文串的排列之一
在C语言中,你可以选择链表数据结构来编写一个判断字符序列是否为回文的函数。这里我们提供两种方法,一种是使用双向链表(类似队列的操作),另一种是使用单向链表结合递归(类似栈的行为)。
**方法一:双端链表(类似于队列操作)**
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct Node {
char data;
struct Node* next;
} Node;
// 创建链表头指针
Node* createList(char *str) {
Node* head = (Node*)malloc(sizeof(Node));
Node* temp = head;
for (int i = 0; str[i]; i++) {
temp->data = str[i];
temp->next = (Node*)malloc(sizeof(Node));
temp = temp->next;
}
return head;
}
// 验证链表是否回文
int isPalindrome(Node* head) {
Node* start = head;
Node* end = NULL;
while (start && start->next) {
end = start->next;
if (start->data != end->data) {
return 0; // 回文失败
}
start = start->next->next;
end = end->prev;
}
return start == end || (!start && !end); // 如果只有一个元素或为空,则是回文
}
// 主函数测试
int main() {
char str[] = "madam";
Node* list = createList(str);
int result = isPalindrome(list);
if (result) {
printf("'%s' is a palindrome.\n", str);
} else {
printf("'%s' is not a palindrome.\n", str);
}
free(list); // 清理内存
return 0;
}
```
**方法二:单向链表(递归,类似栈操作)**
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct Node {
char data;
struct Node* next;
} Node;
// 将字符串转换成链表
Node* stringToList(char* str) {
// ...(此处省略链表创建的具体代码)
}
// 判断链表是否回文
int isPalindrome(Node* node, Node* reversed) {
if (!node || !reversed) {
return node == reversed;
}
return node->data == reversed->data && isPalindrome(node->next, reversed->prev);
}
// 主函数测试
int main() {
char str[] = "madam";
Node* list = stringToList(str);
if (isPalindrome(list, list)) {
printf("'%s' is a palindrome.\n", str);
} else {
printf("'%s' is not a palindrome.\n", str);
}
free(list); // 清理内存
return 0;
}
```
这两种方法都可以判断输入的字符序列是否为回文,它们的主要区别在于处理方式,第一种更直观地利用了链表的特性,第二种则是通过递归来模拟栈操作。
阅读全文