題目

回文是指正讀反讀均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫(xiě)一個(gè)算法判定給定的字符序列是否為回文。（提示：將一半字符入棧）

算法思想

將字符串前一半入棧，然后，棧中元素和字符串后一半進(jìn)行比較。即將第一個(gè)出棧元素和后一半串中第一個(gè)字符比較，若相等，則再出棧一個(gè)元素與后一個(gè)字符比較，以此類推，直至棧空。

完整代碼

#include <iostream>
#include <string.h>
using namespace std;

//回文是指正讀反讀均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫(xiě)一個(gè)算法判定給定的字符序列是否為回文。（提示：將一半字符入棧） 

#define MAXSIZE 100    //順序棧存儲(chǔ)空間的初始分配量 
typedef int SElemType;
typedef struct{
    SElemType *base;   //棧底指針 
    SElemType *top;    //棧頂指針 
    int stacksize;     //?？捎玫淖畲笕萘?
}SqStack; 

//順序棧的初始化
void InitStack(SqStack &S){
    //構(gòu)造一個(gè)空棧 
    S.base = new SElemType[MAXSIZE];  //為順序棧動(dòng)態(tài)分配一個(gè)最大容量為MAXSIZE的數(shù)組空間 
    if(! S.base){
        //exit(OVERFLOW);               //存儲(chǔ)分配失敗 
    }
    S.top = S.base;                   //top初始為base，空棧 
    S.stacksize = MAXSIZE;            //stacksize置為棧的最大容量MAXSIZE 
    //return OK;
} 

//順序棧的出棧
char Pop(SqStack &S, SElemType e){
    //刪除S的棧頂元素，用e返回其值 
    if(S.top == S.base){               //?？?
        //return ERROR;
    } 
    e == *--S.top;                     //棧頂指針減1，將棧頂元素賦給e 
    return e;
} 

bool EmptyStack(SqStack S){
    if(S.top== 0)
    {
        return false;
    }
   else
   {
        return true;
   }
}

void Push(SqStack &S, SElemType e){
    //插入元素e為新的棧頂元素 
    if(S.top - S.base == S.stacksize){  //棧滿 
        //return ERROR;
    }
    *S.top ++ = e;                      //元素e壓入棧頂，棧頂指針加1 
    //return OK;
} 

int IsPalindrome(SqStack S, char *t)
{
    //判斷t字符向量是否為回文，若是，返回1，否則返回0 
    SElemType e;
    int flag = 1, temp;
    InitStack(S);
    int j = 1, len = strlen(t);           //求向量長(zhǎng)度 
    while(2 * j <= len){
        Push(S, *t);
        j ++;
        *t ++;
    }
    if(len % 2 == 1){
        *t ++;
    } 
    for(int k = j - 1; k >= 1; k --){
        temp = Pop(S,e);
        if(*t == e){
            *t ++;
        } 
        else{
            flag=0;
        } 
    }
    return flag;
}

int main(){
    char *t;
    SqStack S;
    t = "dahlagioa";
    if(IsPalindrome(S, t)){
        cout << "字符串" << t << "是回文" << endl;
    }
    else{
        cout << "字符串" << t << "不是回文" << endl;
    }
    return 0;
}

結(jié)果顯示

TIM圖片20191031102850.png