实验三 栈和队列Word格式.docx
- 文档编号:4874366
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:21
- 大小:78.08KB
实验三 栈和队列Word格式.docx
《实验三 栈和队列Word格式.docx》由会员分享,可在线阅读,更多相关《实验三 栈和队列Word格式.docx(21页珍藏版)》请在冰点文库上搜索。
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);
}
C)进栈操作
intPush_LinkStack(LinkStack*L_pointer,ElemTypex)
Node*p;
p=(LinkStack)malloc(sizeof(Node));
if(p==NULL)
returnOverFlow;
p->
data=x;
next=*L_pointer;
*L_pointer=p;
returnOK;
D)出栈操作
intPop_LinkStack(LinkStack*L_pointer,ElemType*x_pointer)
if(Empty_LinkStack(*L_pointer)==True)
returnFalse;
else
*x_pointer=(*L_pointer)->
data;
p=*L_pointer;
*L_pointer=(*L_pointer)->
free(p);
returnOK;
E)打印堆栈中的所有元素
voidShow_LinkStack(LinkStackL_pointer)
p=L_pointer;
printf("
\n此表为空!
\n"
);
while(p!
{
printf("
%d"
p->
data);
p=p->
}
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);
%d"
temp);
printf("
SetNull_LinkStack(&
主函数:
#include"
stdio.h"
stdlib.h"
#defineTrue1
#defineOK1
#defineOverFlow-1
#defineFalse0
#defineN30
typedefintElemType;
typedefstructnode
ElemTypedata;
structnode*next;
}Node,*LinkStack;
intEmpty_LinkStack(LinkStackL_pointer)
if(L_pointer==NULL)
returnTrue;
intmain()
inti,j,a[N],b,c,d,e,f,temp;
LinkStackL_p;
L_p);
请输入你想存入的元素个数:
scanf("
&
b);
请输入你想要存入的数:
for(i=0;
i<
b;
i++)
scanf("
a[i]);
L_p,a[i]);
Show_LinkStack(L_p);
\n请输入你想出栈的元素个数\n"
c);
for(j=0;
j<
c;
j++)
L_p,&
d=Empty_LinkStack(L_p);
\n清空栈操作"
if(d==1)
\n栈已空\n"
\n栈未空\n"
请输入你想转换进制的数\n你想要转换成的进制:
e);
f);
conversion(e,f);
return0;
运行结果:
G)括号匹配程序,可以实现任意括号序列的匹配功能,当括号匹配成功时,输出“括号匹配成功”,否则输出“括号匹配失败”
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
#defineERROR0
#defineOVERFLOW-2
typedefintStatus;
typedefcharSElemType;
typedefstruct
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
StatusInitStack(SqStack*S)
S->
base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
top=S->
base;
stacksize=STACK_INIT_SIZE;
StatusStackEmpty(SqStack*S)
if(S->
top!
=S->
base)returnERROR;
StatusPush(SqStack*S,SElemTypee)
top-S->
base>
stacksize)
S->
base=(SElemType*)realloc(S->
base,(S->
stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!
base)exit(OVERFLOW);
base+S->
stacksize;
stacksize+=STACKINCREMENT;
*S->
top++=e;
StatusPop(SqStack*S,SElemType*e)
top==S->
*e=*--S->
top;
StatusBracket(SqStack*S,char*str)
inti=0,flag1=0,flag2;
SElemTypee;
while(str[i]!
='
\0'
)
switch(str[i])
case'
('
:
Push(S,'
break;
['
{'
)'
{Pop(S,&
if(e!
flag1=1;
break;
]'
}'
default:
if(flag1)break;
i++;
flag2=StackEmpty(S);
if(!
flag1&
&
flag2)printf("
正确!
elseprintf("
错误!
chartemp,flag='
y'
;
while(flag=='
charstr[255];
SqStackS;
InitStack(&
S);
请输入一串字符:
"
%s"
str);
%c"
Bracket(&
S,str);
doyouwanttotryagain(enteryagain):
"
flag);
close.\n"
2.
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;
C)入队
intPush_LinkQueue(LinkQueue*L,ElemTypex)
LinkQueuep;
p=(LinkQueue)malloc(sizeof(Node));
rear->
next=p;
rear=p;
next=(*L);
D)出队
intPop_LinkQueue(LinkQueue*L,ElemType*x_pointer)
LinkQueuetemp;
*x_pointer=(*L)->
next->
temp=(*L)->
next=(*L)->
free(temp);
E)取队头元素
intGetFront_LinkQueue(LinkQueue*L)
ElemTypex;
x=(*L)->
returnx;
F)清空一个队列
voidSetNull_LinkQueue(LinkQueueL)
p=L->
=L)
L->
next=L;
G)打印队列中的所有元素
voidShow_LinkQueue(LinkQueue*L)
p=(*L)->
=(*L))
#defineError-1
#defineOk1
typedefstructQueue
structQueue*rear;
structQueue*next;
}Node,*LinkQueue;
分配一个结点
数据域赋值
插入队尾
备用指针
取队头元素到*x。
。
所指空间
头结点进入到备用指针
把对头元素变为队头元素的后继结点
释放原来的队头元素
返回操作成功标记
LinkQueueLQ;
inta[N],i,j,b,c,d,temp;
Init_LinkQueue(&
LQ);
请输入你想在队列里存入元素的个数:
请输入你要存入的元素:
Push_LinkQueue(&
LQ,a[i]);
Show_LinkQueue(&
\n请输入你想要出队的元素个数:
Pop_LinkQueue(&
LQ,&
\n取队头元素:
%d\n"
GetFront_LinkQueue(&
LQ));
清空队列操作:
SetNull_LinkQueue(LQ);
d=Empty_LinkQueue(&
该队列已空\n"
该队列为空\n"
5.实验总结:
学习了链栈操作,会了进栈、退栈,进队、出队的操作。
说明:
1.实验名称、实验目的、实验内容、实验要求由教师确定,实验前由教师事先填好,然后作为实验报告模版供学生使用;
2.实验准备由学生在实验或上机之前填写,教师应该在实验前检查;
3.实验过程由学生记录实验的过程,包括操作过程、遇到哪些问题以及如何解决等;
4.实验总结由学生在实验后填写,总结本次实验的收获、未解决的问题以及体会和建议等;
5.源程序、代码、具体语句等,若表格空间不足时可作为附录另外附页。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验三 栈和队列 实验 队列
![提示](https://static.bingdoc.com/images/bang_tan.gif)