《計(jì)算機(jī)科學(xué)導(dǎo)論》PPT配套課件

《計(jì)算機(jī)科學(xué)導(dǎo)論》PPT配套課件,計(jì)算機(jī)科學(xué)導(dǎo)論,計(jì)算機(jī)科學(xué),導(dǎo)論,PPT,配套,課件 第第1313章章 文件結(jié)構(gòu)文件結(jié)構(gòu)本章內(nèi)容安排本章內(nèi)容安排&存取方法存取方法&順序文件順序文件&索引文件索引文件&散列文件散列文件&目錄目錄&文本文件與二進(jìn)制文件文本文件與二進(jìn)制文件2文件概述文件概述&文件文件是作為一個(gè)單元看待的相關(guān)數(shù)據(jù)的外部集合，是作為一個(gè)單元看待的相關(guān)數(shù)據(jù)的外部集合，文件主要目的是文件主要目的是存儲(chǔ)數(shù)據(jù)存儲(chǔ)數(shù)據(jù)。&計(jì)算機(jī)關(guān)閉時(shí)，主存中的內(nèi)容將丟失，需要使用計(jì)算機(jī)關(guān)閉時(shí)，主存中的內(nèi)容將丟失，需要使用文件這種永久的方式來(lái)存儲(chǔ)數(shù)據(jù)。文件這種永久的方式來(lái)存儲(chǔ)數(shù)據(jù)。&數(shù)據(jù)的集合可能非常大，不能一次全部駐留內(nèi)存，數(shù)據(jù)的集合可能非常大，不能一次全部駐留內(nèi)存，必須能夠讀寫(xiě)部分?jǐn)?shù)據(jù)。必須能夠讀寫(xiě)部分?jǐn)?shù)據(jù)。3文件概述文件概述&文件通常存儲(chǔ)在文件通常存儲(chǔ)在輔助存儲(chǔ)設(shè)備輔助存儲(chǔ)設(shè)備(或二級(jí)存儲(chǔ)設(shè)備或二級(jí)存儲(chǔ)設(shè)備)中，中，常見(jiàn)的存儲(chǔ)設(shè)備有磁盤(pán)和磁帶，這些設(shè)備是可讀寫(xiě)常見(jiàn)的存儲(chǔ)設(shè)備有磁盤(pán)和磁帶，這些設(shè)備是可讀寫(xiě)的。的。&文件也可以以計(jì)算機(jī)只能寫(xiě)不能讀的形式存在，文件也可以以計(jì)算機(jī)只能寫(xiě)不能讀的形式存在，如系統(tǒng)在監(jiān)視器上顯示信息。從廣義的角度看，鍵如系統(tǒng)在監(jiān)視器上顯示信息。從廣義的角度看，鍵盤(pán)也是文件，鍵盤(pán)只能讀不能寫(xiě)。盤(pán)也是文件，鍵盤(pán)只能讀不能寫(xiě)。&還可以把文件看成還可以把文件看成數(shù)據(jù)記錄的集合數(shù)據(jù)記錄的集合，而每一個(gè)記，而每一個(gè)記錄由一個(gè)或多個(gè)域組成。錄由一個(gè)或多個(gè)域組成。4存取方法存取方法&設(shè)計(jì)文件的關(guān)鍵在于將來(lái)如何從文件中檢索信息設(shè)計(jì)文件的關(guān)鍵在于將來(lái)如何從文件中檢索信息(特定的記錄特定的記錄)。常用的檢索方法有順序檢索和隨機(jī)。常用的檢索方法有順序檢索和隨機(jī)檢索，它們是由存取方法決定的。檢索，它們是由存取方法決定的。順序存取方法順序存取方法順序存取方法順序存取方法：如果需要順序存取文件：如果需要順序存取文件：如果需要順序存取文件：如果需要順序存取文件(從頭到尾，逐條從頭到尾，逐條從頭到尾，逐條從頭到尾，逐條記錄處理記錄處理記錄處理記錄處理)，則使用，則使用，則使用，則使用順序存取文件結(jié)構(gòu)順序存取文件結(jié)構(gòu)順序存取文件結(jié)構(gòu)順序存取文件結(jié)構(gòu)。隨機(jī)存取方法隨機(jī)存取方法隨機(jī)存取方法隨機(jī)存取方法：想存取某一特定記錄而不用檢索之前的：想存取某一特定記錄而不用檢索之前的：想存取某一特定記錄而不用檢索之前的：想存取某一特定記錄而不用檢索之前的所有記錄，則用所有記錄，則用所有記錄，則用所有記錄，則用隨機(jī)存取文件結(jié)構(gòu)隨機(jī)存取文件結(jié)構(gòu)隨機(jī)存取文件結(jié)構(gòu)隨機(jī)存取文件結(jié)構(gòu)。5文件結(jié)構(gòu)分類(lèi)文件結(jié)構(gòu)分類(lèi)6本章內(nèi)容安排本章內(nèi)容安排&存取方法存取方法&順序文件順序文件&索引文件索引文件&散列文件散列文件&目錄目錄&文本文件與二進(jìn)制文件文本文件與二進(jìn)制文件71、順序文件、順序文件&順序文件順序文件是指其記錄只能按照順序從頭到尾一個(gè)是指其記錄只能按照順序從頭到尾一個(gè)接一個(gè)地進(jìn)行存取。記錄被一個(gè)接一個(gè)地存儲(chǔ)到輔接一個(gè)地進(jìn)行存取。記錄被一個(gè)接一個(gè)地存儲(chǔ)到輔助存儲(chǔ)器中，在所有記錄之后加上助存儲(chǔ)器中，在所有記錄之后加上EOFEOF作為文件結(jié)作為文件結(jié)束標(biāo)記。束標(biāo)記。8示例處理順序文件示例處理順序文件92、應(yīng)用、應(yīng)用&順序文件用于需要順序文件用于需要從頭到尾存取記錄從頭到尾存取記錄的應(yīng)用。如的應(yīng)用。如公司員工的個(gè)人資料存儲(chǔ)在文件中，可以通過(guò)順序公司員工的個(gè)人資料存儲(chǔ)在文件中，可以通過(guò)順序存取檢索每條記錄來(lái)打印工資，此時(shí)更加簡(jiǎn)潔高效。存取檢索每條記錄來(lái)打印工資，此時(shí)更加簡(jiǎn)潔高效。&問(wèn)題：順序文件問(wèn)題：順序文件隨機(jī)檢索效率非常低隨機(jī)檢索效率非常低。假如銀行。假如銀行客戶(hù)記錄只能被順序存取，要想從取款機(jī)提款，必客戶(hù)記錄只能被順序存取，要想從取款機(jī)提款，必須從頭到尾檢索所有記錄直到找到該客戶(hù)，效率當(dāng)須從頭到尾檢索所有記錄直到找到該客戶(hù)，效率當(dāng)然低下。然低下。103、更新順序文件、更新順序文件&順序文件的更新非常麻煩，涉及四個(gè)文件順序文件的更新非常麻煩，涉及四個(gè)文件 新主文件新主文件新主文件新主文件：新的永久數(shù)據(jù)文件；：新的永久數(shù)據(jù)文件；：新的永久數(shù)據(jù)文件；：新的永久數(shù)據(jù)文件；舊主文件舊主文件舊主文件舊主文件：需要更新的永久文件，更新后該文件繼續(xù)保：需要更新的永久文件，更新后該文件繼續(xù)保：需要更新的永久文件，更新后該文件繼續(xù)保：需要更新的永久文件，更新后該文件繼續(xù)保留作為參考；留作為參考；留作為參考；留作為參考；事務(wù)文件事務(wù)文件事務(wù)文件事務(wù)文件：包含對(duì)主文件要作的改變的描述。添加事務(wù)：包含對(duì)主文件要作的改變的描述。添加事務(wù)：包含對(duì)主文件要作的改變的描述。添加事務(wù)：包含對(duì)主文件要作的改變的描述。添加事務(wù)包含要添加到主文件中的數(shù)據(jù)；刪除事務(wù)標(biāo)識(shí)需要?jiǎng)h除包含要添加到主文件中的數(shù)據(jù)；刪除事務(wù)標(biāo)識(shí)需要?jiǎng)h除包含要添加到主文件中的數(shù)據(jù)；刪除事務(wù)標(biāo)識(shí)需要?jiǎng)h除包含要添加到主文件中的數(shù)據(jù)；刪除事務(wù)標(biāo)識(shí)需要?jiǎng)h除的記錄；更改事務(wù)包含對(duì)文件中特定記錄的修改。事務(wù)的記錄；更改事務(wù)包含對(duì)文件中特定記錄的修改。事務(wù)的記錄；更改事務(wù)包含對(duì)文件中特定記錄的修改。事務(wù)的記錄；更改事務(wù)包含對(duì)文件中特定記錄的修改。事務(wù)通過(guò)唯一確定記錄的通過(guò)唯一確定記錄的通過(guò)唯一確定記錄的通過(guò)唯一確定記錄的鍵鍵鍵鍵標(biāo)識(shí)。標(biāo)識(shí)。標(biāo)識(shí)。標(biāo)識(shí)。錯(cuò)誤報(bào)告文件錯(cuò)誤報(bào)告文件錯(cuò)誤報(bào)告文件錯(cuò)誤報(bào)告文件：記錄更新數(shù)據(jù)過(guò)程中的錯(cuò)誤清單。：記錄更新數(shù)據(jù)過(guò)程中的錯(cuò)誤清單。：記錄更新數(shù)據(jù)過(guò)程中的錯(cuò)誤清單。：記錄更新數(shù)據(jù)過(guò)程中的錯(cuò)誤清單。11更新順序文件過(guò)程更新順序文件過(guò)程12具體更新步驟具體更新步驟&為使更新更加有效，文件的記錄按鍵排序。為使更新更加有效，文件的記錄按鍵排序。&更新時(shí)，比較事務(wù)文件和舊主文件中的鍵，遵循更新時(shí)，比較事務(wù)文件和舊主文件中的鍵，遵循一定的規(guī)則執(zhí)行增加一定的規(guī)則執(zhí)行增加AA、刪除、刪除DD、修改、修改C C等操作。等操作。事務(wù)文件的鍵小，事務(wù)是一個(gè)增加事務(wù)事務(wù)文件的鍵小，事務(wù)是一個(gè)增加事務(wù)事務(wù)文件的鍵小，事務(wù)是一個(gè)增加事務(wù)事務(wù)文件的鍵小，事務(wù)是一個(gè)增加事務(wù)(A)(A)，將記錄追，將記錄追，將記錄追，將記錄追加到新主文件中加到新主文件中加到新主文件中加到新主文件中 如果事務(wù)文件的鍵與舊主文件的相同。如果事務(wù)文件的鍵與舊主文件的相同。如果事務(wù)文件的鍵與舊主文件的相同。如果事務(wù)文件的鍵與舊主文件的相同。11事務(wù)代碼是事務(wù)代碼是C C，修改記錄并寫(xiě)入新主文件中；，修改記錄并寫(xiě)入新主文件中；11如果代碼是如果代碼是D D，忽略該記錄（不寫(xiě)入新主文件）。，忽略該記錄（不寫(xiě)入新主文件）。如果事務(wù)文件的鍵大于舊主文件的鍵，該記錄原封不動(dòng)如果事務(wù)文件的鍵大于舊主文件的鍵，該記錄原封不動(dòng)如果事務(wù)文件的鍵大于舊主文件的鍵，該記錄原封不動(dòng)如果事務(wù)文件的鍵大于舊主文件的鍵，該記錄原封不動(dòng)寫(xiě)入新主文件寫(xiě)入新主文件寫(xiě)入新主文件寫(xiě)入新主文件13更新的圖示更新的圖示14更新出錯(cuò)的情況更新出錯(cuò)的情況&產(chǎn)生錯(cuò)誤的產(chǎn)生錯(cuò)誤的2 2種情況種情況 如果事務(wù)文件中增加事務(wù)的鍵，在舊主文件中已經(jīng)存在如果事務(wù)文件中增加事務(wù)的鍵，在舊主文件中已經(jīng)存在如果事務(wù)文件中增加事務(wù)的鍵，在舊主文件中已經(jīng)存在如果事務(wù)文件中增加事務(wù)的鍵，在舊主文件中已經(jīng)存在（鍵值相同）（鍵值相同）（鍵值相同）（鍵值相同）如果事務(wù)文件中的刪除或修改事務(wù)的鍵，在舊主文件中如果事務(wù)文件中的刪除或修改事務(wù)的鍵，在舊主文件中如果事務(wù)文件中的刪除或修改事務(wù)的鍵，在舊主文件中如果事務(wù)文件中的刪除或修改事務(wù)的鍵，在舊主文件中不存在不存在不存在不存在15本章內(nèi)容安排本章內(nèi)容安排&存取方法存取方法&順序文件順序文件&索引文件索引文件&散列文件散列文件&目錄目錄&文本文件與二進(jìn)制文件文本文件與二進(jìn)制文件16索引文件索引文件&要支持對(duì)文件的要支持對(duì)文件的隨機(jī)存取隨機(jī)存取，必須知道記錄的，必須知道記錄的地址地址(記錄在磁盤(pán)上的相對(duì)位置記錄在磁盤(pán)上的相對(duì)位置)。&用戶(hù)往往并不知道記錄的實(shí)際地址，如銀行系統(tǒng)用戶(hù)往往并不知道記錄的實(shí)際地址，如銀行系統(tǒng)中查詢(xún)客戶(hù)記錄，客戶(hù)只能給出賬號(hào)（中查詢(xún)客戶(hù)記錄，客戶(hù)只能給出賬號(hào)（鍵鍵），索引），索引文件通過(guò)建立賬號(hào)和地址的映射，實(shí)現(xiàn)文件通過(guò)建立賬號(hào)和地址的映射，實(shí)現(xiàn)隨機(jī)訪問(wèn)隨機(jī)訪問(wèn)。17索引文件示意索引文件示意18索引文件的構(gòu)成索引文件的構(gòu)成&索引文件由索引文件由數(shù)據(jù)文件數(shù)據(jù)文件和和索引索引組成，數(shù)據(jù)文件是順組成，數(shù)據(jù)文件是順序文件序文件(按記錄存儲(chǔ)數(shù)據(jù)按記錄存儲(chǔ)數(shù)據(jù))。&索引占用的空間非常少，只有兩個(gè)域，一個(gè)是記索引占用的空間非常少，只有兩個(gè)域，一個(gè)是記錄對(duì)應(yīng)的鍵，另一個(gè)是磁盤(pán)上相應(yīng)記錄的地址。錄對(duì)應(yīng)的鍵，另一個(gè)是磁盤(pán)上相應(yīng)記錄的地址。19索引文件的存取步驟索引文件的存取步驟&將整個(gè)索引都載入到內(nèi)存中（文件很?。粚⒄麄€(gè)索引都載入到內(nèi)存中（文件很?。?根據(jù)提供的鍵，搜索索引中的項(xiàng)目，一般采用高根據(jù)提供的鍵，搜索索引中的項(xiàng)目，一般采用高效的搜索算法效的搜索算法(如折半查找法如折半查找法)查找到目標(biāo)鍵；查找到目標(biāo)鍵；&提取該鍵對(duì)應(yīng)記錄的地址；提取該鍵對(duì)應(yīng)記錄的地址；&根據(jù)地址檢索數(shù)據(jù)記錄并返回給用戶(hù)。根據(jù)地址檢索數(shù)據(jù)記錄并返回給用戶(hù)。20索引文件存取示意圖索引文件存取示意圖21倒排文件倒排文件&索引文件索引文件支持多個(gè)索引支持多個(gè)索引，每個(gè)索引使用不同的鍵，每個(gè)索引使用不同的鍵，每個(gè)索引按指定的鍵排序，可實(shí)現(xiàn)按不同索引隨機(jī)每個(gè)索引按指定的鍵排序，可實(shí)現(xiàn)按不同索引隨機(jī)存取記錄。這種索引文件稱(chēng)為存取記錄。這種索引文件稱(chēng)為倒排文件倒排文件。&例如，公司職員文件可以按社會(huì)保險(xiǎn)號(hào)或者按姓例如，公司職員文件可以按社會(huì)保險(xiǎn)號(hào)或者按姓名進(jìn)行檢索。名進(jìn)行檢索。22本章內(nèi)容安排本章內(nèi)容安排&存取方法存取方法&順序文件順序文件&索引文件索引文件&散列文件散列文件&目錄目錄&文本文件與二進(jìn)制文件文本文件與二進(jìn)制文件23散列文件散列文件&索引文件中，索引是文件的一部分，通過(guò)索引將索引文件中，索引是文件的一部分，通過(guò)索引將鍵映射到地址。鍵映射到地址。&散列文件散列文件并不存儲(chǔ)鍵和地址的映射表，而通過(guò)一并不存儲(chǔ)鍵和地址的映射表，而通過(guò)一個(gè)個(gè)函數(shù)函數(shù)來(lái)完成映射，用戶(hù)給出鍵，函數(shù)根據(jù)鍵臨時(shí)來(lái)完成映射，用戶(hù)給出鍵，函數(shù)根據(jù)鍵臨時(shí)計(jì)算得出地址，再根據(jù)地址檢索記錄。計(jì)算得出地址，再根據(jù)地址檢索記錄。&哈希文件沒(méi)有索引，節(jié)省了索引的開(kāi)銷(xiāo)，但也有哈希文件沒(méi)有索引，節(jié)省了索引的開(kāi)銷(xiāo)，但也有其自身的問(wèn)題。其自身的問(wèn)題。24散列文件示意散列文件示意25散列方法散列方法&如何根據(jù)用戶(hù)給出的鍵產(chǎn)生地址的方法眾多，下如何根據(jù)用戶(hù)給出的鍵產(chǎn)生地址的方法眾多，下面介紹三種典型方法。面介紹三種典型方法。直接法直接法直接法直接法 求模法求模法求模法求模法 數(shù)字析取法數(shù)字析取法數(shù)字析取法數(shù)字析取法261、直接法、直接法&直接散列法中，鍵和地址一一對(duì)應(yīng)，直接散列法中，鍵和地址一一對(duì)應(yīng)，鍵值直接作鍵值直接作為地址為地址，要求文件必須對(duì)每個(gè)可能的鍵包含一個(gè)記，要求文件必須對(duì)每個(gè)可能的鍵包含一個(gè)記錄。錄。&直接哈希的應(yīng)用較少，但也有其優(yōu)點(diǎn)，直接哈希的應(yīng)用較少，但也有其優(yōu)點(diǎn)，它保證不它保證不會(huì)產(chǎn)生沖突會(huì)產(chǎn)生沖突(沖突是指輸入兩個(gè)不同的鍵，哈希函沖突是指輸入兩個(gè)不同的鍵，哈希函數(shù)返回相同的地址數(shù)返回相同的地址)。27直接法應(yīng)用示例直接法應(yīng)用示例&某個(gè)機(jī)構(gòu)的雇員少于某個(gè)機(jī)構(gòu)的雇員少于100100個(gè)，每個(gè)職員分配個(gè)，每個(gè)職員分配11001100的編號(hào)。的編號(hào)。如果建立如果建立如果建立如果建立100100個(gè)職員記錄的文件，可以用職員編號(hào)直接個(gè)職員記錄的文件，可以用職員編號(hào)直接個(gè)職員記錄的文件，可以用職員編號(hào)直接個(gè)職員記錄的文件，可以用職員編號(hào)直接作為記錄的地址。作為記錄的地址。作為記錄的地址。作為記錄的地址。文件大小為文件大小為文件大小為文件大小為100100個(gè)記錄，部分空間被浪費(fèi)了個(gè)記錄，部分空間被浪費(fèi)了個(gè)記錄，部分空間被浪費(fèi)了個(gè)記錄，部分空間被浪費(fèi)了&此應(yīng)用非常有限，如果用社會(huì)保險(xiǎn)號(hào)作為鍵則效此應(yīng)用非常有限，如果用社會(huì)保險(xiǎn)號(hào)作為鍵則效率低下，社會(huì)保險(xiǎn)號(hào)有率低下，社會(huì)保險(xiǎn)號(hào)有9 9位，需要位，需要999999999999999999條記錄條記錄的巨大文件；而公司的職員可能不到的巨大文件；而公司的職員可能不到100100個(gè)，只使個(gè)，只使用了其中小部分記錄，多數(shù)記錄被浪費(fèi)。應(yīng)該尋求用了其中小部分記錄，多數(shù)記錄被浪費(fèi)。應(yīng)該尋求將較大的鍵取值范圍映射到較小的地址取值范圍。將較大的鍵取值范圍映射到較小的地址取值范圍。28直接法應(yīng)用圖示直接法應(yīng)用圖示292、求模法、求模法&求模法求模法也稱(chēng)除余散列法，計(jì)算地址時(shí)，求模法用也稱(chēng)除余散列法，計(jì)算地址時(shí)，求模法用文件中的記錄數(shù)量去除鍵，將余數(shù)加文件中的記錄數(shù)量去除鍵，將余數(shù)加1 1作為地址。作為地址。address=key%list_size+1address=key%list_size+1&求模法會(huì)產(chǎn)生沖突，盡量選擇與記錄數(shù)量接近的求模法會(huì)產(chǎn)生沖突，盡量選擇與記錄數(shù)量接近的素?cái)?shù)作為除數(shù)，相對(duì)會(huì)產(chǎn)生更少的沖突。素?cái)?shù)作為除數(shù)，相對(duì)會(huì)產(chǎn)生更少的沖突。30求模法應(yīng)用示例求模法應(yīng)用示例&如果公司擴(kuò)大了，發(fā)現(xiàn)雇員很快將超過(guò)如果公司擴(kuò)大了，發(fā)現(xiàn)雇員很快將超過(guò)100100名，長(zhǎng)名，長(zhǎng)遠(yuǎn)起見(jiàn)，創(chuàng)建一個(gè)編號(hào)系統(tǒng)可以容納遠(yuǎn)起見(jiàn)，創(chuàng)建一個(gè)編號(hào)系統(tǒng)可以容納100100萬(wàn)名雇員萬(wàn)名雇員的編號(hào)系統(tǒng)，而實(shí)際只提供可以容量的編號(hào)系統(tǒng)，而實(shí)際只提供可以容量300300名雇員的名雇員的數(shù)據(jù)空間，沒(méi)必要如直接散列法那樣創(chuàng)建含數(shù)據(jù)空間，沒(méi)必要如直接散列法那樣創(chuàng)建含100100萬(wàn)萬(wàn)條記錄的文件。條記錄的文件。&實(shí)際選擇實(shí)際選擇307(307(大于大于300300的第一個(gè)素?cái)?shù)的第一個(gè)素?cái)?shù))。則某個(gè)雇員。則某個(gè)雇員對(duì)應(yīng)記錄的地址為：對(duì)應(yīng)記錄的地址為：雇員編號(hào)雇員編號(hào)%307+1%307+131求模法應(yīng)用示例求模法應(yīng)用示例323、數(shù)字析取法、數(shù)字析取法&如果鍵的取值較大，可以從鍵中析取部分?jǐn)?shù)字作如果鍵的取值較大，可以從鍵中析取部分?jǐn)?shù)字作為地址。如為地址。如6 6位員工編號(hào)，我們可以從該數(shù)值中析位員工編號(hào)，我們可以從該數(shù)值中析取取3 3位位(如選擇第如選擇第1 1、第、第3 3和第和第4 4位數(shù)字作為地址位數(shù)字作為地址)，構(gòu)，構(gòu)造造09990999的地址空間。的地址空間。125870 158125870 158122801 128122801 128121267 112121267 112、33沖突的概念沖突的概念&通常情況下，通常情況下，鍵的數(shù)量鍵的數(shù)量比數(shù)據(jù)文件中的比數(shù)據(jù)文件中的記錄數(shù)量記錄數(shù)量要多。會(huì)導(dǎo)致哈希文件中有多個(gè)鍵散射為同一個(gè)地要多。會(huì)導(dǎo)致哈希文件中有多個(gè)鍵散射為同一個(gè)地址。我們把映射為同一地址的鍵稱(chēng)為址。我們把映射為同一地址的鍵稱(chēng)為同義詞同義詞。34沖突的概念沖突的概念&如果插入列表的實(shí)際數(shù)據(jù)中存在兩個(gè)或多個(gè)同義如果插入列表的實(shí)際數(shù)據(jù)中存在兩個(gè)或多個(gè)同義詞，將會(huì)產(chǎn)生詞，將會(huì)產(chǎn)生沖突沖突。沖突的產(chǎn)生是在散列算法為鍵。沖突的產(chǎn)生是在散列算法為鍵值產(chǎn)生地址時(shí)，發(fā)現(xiàn)該地址已經(jīng)被占用。值產(chǎn)生地址時(shí)，發(fā)現(xiàn)該地址已經(jīng)被占用。&由散列算法產(chǎn)生的地址稱(chēng)為由散列算法產(chǎn)生的地址稱(chēng)為內(nèi)部（起始）地址內(nèi)部（起始）地址，包含所有內(nèi)部地址記錄的文件區(qū)域稱(chēng)為包含所有內(nèi)部地址記錄的文件區(qū)域稱(chēng)為主區(qū)主區(qū)。&當(dāng)兩個(gè)鍵在內(nèi)部地址上沖突時(shí)，必須將其中的一當(dāng)兩個(gè)鍵在內(nèi)部地址上沖突時(shí)，必須將其中的一個(gè)記錄保存到另一個(gè)地址單元中。個(gè)記錄保存到另一個(gè)地址單元中。35沖突的解決沖突的解決&除了直接法，其他方法沒(méi)有建立鍵和地址的一一除了直接法，其他方法沒(méi)有建立鍵和地址的一一對(duì)應(yīng)關(guān)系，存取數(shù)據(jù)時(shí)可能會(huì)產(chǎn)生沖突。對(duì)應(yīng)關(guān)系，存取數(shù)據(jù)時(shí)可能會(huì)產(chǎn)生沖突。&常用的解決沖突方法下面幾種，解決沖突方法與常用的解決沖突方法下面幾種，解決沖突方法與散列算法無(wú)關(guān)。散列算法無(wú)關(guān)。開(kāi)放尋址開(kāi)放尋址開(kāi)放尋址開(kāi)放尋址 鏈表解決法鏈表解決法鏈表解決法鏈表解決法 桶哈希法桶哈希法桶哈希法桶哈希法 組合方法組合方法組合方法組合方法361、開(kāi)放尋址、開(kāi)放尋址&當(dāng)沖突發(fā)生時(shí)，將在主區(qū)地址中當(dāng)沖突發(fā)生時(shí)，將在主區(qū)地址中查找開(kāi)放的或空查找開(kāi)放的或空閑的記錄來(lái)存放新數(shù)據(jù)閑的記錄來(lái)存放新數(shù)據(jù)。&對(duì)于不能在內(nèi)部地址中存放的數(shù)據(jù)，一種簡(jiǎn)單的對(duì)于不能在內(nèi)部地址中存放的數(shù)據(jù)，一種簡(jiǎn)單的策略就是把它們存儲(chǔ)在下一個(gè)地址中策略就是把它們存儲(chǔ)在下一個(gè)地址中(起始地址起始地址+1)+1)，如果該地址也被占用，繼續(xù)往下順延。，如果該地址也被占用，繼續(xù)往下順延。&問(wèn)題：每個(gè)沖突的解決增加了將來(lái)產(chǎn)生沖突的可問(wèn)題：每個(gè)沖突的解決增加了將來(lái)產(chǎn)生沖突的可能性。能性。37開(kāi)放尋址示意開(kāi)放尋址示意382、鏈表解決法、鏈表解決法&鏈表解決法鏈表解決法克服了開(kāi)放尋址的缺點(diǎn)。將第一條記克服了開(kāi)放尋址的缺點(diǎn)。將第一條記錄存儲(chǔ)在起始地址中，但包含了一個(gè)指向下一條記錄存儲(chǔ)在起始地址中，但包含了一個(gè)指向下一條記錄錄(沖突的記錄沖突的記錄)的指針，沖突的記錄存儲(chǔ)在專(zhuān)門(mén)開(kāi)的指針，沖突的記錄存儲(chǔ)在專(zhuān)門(mén)開(kāi)辟的辟的溢出區(qū)溢出區(qū)。393、桶散列法、桶散列法&另一種解決沖突的方法是散列到桶，每個(gè)桶是能另一種解決沖突的方法是散列到桶，每個(gè)桶是能容納多個(gè)記錄的節(jié)點(diǎn)。將產(chǎn)生沖突的多個(gè)鍵映射到容納多個(gè)記錄的節(jié)點(diǎn)。將產(chǎn)生沖突的多個(gè)鍵映射到桶中不同的記錄上。缺點(diǎn)是可能會(huì)浪費(fèi)很多空間。桶中不同的記錄上。缺點(diǎn)是可能會(huì)浪費(fèi)很多空間。40本章內(nèi)容安排本章內(nèi)容安排&存取方法存取方法&順序文件順序文件&索引文件索引文件&散列文件散列文件&目錄目錄&文本文件與二進(jìn)制文件文本文件與二進(jìn)制文件41目錄的概念目錄的概念&目錄目錄是大多數(shù)操作系統(tǒng)提供的，用來(lái)組織是大多數(shù)操作系統(tǒng)提供的，用來(lái)組織文件文件。&目錄類(lèi)似檔案柜中的文件夾。對(duì)多數(shù)操作系統(tǒng)來(lái)目錄類(lèi)似檔案柜中的文件夾。對(duì)多數(shù)操作系統(tǒng)來(lái)說(shuō)，目錄表示為含有其他文件信息的說(shuō)，目錄表示為含有其他文件信息的特殊文件特殊文件。功能上類(lèi)似功能上類(lèi)似功能上類(lèi)似功能上類(lèi)似索引索引索引索引文件，告訴操作系統(tǒng)文件在輔助存儲(chǔ)設(shè)文件，告訴操作系統(tǒng)文件在輔助存儲(chǔ)設(shè)文件，告訴操作系統(tǒng)文件在輔助存儲(chǔ)設(shè)文件，告訴操作系統(tǒng)文件在輔助存儲(chǔ)設(shè)備上的位置；備上的位置；備上的位置；備上的位置；還包含了所含文件的其他還包含了所含文件的其他還包含了所含文件的其他還包含了所含文件的其他信息信息信息信息：如訪問(wèn)權(quán)限、文件的創(chuàng)：如訪問(wèn)權(quán)限、文件的創(chuàng)：如訪問(wèn)權(quán)限、文件的創(chuàng)：如訪問(wèn)權(quán)限、文件的創(chuàng)建和修改日期等建和修改日期等建和修改日期等建和修改日期等 多數(shù)系統(tǒng)中，目錄被組織為類(lèi)似樹(shù)的抽象數(shù)據(jù)類(lèi)型。多數(shù)系統(tǒng)中，目錄被組織為類(lèi)似樹(shù)的抽象數(shù)據(jù)類(lèi)型。多數(shù)系統(tǒng)中，目錄被組織為類(lèi)似樹(shù)的抽象數(shù)據(jù)類(lèi)型。多數(shù)系統(tǒng)中，目錄被組織為類(lèi)似樹(shù)的抽象數(shù)據(jù)類(lèi)型。42UNIX系統(tǒng)的目錄示例系統(tǒng)的目錄示例43UNIX中的目錄中的目錄&特殊目錄特殊目錄 根目錄根目錄根目錄根目錄：文件系統(tǒng)層次結(jié)構(gòu)的最高層，是整個(gè)文件結(jié)構(gòu)：文件系統(tǒng)層次結(jié)構(gòu)的最高層，是整個(gè)文件結(jié)構(gòu)：文件系統(tǒng)層次結(jié)構(gòu)的最高層，是整個(gè)文件結(jié)構(gòu)：文件系統(tǒng)層次結(jié)構(gòu)的最高層，是整個(gè)文件結(jié)構(gòu)的根，它沒(méi)有父目錄的根，它沒(méi)有父目錄的根，它沒(méi)有父目錄的根，它沒(méi)有父目錄 主目錄主目錄主目錄主目錄：針對(duì)每個(gè)用戶(hù)設(shè)置：針對(duì)每個(gè)用戶(hù)設(shè)置：針對(duì)每個(gè)用戶(hù)設(shè)置：針對(duì)每個(gè)用戶(hù)設(shè)置1 1個(gè)主目錄，主目錄是用戶(hù)個(gè)主目錄，主目錄是用戶(hù)個(gè)主目錄，主目錄是用戶(hù)個(gè)主目錄，主目錄是用戶(hù)個(gè)人目錄結(jié)構(gòu)的開(kāi)始位置；用戶(hù)登錄系統(tǒng)時(shí)，使用對(duì)應(yīng)個(gè)人目錄結(jié)構(gòu)的開(kāi)始位置；用戶(hù)登錄系統(tǒng)時(shí)，使用對(duì)應(yīng)個(gè)人目錄結(jié)構(gòu)的開(kāi)始位置；用戶(hù)登錄系統(tǒng)時(shí)，使用對(duì)應(yīng)個(gè)人目錄結(jié)構(gòu)的開(kāi)始位置；用戶(hù)登錄系統(tǒng)時(shí)，使用對(duì)應(yīng)用戶(hù)的主目錄作為工作目錄用戶(hù)的主目錄作為工作目錄用戶(hù)的主目錄作為工作目錄用戶(hù)的主目錄作為工作目錄 工作目錄工作目錄工作目錄工作目錄：用戶(hù)工作的當(dāng)前目錄，首次登錄后，工作目：用戶(hù)工作的當(dāng)前目錄，首次登錄后，工作目：用戶(hù)工作的當(dāng)前目錄，首次登錄后，工作目：用戶(hù)工作的當(dāng)前目錄，首次登錄后，工作目錄是用戶(hù)的主目錄，可以在使用過(guò)程中修改目錄，工作錄是用戶(hù)的主目錄，可以在使用過(guò)程中修改目錄，工作錄是用戶(hù)的主目錄，可以在使用過(guò)程中修改目錄，工作錄是用戶(hù)的主目錄，可以在使用過(guò)程中修改目錄，工作目錄隨之改變目錄隨之改變目錄隨之改變目錄隨之改變 父目錄父目錄父目錄父目錄：工作目錄的直接上層目錄。：工作目錄的直接上層目錄。：工作目錄的直接上層目錄。：工作目錄的直接上層目錄。44路徑和路徑名路徑和路徑名&文件系統(tǒng)的每個(gè)目錄和文件都必須有一個(gè)名字文件系統(tǒng)的每個(gè)目錄和文件都必須有一個(gè)名字 在不同目錄下允許使用相同名字的文件在不同目錄下允許使用相同名字的文件在不同目錄下允許使用相同名字的文件在不同目錄下允許使用相同名字的文件 要唯一標(biāo)識(shí)一個(gè)文件，必須要指明從根目錄到文件的文要唯一標(biāo)識(shí)一個(gè)文件，必須要指明從根目錄到文件的文要唯一標(biāo)識(shí)一個(gè)文件，必須要指明從根目錄到文件的文要唯一標(biāo)識(shí)一個(gè)文件，必須要指明從根目錄到文件的文件路徑，從根開(kāi)始的路徑為件路徑，從根開(kāi)始的路徑為件路徑，從根開(kāi)始的路徑為件路徑，從根開(kāi)始的路徑為絕對(duì)路徑名絕對(duì)路徑名絕對(duì)路徑名絕對(duì)路徑名，它是用，它是用，它是用，它是用“/”/”分隔的所有目錄的列表分隔的所有目錄的列表分隔的所有目錄的列表分隔的所有目錄的列表 絕對(duì)路徑名可能會(huì)很長(zhǎng)，在特定環(huán)境下，可以使用相對(duì)絕對(duì)路徑名可能會(huì)很長(zhǎng)，在特定環(huán)境下，可以使用相對(duì)絕對(duì)路徑名可能會(huì)很長(zhǎng)，在特定環(huán)境下，可以使用相對(duì)絕對(duì)路徑名可能會(huì)很長(zhǎng)，在特定環(huán)境下，可以使用相對(duì)于工作目錄的路徑名（于工作目錄的路徑名（于工作目錄的路徑名（于工作目錄的路徑名（相對(duì)路徑名相對(duì)路徑名相對(duì)路徑名相對(duì)路徑名）標(biāo)識(shí)文件。）標(biāo)識(shí)文件。）標(biāo)識(shí)文件。）標(biāo)識(shí)文件。假設(shè)工作目錄為假設(shè)工作目錄為/usr/staff/joan/usr/staff/joan，標(biāo)識(shí)其下的，標(biāo)識(shí)其下的file3file3相對(duì)路徑：相對(duì)路徑：joan/file3joan/file3絕對(duì)路徑：絕對(duì)路徑：/usr/staff/joan/file3/usr/staff/joan/file345本章內(nèi)容安排本章內(nèi)容安排&存取方法存取方法&順序文件順序文件&索引文件索引文件&散列文件散列文件&目錄目錄&文本文件與二進(jìn)制文件文本文件與二進(jìn)制文件46文本文件和二進(jìn)制文件文本文件和二進(jìn)制文件&存儲(chǔ)在存儲(chǔ)設(shè)備上的文件是存儲(chǔ)在存儲(chǔ)設(shè)備上的文件是位的序列位的序列，它們可以，它們可以被應(yīng)用程序翻譯成被應(yīng)用程序翻譯成文本文件文本文件或或二進(jìn)制文件二進(jìn)制文件。不同的。不同的文件格式對(duì)內(nèi)容的解釋是不同的。文件格式對(duì)內(nèi)容的解釋是不同的。47文本文件文本文件&文本文件是字符文件。在它們的內(nèi)存儲(chǔ)器格式中文本文件是字符文件。在它們的內(nèi)存儲(chǔ)器格式中不能包含整數(shù)、浮點(diǎn)數(shù)或其它不能包含整數(shù)、浮點(diǎn)數(shù)或其它數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)。要存儲(chǔ)這。要存儲(chǔ)這些類(lèi)型數(shù)據(jù)，必須要把它們轉(zhuǎn)換成對(duì)應(yīng)的字符格式，些類(lèi)型數(shù)據(jù)，必須要把它們轉(zhuǎn)換成對(duì)應(yīng)的字符格式，按字符存儲(chǔ)。按字符存儲(chǔ)。&如要存儲(chǔ)浮點(diǎn)數(shù)如要存儲(chǔ)浮點(diǎn)數(shù)3.14153.1415，必須轉(zhuǎn)換為，必須轉(zhuǎn)換為3 3、.、1 1、4 4、1 1、5 5六個(gè)字符再存儲(chǔ)六個(gè)字符再存儲(chǔ)48二進(jìn)制文件二進(jìn)制文件&二進(jìn)制文件是用二進(jìn)制文件是用計(jì)算機(jī)內(nèi)部格式存儲(chǔ)的數(shù)據(jù)集合計(jì)算機(jī)內(nèi)部格式存儲(chǔ)的數(shù)據(jù)集合，數(shù)據(jù)可以是整型、浮點(diǎn)型、字符型或其它數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)可以是整型、浮點(diǎn)型、字符型或其它數(shù)據(jù)結(jié)構(gòu)。&3.14153.1415在內(nèi)存中按在內(nèi)存中按IEEEIEEE標(biāo)準(zhǔn)存儲(chǔ)，可能占用標(biāo)準(zhǔn)存儲(chǔ)，可能占用4 4個(gè)字個(gè)字節(jié)，要將其存入二進(jìn)制文件時(shí)，把節(jié)，要將其存入二進(jìn)制文件時(shí)，把3232位原封不動(dòng)存位原封不動(dòng)存入文件中。入文件中。&如果要把如果要把3.14153.1415存入文本文件，首先必須轉(zhuǎn)換為存入文本文件，首先必須轉(zhuǎn)換為6 6個(gè)字符然后再存入文件中。個(gè)字符然后再存入文件中。49