★ FEATURED ARTICLE 简介这份数据结构期末作业资源聚焦银行排队系统的完整实现面向正在学习队列、优先级调度与文件I/O的计算机专业学生尤其适合需要完成课程设计或期末大作业的读者参考。压缩包共9个文件约1.03MB包含cpp源码、txt数据文件、cbp项目配置、depend依赖记录、layout布局文件以及编译生成的exe与o文件覆盖从源码到可执行程序的完整链路。资源核心在于用两个队列分别管理VIP与普通用户通过优先检查VIP队列实现优先级服务并借助C STL的queue容器完成入队、出队与队头读取同时演示了从文本文件读取用户到达时间与身份信息并解析为队列输入的过程。已有3362人学习下载读者可据此理解多队列设计、控制流程逻辑与文件I/O操作并对照项目结构快速复现和调试自己的银行排队模拟程序。1. 银行排队系统为什么它是数据结构课设里最值得死磕的一个银行排队系统这个题目几乎每届数据结构作业都会出现。很多人第一反应是“不就是个队列吗”然后花两小时写完一个先进先出交上去发现连及格线都够呛。问题出在真实的银行排队根本不是单一队列。窗口有普通窗口和 VIP 窗口客户分个人业务和对公业务柜员有忙有闲客户还会因为等太久直接走人。这些细节背后对应的是队列、优先队列、链表、时间模拟四套数据结构的组合运用。这个题目的价值在于它逼着你把“抽象数据类型”和“真实业务约束”对上号。做透了你能掌握离散事件模拟的基本套路这套思路在流量调度、任务编排、订单撮合里是通用的。做不透就只是一个把数字从队尾搬到队头的练习。这篇文章面向正在做这个作业的学生也面向想用一个小项目把队列和模拟串起来的人。下面从建模、选结构、写代码到排错一步步拆开讲。2. 先把业务模型定死三类客户、两种窗口、一个时钟2.1 离散事件模拟到底在模拟什么银行排队系统的本质是一个离散事件模拟。时间不是连续流动的而是被“事件”切成一段一段客户到达是一个事件客户开始办理是一个事件客户办理完成离开是一个事件。你不需要每毫秒去更新状态只需要维护一个按时间排序的事件序列每次取出最早的事件处理然后推进时钟。这个思路的好处是效率极高。假设一天有 500 个客户你只需要处理大约 1500 个事件而不是模拟 28800 秒的每一秒。常见做法是用一个优先队列最小堆来存事件按事件时间排序。每次弹出堆顶把时钟拨到那个时刻处理完再生成后续事件塞回去。这里有一个容易翻车的地方事件时间必须严格单调递增。如果生成后续事件时算错了时间比如服务完成时间早于开始时间整个模拟就会乱套。我一般会在事件结构体里加一个自增序号作为第二关键字时间相同时按序号排避免堆里出现不确定顺序。2.2 客户类型和窗口类型怎么映射到数据结构先定义清楚业务规则。假设银行有两类窗口普通窗口只服务个人客户综合窗口可以服务个人客户和对公客户。客户到达时按概率分布随机决定类型。个人客户占多数对公客户占少数但办理时间长。客户实体需要这些字段到达时间、类型、业务耗时、优先级。窗口实体需要窗口编号、类型、当前服务的客户、空闲时间点。队列方面普通窗口前挂一个普通队列综合窗口前挂两个队列——一个个人队列一个对公队列综合窗口空闲时优先取对公队列因为对公客户少但耗时长积压了会影响满意度。VIP 客户的处理有两种常见方案。方案一是单独开 VIP 窗口方案二是 VIP 客户插入普通队列头部。方案一更简单方案二更贴近真实但实现时要小心如果 VIP 客户不断到达普通客户可能永远排不到这就是优先级反转。我一般建议作业里用方案一逻辑清晰也好向老师解释。2.3 用参数表把随机性管起来模拟离不开随机数但随机数不能散落在代码各处。把所有概率和分布参数集中到一张配置表里改参数不用翻代码。参数名含义建议取值备注arrive_rate客户到达速率人/分钟0.5~2.0泊松分布均值vip_ratioVIP 客户占比0.1~0.2均匀分布判定corp_ratio对公客户占比0.15~0.3在非 VIP 中判定personal_service个人业务耗时均值分钟3~6指数分布corp_service对公业务耗时均值分钟8~15指数分布window_count普通窗口数2~4整数vip_window_countVIP 窗口数1整数sim_duration模拟总时长分钟480一个工作日这张表的意义在于你可以用不同参数组合跑多组实验观察平均等待时间怎么变化。作业里如果能附上“窗口数从 2 增加到 4平均等待时间下降 60%”这样的结论分数会好看很多。3. 队列选型数组队列、链表队列和优先队列各管什么3.1 普通队列用循环数组还是链表普通窗口前的客户队列操作只有入队和出队先进先出。用循环数组实现的好处是内存连续、缓存友好缺点是容量固定需要预估最大排队人数。用链表实现的好处是容量无上限缺点是指针跳转和内存分配开销。我的建议是如果模拟时长固定、到达率已知用循环数组容量设为“最大可能排队人数 余量”。计算方法是到达率 × 模拟时长 × 1.5。比如到达率 2 人/分钟、模拟 480 分钟最多 960 人到达容量设 1500 足够。如果不想算直接用链表省心。循环数组队列的关键是判空和判满。用 front 和 rear 两个下标front 指向队头元素rear 指向队尾元素的下一个位置。判空条件是 front rear判满条件是 (rear 1) % capacity front。注意这里牺牲了一个存储单元来区分空和满这是常见做法。// 循环数组队列定义 #define QUEUE_CAPACITY 1500 typedef struct { Customer data[QUEUE_CAPACITY]; int front; // 队头下标 int rear; // 队尾下标的下一个位置 } CircularQueue; // 初始化 void queue_init(CircularQueue *q) { q-front 0; q-rear 0; } // 判空 int queue_empty(CircularQueue *q) { return q-front q-rear; } // 判满牺牲一个单元 int queue_full(CircularQueue *q) { return (q-rear 1) % QUEUE_CAPACITY q-front; } // 入队 int queue_push(CircularQueue *q, Customer c) { if (queue_full(q)) return -1; // 队满入队失败 q-data[q-rear] c; q-rear (q-rear 1) % QUEUE_CAPACITY; return 0; } // 出队 int queue_pop(CircularQueue *q, Customer *c) { if (queue_empty(q)) return -1; // 队空出队失败 *c q-data[q-front]; q-front (q-front 1) % QUEUE_CAPACITY; return 0; }这段代码里QUEUE_CAPACITY是容量实际可用元素数是QUEUE_CAPACITY - 1。queue_push和queue_pop返回 -1 表示失败调用方必须检查返回值。很多人的翻车点就在这里入队不检查满没满数组越界写坏了其他变量程序跑着跑着结果就飘了。3.2 优先队列最小堆怎么实现事件调度事件调度需要每次取出时间最早的事件这正是最小堆的拿手好戏。堆用数组存储下标从 0 开始。父节点下标 i左孩子 2i1右孩子 2i2。插入时把新元素放到数组末尾然后上浮删除堆顶时把末尾元素移到堆顶然后下沉。// 事件结构体 typedef struct { double time; // 事件发生时间 int seq; // 同时间事件的序号保证稳定排序 int type; // 0到达 1开始服务 2服务完成 int customer_id; // 关联客户 int window_id; // 关联窗口 } Event; // 最小堆 typedef struct { Event data[MAX_EVENTS]; int size; } MinHeap; // 比较两个事件时间小的优先时间相同序号小的优先 int event_less(Event a, Event b) { if (a.time ! b.time) return a.time b.time; return a.seq b.seq; } // 上浮 void heap_up(MinHeap *h, int i) { while (i 0) { int parent (i - 1) / 2; if (event_less(h-data[i], h-data[parent])) { Event tmp h-data[i]; h-data[i] h-data[parent]; h-data[parent] tmp; i parent; } else break; } } // 下沉 void heap_down(MinHeap *h, int i) { while (1) { int left 2 * i 1; int right 2 * i 2; int smallest i; if (left h-size event_less(h-data[left], h-data[smallest])) smallest left; if (right h-size event_less(h-data[right], h-data[smallest])) smallest right; if (smallest i) break; Event tmp h-data[i]; h-data[i] h-data[smallest]; h-data[smallest] tmp; i smallest; } } // 插入事件 void heap_push(MinHeap *h, Event e) { h-data[h-size] e; heap_up(h, h-size); h-size; } // 弹出堆顶 Event heap_pop(MinHeap *h) { Event top h-data[0]; h-data[0] h-data[h-size - 1]; h-size--; heap_down(h, 0); return top; }event_less是堆的核心比较函数。先比时间时间相同比序号。序号在生成事件时全局自增保证不会有两个事件完全相等。heap_push先放末尾再上浮heap_pop先把末尾移到堆顶再下沉。这两个操作的时间复杂度都是 O(log n)n 是事件数。3.3 窗口空闲列表用数组还是链表窗口数量通常不多几个到十几个用数组存窗口状态就够了。每个窗口记录编号、类型、是否空闲、当前客户 ID、预计空闲时间。当客户到达时遍历窗口数组找空闲且类型匹配的窗口。如果找到直接开始服务如果没找到客户入对应队列。遍历数组是 O(n)但 n 很小不值得优化。如果非要优化可以维护一个空闲窗口的链表但作业里没必要反而增加出错概率。我见过有人用链表维护空闲窗口结果删除节点时忘了改前驱指针窗口凭空消失模拟结果完全不对。4. 核心调度逻辑从客户到达 to 离开的完整链路4.1 事件循环的骨架整个模拟的主循环就是不断从堆里取事件、处理事件、生成新事件。伪代码如下void run_simulation(SimConfig *cfg) { MinHeap events; heap_init(events); // 生成第一个到达事件 Event first_arrival { .time generate_arrival_time(cfg), .seq next_seq, .type EVENT_ARRIVAL, .customer_id next_customer_id }; heap_push(events, first_arrival); double clock 0.0; while (events.size 0) { Event e heap_pop(events); clock e.time; // 时钟推进到事件时刻 switch (e.type) { case EVENT_ARRIVAL: handle_arrival(events, clock, e, cfg); break; case EVENT_START_SERVICE: handle_start_service(events, clock, e, cfg); break; case EVENT_FINISH_SERVICE: handle_finish_service(events, clock, e, cfg); break; } } }clock变量记录当前模拟时间。每次弹出事件后把 clock 设为事件时间。注意不要用 clock 去生成随机数种子否则每次跑结果都一样。随机数种子应该在模拟开始前设一次。handle_arrival负责记录客户到达统计、判断客户类型、找空闲窗口或入队、生成下一个到达事件。handle_start_service负责更新窗口状态、生成服务完成事件。handle_finish_service负责释放窗口、从队列取下一个客户、如果队列非空则生成开始服务事件。4.2 到达事件的处理细节void handle_arrival(MinHeap *events, double *clock, Event e, SimConfig *cfg) { // 统计到达人数 stats.total_arrived; // 判断客户类型 Customer c; c.id e.customer_id; c.arrive_time e.time; c.type determine_customer_type(cfg); // 个人/对公/VIP // 找空闲且类型匹配的窗口 int wid find_idle_window(c.type); if (wid 0) { // 窗口空闲直接开始服务 Event start { .time *clock, .seq next_seq, .type EVENT_START_SERVICE, .customer_id c.id, .window_id wid }; heap_push(events, start); } else { // 没有空闲窗口入队 enqueue_customer(c); stats.total_queued; } // 生成下一个到达事件 if (*clock cfg-sim_duration) { Event next { .time *clock generate_interarrival(cfg), .seq next_seq, .type EVENT_ARRIVAL, .customer_id next_customer_id }; if (next.time cfg-sim_duration) { heap_push(events, next); } } }determine_customer_type用随机数决定客户类型。find_idle_window遍历窗口数组返回第一个空闲且类型匹配的窗口下标找不到返回 -1。enqueue_customer根据客户类型把客户放入对应队列。注意next.time cfg-sim_duration这个判断如果下一个到达时间超过了模拟结束时间就不再生成到达事件。但已经入队的客户还要继续服务完所以主循环不能因为到达事件没了就退出要等所有事件处理完。4.3 服务完成与队列出队void handle_finish_service(MinHeap *events, double *clock, Event e, SimConfig *cfg) { int wid e.window_id; Window *w windows[wid]; // 记录客户离开时间和等待时间 Customer *c customers[e.customer_id]; c-leave_time *clock; c-wait_time c-service_start_time - c-arrive_time; stats.total_wait_time c-wait_time; stats.total_served; // 释放窗口 w-idle 1; w-current_customer -1; // 从队列取下一个客户 Customer next_c; if (dequeue_customer(w-type, next_c)) { // 队列非空立即开始服务 Event start { .time *clock, .seq next_seq, .type EVENT_START_SERVICE, .customer_id next_c.id, .window_id wid }; heap_push(events, start); } }dequeue_customer根据窗口类型从对应队列取客户。综合窗口优先取对公队列对公队列空了再取个人队列。这个优先级顺序会影响对公客户的平均等待时间可以在实验里对比两种策略。wait_time的计算是service_start_time - arrive_time不是leave_time - arrive_time。后者包含了服务时间不是真正的等待时间。这个细节很多人搞混导致统计结果偏大。5. 避坑与排查模拟结果不对时先查这五个地方5.1 平均等待时间是负数现象跑完模拟统计输出里平均等待时间是负数。原因service_start_time在客户入队时没有正确设置或者事件处理顺序错了先处理了服务完成再处理开始服务。解决在handle_start_service里设置c-service_start_time *clock确保这个赋值发生在生成服务完成事件之前。另外检查堆的比较函数确保时间早的事件先弹出。5.2 队列长度只增不减现象模拟跑了一段时间后队列越来越长窗口却有空闲。原因find_idle_window的类型匹配逻辑写错了比如把个人客户匹配到了对公窗口或者窗口释放后idle标志没置回 1。解决在handle_finish_service里确认w-idle 1被执行了。再检查find_idle_window里的类型判断个人客户只能匹配普通窗口和综合窗口对公客户只能匹配综合窗口。5.3 模拟时间不推进死循环现象程序卡住不输出结果CPU 占用高。原因事件时间没有递增堆里不断弹出同一个时间的事件或者生成新事件时时间算错导致新事件时间等于当前时间。解决在生成下一个到达事件时generate_interarrival必须返回正数。如果用了指数分布要确保随机数不为 0。另外检查heap_pop之后size有没有减 1忘了减会导致堆顶永远是同一个元素。5.4 随机数每次跑结果一样现象多次运行程序输出结果完全相同。原因随机数种子固定或者根本没设种子。解决在main函数开头调用srand(time(NULL))。如果是在线评测系统time(NULL) 可能返回相同值可以用srand(time(NULL) getpid())。但注意如果作业要求结果可复现那就固定种子这是另一回事。5.5 统计数据和手工计算对不上现象模拟输出的服务人数和到达人数不一致或者平均等待时间和手算差很多。原因统计变量在错误的地方累加比如客户入队时加了等待时间出队时又加了一次。解决把统计逻辑集中到一个函数里每次客户离开时统一更新。另外注意模拟结束时队列里还有客户没服务完这些客户的等待时间不能算进平均值否则会偏大。可以在最后输出“队列剩余人数”作为参考。6. 让作业加分多组实验对比与可视化输出6.1 用参数扫描找出窗口数的最优解作业如果只跑一组参数结论很单薄。我一般会做参数扫描固定到达率和服务时间把普通窗口数从 2 增加到 6每组跑 10 次取平均记录平均等待时间和窗口利用率。窗口利用率 总服务时间 / (窗口数 × 模拟时长)。理想情况下利用率在 70% 到 85% 之间比较健康太低浪费人力太高客户等太久。// 参数扫描示例 for (int wc 2; wc 6; wc) { double total_wait 0.0; double total_util 0.0; for (int trial 0; trial 10; trial) { SimConfig cfg default_config(); cfg.window_count wc; SimResult r run_simulation(cfg); total_wait r.avg_wait_time; total_util r.window_utilization; } printf(窗口数%d, 平均等待%.2f 分钟, 利用率%.1f%%\n, wc, total_wait / 10, total_util / 10 * 100); }这段代码跑完会输出一张表直接放进作业报告里就是现成的实验数据。注意每次 trial 要重新初始化随机数种子否则 10 次结果一样。如果要求可复现就固定种子但改变窗口数。6.2 输出时间线日志方便排查模拟过程中把关键事件打到日志文件里格式为“时间 事件类型 客户ID 窗口ID”。出问题时打开日志一看就知道哪个环节断了。日志不用太详细到达、开始服务、服务完成三类事件足够。可以在编译时用宏控制日志开关交作业时关掉调试时打开。#ifdef DEBUG_LOG fprintf(logfile, %.2f ARRIVE cust%d type%d\n, *clock, c.id, c.type); #endif这个技巧在排查“为什么这个客户等了 100 分钟”这类问题时特别有用。顺着日志找到客户的到达时间再看窗口的空闲时间很快就能定位是窗口不够还是调度逻辑有问题。6.3 用 Python 画等待时间分布图C 语言负责模拟输出 CSV 文件每行一个客户的等待时间。然后用 Python 的 matplotlib 画直方图。这样作业报告里既有代码又有图说服力强很多。import matplotlib.pyplot as plt import csv wait_times [] with open(wait_times.csv, r) as f: reader csv.reader(f) for row in reader: wait_times.append(float(row[0])) plt.hist(wait_times, bins30, edgecolorblack) plt.xlabel(Waiting Time (minutes)) plt.ylabel(Number of Customers) plt.title(Distribution of Customer Waiting Time) plt.savefig(wait_dist.png, dpi150) plt.show()这段 Python 代码读 CSV 画直方图。如果等待时间分布明显右偏说明有少数客户等了很久可以考虑增加窗口或调整队列策略。如果分布接近对称说明系统比较均衡。6.4 一个我踩过的坑浮点数比较模拟时间用 double 存储比较两个时间是否相等时不能用。比如判断“客户到达时间是否等于窗口空闲时间”应该用fabs(a - b) 1e-9。我当初没注意这个导致某些客户明明窗口空闲却被判定为需要排队平均等待时间凭空多了好几分钟。后来把所有时间比较都改成带容差的函数问题消失。这个坑在 C 语言里很常见写模拟程序时尤其要注意。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
