数据结构 实验2停车场管理 队列和栈的运用

实习二栈、队列和递归算法设计-停车场管理一、需求分析1.每一组输入数据包括：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。

2.输出信息：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用。

3.测试数据设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’表示输入结束。

4.【选作内容】：两个栈共享空间，思考应开辟数组的空间是多少？5.【选作内容】：停放在便道上的汽车也收费，收费标准比停放在停车场的车。

实习二栈、队列和递归算法设计题目：停车场管理实习时间：2012/10/14一、需求分析1.每一组输入数据包括：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。

2.输出信息：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用。

3.测试数据设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’表示输入结束。

4.【选作内容】：两个栈共享空间，思考应开辟数组的空间是多少？5.【选作内容】：停放在便道上的汽车也收费，收费标准比停放在停车场的车。

二、设计二、 1. 设计思想二、（1）存储结构以栈模拟停车场，以队列模拟车场外的便道。

栈以顺序结构实现，队列以链表结构实现。

不需另设一个栈，栈顶空间临时停放为将要离去的汽车让路而从停车场退出来的汽车，栈用顺序存储结构实现。

数据结构实验报告实验二栈和队列实验班级：计12-2 姓名：毛文祥学号12101020223一.实验目的熟悉栈和队列的基本特性，掌握栈和队列基本运算的实现过程。

重点掌握栈和队列各种操作的实现。

二.问题描述设停车场内只有一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出，汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满 n 辆汽车，则后来的汽车只能在门外的便道上等候, 一旦有车开走，则排在便道上的第一辆车即可开入，当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用，试为停车场编制按上述要求进行管理的模拟程序。

三.需求分析该停车场问题可以理解为栈和队列的结合，因为停车场内部是先进入的车辆放到最北面，之后进来的车辆依次排到南面，如果有车辆要出去，那么在它之后进入的车辆必须先退出，给这个车辆让路，这个车辆出去之后再返回到停车场，这就是栈的先进后出的操作一致，因此选择栈存储停车场内的车辆，而便道上的车辆则不同，便道上的车辆，进来之后就排在最西边，如果有车辆要出去，那么在它之前车辆必须依次排到队尾，之后这个车辆开出便道，这和队列的先进先出操作一致，因此用队列存储便道上的车辆。

四.系统设计1.数据结构定义：struct Park{int status;//车的状态,0表示进入,1表示离开int num;//车的牌号int time;//车离开或者进入的时间};//车的基本信息的结构体定义typedef struct{struct Park *base;//栈底指针struct Park *top;//栈顶指针int stacksize;}SqStack;栈数据结构定义队列数据结构类型定义typedef struct QNode{struct Park data;//数据域struct QNode *next;}QNode,*Queueptr;typedef struct{Queueptr front;//队头指针Queueptr rear;//队尾指针}LinkQueue;2.基本操作描述void InitStack(SqStack &S);//初始化一个栈void Push(SqStack &S,struct Park e);//压入一个栈顶元素struct Park GetTop(SqStack &S);//得到栈顶元素,函数的返回值为存放车的信息的结构体变量struct Park Pop(SqStack &S);//删除栈顶元素，且函数的返回值为栈顶元素int EmptyStack(SqStack S);//判断一个栈是否为空，空返回1，非空返回0void VisitStack(SqStack S);//遍历一个栈而且输出栈元素的信息,输出顺序为从栈底元素到栈顶元素 void InitQueue(LinkQueue &Q);//初始化一个队列void InsertQueue(LinkQueue &Q,struct Park e);//在队列的队尾处中插入一个元素void DeleteQueue(LinkQueue &Q);//删除队头元素void VisitQueue(LinkQueue Q);//遍历队列，且输出队列元素信息,按照从队头到队尾的顺序输出void DQueue(LinkQueue &Q,struct Park e);//在队列中删除元素信息的数据域中的num值和e的num相等的元素int DStack(SqStack &S,struct Park p,double &d);//在栈中查找是否有与p的num值相等的元素，如果找到，改变d的值，函数值返回1，否则函数值返回03.主程序模块处理过程描述首先输入该车辆信息，判断是否是输入结束标志，是则跳出循环，否则判断是否是进入的车辆，如果是进入的车辆，那么判断此时栈是否已经满了，如果此时栈已满，那么该车辆就要入队列，否则入栈。

课程设计2 栈和队列课程设计一、1、停车场管理问题描述：停车场是一个能放n辆车的狭长通道，只有一个大门，汽车按到达的先后次序停放。

若车场满了，车要停在门外的便道上等候，一旦有车走，则便道上第一辆车进入。

当停车场中的车离开时，由于通道窄，在它后面的车要先退出，待它走后在依次进入。

汽车离开时按停放时间收费。

基本功能要求：（1）建立三个数据结构分别是：停放、让路、等候。

（2）输入数据模拟管理过程，数据（入或出，车号）。

停车场管理#include<iostream>using namespace std;#define Maxsize 10//停车场共停10辆车#define maxsize 10//等待区共停10辆车typedef int datatype;typedef struct ////////////用栈表示汽车停放和让路{datatype data[Maxsize+1];int top;}Seqstack;void Initstack(Seqstack *&s){s=(Seqstack *)malloc(sizeof(Seqstack));s->top=0;}int push(Seqstack *&s,datatype e){if(s->top==Maxsize)return 0;s->top++;s->data[s->top]=e;return 1;}int pop(Seqstack *&s,datatype &e){if(s->top==0)return 0;e=s->data[s->top];s->top--;return e;}void Dispstack(Seqstack *s)int i;cout<<"车号";for(i=s->top;i>0;i--)cout<<i<<" ";cout<<endl;cout<<"停车时间";for(i=s->top;i>0;i--)cout<<s->data[i]<<" ";cout<<endl;}int Stacklength(Seqstack *s){return(s->top);}////////////////////////////////queue///////////////////////////////////// typedef struct ////////////////////用队列表示汽车等候{datatype data[maxsize+1];int front, rear;}sqqueue;void InitQueue(sqqueue *&q){q=(sqqueue *)malloc(sizeof(sqqueue));q->front=q->rear=0;}int enQueue(sqqueue *&q,datatype e){if((q->rear+1)%maxsize==q->front)return 0;q->rear=(q->rear+1)%maxsize;q->data[q->rear]=e;return 1;}int deQueue(sqqueue *&q,datatype &e){if(q->front==q->rear)return 0;q->front=(q->front+1)%maxsize;e=q->data[q->front];return 1;}int lenqueue(sqqueue *&q)return(q->rear-q->front);}void Disqqueue(sqqueue *q)//输出队列元素{if(q->front==q->rear)cout<<"No element!"<<endl;cout<<"The elemnt in this Sqqueue is:"<<endl;while(q->front!=q->rear){cout<<q->data[q->front+1]<<" ";q->front++;}q->front=0;cout<<endl;}void menu(){cout<<"------------Welcome to our Car Parking-----------------"<<endl;cout<<"1-----------停车"<<endl;cout<<"2-----------离开"<<endl;cout<<"3-----------查看停车场停车情况"<<endl;cout<<"4-----------退出"<<endl;}void current(Seqstack *&s1,sqqueue *&q){cout<<"* * * * * * * * 目前停车场状况* * * * * * * * *"<<endl;cout<<"停车场共"<<Maxsize<<"个车位,"<<"当前停车场共有"<<s1->top<<"辆车.";cout<<"等待区共有"<<lenqueue(q)<<"辆车."<<endl;cout<<"* * * * * * * * * * * * * * * * * * * * * * * "<<endl;}void chargemoney(Seqstack *s)//收费系统，按每小时2元钱{cout<<"收取车号为"<<s->top<<"的车,停车费"<<(s->data[s->top])*2<<"元."<<endl;}int main(){Seqstack *s1,*s2;sqqueue *q;Initstack(s1);Initstack(s2);InitQueue(q);int a[8]={10,20,30,40,50,60,70,80};for(int i=0;i<8;i++)push(s1,a[i]);int In;datatype x,e;current(s1,q);do{menu();cin>>In;switch(In){case 1:int time;cout<<"请输入停放时间(/小时，每小时2元):"<<endl;cin>>time;if(push(s1,time)!=0)cout<<"您的车号是:"<<s1->top<<endl;else{enQueue(q,time);cout<<"停车场已满,请稍等..."<<endl;cout<<"等待车号为"<<q->rear<<endl;}current(s1,q);break;case 2:cout<<"请输入车号:"<<endl;int num;cin>>num;for( i=Stacklength(s1);i>num;i--){pop(s1,x);push(s2,x);} chargemoney(s1);pop(s1,x);for(i=Maxsize;i>num;i--){pop(s2,x);push(s1,x);}if(q->front!=q->rear){deQueue(q,e);push(s1,e);cout<<"等待车号为"<<q->front<<"的车,进入停车场,停车车号为"<<s1->top<<endl;}current(s1,q);break;case 3:Dispstack(s1);break;case 4:break;default:cout<<"error input!"<<endl;}}while(In!=4);return 0;}实验结果截图：。

2.3 栈与队列的应用2.3.1模拟停车厂管理一．问题描述设停车厂是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。

汽车在停车场内按车辆到达的先后顺序依次排列，若停车场内已停满汽车，则后来的汽车只能在门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆车即可进入；当停车场内某辆车要离开时，由于停车场是狭长的通道，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门后，为它让路的车辆再按原次序进入车场。

每辆停放在停车场的车，在离开时按其在停车场停留时间的长短交费。

在这里假设汽车不能从便道上开走。

试设计一个实现停车场管理的程序。

二．基本要求按照从终端输入数据序列进行模拟管理。

1．栈用顺序结构实现，队列用链式结构实现；2．每一组输入数据包括三个数据项：汽车“到达”或“离去”的信息、汽车牌照号码、汽车到达或离去的时刻；3．对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出车辆在停车场内或便道上的停车位置；若是车辆离去，则输出车辆在停车场内停留的时间和应缴纳的费用（假设在便道上等候的时间不收费）。

三．提示与分析1．根据问题描述可知，使用栈来模拟停车场，使用队列来模拟车场外的便道；还需另设一个辅助栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车；输入数据时必须保证按到达或离去的时间有序。

2．主要数据结构：①为了便于区分每辆汽车并了解每辆车当前所处的位置等信息，需要记录汽车的牌照号码、进入停车场的时刻及汽车的当前状态，汽车的类型定义描述如下：typedef struct{char license_plate; /*汽车牌照号码，定义为一个字符指针类型*/float time; /*汽车进入停车场的时刻*/char state; /*汽车当前状态，字符p表示停放在停车位上，字符q表示停放在便道上*/ }Car；②由于车位是一个狭长的通道，不允许两辆车同时出入停车位，当有车到来时要进入停车位的时候也要顺次停放，当某辆车要离开时，比它后到的车要先暂时离开停车位，而且越后到的车就越先离开停车位，显然这与栈的“后进先出”特点相吻合，因此用栈来描述停车场是合适的。

栈与队列的应⽤：停车场管理设停车场是⼀个可停放n辆车的狭长通道，且只有⼀个⼤门可供汽车进出。

在停车场内，汽车按到达的先后次序，由北向南依次排列（假设⼤门在最南端）。

若车场内已停满n辆车，则后来的汽车需在门外的便道上等候，当有车开⾛时，便道上的第⼀辆车即可开⼊。

当停车场内某辆车要离开时，在它之后进⼊的车辆必须先退出车场为它让路，待该辆车开出⼤门后，其他车辆再按原次序返回车场。

每辆车离开停车场时，应按其停留时间的长短交费（在便道上停留的时间不收费）。

试编写程序，模拟上述管理过程。

要求以顺序栈模拟停车场，以链队列模拟便道。

从终端读⼊汽车到达或离去的数据，每组数据包括三项：①是“到达”还是“离去”；②汽车牌照号码；③“到达”或“离去”的时刻（获取系统时间，以秒为单位）。

与每组输⼊信息相应的输出信息为：如果是到达的车辆，则输出其在停车场中或便道上的位置；如果是离去的车辆，则输出其在停车场中停留的时间和应交的费⽤。

（提⽰：需另设⼀个栈，临时停放为让路⽽从车场退出的车。

）第⼀次发出的代码没有考虑在为要出车库的车挪地⽅的时候会把真实时间覆盖，现在⼜在代码中加⼊了挪动操作，时间不进⾏改变。

代码如下：#include<stdio.h>#include<time.h>#include<stdlib.h>#include<string.h>#include<math.h>#define PARK_SIZE 5//定义车的结构体typedef struct{int plateNum;time_t ariTine;//进库时间time_t leaTime;// 出库时间}Car;//车库，⽤顺序栈表⽰typedef struct{Car park[PARK_SIZE];int top;}seqParkList;//便道，⽤链队列表⽰typedef struct LoadNode{Car loadnode;LoadNode *next;}LoadNode, *LoadList;//Park1为车库，Park2为中间车库来安放为Park1重要出栈的腾位置的车seqParkList Park1, Park2;//Load为便道LoadList Load;//初始化车库（栈）void InitSeqStack(seqParkList *top){top->top = -1;}//初始化便道（队列）void InitQueue(LoadList *Q){*Q = (LoadList)malloc(sizeof(LoadNode));(*Q)->next = NULL;}//车出⼩道（出队列）int DeletQueue(Car *car){LoadNode *tcar;tcar = Load->next;if(tcar == NULL) return0;*car = tcar->loadnode;Load->next = tcar->next;free(tcar);return1;}//车进⼊⼩道，并且返回在⼩道的位置int EnterQueue(Car *car){//尾插创建队列int order = 0;LoadNode *p1, *p2;p1 = p2 = Load;LoadNode *newCar = (LoadNode *)malloc(sizeof(LoadNode));//找到队尾，顺便返回即将被放在便上车的位置while(p1 != NULL){order++;p2 = p1;p1 = p1->next;}newCar->loadnode = *car;p2->next = newCar;newCar->next = NULL;return order;}//判断车库是否停满bool isFull(){if(Park1.top == PARK_SIZE - 1) return true;return false;}//车进车库（进栈）int Push(seqParkList *S, Car *car){if(S->top == PARK_SIZE - 1) return -1;S->top++;//进库时获取当前系统的时间time(&car->ariTine);S->park[S->top] = *car;return S->top;}//此时仅做进车库操作，不算更新车进出库时间，因为只是为要出库得车腾地⽅⽽进⾏的动作int MoveIn(seqParkList *S, Car *car){if(S->top == PARK_SIZE - 1) return -1;S->top++;S->park[S->top] = *car;return S->top;}//车出库（出栈）int Pop(seqParkList *S, Car *car){if(S->top == -1) return S->top;*car = S->park[S->top];//出车库时获取当前系统的时间time(&car->leaTime);S->top--;return S->top + 1;}//此时仅做出车库操作，不算更新车进出库时间，因为只是为要出库得车腾地⽅⽽进⾏的动作int MoveOut(seqParkList *S, Car *car){if(S->top == -1) return S->top;*car = S->park[S->top];S->top--;return S->top + 1;}//获取车库最外的车（获取栈顶元素）int GetTop(seqParkList *S, Car *car){if(S->top == -1) return S->top;*car = S->park[S->top];return S->top;}//返回车库（栈）是否为空bool isParkEmpty(seqParkList *park){if(park->top == -1) return true;return false;}//⽐较两个车的信息bool ComCar(Car c1, Car c2){if(c1.plateNum == c2.plateNum) return true;return false;}//车到达进⾏相应的操作void CarIn(Car *car){int order;//只要车到来就进⼊便道，接下来在看要不要进车库order = EnterQueue(car);if(isFull()){//如果车库满了则输出⼀下信息printf("车在便道 %d位置\n", order);}else{//反之车库没满Car tcar;DeletQueue(&tcar);//出便道，order = Push(&Park1, &tcar);//进车库printf("车在车库 %d位置\n", order + 1);}}//车离开进⾏相应的操作void CarOut(Car *car){if(isParkEmpty(&Park1)){//如果车库为空便输出相应的信息printf("Garage is empty!\n");}else{Car c1;GetTop(&Park1, &c1);//如果车库最外边不是将要出库的车，便从栈中挪出//存⼊另⼀个栈，直到车库最外边为要出库的车while(!ComCar(c1, *car)){MoveOut(&Park1, &c1);MoveIn(&Park2, &c1);GetTop(&Park1, &c1);}int order = Pop(&Park1, &c1);//输出出库车在停车场停留时间，并且计算费⽤，假设10秒2元，11-20s都算4元printf("此车在车库停留 %lds 并且花费 %d 元（10s/2元）!\n", c1.leaTime - c1.ariTine, (c1.leaTime - c1.ariTine + 9 ) / 10 * 2);//然后把Park2中的车重新放回Park1while(!isParkEmpty(&Park2)){MoveOut(&Park2, &c1);MoveIn(&Park1, &c1);}}//车库出了⼀个车，便道上的车便要进⼊车库 Car c1;if(DeletQueue(&c1)){Push(&Park1, &c1);}}int main(){InitQueue(&Load);InitSeqStack(&Park1);InitSeqStack(&Park2);seqParkList park1, park2;LoadList Load;Car car1;printf("请输⼊车牌号，动作\n");char action[6];scanf("%d %s", &car1.plateNum, action);//直到输⼊车牌号为0结束程序while(car1.plateNum){if(strcmp(action, "到达") == 0){CarIn(&car1);}else if(strcmp(action, "离去") == 0){CarOut(&car1);}printf("请输⼊车牌号，动作\n");scanf("%d %s", &car1.plateNum, action); }}运⾏结果：。

数据结构停车场管理实验报告一、实验目的本次实验旨在通过设计和实现一个停车场管理系统，深入理解和应用数据结构中的栈和队列等知识，提高解决实际问题的能力。

二、实验环境编程语言：C+＋开发工具：Visual Studio三、实验原理1、停车场采用栈结构来存储停放的车辆信息。

栈具有先进后出的特点，符合车辆先进入停车场后离开的逻辑。

2、停车场外的便道采用队列结构来存储等待进入停车场的车辆。

队列具有先进先出的特点，符合车辆按到达顺序进入停车场的需求。

四、实验内容1、设计数据结构定义栈和队列的数据结构，包括存储车辆信息的结构体。

实现栈和队列的基本操作，如入栈、出栈、入队、出队等。

2、功能实现车辆进入停车场：当有车辆进入停车场时，将车辆信息压入栈中。

车辆离开停车场：当有车辆离开停车场时，从栈中弹出相应车辆，并计算停车费用。

显示停车场状态：实时显示停车场内车辆的信息。

处理便道上的车辆：当停车场有空位时，将便道上的车辆依次入停车场。

3、界面设计设计简单的命令行交互界面，方便用户输入操作指令。

五、实验步骤1、定义数据结构｀｀｀cppstruct Car ｛int carNumber;int arrivalTime;int departureTime;｝；class Stack ｛private:Car stackArray;int top;int capacity;public:Stack(int size) ｛capacity ＝ size;stackArray ＝ new Carcapacity; top ＝－1;｝～Stack(）｛delete stackArray;｝bool isFull(）｛return top ＝＝ capacity 1;｝bool isEmpty(）｛return top ＝＝－1;｝void push(Car car) ｛if （！isFull(））｛stackArray+＋top ＝ car;｝ else ｛std:：cout ＜＜＂停车场已满，无法进入！＂＜＜ std:：endl;｝｝Car pop(）｛if （！isEmpty(））｛return stackArraytop;｝ else ｛std:：cout ＜＜＂停车场为空，无法离开！＂＜＜ std:：endl; return ｛－1, －1, －1}；｝｝Car peek(）｛if （！isEmpty(））｛return stackArraytop;｝ else ｛std:：cout ＜＜＂停车场为空！＂＜＜ std:：endl; return ｛－1, －1, －1}；｝｝｝；class Queue ｛private:Car queueArray;int front;int rear;int capacity;public:Queue(int size) ｛capacity ＝ size;queueArray ＝ new Carcapacity;front ＝ rear ＝－1;｝～Queue(）｛delete queueArray;｝bool isFull(）｛return （rear ＋ 1) ％ capacity ＝＝ front;｝bool isEmpty(）｛return front ＝＝－1;｝void enqueue(Car car) ｛if （！isFull(））｛if （isEmpty(））｛front ＝ 0;｝rear ＝（rear ＋ 1) ％ capacity; queueArrayrear ＝ car;｝ else ｛std:：cout ＜＜＂便道已满，无法等待！＂＜＜ std:：endl;｝｝Car dequeue(）｛if （！isEmpty(））｛Car car ＝ queueArrayfront;if （front ＝＝ rear) ｛front ＝ rear ＝－1;｝ else ｛front ＝（front ＋ 1) ％ capacity;｝return car;｝ else ｛std:：cout ＜＜＂便道为空！＂＜＜ std:：endl;return ｛－1, －1, －1}；｝｝Car frontElement(）｛if （！isEmpty(））｛return queueArrayfront;｝ else ｛std:：cout ＜＜＂便道为空！＂＜＜ std:：endl;return ｛－1, －1, －1}；｝｝｝；｀｀｀2、主函数实现｀｀｀cppint main(）｛int parkingLotCapacity ＝ 10; ／／假设停车场容量为 10 Stack parkingLot(parkingLotCapacity)；Queue waitingQueue(parkingLotCapacity)；int choice;while （true) ｛std:：cout ＜＜＂1、车辆进入停车场" ＜＜ std:：endl;std:：cout ＜＜＂2、车辆离开停车场" ＜＜ std:：endl;std:：cout ＜＜＂3、显示停车场状态" ＜＜ std:：endl;std:：cout ＜＜＂4、退出" ＜＜ std:：endl;std:：cout ＜＜＂请选择操作：＂；std:：cin ＞＞ choice;switch （choice) ｛case 1: ｛int carNumber;std:：cout ＜＜＂请输入车辆号码：＂；std:：cin ＞＞ carNumber;Car car ＝｛carNumber, time(NULL)，－1}；if （！parkingLotisFull(））｛parkingLotpush(car)；std:：cout ＜＜＂车辆＂＜＜ carNumber ＜＜＂进入停车场" ＜＜std:：endl;｝ else ｛waitingQueueenqueue(car)；std:：cout ＜＜＂停车场已满，车辆＂＜＜ carNumber ＜＜＂在便道等待" ＜＜ std:：endl;｝break;｝case 2: ｛int carNumber;std:：cout ＜＜＂请输入要离开的车辆号码：＂；std:：cin ＞＞ carNumber;Car car;bool found ＝ false;for （int i ＝ parkingLottop; i ＞＝ 0; i) ｛if （parkingLotstackArrayicarNumber ＝＝ carNumber) ｛car ＝ parkingLotpop(）；cardepartureTime ＝ time(NULL)；found ＝ true;break;｝｝if （found) ｛int parkingTime ＝ difftime(cardepartureTime, cararrivalTime)；double parkingFee ＝ parkingTime 2; ／／假设每单位时间停车费为2 元std:：cout ＜＜＂车辆＂＜＜ carNumber ＜＜＂离开停车场，停车时间：＂＜＜ parkingTime ＜＜＂秒，停车费用：＂＜＜parkingFee ＜＜＂元" ＜＜ std:：endl;if （！waitingQueueisEmpty(））｛Car waitingCar ＝ waitingQueuedequeue(）；parkingLotpush(waitingCar)；std:：cout ＜＜＂便道上的车辆＂＜＜ waitingCarcarNumber ＜＜＂进入停车场" ＜＜ std:：endl;｝｝ else ｛std:：cout ＜＜＂未找到要离开的车辆" ＜＜ std:：endl;｝break;｝case 3: ｛std:：cout ＜＜＂停车场内车辆：＂＜＜ std:：endl;for （int i ＝ parkingLottop; i ＞＝ 0; i) ｛std:：cout ＜＜ parkingLotstackArrayicarNumber ＜＜＂＂；｝std:：cout ＜＜ std:：endl;std:：cout ＜＜＂便道上等待的车辆：＂＜＜ std:：endl;if （！waitingQueueisEmpty(））｛for （int i ＝ waitingQueuefront; i!＝ waitingQueuerear; i ＝（i ＋ 1) ％waitingQueuecapacity) ｛std:：cout ＜＜ waitingQueuequeueArrayicarNumber ＜＜＂＂；｝std:：cout ＜＜ waitingQueuequeueArraywaitingQueuerearcarNumber＜＜ std:：endl;｝ else ｛std:：cout ＜＜＂无" ＜＜ std:：endl;｝break;｝case 4:return 0;default:std:：cout ＜＜＂无效的选择，请重新输入" ＜＜ std:：endl;｝｝return 0;｝｀｀｀六、实验结果1、车辆正常进入停车场，并在停车场已满时在便道等待。

华北水利水电大学数据结构实验报告2013～2014学年第二学期2013级计算机科学与技术（专升本）专业班级：208 学号：201320836 姓名：高攀实验二栈和队列及其应用一、实验题目：栈和队列及其应用——停车场管理二、实验内容：设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。

汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北段），若停车厂内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车迹可开入；停车场内某辆车要离开时，在它之后进入的车连必须先退出车厂为它让路，待该车辆开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车时必须按它停留的时间长短缴纳费用。

编写按上述要求进行管理的模拟程序。

可以将停车场定义成一个顺序栈s0，便道定义成一个链队列q，而停车场中的某辆车要离开，则在它后面进停车场的车必须让道，让其离开，所以必须有一个临时的顺序栈s1，存放让道的车辆。

当有车辆进停车场时，若栈s0不满，则直接进入栈s0；若栈s0满，则进入便道（链队列q）。

若有s0中车辆x离开时，先让在x后面进栈的车从s0退栈并进入栈s1中，让x离开并收取停车费（在便道上停留的时间不收费），然后再把s1中所有元素退栈并重新进入s0栈，最后，将链队列q中的队头元素出队并进栈到s0中。

三、程序源代码：#include<stdio.h>#include<stdlib.h>#define OVERFLOW -1#define N 2#define PRICE 20#define STACK_INIT_SIZE 100//构造顺序栈结构typedef struct data{int num; //车牌号int Atime; //车到达时间}data;typedef struct{data *base;data *top;int stacksize;}SqStack;//构造链队列结构typedef struct QNode{int num; //车牌号struct QNode *next;}QNode,*QueuePtr;typedef struct{QueuePtr front;//队头指针QueuePtr rear;//队尾指针}LinkQueue;void InitStack(SqStack &s){//构造一个空栈ss.base=(data *)malloc(STACK_INIT_SIZE*sizeof(data));if(!s.base) exit (OVERFLOW); //存储分配失败s.top=s.base; //栈空的条件int sistacksize=STACK_INIT_SIZE;}//InitStackbool StackEmpty(SqStack &s){//若栈s为空栈，则返回TRUE，否则返回FLASEif(s.top==s.base) return true;elsereturn false;}int GetTop(SqStack &s){int e;//若栈不空,则用e返回s的栈顶元素，并返回OK;否则返回ERRORif(s.top==s.base) return false;e=(s.top-1)->Atime;return e; //返回车进站的时间}//GetTopvoid Push(SqStack &s,int e,int e1)//e表示车牌号 e1表示车进站时间{//插入元素e为新的栈顶元素s.top->num=e;s.top->Atime=e1;s.top++;}//Pushint Pop(SqStack &s){int e;//删除s的栈顶元素，用e返回其值s.top--;e=s.top->num;return e; //返回车牌号}//Pop//---------------------------------void InitQueue(LinkQueue &q){//构造一个空队列qq.front=q.rear=(QueuePtr)malloc(sizeof(QNode));if(!q.front) exit(OVERFLOW);q.front->next=NULL;}void EnQueue(LinkQueue &q,int e) //e表示车牌号{//插入元素e为q的新的队尾元素QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p) exit(OVERFLOW);//存储分配失败p->num=e;p->next=NULL;q.rear->next=p;q.rear=p;}int DeQueue(LinkQueue &q){int e;//若队列不空，则删除q的队头元素，用e返回其值，并返回OK;否则返回ERROR if(q.front==q.rear) return false;QueuePtr p;p=q.front->next;e=p->num;q.front->next=p->next;if(q.rear==p) q.rear=q.front;free(p);return e; //返回车牌号}bool QueueEmpty(LinkQueue &q){ //若队列q为空队列，则返回TRUE，否则返回FLASEif(q.front==q.rear) return true;elsereturn false;}void Car(SqStack &s0,SqStack &s1,LinkQueue &q,int n){//构造两个空栈s0 s1 一个空链队列qInitStack(s0);InitStack(s1);InitQueue(q);char solu; //车的状态：到达(A),离开(D),结束(E)int count=0,Atime,Dtime,num,e,e1,m=0;//count 停车场的车辆数 Atime 车进站时刻 Dtime 车离开时间 num 车牌号 e 返回的车牌号 e1返回的车进站时刻while(m==0){printf("请输入车的状态：到达(A),离开(D),结束(E)\n");scanf("%c",&solu);if(solu=='A'){printf("请输入车牌号以及车到达的时刻(1-24)：\n");scanf("%d %d",&num,&Atime);if(count>=n) //停车场满了，车停进门外的便道即链队列{EnQueue(q,num);printf("停车场满了，车牌号为%d的车停进门外的便道!\n",num);}if(count<n) //停车场未满，车进站即进入栈s1{printf("车牌号为%d的车进站！\n",num);Push(s0,num,Atime);count++;}}m=0;if(solu=='D'){printf("请输入车牌号以及车离开的时刻：\n");scanf("%d %d",&num,&Dtime);while(!StackEmpty(s0)){e1=GetTop(s0); //得到栈顶元素到达时间e=Pop(s0);//得到栈顶元素车牌号if(e==num){printf("车牌号为%d的车出站!\n",num);printf("输出该车在停车场停留的时间以及要付的费用：\n");printf("%d %d\n",Dtime-e1,(Dtime-e1)*PRICE);count--;while(!StackEmpty(s1)){e1=GetTop(s1);e=Pop(s1);printf("车牌号为%d的车由临时车站进入车站!\n",e);Push(s0,e,e1);count++;}if(!QueueEmpty(q)){e=DeQueue(q);printf("车牌号为%d的车进站！\n",e);printf("输入车牌号为%d的车的由便道进入车站的时间!\n",e);scanf("%d",&Atime);Push(s0,e,Atime);count++;}break;}else{ printf("车牌号为%d的车进入临时车站!\n",e);Push(s1,e,e1);count--;}}m=0;}if(solu=='E'){printf("停车场关门，输出停车场以及便道上车的信息！\n");while(!StackEmpty(s0)){e1=GetTop(s0); //得到栈顶的元素中的到达时间e=Pop(s0);//得到栈顶的元素中的车牌号printf("输出车牌号为%d的车在停车场停留的时间以及要付的费用：\n",e);printf("%d %d\n",24-e1,(24-e1)*PRICE);}while(!QueueEmpty(q)){e=DeQueue(q);printf("输出在便道上的车的车牌号：%d\n",e);}m=1;}}}int main(){void Car(SqStack &s0,SqStack &s1,LinkQueue &q,int n);SqStack s0,s1;LinkQueue q;Car(s0,s1,q,N);return 0;}四、测试结果：五、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）车进站这个实验花费了我相当多的时间，虽然老师给了我们做题的思路，但由于我栈的内容没学扎实，因此在计算停车时间的时候遇到了不能解决的问题，后来参考了网上的做法才知道栈里面可以存放节点，这个问题才得以解决。

实习报告题目：停车场管理一．需求分析1．用栈来表示停车场，用队列来表示停车道。

2．用户需输入车辆的必要信息，如车辆的到达或离开，汽车牌号以及到达或离去的时刻。

停车场的容量及单位时间的停车费由编程序者自行设置，结构需输出车辆停车所需缴纳的费用。

3．本程序要求对车辆的动态能够输出具体的信息内容，包括停车或离开的时间，位置，及所需缴纳的停车费。

4．测试数据为：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’表示输入结束。

5.程序执行的命令为：1.创建栈和队列。

2.对车辆的行为进行相应的处理。

3.输出车辆的信息。

二．概要设计1.设定栈的抽象数据类型定义：ADT Stack{数据对象：D={ai|ai属于Elem,i=1,2……,n, n>=0}数据关系：R1={<ai-1, ai>| ai-1,ai属于D，i=2,……，n}基本操作：initStack(&S)操作结果：构造一个空栈S.pop(&S,&e)初始条件：栈S已存在。

操作结果：删除S的栈顶元素，并以e返回其值。

push(&S,&e )初始条件：栈S已存在。

操作结果：在栈S的栈顶插入新的栈顶元素e。

lengthstack(S)初始条件：栈S已存在。

操作结果：返回S中的元素个数，即栈的长度。

}ADT Stack;2.设定队列的抽象数据类型定义：ADT Queue{数据对象：D={ai| ai属于Elem, i=1,2,……，n, n>=0}数据关系：R1={<ai-1 ,ai>| ai-1,ai 属于D，i=2,……,n}基本操作：initqueue(&Q)操作结果：构造一个空队列Q.enqueue(&Q, e)初始条件：队列Q已存在。