利用编程思维做题之判断回文字符串
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),栈和队列各需存储字符串的每个字符。