栈和队列的基本操作实验报告.docx
《栈和队列的基本操作实验报告.docx》由会员分享，可在线阅读，更多相关《栈和队列的基本操作实验报告.docx（12页珍藏版）》请在冰点文库上搜索。
栈和队列的基本操作实验报告
《数据结构》
实
验
报
告
一
软件132
2
徐蜀
实验二栈和队列的基本操作及其应用
一、实验目的
1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。
2、掌握栈和队列的特点，即后进先出和先进先出的原则。
3、掌握栈和队列的基本运算，如：
入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。
二、实验内容
1．回文判断
三、实验要求
1、按照数据结构实验任务书，提前做好实验预习与准备工作。
2、加“*”题目必做，其他题目任选；多选者并且保质保量完成适当加分。
3、严格按照数据结构实验报告模板和规范，及时完成实验报告。
四、实验步骤
（说明：
依据实验内容分别说明实验程序中用到的数据类型的定义、主程序的流程以及每个操作（函数）的伪码算法、函数实现、程序编码、调试与分析。
附流程图与主要代码）
㈠、数据结构与核心算法的设计描述
（程序中每个模块或函数应加注释，说明函数功能、入口及出口参数）
1、栈的初始长度与需要再增加的长度
#defineSTACK_INIT_SIZE100;
#defineSTACKINCREMENT10;
typedefcharSElemType;//定义SElemType为char型
2、栈的顺序存储表示
typedefstruct
{
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
3、队列的链式表示方法
typedefstructQNode
{
SElemTypedata;
structQNode*next;
}QNode,*QueuePtr;
typedefstruct
{
QueuePtrfront;
QueuePtrrear;
}LinkQueue;
4、初始化栈
/*函数功能：
对栈进行初始化
参数：
栈（SqStack&S）
成功返回1，否则返回0*/
intInitStack（SqStack&S）
{
S.base=（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType））;
//申请内存
if（!
S.base）//判断有无申请到空间
returnERROR;//没有申请到内存，返回0
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}
5、入栈操作
/*函数功能：
将元素入栈
参数：
栈（SqStack&S）,插入元素e
插入成功返回1，否则返回0*/
intPush（SqStack&S,SElemTypee）
{
if（S.top-S.base>=S.stacksize）//判断栈顶与栈底的差是否大于栈的//容量
{
S.base=（SElemType*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（SElemType））;//栈满了，重新申请内存
if（!
S.base）//判断是否申请成功
returnERROR;//不成功返回0
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
returnOK;
}
6、出栈操作
/*函数功能：
将栈中的元素弹出
参数：
栈（SqStack&S）,记录元素e*/
intPop（SqStack&S,SElemType&e）
{
if（S.top==S.base）//判断栈是否为空
returnERROR;
e=*（--S.top）;
returnOK;
}
7、初始化队列
/*函数功能：
初始化队列
参数：
队列（LinkQueue&Q）
成功返回1，否则返回0*/
intInitQueue（LinkQueue&Q）
{
Q.front=Q.rear=（QueuePtr）malloc（sizeof（QNode））;
//申请结点的内存
if（!
Q.front）//判断有无申请到空间
returnERROR;//没有返回0
Q.front->next=NULL;
returnOK;
}
8.在队列队尾插入元素
/*函数功能：
在队列队尾插入元素
参数：
队列（LinkQueue&Q），插入元素e
成功返回1，否则返回0*/
intEnQueue（LinkQueue&Q,QElemTypee）
{
p=（QueuePtr）malloc（sizeof（QNode））;//申请新的结点
if（!
p）
returnERROR;
p->data=e;
p->next=NULL;
Q.rear->next=P;
Q.rear=p;
returnOK;
}
9.删除队头元素
/*函数功能：
删除对头元素
参数：
队列（LinkQueue&Q），记录值e
成功返回1，否则返回0*/
intDeQueue（LinkQueue&Q,QElemType&e）
{
if（Q.front==Q.rear）//判断队列是否为空
returnERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if（Q.rear==p）
Q.rear=Q.front;
free（p）;
returnOK;
}
10、主函数
intmain（）
{
SqStackS;//声明一个栈
LinkQueueQ;//声明一个队列
charm,k,c;
intn=0,i,j,t=0,z=0;
while（!
t）
{
cout<<"请输入你要判断回文的字符串，输入@结束：
";
InitQueue（Q）;
InitStack（S）;
while（（c=getchar（））!
='@'）//对字符的判断不断输入字符
{
EnQueue（Q,c）;
Push（S,c）;
n++;
}
for（j=1;j<=n;j++）
{
OutQueue（Q,m）;
Pop（S,k）;
if（m!
=k）
break;
}
if（j>n）//如果j>n则说明全部相等
cout<<"这个字符串不是回文字符串"<else
cout<<"这个字符串是回文字符串"<}
return0;
}
说明：
通过调用序列号不同的函数进行各种操作。
函数根据每次输入的数进行判断不在1—10内的函数将结束，否则将继续进行。
㈢程序调试及运行结果分析（应包含多组测试数据）
五、实验总结
通过这次试验，我知道自己还有很多不足，还会犯一些细节上的错误，但是也因此对栈和队列的操作有了很好的认识
附录
1
开始
、程序流程图
执行主函数main
声明一个栈S和队列Q
！
t
N
（c=getchar（））!
='@'
Y
N
Y
入栈入队列
j=1;j<=n;j++
N
出栈出队列，并判断值是否想等
Y
判断是否是回文数，并输出判断语句
结束
2、程序清单
#include
#include
usingnamespacestd;
//栈的表示和实现
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
#defineERROR0
#defineOK1
typedefcharSElemType;
typedefstruct
{
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
//队列的表示和实现
typedefstructQNode
{
SElemTypedata;
structQNode*next;
}QNode,*QueuePtr;
typedefstruct
{
QueuePtrfront;
QueuePtrrear;
}LinkQueue;
//关于栈的函数
intInitStack（SqStack&S）
{
S.base=（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType））;
if（!
S.base）
returnERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}
intPush（SqStack&S,SElemTypee）
{
if（S.top-S.base>=S.stacksize）
{
S.base=（SElemType*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（SElemType））;
if（!
S.base）
returnERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
returnOK;
}
intPop（SqStack&S,SElemType&e）
{
if（S.top==S.base）
returnERROR;
e=*（--S.top）;
returnOK;
}
//关于队列的函数
intInitQueue（LinkQueue&Q）
{
Q.front=Q.rear=（QueuePtr）malloc（sizeof（QNode））;
if（!
Q.front）
returnERROR;
Q.front->next=NULL;
returnOK;
}
intEnQueue（LinkQueue&Q,SElemTypee）
{
QueuePtrp=（QueuePtr）malloc（sizeof（QNode））;
if（!
p）
returnERROR;
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
returnOK;
}
intDeQueue（LinkQueue&Q,SElemType&e）
{
if（Q.front==Q.rear）
returnERROR;
QueuePtrp=Q.front->next;
e=p->data;
Q.front->next=p->next;
if（Q.rear==p）
Q.rear=Q.front;
free（p）;
returnOK;
}
//主函数
intmain（）
{
SqStackS;
LinkQueueQ;
charm,k,c;
intn=0,i,j,t=0,z=0;
while（!
t）
{
cout<<"请输入你要判断回文的字符串：
"<InitQueue（Q）;
InitStack（S）;
while（（c=getchar（））!
='@'）//对字符的判断不断输入字符
{
EnQueue（Q,c）;
Push（S,c）;
n++;
}
for（j=1;j<=n;j++）
{
DeQueue（Q,m）;
Pop（S,k）;
if（m!
=k）
break;
}
if（j>n）
cout<<"这个字符串是回文字符串"<else
cout<<"这个字符串不是回文字符串"<}
return0;
}
升级会员 