习题3.2

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

【算法思想】
将字符串前一半入栈，然后，栈中元素和字符串后一半进行比较。即将第一个出栈元素和后一半串中第一个字符比较,若相等，则再出栈一个元素与后一个字符比较，以此类推，直至栈空,在这种情况下可判定该字符序列是回文。如果出栈元素与串中的字符进行比较时出现不等的情况,则可判定该字符序列不是回文。

完整代码：

若输出1，则为回文，输出0则不是

#include <iostream>
#include <string.h>
using namespace std;
typedef int Status;
typedef char TypeStack;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAX 100  //栈空间初始大小

int readchar(char *t);


//顺序栈
typedef struct SqStack 
{
	TypeStack* top;//栈顶指针
	TypeStack* base; //栈底指针
	int size;//当前栈空间的大小
}SqStack;
int ISPalindrom(SqStack &S,char t[],int len);

bool EmptyStack(SqStack S)
{

if(S.top==S.base)

return true ;

else return false ;

}

Status InitStack(SqStack &S)
{
    S.base=new TypeStack[MAX];
    if(!S.base) exit(OVERFLOW);
    S.top=S.base;
    S.size=MAX;
    return OK;
}

Status push(SqStack &S,TypeStack e)
{
    if(S.top-S.base==S.size)
    {
        cout<< "栈满！" << endl;
        return ERROR;
    }
    *S.top=e;
    *S.top++;
    return OK;

}

Status Pop(SqStack &S,TypeStack &e)
{
    if(S.top==S.base) 
    {
        cout<< "栈为空" << endl;
		return ERROR;
    }
    *--S.top;
    e=*S.top;
    return OK;
}

TypeStack GetTop(SqStack S)
{
    if(S.top!=S.base)
    return *(S.top-1);
}

Status PrintStack(SqStack S)
{
    TypeStack *x=S.base;
    while(x<S.top)
    {   
        cout<<*x<<" ";
        x++;

    }
    return OK;
}

Status somepush(SqStack &S)
{
    int num;
    int i=0;
    TypeStack n;
    cout << "输入元素个数n,初始化栈" << endl;
	cin >> num;
	cout << "请依次输入元素:" << endl;
    while(1)
    {
        cin>>n;
        push(S,n);
        i++;
        if(i==num) break;
    }
}
int main()
{   
    int len;
   char t[100];
   SqStack S;
   InitStack(S);
   int x=0;
    len=readchar(t);
    x=ISPalindrom(S,t,len);
    cout<<endl;
    cout<<x;


return 0;
}

int ISPalindrom(SqStack &S,char t[],int len)
{
    
    int i=0;
    char temp;
    

    for(i=0;i<len/2;i++)
    {push(S,t[i]);
    
    }

    if(len%2!=0)
    i++;
    while(!EmptyStack(S))
    {
        Pop(S,temp);
        
        if(temp!=t[i])
        return 0;
        else
        i++;
    }
    return 1;
}

int readchar(char *t)
{
   
   int i=0,num=0;
   char c;
   while (1)
   {
     t[i]=cin.get(); 
     
     i++;
     if(t[i-1]=='\n')
     {
        i--;
        break;
     }
     
   }
    num=i-1;
    return i;

}