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

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

一_一、实验目的

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)

- 1 -

{ }

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)

- 2 -

{ }

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

一_四、函数的调用

主函数主要设计：

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; }

- 3 -

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; S.stacksize=STACK_INIT_SIZE; S.base=new SElemType; return 0; }

int StackEmpty(SqStack S) { if(S.top==S.base) return -1; else return 0; }

int Push(SqStack &S,SElemType e) { if(S.top-S.base>=S.stacksize) {

- 4 -