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

实习指导 [实习题目]： 停车场管理。 [实习内容]： 首先，实现栈和队列的基本操作，在此基础上，实现停车场管理。 停车场管理问题描述：设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。在停车场内，汽车按到达的先后次序，由北向南依次排列（假设大门在最南端）。若车场内已停满n辆车，则后来的汽车需在门外的便道上等候，当有车开走时，便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门后，其它车辆再按原次序返回车场。每辆车离开停车场时，应按其停留时间的长短交费（在便道上停留的时间不收费）。 试编写程序，模拟上述管理过程。要求以顺序栈模拟停车场，以链队列模拟便道。 从终端读入汽车到达或离去的数据，每组数据包括三项： 是“到达”还是“离去”； 汽车牌照号码； “到达”或“离去”的时刻。 与每组输入信息相应的输出信息为： 如果是到达的车辆，则输出其在停车场中或便道上的位置； 如果是离去的车辆，则输出其在停车场中停留的时间和应交的费用。 （提示：需另设一个栈，临时停放为让路而从车场退出的车。） [实习目的]： 通过实习，熟悉栈和队列的基本特点，掌握利用栈和队列解决具体问题的方法。 [实习步骤]： 实现顺序栈的基本操作 基本思路 首先实现一个整型顺序栈的初始化、判栈空、进栈、出栈等基本操作，并在主程序中调用这些操作。 基本框架 #include stdio.h #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 malloc.h （2）在上述程序框架的类型定义部分，增加如下链队列定义： typedef int QueueElementType; typedef struct Node { QueueElementType data; /*数据域*/ struct Node *next; /*指针域*/ } LinkQueueNode; typedef struct { LinkQueueNode * front; LinkQueueNode * rear; } LinkQueue; （3）在上述程序框架的函数原型说明部分，增加如下链队列的操作