前言

最近，帮一个同学编写了一个可视化的停车场管理系统程序，用于辅助他们的管理学的pre。所以这个小项目也非常的简单，刚好运用了之前算法设计与分析与WEB技术的结合。既然是可视化程序，第一反应可以使用C++，但是恰好上学期学习了JavaScript，于是就用JavaScript编写这个程序。

项目在线demo地址：https://park.hoyue.eu.org/

信息描述

对于一个有限的停车场空间内，有一个固定的入口和出口。例子中设置为4列车位，除了最左侧的一列有8个车位外，每一列有7个车位。入口和出口在同一个位置(1,0)，每一列从左往右依次以A0/B1/C2/D3开头命名车位。根据纵坐标，也依次从0开始向上递增。概念图如下：

我们抽象成表格，就是如下的情况：

y \ x A0 B1 C2 D3
8
7
6
5
4
3
2
1
0 Entrance

这是按照坐标轴的表格，其中如果这个位置是可用的，那么它的背景颜色就是绿色(green)的。如果这个位置是无效的，那么它的背景颜色就是海蓝宝石色(aquamarine)。如果它的背景颜色是红色(red)的，那么表示该位置已经被占用，存在车辆了。

现在需要实现如下功能：

  1. 车辆停入：输入入场时间和车牌号，将车辆停入距离入口最近的且未被占用的车位，并显示停入信息。
  2. 车辆驶离：输入出场时间和车牌号，释放被占用的车位，并输出驶离信息。
  3. 费用计算：输出停车产生的费用，该例子中为比较简单的(t-1)×1。
  4. 表格显示：在表格上可视化展示停车位情况，在被占用的停车位中需要写入车牌号。

问题分析

距离最短问题

对于这个问题，还是比较简单解决的。首先是解决距离问题。

因为要求中，每个格子距离起点的距离是固定的，我们不必每次停入的时候都重新计算找最小值，只需要一直维护一个容易保持有最小值的数据结构就可以了。于是很容易想到使用一个最小堆去存储这些距离。

对于在JavaScript中实现堆，只需要稍微根据《Introduction to Algorithm》中的伪代码进行修改即可。

信息存储

这个问题中有很多信息，该如何存储呢？我想到的是使用两个类。

一个类是Heap，用于维护堆数组的，它有属性x和y可以用于定位单元格，有一个属性distance用于记录距离，这是堆数组的排列依据。

另一个类Position是用来维护车位的，即单元格，有属性status用于记录当前单元格的状态，分为"occupied"（已占用）、"available"（可用）和"null"（无效），一个属性name用于记录车辆信息，若车位非占用状态则为空，一个属性t用来记录车辆的入场时间。

初始情况下，定义一个一维数组heap作为Heap类的变量，定义一个二维数组pos作为Position类的变量。根据表格现有信息，初始化这两个数组即可。

入场问题

当车入场时，要做的事很简单。首先就是取到最短可用的车位的坐标，通过获取堆首的信息中x,y属性就可以知道它的坐标。然后在单元格数组pos中，标记指定位置，填入特定信息即可。

出场问题

当车出场时，若输入的车牌在停车场中，那么就恢复指定单元格位置，并且输出指定信息。我们可以在每次删去堆的时候，将其放到数组的末尾，这样出场的时候只需要匹配heapSize + 1到SIZE即可。

代码

代码按照部分展示在本文中，全文代码请看：https://github.com/Aki-Hoyue/parking_system

初始化

堆实现

这里是参考《Introduction to Algorithm》的堆实现部分的JavaScript代码。

伪代码部分以及分析请见：

【算法设计与分析】堆排序分析

首先是基本堆函数：

function heapParent(i) {
    return Math.floor(i / 2);
}

function left(i) {
    return i * 2;
}

function right(i) {
    return i * 2 + 1;
}

维护最小堆： 

function minHeapify(A, i) {
    var l = left(i);
    var r = right(i);
    var smallest = i;

    if (l <= heapSize && A[l].distance < A[i].distance)
        smallest = l;
    
    if (r <= heapSize && A[r].distance < A[smallest].distance)
        smallest = r;

    if (smallest !== i) {
        var temp = A[i];
        A[i] = A[smallest];
        A[smallest] = temp;
        minHeapify(A, smallest);
    }
}

建堆：

function buildMinHeap(A, n) {
    for (var i = Math.floor(n / 2); i >= 1; i--) {
        minHeapify(A, i);
    }
}

删除堆首并放到堆后：

function extractMinFromHeap(A) {
    if (heapSize < 1)
        throw new Error("heap underflow");

    const minElement = A[1];
    A[1] = A[heapSize];
    A[heapSize] = minElement;
    heapSize --;
    minHeapify(A, 1);
    return minElement;
}

插入进堆：

function insertHeap(A,index){
    if (heapSize == SIZE)
        throw new Error("heap overflow");
    const element = A[heapSize + 1];
    A[++heapSize] = A[index];
    A[index] = element;
    for (var i = Math.floor(heapSize / 2); i >= 1; i--) {
        minHeapify(A, i);
    }
}

这是一个非常经典的算法导论的JavaScript实现，接下来就是把堆当做数据结构去使用堆。

堆初始化

var heapSize = 0;
class Heap{
    constructor(x,y)
    {
        this.x = x;
        this.y = y;
        this.distance = Math.sqrt((x-1)*(x-1) + y * y);
    }
}

var heap = new Array(4 * 9);
heap[0] = -1;
var index = 1;
heap[index++] = new Heap(0, 1);
for (var x = 0; x < 4; x++) {
    for (var y = 2; y < 9; y++) {
        heap[index++] = new Heap(x, y);
    }
}
heapSize = index - 1;
const SIZE = heapSize;
buildMinHeap(heap,heapSize);

设置Heap类的三个属性x,y和distance，distance会根据x,y的值自动计算，初始化0位置为一个非常小的值，这里因为距离是正数就设置为-1。index作为堆数组的索引，创建每个位置上的Heap类元素。

设置一个常量SIZE，作为最大的情况，之后检测的时候用到。

单元格初始化

单元格就简单很多，根据之前的表格初始化即可，如下：

y \ x A0 B1 C2 D3
8
7
6
5
4
3
2
1
0 Entrance 
class Position {
    constructor(status, name, t) {
    this.status = status;
    this.name = name;
    this.t = t;
    }
}

var pos = new Array(4);
for (var x = 0; x < 4; x++) {
    pos[x] = new Array(9);
    for (var y = 0; y < 9; y++) {
    if (!y || (y == 1 && x)) {
        pos[x][y] = new Position("null", "", "");
        continue;
    } 
    pos[x][y] = new Position("available", "", "");
    }
}

当页面被加载的时候，还需要初始化单元格的背景颜色：

function loding(){
    var table = document.getElementById("ParkingArea");
    for(var i = 0; i < 9; i++)  //y
        for(var j = 0; j < 4; j++)  //x
        {
            var cell = table.rows[9-i].cells[j+1];
            if(cell.innerHTML == "Entrance") continue;
            if(pos[j][i].status == "null")
                cell.style.backgroundColor = "aquamarine";
            else cell.style.backgroundColor = "green";
        }
}

入场

我们需要考虑一些意外条件，先行判断：

  • 堆（停车场）是否已满。
  • 输入的入场时间是否符合标准。
  • 车牌是否为空或者已经停入。

我们需要先特判这些问题：

  • 对于堆是否已满，只需要检查heapSize的大小(heapSize < 1则已满)即可。
  • 对于时间的格式，我们提示用户应该输入格式为“yyyy/mm/dd hh:mm:ss”，并且使用正则表达式来检查用户的输入。
  • 对于车牌，首先先判断是否为空，再在heap数组中heapSize + 1到SIZE之间（这之间的是已经入场的位置）查找是否有相同的车牌。

于是代码为：

function input()
{
    if (heapSize < 1)
    {
        window.alert("The parking area is full!");
        throw new Error("heap overflow.");
    }
    var entranceTime = document.getElementById("entrance_time");
    var entranceName = document.getElementById("entrance_name");
    var acTest = /^([0-9]{4})\/([0-1][0-9])\/([0-3][0-9]) ([0-2][0-9]):([0-5][0-9]):([0-5][0-9])$/;
    if(!acTest.test(entranceTime.value))
    {
        window.alert("The time is not formatted correctly!");
        throw new Error("Time format error.");
    }
    if(!entranceName.value)
    {
        window.alert("The name of license could not be empty!");
        throw new Error("name error.");
    }

    for(var i = heapSize + 1; i <= SIZE; i++)
    {
        var temp = heap[i];
        if(pos[temp.x][temp.y].name == entranceName.value)
        {
            window.alert("The car has already been parked!");
            throw new Error("repark error.");
        }
    }

    var parkArea = extractMinFromHeap(heap);
    pos[parkArea.x][parkArea.y].status = 'occupied';
    pos[parkArea.x][parkArea.y].name = entranceName.value;
    pos[parkArea.x][parkArea.y].t = entranceTime.value;

    var table = document.getElementById("ParkingArea");
    var cell = table.rows[9-parkArea.y].cells[parkArea.x+1];
    cell.style.backgroundColor = "red";
    cell.innerHTML = entranceName.value;
    cell.style.color = "green";

    var info = document.getElementById("info_box");
    info.innerHTML = "<b>" + entranceName.value + "</b> parks at <b>" + 
        String.fromCharCode(parkArea.x + 65) + parkArea.x + parkArea.y + "</b>";

}

这个代码它会检查停车场是否已满，如果已满，就会显示一个警告讯息并抛出一个错误。接著，它会检查输入的时间和车牌是否符合格式要求，如果不符合，就会显示一个警告讯息并抛出一个错误。如果输入的车牌已经被停在停车场上，就会显示一个警告讯息并抛出一个错误。如果以上都没有问题，就会从停车场中取出一个空格并将车辆停在上面，并在停车场的表格中显示车辆的车牌和停车时间。最后，它会显示一个讯息，显示车辆的车牌和停车的位置。

出场

对于出场，我们同样考虑如下特殊情况：

  • 堆（停车场）是否已满。
  • 输入的出场时间是否符合标准，是否满足出场时间必须晚于入场时间。
  • 车牌是否为空已经停入。

解决方法还是如上入场内容。特别的是，因为要计算时间差值，要求出场时间必须晚于入场时间。

代码如下：

function output()
{
    var time = document.getElementById("out_time");
    var acTest = /^([0-9]{4})\/([0-1][0-9])\/([0-3][0-9]) ([0-2][0-9]):([0-5][0-9]):([0-5][0-9])$/;
    if(!acTest.test(time.value))
    {
        window.alert("The time is not formatted correctly!");
        throw new Error("Time format error.");
    }
    var outTime = new Date(time.value);
    var outName = document.getElementById("out_name");
    if(!outName.value)
    {
        window.alert("The name of license could not be empty!");
        throw new Error("name error.");
    }

    var flag = 0;
    for(var i = heapSize + 1; i <= SIZE; i++)
    {
        var temp = heap[i];
        if(pos[temp.x][temp.y].status == 'occupied' && pos[temp.x][temp.y].name == outName.value)
        {
            flag = 1;
            var inTime = new Date(pos[temp.x][temp.y].t);
            var diff = (outTime.getTime() - inTime.getTime()) / (1000 * 60 * 60);
            if(diff < 0)
            {
                window.alert("The exit time must not be less than the entry time!");
                throw new Error("Time error.");
            }
            var fee = wealth(Math.ceil(diff));

            var table = document.getElementById("ParkingArea");
            var cell = table.rows[9-temp.y].cells[temp.x+1];
            cell.style.backgroundColor = "green";
            cell.innerHTML = "";
            var info = document.getElementById("info_box");
            info.innerHTML = "<b>" + outName.value + "</b> was parked for <b>" + Math.floor(diff) + 
                "hours and " + Math.round((diff - Math.floor(diff)) * 60) + "minutes</b> from " + 
                 pos[temp.x][temp.y].t + " to " + time.value + "<br>Fee: <b>" + fee + "</b> yuan";

            pos[temp.x][temp.y].name = "";
            pos[temp.x][temp.y].t = "";
            pos[temp.x][temp.y].status = "available";
            insertHeap(heap,i);
        }
    }
    if(!flag)
    {
        window.alert("License mismatch!");
                throw new Error("No parking.");
    }
}

它首先获取一个时间值和一个车辆牌照号码，然后检查这些值是否符合格式要求。接下来，它将出场时间转换为Date对象，并检查车辆牌照号码是否存在于堆中。如果存在，则计算出场时间与入场时间之间的差异，并根据差异计算费用。然后，它将车辆牌照号码从堆中删除，并将车辆状态设置为“available”，并将车辆所在的位置设置为空闲。最后，它将信息显示在页面上，并将页面背景颜色设置为绿色。如果车辆牌照号码不存在于堆中，则显示警告信息。如果时间格式不正确或车辆牌照号码为空，则抛出错误。

费用结算

费用计算就比较简单了，计算公式就是1小时免费，超过一小时收费(t-1)元。代码如下：

function wealth(t) {
    return (t > 0)? (t - 1) : 0;
}

HTML

最后在HTML页面中，我设计了左右结构的视图，如下图所示：

代码为：

<!DOCTYPE html>
<html>
<head>
  <title>Parking System</title>
  <link rel="stylesheet" href="style.css">
  <script src="parking.js" async></script>
  <meta http-equiv="Content-Script-Type" content="text/javascript" />
</head>

<body onload="loding()">
  <table>
      <tr>
      <td width="50%">
      <table id="ParkingArea">
          <caption>Parking Area</caption>
          <tr>
              <th></th>
              <th>A / 0</th>
              <th>B / 1</th>
              <th>C / 2</th>
              <th>D / 3</th>
              </tr>
          <tr>
              <th>8</th>
              <td></td>
              <td></td>
              <td></td>
              <td></td>
          </tr>
          <tr>
              <th>7</th>
              <td></td>
              <td></td>
              <td></td>
              <td></td>
          </tr>
          <tr>
              <th>6</th>
              <td></td>
              <td></td>
              <td></td>
              <td></td>
          </tr>
          <tr>
              <th>5</th>
              <td></td>
              <td></td>
              <td></td>
              <td></td>
          </tr>
          <tr>
              <th>4</th>
              <td></td>
              <td></td>
              <td></td>
              <td></td>
          </tr>
          <tr>
              <th>3</th>
              <td></td>
              <td></td>
              <td></td>
              <td></td>
          </tr>
          <tr>
              <th>2</th>
              <td></td>
              <td></td>
              <td></td>
              <td></td>
          </tr>
          <tr>
              <th>1</th>
              <td></td>
              <td></td>
              <td></td>
              <td></td>
          </tr>
          <tr>
              <th>0</th>
              <td></td>
              <td id="entrance_point">Entrance</td>
              <td></td>
              <td></td>
          </tr>
      </table>
      </td>
      <td width="50%">
      <h2>Dashboard</h2>
          <form id="parking_form">
          <fieldset>
              <legend>Enter</legend>
              <label for="entrance_time">Entrance Time:</label>
              <input type="text" id="entrance_time" name="entrance_time" maxlength="80" placeholder="yyyy/mm/dd hh:mm:ss" size="30" required><br>
              <label for="entrance_name" >License:</label>
              <input type="text" id="entrance_name" name="entrance_name" maxlength="30" size="30" required><br>
              <input type="button" value="Park" onclick="input()">
          </fieldset>
          <fieldset>
              <legend>Exit</legend>
              <label for="out_time">Exit Time:</label>
              <input type="text" id="out_time" name="out_time" maxlength="80" placeholder="yyyy/mm/dd hh:mm:ss" size="30" required><br>
              <label for="out_name">License:</label>
              <input type="text" id="out_name" name="out_name" maxlength="30" size="30" required><br>
              <input type="button" value="Check Out" onclick="output()">
          </fieldset>
          <fieldset>
              <legend>Output</legend>
              <label id="info_box">Information here...</label><br><br>
              <label>Notice: The format of the time must be "<em>yyyy/mm/dd hh:mm:ss</em>"</label><br>
              <label>Comment: a cell in <span style="color: aquamarine;">aquamarine</span> is <em>unavailable</em>, and that in <span style="color: green;">green</span> is <em>available</em>, in <span style="color: red;">red</span> is <em>occupied</em>.</label><br>
              <input type="reset" value="Clear">
          </fieldset>
          </form>
      </td>
      </tr>
  </table>
</body>
</html>

CSS

这个CSS设计得就比较简单了，如下：

#ParkingArea{
    width: 100%;
    border-collapse: collapse;
    float: left;
}

table caption{
    font-size: 2em;
    font-weight: bold;
    margin: 1em 0;
}

#ParkingArea th,#ParkingArea td{
    border: 1px solid black;
    text-align: center;
    padding: 14px 0;
}

#ParkingArea tbody tr{
    background-color: #eee;
}

#ParkingArea th{
    background-color:cadetblue;
    color:whitesmoke;
}

#entrance_point{
    background-color: goldenrod;
    color: purple;
}

h2{
    font-size: 2em;
    font-weight: bold;
    text-align: center;
} 

form{
    font-size: 14pt;
}

后记

项目在线demo地址：https://park.hoyue.eu.org/

好了，这个小项目就简单地完成了，这个项目联系了算法与WEB技术，是个不错的小实践。

这里的一切都有始有终，却能容纳所有的不期而遇和久别重逢。
最后更新于 2023-06-26