实验三 栈和队列的定义及基本操作1

《实验三 栈和队列的定义及基本操作1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验三：栈的定义及基本操作（必做：2学时）一、实验目的：.熟练掌握栈和队列的特点.掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用.掌握对列的定义和基本操作，熟练掌握链式队列的操作及应用,掌握环形队列的入队和出队等基本操作.加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力二、实验内容定义顺序栈，完成栈的基本操作：空栈、入栈、出栈、取栈顶元素；实现十进制数与八进制数的转换，十进制数与十六进制数的转换和任意进制之间的转换；定义链式队列，完成队列的基本操作：入队和出队；1．问题描述：利用栈的顺序存储结构,设计一组输入数据（假定为一组整数），能够对顺序栈进行如下操作：.初始化一

2、个空栈，分配一段连续的存储空间，且设定好栈顶和栈底；.完成一个元素的入栈操作，修改栈顶指针；.完成一个元素的出栈操作，修改栈顶指针；.读取栈顶指针所指向的元素的值；.将十进制数N和其它d进制数的转换是计算机实现计算的基本问题，其解决方案很多，其中最简单方法基于下列原理：即除d取余法。例如：（1348）10=（2504）8NNdiv8Nmod8134816841682102125202从中我们可以看出，最先产生的余数4是转换结果的最低位，这正好符合栈的特性即后进先出的特性。所以可以用顺序栈来模拟这个过程。以此来实现十进制数与八进制数的转换，十进制数与十六进制数的转换；.编写主程序，实现

3、对各不同的算法调用。2．实现要求：对顺序栈的各项操作一定要编写成为C（C++）语言函数，组合成模块化的形式，每个算法的实现要从时间复杂度和空间复杂度上进行评价。.“初始化栈算法”操作结果：构造一个空栈S；.“判是否空栈算法”操作结果：若栈S为空栈，则返回1，否则返回0；.“取栈顶元素算法”操作结果：若栈不空，则用*x返回栈顶元素，并返回1；否则返回0；.“入栈算法”操作结果：插入元素x为新的栈顶元素.“出栈算法”操作结果：若栈不空，则删除栈顶元素，用*x返回其值，并返回1；否则返回0.“实现十进制数与八进制数的转换算法”操作结果：输入任意一个非负的十进制数，输出对应的八进制数；.“实

4、现十进制数与十六进制数的转换算法”操作结果：输入任意一个非负的十进制数，输出对应的十六进制数；三、实验指导1．首先将顺序栈存储结构定义放在一个头文件：如取名为SqStackDef.h。2．将顺序栈的基本操作算法也集中放在一个文件之中，如取名为SqStackAlgo.h。如：InitStack_sq、Empty_sq、GetTop_sq、Push_sq、Pop_sq、conversion10_8、conversion10_16等。3．将函数的测试和主函数组合成一个文件，如取名为SqStackUse.cpp。四、参考程序1．文件SqStackDef.h中实现了栈的顺序存储表示#defin

5、eMAXLEN10typedefintelementtype;typedefstruct/*栈的顺序存储结构定义*/{elementtypeelement[MAXLEN];/*存放栈元素的数组*/inttop;/*栈指针*/}SqStack;2．文件SqStackAlgo.h中实现顺序栈的基本操作（存储结构由SqStackDef.h定义）#includeSqStackInitStack_sq()/*建立一个空栈s*/{SqStacks;s.top=-1;return(s);}intGetTop_sq(SqStack*s,elementtype*x)/*取栈顶元素,若

6、栈s非空,用*x返回栈顶元素*/{if(s->top==-1)return(0);/*栈空返回0*/else{*x=s->element[s->top];return(1);}}intPush_sq(SqStack*s,elementtypex)/*进栈操作,若栈s未满，将元素x进栈*/{if(s->top==MAXLEN-1)return(0);/*栈满返回0*/s->top++;s->element[s->top]=x;return(1);}intPop_sq(SqStack*s,elementtype*x)/*出栈操作,若栈s非空,删除s的栈顶元素,并用*x返回栈顶元素*/{i

7、f(s->top==-1)return(0);/*栈空返回0*/*x=s->element[s->top];s->top--;return(1);}intEmpty_sq(SqStack*s)/*判断栈s是否为空,空则返回1,非空返回0*/{return(s->top==-1);}voidconversion10_8()/*算法3.1*/{/*对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数*/SqStacks;unsignedn;/*非负整数