停车场管理系统课程设计

一、程序中所采用的数据结构及存储结构的说明

以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。栈以顺序结构实现，队列以链表实现。

程序中分别采用了“栈”和“队列”作为其存储结构。

“栈”的定义可知，每一次入栈的元素都在原栈顶元素之上成为新的元素，每一次出栈的元素总是当前栈顶元素使次栈元素成为新的栈顶元素，即最后进栈者先出栈。程序中采用的结构是：

typedef struct NODE{ CarNode *stack[MAX+1]; int top;

}SeqStackCar; /*模拟车库*/

“队列”是限定所有插入操作只能在表的一端进行，而所有的删除操作都只能在表的另一端进行。插入端叫队尾，删除端叫对头。按先进先出规则进行。程序中采用的结构是：

typedef struct Node{ QueueNode *head; QueueNode *rear;

}LinkQueueCar; /*模拟通道*/ 二、算法的设计思想

由于停车场是一个狭窄通道，而且只有一个大门可供汽车进出，问题要求汽车停车场内按车辆到达时间的先后顺序，依次由北向南排列。由此很容易联想到数据结构中的堆栈模型，因此可首先设计一个堆栈，以堆栈来模拟停车场，又每个汽车的车牌号都不一样，这样一来可以根据车牌号准确找到汽车位置，所以堆栈里的数据元素我设计成汽车的车牌号。当停车场内某辆车要离开时，在他之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入停车场。这是个一退一进的过程，而且让道的汽车必须保持原有的先后顺序，因此可再设计一个堆栈，以之来暂时存放为出站汽车暂时让道的汽车车牌号。当停车场满后，继续进来的汽车需要停放在停车场旁边的便道上等候，若停车场有汽车开走，则按排队的先后顺序依次进站，最先进入便道的汽车将会最先进入停车场，这完全是一个先进先出模型，因此可设计一个队列来模拟

便道，队列中的数据元素仍然设计成汽车的车牌号。另外，停车场根据汽车在停车场内停放的总时长来收费的，在便道上的时间不计费，因此必须记录车辆进入停车场时的时间，车辆离开停车场时的时间不需要记录，当从终端输入时可直接使用。由于时间不象汽车一样需要让道，我设计了一个顺序表来存放时间。又用顺序表用派生法设计了一个堆栈，恰好满足上面模拟停车场的需要。 三、时间复杂度的分析

说明：对时间复杂度的分析，均指在最坏情况下的时间复杂度。 在栈结构中：

(1) 初始化栈（即车库），使车库为空的，此时,时间复杂度=O(max)。 (2) 停车最坏的情况是要车位已经满，此时,时时间复杂度=O(1)。 (3) 关于车辆离开的时间复杂度=O(max)。 (4) 车场信息的显示的时间复杂度=O(1)。 在队列结构中：

(1) 出场车的信息的时间复杂度＝O（1）。

(2) 判断通道上是否有车及车站是否已满，此时，时间复杂度O=（max）。 (3) 车辆停车费用的时间复杂度O=（1）。 四.设计原理、框图

五.运行结果 车辆进入车场：以堆栈来模拟停车场和以堆栈里的数据元素我设计成汽车的车牌号 初始化车站, 初始化让路的临时栈, 初始化通道 车辆到达 车场已满，车进便道 车场未满，车进车场 判断车场是否已满 输入车子到达时间,车牌号 未满 车进入车场 判断车场内是否有车 不做任何计算 无有 输入离开车辆的离开时间,进行停车费用的计算 此车后面的车辆退出并进入临时栈 车子离开

车场已满：

车辆离开，并收费：

列出车场信息：

列出车道信息：

2.7程序

#include #include #include

/*------------------------------------------------------------------------------*/ #define MAX 3 /*车库容量*/ #define price 0.05 /*每车每分钟费用*/ typedef struct time{ int hour; int min;

}Time; /*时间结点*/ typedef struct node{ char num[10]; Time reach; Time leave;

}CarNode; /*车辆信息结点*/ typedef struct NODE{ CarNode *stack[MAX+1]; int top;

}SeqStackCar; /*模拟车场*/ typedef struct car{ CarNode *data; struct car *next; }QueueNode; typedef struct Node{

QueueNode *head; QueueNode *rear;

}LinkQueueCar; /*模拟通道*/

/*------------------------------------------------------------------------------*/ void InitStack(SeqStackCar *); /*初始化栈*/ int InitQueue(LinkQueueCar *); /*初始化便道*/ int Arrival(SeqStackCar *,LinkQueueCar *); /*车辆到达*/

void Leave(SeqStackCar *,SeqStackCar *,LinkQueueCar *); /*车辆离开*/ void List(SeqStackCar,LinkQueueCar); /*显示存车信息*/ /*------------------------------------------------------------------------------*/ void main() {

SeqStackCar Enter,Temp; LinkQueueCar Wait; int ch;

InitStack(&Enter); /*初始化车站*/

InitStack(&Temp); /*初始化让路的临时栈*/ InitQueue(&Wait); /*初始化通道*/ while(1) {

printf(\"\\n1.车辆到达\"); printf(\" 2.车辆离开\"); printf(\" 3.列表显示 \"); printf(\" 4.退出系统\"); while(1) {

scanf(\"%d\ if(ch>=1&&ch<=4)break;

else printf(\"\\nplease choose： 1|2|3|4.\"); }

switch(ch) {

case 1:Arrival(&Enter,&Wait);break; /*车辆到达*/ case 2:Leave(&Enter,&Temp,&Wait);break; /*车辆离开*/ case 3:List(Enter,Wait);break; /*列表打印信息*/ case 4:exit(0); /*退出主程序*/ default: break; } } }

/*------------------------------------------------------------------------------*/ void InitStack(SeqStackCar *s) /*初始化栈*/ { int i; s->top=0;

for(i=0;i<=MAX;i++) s->stack[s->top]=NULL; }

int InitQueue(LinkQueueCar *Q) /*初始化便道*/ {

Q->head=(QueueNode *)malloc(sizeof(QueueNode)); if(Q->head!=NULL) {

Q->head->next=NULL; Q->rear=Q->head; return(1); }

else return(-1); }

void PRINT(CarNode *p,int room) /*打印出场车的信息*/

{

int A1,A2,B1,B2;

printf(\"\\n请输入离开的时间:/**:**/\");

scanf(\"%d:%d\ printf(\"\\n离开车辆的车牌号为:\"); puts(p->num);

printf(\"\\n其到达时间为: %d:%d\ printf(\"离开时间为: %d:%d\ A1=p->reach.hour; A2=p->reach.min; B1=p->leave.hour; B2=p->leave.min;

printf(\"\\n应交费用为:%2.1f元\ free(p); }

int Arrival(SeqStackCar *Enter,LinkQueueCar *W) /*车辆到达*/ {

CarNode *p; QueueNode *t;

p=(CarNode *)malloc(sizeof(CarNode)); flushall();

printf(\"\\n请输入车牌号(例如：闽A1234):\"); gets(p->num);

if(Enter->topEnter->top++;

printf(\"\\n车辆在车场第%d位置.\ printf(\"\\n请输入到达时间:/**:**/\");

scanf(\"%d:%d\ Enter->stack[Enter->top]=p;

return(1); }

else /*车场已满,车进便道*/ {

printf(\"\\n该车须在便道等待!\");

t=(QueueNode *)malloc(sizeof(QueueNode)); t->data=p; t->next=NULL; W->rear->next=t; W->rear=t; return(1); } }

void Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W) { /*车辆离开*/ int i, room; CarNode *p,*t; QueueNode *q;

/*判断车场内是否有车*/ if(Enter->top>0) /*有车*/ {

while(1) /*输入离开车辆的信息*/ {

printf(\"\\n请输入车在车场的位置/1--%d/：\ scanf(\"%d\

if(room>=1&&room<=Enter->top) break; }

while(Enter->top>room) /*车辆离开*/ {

Temp->top++;

Temp->stack[Temp->top]=Enter->stack[Enter->top]; Enter->stack[Enter->top]=NULL; Enter->top--; }

p=Enter->stack[Enter->top]; Enter->stack[Enter->top]=NULL; Enter->top--; while(Temp->top>=1) {

Enter->top++;

Enter->stack[Enter->top]=Temp->stack[Temp->top]; Temp->stack[Temp->top]=NULL; Temp->top--; }

PRINT(p,room);

/*判断通道上是否有车及车站是否已满*/

if((W->head!=W->rear)&&Enter->topq=W->head->next; t=q->data; Enter->top++;

printf(\"\\n便道的%s号车进入车场第%d位置.\ printf(\"\\n请输入现在的时间/**:**/:\");

scanf(\"%d:%d\ W->head->next=q->next;

if(q==W->rear) W->rear=W->head; Enter->stack[Enter->top]=t; free(q); }

else printf(\"\\n便道里没有车.\\n\");

}

else printf(\"\\n车场里没有车.\"); /*没车*/ }

void List1(SeqStackCar *S) /*列表显示车场信息*/ { int i;

if(S->top>0) /*判断车站内是否有车*/ {

printf(\"\\n车场:\");

printf(\"\\n 位置 到达时间 车牌号\\n\"); for(i=1;i<=S->top;i++) {

printf(\" %d \

printf(\"%d:%d \ puts(S->stack[i]->num); } }

else printf(\"\\n车场里没有车\"); }

void List2(LinkQueueCar *W) /*列表显示便道信息*/ {

QueueNode *p; p=W->head->next;

if(W->head!=W->rear) /*判断通道上是否有车*/ {

printf(\"\\n等待车辆的号码为:\"); while(p!=NULL) {

puts(p->data->num); p=p->next;

} }

else printf(\"\\n便道里没有车.\"); }

void List(SeqStackCar S,LinkQueueCar W) {

int flag,tag; flag=1; while(flag) {

printf(\"\\n请选择 1|2|3:\");

printf(\"\\n1.车场\\n2.便道\\n3.返回\\n\"); while(1) {

scanf(\"%d\ if(tag>=1||tag<=3) break; else printf(\"\\n请选择 1|2|3:\"); } switch(tag) {

case 1:List1(&S);break; /*列表显示车场信息*/ case 2:List2(&W);break; /*列表显示便道信息*/ case 3:flag=0;break; default: break; } }