通过“回文字算法”复习C++语言。

一、什么是回文字

给定一个字符串,从前往后读和从后往前读,字符串序列不变。例如,河北省农村信用社的客服电话是“96369”,无论从后往前读,还是从前后往后读,各个字符出现的位置不变。

二、功能实现

(一)、给定一个字符串,判断该字符串是否是回文字。

(二)、给定一个任意字符串,判断是否可以转换为回文字,如果可以转换为回文字,给出具体的算法。

三、C++语言实现版本(JAVA语言版本后续实现)

(一)头文件 (BackText.h)

/*
* BackText.h
*
* Created on: 2016年9月30日
* Author: gaodianhua
*/
#include <string>
#include <cstring>
#include <map>
#ifndef BACKTEXT_H_
#define BACKTEXT_H_
using namespace std;

class BackText {
  string text;
  map<char,int> mapBychar;
  int checksum;
  public:
  BackText();
  BackText(char str[]);
  BackText(string text);
  virtual ~BackText();
  bool isBackText();
  void print() const;
  void countDiffCh();
  void convert(char * dest);

};

#endif /* BACKTEXT_H_ */

(二)类的实现

/*
* BackText.cpp
*
* Created on: 2016年9月30日
* Author: gaodianhua
*/

#include "BackText.h"
#include <iostream>
#include <string>
#include <iterator>
#include <cstring>
#include <cstdlib>
#include <map>

using namespace std;

BackText::BackText() {
}

BackText::~BackText() {
  this->checksum=0;
}

BackText::BackText(char *str){
  this->text=str;
  this->checksum=0;
}

BackText::BackText(string str){
  this->text=str;
  this->checksum=0;
}

bool BackText::isBackText(){
  string::iterator it1,it2;
  it1=text.begin();

  it2=text.end()-1;
  for(;it1<=it2;it1++,it2--){
    if(*it1!=*it2)
    return false;
  }
  return true;
}

void BackText::print() const{
  cout<<this->text<<endl;
}

void BackText::countDiffCh(){
  string::iterator it1,it2;
  string temp;
  temp.clear();
  int index=0;
  for(it1=text.begin();it1<text.end();it1++){
    if( strchr(temp.data(),*it1)==NULL ){
      temp.insert(index,1,*it1);
      index++;
    }
  }
  for( it2=temp.begin();it2<temp.end();it2++){
    int count=0;
    for(it1=text.begin();it1<text.end();it1++){
      if(*it1==*it2){
        count++;
        checksum++;
      }
    }
    mapBychar.insert(pair<char,int>(*it2,count));
  }

  map<char,int>::iterator m;
  for(m=mapBychar.begin( );m != mapBychar.end( ); m++ )
    cout <<m->first<<" "<<m->second<<endl;
}

void BackText::convert(char* dest){
  if(isBackText()){
    strcpy(dest,text.data());
    return;
  }
  int cnt=0;
  map<char,int>::iterator m;
  for(m=mapBychar.begin( );m != mapBychar.end( ); m++ ){
    if(m->second%2!=0){
      cnt++;
    }
  }
  if(cnt>1){
    cout<<"该字符串不能被转化为回文字"<<endl;
    return;
  }
  cout<<"开始转换..."<<endl;
  int begIndex=0;
  int endIndex=checksum-1;
  bool oddflag=0;
  char oddchar;
  for(m=mapBychar.begin( );m != mapBychar.end( ); m++ ){
    if( checksum % 2 == 0 ){
      for( int i=0; i< m->second/2; i++ ){
        dest[begIndex++]=m->first;
        dest[endIndex--]=m->first;
      }
    }else{
      if(m->second % 2 == 0){
        for( int i=0; i< m->second/2 ; i++ ){
          dest[begIndex++]=m->first;
          dest[endIndex--]=m->first;
        }
      }else{
        oddchar=m->first;
        oddflag=true;
        continue;
      }
    }
  }
  if(oddflag){
    map<char,int>::iterator it;
    it=mapBychar.find(oddchar);
    if(it==mapBychar.end()){
      cout<<"do not find "<< oddchar <<endl;
      return;
    }
    for( int i=0; i< it->second; i++ ){
      dest[begIndex++]=it->first;
    }
  }
}

(三)main函数

/*
* main.cpp
*
* Created on: 2016年9月30日
* Author: gaodianhua
*/
#include <iostream>
#include "BackText.h"
#include <cstdlib>
#include <string>
using namespace std;
int main(){
  string text;
  text.clear();
  cout<<"请输入字符串:";
  cin>>text;
  BackText bt=BackText(text);
  bt.print();
  if( !bt.isBackText() )
  cout<<"不是回文字符串"<<endl;
  bt.countDiffCh();
  char dest[100];
  memset(dest,0x0,sizeof(dest));
  bt.convert(dest);
  cout<<dest<<endl;
  return 0;
}

上一篇:集合和String


下一篇:javaweb学习总结十六(tomcat服务器的使用、虚拟目录的映射)