设停车场（如下图1所示）内只有一个可停放几量汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已经停满几量汽车，则后来的汽车只能在门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆汽车即可开入；当停车场内某车辆要离开时，由于停车场是狭长的通道，在它之后开入车场的车辆必须先退出车场为它让路，待该车辆开出大门外后，为它让路的车辆再按原次序进入车场。在这里假设汽车不能从便道上开走。试设计一个停车场管理程序（这里只是一个假想的停车场管理，并不代表实际的停车场管理）。
北
图1 停车场示意图
分析：汽车在停车场内进出是按照栈的运算方式来实现的，先到的先进停车场；停车场的汽车离开停车场时，汽车场内其它汽车为该辆汽车让路，也是按栈的方式进行；汽车在便道上等候是按队列的方式进行的。因此，将停车场设计成一个栈，汽车让路也需要另一个栈来协助完成，汽车进出便道用队列来实现。
本设计，栈采用顺序栈结构，队列用链式存储结构。
存储结构定义如下：
#define stacksize 10
typedef struct sqstack
{
int data[stacksize];
int top;
} SqStackTp;
typedef struct linked_queue
{
int data;
struct linked_queue * next;
}LqueueTp;
typedef struct
{
LqueueTp *front , *rear ;
} QueptrTp;
停车场管理的算法描述如下：
1）接受命令和车号，若是汽车要进停车场，先判断停车场栈是否满，若不满，则汽车入栈，否则汽车进入便道队列等候。
2）若是汽车要离开停车场，为给汽车让路，将停车场栈上若干辆汽车入临时栈，等这辆车出停车场后，临时栈中的汽车出栈，在回到停车场栈，然后看便道队列是否为空，若不空则说明有汽车等候，从队头取出汽车号，让该车进入停车场栈。
3）重复1），2）直到为退出命令（车号为0或负数）。
代码结构
Parking.h
#ifndef PARKING_H_INCLUDED
#define PARKING_H_INCLUDED
#define MaxSize 4
//***************************链队******************************//
typedef int ElemType1;
typedef struct qnode{
ElemType1 data;
struct qnode *next;
}DataNode;
typedef struct{
DataNode *front;
DataNode *rear;
}LinkQuNode;
void InitQueue(LinkQuNode *&q);//初始化
void DestroyQueue(LinkQuNode *&q);//销毁
bool QueueEmpty(LinkQuNode *q);//判断空否
void EnQueue(LinkQuNode *&q,ElemType1 e);//进队
bool DeQueue(LinkQuNode *&q,ElemType1 &e);//出队
int QueueLength(LinkQuNode *q);//队列的长度
void DispQueue(LinkQuNode *q);//输出等待
int LocateElem1(LinkQuNode *q,ElemType1 e);//查找
//***************************顺序栈******************************//
typedef int ElemType;
#define MaxSize 4
typedef struct
{
ElemType data[MaxSize];
int length;
}SqList; //顺序表类型
void CreateList(SqList*&L,ElemType a[],int n);//建立
void InitList(SqList*&L);//初始化
void DestroyList(SqList *&L);//销毁
bool ListEmpty(SqList *L);//检查空
int ListLength(SqList *L);//长度
void DispList(SqList *L);//输出
bool GetElem(SqList *L,int i,ElemType &e);//求值
int LocateElem(SqList *L,ElemType e);//查找
bool ListInsert(SqList *&L,int i,ElemType e);//插入
bool Listinput(SqList *&L,ElemType e);//输入
void ParkToDoorToPark(SqList *&L,SqList *&LD,ElemType1 e);//ParkToDoorToPark
void RoadToPark(LinkQuNode *&q,SqList *&L);//RoadToPark
//***************************welcom******************************//
void Welcom();
void Goodbye();
void WhenParkIsFull();
void Look(LinkQuNode *q,SqList *L);
#endif // PARKING_H_INCLUDED
main.c
#include <iostream>
#include <bits/stdc++.h>
#include"Parking.h"
#define MaxSize 4
using namespace std;
int main()
{
//定义两个链队，一个顺序栈
//
SqList *park;//停车场
SqList *door;//大门外
LinkQuNode *road;//便道
InitList(park);//初始化
InitList(door);
InitQueue(road);
while(1)
{
int NumOfFunction;
int NumOfCar;
Welcom();
reinput:
cin>>NumOfFunction;
if(NumOfFunction!=0 && NumOfFunction!=1 && NumOfFunction!=2 && NumOfFunction!=3)
{
cout<<"输入有误，请重新输入:"<<endl;
goto reinput;
}
else if(NumOfFunction==0)//退出
{
break;
}
else if(NumOfFunction==1)//停车
{
if(ListLength(park)==MaxSize)//停车场满
{
int NumOfFunction1;
WhenParkIsFull();
reinput1:
cin>>NumOfFunction1;
if(NumOfFunction1!=1 && NumOfFunction1!=2)
{
cout<<"输入有误，请重新输入:"<<endl;
goto reinput1;
}
else if(NumOfFunction1==1)//进入便道等待
{
cout<<"请输入车牌号："<<endl;
reinput2:
cin>>NumOfCar;
//查停车场和便道中的车牌号；如果没有，继续；如果有，重新输入
if(LocateElem(park,NumOfCar)!=0 || LocateElem1(road,NumOfCar)!=0)//有,重新输入
{
cout<<"该车已进入停车场或便道，请重新输入车牌号："<<endl;
goto reinput2;
}
EnQueue(road,NumOfCar);//进便道
cout<<"已进入便道!"<<endl;
}
else//离开停车场
{
break;
}
}
else//停车场不满
{
cout<<"当前剩余车位"<<MaxSize-park->length<<"个"<<endl;
cout<<"请输入车牌号："<<endl;
reinput3:
cin>>NumOfCar;
//查停车场和便道中的车牌号；如果没有相同，继续；如果有相同，重新输入
if(LocateElem(park,NumOfCar)!=0 || LocateElem1(road,NumOfCar)!=0)//有,重新输入
{
cout<<"该车已进入停车场或便道，请重新输入车牌号："<<endl;
goto reinput3;
}
Listinput(park,NumOfCar);//进停车场
cout<<"停泊成功！"<<endl;
}
}
else if(NumOfFunction==3)
{
Look(road,park);
}
else//取车
{
if(park->length==0)//车场没车
{
cout<<"当前停车场无停泊车辆，请重新选择"<<endl;
}
else//车场有车
{
cout<<"请输入车牌号："<<endl;
reinput4:
cin>>NumOfCar;
if(LocateElem(park,NumOfCar)==0)//没有
{
cout<<"停车场无此车，请重新输入车牌号："<<endl;
goto reinput4;
}
else
{
//for(int a=0;a<4;a++)
// printf("%d ",park->data[a]);
ParkToDoorToPark(park,door,NumOfCar);
//for(int a=0;a<4;a++)
// printf("%d ",park->data[a]);
if(QueueEmpty(road)==false)
{
RoadToPark(road,park);
cout<<"取车成功！且便道内头车已入库！"<<endl;
}
else
{
cout<<"取车成功！"<<endl;
}
}
}
}
}
DestroyList(park);
DestroyList(door);
DestroyQueue(road);
Goodbye();
return 0;
}
LinkQueue.cpp
#include <bits/stdc++.h>
#include"Parking.h"
#define MaxSize 4
using namespace std;
void InitQueue(LinkQuNode *&q){//初始化
q=(LinkQuNode *)malloc(sizeof(LinkQuNode));
q->front=q->rear=NULL;
}
void DestroyQueue(LinkQuNode *&q){//销毁
DataNode *pre=q->front,*p;
if(pre!=NULL){
p=pre->next;
while(p!=NULL){
free(pre);
pre=p;
p=p->next;
}
free(pre);
}
free(q);
}
bool QueueEmpty(LinkQuNode *q){//判断空否
return(q->rear==NULL);
}
void EnQueue(LinkQuNode *&q,ElemType1 e){//进队
DataNode *p;
p=(DataNode *)malloc(sizeof(DataNode));
p->data=e;
p->next=NULL;
if(q->rear==NULL) q->front=q->rear=p;
else{
q->rear->next=p;
q->rear=p;
}
}
bool DeQueue(LinkQuNode *&q,ElemType1 &e){//出队
DataNode *t;
if(q->rear==NULL) return false;
t=q->front;
if(q->front==q->rear) q->front=q->rear=NULL;
else q->front=q->front->next;
e=t->data;
free(t);
return true;
}
int QueueLength(LinkQuNode *q){//队列的长度
int length=0;
if(QueueEmpty(q)) return length;
else if(!QueueEmpty(q)){
DataNode *p;
p=q->front;
while(p){
length++;
p=p->next;
}
return length;
}
}
void DispQueue(LinkQuNode *q)//输出等待
{
DataNode *t=q->front;
while(t!=NULL)
{
printf("车牌号：%d\n",t->data);
t=t->next;
}
}
int LocateElem1(LinkQuNode *q,ElemType1 e)//查找
{
int num=0;
DataNode *p;
p=q->front;
while(p)
{
num++;
if(p->data==e)
break;
p=p->next;
}
if(num!=0) return 0;//没找到
else return num;
}
SqList.cpp
#include <bits/stdc++.h>
#include"Parking.h"
#define MaxSize 4
using namespace std;
void CreateList(SqList*&L,ElemType a[],int n)//建立
{
int i;
L=(SqList*)malloc(sizeof(SqList));
for(i=0;i<n;i++)
L->data[i]=a[i];
L->length=n;
}
void InitList(SqList*&L)//初始化
{
int i;
L=(SqList*)malloc(sizeof(SqList));
for(i=0;i<MaxSize;i++)
{
L->data[i]=-1;
//printf("%d ",L->data[i]);
//cout<<L->data[i]<<endl;
}
L->length=0;
}
void DestroyList(SqList *&L)//销毁
{
free(L);
}
bool ListEmpty(SqList *L)//检查空
{
return(L->length==0);
}
int ListLength(SqList *L)//长度
{
return(L->length);
}
bool GetElem(SqList *L,int i,ElemType &e)//求值
{
if (i<1 || i>L->length) return false;
e=L->data[i-1];
return true;
}
int LocateElem(SqList *L,ElemType e)//查找
{
int i=0;
for(i=0;i<L->length;i++)
{
if(L->data[i]==e)
break;
}
if(i==L->length)
return 0;
else return i+1;
}
bool ListInsert(SqList *&L,int i,ElemType e)//插入
{
int j;
if(i<1||i>L->length+1) return false;
i--;
for(j=L->length;j>i;j--) L->data[j]=L->data[j-1];
L->data[i]=e;
L->length++;
return true;
}
bool Listinput(SqList *&L,ElemType e)//输入
{
L->data[L->length]=e;
L->length++;
return true;
}
void ParkToDoorToPark(SqList *&L,SqList *&LD,ElemType1 e)
{
int i;
int k=L->length-1;
for(i=k;i>LocateElem(L,e)-1;i--)
{
Listinput(LD,L->data[i]);
L->data[i]=-1;
L->length--;
}
L->length--;
int m=LD->length-1;
for(i=m;i>=0;i--)
{
Listinput(L,LD->data[i]);
LD->data[i]=-1;
LD->length--;
}
}
void RoadToPark(LinkQuNode *&q,SqList *&L)
{
DataNode *t;
int e;
t=q->front;
if(q->front==q->rear) q->front=q->rear=NULL;
else q->front=q->front->next;
e=t->data;
free(t);
Listinput(L,e);
}
Welcom.cpp
#include <bits/stdc++.h>
#include"Parking.h"
#define MaxSize 4
using namespace std;
void Welcom(){
cout<<"************* 欢迎使用笑哈哈停车场系统 ***********"<<endl;
cout<<"* *"<<endl;
cout<<"* 1.停车 *"<<endl;
cout<<"* 2.取车 *"<<endl;
cout<<"* 3.查看停车场及便道 *"<<endl;
cout<<"* 0.退出系统 *"<<endl;
cout<<"* *"<<endl;
cout<<"* 请输入功能编号： *"<<endl;
}
void Goodbye(){
cout<<"************* 感谢使用笑哈哈停车场系统！ **********"<<endl;
}
void WhenParkIsFull()
{
cout<<"****************************************************"<<endl;
cout<<"* 停车场已满，您是否愿意前往便道等待车位？ *"<<endl;
cout<<"* 1.愿意 *"<<endl;
cout<<"* 2.不愿意并离开停车场 *"<<endl;
cout<<"* *"<<endl;
cout<<"* 请输入功能编号： *"<<endl;
}
void Look(LinkQuNode *q,SqList *L)
{
int i;
printf("停车场停车情况：");
for(i=0;i<L->length;i++)
printf("%d ",L->data[i]);
printf("\n");
printf("便道等待情况：");
DataNode *t;
t=q->front;
while(t!=NULL)
{
printf("%d ",t->data);
t=t->next;
}
printf("\n");
free(t);
}
本文含有隐藏内容，请 开通VIP 后查看