实验二栈队列地实现与应用.docx
《实验二栈队列地实现与应用.docx》由会员分享，可在线阅读，更多相关《实验二栈队列地实现与应用.docx（20页珍藏版）》请在冰点文库上搜索。
实验二栈队列地实现与应用
实验二栈、队列的实现及应用
实验课程名：
数据结构与算法
专业班级：
学号：
：
实验时间：
实验地点：
指导教师：
珊
一、实验目的
1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。
2、掌握栈和队列的特点，即先进后出与先进先出的原则。
3、掌握栈和队列的基本操作实现方法。
二、实验容
一、实验目的及要求
1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。
2、掌握栈和队列的特点，即先进后出与先进先出的原则。
3、掌握栈和队列的基本操作实现方法。
二、实验学时
2学时
三、实验任务
任务一：
（1）实现栈的顺序存储
（2）实现栈的链式存储。
任务二：
实现顺序存储的循环队列，完成键盘缓冲区的功能。
四、实验重点、难点
1.进栈、出栈栈顶指针都要改变。
2.队空、队满的条件及入队、出队时指针的变更。
五、操作容与要求
1.任务一
（1）：
完成下列程序，该程序实现栈的顺序存储结构，构建顺序栈（栈中的元素依次为R，S，Y，F，C，T），依次进行进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。
要求生成顺序栈时，从键盘上读取数据元素。
（1）源代码：
#include
#include
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
#defineOK1
#defineERROR0
typedefcharSElemType;
/*顺序栈的存储类型*/
typedefstruct//definestructureSqStack（）
{
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
/*构造空顺序栈*/
intInitStack（SqStack*S）//InitStack（）sub-function
{
S->base=（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType））;
if（!
S->base）
{
printf（"分配空间失败!
\n"）;
return（ERROR）;
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
printf（"栈初始化成功！
\n"）;
return（OK）;
}//InitStack（）end
/*取顺序栈顶元素*/
intGetTop（SqStack*S,SElemType*e）//GetTop（）sub-function
{
if（S->top==S->base）
{
printf（"栈为空!
\n"）;//ifemptySqStack
return（ERROR）;
}
*e=*（S->top-1）;
return（OK）;
}//GetTop（）end
/*将元素压入顺序栈*/
intPush（SqStack*S）//Push（）sub-function
{
SElemTypee;
if（S->top-S->base>S->stacksize）
{
S->base=（SElemType*）realloc（S->base,（S->stacksize+
STACKINCREMENT*sizeof（SElemType）））;
if（!
S->base）
{
printf（"存储空间分配失败!
\n"）;
return（ERROR）;
}
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
fflush（stdin）;//清除输入缓冲区，否则原来的输入会默认送给变量x
printf（"请输入要入栈的元素的值:
"）;
e=getchar（）;
*S->top++=e;
return（OK）;
}//Push（）end
/*将元素弹出顺序栈*/
intPop（SqStack*S,SElemType*e）//Pop（）sub-function
{
if（S->top==S->base）
{
printf（"栈为空!
\n"）;
return（ERROR）;
}
*e=*--S->top;
return（OK）;
}//Pop（）end
voiddisplay（SqStack*s）
{
if（s->top==s->base）
printf（"栈为空!
\n"）;
else{
while（s->top!
=s->base）
{
s->top=s->top-1;
printf（"%c->",*（s->top））;
}
}
printf（"\n"）;
}
intmain（）
{
intchoice;
SElemTypee;
SqStacks;
do
{
printf（"===============================\n"）;
printf（"0:
退出\n"）;
printf（"1:
初始化栈\n"）;
printf（"2:
入栈\n"）;
printf（"3:
出栈\n"）;
printf（"4:
读取栈顶元素\n"）;
printf（"5:
显示栈中元素\n"）;
printf（"===============================\n"）;
printf（"输入操作选择代码（0-5）:
"）;
scanf（"%d",&choice）;
while（choice<0||choice>5）{printf（"输入有误，请重新输入（0-5）:
"）;scanf（"%d",&choice）;}
switch（choice）
{
case0:
exit
（1）;
case1:
InitStack（&s）;break;
case2:
printf（"2\n"）;Push（&s）;break;
case3:
Pop（&s,&e）;printf（"出栈元素的值是:
%c\n",e）;break;
case4:
GetTop（&s,&e）;printf（"栈顶元素的值是:
%c\n",e）;break;
case5:
printf（"栈中元素的值是为：
\n"）;display（&s）;break;
}
}while（choice）;
return0;
}
（2）运行结果
（3）结果分析
顺序表通过设置栈顶运用线性结构实现先进先出功能。
2.任务一
（2）：
完成下列程序，该程序实现栈的链式存储结构，构建链栈（栈中的元素依次为China，Japan，France，India，Australia），依次进行进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。
要求生成链栈时，从键盘上读取数据元素。
（1）源代码：
#include
#include
#include
#defineOK1
#defineERROR0
typedefcharDataType;
/*链式栈的存储类型*/
typedefstructSNode//definestructureLinkStack
{DataTypedata[20];
structSNode*next;
}SNode,*LinkStack;
voidInitStack_L（LinkStack*top）
{
top=（LinkStack）malloc（sizeof（SNode））;
top->next=NULL;
printf（"\n\n栈初始化成功！
\n\n"）;
}
/*取链式栈顶元素*/
intGetTop_L（LinkStack*top,DataTypee[]）//GetTop_L（）sub-function
{if（!
top->next）
{printf（"链栈为空!
\n"）;
return（ERROR）;
}
else
{strcpy（e,top->next->data）;
return（OK）;
}
}//GetTop_L（）end
/*将元素压入链式栈*/
intPush_L（LinkStack*top）//Push_L（）sub-function
{SNode*q;
DataTypee[20];
q=（LinkStack）malloc（sizeof（SNode））;
if（!
q）
{printf（"存储空间分配失败!
\n"）;
return（ERROR）;
}
fflush（stdin）;//清除输入缓冲区，否则原来的输入会默认送给变量e
printf（"\n请输入要入栈的元素的值:
"）;
gets（e）;
strcpy（q->data,e）;
q->next=top->next;
top->next=q;
return（OK）;
}//Push_L（）end
/*将元素弹出链式栈*/
intPop_L（LinkStack*top,DataTypee[]）//Pop_L（）sub-function
{SNode*q;
if（!
top->next）
{printf（"链栈为空!
\n"）;
return（ERROR）;
}
strcpy（e,top->next->data）;
q=top->next;
top->next=q->next;
free（q）;
return（OK）;
}//Pop_L（）end
voiddisplay（LinkStack*top）
{
LinkStackp=top->next;
if（!
p）
printf（"栈为空!
\n"）;
else{
while（p）
{
printf（"%s->",p->data）;
p=p->next;
}
}
printf（"^\n"）;
}
intmain（）
{
charchoice;
DataTypee[20]="";
LinkStacks=NULL;
do
{
printf（"===============================\n"）;
printf（"0:
退出\n"）;
printf（"1:
初始化栈\n"）;
printf（"2:
入栈\n"）;
printf（"3:
出栈\n"）;
printf（"4:
读取栈顶元素\n"）;
printf（"5:
显示栈中元素\n"）;
printf（"===============================\n"）;
printf（"输入操作选择代码（0-5）:
"）;
fflush（stdin）;
scanf（"%c",&choice）;
while（choice<'0'||choice>'5'）
{
printf（"输入有误，请重新输入（0-5）:
"）;
fflush（stdin）;
scanf（"%c",&choice）;
}
switch（choice）
{
case'0':
exit
（1）;
case'1':
InitStack_L（&s）;break;
case'2':
Push_L（&s）;break;
case'3':
Pop_L（&s,e）;break;
case'4':
GetTop_L（&s,e）;printf（"栈顶元素的值是:
%s\n",e）;break;
case'5':
printf（"栈中元素的值是:
"）;display（&s）;
}
}while（choice）;
return0;
}
（2）运行结果
（3）结果分析
链表通过设置栈顶运用指针实现先进先出功能
3.任务二：
完成下列程序，该程序实现循环队列的存储和基本操作，构建循环队列，完成键盘缓冲区的功能，每输入一个字符，链入缓冲区队列中；每输出一个字符，将该字符从缓冲区中删除。
（1）源代码：
#include
#include
#defineMAXQSIZE100
#defineOK1
#defineERROR0
/*定义QElemType为int或别的自定义类型*/
typedefcharQElemType;
/*顺序队列的存储类型*/
typedefstructSqQueue//definestructureSqQueue
{QElemType*base;
intfront;
intrear;
}SqQueue;
/*构造空顺序队列*/
intInitQueue（SqQueue*Q）//InitQueue（）sub-function
{Q->base=（QElemType*）malloc（MAXQSIZE*sizeof（QElemType））;
if（!
Q->base）
{printf（"分配空间失败!
\n"）;
return（ERROR）;
}
Q->front=Q->rear=0;
printf（"队列初始化成功!
\n"）;
return（OK）;
}//InitQueue（）end
/*求顺序队列长度*/
intQueueLength（SqQueue*Q）//QueueLength（）sub-function
{return（（Q->rear-Q->front+MAXQSIZE）%MAXQSIZE）;
}
/*在顺序队列尾插入新元素*/
intEnQueue（SqQueue*Q,QElemTypee）//EnQueue（）sub-function
{if（（Q->rear+1）%MAXQSIZE==Q->front）
{printf（"队列已满!
\n"）;
return（ERROR）;
}
Q->base[Q->rear]=e;
Q->rear=（Q->rear+1）%MAXQSIZE;
return（OK）;
}//EnQueue（）end
/*在顺序队列头删除旧元素*/
intDeQueue（SqQueue*Q,QElemTypee）//DeQueue（）sub-function
{if（Q->front==Q->rear）
{printf（"队列为空!
\n"）;
return（ERROR）;
}
e=Q->base[Q->front];
Q->front=（Q->front+1）%MAXQSIZE;
return（OK）;
}//DeQueue（）end
voiddisplay（SqQueue*Q）{
if（Q->front==Q->rear）
printf（"队列为空!
\n"）;
inti=Q->front;
while（（i+1）%MAXQSIZE!
=Q->rear）
{
printf（"%c->",Q->base[i]）;
i++;
}
printf（"^\n"）;
}
intmain（）
{
QElemTypee;
intchoice;
SqQueueQ;
InitQueue（&Q）;
printf（"==============================\n"）;
printf（"0、退出\n"）;
printf（"1、入队\n"）;
printf（"2、出队\n"）;
printf（"3、显示队列元素\n"）;
printf（"==============================\n"）;
do
{
printf（"你操作选择是（0-3）:
"）;
scanf（"%d",&choice）;
switch（choice）
{
case1:
fflush（stdin）;//清除输入缓冲区
printf（"请输入要入队的字符或字符串,以'#'结束:
"）;
while（（e=getchar（））!
='#'）
{
EnQueue（&Q,e）;
}
break;
case2:
DeQueue（&Q,e）;
break;
case3:
display（&Q）;
}
}while（choice>0&&choice<=3）;
return0;
}
（2）运行结果
（3）结果分析
循环队列通过设置队首和队尾实现先进后出功能
实验总结：
1.在本次试验中我学会了如何实现的栈的顺序存储以及链式存储。
2.以及懂得了栈的基本特性：
仅在表尾进行删除和插入操作、先进后出。
升级会员 