簡介這是一份數(shù)據(jù)結(jié)構(gòu)課程期末作業(yè)的完整工程包主題為銀行排隊系統(tǒng)適合需要完成同類作業(yè)或練習隊列應用的在校學生。資源通過雙隊列模型實現(xiàn)VIP與普通用戶的優(yōu)先級服務(wù)重點覆蓋隊列的入隊出隊操作、多隊列調(diào)度邏輯、基于文件讀取用戶信息以及C STL中queue容器的使用能幫助理解隊列結(jié)構(gòu)在真實場景中的落地方式。壓縮包共9個文件大小1.03MB包含C源碼、項目配置與依賴文件、用戶信息數(shù)據(jù)文件以及編譯生成的exe/obj等既可直接運行查看效果也可打開工程研讀實現(xiàn)細節(jié)。目前已有3361人學習此資源適合作為數(shù)據(jù)結(jié)構(gòu)期末項目參考也可在此基礎(chǔ)上擴展業(yè)務(wù)規(guī)則或改進可視化界面。1. 數(shù)據(jù)結(jié)構(gòu)期末作業(yè)里的?？豌y行排隊系統(tǒng)到底在考什么如果你正在準備數(shù)據(jù)結(jié)構(gòu)期末大概率會撞上「銀行排隊系統(tǒng)」這道經(jīng)典題目。它表面是個控制臺項目實際考的是隊列在真實業(yè)務(wù)里的建模能力客戶到達、排隊、窗口叫號、等待時長統(tǒng)計這些環(huán)節(jié)全都要落到數(shù)據(jù)結(jié)構(gòu)和算法上。很多同學拿到題先寫界面寫完發(fā)現(xiàn)核心邏輯全擠在一堆 if 里窗口一多就亂套數(shù)據(jù)一跑就崩。這份作業(yè)資源把整個系統(tǒng)拆成了客戶管理、隊列調(diào)度、時間片推進、統(tǒng)計輸出四個模塊用 C 語言實現(xiàn)邏輯完整實驗報告也配套好了。適合正在做數(shù)據(jù)結(jié)構(gòu)課程設(shè)計、需要一份能跑通能答辯的參考工程的同學也適合想在期末復習里把鏈隊列和循環(huán)隊列一次看明白的人。不吹復雜度但能讓你少走三個禮拜彎路。2. 先把模型立住隊列選型、客戶狀態(tài)機與三類設(shè)計取舍2.1 為什么是隊列而不是棧從真實柜臺業(yè)務(wù)倒推數(shù)據(jù)結(jié)構(gòu)選型銀行排隊這件事本質(zhì)是先進先出先到的人先被叫號后到的人排在隊尾。這正好對應隊列隊列的操作受限在兩端隊尾入隊、隊頭出隊。上學期學棧的時候你大概率背過「后進先出」但真正面對業(yè)務(wù)場景時能不能從需求反推結(jié)構(gòu)才是關(guān)鍵。銀行排隊系統(tǒng)如果用棧來模擬就會變成最后一個人先被服務(wù)這在業(yè)務(wù)上是災難面試官一眼就能看出你沒有建模能力。這道作業(yè)題的刻意之處在于它逼著你從「業(yè)務(wù)規(guī)則」出發(fā)而不是從「我會寫什么代碼」出發(fā)。我在拆這份資源時最先看的不是代碼怎么寫而是它的模型定義。完整的銀行排隊系統(tǒng)至少要回答四個問題客戶是什么時候來的客戶需要服務(wù)多久窗口什么時候空閑空閑窗口該叫誰。這四個問題分別對應客戶數(shù)據(jù)結(jié)構(gòu)里的到達時間、服務(wù)時長以及調(diào)度模塊里的窗口狀態(tài)判斷隊列出隊操作。順序一旦反了比如先出隊再查空閑窗口就會出現(xiàn)窗口空著沒人服務(wù)、隊首客戶卻干等的情況。選隊列還有一個理由它允許你在常量時間內(nèi)完成入隊和出隊。鏈隊列的入隊出隊都是 O(1)不會隨著客戶數(shù)量增加而變慢。這是這門課里最容易被忽視的考點——老師只要追問一句「為什么不用數(shù)組模擬」你要能說出擴容代價和空間浪費。順序隊列雖然也行但循環(huán)隊列的實現(xiàn)細節(jié)多處理不好就翻車后面避坑章節(jié)我會專門講。2.2 鏈隊列 vs 順序隊列期末作業(yè)場景下的取舍標準期末作業(yè)場景下選鏈隊列還是順序隊列我建議直接看兩個條件一是你的客戶數(shù)量是否有限制二是你要不要頻繁取隊頭元素。這份資源用的是簡單鏈隊列頭節(jié)點作為哨兵front 指針始終指向哨兵rear 指向隊尾入隊操作接在 rear 后面出隊操作從 front 后面取。這套實現(xiàn)的好處是判空特別直觀front 的 next 為空就是空隊列不需要維護 front 和 rear 相等這種邊界狀態(tài)。如果你選順序隊列注意循環(huán)隊列的判空和判滿條件容易混淆。很多同學用 headtail 判空又用 headtail 判滿結(jié)果隊列滿的時候和空的時候表現(xiàn)一樣運行起來邏輯全亂。順序隊列適合客戶數(shù)量固定、你明確知道峰值容量不超過某個值的場景比如題目規(guī)定了「銀行最多同時接待 100 個客戶」。鏈隊列則沒有這個限制內(nèi)存按需分配更適合做模擬類作業(yè)——你不知道模擬到第 1000 分鐘時排隊人數(shù)是 5 個還是 50 個。兩份答案我都見過優(yōu)秀的作業(yè)案例。順序隊列勝在代碼短適合時間緊張、只想交差的情況鏈隊列勝在魯棒性適合想沖高分、答辯時能多說幾句的情況。這份資源選鏈隊列還有個實際考慮它要在模擬結(jié)束后遍歷隊列輸出每個客戶的等待時間鏈隊列的遍歷邏輯比順序隊列下標翻轉(zhuǎn)更好講清楚。2.3 客戶對象的數(shù)據(jù)結(jié)構(gòu)狀態(tài)機、等待時長與窗口分配客戶是系統(tǒng)里的核心對象它的數(shù)據(jù)結(jié)構(gòu)定義決定了整個系統(tǒng)的復雜度。我看過不少作業(yè)把客戶簡化成一個整數(shù)編號結(jié)果后面統(tǒng)計平均等待時間時完全無從下手。客戶至少要有七個字段編號、到達時間、服務(wù)時長、開始服務(wù)時間、等待時長、狀態(tài)、指向下一個客戶的指針。狀態(tài)字段可以定義成枚舉取值包括未到達、排隊中、服務(wù)中、已完成四種?？蛻舻臓顟B(tài)機是整個系統(tǒng)的內(nèi)在邏輯未到達的客戶在模擬主循環(huán)里按概率生成并入隊排隊中的客戶等待窗口空出服務(wù)中的客戶消耗窗口剩余時間已完成的客戶統(tǒng)計數(shù)據(jù)并釋放內(nèi)存。這份資源把狀態(tài)機分散在調(diào)度模塊和主循環(huán)里而不是用一個大 switch 包裹我覺得更符合實際工程習慣——每個狀態(tài)只有一種轉(zhuǎn)型路徑狀態(tài)間的關(guān)系在代碼流程里自然體現(xiàn)答辯時你能講清楚每個分支為什么這么寫。窗口分配的規(guī)則需要單獨說。最簡單的分配策略是掃描所有窗口找到第一個空閑窗口就把隊首客戶分配過去。復雜度為 O(窗口數(shù))窗口少時無感窗口數(shù)到 20 以上時每一分鐘都要掃描一次就會浪費大量時間。進階做法是維護一個空閑窗口鏈表空閑窗口入鏈忙碌窗口出鏈分配時直接取鏈表頭部復雜度 O(1)。這份資源用的是掃描法因為它窗口數(shù)一般不超過 10代碼更直觀適合期末作業(yè)的教學目標。2.4 雙端隊列與優(yōu)先級隊列作業(yè)里哪些「加分設(shè)計」值得做數(shù)據(jù)結(jié)構(gòu)教材里比普通隊列高階的是雙端隊列和優(yōu)先級隊列。雙端隊列允許隊頭隊尾都能入隊出隊優(yōu)先級隊列則按優(yōu)先級出隊而不是按到達順序。銀行排隊系統(tǒng)里這兩種結(jié)構(gòu)都能找到應用場景但我不建議在基礎(chǔ)版本里直接用。原因很簡單老師批改作業(yè)時先看的是你能否用最樸素的方式把業(yè)務(wù)模擬清楚花里胡哨的進階結(jié)構(gòu)如果沒有業(yè)務(wù)支撐答辯時一個「為什么要用雙端隊列」就能把你問住。如果你一定要做加分設(shè)計優(yōu)先級隊列有兩個位置可以合理地出現(xiàn)VIP 客戶插隊和老年客戶優(yōu)先窗口。這兩個業(yè)務(wù)規(guī)則都天然符合優(yōu)先隊列的語義不是硬套。具體做法是給客戶結(jié)構(gòu)體加一個 priority 字段普通客戶為 0VIP 客戶為 1然后在小頂堆的基礎(chǔ)上改成按優(yōu)先級比較、同優(yōu)先級再按到達時間排序。這份資源里沒有用堆而是簡單地對隊列做了一次查找找到優(yōu)先級最高的客戶再出隊復雜度是 O(n)適合處理少量 VIP 的場景。雙端隊列在這個項目里最合理的用途是實現(xiàn)「喊號不回應則重新排到隊尾」這個業(yè)務(wù)。喊號超時未到的客戶從隊頭移除再插入到隊尾普通隊列要實現(xiàn)這個邏輯得先出隊再入隊雙端隊列語義上更貼切。但注意如果老師沒要求這個業(yè)務(wù)做得再好也是額外負擔。我給你的建議是優(yōu)先保證基礎(chǔ)流程完整、數(shù)據(jù)統(tǒng)計準確再把剩余時間花在測試和報告上這兩項的性價比遠高于加一個堆排序。3. 核心代碼落地排隊模擬器的四個模塊與關(guān)鍵函數(shù)3.1 工具模塊隨機客戶生成與時間片推進模擬類作業(yè)的核心思路不是「寫一個真實的銀行系統(tǒng)」而是「在離散時間片里推進狀態(tài)」。常見做法是以分鐘為最小時間單位每分鐘做三件事決定是否有新客戶到達、讓忙碌窗口的剩余服務(wù)時間減一、把空閑窗口分配給隊首客戶。這樣整個系統(tǒng)的狀態(tài)就是可追蹤的任何時刻你都能解釋某個客戶在哪個隊列、某個窗口在服務(wù)誰?？蛻舻竭_的邏輯一般用概率控制。每分鐘到達一個新客戶或者每 N 分鐘到達一個客戶兩種模式各有用途。固定間隔適合測試概率到達適合模擬真實場景。下面這段代碼用的是概率模式用隨機數(shù)判斷當前分鐘是否有客戶到達void generate_customer(Queue *q, int current_time, int *global_id) { Customer *c (Customer *)malloc(sizeof(Customer)); if (!c) { printf(內(nèi)存分配失敗模擬終止\n); exit(1); } c-id (*global_id); c-arrive_time current_time; // 服務(wù)時長2 到 8 分鐘之間的隨機數(shù)模擬不同業(yè)務(wù)復雜度 c-service_time rand() % 7 2; c-start_time -1; c-wait_time 0; c-state 1; // 1 表示排隊中0 表示未到達2 表示服務(wù)中3 表示已完成 c-next NULL; q-rear-next c; q-rear c; q-size; }這段代碼里最關(guān)鍵的是rand() % 7 2。這個表達式生成 2 到 8 的整數(shù)表示客戶需要的服務(wù)時長。如果你覺得業(yè)務(wù)里應該有些客戶快速辦完、有些客戶磨嘰很久可以把隨機分布從均勻分布改成分段分布比如 70% 概率生成 2 到 4 分鐘30% 概率生成 6 到 10 分鐘。很多作業(yè)的統(tǒng)計結(jié)果「看起來不真實」就是因為服務(wù)時長用了均勻分布現(xiàn)實中銀行不會所有人都平均耗時。時間片推進的主循環(huán)要維護一個時鐘變量每循環(huán)一次加一。循環(huán)終止條件有兩個常見選項固定運行 480 分鐘模擬銀行一天的營業(yè)時長或者運行到隊列清空且所有窗口空閑。推薦用前者作為主終止條件后者作為程序結(jié)束前的收尾步驟——你要統(tǒng)計完整營業(yè)日的數(shù)據(jù)就必須把已經(jīng)入隊但還沒服務(wù)完的客戶處理掉。另外注意rand()在多次運行時如果不設(shè)置隨機種子每次結(jié)果都一樣這在測試階段很方便但最終演示時要加srand(time(NULL))讓每次運行的數(shù)據(jù)不同。3.2 隊列模塊入隊、出隊、判空與遍歷統(tǒng)計鏈隊列的實現(xiàn)建議加上一個 sentinel 頭節(jié)點。頭節(jié)點不存數(shù)據(jù)只作為鏈表起點front 指向它rear 指向最后一個真實節(jié)點。這樣做的好處是空隊列的表示非常干凈front 和 rear 都指向頭節(jié)點沒有任何多余判斷。判空邏輯是front-next NULL這個條件在整個調(diào)度模塊里會反復用寫錯一次可能只有到窗口分配時才能發(fā)現(xiàn)。入隊邏輯是往 rear 后面掛新節(jié)點同時更新 rear出隊邏輯是摘掉 front 后面的第一個真實節(jié)點如果摘完發(fā)現(xiàn)隊列空了要把 rear 重新指回頭節(jié)點——這一步漏掉就直接翻車后面無限遍歷。int is_queue_empty(Queue *q) { return q-front-next NULL; } void enqueue(Queue *q, Customer *c) { c-next NULL; q-rear-next c; q-rear c; q-size; } Customer *dequeue(Queue *q) { if (is_queue_empty(q)) return NULL; Customer *c q-front-next; q-front-next c-next; if (q-front-next NULL) { q-rear q-front; // 隊列空了rear 回到哨兵 } q-size--; c-next NULL; return c; }有兩點值得你注意。第一出隊時為什么要把c-next置空這不是必須的但能防止上層誤用已出隊節(jié)點的指針做遍歷屬于防御性編程的順手操作。第二dequeue返回的是客戶指針而不是 void這樣調(diào)度模塊可以拿這個指針直接設(shè)置開始服務(wù)時間省一次查找。數(shù)據(jù)結(jié)構(gòu)作業(yè)里函數(shù)的設(shè)計能體現(xiàn)出你有沒有工程素質(zhì)面試官翻代碼時第一個看的就是「出隊的客戶數(shù)據(jù)怎么被上層使用」。如果把這一步做成先出隊再從某個數(shù)組里按 id 找回客戶那就白白浪費了出隊的返回值。隊列遍歷統(tǒng)計是另一個高頻功能。營業(yè)結(jié)束后要把隊列里剩下沒處理的客戶標記為「未完成」同時在表格里輸出。遍歷用for (Customer *p q-front-next; p ! NULL; p p-next)就夠了。統(tǒng)計峰值隊列長度時在每次入隊和出隊后更新max_len變量比最后再掃一遍隊列要簡單得多也更不容易出錯。3.3 調(diào)度模塊窗口空閑檢測與分配邏輯調(diào)度模塊是銀行排隊系統(tǒng)的核心也是最能拉開分數(shù)差距的地方。每次主循環(huán)進入調(diào)度階段時遍歷所有窗口找到剩余服務(wù)時間為 0 的窗口把隊首客戶出隊分配給它。但這里有一個容易被忽視的業(yè)務(wù)細節(jié)同一分鐘內(nèi)有多個窗口空閑時先分配哪個窗口其實對客戶而言沒有區(qū)別但對代碼實現(xiàn)來說每個窗口獨立分配即可不需要額外排序。typedef struct { int remaining_time; // 剩余服務(wù)時間0 表示空閑 int served_count; // 今日已服務(wù)客戶數(shù) int total_busy_time; // 累計忙碌時間用于計算窗口利用率 } Window; void dispatch(Queue *q, Window *windows, int window_count, int current_time) { for (int i 0; i window_count; i) { if (windows[i].remaining_time 0 !is_queue_empty(q)) { Customer *c dequeue(q); c-start_time current_time; c-wait_time current_time - c-arrive_time; c-state 2; // 服務(wù)中 windows[i].remaining_time c-service_time; windows[i].served_count; printf(分鐘 %d客戶 %d 開始在窗口 %d 服務(wù)等待 %d 分鐘\n, current_time, c-id, i 1, c-wait_time); } if (windows[i].remaining_time 0) { windows[i].remaining_time--; } } }注意上面代碼里remaining_time--的位置。它放在同一輪循環(huán)的最后先分配再遞減。這樣窗口在ts時刻被分配客戶服務(wù)時間立即減一代表這一分鐘已經(jīng)消耗掉。如果你把遞減放在循環(huán)開頭邏輯就會變成「這一分鐘先被跳過」導致所有客戶的服務(wù)結(jié)束時間延后一分鐘統(tǒng)計出的平均等待時間偏大。這種差一分鐘的 bug 最難查因為整個系統(tǒng)還能跑通只是數(shù)據(jù)不對。調(diào)度模塊還有一個細節(jié)客戶分配給了窗口之后進度要不要立即打印。我看過一些作業(yè)把printf放在所有窗口處理完之后統(tǒng)一輸出導致日志時序錯亂客戶明明在第 50 分鐘開始服務(wù)打印卻出現(xiàn)在第 51 分鐘。這里的教訓是模擬系統(tǒng)的日志輸出必須緊貼狀態(tài)變更不要為了排版整齊而延遲打印。答辯時老師會拿著你的運行日志和代碼對照看對不上就露餡了。3.4 結(jié)算模塊平均等待時間、隊列長度峰值的計算口徑結(jié)算模塊的目標是在模擬結(jié)束后輸出三項數(shù)據(jù)服務(wù)客戶總數(shù)、平均等待時間、最大隊列長度。三個數(shù)據(jù)的計算口徑各有講究。服務(wù)客戶總數(shù)是窗口served_count之和這個最簡單但注意要排除掉營業(yè)結(jié)束還沒被服務(wù)的客戶——用總數(shù)除以窗口數(shù)算平均每個窗口的服務(wù)量時邊界情況很容易錯。平均等待時間的計算要區(qū)分「已服務(wù)客戶」和「所有到達客戶」。這份資源里統(tǒng)計的是已服務(wù)客戶的平均等待時間即總等待時間 / 已服務(wù)客戶數(shù)。如果你把還在隊列里等待的客戶也算進去這些客戶 wait_time 還未更新會導致結(jié)果虛低。計算總等待時間時在dispatch里累加c-wait_time到全局變量total_wait_time最后一步再除以served_total避免結(jié)算時再遍歷一次隊列。void settle(Queue *q, Window *windows, int window_count, int total_wait_time, int served_total) { printf(\n 營業(yè)結(jié)束統(tǒng)計 \n); printf(總服務(wù)客戶數(shù)%d\n, served_total); printf(已服務(wù)客戶平均等待時間%.2f 分鐘\n, served_total 0 ? (double)total_wait_time / served_total : 0.0); int left 0; for (Customer *p q-front-next; p ! NULL; p p-next) { left; } printf(營業(yè)結(jié)束時仍在排隊的客戶數(shù)%d\n, left); printf(最大隊列長度%d\n, max_queue_len); }結(jié)算模塊里最容易犯的錯是除零。如果模擬參數(shù)設(shè)置得極端比如客戶到達概率極低、窗口數(shù)量多到幾乎不需要排隊可能出現(xiàn)served_total為 0 或者隊列里始終沒人除零直接崩潰或輸出inf。答辯時老師喜歡改參數(shù)測試的魯棒性你要在結(jié)算函數(shù)里做防御性判斷。上面的代碼已經(jīng)用三元表達式擋了一層但這只是最低限度更穩(wěn)的做法是在主循環(huán)里檢查客戶總數(shù)為 0 時提前結(jié)束模擬。4. 避坑與排查五個導致銀行排隊系統(tǒng)翻車的典型問題4.1 現(xiàn)象運行幾秒后程序閃退或死循環(huán)這個現(xiàn)象在鏈隊列實現(xiàn)里尤其常見。閃退多半發(fā)生在窗口分配時訪問了空指針死循環(huán)多半發(fā)生在遍歷隊列時鏈表斷裂或成環(huán)。最常見的根因是出隊操作時沒有在隊列為空的情況下重置rear指針。出隊最后一個客戶后front和rear還指向那個已經(jīng)被釋放的節(jié)點下一次入隊會繼續(xù)往這個釋放過的內(nèi)存地址上寫數(shù)據(jù)程序直接崩潰。解決把出隊函數(shù)里q-rear q-front這行加上確保隊列空了以后 rear 重新回到哨兵節(jié)點。如果你用的是上課給的模板代碼先檢查模板里出隊函數(shù)是否處理了「出隊后變空」這個邊界條件。很多教科書為了簡潔省略了這步作業(yè)直接照抄就翻車。4.2 現(xiàn)象所有客戶集中擠在一個窗口其他窗口都是空閑的這通常是窗口分配邏輯中的判斷方向?qū)懛戳恕＜僭O(shè)一個窗口的remaining_time為 0 表示空閑如果你順手寫成 0那么窗口剛被分配完客戶后仍然滿足條件同一輪循環(huán)里會被二次分配相當于一個窗口連續(xù)搶走多個客戶。表現(xiàn)就是只有一個窗口在忙其余窗口一直空閑服務(wù)數(shù)據(jù)完全失真。解決把窗口空閑判斷收斂成remaining_time 0這一個條件同時確保遞減邏輯在分配之后執(zhí)行。如果同一個窗口在同一次循環(huán)里既被分配又被遞減把它拆成「先分配后遞減」兩個階段不要混在一起。打印日志確認每個窗口每次循環(huán)最多只被分配一次客戶。4.3 現(xiàn)象平均值忽大忽小每次運行結(jié)果都不一樣無法復現(xiàn)沒有設(shè)置隨機種子導致的問題在測試階段尤其煩人。rand()默認種子是 1每次運行生成相同的隨機序列但如果你在代碼里加了srand(time(NULL))每次運行結(jié)果都不同這導致你沒法穩(wěn)定地復現(xiàn)一個 bug。我見過有人為了「看起來真實」每次運行都換隨機種子結(jié)果 debug 時改一個參數(shù)隊列行為完全變了沒法判斷是參數(shù)改動還是隨機因素導致的。解決在測試模式下調(diào)srand(1)固定種子讓每次運行結(jié)果一模一樣確認邏輯正確后再切到隨機種子。建議在主函數(shù)里加一個測試開關(guān)比如if (test_mode) srand(42); else srand(time(NULL));。這個習慣也能在答辯時加分——你可以當著老師的面用固定種子復現(xiàn)數(shù)據(jù)再切隨機種子演示一次說明兩種模式都驗證過。4.4 現(xiàn)象輸入菜單選項后程序不執(zhí)行對應功能直接跳過這是 C 語言控制臺程序里最常見的問題幾乎每份作業(yè)都會踩一次。scanf(%d, choice)讀取完數(shù)字后緩沖區(qū)里還殘留一個換行符\n緊接著的getchar()或scanf(%c)會把換行符讀進去導致后續(xù)邏輯以為你輸入了一個非法字符?，F(xiàn)象就是菜單選了 1程序秒過什么都沒發(fā)生。解決在每個scanf后面加一個while (getchar() ! \n);清空緩沖?；蛘呓y(tǒng)一用fgets讀整行再用sscanf解析后者更穩(wěn)但代碼量會大一些。期末作業(yè)用第一種就行改動最小風險最低。注意這個坑在 Windows 和 Linux 下表現(xiàn)不一致Windows 下\r\n處理更麻煩盡量在 main 函數(shù)開頭就用 setbuf 或者在每個輸入點后清一次緩沖。4.5 現(xiàn)象數(shù)據(jù)量大時輸出錯亂日志跟實際業(yè)務(wù)對不上模擬運行超過幾百分鐘、客戶數(shù)量上千時控制臺輸出會變得非常長。問題不在邏輯而在輸出緩沖和滾動速度——你看到的日志可能是幾十秒前的排查時對著舊日志調(diào)新代碼越調(diào)越亂。另外有些人用printf輸出調(diào)試信息跑完才發(fā)現(xiàn)正式輸出和調(diào)試輸出混在一起答辯時老師根本不知道哪行是結(jié)果。解決把日志分級模塊內(nèi)部用DEBUG宏控制是否輸出只有客戶狀態(tài)變更和最終統(tǒng)計結(jié)果走正式輸出通道。在 main 循環(huán)頂部打印當前分鐘數(shù)方便對照。如果你用的是 Windows 終端輸出量大時建議重定向到文件運行一次./bank_system log.txt再打開文件逐行看。這也是我給你的建議模擬類作業(yè)的正確調(diào)試方式從來都是看文件不是盯控制臺。5. 測試與驗證用一份可復現(xiàn)的實驗數(shù)據(jù)證明作業(yè)能跑通5.1 測試用例設(shè)計邊界條件、極端負載與穩(wěn)定運行期末作業(yè)最怕的不是功能做不出來而是測試階段做的都是「正常情況」邊界條件一碰就崩。好的測試用例至少要有四類。第一類是空隊列運行把客戶到達概率設(shè)為 0窗口數(shù)設(shè) 1跑完整 480 分鐘程序應能正常結(jié)束且統(tǒng)計結(jié)果為全 0不能出現(xiàn)除零崩潰。第二類是極端負載窗口數(shù)設(shè) 1到達概率設(shè) 1每分鐘都來一個人模擬結(jié)束后確認沒有內(nèi)存泄漏、沒有隊列溢出。第三類是常規(guī)負載窗口數(shù)設(shè) 3 到 5到達概率設(shè) 0.3 到 0.5記錄平均等待時間驗證結(jié)果在合理范圍內(nèi)——正常情況下平均等待時間應該在一二十分鐘左右如果超過兩小時說明調(diào)度有問題。第四類是混合服務(wù)時長把服務(wù)時長的分布從均值改為偏態(tài)分布觀察隊列長度峰值的變化。下面給一份可以直接粘貼的測試用例表字段包括測試名、參數(shù)、預期結(jié)果、實際結(jié)果、判定。我每次做課程設(shè)計都會先建這張表填完再動手改代碼比邊寫邊測效率高一倍。測試名窗口數(shù)到達概率服務(wù)時長范圍預期結(jié)果判定空隊列10.0-正常結(jié)束統(tǒng)計數(shù)據(jù)全 0通過極限負載11.02-8 分鐘所有客戶被服務(wù)無崩潰通過常規(guī)混跑40.42-8 分鐘平均等待 5-25 分鐘需驗證VIP 插隊40.4混合分布VIP 平均等待低于普通客戶需驗證5.2 數(shù)據(jù)結(jié)果分析平均等待時間與服務(wù)窗口數(shù)的關(guān)系銀行排隊系統(tǒng)的核心輸出指標是平均等待時間和最大隊列長度。這兩個指標對窗口數(shù)的敏感度極高窗口從 3 個增加到 4 個平均等待時間可能從 30 分鐘直接掉到 10 分鐘但從 5 個增加到 6 個改善幅度就不明顯了。這是因為排隊論里的利用率臨界點效應——當窗口數(shù)量增加到一定程度后瓶頸從窗口數(shù)轉(zhuǎn)移到了客戶到達規(guī)律本身。一份能拿高分的作業(yè)會在報告里展示三組不同窗口數(shù)下的運行結(jié)果并解釋「為什么窗口加到 5 個以后平均等待時間下降趨緩」。這份實驗可以跟著做固定到達概率為 0.5、模擬 480 分鐘、服務(wù)時長 2 到 8 分鐘分別用 2、3、4、5、6 個窗口跑記錄平均等待時間和最大隊列長度你會發(fā)現(xiàn)曲線從陡降變成平緩。這組數(shù)據(jù)就是緒論里「銀行該開多少個窗口」這個問題最直觀的回答。還要注意一個統(tǒng)計細節(jié)最大隊列長度應該記錄「營業(yè)期間任意時刻排隊的客戶數(shù)最大值」而不是「營業(yè)結(jié)束時隊列里還剩多少人」。很多同學把這兩個數(shù)搞混答辯時被老師一句「你最大隊列長度才 3但日志里顯示中間有段時間排隊 20 多人」問得啞口無言。實現(xiàn)時在入隊操作后加一行if (q-size max_queue_len) max_queue_len q-size;比最后遍歷逐步判定準確得多。5.3 復雜度分析期末答辯必問的時間復雜度與空間復雜度答辯時老師必問的問題是「你這個系統(tǒng)的時間復雜度和空間復雜度是多少」。很多人在這道送分題上翻車因為模擬類作業(yè)的時間復雜度不能簡單地用單步操作 O(1) 來回答要和模擬的分鐘數(shù) M、客戶總數(shù) N、窗口數(shù) W 三個維度掛鉤。整體時間復雜度的推導脈絡(luò)是主循環(huán)運行 M 分鐘每分鐘做一次到達判斷O(1)和一次調(diào)度O(W)所以調(diào)度部分的總復雜度 O(M * W)。如果使用優(yōu)先級隊列做 VIP 插隊調(diào)度部分復雜度為 O(M * logN)因為每次出隊要維護堆結(jié)構(gòu)?？臻g復雜度由隊列長度決定最壞情況下所有客戶在同一時段到達且窗口無法及時處理隊列長度為 O(N)。另外每個客戶結(jié)構(gòu)體占固定空間總空間 O(N)。答到這里就把 O(N) 的答案和「為什么不是 O(N2)」講清楚了。6. 答辯與報告把作業(yè)從及格線拉到優(yōu)秀檔的三個習慣6.1 實驗報告這樣寫老師第一眼就認可報告的結(jié)構(gòu)別按教科書模板抄按你代碼里的模塊走。先寫業(yè)務(wù)需求分析把「先進先出、窗口空閑叫號、超時重新排隊」三條規(guī)則用自然語言描述清楚再畫數(shù)據(jù)結(jié)構(gòu)定義直接用你代碼里的結(jié)構(gòu)體。核心是展示一張運行結(jié)果表列出 3 組窗口數(shù)下平均等待時間、最大隊列長度、總服務(wù)客戶數(shù)然后補一段對結(jié)果的分析。這兩樣The last part of the report is the hardest one: dont write too much, and dont paste a new chapter. The teacher will read the report and code for 20 minutes, and the empty words will be crossed out. The most direct way to get a high score is to show that you have actually done many experiments and have a comparison. If you can append a test log of two shots, the credibility will immediately rise.6.2 Source code organization and two useful expansion directionsSource code dont put everything into one main.c. Split into queue module. c, dispatch. c, stats. c, plus the header file, accompanied by a makefile. Consider that most data structure courses only use C, but I suggest that you do this anyway, because in defense I have many students type code in front of the teacher to say my code is all in one file, which is actually not a problem, but if you show 3 files, the impression of engineering quality is enough to push the score up half a gear.Two cost-effective expansion directions: the first is VIP priority channel, often use priority queue implementation, business logic is clear; the second is to add too late to call the number processing, two times failed to respond to the customer back to the tail of the queue. Both are small changes, code scale about 50 lines. If you can also mention the queue length peak change with the window number trend line, the answer to the optimization question will have material. I have done more than a dozen such projects, each time the final defense is forced to walk through these three things: fixed seeds reproducing a set of experimental data, boundary test to run again, report the complexity analysis once. Since then, whenever I take over a similar simulation project, I first do three stops: fixed seeds, boundary tests, complexity, and then change the logic. Hope it helps you, at least on the last night before the deadline to have a batch of can answer the code.本文還有配套的精品資源點擊獲取