第1章

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

k5

k4

k3

k2

k1

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

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

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

k-2

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

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

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

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

84218421.84218421

11001111.01111

C

F

.7

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

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

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

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

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

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

2）字節(jié)（Byte）

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

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

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

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

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

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

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

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

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

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

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

“或”運算又稱加運算，運算符號有“+”“V”“OR”等。

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

也就是說，在給定的邏輯變量中，只要有一個變量為1，其運算結果為1；當邏輯變量都為0時，運算結果為0。其運算規(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“與”運算

“與”運算又稱乘運算，運算符號有“x”“^”“.”等。

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

也就是說，只有當參與運算的邏輯變量同時取值為1時，其運算結果才等于1。其運算規(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“非”運算

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

“非”邏輯是指當輸入變量為1時，輸出結果為0；當輸入變量為0時，輸出結果為1。也就是說，0的非為1，1的非為0。1.2.4“異或”運算

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

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

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

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

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

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

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

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

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

圖1-2樹結構

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

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

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

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

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

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

（1）節(jié)點

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

（2）節(jié)點的度

（10）祖先節(jié)點

（3）樹的度

（11）子孫節(jié)點

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

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

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

（13）樹的高（深）度

（6）子女節(jié)點

（14）有序樹

（7）雙親節(jié)點

（15）無序樹

（8）兄弟節(jié)點

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

二叉樹是樹形結構的一種，只要對樹的結構加以限制就能得到二叉樹。

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

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

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

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

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

圖1-7空二叉樹

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

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

圖1-11左、右子樹均為空的二叉樹1.3.3樹結構4．二叉樹的類型

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

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

圖1-12滿二叉樹

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

圖1-14B樹

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

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

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

B-樹

1）B-樹的定義

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

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

B-樹

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

B-樹

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

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

B-樹

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

B-樹

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

B-樹

4）B-樹的刪除

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

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

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

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

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

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

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

（3）在B+樹中，所有葉節(jié)點包含了全部關鍵字及指向對應記錄的指針，且所有葉節(jié)點按關鍵字從小到大的順序依次連接。

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

1）B+樹的定義

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

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

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

4）B+樹的刪除

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

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

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

B樹：屬于二叉樹，每個節(jié)點只存儲一個關鍵字；如果查找的關鍵字與節(jié)點關鍵字相等，那么該節(jié)點關鍵字即為查找的關鍵字；如果查找的關鍵字比節(jié)點關鍵字小，就進入左子女節(jié)點；如果查找的關鍵字比節(jié)點關鍵字大，就進入右子女節(jié)點；如果左子女節(jié)點或右子女節(jié)點的指針為空，則報告找不到相應的關鍵字。B-樹：屬于多路搜索樹，每個節(jié)點存儲m/2-l到m-1個關鍵字；非葉節(jié)點關鍵字存儲指向關鍵字范圍的子節(jié)點；所有關鍵字在整棵樹中出現(xiàn)且只出現(xiàn)一次。B+樹：每個節(jié)點存儲m/2到m個關鍵字；在B-樹的基礎上，B+樹為葉子節(jié)點增加鏈表指針；所有關鍵字都在葉節(jié)點中出現(xiàn)；非葉節(jié)點作為葉節(jié)點的索引。B*樹：在B+樹的基礎上，B*樹為非葉節(jié)點增加了鏈表指針，將節(jié)點的最低利用率從1/2提高到了2/3。1.3.5樹的遍歷

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

二叉樹的3種最重要的遍歷方式分別稱為先序遍歷、中序遍歷和后序遍歷。在以這3種方式遍歷一棵二叉樹時，若按訪問節(jié)點的先后次序將節(jié)點進行排列，就能分別得到在二叉樹中所有節(jié)點的先序列表、中序列表和后序列表。相應的節(jié)點次序分別稱為節(jié)點的先序、中序和后序。

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

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

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

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

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

先左后右

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

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

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

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

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

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

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

WinHex工具

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

WinHex工具

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

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

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

圖2-3“建立新文件”對話框2.1

WinHex工具

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

1．“文件”菜單

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

WinHex工具（3）“保存”命令。通過“保存”命令可以保存對文件或磁盤的修改。（4）“另存為”命令。通過“另存為”命令可以更改文件名。（5）“制作備份復制”命令?！爸谱鱾浞輳椭啤泵钍荳inHex最常用、最重要的功能之一，被廣泛應用于電子取證、磁盤克隆、數(shù)據(jù)備份等領域。通過該命令可以打開“創(chuàng)建磁盤鏡像”對話框，如圖2-4所示。

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

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

1．“文件”菜單2.1

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

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

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

1．“文件”菜單2.1

WinHex工具

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

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

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

2．“編輯”菜單2.1

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

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

WinHex工具①“正?！泵睢Ｔ撁钍荳inHex內部使用的復制方式，只能粘貼在WinHex內部，是使用最頻繁的命令。在使用時，先選中一段內容，在扇區(qū)處右擊，運行“編輯”→“復制扇區(qū)”→“正?！泵睿纯蓮椭粕葏^(qū)的內容，如圖2-8所示。

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

WinHex工具

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

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

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

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

WinHex工具

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

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

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

2．“編輯”菜單圖2-13運行“編輯器顯示”命令2.1

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

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

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

2．“編輯”菜單2.1

WinHex工具

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

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

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

WinHex工具

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

2．“編輯”菜單2.1

WinHex工具

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

2．“編輯”菜單

圖2-17“移除”命令2.1

WinHex工具

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

2．“編輯”菜單

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

WinHex工具

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

2．“編輯”菜單

圖2-19“定義選塊”對話框2.1

WinHex工具

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

2．“編輯”菜單

圖2-21設置結尾位置

圖2-20設置開始位置2.1

WinHex工具

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

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

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

2．“編輯”菜單2.1

WinHex工具

2．“編輯”菜單

圖2-21“轉換選塊”對話框2.1

WinHex工具

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

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

2．“編輯”菜單2.1

WinHex工具

2．“編輯”菜單

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

WinHex工具

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

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

WinHex工具

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

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

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

WinHex工具

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

3．“搜索”菜單2.1

WinHex工具

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

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

WinHex工具

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

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

3．“搜索”菜單2.1

WinHex工具

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

WinHex工具

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

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

WinHex工具

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

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

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

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

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

3．“搜索”菜單2.1

WinHex工具

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

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

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

3．“搜索”菜單2.1

WinHex工具

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

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

WinHex工具

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