栈和队列的基本操作实现及其应用

实验二栈和队列的基本操作实现及其应用

一_一、实验目的

1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。

一_二、实验内容

题目一、试写一个算法，判断依次读入的一个以@为结束符的字符序列，是否为回文。所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。

相关常量及结构定义：

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

typedef int SElemType;

typedef struct SqStack

{ SElemType *base;

SElemType *top;

int stacksize;

}SqStack;

设计相关函数声明：

判断函数：int IsReverse()

栈：int InitStack(SqStack &S )

int Push(SqStack &S, SElemType e )

int Pop(SqStack &S,SElemType &e)

int StackEmpty(s)

一_三、数据结构与核心算法的设计描述

1、初始化栈

/* 函数功能：对栈进行初始化。参数：栈(SqStack S)。

成功初始化返回0,否则返回-1 */

int InitStack(SqStack &S)

{

S.base=(SElemType *)malloc(10*sizeof(SElemType));

if(!S.base) //判断有无申请到空间

return -1; //没有申请到内存,参数失败返回-1

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

S.base=new SElemType;

return 0;

}

2、判断栈是否是空

/*函数功能:判断栈是否为空。参数; 栈(SqStack S)。栈为空时返回-1,不为空返回0*/

int StackEmpty(SqStack S)

{

if(S.top==S.base) return -1;

else return 0;

}

3、入栈

/*函数功能:向栈中插入元素。参数; 栈(SqStack S),元素(SElemtype e)。成功插入返回0,否则返回-1 */

int Push(SqStack &S,SElemType e)

{

if(S.top-S.base>=S.stacksize)

{

S.base=(SElemType *)realloc(S.base,(S.stacksize+1) * sizeof(SElemType));

//重新分配空间

if(!S.base) return -1;

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e; //插入操作

return 0;

}

4、出栈

/*函数功能:在栈中删除元素。参数;栈(SqStack S),元素(SElemtype e)。成功删除返回0,否则返回-1 */

int Pop(SqStack &S,SElemType &e)

{

if(S.top==S.base) return -1;

e=*--S.top; //删除操作

return 0;

}

5、判断是否为回文

/*函数功能:判断栈中的字符串是否为回文。参数; 栈(SqStack S)。是回文时返回1,否则返回0*/

int IsReverse(SqStack &S)

{

int i;

char a;

for(i=0;i

{

Pop(S,a);

if(a!=b[i]) return 0;

}

return 1;

}

一_四、函数的调用

主函数主要设计：

int lpp;

char ch;

SqStack p;

InitStack(p);

cout<<"请输入字符：";

while((ch=cin.get())&&ch!='@')

{

Push(p,ch);

b[j]=ch;

j++;

}

if (StackEmpty(p)==-1)

{

cout<<"此为空栈"<

return 0;

}

lpp=IsReverse(p);

if(lpp==0) cout<<"此字符串不是回文。"<

else cout<<"此字符串是回文。"<

一_五、实验总结

通过这次试验我熟悉了对栈的基本操作，对基本的栈操作有了很好的掌握，知道自己容易在什么地方出错，。

一_六、程序清单

#include

using namespace std;

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

char b[STACK_INIT_SIZE+STACKINCREMENT];

int j=0;

typedef char SElemType;

typedef struct SqStack

{ SElemType *base;

SElemType *top;

int stacksize;

}SqStack;

int InitStack(SqStack &S)

{

S.base=(SElemType *)malloc(10*sizeof(SElemType));

if(!S.base) return -1;

S.top=S.base;