简介本资源是一份面向计算机专业本科生的数据结构课程设计报告聚焦电梯模拟系统开发旨在通过真实项目实践深化对线性表、栈、队列等核心数据结构的理解与应用。报告完整覆盖系统分析、概要设计、详细实现及测试运行全过程含7章内容从需求建模、状态机设计Opening/Waiting/Closing等7种电梯状态到链队列管理楼层候梯乘客、五层乘客栈调度、时间驱动仿真机制0.1秒精度等关键技术实现代码量超300行推荐使用C/C编写并附规范注释。资源为单个Word文档.doc大小523KB排版规范、目录清晰含参考文献与答辩记录适合作为课程设计范本或毕业设计参考。目前已有138人学习下载可直接用于教学复现、算法验证与数据结构综合能力训练。1. 为什么用链表和队列写电梯模拟比直接套GUI框架更能拿高分“毕业设计-数据结构电梯模拟.doc”——这个标题不是在说“做个带按钮的电梯动画”而是在考你能不能把线性表、栈、队列、链表这些抽象结构真正焊进一个有真实调度逻辑的系统里。我带过三届毕设每年都有学生用 PyGame 或 JavaFX 画个会动的轿厢配个“上行/下行”标签结果答辩被问一句“你用的什么数据结构管理候梯队列插入删除时间复杂度多少如果100人同时在3楼按上行键你的队列怎么保证FIFO不乱序”当场卡壳。真正的得分点从来不在UI多炫而在调度策略是否可验证、状态迁移是否可追溯、数据结构选型是否有依据。这篇笔记就带你从零手写一个纯逻辑驱动、无图形界面、但能完整复现电梯运行时序与资源竞争的模拟器——它能跑在命令行里能导出每秒状态日志能对接严蔚敏《数据结构C语言版》第3章队列、第2章链表的课后习题逻辑也能直接作为王道408数据结构大题的代码原型。适合计算机、软件工程、物联网、甚至机械类偏软方向的同学不拼硬件、不堆库、只靠结构设计说话。2. 用双向循环链表建楼层请求池为什么不用数组而选链表电梯调度的核心矛盾之一是请求动态生成、位置不确定、需频繁插入/删除。比如5楼有人按上行7楼有人按下行12楼又按上行——这些请求不是按楼层顺序来的也不能预分配固定大小数组。用数组硬存要么浪费空间预留100层但实际只用20层要么频繁reallocC语言里极不优雅而链表天然支持O(1)插入删除且能按需增长。但普通单链表查前驱节点要O(n)而电梯需要“当前楼层→向上最近请求→向下最近请求”三向扫描所以必须用双向循环链表。2.1 链表节点定义与初始化逻辑// 楼层请求节点记录请求来源楼层、方向、时间戳用于FCFS排序 typedef struct FloorRequest { int floor; // 请求楼层1~N int direction; // 1up, -1down, 0both停靠但不响应方向 unsigned long timestamp; // 系统毫秒级时间戳用于同层多请求排序 struct FloorRequest *next; struct FloorRequest *prev; } FloorRequest; // 初始化空的双向循环链表哨兵节点 FloorRequest* init_request_list() { FloorRequest *head (FloorRequest*)malloc(sizeof(FloorRequest)); if (!head) return NULL; head-floor 0; head-direction 0; head-timestamp 0; head-next head; head-prev head; return head; }提示这里用哨兵节点sentinel node而非NULL指针避免边界判断爆炸。head-next永远指向第一个有效请求head-prev永远指向最后一个——循环特性让“找最高/最低请求楼层”变成O(1)遍历而不是每次遍历全链表。2.2 插入请求按楼层时间戳双关键字排序电梯不是先到先服务FCFS那么简单。同一楼层多个请求必须按时间戳排序不同楼层则按楼层号升序上行或降序下行插入。我们封装一个通用插入函数// 向链表中插入请求按direction分组同组内按floor排序同floor按timestamp升序 void insert_request(FloorRequest *head, int floor, int direction) { FloorRequest *new_node (FloorRequest*)malloc(sizeof(FloorRequest)); if (!new_node) return; new_node-floor floor; new_node-direction direction; new_node-timestamp get_current_ms(); // 自定义函数返回毫秒时间戳 // 找插入位置遍历链表找到第一个floor new_node-floor的节点上行方向 // 注意此处简化为统一按floor升序插入实际调度策略会在第4章细化 FloorRequest *p head-next; while (p ! head p-floor floor) { p p-next; } // 插入到p之前即升序位置 new_node-next p; new_node-prev p-prev; p-prev-next new_node; p-prev new_node; }参数说明direction不参与排序仅标记该请求的意图后续调度算法会根据当前电梯运动方向筛选有效请求get_current_ms()必须用clock_gettime(CLOCK_MONOTONIC, ...)或GetTickCount64()实现严禁用time(NULL)——秒级精度无法区分同一秒内多个请求插入后链表仍保持循环结构head-next和head-prev始终有效。2.3 删除已响应请求O(1)定位 O(1)摘除当电梯到达某楼层并响应请求后必须从链表中移除对应节点。关键在于不能遍历查找O(n)太慢而应让电梯控制器持有指向该节点的指针。我们在电梯状态结构体中加一个current_target字段typedef struct Elevator { int current_floor; // 当前所在楼层 int target_floor; // 下一目标楼层由调度器设定 int direction; // 当前运行方向1up, -1down, 0stop FloorRequest *current_target_node; // 指向链表中该请求节点用于O(1)删除 // ... 其他字段 } Elevator; // 响应完当前请求后调用 void remove_current_target(Elevator *elev, FloorRequest *head) { if (!elev-current_target_node || elev-current_target_node head) return; // 直接摘除修改前后指针 elev-current_target_node-prev-next elev-current_target_node-next; elev-current_target_node-next-prev elev-current_target_node-prev; free(elev-current_target_node); elev-current_target_node NULL; }为什么必须存指针因为调度器在选目标楼层时已经遍历过链表并记住了匹配节点地址。若此时再用floor值去链表里搜索等于重复O(n)操作——毕设答辩时老师会立刻追问“你这里两次遍历时间复杂度是不是O(n²有没有优化空间” 存指针是标准解法也是严蔚敏教材链表应用题的隐含要求。3. 用环形缓冲区模拟乘客队列为什么不用标准queue而手写电梯轿厢容量有限比如8人乘客进入/离开是典型的生产者-消费者模型楼层请求是生产者电梯运载是消费者。标准库queue或deque虽可用但毕设要求你展示对底层结构的理解。环形缓冲区Circular Buffer用数组实现空间连续、缓存友好、无内存碎片且能清晰体现“满/空”判断逻辑——这正是数据结构实验报告里要求画图分析的考点。3.1 环形缓冲区结构定义与边界判断#define MAX_PASSENGERS 8 typedef struct PassengerQueue { int passengers[MAX_PASSENGERS]; // 存储乘客目标楼层1~N int front; // 队首索引指向下一个将被取出的元素 int rear; // 队尾索引指向下一个将被插入的位置 int size; // 当前人数避免模运算误差 } PassengerQueue; PassengerQueue* init_passenger_queue() { PassengerQueue *q (PassengerQueue*)malloc(sizeof(PassengerQueue)); if (!q) return NULL; q-front 0; q-rear 0; q-size 0; return q; }注意这里用size字段而非(rear - front MAX_PASSENGERS) % MAX_PASSENGERS判断容量是因为模运算在负数时行为不一致C语言中-1%8-1容易引发玄学bug。size字段让“满/空”判断变得绝对可靠size 0→ 空size MAX_PASSENGERS→ 满size增减直接控制front/rear移动逻辑干净。3.2 入队与出队严格遵循FIFO且带容量保护// 入队乘客在某楼层进入轿厢目标楼层为dest_floor int enqueue_passenger(PassengerQueue *q, int dest_floor) { if (q-size MAX_PASSENGERS) { return -1; // 满拒绝进入 } q-passengers[q-rear] dest_floor; q-rear (q-rear 1) % MAX_PASSENGERS; q-size; return 0; } // 出队电梯到达某楼层所有目标为此楼层的乘客离开 int dequeue_passengers(PassengerQueue *q, int target_floor, int *count) { *count 0; // 注意环形队列不支持随机删除只能按FIFO顺序检查 // 实际中应维护一个独立的“待下客”列表但毕设简化为只允许在target_floor下客 // 所以这里做一次扫描式清理O(n)因MAX_PASSENGERS仅8可接受 int new_front q-front; for (int i 0; i q-size; i) { int idx (q-front i) % MAX_PASSENGERS; if (q-passengers[idx] target_floor) { // 将该位置标记为无效用0表示空位并计数 q-passengers[idx] 0; (*count); } } // 重构队列把非0元素前移保持FIFO顺序 int write_idx q-front; for (int i 0; i q-size; i) { int read_idx (q-front i) % MAX_PASSENGERS; if (q-passengers[read_idx] ! 0) { if (read_idx ! write_idx) { q-passengers[write_idx] q-passengers[read_idx]; q-passengers[read_idx] 0; } write_idx (write_idx 1) % MAX_PASSENGERS; } } q-size - (*count); return 0; }参数说明enqueue_passenger()返回-1表示满载这是答辩时的关键得分点——必须体现容量约束dequeue_passengers()中的“扫描重构”看似低效但因MAX_PASSENGERS8最坏8次操作远优于动态内存分配passengers[]存的是目标楼层不是ID简化状态管理毕设不需追踪个体。3.3 与楼层请求链表的联动谁决定谁进轿厢关键逻辑在这里不是所有按了按钮的人都能立刻上电梯。必须满足两个条件电梯当前运行方向与请求方向一致如电梯上行只响应上行请求轿厢未满且该请求楼层在电梯路径上如电梯从3楼向上目标10楼则4~10楼的上行请求才有效。调度器伪代码如下// 调度主循环片段 while (has_requests(request_list)) { int next_target select_next_target(elev, request_list); if (next_target ! -1) { // 电梯移动到next_target move_elevator(elev, next_target); // 到达后1. 响应本层请求加入乘客队列2. 清理本层下客 handle_floor_arrival(elev, next_target, passenger_queue, request_list); } } void handle_floor_arrival(Elevator *elev, int floor, PassengerQueue *q, FloorRequest *head) { // 步骤1响应本层上行/下行请求按顺序加入乘客队列 FloorRequest *p head-next; while (p ! head) { if (p-floor floor ((elev-direction 1 p-direction 1) || (elev-direction -1 p-direction -1))) { if (enqueue_passenger(q, floor) 0) { // 成功入队标记该请求已处理后续删除 p-direction 0; // 标记为已响应 } } p p-next; } // 步骤2本层下客所有目标为floor的乘客离开 int left_count 0; dequeue_passengers(q, floor, left_count); // 步骤3从链表中删除已响应的请求direction0的节点 p head-next; while (p ! head) { FloorRequest *next p-next; if (p-floor floor p-direction 0) { remove_request_node(head, p); } p next; } }血泪经验很多同学把“响应请求”和“乘客入队”混为一谈导致同一请求被多次处理。必须用direction0作为已响应标记并在handle_floor_arrival末尾统一清理——这是严蔚敏教材“链表应用”章节强调的状态一致性原则。4. 三种调度策略实现与对比SCAN、LOOK、FCFS哪个更适合毕设单纯实现“电梯动起来”只是及格线。答辩高分的关键在于你能分析不同策略的时空复杂度并用数据证明优劣。我们实现最常用的三种策略核心逻辑时间复杂度空间复杂度毕设适配度典型问题FCFS按请求到达顺序服务O(n) per requestO(1)★★☆饥饿远处请求永远排不上SCAN电梯单向扫描到端点反转O(n) per decisionO(1)★★★★“山峰效应”端点请求响应慢LOOKSCAN改进版无空跑到最远请求即返O(n) per decisionO(1)★★★★★最平衡代码稍复杂4.1 FCFS最简实现但必须暴露缺陷// FCFS取链表第一个有效请求按timestamp最早 int fcfs_select_target(Elevator *elev, FloorRequest *head) { FloorRequest *p head-next; while (p ! head) { if (p-direction ! 0 ((elev-direction 1 p-direction 1) || (elev-direction -1 p-direction -1))) { return p-floor; } p p-next; } return -1; // 无匹配请求 }为什么必须写FCFS因为它是所有策略的baseline。毕设报告里要画出“平均等待时间 vs 请求密度”曲线FCFS一定是最高那条——这才能衬托出你实现的LOOK策略有多优秀。别怕暴露缺点能指出缺陷并给出量化证据比假装完美更专业。4.2 SCAN模拟真实电梯的“撞墙反转”SCAN策略要求电梯记住运行方向一直走到顶层或底层才反转。关键点是反转前必须清空反向请求否则会漏掉。int scan_select_target(Elevator *elev, FloorRequest *head) { // 方向为up找当前楼层以上第一个上行请求 if (elev-direction 1) { FloorRequest *p head-next; while (p ! head) { if (p-floor elev-current_floor p-direction 1) { return p-floor; } p p-next; } // 无更高上行请求反转找最高下行请求即开始向下扫描 elev-direction -1; int max_down_floor -1; p head-next; while (p ! head) { if (p-direction -1 p-floor elev-current_floor) { if (p-floor max_down_floor) max_down_floor p-floor; } p p-next; } return max_down_floor; } // direction -1类似逻辑找当前楼层以下第一个下行请求无则反转 // 代码省略结构对称 return -1; }避坑点SCAN的“撞墙”不是真到1楼或N楼才反转而是当电梯向上运行时发现上方再无上行请求就立即反转。很多同学硬编码if (elev-current_floor MAX_FLOORS) elev-direction -1这是错的——真实电梯不会空跑到顶再回头。4.3 LOOK毕设推荐策略代码量可控且效果好LOOK是SCAN的实用改进不跑到端点而是在当前方向上能找到的最远请求处就反转。实现只需两步扫描当前方向上的所有请求记录最远楼层若最远楼层存在返回第一个可达请求否则反转并重复。int look_select_target(Elevator *elev, FloorRequest *head) { int farthest -1; FloorRequest *p head-next; // 第一遍找当前方向最远请求楼层 if (elev-direction 1) { while (p ! head) { if (p-direction 1 p-floor elev-current_floor) { if (p-floor farthest) farthest p-floor; } p p-next; } } else { while (p ! head) { if (p-direction -1 p-floor elev-current_floor) { if (p-floor farthest || farthest -1) farthest p-floor; } p p-next; } } // 第二遍找第一个可达请求即离当前楼层最近的同向请求 if (elev-direction 1 farthest ! -1) { p head-next; while (p ! head) { if (p-direction 1 p-floor elev-current_floor p-floor farthest) { return p-floor; // 返回第一个即最近的 } p p-next; } } else if (elev-direction -1 farthest ! -1) { p head-next; while (p ! head) { if (p-direction -1 p-floor elev-current_floor p-floor farthest) { return p-floor; } p p-next; } } // 无同向请求反转方向递归调用或直接调用scan逻辑 elev-direction * -1; return look_select_target(elev, head); // 简化写法实际建议拆成独立函数防栈溢出 }参数说明farthest记录方向极限避免空跑两次遍历是必要的第一次确定范围第二次找首个目标——这比“边扫边记最小距离”更易理解也符合教材思路递归调用仅作示意实际应改用循环状态机防止极端情况栈溢出。5. 避坑指南毕设答辩最常被问的5个致命问题与现场应对毕设不是写完能跑就行答辩时老师专挑结构设计漏洞、边界没处理、复杂度没分析的地方问。以下是近三年我见过的真实翻车场景附解决方案5.1 现象电梯在2楼和3楼之间反复横跳停不下来原因调度器未处理“当前楼层有请求但轿厢已满”的情况。代码逻辑是“到达楼层→尝试入队→入队失败→不删除请求→下次又来”导致请求节点永远在链表里电梯反复响应。解决在handle_floor_arrival()中即使enqueue_passenger()失败也要将该请求direction置0并删除。满载不是拒绝理由而是调度器必须决策“先服务谁、谁等下一趟”的信号。5.2 现象多部电梯模拟时请求被重复分配给两部电梯原因共享的request_list链表没有加锁或学生用全局变量但没考虑并发。C语言毕设虽不强制多线程但若用fork()模拟多梯必须用pthread_mutex_t保护链表操作。解决声明全局互斥锁pthread_mutex_t request_mutex PTHREAD_MUTEX_INITIALIZER;所有insert_request()、remove_request_node()前加pthread_mutex_lock(request_mutex)后加unlock。哪怕单线程毕设加上锁注释也能体现工程意识。5.3 现象输入“100个请求”后程序崩溃Valgrind报invalid read原因链表删除节点时只改了前后指针但没置node-next node-prev NULL后续误用野指针。解决在remove_request_node()函数末尾free(p)前加p-next p-prev NULL;。严蔚敏教材P45明确要求“释放前置空指针”这是扣分重灾区。5.4 现象答辩演示时老师输入“楼层0”或“楼层1000”程序直接退出原因输入校验缺失。毕设文档要求“健壮性”必须对floor参数做if (floor 1 || floor MAX_FLOORS)检查。解决在insert_request()入口加校验非法值直接return并打印fprintf(stderr, Invalid floor: %d\n, floor);。不要用exit()否则答辩时老师连续输错三次就崩了。5.5 现象老师问“你的时间复杂度分析是基于最坏情况还是平均情况”答不上来原因只写了O(n)没说明n是什么请求总数楼层总数、在哪一步插入调度、最坏/平均场景分别是什么。解决在报告附录写明insert_request()O(n)n为链表长度最坏插入头结点look_select_target()O(n)n为请求总数因需两次遍历enqueue_passenger()O(1)环形缓冲区固定大小特别注明“本实现中n ≤ 100人工模拟上限故实际性能恒定”。——用具体数字堵住质疑。6. 用日志驱动验证如何让答辩老师一眼看懂你的调度优势毕设最怕“你说好但老师看不出好在哪”。我的做法是不截图UI而输出结构化日志用Excel画对比图。核心就三步6.1 定义日志格式每秒一条字段对齐[TIME1234] ELEVATOR: floor5, dir1, target8, pass_count3 [TIME1235] REQUEST: added floor7, dir1, ts123456789 [TIME1235] DISPATCH: selected floor7 via LOOK strategy [TIME1236] PASSENGER: entered floor5, dest7 [TIME1237] ARRIVAL: at floor7, dropped1, picked2用fprintf(log_file, [TIME%lu] %s\n, get_current_ms(), log_msg);生成。关键所有日志带TIME前缀且毫秒级时间戳——这样导入Excel后A列时间B列事件类型C列参数就能用数据透视表统计“各策略下平均等待时间”。6.2 自动生成对比报告Python脚本一键出图写一个analyze_log.py读取不同策略的日志文件提取关键指标import pandas as pd import matplotlib.pyplot as plt def parse_log(file_path): data [] with open(file_path) as f: for line in f: if ARRIVAL in line and dropped in line: # 提取到达时间、楼层、下客数 parts line.strip().split() time_ms int(parts[0].split()[1].rstrip(])) floor int(parts[3].split()[1].rstrip(,)) dropped int(parts[4].split()[1]) data.append({time: time_ms, floor: floor, dropped: dropped}) return pd.DataFrame(data) # 分析FCFS和LOOK日志 df_fcfs parse_log(fcfs.log) df_look parse_log(look.log) # 计算每个请求的等待时间简化用首次请求时间到到达时间 # 此处省略具体计算逻辑重点是输出可验证的数字 plt.figure(figsize(10,6)) plt.hist(df_fcfs[wait_time], alpha0.5, labelFCFS, bins20) plt.hist(df_look[wait_time], alpha0.5, labelLOOK, bins20) plt.xlabel(Waiting Time (ms)) plt.ylabel(Count) plt.legend() plt.title(Waiting Time Distribution: FCFS vs LOOK) plt.savefig(comparison.png, dpi300)答辩时直接打开comparison.png指着图说“老师您看FCFS等待时间集中在2000ms以上而LOOK压到了800ms以内标准差降低62%——这证明LOOK策略有效缓解了饥饿问题。”数据比嘴说有力得多。6.3 终极技巧用“请求生命周期”表格锁定设计正确性在报告最后一页放一张手动追踪的表格选3个典型请求如t100ms时3楼按上行t150ms时8楼按下行t200ms时5楼按上行列出它们在链表中的状态变迁请求ID时间戳楼层方向链表状态被哪部电梯响应响应时间等待时长R11003upinserted → served → removedElevator112001100msR21508downinserted → ignored → reversed → servedElevator125002350msR32005upinserted → served → removedElevator218001600ms为什么这招必杀因为老师只要扫一眼就能确认你真的实现了“方向匹配”R2初始被忽略因Elevator1当时上行你处理了“反转逻辑”R2在Elevator1到达顶层后被响应你区分了“响应”和“服务完成”R1的served状态在ARRIVAL日志后才变removed你没漏掉任何环节——这是数据结构课程设计最看重的状态完整性。我带的学生里凡在答辩前花2小时手填这张表的100%过了。不是因为表多高级而是它强迫你把整个系统像电路一样逐节点、逐状态、逐时间戳地推演一遍。当你能闭着眼说出“R2在t2200ms时正躺在链表第7个节点prev指向R1next指向R3”老师就知道这孩子真把链表和队列焊进骨头里了。希望帮到你。本文还有配套的精品资源点击获取