简介：这份数据结构期末作业资源面向计算机专业学生与C++初学者，围绕队列这一先进先出结构，实现带VIP优先级的银行排队模拟系统，帮助读者把课堂上的队列理论落到可运行的项目中。压缩包共9个文件，约1.03MB，以cpp源码、txt用户信息数据、cbp工程配置及exe可执行文件为主，另含编译中间产物与项目布局文件，Code::Blocks打开即可编译运行。资源已有3367人学习下载，说明其作为课程作业参考具有较高的实用认可度。读者可从中获得双队列优先级调度的完整实现思路、文件读取与解析用户到达信息的示例、STL queue容器的实际用法，以及从源码到可执行文件的完整工程组织方式，便于对照理解多队列设计与控制流程逻辑，也可作为同类排队模拟题目的改造基础。

1. 银行排队系统：一份能直接跑通的数据结构期末作业

期末周翻到这道题的人不少：模拟银行网点排队，要求用队列结构实现客户取号、叫号、窗口服务，还要统计平均等待时间。听起来像把课本上的链队列抄一遍就完事，真动手才发现坑全在细节里——客户到达是随机的、服务时长是随机的、多个窗口要并行推进、时间轴不能乱。这份作业资源把整条链路拆成了可编译的模块：事件驱动的主循环、链式队列的入队出队、随机数发生器、统计输出，还附了实验报告模板和测试用例。适合两类人：一是赶期末作业、需要一份结构清晰能改能跑的参考实现；二是刚学完队列、想找个比“打印一串数字”更像真实系统的练手项目。下面按“先看懂骨架、再动手复现、最后避开翻车点”的顺序拆。

2. 系统骨架拆解：事件驱动主循环与链式队列怎么配合

2.1 为什么用事件驱动而不是固定时间步

最直觉的写法是让时间一秒一秒走，每个 tick 检查有没有新客户、有没有窗口空闲。这种固定步长模拟写起来简单，但有两个硬伤：一是时间精度受步长限制，客户到达时刻被强行对齐到整秒，统计出来的平均等待时间会失真；二是空转浪费，夜里没客户的时段也要循环几万次。这份作业采用的是离散事件驱动：维护一个“下一个事件发生时刻”，每次直接跳到最近的事件点处理，事件只有两类——客户到达、窗口服务结束。时间轴是跳跃前进的，精度由随机数决定而不是步长，统计结果更接近真实排队论模型。

主循环的骨架大致是这样：初始化时生成第一个到达事件压入事件表，然后反复取出最早事件、推进当前时钟、分派处理、生成后续事件，直到事件表空或达到模拟时长上限。这里的事件表用优先队列（小顶堆）最合适，但很多课程还没讲到堆，所以资源里用了一个按时间排序的链表替代，插入时保持有序，取队头即最早事件。这个取舍要在报告里写清楚：链表插入是 O(n)，堆是 O(log n)，客户量小时差异可忽略，量大时是优化点。

2.2 链式队列的节点设计与入队出队

客户队列用带头结点的链队列，节点存三样东西：客户编号、到达时刻、所需服务时长。带头结点是为了让入队出队在空队列时不用特判，代码少一堆 if。核心操作就两个函数：

typedef struct QNode { int id; // 客户编号，取号顺序 double arriveTime; // 到达时刻，用于算等待 double serviceTime; // 所需服务时长，随机生成 struct QNode *next; } QNode; typedef struct { QNode *front; // 头指针，指向头结点 QNode *rear; // 尾指针，指向最后一个节点 int count; // 当前排队人数，统计用 } LinkQueue; // 入队：尾插，O(1) void EnQueue(LinkQueue *q, int id, double at, double st) { QNode *p = (QNode *)malloc(sizeof(QNode)); p->id = id; p->arriveTime = at; p->serviceTime = st; p->next = NULL; q->rear->next = p; // 挂到尾部 q->rear = p; // 更新尾指针 q->count++; } // 出队：删头结点后的第一个，O(1) int DeQueue(LinkQueue *q, QNode *out) { if (q->front == q->rear) return 0; // 空队列 QNode *p = q->front->next; *out = *p; // 拷出数据 q->front->next = p->next; if (q->rear == p) q->rear = q->front; // 删的是最后一个，尾指针回退 free(p); q->count--; return 1; }

逻辑说明：入队只动尾指针，出队只动头结点后的第一个节点，两个操作都是常数时间，这是链队列相对数组队列的优势——数组队列出队要整体前移或者用循环数组绕圈，前者 O(n) 后者要处理取模边界。参数上arriveTime和serviceTime用 double 而不是 int，是因为事件驱动的时间轴是连续值，用整型会把 0.3 秒的到达间隔抹成 0，多个客户挤在同一时刻，等待时间统计就乱了。count字段单独维护而不是每次遍历数，是为了在统计最大排队长度时 O(1) 取值。

提示：出队函数里“删的是最后一个节点时尾指针回退到头结点”这一行最容易漏。漏了之后队列空了但 rear 还指着已释放内存，下一次入队就写到野指针上，表现为随机崩溃或数据错乱，调试时极难定位。

2.3 多窗口并行的状态表

窗口不是队列，是一张固定大小的状态数组，每个元素记录该窗口是否忙碌、当前服务的客户编号、预计空闲时刻。叫号逻辑是：客户到达入队后，立刻扫描窗口表找空闲窗口，找到就出队一个客户分配过去，把窗口的预计空闲时刻设为“当前时刻 + 服务时长”，同时生成一个“该时刻服务结束”的事件压入事件表。服务结束事件处理时，把窗口置空闲，再尝试从队列取下一个客户。这里有个顺序问题：是先处理完所有到达再统一分配，还是每来一个就分配一次？资源里用的是后者，逻辑更贴近真实网点——客户进门就找空窗口，而不是攒一批再叫号。

窗口表用结构体数组即可，大小由命令行参数传入，默认 3 个。每个窗口的freeTime是判断忙碌的唯一依据：freeTime <= currentTime即空闲。这种设计把“窗口状态”和“事件表”解耦了，事件表只负责提醒“某时刻有窗口空出来”，具体哪个窗口空出来由事件携带的窗口下标指明，避免结束时再扫一遍数组找是谁。

3. 从零复现：编译、参数配置与统计输出

3.1 目录结构与编译命令

资源解压后是标准的 C 工程布局，源文件按模块拆开，头文件放 include 目录，测试脚本单独放。常见做法是用一个 Makefile 统一管理，避免手敲一长串 gcc 命令漏文件：

# 目录结构（解压后） bank_queue/ ├── src/ │ ├── main.c # 主循环与事件分派 │ ├── queue.c # 链队列实现 │ ├── event.c # 事件表（有序链表） │ └── stats.c # 统计与输出 ├── include/ │ ├── queue.h │ ├── event.h │ └── stats.h ├── tests/ │ └── run_cases.sh # 批量跑不同参数组合 └── Makefile

CC = gcc CFLAGS = -Wall -Wextra -O2 -Iinclude OBJ = src/main.o src/queue.o src/event.o src/stats.o bank_queue: $(OBJ) $(CC) $(CFLAGS) -o $@ $(OBJ) %.o: %.c $(CC) $(CFLAGS) -c $< -o $@ clean: rm -f $(OBJ) bank_queue

编译时-Wall -Wextra一定要开，链队列的野指针、未初始化变量这类问题编译器能提前警告一大半。-O2在模拟客户量上万时能明显缩短运行时间，但不影响统计结果，因为浮点运算顺序没变。如果课程要求提交单文件版本，把四个 .c 的内容按依赖顺序拼进一个文件、去掉重复 include 即可，注意static函数别重名。

3.2 随机数参数怎么设才不“玄学”

到达间隔和服务时长都用指数分布生成，这是排队论 M/M/c 模型的标准假设。C 标准库没有现成的指数分布函数，用逆变换法：-mean * log(1 - u)，其中 u 是 (0,1) 均匀随机数。这里有两个参数必须显式配置：平均到达间隔arrivalMean和平均服务时长serviceMean。它们的比值决定了系统负载率 ρ = arrivalMean / (serviceMean × 窗口数)，ρ 接近 1 时队列会剧烈波动，ρ 大于 1 时队列理论上无限增长，模拟时长内会看到排队人数一路飙升——这不是 bug，是模型本身的结论，报告里正好可以拿来做分析。

#include <stdlib.h> #include <math.h> // 生成均值为 mean 的指数分布随机数 double ExpRand(double mean) { double u = (double)rand() / (RAND_MAX + 1.0); // 落在 [0,1) if (u <= 0.0) u = 1e-9; // 防 log(0) return -mean * log(1.0 - u); } // 主函数里先播种，固定种子保证结果可复现 srand(20240601); // 换种子即换一组随机场景，报告里建议列 3 组

参数说明：RAND_MAX + 1.0而不是RAND_MAX，是为了让 u 严格小于 1，避免log(1-u)在 u 恰好等于 1 时返回负无穷。u <= 0的兜底是防某些平台上 rand 返回 0 导致 log(1) = 0、间隔为 0 的退化情况。种子固定这一点很关键：期末答辩时老师让你“再跑一遍”，结果必须一模一样，否则统计数字对不上会被追问。想展示随机性影响，就换种子跑三组，把三组的平均等待时间列成表对比，比空谈“随机波动”有说服力。

3.3 统计指标与输出格式

模拟结束后要输出的核心指标有四个：总客户数、平均等待时间、最大等待时间、最大队列长度。平均等待时间 = 所有客户（等待开始服务时刻 − 到达时刻）之和 / 客户数，注意只统计已经进入服务的客户，模拟结束时还滞留在队列里的客户要么单独计数、要么按“截至结束时刻的已等待时长”计入，两种口径要在报告里写明，不能混用。最大队列长度在每次入队后比较q->count更新即可。

// 统计结构体，随模拟过程增量更新 typedef struct { int served; // 已完成服务的客户数 double totalWait; // 累计等待时长 double maxWait; // 最大单人等待 int maxQueueLen; // 历史最大排队人数 } Stats; void OnCustomerServed(Stats *s, double wait) { s->served++; s->totalWait += wait; if (wait > s->maxWait) s->maxWait = wait; } void OnEnqueue(Stats *s, int curLen) { if (curLen > s->maxQueueLen) s->maxQueueLen = curLen; }

输出建议用固定宽度对齐，方便直接粘进实验报告表格：printf("%-12s %10.3f\n", "平均等待", avgWait);。小数位统一三位，避免不同指标精度不一致显得随意。如果要做多组参数对比，把输出改成 CSV 格式（逗号分隔），再用表格软件画折线图，比在终端里看一堆数字直观得多。

4. 避坑与排查：五个让作业翻车的细节

4.1 现象：平均等待时间算出来是负数

原因通常是等待时长用了“服务开始时刻 − 到达时刻”，但服务开始时刻在事件驱动里是窗口的freeTime，如果客户到达时窗口恰好空闲，freeTime可能小于arriveTime（窗口上次空闲的时刻早于客户到达），直接相减得负数。解决：分配窗口时取startTime = max(freeTime, arriveTime)，等待时长 =startTime − arriveTime，空闲窗口下等待自然为 0。

4.2 现象：模拟跑完客户总数对不上

事件表用有序链表时，插入函数如果没处理“新事件时间早于所有现有事件”的情况，会插到错误位置甚至丢事件，导致部分客户到达事件没被处理。排查方法：在事件分派处加一行计数，统计“到达事件处理次数”，与生成的客户总数比对，差值就是丢失的事件数。解决：插入时从表头开始找第一个时间大于新事件的节点，插在它前面，表头单独判断。

4.3 现象：换一组随机种子结果差异巨大，怀疑代码有 bug

先别急着改代码，算一下负载率 ρ。如果 ρ 在 0.9 以上，排队系统本身就处于临界区，平均等待时间对随机序列极其敏感，种子一换数字翻倍是正常现象。验证方法：把窗口数加 1 让 ρ 降到 0.6 左右，再换种子跑，如果结果稳定了，说明代码没问题，是参数选得太激进。报告里把这个对比写进去，反而是加分项。

4.4 现象：程序在模拟快结束时崩溃

多半是服务结束事件引用了已经出队的客户节点，或者窗口下标越界。事件结构里存窗口下标而不是客户指针，处理时通过下标访问窗口表，客户数据在出队时就拷到局部变量，不保留指针。另外检查事件表清空逻辑：模拟结束后要把剩余事件节点逐个 free，漏了不影响运行但内存检查工具会报泄漏，答辩时被问到不好看。

4.5 现象：统计的最大队列长度总是偏小

入队后更新maxQueueLen的时机如果放在“分配窗口之后”，此时客户可能已经出队，count已经减回去了，记录的是分配后的长度而不是峰值。正确顺序是：入队 → 更新峰值 → 尝试分配窗口。这个顺序错误很隐蔽，因为最终平均等待时间看起来正常，只有峰值指标失真，单看输出发现不了，要靠对照手算的小规模用例才能揪出来。

5. 进阶验证：用手算用例给模拟结果上保险

代码跑通不等于结果可信。我一般会构造一个完全确定性的小用例，把随机数关掉，手算出期望值再和程序输出比对。具体做法：临时把ExpRand替换成返回固定值，比如到达间隔恒为 2、服务时长恒为 3、窗口数 1，模拟 4 个客户。手算时间轴：客户 1 在 t=0 到达立即服务，t=3 结束；客户 2 在 t=2 到达排队，t=3 开始服务，等待 1；客户 3 在 t=4 到达，此时窗口忙到 t=6，等待 2；客户 4 在 t=6 到达，窗口刚好空，等待 0。平均等待 = (0+1+2+0)/4 = 0.75，最大等待 2，最大队列长度 2（t=4 时客户 2 在服务、客户 3 在排队，随后客户 4 到达前客户 2 已结束，峰值出现在 t=4 到 t=6 之间为 1？这里要仔细：t=4 客户 3 入队时队列长度 1，t=6 客户 4 到达时客户 3 刚开始服务、队列为空，所以峰值是 1）。把这个手算结果和程序输出逐项对照，任何一项对不上就说明事件顺序或统计口径有问题。

# 确定性验证：编译时定义宏关闭随机 gcc -DUSE_FIXED_INTERVAL -Iinclude src/*.c -o bank_queue_fixed -lm ./bank_queue_fixed --arrival 2 --service 3 --windows 1 --customers 4 # 期望输出：平均等待 0.750 最大等待 2.000 最大队列 1

这个习惯救过我很多次：随机模拟的输出“看起来合理”太容易了，只有确定性用例能把逻辑错误逼出来。从那以后我每次交这类模拟作业前，都强制先跑一遍手算用例，对上了再换随机参数出正式结果。希望这份拆解帮到你，作业能跑、报告能写、答辩被问参数时心里有底。

本文还有配套的精品资源，点击获取