完成回文判断函数的设计(要求同时使用顺序栈和顺序循环队列两种数据结构),并设计main函数进行测试,给出测试结果(huiwen.cpp)。设计思路
时间: 2024-05-11 12:17:24 浏览: 149
回文判断函数的设计可以使用顺序栈和顺序循环队列两种数据结构相结合的方式实现。具体思路如下:
1. 首先读入待判断的字符串,将字符串中的每个字符依次压入顺序栈中。
2. 然后再将每个字符依次插入到顺序循环队列的队尾中。
3. 从顺序栈中弹出字符,从顺序循环队列的队头取出字符,进行比较,如果不相等,则说明不是回文字符串,直接返回 false。
4. 如果顺序栈中的字符全部弹出并和顺序循环队列中的字符比较完毕,仍然没有发现不相等的字符,则说明是回文字符串,返回 true。
完整代码如下:
```c++
#include <iostream>
#include <cstring>
#define MAXSIZE 100
using namespace std;
// 顺序栈的定义
struct SqStack {
char data[MAXSIZE];
int top;
};
// 顺序循环队列的定义
struct SqQueue {
char data[MAXSIZE];
int front, rear;
};
// 初始化顺序栈
void InitStack(SqStack &S) {
S.top = -1;
}
// 判断顺序栈是否为空
bool IsEmptyStack(SqStack S) {
return S.top == -1;
}
// 入栈操作
bool Push(SqStack &S, char x) {
if (S.top == MAXSIZE - 1) {
return false;
}
S.data[++S.top] = x;
return true;
}
// 出栈操作
bool Pop(SqStack &S, char &x) {
if (S.top == -1) {
return false;
}
x = S.data[S.top--];
return true;
}
// 初始化顺序循环队列
void InitQueue(SqQueue &Q) {
Q.front = Q.rear = 0;
}
// 判断顺序循环队列是否为空
bool IsEmptyQueue(SqQueue Q) {
return Q.front == Q.rear;
}
// 入队操作
bool EnQueue(SqQueue &Q, char x) {
if ((Q.rear + 1) % MAXSIZE == Q.front) {
return false;
}
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1) % MAXSIZE;
return true;
}
// 出队操作
bool DeQueue(SqQueue &Q, char &x) {
if (Q.front == Q.rear) {
return false;
}
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MAXSIZE;
return true;
}
// 判断字符串是否为回文字符串
bool IsPalindrome(char str[]) {
SqStack S;
InitStack(S);
SqQueue Q;
InitQueue(Q);
int len = strlen(str);
for (int i = 0; i < len; i++) {
Push(S, str[i]);
EnQueue(Q, str[i]);
}
while (!IsEmptyStack(S) && !IsEmptyQueue(Q)) {
char c1, c2;
Pop(S, c1);
DeQueue(Q, c2);
if (c1 != c2) {
return false;
}
}
return true;
}
int main() {
char str[MAXSIZE];
cout << "请输入一个字符串:" << endl;
cin >> str;
if (IsPalindrome(str)) {
cout << "是回文字符串" << endl;
} else {
cout << "不是回文字符串" << endl;
}
return 0;
}
```
测试结果如下:
```
请输入一个字符串:
abccba
是回文字符串
```
```
请输入一个字符串:
hello
不是回文字符串
```
阅读全文