实验指导-栈
- 格式：doc
- 大小：92.50 KB
- 文档页数：4
实验二栈的应用
一、实验题目
栈的应用
二、实验课时
2课时
三、实验目的
1．掌握栈的概念、特点；
2．熟悉栈的两种存储结构：顺序存储、链表存储，以及基于两种存储结构的相关运算的实现；
3．掌握栈的相关应用问题的程序设计方法，培养分析问题、解决问题的能力。
四、实验内容和要求
1．验证顺序栈的基本操作，要求编制一个程序，实现顺序栈的初始化、判断栈空、判断栈满、入栈、出栈、取栈顶等基本操作。
要求：
（1）顺序栈的存储结构定义：typedef struct sqstack
{int data[MaxSize];
int top;
}SqStack;
（2）源代码：参见附录一
注意：此源代码中包含五处错误，请调试、修正，直至顺利运行源代码，在实验报告中本题不用贴代码，但要贴出运行界面截图。
2. 请按如下定义改写第一题的代码。
#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
在实验报告中本题需要提交代码及运行界面截图。
3．程序员在终端输入程序时，不能保证不出差错，但可以在发现敲错时及时纠正。
例如，每当敲错一个键时，约定补敲一个“＃”以表示前一个字符无效；如果发现当前一行有错，约定敲入一个“@”以表示“@”与前一个换行符之间的字符全部无效。
例如：假设在终端上输入了这样两行字符：
BGE##EGIM#N
RAD(A@READ(A)
则实际有效的是下面两行：
BEGIN
READ(A)
请编制一个相应的输入处理程序来完成上述修改。
提示：
程序中可以使用一个栈来逐行处理从终端输入的字符。
每次从终端接收一个字符后先作如下判断，如果它既不是“#”也不是“@”，则将该字符压入栈顶；如果是“#”则从栈顶删去一个字符；如果是“@”，则把字符栈清空。
在实验报告中本题需要提交代码及运行界面截图。
4、停车场管理模拟程序
设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出，汽车在停车场内按车辆到达的时间先后顺序，依次由南向北排列（大门在最北端，最先到达的第一辆车在停车场的最南端）。
若停车场内已停满n辆车，则再来的车拒绝进入。
当停车场内某辆车要离开时，在它之后进入的车辆必须先退出，为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场。
试为停车场编制按上述要求进行管理的模拟程序。
提示：
以栈模拟停车场，按照从终端输入的数据进行模拟管理。
每次输入的数据包括两方面的信息，汽车到达（用1表示）或离开（用2表示），汽车车牌号。
对每一次的输入数据进行操作后的输出信息应该是：若汽车到达，则输出汽车在停车场上的位置；若汽车离去，则输出停车场上剩余车辆及停放位置。
栈以顺序结构实现。
运行结果：
在实验报告中本题需要提交代码及运行界面截图。
附录一：此代码包含五处错误，请调试修正。
#include <iostream>
using namespace std;
#define MaxSize 50
#define Null 0
typedef struct sqstack
{int data[MaxSize];
int top;
}SqStack
void InitStack(SqStack &s)
{
s.top==0;
}
int EmptyStack( SqStack &s)
{
return(s.top==0);
}
int FullStack(SqStack &s)
{
return(s.top==MaxSize-1);
}
int Push(SqStack &s,int e)
{ if (FullStack(s)) return 0;
s.data[s.top]=e;
s.top++;
return 1;
}
int GetTop(SqStack &s,int &e) { if (EmptyStack(s))
return 0;
e=s.data[s.top--];
return 1;
}
int Pop(SqStack &s,int &e)
{ if (EmptyStack(s))
return 0;
e=s.data[--s.top];
return 1;
}
void DispStack(SqStack &s)
{int i;
if(EmptyStack(s))
cout<<"Stack is empty!"<<endl; else
{cout<<"Stack is:"<<endl;
for(i=s.top;i>=0;i--)
cout<<s.data[i]<<' ';
cout<<endl;
}
}
void main()
{SqStack s;
int n,i,x,y,z;
InitStack(s);
cout<<"How many Elements?"<<endl; cin>>n;
cout<<"Pleast input:"<<endl;
for(i=0;i<n;i++)
{cin>>x;
y=Push(s,x);
if(!y)
{cout<<"Stack is full!"<<endl;
break;
}
}
DispStack(s);
y=GetTop(s,z);
if(!y)
cout<<"Stack is empty!"<<endl; else
cout<<"top is :"<<z<<endl;
cout<<"Push what?"<<endl;
cin>>x;
y=Push(s,x);
if(!y)
cout<<"Stack is full!"<<endl; DispStack(s);
y=GetTop(s,z);
if(!y)
cout<<"Stack is empty!"<<endl; else
cout<<"top is :"<<z<<endl;
cout<<"Pop......"<<endl;
y=Pop(s,z);
if(!y)
cout<<"Stack is empty!"<<endl;
else
cout<<z<<" is already pop!"<<endl; DispStack(s);
y=GetTop(s,z);
if(!y)
cout<<"Stack is empty!"<<endl; else
cout<<"top is :"<<z<<endl;
}。
