实验三栈和队列讲解.docx
- 文档编号:17069352
- 上传时间:2023-07-21
- 格式:DOCX
- 页数:18
- 大小:18.80KB
实验三栈和队列讲解.docx
《实验三栈和队列讲解.docx》由会员分享,可在线阅读,更多相关《实验三栈和队列讲解.docx(18页珍藏版)》请在冰点文库上搜索。
实验三栈和队列讲解
《数据结构与算法》实验指导与报告书
______学年第____学期
专业:
___________________________________________
学号:
___________________________________________
姓名:
___________________________________________
实验地点:
___________________________________________
指导教师:
___________________________________________
计算机科学与工程学院
2015
实验三栈和队列
【实验目的】
1、掌握栈的结构特性及其入栈,出栈操作;
2、掌握队列的结构特性及其入队、出队的操作,掌握循环队列的特点及其操作。
3、理解掌握递归调用程序设计思想。
【实验学时】
4学时
【实验预习】
回答以下问题:
1、栈的顺序存储表示
2、单链队列的存储表示
3、循环队列的顺序存储表示
【实验内容和要求】
1、按照要求完成程序exp3_1.c,实现顺序栈的相关操作。
以下具有返回值的函数,若操作完成,返回OK,操作失败返回ERROR。
函数需返回的其他数据,使用函数参数返回。
调试及测试数据并给出结果:
•初始化栈;
•连续进栈3,5,7,9,13;
•获取当前栈顶元素;
•返回当前栈长度;
•判断当前栈是否为空;
•栈内元素依次出栈;
•判断当前栈是否为空;
•清空栈;
•利用栈实现数制转换,测试整数8和255;
•判断表达式括号是否匹配,测试以下三个表达式:
表达式1:
1*(2+3)/4;
表达式2:
((3+4)*7-(8-9);
表达式3:
((1+2)*(3+4)-(5+6)*3)
exp3_1.c部分代码如下:
#include
#include
#include
#defineERROR0
#defineOK1
#defineSTACK_INT_SIZE10/*存储空间初始分配量*/
#defineSTACKINCREMENT5/*存储空间分配增量*/
typedefintElemType;/*定义元素的类型*/
/*
(1)---补充栈的顺序存储分配表示,采用定长和可变长度存储均可*/
intInitStack(SqStack*S);/*构造空栈*/
intPush(SqStack*S,ElemTypee);/*入栈*/
intPop(SqStack*S,ElemType*e);/*出栈*/
intGetTop(SqStack*S,ElemType*e);/*获取栈顶元素*/
intClearStack(SqStack*S);/*清空栈*/
intStackEmpty(SqStack*S);/*判断栈是否为空*/
intStackLength(SqStack*S);/*求栈的长度*/
voidconversion();/*十进制转换为二进制*/
voidCorrect();/*判断表达式括号是否匹配*/
/*
(2)---初始化栈函数*/
intInitStack(SqStack*S)
{
}/*InitStack*/
/*(3)---入栈函数*/
intPush(SqStack*S,ElemTypee)
{
}/*Push*/
/*(4)---出栈函数*/
intPop(SqStack*S,ElemType*e)
{
}/*Pop*/
/*(5)---返回栈顶元素函数*/
intGetTop(SqStack*S,ElemType*e)
{
}/*GetTop*/
/*(6)---清空栈函数*/
intClearStack(SqStack*S)
{
}/*ClearStack*/
/*(8)---判断栈是否为空函数*/
intStackEmpty(SqStack*S)
{
}/*StackEmpty*/
/*(9)---返回栈的长度函数*/
intStackLength(SqStack*S)
{
}/*StackLength*/
/*(10)---十进制整数转换为二进制并输出函数*/
voidConversion()
{
}/*Conversion*/
/*(11)---判断表达式括弧是否匹配(假设只有一种小括弧)函数*/
voidCorrect()
{
}/*Correct*/
/*定义菜单字符串数组*/
intmenu_select()
{
char*menu[]={"\n***************MENU******************\n",
"1.InitSatck\n",/*初始化顺序栈*/
"2.PushElement\n",/*入栈*/
"3.GetTopElement\n",/*获得栈顶元素*/
"4.ReturnStackLength\n",/*返回栈的长度*/
"5.StackIsEmpty\n",/*判断是否栈空*/
"6.PopElement\n",/*出栈*/
"7.ClearStack\n",/*清空栈*/
"8.Conversion\n",/*利用栈进行数制转换*/
"9.Correct\n",/*利用栈进行括号匹配*/
"0.Quit\n",/*退出*/
"\n***************MENU******************\n"
};
chars[3];/*以字符形式保存选择号*/
intc,i;/*定义整形变量*/
for(i=0;i<11;i++)/*输出主菜单数组*/
printf("%s",menu[i]);
do
{
printf("\nEnteryouchoice(0~9):
");/*在菜单窗口外显示提示信息*/
scanf("%s",s);/*输入选择项*/
c=atoi(s);/*将输入的字符串转化为整形数*/
}
while(c<0||c>9);/*选择项不在0~9之间重输*/
returnc;/*返回选择项,主程序根据该数调用相应的函数*/
}
intmain()
{
SqStackss;
inte;
InitStack(&ss);
for(;;)
{
switch(menu_select())
{
case1:
printf("\n1-InitSatck:
\n");
if(InitStack(&ss))
printf("InitOK!
\n");
else
printf("InitERROR!
\n");
break;
case2:
printf("\n2-PushElement:
\n");
printf("inputdata(Terminatedbyinputingacharacter):
");
while(scanf("%d",&e)==1)
{
if(Push(&ss,e))
printf("Push%dOK!
\n",e);
else
printf("Push%dERROR!
\n",e);
printf("inputdata:
(Terminatedbyinputingacharacter)");
}
getchar();
break;
case3:
printf("\n3-GetTopElement:
\n");
if(GetTop(&ss,&e))
printf("Topis%d",e);
else
printf("StackisEmpty!
");
break;
case4:
printf("\n4-ReturnStackLength:
\n");
printf("StackLengthis%d",StackLength(&ss));
break;
case5:
printf("\n5-StackIsEmpty:
\n");
if(StackEmpty(&ss))
{
printf("StackisEmpty!
");
}
else
{
printf("StackisnotEmpty!
");
}
break;
case6:
printf("\n6-PopElement:
\n");
if(StackEmpty(&ss))
{
printf("StackisEmpty!
");
}
else
{
printf("AllelementsofStack:
");
while(Pop(&ss,&e))
{
printf("%d",e);
}
}
break;
case7:
printf("\n7-ClearStack:
\n");
ClearStack(&ss);
printf("ClearStackOK!
");
break;
case8:
printf("\n8-Conversion:
\n");
Conversion();
break;
case9:
printf("\n9-Correct:
\n");
getchar();
Correct();
break;
case0:
exit(0);
}
}
return0;
}
2、按照要求完成程序exp3_2.c,实现循环队列的相关操作。
以下具有返回值的函数,若操作完成,返回OK,操作失败返回ERROR。
函数需返回的其他数据,使用函数参数返回。
调试及测试数据并给出结果:
•初始化队列;
•返回当前队列长度;
•连续入队2,4,6,8,10;
•获取当前队头元素;
•返回当前队列长度;
•判断当前队列是否为空;
•队列元素依次出队;
•判断当前队列是否为空;
exp3_2.c部分代码如下:
#include
#include
#defineERROR0
#defineOK1
#defineMAXQSIZE100
typedefintQElemType;/*定义元素的类型*/
/*
(1)---循环队列顺序存储表示*/
typedefstruct
{
}SqQueue;
/*
(2)---构造一个空循环队列*/
intInitQueue(SqQueue*Q)
{
}/*InitQueue*/
/*(3)---返回循环队列的长度*/
intQueueLength(SqQueue*Q)
{
}/*QueueLentgh*/
/*(4)---入队操作*/
intEnQueue(SqQueue*Q,QElemTypee)
{
}/*EnQuese*/
/*(5)---出队操作*/
intDeQueue(SqQueue*Q,QElemType*e)
{
}/*DeQueue*/
/*(6)---判断队列是否为空*/
intQueueEmpty(SqQueue*Q)
{
}/*QueueEmpty*/
/*(7)---取队头元素*/
intGetHead(SqQueue*Q,QElemType*e)
{
}/*GetHead*/
/*销毁队列*/
intDestroyQueue(SqQueue*Q)
{
if(Q->base)
{
Q->rear=Q->front=0;
free(Q->base);
}
returnOK;
}/*DestroyQueue*/
/*定义菜单字符串数组*/
intmenu_select()
{
char*menu[]={"\n***************MENU******************\n",
"1.InitQueue\n",/*初始化循环队列*/
"2.GetQueueLength\n",/*求队列的长度*/
"3.EnQueue\n",/*入队操作*/
"4.GetHead\n",/*取队头元素*/
"5.QueueIsEmpty\n",/*判断是否队空*/
"6.DeQueue\n",/*出队操作*/
"0.Quit\n",/*销毁队列并退出*/
"\n***************MENU******************\n"
};
chars[3];
intc,i;
for(i=0;i<=8;i++)
printf("%s",menu[i]);
do
{
printf("\nEnteryouchoice(0~6):
");
scanf("%s",s);
c=atoi(s);
}
while(c<0||c>6);
returnc;
}
/*主函数*/
intmain()
{
SqQueueqq;
inte;
InitQueue(&qq);
for(;;)
{
switch(menu_select())
{
case1:
printf("\n1-InitQueue:
\n");
if(InitQueue(&qq))
printf("InitOK!
\n");
else
printf("InitERROR!
\n");
break;
case2:
printf("\n2-GetQueueLength:
\n");
printf("Queuelengthis%d",QueueLength(&qq));
break;
case3:
printf("\n3-EnQueue:
\n");
printf("pleaseinputdata:
");
scanf("%d",&e);
if(EnQueue(&qq,e))
printf("%dEnQueueOK!
\n",e);
else
printf("EnQueueError!
\n");
break;
case4:
printf("\n4-GetHead:
\n");
if(GetHead(&qq,&e))
printf("Headis%d\n",e);
else
printf("GetHeadError!
\n");
break;
case5:
printf("\n5-QueueEmpty:
\n");
if(QueueEmpty(&qq))
printf("QueueisEmpty!
");
else
printf("QueueisnotEmpty");
break;
case6:
printf("\n6-DeQueue:
\n");
printf("Queueis:
");
while(!
QueueEmpty(&qq))
{
if(DeQueue(&qq,&e))
printf("%d",e);
}
break;
case0:
DestroyQueue(&qq);
exit(0);
}
}
return0;
}
3、递归(汉诺塔问题)
利用递归算法程序设计编写程序exp3_3.c,解决n阶汉诺塔问题(A柱为起始,C柱为目的)。
请将程序补充完整,并分别调试盘子数为3,7的情况。
exp3_3.c部分代码如下:
#include
intstep=1;
voidhanoi(charA,intn,charB,charC)
{
if(n==1)
{
printf("第%d步:
\n",step++);
printf("将%c柱子上唯一的1个盘子移到%c柱子!
\n",A,C);
}
else
{
printf("先将%c柱子上的多余的%d个盘子移到%c柱子中过程:
\n",A,n-1,B);
hanoi(A,____________,C,_____________);
printf("第%d步:
\n",step++);
printf("将%c柱子上的最大的盘子移到%c柱子中!
\n",A,C);
printf("接下来将%c柱子上的%d个盘子移到%c柱子中过程:
\n",B,n-1,C);
hanoi(B,_____________,A,____________);
}
}
intmain()
{
intn;
charA,B,C;
A='A';
B='B';
C='C';
printf("输入A柱子上盘子的个数:
");
scanf("%d",&n);
hanoi(A,n,B,C);
printf("\n移动结束");
return0;
}
4、拓展实验:
设计程序实现简单四则算术运算。
要求说明:
(1)从键盘接收算术表达式,以“#”表示接收结束;
(2)输出算术表达式的值;
(3)操作数仅限于非负整数,操作符只能是+、-、*、/、^、(、)
(4)可以判断表达式的合法性(如括号的匹配)
提示:
借助栈来完成,将一个表达式转换为后缀表达式,并按照后缀表达式进行计算,得出表达式得结果。
【实验小结】
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 队列 讲解