实验三 栈和队列.docx
《实验三 栈和队列.docx》由会员分享，可在线阅读，更多相关《实验三 栈和队列.docx（21页珍藏版）》请在冰点文库上搜索。
实验三栈和队列
实验报告
课程名称数据结构课程设计
实验项目栈和队列的实现
实验仪器PC机一台
学院_____信息管理学院_______
专业电子商务
班级/学号___
学生姓名_____________
实验日期___12.4__
成绩_______________________
指导教师_________________
北京信息科技大学
信息管理学院
（课程上机）实验报告
实验课程名称:
数据结构课程设计专业:
电子商务班级:
商务1401
学号:
姓名:
__成绩:
实验名称
栈和队列的实现
实验地点
小营学院机房
实验时间
12.4.2015
1.实验目的：
1）熟练掌握栈和队列的特性；
2）熟练掌握栈的基本操作在顺序存储结构、链式存储结构上的实现；
3）熟练掌握队列的基本操作在顺序存储结构、链式存储结构上的实现。
2.实验要求：
1）学时为4学时；
2）在上机前完成源程序；
3）能在机器上正确、调试运行程序；
4）本实验需提交实验报告；
5）实验报告文件命名方法：
实验3_xx班_学号后两位_姓名.doc
3.实验内容和步骤：
1）实现链栈的基本操作
a）创建一个空的堆栈
b）清空堆栈
c）进栈操作
d）出栈操作
e）打印堆栈中的所有元素
利用上述算法完成下面的操作：
f）数值转换程序，可以实现十进制向任意进制数的转换。
g）括号匹配程序，可以实现任意括号序列的匹配功能，当括号匹配成功时，输出“括号匹配成功”，否则输出“括号匹配失败”
2）假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素（不设头指针），请实现队列的以下操作：
a）创建一个空队列
b）判队空
c）入队
d）出队
e）取队头元素
f）清空一个队列
g）打印队列中的所有元素
编写主函数，调用以上各基本操作。
4.实验过程：
1.
A）创建一个空队列
voidInit_LinkStack（LinkStack*L_pointer）
{
*L_pointer=NULL;
}
B）清空堆栈
voidSetNull_LinkStack（LinkStack*L_pointer）
{
Node*p,*q;
p=*L_pointer;
while（p!
=NULL）
{
q=p;
p=p->next;
free（q）;
}
*L_pointer=NULL;
}
C）进栈操作
intPush_LinkStack（LinkStack*L_pointer,ElemTypex）
{
Node*p;
p=（LinkStack）malloc（sizeof（Node））;
if（p==NULL）
returnOverFlow;
p->data=x;
p->next=*L_pointer;
*L_pointer=p;
returnOK;
}
D）出栈操作
intPop_LinkStack（LinkStack*L_pointer,ElemType*x_pointer）
{
Node*p;
if（Empty_LinkStack（*L_pointer）==True）
returnFalse;
else
{
*x_pointer=（*L_pointer）->data;
p=*L_pointer;
*L_pointer=（*L_pointer）->next;
free（p）;
returnOK;
}
}
E）打印堆栈中的所有元素
voidShow_LinkStack（LinkStackL_pointer）
{
Node*p;
p=L_pointer;
if（p==NULL）
printf（"\n此表为空！
\n"）;
else
while（p!
=NULL）
{
printf（"%d",p->data）;
p=p->next;
}
}
F）数值转换程序，可以实现十进制向任意进制数的转换。
voidconversion（intnum,intbase）
{
inttemp;
LinkStackp;
Init_LinkStack（&p）;
while（num）
{
Push_LinkStack（&p,num%base）;
num=num/base;
}
while（Empty_LinkStack（p）==False）
{
Pop_LinkStack（&p,&temp）;
printf（"%d",temp）;
}
printf（"\n"）;
SetNull_LinkStack（&p）;
}
主函数：
#include"stdio.h"
#include"stdlib.h"
#defineTrue1
#defineOK1
#defineOverFlow-1
#defineFalse0
#defineN30
typedefintElemType;
typedefstructnode
{
ElemTypedata;
structnode*next;
}Node,*LinkStack;
voidInit_LinkStack（LinkStack*L_pointer）
{
*L_pointer=NULL;
}
voidSetNull_LinkStack（LinkStack*L_pointer）
{
Node*p,*q;
p=*L_pointer;
while（p!
=NULL）
{
q=p;
p=p->next;
free（q）;
}
*L_pointer=NULL;
}
intEmpty_LinkStack（LinkStackL_pointer）
{
if（L_pointer==NULL）
returnTrue;
else
returnFalse;
}
intPush_LinkStack（LinkStack*L_pointer,ElemTypex）
{
Node*p;
p=（LinkStack）malloc（sizeof（Node））;
if（p==NULL）
returnOverFlow;
p->data=x;
p->next=*L_pointer;
*L_pointer=p;
returnOK;
}
intPop_LinkStack（LinkStack*L_pointer,ElemType*x_pointer）
{
Node*p;
if（Empty_LinkStack（*L_pointer）==True）
returnFalse;
else
{
*x_pointer=（*L_pointer）->data;
p=*L_pointer;
*L_pointer=（*L_pointer）->next;
free（p）;
returnOK;
}
}
voidShow_LinkStack（LinkStackL_pointer）
{
Node*p;
p=L_pointer;
if（p==NULL）
printf（"\n此表为空！
\n"）;
else
while（p!
=NULL）
{
printf（"%d",p->data）;
p=p->next;
}
}
voidconversion（intnum,intbase）
{
inttemp;
LinkStackp;
Init_LinkStack（&p）;
while（num）
{
Push_LinkStack（&p,num%base）;
num=num/base;
}
while（Empty_LinkStack（p）==False）
{
Pop_LinkStack（&p,&temp）;
printf（"%d",temp）;
}
printf（"\n"）;
SetNull_LinkStack（&p）;
}
intmain（）
{
inti,j,a[N],b,c,d,e,f,temp;
LinkStackL_p;
Init_LinkStack（&L_p）;
printf（"请输入你想存入的元素个数:
\n"）;
scanf（"%d",&b）;
printf（"请输入你想要存入的数:
\n"）;
for（i=0;i{
scanf（"%d",&a[i]）;
Push_LinkStack（&L_p,a[i]）;
}
Show_LinkStack（L_p）;
printf（"\n请输入你想出栈的元素个数\n"）;
scanf（"%d",&c）;
for（j=0;jPop_LinkStack（&L_p,&temp）;
Show_LinkStack（L_p）;
SetNull_LinkStack（&L_p）;
d=Empty_LinkStack（L_p）;
printf（"\n清空栈操作"）;
if（d==1）
printf（"\n栈已空\n"）;
else
printf（"\n栈未空\n"）;
printf（"请输入你想转换进制的数\n你想要转换成的进制:
\n"）;
scanf（"%d",&e）;
scanf（"%d",&f）;
conversion（e,f）;
return0;
}
运行结果：
G）括号匹配程序，可以实现任意括号序列的匹配功能，当括号匹配成功时，输出“括号匹配成功”，否则输出“括号匹配失败”
#include"stdio.h"
#include"stdlib.h"
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
#defineOK1
#defineERROR0
#defineOVERFLOW-2
typedefintStatus;
typedefcharSElemType;
typedefstruct
{
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
StatusInitStack（SqStack*S）
{
S->base=（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType））;
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
returnOK;
}
StatusStackEmpty（SqStack*S）
{
if（S->top!
=S->base）returnERROR;
returnOK;
}
StatusPush（SqStack*S,SElemTypee）
{
if（S->top-S->base>=S->stacksize）
{
S->base=（SElemType*）realloc（S->base,（S->stacksize+STACKINCREMENT）*sizeof（SElemType））;
if（!
S->base）exit（OVERFLOW）;
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*S->top++=e;
returnOK;
}
StatusPop（SqStack*S,SElemType*e）
{
if（S->top==S->base）returnERROR;
*e=*--S->top;
returnOK;
}
StatusBracket（SqStack*S,char*str）
{
inti=0,flag1=0,flag2;
SElemTypee;
while（str[i]!
='\0'）
{
switch（str[i]）
{
case'（':
Push（S,'（'）;break;
case'[':
Push（S,'['）;break;
case'{':
Push（S,'{'）;break;
case'）':
{Pop（S,&e）;
if（e!
='（'）
flag1=1;
break;
}
case']':
{Pop（S,&e）;
if（e!
='['）
flag1=1;
break;
}
case'}':
{Pop（S,&e）;
if（e!
='{'）
flag1=1;
break;
}
default:
break;
}
if（flag1）break;
i++;
}
flag2=StackEmpty（S）;
if（!
flag1&&flag2）printf（"正确!
\n"）;
elseprintf（"错误!
\n"）;
returnOK;
}
intmain（）
{
chartemp,flag='y';
while（flag=='y'）
{
charstr[255];
SqStackS;
InitStack（&S）;
printf（"请输入一串字符:
"）;
scanf（"%s",str）;
scanf（"%c",&temp）;
Bracket（&S,str）;
printf（"doyouwanttotryagain（enteryagain）:
"）;
scanf（"%c",&flag）;
printf（"\n"）;
}
printf（"close.\n"）;
}
2.
A）创建一个空队列
intInit_LinkQueue（LinkQueue*L）
{
（*L）
=（LinkQueue）malloc（sizeof（Node））;
if（（*L）==NULL）
returnError;
（*L）->rear=（*L）;
returnOk;
}
B）判队空
intEmpty_LinkQueue（LinkQueue*L）
{
if（（*L）->rear==（*L））
returnOk;
else
returnFalse;
}
C）入队
intPush_LinkQueue（LinkQueue*L,ElemTypex）
{
LinkQueuep;
p=（LinkQueue）malloc（sizeof（Node））;
p->data=x;
（*L）->rear->next=p;
（*L）->rear=p;
p->next=（*L）;
returnOk;
}
D）出队
intPop_LinkQueue（LinkQueue*L,ElemType*x_pointer）
{
LinkQueuetemp;
*x_pointer=（*L）->next->data;
temp=（*L）->next;
（*L）->next=（*L）->next->next;
free（temp）;
returnOk;
}
E）取队头元素
intGetFront_LinkQueue（LinkQueue*L）
{
ElemTypex;
x=（*L）->next->data;
returnx;
}
F）清空一个队列
voidSetNull_LinkQueue（LinkQueueL）
{
Node*p,*q;
p=L->next;
while（p!
=L）
{
q=p;
p=p->next;
free（q）;
}
L->next=L;
}
G）打印队列中的所有元素
voidShow_LinkQueue（LinkQueue*L）
{
Node*p;
p=（*L）->next;
while（p!
=（*L））
{
printf（"%d",p->data）;
p=p->next;
}
}
主函数：
#include"stdio.h"
#include"stdlib.h"
#defineN30
#defineError-1
#defineOk1
#defineFalse0
#defineOverFlow-1
typedefintElemType;
typedefstructQueue
{
ElemTypedata;
structQueue*rear;
structQueue*next;
}Node,*LinkQueue;
intInit_LinkQueue（LinkQueue*L）
{
（*L）
=（LinkQueue）malloc（sizeof（Node））;
if（（*L）==NULL）
returnError;
（*L）->rear=（*L）;
returnOk;
}
voidSetNull_LinkQueue（LinkQueueL）
{
Node*p,*q;
p=L->next;
while（p!
=L）
{
q=p;
p=p->next;
free（q）;
}
L->next=L;
}
intEmpty_LinkQueue（LinkQueue*L）
{
if（（*L）->rear==（*L））
returnOk;
else
returnFalse;
}
intPush_LinkQueue（LinkQueue*L,ElemTypex）
{
LinkQueuep;
p=（LinkQueue）malloc（sizeof（Node））;分配一个结点
p->data=x;数据域赋值
（*L）->rear->next=p;插入队尾
（*L）->rear=p;插入队尾
p->next=（*L）;
returnOk;
}
intPop_LinkQueue（LinkQueue*L,ElemType*x_pointer）
{
LinkQueuetemp;备用指针
*x_pointer=（*L）->next->data;取队头元素到*x。
。
。
所指空间
temp=（*L）->next;头结点进入到备用指针
（*L）->next=（*L）->next->next;把对头元素变为队头元素的后继结点
free（temp）;释放原来的队头元素
returnOk;返回操作成功标记
}
intGetFront_LinkQueue（LinkQueue*L）
{
ElemTypex;
x=（*L）->next->data;
returnx;
}
voidShow_LinkQueue（LinkQueue*L）
{
Node*p;
p=（*L）->next;
while（p!
=（*L））
{
printf（"%d",p->data）;
p=p->next;
}
}
intmain（）
{
LinkQueueLQ;
inta[N],i,j,b,c,d,temp;
Init_LinkQueue（&LQ）;
printf（"请输入你想在队列里存入元素的个数:
\n"）;
scanf（"%d",&b）;
printf（"请输入你要存入的元素:
\n"）;
for（i=0;i{
scanf（"%d",&a[i]）;
Push_LinkQueue（&LQ,a[i]）;
}
Show_LinkQueue（&LQ）;
printf（"\n请输入你想要出队的元素个数:
\n"）;
scanf（"%d",&c）;
for（j=0;jPop_LinkQueue（&LQ,&temp）;
Show_LinkQueue（&LQ）;
printf（"\n取队头元素:
\n"）;
printf（"%d\n",GetFront_LinkQueue（&LQ））;
printf（"清空队列操作:
\n"）;
SetNull_LinkQueue（LQ）;
d=Empty_LinkQueue（&LQ）;
if（d==1）
printf（"该队列已空\n"）;
else
printf（"该队列为空\n"）;
return0;
}
5.实验总结：
学习了链栈操作，会了进栈、退栈，进队、出队的操作。
说明：
1.实验名称、实验目的、实验内容、实验要求由教师确定，实验前由教师事先填好，然后作为实验报告模版供学生使用；
2.实验准备由学生在实验或上机之前填写，教师应该在实验前检查；
3.实验过程由学生记录实验的过程，包括操作过程、遇到哪些问题以及如何解决等；
4.实验总结由学生在实验后填写，总结本次实验的收获、未解决的问题以及体会和建议等；
5.源程序、代码、具体语句等，若表格空间不足时可作为附录另外附页。
升级会员 