#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status;
typedef int ElemType;
typedef int ElemType;
Status Palindrome(char *word);
typedef struct{
ElemType*base;
ElemType*top;
int stacksize;
}SqStack;
Status InitStack(SqStack&S){
S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType))
if(!S.base)exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return(OK);
}
Status Push(SqStack &S, ElemType e){
//插入e为栈顶元素
if(S.top-S.base==S.stacksize){//栈满则应重新分配空间
S.base=(ElemType *)
realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base)exit(OVERFLOW);
S.top=(S.base+S.stacksize);//使得S.top重新指向栈顶,因realloc
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
//top指向待插入位置
return(OK);
}//Push ,复杂度O(1)
Status Pop(SqStack &S,ElemType &e){
//若栈不空则栈顶元素出栈并用e带回其值
if(S.top==S.base)return ERROR;
e=*(--S.top);
//栈顶元素为*(S.top-1)
return OK;
} //复杂度O(1)
Status StackEmpty(SqStack S)
{if(S.top==S.base)return TRUE;else return FALSE;}
int StackLength (SqStack S)
{ return (S.top-S.base); }
Status GetTop(SqStack S,
ElemType &e){
{
if(S.top==S.base)return ERROR;
e=*(S.top-1);
//注意top指向待插入位置
return OK;
}
typedef struct QNode {
ElemType
data;
struct QNode
*next;
} QNode, *QueuePtr;
typedef struct {
QueuePtr
front;//队头指针
QueuePtr
rear; //队尾指针
} LinkQueue;// 链队列
Status InitQueue (LinkQueue &Q) {
// 构造一个空队列Q
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if (!Q.front) exit (OVERFLOW);
Q.front->next = NULL;
//莫忘!!
return OK;
}//时间复杂度O(1)
Status EnQueue (LinkQueue &Q, ElemType e) {
// 插入元素e为Q的新的队尾元素
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if (!p)exit(OVERFLOW);//存储分配失败
p->data = e;
p->next = NULL;//莫忘!!
Q.rear->next = p;
Q.rear = p;
return OK;
}//复杂度O(1)
Status DeQueue (LinkQueue &Q, ElemType &e) {
// 若队列不空,则删除Q的队头元素,用 e 返回其“值”
if (Q.front ==Q.rear) return ERROR;//空队列
QueuePtr p= Q.front->next;
e = p->data;
Q.front->next = p->next;
if(Q.rear == p) Q.rear = Q.front;//只1个结点时改尾指针
free (p);
return OK;
}//复杂度O(1)
Status DestroyQueue (LinkQueue &Q) {
//销毁队列Q,此处不同于教材,先清空元素结点,后释放头结点
QueuePtr p=Q.front->next;
while(p){//依次释放首元素至最后一个元素
Q.front->next=p->next;free(p);p=Q.front->next;
}
free(Q.front);
Q.front=NULL;Q.rear=NULL;
return OK;
}//类此可写置空操作, 复杂度O(n)
Status Palindrome(char *word)
//算法思路:利用栈后进先出和队列先进先出的特点。分别将字符序列存到栈和队列里面。
//分别从栈和队列里面输出字符序列,并经行比较若始终相同,则字符序列word是回文。
//否则不是回文。
{
char a,b,*p;
Stack S;
Queue Q;
InitStack(S);
InitQueue(Q);
for(p=word;p&&*p!='@';p++)
{
Push(S,*p);EnQueue(Q,*p);
}
while(!StackEmpty(S))
{
Pop(S,a);
DeQueue(Q,b);
if(a!=b) return ERROR;
}
return OK;
}
int main(){
}
//刚刚忙出来,主函数楼主自己写吧。。。