数据结构实验报告堆栈和队列.doc

实验报告
实验目的:
掌握堆栈和队列的基本概念;
掌握堆栈和队列的基本操作。
了解产生随机数的相关操作。
实验内容:
,建立一个学生成绩栈,要求从键盘上输入N个数,按照下列要求分别进入不同栈。
若输入的整数x小于60,则进入第一个栈;
若输入的整数x大于等于60并小于100,则进入第二个栈;
若输入的整数x大于100,则进入第三个栈;
分别输出每个栈的内容。
2. 编写一个程序,使用两个链队q1和q2,用来分别存储有计算机随机产生的20个100以内的奇数和偶数,然后每行输出q1和q2中的一个值,即奇数和偶数配对输出,直到任一队列为空为止。
3. 假设一个算术表达式中可以包含三种括号:“(”和“)”,方括号“[”和“]”及花括号“{”和“}”,且这三种括号可按照任意的次序嵌套使用。编写算法判断给定表达式中所含括号是否成对出现。
实验原理:
堆栈是一种只允许在表的一端进行插入和删除运算的线性表。允许插入和删除运算的一端叫栈顶,另一端叫栈底。堆栈进栈的元素都是放在原当前栈顶元素之前而成为新的栈顶元素,每次退栈元素都是原当前栈顶的元素,最后进入堆栈的数据元素总是最先退出堆栈。
队列是一种只允许在表的一端进行插入,而在表的另一端进行删除的特殊线性表。允许进行插入的一端叫队尾,另一端叫队头。队的插入和删除运算分别是在各自的一端进行的,每个元素必须按照进入的次序离队。
链栈和链队的存储结构中,逻辑上相邻的两个元素对应的存储位置是通过指针反应的,不要求物理上的相邻。
1题定义一个结点结构和栈类。栈类中定义构造函数、析构函数、进栈函数、出栈函数、清栈函数,利用各个函数实现对堆栈的操作。
2题定义一个结点结构和队类。队类中定义构造函数、析构函数、进队函数、出队函数、清队函数,利用各个函数实现对链队的操作。
3题定义一个结点结构和栈类。栈类中定义构造函数、析构函数、进栈函数、出栈函数、清栈函数、测试栈空函数,利用各个函数实现对堆栈的操作。
设计思想:
为了实现代码的重复利用,3个程序源代码使用了模板。
1题中定义三个链栈。根据输入的数值按照相关要求调用进栈函数进栈。然后对三个栈进行出栈操作,若栈为空则输出空,非空则输出相应元素。
2题中定义两个队列。随机产生20个100以内的数。根据产生的数值按照相关要求调用进队函数进队。然后分别对两个队列交替调用出队函数出队,直到有一个队列为空为止。
3题中定义一个链栈。根据输入的值进行相应的操作。如果输入的是左括号则放入栈中。如果输入的是右括号,则先进行出栈处理,如果括号配对,则不再处理;如果括号不配对,则分别对相应的左括号和右括号进行进栈处理。如果输入其他数值和符号不进行任何操作。输入#终止输入。最后调用测试栈空函数,如果栈空则括号配对,否则不配对。
实现部分:
源代码:
1题:
#include<>
#include<>
template<class t1>
struct stacknode{
t1 data;
stacknode *next;};
template<class t1>
class linkstack
{
stacknode<t1> *top;
unsigned heig