簡(jiǎn)介這是一份數(shù)據(jù)結(jié)構(gòu)課程期末作業(yè)的完整工程包主題為銀行排隊(duì)系統(tǒng)適合需要完成同類作業(yè)或練習(xí)隊(duì)列應(yīng)用的在校學(xué)生。資源通過(guò)雙隊(duì)列模型實(shí)現(xiàn)VIP與普通用戶的優(yōu)先級(jí)服務(wù)重點(diǎn)覆蓋隊(duì)列的入隊(duì)出隊(duì)操作、多隊(duì)列調(diào)度邏輯、基于文件讀取用戶信息以及C STL中queue容器的使用能幫助理解隊(duì)列結(jié)構(gòu)在真實(shí)場(chǎng)景中的落地方式。壓縮包共9個(gè)文件大小1.03MB包含C源碼、項(xiàng)目配置與依賴文件、用戶信息數(shù)據(jù)文件以及編譯生成的exe/obj等既可直接運(yùn)行查看效果也可打開(kāi)工程研讀實(shí)現(xiàn)細(xì)節(jié)。目前已有3361人學(xué)習(xí)此資源適合作為數(shù)據(jù)結(jié)構(gòu)期末項(xiàng)目參考也可在此基礎(chǔ)上擴(kuò)展業(yè)務(wù)規(guī)則或改進(jìn)可視化界面。1. 數(shù)據(jù)結(jié)構(gòu)期末作業(yè)里的?？豌y行排隊(duì)系統(tǒng)到底在考什么如果你正在準(zhǔn)備數(shù)據(jù)結(jié)構(gòu)期末大概率會(huì)撞上「銀行排隊(duì)系統(tǒng)」這道經(jīng)典題目。它表面是個(gè)控制臺(tái)項(xiàng)目實(shí)際考的是隊(duì)列在真實(shí)業(yè)務(wù)里的建模能力客戶到達(dá)、排隊(duì)、窗口叫號(hào)、等待時(shí)長(zhǎng)統(tǒng)計(jì)這些環(huán)節(jié)全都要落到數(shù)據(jù)結(jié)構(gòu)和算法上。很多同學(xué)拿到題先寫界面寫完發(fā)現(xiàn)核心邏輯全擠在一堆 if 里窗口一多就亂套數(shù)據(jù)一跑就崩。這份作業(yè)資源把整個(gè)系統(tǒng)拆成了客戶管理、隊(duì)列調(diào)度、時(shí)間片推進(jìn)、統(tǒng)計(jì)輸出四個(gè)模塊用 C 語(yǔ)言實(shí)現(xiàn)邏輯完整實(shí)驗(yàn)報(bào)告也配套好了。適合正在做數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)、需要一份能跑通能答辯的參考工程的同學(xué)也適合想在期末復(fù)習(xí)里把鏈隊(duì)列和循環(huán)隊(duì)列一次看明白的人。不吹復(fù)雜度但能讓你少走三個(gè)禮拜彎路。2. 先把模型立住隊(duì)列選型、客戶狀態(tài)機(jī)與三類設(shè)計(jì)取舍2.1 為什么是隊(duì)列而不是棧從真實(shí)柜臺(tái)業(yè)務(wù)倒推數(shù)據(jù)結(jié)構(gòu)選型銀行排隊(duì)這件事本質(zhì)是先進(jìn)先出先到的人先被叫號(hào)后到的人排在隊(duì)尾。這正好對(duì)應(yīng)隊(duì)列隊(duì)列的操作受限在兩端隊(duì)尾入隊(duì)、隊(duì)頭出隊(duì)。上學(xué)期學(xué)棧的時(shí)候你大概率背過(guò)「后進(jìn)先出」但真正面對(duì)業(yè)務(wù)場(chǎng)景時(shí)能不能從需求反推結(jié)構(gòu)才是關(guān)鍵。銀行排隊(duì)系統(tǒng)如果用棧來(lái)模擬就會(huì)變成最后一個(gè)人先被服務(wù)這在業(yè)務(wù)上是災(zāi)難面試官一眼就能看出你沒(méi)有建模能力。這道作業(yè)題的刻意之處在于它逼著你從「業(yè)務(wù)規(guī)則」出發(fā)而不是從「我會(huì)寫什么代碼」出發(fā)。我在拆這份資源時(shí)最先看的不是代碼怎么寫而是它的模型定義。完整的銀行排隊(duì)系統(tǒng)至少要回答四個(gè)問(wèn)題客戶是什么時(shí)候來(lái)的客戶需要服務(wù)多久窗口什么時(shí)候空閑空閑窗口該叫誰(shuí)。這四個(gè)問(wèn)題分別對(duì)應(yīng)客戶數(shù)據(jù)結(jié)構(gòu)里的到達(dá)時(shí)間、服務(wù)時(shí)長(zhǎng)以及調(diào)度模塊里的窗口狀態(tài)判斷隊(duì)列出隊(duì)操作。順序一旦反了比如先出隊(duì)再查空閑窗口就會(huì)出現(xiàn)窗口空著沒(méi)人服務(wù)、隊(duì)首客戶卻干等的情況。選隊(duì)列還有一個(gè)理由它允許你在常量時(shí)間內(nèi)完成入隊(duì)和出隊(duì)。鏈隊(duì)列的入隊(duì)出隊(duì)都是 O(1)不會(huì)隨著客戶數(shù)量增加而變慢。這是這門課里最容易被忽視的考點(diǎn)——老師只要追問(wèn)一句「為什么不用數(shù)組模擬」你要能說(shuō)出擴(kuò)容代價(jià)和空間浪費(fèi)。順序隊(duì)列雖然也行但循環(huán)隊(duì)列的實(shí)現(xiàn)細(xì)節(jié)多處理不好就翻車后面避坑章節(jié)我會(huì)專門講。2.2 鏈隊(duì)列 vs 順序隊(duì)列期末作業(yè)場(chǎng)景下的取舍標(biāo)準(zhǔn)期末作業(yè)場(chǎng)景下選鏈隊(duì)列還是順序隊(duì)列我建議直接看兩個(gè)條件一是你的客戶數(shù)量是否有限制二是你要不要頻繁取隊(duì)頭元素。這份資源用的是簡(jiǎn)單鏈隊(duì)列頭節(jié)點(diǎn)作為哨兵front 指針始終指向哨兵rear 指向隊(duì)尾入隊(duì)操作接在 rear 后面出隊(duì)操作從 front 后面取。這套實(shí)現(xiàn)的好處是判空特別直觀front 的 next 為空就是空隊(duì)列不需要維護(hù) front 和 rear 相等這種邊界狀態(tài)。如果你選順序隊(duì)列注意循環(huán)隊(duì)列的判空和判滿條件容易混淆。很多同學(xué)用 headtail 判空又用 headtail 判滿結(jié)果隊(duì)列滿的時(shí)候和空的時(shí)候表現(xiàn)一樣運(yùn)行起來(lái)邏輯全亂。順序隊(duì)列適合客戶數(shù)量固定、你明確知道峰值容量不超過(guò)某個(gè)值的場(chǎng)景比如題目規(guī)定了「銀行最多同時(shí)接待 100 個(gè)客戶」。鏈隊(duì)列則沒(méi)有這個(gè)限制內(nèi)存按需分配更適合做模擬類作業(yè)——你不知道模擬到第 1000 分鐘時(shí)排隊(duì)人數(shù)是 5 個(gè)還是 50 個(gè)。兩份答案我都見(jiàn)過(guò)優(yōu)秀的作業(yè)案例。順序隊(duì)列勝在代碼短適合時(shí)間緊張、只想交差的情況鏈隊(duì)列勝在魯棒性適合想沖高分、答辯時(shí)能多說(shuō)幾句的情況。這份資源選鏈隊(duì)列還有個(gè)實(shí)際考慮它要在模擬結(jié)束后遍歷隊(duì)列輸出每個(gè)客戶的等待時(shí)間鏈隊(duì)列的遍歷邏輯比順序隊(duì)列下標(biāo)翻轉(zhuǎn)更好講清楚。2.3 客戶對(duì)象的數(shù)據(jù)結(jié)構(gòu)狀態(tài)機(jī)、等待時(shí)長(zhǎng)與窗口分配客戶是系統(tǒng)里的核心對(duì)象它的數(shù)據(jù)結(jié)構(gòu)定義決定了整個(gè)系統(tǒng)的復(fù)雜度。我看過(guò)不少作業(yè)把客戶簡(jiǎn)化成一個(gè)整數(shù)編號(hào)結(jié)果后面統(tǒng)計(jì)平均等待時(shí)間時(shí)完全無(wú)從下手?？蛻糁辽僖衅邆€(gè)字段編號(hào)、到達(dá)時(shí)間、服務(wù)時(shí)長(zhǎng)、開(kāi)始服務(wù)時(shí)間、等待時(shí)長(zhǎng)、狀態(tài)、指向下一個(gè)客戶的指針。狀態(tài)字段可以定義成枚舉取值包括未到達(dá)、排隊(duì)中、服務(wù)中、已完成四種?？蛻舻臓顟B(tài)機(jī)是整個(gè)系統(tǒng)的內(nèi)在邏輯未到達(dá)的客戶在模擬主循環(huán)里按概率生成并入隊(duì)排隊(duì)中的客戶等待窗口空出服務(wù)中的客戶消耗窗口剩余時(shí)間已完成的客戶統(tǒng)計(jì)數(shù)據(jù)并釋放內(nèi)存。這份資源把狀態(tài)機(jī)分散在調(diào)度模塊和主循環(huán)里而不是用一個(gè)大 switch 包裹我覺(jué)得更符合實(shí)際工程習(xí)慣——每個(gè)狀態(tài)只有一種轉(zhuǎn)型路徑狀態(tài)間的關(guān)系在代碼流程里自然體現(xiàn)答辯時(shí)你能講清楚每個(gè)分支為什么這么寫。窗口分配的規(guī)則需要單獨(dú)說(shuō)。最簡(jiǎn)單的分配策略是掃描所有窗口找到第一個(gè)空閑窗口就把隊(duì)首客戶分配過(guò)去。復(fù)雜度為 O(窗口數(shù))窗口少時(shí)無(wú)感窗口數(shù)到 20 以上時(shí)每一分鐘都要掃描一次就會(huì)浪費(fèi)大量時(shí)間。進(jìn)階做法是維護(hù)一個(gè)空閑窗口鏈表空閑窗口入鏈忙碌窗口出鏈分配時(shí)直接取鏈表頭部復(fù)雜度 O(1)。這份資源用的是掃描法因?yàn)樗翱跀?shù)一般不超過(guò) 10代碼更直觀適合期末作業(yè)的教學(xué)目標(biāo)。2.4 雙端隊(duì)列與優(yōu)先級(jí)隊(duì)列作業(yè)里哪些「加分設(shè)計(jì)」值得做數(shù)據(jù)結(jié)構(gòu)教材里比普通隊(duì)列高階的是雙端隊(duì)列和優(yōu)先級(jí)隊(duì)列。雙端隊(duì)列允許隊(duì)頭隊(duì)尾都能入隊(duì)出隊(duì)優(yōu)先級(jí)隊(duì)列則按優(yōu)先級(jí)出隊(duì)而不是按到達(dá)順序。銀行排隊(duì)系統(tǒng)里這兩種結(jié)構(gòu)都能找到應(yīng)用場(chǎng)景但我不建議在基礎(chǔ)版本里直接用。原因很簡(jiǎn)單老師批改作業(yè)時(shí)先看的是你能否用最樸素的方式把業(yè)務(wù)模擬清楚花里胡哨的進(jìn)階結(jié)構(gòu)如果沒(méi)有業(yè)務(wù)支撐答辯時(shí)一個(gè)「為什么要用雙端隊(duì)列」就能把你問(wèn)住。如果你一定要做加分設(shè)計(jì)優(yōu)先級(jí)隊(duì)列有兩個(gè)位置可以合理地出現(xiàn)VIP 客戶插隊(duì)和老年客戶優(yōu)先窗口。這兩個(gè)業(yè)務(wù)規(guī)則都天然符合優(yōu)先隊(duì)列的語(yǔ)義不是硬套。具體做法是給客戶結(jié)構(gòu)體加一個(gè) priority 字段普通客戶為 0VIP 客戶為 1然后在小頂堆的基礎(chǔ)上改成按優(yōu)先級(jí)比較、同優(yōu)先級(jí)再按到達(dá)時(shí)間排序。這份資源里沒(méi)有用堆而是簡(jiǎn)單地對(duì)隊(duì)列做了一次查找找到優(yōu)先級(jí)最高的客戶再出隊(duì)復(fù)雜度是 O(n)適合處理少量 VIP 的場(chǎng)景。雙端隊(duì)列在這個(gè)項(xiàng)目里最合理的用途是實(shí)現(xiàn)「喊號(hào)不回應(yīng)則重新排到隊(duì)尾」這個(gè)業(yè)務(wù)。喊號(hào)超時(shí)未到的客戶從隊(duì)頭移除再插入到隊(duì)尾普通隊(duì)列要實(shí)現(xiàn)這個(gè)邏輯得先出隊(duì)再入隊(duì)雙端隊(duì)列語(yǔ)義上更貼切。但注意如果老師沒(méi)要求這個(gè)業(yè)務(wù)做得再好也是額外負(fù)擔(dān)。我給你的建議是優(yōu)先保證基礎(chǔ)流程完整、數(shù)據(jù)統(tǒng)計(jì)準(zhǔn)確再把剩余時(shí)間花在測(cè)試和報(bào)告上這兩項(xiàng)的性價(jià)比遠(yuǎn)高于加一個(gè)堆排序。3. 核心代碼落地排隊(duì)模擬器的四個(gè)模塊與關(guān)鍵函數(shù)3.1 工具模塊隨機(jī)客戶生成與時(shí)間片推進(jìn)模擬類作業(yè)的核心思路不是「寫一個(gè)真實(shí)的銀行系統(tǒng)」而是「在離散時(shí)間片里推進(jìn)狀態(tài)」。常見(jiàn)做法是以分鐘為最小時(shí)間單位每分鐘做三件事決定是否有新客戶到達(dá)、讓忙碌窗口的剩余服務(wù)時(shí)間減一、把空閑窗口分配給隊(duì)首客戶。這樣整個(gè)系統(tǒng)的狀態(tài)就是可追蹤的任何時(shí)刻你都能解釋某個(gè)客戶在哪個(gè)隊(duì)列、某個(gè)窗口在服務(wù)誰(shuí)?？蛻舻竭_(dá)的邏輯一般用概率控制。每分鐘到達(dá)一個(gè)新客戶或者每 N 分鐘到達(dá)一個(gè)客戶兩種模式各有用途。固定間隔適合測(cè)試概率到達(dá)適合模擬真實(shí)場(chǎng)景。下面這段代碼用的是概率模式用隨機(jī)數(shù)判斷當(dāng)前分鐘是否有客戶到達(dá)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ù)時(shí)長(zhǎng)2 到 8 分鐘之間的隨機(jī)數(shù)模擬不同業(yè)務(wù)復(fù)雜度 c-service_time rand() % 7 2; c-start_time -1; c-wait_time 0; c-state 1; // 1 表示排隊(duì)中0 表示未到達(dá)2 表示服務(wù)中3 表示已完成 c-next NULL; q-rear-next c; q-rear c; q-size; }這段代碼里最關(guān)鍵的是rand() % 7 2。這個(gè)表達(dá)式生成 2 到 8 的整數(shù)表示客戶需要的服務(wù)時(shí)長(zhǎng)。如果你覺(jué)得業(yè)務(wù)里應(yīng)該有些客戶快速辦完、有些客戶磨嘰很久可以把隨機(jī)分布從均勻分布改成分段分布比如 70% 概率生成 2 到 4 分鐘30% 概率生成 6 到 10 分鐘。很多作業(yè)的統(tǒng)計(jì)結(jié)果「看起來(lái)不真實(shí)」就是因?yàn)榉?wù)時(shí)長(zhǎng)用了均勻分布現(xiàn)實(shí)中銀行不會(huì)所有人都平均耗時(shí)。時(shí)間片推進(jìn)的主循環(huán)要維護(hù)一個(gè)時(shí)鐘變量每循環(huán)一次加一。循環(huán)終止條件有兩個(gè)常見(jiàn)選項(xiàng)固定運(yùn)行 480 分鐘模擬銀行一天的營(yíng)業(yè)時(shí)長(zhǎng)或者運(yùn)行到隊(duì)列清空且所有窗口空閑。推薦用前者作為主終止條件后者作為程序結(jié)束前的收尾步驟——你要統(tǒng)計(jì)完整營(yíng)業(yè)日的數(shù)據(jù)就必須把已經(jīng)入隊(duì)但還沒(méi)服務(wù)完的客戶處理掉。另外注意rand()在多次運(yùn)行時(shí)如果不設(shè)置隨機(jī)種子每次結(jié)果都一樣這在測(cè)試階段很方便但最終演示時(shí)要加srand(time(NULL))讓每次運(yùn)行的數(shù)據(jù)不同。3.2 隊(duì)列模塊入隊(duì)、出隊(duì)、判空與遍歷統(tǒng)計(jì)鏈隊(duì)列的實(shí)現(xiàn)建議加上一個(gè) sentinel 頭節(jié)點(diǎn)。頭節(jié)點(diǎn)不存數(shù)據(jù)只作為鏈表起點(diǎn)front 指向它rear 指向最后一個(gè)真實(shí)節(jié)點(diǎn)。這樣做的好處是空隊(duì)列的表示非常干凈front 和 rear 都指向頭節(jié)點(diǎn)沒(méi)有任何多余判斷。判空邏輯是front-next NULL這個(gè)條件在整個(gè)調(diào)度模塊里會(huì)反復(fù)用寫錯(cuò)一次可能只有到窗口分配時(shí)才能發(fā)現(xiàn)。入隊(duì)邏輯是往 rear 后面掛新節(jié)點(diǎn)同時(shí)更新 rear出隊(duì)邏輯是摘掉 front 后面的第一個(gè)真實(shí)節(jié)點(diǎn)如果摘完發(fā)現(xiàn)隊(duì)列空了要把 rear 重新指回頭節(jié)點(diǎn)——這一步漏掉就直接翻車后面無(wú)限遍歷。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; // 隊(duì)列空了rear 回到哨兵 } q-size--; c-next NULL; return c; }有兩點(diǎn)值得你注意。第一出隊(duì)時(shí)為什么要把c-next置空這不是必須的但能防止上層誤用已出隊(duì)節(jié)點(diǎn)的指針做遍歷屬于防御性編程的順手操作。第二dequeue返回的是客戶指針而不是 void這樣調(diào)度模塊可以拿這個(gè)指針直接設(shè)置開(kāi)始服務(wù)時(shí)間省一次查找。數(shù)據(jù)結(jié)構(gòu)作業(yè)里函數(shù)的設(shè)計(jì)能體現(xiàn)出你有沒(méi)有工程素質(zhì)面試官翻代碼時(shí)第一個(gè)看的就是「出隊(duì)的客戶數(shù)據(jù)怎么被上層使用」。如果把這一步做成先出隊(duì)再?gòu)哪硞€(gè)數(shù)組里按 id 找回客戶那就白白浪費(fèi)了出隊(duì)的返回值。隊(duì)列遍歷統(tǒng)計(jì)是另一個(gè)高頻功能。營(yíng)業(yè)結(jié)束后要把隊(duì)列里剩下沒(méi)處理的客戶標(biāo)記為「未完成」同時(shí)在表格里輸出。遍歷用for (Customer *p q-front-next; p ! NULL; p p-next)就夠了。統(tǒng)計(jì)峰值隊(duì)列長(zhǎng)度時(shí)在每次入隊(duì)和出隊(duì)后更新max_len變量比最后再掃一遍隊(duì)列要簡(jiǎn)單得多也更不容易出錯(cuò)。3.3 調(diào)度模塊窗口空閑檢測(cè)與分配邏輯調(diào)度模塊是銀行排隊(duì)系統(tǒng)的核心也是最能拉開(kāi)分?jǐn)?shù)差距的地方。每次主循環(huán)進(jìn)入調(diào)度階段時(shí)遍歷所有窗口找到剩余服務(wù)時(shí)間為 0 的窗口把隊(duì)首客戶出隊(duì)分配給它。但這里有一個(gè)容易被忽視的業(yè)務(wù)細(xì)節(jié)同一分鐘內(nèi)有多個(gè)窗口空閑時(shí)先分配哪個(gè)窗口其實(shí)對(duì)客戶而言沒(méi)有區(qū)別但對(duì)代碼實(shí)現(xiàn)來(lái)說(shuō)每個(gè)窗口獨(dú)立分配即可不需要額外排序。typedef struct { int remaining_time; // 剩余服務(wù)時(shí)間0 表示空閑 int served_count; // 今日已服務(wù)客戶數(shù) int total_busy_time; // 累計(jì)忙碌時(shí)間用于計(jì)算窗口利用率 } 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 開(kāi)始在窗口 %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時(shí)刻被分配客戶服務(wù)時(shí)間立即減一代表這一分鐘已經(jīng)消耗掉。如果你把遞減放在循環(huán)開(kāi)頭邏輯就會(huì)變成「這一分鐘先被跳過(guò)」導(dǎo)致所有客戶的服務(wù)結(jié)束時(shí)間延后一分鐘統(tǒng)計(jì)出的平均等待時(shí)間偏大。這種差一分鐘的 bug 最難查因?yàn)檎麄€(gè)系統(tǒng)還能跑通只是數(shù)據(jù)不對(duì)。調(diào)度模塊還有一個(gè)細(xì)節(jié)客戶分配給了窗口之后進(jìn)度要不要立即打印。我看過(guò)一些作業(yè)把printf放在所有窗口處理完之后統(tǒng)一輸出導(dǎo)致日志時(shí)序錯(cuò)亂客戶明明在第 50 分鐘開(kāi)始服務(wù)打印卻出現(xiàn)在第 51 分鐘。這里的教訓(xùn)是模擬系統(tǒng)的日志輸出必須緊貼狀態(tài)變更不要為了排版整齊而延遲打印。答辯時(shí)老師會(huì)拿著你的運(yùn)行日志和代碼對(duì)照看對(duì)不上就露餡了。3.4 結(jié)算模塊平均等待時(shí)間、隊(duì)列長(zhǎng)度峰值的計(jì)算口徑結(jié)算模塊的目標(biāo)是在模擬結(jié)束后輸出三項(xiàng)數(shù)據(jù)服務(wù)客戶總數(shù)、平均等待時(shí)間、最大隊(duì)列長(zhǎng)度。三個(gè)數(shù)據(jù)的計(jì)算口徑各有講究。服務(wù)客戶總數(shù)是窗口served_count之和這個(gè)最簡(jiǎn)單但注意要排除掉營(yíng)業(yè)結(jié)束還沒(méi)被服務(wù)的客戶——用總數(shù)除以窗口數(shù)算平均每個(gè)窗口的服務(wù)量時(shí)邊界情況很容易錯(cuò)。平均等待時(shí)間的計(jì)算要區(qū)分「已服務(wù)客戶」和「所有到達(dá)客戶」。這份資源里統(tǒng)計(jì)的是已服務(wù)客戶的平均等待時(shí)間即總等待時(shí)間 / 已服務(wù)客戶數(shù)。如果你把還在隊(duì)列里等待的客戶也算進(jìn)去這些客戶 wait_time 還未更新會(huì)導(dǎo)致結(jié)果虛低。計(jì)算總等待時(shí)間時(shí)在dispatch里累加c-wait_time到全局變量total_wait_time最后一步再除以served_total避免結(jié)算時(shí)再遍歷一次隊(duì)列。void settle(Queue *q, Window *windows, int window_count, int total_wait_time, int served_total) { printf(\n 營(yíng)業(yè)結(jié)束統(tǒng)計(jì) \n); printf(總服務(wù)客戶數(shù)%d\n, served_total); printf(已服務(wù)客戶平均等待時(shí)間%.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íng)業(yè)結(jié)束時(shí)仍在排隊(duì)的客戶數(shù)%d\n, left); printf(最大隊(duì)列長(zhǎng)度%d\n, max_queue_len); }結(jié)算模塊里最容易犯的錯(cuò)是除零。如果模擬參數(shù)設(shè)置得極端比如客戶到達(dá)概率極低、窗口數(shù)量多到幾乎不需要排隊(duì)可能出現(xiàn)served_total為 0 或者隊(duì)列里始終沒(méi)人除零直接崩潰或輸出inf。答辯時(shí)老師喜歡改參數(shù)測(cè)試的魯棒性你要在結(jié)算函數(shù)里做防御性判斷。上面的代碼已經(jīng)用三元表達(dá)式擋了一層但這只是最低限度更穩(wěn)的做法是在主循環(huán)里檢查客戶總數(shù)為 0 時(shí)提前結(jié)束模擬。4. 避坑與排查五個(gè)導(dǎo)致銀行排隊(duì)系統(tǒng)翻車的典型問(wèn)題4.1 現(xiàn)象運(yùn)行幾秒后程序閃退或死循環(huán)這個(gè)現(xiàn)象在鏈隊(duì)列實(shí)現(xiàn)里尤其常見(jiàn)。閃退多半發(fā)生在窗口分配時(shí)訪問(wèn)了空指針?biāo)姥h(huán)多半發(fā)生在遍歷隊(duì)列時(shí)鏈表斷裂或成環(huán)。最常見(jiàn)的根因是出隊(duì)操作時(shí)沒(méi)有在隊(duì)列為空的情況下重置rear指針。出隊(duì)最后一個(gè)客戶后front和rear還指向那個(gè)已經(jīng)被釋放的節(jié)點(diǎn)下一次入隊(duì)會(huì)繼續(xù)往這個(gè)釋放過(guò)的內(nèi)存地址上寫數(shù)據(jù)程序直接崩潰。解決把出隊(duì)函數(shù)里q-rear q-front這行加上確保隊(duì)列空了以后 rear 重新回到哨兵節(jié)點(diǎn)。如果你用的是上課給的模板代碼先檢查模板里出隊(duì)函數(shù)是否處理了「出隊(duì)后變空」這個(gè)邊界條件。很多教科書為了簡(jiǎn)潔省略了這步作業(yè)直接照抄就翻車。4.2 現(xiàn)象所有客戶集中擠在一個(gè)窗口其他窗口都是空閑的這通常是窗口分配邏輯中的判斷方向?qū)懛戳?。假設(shè)一個(gè)窗口的remaining_time為 0 表示空閑如果你順手寫成 0那么窗口剛被分配完客戶后仍然滿足條件同一輪循環(huán)里會(huì)被二次分配相當(dāng)于一個(gè)窗口連續(xù)搶走多個(gè)客戶。表現(xiàn)就是只有一個(gè)窗口在忙其余窗口一直空閑服務(wù)數(shù)據(jù)完全失真。解決把窗口空閑判斷收斂成remaining_time 0這一個(gè)條件同時(shí)確保遞減邏輯在分配之后執(zhí)行。如果同一個(gè)窗口在同一次循環(huán)里既被分配又被遞減把它拆成「先分配后遞減」兩個(gè)階段不要混在一起。打印日志確認(rèn)每個(gè)窗口每次循環(huán)最多只被分配一次客戶。4.3 現(xiàn)象平均值忽大忽小每次運(yùn)行結(jié)果都不一樣無(wú)法復(fù)現(xiàn)沒(méi)有設(shè)置隨機(jī)種子導(dǎo)致的問(wèn)題在測(cè)試階段尤其煩人。rand()默認(rèn)種子是 1每次運(yùn)行生成相同的隨機(jī)序列但如果你在代碼里加了srand(time(NULL))每次運(yùn)行結(jié)果都不同這導(dǎo)致你沒(méi)法穩(wěn)定地復(fù)現(xiàn)一個(gè) bug。我見(jiàn)過(guò)有人為了「看起來(lái)真實(shí)」每次運(yùn)行都換隨機(jī)種子結(jié)果 debug 時(shí)改一個(gè)參數(shù)隊(duì)列行為完全變了沒(méi)法判斷是參數(shù)改動(dòng)還是隨機(jī)因素導(dǎo)致的。解決在測(cè)試模式下調(diào)srand(1)固定種子讓每次運(yùn)行結(jié)果一模一樣確認(rèn)邏輯正確后再切到隨機(jī)種子。建議在主函數(shù)里加一個(gè)測(cè)試開(kāi)關(guān)比如if (test_mode) srand(42); else srand(time(NULL));。這個(gè)習(xí)慣也能在答辯時(shí)加分——你可以當(dāng)著老師的面用固定種子復(fù)現(xiàn)數(shù)據(jù)再切隨機(jī)種子演示一次說(shuō)明兩種模式都驗(yàn)證過(guò)。4.4 現(xiàn)象輸入菜單選項(xiàng)后程序不執(zhí)行對(duì)應(yīng)功能直接跳過(guò)這是 C 語(yǔ)言控制臺(tái)程序里最常見(jiàn)的問(wèn)題幾乎每份作業(yè)都會(huì)踩一次。scanf(%d, choice)讀取完數(shù)字后緩沖區(qū)里還殘留一個(gè)換行符\n緊接著的getchar()或scanf(%c)會(huì)把換行符讀進(jìn)去導(dǎo)致后續(xù)邏輯以為你輸入了一個(gè)非法字符。現(xiàn)象就是菜單選了 1程序秒過(guò)什么都沒(méi)發(fā)生。解決在每個(gè)scanf后面加一個(gè)while (getchar() ! \n);清空緩沖。或者統(tǒng)一用fgets讀整行再用sscanf解析后者更穩(wěn)但代碼量會(huì)大一些。期末作業(yè)用第一種就行改動(dòng)最小風(fēng)險(xiǎn)最低。注意這個(gè)坑在 Windows 和 Linux 下表現(xiàn)不一致Windows 下\r\n處理更麻煩盡量在 main 函數(shù)開(kāi)頭就用 setbuf 或者在每個(gè)輸入點(diǎn)后清一次緩沖。4.5 現(xiàn)象數(shù)據(jù)量大時(shí)輸出錯(cuò)亂日志跟實(shí)際業(yè)務(wù)對(duì)不上模擬運(yùn)行超過(guò)幾百分鐘、客戶數(shù)量上千時(shí)控制臺(tái)輸出會(huì)變得非常長(zhǎng)。問(wèn)題不在邏輯而在輸出緩沖和滾動(dòng)速度——你看到的日志可能是幾十秒前的排查時(shí)對(duì)著舊日志調(diào)新代碼越調(diào)越亂。另外有些人用printf輸出調(diào)試信息跑完才發(fā)現(xiàn)正式輸出和調(diào)試輸出混在一起答辯時(shí)老師根本不知道哪行是結(jié)果。解決把日志分級(jí)模塊內(nèi)部用DEBUG宏控制是否輸出只有客戶狀態(tài)變更和最終統(tǒng)計(jì)結(jié)果走正式輸出通道。在 main 循環(huán)頂部打印當(dāng)前分鐘數(shù)方便對(duì)照。如果你用的是 Windows 終端輸出量大時(shí)建議重定向到文件運(yùn)行一次./bank_system log.txt再打開(kāi)文件逐行看。這也是我給你的建議模擬類作業(yè)的正確調(diào)試方式從來(lái)都是看文件不是盯控制臺(tái)。5. 測(cè)試與驗(yàn)證用一份可復(fù)現(xiàn)的實(shí)驗(yàn)數(shù)據(jù)證明作業(yè)能跑通5.1 測(cè)試用例設(shè)計(jì)邊界條件、極端負(fù)載與穩(wěn)定運(yùn)行期末作業(yè)最怕的不是功能做不出來(lái)而是測(cè)試階段做的都是「正常情況」邊界條件一碰就崩。好的測(cè)試用例至少要有四類。第一類是空隊(duì)列運(yùn)行把客戶到達(dá)概率設(shè)為 0窗口數(shù)設(shè) 1跑完整 480 分鐘程序應(yīng)能正常結(jié)束且統(tǒng)計(jì)結(jié)果為全 0不能出現(xiàn)除零崩潰。第二類是極端負(fù)載窗口數(shù)設(shè) 1到達(dá)概率設(shè) 1每分鐘都來(lái)一個(gè)人模擬結(jié)束后確認(rèn)沒(méi)有內(nèi)存泄漏、沒(méi)有隊(duì)列溢出。第三類是常規(guī)負(fù)載窗口數(shù)設(shè) 3 到 5到達(dá)概率設(shè) 0.3 到 0.5記錄平均等待時(shí)間驗(yàn)證結(jié)果在合理范圍內(nèi)——正常情況下平均等待時(shí)間應(yīng)該在一二十分鐘左右如果超過(guò)兩小時(shí)說(shuō)明調(diào)度有問(wèn)題。第四類是混合服務(wù)時(shí)長(zhǎng)把服務(wù)時(shí)長(zhǎng)的分布從均值改為偏態(tài)分布觀察隊(duì)列長(zhǎng)度峰值的變化。下面給一份可以直接粘貼的測(cè)試用例表字段包括測(cè)試名、參數(shù)、預(yù)期結(jié)果、實(shí)際結(jié)果、判定。我每次做課程設(shè)計(jì)都會(huì)先建這張表填完再動(dòng)手改代碼比邊寫邊測(cè)效率高一倍。測(cè)試名窗口數(shù)到達(dá)概率服務(wù)時(shí)長(zhǎng)范圍預(yù)期結(jié)果判定空隊(duì)列10.0-正常結(jié)束統(tǒng)計(jì)數(shù)據(jù)全 0通過(guò)極限負(fù)載11.02-8 分鐘所有客戶被服務(wù)無(wú)崩潰通過(guò)常規(guī)混跑40.42-8 分鐘平均等待 5-25 分鐘需驗(yàn)證VIP 插隊(duì)40.4混合分布VIP 平均等待低于普通客戶需驗(yàn)證5.2 數(shù)據(jù)結(jié)果分析平均等待時(shí)間與服務(wù)窗口數(shù)的關(guān)系銀行排隊(duì)系統(tǒng)的核心輸出指標(biāo)是平均等待時(shí)間和最大隊(duì)列長(zhǎng)度。這兩個(gè)指標(biāo)對(duì)窗口數(shù)的敏感度極高窗口從 3 個(gè)增加到 4 個(gè)平均等待時(shí)間可能從 30 分鐘直接掉到 10 分鐘但從 5 個(gè)增加到 6 個(gè)改善幅度就不明顯了。這是因?yàn)榕抨?duì)論里的利用率臨界點(diǎn)效應(yīng)——當(dāng)窗口數(shù)量增加到一定程度后瓶頸從窗口數(shù)轉(zhuǎn)移到了客戶到達(dá)規(guī)律本身。一份能拿高分的作業(yè)會(huì)在報(bào)告里展示三組不同窗口數(shù)下的運(yùn)行結(jié)果并解釋「為什么窗口加到 5 個(gè)以后平均等待時(shí)間下降趨緩」。這份實(shí)驗(yàn)可以跟著做固定到達(dá)概率為 0.5、模擬 480 分鐘、服務(wù)時(shí)長(zhǎng) 2 到 8 分鐘分別用 2、3、4、5、6 個(gè)窗口跑記錄平均等待時(shí)間和最大隊(duì)列長(zhǎng)度你會(huì)發(fā)現(xiàn)曲線從陡降變成平緩。這組數(shù)據(jù)就是緒論里「銀行該開(kāi)多少個(gè)窗口」這個(gè)問(wèn)題最直觀的回答。還要注意一個(gè)統(tǒng)計(jì)細(xì)節(jié)最大隊(duì)列長(zhǎng)度應(yīng)該記錄「營(yíng)業(yè)期間任意時(shí)刻排隊(duì)的客戶數(shù)最大值」而不是「營(yíng)業(yè)結(jié)束時(shí)隊(duì)列里還剩多少人」。很多同學(xué)把這兩個(gè)數(shù)搞混答辯時(shí)被老師一句「你最大隊(duì)列長(zhǎng)度才 3但日志里顯示中間有段時(shí)間排隊(duì) 20 多人」問(wèn)得啞口無(wú)言。實(shí)現(xiàn)時(shí)在入隊(duì)操作后加一行if (q-size max_queue_len) max_queue_len q-size;比最后遍歷逐步判定準(zhǔn)確得多。5.3 復(fù)雜度分析期末答辯必問(wèn)的時(shí)間復(fù)雜度與空間復(fù)雜度答辯時(shí)老師必問(wèn)的問(wèn)題是「你這個(gè)系統(tǒng)的時(shí)間復(fù)雜度和空間復(fù)雜度是多少」。很多人在這道送分題上翻車因?yàn)槟M類作業(yè)的時(shí)間復(fù)雜度不能簡(jiǎn)單地用單步操作 O(1) 來(lái)回答要和模擬的分鐘數(shù) M、客戶總數(shù) N、窗口數(shù) W 三個(gè)維度掛鉤。整體時(shí)間復(fù)雜度的推導(dǎo)脈絡(luò)是主循環(huán)運(yùn)行 M 分鐘每分鐘做一次到達(dá)判斷O(1)和一次調(diào)度O(W)所以調(diào)度部分的總復(fù)雜度 O(M * W)。如果使用優(yōu)先級(jí)隊(duì)列做 VIP 插隊(duì)調(diào)度部分復(fù)雜度為 O(M * logN)因?yàn)槊看纬鲫?duì)要維護(hù)堆結(jié)構(gòu)?？臻g復(fù)雜度由隊(duì)列長(zhǎng)度決定最壞情況下所有客戶在同一時(shí)段到達(dá)且窗口無(wú)法及時(shí)處理隊(duì)列長(zhǎng)度為 O(N)。另外每個(gè)客戶結(jié)構(gòu)體占固定空間總空間 O(N)。答到這里就把 O(N) 的答案和「為什么不是 O(N2)」講清楚了。6. 答辯與報(bào)告把作業(yè)從及格線拉到優(yōu)秀檔的三個(gè)習(xí)慣6.1 實(shí)驗(yàn)報(bào)告這樣寫老師第一眼就認(rèn)可報(bào)告的結(jié)構(gòu)別按教科書模板抄按你代碼里的模塊走。先寫業(yè)務(wù)需求分析把「先進(jìn)先出、窗口空閑叫號(hào)、超時(shí)重新排隊(duì)」三條規(guī)則用自然語(yǔ)言描述清楚再畫數(shù)據(jù)結(jié)構(gòu)定義直接用你代碼里的結(jié)構(gòu)體。核心是展示一張運(yùn)行結(jié)果表列出 3 組窗口數(shù)下平均等待時(shí)間、最大隊(duì)列長(zhǎng)度、總服務(wù)客戶數(shù)然后補(bǔ)一段對(duì)結(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.本文還有配套的精品資源點(diǎn)擊獲取