数据结构--停车场管理

　

停车场管理

停车场管理

【问题描述】

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

【基本要求】

以栈模拟停车场，以队列模拟车场外的便道，按照以终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应该缴纳的费用（在便道上停留的时间不收费）。

【测试数据】

设n = 2，输入数据为：（A,1,50）,(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表示输入结束。

【程序实现】

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
struct stackstruct                     /*栈的结构体*/
{
	int id;
	int time;
	struct stackstruct *pre;
	struct stackstruct *next;
};

struct queuestruct
{
	int id;
	struct queuestruct *next;
};

struct stackstruct *stackhead1, *stackend1;
struct stackstruct *stackhead2, *stackend2;
struct queuestruct *queuehead, *queueend;
int stack1count, stack2count;                         /*栈中元素总数*/
int queuecount;                         /*队列中元素总数*/

void push(int flag, struct stackstruct *p)
{
	struct stackstruct *stack;
	if (flag == 0)                  /*栈1进栈操作*/
	{
		if (stack1count == 0)
		{
			stackhead1 = (struct stackstruct *)malloc(sizeof(struct stackstruct));
			stackhead1->id = p->id;
			stackhead1->time = p->time;
			stackhead1->next = NULL;
			stackhead1->pre = NULL;
			stackend1 = stackhead1;
		}
		else
		{
			stack = (struct stackstruct *)malloc(sizeof(struct stackstruct));
			stack->id = p->id;
			stack->time = p->time;
			stackend1->next = stack;
			stack->pre = stackend1;
			stack->next = NULL;
			stackend1 = stack;
		}
		stack1count++;
	}
	else if (flag == 1)               /*栈2进栈操作*/
	{
		if (stack2count == 0)
		{
			stackhead2 = (struct stackstruct *)malloc(sizeof(struct stackstruct));
			stackhead2->id = p->id;
			stackhead2->time = p->time;
			stackhead2->next = NULL;
			stackhead2->pre = NULL;
			stackend2 = stackhead2;
		}
		else
		{
			stack = (struct stackstruct *)malloc(sizeof(struct stackstruct));
			stack->id = p->id;
			stack->time = p->time;
			stackend2->next = stack;
			stack->pre = stackend2;
			stack->next = NULL;
			stackend2 = stack;
		}
		stack2count++;
	}
}

struct stackstruct *pop(int id, int time)
{
	struct stackstruct *stack;
	stack = (struct stackstruct *)malloc(sizeof(struct stackstruct));

	if (stackend1->id != id)
	{
		stack->id = stackend1->id;
		stack->time = stackend1->time;
		stack->pre = stackend1->pre;
		free(stackend1);
		stackend1 = stack->pre;
		stackend1->next = NULL;
		stack1count--;
	}
	else
	{
		stack->id = stackend1->id;
		stack->time = stackend1->time;
		stack->pre = stackend1->pre;
		printf("%d号汽车出停车场\n", id);
		printf("停车场停留时间: %d\n", time - stack->time);
		printf("应该缴纳的费用(单价: 5): %d\n", 5 * (time - stack->time));
		free(stackend1);
		if (--stack1count == 0)
			stackend1 = stackhead1 = NULL;
		else
		{
			stackend1 = stack->pre;
			stackend1->next = NULL;
		}
		stack = NULL;
	}
	return stack;
}

struct stackstruct *pop1()
{
	struct stackstruct *stack;
	stack = (struct stackstruct *)malloc(sizeof(struct stackstruct));

	stack->id = stackend2->id;
	stack->time = stackend2->time;
	stack->pre = stackend2->pre;
	free(stackend2);
	stackend2 = stack->pre;
	stack2count--;

	return stack;
}

void Enqueue(struct stackstruct *p)
{
	struct queuestruct *queue;
	if (queuecount == 0)
	{
		queuehead = (struct queuestruct *)malloc(sizeof(struct queuestruct));
		queuehead->id = p->id;
		queuehead->next = NULL;
		queueend = queuehead;
	}
	else
	{
		queue = (struct queuestruct *)malloc(sizeof(struct queuestruct));
		queue->id = p->id;
		queue->next = NULL;
		queueend->next = queue;
		queueend = queue;
	}
	queuecount++;
}

struct stackstruct *Dequeue(int time)
{
	struct stackstruct *stack;
	stack = (struct stackstruct *)malloc(sizeof(struct stackstruct));

	stack->id = queuehead->id;
	stack->time = time;
	if (--queuecount == 0)
	{
		queuehead = NULL;
		queueend = NULL;
	}
	else
		queuehead = queuehead->next;
	return stack;
}
int main()
{
	int n;
	char s;
	struct stackstruct *p;

	printf("输入狭长通道可停放汽车数量: ");
	scanf("%d", &n);
	getchar();
	stack1count = stack2count = queuecount = 0;
	p = (struct stackstruct *)malloc(sizeof(struct stackstruct));

	while (scanf("(%c,%d,%d)", &s, &p->id, &p->time) != EOF)
	{
		getchar();
		if (s == 'E')
			break;
		else if (s == 'A')                /*汽车到达*/
		{
			if (stack1count < n)                 /*栈未满，进栈操作*/
			{
				push(0, p);
				printf("%d号汽车进入停车场\n", stackend1->id);
				printf("进入停车场时间: %d\n", stackend1->time);
				printf("停车位置: %d\n", stack1count);
			}
			else                                /*栈满，进队列操作*/
			{
				Enqueue(p);
				printf("%d号汽车进入便道\n", p->id);
				printf("进入便道时间: %d\n", p->time);
				printf("便道位置: %d\n", queuecount);
			}
		}
		else if (s == 'D')                /*汽车离去*/
		{
			struct stackstruct *temp;
			while ((temp = pop(p->id, p->time)) != NULL)
			{
				push(1, temp);                  
			}
			while (stack2count != 0)
			{
				push(0, pop1());
			}
			if (queuecount != 0)
			{
				push(0, Dequeue(p->time));
				printf("%d号汽车进入停车场\n", stackend1->id);
				printf("进入时间: %d\n", stackend1->time);
				printf("停车位置: %d\n", stack1count);
			}
		}
	}
	return 0;
}

实现这个程序主要是利用了两个栈和一个队列。其中队列模拟便道，一个栈用于模拟停车场，另一个栈主要是用于模拟汽车离开时后面汽车出停车场等待汽车离开后重新进入停车场的过程。主要是利用了pop和push的基本操作，队列也是运用了最基本的进出队列操作。

相关阅读

关于layuiAdmin 后台管理模板购买授权的问题

购买授权之前，建议认真阅读下述 “解惑”，以免造成不必要的困惑。另外也可以阅读 《layui 付费产品服务条款》注意：layuiAdmin 受国

第七章 软件配置管理

本章内容提要软件配置管理的作用软件配置管理的相关概念建立软件配置管理环境版本控制系统集成分支管理变更管理配置审计和配置状

python之Django的入门08------事务管理、悲观锁、乐观

上一篇文章链接Django07我们接着上一篇文章的基础上，来继续了解进一步的Django框架一.事务管理在实际项目里，事务管理是一个很重要

数据结构之二叉排序树（C语言实现）

一、基本概念 1.二叉排序树 二叉排序树（Binary sort tree，BST），又称为二叉查找树，或者是一棵空树；或者是具有下列性质的二叉树： (1)若

数据结构与算法（一）---重点复习知识

吐槽 国庆假期第二天，去实验室开门，给猫猫铲丑丑，然后给她换猫粮，换水，喂这货吃的emmmmmm，然后今天就把之前在极客时间上买的数据结构与