数据结构 停车场的程序模拟

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

 基本要求
以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项:汽车“达到”或“离去”信息、汽车牌照号码以及达到或离去的时刻。对每一组输入数据进行操作后的输出信息为:若是车辆达到、则输出汽车在停车场内或便道上停车位置;若是车辆离去,则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费)。栈以顺序结构实现,队列以链表结构实现。
 测试数据
设n=2,输入数据为(“A”,1,5), (“A”,2,10), (“D”,1, 15), (“A”,3,20),(“D”,2, 35), (“E”,0,0),
(“A”,1,5), 其中:“A”表示达到(Arrival);“D”表示离去(Departure); “E”表示输入结束(End)。
3 实现提示:
需另设一个栈,临时停放 为给要离去的汽车让路而从停车场退出来的汽车,也用顺序存储结构实现。输入数据按达到或离去的时刻有序。栈中每个元素表示一辆汽车,包括两个数据项:汽车的牌照号码和进入停车场的时刻。
4 实验要求:任选一种高级程序语言编写源程序,并调试通过,测试正确。

本人折腾了不少时间,初学数据结构,确实不熟悉:)

源代码

//停车场管理 
// 顺序栈   链队列
#include<stdio.h>
#include<stdlib.h>

#define status int
#define ok 1
typedef int elemtype;
#define capacity 2//停车场所能容纳的车数量
char flag='A';

//----------------实现链队列-----------------
typedef struct QNode
{
	elemtype license;//  汽车牌照
	elemtype moment;//  汽车进入停车场时刻
	struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;
status InitQueue(LinkQueue &Q)
{
	Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
	if(!Q.front)
	{
		printf("队列初始化失败\n");
		exit(1);
	}
	Q.front->next=NULL;
	return ok;
}
status EnQueue(LinkQueue &Q,elemtype license,elemtype moment)
{
	QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
	if(!p)
	{
		printf("入队分配节点失败\n");
		exit(1);
	}
	p->license=license;
	p->moment=moment;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return ok;
}
status DeQueue(LinkQueue &Q,elemtype &license,elemtype moment)
{
	if(Q.front==Q.rear)
	{
		printf("the Queue is empty . failed. \n");
		exit(1);
	}
	QueuePtr p=Q.front->next;
	license=p->license;
	moment=p->moment;
	Q.front->next=p->next;
	free(p);
	return ok;
}
status DisplayQueue(LinkQueue Q)
{
	QueuePtr p=Q.front->next;
	while(p!=NULL)
	{
		printf("%d\t",p->license);
		printf("%d\t",p->moment);
		p=p->next;
	}
	return ok;
}
//--------------链队列--------------------
//------------顺序栈实现-----------------
#define stack_init_size 100
#define stack_increment 10
typedef struct
{
	elemtype *base;
	elemtype *top_license;//汽车牌照
	elemtype *top_moment;//汽车进入停车场时间
	int stacksize;
	int length;
}SqStack;
status InitStack(SqStack &S)
{
	S.top_license=S.base=(elemtype *)malloc(sizeof(elemtype)*stack_init_size);
	S.top_moment=(elemtype *)malloc(sizeof(elemtype)*stack_init_size);
	if(!S.base)
	{
		printf("顺序栈初始化失败\n");
		exit(1);
	}
	S.length=0;
	S.stacksize=stack_init_size;
	return ok;
}
status push(SqStack &S,elemtype license,elemtype moment)
{
	if(S.top_license-S.base>=S.stacksize)
	{
		S.base=(elemtype *)realloc(S.base,sizeof(elemtype)*(S.stacksize+stack_increment));
		S.top_license=S.top_moment=S.base+S.stacksize;
		S.stacksize+=stack_increment;
	}
	S.length++;
	*S.top_license++=license;
	*S.top_moment++=moment;
	return ok;
}
status pop(SqStack &S,elemtype &license,elemtype &moment)
{
	if(S.top_license==S.base)
	{
		printf("the Stack is empty. Failed.");
		exit(1);
	}
	S.top_license--;
	S.top_moment--;
	license=*S.top_license;
	moment=*S.top_moment;
	S.length--;
	return ok;
}
status DisplayStack(SqStack S)
{
	while(S.top_license!=S.base)
	{
		S.top_license--;
		S.top_moment--;
		printf("%d\t",*S.top_license);
		printf("%d\t",*S.top_moment);
		printf("\n");
	}
	return ok;
}
//------------顺序栈---------------------
//----------停车场数据的处理------------
bool park_check(SqStack S,elemtype license)
	//检查停车场是否可以再停车--------
{
	if(S.length>=capacity)
		return false;
	else
		return true;
}
void welcome()
{
	printf("请按照以下格式输入  ('A',1,5)  A为到达,D为离去,E为输入结束,1为牌照,5为进入停车场时刻.否则出错\n");
}
status Input(SqStack &P,LinkQueue &Q,SqStack &S)
{
	int license_c,moment_c;//副本,记录
	int departure_moment;
	int license,moment;//汽车的牌照,进入停车场的时间
	scanf("('%c',%d,%d),",&flag,&license,&moment);
	printf("%c  %d  %d\n",flag,license,moment);
	switch(flag)
	{
	case 'A':
		{
		if(park_check(P,license))
		{
			printf("汽车 %d 进入停车场\n",license);
			push(P,license,moment);
			printf("成功进入\n");
			printf("现在有%d辆车\n",P.length);
		}
		else
		{
			printf("汽车 %d 停留在便道\n",license);
			printf("现在有%d辆车\n",P.length);
			EnQueue(Q,license,moment);
		}
		//DisplayStack(P);
		break;
		}
	case 'D':
		{
		while(1)
		{
			pop(P,license_c,moment_c);//弹出P
			if(license_c==license)
			{
				departure_moment=moment_c;
				break;
			}
			push(S,license_c,moment_c);//压入S
		}
		while(S.base!=S.top_license)
		{
			pop(S,license_c,moment_c);
			push(P,license_c,moment_c);
		}
		printf("汽车 %d 离开停车场 ,停留时间 %d\n",license,moment-departure_moment);
		printf("现在有%d辆车\n",P.length);
		if(Q.front!=Q.rear)
		{
		DeQueue(Q,license_c,moment_c);
		push(P,license_c,moment_c);
		printf("汽车 %d 进入停车场\n",license_c);
		printf("现在有%d辆车\n",P.length);
		}
		break;
		}
	case 'E':
		{
		printf("整个过程结束\n");
		break;
		}
	default:break;
	}
	//printf("操作成功.\n\n");
	return ok;
}
void main()
{
	SqStack P;//停车场栈
	LinkQueue Q;//队列 便道
	SqStack S;//有车辆离开时,临时停放让路的车 栈
	InitStack(P);InitStack(S);InitQueue(Q);
	welcome();
	while(1)
	{
		Input(P,Q,S);
		printf("\n");
		if(flag=='E')
			break;
	}
}

QQ图片20141031005347

发表评论

邮箱地址不会被公开。 必填项已用*标注