数据结构停车场管理实验报告

停车场管理实验报告 学院：计算机工程学院 班级：计算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 ∈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 ∈D, i=2,„n}其中:a1为队头, an为队尾 基本操作:

InitQueue(&Q);

操作结果：构造一个空队列Q

EnQueue(&Q,&e);

初始条件：对列Q已存在。

操作结果：插入元素e为Q的新队尾元素。

DeQueue(&Q,&e);

初始条件：对列Q已存在。

操作结果：删除Q的队头元素, 并用e返回。

}ADT Queue

（2）本程序包含七个模块：

主程序模块，其中主函数为

Void main(){

初始化；

构造空栈；

输入已知数据；

插入数据入栈；

分析

{入栈；出栈；入队；出队；}

输出数据；

}

构造栈模块-----构造一个空栈；

栈插入模块-----插入新的数据元素；

栈删除模块-----删除指定的数据元素；

构造队列模块-----构造一个空队列；

队列插入模块-----插入新的数据元素；

队列删除模块-----删除指定的数据元素；

（3）各模块之间的调用关系如下：

2．详细设计

类型定义

#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;

栈和队列的基本操作

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;

部分操作的算法

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

#include

#include

#include

//------------------------函数结果状态代码

#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

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

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

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(

printf(

开）：\n

scanf(

while(strcmp(e1.a,

if(strcmp(e1.a,

if(s1_num

printf(

else {EnQueue(Q,e1);Q_num++;

printf(

}

else if(strcmp(e1.a,

f=s1_num;

for(i=0;i

Pop(s1,e);s1_num--;

if(e1.num==e.num){

t=e1.time-e.time;m=MONEY*t;

printf(

else Push(s2,e);}

if(t==0&&m==0){printf(

Pop(s2,e);Push(s1,e);s1_num++;}

if(Q.front!=Q.rear){

DeQueue(Q,e);Push(s1,e);s1_num++;}

}

else printf(

printf(

scanf(

}六．实验步骤及调试分析

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）在试验中要先分析好停车场的运作，然后写出各个函数调用条件。在调用中要认真，在数据的运算上不能马虎。要时刻留心指针的指向以及它的值。

七．实验结果及分析

以上数据运算正确，符合试验要求的内容。