实习二 栈和队列应用
仅仅认识到栈和队列是两种特殊的线性表是远远不够的，本次实习的目的在于使读者深入了解栈和队列的特征，以便在实际问题背景下灵活运用它们，同时还将巩固这两种结构的构造方法。
停车场管理
[问题描述]
设停车场内只有一个的停放 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’表示输入结束。
[基本要求]
以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟
管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到
达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车
在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳
的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。
[实现提示]
需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存 储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数 据项：汽车的牌照号码和进入停车场的时刻。
程序：
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define ERROR 0
#define OK 1
#define OVERFLOW -1
#define MAX1 10
#define MAX2 20
typedef struct Message{
char card[10];
char start[10];
char end[10];
int num;
}Message;
typedef struct Stack{
struct Message *top;
struct Message *base;
}Stack;
Stack stack1,stack2;
typedef struct Quence{
int data;
struct Quence *next;
}Quence;
typedef struct Linkquence{
struct Quence *front;
struct Quence *rear;
}Linkquence;
Linkquence quence1;
int Initstack(Stack S)
{
S.base=(Message *)malloc(sizeof(Message)); if(!S.base)return ERROR;
S.top=S.base;
return OK;
}
Stack Push(Stack S,int i)
{
Message *p;
p=(Message *)malloc(sizeof(Message)); p->num=i;
getchar();
printf("这是第%d辆车",i);
printf("请输入该车的车牌号:");
gets(p->card);
printf("请输入该车到达时间:");
gets(p->start);
printf("请输入该车离开时间:");
gets(p->end);
S.top++;
return S;
}
int Pop(Stack S)
{
if(S.top=S.base)return ERROR;
printf("依次输出出栈汽车的车牌号，到达时间以及离开时间:\n");
Stack *q;
q->base=S.base;
while(q->base<S.top)
q->base++;
int time,money;
puts(q->base->end);
puts(q->base->start);
time=q->base->end - q->base->start;
money=time*1;
printf("该车停留了%d分钟，应缴费用为%d元\n",time,money); free(q);
return OK;
}
void Initquence(Linkquence Q)
{
Q.rear=Q.front=(Quence *)malloc(sizeof(Quence)); if(!Q.front)exit(OVERFLOW);
Q.front->next=NULL;
}
int Enterquence(Linkquence Q,int e)
{
Push(stack1,e);
return OK;
}
int Empty(Stack S)
{
if(S.top==S.base)return OK;
else return ERROR;
}
int DeleteQuence(Stack S1,Stack S2)
{
int e;
while(Empty(S1))Push(S2,Pop(S1));
e=Pop(S2);
while(Empty(S2))Push(S1,Pop(S2));
return e;
}
int main()
{
Initstack(stack1);
int elem1,elem2;
static int num1=0,num2=0;
printf("建立停车场内的车辆号码:\n");
scanf("%d",&elem1);
while(elem1)
{
stack1=Push(stack1,elem1);
scanf("%d",&elem1);
num1++;
}
printf("停车场内共有%d辆车\n",num1);
printf("\n");
Initstack(stack2);
Initquence(quence1);
printf("建立便道上的车辆号码:\n");
scanf("%d",&elem2);
while(elem2)
{
Enterquence(quence1,elem2);
quence1.rear++;
scanf("%d",&elem2);
num2++;
}
printf("便道上共有%d辆车\n",num2);
printf("\n");
int flag;
printf("判断是否有车到达或离开,输入非0的数表示车辆到达，输出汽车在停车场内或便道上的停车位置，输入0表示车辆离开.请输入:");
scanf("%d",&flag);
if(flag!=0)
{
if(num1==MAX1)
if(num2!=MAX2)
{Enterquence(quence1,flag);
num2++;
printf("新来的车停在了便道上，是便道上的第%d辆车",num2);}
else printf("该车场已没有位置可供外来车辆停靠\n"); else
{Push(stack1,flag);
num1++;
printf("新来的车停在了停车场，是停车场内的第%d辆车",num1);} }
else DeleteQuence(stack1,stack2);
return 0;
}
实验总结
通过此次实验，我了解到程序中主要注意在进栈和出栈时主要修改栈顶指针
的指向，同时还要保存当前的栈底位置，也可以直接保存一个包含栈顶和栈底元素的栈。另外，定义顺序栈可以通过向数组中传递参数来实现，而链队列则是需要建立一个指向链类型的指针来指向下一个元素的位置，在编写程序过程中可以分开建立函数并对各个函数进行调试来完善程序，将错误尽可能早的查找出来更利于主函数中对这些函数的调用。在今后的学习中要注重实践，注重知识的应用，同时要有耐心，做到踏实仔细。
第二篇：栈和队列的应用实验报告
数据结构实验报告
一、抄写自己所选择的题目。
二、写出算法设计思路。
三、编写代码，调试运行，实现题目要求（提示：考虑到插入和删除的位置是否超出范围等可能出现的异常问题）。
四、写出算法设计、编程和调试运行的体会。