备案控制台
开发者社区 云计算 文章 正文

数据结构电梯模拟 不限电梯数 不限楼层数 100梯1000层

2022-04-21 205
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 本文提供数据结构教材习题 “电梯模拟” 的一种解答。

电梯模拟

实验要求

【问题描述】

设计一个电梯模拟系统。这是一个离散的模拟程序，因为电梯系统是乘客和电梯等 “活动体” 构成的集合，虽然他们彼此交互作用，但他们的行为是基本独立的。在离散的模拟中，以模拟时钟决定每个活动体的动作发生的时刻和顺序，系统在某个模拟瞬间处理有待完成的各种事情，然后把模拟时钟推进到某个动作预定要发生的下一时刻。

【基本要求】

  1. 模拟某校五层教学楼的电梯系统。该楼有一个自动电梯，能在每层停留。五个楼层由下至上依次称为地下层、第一层、第二层、第三层和第四层，其中第一层是大楼的迸出层，即是电梯的 “本垒层”，电梯 “空闲” 时，将来到该层候命。
  2. 乘客可随机地进出于任何层。对每个人来说，他有一个能容忍的最长等待时间，一旦等候电梯时间过长，他将放弃。

  3. 模拟时钟从 0 开始，时间单位为 0.1 秒。人和电梯的各种动作均要耗费一定的时间单位 ( 简记为 t )，比如：

    • 有人进出时，电梯每隔 40t 测试一次，若无人进出，则关门；
    • 关门和开门各需要 20t；
    • 每个人进出电梯均需要 25t；
    • 如果电梯在某层静止时间超过 300t，则驶回 1 层候命。
    • 电梯加速需要 15t，向上移动需要 51t，向上减速需要 14t，向下移动需要 61t，向下减速需要 23t ( 电梯下降比上升慢 )
  4. 按时序显示系统状态的变化过程：发生的全部人和电梯的动作序列。

【测试数据】

模拟时钟 Time 的初值为 0，终值可在 500~10000 范围内逐步增加。

【选做内容】

  1. 增加电梯数量，模拟多梯系统。
  2. 某高校的一座 30 层住宅楼有三部自动电梯，每梯最多载客 15 人。大楼每层八户，每户平均 3.5 人，每天早晨平均每户有 3 人必须在 7 时之前离开大楼去上班或上学。模拟该电梯系统，并分析分别在一梯、二梯和三梯运行情况下，下楼高峰期间各层的住户应提前多少时间候梯下楼？研究多梯运行最佳策略。

【输入】

自行设定输入格式，要求至少能在 500~10000 范围内自由输入电梯系统运行时间，可以适度拓展，如根据输入的楼层数和电梯数来确定电梯模拟时的总楼层数和总电梯数

【输出】

按时序显示系统状态的变化过程：发生的全部人和电梯的动作序列。

可以适度拓展，如图形化界面等。

设计思路

设计要求

设计出的电梯系统需满足如下要求：

  • 满足题目所有基本要求
  • 电梯数量 和 楼层总数 由用户输入设定，即 任意电梯数与楼层数
  • 电梯系统运行时间由用户输入设定
  • 电梯容量有上限，且由用户输入设定
  • 电梯本垒层需根据用户输入的楼层总数决定，即当楼层总数较少时本垒层设置为第一层，当楼层总数较多时本垒层设置为楼的中间层
  • 电梯调度优化，减少电梯资源浪费

最终，设计出的电梯系统满足上述所有要求。

设计实现

类和对象

在电梯模拟系统中，有电梯和乘客两个对象，需要模拟的也就是它们各自发生的事件与其之间的交互。

更细致地划分，可分为如下几个对象：

  • 电梯：有楼层总数、当前楼层、按钮等属性，有状态转换、判断是否需要停在下一层等方法，需要注意的是，在代码实现中，每部电梯内都有对应楼层的按钮，但每一层楼只有一个上升按钮和一个下降按钮，即在每一层所有电梯共用一对上升下降按钮（为了问题的简化）
  • 乘客栈：为了模拟 “先进入的乘客后出去” 这一实际情况，需对每一部电梯在每一层设置一个乘客栈，且应封装在电梯类内
  • 乘客：有出现楼层、目标楼层、编号、放弃时间等属性，有出现、放弃等方法
  • 等待队列：为了模拟人排队等候电梯，需在每一层设置一个上升队列和下降队列

模拟方法

离散事件模拟一般有两种可选方法，一种是事件表推进法，另一种是时间递增法。本实验采用时间递增法，即设定一个记录当前时间的变量 time，每次循环使 time++，并处理当前时间下所发生的事情。

有限状态机

一台电梯实际上是一个 FSM，有 Opening、Opened、Closing 等状态，每种状态有一定的持续时间，当时间到时，就要判断是否需要改变状态、改变成什么状态

电梯调度优化

为每一层的上升下降按钮设置四个属性：

  • 0：未被按下
  • 1：按下但尚未有电梯响应该请求
  • -1：按下且有电梯响应该请求，但电梯未到达该层
  • -2：电梯已到达该层未该层的上升或下降请求工作

从而当考察某一台处于闲置状态状态的电梯是否需要去响应某一层的请求时，只需要看该层对应按钮是否变为负值，若变为负值则无需调度该电梯，否则需要

且在设置了这四个属性之后，绝大多数情况下不会出现两台及以上的电梯同时在某一层一起为该层的上升队列（或下降队列）服务的情况，只有当该层本来就有一台电梯在工作且另一台电梯内有人需要到该层才会出现这样的情况，从而很好地减少电梯资源的浪费

综合

综合而言，设计思路即主程序里主要是一个大循环，每次循环使 time++，并完成当前时间要干的事情。而当前时间要干的事情分为 两类：人的出现入队按按钮放弃（不以 FSM 为主动者）和各个电梯的状态的考察与改变（以 FSM 为主动者）。实际实现中，将各个电梯的状态的考察与改变划分为对 Waiting 状态的电梯的唤醒与对其他状态下的电梯的考察与改变。

#include "system.h"

using namespace std;

int g_current_time = 0;
int g_capacity;
int g_max_time;
int g_elevator_num;
int g_total_floor; 
int g_id = 0;
int g_next_passenger_inter_time = 0;

int g_new_num = 0;
int g_get_in_num = 0;
int g_get_out_num = 0;
int g_give_up_num = 0;

int *g_call_up, *g_call_down;

WaitQueuePtr *g_wait_queue; // g_wait_queue[UP]: up, [DOWN]: down

ElevatorPtr g_elevator;

// Stack
// -------------------------------------------------------------------------
void InitStack(PassengerStack &s)
{
    s.base = (PassengerPtr *)malloc(STACK_INIT_SIZE * sizeof(PassengerPtr));
    if (!s.base)
    {
        cout << "overflow" << endl;
        exit(OVERFLOW);
    }
    s.top = s.base;
    s.stack_size = STACK_INIT_SIZE;
}

void DestroyStack(PassengerStack &s)
{
    PassengerPtr *p = s.base;
    while (p != s.top)
    {
        if (*p)
            free(*p); // free passenger in the elevator
        free(p);      // free passenger ptr in the elevator
        ++p;
    }
}

bool StackEmpty(PassengerStack &s)
{
    return s.base == s.top;
}

void Push(PassengerStack &s, PassengerPtr p)
{
    if (s.top - s.base >= s.stack_size)
    {
        s.base = (PassengerPtr *)realloc(s.base, (s.stack_size + STACK_INCREMENT) * sizeof(PassengerPtr));
        if (!s.base)
        {
            cout << "overflow" << endl;
            exit(OVERFLOW);
        }
        s.top = s.base + s.stack_size;
        s.stack_size += STACK_INCREMENT;
    }
    *s.top++ = p;
}

PassengerPtr Pop(PassengerStack &s)
{
    if (s.base == s.top)
    {
        cout << "stack empty" << endl;
        exit(STACK_EMPTY);
    }
    return *(--s.top);
}
// -------------------------------------------------------------------------

// Queue
// -------------------------------------------------------------------------
void InitQueue(WaitQueue &q)
{
    q.front = q.rear = (WaitQueueNodePtr)malloc(sizeof(WaitQueueNode));
    if (!q.front)
    {
        cout << "overflow" << endl;
        exit(OVERFLOW);
    }
    q.num = 0;
    q.front->data = NULL;
    q.front->next = NULL;
}

void DestroyQueue(WaitQueue &q)
{
    while (q.front)
    {
        q.rear = q.front->next;
        if (q.front->data)
            free(q.front->data); // free passenger in wait queue, it will not conflict with DestroyStack
        free(q.front);
        q.front = q.rear;
    }
}

bool QueueEmpty(WaitQueue &q)
{
    return q.front == q.rear;
}

void EnQueue(WaitQueue &q, PassengerPtr p)
{
    WaitQueueNodePtr t = (WaitQueueNodePtr)malloc(sizeof(WaitQueueNode));
    if (!t)
    {
        cout << "overflow" << endl;
        exit(OVERFLOW);
    }
    t->data = p;
    t->next = NULL;
    q.rear->next = t;
    q.rear = t;
    ++q.num;
}

PassengerPtr DeQueue(WaitQueue &q)
{
    if (q.front == q.rear)
    {
        cout << "queue empty" << endl;
        exit(QUEUE_EMPTY);
    }
    WaitQueueNodePtr t = q.front->next;
    PassengerPtr p = t->data;
    q.front->next = t->next;
    if (q.rear == t)
        q.rear = q.front;
    free(t); 
    --q.num; 
    return p;
}

int NumBefore(WaitQueue &q, WaitQueueNodePtr p)
{
    // assume that p won't be NULL
    int count = 0;
    WaitQueueNodePtr t = q.front;
    while (t->next != p)
    {
        ++count;
        t = t->next;
    }
    return count;
}

void CheckQueueForGiveUp(enum WaitQueueType type, int floor)
{
    WaitQueueNodePtr p = g_wait_queue[type][floor].front;
    while (p->next)
    {
        if (p->next->data->give_up_time > 0) 
        {
            p = p->next;
            p->data->give_up_time--;
        }
        else
        {
            int i;
            for (i = 0; i < g_elevator_num; ++i)
            {
                if (g_elevator[i].current_floor == floor &&
                    (g_elevator[i].move == OPENING || g_elevator[i].move == OPENED) &&
                    ((type == UP && g_elevator[i].state != GOING_DOWN) || (type == DOWN && g_elevator[i].state != GOING_UP)) &&
                    g_elevator[i].passenger_num + NumBefore(g_wait_queue[type][floor], p->next) < g_elevator[i].capacity)
                    break;
            }
            if (i < g_elevator_num)
                p = p->next;
            else
            {
                // should leave
                ++g_give_up_num;
                PassengerPtr pp = p->next->data;
                --g_wait_queue[type][floor].num;
                WaitQueueNodePtr temp = p->next;
                p->next = temp->next;
                if (temp == g_wait_queue[type][floor].rear)
                    g_wait_queue[type][floor].rear = p;
                Show(GIVE_UP, pp->id, pp->in_floor, pp->out_floor, -1, -1);
                free(pp);
                free(temp);
            }
        }
    }
}

void CheckGiveUp()
{
    for (int i = 0; i < g_total_floor; ++i)
    {
        CheckQueueForGiveUp(UP, i);
        CheckQueueForGiveUp(DOWN, i);
    }
}
// -------------------------------------------------------------------------

// Passenger
void NewPassenger()
{
    PassengerPtr p = (PassengerPtr)malloc(sizeof(Passenger));
    if (!p)
    {
        cout << "overflow" << endl;
        exit(OVERFLOW);
    }
    ++g_new_num;
    p->id = g_id++;
    p->give_up_time = rand() % MAX_GIVE_UP_TIME + 300; // can't be 0
    p->in_floor = rand() % g_total_floor;
    p->out_floor = rand() % g_total_floor;
    while (p->in_floor == p->out_floor)
        p->out_floor = rand() % g_total_floor;
    if (p->in_floor < p->out_floor)
    {
        EnQueue(g_wait_queue[UP][p->in_floor], p);
        if (!g_call_up[p->in_floor])
            g_call_up[p->in_floor] = 1;
    }
    else
    {
        EnQueue(g_wait_queue[DOWN][p->in_floor], p);
        if (!g_call_down[p->in_floor])
            g_call_down[p->in_floor] = 1;
    }
    Show(NEW_PASSENGER, p->id, p->in_floor, p->out_floor, -1, -1);
    g_next_passenger_inter_time = rand() % MAX_INTER_TIME + 50; 
}

bool PassengerOut(int lift)
{
    if (!StackEmpty(g_elevator[lift].stack_array[g_elevator[lift].current_floor]))
    {
        // steps: pop -> change elevator attributes -> show -> delete sb. -> return true
        ++g_get_out_num;
        PassengerPtr pp = Pop(g_elevator[lift].stack_array[g_elevator[lift].current_floor]);
        int i;
        for (i = 0; i < g_elevator[lift].passenger_num; ++i)
            if (g_elevator[lift].passenger_id[i] == pp->id)
                break;
        for (int j = i + 1; j < g_elevator[lift].passenger_num; ++j)
            g_elevator[lift].passenger_id[j - 1] = g_elevator[lift].passenger_id[j];
        --g_elevator[lift].passenger_num;
        Show(PASSENGER_OUT, pp->id, pp->in_floor, pp->out_floor, lift, pp->out_floor);
        free(pp);
        return true;
    }
    return false;
}

bool PassengerIn(int lift)
{
    // only go in one passenger
    if (g_elevator[lift].passenger_num == g_elevator[lift].capacity)
        return false;
    switch (g_elevator[lift].state)
    {
    case GOING_UP:
    {
        if (!g_wait_queue[UP][g_elevator[lift].current_floor].num)
            return false;
        ++g_get_in_num;
        PassengerPtr pp = DeQueue(g_wait_queue[UP][g_elevator[lift].current_floor]);
        Push(g_elevator[lift].stack_array[pp->out_floor], pp);
        g_elevator[lift].passenger_id[g_elevator[lift].passenger_num++] = pp->id;
        g_elevator[lift].call_car[pp->out_floor] = 1;
        Show(PASSENGER_IN, pp->id, pp->in_floor, pp->out_floor, lift, pp->in_floor);
        return true;
    }

    case GOING_DOWN:
    {
        if (!g_wait_queue[DOWN][g_elevator[lift].current_floor].num)
            return false;

        ++g_get_in_num;
        PassengerPtr pp = DeQueue(g_wait_queue[DOWN][g_elevator[lift].current_floor]);
        Push(g_elevator[lift].stack_array[pp->out_floor], pp);
        g_elevator[lift].passenger_id[g_elevator[lift].passenger_num++] = pp->id;
        g_elevator[lift].call_car[pp->out_floor] = 1;
        Show(PASSENGER_IN, pp->id, pp->in_floor, pp->out_floor, lift, pp->in_floor);
        return true;
    }

    case IDLE:
        exit(UNKNOWN_ERROR);
    }
}
// -------------------------------------------------------------------------

// Elevator
// -------------------------------------------------------------------------
bool NoPassengerOutOrIn(int lift)
{
    if (!StackEmpty(g_elevator[lift].stack_array[g_elevator[lift].current_floor]))
        return false; // sb. prepare to out
    if (g_elevator[lift].state == GOING_DOWN && g_wait_queue[DOWN][g_elevator[lift].current_floor].num && g_elevator[lift].passenger_num < g_elevator[lift].capacity)
        return false; // sb. prepare to down
    if (g_elevator[lift].state == GOING_UP && g_wait_queue[UP][g_elevator[lift].current_floor].num && g_elevator[lift].passenger_num < g_elevator[lift].capacity)
        return false; // sb. prepare to up
    if (g_elevator[lift].in_out_timer > 0)
        return false; // sb. is in or out right now
    return true;
}

bool MoveTimeUp(int lift)
{
    return g_elevator[lift].move_timer == 0;
}

int HigherUpOrDownNotArriveCall(int floor)
{
    int i;
    for (i = floor + 1; i < g_total_floor; ++i)
        if (g_call_down[i] == 1 || g_call_down[i] == -1 ||
            g_call_up[i] == 1 || g_call_up[i] == -1)
            break;
    if (i == g_total_floor)
        return -1;
    return i;
}

int LowerUpOrDownNotArriveCall(int floor)
{
    int i;
    for (i = floor - 1; i >= 0; --i)
        if (g_call_down[i] == 1 || g_call_down[i] == -1 ||
            g_call_up[i] == 1 || g_call_up[i] == -1)
            break;
    return i;
}

int HigherCallCar(int lift)
{
    int i;
    for (i = g_elevator[lift].current_floor + 1; i < g_total_floor; ++i)
        if (g_elevator[lift].call_car[i])
            break;
    if (i == g_total_floor)
        return -1;
    return i;
}

int LowerCallCar(int lift)
{
    int i;
    for (i = g_elevator[lift].current_floor - 1; i >= 0; --i)
        if (g_elevator[lift].call_car[i])
            break;
    return i;
}

bool StopNextFloor(int lift)
{
    if (g_elevator[lift].state == GOING_UP)
    {
        if (g_elevator[lift].current_floor == g_total_floor - 1)
        {
            g_call_down[g_total_floor - 1] = -2;
            g_elevator[lift].whether_change_state = 1;
            return true; 
        }

        if (g_elevator[lift].call_car[g_elevator[lift].current_floor])
        {
            if (HigherCallCar(lift) == -1 && HigherUpOrDownNotArriveCall(g_elevator[lift].current_floor) == -1 &&
                g_call_up[g_elevator[lift].current_floor] != 1 && g_call_up[g_elevator[lift].current_floor] != -1)
            {
                g_elevator[lift].whether_change_state = 1;
                g_call_down[g_elevator[lift].current_floor] = -2;
            }
            else
                g_call_up[g_elevator[lift].current_floor] = -2;
            return true;
        }

        if (g_elevator[lift].passenger_num < g_elevator[lift].capacity &&
            (g_call_up[g_elevator[lift].current_floor] == 1 || g_call_up[g_elevator[lift].current_floor] == -1))
        {
            g_call_up[g_elevator[lift].current_floor] = -2;
            return true;
        }

        if (HigherCallCar(lift) == -1 && g_call_up[g_elevator[lift].current_floor] != 1 && g_call_up[g_elevator[lift].current_floor] != -1)
        {
            int floor = HigherUpOrDownNotArriveCall(g_elevator[lift].current_floor);
            if (floor == -1)
            {
                if (g_call_down[g_elevator[lift].current_floor] != -2)
                {
                    // stop this floor and change state
                    g_elevator[lift].whether_change_state = 1;
                    g_call_down[g_elevator[lift].current_floor] = -2;
                    return true;
                }
            }
            else
            {
                if (g_call_up[floor] == 1)
                    g_call_up[floor] = -1;
                else if (g_call_down[floor] == 1)
                    g_call_down[floor] = -1;
            }
        }

        return false;
    }
    else
    {
        if (g_elevator[lift].current_floor == 0)
        {
            g_call_up[0] = -2;
            g_elevator[lift].whether_change_state = 1;
            return true;
        }

        if (g_elevator[lift].call_car[g_elevator[lift].current_floor])
        {
            if (LowerCallCar(lift) == -1 && LowerUpOrDownNotArriveCall(g_elevator[lift].current_floor) == -1 &&
                g_call_down[g_elevator[lift].current_floor] != 1 && g_call_down[g_elevator[lift].current_floor] != -1)
            {
                g_elevator[lift].whether_change_state = 1;
                g_call_up[g_elevator[lift].current_floor] = -2;
            }
            else
                g_call_down[g_elevator[lift].current_floor] = -2;
            return true;
        }

        if (g_elevator[lift].passenger_num < g_elevator[lift].capacity &&
            (g_call_down[g_elevator[lift].current_floor] == 1 || g_call_down[g_elevator[lift].current_floor] == -1))
        {
            g_call_down[g_elevator[lift].current_floor] = -2;
            return true;
        }

        if (LowerCallCar(lift) == -1 && g_call_down[g_elevator[lift].current_floor] != 1 && g_call_down[g_elevator[lift].current_floor] != -1)
        {
            int floor = LowerUpOrDownNotArriveCall(g_elevator[lift].current_floor);
            if (floor == -1)
            {
                if (g_call_up[g_elevator[lift].current_floor] != -2)
                {
                    // stop this floor and change state
                    g_elevator[lift].whether_change_state = 1;
                    g_call_up[g_elevator[lift].current_floor] = -2;
                    return true;
                }
            }
            else
            {
                if (g_call_down[floor] == 1)
                    g_call_down[floor] = -1;
                else if (g_call_up[floor] == 1)
                    g_call_up[floor] = -1;
            }
        }

        return false;
    }
}

void ChangeElevatorMove(int lift)
{
    switch (g_elevator[lift].move)
    {
    case OPENING:
        g_elevator[lift].move = OPENED;
        g_elevator[lift].move_timer = CLOSING_TEST_TIME;
        break;

    case OPENED:
        if (NoPassengerOutOrIn(lift))
        {
            g_elevator[lift].move = CLOSING;
            g_elevator[lift].move_timer = DOOR_TIME;
            Show(DOOR_CLOSING, -1, -1, -1, lift, g_elevator[lift].current_floor);
        }
        else
            g_elevator[lift].move_timer = CLOSING_TEST_TIME;
        break;

    case CLOSING:
        if (g_elevator[lift].passenger_num == g_elevator[lift].capacity)
            g_elevator[lift].move = CLOSED;
        else if ((g_elevator[lift].state == GOING_UP && g_wait_queue[UP][g_elevator[lift].current_floor].num) ||
                 (g_elevator[lift].state == GOING_DOWN && g_wait_queue[DOWN][g_elevator[lift].current_floor].num))
        {
            g_elevator[lift].move = OPENING;
            g_elevator[lift].move_timer = DOOR_TIME;
            Show(DOOR_REOPENING, -1, -1, -1, lift, g_elevator[lift].current_floor);
        }
        else
            g_elevator[lift].move = CLOSED;
        break;

    case CLOSED:
    {
        if (g_elevator[lift].state == GOING_UP)
        {
            // decided to go up when arrived just now
            // deal with button
            if (g_wait_queue[UP][g_elevator[lift].current_floor].num)
                g_call_up[g_elevator[lift].current_floor] = 1;
            else
                g_call_up[g_elevator[lift].current_floor] = 0;

            int i;
            for (i = g_elevator[lift].current_floor + 1; i < g_total_floor; ++i)
            {
                if (g_elevator[lift].call_car[i])
                {
                    g_elevator[lift].move = ACCELERATING;
                    g_elevator[lift].move_timer = ACCELERATE_TIME;
                    Show(ELEVATOR_ACCELERATING, -1, -1, -1, lift, g_elevator[lift].current_floor);
                    break;
                }
            }
            if (i == g_total_floor)
            {
                g_elevator[lift].move = WAITING;
                g_elevator[lift].state = IDLE;
                g_elevator[lift].move_timer = MAX_WAITING_TIME;
                Show(BE_IDLE, -1, -1, -1, lift, g_elevator[lift].current_floor);
            }
        }
        else if (g_elevator[lift].state == GOING_DOWN)
        {
            if (g_wait_queue[DOWN][g_elevator[lift].current_floor].num)
                g_call_down[g_elevator[lift].current_floor] = 1;
            else
                g_call_down[g_elevator[lift].current_floor] = 0;

            int i;
            for (i = g_elevator[lift].current_floor - 1; i >= 0; --i)
            {
                if (g_elevator[lift].call_car[i])
                {
                    g_elevator[lift].move = ACCELERATING;
                    g_elevator[lift].move_timer = ACCELERATE_TIME;
                    Show(ELEVATOR_ACCELERATING, -1, -1, -1, lift, g_elevator[lift].current_floor);
                    break;
                }
            }
            if (i == -1)
            {
                g_elevator[lift].move = WAITING;
                g_elevator[lift].state = IDLE;
                g_elevator[lift].move_timer = MAX_WAITING_TIME;
                Show(BE_IDLE, -1, -1, -1, lift, g_elevator[lift].current_floor);
            }
        }
        else
            exit(UNKNOWN_ERROR); 
        break;
    }

    case ACCELERATING:
        g_elevator[lift].move = MOVING;
        if (g_elevator[lift].state == GOING_UP)
            g_elevator[lift].move_timer = UP_TIME;
        else
            g_elevator[lift].move_timer = DOWN_TIME;
        Show(IS_MOVING, -1, -1, -1, lift, g_elevator[lift].current_floor);
        break;

    case MOVING:
        if (g_elevator[lift].state == GOING_UP)
        {
            ++g_elevator[lift].current_floor;
            if (StopNextFloor(lift))
            {
                g_elevator[lift].move = SLOWING_DOWN;
                g_elevator[lift].move_timer = UP_SLOW_TIME;
                Show(IS_SLOWING_DOWN, -1, -1, -1, lift, g_elevator[lift].current_floor);
            }
            else
            {
                g_elevator[lift].move_timer = UP_TIME;
                Show(IS_MOVING, -1, -1, -1, lift, g_elevator[lift].current_floor);
            }
        }
        else if (g_elevator[lift].state == GOING_DOWN)
        {
            --g_elevator[lift].current_floor;
            if (StopNextFloor(lift))
            {
                g_elevator[lift].move = SLOWING_DOWN;
                g_elevator[lift].move_timer = DOWN_SLOW_TIME;
                Show(IS_SLOWING_DOWN, -1, -1, -1, lift, g_elevator[lift].current_floor);
            }
            else
            {
                g_elevator[lift].move_timer = DOWN_TIME;
                Show(IS_MOVING, -1, -1, -1, lift, g_elevator[lift].current_floor);
            }
        }
        else
            exit(UNKNOWN_ERROR);
        break;

    case SLOWING_DOWN:
    {
        // g_call_up or g_call_down has been changed to -2 in StopNextFloor function
        g_elevator[lift].call_car[g_elevator[lift].current_floor] = 0;
        g_elevator[lift].move = OPENING;
        g_elevator[lift].move_timer = DOOR_TIME;
        Show(ARRIVE_AND_OPENING, -1, -1, -1, lift, g_elevator[lift].current_floor);

        // judge whether change state
        if (g_elevator[lift].state == GOING_UP)
        {
            if (g_elevator[lift].whether_change_state)
                g_elevator[lift].state = GOING_DOWN;
            g_elevator[lift].whether_change_state = 0;
        }
        else if (g_elevator[lift].state == GOING_DOWN)
        {
            if (g_elevator[lift].whether_change_state)
                g_elevator[lift].state = GOING_UP;
            g_elevator[lift].whether_change_state = 0;
        }
        else
            exit(UNKNOWN_ERROR);
        break;
    }

    case WAITING:
        if (g_elevator[lift].current_floor == g_elevator[lift].idle_floor)
            g_elevator[lift].move_timer = MAX_WAITING_TIME;
        else
        {
            if (g_elevator[lift].current_floor > g_elevator[lift].idle_floor)
                g_elevator[lift].state = GOING_DOWN;
            else
                g_elevator[lift].state = GOING_UP;
            g_elevator[lift].call_car[g_elevator[lift].idle_floor] = 1;
            g_elevator[lift].move_timer = ACCELERATE_TIME;
            g_elevator[lift].move = ACCELERATING;
            Show(IDLE_RETURN, -1, -1, -1, lift, g_elevator[lift].current_floor);
        }
        break;
    }
}

int NearestCall(int floor)
{
    int i = 1;
    while (floor - i >= 0 || floor + i < g_total_floor)
    {
        if ((floor - i >= 0 && (g_call_down[floor - i] == 1 || g_call_up[floor - i] == 1)) || 
            (floor + i < g_total_floor && (g_call_down[floor + i] == 1 || g_call_up[floor + i] == 1)))
            break;
        ++i;
    }
    if (!(floor - i >= 0 || floor + i < g_total_floor))
        return -1;
    if (floor - i >= 0 && (g_call_down[floor - i] == 1 || g_call_up[floor - i] == 1))
        return floor - i; 
    return floor + i;
}

void WakeUp()
{
    for (int i = 0; i < g_elevator_num; ++i)
    {
        if (g_elevator[i].move == WAITING)
        {
            // try to wake up the waiting lift
            if (g_call_up[g_elevator[i].current_floor] == 1 || g_call_up[g_elevator[i].current_floor] == -1)
            {
                // change and show
                g_call_up[g_elevator[i].current_floor] = -2;
                g_elevator[i].state = GOING_UP;
                g_elevator[i].move = OPENING;
                g_elevator[i].move_timer = DOOR_TIME;
                Show(IDLE_OPENING, -1, -1, -1, i, g_elevator[i].current_floor);
            }
            else if (g_call_down[g_elevator[i].current_floor] == 1 || g_call_down[g_elevator[i].current_floor] == -1)
            {
                g_call_down[g_elevator[i].current_floor] = -2;
                g_elevator[i].state = GOING_DOWN;
                g_elevator[i].move = OPENING;
                g_elevator[i].move_timer = DOOR_TIME;
                Show(IDLE_OPENING, -1, -1, -1, i, g_elevator[i].current_floor);
            }
            else
            {
                // whether go to other floor
                int nearest = NearestCall(g_elevator[i].current_floor);
                if (nearest != -1)
                {
                    if (nearest > g_elevator[i].current_floor)
                    {
                        if (g_call_up[nearest] == 1)
                            g_call_up[nearest] = -1;
                        else
                            g_call_down[nearest] = -1;
                        g_elevator[i].state = GOING_UP;
                        g_elevator[i].move = ACCELERATING;
                        g_elevator[i].move_timer = ACCELERATE_TIME;
                        Show(ELEVATOR_ACCELERATING, -1, -1, -1, i, g_elevator[i].current_floor);
                    }
                    else
                    {
                        // should go down
                        if (g_call_down[nearest] == 1)
                            g_call_down[nearest] = -1;
                        else
                            g_call_up[nearest] = -1;
                        g_elevator[i].state = GOING_DOWN;
                        g_elevator[i].move = ACCELERATING;
                        g_elevator[i].move_timer = ACCELERATE_TIME;
                        Show(ELEVATOR_ACCELERATING, -1, -1, -1, i, g_elevator[i].current_floor);
                    }
                }
            }
        }
    }
}
// -------------------------------------------------------------------------

// show
void Show(int type, int id, int in_floor, int out_floor, int lift, int lift_floor)
{
    switch (type)
    {
    case NEW_PASSENGER:
        cout << "Time: " << g_current_time << endl;
        cout << id << " comes in Floor " << in_floor << " ";
        cout << "and wanna go to Floor " << out_floor << endl;
        break;

    case GIVE_UP:
        cout << "Time: " << g_current_time << endl;
        cout << id << " gives up" << endl;
        break;

    case PASSENGER_OUT:
        cout << "Time: " << g_current_time << endl;
        cout << id << " get out of Elevator " << lift << " ";
        cout << "in Floor " << lift_floor << " and leave" << endl;
        break;

    case PASSENGER_IN:
        cout << "Time: " << g_current_time << endl;
        cout << id << " get in Elevator " << lift << " ";
        cout << "in Floor " << lift_floor << endl;
        break;

    case DOOR_CLOSING:
        cout << "Time: " << g_current_time << endl;
        cout << "Elevator " << lift << " is closing door ";
        cout << "and has " << g_elevator[lift].passenger_num << " passenger(s)" << endl;
        break;

    case DOOR_REOPENING:
        cout << "Time: " << g_current_time << endl;
        cout << "Elevator " << lift << " is reopening door" << endl;
        break;

    case ELEVATOR_ACCELERATING:
        cout << "Time: " << g_current_time << endl;
        cout << "Elevator " << lift << " accelerating ";
        if (g_elevator[lift].state == GOING_DOWN)
            cout << "down from Floor " << lift_floor << endl;
        else
            cout << "up from Floor " << lift_floor << endl;
        break;

    case BE_IDLE:
        cout << "Time: " << g_current_time << endl;
        cout << "Elevator " << lift << " is idle in Floor " << lift_floor << endl;
        break;

    case IS_MOVING:
        cout << "Time: " << g_current_time << endl;
        cout << "Elevator " << lift << " is moving from Floor " << lift_floor;
        cout << " to Floor ";
        if (g_elevator[lift].state == GOING_DOWN)
            cout << lift_floor - 1 << endl;
        else
            cout << lift_floor + 1 << endl;
        break;

    case IS_SLOWING_DOWN:
        cout << "Time: " << g_current_time << endl;
        cout << "Elevator " << lift << " is slowing down in Floor " << lift_floor << endl;
        break;

    case ARRIVE_AND_OPENING:
        cout << "Time: " << g_current_time << endl;
        cout << "Elevator " << lift << " arrives in Floor " << lift_floor;
        cout << " and is opening door" << endl;
        break;

    case IDLE_RETURN:
        cout << "Time: " << g_current_time << endl;
        cout << "Elevator " << lift << " is idle for a long time and goes back to Floor ";
        cout << g_elevator[lift].idle_floor << " from Floor " << lift_floor << endl;
        break;

    case IDLE_OPENING:
        cout << "Time: " << g_current_time << endl;
        cout << "Elevator " << lift << " is opening door in Floor " << lift_floor << endl;
        break;
    }
    cout << endl;
}

// UserInput
void UserInput()
{
    while (1)
    {
        cout << "Input max run time(>= 500):" << endl;
        cin >> g_max_time;
        if (g_max_time >= 500)
            break;
    }
    while (1)
    {
        cout << "Input the number of elevator(s) (>= 1):" << endl;
        cin >> g_elevator_num;
        if (g_elevator_num >= 1)
            break;
    }
    while (1)
    {
        cout << "Input elevator capacity(>= 1):" << endl;
        cin >> g_capacity;
        if (g_capacity >= 1)
            break;
    }
    while (1)
    {
        cout << "Input the number of floors(>= 3):" << endl;
        cin >> g_total_floor;
        if (g_total_floor >= 3)
            break;
    }
}

// Initialize
void Initialize()
{
    // Elevator
    g_elevator = (ElevatorPtr)malloc(g_elevator_num * sizeof(Elevator));
    if (!g_elevator)
    {
        cout << "overflow" << endl;
        exit(OVERFLOW);
    }
    for (int i = 0; i < g_elevator_num; ++i)
    {
        g_elevator[i].passenger_num = 0;
        g_elevator[i].capacity = g_capacity;
        g_elevator[i].stack_array = (PassengerStackPtr)malloc(g_total_floor * sizeof(PassengerStack));
        if (!g_elevator[i].stack_array)
        {
            cout << "overflow" << endl;
            exit(OVERFLOW);
        }
        for (int j = 0; j < g_total_floor; ++j)
            InitStack(g_elevator[i].stack_array[j]);
        g_elevator[i].passenger_id = (int *)malloc(g_capacity * sizeof(int));
        if (!g_elevator[i].passenger_id)
        {
            cout << "overflow" << endl;
            exit(OVERFLOW);
        }
        g_elevator[i].call_car = (int *)malloc(g_total_floor * sizeof(int));
        if (!g_elevator[i].call_car)
        {
            cout << "overflow" << endl;
            exit(OVERFLOW);
        }
        for (int j = 0; j < g_total_floor; ++j)
            g_elevator[i].call_car[j] = 0;
        if (g_total_floor <= 10)
            g_elevator[i].current_floor = g_elevator[i].idle_floor = 1;
        else
            g_elevator[i].current_floor = g_elevator[i].idle_floor = g_total_floor / 2;
        g_elevator[i].total_floor = g_total_floor;
        g_elevator[i].move = WAITING;
        g_elevator[i].state = IDLE;
        g_elevator[i].move_timer = MAX_WAITING_TIME;
        g_elevator[i].in_out_timer = 0; // must be 0!!!!! To get the first passenger in at once!!! or it may generate bugs!!!
        g_elevator[i].whether_change_state = 0;
    }

    // call_up, call_down
    g_call_down = (int *)malloc(g_total_floor * sizeof(int));
    g_call_up = (int *)malloc(g_total_floor * sizeof(int));
    if (!g_call_up || !g_call_down)
    {
        cout << "overflow" << endl;
        exit(OVERFLOW);
    }
    for (int i = 0; i < g_total_floor; ++i)
        g_call_down[i] = g_call_up[i] = 0;

    // wait queue
    g_wait_queue = (WaitQueuePtr *)malloc(2 * sizeof(WaitQueuePtr));
    if (!g_wait_queue)
    {
        cout << "overflow" << endl;
        exit(OVERFLOW);
    }
    for (int i = 0; i < 2; ++i)
    {
        g_wait_queue[i] = (WaitQueuePtr)malloc(g_total_floor * sizeof(WaitQueue));
        if (!g_wait_queue[i])
        {
            cout << "overflow" << endl;
            exit(OVERFLOW);
        }
    }
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < g_total_floor; ++j)
            InitQueue(g_wait_queue[i][j]);
}

// PrintReady
void PrintReady()
{
    cout << "----------------------------------------------------------" << endl;
    cout << "----------------------------------------------------------" << endl;
    cout << "--------------------------Ready---------------------------" << endl;
    cout << "----------------------------------------------------------" << endl;
    cout << "----------------------------------------------------------" << endl;
}

void PrintEnd()
{
    cout << "----------------------------------------------------------" << endl;
    cout << "----------------------------------------------------------" << endl;
    cout << "---------------------------End----------------------------" << endl;
    cout << "----------------------------------------------------------" << endl;
    cout << "----------------------------------------------------------" << endl;
    cout << "    new: " << g_new_num << endl;
    cout << "     in: " << g_get_in_num << endl;
    cout << "    out: " << g_get_out_num << endl;
    cout << "give up: " << g_give_up_num << endl;
}

void AllClear()
{
    // call_up, call_down
    free(g_call_down);
    free(g_call_up);

    // wait queue
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < g_total_floor; ++j)
            DestroyQueue(g_wait_queue[i][j]);
    for (int i = 0; i < 2; ++i)
        free(g_wait_queue[i]); // I think it can' be "free(g_wait_queue[i][j])" because what I malloc is g_wait_queue[i]
    free(g_wait_queue);

    // Elevator
    for (int i = 0; i < g_elevator_num; ++i)
    {
        free(g_elevator[i].call_car);
        free(g_elevator[i].passenger_id);
        for (int j = 0; j < g_total_floor; ++j)
            DestroyStack(g_elevator[i].stack_array[j]);
        free(g_elevator[i].stack_array);
    }
    free(g_elevator);
}

void Simulate()
{
    UserInput();
    Initialize();
    srand((unsigned)time(NULL)); // just need to srand one time
    PrintReady();
    while (g_current_time < g_max_time)
    {
        if (g_next_passenger_inter_time == 0)
            NewPassenger();
        else
            --g_next_passenger_inter_time;
        CheckGiveUp();
        WakeUp();
        for (int i = 0; i < g_elevator_num; ++i)
        {
            if (g_elevator[i].move == OPENED)
            {
                if (g_elevator[i].in_out_timer == 0)
                {
                    bool out, in;
                    // first out, then in
                    if (!(out = PassengerOut(i)))
                        in = PassengerIn(i);
                    if (out || in)
                        g_elevator[i].in_out_timer = IN_OUT_TIME;
                }
                else
                    --g_elevator[i].in_out_timer;
            }
            if (MoveTimeUp(i))
                ChangeElevatorMove(i);
            else
                --g_elevator[i].move_timer;
        }
        ++g_current_time;
    }
    PrintEnd();
    AllClear();
}

int main()
{
    Simulate();
    system("pause");
    return 0;
}
文章标签：
调度
关键词：
数据结构模拟
游客ccnmnkqy42xjq
目录
相关文章
q4qlc6vqsegx4
|
存储 Java 索引
不可上位！数据结构队列，老实排队，Java实现数组模拟队列及可复用环形队列
不可上位！数据结构队列，老实排队，Java实现数组模拟队列及可复用环形队列
q4qlc6vqsegx4
117 0
不可上位！数据结构队列，老实排队，Java实现数组模拟队列及可复用环形队列
刘健祥
|
存储 Java Linux
C++ 第八节&数据结构 第七节 ——二叉搜索树 AVL树 红黑树（底层原理图+模拟实现）
每一个关键码key，都有与之对应的值Value，即&lt;Key, Value&gt;的键值对。该种方式在现实生活中非常常见：比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文&lt;word, chinese&gt;就构成一种键值对；
刘健祥
196 0
C++ 第八节&数据结构 第七节 ——二叉搜索树 AVL树 红黑树（底层原理图+模拟实现）
拼命阿紫
|
存储 编译器
【数据结构】模拟实现双向链表（2）
【数据结构】模拟实现双向链表
拼命阿紫
85 0
【数据结构】模拟实现双向链表（2）
拼命阿紫
|
存储
【数据结构】模拟实现双向链表（1）
【数据结构】模拟实现双向链表
拼命阿紫
84 0
【数据结构】模拟实现双向链表（1）
拼命阿紫
|
存储 编译器
【数据结构】认识链表和模拟实现单链表（2）
【数据结构】认识链表和模拟实现单链表
拼命阿紫
113 0
拼命阿紫
|
存储
【数据结构】认识链表和模拟实现单链表（1）
【数据结构】认识链表和模拟实现单链表
拼命阿紫
87 0
【数据结构】认识链表和模拟实现单链表（1）
兴趣使然黄小黄
|
存储 算法 Java
Java数据结构：使用数组模拟队列（队列与环形队列）
文章目录 1 队列 1.1 何为队列及实现思路 1.2 数组模拟队列ArrayQueue的实现 1.3 测试队列ArrayQueueDemo测试类的实现 2 环形队列 2.1 环形队列简介及实现思路 2.2 数组模拟环形队列CircleArrayQueue的实现 2.3 测试队列CircleArrayQueueDemo测试类的实现 写在最后
兴趣使然黄小黄
136 0
Java数据结构：使用数组模拟队列（队列与环形队列）
ybbf7fwncy2w2
|
算法 Go 开发者
数据结构和算法-数组模拟环形队列实现（二）|学习笔记
快速学习数据结构和算法-数组模拟环形队列实现（二）
ybbf7fwncy2w2
59 0
ybbf7fwncy2w2
|
算法 开发者 索引
数据结构和算法-数组模拟环形队列|学习笔记
快速学习数据结构和算法-数组模拟环形队列
ybbf7fwncy2w2
91 0
数据结构和算法-数组模拟环形队列|学习笔记
ybbf7fwncy2w2
|
算法 Go 开发者
数据结构和算法-数组模拟队列实现|学习笔记
快速学习数据结构和算法-数组模拟队列实现
ybbf7fwncy2w2
76 0
数据结构和算法-数组模拟队列实现|学习笔记