实验报告
实验目的：
1. 掌握堆栈和队列的基本概念；
2. 掌握堆栈和队列的基本操作。
3. 了解产生随机数的相关操作。
实验内容：
1.试编写一个算法，建立一个学生成绩栈，要求从键盘上输入N个数，按照下列要求分别进入不同栈。
（1） 若输入的整数x小于60，则进入第一个栈；
（2） 若输入的整数x大于等于60并小于100，则进入第二个栈；
（3） 若输入的整数x大于100，则进入第三个栈；
（4） 分别输出每个栈的内容。
2. 编写一个程序，使用两个链队q1和q2，用来分别存储有计算机随机产生的20个100以内的奇数和偶数，然后每行输出q1和q2中的一个值，即奇数和偶数配对输出，直到任一队列为空为止。
3. 假设一个算术表达式中可以包含三种括号：“（”和“）”，方括号“[”和“]”及花括号“{”和“}”，且这三种括号可按照任意的次序嵌套使用。编写算法判断给定表达式中所含括号是否成对出现。
实验原理：
堆栈是一种只允许在表的一端进行插入和删除运算的线性表。允许插入和删除运算的一端叫栈顶，另一端叫栈底。堆栈进栈的元素都是放在原当前栈顶元素之前而成为新的栈顶元素，每次退栈元素都是原当前栈顶的元素，最后进入堆栈的数据元素总是最先退出堆栈。 队列是一种只允许在表的一端进行插入，而在表的另一端进行删除的特殊线性表。允许进行插入的一端叫队尾，另一端叫队头。队的插入和删除运算分别是在各自的一端进行的，每个元素必须按照进入的次序离队。
链栈和链队的存储结构中，逻辑上相邻的两个元素对应的存储位置是通过指针反应的，不要求物理上的相邻。
1题定义一个结点结构和栈类。栈类中定义构造函数、析构函数、进栈函数、出栈函数、清栈函数，利用各个函数实现对堆栈的操作。
2题定义一个结点结构和队类。队类中定义构造函数、析构函数、进队函数、出队函数、清队函数，利用各个函数实现对链队的操作。
3题定义一个结点结构和栈类。栈类中定义构造函数、析构函数、进栈函数、出栈函数、清栈函数、测试栈空函数，利用各个函数实现对堆栈的操作。
设计思想:
为了实现代码的重复利用，3个程序源代码使用了模板。
1题中定义三个链栈。根据输入的数值按照相关要求调用进栈函数进栈。然后对三个栈进行出栈操作，若栈为空则输出空，非空则输出相应元素。
2题中定义两个队列。随机产生20个100以内的数。根据产生的数值按照相关要求调用进队函数进队。然后分别对两个队列交替调用出队函数出队，直到有一个队列为空为止。
3题中定义一个链栈。根据输入的值进行相应的操作。如果输入的是左括号则放入栈中。如果输入的是右括号，则先进行出栈处理，如果括号配对，则不再处理；如果括号不配对，则分别对相应的左括号和右括号进行进栈处理。如果输入其他数值和符号不进行任何操作。输入#终止输入。最后调用测试栈空函数，如果栈空则括号配对，否则不配对。
实现部分:
源代码：
1题：
#include<iostream.h>
#include<assert.h>
template<class t1>
struct stacknode{
t1 data;
stacknode *next;};
template<class t1>
class linkstack
{
stacknode<t1> *top;
unsigned height;
public:
linkstack();
~linkstack()
{clear();}
void clear();
void push(t1 &x);
bool pop(t1 &x);
bool isempty()
{return(heighe==0)?true:false;}
};
template<class t1>
linkstack<t1>::linkstack()
{height=0;
top=NULL;}
//清栈函数
template<class t1>
void linkstack<t1>::clear()
{t1 x;
while(pop(x));
}
//进栈函数
template<class t1>
void linkstack<t1>::push(t1 &x)
{stacknode<t1> *p;
if(top)
{p=new stacknode<t1>;
assert(p);
p->data=x;
p->next=top;
top=p;
}
else
{top=new stacknode<t1>;
assert(top);
top->data=x;
top->next=NULL;
}
height++;}
//出栈函数
template<class t1>
bool linkstack<t1>::pop(t1&x)
{stacknode<t1> *p;
if(height)
{x=top->data;
p=top;
top=top->next;
delete p;
height--;
return true;}
else
return false;}
int main()
{int i,j=0,x;
linkstack<int> a,b,c;
cout<<"请输入要输入整数的个数"<<endl; cin>>i;
cout<<"请输入整数"<<endl;
while(j<i)
{cin>>x;
if(x<60)a.push(x);
if(60<=x&&x<100)b.push(x); if(x>100)c.push(x);
j++;}
cout<<"小于60的整数"<<endl; if(!a.pop(x))
cout<<"空";
else a.push(x);
while(a.pop(x))
{cout<<x<<" ";}
cout<<endl;
cout<<"大于等于60小于100的整数"<<endl; if(!b.pop(x))cout<<"空";
else b.push(x);
while(b.pop(x))
{cout<<x<<" ";}
cout<<endl;
cout<<"大于100的整数"<<endl;
if(!c.pop(x))cout<<"空";
else c.push(x);
while(c.pop(x))
{cout<<x<<" ";}
cout<<endl;
return 0;
}
2题：
#include<iostream.h>
#include<assert.h>
#include<stdlib.h>
#include<time.h>
template<class t1>
struct quenenode{
t1 data;
quenenode *next;};
template<class t1>
class linkquene{
quenenode<t1> *head,*tail;
unsigned qsize;
public:
linkquene();
~linkquene()
{clear();}
void clear();
void pushtail(t1 &x);
bool popfront(t1 &x);
bool isempty()
{return(qsize==0)?true:false;} };
template<class t1>
linkquene<t1>::linkquene()
{qsize=0;head=tail=NULL;} //清队函数
template<class t1>
void linkquene<t1>::clear() { t1 x;
while(popfront(x)); head=tail=NULL;
}
//进队函数
template<class t1>
void linkquene<t1>::pushtail(t1 &x) {quenenode<t1> *p;
p=new quenenode<t1>; assert(p);
p->data=x;
if(tail)
{
p->next=NULL; tail->next=p;
tail=p;
}
else
{
p->next=NULL;
tail=p;head=p;
}
qsize++;}
//出队函数
template<class t1>
bool linkquene<t1>::popfront(t1&x) {quenenode<t1> *p;
if(head)
{x=head->data;
p=head;
head=head->next;
if(head==NULL)
tail=NULL;
delete p;
qsize--;
return true;}
else
return false;}
int main()
{int i,m,x,e,f;
linkquene<int> a,b;
cout<<"请输入要产生随机数的个数"; cin>>x;
srand(time(NULL));
cout<<"产生的随机数为：";
for(i=0;i<x;i++)
{m=rand()%100;
cout<<m<<" ";
if(m%2==0)a.pushtail(m);
else b.pushtail(m);}
cout<<endl;
cout<<"成对的奇数和偶数分别为"<<endl; while(a.popfront(e)&&b.popfront(f)) {cout<<f<<" "<<e<<" "<<endl;} return 0;
}
3题：
#include<iostream.h>
#include<assert.h>
template<class t1>
struct stacknode{
t1 data;
stacknode *next;};
template<class t1>
class linkstack{
stacknode<t1> *top;
unsigned height;
public:
linkstack();
~linkstack()
{clear();}
void clear();
void push(t1 &x);
bool pop(t1 &x);
bool isempty()
{return(height==0)?true:false;} };
template<class t1>
linkstack<t1>::linkstack()
{height=0;
top=NULL;}
//清栈函数
template<class t1>
void linkstack<t1>::clear()
{t1 x;
while(pop(x));
}
//进栈函数
template<class t1>
void linkstack<t1>::push(t1 &x) {stacknode<t1> *p;
if(top)
{p=new stacknode<t1>; assert(p);
p->data=x;
p->next=top;
top=p;
}
else
{top=new stacknode<t1>; assert(top);
top->data=x;
top->next=NULL;
}
height++;}
//出栈函数
template<class t1>
bool linkstack<t1>::pop(t1&x) {stacknode<t1> *p;
if(height)
{x=top->data;
p=top;
top=top->next;
delete p;
height--;
return true;}
else
return false;
}
int main()
{linkstack<char> a;
char c,d;
cout<<"请输入算式，以#结束"<<endl; cin>>c;
while(c!='#')
{ if(c=='('||c=='['||c=='{')
a.push(c);
if(c==')')
{a.pop(d);
{if(d==c-1);
else {a.push(d);a.push(c);} }
}
if(c==']'||c=='}')
{a.pop(d);
{if(d==c-2);
else {a.push(d);a.push(c);} }
}
cin>>c;
}
if(a.isempty()){cout<<"括号配对"<<endl;} else {cout<<"括号错误"<<endl;}
}
测试用例：
1题测试用例1.
输入整数的个数 5；
输入数值为 5 30 60 90 110
程序运行结果:
题测试用例2.
输入链表长度为3；
输入数值为 5 10 60
程序运行结果：
2题测试用例1
输入产生的随机数的个数 20； 程序运行结果：
3题测试用例1.
输入算式 5*{8+[3+4*(3+5)+3]+4}=# 程序运行结果:
3题测试用例2.
输入算式3+(4*[5+6)]=#
程序运行结果：
3题测试用例3.
输入算式 3+(4*5=#
程序运行结果：
实验小节：
1题程序对输出时栈空进行了相应处理，体现了程序的健壮性。
2题中有产生随机数的相关操作，掌握了产生随机数的操作。
3题中输入时采用了以#为标志结束，无需计数输入算式的长度，方便自然。
通过对本程序的练习，更好地掌握了链栈链队的概念和相关操作，对链栈的进栈出栈、链队的进队出队有了更深刻的认识。
第二篇：数据结构实验二：堆栈与队列
实验二：堆栈与队列(2学时)
一、实验目的：采用数组和链表两种形式分别实现堆栈与队列的功能。要求每个学生充分理解堆栈与队列的相同和相异之处。
二、实验内容：
1．数制转换问题
[问题描述]
将十进制数N和其它d进制数的转换是计算机实现计算的基本问题，其解决方案很多，其中最简单方法基于下列原理：即除d取余法。例如：（1348）10=（2504）8
N N div 8 N mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
从中我们可以看出，最先产生的余数4是转换结果的最低位，这正好符合栈的特性即后进先出的特性。所以可以用顺序栈来模拟这个过程。
[基本要求]
对于键盘输入的任意一个非负的十进制整数，打印输出与其等值的八进制数。由于上述的计算过程是从低位到高位顺序产生的八进制数的各个数位，而打印输出，一般来说应从高位到地位进行，恰好和计算过程相反。因此可以先将计算过程中得到的八进制数的各位进栈，待相对应的八进制数的各位均产生以后，再使其按顺序出栈，并打印输出。即得到了与输入的十进制数相对应的八进制数。
[测试数据]
由学生依据软件工程的测试技术自己确定。注意测试边界数据。
2．回文判断
[问题描述]
试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1 & 序列2’模式的字符序列。其中序列1和序列2 中都不含字符‘&’，且序列2 是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。
[实现提示]
首先，序列1进栈，然后序列1出栈并与序列2比较。
[测试数据]
由学生依据软件工程的测试技术自己确定。注意测试边界数据，如序列1和序列2均为空串。
3．商品货架管理
[问题描述]
商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近。上货时，需要倒货架，以保证生产日期较近的商品在较下的位置。
[基本要求]
针对一种特定商品，实现上述管理过程。
[实现提示]
用栈模拟货架和周转空间。
[测试数据]
由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空栈。
4．括号匹配的检验
[问题描述]
假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（（）
[ ]）或
[（[ ] [ ]）]等为正确格式，[（ ]）或（（（]均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列：
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
当计算机接受了第1个括号以后，他期待着与其匹配的第8个括号的出现，然而等来的却是第2个括号，此时第1个括号“[”只能暂时靠边，而迫切等待与第2个括号相匹配的 第7个括号“）”的出现，类似的，因只等来了第3个括号“[”，此时，其期待的紧迫程度较第2个括号更紧迫，则第2个括号只能靠边，让位于第3个括号，显然第3个括号的期待紧迫程度高于第2个括号，而第2个括号的期待紧迫程度高于第1个括号；在接受了第4个括号之后，第3个括号的期待得到了满足，消解之后，第2个括号的期待匹配就成了最急迫的任务了，?? ，依次类推。可见这个处理过程正好和栈的特点相吻合。
[基本要求]
读入圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法”。
[测试数据]
输入（[ ]（）），结果“匹配”
输入 [（ ）]，结果“此串括号匹配不合法”
[实现提示]
设置一个栈，每读入一个括号，若是左括号，则作为一个新的更急迫的期待压入栈中；若是右括号，并且与当前栈顶的左括号相匹配，则将当前栈顶的左括号退出，继续读下一个括号，如果读入的右括号与当前栈顶的左括号不匹配，则属于不合法的情况。在初始和结束时，栈应该是空的。
[选作内容]
考虑增加大括号的情况。
5．停车场管理
[问题描述]
设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。
[测试数据]
设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3， 20）， （‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。
[基本要求]
以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。
[实现提示]
需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含三个数据项：汽车“到达”或“离去”信息、汽车的牌照号码和进入停车场的时刻。
[选作内容]
（1） 两个栈共享空间，思考应开辟数组的空间是多少？
（2） 汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。
（3） 汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。
（4） 停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。