算法设计题:假设称正读和反读都相同的字符序列为“回文”,例如,“abba”和“abcba”是回文,“abcde”和“ababab”则不是回文。利用栈和队列的知识,写一算法判别读入的一个以“@”为结束符的字符序列是否是“回文”。
时间: 2024-10-20 09:04:57 浏览: 6
要判断一个字符序列是否是回文,我们可以使用双指针策略,一个从前往后移动(称为左指针),另一个从后往前移动(称为右指针)。同时,我们还可以利用栈的数据结构,将遇到的字符依次压入栈中,然后遍历栈中的元素并与当前对应的字符进行比较。
以下是一个简单的C++算法实现:
```cpp
#include <iostream>
#include <stack>
#include <string>
bool isPalindrome(std::string str) {
std::stack<char> stack;
int left = 0, right = str.length() - 1;
// 将字符串后半部分的字符依次压入栈
while (right >= left) {
stack.push(str[right]);
right--;
}
// 检查栈顶元素与原字符串前半部分对应位置的字符是否相等
while (left < right) {
if (stack.top() != str[left]) {
return false; // 不是回文
}
stack.pop();
left++;
}
// 如果所有字符检查完毕,说明是回文
return true;
}
int main() {
std::string input;
std::cout << "请输入字符序列(以 '@' 结束):";
getline(std::cin, input);
if (input.back() == '@') {
input.pop_back(); // 移除结尾的 '@'
}
bool result = isPalindrome(input);
if (result) {
std::cout << "给定的字符序列是回文。\n";
} else {
std::cout << "给定的字符序列不是回文。\n";
}
return 0;
}
```
在这个程序中,我们首先用`isPalindrome`函数接收一个字符串,然后用两个指针`left`和`right`分别指向字符串的开头和结尾。当`right`大于等于`left`时,我们将`str[right]`压入栈中并移动`right`;当`left`小于`right`时,从栈顶取出一个字符并与`str[left]`比较。如果发现不匹配,则返回`false`,否则继续比较直到左右指针相遇,表示是回文。
阅读全文