华北水利水电学院 数据结构实验报告
2011～2012学年 第二学期 2011级 计算机 专业
班级： **** 学号： ***** 姓名： **** -
实验二 栈和队列及其应用
一、 实验目的：
1．掌握栈的特点(先进后出FILO)及基本操作，如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。
2．掌握队列的特点(先进先出FIFO)及基本操作，如入队、出队等，队列顺序存储结构、链式存储结构和循环队列的实现，以便在实际问题背景下灵活运用。
二、 实验内容：
1．链栈的建立、入栈、出栈操作。
2．环形队列的建立、入队、出队操作。
3．停车场管理。设停车场内只有一个可停放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． C/ C++完成算法设计和程序设计并上机调试通过。
2． 撰写实验报告，提供实验结果和数据。
3． 写出算法设计小结和心得。
四、 程序源代码：
1.#include<iostream.h>
#include<stdlib.h>
typedef struct stnode
{
int data;
stnode *next;
}LinkStack;
//创建一个栈头结点，无头结
void InitStack(LinkStack *&ls)
{
ls=NULL;
}
//进栈，相当于头插法
void Push(LinkStack *&ls,int x)
{
LinkStack *p;
p=(LinkStack *)malloc(sizeof(LinkStack));
p->data=x;
p->next=NULL;
p->next=ls;
ls=p;
}
//出栈
void Pop(LinkStack *&ls)
{
if(ls==NULL)
return;
LinkStack *p;
int x;
p=ls;
while(p)
{
x=p->data;
ls=p->next;
cout<<x<<" ";
free(p);
p=ls;
}
cout<<"出栈成功!!"<<endl;
}
//创建栈
void CreatStack(LinkStack *&ls)
{
InitStack(ls);
int i=1,num;
cout<<"以000表示输入结束!!"<<endl;
while(1)
{
cout<<"请输入第"<<i<<"个元素:";
cin>>num;
if(num==000)
break;
Push(ls,num);
i++;
}
cout<<"进栈成功！！"<<endl;
}
void main()
{
LinkStack *ls,*p;
CreatStack(ls);
Pop(ls);
}
2.#include<iostream.h>
#define QueueSize 100
typedef struct sqqueue
{
int data[QueueSize];
int front,rear;
}SqQueue;
//初始化队列
void InitQueue(SqQueue &qu)
{
qu.rear=qu.front=0;
}
//进队
int EnQueue(SqQueue &sq,int x)
{
if((sq.rear+1)%QueueSize==sq.front)
return 0;
sq.rear=(sq.rear+1)%QueueSize;
sq.data[sq.rear]=x;
return 1;
}
//出队
void DeQueue(SqQueue &sq)
{
int x;
if(sq.front==sq.rear)
return;
while(sq.front!=sq.rear)
{
sq.front=(sq.front+1)%QueueSize;
x=sq.data[sq.front];
cout<<x<<" ";
}
cout<<"出队成功!!"<<endl;
}
//创建队
void CreatQueue(SqQueue &sq)
{
InitQueue(sq);
int num,i=1;
cout<<"以000表示输入结束！！"<<endl;
while(1)
{
cout<<"请输入第"<<i<<"个元素:";
cin>>num;
if(num==000)
break;
EnQueue(sq,num);
i++;
}
cout<<"进队成功！！"<<endl;
}
void main()
{
SqQueue sq;
CreatQueue(sq);
DeQueue(sq);
}
3.#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
#define MAX 2
#define price 0.05
typedef struct node
{
int hour;
int min;
}Time;//时间结点
typedef struct Node
{
char num[10];//车牌号
Time reach;//时间
Time leave;
}CarNode;//车辆信息结点
typedef struct NODE
{
CarNode *stack[MAX];
int top;
}CarStack;//顺序栈模拟车站
typedef struct QNode//队列
{
CarNode *data;
QNode *next;
}QueueNode;//链队结点类型
typedef struct pqrt
{
QueueNode *front,*rear;//设置头指针尾指针
}LinkQueueCar;//模拟通道
//初始化栈
void InitStack(CarStack *cs);
//初始化队列(便道)
int InitQueue(LinkQueueCar *qc);
//车辆到达
int Arrival(CarStack *Enter,LinkQueueCar *qc);
//车辆离开
void Leave(CarStack *Enter,CarStack *Temp,LinkQueueCar *qc);
//显示车库信息
void List(CarStack s,LinkQueueCar w);
void main()
{
CarStack Enter,Temp;
LinkQueueCar Wait;
int ch;
InitStack(&Enter);
InitStack(&Temp);
InitQueue(&Wait);
while(1)
{
cout<<"欢迎光临"<<endl;
cout<<"-----------------------"<<endl;
cout<<"1.车辆到达"<<endl;
cout<<"2.车辆离开"<<endl;
cout<<"3.车场显示"<<endl;
cout<<"4.退出程序"<<endl;
cout<<"-----------------------"<<endl;
cout<<"请选择所需的服务!"<<endl;
while(1)
{
cin>>ch;
if(ch>=1&&ch<=4)
break;
}
switch(ch)
{
case 1:Arrival(&Enter,&Wait);
break;
case 2:Leave(&Enter,&Temp,&Wait);
break;
case 3:List(Enter,Wait);
break;
case 4:exit(0);
break;
default:break;
}
}
}
void InitStack(CarStack *cs)
{
cs->top=-1;//初始化栈
for(int i=0;i<MAX;i++)
cs->stack[cs->top]=NULL;
}
int InitQueue(LinkQueueCar *qc)//初始化队列
{
//qc=(LinkQueueCar *)malloc(sizeof(LinkQueueCar));这句话不能要?????
qc->front=(QueueNode *)malloc(sizeof(QueueNode));
if(qc->front!=NULL)
{
qc->front->next=NULL;//带头结点的
qc->rear=qc->front;//一定要注意赋值顺序不能反了!!!!!!!!!!
return 1;
}
else
return -1;
}
//打印车站车离开的信息
void Print(CarNode *p,int room)
{
int A1,A2,B1,B2;//车辆收费
cout<<"请输入离开时间:/**:**/"<<endl;
cout<<"请输入离开时间的时(0-23):";
cin>>p->leave.hour;
while(p->leave.hour<p->reach.hour||p->leave.hour>23)
{
cout<<"error!!"<<endl;
cin>>p->leave.hour;
}
B1=p->leave.hour;
cout<<"请输入离开时间的分钟(0-59):";
cin>>p->leave.min;
while(p->leave.min<0||p->leave.min>59)
{
cout<<"error!!"<<endl;
cin>>p->leave.min;
}
B2=p->leave.min;
cout<<endl<<"离开汽车的车牌号为："<<endl;
puts(p->num);
cout<<"其到达时间为:"<<p->reach.hour<<":"<<p->reach.min<<endl;
cout<<"其离开时间为:"<<p->leave.hour<<":"<<p->leave.min<<endl;
A1=p->reach.hour;
A2=p->reach.min;
cout<<"应交费用为:"<<((B1-A1)*60+(B2-A2))*price<<"元"<<endl;
free(p);
}
int Arrival(CarStack *Enter,LinkQueueCar *qc)
{
CarNode *p;
QueueNode *t;
p=(CarNode *)malloc(sizeof(CarNode));
cout<<"请输入车牌号(例A8888):"<<endl;
gets(p->num);
if((Enter->top+1)<MAX)
{
Enter->top++;
cout<<"车辆在车场第"<<Enter->top<<"位置"<<endl;
cout<<"请输入到达时间:/**:**/"<<endl;
cout<<"请输入到达时间的时(0-23):";
cin>>p->reach.hour;
while(p->reach.hour<0||p->reach.hour>23)
{
cout<<"error!!"<<endl;
cin>>p->reach.hour;
}
cout<<"请输入到达时间的分(0-59):";
cin>>p->reach.min;
Enter->stack[Enter->top]=p;//注意数组下标是从0开始，在显示时下标也要与之对应
cout<<"车近停车场成功!!"<<endl;
return 1;
}
else
{
cout<<"该车需在便道上等待!"<<endl;
t=(QueueNode *)malloc(sizeof(QueueNode));//进队列
t->data=p;
t->next=NULL;
qc->rear->next=t;
qc->rear=t;
cout<<"车进便道成功!!"<<endl;
return 1;
}
}
void Leave(CarStack *Enter,CarStack *Temp,LinkQueueCar *qc)
{
CarNode *p,*t;
QueueNode *q;
int room;
if(Enter->top>-1)//判断车场是否为空
{
while(1)
{
cout<<"请输入车在车场中的位置:";
cin>>room;
if(room>=0&&room<=Enter->top)
break;
}
//要离开的车后面还有车，则后面的车需进入临时栈给前面的车让路
while(Enter->top>room)//用Enter->top和room相比看你的车在第几个位置，前面的几辆车需全部让路
{
Temp->top++;
Temp->stack[Temp->top]=Enter->stack[Enter->top];
Enter->stack[Enter->top]=NULL;
Enter->top--;
}
//让路完以后车再离开
p=Enter->stack[Enter->top];
Enter->stack[Enter->top]=NULL;
Enter->top--;
//车离开后，如果临时栈里有车，重新进车站
while(Temp->top>=0)
{
Enter->top++;
Enter->stack[Enter->top]=Temp->stack[Temp->top];
Temp->stack[Temp->top]=NULL;
Temp->top--;
cout<<"临时车场里的车重新进站成功!!"<<endl;
}
Print(p,room);//调用计费函数
//车离开后如果便道上有车，也进车站
if(qc->front!=qc->rear&&Enter->top<MAX)//判断便道上是否有车以及车站是否已满
{
q=qc->front->next;
t=q->data;
Enter->top++;
cout<<"便道上的"<<t->num<<"号车进入车场第"<<Enter->top<<"位置"<<endl;
cout<<"请输入现在的时间:/**:**/"<<endl;
cout<<"请输入到达时间的时(0-23):";
cin>>t->reach.hour;
while(t->reach.hour<0||t->reach.hour>23)
{
cout<<"error!!"<<endl;
cin>>t->reach.hour;
}
cout<<"请输入到达时间的分(0-59):";
cin>>t->reach.min;
qc->front->next=q->next;//出便道
if(q==qc->rear) qc->front=qc->rear;
Enter->stack[Enter->top]=t;//进车站
free(q);
cout<<"便道的车进入停车场成功!!"<<endl;
}
else
cout<<"便道里没有车!!"<<endl;
}
else
cout<<"车场里没有车!!"<<endl;
}
void List1(CarStack *s)//显示车场信息
{
int i;
if(s->top>-1)
{
cout<<"车场"<<endl;
cout<<"位置 时间 车牌号"<<endl;
for(i=0;i<(s->top+1);i++)
{
cout<<" "<<i<<" "<<s->stack[i]->reach.hour<<":"<<s->stack[i]->reach.min<<" "<<s->stack[i]->num<<endl;
}
}
else
cout<<"车场里没有车!!"<<endl;
}
void List2(LinkQueueCar *w)//显示便道信息
{
QueueNode *p;
p=w->front->next;//p先指向第一辆车，
if(w->front!=w->rear)//判断便道是否为空
{
cout<<"等待车辆的号码为:"<<endl;
while(p)//用指针p遍历输出数据
{
puts(p->data->num);
p=p->next;
}
}
else
cout<<"便道里没有车!"<<endl;
}
void List(CarStack s,LinkQueueCar w)//显示整个停车场的信息
{
int flag,tag;
flag=1;
while(flag)
{
cout<<"请选择1|2|3:"<<endl;
cout<<"1.车场"<<" "<<"2.便道"<<" "<<"3.返回"<<endl;
while(1)
{
cin>>tag;
if(tag>=1||tag<=3)
break;
else
cout<<"请选择1|2|3:"<<endl;
}
switch(tag)
{
case 1:List1(&s);
break;
case 2:List2(&w);
break;
case 3:flag=0;
break;
default:break;
}
}
}
五、 程序运行情况（写出输入数据及运行结果）
六、 小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）
本次实验前两题是栈和队列的基本算法，是基础练习，关键是第三题，具体谈谈我理解的停车场。
停车场系统总的来说分为五大块，第一块和第二块属于基本操作，包括初始化栈和队列；第三块是车到达，分为两个层次：1.车到达了进栈2.栈满，进队列。第四块是车离开，分为五个层次：1.车离开，判断该车后面是否还有车2.有车的话，后面的车让路，进临时栈3.然后该车离开，打印出离开信息4.离开后，判断临时栈上是否有车，有车重新进车站5.再判断便道上是否有车，有车也进车站。第五块是显示车站信息，分为三个层次：1.显示车站信息2.显示便道信息3.返回。
整个停车场系统涉及的结构体有：
1.描述时间Time 2.描述一辆车CarNode
3.模拟车站CarStack 4.模拟便道QueueNode，LinkQueueCar
整个停车场系统涉及的函数有;
1.栈和队列的初始化2.车进站3.车出战4.计费函数
5.显示车站信息6.显示便道信息7.显示整个停车场的信息
需要注意的问题：
1. 在初始化栈是top=-1或0是不一样的，涉及到后面显示时数组下标的问题。另外因为栈中包含指针数组所以必须给指针初始化
2. 车出站时分的几个层次都要考虑到，注意函数的参数包括三部分(车站，临时车站，队列)，注意各个环节的连接，临时栈的应用。在判断车在第几个位置时需要根据自己输入车在车场的位置，然后与top比较，看车是否在栈尾，是直接出栈还是需要让路后在出栈？判断便道上的车是否能进车站时要根据两个条件，一是便道上有车，二是车站没满。
3. 显示时要注意数组的下标，初始化时top=-1，所以在用for循环遍历所有的结点时要用for(i=0;i<(s->top+1);i++)才能正确输出。
4. 在写计费函数时，分别用几个变量存放到达和离开的时间，做减法后乘以价格输出就行了，容易实现关键是要理解。
5. 主函数和显示函数中都用的是switch语句，很好用。同时我觉得while(1)死循环也很好用，以后要试着多用。