栈和队列的基本操作实现及其应用资料.doc

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

精品资料
实验 二 栈和队列的基本操作实现及其应用
一_一、实验目的
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<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 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<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;
else
cout<<"初始化失败！"<<endl;
break;
case 2:
if(QueueLength(Q)==0)
{
cout<<"队列为空无法出队！"<<endl;
break;
}
if(DeQueue(Q,c)==0)
cout<<"删除成功！"<<endl;
else
cout<<"删除失败！"<<endl;
break;
case 3:
cout<<"输入你要入队元素"<<endl;
cin>>c;
if(EnQueue(Q,c) ==0)
cout<<"入队成功！"<<endl;
else
cout<<"入队失败！"<<endl;
break;
case 4:
b=QueueLength(Q);
cout<<"队列的长度为："<<b<<endl;
break;
case 5:
cout<<"您要查找的元素：";
cin>>b;
if(QueueFind(Q,b)==1)
cout<<"恭喜您，队列中有您要找的元素"<<b<<endl;
else
cout<<"不好意思，队列中没有您要找的元素"<<b<<endl;
break;
case 6:
QueueTraverse(Q);
break;
default:
break;
}
zhujiemian();
cin>>a;
cout<<endl;
}while(a>0&&a<=6);
说明：
通过调用序列号不同的函数进行各种操作。函数根据每次输入的数进行判断不在1—6内的函数将结束，否则将继续进行。
二_五、程序调试及运行结果分析
程序第一步必须执行初始化，否则程序不能运行。
在程序第一步必须执行初始化后，程序完美运行，在进行任何函数操作程序都是正常运行，而且本程序对插入和删除时进行错误检测如有的地方不可以插入，有点地方不能删除，如果队列为空时则程序会输出队列为空，并继续进行其他操作，大大减少了程序的bug。
二_六、程序清单
#include<iostream>
using namespace std;
typedef int QElemType;
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
int count;
}LinkQueue;
int InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front) return -1;
Q.front->next=NULL;
return 0;
}
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;
}
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;
}
int QueueLength(LinkQueue Q)
{
QueuePtr lpp=Q.front;
int i=0;
while(lpp!=Q.rear)
{
i++;
lpp=lpp->next;
}
return i;
}
int QueueTraverse(LinkQueue Q)
{
QueuePtr p;
p=Q.front->next;
while(p)
{
cout<<p->data<<'\t';
p=p->next;
}
cout<<endl;
return 0;
}
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;
}
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） 】:";
}
int main()
{
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;
else
cout<<"初始化失败！"<<endl;
break;
case 2:
if(QueueLength(Q)==0)
{
cout<<"队列为空无法出队！"<<endl;
break;
}
if(DeQueue(Q,c)==0)
cout<<"删除成功！"<<endl;
else
cout<<"删除失败！"<<endl;
break;
case 3:
cout<<"输入你要入队元素"<<endl;
cin>>c;
if(EnQueue(Q,c) ==0)
cout<<"入队成功！"<<endl;
else
cout<<"入队失败！"<<endl;
break;
case 4:
b=QueueLength(Q);
cout<<"队列的长度为："<<b<<endl;
break;
case 5:
cout<<"您要查找的元素：";
cin>>b;
if(QueueFind(Q,b)==1)
cout<<"恭喜您，队列中有您要找的元素"<<b<<endl;
else
cout<<"不好意思，队列中没有您要找的元素"<<b<<endl;
break;
case 6:
QueueTraverse(Q);
break;
default:
break;
}
zhujiemian();
cin>>a;
cout<<endl;
}while(a>0&&a<=6);
return 0;
}
仅供学习与交流，如有侵权请联系网站删除 谢谢16