实验二栈和队列的操作与应用

《实验二栈和队列的操作与应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验二栈和队列的操作与应用【实验目的】1．熟练掌握栈和队列的特点2．掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用3．掌握对列的定义和基本操作，熟练掌握链式队列的操作及应用,掌握环形队列的入队和出队等基本操作4．加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力1．掌握线性表的两类存储结构（顺序存储结构和链式存储结构）的描述方法。【实验内容】1．定义顺序栈，完成栈的基本操作：空栈、入栈、出栈、取栈顶元素;2．实现十进制数与八进制数的转换，十进制数与十六进制数的转换和任意进制之间的转换;3．定义链式队列，完成队列的基本操作：入队和出队;···1亲亲1···

2、···············11112【实验指导】1.利用栈的顺序存储结构,设计一组输入数据（假定为一组整数），能够对顺序栈进行如下操作：（1）初始化一个空栈，分配一段连续的存储空间，且设定好栈顶和栈底;（2）完成一个元素的入栈操作，修改栈顶指针;（3）完成一个元素的出栈操作，修改栈顶指针;（4）读取栈顶指针所指向的元素的值;（5）将十进制数N和其它d进制数的转换是计算机实现计算的基本问题，其解决方案很多，其中最简单方法基于下列原理：即除d取余法。例如：（1348）10=（2504）8NNdiv8Nmod8134816841682102125202从中我们可以看出，

3、最先产生的余数4是转换结果的最低位，这正好符合栈的特性即后进先出的特性。所以可以用顺序栈来模拟这个过程。以此来实现十进制数与八进制数的转换，十进制数与十六进制数的转换;（6）编写主程序，实现对各不同的算法调用。2.程序组织（1）首先将顺序栈存储结构定义放在一个头文件：如取名为SqStackDef.h。（2）将顺序栈的基本操作算法也集中放在一个文件之中，如取名为SqStackAlgo.h。如：InitStack、DestroyStack、ClearStack、StackEmpty、StackLength、GetTop、Push、Pop等。（3）将函数的测试和主函数组合成

4、一个文件，如取名为SqStackUse.cpp。3.利用队列的链式存储结构,设计一组输入数据（假定为一组整数），能够对链式队列进行如下操作：（1）初始化一个空队列，形成一个带表头结点的空队;（2）完成一个元素的入队操作，修改队尾指针;（3）完成一个元素的出队操作，修改队头指针;（4）修改主程序，实现对各不同的算法调用。4.程序组织（1）首先将链式队列的存储结构定义放在一个头文件：如取名为LinkQueueDef.h。（2）将链式队列的基本操作算法也集中放在一个文件之中，如取名为LinkQueueAlgo.h。如：InitQueue、DestroyQueue、Clear

5、Queue、QueueEmpty、QueueLength、GetHead_Q、EnQueue、DeQueue、QueueTraverse等。（3）将函数的测试和主函数组合成一个文件，如取名为LinkQueueUse.cpp。长春大学计算机科学技术学院实验报告日期_______________地点______________指导教师_____________成绩实验二栈和队列的操作与应用要求：1.完成算法填空，并上机运行调试。2.将运行结果粘贴在指定处。3.将完成的实验报告单独建立一个新文件，命名为：班级+学号+姓名+（实验二），（如：1340538张三（实验二）），发

6、邮件到：ccujsjzl@163.com。一、顺序栈，对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数1．文件SqStackDef.h中实现了栈的顺序存储表示#defineSTACK_INIT_SIZE10/*存储空间初始分配量*/#defineSTACKINCREMENT2/*存储空间分配增量*/typedefstructSqStack{SElemType*base;/*在栈构造之前和销毁之后，base的值为NULL*/SElemType*top;/*栈顶指针*/intstacksize;/*当前已分配的存储空间，以元素为单位*/}SqStack;/*顺

7、序栈*/2．文件SqStackAlgo.h中实现顺序栈的基本操作（存储结构由SqStackDef.h定义）StatusInitStack(SqStack&S){/*构造一个空栈S*/S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);/*存储分配失败*/S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}intStackLength(SqStackS){/*返回S的元素个数，即栈的