Author: 王介哲 1200010730
假设某机场停机坪共可停放n架飞机,若停机坪上已停满n架飞机, 则后来的飞机只能在空中盘旋等候, 调度等候飞机降落的顺序是由飞机的当前现有燃油量程度来决定。 机场按照所有飞机到达的时间顺序给飞机编号ID,依次为1,2,3,…,m; 并且根据飞机的燃油量设置Priority值,燃油量越少,Priority的值越小。 一旦停机坪上的飞机起飞,系统将根据等候的飞机的Priority值, 由小到大依次安排飞机降落。 航空公司必须按照每架飞机在停机坪停留的时间长短交纳费用。
开发一个机场对飞机起落进行管理的程序。
这一部分的信息储存在
src/data.h
中
总体来说,整个程序分为两个层次:界面和内部数据处理。
由于采用的是GTK+界面编程,主要涉及到的是GTK+的C API函数的调用和实现。
这一部分的具体实现见后面。
这一层又分为四个部分:飞机进入等待队列,飞机降落,飞机起飞和飞机修整。
由于飞机的降落顺序是按照其剩余油量来确定的,剩余油量较少的飞机优先降落,
遵循最小元素先出的原则。因此,采用优先队列来实现飞机的等待队列waiting
。
为了便于比较以及后面不需要做过多的转化,在存储飞机信息是并不是直接存储其剩余油量, 而是将其换算成允许降落的最后期限。这样得到的排序与直接按剩余油量得到的排序结果相同。
具体的实现方式是采用小根堆,与二叉树的定义类似。
struct PriorityQueue { /* 优先队列 */
int MAXNUM;
int n;
DataType_pq * pq; /* 优先队列中元素的顺序表示 */
};
typedef struct PriorityQueue * PPriorityQueue;
PPriorityQueue waiting;
其中,DataType_pq为等待降落的飞机的信息的定义。 由于需要同时储存飞机的航班号和允许降落的最后期限,故用一个结构来存储飞机信息:
struct flight {
char flight_name[7]; /* 航班号,国内航班为六位,国际航班为七位 */
time_t landing_deadline; /* 允许降落的最后期限 */
};
typedef struct flight DataType_pq;
这样,每次有飞机到来,点击New plane arrived
按钮,并输入航班号和剩余油量,
即可将其加入到等待队列中,剩余油量和最后降落期限的转化由系统自动完成。
为了便于与其他信号函数进行信息交互,定义一个runway_down
表示降落跑道的状态:
gint runway_down;
runway_down
的值为0(即初始值),表示跑道空闲,可以降落飞机;
runway_down
的值为1,表示跑道已被占用或正在准备,不能降落飞机。
根据前面的假设,各架飞机降落和修整的时间均相同,
故先降落的飞机先修整完毕,进入等待起飞状态。
这符合先进先出的原则,故可以用以个队列来实现停机坪上的飞机队列reseting
。
具体的实现方式可以通过环形队列的顺序表示来实现:
struct SeqQueue{
int MAXNUM;
int f,r;
DataType_q *q;
};
typedef struct SeqQueue * PSeqQueue;
PSeqQueue resting;
其中,DataType_q
为停在停机坪上的飞机的信息的定义,
由于需要储存飞机的航班号和其降落时间,故采用一个结构来实现:
struct SeqQueue{
int MAXNUM;
int f,r;
DataType_q *q;
};
typedef struct SeqQueue * PSeqQueue;
PSeqQueue reseting;
需要注意的是由于采用环形队列牺牲了一个节点, 故
resting->MAXNUM
应该比停机坪的最大允许停机数目大1.
这样,当New plane to land
按钮可用时,
点击即可将等待队列中的最前端的一架飞机由等待队列进入停机队列。
如果等待队列为空,将给出提示信息,无其他任何影响。
遇上面类似,定义一个runway_up
来表示起飞跑道的状态:
gint runway_up;
runway_up
的值为0(即初始值),表示跑道空闲,可以起飞飞机;
runway_up
的值为1,表示跑道已被占用或正在准备,不能起飞飞机。
当New plane to take off
按钮可用时,点击即可发送飞机起飞指令,
处在停机队列最前端的飞机随即进入起飞过程。
事实上,飞机修整部分与降落和起飞部分并不是相互独立的,
主要涉及到的就是飞机由停机队列到起飞的过程转化。
这一过程主要利用alarm
函数来实现。
当停机队列最前端的飞机达到休息时间时,向自己发送SIFALRM
信号,
程序接受到该信号后使New plane to take off
按钮变为可用,
即修整完毕可以进入起飞过程。
先调用gtk_window_new(GTK_WINDOW_TOPLEVEL)
建立主窗口,
并调用g_signal_connect
绑定基本信号。
然后建立菜单栏和状态栏,这一部分内容较少。
最后是界面的主要控制和输出部分,分为三个部分: 空中等待,飞机降落和飞机起飞。
左边部分。
具体分为三部分。
最上面为New plane arrived
按钮,为控制其大小建立在一个表格中。
中间是一个标签,现实等待队列中的剩余飞机数。
下面是信息输出框,当数据增加时,会自动显示滚动条并跟踪输出数据滚动。
这一部分的重点在于
New plane arrived
的回调函数。当用户点击该按钮时,程序会调用
gtk_dialog_new
构建一个新的对话框。 当用户输入正确的数据后(这里未设置检查函数,要求用户对自己的输入负责), 点击Ok
后程序将调用dialog_ok_clicked
用户的输入导入到等待队列中, 并在下方的输出框中显示存储的信息; 点击Cancal
取消输入。
中间部分。
最上面为New plane to land
按钮,构建同上。
中间是一个进度条,用来显示飞机降落的进度。
下面是信息输出框,现实降落的飞机的信息。
这一部分的重点在于
New plane to land
的回调函数。当用户点击该按钮时,程序会调用
new_plane_to_land
函数。 该函数首先检查等待队列是否为空,若为空则在下方输出提示信息并返回。 若不为空,则将等待队列中的第一个取出并从队列中删除, 然后在下方输出提示信息,并将启动进度条控制函数progress_timeout2
, 同时将New plane to land
按钮变为不可用。
progress_timeout2
按照计时器pdata2->timer
不断更新进度条pdata2->pbar
, 直到进度条满后,停止计时器,将飞机的航班号和降落时间存入停机队列, 并输出提示信息,根据停机队列的情况将New plane to land
按钮变为可用 或启动alarm
函数。
右边部分。
结构与中间类似,按钮为New plane to take off
。
与中间不同的是,该按钮在初始状态下不可用,必须当有飞机可以起飞时,
被alarm
函数唤醒后才可使用。
这一部分的重点在于
New plane to take off
的回调函数。当用户点击该按钮是,程序会调用
new_plane_to_take_off
函数。 改善数将停机队列中的第一个取出并从队列中删除, 然后在下方输出提示信息,并启动进度条控制函数progress_timeout3
, 同时将New plane to take off
按钮变为不可用。
progress_timeout3
按照计时器pdata3->timer
不断更新进度条pdata3->pbar
, 直到进度条满后,停止计时器,输出提示信息, 并根据停机队列的情况启动alarm
函数。
时间代价主要是两个队列的操作。
飞机等待队列waiting
的插入和删除,由于采用的是优先队列,故其时间代价都是O(log2n)。
飞机停机队列reseting
采用的是顺序表示的队列,时间代价为O(1)。
空间代价主要是两个队列和程序控件的存储。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。