请查看原文:
http://www.ibaiyang.org/2012/11/20/queue-list/
在我读严蔚敏版的《数据结构》的时候,看到其中一个例子,让我对数据结构佩服的五体投地,让人把如此的一个问题分析的这么透彻,十分钦佩。也让我明白了一个道理,在设计好的算法之前,一定要设计好的数据结构,当你设计了好的数据结构之后,反而会为你写算法有很大的帮助,这是我深有体会的。
在这里,就将在重复一下这个例子吧,方便以后借鉴,这个例子主要是模拟离散事件的例子。
引言
在日常生活中,我们经常会遇到各种排队的事情,比如乘地铁,去食堂就餐。我们就以去银行办理业务为例,在我们走进银行之后,我们需要到窗口办理自己的业务。
现在需要编制一个软件,模拟银行的这种业务活动并计算一天客户中在银行逗留的平均时间。
在这里,需要满足以下条件:
- 进来的客户是随即的;
- 进来之后的客户选择较短的队列排队;
为了计算客户在一天当中的平均逗留时间,需要知道每个客户在银行的逗留时间,然后其每个客户逗留时间之和除以总人数既是平均逗留时间。在通常情况下,我们知道客户到达和离开银行的时间,自然知道每个客户在银行的逗留时间。所以,我们将客户达到和离开银行这二个时刻发生的事情称为“事件”,整个模拟程序是按照事件发生的先后顺序来进行处理,这样一种模拟程序称作“事件驱动模拟”。
实现
以下描述正是上述银行客户的离散事件驱动模拟程序:
void bank_simulation(int close_time)
{
open_for_day();
while(more_event){
event_drive(occure_time, event_type);
switch(event_type){
case "A": customer_arrived(); break;
case "D": customer_departure(); break;
default: invalid();
}
}
close_for_day();
}
以上算法主要处理对象是“事件”, 事件的主要信息是由事件类型和事件发生的时刻。算法中要处理二类事件:一类是客户达到事件;一类是客户离开事件。前一类事件发生的时刻随客户的打来而自然形成;后一类事件发生则由客户事务所需时间和等待所消耗的时间而定。由于程序驱动是按照事件发生时刻的先后顺序进行,则事件表应该是有序表,其主要操作是插入和删除事件。
模拟程序中的另一种数据结构是表示客户排队的队列,假设银行有4个窗口,则程序需要有4个队列,队列中有关客户的主要信息是客户到达的时刻和客户办理事务所需要的时间。每个队列中的对头客户即为正在窗口办理事务的客户,他办完事务离开队列的时刻就是即将发生客户离开事件的时刻,对每个队列头客户都存在一个将要驱动的客户离开事件。因此,在任何时刻即将发生的事件只有以下5种可能:
- 新的客户达到;
- 1号窗口客户离开;
- 2号窗口客户离开;
- 3号窗口客户离开;
- 4号窗口客户离开;
由以上分析,在这个模拟程序中只需要二种数据结构:有序表和队列。他们的数据元素类型分别定义如下:
typedef struct {
int occure_time;
int event_type;
} Event;
typedef vector< Event> event_list;
typedef struct {
int arrival_time;
int duration;
} QElemType;
给出了数据结构,结合之前的算法框架,就很容易实现程序了,以下给出伪代码
event_list ev; // 事件表
Event en; // 事件
LinkQueue q[5]; // 4个客户队列
QElemType customer; // 客户记录
int total_time, customer_nr = 0;
void open_for_day()
{
total_time = customer_nr = 0;
init_list(ev);
en.occure_time = 0; en.event_type = 0; // 设定第一个客户到达事件
order_insert(ev, en, cmp);
for(i = 1; i < 4; i++){
init_queue(q[i]);
}
}
void customer_arrived()
{
customer_nr ++;
random(durtime, intertime); // 产生随机数
t = en.occure_time + intertime; // 下一个客户到达事件
if( t < close_time ){
order_insert(ev, (t, 0), cmp);
}
i = minimum(q);
enqueue(q[i], (en.occure_time, durtime));
if( queue_len(q[i]) == 1){
order_insert(ev, (en.occure_time + durtime, i), cmp);
}
}
void customer_departure()
{
i = en.event_type; del_queue(q[i], customer); // 删除队列头的客户
total_time += en.occure_time - customer.arrival_time;
if( !queue_empty() ){ // 设定第i队列的一个离开事件并插入事件表
get_head(q[i], customer);
order_insert(ev, (en.occure_time + customer.duration, i)), cmp);
}
}
我觉得写到这里,读者应该仔细去体会“驱动”二字,请分别看以上函数,举customer_departure函数为例,当该i队列产生客户离开事件后,并产生一个新的离开事件,如果该i队列不为空的话,为何会产生这个离开事件呢,因为事件表中产生了一个事件,表明第i个队列的头客户已经离开,故会产生另一个客户排在队头,当然会产生一个离开事件了。
联想
在慢慢的品味这个算法时,让我联想到了多线程中,生产—消费模型,貌似也是一个事件驱动模型,不知道对不对,不过我认为是吧,可以知道生产和消费为其中的二个事件。给出伪代码。
void produce()
{
// 创建临界区域
lock();
while( v.len() == max_len ){
condition_wait();
}
v.push_back( t );
unlock();
if( v.len() == 1){
notify_all();
}
}
void consume()
{
lock();
while ( v.len() == 0 ){
condition_wait();
}
t = v.pop();
unlock();
if( v.len() == 0){
notify_all();
}
}
为什么我说这是事件驱动模型呢,因为我觉得,当生产出来了资源,即v不为空时,自然会唤醒consume线程去消费它,相反,当v为空时,又会唤醒produce生产资源,其中的唤醒类似驱动原理。
【注】如有理解偏差,实属能力问题,本人还在努力之中,共同进步。
-----------------打造高质量的文章 更多关注 把酒泯恩仇---------------
为了打造高质量的文章,请 推荐 一下吧。。。。谢谢了,请关注我后续的文章,会更精彩哦
请关注sina微博:http://weibo.com/baiyang26
把酒泯恩仇官方博客:http://www.ibaiyang.org 【推荐用google reader订阅】
把酒泯恩仇官方豆瓣:http://www.douban.com/people/baiyang26/
如果您想转载本博客,请注明出处
如果您对本文有意见或者建议,欢迎留言
分享到:
相关推荐
队列和链表节选2队列和链表节选2队列和链表节选2
链表实战题目4 - 链表入环的第一个节点给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回 null。为了表示给定链表中的环,我们使用整数 pos
队列的链表表示(节点数据为结构),源码,已测试可运行
排序 查找 队列 栈 链表等的C语言简单实现
在队列的代码中,引用了链表的代码
1. 数组实现 2. 链表实现 1. 数组实现 2. 链表实现
1. 数组实现 2. 链表实现 1. 数组实现 2. 链表实现
队列关于数组与链表的实现, linux c语言
使用C++语言实现了栈,队列和链表三种数据结构,程序中包含有各种数据结构的初始化,插入元素,删除元素等相关操作。
算法思想:首先先得到链表长度,边遍历边逆置,逆置一半len/2,定义双指针,如果链表长为奇数,那么pCur指向中间位置,直接跳过即可判断对应位置元素是否相等,直
数据库与数据结构课程 堆栈链表与队列链表的基本操作函数,还有可供参考的可执行文件exe
# 将第一个节点指向第三个节点# 第二个节点指向第一个节点# 节点first指向第二个节点# 当前节点后移动,记得a.next是节点3,相当于跳了一个节点,往后
python利用数组和链表实现栈和队列 数组和链表.pdf
015-反转链表题目描述输入一个链表,反转链表后,输出新链表的表头。思路从原链表的头部一个一个取节点并插入到新链表的头部。指针tmp指向还没进行反转的原链表头部
python算法-数组和链表 数组和链表.pdf
给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回 null。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从
VC 运用循环队列和链表技巧开发的贪吃蛇游戏,游戏的玩法和其它的贪食蛇游戏没什么区别,但是编程思路和运用的技巧却与其它的同类游戏大相径庭,本游戏运用了循环队列和链表的技巧而编写,操作方法:按键盘上的W/A/S...
解释:链表中有一个环,其尾部连接到第二个节点。示例 2:解释:链表中有一个环,其尾部连接到第一个节点。示例 3:输出:false解释:链表中没有环。进阶:你能用
顺序建链表
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。示例 2:输入解释:从各自的表头开始算起,链表 A 为