栈与队列基本操作实现附其应用.docxVIP

题目一 试写一个算法，判断依次读入的一个以@为结束符的字符序列，是否为回文。所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。 一、相关常量及结构定义： # define STACK_INIT_SIZE 100 # define STACKINCREMENT 10 # define OK 1 # define ERROR 0 typedef char SElemType; //把char类型定义为SElemType //栈类型定义 typedef struct SqStack { SElemType *base; //栈底 SElemType *top; //栈顶 int stacksize; //最大容量 }SqStack; //队列类型定义 typedef struct QNode { SElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; //队首 QueuePtr rear; //队尾 }LinkQueue; 二、设计相关函数声明： 判断函数： int IsReverse() 栈： int InitStack(SqStack S ) int Push(SqStack S, SElemType e ) int Pop(SqStack S,SElemType e) int StackEmpty(s) 队列； int initqueue(LinkQueue Q) int EnQueue(LinkQueue Q,SElemType e) int DeQueue(LinkQueue Q,SElemType e) 三、函数说明： 1、栈初始化 /* 函数功能：对栈进行初始化 参数：栈(SqStack S) 成功初始化返回1,否则返回0 */ int InitStack(SqStack S) { S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); //对栈申请空间。 if(!S.base) exit(0); //未申请空间退出。 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } 2、弹出栈顶元素，并返回 /* 函数功能：对栈删除栈顶元素 参数：栈SqStack S, 元素SElemType e 用e返回栈顶元素 */ int Pop(SqStack S,SElemType e) { if(S.top==S.base) //栈为空时返回错误。 return ERROR; e=*--S.top; //成功返回栈顶元素 return OK; } 3、向栈中压入元素 /* 函数功能：向栈中压入元素 参数：栈SqStack S, 元素SElemType e 成功压入返回1，否则返回0 */ int Push(SqStack S,SElemType e) { if(S.top-S.base=S.stacksize) //栈的大小过小时，从新申请内存 { S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base) exit(0); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++ = e; //成功压入元素。 return OK; } 4、栈是否为空 /* 函数功能：判断栈是否为空 参数：栈SqStack S 为空返回1，否则返回0 */ int StackEmpty(SqStack S) { if(S.top==S.base) //为空条件S.top=S.base return OK; else return ERROR; //不空返回0 } 5、队列初始化 /* 函数功能：对队列进行初始化 参数：队列(LinkQueue Q) 成功初始化返回1,否则返回0 */ int initqueue(LinkQueue Q) { Q.front=Q.rear=(Queu