栈和队列的基本操作实现及其应用
- 格式:doc
- 大小:47.00 KB
- 文档页数:15
实验二栈和队列的基本操作实现及其应用
一_一、实验目的
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)
{
=(SElemType *)malloc(10*sizeof(SElemType));
if(! //判断有无申请到空间
return -1; //没有申请到内存,参数失败返回-1
=;
=STACK_INIT_SIZE;
=new SElemType;
return 0;
}
2、判断栈是否是空
/*函数功能:判断栈是否为空。参数; 栈(SqStack S)。栈为空时返回-1,不为空返回0*/
int StackEmpty(SqStack S)
{
if== return -1;
else return 0;
}
3、入栈
/*函数功能:向栈中插入元素。参数; 栈(SqStack S),元素(SElemtype e)。成功插入返回0,否则返回-1 */
int Push(SqStack &S,SElemType e)
{
if {
=(SElemType *)realloc,+1) * sizeof(SElemType));
//重新分配空间
if(! return -1;
=+;
+=STACKINCREMENT;
}
*++=e; //插入操作
return 0;
}
4、出栈
/*函数功能:在栈中删除元素。参数;栈(SqStack S),元素(SElemtype e)。成功删除返回0,否则返回-1 */
int Pop(SqStack &S,SElemType &e)
{
if== return -1;
e=*; //删除操作
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=())&&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) { =(SElemType *)malloc(10*sizeof(SElemType)); if(! return -1; =; =STACK_INIT_SIZE; =new SElemType; return 0; } int StackEmpty(SqStack S) { if== return -1; else return 0; } int Push(SqStack &S,SElemType e) { if { =(SElemType *)realloc,+1) * sizeof(SElemType)); if(! return -1;