简介这份数据结构期末作业资源面向计算机专业学生与C初学者围绕队列这一先进先出结构实现带VIP优先级的银行排队模拟系统帮助读者把课堂上的队列理论落到可运行的项目中。压缩包共9个文件、约1.03MB以cpp源码、txt数据文件、cbp工程配置及exe可执行文件为主源码承载队列操作与主控逻辑文本文件存放用户到达时间与VIP标识等信息工程文件便于在Code::Blocks中直接打开编译。已有3367人学习下载说明其作为课程作业参考具有较高认可度。读者可从中获得双队列优先级调度的完整实现思路、文件读取与解析的写法以及STL queue容器的实际用法并借助可执行文件对照运行结果理解入队、出队与循环判断如何协同模拟真实服务流程适合作为期末作业模板或队列练习的对照案例。1. 银行排队系统一份数据结构期末作业的完整交付思路银行排队系统这道题几乎每年都会出现在数据结构期末作业的选题清单里。表面上看它只是队列的增删改查但真正动手做过的同学都清楚难点根本不在队列本身而在于怎么把随机到达的客户、多个服务窗口、不同业务耗时这些现实因素塞进一个可计算、可验证的模型里。这份方案要解决的就是这个问题把银行排队系统从一句模糊的题目要求拆成需求定义、数据结构选型、事件调度、统计输出四个可交付的部分。适合正在做数据结构期末作业、课程设计的学生也适合需要一份离散事件模拟参考方案的从业者。下面按需求怎么立、结构怎么选、代码怎么写、结果怎么验的顺序展开。2. 需求与模型设计把排队翻译成可计算的问题2.1 从业务场景到抽象模型银行排队系统的核心业务链条很短客户到达、取号、等待、叫号、到窗口办理、离开。但要把这条链条变成程序必须先回答几个问题——客户什么时候来、来多少人、每个窗口办业务要多久、客户等多久会不耐烦。这些在真实银行里是统计规律在作业里就必须变成可配置的参数。我一般会把模型抽象成三个实体客户Customer、窗口Window、事件Event。客户携带到达时间、业务类型、所需服务时长三个属性窗口携带编号、空闲状态、当前服务的客户事件则是驱动整个模拟向前推进的引擎分为客户到达和服务完成两类。整个系统的运行逻辑就是不断从事件队列里取出最早发生的事件处理它再根据处理结果生成新的事件直到模拟时间结束。这个抽象的好处是它把排队这个连续过程离散化了。你不需要真的让程序等客户排队而是用事件的时间戳跳跃式推进几秒钟就能模拟完银行一整天的营业。这也是离散事件模拟Discrete Event Simulation的基本套路数据结构课设里用这一套既贴合题目又显得有章法。2.2 关键参数与假设的确定参数定得不合理跑出来的统计结果就没有说服力。通常的做法是给出一张参数表把每个参数的取值、单位和依据写清楚答辩时被问到你这个数怎么来的能直接指过去。参数符号建议取值说明模拟总时长T480 分钟一个营业日 8 小时客户到达间隔Δt均值 3 分钟的指数分布泊松到达过程的间隔服从指数分布窗口数量N35 个可配置用于对比实验单笔业务时长s均值 5 分钟的指数分布不同业务类型可设不同均值客户 patienceP20 分钟超过则离开可选功能这里有两个假设必须写进文档一是客户到达服从泊松过程所以到达间隔用指数分布生成二是服务时长也近似服从指数分布。如果作业要求里没提分布用均匀分布也能跑但指数分布更贴近真实排队场景答辩时是个加分点。生成指数分布随机数的公式是-mean * ln(U)其中 U 是 (0,1) 上的均匀随机数这个公式要能当场推给老师看。2.3 功能边界必做项与加分项一份合格的银行排队系统作业必做功能通常包括多窗口并行服务、客户按到达顺序排队先到先服务、统计平均等待时间、平均队列长度、窗口利用率。加分项则可以加VIP 客户优先队列、客户因等待过久离开带 patience 的排队、多队列 vs 单队列的对比、结果导出为 CSV 或图表。我的建议是必做项做扎实加分项挑一到两个做透。比如单队列多窗口和多队列单窗口的对比实验只需要改几行调度逻辑却能产出一组很有说服力的对比数据性价比最高。VIP 优先队列也不难把普通队列换成优先队列堆即可正好呼应数据结构课程里优先队列这个知识点老师看到会觉得你学以致用了。3. 数据结构选型队列、优先队列与事件表的取舍3.1 客户队列循环队列还是链队列客户排队最直接的实现就是队列。这里有个容易被忽略的细节用数组实现的循环队列容量必须预先设定一旦客户数超过容量就会溢出用链队列则动态增长不存在溢出问题但每个节点要额外存指针。在银行排队这个场景里队列长度本身是波动的高峰期可能排到几十人低谷期可能一个人都没有。我一般会选链队列理由是容量不确定、插入删除频繁、不需要随机访问。如果作业明确要求用循环队列实现那就老老实实用循环队列但要把容量设得足够大比如 200并在文档里说明容量依据历史峰值估计超出则触发扩容或拒绝新客户。链队列的核心操作只有两个入队尾插和出队头删时间复杂度都是 O(1)。下面是一个最小可用的链队列节点定义和入队出队实现语言用 C因为数据结构课设大多要求 C 或 C。typedef struct Customer { int id; // 客户编号 double arriveTime; // 到达时刻分钟 double serviceTime; // 所需服务时长分钟 int type; // 0普通, 1VIP struct Customer *next; } Customer; typedef struct { Customer *front; // 队头出队端 Customer *rear; // 队尾入队端 int size; // 当前队列长度 } LinkedQueue; // 入队尾插O(1) void enqueue(LinkedQueue *q, Customer *c) { c-next NULL; if (q-rear NULL) { // 空队列特判 q-front q-rear c; } else { q-rear-next c; q-rear c; } q-size; } // 出队头删返回被服务的客户O(1) Customer* dequeue(LinkedQueue *q) { if (q-front NULL) return NULL; // 队列为空 Customer *c q-front; q-front q-front-next; if (q-front NULL) q-rear NULL; // 出队后变空尾指针复位 q-size--; return c; }这段代码有两个地方值得在文档里点出来一是空队列时rear和front要同时置空否则下次入队会出错二是出队后如果队列变空rear必须复位为 NULL这是链队列最容易翻车的地方很多同学调试半天发现队列明明空了却还能出队就是这里漏了复位。3.2 事件表为什么用优先队列而不是普通队列事件表是整个模拟的黑匣子它决定了下一个该处理什么。客户到达事件和服务完成事件混在一起谁的时间戳早谁先处理这天然就是一个按时间排序的优先队列。如果图省事用普通队列按生成顺序处理那模拟就乱套了——可能先处理了 10 分钟后才发生的服务完成事件再回头处理 5 分钟前的到达事件时间倒流统计全错。所以事件表必须用优先队列最小堆按事件时间戳排序每次取堆顶就是最早发生的事件。C 语言里没有现成的优先队列需要自己写一个最小堆。核心操作是插入上浮和取最小下沉时间复杂度都是 O(log n)。如果作业允许用 C直接std::priority_queue配自定义比较器即可省事且不容易错。下面给出 C 版本的最小堆核心逻辑重点看push的上浮和pop的下沉。typedef struct { double time; // 事件发生时刻 int type; // 0到达, 1服务完成 int windowId; // 服务完成事件关联的窗口 } Event; typedef struct { Event heap[1000]; int size; } MinHeap; // 上浮新元素插入堆尾后向上调整 void push(MinHeap *h, Event e) { int i h-size; h-heap[i] e; while (i 0) { int parent (i - 1) / 2; if (h-heap[parent].time h-heap[i].time) break; Event tmp h-heap[parent]; h-heap[parent] h-heap[i]; h-heap[i] tmp; i parent; } } // 下沉取走堆顶后把堆尾元素放到堆顶向下调整 Event pop(MinHeap *h) { Event top h-heap[0]; h-heap[0] h-heap[--h-size]; int i 0; while (1) { int l 2 * i 1, r 2 * i 2, min i; if (l h-size h-heap[l].time h-heap[min].time) min l; if (r h-size h-heap[r].time h-heap[min].time) min r; if (min i) break; Event tmp h-heap[i]; h-heap[i] h-heap[min]; h-heap[min] tmp; i min; } return top; }参数说明time是事件发生的绝对时刻从营业开始算起的分钟数type区分事件种类windowId只在服务完成事件里有意义。堆的比较键只有一个——time这是保证事件按时间顺序处理的关键。如果两个事件时间相同处理顺序不影响正确性但为了结果可复现可以加一个次级比较键比如到达事件优先于完成事件。3.3 窗口管理数组足够不必上复杂结构窗口数量固定且不多通常 35 个用数组存窗口状态就够了每个窗口记录编号、是否空闲、当前服务的客户指针、累计服务人数和累计忙碌时长。查找空闲窗口就是遍历数组找第一个isBusy 0的O(N) 的复杂度在 N≤5 时完全可以接受没必要上什么平衡树。这里有个设计选择值得说清楚当有多个窗口空闲时选哪个最简单的策略是选编号最小的空闲窗口实现简单、结果确定。另一种是选累计服务人数最少的窗口负载更均衡但要多维护一个计数。作业里用前者就行文档里提一句后者作为改进方向显得你有思考。4. 核心调度实现事件驱动的主循环怎么写4.1 主循环的骨架与状态流转整个模拟的主循环可以用一段伪代码概括初始化事件表放入第一个到达事件→ 循环取最早事件 → 根据事件类型分派处理 → 处理过程中可能生成新事件 → 直到事件表为空或超过模拟时长。这个骨架是所有离散事件模拟的通用结构写清楚它后面的细节都是往里填。void simulate(double totalTime, int windowCount) { MinHeap events {0}; LinkedQueue queue {NULL, NULL, 0}; Window windows[10]; // 假设最多 10 个窗口 initWindows(windows, windowCount); // 放入第一个到达事件 Event first { .time genArrivalInterval(), .type 0, .windowId -1 }; push(events, first); double totalWait 0; // 累计等待时间 int servedCount 0; // 已服务人数 while (events.size 0) { Event e pop(events); if (e.time totalTime) break; // 超出营业时间停止 if (e.type 0) { // 客户到达 Customer *c createCustomer(e.time); enqueue(queue, c); // 生成下一个到达事件 Event next { .time e.time genArrivalInterval(), .type 0, .windowId -1 }; push(events, next); // 尝试立即服务 dispatch(windows, windowCount, queue, events, totalWait, servedCount); } else { // 服务完成 Window *w windows[e.windowId]; w-isBusy 0; w-busyTime w-currentServiceTime; free(w-currentCustomer); w-currentCustomer NULL; dispatch(windows, windowCount, queue, events, totalWait, servedCount); } } printStats(totalWait, servedCount, windows, windowCount); }这段代码的关键在dispatch函数它检查是否有空闲窗口且有排队客户如果有就出队一个客户、占用窗口、生成一个服务完成事件。到达事件和服务完成事件都要调用它因为两种情况下都可能触发新的服务。这个统一分派的设计避免了逻辑重复也让状态流转更清晰。4.2 到达事件与服务完成事件的联动到达事件的处理逻辑是创建客户、入队、生成下一个到达事件、尝试分派。服务完成事件的处理逻辑是释放窗口、累计忙碌时间、尝试分派。两者的共同点是最后都调用dispatch区别在于前者可能让队列变长后者可能让窗口变空闲。这里有个容易写错的地方生成下一个到达事件时时间戳是当前事件时间 随机间隔而不是上一个到达时间 间隔。如果写成后者一旦中间有事件处理延迟时间就会漂移。正确做法是始终以当前事件的时间戳为基准累加保证时间轴单调递增。dispatch的实现如下逻辑不复杂但要注意边界队列为空时直接返回没有空闲窗口时也直接返回。void dispatch(Window *windows, int n, LinkedQueue *q, MinHeap *events, double *totalWait, int *servedCount) { while (q-size 0) { int idle findIdleWindow(windows, n); if (idle -1) return; // 无空闲窗口客户继续等待 Customer *c dequeue(q); double wait currentTime - c-arriveTime; // 等待时长 *totalWait wait; (*servedCount); windows[idle].isBusy 1; windows[idle].currentCustomer c; windows[idle].currentServiceTime c-serviceTime; // 生成服务完成事件 Event done { .time currentTime c-serviceTime, .type 1, .windowId idle }; push(events, done); } }注意currentTime这个变量它应该等于当前正在处理的事件的时间戳。很多实现里忘了维护它导致等待时间算错。我的做法是在主循环里每取一个事件就更新currentTime e.time全局只此一处赋值避免多处修改导致不一致。4.3 统计指标的采集与输出模拟跑完后要输出至少四个指标平均等待时间、平均队列长度、窗口利用率、最大队列长度。平均等待时间 累计等待时间 / 已服务人数窗口利用率 窗口累计忙碌时长 / 模拟总时长平均队列长度需要在模拟过程中采样比如每处理一个事件就记录一次当前队列长度最后求平均。这里有个细节平均队列长度如果只在事件发生时采样会偏向于事件密集时刻的队列状态不够准确。更严谨的做法是按时间加权即记录每个队列长度持续的时间段最后用长度×持续时间求和除以总时长。作业里用简单采样平均也能交差但文档里把时间加权的方法写出来是个明显的加分项。输出格式建议用表格每个窗口一行最后一行汇总。如果作业允许把结果同时写一份 CSV 文件方便后续画图。下面是一个输出示例的结构具体数值因随机种子而异。窗口服务人数忙碌时长(分)利用率142380.579.3%238365.276.1%340372.877.7%合计1201118.577.7%平均等待时间 6.8 分钟平均队列长度 4.2 人最大队列长度 11 人。这组数据是否合理可以用利特尔法则Littles Law粗验平均队列长度 ≈ 到达率 × 平均等待时间。如果到达率是 1/3 人每分钟等待 6.8 分钟理论队列长度约 2.3 人和实测 4.2 有差距说明系统接近饱和这个分析写进文档会很有说服力。5. 避坑与排查这类作业最容易翻车的五个点5.1 时间倒流事件处理顺序错乱现象模拟结果里出现负的等待时间或者某个客户的服务完成时间早于到达时间。原因事件表没用优先队列或者用了优先队列但比较键写错比如按事件类型排序而不是按时间排序。解决检查堆的比较逻辑确保只按time排序在主循环里加一句断言assert(e.time currentTime)一旦时间倒流立刻暴露。5.2 队列假空链队列尾指针未复位现象队列明明已经出队到空了再次入队却崩溃或数据错乱。原因出队时只更新了front忘了在队列变空时把rear也置为 NULL。解决出队函数里加判断if (q-front NULL) q-rear NULL;这是链队列的标配操作漏了必翻车。5.3 内存泄漏客户节点只出队不释放现象模拟时间一长程序内存占用持续上涨或者跑大批量数据时崩溃。原因出队后的客户节点没有free服务完成事件里也没释放。解决明确所有权——客户节点由队列持有出队后所有权转移给窗口窗口服务完成后负责释放。在dispatch和完成事件处理里各加一次free并用 valgrind 跑一遍确认无泄漏。5.4 统计失真等待时间基准取错现象平均等待时间明显偏大或偏小和手工推算对不上。原因计算等待时间时用了错误的基准时间比如用了当前模拟时间而不是客户到达时间或者currentTime没有随事件更新。解决全局只维护一个currentTime在主循环取事件后立即更新等待时间严格用currentTime - c-arriveTime并在小规模数据比如手动构造 3 个客户上手工验算一遍。5.5 随机数不可复现每次跑结果都不一样现象答辩时老师让你再跑一次结果和刚才展示的不一样很尴尬。原因用了rand()但没设种子或者设了time(NULL)导致每次种子不同。解决在程序入口固定种子srand(42)并在文档里注明固定种子保证结果可复现如果需要多组实验用循环改变种子并记录每组种子值。这个习惯看似小答辩时能救场。6. 验收与答辩怎么证明这套系统是对的验收这件事很多同学的理解是程序能跑就行但老师要看的是你怎么知道它跑对了。我的做法是准备三层验证从下往上依次是单元验证、手工对拍、统计合理性检验。第一层单元验证。对队列和堆单独写测试入队 5 个再出队 5 个检查顺序是否先进先出往堆里乱序插入 10 个事件逐个弹出检查是否按时间升序。这层测试不需要模拟主循环几行代码就能写完但能挡住大部分底层 bug。第二层手工对拍。构造一个极小场景2 个窗口、3 个客户到达时间分别是 0、1、2 分钟服务时长都是 5 分钟。手工推演每个客户的等待时间和服务完成时间和程序输出逐项对比。下面这张表就是手工推演的结果答辩时直接展示比任何口头解释都有力。客户到达窗口开始服务等待完成1010052121063215310第三层统计合理性。跑 1000 次模拟取平均检查平均等待时间是否随窗口数增加而下降、随到达率上升而上升。如果趋势反了说明调度逻辑有问题。还可以用利特尔法则做粗验偏差在 20% 以内算合理偏差过大就要回头查统计代码。答辩时还有一个技巧主动说出系统的局限。比如当前模型假设服务时长服从指数分布实际业务中可能有固定时长的业务后续可以把服务时长改成混合分布。主动暴露局限比被老师问出来强得多而且显得你对模型的理解是完整的不是照抄模板。我带项目时有个习惯每次交付前都强制走一遍小数据手工对拍哪怕代码看起来再简单。这个习惯救过我很多次——有一次堆的比较逻辑写反了大数据跑出来只是数字难看看不出错正是 3 个客户的手工对拍让我当场发现了问题。希望这套思路能帮你把这份作业交得踏实也能在答辩时说得清楚。本文还有配套的精品资源点击获取