[其它]數(shù)據(jù)結(jié)構(gòu)第10章(編輯修改稿)
2025-02-15 10:02 本頁面
【文章內(nèi)容簡介】 容納600個(gè)記錄的空間，現(xiàn)要對該文件進(jìn)行排序，排序過程可按如下步驟進(jìn)行： ? 第一步，每次將三個(gè)頁塊（ 600個(gè)記錄）由外存讀到內(nèi)存， 進(jìn)行內(nèi)排序，整個(gè)文件共得到 6個(gè)初始順串 R1~R6 （ 每一個(gè)順串占三個(gè)頁塊），然后把它們寫回到磁盤上去，如圖 示。 第 10章 外部排序 圖 內(nèi)排序后得到的初始順串 第 10章 外部排序 第二步，將供內(nèi)排序使用的內(nèi)存緩沖區(qū)分為三塊相等的部分（即每塊可容納 200個(gè)記錄），其中兩塊作為輸入緩沖區(qū)，一塊作為輸出緩沖區(qū)，然后對各順串進(jìn)行兩路歸并。首先歸并 R1和 R2這兩個(gè)順串中各自的第一個(gè)頁塊并分別讀入到兩個(gè)緩沖區(qū)中，進(jìn)行歸并后送入輸出緩沖區(qū)。當(dāng)輸出緩沖區(qū)裝滿 200個(gè)記錄時(shí)，就把它寫回磁盤；如果歸并期間某個(gè)輸入緩沖區(qū)空了，便立即讀入同一順串中的下一個(gè)頁塊，繼續(xù)進(jìn)行歸并，此過程不斷進(jìn)行，直到順串 R1和順串 R2歸并為一個(gè)新的順串為止。這個(gè)經(jīng)歸并后的新的順串含有 1200個(gè)記錄。 第 10章 外部排序 在 R1和 R2歸并完成之后，再歸并 R3和 R4，最后歸并 R5和 R6。到此為止，完成了對整個(gè)文件的一遍掃描，這意味著文件中的每一個(gè)記錄被讀寫一次（即從磁盤上讀入內(nèi)存一次，并從內(nèi)存寫到磁盤一次）。經(jīng)一遍掃描后形成了三個(gè)順串，每個(gè)順串含有 6個(gè)頁塊（共 1200個(gè)記錄）。利用上述方法，再對這三個(gè)順串進(jìn)行歸并，即先將其中的兩個(gè)順串歸并起來，結(jié)果得到一個(gè)含有 2400個(gè)記錄的順串；然后再把該順串和剩下的另一個(gè)含有 1200個(gè)記錄的順串進(jìn)行歸并，從而得到最終的一個(gè)順串，即為所要求的排序的文件。圖。 第 10章 外部排序 圖 6個(gè)順串的歸并過程 第 10章 外部排序 從以上歸并過程可見，掃描遍數(shù)對于歸并過程所需要的時(shí)間起著關(guān)鍵的作用，在上例中，除了在內(nèi)排序形成初始順串時(shí)需作一遍掃描外，各順串的歸并還需 遍掃描 把 6個(gè)長為 600個(gè)記錄的順串歸并為 3個(gè)長為 1200個(gè)記錄的順串需要掃描一遍；把兩個(gè)長為 1200個(gè)記錄的順串歸并為一個(gè)長為2400個(gè)記錄的順串需要掃描 2/3遍 , 把一個(gè)長為 2400個(gè)記錄的順串與另一個(gè) 長為 1200個(gè)記錄的順串歸并在一起， 需要掃描一遍。 第 10章 外部排序 2. 多路歸并 圖 16個(gè)順串歸并的示例 第 10章 外部排序 圖 8路歸并程序的選擇樹 (勝方樹 ) 第 10章 外部排序 圖 勝方樹的修改 第 10章 外部排序 圖 對應(yīng)于圖 第 10章 外部排序 圖 敗方樹的修改 第 10章 外部排序 3. 初始順串的生成 假定內(nèi)存中可以存放 k個(gè)記錄及在此基礎(chǔ)上所構(gòu)成的敗方樹，并且輸入／輸出操作是通過輸入／輸出緩沖區(qū)進(jìn)行的。敗方樹方
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1