C++实现回文串算法思想 |21xrx.com

C++实现回文串算法思想

2023-07-10 11:35:04 深夜i -- --

C++ 回文串算法实现思想字符串处理

回文串是指正序和倒序都一样的字符串，比如“level”、“racecar”等。在编程中，判断一个字符串是否为回文串是一项常见的任务。而C++作为一门高级编程语言，提供了多种方法来实现回文串算法思想。

首先，可以利用普通的字符串比较函数来判断回文串。具体的实现步骤如下：

1. 读入待判断的字符串。

2. 利用字符串长度和循环控制条件，对字符串进行遍历。

3. 以字符串中心点为基准，比较左右两侧的字符是否相同。

4. 如果左右两侧的字符不相同，则该字符串不是回文串；如果比较完了所有字符，左右两侧的字符都相同，则该字符串是回文串。

代码实现如下：


#include <iostream>
#include <cstring>
using namespace std;
int main() {
  char s[100];
  bool flag = true;
  cin >> s;
  int len = strlen(s);
  for (int i = 0; i < len / 2; i++) {
    if (s[i] != s[len - i - 1])
      flag = false;
      break;
    
  }
  if (flag) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

第二种方法是利用C++中的STL容器——栈，对字符串进行处理。具体的实现步骤如下：

1. 读入待判断的字符串。

2. 建立一个栈，将字符串的前一半字符一次压入栈中。

3. 如果字符串长度为奇数，则将中间的字符跳过。

4. 对字符串后一半的字符依次和栈中元素进行比较，如果不相等就说明该字符串不是回文串；如果相等，就弹出栈中的元素继续比较。

5. 如果比较完了所有字符，栈仍然不为空，则说明该字符串不是回文串；如果比较完了所有字符，栈为空，则说明该字符串是回文串。

代码实现如下：


#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
int main() {
  char s[100];
  stack<char> st;
  cin >> s;
  int len = strlen(s);
  for (int i = 0; i < len / 2; i++) {
    st.push(s[i]);
  }
  int i = (len % 2 == 0) ? len / 2 : len / 2 + 1;
  for (; i < len; i++) {
    if (st.top() != s[i])
      cout << "No" << endl;
      return 0;
    
    st.pop();
  }
  cout << "Yes" << endl;
  return 0;
}

最后，可以使用C++中的STL容器——字符串，对字符串进行处理。具体实现步骤如下：

1. 读入待判断的字符串。

2. 利用字符串自带的反转函数，将字符串反转后和原字符串比较，如果相等则说明该字符串是回文串；否则不是。

代码实现如下：


#include <iostream>
#include <cstring>
using namespace std;
int main() {
  string s;
  cin >> s;
  string s2 = s;
  reverse(s.begin(), s.end());
  if (s == s2) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

综上所述，以上三种方法都可以有效地实现回文串算法思想，在实际的编程中可以根据需要选择。

上一篇: idea打包java可执行jar包

下一篇: C++实验：一元多项式相加

评论区

()

相似文章