資料結(jié)構(gòu)簡(jiǎn)介課件

14.4佇列cba入口出口尾端(rear)頭端(front)cb出口尾端(rear)頭端(front)入口dcb尾端(rear)頭端(front)入口特徵：刪除新增d14.4佇列cba入口出口尾端(rear)頭端(fron24.4.1以陣列實(shí)作佇列224.4.1以陣列實(shí)作佇列234.4.1以陣列實(shí)作佇列—移動(dòng)門(ch4_queue_1.java)優(yōu)點(diǎn)：簡(jiǎn)單缺點(diǎn)：還有空位卻認(rèn)為已滿解決方法：當(dāng)有remove動(dòng)作時(shí)，搬移資料，讓剩下的所有佇列資料都由陣列索引位置0開(kāi)始

或參考4.5.5環(huán)狀佇列適用於限量服務(wù)，不適合不限量、但座位有限的服務(wù)34.4.1以陣列實(shí)作佇列—移動(dòng)門(ch4_queue_44.4.2以串列實(shí)作佇列(ch4_queue_2.java)

classNode{intdata;Nodelink;}classQueue{Nodefront;Noderear;}44.4.2以串列實(shí)作佇列(ch4_queue_2.java54.4.2以串列實(shí)作佇列(ch4_queue_2.java)範(fàn)例ch4_queue_2.java未處理54.4.2以串列實(shí)作佇列(ch4_queue_2.java64.4.2以串列實(shí)作佇列(ch4_queue_2.java)基本動(dòng)作如下：建立一個(gè)空佇列：生成front跟rear節(jié)點(diǎn)，而且兩者的link都是nullvoidadd(intdata):生成新節(jié)點(diǎn)，將data值存在此節(jié)點(diǎn)，依佇列是否為空，分別處理(第4頁(yè)投影片)intremove():刪除並傳回佇列頭端資料intgetfront():傳回頭端資料intgetrear():傳回尾端資料booleanempty():傳回佇列是否為空之布林值練習(xí)：intgetlength()：傳回長(zhǎng)度如果想以串列實(shí)作，但又要限制佇列長(zhǎng)度(最多為n)，則可以檢查getlength()是否等於n，來(lái)判斷是否佇列已滿64.4.2以串列實(shí)作佇列(ch4_queue_2.java7784.5變形堆疊和變形佇列4.5.1,4.5.2多重堆疊，多重佇列[課本這兩節(jié)跳過(guò)]課本：將一陣列切成3段，每段實(shí)作一堆疊(佇列)，當(dāng)某一堆疊(佇列)滿了，其他堆疊(佇列)還有空間時(shí)，需重新分配，處理起來(lái)太複雜。其實(shí)可以用之前設(shè)計(jì)之Stack或Queue來(lái)實(shí)作。重新設(shè)計(jì)：classThreeStack{Stacks1;Stacks2;Stacks3;ints1_max_size;//optionalints2_max_size;//optionalints3_max_size;//optionalvoidpush(inti,intdata)intpop(inti)booleanfull(inti)booleanempty(inti)}classThreeQueue{Queueq1;Queueq2;Queueq3;intq1_max_size;//optionalintq2_max_size;//optionalintq3_max_size;//optionalvoidadd(inti,intdata)intremove(inti)boolanfull(inti)booleanempty(inti)}如果對(duì)堆疊容量有設(shè)限84.5變形堆疊和變形佇列4.5.1,4.5.2多重堆4.5.1,4.5.2多重堆疊，多重佇列(重新設(shè)計(jì)，補(bǔ)充)其方法(以多重堆疊為例：ch4_threestack.java)建構(gòu)子:初始化3個(gè)堆疊voidpush(inti,intdata)：新增資料data到第i個(gè)堆疊intpop(inti):由第i個(gè)堆疊取出資料(要移除)booleanfull(inti):檢查第i個(gè)堆疊是否滿了(對(duì)堆疊容量有設(shè)限時(shí)才需要)booleanempty(inti)：檢查第i個(gè)堆疊是否為空也可擴(kuò)充為可變長(zhǎng)度之多重堆疊(ch4_MultiStack.java)建構(gòu)子：以整數(shù)陣列代表需要新增的堆疊的各個(gè)長(zhǎng)度限制94.5.1,4.5.2多重堆疊，多重佇列(重新設(shè)計(jì)，補(bǔ)充104.5.3優(yōu)先佇列課本作法1：將一陣列切成3段，每段實(shí)作一佇列，由左到右分級(jí)課本作法2：以鍊結(jié)串列104.5.3優(yōu)先佇列課本作法1：將一陣列切成3段，114.5.3優(yōu)先佇列(補(bǔ)充)重新設(shè)計(jì):視為一個(gè)佇列，由3個(gè)佇列實(shí)作，新增時(shí)可設(shè)定要加入第幾個(gè)佇列。移除時(shí)會(huì)由q1,q2,q3依續(xù)移除classPriorityQueue{Queueq1;Queueq2;Queueq3;intq1_max_size;intq2_max_size;intq3_max_size;voidadd(inti,intdata)intremove()boolanfull()booleanempty()}常用於服務(wù)有分等級(jí)時(shí)，例如q1為頭等艙旅客，q2為商務(wù)艙旅客，q3為經(jīng)濟(jì)艙旅客。add表示旅客到達(dá)櫃臺(tái)排隊(duì)。remove表示請(qǐng)排在最前面旅客到櫃臺(tái)接受服務(wù)(但需依照等級(jí))練習(xí)：請(qǐng)畫(huà)出經(jīng)過(guò)以下動(dòng)作後，各佇列內(nèi)容：add(1,1)、add(2,2)、add(3,3)、add(2,4)、remove()、remove()、remove()、add(1,5)、remove()114.5.3優(yōu)先佇列(補(bǔ)充)重新設(shè)計(jì):視為一個(gè)佇列，124.5.4雙向佇列(DQueue)課本：將一個(gè)陣列切成2半重新設(shè)計(jì)classDQueue{Queueq1;Queueq2;intmax_size;//兩個(gè)佇列長(zhǎng)度和voidadd(inti,intdata)intremove(inti)boolanfull()booleanempty(){returnq1.empty()&&q2.empty();}}124.5.4雙向佇列(DQueue)課本：將一個(gè)陣列切134.5.5以陣列實(shí)作環(huán)狀佇列(ch4_cqueue.java)4.4.1

以陣列實(shí)作佇列的缺點(diǎn)改進(jìn)的想法：當(dāng)有remove動(dòng)作時(shí)，搬移資料，讓剩下的所有佇列資料都由陣列索引位置0開(kāi)始(作業(yè))將陣列的頭尾相接，以利用空出來(lái)的位置134.5.5以陣列實(shí)作環(huán)狀佇列(ch4_cqueue.ja4.5.5環(huán)狀佇列(ch4_cqueue.java)144.5.5環(huán)狀佇列(ch4_cqueue.java)144.5.5環(huán)狀佇列154.5.5環(huán)狀佇列151616練習(xí)為了使用陣列來(lái)實(shí)作不限量、但座位有限的佇列服務(wù)，請(qǐng)改進(jìn)ch4_queue_1.java還有空位卻認(rèn)為已滿的缺點(diǎn)，當(dāng)有remove動(dòng)作時(shí)，搬移陣列資料，讓剩下的所有佇列資料都由陣列索引位置0開(kāi)始(由於以上這個(gè)特性，這樣的佇列不需要front)。請(qǐng)改寫(xiě)ch4_queue_1.java所有方法，並加以測(cè)試。請(qǐng)以堆疊陣列完成可變長(zhǎng)度之多重堆疊的相關(guān)方法，並加以測(cè)試完成優(yōu)先佇列的相關(guān)方法，並加以測(cè)試17練習(xí)為了使用陣列來(lái)實(shí)作不限量、但座位有限的佇列服務(wù)，請(qǐng)改進(jìn)184.4佇列cba入口出口尾端(rear)頭端(front)cb出口尾端(rear)頭端(front)入口dcb尾端(rear)頭端(front)入口特徵：刪除新增d14.4佇列cba入口出口尾端(rear)頭端(fron194.4.1以陣列實(shí)作佇列1924.4.1以陣列實(shí)作佇列2204.4.1以陣列實(shí)作佇列—移動(dòng)門(ch4_queue_1.java)優(yōu)點(diǎn)：簡(jiǎn)單缺點(diǎn)：還有空位卻認(rèn)為已滿解決方法：當(dāng)有remove動(dòng)作時(shí)，搬移資料，讓剩下的所有佇列資料都由陣列索引位置0開(kāi)始

或參考4.5.5環(huán)狀佇列適用於限量服務(wù)，不適合不限量、但座位有限的服務(wù)34.4.1以陣列實(shí)作佇列—移動(dòng)門(ch4_queue_214.4.2以串列實(shí)作佇列(ch4_queue_2.java)

classNode{intdata;Nodelink;}classQueue{Nodefront;Noderear;}44.4.2以串列實(shí)作佇列(ch4_queue_2.java224.4.2以串列實(shí)作佇列(ch4_queue_2.java)範(fàn)例ch4_queue_2.java未處理54.4.2以串列實(shí)作佇列(ch4_queue_2.java234.4.2以串列實(shí)作佇列(ch4_queue_2.java)基本動(dòng)作如下：建立一個(gè)空佇列：生成front跟rear節(jié)點(diǎn)，而且兩者的link都是nullvoidadd(intdata):生成新節(jié)點(diǎn)，將data值存在此節(jié)點(diǎn)，依佇列是否為空，分別處理(第4頁(yè)投影片)intremove():刪除並傳回佇列頭端資料intgetfront():傳回頭端資料intgetrear():傳回尾端資料booleanempty():傳回佇列是否為空之布林值練習(xí)：intgetlength()：傳回長(zhǎng)度如果想以串列實(shí)作，但又要限制佇列長(zhǎng)度(最多為n)，則可以檢查getlength()是否等於n，來(lái)判斷是否佇列已滿64.4.2以串列實(shí)作佇列(ch4_queue_2.java247254.5變形堆疊和變形佇列4.5.1,4.5.2多重堆疊，多重佇列[課本這兩節(jié)跳過(guò)]課本：將一陣列切成3段，每段實(shí)作一堆疊(佇列)，當(dāng)某一堆疊(佇列)滿了，其他堆疊(佇列)還有空間時(shí)，需重新分配，處理起來(lái)太複雜。其實(shí)可以用之前設(shè)計(jì)之Stack或Queue來(lái)實(shí)作。重新設(shè)計(jì)：classThreeStack{Stacks1;Stacks2;Stacks3;ints1_max_size;//optionalints2_max_size;//optionalints3_max_size;//optionalvoidpush(inti,intdata)intpop(inti)booleanfull(inti)booleanempty(inti)}classThreeQueue{Queueq1;Queueq2;Queueq3;intq1_max_size;//optionalintq2_max_size;//optionalintq3_max_size;//optionalvoidadd(inti,intdata)intremove(inti)boolanfull(inti)booleanempty(inti)}如果對(duì)堆疊容量有設(shè)限84.5變形堆疊和變形佇列4.5.1,4.5.2多重堆4.5.1,4.5.2多重堆疊，多重佇列(重新設(shè)計(jì)，補(bǔ)充)其方法(以多重堆疊為例：ch4_threestack.java)建構(gòu)子:初始化3個(gè)堆疊voidpush(inti,intdata)：新增資料data到第i個(gè)堆疊intpop(inti):由第i個(gè)堆疊取出資料(要移除)booleanfull(inti):檢查第i個(gè)堆疊是否滿了(對(duì)堆疊容量有設(shè)限時(shí)才需要)booleanempty(inti)：檢查第i個(gè)堆疊是否為空也可擴(kuò)充為可變長(zhǎng)度之多重堆疊(ch4_MultiStack.java)建構(gòu)子：以整數(shù)陣列代表需要新增的堆疊的各個(gè)長(zhǎng)度限制264.5.1,4.5.2多重堆疊，多重佇列(重新設(shè)計(jì)，補(bǔ)充274.5.3優(yōu)先佇列課本作法1：將一陣列切成3段，每段實(shí)作一佇列，由左到右分級(jí)課本作法2：以鍊結(jié)串列104.5.3優(yōu)先佇列課本作法1：將一陣列切成3段，284.5.3優(yōu)先佇列(補(bǔ)充)重新設(shè)計(jì):視為一個(gè)佇列，由3個(gè)佇列實(shí)作，新增時(shí)可設(shè)定要加入第幾個(gè)佇列。移除時(shí)會(huì)由q1,q2,q3依續(xù)移除classPriorityQueue{Queueq1;Queueq2;Queueq3;intq1_max_size;intq2_max_size;intq3_max_size;voidadd(inti,intdata)intremove()boolanfull()booleanempty()}常用於服務(wù)有分等級(jí)時(shí)，例如q1為頭等艙旅客，q2為商務(wù)艙旅客，q3為經(jīng)濟(jì)艙旅客。add表示旅客到達(dá)櫃臺(tái)排隊(duì)。remove表示請(qǐng)排在最前面旅客到櫃臺(tái)接受服務(wù)(但需依照等級(jí))練習(xí)：請(qǐng)畫(huà)出經(jīng)過(guò)以下動(dòng)作後，各佇列內(nèi)容：add(1,1)、add(2,2)、add(3,3)、add(2,4)、remove()、remove()、remove()、add(1,5)、remove()114.5.3優(yōu)先佇列(補(bǔ)充)重新設(shè)計(jì):視為一個(gè)佇列，294.5.4雙向佇列(DQueue)課本：將一個(gè)陣列切成2半重新設(shè)計(jì)classDQueue{Queueq1;Queueq2;intmax