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

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

2、C 机 Windows xp Visual c+ c 语言 四. 实验原理 1. 概要设计 (1) 抽象数据类型泄义 ADT Stack 数据对象:D=ai ai GElemSet, i二 1, 2,n;n0 数据关系:Rl= ai-1, ai CD, i二2,n 基本操作： InitStack(SS) 操作结果：构造一个空栈S。 Push( n0 数据关系:Rl= ai-1, ai GD, i=2, n其中:al 为队头，an 为队尾 基本操作： InitQueue( 操作结果：构造一个空队列Q EnQueue ( 初始条件：对列Q已存在。 操作结果：插入元素e为Q的新队尾元素。 DeQue

3、ue ( 初始条件：对列Q已存在。 操作结果：删除Q的队头元素，并用e返回。 ADT Queue （2）本程序包含七个模块： 主程序模块，英中主函数为 Void mainO 初始化； 构造空栈： 输入已知数据： 插入数据入栈： 分析 入栈：出栈：入队：出队； 输出数据： 构造栈模块构造一个空栈； 栈插入模块插入新的数据元素； 栈删除模块删除指左的数据元素： 构造队列模块构造一个空队列； 队列插入模块插入新的数据元素： 队列删除模块删除指左的数据元素： （3）各模块之间的调用关系如下： 主函数模块 （构造栈模块 栈插入模块 栈删除模块 构适队列模块队列插入模块 L分析 队列删除模块 2. 详细设

4、计 类型左义 #define STACK_INH_SIZE 100 #define STACKINCREMENT 10 #define MONEY 5 typedef int Status; typedef struct ElemTypet char a3; int num; int time; ElemType; typedef struct SqStack ElemType *base;/在栈构造之前和销毁之后,base的值为NULL ElemType * top;/ 栈顶指针 int stacksize;/当前已经分配的存储空间，以元素为单位 SqStack;/栈的表示 typedef

5、struct QNode ElemType data; struct QNode *next; QNode, *QueuePtr;/队列的表示 typedef struct LinkQueue QueuePtr front;/队头指针 QueuePtr rear; /队尾指针 LinkQueue; 栈和队列的基本操作 Status InitStack(SqStack 否则返回ERROR; 部分操作的算法 Status InitStack(SqStack 辻(！ exit (OVERFLOW); =STACK_INIT_SIZE; return OK; Status Push(SqStack i

6、f(! exit (OVERFLOW);/存储分配失败 =+; +=STACK_INIT_SIZE; *+=e; return OK; Status Pop(SqStack e=*; return OK; /队列 Status InitQueue(LinkQueue if(! exit (OVERFLOW);/存储分配失败 next二NULL; return OK; Status EnQueue (LinkQueue /存储分配失败 if(!p) exit(OVERFLOW); p-data=e;p-next=NULL; next=p; 二P； return OK; Status DeQueu

7、e(LinkQueue 否则返回ERROR; if二二 return ERROR; p=next; e=p-data; next=p-next; if=p)=; free(p); return OK; 五. 源程序 #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;

8、#define STACK.INIT_SIZE 100 Sdefine STACKINCREMENT 10 define MONEY 5 typedef struct ElemType char a3J; int num; int time; /ElemType; typedef struct SqStack ElemType *base;/在栈构造之前和销毁之后,base的值为NULL ElemType * top;/ 栈顶指针 int stacksize;/当前已经分配的存储空间，以元素为单位 SqStack; /栈的表示 typedef struct QNode ElemType dat

9、a; struct QNode *next; :QNode, *QueuePtr; /队列的表示 typedef struct LinkQueue QueuePtr front;/队头指针 QueuePtr rear;/队尾指针 /LinkQueue; /基本操作的实现 Status InitStack(SqStack if(! exit (OVERFLOW); =STACK_INIT_SIZE; return OK; /InitStack Status Push(SqStack if(! exit (OVERFLOW);/存储分配失败 二+； +二STACK_INIT_SIZE; *+=e;

10、 return OK; /Push Status Pop (SqStack e 二*; return OK; /Pop /队列 Status InitQueue(LinkQueue if(! exit (OVERFLOW);/存储分配失败 next二NULL; return OK; /InitQueue Status EnQueue (LinkQueue p= (QueuePtr)malloc (sizeof (QNode);/存储分配失败 if(!p) exit(OVERFLOW); p-data=e:p-next=NULL; next=p; 二P； return OK; /EnQueue

11、Status DeQueue(LinkQueue 否则返回ERROR; struct QNode *p; if二二 return ERROR; p=next; e=p-data; next=p-next; if=p)=; free(p); return OK; /DeQueue /主函数 void mainO int i, t, f, m, n, sl_num, Q_num; struct SqStack si,s2; struct LinkQueue Q; struct ElemType e, el; sl_num=0;Q_num=0;t=0;m=0; InitStack(sl);InitS

12、tack(s2);InitQueue(Q); printf (”停车场的容量是n); scanf printf (/?输入数据n); scanf (，?%s，z, ; scanf， while(strcmp, E) !=0) if(strcmp, A)=0) /当有车辆进来的时候 if(sl_numn) Push(sl, el) ;sl_num+; printf(”此车停在停车场内由北向南第”)； printf (/z%d sl_num); printfC 个 )； else EnQueue(Q, el);Q_num+; printf(”此车停在便道距门口第”)； printfQ_num);

13、printfC 个 n); else辻(strcmp,D)=O) /当有车辆离开的时候 f=sl_num; for(i=0;if;i+) Pop (si, e) ; sl_num: if= t=printfC此车停车时间d,所需费用d元 n, t,m);break; else Push(s2, e); 辻(t=0Q_num; while!= Pop(s2, e) ; Push (si, e) ; sl_num+; 辻!二 DeQueue(Q, e):Push(sl, e);sl_num+; else printf C错误n); printf (输入数摒n); scanf; scanf (?，%

14、d%d*, 六. 实验步骤及调试分析 1. 输入数据为 n 二 2, (“A”，l,5), (“A”，2, 10), (“D”，l,(“A”，3,20), ( “D”，2, 35), (“E”，0,0), 2. (1)本试验难度较高，除了对书上介绍算法应用还要分析怎么样调用函数，什么时候调 用，以及抽象的空间想象停车场的结构，作业完成艰难。 (2)只是理解栈和队列的数据结构做本试验是不够的，它还需要逻辑分析函数之间的关 系及整个数据结构的组成和应用。 (3)在试验中要先分析好停车场的运作，然后写出并个函数调用条件。在调用中要认 真，在数据的运算上不能马虎。要时刻留心指针的指向以及它的值。 七. 实