停车场管理实验报告
学院：计算机工程学院 班级：计算1414 姓名：李连活
一． 实验目的和要求
熟练栈和队列的结构特性，掌握在实际问题背景下的应用
二． 实验主要内容
以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“达到”或“离去”信息、汽车牌照号码以及达到或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆达到、则输出汽车在停车场内或便道上停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。
三． 实验仪器和环境
PC机 Windows 8.1 Visual c++ c语言
四．实验原理
1.概要设计
（1）抽象数据类型定义
ADT Stack{
数据对象:D={ai|ai ∈ElemSet, i=1,2,…n;n>0}
数据关系:R1={<ai-1,ai>|ai-1,ai ∈D,i=2,…n}
基本操作:
InitStack(&S)
操作结果：构造一个空栈S。
Push(&S,e)
初始条件：栈S已存在。
操作结果：插入e为新的栈顶元素
Pop(&S,&e)
初始条件：栈S已存在。
操作结果：删除S的栈顶元素,并且用e返回。
}ADT Stack
ADT Queue {
数据对象:D={ai|ai ∈ElemSet, i=1,2,…n; n>0}
数据关系:R1={<ai-1,ai>|ai-1,ai ∈D, i=2,…n}其中:a1为队头, an为队尾
基本操作:
InitQueue(&Q);
操作结果：构造一个空队列Q
EnQueue(&Q,&e);
初始条件：对列Q已存在。
操作结果：插入元素e为Q的新队尾元素。
DeQueue(&Q,&e);
初始条件：对列Q已存在。
操作结果：删除Q的队头元素, 并用e返回。
}ADT Queue
（2）本程序包含七个模块：
<1>主程序模块，其中主函数为
Void main(){
初始化；
构造空栈；
输入已知数据；
插入数据入栈；
分析
{入栈；出栈；入队；出队；}
输出数据；
}
<2>构造栈模块-----构造一个空栈；
栈插入模块-----插入新的数据元素；
栈删除模块-----删除指定的数据元素；
构造队列模块-----构造一个空队列；
队列插入模块-----插入新的数据元素；
队列删除模块-----删除指定的数据元素；
（3）各模块之间的调用关系如下：
2．详细设计
<1>类型定义
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MONEY 3
typedef int Status;
typedef struct ElemType{
char a[3];
int num;
int time;
}ElemType;
typedef struct SqStack {
ElemType *base;//在栈构造之前和销毁之后,base的值为NULL
ElemType *top;//栈顶指针
int stacksize;//当前已经分配的存储空间,以元素为单位
}SqStack;//栈的表示
typedef struct QNode{
ElemType data;
struct QNode *next;
}QNode,*QueuePtr;//队列的表示
typedef struct LinkQueue{
QueuePtr front;//队头指针
QueuePtr rear;//队尾指针
}LinkQueue;
<2>栈和队列的基本操作
Status InitStack(SqStack &S)
//构造一个空栈
Status Push(SqStack &S,ElemType e)
//插入元素e为新的栈顶元素
Status Pop(SqStack &S,ElemType &e)
//若栈不空，则删除S的栈顶元素，用e 返回其值，并返回OK；否则返回ERROR
Status InitQueue(LinkQueue &Q)
//构造一个空队列Q
Status EnQueue(LinkQueue &Q,ElemType e)
//插入元素e为Q的新队列
Status DeQueue(LinkQueue &Q,ElemType &e)
//若队列不空,则删除Q的对头元素,用e返回其值,并返回Ok;否则返回ERROR;
<3>部分操作的算法
Status InitStack(SqStack &S){//构造一个空栈
S.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S.base) exit (OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status Push(SqStack &S,ElemType e){//插入元素e为新的栈顶元素
if(S.top-S.base>=S.stacksize){//栈满，追加存储空间
S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base) exit(OVERFLOW);//存储分配失败
S.top=S.base+S.stacksize;
S.stacksize+=STACK_INIT_SIZE;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,ElemType &e){
//若栈不空，则删除S的栈顶元素，用e 返回其值，并返回OK；否则返回ERROR
if(S.top==S.base) return OK;
e=*--S.top;
return OK;
}
//----------------队列
Status InitQueue(LinkQueue &Q){//构造一个空队列Q
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front) exit (OVERFLOW);//存储分配失败
Q.front->next=NULL;
return OK;
}
Status EnQueue(LinkQueue &Q,ElemType e){//插入元素e为Q的新队列
p=(QueuePtr)malloc(sizeof(QNode));//存储分配失败
if(!p) exit(OVERFLOW);
p->data=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
Status DeQueue(LinkQueue &Q,ElemType &e){
//若队列不空,则删除Q的对头元素,用e返回其值,并返回Ok;否则返回ERROR;
if(Q.front==Q.rear) return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;
free(p);
return OK;
}
五．源程序
Stop1.h:
#include <stdio.h>
#include <process.h>
#include <malloc.h>
#include <string.h>
//------------------------函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define TNFEASIBLE -1
#define OVERFLOW -2
//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MONEY 3
Stop2.h:
#include"stop1.h"
typedef struct ElemType{
char a[3];
int num;
int time;
}ElemType;
typedef struct SqStack{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;//栈的表示
typedef struct QNode{
ElemType data;
struct QNode *next;
}QNode,*QueuePtr;//队列的表示
typedef struct LinkQueue{
QueuePtr front;//队头指针
QueuePtr rear;//队尾指针
}LinkQueue;
Status InitStack(SqStack &S);//构造空栈
Status Push(SqStack &S,ElemType e);//进栈
Status Pop(SqStack &S,ElemType &e);//出栈
Status InitQueue(LinkQueue &Q);//构造一个空队列
Status EnQueue(LinkQueue &Q,ElemType e);//入队
Status DeQueue(LinkQueue &Q,ElemType &e);//出队
Stop.cpp:
#include"stop2.h"
Status InitStack(SqStack &S){//构造空栈
S.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S.base) exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status Push(SqStack &S,ElemType e){//插入元素e为新的栈顶元素
if(S.top-S.base>=S.stacksize){//栈满，追加存储空间
S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base) exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACK_INIT_SIZE;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,ElemType &e){//出栈
if (S.top==S.base) return OK;
e=*--S.top;
return OK;
}
/***********************************************************************队列*/
Status InitQueue(LinkQueue &Q){//构造一个空队列
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front) exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
Status EnQueue(LinkQueue &Q,ElemType e){//插入元素e为Q的新队列
struct QNode *p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p->data=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
Status DeQueue(LinkQueue &Q,ElemType &e){
struct QNode *p;
if(Q.front=Q.rear) return ERROR;
p=Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;
free(p);
return OK;
}
Stop_main.cpp:
#include"stop2.h"
main(){
int i,t,f,m,n,s1_num,Q_num;
struct SqStack s1,s2;
struct LinkQueue Q;
struct ElemType e,e1;
s1_num=0;Q_num=0;t=0;m=0;
InitStack(s1);InitStack(s2);InitQueue(Q);
printf("停车场的容量是:");
scanf("%d",&n);
printf("输入车辆信息（E为退出，A为进入标志，D为离开标志，车牌号 时间空格隔开）：\n");
scanf("%s",e1.a);scanf("%d%d",&e1.num,&e1.time);
while(strcmp(e1.a,"E")!=0){
if(strcmp(e1.a,"A")==0) {//当有车辆进来的时候
if(s1_num<n) {Push(s1,e1);s1_num++;
printf("此车停在停车场第%d辆\n",s1_num);}
else {EnQueue(Q,e1);Q_num++;
printf("此车停在便道距离门口第%d辆\n",Q_num);}
}
else if(strcmp(e1.a,"D")==0) {//当有车辆离开的时候
f=s1_num;
for(i=0;i<f;i++){
Pop(s1,e);s1_num--;
if(e1.num==e.num){
t=e1.time-e.time;m=MONEY*t;
printf("此车停车时间%d,所需费用%d元\n",t,m);break;}
else Push(s2,e);}
if(t==0&&m==0){printf("此车为便道内车,故无需收费\n");Q_num--;}
while(s2.top!=s2.base){
Pop(s2,e);Push(s1,e);s1_num++;}
if(Q.front!=Q.rear){
DeQueue(Q,e);Push(s1,e);s1_num++;}
}
else printf("错误\n");
printf("输入数据\n");
scanf("%s",e1.a);scanf("%d%d",&e1.num,&e1.time);}
}六．实验步骤及调试分析
1．输入数据为n=2， (“A”,1,2), (“A”,2,3), (“D”,1, 20), (“A”,3,6),(“A”,4 ,9),(“D”,2, 50), (“E”,0,0),
2．（1）本试验难度较高，除了对书上介绍算法应用还要分析怎么样调用函数，什么时候调用，以及抽象的空间想象停车场的结构，作业完成艰难。
（2）只是理解栈和队列的数据结构做本试验是不够的，它还需要逻辑分析函数之间的关系及整个数据结构的组成和应用。
（3）在试验中要先分析好停车场的运作，然后写出各个函数调用条件。在调用中要认真，在数据的运算上不能马虎。要时刻留心指针的指向以及它的值。
七．实验结果及分析
以上数据运算正确，符合试验要求的内容。