数据结构停车场管理实验报告(共8页)

1、停车场管理实验报告姓名： 学号： 学院：继续教育学院 班级：计算机科学与技术一 实验目的和要求熟练栈和队列的结构特性，掌握在实际问题背景下的应用二 实验主要内容以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“达到”或“离去”信息、汽车牌照号码以及达到或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆达到、则输出汽车在停车场内或便道上停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。三 实验仪器和环境PC机 Windows xp

2、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

3、,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() 初始化； 构造空栈； 输入已知数据； 插入数据入栈

4、； 分析 入栈；出栈；入队；出队；输出数据； <2>构造栈模块-构造一个空栈； 栈插入模块-插入新的数据元素； 栈删除模块-删除指定的数据元素；构造队列模块-构造一个空队列； 队列插入模块-插入新的数据元素； 队列删除模块-删除指定的数据元素；（3）各模块之间的调用关系如下：主函数模块构造栈模块栈插入模块栈删除模块构造队列模块队列插入模块队列删除模块分析2详细设计<1>类型定义#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define MONEY 5typedef int Status;typedef stru

5、ct ElemTypechar a3;int num;int time;ElemType;typedef struct SqStack ElemType *base;/在栈构造之前和销毁之后,base的值为NULL ElemType *top;/栈顶指针 int stacksize;/当前已经分配的存储空间,以元素为单位SqStack;/栈的表示typedef struct QNodeElemType data; struct QNode *next;QNode,*QueuePtr;/队列的表示typedef struct LinkQueue QueuePtr front;/队头指针Queue

6、Ptr rear;/队尾指针LinkQueue;<2>栈和队列的基本操作Status InitStack(SqStack &S)/构造一个空栈Status Push(SqStack &S,ElemType e)/插入元素e为新的栈顶元素Status Pop(SqStack &S,ElemType &e)/若栈不空，则删除S的栈顶元素，用e 返回其值，并返回OK；否则返回ERRORStatus InitQueue(LinkQueue &Q)/构造一个空队列QStatus EnQueue(LinkQueue &Q,ElemType e)/

7、插入元素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;Sta

8、tus 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 &am

9、p;S,ElemType &e)/若栈不空，则删除S的栈顶元素，用e 返回其值，并返回OK；否则返回ERRORif(S.top=S.base) return OK;e=*-S.top;return OK;/-队列Status InitQueue(LinkQueue &Q)/构造一个空队列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front) exit (OVERFLOW);/存储分配失败Q.front->next=NULL;return OK;Status EnQueue(LinkQueue &Q,E

10、lemType 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->dat

11、a;Q.front->next=p->next;if(Q.rear=p) Q.rear=Q.front;free(p);return OK;五源程序#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 是函数的类型

12、，其值是函数结果状态代码typedef int Status;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define MONEY 5typedef struct ElemTypechar a3;int num;int time;ElemType;typedef struct SqStack ElemType *base;/在栈构造之前和销毁之后,base的值为NULL ElemType *top;/栈顶指针 int stacksize;/当前已经分配的存储空间,以元素为单位SqStack;/栈的表示typedef struct Q

13、NodeElemType data;struct QNode *next;QNode,*QueuePtr;/队列的表示typedef struct LinkQueueQueuePtr front;/队头指针QueuePtr rear;/队尾指针LinkQueue;/-基本操作的实现/-栈Status InitStack(SqStack &S)/构造一个空栈 S.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType); if(!S.base) exit (OVERFLOW); S.top=S.base; S.stacksize=S

14、TACK_INIT_SIZE; return OK;/InitStackStatus 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.

15、top+=e;return OK;/PushStatus Pop(SqStack &S,ElemType &e)/若栈不空，则删除S的栈顶元素，用e 返回其值，并返回OK；否则返回ERRORif(S.top=S.base) return OK;e=*-S.top;return OK;/Pop/-队列Status InitQueue(LinkQueue &Q)/构造一个空队列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front) exit (OVERFLOW);/存储分配失败Q.front->next=

16、NULL;return OK;/InitQueueStatus 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;/EnQueueStatus DeQueue(LinkQueue &Q,ElemType &e)/若队列不空,则删除Q的对头元素,用e

17、返回其值,并返回Ok;否则返回ERROR; struct QNode *p;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;/DeQueue/-主函数void 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_n

18、um=0;t=0;m=0;InitStack(s1);InitStack(s2);InitQueue(Q);printf("停车场的容量是n");scanf("%d",&n);printf("输入数据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_

19、num<n) Push(s1,e1);s1_num+; printf("此车停在停车场内由北向南第 "); printf("%d",s1_num); printf("个n"); else EnQueue(Q,e1);Q_num+; printf("此车停在便道距门口第 "); printf("%d",Q_num); printf("个n");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,所需