实验二栈和队列的基本操作实现及其应用一_一、实验目的1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。

一_二、实验内容题目一、试写一个算法，判断依次读入的一个以@为结束符的字符序列，是否为回文。

所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。

相关常量及结构定义：#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef 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; //没有申请到内存,参数失败返回-1S.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<j;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<<"此为空栈"<<endl;return 0;}lpp=IsReverse(p);if(lpp==0) cout<<"此字符串不是回文。

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

"<<endl;一_五、实验总结通过这次试验我熟悉了对栈的基本操作，对基本的栈操作有了很好的掌握，知道自己容易在什么地方出错，。

一_六、程序清单#include<iostream>using namespace std;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10char 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<j;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<<"此为空栈"<<endl;return 0;}lpp=IsReverse(p);if(lpp==0) cout<<"此字符串不是回文。

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

"<<endl;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;lpp=(QueuePtr)malloc(sizeof(QNode));if(!lpp) return -1;lpp->data=e; lpp->next=NULL;if(Q.front==NULL){Q.front->next=lpp;Q.rear=lpp;}else{Q.rear->next=lpp;Q.rear=lpp;}return 0;}3、出队列int DeQueue(LinkQueue &Q,QElemType &e) {QueuePtr lpp;if(Q.front==Q.rear) return -1;lpp=Q.front->next;e=lpp->data;Q.front->next=lpp->next;if(Q.rear==lpp) Q.rear=Q.front;delete lpp;return 0;}4、统计队列的长度int QueueLength(LinkQueue Q){QueuePtr lpp=Q.front;int i=0;while(lpp!=Q.rear){i++;lpp=lpp->next;}return i;}5、查找队列的某个元素int QueueFind(LinkQueue Q,QElemType e){QueuePtr p;p=Q.front->next;while(p){if(p->data==e)return 1;p=p->next;}return 0;}6、遍历队列int QueueTraverse(LinkQueue Q){QueuePtr p;p=Q.front->next;while(p){cout<<p->data<<'\t';p=p->next;}cout<<endl;return 0;}7、主界面函数void zhujiemian(){cout<<endl;cout<<"【\t\t 数据结构实验二】"<<endl;cout<<"【\t\t---------------------------------------------------------------------】"<<endl;cout<<"【\t\t 1 队列初始化】"<<endl;cout<<"【\t\t 2 出队列】"<<endl;cout<<"【\t\t 3 入队列】"<<endl;cout<<"【\t\t 4 队列长度】"<<endl;cout<<"【\t\t 5 在队列中查找元素】"<<endl;cout<<"【\t\t 6 遍历队列】"<<endl;cout<<"【\t\t 其他键退出】"<<endl;cout<<"【\t\t---------------------------------------------------------------------】"<<endl;cout<<"【\t\t 请选择要进行操作的序号（1--6）】:";}二_四、函数调用及主函数设计主函数主要涉及：LinkQueue Q;int a,b,c;zhujiemian();cin>>a;while(a!=1){cout<<"输入错误，必须先初始化，请重新输入：";cin>>a;}cout<<endl;do{switch(a){case 1:if(InitQueue(Q)==0)cout<<"初始化成功！"<<endl;elsecout<<"初始化失败！"<<endl;break;case 2:if(QueueLength(Q)==0){cout<<"队列为空无法出队！"<<endl;break;}if(DeQueue(Q,c)==0)cout<<"删除成功！"<<endl;elsecout<<"删除失败！"<<endl;break;case 3:cout<<"输入你要入队元素"<<endl;cin>>c;if(EnQueue(Q,c) ==0)cout<<"入队成功！"<<endl;elsecout<<"入队失败！"<<endl;break;case 4:b=QueueLength(Q);cout<<"队列的长度为："<<b<<endl;break;case 5:cout<<"您要查找的元素：";cin>>b;if(QueueFind(Q,b)==1)cout<<"恭喜您，队列中有您要找的元素"<<b<<endl;elsecout<<"不好意思，队列中没有您要找的元素"<<b<<endl;break;case 6:QueueTraverse(Q);break;default:break;}zhujiemian();cin>>a;cout<<endl;}while(a>0&&a<=6);说明：通过调用序列号不同的函数进行各种操作。