第3單元線性數(shù)據(jù)結(jié)構(gòu)二(編輯修改稿)
2025-08-16 10:04 本頁面
【文章內(nèi)容簡介】 取隊頭元素 22/53 四、隊列的順序存儲 ? 1. 定義空隊列 : 用一維數(shù)組 – define MAXSIZE n – int queue[MAXSIZE]； – int front=1, rear=1。 ? front：隊頭指針 。 ? rear：隊尾指針 。 –空隊列： front = rear –滿隊列： rear = MAXSIZE1 23/53 ? 約定： ? front: 總是指向隊頭元素的前一個位置； ? rear: 總是指向隊尾元素的位置 ? 結(jié)果： 對任何元素，操作都一樣 ? 出隊 : 入隊 : ? front = front + 1 ； rear=rear+1。 ? x = queue [front]； queue[rear]=x。 ? front rear a1 a2 … a n 24/53 舉例：順序隊列的入隊、出隊操作 ? 1）空隊列 ? 2） A、 B、 C、 D、 E入隊 ? 3） A、 B、 C出隊 front rear D E front rear A B C D E front rear 入隊時， rear在變 出隊時， front在變 25/53 ? 4） F、 G、 H入隊 ? 5） D、 E、 F、 G、 H出隊，出現(xiàn)假“溢出” front front rear D E F G H rear 26/53 3. 假溢出 ? 假溢出 –隊列是空的情況下出現(xiàn)的溢出。 ? 解決方法 – 1) 整個隊列左移 ,費時 – 2) 隊列的首尾相連 循環(huán)隊列 ? 目的 –隊列中真正沒有空位置時，才產(chǎn)生溢出。 27/53 循環(huán)隊列 ? (隊頭指針移動 ) – front=(front+1)%MAXSIZE； ? 等價于： – if – (front+1= MAXSIZE) – front = 0 。 – else – front=front+1。 (隊尾指針移動 ) rear=(rear+1)%MAXSIZE； 等價于： if (rear+1=MAXSIZE) rear = 0。 else rear=rear+1。 28/53 循環(huán)隊列隊空、隊滿條件 ? 約定 : –隊頭指針指示的 –結(jié)點不用于存儲 –元素 ,只作標(biāo)志 –即保留一個節(jié)點 ? 隊空條件 – front = rear ； ? 隊滿條件 – front = (rear+1) % MAXSIZE rear front 0 1 3 2MAXSIZE 1 ... 0 1 2 ... i rear i+1 front ... MAXSIZE 1 a1 a2 a3 ai 空 滿 29/53 算法 112:循環(huán)隊列入隊算法 ? step1 判別隊列是否已滿 。 ? step2 隊尾指針后移一個位置 ,將新結(jié)點元素值存入當(dāng)前結(jié)點單元。 ? 程序 (略 ) 30/53 算法 113 循環(huán)隊列出隊算法 ? step1 判別隊列是否為空 。若空 ,則顯示‘下溢’ 。 ? step2 隊頭指針后移一個位置。 ? step3 返回隊頭元素 ? 程序 (略 ) 31/53 五 .隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu) ? 用帶頭結(jié)點的單鏈表作為隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)。 ? C語言描述 – struct qnode – { int data ； – struct qnode * next； }； – typedef struct qnode QNODE ； – QNODE *front , *rear； 32/53 鏈隊列的表示 ? 鏈隊列滿 : T = = NULL 沒有存儲空間 ? 鏈隊列空 : front = =rear ? ? 空隊列 : ? 非空隊列 : ? ? front rear NULL
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號-1