利用编程思维做题之判断回文字符串
1. 理解问题
我们需要设计一个程序来判断给定的字符串是否为回文字符串。回文字符串是指一个字符串与其逆序串相等。例如，“CSUSTSUSC”就是一个回文字符串。
2. 输入输出
- 输入：一个字符串。
- 输出：如果字符串是回文，打印“yes”；否则，打印“no”。
3. 数据结构
我们将使用顺序栈和链队列来实现该程序。栈用于保存字符串的字符，而队列用于逐个比较字符。
栈的定义：
#define MAX_SIZE 100
struct Stack {
char data[MAX_SIZE]; // 栈的元素
int top; // 栈顶指针
};
// 栈的初始化
void initStack(struct Stack* stack) {
stack->top = -1;
}
// 判栈空
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
// 入栈
void push(struct Stack* stack, char value) {
stack->data[++stack->top] = value;
}
// 出栈
char pop(struct Stack* stack) {
return stack->data[stack->top--];
}
队列的定义：
struct Node {
char data; // 队列的元素
struct Node* next; // 指向下一个节点的指针
};
struct Queue {
struct Node* front; // 队列前端
struct Node* rear; // 队列后端
};
// 队列的初始化
void initQueue(struct Queue* queue) {
queue->front = queue->rear = NULL;
}
// 判队空
int isQueueEmpty(struct Queue* queue) {
return queue->front == NULL;
}
// 入队
void enqueue(struct Queue* queue, char value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (isQueueEmpty(queue)) {
queue->front = queue->rear = newNode;
} else {
queue->rear->next = newNode;
queue->rear = newNode;
}
}
// 出队
char dequeue(struct Queue* queue) {
if (isQueueEmpty(queue)) return '\0'; // 返回空字符
struct Node* temp = queue->front;
char value = temp->data;
queue->front = queue->front->next;
free(temp);
return value;
}
4. 制定策略
- 使用栈：将字符串的每个字符压入栈中。
- 使用队列：将字符串的每个字符入队。
- 比较：从栈中出栈的字符和队列中出队的字符逐一比较，如果全部相等，则该字符串为回文。
5. 实现代码
5.1 完整 C 代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 100
// 栈的定义
struct Stack {
char data[MAX_SIZE]; // 栈的元素
int top; // 栈顶指针
};
// 栈的初始化
void initStack(struct Stack* stack) {
stack->top = -1;
}
// 判栈空
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
// 入栈
void push(struct Stack* stack, char value) {
stack->data[++stack->top] = value;
}
// 出栈
char pop(struct Stack* stack) {
return stack->data[stack->top--];
}
// 队列的定义
struct Node {
char data; // 队列的元素
struct Node* next; // 指向下一个节点的指针
};
struct Queue {
struct Node* front; // 队列前端
struct Node* rear; // 队列后端
};
// 队列的初始化
void initQueue(struct Queue* queue) {
queue->front = queue->rear = NULL;
}
// 判队空
int isQueueEmpty(struct Queue* queue) {
return queue->front == NULL;
}
// 入队
void enqueue(struct Queue* queue, char value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (isQueueEmpty(queue)) {
queue->front = queue->rear = newNode;
} else {
queue->rear->next = newNode;
queue->rear = newNode;
}
}
// 出队
char dequeue(struct Queue* queue) {
if (isQueueEmpty(queue)) return '\0'; // 返回空字符
struct Node* temp = queue->front;
char value = temp->data;
queue->front = queue->front->next;
free(temp);
return value;
}
// 判断字符串是否为回文
int isPalindrome(const char* str) {
struct Stack stack;
struct Queue queue;
initStack(&stack);
initQueue(&queue);
int length = strlen(str);
// 入栈和入队
for (int i = 0; i < length; i++) {
push(&stack, str[i]);
enqueue(&queue, str[i]);
}
// 比较
for (int i = 0; i < length; i++) {
if (pop(&stack) != dequeue(&queue)) {
return 0; // 不是回文
}
}
return 1; // 是回文
}
// 主程序
int main() {
const char* str = "CSUSTSUSC";
if (isPalindrome(str)) {
printf("yes\n");
} else {
printf("no\n");
}
return 0;
}
5.2 代码说明
- *isPalindrome(const char str)**：判断字符串是否为回文。利用栈和队列分别存储字符，然后比较它们。
- 主程序：调用判断函数并根据返回值输出结果。
5.3 模拟过程
以字符串 “CSUSTSUSC” 为例：
-
入栈和入队：
- 栈：[C, S, U, S, T, S, U, S, C]
- 队列：[C, S, U, S, T, S, U, S, C]
-
比较：
- 从栈出栈 C，队列出队 C，匹配。
- 从栈出栈 S，队列出队 S，匹配。
- 依此类推，直到比较完毕。
-
结果：
- 所有字符匹配，字符串为回文，输出“yes”。
6. 运行结果
对于输入字符串 “CSUSTSUSC”，运行结果为：yes。
7. 时间和空间复杂度分析
- 时间复杂度：O(n)，其中 n 为字符串的长度。我们遍历字符串的每个字符一次。
- 空间复杂度：O(n)，栈和队列各需存储字符串的每个字符。