数据结构上机--停车场管理问题.doc

实习指导
[实习题目]:
停车场管理。
[实习内容]:
首先,实现栈和队列的基本操作,在此基础上,实现停车场管理。
停车场管理问题描述:设停车场是一个可停放n辆车的狭长通道,且只有一个大门可供汽车进出。在停车场内,汽车按到达的先后次序,由北向南依次排列(假设大门在最南端)。若车场内已停满n辆车,则后来的汽车需在门外的便道上等候,当有车开走时,便道上的第一辆车即可开入。当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门后,其它车辆再按原次序返回车场。每辆车离开停车场时,应按其停留时间的长短交费(在便道上停留的时间不收费)。
试编写程序,模拟上述管理过程。要求以顺序栈模拟停车场,以链队列模拟便道。
从终端读入汽车到达或离去的数据,每组数据包括三项:
是“到达”还是“离去”;
汽车牌照号码;
“到达”或“离去”的时刻。
与每组输入信息相应的输出信息为:
如果是到达的车辆,则输出其在停车场中或便道上的位置;
如果是离去的车辆,则输出其在停车场中停留的时间和应交的费用。
(提示:需另设一个栈,临时停放为让路而从车场退出的车。)
[实习目的]:
通过实习,熟悉栈和队列的基本特点,掌握利用栈和队列解决具体问题的方法。
[实习步骤]:
实现顺序栈的基本操作
基本思路
首先实现一个整型顺序栈的初始化、判栈空、进栈、出栈等基本操作,并在主程序中调用这些操作。
基本框架
#include <>
#define TRUE 1
#define FALSE 0
#define Stack_Size 50
typedef int StackElementType;
typedef struct
{
StackElementType elem[Stack_Size];
int top;
} SeqStack;
/* 以下是函数原形说明。注意函数头后面有分号。*/
void InitStack(SeqStack *s);
int IsEmpty(SeqStack *s);
int Push(SeqStack *s, StackElementType e);
int Pop(SeqStack *s, StackElementType *e);
/* 以下是函数定义。注意函数头后面无分号。*/
void InitStack(SeqStack *s)
/* 顺序栈的初始化函数*/
{ ……; }
int IsEmpty(SeqStack *s)
/* 顺序栈的判栈空函数*/
{ ……; }
int Push(SeqStack *s, StackElementType e)
/* 顺序栈的进栈函数*/
{ ……; }
Status Pop(SeqStack *s, StackElementType *e)
/* 顺序栈的出栈函数*/
{ ……; }
void main(void)
{ ……; }
要点提示
主程序的基本过程如下:
void main(void)
{ SeqStack my_stack ;
StackElementType x;
StackElementType y;
InitStack(&my_stack );
if(IsEmpty(&my_stack)) 打印:“my_stack已被初始化为空栈”;
提示输入10个正整数;
循环10次,执行下面操作:
{
读入整数x;
Push(&my_stack, x);
}
while(!IsEmpty(&my_stack))
{
Pop(&my_stack, &y);
打印y;
}
}
测试数据
读入数据:19,14,23,01,68,20,84,27,55,11
打印结果:读入序列的逆序。
同时实现顺序栈和链队列的基本操作
基本思路
在前面已经实现的整型顺序栈的基础上,进一步实现一个整型链队列的基本操作。
基本框架
(1)在上述程序框架的前面,增加如下包含语句:
#include <>
(2)在上述程序框架的类型定义部分,增加如下链队列定义:
typedef int QueueElementType;
typedef struct Node
{
QueueElementType data; /*数据域*/
struct Node *next; /*指针域*/
} LinkQueueNode;
typedef struct
{
LinkQueueNode * front;
LinkQueueNode * rear;
} LinkQueue;
(3