栈和队列算法设计题（一）

题目

回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符序列是否为回文。（提示：将一半字符入栈）

算法思想

将字符串前一半入栈，然后，栈中元素和字符串后一半进行比较。即将第一个出栈元素和后一半串中第一个字符比较，若相等，则再出栈一个元素与后一个字符比较，以此类推，直至栈空。

完整代码

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

//回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符序列是否为回文。（提示：将一半字符入栈） 

#define MAXSIZE 100    //顺序栈存储空间的初始分配量 
typedef int SElemType;
typedef struct{
    SElemType *base;   //栈底指针 
    SElemType *top;    //栈顶指针 
    int stacksize;     //栈可用的最大容量 
}SqStack; 

//顺序栈的初始化
void InitStack(SqStack &S){
    //构造一个空栈 
    S.base = new SElemType[MAXSIZE];  //为顺序栈动态分配一个最大容量为MAXSIZE的数组空间 
    if(! S.base){
        //exit(OVERFLOW);               //存储分配失败 
    }
    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);           //求向量长度 
    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;
}

结果显示

TIM图片20191031102850.png