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