数据结构栈和队列.docx
- 文档编号:9653985
- 上传时间:2023-05-20
- 格式:DOCX
- 页数:11
- 大小:26.11KB
数据结构栈和队列.docx
《数据结构栈和队列.docx》由会员分享,可在线阅读,更多相关《数据结构栈和队列.docx(11页珍藏版)》请在冰点文库上搜索。
数据结构栈和队列
实践二:
栈和队列
1.实验目的要求
本次实验的目的在于使学生深入了解栈和队列的特征,掌握在实际问题背景下的灵活运用。
实验要求,正确调试本程序,记录输出结果。
完成实验报告。
2.实验主要内容
2.1用顺序结构表示栈并实现栈的各种基本操作
2.2十进制数向N进制数据的转换。
2.3使用栈检查括号匹配的检验
2.4采用链式结构表示队列并实现各种基本操作实现(选做)。
3.实验步骤
2.1实验步骤
●建立main函数
●按p46录入SqStack类型定义和相关常量定义,注意常量定义后没有分号(课本上有错误),函数原型说明部分可不录入。
●录入并调试p47方法InitStack、GetTop、Push、Pop方法
●编写方法输出栈中元素内容
●调用方法,出栈入栈若干元素,通过输出栈内容,观察栈内容变化
2.2实验步骤
●将2.1中完成的栈定义和方法,形成头文件
●由于本实验项目处理的是整数,因此需要将SElemType定义为int
●录入并调试算法3.1,注意调用Scanf方法录入数据时,变量前要加地址符&,即:
scanf(“%d”,&N);
2.3实验思路
●栈操作为字符,因此需要将SElemType定义为char
●循环:
获取一个字符,当字符,如果是左括号,入栈;如果是右括号,判断栈顶括号是否和右括号匹配,如匹配,栈顶元素出栈,读入下一个字符,继续循环;如果不匹配,退出循环,返回false;如果字符不是括号,提示输入错误,退出方法。
如果所有字符读取完毕,栈为空,返回true,则括号匹配,否则括号不匹配,返回false。
2.4实验步骤
●录入p66链队列定义
●实现p67,链队列InitQueue、DestroyQueue、EnQueue、DeQueue方法。
●实现输出队列内元素方法
●入队列、出队列若干数据,观察队列内容变化
(1)、
#include
#include
#include
#defineOK1
#defineERROR0
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
typedefcharSElemType;
typedefcharStatus;
typedefstruct{
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
StatusInitStack(SqStack&S){
S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!
S.base)exit(-2);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}
StatusGetTop(SqStackS,SElemType&e){
if(S.top==S.base)returnERROR;
e=*(S.top-1);
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(-2);
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;
}
voidmain()
{
SqStacks;
InitStack(s);
charc;
printf("将a,b,c,d依次压入栈\n");
Push(s,'a');
Push(s,'b');
Push(s,'c');
Push(s,'d');
printf("输出栈顶元素:
\n");
GetTop(s,c);
printf("%c\n",c);
printf("出栈:
\n");
Pop(s,c);
printf("%c\n",c);
Pop(s,c);
printf("%c\n",c);
Pop(s,c);
printf("%c\n",c);
Pop(s,c);
printf("%c\n",c);
}
输出:
(2)、#include
#include
#include
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
typedefstruct{
int*base;
int*top;
intstacksize;
}SqStack;
intInitStack(SqStack&S)
{
S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));
if(!
S.base)return0;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return1;
}
intGetTop(SqStackS,int&e)
{
if(S.top==S.base)return0;
e=*(S.top-1);
return1;
}
intPush(SqStack&S,inte)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));
if(!
S.base)return0;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return1;
}
intPop(SqStack&S,int&e)
{
if(S.top==S.base)return0;
e=*--S.top;
return1;
}
intOutputStack(SqStack&S)
{
int*p;
inti;
p=S.top-1;
printf("栈中的元素有:
");
for(i=0;i { printf("%d",*p);p--; } return1; } voidconversion() { intN,e; SqStackS; InitStack(S); printf("请输入一个十进制数: "); scanf("%d",&N); printf("转换成八进制数为: "); while(N) { Push(S,N%8); N=N/8; } while(S.top! =S.base){ Pop(S,e); printf("%d",e); } printf("\n"); } voidmain() { conversion(); } 输出: (3)、#include #include #include #defineMAXLEN50 typedefstructstack { charch[50]; inttop; }ST; ST*ST_Init() { ST*st; if(st=(ST*)malloc(sizeof(ST))) { st->top=0; returnst; } returnNULL; } intST_Pop(ST*st) { if(st->top==0) { printf("栈为空\n"); return0; } st->top--; returnst->ch[st->top]; } voidst_Push(ST*st,charc) { if(st->top==MAXLEN) { printf("栈溢出\n"); return; } st->ch[st->top]=c; st->top++; } voidcheck_symbol(ST*st,char*a) { inti; st_Push(st,a[0]); for(i=1;i { if((a[i]==']'&&st->ch[st->top-1]=='[')||(a[i]==')'&&st->ch[st->top-1]=='(')) { ST_Pop(st); } else { st_Push(st,a[i]); } } if(st->top==0) { printf("输入的括号匹配\n\n"); } else { printf("输入的括号不匹配\n\n"); } } voidmain() { while (1) { chars[50]; ST*st; st=ST_Init(); printf("请输入一串括号: \n"); scanf("%s",s); if(s[0]=='E') return; check_symbol(st,s); } } 输出:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 队列