数据结构-海关检查站模拟-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构-海关检查站模拟。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言： 基于python数据结构开发一个负责检查过境车辆的海关检查站模拟系统。

一、题目要求

二、需求分析

三、数据结构和类设计

四、算法设计

五、代码实现

六、演示模拟

一、题目要求

该系统需要模拟海关检查站的检查过程，并输出一系列事件（在一个时间段中有多少车来访），以及车辆的平均排队时间和平均运输时间。

需要考虑以下基本注意事项：

海关的职责是检查过往车辆，这里只模拟一个方向的交通检查。
假设车辆以一定的速率到达，则存在一定的随机性，并且车辆每隔a到b分钟(自己设定)到达一次。
海关有k个查验渠道，查验需要c到d分钟。
到达的车辆在专用线路上排队等候。一旦检查通道空闲，队列中的第一辆车将进入该通道进行检查。如果车辆到达时有空车道并且没有等待车辆，则立即进入车道并开始检查。（先判断线路上上是否有等待车辆）。
所需数据包括车辆的平均等待时间和通过检查站的平均时间。
假设模拟一天的平均值。

二、需求分析

该问题要实现一个模拟海关检查的系统，需要自己设定各种随机的值，比如车辆到达站点的间隔时间，海关检查的所需时间，一共有多少个关卡，海关的工作时间等等，在用户自我规定的工作时间中，记录来访车辆的总数、以及车辆的平均排队时间和平均运输时间。并且要动态的记录车辆的自身数据，可以由用户随机设定每辆车的属性。

最后需要输出的是在用户规定的工作时间段内车辆通过海关的动态情况，海关开放的关卡数，有多少条等待队列，多少条空队列，通过海关的总车辆，以及车辆的平均排队时间和平均运输时间。

三、数据结构和类设计

在实验中主要采用的数据结构为队列，因为模拟车辆通行，等待的车流通道相当于一个队列，海关关卡为队列的头，遵循先进先出的原则，所以使用队列更符合海关检查的情形。

包含的类有Car、Queue

Queue：遵循先进先出原则,这个类中又包含enqueue、dequeue、ger_head 、travle等函数

Car: 包含车辆的内置属性（车辆的最佳接受检查的站点，车辆检查所需要的时间

包含的函数有shortesttime_customs_num、simulate

Shortesttime_customs_num:根据虚拟等待时间来计算车辆的车辆的最佳接受检查的站点

Simulate:模拟实现车辆接收检查的过程

数据结构-海关检查站模拟,数据结构,python

四、算法设计

(1）遍历整个ServTime，对每个时刻来说，首先判断此刻是否有车辆到来。

(2）若此刻没有顾客来，那么无需安排顾客排队。若此刻有顾客来，那么查看每个站点后是否还有等待时间。若虚拟等待时间队列为空，则让车辆加入；若等待时间不为0，则查看哪个站点的等待总时间最短，并安排车辆当他在队头时，下一步在此站点进行检查。

(3）最后，每个虚拟等待时间队列的队头车辆的检查时间都要-1。若有顾客的时间变为0，则让其出站，下一辆车接受检查。

五、代码实现

import random

#显示的数据均是每一分钟的时刻末
#定义一个基于列表的队列 来维护车辆队列
class Queue(object):
    """队列"""
    def __init__(self):
        self.items = []

    def is_empty(self):
        return self.items == []

    def enqueue(self, item):
        """进队列"""
        self.items.append(item)

    def dequeue(self):
        """出队列"""
        return self.items.pop(0)

    def size(self):
        """返回大小"""
        return len(self.items)

    def get_head(self):
        if self.is_empty():
            return False
        else:
            return self.items[0]

    def travle(self):
        return self.items


class Car:
    def __init__(self, c=-1, t=-1):
        self.customs_num = c #当车辆在队头时应当排在第几窗口
        self.time = t #车辆检查所需要的时间

    def __str__(self):
        return f"leave from custom: {self.customs_num}"

# 找出目前等待总时间最短的站点
def shortesttime_customs_num(custom_line, customs):#传入站点的个数
    """返回最合适的检查站编号"""
    shortest_time = 10000
    shortesttime_custom = 1000
    for i in range(customs):
        if custom_line[i].is_empty():
            return i#若站点为空 则直接返回
        else:
            list = [j.time for j in custom_line[i].travle()]#等待时间列表
            sum = 0
            for k in list:
                sum += k#求等待时间之和最短
        if sum < shortest_time:
            shortest_time = sum
            shortesttime_custom = i
    return shortesttime_custom

#模拟函数
def simulate(customs: int, servTime: int):
    start_checktime = int(input("please input the start time of one check:"))
    end_checktime = int(input("please input the end time of one check:"))
    custom_lines = [Queue() for _ in range(customs)] # 生成一个有n个链队列的列表，假设每个站点前即都有一个虚拟队列
    total_cars = 0#计算车辆总数
    total_wait_time = 0
    total_check_time = 0
    average_wait_time = 0
    average_check_time = 0
    for now in range(servTime):  # 遍历每一个时刻
        print("现在是第",now,"分钟")
        if random.randint(0,1):#随机来车 电脑生成
            print("有车入队！")
            total_cars += 1#计算总车辆数
            bset_num = shortesttime_customs_num(custom_lines,customs)#等待时间最短的站点
            a = random.randint(start_checktime,end_checktime) #这里假设顾客的所需服务时间为[3,5)
            total_check_time += a#总检察时间
            car = Car(bset_num,a)#车辆自身属性（最佳站点，检查时间）
            custom_lines[bset_num].enqueue(car)
            print("TA的最佳入站点是%s，TA所需检查时间是%s"%(bset_num,a))
            print("第%s个车辆到第%s个站点侯检..."%(now,bset_num))
        else:
            print("此分钟没有车辆来！")
        for i in range(customs):
            if not custom_lines[i].is_empty():
                if custom_lines[i].get_head().time == 0:#车辆检查完毕，车辆出站，头节点用0代替
                    custom_lines[i].dequeue()#出站
                    print("第%s个站点的车辆已经离开" % (i))
                else:
                    custom_lines[i].get_head().time = custom_lines[i].get_head().time-1#总时间每过一分钟，检查时间减少一分钟

        for i in range(customs):
            list = []
            for j in custom_lines[i].travle():
                list.append(j.time)#将在主队列的所有车辆转为虚拟队列的等待时间
            for k in list[1:]:#每个虚拟等待时间队列的第一个元素往后都是车辆排队等待时间
                total_wait_time += k

            # average_wait_time = total_wait_time / total_cars
            # average_check_time = total_check_time / total_cars

            #检测各站点的状态 开头的状态
            if list == []:
                state = '空闲'
            else:
                for s in list[:1]:
                    if s != 0:
                        state = '检查中'
                    else:
                        state = '空闲'

            ####print(list)
            print("Current check status of site %s：%s|The remaining time of vehicle inspection at the station at that time %s"%(i,state,list))
        average_wait_time = total_wait_time / total_cars
        average_check_time = total_check_time / total_cars
        print("————————|||————————End of minute %s————————|||————————"%(now))
    print("The total number of vehicles passing through is：%s"%(total_cars))
    print("Total waiting time of vehicles：%s"%total_wait_time)
    print("Average waiting time of vehicles is：%s"%(average_wait_time))
    print("Average waiting time of vehicles is：%s"%total_check_time)
    print("Average vehicle inspection time is：%s"%(average_check_time))

if __name__ == '__main__':
    customs = int(input("please input the number of customs:"))
    total_time = int(input("please input the total custom's working time:"))
    simulate(customs,total_time)