简介这是一份以“电梯模拟”为题的数据结构课程设计/毕业设计完整报告面向计算机专业学生以及正在准备课程设计、毕业设计或答辩的读者。文档以某五层教学楼电梯系统为实际场景围绕乘客等待队列、内选目标层、电梯运行状态等核心问题展示如何选用链队列与乘客栈等数据结构完成系统建模与算法设计。内容涵盖课程设计任务书、系统分析、概要设计、详细设计、运行与测试、总结与心得等完整章节并包含0.1秒模拟时钟下的状态变化时序、C/C实现要点、调试记录与参考文献便于读者对照学习完整的设计与编码思路。压缩包内共1个DOC文档约523KB结构清晰可直接查阅或作为同类课程设计的参考模板。目前已有139人学习对想巩固数据结构知识并完成电梯模拟类题目的学生具有实际参考价值。1. 数据结构电梯模拟到底在做什么——一个课设题目背后的真实需求拿到“数据结构电梯模拟”这个课设题目时大多数人第一反应是“这不就是控制电梯上下跑吗”。真正做进代码里你才会发现电梯本身只是一堆 if 判断难点全在“乘客请求来了你该用哪种数据结构存它又按什么顺序处理它”。这个题目能训练的是队列、优先队列、链表这些结构在真实调度中的取舍也是面试里高频考到“如何用队列模拟排队”的实战版。这个方案适合正在做课程设计、准备期末大作业的人也适合想补数据结构实践但不想刷纯算法的同学。你不需要写图形界面也能把核心调度讲清楚用控制台加日志就够了如果你愿意后面加个简易可视化就会很加分。接下来我按自己做过的方式从数据结构选型开始一步步拆。2. 电梯模拟里的数据结构怎么选队列、堆、还是双向链表2.1 请求队列为什么 FIFO 队列不能直接用于电梯调度很多同学一看到“电梯模拟”就说用队列因为乘客在外面上电梯肯定先来先服务。但真实电梯不是这样工作的一个乘客在 1 楼按上行要去 10 楼另一个乘客在 5 楼按上行要去 8 楼电梯会先停在 5 楼接人再去 8 楼而不是按到达顺序先跑到 10 楼再折返。所以 FIFO 队列只适合表示“同一时间、同一方向上的等待池”不能作为全局调度结构。我一般会在设计里把请求分两层存外层是所有等待中的乘客列表内层是电梯当前正在响应的目标楼层集合。外层可以用std::queue但更推荐std::deque因为你需要从头部取走已响应的请求、从尾部追加新请求。内层是电梯真正要停靠的楼层这个集合必须支持快速判断“当前楼层是否在停靠集合里”所以用数组或std::set比队列更合适。#include deque #include vector struct PassengerRequest { int fromFloor; // 起始楼层 int toFloor; // 目标楼层 bool isTaken; // 是否已经被某部电梯响应 }; // 所有待响应的乘客请求按产生顺序排 std::dequePassengerRequest allRequests; // 每部电梯各自要停的楼层用 bool 数组idx 是楼层号 std::vectorbool targetFloors(20, false);逻辑很简单allRequests负责保存还没被分配走的人targetFloors负责记录某部电梯接下来要去的所有楼层。为什么要用std::deque而不是std::queue因为课设里你经常需要打印当前等待列表、人工移除某个异常请求deque支持随机访问和从中间删除调试起来舒服得多。std::queue只能头出尾进一旦你想“把这个人换成另一部电梯响应”就得重写队列。2.2 优先队列与电梯调度看起来合理用起来翻车如果学过《数据结构与算法分析》或王道考研数据结构你一定知道优先队列适合“每次取最大/最小”。放到电梯里有人会想把请求目标楼层按离当前楼层最近优先级每次取最近的目标去不就行了这就是最常见的翻车点。电梯正在上行时你取了一个“最近”的请求结果它在下方楼层电梯就得立刻掉头下一 tick 又算出一个更近的在上方再掉头。最后电梯在中间来回抖乘客永远等不来。优先队列并不是不能用而是只能用在“同一个方向”的局部排序里。也就是说电梯上行时它应当按目标楼层从小到大处理下行时按从大到小。这个排序你可以每次重新对targetFloors做一次排序也可以用两个std::priority_queue一个存上行目标一个存下行目标。但注意 C 的priority_queue默认是大顶堆下行想要从小到大取就需要自定义比较器课设代码会变得绕。我更推荐的做法是不用优先队列直接用std::setint存目标楼层因为set天然有序。电梯上行时取*begin()最小楼层下行时取*rbegin()最大楼层取完删掉复杂度 O(log n)写起来比优先队列直观得多答辩也好解释。#include set class Elevator { public: int currentFloor; // 当前楼层 int direction; // 1 上行-1 下行0 待机 std::setint targets; // 需要停靠的楼层自动排序 // 添加一个目标楼层 void addTarget(int floor) { targets.insert(floor); } // 判断当前楼层是否应该开门 bool shouldStopHere() { return targets.count(currentFloor) 0; } };这段代码里set就是核心数据结构。上行的停靠序列天然是升序下行的降序则用反向迭代器取。为什么不用vector加sort因为电梯运行过程中会不断新增目标如果每来一个请求就重新sort一次复杂度是 O(n log n)而set每次插入是 O(log n)在请求频繁时差距明显。虽然课设楼层只有 20 层性能不是瓶颈但用set能让你的代码逻辑更接近“调度原理”。2.3 结构体设计乘客、电梯、楼层的三维关系数据结构不只是“队列”“堆”还包括整个程序里对象之间的关联。我习惯用三个结构PassengerRequest描述一次乘梯需求Elevator描述状态Building描述楼栋里的电梯组和请求池。楼层本身不需要专门建结构体用一个 int 表示即可否则会陷入“为了建对象而建对象”的设计。struct Stat { int totalPassengers; // 总服务人数 int totalWaitingTime; // 所有人等待时间之和 int maxWaitingTime; // 最长等待时间 }; struct Building { int floorCount; // 总楼层 std::vectorElevator elevators; // 电梯组 std::dequePassengerRequest waitQueue; // 还没被分配的乘客 Stat stats; };Building把电梯和请求池绑在一起所有调度函数都操作Building。waitQueue里存的是还“没被任何电梯响应”的乘客一旦某部电梯决定接他就把这个请求从waitQueue移到那部电梯的targets里。这里的关键边界是一个乘客被分配后不能同时出现在两部电梯的停靠集合里否则会出现 5.2 里的“幽灵停靠”。3. 调度算法拆解用 SCAN 和 LOOK 把电梯跑起来3.1 经典算法对比SCAN 电梯扫描与 LOOK 算法的差别电梯调度最经典的算法是 SCAN也叫电梯扫描算法。它模拟机械鼠标的扫描方式电梯先向上走遇到最高请求层后折返向下再遇到最低请求层后折返永远从一端扫到另一端。LOOK 是 SCAN 的改进电梯不需要一直走到物理最顶层/最底层只要前方没有请求就提前掉头。LOOK 比 SCAN 平均等待时间更短因为减少了无用行程。课设推荐直接用 LOOK理由有二一是代码少二是解释“为什么提前掉头”能展示你对调度的理解。SCAN 适合在楼里有人会“按顶楼但不坐”这种极端场景但课设随机生成乘客时LOOK 通常表现更好。下面表格是两者的关键区别算法折返条件适用场景平均等待时间SCAN到达物理最高/最低楼层请求分布均匀、满载场景较长LOOK同方向前方无请求请求稀疏或中等密度较短FCFS不折返按请求顺序只有一个请求时抖动严重3.2 单电梯 LOOK 调度的最小可跑代码我们把上面的Elevator类加上一个step()函数每调用一次表示电梯运行一个时间单位。这是整个模拟器的核心值得抄下来跑一遍。// 每 tick 调用一次模拟电梯运行一个单位时间 void stepElevator(Elevator e) { // 如果当前楼层需要停靠开门并移除目标 if (e.targets.count(e.currentFloor) 0) { e.targets.erase(e.currentFloor); e.doorTimer e.openTime; // 开门后要停留 openTime 个 tick } // 开门状态下不走动 if (e.doorTimer 0) { e.doorTimer--; return; } // 方向待机时如果有目标就选择一个方向启动 if (e.direction 0) { if (!e.targets.empty()) { e.direction (*e.targets.begin() e.currentFloor) ? 1 : -1; } } else if (e.direction 1) { // 上行时如果更高层没目标了就掉头向下 auto it e.targets.upper_bound(e.currentFloor); if (it e.targets.end()) { e.direction -1; } } else if (e.direction -1) { // 下行时如果更低层没目标了就掉头向上 auto it e.targets.lower_bound(e.currentFloor); if (it e.targets.begin()) { e.direction 1; } } // 按当前方向移动一层 e.currentFloor e.direction; }这段代码有几个细节必须注意。第一开门判断放在移动之前意思是电梯到达目标楼层的那一个 tick 就直接开门不再移动。第二doorTimer用于模拟开门到关门的时间在这段时间里电梯原地不动其他请求照常积累。第三方向切换用upper_bound和lower_bound判断同方向是否还有目标上行时用upper_bound找“大于当前楼层”的第一层找不到说明上面没人要停掉头。下行时用lower_bound找“大于等于当前楼层”的迭代器如果等于begin()说明当前楼层以下没有目标。参数都是可以调的openTime一般设 3~5 个 tick代表开门到关门moveTime隐含在每次step中每个 tick 移动一层。如果你要让电梯一秒钟移动一层就把主循环的sleep(1000)调成对应毫秒数。3.3 多电梯怎么分派请求就近分配还是动态接管多电梯时不能每部电梯都维护同一份waitQueue然后各跑各的那样一个请求会被多部电梯响应。常见做法是当新乘客出现时遍历所有电梯选一个“最合适”的接单。最合适的标准通常是距离乘客所在楼层最近且运动方向能和乘客想去的方向匹配。// 给新请求选择一个电梯返回电梯下标 int selectElevator(Building b, const PassengerRequest req) { int bestIdx -1; int bestScore 1e9; for (int i 0; i b.elevators.size(); i) { Elevator e b.elevators[i]; int dist abs(e.currentFloor - req.fromFloor); // 电梯顺路接人的分数较低不顺路但要绕过去的分数高 int score dist; // 如果电梯正在往下而乘客想去更高层分数加惩罚 if (e.direction 0 req.toFloor req.fromFloor) score 50; if (e.direction 0 req.toFloor req.fromFloor) score 50; // 电梯空闲时优先 if (e.direction 0) score - 10; if (score bestScore) { bestScore score; bestIdx i; } } if (bestIdx 0) { b.elevators[bestIdx].addTarget(req.fromFloor); b.elevators[bestIdx].addTarget(req.toFloor); } return bestIdx; }这段“抢单”逻辑是课设里常见做法但分数阈值是玄学score 50和score - 10都是我一拍脑袋定的。你完全可以改成“电梯方向完全相同优先”“空闲优先”等更简单的规则。核心是保证每个请求只被分配给一部电梯并且把fromFloor和toFloor都放进那部电梯的目标集合。分配后还要把 request 标记为已响应防止主循环再分配一次。4. 从请求到运行事件驱动的电梯模拟实现要点4.1 时间步进tick模型 vs 事件驱动为什么课设选 tick 更省事电梯模拟有两种主循环风格。第一种是时间步进设定一个总时间比如 600 秒每秒叫一次stepElevator并顺带随机生成乘客。第二种是事件驱动用一个优先队列存未来事件比如“第 10 秒 3 楼有乘客按上行”到时间才触发。事件驱动更精确但代码复杂而且你需要手动管理事件间的时间跳跃。我做过几次课设结论是如果只是为了交作业用 tick 模型足够。tick 模型直观调试时打印每一秒的状态很方便万一逻辑错了直接在控制台看电梯怎么走。事件驱动的优势是当请求极其稀疏时可以跳过很多无意义循环但课设场景通常请求密集tick 模型每轮循环也就是几十次判断性能完全没问题。const int TOTAL_TIME 600; // 模拟 600 秒 const int REQUEST_INTERVAL 3; // 每 3 秒尝试生成请求 int currentTime 0; while (currentTime TOTAL_TIME) { // 按固定间隔生成新乘客请求 if (currentTime % REQUEST_INTERVAL 0) { generateRandomPassenger(building); } // 让每部电梯走一步 for (Elevator e : building.elevators) { stepElevator(e); } // 记录统计和日志 recordLog(building, currentTime); currentTime; }这段主循环已经能跑通一个最小模拟。generateRandomPassenger会在随机楼层产生一个乘客并把他加入waitQueue然后调用selectElevator分配。注意顺序先生成请求再让电梯移动这样本 tick 产生的请求不会立刻被当前 tick 响应更接近真实。4.2 乘客生成随机参数怎么调才能不把电梯打爆如果每个 tick 都在每个楼层生成乘客电梯很快会忙不过来模拟结果全是超时。我一般控制生成概率只在小区间内产生且每个楼层每秒最多一个乘客。下面的生成函数可以照抄参数按你的电梯数量调整。void generateRandomPassenger(Building b) { // 随机选一个起始楼层避开顶层和底层避免极端情况 int from rand() % (b.floorCount - 2) 2; int to rand() % (b.floorCount - 2) 2; if (to from) to (from b.floorCount - 1) ? from - 1 : from 1; PassengerRequest req {from, to, false}; // 30% 概率生成请求约每 3 秒产生一个左右 if (rand() % 100 30) { selectElevator(b, req); } }这个函数看起来简单坑在目的楼层生成直接用rand() % floorCount很容易生成和起始楼层一样的值导致电梯空跑一趟。上面代码先随机生成 from 和 to如果一样就强制改正。参数rand() % 100 30是生成概率调成 10 则请求稀疏调成 80 则电梯永远忙碌。做实验时建议固定几个档位低负载 10%中负载 30%高负载 70%分别记录平均等待时间这是实验报告里很漂亮的一组对比数据。4.3 记录状态与统计为了交实验报告你得留这些日志很多课设要求写《数据结构实验报告》里面必须有“运行结果分析”。如果你没有日志数据只能写“电梯正常运行”答辩大概率被追问。我一般会给每部电梯写一个状态日志文件包括时间、楼层、方向、目标集合大小、当前等待乘客数。统计量至少三个平均等待时间、最大等待时间、电梯利用率。void recordLog(const Building b, int time) { // 控制台或文件每 20 秒打印一次状态 if (time % 20 ! 0) return; printf([%4d s] , time); for (const Elevator e : b.elevators) { printf(E%d at %2d dir%d targets%zu | , e - b.elevators[0], e.currentFloor, e.direction, e.targets.size()); } printf(waiting%zu\n, b.waitQueue.size()); }这个日志让你在答辩时直接贴一段运行结果不用凭空口播。e - b.elevators[0]是取电梯下标的土办法也可以用循环索引。统计平均等待时间时需要在乘客从生成到被服务完成之间累计等待 tick 数建议在每个请求里加一个waitTime字段每 tick 末尾对所有未完成请求的waitTime加 1。5. 电梯模拟的 5 个常见坑死锁、边界和玄学数据5.1 电梯在第一层不动请求来了也一直待机现象模拟开始后明明有乘客在 3 楼按电梯但电梯显示 direction0 且 currentFloor1一直不动。原因selectElevator在分配请求时只把toFloor加进了目标集合忘了加fromFloor或者方向判断逻辑在 direction0 时没有启动项。解决把targets.insert(req.fromFloor)和insert(req.toFloor)都写上并且在stepElevator开头检查if (targets.empty()) return;确保待机时不会瞎动。5.2 多电梯抢同一批乘客出现“幽灵停靠”现象A 电梯已经到 5 楼开门接人B 电梯也跑到 5 楼开门但没人进出。原因随机生成请求时没有标记请求已被响应第二次生成时又把同一个逻辑执行了一遍或者selectElevator被调用多次。解决给每个请求加bool isTaken生成后立刻分配分配后从waitQueue移除并设置isTaken true。如果有两部电梯同时被selectElevator选中那说明你的遍历里没有break或没有排除已分配请求。5.3 开门时间导致的时间统计比真实值偏少现象理论上从 1 楼到 10 楼需要 9 秒但日志显示只用了 6 秒。原因你在stepElevator里把开门过程当成瞬间事件乘客一进去就关门走人而真实的doorTimer没有生效。解决把doorTimer openTime放在开门判断里并且在开门状态下直接return电梯那一 tick 不移动。调参时先固定 openTime0跑通后再改成 3 或 5看统计变化。5.4 随机种子不同实验结果完全不一样复现不了现象上午跑一次平均等待 12 秒下午跑一次变成 30 秒答辩时被老师质疑“算法失效”。原因没有固定随机种子或每次运行都调用了srand(time(NULL))。解决在main()开头写srand(42)用一个固定整数。这样每次运行结果完全一致你可以在报告里写“采用固定随机种子保证实验可复现”。如果你想让数据更漂亮可以多试几个种子选一个中等偏上的结果放报告但代码里要保持种子的注释说明。5.5 硬套“栈”结构电梯下行是后进先出所以我用栈模拟现象有人报告里写“电梯下行时乘客后进入的先出来符合栈特性”然后真用std::stack存乘客。原因混淆了“现象”和“结构”。电梯轿厢里的乘客进出顺序受按钮顺序和楼层影响栈只适合记录调试用的进出序列不适合作为调度的主结构。解决栈可以用于审计日志例如记录哪个乘客最后进去、第一个出来但调度主逻辑只用set和deque。答辩时你可以主动说“我调研过用栈但栈的受限访问方式无法高效处理随机楼层请求所以最终选择了有序集合”这反而是加分的分析。6. 最后一步可视化、日志验证与答辩话术6.1 用 20 行代码打印一个简单的 ASCII 电梯状态答辩时如果只放黑底白字的 printf老师容易走神。我一般会在控制台画一个简单的竖向楼层图每 0.5 秒刷新一次能看到电梯上下移动。代码很短void drawBuilding(const Building b) { // 从顶楼往下打印 for (int floor b.floorCount; floor 1; --floor) { printf(%2d |, floor); for (const Elevator e : b.elevators) { if (e.currentFloor floor) { printf( [E] ); } else { printf( ); } } printf(|\n); } printf( ); for (const Elevator e : b.elevators) printf(); printf(\n); }这个函数用floorCount从高到低打印每一层电梯所在楼层显示[E]。在main循环里每操作一次就调用system(clear)或system(cls)就能看到动态效果。注意 Windows 的system(cls)和 Linux 的clear不同写代码时可以用宏隔离。这段可视化不改变任何调度逻辑但能让你的课设看起来“像一个完整项目”。6.2 用日志文件验证调度算法是否“正确”可视化只能看个大概真正验证算法靠的是固定场景测试。我在提交前会手动构造一批请求不走随机生成比如两台电梯、10 层楼顺序产生“1 楼上要去 8 楼”“5 楼下要去 2 楼”然后打印每一秒的电梯位置和目标集合确认行为符合预期。这种单测文件比随机日志更有说服力。以下是一个最简单的验证用例表你可以直接抄进实验报告用例电梯数楼层数请求序列期望结果1152楼→4楼3楼→1楼先到2接人再到3再接人下行时先到4再下到122101楼→9楼8楼→2楼两电梯分别响应无幽灵停靠3120连续高层请求电梯不抖动每层停靠一次这些用例里“期望结果”是我根据 SELECT 算法写出来的。如果你发现实际结果和表格不一致说明逻辑中有方向判断问题比随机跑一百次再猜原因高效得多。6.3 答辩时怎么把数据结构讲出深度答辩时很多同学喜欢讲“我做了几层、电梯怎么走”老师其实更关心你的数据结构意识。我自己的经验是准备三句话第一句“请求池用了deque因为需要头部取走和尾部追加”第二句“电梯的目标楼层用了set因为上行/下行都要有序访问且频繁插入删除”第三句“多电梯分配是一个贪心选择问题我用了最近可用电梯策略复杂度 O(N)”。这三句话一出老师就知道你确实理解这个题目的数据结构核心。最后提一下我踩过的坑当初我把电梯目标集合写成vector每次到达就删掉第一个元素结果发现上行时目标顺序乱了因为 vector 头删会让所有元素前移。后来换成set才顺利跑完整个模拟。如果你也在做这个课设不妨先按上面第 2 章的结构写一版最小系统再逐步加调度和统计。希望帮到你。本文还有配套的精品资源点击获取
