計算機(jī)數(shù)據(jù)恢復(fù)技術(shù) 課件 第1章 計算機(jī)數(shù)據(jù)恢復(fù)基礎(chǔ)

第1章

計算機(jī)數(shù)據(jù)恢復(fù)基礎(chǔ)1.1數(shù)據(jù)的表示方法

1.1.1計算機(jī)數(shù)據(jù)的含義計算機(jī)數(shù)據(jù)：

是指所有能輸入計算機(jī)并被計算機(jī)程序處理的符號的介質(zhì)的總稱，是輸入計算機(jī)后進(jìn)行處理并具有一定意義的數(shù)字、字母和模擬量等的通稱。數(shù)據(jù)（Data）需要解釋才能成為信息，要將數(shù)據(jù)轉(zhuǎn)換為信息，必須考慮幾個已知因素。所涉及的因素由數(shù)據(jù)的創(chuàng)建者和所需信息決定。元數(shù)據(jù)是用于引用有關(guān)數(shù)據(jù)的數(shù)據(jù)。元數(shù)據(jù)可以間接或直接地被指定或給定。計算機(jī)數(shù)據(jù)簡單來說就是能被計算機(jī)識別、處理且存儲在計算機(jī)設(shè)備中的數(shù)據(jù)。計算機(jī)數(shù)據(jù)涉及的領(lǐng)域有數(shù)據(jù)維護(hù)和恢復(fù)、數(shù)據(jù)安全等。1．進(jìn)位計數(shù)制我們所使用的計算機(jī)均為馮·諾依曼型計算機(jī)，且其內(nèi)部使用二進(jìn)制來表示數(shù)據(jù)。數(shù)制也稱計數(shù)制，是指用一組固定的符號和統(tǒng)一的規(guī)則來表示數(shù)值的方法。

在日常生活中，人們最常用的進(jìn)位計數(shù)制是十進(jìn)制，即按照“逢十進(jìn)一”的原則進(jìn)行計數(shù)。但在實際應(yīng)用中，常會用到其他的進(jìn)位計數(shù)制，如二進(jìn)制、八進(jìn)制、十六進(jìn)制、六十進(jìn)制等。進(jìn)位計數(shù)制的特點(diǎn)是通過一組規(guī)定的數(shù)字來表示任意的數(shù)。

例如，一個二進(jìn)制數(shù)只能用0和1來表示，一個十進(jìn)制數(shù)只能用0～9來表示，一個十六進(jìn)制數(shù)只能用0～9和A～F這16個數(shù)碼來表示。一種進(jìn)位計數(shù)制包含一組數(shù)碼和3個基本因素（基數(shù)、數(shù)位、權(quán)）。1．進(jìn)位計數(shù)制（1）數(shù)碼。一組用來表示某種進(jìn)位計數(shù)制的符號。例如，十進(jìn)制的數(shù)碼是0、1、

2、3、4、5、6、7、8、9；二進(jìn)制的數(shù)碼是0、1。（2）基數(shù)。某進(jìn)位計數(shù)制可以使用的數(shù)碼個數(shù)。例如，十進(jìn)制的基數(shù)是10，二

進(jìn)制的基數(shù)是2。（3）數(shù)位。數(shù)碼在一個數(shù)中所處的位置。（4）權(quán)。權(quán)是基數(shù)的冪，表示數(shù)碼在不同位置上的數(shù)值。

在基數(shù)為J的進(jìn)位計數(shù)制中，包含J個不同的數(shù)碼，每個數(shù)位計滿J就向高位進(jìn)1，即“逢

J進(jìn)一”。1．進(jìn)位計數(shù)制

一個數(shù)碼處在不同數(shù)位時，所表示的數(shù)值是不同的。每個數(shù)碼所表示的數(shù)值等于該數(shù)碼乘以一個與數(shù)碼所在數(shù)位有關(guān)的常數(shù)，這個常數(shù)稱為位權(quán)，簡稱權(quán)。權(quán)的大小是以基數(shù)為底，以數(shù)碼所在位置的序號為指數(shù)的整數(shù)次冪。例如，十進(jìn)制數(shù)的百分位、十分位、個位、十位、百位、千位的權(quán)依次是：10-2、10-1、100、101、102、103。一個

J進(jìn)制數(shù)(S)J按權(quán)展開的多項式和的一般表達(dá)式為：2．二進(jìn)制

二進(jìn)制是在計算機(jī)技術(shù)中被廣泛采用的一種數(shù)制。二進(jìn)制數(shù)是用0和1兩個數(shù)碼來表示的。它的基數(shù)為2，進(jìn)位規(guī)則是“逢二進(jìn)一”，借位規(guī)則是“借一當(dāng)二”。當(dāng)前的計算機(jī)系統(tǒng)使用的數(shù)制基本均為二進(jìn)制。計算機(jī)內(nèi)部采用二進(jìn)制的原因主要有以下幾點(diǎn)：（1）技術(shù)實現(xiàn)簡單。（2）運(yùn)算規(guī)則簡單。（3）適合邏輯運(yùn)算。（4）易于進(jìn)行轉(zhuǎn)換。（5）具有抗干擾能力強(qiáng)，可靠性高等優(yōu)點(diǎn)。2．二進(jìn)制

二進(jìn)制的基數(shù)為2，只有“0”和“1”兩個數(shù)碼。二進(jìn)制在計數(shù)時“逢二進(jìn)一”，第i位的權(quán)是2的i次冪。一個二進(jìn)制數(shù)展開成多項式和的表達(dá)式為：例如，（1101.011）2=1×23+1×22+0×21+1×20+0×2-1+1×2-2+1×2-3。

十六進(jìn)制的基數(shù)為16，有0、1、2、3、4、5、6、7、8、9及大寫英文字母A、B、C、D、E、F（數(shù)碼A~F對應(yīng)十進(jìn)制數(shù)分別是10~15）共16個數(shù)碼。十六進(jìn)制在計數(shù)時“逢十六進(jìn)一”，第i位上的權(quán)是16的i次冪。一個十六進(jìn)制數(shù)展開成多項式和的表達(dá)式為：2．二進(jìn)制

十進(jìn)制數(shù)、十六進(jìn)制數(shù)和二進(jìn)制數(shù)之間有著非常簡單的對應(yīng)關(guān)系。3種常用進(jìn)位計數(shù)制數(shù)的對照表如表1-1所示。十進(jìn)制數(shù)二進(jìn)制數(shù)十六進(jìn)制數(shù)十進(jìn)制數(shù)二進(jìn)制數(shù)十六進(jìn)制數(shù)00081000811191001921021010l0A3113111011B41004121l00C51015131101D61106141110E71117151111F3．進(jìn)位計數(shù)制數(shù)的相互轉(zhuǎn)換1）二進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)

若想將二進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)，只需要把二進(jìn)制數(shù)寫成按權(quán)展開多項式和的形式，再計算此表達(dá)式的和即可。例如：1101B=1×23+1×22+0×21+1×20=23+22+20=13D。

為了使進(jìn)位計數(shù)制數(shù)表述清晰、方便，常在其后面加上大寫字母加以區(qū)別：加字母B（Blnary）表示二進(jìn)制數(shù)；加字母O（Octal）表示八進(jìn)制數(shù)；加字母H（Hexadecimal）表示十六進(jìn)制數(shù)；加字母D（Decimal）或不加字母表示十進(jìn)制數(shù)。3．進(jìn)位計數(shù)制數(shù)的相互轉(zhuǎn)換2）十進(jìn)制整數(shù)轉(zhuǎn)換成二進(jìn)制整數(shù)

如果十進(jìn)制整數(shù)轉(zhuǎn)換成二進(jìn)制整數(shù)，則采用“除2取余”法。其規(guī)則：除2取余，直至商為0，再進(jìn)行倒排，即將十進(jìn)制整數(shù)除以2，得到一個商和一個余數(shù)，再將商除以2，又得到一個商和一個余數(shù)，以此類推，直至商為0，再將每次得到的余數(shù)倒序排列，就是對應(yīng)的二進(jìn)制整數(shù)。例如，將十進(jìn)制整數(shù)86轉(zhuǎn)換成二進(jìn)制整數(shù)：即86D=(k6

k5

k4

k3

k2

k1

k0)=1010110B。3．進(jìn)位計數(shù)制數(shù)的相互轉(zhuǎn)換3）十進(jìn)制小數(shù)轉(zhuǎn)換成二進(jìn)制小數(shù)

如果十進(jìn)制小數(shù)轉(zhuǎn)換成二進(jìn)制小數(shù)，則采用“乘2取整”法。其規(guī)則：乘2取整，直至小數(shù)部分為0或給定的精度，再進(jìn)行順排，即用2逐次去乘十進(jìn)制小數(shù)，將每次得到的積的整數(shù)部分按各自出現(xiàn)的先后順序依次排列，即可得到對應(yīng)的二進(jìn)制小數(shù)。

例如，將十進(jìn)制小數(shù)0.875轉(zhuǎn)換成二進(jìn)制小數(shù)：即0.875D=(k-1

k-2

k-3)=0.111B。3．進(jìn)位計數(shù)制數(shù)的相互轉(zhuǎn)換4）十六進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)

十六進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)的規(guī)則：將每一位十六進(jìn)制數(shù)改寫成等值的4位二進(jìn)制數(shù)，次序不變。

例如，將十六進(jìn)制數(shù)1CA.BH轉(zhuǎn)換成二進(jìn)制數(shù)：1CA.B000111001010.1011即1CA.BH=000111001010.1011B=111001010.1011B。3．進(jìn)位計數(shù)制數(shù)的相互轉(zhuǎn)換5）二進(jìn)制數(shù)轉(zhuǎn)換成十六進(jìn)制數(shù)將二進(jìn)制數(shù)轉(zhuǎn)換成十六進(jìn)制數(shù)的規(guī)則：（1）整數(shù)部分從最低有效位開始，以4位為一組，含最高有效位的一組不足4位時以0補(bǔ)齊，每一組二進(jìn)制數(shù)均可轉(zhuǎn)換成一個十六進(jìn)制數(shù)，各組轉(zhuǎn)換完畢后即可得到轉(zhuǎn)換后的十六進(jìn)制整數(shù)。

（2）小數(shù)部分從最高有效位開始，以4位為一組，含最低有效位的一組不足4位時以0補(bǔ)齊，每一組二進(jìn)制數(shù)均可轉(zhuǎn)換成一個十六進(jìn)制數(shù)，各組轉(zhuǎn)換完畢后即可得到轉(zhuǎn)換后的十六進(jìn)制小數(shù)。例如，將二進(jìn)制數(shù)11001111.01111B轉(zhuǎn)換成十六進(jìn)制數(shù)：

84218421.84218421

11001111.01111

C

F

.7

8即11001111.01111B=CF.78H。1.1.2數(shù)值數(shù)據(jù)在計算機(jī)中的表示方法

計算機(jī)只能識別二進(jìn)制數(shù)，而要求計算機(jī)處理的數(shù)卻種類繁多，這該怎么辦呢？在計算機(jī)中，各種形式的編碼很好地解決了數(shù)及字符等信息的表示問題。

數(shù)據(jù)可分為兩大類：數(shù)值數(shù)據(jù)和非數(shù)值數(shù)據(jù)。前者表示數(shù)量的多少；后者表示字符、漢字、圖形、圖像、聲音等數(shù)據(jù)，又稱符號數(shù)據(jù)。在計算機(jī)內(nèi)，無論哪一種數(shù)據(jù)，都以二進(jìn)制的形式來表示。1．?dāng)?shù)據(jù)的單位數(shù)據(jù)的常用單位有位、字節(jié)和字。1）位（Bit）

在計算機(jī)中，最小的數(shù)據(jù)單位是二進(jìn)制的一個數(shù)位，簡稱位（英文名稱為Bit，讀音為“比特”）。一位二進(jìn)制數(shù)只具有“0”和“1”兩個狀態(tài)。在計算機(jī)中，最直接和最基本的操作就是對二進(jìn)制位的操作。

字節(jié)（Byte，B）是計算機(jī)信息技術(shù)用于計量存儲量的一種計量單位。字節(jié)這一名詞專門用來表示8位二進(jìn)制數(shù)。

作為一個8位二進(jìn)制數(shù)，一個字節(jié)可以從00000000取值到11111111，可以表示0~255的正數(shù)，也可以表示-128～127的正、負(fù)數(shù)。總之，一個特定的字節(jié)可以代表28（即256種）不同事物中的一種。

2）字節(jié)（Byte）

在計算機(jī)中，作為一個整體被存取、傳送、處理的二進(jìn)制數(shù)串稱為一個“字”或“單元”。字通?？煞譃槿舾蓚€字節(jié)。在存儲器中，通常情況下每個單元存儲一個字。因此，每個字都是可以尋址的。字的長度用位數(shù)來表示。1．?dāng)?shù)據(jù)的單位3）字（Word）2．字長

在字中，二進(jìn)制位數(shù)的長度稱為字長。根據(jù)計算機(jī)的不同，字長有固定的和可變的兩種。固定字長，即字的長度無論在什么情況下都是固定不變的；可變字長，即其長度在一定范圍內(nèi)是可變的。

計算機(jī)的字長是指計算機(jī)一次可處理的二進(jìn)制數(shù)的長度。計算機(jī)處理數(shù)據(jù)的速率和它一次處理的信息位數(shù)以及其進(jìn)行運(yùn)算的快慢有關(guān)。如果一臺計算機(jī)的字長是另一臺計算機(jī)的兩倍，兩臺計算機(jī)的運(yùn)算速度相同，在相同的時間內(nèi)，前者能做的工作是后者的兩倍。

在微型計算機(jī)中，通常用字節(jié)來表示存儲器的存儲容量。在計算機(jī)的運(yùn)算器和控制器中，數(shù)據(jù)通常是以字為單位進(jìn)行傳送的。另外，字在不同的地址中出現(xiàn)其含義是不相同的。例如，送往控制器的字是指令，而送往運(yùn)算器的字就僅是一個數(shù)。一個字由若干個字節(jié)組成。不同計算機(jī)系統(tǒng)的字長也是不同的，常見的有8位、16位、32位、64位等。字長越長，計算機(jī)一次處理的信息位就越多，精度就越髙。字長是計算機(jī)性能的一個重要指標(biāo)。在一般情況下，大型計算機(jī)的字長為32～64位，小型計算機(jī)的字長為12～32位，而微型計算機(jī)的字長為4～16位。字長是衡量計算機(jī)性能的一個重要因素。1.1.3字符數(shù)據(jù)在計算機(jī)中的表示方法

在計算機(jī)領(lǐng)域中，數(shù)據(jù)的概念是廣義的。計算機(jī)除了處理各種數(shù)值之外，還要處理大量的符號，如英文字母和漢字等非數(shù)值信息。例如，當(dāng)要用計算機(jī)編寫文章時，就需要將文章中的各種符號、英文字母和漢字等字符輸入計算機(jī)，然后由計算機(jī)進(jìn)行編輯和排版。

計算機(jī)中的數(shù)據(jù)可以分為數(shù)值數(shù)據(jù)與非數(shù)值數(shù)據(jù)兩種。其中，數(shù)值數(shù)據(jù)就是常說的“數(shù)”（如整數(shù)、實數(shù)等），且在計算機(jī)中是以二進(jìn)制數(shù)的形式存放的；而非數(shù)值數(shù)據(jù)與一般的“數(shù)”不同，通常不表示數(shù)值大小，只表示字符或圖形等信息，但這些信息在計算機(jī)中也是以二進(jìn)制數(shù)的形式存放的。美國信息交換標(biāo)準(zhǔn)代碼（AmericanStandardCodeforInformationInterchange，ASCII）是基于拉丁字母的一套計算機(jī)編碼系統(tǒng)，也是國際通用的信息交換標(biāo)準(zhǔn)。ASCII使用指定的7位或8位二進(jìn)制數(shù)的組合來表示128種或256種可能的字符。用ASCII表示的字符稱為ASCII字符。如表1-2所示為ASCII編碼表。1.1.3字符數(shù)據(jù)在計算機(jī)中的表示方法

0000010100111001011101110000NULDELSP0@P0‘p0001SOHDC1!1AQaq0010STXDC2“2BRbr0011ETXDC3#3CSCs0100EOTDC4$4DTdt0101ENQNAK%5EUeU0110ACKSYN&6FVfV0111DELETB

7GWgW1000BSCAN（8HXhx1001HTEM）9IYiy1010LFSUB*：JZjz1011VTESC+；K[k{1100FFFS，<

L\ll1101CRGS-=M]m}1110S0RS.>

N

n-1111SIUS/?O_oDEL1.2數(shù)據(jù)的邏輯運(yùn)算

邏輯運(yùn)算又稱布爾運(yùn)算。英國的數(shù)學(xué)家布爾，在1847年發(fā)明了處理二值之間關(guān)系的邏輯數(shù)學(xué)計算法。他用等式表示判斷，把推理看成等式的變換。這種變換的有效性不依賴于人們對符號的認(rèn)識，只依賴于符號的組合規(guī)律。20世紀(jì)30年代，邏輯代數(shù)在電路系統(tǒng)中得到應(yīng)用。之后，隨著電子技術(shù)與計算機(jī)的發(fā)展，出現(xiàn)了各種復(fù)雜的系統(tǒng)。這些系統(tǒng)的變換規(guī)律也遵守布爾所揭示的規(guī)律。

邏輯運(yùn)算是CPU運(yùn)算的本質(zhì)。計算機(jī)在處理無論多么復(fù)雜的事情時，都得通過電路的開關(guān)。邏輯是指對某個事物的推理，有“真”和“假”是兩個對立的邏輯狀態(tài)。邏輯運(yùn)算是指用數(shù)學(xué)符號來表示邏輯狀態(tài)，以便于用數(shù)學(xué)方法研究邏輯問題。1.2數(shù)據(jù)的邏輯運(yùn)算

在計算機(jī)中進(jìn)行的運(yùn)算是二進(jìn)制運(yùn)算，邏輯判斷的結(jié)果只有兩個值，這兩個值稱為“邏輯值”，用數(shù)碼來表示就是“1”和“0”。其中，“1”表示該邏輯運(yùn)算的結(jié)果為“真”，“0”表示該邏輯運(yùn)算的結(jié)果為“假”。我們常將電路通電狀態(tài)表示為“真”，用數(shù)字“1”表示，不通電狀態(tài)表示為“假”，用數(shù)字“0”表示。

計算機(jī)的邏輯運(yùn)算與算術(shù)運(yùn)算的主要區(qū)別：邏輯運(yùn)算是按位進(jìn)行的，位與位之間不像加/減運(yùn)算那樣有進(jìn)位或借位的聯(lián)系。

邏輯運(yùn)算主要包括3種基本運(yùn)算：“或”運(yùn)算、“與”運(yùn)算和“非”運(yùn)算。此外，還有一種“異或”運(yùn)算也很有用。在磁盤陣列（redundantarrayofindependentdisks，簡寫為RAID）中，就會大量使用“異或”運(yùn)算作為校驗算法。1.2.1“或”運(yùn)算

“或”運(yùn)算又稱加運(yùn)算，運(yùn)算符號有“+”“V”“OR”等。

“或”邏輯是指當(dāng)輸入變量中有一個變量滿足條件時，輸出結(jié)果就有效。只有當(dāng)所有輸入變量均不滿足條件時，輸出結(jié)果才無效。

也就是說，在給定的邏輯變量中，只要有一個變量為1，其運(yùn)算結(jié)果為1；當(dāng)邏輯變量都為0時，運(yùn)算結(jié)果為0。其運(yùn)算規(guī)則如下：0+0=0，0∨0=00+1=1，0∨1=11+0=1，1∨0=11+1=1，1∨1=1例如，x=10110011、y=10011011，求x∨y。即x∨y=10111011B1.2.2“與”運(yùn)算

“與”運(yùn)算又稱乘運(yùn)算，運(yùn)算符號有“x”“^”“.”等。

“與”邏輯是指當(dāng)所有輸入變量同時滿足條件時，輸出結(jié)果才有效，否則輸出結(jié)果無效。

也就是說，只有當(dāng)參與運(yùn)算的邏輯變量同時取值為1時，其運(yùn)算結(jié)果才等于1。其運(yùn)算規(guī)則如下：0x0=0,0∧0=0,0?0=00x1=0,0∧1=0,0?1=01x0=0,1∧0=0,1?0=01x1=1,1∧1=1,1?1=1例如，x=10110011、y=10011011，求x∧y。即x∧y=10010011B1.2.3“非”運(yùn)算

“非”運(yùn)算又稱反運(yùn)算，運(yùn)算符號為在變量上畫一條橫線。

“非”邏輯是指當(dāng)輸入變量為1時，輸出結(jié)果為0；當(dāng)輸入變量為0時，輸出結(jié)果為1。也就是說，0的非為1，1的非為0。1.2.4“異或”運(yùn)算

“異或”邏輯表示兩個值不同為“真”、“相同”為假。也就是說，兩個值都為0或者1，其運(yùn)算結(jié)果為0；而一個值為0，另一個值為1，其運(yùn)算結(jié)果為1?！爱惢颉边\(yùn)算通常用符號“⊕”表示，其運(yùn)算規(guī)則如下：0⊕0=00⊕1=11⊕0=11⊕1=0例如，x=10110011、y=10011011，求x⊕y。即x⊕y=00101000B1.3數(shù)據(jù)結(jié)構(gòu)

如果想深入掌握數(shù)據(jù)恢復(fù)技術(shù)，就不能缺少對數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，因為在數(shù)據(jù)的存儲和管理中處處離不開數(shù)據(jù)結(jié)構(gòu)，如硬盤的分區(qū)結(jié)構(gòu)、文件的系統(tǒng)結(jié)構(gòu)等，都是對數(shù)據(jù)結(jié)構(gòu)的具體應(yīng)用。1.3.1數(shù)據(jù)結(jié)構(gòu)的概念與分類

數(shù)據(jù)結(jié)構(gòu)是計算機(jī)學(xué)科中的一門專業(yè)課程，更是在程序設(shè)計中不可或缺的一部分。數(shù)據(jù)結(jié)構(gòu)是計算機(jī)存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。在通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行和存儲效率。數(shù)據(jù)結(jié)構(gòu)往往與高效的檢索算法和索引技術(shù)有關(guān)。1．?dāng)?shù)據(jù)結(jié)構(gòu)的基本概念1）什么是數(shù)據(jù)

數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)是指所有能被輸入計算機(jī)，且能被計算機(jī)處理的符號（數(shù)字、字符等）的集合，是計算機(jī)操作對象的總稱。1．?dāng)?shù)據(jù)結(jié)構(gòu)的基本概念2）數(shù)據(jù)元素

數(shù)據(jù)元素是在數(shù)據(jù)集合中的一個“個體”，是數(shù)據(jù)結(jié)構(gòu)的基本單位。

數(shù)據(jù)元素有兩類，一類是不可分割的“原子”型數(shù)據(jù)元素，如數(shù)值“1”、字符“N”等；另一類是由多個款項構(gòu)成的數(shù)據(jù)元素。其中每個款項稱為一個“數(shù)據(jù)項”。

關(guān)鍵字是指能識別一個或多個數(shù)據(jù)元素的數(shù)據(jù)項。若能起唯一識別作用，則稱為“主關(guān)鍵字”，否則稱為“次關(guān)鍵字”。3）關(guān)鍵字

數(shù)據(jù)對象是具有相同特性的數(shù)據(jù)元素的集合，如整數(shù)、實數(shù)等。數(shù)據(jù)對象是數(shù)據(jù)的一個子集D。4）數(shù)據(jù)對象1．?dāng)?shù)據(jù)結(jié)構(gòu)的基本概念5）數(shù)據(jù)結(jié)構(gòu)

若特性相同的數(shù)據(jù)元素集合中的數(shù)據(jù)元素間存在一種或多種特定的關(guān)系，則該數(shù)據(jù)元素集合稱為“數(shù)據(jù)結(jié)構(gòu)”。也就是說，數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合，“結(jié)構(gòu)”即指數(shù)據(jù)元素之間存在的關(guān)系。2．?dāng)?shù)據(jù)結(jié)構(gòu)的分類1）按照數(shù)據(jù)結(jié)構(gòu)的關(guān)系分類數(shù)據(jù)結(jié)構(gòu)按照數(shù)據(jù)結(jié)構(gòu)的關(guān)系可分為線性結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu)和集合結(jié)構(gòu)。（1）線性結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)中的元素存在一對一的相互關(guān)系，如圖1-1所示。（2）樹結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)中的元素存在一對多的相互關(guān)系，如圖1-2所示。

圖1-2樹結(jié)構(gòu)

圖1-1線性結(jié)構(gòu)2．?dāng)?shù)據(jù)結(jié)構(gòu)的分類1）按照數(shù)據(jù)結(jié)構(gòu)的關(guān)系分類（3）圖結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)中的元素存在多對多的相互關(guān)系，如圖1-3所示。（4）集合結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)中的元素間除了“同屬一個集合”的相互關(guān)系外無其他關(guān)系，如圖1-4所示。

圖1-3圖結(jié)構(gòu)圖1-4集合結(jié)構(gòu)2．?dāng)?shù)據(jù)結(jié)構(gòu)的分類2）按照數(shù)據(jù)結(jié)構(gòu)的層次分類（1）邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)，可以用一個數(shù)據(jù)元素的集合來定義在此集合上的若干關(guān)系。其中，邏輯關(guān)系是指數(shù)據(jù)元素之間的前后間關(guān)系，而與其在計算機(jī)中的存儲位置無關(guān)。

（2）物理結(jié)構(gòu)又稱存儲結(jié)構(gòu)，是指數(shù)據(jù)結(jié)構(gòu)中的元素在計算機(jī)存儲空間中的存放形式。①數(shù)據(jù)元素的機(jī)內(nèi)表示：用二進(jìn)制的位串表示數(shù)據(jù)元素。

②關(guān)系的機(jī)內(nèi)表示：數(shù)據(jù)元素間關(guān)系的機(jī)內(nèi)表示可以分為順序映像和非順序映像。

一般來說，一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以根據(jù)需要表示成多種存儲結(jié)構(gòu)。常用的存儲結(jié)構(gòu)有順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、索引存儲和散列存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)的特點(diǎn)：借助數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。非順序存儲結(jié)構(gòu)的特點(diǎn)：借助指示數(shù)據(jù)元素存儲地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系。2．?dāng)?shù)據(jù)結(jié)構(gòu)的分類2）按照數(shù)據(jù)結(jié)構(gòu)的層次分類（1）順序存儲結(jié)構(gòu)：（2）鏈?zhǔn)酱鎯Y(jié)構(gòu)（3）索引存儲結(jié)構(gòu)（4）散列存儲結(jié)構(gòu)1.3.2樹結(jié)構(gòu)1.樹結(jié)構(gòu)的定義

樹結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，它是由n（n≥1）個有限節(jié)點(diǎn)組成的具有層次關(guān)系的集合。在樹結(jié)構(gòu)中，用一個圓圈表示一個節(jié)點(diǎn)，圓圈內(nèi)的符號代表該節(jié)點(diǎn)的數(shù)據(jù)信息，節(jié)點(diǎn)之間的關(guān)系通過有方向的連線表示。其方向為從上向下，即上方節(jié)點(diǎn)是下方節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，下方節(jié)點(diǎn)是上方節(jié)點(diǎn)的后繼節(jié)點(diǎn)。樹結(jié)構(gòu)（簡稱樹）看起來像一棵倒掛的樹，如下圖所示。1.3.2樹結(jié)構(gòu)2．樹結(jié)構(gòu)的基本術(shù)語

（1）節(jié)點(diǎn)

（9）堂兄弟節(jié)點(diǎn)

（2）節(jié)點(diǎn)的度

（10）祖先節(jié)點(diǎn)

（3）樹的度

（11）子孫節(jié)點(diǎn)

（4）葉節(jié)點(diǎn)（終端節(jié)點(diǎn)）

（12）節(jié)點(diǎn)的層次

（5）分支節(jié)點(diǎn)（非終端節(jié)點(diǎn)）

（13）樹的高（深）度

（6）子女節(jié)點(diǎn)

（14）有序樹

（7）雙親節(jié)點(diǎn)

（15）無序樹

（8）兄弟節(jié)點(diǎn)

（16）森林1.3.2樹結(jié)構(gòu)3．樹結(jié)構(gòu)的特點(diǎn)（1）每個節(jié)點(diǎn)有0個或多個子節(jié)點(diǎn)。（2）每個子節(jié)點(diǎn)只有一個父節(jié)點(diǎn)。（3）沒有前驅(qū)節(jié)點(diǎn)作為根節(jié)點(diǎn)。（4）除了根節(jié)點(diǎn)外，每個子節(jié)點(diǎn)可以分為m個不相交的子樹。1.3.3樹結(jié)構(gòu)1．二叉樹的定義

二叉樹是樹形結(jié)構(gòu)的一種，只要對樹的結(jié)構(gòu)加以限制就能得到二叉樹。

二叉樹是n（n≥0）個節(jié)點(diǎn)的有限集合，并且滿足下面的任意一個條件。（1）為空二叉樹，即n=0。（2）由一個根節(jié)點(diǎn)和兩個互不相交的左子樹和右子樹組成。左子樹和右子樹的順序不能任意顛倒。如圖1-6所示的（a）和（b）就是兩個完全不同的二叉樹。1.3.3樹結(jié)構(gòu)2．樹和二叉樹的區(qū)別

（1）樹的節(jié)點(diǎn)個數(shù)至少為1，而二叉樹的節(jié)點(diǎn)個數(shù)可以為0。

（2）樹節(jié)點(diǎn)對最大度數(shù)沒有限制，而二叉樹節(jié)點(diǎn)的最大度數(shù)為2。

（3）樹的節(jié)點(diǎn)無左、右之分，而二叉樹的節(jié)點(diǎn)有左、右之分。1.3.3樹結(jié)構(gòu)3．二叉樹的基本形態(tài)（1）空二叉樹，如圖1-7所示。（2）僅有根節(jié)點(diǎn)的二叉樹，如圖1-8所示。（3）右子樹為空的二叉樹，如圖1-9所示。（4）左子樹為空的二叉樹，如圖1-10所示。（5）左、右子樹均為非空的二叉樹，如圖1-11所示。

圖1-8僅有根節(jié)點(diǎn)的二叉樹

圖1-7空二叉樹

圖1-9右子樹為空的二叉樹

圖1-10左子樹為空二叉樹

圖1-11左、右子樹均為空的二叉樹1.3.3樹結(jié)構(gòu)4．二叉樹的類型

（1）滿二叉樹。滿二叉樹是指除了葉節(jié)點(diǎn)外每個節(jié)點(diǎn)都有左、右子女節(jié)點(diǎn)，且葉節(jié)點(diǎn)都處在最底層的二叉樹，如圖1-12所示。

（2）完全二叉樹。完全二叉樹是指除最后一層，每層的節(jié)點(diǎn)數(shù)均達(dá)到最大值，且在最后一層上只缺少右邊的若干節(jié)點(diǎn)的二叉樹，如圖1-13所示。

圖1-12滿二叉樹

圖1-13完全二叉樹1.3.4B樹、B-樹、B+樹和B*樹1．B樹1）B樹的定義B樹就是二叉查找樹，需要滿足下列條件。（1）所有非葉節(jié)點(diǎn)最多擁有兩個子女節(jié)點(diǎn)（左子女節(jié)點(diǎn)和右子女節(jié)點(diǎn)）。（2）所有節(jié)點(diǎn)存儲一個關(guān)鍵字。（3）非葉節(jié)點(diǎn)的左指針指向小于其關(guān)鍵字的子樹，右指針指向大于其關(guān)鍵字的子樹。如圖1-14所示的樹就是一個B樹。

圖1-14B樹

1.3.4B樹、B-樹、B+樹和B*樹1．B樹

2）B樹的查找B樹的查找是從根節(jié)點(diǎn)開始，如果查找的關(guān)鍵字與節(jié)點(diǎn)關(guān)鍵字相等，那么該節(jié)點(diǎn)關(guān)鍵字即為查找的關(guān)鍵字；如果查找的關(guān)鍵字比節(jié)點(diǎn)關(guān)鍵字小，就進(jìn)入左子女節(jié)點(diǎn)；如果查找的關(guān)鍵字比節(jié)點(diǎn)關(guān)鍵字大，就進(jìn)入右子女節(jié)點(diǎn)；如果左子女節(jié)點(diǎn)或右子女節(jié)點(diǎn)的指針為空，則報告找不到相應(yīng)的關(guān)鍵字。

1.3.4B樹、B-樹、B+樹和B*樹2．

B-樹

1）B-樹的定義

B-樹是一種平衡的多叉樹。通常，m階的B-樹必須滿足下列條件。（1）每個節(jié)點(diǎn)最多擁有m個子女節(jié)點(diǎn)。（2）除根節(jié)點(diǎn)和葉節(jié)點(diǎn)外，其他的每個節(jié)點(diǎn)至少有m/2個子女節(jié)點(diǎn)。（3）若根節(jié)點(diǎn)不是葉節(jié)點(diǎn)，則至少有兩個子女節(jié)點(diǎn)。（4）所有的葉節(jié)點(diǎn)在同一層，且葉節(jié)點(diǎn)不包含任何關(guān)鍵字信息。（5）有k個子節(jié)點(diǎn)的非終端節(jié)點(diǎn)最多包含k-1個關(guān)鍵字信息

圖1-15B-樹1.3.4B樹、B-樹、B+樹和B*樹2．

B-樹

2）B-樹的查找B-樹的查找是一個順指針查找節(jié)點(diǎn)和在節(jié)點(diǎn)內(nèi)的關(guān)鍵字中查找交叉進(jìn)行的過程。從根節(jié)點(diǎn)開始，在節(jié)點(diǎn)包含的關(guān)鍵字中查找給定的關(guān)鍵字，找到則查找成功；否則確定給定關(guān)鍵字可能存在的子樹，重復(fù)以上操作，直到查找成功或者指針為空為止。1.3.4B樹、B-樹、B+樹和B*樹2．

B-樹

3）B-樹的插入B-樹的插入首先是在恰當(dāng)?shù)娜~節(jié)點(diǎn)中添加關(guān)鍵字。如果在該節(jié)點(diǎn)中關(guān)鍵字不超過m-1個，則插入成功；否則要把這個節(jié)點(diǎn)分裂為兩個，并把中間的一個關(guān)鍵字拿出來插到節(jié)點(diǎn)的父節(jié)點(diǎn)中。當(dāng)插入父節(jié)點(diǎn)失敗時，就需要將父節(jié)點(diǎn)再分裂，繼續(xù)進(jìn)行插入操作。當(dāng)需要分裂根節(jié)點(diǎn)時，由于根節(jié)點(diǎn)沒有父節(jié)點(diǎn)，這時就需要建立一個新的根節(jié)點(diǎn)。B-樹的插入可能導(dǎo)致B-樹朝著根的方向生長。

例如，若想在如圖1-16所示的一個6階B-樹中插入關(guān)鍵字“33”，因為在最右邊的節(jié)點(diǎn)中關(guān)鍵字的個數(shù)已經(jīng)達(dá)到5個，所以不能將“33”直接插入，而要把這個節(jié)點(diǎn)分裂為兩個，并把中間的一個關(guān)鍵字“36”拿出來插到節(jié)點(diǎn)的父節(jié)點(diǎn)里。1.3.4B樹、B-樹、B+樹和B*樹2．

B-樹

圖1-16一個6階B-樹圖1-17插入關(guān)鍵字“36”后的B-樹1.3.4B樹、B-樹、B+樹和B*樹2．

B-樹

4）B-樹的刪除B-樹的刪除分為以下兩種情況。（1）B-樹的刪除與插入類似，但會稍微復(fù)雜些。如果刪除的關(guān)鍵字不在葉節(jié)點(diǎn)層，就需要先把此關(guān)鍵字與它在B-樹里的后繼節(jié)點(diǎn)對換位置，然后再刪除該關(guān)鍵字。（2）如果刪除的關(guān)鍵字在葉節(jié)點(diǎn)層，則把它從它所在的節(jié)點(diǎn)里去掉，這可能導(dǎo)致此節(jié)點(diǎn)所包含的關(guān)鍵字的個數(shù)小于m/2-1。這種情況下，考察該節(jié)點(diǎn)的左或右兄弟節(jié)點(diǎn)，從兄弟節(jié)點(diǎn)移若干個關(guān)鍵字到該節(jié)點(diǎn)中來，使兩個節(jié)點(diǎn)所含關(guān)鍵字的個數(shù)基本相同。只有在兄弟節(jié)點(diǎn)的關(guān)鍵字個數(shù)剛好等于m/2-1時，這個移動才能進(jìn)行。這種情況下，要將刪除關(guān)鍵字的節(jié)點(diǎn)、其兄弟節(jié)點(diǎn)及其父節(jié)點(diǎn)中的一個關(guān)鍵字合并為一個節(jié)點(diǎn)。1.3.4B樹、B-樹、B+樹和B*樹2．

B-樹

4）B-樹的刪除

例如，要在如圖1-18所示的3階B-樹中刪除關(guān)鍵字“46”，刪除后該節(jié)點(diǎn)的關(guān)鍵字個數(shù)為“0”，低于最低限制“1”，而它的左兄弟節(jié)點(diǎn)和右兄弟節(jié)點(diǎn)的關(guān)鍵字個數(shù)都為最低限制“1”，所以只能將刪除關(guān)鍵字的節(jié)點(diǎn)、其兄弟節(jié)點(diǎn)及其父節(jié)點(diǎn)中的一個關(guān)鍵字合并為一個節(jié)點(diǎn)。

將關(guān)鍵字“46”刪除后，該B-樹如圖1-19所示。

圖1-18一個3階B-樹圖1-19刪除關(guān)鍵字“46”后的B-樹1.3.4B樹、B-樹、B+樹和B*樹3．B+樹

1）B+樹的定義B+樹是B-樹的一種變體。B+樹與B-樹的差異有以下幾點(diǎn)。

（1）在B-樹中，每個節(jié)點(diǎn)含有n個關(guān)鍵字和n+1棵子樹。在B+樹中，每個節(jié)點(diǎn)含有n個關(guān)鍵字和n棵子數(shù)，即每個關(guān)鍵字對應(yīng)一棵子樹。

（2）在B-樹中，每個節(jié)點(diǎn)（除根節(jié)點(diǎn)外）中關(guān)鍵字個數(shù)n的取值范圍是m/2-1≤n≤

m-1。而在B+樹中，每個節(jié)點(diǎn)（除根節(jié)點(diǎn)外）中關(guān)鍵字個數(shù)n的取值范圍是m/2≤n≤m。

（3）在B+樹中，所有葉節(jié)點(diǎn)包含了全部關(guān)鍵字及指向?qū)?yīng)記錄的指針，且所有葉節(jié)點(diǎn)按關(guān)鍵字從小到大的順序依次連接。

（4）在B+樹中，所有非葉節(jié)點(diǎn)僅起到索引的作用，即在節(jié)點(diǎn)中的每個索引項只含有對應(yīng)子樹的最大關(guān)鍵字和指向該子樹的指針，不含有該關(guān)鍵字對應(yīng)記錄的存儲地址。1.3.4B樹、B-樹、B+樹和B*樹3．B+樹

1）B+樹的定義

例如，如圖1-20所示的一棵3階B+樹，其中葉節(jié)點(diǎn)的每個關(guān)鍵字下的指針指向?qū)?yīng)記錄的存儲位置。通常在B+樹上有兩個頭指針：一個指向根節(jié)點(diǎn)，用于從根節(jié)點(diǎn)起對樹進(jìn)行查找、插入、刪除等操作；另一個指向關(guān)鍵字最小的葉節(jié)點(diǎn)，用于從最小的關(guān)鍵字起順序查找和處理在每個葉節(jié)點(diǎn)中的關(guān)鍵字和記錄。

由于B-樹只適合隨機(jī)檢索，B+樹同時支持隨機(jī)檢索和順序檢索，所以在實際中，B+樹應(yīng)用比較多，NTFS就是使用B+樹進(jìn)行動態(tài)索引的。圖1-203階B+樹1.3.4B樹、B-樹、B+樹和B*樹3．B+樹

2）B+樹的查找B+樹的查找與B-樹的查找類似，但也存在不同之處。由于與記錄有關(guān)的信息都存放在葉節(jié)點(diǎn)中，在查找時若在上層已找到待查找的關(guān)鍵字，則查找不會停止，而會繼續(xù)沿指針向下一直查找到葉節(jié)點(diǎn)層的關(guān)鍵字。另外，B+樹的所有葉節(jié)點(diǎn)構(gòu)成一個有序鏈表，可以按照關(guān)鍵字排序的次序遍歷全部記錄。將這兩種方式結(jié)合起來，便使B+樹非常適合范圍檢索。3）B+樹的插入B+樹的插入與B-樹的插入類似，不同之處在于B+樹是在葉節(jié)點(diǎn)上進(jìn)行插入的。如果在葉節(jié)點(diǎn)中關(guān)鍵字的數(shù)量超過m個，該葉節(jié)點(diǎn)就必須分裂成關(guān)鍵字?jǐn)?shù)量大致相同的兩個節(jié)點(diǎn)，并保證在上層節(jié)點(diǎn)中有這兩個節(jié)點(diǎn)的最大關(guān)鍵字。1.3.4B樹、B-樹、B+樹和B*樹3．B+樹

4）B+樹的刪除

當(dāng)B+樹中的關(guān)鍵字在葉節(jié)點(diǎn)層被刪除后，其在上層的副本可以保留，作為一個“分解關(guān)鍵字”的存在。如果因為刪除操作而造成在節(jié)點(diǎn)中關(guān)鍵字的數(shù)量小于m/2-1個，其處理過程便與B-樹的刪除操作一樣。1.3.4B樹、B-樹、B+樹和B*樹4．B*樹

B*樹是B+樹的變體，即在B+樹的非根節(jié)點(diǎn)和非葉節(jié)點(diǎn)中增加了指向兄弟的指針。B*樹的非葉節(jié)點(diǎn)關(guān)鍵字的數(shù)量至少為2m/3個，而B+樹的則是m/2個。B+樹的分裂方法：當(dāng)一個節(jié)點(diǎn)滿時，分配一個新的節(jié)點(diǎn)，并將原節(jié)點(diǎn)中1/2的數(shù)據(jù)復(fù)制到新節(jié)點(diǎn)中，最后在父節(jié)點(diǎn)中增加新節(jié)點(diǎn)的指針。B+樹的分裂只影響原節(jié)點(diǎn)和父節(jié)點(diǎn)，不會影響兄弟節(jié)點(diǎn)，所以它不需要指向兄弟的指針。B*樹的分裂方法：當(dāng)一個節(jié)點(diǎn)滿時，如果它的下一個兄弟節(jié)點(diǎn)未滿，那么將一部分?jǐn)?shù)據(jù)移動到該兄弟節(jié)點(diǎn)中，再在原節(jié)點(diǎn)處插入關(guān)鍵字，最后修