第1章

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

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

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

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

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

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

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

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

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

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

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

二進(jìn)制是在計(jì)算機(jī)技術(shù)中被廣泛采用的一種數(shù)制。二進(jìn)制數(shù)是用0和1兩個(gè)數(shù)碼來表示的。它的基數(shù)為2，進(jìn)位規(guī)則是“逢二進(jìn)一”，借位規(guī)則是“借一當(dāng)二”。當(dāng)前的計(jì)算機(jī)系統(tǒng)使用的數(shù)制基本均為二進(jìn)制。計(jì)算機(jī)內(nèi)部采用二進(jìn)制的原因主要有以下幾點(diǎn)：（1）技術(shù)實(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”兩個(gè)數(shù)碼。二進(jìn)制在計(jì)數(shù)時(shí)“逢二進(jìn)一”，第i位的權(quán)是2的i次冪。一個(gè)二進(jìn)制數(shù)展開成多項(xiàng)式和的表達(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對(duì)應(yīng)十進(jìn)制數(shù)分別是10~15）共16個(gè)數(shù)碼。十六進(jìn)制在計(jì)數(shù)時(shí)“逢十六進(jìn)一”，第i位上的權(quán)是16的i次冪。一個(gè)十六進(jìn)制數(shù)展開成多項(xiàng)式和的表達(dá)式為：2．二進(jìn)制

十進(jìn)制數(shù)、十六進(jìn)制數(shù)和二進(jìn)制數(shù)之間有著非常簡單的對(duì)應(yīng)關(guān)系。3種常用進(jìn)位計(jì)數(shù)制數(shù)的對(duì)照表如表1-1所示。十進(jìn)制數(shù)二進(jìn)制數(shù)十六進(jìn)制數(shù)十進(jìn)制數(shù)二進(jìn)制數(shù)十六進(jìn)制數(shù)00081000811191001921021010l0A3113111011B41004121l00C51015131101D61106141110E71117151111F3．進(jìn)位計(jì)數(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)展開多項(xiàng)式和的形式，再計(jì)算此表達(dá)式的和即可。例如：1101B=1×23+1×22+0×21+1×20=23+22+20=13D。

為了使進(jìn)位計(jì)數(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)位計(jì)數(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，得到一個(gè)商和一個(gè)余數(shù)，再將商除以2，又得到一個(gè)商和一個(gè)余數(shù)，以此類推，直至商為0，再將每次得到的余數(shù)倒序排列，就是對(duì)應(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)位計(jì)數(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)的先后順序依次排列，即可得到對(duì)應(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)位計(jì)數(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)位計(jì)數(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位時(shí)以0補(bǔ)齊，每一組二進(jìn)制數(shù)均可轉(zhuǎn)換成一個(gè)十六進(jìn)制數(shù)，各組轉(zhuǎn)換完畢后即可得到轉(zhuǎn)換后的十六進(jìn)制整數(shù)。

（2）小數(shù)部分從最高有效位開始，以4位為一組，含最低有效位的一組不足4位時(shí)以0補(bǔ)齊，每一組二進(jìn)制數(shù)均可轉(zhuǎn)換成一個(gè)十六進(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ì)算機(jī)只能識(shí)別二進(jìn)制數(shù)，而要求計(jì)算機(jī)處理的數(shù)卻種類繁多，這該怎么辦呢？在計(jì)算機(jī)中，各種形式的編碼很好地解決了數(shù)及字符等信息的表示問題。

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

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

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

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

2）字節(jié)（Byte）

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

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

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

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

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

計(jì)算機(jī)中的數(shù)據(jù)可以分為數(shù)值數(shù)據(jù)與非數(shù)值數(shù)據(jù)兩種。其中，數(shù)值數(shù)據(jù)就是常說的“數(shù)”（如整數(shù)、實(shí)數(shù)等），且在計(jì)算機(jī)中是以二進(jìn)制數(shù)的形式存放的；而非數(shù)值數(shù)據(jù)與一般的“數(shù)”不同，通常不表示數(shù)值大小，只表示字符或圖形等信息，但這些信息在計(jì)算機(jī)中也是以二進(jìn)制數(shù)的形式存放的。美國信息交換標(biāo)準(zhǔn)代碼（AmericanStandardCodeforInformationInterchange，ASCII）是基于拉丁字母的一套計(jì)算機(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ì)算機(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é)計(jì)算法。他用等式表示判斷，把推理看成等式的變換。這種變換的有效性不依賴于人們對(duì)符號(hào)的認(rèn)識(shí)，只依賴于符號(hào)的組合規(guī)律。20世紀(jì)30年代，邏輯代數(shù)在電路系統(tǒng)中得到應(yīng)用。之后，隨著電子技術(shù)與計(jì)算機(jī)的發(fā)展，出現(xiàn)了各種復(fù)雜的系統(tǒng)。這些系統(tǒng)的變換規(guī)律也遵守布爾所揭示的規(guī)律。

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

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

計(jì)算機(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）中，就會(huì)大量使用“異或”運(yùn)算作為校驗(yàn)算法。1.2.1“或”運(yùn)算

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

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

也就是說，在給定的邏輯變量中，只要有一個(gè)變量為1，其運(yùn)算結(jié)果為1；當(dāng)邏輯變量都為0時(shí)，運(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)算符號(hào)有“x”“^”“.”等。

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

也就是說，只有當(dāng)參與運(yùn)算的邏輯變量同時(shí)取值為1時(shí)，其運(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)算符號(hào)為在變量上畫一條橫線。

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

“異或”邏輯表示兩個(gè)值不同為“真”、“相同”為假。也就是說，兩個(gè)值都為0或者1，其運(yùn)算結(jié)果為0；而一個(gè)值為0，另一個(gè)值為1，其運(yùn)算結(jié)果為1?！爱惢颉边\(yùn)算通常用符號(hào)“⊕”表示，其運(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ù)，就不能缺少對(duì)數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，因?yàn)樵跀?shù)據(jù)的存儲(chǔ)和管理中處處離不開數(shù)據(jù)結(jié)構(gòu)，如硬盤的分區(qū)結(jié)構(gòu)、文件的系統(tǒng)結(jié)構(gòu)等，都是對(duì)數(shù)據(jù)結(jié)構(gòu)的具體應(yīng)用。1.3.1數(shù)據(jù)結(jié)構(gòu)的概念與分類

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)學(xué)科中的一門專業(yè)課程，更是在程序設(shè)計(jì)中不可或缺的一部分。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。在通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行和存儲(chǔ)效率。數(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ī)，且能被計(jì)算機(jī)處理的符號(hào)（數(shù)字、字符等）的集合，是計(jì)算機(jī)操作對(duì)象的總稱。1．?dāng)?shù)據(jù)結(jié)構(gòu)的基本概念2）數(shù)據(jù)元素

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

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

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

數(shù)據(jù)對(duì)象是具有相同特性的數(shù)據(jù)元素的集合，如整數(shù)、實(shí)數(shù)等。數(shù)據(jù)對(duì)象是數(shù)據(jù)的一個(gè)子集D。4）數(shù)據(jù)對(duì)象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)中的元素存在一對(duì)一的相互關(guān)系，如圖1-1所示。（2）樹結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)多的相互關(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)中的元素存在多對(duì)多的相互關(guān)系，如圖1-3所示。（4）集合結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)中的元素間除了“同屬一個(gè)集合”的相互關(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)，可以用一個(gè)數(shù)據(jù)元素的集合來定義在此集合上的若干關(guān)系。其中，邏輯關(guān)系是指數(shù)據(jù)元素之間的前后間關(guān)系，而與其在計(jì)算機(jī)中的存儲(chǔ)位置無關(guān)。

（2）物理結(jié)構(gòu)又稱存儲(chǔ)結(jié)構(gòu)，是指數(shù)據(jù)結(jié)構(gòu)中的元素在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。①數(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ù)需要表示成多種存儲(chǔ)結(jié)構(gòu)。常用的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、索引存儲(chǔ)和散列存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：借助數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。非順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：借助指示數(shù)據(jù)元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系。2．?dāng)?shù)據(jù)結(jié)構(gòu)的分類2）按照數(shù)據(jù)結(jié)構(gòu)的層次分類（1）順序存儲(chǔ)結(jié)構(gòu)：（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（3）索引存儲(chǔ)結(jié)構(gòu)（4）散列存儲(chǔ)結(jié)構(gòu)1.3.2樹結(jié)構(gòu)1.樹結(jié)構(gòu)的定義

樹結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，它是由n（n≥1）個(gè)有限節(jié)點(diǎn)組成的具有層次關(guān)系的集合。在樹結(jié)構(gòu)中，用一個(gè)圓圈表示一個(gè)節(jié)點(diǎn)，圓圈內(nèi)的符號(hào)代表該節(jié)點(diǎn)的數(shù)據(jù)信息，節(jié)點(diǎn)之間的關(guān)系通過有方向的連線表示。其方向?yà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）每個(gè)節(jié)點(diǎn)有0個(gè)或多個(gè)子節(jié)點(diǎn)。（2）每個(gè)子節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)。（3）沒有前驅(qū)節(jié)點(diǎn)作為根節(jié)點(diǎn)。（4）除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為m個(gè)不相交的子樹。1.3.3樹結(jié)構(gòu)1．二叉樹的定義

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

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

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

（2）樹節(jié)點(diǎn)對(duì)最大度數(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)外每個(gè)節(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)最多擁有兩個(gè)子女節(jié)點(diǎn)（左子女節(jié)點(diǎn)和右子女節(jié)點(diǎn)）。（2）所有節(jié)點(diǎn)存儲(chǔ)一個(gè)關(guān)鍵字。（3）非葉節(jié)點(diǎn)的左指針指向小于其關(guān)鍵字的子樹，右指針指向大于其關(guān)鍵字的子樹。如圖1-14所示的樹就是一個(gè)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)的指針為空，則報(bào)告找不到相應(yīng)的關(guān)鍵字。

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

B-樹

1）B-樹的定義

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

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

B-樹

2）B-樹的查找B-樹的查找是一個(gè)順指針查找節(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個(gè)，則插入成功；否則要把這個(gè)節(jié)點(diǎn)分裂為兩個(gè)，并把中間的一個(gè)關(guān)鍵字拿出來插到節(jié)點(diǎn)的父節(jié)點(diǎn)中。當(dāng)插入父節(jié)點(diǎn)失敗時(shí)，就需要將父節(jié)點(diǎn)再分裂，繼續(xù)進(jìn)行插入操作。當(dāng)需要分裂根節(jié)點(diǎn)時(shí)，由于根節(jié)點(diǎn)沒有父節(jié)點(diǎn)，這時(shí)就需要建立一個(gè)新的根節(jié)點(diǎn)。B-樹的插入可能導(dǎo)致B-樹朝著根的方向生長。

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

B-樹

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

B-樹

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

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

圖1-18一個(gè)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-樹中，每個(gè)節(jié)點(diǎn)含有n個(gè)關(guān)鍵字和n+1棵子樹。在B+樹中，每個(gè)節(jié)點(diǎn)含有n個(gè)關(guān)鍵字和n棵子數(shù)，即每個(gè)關(guān)鍵字對(duì)應(yīng)一棵子樹。

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

m-1。而在B+樹中，每個(gè)節(jié)點(diǎn)（除根節(jié)點(diǎn)外）中關(guān)鍵字個(gè)數(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)中的每個(gè)索引項(xiàng)只含有對(duì)應(yīng)子樹的最大關(guān)鍵字和指向該子樹的指針，不含有該關(guān)鍵字對(duì)應(yīng)記錄的存儲(chǔ)地址。1.3.4B樹、B-樹、B+樹和B*樹3．B+樹

1）B+樹的定義

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

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

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

4）B+樹的刪除

當(dāng)B+樹中的關(guān)鍵字在葉節(jié)點(diǎn)層被刪除后，其在上層的副本可以保留，作為一個(gè)“分解關(guān)鍵字”的存在。如果因?yàn)閯h除操作而造成在節(jié)點(diǎn)中關(guān)鍵字的數(shù)量小于m/2-1個(gè)，其處理過程便與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個(gè)，而B+樹的則是m/2個(gè)。B+樹的分裂方法：當(dāng)一個(gè)節(jié)點(diǎn)滿時(shí)，分配一個(gè)新的節(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)，不會(huì)影響兄弟節(jié)點(diǎn)，所以它不需要指向兄弟的指針。B*樹的分裂方法：當(dāng)一個(gè)節(jié)點(diǎn)滿時(shí)，如果它的下一個(gè)兄弟節(jié)點(diǎn)未滿，那么將一部分?jǐn)?shù)據(jù)移動(dòng)到該兄弟節(jié)點(diǎn)中，再在原節(jié)點(diǎn)處插入關(guān)鍵字，最后修改在父節(jié)點(diǎn)中兄弟節(jié)點(diǎn)的關(guān)鍵字；如果兄弟節(jié)點(diǎn)也滿了，則在原節(jié)點(diǎn)與兄弟節(jié)點(diǎn)之間增加新節(jié)點(diǎn)，并各復(fù)制1/3的數(shù)據(jù)到新節(jié)點(diǎn)中，最后在父節(jié)點(diǎn)處增加新節(jié)點(diǎn)的指針。

綜上可知，B*樹比B+樹分配新節(jié)點(diǎn)的概率要低，空間利用率更高。1.3.4B樹、B-樹、B+樹和B*樹5．對(duì)B樹、B-樹、B+樹和B*樹的總結(jié)

B樹：屬于二叉樹，每個(gè)節(jié)點(diǎn)只存儲(chǔ)一個(gè)關(guā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)的指針為空，則報(bào)告找不到相應(yīng)的關(guān)鍵字。B-樹：屬于多路搜索樹，每個(gè)節(jié)點(diǎn)存儲(chǔ)m/2-l到m-1個(gè)關(guān)鍵字；非葉節(jié)點(diǎn)關(guān)鍵字存儲(chǔ)指向關(guān)鍵字范圍的子節(jié)點(diǎn)；所有關(guān)鍵字在整棵樹中出現(xiàn)且只出現(xiàn)一次。B+樹：每個(gè)節(jié)點(diǎn)存儲(chǔ)m/2到m個(gè)關(guān)鍵字；在B-樹的基礎(chǔ)上，B+樹為葉子節(jié)點(diǎn)增加鏈表指針；所有關(guān)鍵字都在葉節(jié)點(diǎn)中出現(xiàn)；非葉節(jié)點(diǎn)作為葉節(jié)點(diǎn)的索引。B*樹：在B+樹的基礎(chǔ)上，B*樹為非葉節(jié)點(diǎn)增加了鏈表指針，將節(jié)點(diǎn)的最低利用率從1/2提高到了2/3。1.3.5樹的遍歷

樹的遍歷是樹的一種重要運(yùn)算。遍歷是指對(duì)樹中所有的節(jié)點(diǎn)系統(tǒng)地訪問，即依次對(duì)樹中的每個(gè)節(jié)點(diǎn)進(jìn)行訪問且僅訪問一次。

二叉樹的3種最重要的遍歷方式分別稱為先序遍歷、中序遍歷和后序遍歷。在以這3種方式遍歷一棵二叉樹時(shí)，若按訪問節(jié)點(diǎn)的先后次序?qū)⒐?jié)點(diǎn)進(jìn)行排列，就能分別得到在二叉樹中所有節(jié)點(diǎn)的先序列表、中序列表和后序列表。相應(yīng)的節(jié)點(diǎn)次序分別稱為節(jié)點(diǎn)的先序、中序和后序。

多叉樹的遍歷通常有兩種：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。1.3.5樹的遍歷1．先序遍歷

先序遍歷是指先訪問根節(jié)點(diǎn)，再訪問子女節(jié)點(diǎn)的遍歷方式。若二叉樹為非空，則遍歷過程如下。（1）訪問根節(jié)點(diǎn)。（2）先序遍歷左子樹。（3）先序遍歷右子樹。2．中序遍歷

中序遍歷是指先訪問左（右）子女節(jié)點(diǎn)，再訪問根節(jié)點(diǎn)，最后訪問右（左）子女節(jié)點(diǎn)的遍歷方式。若二叉樹為非空，則遍歷過程如下。（1）按中序遍歷左子樹。（2）訪問根節(jié)點(diǎn)。（3）按中序遍歷右子樹。1.3.5樹的遍歷3．后序遍歷

后序遍歷是指先訪問子女節(jié)點(diǎn)，然后訪問根節(jié)點(diǎn)的遍歷方式。若二叉樹為非空，則遍歷過程如下。（1）按后序遍歷左子樹。（2）按后序遍歷右子樹。（3）訪問根節(jié)點(diǎn)。

如圖1-21所示，D為在二叉樹中的某個(gè)節(jié)點(diǎn)，L、R分別為節(jié)點(diǎn)D的左、右子樹，則該二叉樹的遍歷方式有6種：

先左后右

先右后左先序DLRDRL中序LDRRDL后序LRDRLD1.3.5樹的遍歷3．后序遍歷

例如，以先左后右的方式用3種遍歷方法對(duì)如圖1-22所示的二叉樹進(jìn)行遍歷。用先序遍歷的方式，得到的結(jié)果為ABDECF。用中序遍歷的方式，得到的結(jié)果為DBEACF。用后序遍歷的方式，得到的結(jié)果為DEBFCA。

圖1-21二叉樹示例1圖1-22二叉樹示例2謝謝觀看！第2章

數(shù)據(jù)恢復(fù)基本工具與

Windows系統(tǒng)分區(qū)2.1

WinHex工具WinHex是由X-Ways軟件技術(shù)公司開發(fā)的一款專業(yè)的磁盤編輯工具。該工具是在Windows系統(tǒng)下運(yùn)行的十六進(jìn)制編輯軟件，能支持Windows98、Windows2000、WindowsXP和Windows2003等操作系統(tǒng)。

WinHex的功能非常強(qiáng)大，有著完善的分區(qū)管理功能和文件管理功能，能自動(dòng)分析分區(qū)表鏈和文件簇鏈，并能以不同的方式進(jìn)行不同程度的備份，直至克隆整個(gè)硬盤。作為一款磁盤編輯軟件，WinHex具有所有編輯軟件所具有的通用功能（如查找、替換等），并能夠完整地顯示和編輯任何一種文件類型的二進(jìn)制內(nèi)容（用十六進(jìn)制方式顯示）。其磁盤編輯器可以編輯物理磁盤或邏輯磁盤的任意扇區(qū)；其內(nèi)存編輯器可以直接編輯內(nèi)存，是一款非常好用的磁盤編輯軟件。2.1

WinHex工具

要學(xué)習(xí)WinHex，首先要學(xué)會(huì)其菜單的使用。WinHex主界面如圖2-1所示，有“文件”“搜索”“位置”等菜單。圖2-1WinHex主界面2.1

WinHex工具

（1）“新建”命令。單擊“新建”命令，出現(xiàn)“建立新文件”對(duì)話框，如圖2-3所示，輸入要?jiǎng)?chuàng)建文件的大小，單位可以是B、KB、MB、GB。

例如，輸入10KB，單擊“確定”按鈕，即可創(chuàng)建一個(gè)未命名文件，大小是10KB，由全零值構(gòu)成。此時(shí)，可以為這些零值賦予有意義的值，也可以復(fù)制任意文件的內(nèi)容到該文件中，從而使新文件擁有了“靈魂”。如果熟悉匯編語言和文件編碼，則可以像平時(shí)寫文章一樣，創(chuàng)造出任意格式和結(jié)構(gòu)的文件。

1．“文件”菜單圖2-2展開后的“文件”菜單

圖2-3“建立新文件”對(duì)話框2.1

WinHex工具

（2）“打開”命令。通過“打開”命令可以瀏覽任意文件的十六進(jìn)制（Hex）編碼、字符串等，甚至連磁盤鏡像文件或部分加密文件都可以輕松解析出來。打開文件后即可進(jìn)行各種修改、裁剪、填補(bǔ)、銷毀操作。

1．“文件”菜單

此時(shí)，主界面的右邊會(huì)顯示該文件的各種屬性參數(shù)，如大小、創(chuàng)建時(shí)間等。但應(yīng)注意，普通文件被打開后將不再以扇區(qū)為單位進(jìn)行顯示，而是以“頁面”方式進(jìn)行顯示，還可以看到原本扇區(qū)之間的分割線已經(jīng)消失。單個(gè)頁面沒有固定大小，純粹是顯示單位。當(dāng)然，如果遇到特殊情況，打開的是一個(gè)原始磁盤鏡像文件，按頁面瀏覽時(shí)就會(huì)產(chǎn)生諸多不便，定位扇區(qū)、解釋文件系統(tǒng)等工作將無法完成，這時(shí)就需要將鏡像文件轉(zhuǎn)換為磁盤，將此文件強(qiáng)制按照每512B/扇區(qū)進(jìn)行處理。這樣WinHex介質(zhì)管理器就會(huì)視此文件為一個(gè)標(biāo)準(zhǔn)磁盤，從而激活許多針對(duì)磁盤的特殊功能。2.1

WinHex工具（3）“保存”命令。通過“保存”命令可以保存對(duì)文件或磁盤的修改。（4）“另存為”命令。通過“另存為”命令可以更改文件名。（5）“制作備份復(fù)制”命令。“制作備份復(fù)制”命令是WinHex最常用、最重要的功能之一，被廣泛應(yīng)用于電子取證、磁盤克隆、數(shù)據(jù)備份等領(lǐng)域。通過該命令可以打開“創(chuàng)建磁盤鏡像”對(duì)話框，如圖2-4所示。

1．“文件”菜單圖2-4“創(chuàng)建磁盤鏡像”對(duì)話框2.1

WinHex工具（6）“恢復(fù)鏡像文件”命令。通過該命令可以將已成型的鏡像文件還原到分區(qū)或者磁盤中。注意目標(biāo)磁盤的環(huán)境最好與鏡像文件相仿，不然會(huì)產(chǎn)生問題，給下一步工作帶來困難。（7）“備份管理器”命令。通過該命令可以對(duì)備份文件進(jìn)行管理、歸類、錯(cuò)誤檢查。但是如果一次備份過多文件，就會(huì)嚴(yán)重占用磁盤空間，所以應(yīng)定期刪除過期或無用的備份。（8）“執(zhí)行”命令。通過該命令可以用對(duì)應(yīng)的軟件打開當(dāng)前文件。（9）“打印”命令。通過該命令可以打印當(dāng)前頁面。（10）“屬性”命令。通過該命令可以顯示指定文件的基本屬性，如體積大小、創(chuàng)建時(shí)間、修改時(shí)間、訪問時(shí)間。

1．“文件”菜單2.1

WinHex工具（11）“打開文件夾”命令。通過該命令可以打開根目錄下所有擴(kuò)展名為doc的文件，大大減少工作量，如圖2-5所示。此處需注意的是，在對(duì)象目錄中的文件不宜過多，否則會(huì)長時(shí)間無法完成任務(wù)，甚至造成系統(tǒng)崩潰。

1．“文件”菜單圖2-5批量打開文件2.1

WinHex工具（12）“保存修改的文件”命令。如果一組文件被批量修改，那逐一保存會(huì)花費(fèi)很多時(shí)間和精力，WinHex的批量保存文件功能有效解決了這一問題，在這里只保存修改過的一類文件。（13）“保存所有文件”命令。通過該命令可以將全部打開文件進(jìn)行保存。（14）“退出”命令。通過該命令可以退出WinHex軟件。

1．“文件”菜單2.1

WinHex工具

“編輯”菜單是WinHex中操作性最強(qiáng)的菜單。展開后的“編輯”菜單如圖2-6所示。通過“編輯”菜單可以進(jìn)行字節(jié)級(jí)文件修改工作，例如，粘貼偏移的數(shù)據(jù)到正常方位；從磁盤中提取任意數(shù)據(jù)段并寫入新文件等。對(duì)于已經(jīng)定義大小的文件項(xiàng)目，甚至可以采用“補(bǔ)充0字節(jié)”的方式進(jìn)行擴(kuò)容。對(duì)于具有保密要求的文件或磁盤，可以利用“修改數(shù)據(jù)”命令的各種邏輯代數(shù)算法進(jìn)行簡單的加密。例如，對(duì)某硬盤的所有數(shù)據(jù)進(jìn)行異或修改，而要使用這些數(shù)據(jù)時(shí)，再利用已知元素逆運(yùn)算恢復(fù)回來?？傊莆铡熬庉嫛辈藛蔚南嚓P(guān)命令是熟練使用WinHex的關(guān)鍵。

2．“編輯”菜單圖2-6展開后的“編輯”菜單2.1

WinHex工具（1）“撤銷”命令。通過該命令可以更正某些錯(cuò)誤的修改。此命令與Word軟件中的“撤銷”命令是一個(gè)作用，但不能無限制地撤銷，已經(jīng)保存的數(shù)據(jù)是不能撤銷的。（2）“剪切”命令。通過該命令可以將一定范圍的字節(jié)或字符串移動(dòng)到另一位置。例如，當(dāng)出現(xiàn)文件頭偏移導(dǎo)致文件無法打開時(shí)，只需要將文件頭剪切并粘貼回文件開始的部位即可。也可以用此命令將一個(gè)文件的內(nèi)容轉(zhuǎn)移到另一個(gè)文件中，或是將兩個(gè)文件拼接為一個(gè)大文件。但注意最好不要進(jìn)行超大規(guī)模（包含幾百M(fèi)B或幾GB大小的文件）的剪切操作，有可能會(huì)造成系統(tǒng)崩潰。

2．“編輯”菜單2.1

WinHex工具（3）“復(fù)制扇區(qū)”命令。該命令為最常用到的命令之一。在數(shù)據(jù)恢復(fù)中，應(yīng)準(zhǔn)確地判斷數(shù)據(jù)恢復(fù)的字節(jié)范圍，并將數(shù)據(jù)復(fù)制到合適的地方。例如，當(dāng)分區(qū)引導(dǎo)扇區(qū)（DosBootRecord，DBR）嚴(yán)重?fù)p壞時(shí)，磁盤分區(qū)會(huì)提示“未格式化”字樣，此時(shí)就需要找到DBR的備份并將其復(fù)制到該分區(qū)的首扇區(qū)，數(shù)據(jù)恢復(fù)工作也隨之完成。“復(fù)制扇區(qū)”命令下面還包含了很多子命令，如圖2-7所示。

2．“編輯”菜單圖2-7“復(fù)制扇區(qū)”命令下的子命令2.1

WinHex工具①“正?！泵睢Ｔ撁钍荳inHex內(nèi)部使用的復(fù)制方式，只能粘貼在WinHex內(nèi)部，是使用最頻繁的命令。在使用時(shí)，先選中一段內(nèi)容，在扇區(qū)處右擊，運(yùn)行“編輯”→“復(fù)制扇區(qū)”→“正常”命令，即可復(fù)制扇區(qū)的內(nèi)容，如圖2-8所示。

2．“編輯”菜單圖2-8“正?！泵?.1

WinHex工具

在目標(biāo)位置，右擊，運(yùn)行“編輯”→“剪貼板數(shù)據(jù)”→“寫入”命令（如圖2-9所示），就會(huì)出現(xiàn)如圖2-10所示的寫入提示，單擊“確定”按鈕就即可將數(shù)據(jù)寫入目標(biāo)位置，文件的大小不會(huì)改變。

2．“編輯”菜單圖2-9“寫入”命令圖2-10寫入提示2.1

WinHex工具③“十六進(jìn)制數(shù)值”命令。該命令只針對(duì)十六進(jìn)制字節(jié)進(jìn)行提取，在很多情況下可以作為正常復(fù)制的功能使用。它的優(yōu)勢是可以把Hex值復(fù)制到WinHex以外的系統(tǒng)。如要將某分區(qū)的引導(dǎo)扇區(qū)復(fù)制到記事本中，應(yīng)先選中需要復(fù)制的內(nèi)容，然后右擊，運(yùn)行“復(fù)制”→“十六進(jìn)制數(shù)值”命令，再粘貼到記事本中即可，如圖2-12所示。此功能在研究編碼轉(zhuǎn)換時(shí)非常有用。

2．“編輯”菜單圖2-12運(yùn)行“十六進(jìn)制數(shù)值”命令2.1

WinHex工具

完成數(shù)據(jù)寫入的界面如圖2-11所示。通過一系列操作即可輕松把扇區(qū)內(nèi)容復(fù)制到目標(biāo)位置。②“至新文件”命令。該命令可以將選中的內(nèi)容變成一個(gè)新文件，可以是任意格式的文件。

2．“編輯”菜單圖2-11“寫入”命令2.1

WinHex工具④“編輯器顯示”命令。該命令可以將十六進(jìn)制視圖和文本視圖的主要部分簡單記錄下來，也可以寫入WinHex以外的系統(tǒng)。在使用時(shí)，先選中需要復(fù)制的內(nèi)容，然后右擊，運(yùn)行“復(fù)制扇區(qū)”→“編輯器顯示”命令，再粘貼到記事本中，如圖2-13所示。此功能在進(jìn)行學(xué)術(shù)或科研引用時(shí)非常便利，它意味著我們可以抽取任意數(shù)據(jù)區(qū)進(jìn)行深入分析。

2．“編輯”菜單圖2-13運(yùn)行“編輯器顯示”命令2.1

WinHex工具⑤“GREPHex”命令。該命令只針對(duì)十六進(jìn)制字節(jié)進(jìn)行提取，在很多情況下可以作為正常復(fù)制功能使用。在使用時(shí)，先選中需要復(fù)制的內(nèi)容，然后右擊，運(yùn)行“復(fù)制扇區(qū)”→“GREPHex”命令，再粘貼到記事本中，如圖2-14所示。

2．“編輯”菜單圖2-14“GREPHex”命令2.1

WinHex工具⑥“C源碼”命令。通過該命令復(fù)制的內(nèi)容將轉(zhuǎn)換為C語言程序可識(shí)別的源碼形式。因?yàn)榇疟P編輯器往往配合編程語言做程序開發(fā)用，所以會(huì)不可避免地引入編輯區(qū)的內(nèi)容。但是WinHex的顯示方式和編程語言是大不相同的，這就需要將數(shù)據(jù)提取后依次改變成符合編程語言的格式了。這個(gè)工作如果純粹靠程序員人力完成，將是一項(xiàng)十分浩大的工程。WinHex開發(fā)人員充分考慮了該軟件的實(shí)用性，在其功能中加入了多種格式轉(zhuǎn)換工具，而“復(fù)制扇區(qū)”命令中的“C源碼”子命令就是其中一個(gè)。若想將選塊內(nèi)的字節(jié)轉(zhuǎn)換為C語言程序可以識(shí)別的格式，先選中需要復(fù)制的內(nèi)容，然后右擊，運(yùn)行“復(fù)制扇區(qū)”→“C源碼”命令，再粘貼到記事本中，如圖2-15所示。

2．“編輯”菜單2.1

WinHex工具

2．“編輯”菜單圖2-15“C源碼”命令2.1

WinHex工具⑦“Pascal源碼”命令。通過該命令復(fù)制的內(nèi)容用于Pascal語言。若想將選塊內(nèi)的字節(jié)轉(zhuǎn)換為Pascal語言程序可以識(shí)別的格式，先選中需要復(fù)制的內(nèi)容，然后右擊，運(yùn)行“復(fù)制扇區(qū)”→“Pascal源碼”命令，再粘貼到記事本中，如圖2-16所示。

2．“編輯”菜單圖2-16“Pascal源碼”命令2.1

WinHex工具

（4）“剪貼板數(shù)據(jù)”命令。該命令與其他子項(xiàng)相輔相成，復(fù)制、剪切的內(nèi)容會(huì)儲(chǔ)存在剪切板，且每次操作覆蓋上次的內(nèi)容。它也有4個(gè)子命令：“粘貼”“寫入”“粘貼為新文件”“清空剪貼板”。但要注意，“粘貼”命令和“寫入”命令雖然在結(jié)果上似乎完全相同，但對(duì)使用環(huán)境有不同的要求。例如，若想復(fù)制一段字節(jié)到文件中，可以隨意使用這兩個(gè)命令中的一個(gè)，“粘貼”命令會(huì)讓文件變大，從粘貼位置把后面的內(nèi)容往后移動(dòng)；“寫入”命令不會(huì)改變文件的大小，但如果復(fù)制目標(biāo)是嚴(yán)格按照扇區(qū)劃分的磁盤，就只能使用“寫入”命令，粘貼項(xiàng)會(huì)表示為未激活狀態(tài)（灰色）?！罢迟N為新文件”子命令和“復(fù)制扇區(qū)”命令中的“至新文件”子命令很相似，在剪貼板中存入數(shù)據(jù)后單擊相應(yīng)命令即可。當(dāng)數(shù)據(jù)被寫入一個(gè)新文件時(shí)，單擊“保存”按鈕即可構(gòu)造此文件。

2．“編輯”菜單2.1

WinHex工具

（5）“移除”命令。通過該命令可以將不需要的數(shù)據(jù)部分去掉。這里要特別注意的是，“移除”命令與“粘貼0字節(jié)”命令不同，前者會(huì)使文件變小并改變數(shù)據(jù)排列的方位，從而對(duì)文件功能產(chǎn)生實(shí)際影響；后者是在原來的字節(jié)位置上將數(shù)值變?yōu)?，文件大小不會(huì)發(fā)生變化，其他字節(jié)也不會(huì)因此產(chǎn)生位移。在數(shù)據(jù)恢復(fù)中，經(jīng)常會(huì)碰到某些恢復(fù)的文件摻雜著不少“冗余”數(shù)據(jù)，導(dǎo)致文件無法正常使用。此時(shí)，就可以計(jì)算出“冗余”部分，再用移除功能將它們消滅，使偏移的字節(jié)“返本歸原”。在移除選塊的時(shí)候，系統(tǒng)會(huì)提示確認(rèn)信息，如圖2-17所示，單擊“是”按鈕。

2．“編輯”菜單

圖2-17“移除”命令2.1

WinHex工具

（6）“粘貼0字節(jié)”命令。該命令和“移除”命令的功能完全相反，一個(gè)是使文件變小，一個(gè)是使文件變大。該功能可以在文件中的任何位置實(shí)現(xiàn)0字節(jié)的插入，如圖2-18所示，但該功能在數(shù)據(jù)恢復(fù)工作中很少用到。

2．“編輯”菜單

圖2-18“粘貼0字節(jié)”命令2.1

WinHex工具

（7）“定義選塊”命令。選塊是定義操作對(duì)象范圍的基礎(chǔ)，數(shù)據(jù)恢復(fù)的一切操作都是建立在“選塊準(zhǔn)確”的前提下。定義選塊的方法大體分為3種：指針范圍選塊、使用定義選塊子項(xiàng)、開始結(jié)尾法。指針范圍選塊就是利用鼠標(biāo)拖動(dòng)功能進(jìn)行標(biāo)記，這是最快捷的選塊方式，但是由于鼠標(biāo)的拖動(dòng)范圍有限，用戶不可能采用此方法大規(guī)模定義選塊，而且選塊的結(jié)尾也難以確定，所以只有在選塊范圍小于一個(gè)扇區(qū)或一個(gè)頁面時(shí)才建議用此方法。當(dāng)選塊范圍很大的時(shí)候，可以如圖2-19所示通過輸入數(shù)字來定義選塊開始和結(jié)束位置。

2．“編輯”菜單

圖2-19“定義選塊”對(duì)話框2.1

WinHex工具

開始結(jié)尾法則是先找到開始位置，如圖2-20所示，在開始位置右擊，選擇“選塊起始位置”命令，設(shè)置選塊的開始位置。在結(jié)尾位置右擊，選擇“選塊尾部”命令，設(shè)置結(jié)束位置，如圖2-21所示。通過這種方法可以選擇非常大的范圍。

2．“編輯”菜單

圖2-21設(shè)置結(jié)尾位置

圖2-20設(shè)置開始位置2.1

WinHex工具

（8）“全選”命令。該命令可以選中其操作對(duì)象的所有數(shù)據(jù)區(qū)，可以用于文件拼接、模塊組合等，也可以大范圍搜索所定義的區(qū)域。

（9）“清除選塊”命令。如果發(fā)現(xiàn)選塊錯(cuò)誤，可以運(yùn)行該命令，所有選塊標(biāo)記將被取消。

（10）“轉(zhuǎn)換”命令。該命令在數(shù)據(jù)恢復(fù)中應(yīng)用較少，但其擁有強(qiáng)大的功能。它不僅可以實(shí)現(xiàn)編碼互轉(zhuǎn)、進(jìn)制互轉(zhuǎn)、文件加密，程序化地設(shè)置密鑰，還可以解析NTFS壓縮數(shù)據(jù)流。轉(zhuǎn)換牽扯文件編碼學(xué)、文件系統(tǒng)學(xué)、密碼學(xué)等眾多學(xué)科，是WinHex使用中技術(shù)含量較高的，當(dāng)然與用戶的知識(shí)水平也是密不可分的?！稗D(zhuǎn)換選塊”對(duì)話框如圖2-22所示，其中主要是一些編輯功能。

2．“編輯”菜單2.1

WinHex工具

2．“編輯”菜單

圖2-21“轉(zhuǎn)換選塊”對(duì)話框2.1

WinHex工具

（11）“修改數(shù)據(jù)”命令。該命令可以改變數(shù)據(jù)的排列規(guī)律?！靶薷臄?shù)據(jù)”命令應(yīng)用到了邏輯數(shù)學(xué)的許多知識(shí)。該命令具體實(shí)現(xiàn)的功能有給單個(gè)或批量字節(jié)做指定加數(shù)（整數(shù)，可以是正/負(fù)整數(shù)或是十六進(jìn)制數(shù)）的加法、給單個(gè)或批量字節(jié)做反轉(zhuǎn)位（0～255元素集合內(nèi)的補(bǔ)集運(yùn)算）、16位字節(jié)交換（每兩個(gè)字節(jié)左右交換位置）、32位字節(jié)交換（每4字節(jié)左右交換位置）、“異或”運(yùn)算、“或”運(yùn)算、“與”運(yùn)算、循環(huán)左移一位運(yùn)算、循環(huán)右移一位運(yùn)算、位移運(yùn)算、ROT13運(yùn)算、左旋圓運(yùn)算等。

“與”運(yùn)算在整個(gè)數(shù)據(jù)修改算法中屬于比較簡單的算法，可以給每個(gè)字節(jié)加上相同的數(shù)字，從而徹底改變數(shù)據(jù)，當(dāng)然如果再加上該數(shù)字的負(fù)值，數(shù)據(jù)還可以恢復(fù)原貌。首先確定要修改的數(shù)據(jù)范圍（如果不選范圍將會(huì)對(duì)整個(gè)操作對(duì)象進(jìn)行修改），再運(yùn)行“修改數(shù)據(jù)”命令，出現(xiàn)“修改選塊數(shù)據(jù)”對(duì)話框，如圖2-23所示，選擇“Add”（添加）項(xiàng)，在輸入框內(nèi)填入數(shù)值（正/負(fù)整數(shù)），比如14。單擊“確定”按鈕后可以看到，選塊內(nèi)的字節(jié)發(fā)生了變化。此時(shí)如果需要恢復(fù)原貌，可以再添加-14的值。

2．“編輯”菜單2.1

WinHex工具

2．“編輯”菜單

圖2--23“修改選塊數(shù)據(jù)”對(duì)話框2.1

WinHex工具

（12）“填充磁盤扇區(qū)”命令。該命令應(yīng)用于數(shù)據(jù)銷毀領(lǐng)域，可以將整盤、整文件或指定區(qū)域進(jìn)行無意義字節(jié)填充，從而徹底覆蓋原本數(shù)據(jù)。通過該命令可以打開“填充選塊”對(duì)話框，如圖2-24所示。其中，有4種選項(xiàng)：填充十六進(jìn)制數(shù)值、隨機(jī)字符、模擬加密數(shù)據(jù)、Crypotogr,secutepseudo-random（加密安全性偽隨機(jī)）。這4種選項(xiàng)的效果大同小異，如果要滿足數(shù)據(jù)銷毀的標(biāo)準(zhǔn)，需要重復(fù)多次填充選塊。這里使用十六進(jìn)制數(shù)00進(jìn)行填充，可以看到數(shù)據(jù)被0字節(jié)覆蓋。單擊“添加”按鈕可以設(shè)定多套方案，從而進(jìn)行批量處理。

2．“編輯”菜單圖2-24“填充選塊”對(duì)話框2.1

WinHex工具

“搜索”菜單是在數(shù)據(jù)恢復(fù)中較常使用的菜單之一。在工作中，我們接觸到的往往是文件系統(tǒng)的底層，只有在牢牢記住特征編碼后，才能利用磁盤編輯器去尋找參數(shù)，而WinHex便是搜索工具領(lǐng)域的佼佼者。文件系統(tǒng)對(duì)內(nèi)管理是分層、分級(jí)的，要定位并訪問一個(gè)文件，需要經(jīng)過一級(jí)一級(jí)大量且精確的計(jì)算，而掉電、病毒、誤操作、磁盤物理故障等眾多原因都是破壞這種組合計(jì)算的罪魁禍?zhǔn)住?/p>

“搜索”菜單如圖2-25所示。

3．“搜索”菜單圖2-25“搜索”菜單2.1

WinHex工具

（1）“同步搜索”命令。該命令的集成度和智能化相對(duì)較高，可以同時(shí)完成多個(gè)搜索任務(wù)，但同步搜索的對(duì)象僅限于文本。文本框用于輸入字串，并對(duì)格式有一定要求。如果要進(jìn)行多任務(wù)搜索，則每個(gè)任務(wù)必須占用文本框中獨(dú)立的一行。此外，可以從外部導(dǎo)入文本文件來定義搜索內(nèi)容，這里有邏輯搜索和物理搜索兩種方式。邏輯搜索主要針對(duì)操作對(duì)象文件，搜索范圍較小，速度較快。而物理搜索是字節(jié)級(jí)逐個(gè)檢查的搜索方式，主要針對(duì)物理磁盤。

3．“搜索”菜單2.1

WinHex工具

（2）“查找文本”命令。該命令的主要作用就是搜索、定位操作對(duì)象中存在的任意字符串。很多視頻文件、MSSQL備份文件或者M(jìn)FT記錄頭等都是以某種字符串開頭的，此時(shí)只要查找這些字符串，就可以在字節(jié)的海洋中輕易找到這些文件。雖然字符集有很多種，但“查找文本”命令支持的字符集包括ASCII和UNICODE大類，涵蓋了90%以上的應(yīng)用領(lǐng)域?！安檎椅谋尽睂?duì)話框如圖2-26所示。

3．“搜索”菜單圖226“查找文本”對(duì)話框2.1

WinHex工具

在“查找文本”對(duì)話框中，最上方是一個(gè)文本框，用于輸入用戶想要搜索的字符串；下方是各類搜索條件，用戶可以對(duì)字符串字母的大小寫提出更為準(zhǔn)確的要求，可以自由選擇兩大字符編碼類型，可以在搜索表達(dá)式中加入通配符，可以要求搜索完整語句（精度搜索），可以選擇搜索方向或進(jìn)行全局搜索，可以在指定范圍內(nèi)為搜索對(duì)象確定方位（偏移量），可以選擇只在選塊區(qū)內(nèi)搜索，可以在所有打開的項(xiàng)目中進(jìn)行搜索，可以給出并保存搜索列表，可以忽略讀取的錯(cuò)誤（如跳過壞扇區(qū)）等。在如圖2-26所示的“查找文本”對(duì)話框中的設(shè)定條件如下：

忽略匹配大小寫，選擇ASCII，由于對(duì)象單一且清晰故不采用通配符。FILE是固定單詞，可以搜索完整語句。這里不妨做局部搜索，選擇“向下”。將偏移量設(shè)定為“512=0”（此處設(shè)定得越精確，搜索速度越快）。其中，512的意思是一個(gè)扇區(qū)是512B，按照扇區(qū)的整數(shù)倍進(jìn)行搜索；0的意思是從扇區(qū)的第0號(hào)位置開始搜索。搜索結(jié)果會(huì)自動(dòng)列表并保存。如圖2-27所示是文本搜索結(jié)果。

3．“搜索”菜單2.1

WinHex工具

3．“搜索”菜單圖2-27文本搜索結(jié)果2.1

WinHex工具

（3）“查找十六進(jìn)制數(shù)值”命令。該命令與“查找文本”命令的用法非常相似，只是文本框內(nèi)被要求輸入一組十六進(jìn)制數(shù)值。這里填入DBR的結(jié)束標(biāo)志55AA，如圖2-28所示，單擊“確定”按鈕開始搜索。找到DBR如圖2-29所示。

3．“搜索”菜單圖2-28“查找十六進(jìn)制數(shù)值”對(duì)話框圖2-29找到DBR2.1

WinHex工具

（4）“替換文本”命令。該命令在有規(guī)律地修復(fù)同一錯(cuò)誤時(shí)非常有用。例如，當(dāng)扇區(qū)的有效結(jié)束標(biāo)志55AA被病毒改寫，造成扇區(qū)不能被操作系統(tǒng)識(shí)別的情況時(shí)，就可以利用此功能進(jìn)行整體文本的替換。

（5）“替換十六進(jìn)制數(shù)值”命令。該命令與“替換文本”命令使用方法相同，但替換對(duì)象不一樣。

（6）“組合搜索”命令。該命令可以搜索兩個(gè)文件中相同位置的特定數(shù)據(jù)。該命令對(duì)分析文件的相似性幫助很大。

（7）“整數(shù)數(shù)值”命令。該命令與“組合搜索”命令使用方法相同，但搜索對(duì)象不一樣。

（8）“浮點(diǎn)數(shù)值”命令。該命令支持單一浮點(diǎn)、實(shí)數(shù)、雙精度和擴(kuò)展雙精度數(shù)據(jù)，可以配合反匯編功能跟蹤處理器運(yùn)算，在數(shù)據(jù)恢復(fù)中較少使用。

3．“搜索”菜單2.1

WinHex工具

（9）“文本段落”命令。該命令可以定位操作對(duì)象中的“固定字串”（文字資源）。不僅可以搜索包含文字、數(shù)字、標(biāo)點(diǎn)及特殊符號(hào)在內(nèi)的整句，還能在一定范圍內(nèi)限定單詞短語的長度。

（10）“繼續(xù)全局搜索”命令。該命令可以在當(dāng)前任務(wù)意外中斷后從中斷處繼續(xù)搜索，一直搜索完全部范圍。

（11）“繼續(xù)搜索”命令。該命令在當(dāng)前任務(wù)意外中斷后從中斷處繼續(xù)啟動(dòng)搜索。

3．“搜索”菜單2.1

WinHex工具

隨著存儲(chǔ)技術(shù)的發(fā)展，當(dāng)前個(gè)人存儲(chǔ)解決方案都發(fā)展到了TB級(jí)，而數(shù)據(jù)恢復(fù)是一項(xiàng)與“字節(jié)”打交道的微觀工作，想憑直覺在“數(shù)據(jù)海洋”中打撈自己想要的東西，幾乎是不可能的。所以，要像地球經(jīng)緯度那樣，向客戶提供線性、坐標(biāo)性等各種精確定位方法。“位置”菜單如圖2-30所示。充斥在磁盤中的特殊扇區(qū)、功能扇區(qū)、隱藏在扇區(qū)中的重要字節(jié)，是數(shù)據(jù)恢復(fù)的“下刀點(diǎn)”。所以，用戶要充分運(yùn)用本菜單的各種命令，使整個(gè)工作流暢化。

4．“位置”菜單圖2-30“位置”菜單2.1

WinHex工具

（1）“轉(zhuǎn)到偏移量”命令。該命令是字節(jié)級(jí)的定位方案。從圖2-31中可以看出，編輯區(qū)的Offset列和十六進(jìn)制高低位構(gòu)成了一個(gè)坐標(biāo)系，利用定位可