栈和队列的基本操作实现及其应用
实验二栈和队列的基本操作实现及其应用
一_一、实验目的
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; 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) { 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; } int Pop(SqStack &S,SElemType &e) { if(S.top==S.base) return -1; e=*--S.top; return 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 main() { 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<<"此字符串是回文。"< return 0; } 二_一、实验目的 2、会用栈和队列解决简单的实际问题。 二_二、实验内容 题目二、编程模拟队列的管理，主要包括：出队列、入队、统计队列的长度、查找队列某个元素e、及输出队列中元素。 相关常量及结构定义： typedef int QElemType; typedef struct QNode { QElemType data; struct QNode *next; }QNode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; int count; }LinkQueue; 设计相关函数声明： InitQueue(LinkQueue &Q) EnQueue(LinkQueue &Q,QElemType e) DeQueue(LinkQueue &Q,QElemType &e) QueueLength(LinkQueue Q) QueueTraverse(LinkQueue Q) QueueFind(LinkQueue Q,QElemType e) 二_三、数据结构与核心算法的设计描述1、初始化队列 int InitQueue(LinkQueue &Q) { Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front) return -1; Q.front->next=NULL; return 0; } 2、入队列 int EnQueue(LinkQueue &Q,QElemType e) { QueuePtr lpp;