數(shù)據(jù)恢復(fù)技術(shù)（第二版）第一部分

數(shù)據(jù)恢復(fù)技術(shù)（第二版）第一部分目錄\h第一篇數(shù)據(jù)恢復(fù)入門與進(jìn)階知識儲備\h第1章計(jì)算機(jī)中數(shù)據(jù)的記錄方法\h1.1數(shù)據(jù)的表示方法\h1.1.1計(jì)算機(jī)中數(shù)據(jù)的含義\h1.1.2數(shù)值數(shù)據(jù)在計(jì)算機(jī)中的表示方法\h1.1.3字符數(shù)據(jù)在計(jì)算機(jī)中的表示方法\h1.1.4圖形數(shù)據(jù)在計(jì)算機(jī)中的表示方法\h1.2數(shù)據(jù)存儲的字節(jié)序與位序\h1.2.1Endian的含義\h1.2.2Little-endian的含義\h1.2.3Big-endian的含義\h1.2.4字節(jié)序與CPU架構(gòu)的關(guān)系\h1.2.5位序的含義\h1.3數(shù)據(jù)的邏輯運(yùn)算\h1.3.1邏輯或\h1.3.2邏輯與\h1.3.3邏輯非\h1.3.4邏輯異或\h1.4數(shù)據(jù)恢復(fù)中常用的數(shù)據(jù)結(jié)構(gòu)\h1.4.1數(shù)據(jù)結(jié)構(gòu)簡介\h1.4.2樹\h1.4.3二叉樹\h1.4.4B樹、B-樹、B+樹和B*樹\h1.4.5樹的遍歷\h第2章現(xiàn)代硬盤結(jié)構(gòu)揭秘\h2.1機(jī)械硬盤的物理結(jié)構(gòu)揭秘\h2.1.1硬盤的外殼及盤標(biāo)信息\h2.1.2硬盤的電路結(jié)構(gòu)\h2.1.3硬盤的磁頭定位驅(qū)動(dòng)系統(tǒng)\h2.1.4硬盤的主軸系統(tǒng)\h2.1.5硬盤的數(shù)據(jù)控制系統(tǒng)\h2.1.6硬盤的盤片\h2.1.7硬盤的區(qū)段及物理C/H/S\h2.1.8硬盤的接口技術(shù)\h2.1.9硬盤的主要性能指標(biāo)\h2.2機(jī)械硬盤的邏輯結(jié)構(gòu)揭秘\h2.2.1硬盤的邏輯磁道\h2.2.2硬盤的邏輯扇區(qū)\h2.2.3硬盤的邏輯柱面\h2.2.4硬盤的邏輯磁頭\h2.2.5硬盤的邏輯C/H/S\h2.2.6硬盤的28位LBA及48位LBA\h2.3固態(tài)硬盤結(jié)構(gòu)揭秘\h2.3.1固態(tài)硬盤的結(jié)構(gòu)\h2.3.2固態(tài)硬盤的優(yōu)點(diǎn)\h2.3.3固態(tài)硬盤的缺點(diǎn)\h第3章數(shù)據(jù)恢復(fù)基本工具揭秘\h3.1磁盤編輯器類工具\(yùn)h3.1.1WinHex使用方法詳解\h3.1.2DiskExplorerforFat使用方法詳解\h3.1.3DiskExplorerforNTFS使用方法詳解\h3.1.4DiskExplorerforLinux使用方法詳解\h3.2虛擬工具\(yùn)h3.2.1虛擬硬盤工具使用方法詳解\h3.2.2虛擬機(jī)使用方法詳解\h第二篇邏輯類數(shù)據(jù)恢復(fù)技術(shù)揭秘\h第4章Windows系統(tǒng)數(shù)據(jù)恢復(fù)技術(shù)\h4.1Windows系統(tǒng)的MBR磁盤分區(qū)\h4.1.1主引導(dǎo)記錄MBR的結(jié)構(gòu)和作用\h4.1.2主磁盤分區(qū)的結(jié)構(gòu)分析\h4.1.3擴(kuò)展分區(qū)的結(jié)構(gòu)分析\h4.1.4MBR及EBR被破壞的分區(qū)恢復(fù)實(shí)例\h4.1.5分區(qū)誤刪除的恢復(fù)實(shí)例\h4.1.6系統(tǒng)誤Ghost后的分區(qū)恢復(fù)實(shí)例\h4.2Windows系統(tǒng)的動(dòng)態(tài)磁盤卷\h4.2.1動(dòng)態(tài)磁盤概述\h4.2.2動(dòng)態(tài)磁盤卷的種類及創(chuàng)建方法\h4.2.3動(dòng)態(tài)磁盤LDM結(jié)構(gòu)原理詳解\h4.2.4MBR磁盤誤轉(zhuǎn)換為動(dòng)態(tài)磁盤的恢復(fù)實(shí)例\h4.2.5動(dòng)態(tài)磁盤擴(kuò)展卷丟失的恢復(fù)實(shí)例\h4.3Windows系統(tǒng)的GPT磁盤分區(qū)\h4.3.1GPT磁盤分區(qū)基本介紹\h4.3.2GPT磁盤分區(qū)的創(chuàng)建方法\h4.3.3GPT磁盤分區(qū)的結(jié)構(gòu)原理第一篇數(shù)據(jù)恢復(fù)入門與進(jìn)階知識儲備數(shù)據(jù)恢復(fù)技術(shù)是一門新興的學(xué)科，也是一項(xiàng)涉及知識面非常廣泛的綜合技術(shù)，但是，萬丈高樓平地起，越復(fù)雜的技術(shù)，越要從基礎(chǔ)入手，只有把基礎(chǔ)知識掌握扎實(shí)了，才能更有效地領(lǐng)會深層的技術(shù)。本篇主要講述學(xué)習(xí)數(shù)據(jù)恢復(fù)技術(shù)必備的基礎(chǔ)知識，包括如下3章：第1章計(jì)算機(jī)中數(shù)據(jù)的記錄方法第2章現(xiàn)代硬盤結(jié)構(gòu)揭秘第3章數(shù)據(jù)恢復(fù)基本工具揭秘第1章計(jì)算機(jī)中數(shù)據(jù)的記錄方法人類早已步入信息社會，人們對世界的認(rèn)知和改造過程就是獲取信息、加工信息和傳送信息的過程。人們通過電視、電話、報(bào)刊等各種媒體，每時(shí)都在獲取、加工和傳遞利用著大量的信息。目前，計(jì)算機(jī)已經(jīng)在我們生活和工作的各個(gè)領(lǐng)域得到普及應(yīng)用，計(jì)算機(jī)也成為處理和存儲各種信息的重要工具。這些信息在計(jì)算機(jī)中是以數(shù)據(jù)的形式體現(xiàn)的。下面將學(xué)習(xí)計(jì)算機(jī)如何記錄這些數(shù)據(jù)。提示本章內(nèi)容屬于計(jì)算機(jī)基礎(chǔ)知識，掌握本章的知識對數(shù)據(jù)恢復(fù)技術(shù)中數(shù)據(jù)結(jié)構(gòu)的分析有很大幫助，但該部分內(nèi)容對于非計(jì)算機(jī)專業(yè)的讀者來說可能較難理解，且比較枯燥，為避免因本章的障礙而失去對整本書的興趣，讀者也可戰(zhàn)略性地放棄本章，直接進(jìn)入下一章的學(xué)習(xí)。1.1數(shù)據(jù)的表示方法1.1.1計(jì)算機(jī)中數(shù)據(jù)的含義數(shù)據(jù)（Data）是表示客觀事物的、可以被記錄的、能夠被識別的各種符號，包括字符、符號、表格、聲音和圖形、圖像等。簡言之，一切可以被計(jì)算機(jī)加工、處理的對象都可以被稱為數(shù)據(jù)。數(shù)據(jù)可在物理介質(zhì)上記錄或傳輸，并通過外圍設(shè)備被計(jì)算機(jī)接收，經(jīng)過處理而得到結(jié)果。1.進(jìn)位計(jì)數(shù)制在日常生活中，人們習(xí)慣于用十進(jìn)制計(jì)數(shù)。但是，在實(shí)際應(yīng)用中，還使用其他的計(jì)數(shù)制，如二進(jìn)制、十二進(jìn)制、二十四進(jìn)制、六十進(jìn)制等。用數(shù)字符號排列，由低位向高位進(jìn)位計(jì)數(shù)的方法叫作進(jìn)位計(jì)數(shù)制，簡稱進(jìn)位制。進(jìn)位計(jì)數(shù)制的特點(diǎn)是由一組規(guī)定的數(shù)字來表示任意的數(shù)。例如，一個(gè)二進(jìn)制數(shù)只能用0和1來表示，一個(gè)十進(jìn)制數(shù)只能用0、1、2、…、9來表示，一個(gè)十六進(jìn)制數(shù)用0、1、2、…、9和A～F十六個(gè)數(shù)字符號來表示。數(shù)據(jù)無論使用哪種進(jìn)位制，都涉及兩個(gè)基本要素：“基數(shù)”與各數(shù)位的“位權(quán)”。一種計(jì)數(shù)制允許選用基本數(shù)字符號（數(shù)碼）的個(gè)數(shù)叫基數(shù)。在基數(shù)為J的計(jì)數(shù)制中，包含J個(gè)不同的數(shù)字符號，每個(gè)數(shù)位計(jì)滿J就向高位進(jìn)1，即“逢J進(jìn)一”。例如最常用的十進(jìn)制中，每一位上允許選用0、1、2、…、9共10個(gè)不同數(shù)碼中的一個(gè)，則十進(jìn)制的基數(shù)為10，每位計(jì)滿10時(shí)向高位進(jìn)一。一個(gè)數(shù)字符號處在不同位時(shí)，它所代表的數(shù)值是不同的。每個(gè)數(shù)字符號所表示的數(shù)值等于該數(shù)字符號值乘以一個(gè)與數(shù)碼所在位有關(guān)的常數(shù)，這個(gè)常數(shù)叫作“位權(quán)”，簡稱“權(quán)”。位權(quán)的大小是以基數(shù)為底，數(shù)碼所在位置的序號為指數(shù)的整數(shù)次冪。例如，十進(jìn)制數(shù)的百分位、十分位、個(gè)位、十位、百位、千位的權(quán)依次是10?2、10?1、100、101、102、103。整數(shù)部分的個(gè)位位置的序號是0。J進(jìn)制數(shù)每位的值等于該位的權(quán)與該位數(shù)碼的乘積。一個(gè)J進(jìn)制可以寫成按權(quán)展開的多項(xiàng)式和的形式，一個(gè)J進(jìn)制數(shù)(S)J按權(quán)展開的多項(xiàng)式和的一般表達(dá)式為：式中，n是J進(jìn)制數(shù)整數(shù)部分的位數(shù)；m是J進(jìn)制數(shù)小數(shù)部分的位數(shù)；ki是第i位上的數(shù)碼，也稱系數(shù)；Ji是第i位上的權(quán)。在整數(shù)部分，i是正數(shù)；在小數(shù)部分，i應(yīng)是負(fù)數(shù)?？梢钥闯?，J進(jìn)制數(shù)相鄰兩個(gè)數(shù)的權(quán)相差J倍，如果小數(shù)點(diǎn)向左移一位，數(shù)縮小J倍；反之，小數(shù)點(diǎn)右移一位，數(shù)擴(kuò)大J倍。2.二進(jìn)制計(jì)算機(jī)是由電子元器件組成的?？紤]到經(jīng)濟(jì)、可靠、容易實(shí)現(xiàn)、運(yùn)算簡便、節(jié)省元器件等因素，在計(jì)算機(jī)中的數(shù)都用二進(jìn)制表示而不用十進(jìn)制表示。二進(jìn)制有如下優(yōu)點(diǎn)：（1）技術(shù)容易實(shí)現(xiàn)二進(jìn)制計(jì)數(shù)只需要兩個(gè)數(shù)字符號0和1。在電路中可以用兩種不同的狀態(tài)——低電平（0）和高電平（1）來表示，其運(yùn)算電路的實(shí)現(xiàn)比較簡單，并且數(shù)據(jù)的存儲和傳送也可用簡單而可靠的方式進(jìn)行；而要制造有10種穩(wěn)定狀態(tài)的電子器件分別代表十進(jìn)制中的10個(gè)數(shù)字符號是十分困難的。（2）二進(jìn)制運(yùn)算規(guī)則簡單十進(jìn)制兩個(gè)一位數(shù)的“和”與“積”的結(jié)果各有55種，而二進(jìn)制兩個(gè)一位數(shù)的“和”與“積”分別只有3種結(jié)果。所以二進(jìn)制數(shù)在編碼、計(jì)數(shù)和算術(shù)運(yùn)算方面規(guī)則簡單，容易用開關(guān)電路實(shí)現(xiàn)，為提高計(jì)算機(jī)的運(yùn)算速度和降低實(shí)現(xiàn)成本奠定了基礎(chǔ)。（3）邏輯運(yùn)算方便由于二進(jìn)制數(shù)碼的兩個(gè)基本符號“0”和“1”，能方便地與邏輯命題的“否”和“是”，或稱“假”和“真”相對應(yīng)，為計(jì)算機(jī)中的邏輯運(yùn)算和程序中的邏輯判斷提供了便利條件。二進(jìn)制的基數(shù)為2，只有“0”和“1”兩個(gè)數(shù)碼，計(jì)數(shù)逢二進(jìn)一。第i位上的位權(quán)是2的i次冪。一個(gè)二進(jìn)制數(shù)展開成多項(xiàng)式和的表達(dá)式是：例如：(10101.11)2=1×24+0×23+1×22+0×21+1×20+1×2?1+1×2?23.八進(jìn)制數(shù)與十六進(jìn)制數(shù)在計(jì)算機(jī)內(nèi)部，一切信息的存儲、處理與傳送均采用二進(jìn)制的形式。但由于二進(jìn)制數(shù)寫起來很長，且很難記，為方便起見，人們編寫程序或書寫指令時(shí)，通常采用八進(jìn)制數(shù)或十六進(jìn)制數(shù)。八進(jìn)制數(shù)基數(shù)為8，有0、1、2、3、4、5、6、7，共8個(gè)數(shù)碼，逢八進(jìn)一，第i位上的位權(quán)是8的i次冪。一個(gè)八進(jìn)制數(shù)展開成多項(xiàng)式和的表達(dá)式是：十六進(jìn)制數(shù)基數(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個(gè)數(shù)碼，逢十六進(jìn)一，第i位上的位權(quán)是16的i次冪。一個(gè)十六進(jìn)制數(shù)展開成多項(xiàng)式和的表達(dá)式是：十六進(jìn)制和八進(jìn)制與二進(jìn)制之間有著非常簡單的對應(yīng)關(guān)系，表1-1給出了四種常用計(jì)數(shù)制的對照表。表1-1四種常用計(jì)數(shù)制的對照表4.進(jìn)位計(jì)數(shù)制的相互轉(zhuǎn)換為了清晰方便起見，常在數(shù)字后面加字母B（Binary）表示二進(jìn)制數(shù)；加O（Octal）表示八進(jìn)制數(shù)，為避免把字母O誤認(rèn)為數(shù)字0，本書暫時(shí)改用Q字母；加H（Hexadecimal）表示十六進(jìn)制數(shù)，加D（Decimal）或不加字母表示十進(jìn)制數(shù)。（1）二進(jìn)制轉(zhuǎn)換成十進(jìn)制將二進(jìn)制轉(zhuǎn)換成十進(jìn)制，只需把二進(jìn)制數(shù)寫成按權(quán)展開多項(xiàng)式和的形式，再計(jì)算此表達(dá)式的和即可。例如，10101.11B=1×24+0×23+1×22+0×21+1×20+1×2?1+1×2?2=24+22+20+2?1+2?2=21.75D（2）十進(jìn)制整數(shù)轉(zhuǎn)換成二進(jìn)制整數(shù)將十進(jìn)制整數(shù)轉(zhuǎn)換成二進(jìn)制整數(shù)采用“除2取余法”。即將十進(jìn)制整數(shù)除以2，得到一個(gè)商和一個(gè)余數(shù)；再將商除以2，又得到一個(gè)商和一個(gè)余數(shù)；以此類推，直到商等于零為止。每次得到的余數(shù)的倒排列，就是對應(yīng)二進(jìn)制數(shù)的各位數(shù)。例如，將十進(jìn)制數(shù)153轉(zhuǎn)換成二進(jìn)制數(shù)：即153D=(k7k6k5k4k3k2k1k0)=10011001B。（3）十進(jìn)制小數(shù)轉(zhuǎn)換成二進(jìn)制小數(shù)十進(jìn)制小數(shù)轉(zhuǎn)換成二進(jìn)制小數(shù)是用“乘2取整法”。即用2逐次去乘十進(jìn)制小數(shù)，將每次得到的積的整數(shù)部分按各自出現(xiàn)的先后順序依次排列，就得到相對應(yīng)的二進(jìn)制小數(shù)。例如，把十進(jìn)制小數(shù)0.7875轉(zhuǎn)換成二進(jìn)制數(shù)：即0.7875D=(k?1k?2k?3k?4k?5)=0.11001B。如果一個(gè)十進(jìn)制數(shù)既有整數(shù)部分又有小數(shù)部分，可將整數(shù)部分和小數(shù)部分分別進(jìn)行J進(jìn)制的等值轉(zhuǎn)換，然后合并就可得到結(jié)果。（4）八進(jìn)制轉(zhuǎn)換為二進(jìn)制將八進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)，每位八進(jìn)制數(shù)用3位二進(jìn)制數(shù)表示即可。例如，八進(jìn)制數(shù)617.34Q轉(zhuǎn)換成二進(jìn)制數(shù)：617.34110001111.011100即617.34Q=110001111.011100B。（5）二進(jìn)制轉(zhuǎn)換為八進(jìn)制二進(jìn)制數(shù)轉(zhuǎn)換成八進(jìn)制數(shù)，是將二進(jìn)制數(shù)的整數(shù)部分從右向左每3位一組，每一組為一位八進(jìn)制整數(shù)。二進(jìn)制小數(shù)轉(zhuǎn)換成八進(jìn)制小數(shù)是將小數(shù)部分從左至右每3位一組，每一組是一位八進(jìn)制的小數(shù)。若整數(shù)和小數(shù)部分的最后一組不足3位時(shí)，則用0補(bǔ)足3位。例如，把二進(jìn)制數(shù)11010110110.1001轉(zhuǎn)換成八進(jìn)制數(shù)：即11010110110.1001B=3266.44Q。（6）十六進(jìn)制轉(zhuǎn)換為二進(jìn)制由于24=16，所以每一位十六進(jìn)制數(shù)要用4位二進(jìn)制數(shù)來表示，也就是將每一位十六進(jìn)制數(shù)表示成4位二進(jìn)制數(shù)。例如，將十六進(jìn)制數(shù)3A65.B2H轉(zhuǎn)換成二進(jìn)制數(shù)：即3A65.B2H=11101001100101.1011001B。（7）二進(jìn)制轉(zhuǎn)換為十六進(jìn)制將二進(jìn)制數(shù)轉(zhuǎn)換成十六進(jìn)制數(shù)是將二進(jìn)制數(shù)的整數(shù)部分從右向左每4位一組，每一組為一位十六進(jìn)制整數(shù)；而二進(jìn)制小數(shù)轉(zhuǎn)換成十六進(jìn)制小數(shù)是將二進(jìn)制小數(shù)部分從左向右每4位一組，每一組為一位十六進(jìn)制小數(shù)。最后一組不足4位時(shí)，應(yīng)在后面用0補(bǔ)足4位。例如，二進(jìn)制數(shù)1010101011.0110B轉(zhuǎn)換成十六進(jìn)制數(shù)：001010101011.01102AB.6即(1010101011.0110)2=(2AB.6)16，或?qū)憺?010101011.0110B=2AB.6H。1.1.2數(shù)值數(shù)據(jù)在計(jì)算機(jī)中的表示方法計(jì)算機(jī)只能識別二進(jìn)制數(shù)，而要求計(jì)算機(jī)處理的數(shù)，如無符號數(shù)、有符號數(shù)等，又種類繁多，怎么辦呢？計(jì)算機(jī)中采用各種形式的編碼很好地解決了數(shù)及字符等信息的表示問題。數(shù)據(jù)可分為兩大類：數(shù)值數(shù)據(jù)和非數(shù)值數(shù)據(jù)。前者表示數(shù)量的多少；后者表示字符、漢字、圖形、圖像、聲音等，又稱符號數(shù)據(jù)。在計(jì)算機(jī)內(nèi)，無論哪一種數(shù)據(jù)，都以二進(jìn)制形式表示。本節(jié)首先講解數(shù)值數(shù)據(jù)在計(jì)算機(jī)中的表示方法。1.數(shù)據(jù)的單位計(jì)算機(jī)中數(shù)據(jù)的常用單位有位、字節(jié)和字。（1）位（Bit）計(jì)算機(jī)中最小的數(shù)據(jù)單位是二進(jìn)制的一個(gè)數(shù)位，簡稱為位（英文名稱為Bit，讀音為比特）。計(jì)算機(jī)中最直接、最基本的操作就是對二進(jìn)制位的操作。（2）字節(jié)（Byte）字節(jié)這個(gè)詞是在1956年左右由IBM公司最早提出來的。這個(gè)詞起源于Bite，但用y代替了i，以避免被人誤認(rèn)為它是Bit，也就成了現(xiàn)在的Byte。曾經(jīng)有一段時(shí)期，字節(jié)僅僅簡單地表示特定數(shù)據(jù)路徑上數(shù)據(jù)的位數(shù)。但是到了20世紀(jì)60年代中期，隨著IBM的360系統(tǒng)的發(fā)展，字節(jié)這個(gè)詞專門用來表示8位二進(jìn)制數(shù)。作為一個(gè)8位二進(jìn)制數(shù)，一個(gè)字節(jié)可以從00000000取值到11111111。這些數(shù)可以代表0～255的正數(shù)，也可以表示?128～127范圍之內(nèi)的正、負(fù)數(shù)?？傊?，一個(gè)特定的字節(jié)可以代表28（即256種）不同事物中的一個(gè)。字節(jié)簡寫為B，它是計(jì)算機(jī)中用來表示存儲空間大小的基本容量單位。與字節(jié)有關(guān)的常用換算單位如下：1B=8bit;1KB=1024B=210B;1MB=1024KB=210KB=220B;1GB=1024MB=210MB=230B;1TB=1024GB=210GB=240B;1PB=1024TB=210TB=250B;1EB=1024PB=210PB=260B。提示位與字節(jié)區(qū)別：位是計(jì)算機(jī)中的最小數(shù)據(jù)單位，字節(jié)是計(jì)算機(jī)中的基本信息單位。（3）字（Word）在計(jì)算機(jī)中作為一個(gè)整體被存取、傳送、處理的二進(jìn)制數(shù)字符串叫作一個(gè)“字”或“單元”。每個(gè)字中二進(jìn)制位數(shù)的長度，稱為字長。一個(gè)字由若干個(gè)字節(jié)組成，不同的計(jì)算機(jī)系統(tǒng)的字長是不同的，常見的有8位、16位、32位、64位等。字長越長，計(jì)算機(jī)一次處理的信息位就越多，精度就越高。字長是計(jì)算機(jī)性能的一個(gè)重要指標(biāo)。目前大部分計(jì)算機(jī)都是32位的。在匯編語言程序中，字為16位二進(jìn)制數(shù)，即1Word=2Byte=16bit；把32位二進(jìn)制數(shù)，即兩個(gè)字稱為雙字（DoubleWord）。2.定點(diǎn)數(shù)表示方法在選擇計(jì)算機(jī)數(shù)值的表示方式時(shí)，需要考慮以下幾個(gè)因素：①要表示的數(shù)的類型（小數(shù)、整數(shù)、實(shí)數(shù)和復(fù)數(shù)）;②可能遇到的數(shù)值范圍；③數(shù)值精確度；④數(shù)據(jù)存儲和處理所需要的硬件代價(jià)。計(jì)算機(jī)處理的數(shù)值數(shù)據(jù)多數(shù)帶有小數(shù)。小數(shù)點(diǎn)在計(jì)算機(jī)中通常有兩種表示方法：一種是約定所有數(shù)值數(shù)據(jù)的小數(shù)點(diǎn)隱含在某一個(gè)固定位置上，稱為定點(diǎn)表示法，簡稱定點(diǎn)數(shù)；另一種是小數(shù)點(diǎn)位置可以浮動(dòng)，稱為浮點(diǎn)表示法，簡稱浮點(diǎn)數(shù)。所謂定點(diǎn)數(shù)，就是約定計(jì)算機(jī)中所有數(shù)據(jù)的小數(shù)點(diǎn)位置是固定不變的。在計(jì)算機(jī)中通常采用兩種簡單的約定：將小數(shù)點(diǎn)的位置固定在數(shù)據(jù)的最高位之前，或者是固定在最低位之后。一般常稱前者為定點(diǎn)小數(shù)，后者為定點(diǎn)整數(shù)。（1）定點(diǎn)小數(shù)定點(diǎn)小數(shù)約定的小數(shù)點(diǎn)位置在符號位之后、有效數(shù)值部分最高位之前，即一個(gè)數(shù)的最高二進(jìn)制位是符號位，用來表示數(shù)的符號，而小數(shù)點(diǎn)的位置默認(rèn)為在符號位后面，不單獨(dú)占一個(gè)二進(jìn)制位。例如，數(shù)據(jù)x的形式為x=x0.x1x2…xn（其中，x0為符號位，x1～xn是數(shù)值的有效部分，也稱為尾數(shù)，x1為最高有效位），則x在計(jì)算機(jī)中的表示形式為：所以，在一個(gè)定點(diǎn)小數(shù)中，符號位右邊的所有二進(jìn)制位數(shù)表示的是一個(gè)純小數(shù)。（2）定點(diǎn)整數(shù)定點(diǎn)整數(shù)約定小數(shù)點(diǎn)位置在有效數(shù)值部分最低位之后，即一個(gè)數(shù)的最高二進(jìn)制位是符號位，用以表示數(shù)的符號；而小數(shù)點(diǎn)的位置默認(rèn)為在最低（即最右邊）的二進(jìn)制位的后面，但小數(shù)點(diǎn)不單獨(dú)占一個(gè)二進(jìn)制位。例如數(shù)據(jù)x的形式為x=x0x1x2…xn（其中，x0為符號位，x1～xn是尾數(shù)，xn為最低有效位），則x在計(jì)算機(jī)中的表示形式為：所以，在一個(gè)定點(diǎn)整數(shù)中，符號位右邊的所有二進(jìn)制位數(shù)表示的是一個(gè)純整數(shù)。3.浮點(diǎn)數(shù)表示方法在計(jì)算機(jī)中，定點(diǎn)數(shù)通常只用于表示純整數(shù)或純小數(shù)，而對于既有整數(shù)部分又有小數(shù)部分的數(shù)，由于其小數(shù)點(diǎn)的位置不固定，一般用浮點(diǎn)數(shù)表示。計(jì)算機(jī)中所說的浮點(diǎn)數(shù)就是指小數(shù)點(diǎn)位置不固定的數(shù)。一般地，一個(gè)既有整數(shù)部分又有小數(shù)部分的十進(jìn)制數(shù)D可以表示成如下形式：D=R×10N式中，R為一個(gè)純小數(shù)；N為一個(gè)整數(shù)。例如，一個(gè)十進(jìn)制數(shù)123.456可以表示成0.123456×103，十進(jìn)制小數(shù)0.00123456可以表示成0.123456×10?2。純小數(shù)R的小數(shù)點(diǎn)后第一位一般為非零數(shù)字。同樣，對于既有整數(shù)部分又有小數(shù)部分的二進(jìn)制數(shù)也可以表示成如下形式：D=R×2N式中，R為一個(gè)二進(jìn)制定點(diǎn)小數(shù)，稱為D的尾數(shù)；N為一個(gè)二進(jìn)制定點(diǎn)整數(shù)，稱為D的階碼，它反映了二進(jìn)制數(shù)D的小數(shù)點(diǎn)的實(shí)際位置。為了使有限的二進(jìn)制位數(shù)能表示出最多的數(shù)字位數(shù)，定點(diǎn)小數(shù)R的小數(shù)點(diǎn)后的第一位（即符號位的后面一位）一般為非零數(shù)字（即為“1”）。4.原碼的表示方法二進(jìn)制數(shù)跟十進(jìn)制數(shù)一樣也有正負(fù)之分。在計(jì)算機(jī)中，常采用數(shù)的符號和數(shù)值一起編碼的方法來表示數(shù)據(jù)。常用的有原碼、反碼、補(bǔ)碼、移碼等。這幾種表示法都將數(shù)據(jù)的符號數(shù)碼化。為了區(qū)分一般書寫時(shí)表示的數(shù)和機(jī)器中編碼表示的數(shù)，我們稱前者為真值，后者為機(jī)器數(shù)或機(jī)器碼。所謂原碼就是前面所介紹的二進(jìn)制定點(diǎn)數(shù)表示法，即最高位為符號位，“0”表示正，“1”表示負(fù)，其余位表示數(shù)值的大小。（1）定點(diǎn)小數(shù)的原碼假設(shè)定點(diǎn)小數(shù)的原碼形式為x0.x1x2…xn，則其原碼表示的定義為式中，[x]原是機(jī)器數(shù)；x是真值。例如，x=+0.1001，則[x]原=0.1001x=?0.1001，則[x]原=1.1001（2）定點(diǎn)整數(shù)的原碼假設(shè)定點(diǎn)整數(shù)的原碼形式為x0x1x2…xn，則其原碼表示的定義為原碼表示法的優(yōu)點(diǎn)是比較直觀、簡單易懂，但它的最大缺點(diǎn)是加法運(yùn)算復(fù)雜。這是因?yàn)?，?dāng)兩數(shù)相加時(shí)，如果是同號則數(shù)值相加；如果是異號，則要進(jìn)行減法。而在進(jìn)行減法時(shí)，還要比較絕對值的大小，然后減去小數(shù)，最后還要給結(jié)果選擇恰當(dāng)?shù)姆?。顯然，利用原碼做加減法運(yùn)算是不太方便的。為了解決這些矛盾，人們找到了補(bǔ)碼表示法。5.補(bǔ)碼的表示方法由于計(jì)算機(jī)的運(yùn)算受一定字長的限制，屬于有模運(yùn)算，所以，在計(jì)算機(jī)中可以使用補(bǔ)碼進(jìn)行計(jì)算。在定點(diǎn)小數(shù)機(jī)器中，數(shù)最大不超過1，也就是負(fù)的小數(shù)對“1”的補(bǔ)碼是等價(jià)的。但實(shí)際上，負(fù)數(shù)的符號位還有一個(gè)“1”，要把它看成數(shù)的一部分，所以要對2求補(bǔ)碼，也就是以2為模數(shù)。（1）定點(diǎn)小數(shù)的補(bǔ)碼假設(shè)定點(diǎn)小數(shù)的補(bǔ)碼形式為x0.x1x2…xn，則其補(bǔ)碼表示的定義為對于0，在補(bǔ)碼情況下只有一種表示形式，即[+0]補(bǔ)=[?0]補(bǔ)=0.000…0（2）定點(diǎn)整數(shù)的補(bǔ)碼假設(shè)定點(diǎn)整數(shù)的補(bǔ)碼形式為x0x1x2…xn，則其補(bǔ)碼表示的定義為采用補(bǔ)碼表示法進(jìn)行減法運(yùn)算就比原碼方便多了。因?yàn)椴徽摂?shù)是正還是負(fù)，機(jī)器總是做加法，減法運(yùn)算可變成加法運(yùn)算。但根據(jù)補(bǔ)碼定義，正數(shù)的補(bǔ)碼與原碼形式相同，而求負(fù)數(shù)的補(bǔ)碼要減去|x|。為了用加法代替減法，結(jié)果還得在求補(bǔ)碼時(shí)做一次減法，這顯然是不方便的。從下面介紹的反碼表示法中可以獲得求負(fù)數(shù)補(bǔ)碼的簡便方法，解決負(fù)數(shù)的求補(bǔ)問題。6.反碼的表示方法反碼表示法中，符號的表示法與原碼相同。正數(shù)的反碼與正數(shù)的原碼形式相同；負(fù)數(shù)的反碼符號位為1，數(shù)值部分通過將負(fù)數(shù)原碼的數(shù)值部分各位取反（0變1,1變0）得到。（1）定點(diǎn)小數(shù)的反碼假設(shè)定點(diǎn)小數(shù)的反碼形式為x0.x1x2…xn，則其反碼表示的定義為對于0，在反碼情況下只有兩種表示形式，即[+0]反=0.000…0[?0]反=1.111…1（2）定點(diǎn)整數(shù)的反碼假設(shè)定點(diǎn)整數(shù)的反碼形式為x0x1x2…xn，則其反碼表示的定義為7.移碼的表示方法移碼通常用于表示浮點(diǎn)數(shù)的階碼。階碼是個(gè)n位的整數(shù)，假設(shè)定點(diǎn)整數(shù)移碼形式為x0x1x2…xn時(shí)，移碼的定義為[x]移=2n+x?2n≤x＜2n由移碼的定義式可知，對于同一個(gè)整數(shù)，其移碼與其補(bǔ)碼數(shù)值位完全相同，而符號位正好相反。將十進(jìn)制真值x=?127、?1、0、+1、+127分別表示為8位原碼、反碼、補(bǔ)碼、移碼值的結(jié)果見表1-2。表1-2原碼、反碼、補(bǔ)碼、移碼值舉例8.BCD碼的表示方法計(jì)算機(jī)中使用的是二進(jìn)制數(shù)，人們習(xí)慣使用的是十進(jìn)制數(shù)，因此，輸入到計(jì)算機(jī)中的十進(jìn)制數(shù)需要轉(zhuǎn)換成二進(jìn)制數(shù)；數(shù)據(jù)輸出時(shí)，應(yīng)將二進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)。為了方便，大多數(shù)通用性較強(qiáng)的計(jì)算機(jī)需要能直接處理十進(jìn)制形式表示的數(shù)據(jù)。為此，在計(jì)算機(jī)中還設(shè)計(jì)了一種中間數(shù)字編碼形式，它把每一位十進(jìn)制數(shù)用4位二進(jìn)制編碼表示，稱為二進(jìn)制編碼的十進(jìn)制表示形式，簡稱BCD碼（BinaryCodedDecimal），又稱為二-十進(jìn)制數(shù)。4位二進(jìn)制數(shù)碼，可編碼組合成16種不同的狀態(tài)，而十進(jìn)制數(shù)只有0、1、…、9這十個(gè)數(shù)碼，因此選擇其中的十種狀態(tài)做BCD碼的方案有許多種，如8421BCD碼、格雷碼、余3碼等。編碼方案見表1-3。表1-3常用BCD編碼對照表最常用的BCD碼是8421BCD碼。8421BCD碼選取4位二進(jìn)制數(shù)的前10個(gè)代碼分別對應(yīng)表示十進(jìn)制數(shù)的10個(gè)數(shù)碼，1010～1111這6個(gè)編碼未被使用。從表1-2中可以看到這種編碼是有權(quán)碼。4個(gè)二進(jìn)制位的位權(quán)從高向低分別為8、4、2和1。若按權(quán)求和，和數(shù)就等于該代碼所對應(yīng)的十進(jìn)制數(shù)，例如0110=22+21=6。把一個(gè)十進(jìn)制數(shù)變成它的8421BCD碼數(shù)值，僅對十進(jìn)制數(shù)的每一位單獨(dú)進(jìn)行即可。例如變1986為相應(yīng)的8421BCD碼表示，結(jié)果為0001100110000110。反轉(zhuǎn)換過程也類似，例如變0101100100110111為十進(jìn)制數(shù)，結(jié)果應(yīng)為5937。1.1.3字符數(shù)據(jù)在計(jì)算機(jī)中的表示方法計(jì)算機(jī)中數(shù)據(jù)的概念是廣義的，計(jì)算機(jī)除了處理各種數(shù)之外，還要處理大量符號，如英文字母、漢字等非數(shù)值的信息。例如，當(dāng)要用計(jì)算機(jī)編寫文章時(shí)，就需要將文章中的各種符號、英文字母、漢字等輸入計(jì)算機(jī)，然后由計(jì)算機(jī)進(jìn)行編輯排版。因此，計(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)制形式存放的，這部分內(nèi)容在1.1.2節(jié)中已做了講解。而非數(shù)值型數(shù)據(jù)與一般的“數(shù)”不同，通常不表示數(shù)值的大小，而只表示字符或圖形等信息，但這些信息在計(jì)算機(jī)中也是以二進(jìn)制形式來表示的。本節(jié)具體講解字符數(shù)據(jù)在計(jì)算機(jī)中的表示方法。1.字符的編碼目前，國際上通用的且使用最廣泛的字符有十進(jìn)制數(shù)字符號0～9，大小寫的英文字母，各種運(yùn)算符、標(biāo)點(diǎn)符號等，這些字符的個(gè)數(shù)不超過128個(gè)。為了便于計(jì)算機(jī)識別與處理，這些字符在計(jì)算機(jī)中是用二進(jìn)制形式來表示的，通常稱為字符的二進(jìn)制編碼。由于需要編碼的字符不超過128個(gè)，因此，用7位二進(jìn)制數(shù)就可以對這些字符進(jìn)行編碼。但為了方便，字符的二進(jìn)制編碼一般占8個(gè)二進(jìn)制位，它正好占計(jì)算機(jī)存儲器的一個(gè)字節(jié)。目前國際上通用的是美國國家信息交換標(biāo)準(zhǔn)代碼（AmericanStandardCodeforInformationInterchange），簡稱為ASCII碼（取英文單詞的第一個(gè)字母的組合）。用ASCII表示的字符稱為ASCII碼字符，表1-4是ASCII碼編碼表。表1-4ASCII碼編碼表ASCII碼規(guī)定每個(gè)字符用7位二進(jìn)制編碼表示，表1-4中第一行是第6、5、4位的二進(jìn)制編碼值，第一列是第3、2、1、0位的十進(jìn)制編碼值，第一行、第一列的交點(diǎn)則是指定的字符。7位二進(jìn)制可以給出128個(gè)編碼，表示128個(gè)常用的字符。其中95個(gè)編碼，對應(yīng)著計(jì)算機(jī)終端能輸入并且可以顯示的95個(gè)字符，打印機(jī)設(shè)備也能打印這95個(gè)字符，如大小寫各26個(gè)英文字母，0～9這10個(gè)數(shù)字符，通用的運(yùn)算符和標(biāo)點(diǎn)符號=、+、?、*、/、＜、＞、,、:、·、?、。、(、)、{、}等。例如要知道字母“A”的ASCII碼，查表得知字母A在第2行第5列的位置。行指示了ASCII碼第3、2、1、0位的狀態(tài)，列指示第6、5、4位的狀態(tài)，因此字母A的ASCII碼是1000001B=41H。2.漢字的編碼為了適應(yīng)中文信息處理的需要，1981年國家標(biāo)準(zhǔn)局公布了GB2312—80《信息交換用漢字編碼字符集——基本集》，收集了常用漢字67763個(gè)，并給這些漢字分配了代碼。用計(jì)算機(jī)進(jìn)行漢字信息處理，首先必須將漢字代碼化，即對漢字進(jìn)行編碼，稱為漢字輸入碼。漢字輸入碼送入計(jì)算機(jī)后還必須轉(zhuǎn)換成漢字內(nèi)部碼，才能進(jìn)行信息處理。處理完畢之后，再把漢字內(nèi)部碼轉(zhuǎn)換成漢字字形碼，才能在顯示器或打印機(jī)輸出。因此漢字的編碼有輸入碼、內(nèi)碼、字形碼三種。（1）漢字的輸入碼目前，計(jì)算機(jī)一般是使用西文標(biāo)準(zhǔn)鍵盤輸入的。為了能直接使用西文標(biāo)準(zhǔn)鍵盤輸入漢字，必須給漢字設(shè)計(jì)相應(yīng)的輸入編碼方法。其編碼方案有很多種，主要的分為三類：數(shù)字編碼、拼音碼和字形編碼。①數(shù)字編碼。常用的數(shù)字編碼是國標(biāo)區(qū)位碼，規(guī)定全部國標(biāo)漢字及符號組成94×94的矩陣。在這矩陣中，每一行稱為一個(gè)“區(qū)”，每一列稱為一個(gè)“位”。這樣，就組成了94個(gè)區(qū)（01～94區(qū)），每個(gè)區(qū)內(nèi)有94個(gè)位（01～94）的漢字字符集。區(qū)碼和位碼簡單地組合在一起（即兩位區(qū)碼居高位，兩位位碼居低位）就形成了“區(qū)位碼”。區(qū)位碼可唯一確定某一個(gè)漢字或漢字符號；反之，一個(gè)漢字或漢字符號都對應(yīng)唯一的區(qū)位碼。例如，漢字“?！钡膮^(qū)位碼為“1803”（即在18區(qū)的第3位）。所有漢字及符號的94個(gè)區(qū)劃分成如下四個(gè)組：◆1～15區(qū)為圖形符號區(qū)，其中，1～9區(qū)為標(biāo)準(zhǔn)區(qū)，10～15區(qū)為自定義符號區(qū)?！?6～55區(qū)為一級常用漢字區(qū)，共有3755個(gè)漢字，該區(qū)的漢字按拼音排序。◆56～87區(qū)為二級非常用漢字區(qū)，共有3008個(gè)漢字，該區(qū)的漢字按部首排序。◆88～94區(qū)為用戶自定義漢字區(qū)。數(shù)字編碼輸入的優(yōu)點(diǎn)是無重碼，輸入碼與內(nèi)部編碼的轉(zhuǎn)換比較方便；缺點(diǎn)是代碼難以記憶。②拼音碼。拼音碼是以漢語拼音為基礎(chǔ)的輸入方法。凡掌握漢語拼音的人，不需訓(xùn)練和記憶，即可使用，但漢字同音字太多，輸入重碼率很高，因此按拼音輸入后還必須進(jìn)行同音字選擇，影響了輸入速度。③字形編碼。字形編碼是用漢字的形狀來進(jìn)行的編碼。漢字總數(shù)雖多，但是由一筆一畫組成，全部漢字的部件和各行其實(shí)是有限的。因此，把漢字的筆畫部件用字母或數(shù)字進(jìn)行編碼，按筆畫的順序依次輸入，就能表示一個(gè)漢字了。五筆字型編碼就是最有影響的一種字形編碼方法。（2）漢字的內(nèi)碼同一個(gè)漢字以不同輸入方式進(jìn)入計(jì)算機(jī)時(shí)，編碼長度及0、1組合順序差別很大，使?jié)h字信息進(jìn)一步存取、使用、交流十分不方便，必須轉(zhuǎn)換成長度一致、且與漢字唯一對應(yīng)的能在各種計(jì)算機(jī)系統(tǒng)內(nèi)通用的編碼，滿足這種規(guī)則的編碼叫漢字內(nèi)碼。漢字內(nèi)碼是用于漢字信息的存儲、交換檢索等操作的機(jī)內(nèi)代碼，一般采用兩個(gè)字節(jié)表示。英文字符的機(jī)內(nèi)代碼是7位的ASCII碼，當(dāng)用一個(gè)字節(jié)表示時(shí)，最高位為“0”。為了與英文字符能夠區(qū)別，漢字機(jī)內(nèi)代碼中兩個(gè)字節(jié)的最高位均規(guī)定為“1”。有些系統(tǒng)中字節(jié)的最高位用于奇偶校驗(yàn)位或采用擴(kuò)展ASCII碼，這種情況下用三個(gè)字節(jié)表示漢字內(nèi)碼。（3）漢字的字形碼存儲中計(jì)算機(jī)內(nèi)的漢字需要在屏幕上顯示或在打印機(jī)上輸出時(shí)，需要知道漢字的字形信息。漢字內(nèi)碼并不能直接反映漢字的字形，而要采用專門的字形碼。目前的漢字處理系統(tǒng)中，字形信息的表示大體上有兩類形式：一類是用活字或文字版的母體字形形式；另一類是點(diǎn)陣表示法、矢量表示法等形式，其中最基本的，也是大多數(shù)字形庫采用的是以點(diǎn)陣的形式存儲漢字字形編碼的方法。點(diǎn)陣字形是將字符的字形分解成若干“點(diǎn)”組成的點(diǎn)陣，將此點(diǎn)陣置于網(wǎng)格上，每一小方格是點(diǎn)陣中的一個(gè)“點(diǎn)”，點(diǎn)陣中的每一個(gè)點(diǎn)可以有黑白兩種顏色，有字形筆畫的點(diǎn)用黑色；反之用白色，這樣就能描寫出漢字字形了。圖1-1是漢字“次”的點(diǎn)陣，如果用十進(jìn)制的“1”表示黑色點(diǎn)，用“0”表示沒有筆畫的白色點(diǎn)，每一行16個(gè)點(diǎn)用兩字節(jié)表示，則需32字節(jié)描述一個(gè)漢字的字形，即一個(gè)字形碼占32字節(jié)。圖1-1漢字“次”的點(diǎn)陣一個(gè)計(jì)算機(jī)漢字處理系統(tǒng)常配有宋體、仿宋、黑體、楷體等多種字體。同一個(gè)漢字不同字體的字形編碼是不相同的。根據(jù)漢字輸出的要求不同，點(diǎn)陣的多少也不同。簡易型漢字為16×16點(diǎn)陣，提高型漢字為24×24點(diǎn)陣、32×32點(diǎn)陣，甚至更高。點(diǎn)陣越大，描述的字形越細(xì)致美觀，質(zhì)量越高，所占存儲空間也越大。漢字點(diǎn)陣的信息量是很大的，以16×16點(diǎn)陣為例，每個(gè)漢字要占用32個(gè)字節(jié)，國標(biāo)兩級漢字要占用256KB。因此字模點(diǎn)陣只能用來構(gòu)成漢字庫，而不能用于機(jī)內(nèi)存儲。通常，計(jì)算機(jī)中所有漢字的字形碼集合起來組成漢字庫（或稱為字模庫）存放在計(jì)算機(jī)里，當(dāng)漢字輸出時(shí)由專門的字形檢索程序根據(jù)這個(gè)漢字的內(nèi)碼從漢字庫里檢索出對應(yīng)的字形碼，由字形碼再控制輸出設(shè)備輸出漢字。漢字點(diǎn)陣字形的漢字庫結(jié)構(gòu)簡單，但是當(dāng)需要對漢字進(jìn)行放大、縮小、平移、傾斜、旋轉(zhuǎn)、投影等變換時(shí)，漢字的字形效果不好。若使用矢量漢字庫、曲線字庫的漢字，其字形用直線或曲線表示，能產(chǎn)生高質(zhì)量的輸出字形。綜上所述，漢字從送入計(jì)算機(jī)到輸出顯示，漢字信息編碼形式不盡相同。漢字的輸入編碼、漢字內(nèi)碼、字形碼是計(jì)算機(jī)中用于輸入、內(nèi)部處理、輸出三種不同用途的編碼，不要混為一談。1.1.4圖形數(shù)據(jù)在計(jì)算機(jī)中的表示方法圖形信息是一種重要媒體，與文字、聲音等其他媒體相比，它具有直觀、明了、含義豐富等優(yōu)點(diǎn)。目前，圖形在計(jì)算機(jī)中有兩種數(shù)字化表示方法，一種稱為幾何圖形或矢量圖形，簡稱圖形（Graphics）；另一種稱為點(diǎn)陣圖像或位圖圖像（Image）。下面分別進(jìn)行簡單的介紹。1.圖形（Graphics）圖形表示法是根據(jù)畫面或場景中包含的內(nèi)容，分別用幾何要素（如點(diǎn)、線、面、體）和物體表面的材料與性質(zhì)及環(huán)境的光照條件、用戶觀察位置等來描述。計(jì)算機(jī)圖形學(xué)的任務(wù)是先對處理對象進(jìn)行描述（建模），然后對該模型進(jìn)行必要的處理加工，最后再產(chǎn)生能正確反映該物體的或場景視覺圖像的圖形輸出。計(jì)算機(jī)不僅能夠生成靜止圖形，而且還能生成各種運(yùn)動(dòng)、變化的動(dòng)態(tài)圖形。計(jì)算機(jī)圖形學(xué)在計(jì)算機(jī)輔助設(shè)計(jì)和制造（CAD/CAM）、地理信息和自然資源的圖形制作、作戰(zhàn)指揮和軍事訓(xùn)練、計(jì)算機(jī)動(dòng)畫和計(jì)算機(jī)藝術(shù)、電子出版物等方面有著廣泛的應(yīng)用。2.圖像（Image）圖像表示法是把原始畫面分離成M×N個(gè)像素（Pixel），組成一個(gè)矩陣，所以它又稱為位圖表示法或點(diǎn)陣表示法。黑白畫面用一個(gè)二進(jìn)制整數(shù)來表示每個(gè)像素的灰度值，彩色畫面用多個(gè)二進(jìn)制整數(shù)來表示每個(gè)彩色像素的3個(gè)分量（紅色R、綠色G、藍(lán)色B）的灰度值。圖像表示法適合表現(xiàn)包含大量細(xì)節(jié)的類似于照片和繪畫之類的畫面。主要有以下參數(shù)：①圖像尺寸。指圖像的大小，即水平方向包含的像素的個(gè)數(shù)。②最大顏色（灰度）數(shù)。指圖像中可能出現(xiàn)的不同顏色（灰度）的最大數(shù)目，它取決于組成該圖像的所有平面中像素的位數(shù)之和，也叫圖像深度。③圖像數(shù)據(jù)量。一幅圖像的數(shù)據(jù)量以字節(jié)為單位，可以按下面的公式計(jì)算。圖像數(shù)據(jù)量=圖像寬度×圖像高度×圖像深度/8（B）計(jì)算機(jī)中所處理的黑白或彩色數(shù)字圖像，既可以通過工具軟件（如Photoshop）來創(chuàng)作生成，也能夠利用硬件設(shè)備（如掃描儀、數(shù)碼相機(jī)）來采集。圖形與圖像兩種表示方法各有優(yōu)缺點(diǎn)，它們互相補(bǔ)充、互相依存，在一定條件下還可以互相轉(zhuǎn)換，它們在計(jì)算機(jī)各種應(yīng)用領(lǐng)域中起著非常重要的作用。1.2數(shù)據(jù)存儲的字節(jié)序與位序在各種計(jì)算機(jī)體系結(jié)構(gòu)中，對于字節(jié)、字等的存儲機(jī)制有所不同。對于同一個(gè)數(shù)值，在不同的計(jì)算機(jī)體系中會以相反的順序記錄。例如，十六進(jìn)制數(shù)值12345678H，在一種計(jì)算機(jī)架構(gòu)下存儲為12345678H，而在另一種計(jì)算機(jī)架構(gòu)下會被存儲為78563412H。這就是按照不同的字節(jié)序進(jìn)行存儲的。所以所謂的字節(jié)序指的就是長度跨越多個(gè)字節(jié)的數(shù)據(jù)的存放形式。1.2.1Endian的含義目前的存儲器，多以字節(jié)為訪問的最小單元，當(dāng)一個(gè)邏輯上的單元必須分割為物理上的若干單元時(shí)就存在了先放誰后放誰的問題，于是Endian的問題應(yīng)運(yùn)而生了。對于不同的存儲方法，就有Big-endian和Little-endian兩個(gè)描述。Big-endian和Little-endian這兩個(gè)術(shù)語來自于JonathanSwift的《格利佛游記》。其中交戰(zhàn)的兩個(gè)派別無法就應(yīng)該從哪一端——小端（Little-end）還是大端（Big-end）打開一個(gè)半熟的雞蛋達(dá)成一致。支持從小端打開雞蛋的一派被稱為Little-endian，支持從大端打開雞蛋的一派則被稱為Big-endian。在那個(gè)時(shí)代，Swift是在諷刺英國和法國之間的持續(xù)沖突。后來，一位網(wǎng)絡(luò)協(xié)議的早期開創(chuàng)者DannyCohen，第一次使用這兩個(gè)術(shù)語來指代字節(jié)順序，后來這個(gè)術(shù)語被廣泛接納了。1.2.2Little-endian的含義Little-endian是一種小值的一端（或序列中較不典型的值）存儲在前的順序，也就是說，最低字節(jié)存放在最低位，最高字節(jié)存放在最高位，反序排列。依照人們的習(xí)慣來說，我們的文字及數(shù)字都是以從左到右的方式排列的，這似乎也被認(rèn)為是自然的存儲字符和數(shù)字方式。然而，Little-endian卻恰恰與我們的習(xí)慣相反。例如，按照我們的習(xí)慣寫一個(gè)十六進(jìn)制數(shù)值56AB78EFH，把這個(gè)數(shù)值以Little-endian的方式表達(dá)出來，則是EF78AB56H。1.2.3Big-endian的含義Big-endian是一種大值的一端（或序列中更典型值）存在前面（在最小的存儲地址）的順序，也就是最高字節(jié)在地址最低位，最低字節(jié)在地址最高位，依次排列。Big-endian的方式與人們的書寫習(xí)慣一致。例如，按照我們的習(xí)慣寫一個(gè)十六進(jìn)制數(shù)值56AB78EFH，把這個(gè)數(shù)值以Big-endian的方式表達(dá)出來，也是56AB78EFH。1.2.4字節(jié)序與CPU架構(gòu)的關(guān)系談到字節(jié)序的問題，必然涉及CPU的架構(gòu)。CPU從架構(gòu)上區(qū)分，有x86、x86-64、IA-64等；從指令集上區(qū)分，有CISC、RISC等。1.CPU的架構(gòu)（1）x86架構(gòu)x86又稱IA32，即IntelArchitecture32（Intel32位架構(gòu)）。它是Intel為其第一塊16位CPU（i8086）專門開發(fā)的。IBM1981年推出的世界第一臺微機(jī)中的CPU——i8088（i8086簡化版）使用的也是x86架構(gòu)。同時(shí)計(jì)算機(jī)中為提高浮點(diǎn)數(shù)據(jù)處理能力而增加了x87芯片，以后就將x86指令集和x87指令集統(tǒng)稱為x86架構(gòu)。雖然隨著CPU技術(shù)的不斷發(fā)展，Intel陸續(xù)研制出更新型的i80386、i80486、Pentium系列及至強(qiáng)系列CPU，但為了保證計(jì)算機(jī)能繼續(xù)運(yùn)行以往開發(fā)的各類應(yīng)用程序以保護(hù)和繼承豐富的軟件資源，所以Intel公司所生產(chǎn)的所有CPU仍然繼續(xù)使用x86架構(gòu)，所以它的CPU仍屬于x86系列。由于Intelx86系列及其兼容CPU（如AMD、VIA/Cyrix等）都使用x86架構(gòu)，所以就形成了今天龐大的x86系列及兼容CPU陣容。目前基本上所有x86架構(gòu)的CPU對數(shù)據(jù)的處理，都采用Little-endian字節(jié)序。（2）x86-64架構(gòu)x86-64架構(gòu)是由AMD公司設(shè)計(jì)的，也稱為AMD64。它可以在同一時(shí)間內(nèi)處理64位的整數(shù)運(yùn)算，并兼容于x86-32架構(gòu)。其中支持64位邏輯定址，同時(shí)提供轉(zhuǎn)換為32位定址選項(xiàng)；但數(shù)據(jù)操作指令默認(rèn)為32位和8位，提供轉(zhuǎn)換成64位和16位的選項(xiàng)；支持常規(guī)用途寄存器，如果是32位運(yùn)算操作，就要將結(jié)果擴(kuò)展成完整的64位。這樣，指令中有“直接執(zhí)行”和“轉(zhuǎn)換執(zhí)行”的區(qū)別，其指令字段是8位或32位，可以避免字段過長。x86-64架構(gòu)的CPU對數(shù)據(jù)的處理，也采用Little-endian字節(jié)序。（3）IA-64架構(gòu)IA-64架構(gòu)是Intel為了全面提高以前IA-32處理器的運(yùn)算性能，和HP公司共同開發(fā)了6年的64位CPU架構(gòu)，是專為服務(wù)器市場開發(fā)的一種全新的處理器。它放棄了以前的x86架構(gòu)，認(rèn)為它嚴(yán)重阻礙了處理器的性能提高。IA-64架構(gòu)的最初應(yīng)用是英特爾的Itanium（安騰）系列服務(wù)器處理器，后來的Itanium2系列處理器也采用這一架構(gòu)。由于它不能很好地解決與以前32位應(yīng)用程序的兼容，所以應(yīng)用受到較大的限制，盡管目前Intel采取了各種軟、硬方法來彌補(bǔ)這一不足，但隨著AMDx86-64架構(gòu)處理器的全面投入，Intel的IA-64架構(gòu)的這兩款處理器前景不容樂觀。IA-64架構(gòu)的CPU對數(shù)據(jù)的處理，字節(jié)序是可配置的，既可以采用Little-endian，也可以采用Big-endian。2.CPU的指令集（1）CISC指令集CISC指令集，也稱為復(fù)雜指令集，是“ComplexInstructionSetComputer”的縮寫。在CISC微處理器中，程序的各條指令是按順序串行執(zhí)行的，每條指令中的各個(gè)操作也是按順序串行執(zhí)行的。順序執(zhí)行的優(yōu)點(diǎn)是控制簡單，但計(jì)算機(jī)各部分的利用率不高，執(zhí)行速度慢。Intel生產(chǎn)的x86架構(gòu)（也就是IA-32架構(gòu)）CPU及其兼容如AMD、VIA等CPU，都屬于CISC指令集的范疇。CISC指令集的CPU對數(shù)據(jù)的處理，基本上都采用Little-endian字節(jié)序。（2）RISC指令集RISC是英文“ReducedInstructionSetComputer”的縮寫，中文意思是“精簡指令集”。RISC是在CISC指令集基礎(chǔ)上發(fā)展起來的。有人對CISC機(jī)進(jìn)行測試表明，各種指令的使用頻度相當(dāng)懸殊，最常使用的是一些比較簡單的指令，它們僅占指令總數(shù)的20%，但在程序中出現(xiàn)的頻度卻占80%。復(fù)雜的指令系統(tǒng)必然增加微處理器的復(fù)雜性，使處理器的研制時(shí)間長，成本高。并且復(fù)雜指令需要復(fù)雜的操作，必然會降低計(jì)算機(jī)的速度?；谏鲜鲈?，20世紀(jì)80年代RISC指令集CPU誕生了。相對于CISC指令集CPU,RISC的CPU不僅精簡了指令系統(tǒng)，還采用了一種叫作“超標(biāo)量和超流水線結(jié)構(gòu)”，大大增加了并行處理能力。RISC指令集是高性能CPU的發(fā)展方向，相比而言，RISC的指令格式統(tǒng)一，種類比較少，尋址方式也比復(fù)雜指令集少，當(dāng)然處理速度就提高很多了。目前在中高檔服務(wù)器中普遍采用這一指令系統(tǒng)的CPU，特別是高檔服務(wù)器幾乎全都采用RISC指令集的CPU。RISC指令集CPU與Intel和AMD的CISC指令集CPU在軟件和硬件上都不兼容。目前，在中高檔服務(wù)器中采用RISC指令的CPU主要有PowerPC處理器、SPARC處理器、PA-RISC處理器、MIPS處理器、Alpha處理器等。RISC指令集的CPU對數(shù)據(jù)的處理，大部分都采用Big-endian字節(jié)序。1.2.5位序的含義前面講解了字節(jié)序有Little-endian和Big-endian之分，然而一個(gè)字節(jié)是由8位構(gòu)成的，CPU存儲一個(gè)字節(jié)的數(shù)據(jù)時(shí)其字節(jié)內(nèi)的8個(gè)位之間的順序是否也有Little-endian和Big-endian之分呢？例如，一個(gè)十六進(jìn)制數(shù)值8AH，換算成二進(jìn)制為10001010B，按照Little-endian的位序書寫應(yīng)該是01010001B，按照Big-endian的位序書寫則是10001010B。實(shí)際上，現(xiàn)在的CPU和程序幾乎都是設(shè)計(jì)成Big-endian位序的，也就是說無論在Bigendian還是在Little-endian字節(jié)順序中，每一個(gè)字節(jié)中的8位里面都是使用Big-endian。1.3數(shù)據(jù)的邏輯運(yùn)算邏輯運(yùn)算又稱布爾運(yùn)算，布爾是英國的數(shù)學(xué)家，在1847年發(fā)明了處理二值之間關(guān)系的邏輯數(shù)學(xué)計(jì)算法，他用等式表示判斷，把推理看作等式的變換。這種變換的有效性不依賴人們對符號的解釋，只依賴于符號的組合規(guī)律。20世紀(jì)30年代，邏輯代數(shù)在電路系統(tǒng)上獲得應(yīng)用，隨后，由于電子技術(shù)與計(jì)算機(jī)的發(fā)展，出現(xiàn)各種復(fù)雜的大系統(tǒng)，它們的變換規(guī)律也遵守布爾所揭示的規(guī)律。邏輯運(yùn)算用來判斷一件事情是“對”的還是“錯(cuò)”的，或者說是“真”還是“假”，判斷的結(jié)果是二值的，即沒有“可能是”或者“可能不是”。這個(gè)“可能”的用法是一個(gè)模糊概念，在計(jì)算機(jī)里面進(jìn)行的是二進(jìn)制運(yùn)算，邏輯判斷的結(jié)果只有兩個(gè)值，稱這兩個(gè)值為“邏輯值”，用數(shù)的符號來表示就是“1”和“0”。其中“1”表示該邏輯運(yùn)算的結(jié)果是“真”的，如果一個(gè)邏輯運(yùn)算式的結(jié)果為“0”，那么這個(gè)邏輯運(yùn)算式表達(dá)的內(nèi)容為“假”。計(jì)算機(jī)的邏輯運(yùn)算與算術(shù)運(yùn)算的主要區(qū)別：邏輯運(yùn)算是按位進(jìn)行的，位與位之間不像加減運(yùn)算那樣有進(jìn)位或借位的聯(lián)系。邏輯運(yùn)算主要包括三種基本運(yùn)算：邏輯加法（又稱“或”運(yùn)算）、邏輯乘法（又稱“與”運(yùn)算）和邏輯否定（又稱“非”運(yùn)算）。此外，還有一種“異或”運(yùn)算也很有用，在RAID中就大量使用這種運(yùn)算作為校驗(yàn)算法。1.3.1邏輯或邏輯“或”運(yùn)算也稱為邏輯加運(yùn)算，運(yùn)算符有“+”、“∨”、“OR”等幾種?！盎颉边壿嬍侵府?dāng)輸入變量中有一個(gè)滿足條件（例如，為1有效）時(shí)，輸出就有效（例如，為1）。只有當(dāng)所有輸入變量均不滿足條件（例如，為0）時(shí)，輸出才無效（為0）。也就是說，在給定的邏輯變量中，只要有一個(gè)為1，其邏輯加的結(jié)果為1；邏輯變量都為0則邏輯加為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=10100001、y=10011011，求x∨y。運(yùn)算如下：即x∨y=101110111.3.2邏輯與邏輯“與”運(yùn)算又稱為邏輯乘運(yùn)算，通常用符號“×”或“∧”或“·”來表示?！芭c”邏輯是指當(dāng)所有輸入都同時(shí)滿足條件（例如，都為1）時(shí)，輸出才有效（例如，為1）；否則輸出無效（為0）。也就是說，只有當(dāng)參與運(yùn)算的邏輯變量都同時(shí)取值為1時(shí)，其邏輯乘積才等于1。其運(yùn)算規(guī)則如下：0×0=0,0∧0=0,0·0=00×1=0,0∧1=0,0·1=01×0=0,1∧0=0,1·0=01×1=1,1∧1=1,1·1=1例如，x=10111001、y=11110011，求x∧y。運(yùn)算如下：即x∧y=10110001。1.3.3邏輯非邏輯“非”運(yùn)算也稱為邏輯反運(yùn)算，運(yùn)算符為在變量上畫一條橫線?！胺恰边壿嬍侵府?dāng)輸入變量中為1時(shí)，輸出為0；輸入為0時(shí)，輸出為1。也就是說，0的非為1,1的非為0。例如，A=10110101，求。運(yùn)算如下：即。1.3.4邏輯異或異或運(yùn)算通常用符號“⊕”表示，其運(yùn)算規(guī)則為：0⊕0=00⊕1=11⊕0=11⊕1=0這種邏輯運(yùn)算在RAID中是一種很重要的算法，需要熟練掌握。例如，x=10101011、y=11001100，求x⊕y。運(yùn)算如下：即x⊕y=01100111。1.4數(shù)據(jù)恢復(fù)中常用的數(shù)據(jù)結(jié)構(gòu)如果想對數(shù)據(jù)恢復(fù)技術(shù)的掌握達(dá)到一定的高度，就不能缺少對數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，因?yàn)樵跀?shù)據(jù)的存儲和管理中處處離不開數(shù)據(jù)結(jié)構(gòu)，例如硬盤的分區(qū)結(jié)構(gòu)、文件系統(tǒng)結(jié)構(gòu)等，都是對數(shù)據(jù)結(jié)構(gòu)的具體應(yīng)用。1.4.1數(shù)據(jù)結(jié)構(gòu)簡介數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)學(xué)科中的一門專業(yè)課程，更是程序設(shè)計(jì)中不可或缺的一個(gè)專業(yè)知識，瑞士的一名計(jì)算機(jī)專家則更直接地說：算法+數(shù)據(jù)結(jié)構(gòu)=程序設(shè)計(jì)，可想數(shù)據(jù)結(jié)構(gòu)在程序中的重要性。本書的內(nèi)容不是程序設(shè)計(jì)，而是數(shù)據(jù)恢復(fù)技術(shù)，所以不能花費(fèi)大量篇幅系統(tǒng)介紹數(shù)據(jù)結(jié)構(gòu)，只能針對數(shù)據(jù)恢復(fù)技術(shù)中用到的一些數(shù)據(jù)結(jié)構(gòu)知識進(jìn)行講解。1.數(shù)據(jù)結(jié)構(gòu)的基本概念（1）什么是數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)，是指所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的符號（數(shù)字、字符等）的集合，它是計(jì)算機(jī)操作對象的總稱。（2）數(shù)據(jù)元素?cái)?shù)據(jù)元素是數(shù)據(jù)集合中的一個(gè)“個(gè)體”，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理，是數(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)”。例如描述一個(gè)學(xué)生的信息的數(shù)據(jù)元素可由“姓名、學(xué)號、性別、班級、出生日期、入學(xué)成績”6個(gè)數(shù)據(jù)項(xiàng)組成。其中的出生日期又可以由三個(gè)數(shù)據(jù)項(xiàng)：年、月和日組成，則稱“出生日期”為“組合項(xiàng)”，而其他不可分割的數(shù)據(jù)項(xiàng)為“原子項(xiàng)”。所以，數(shù)據(jù)項(xiàng)是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位。（3）關(guān)鍵字關(guān)鍵字是指能識別一個(gè)或多個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。若能起唯一識別作用，則稱為“主關(guān)鍵字”，否則稱為“次關(guān)鍵字”。（4）數(shù)據(jù)對象數(shù)據(jù)對象是具有相同特性的數(shù)據(jù)元素的集合，如整數(shù)、實(shí)數(shù)等。數(shù)據(jù)對象是數(shù)據(jù)的一個(gè)子集。（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.數(shù)據(jù)結(jié)構(gòu)的分類（1）按照數(shù)據(jù)結(jié)構(gòu)的關(guān)系分類數(shù)據(jù)結(jié)構(gòu)按關(guān)系分類有四種：線性結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu)和集合結(jié)構(gòu)。線性結(jié)構(gòu)如圖1-2所示。圖1-2線性結(jié)構(gòu)樹結(jié)構(gòu)如圖1-3所示。圖結(jié)構(gòu)如圖1-4所示。圖1-3樹結(jié)構(gòu)圖1-4圖結(jié)構(gòu)集合結(jié)構(gòu)如圖1-5所示。（2）按照數(shù)據(jù)結(jié)構(gòu)的層次分類數(shù)據(jù)結(jié)構(gòu)按層次分類有兩種：數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)是對數(shù)據(jù)元素之間存在的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)元素的集合來定義在此集合上的若干關(guān)系。數(shù)據(jù)的邏輯結(jié)構(gòu)又分為線性關(guān)系和非線性關(guān)系。前面講過的線性結(jié)構(gòu)就是線性關(guān)系，而非線性關(guān)系包括圖結(jié)構(gòu)和樹結(jié)構(gòu)。例如，某學(xué)校的一個(gè)年級有兩個(gè)班，由同一個(gè)班主任帶班，每個(gè)班按所住宿舍分組，他們之間的關(guān)系就是非線性關(guān)系，如圖1-6所示。圖1-5集合結(jié)構(gòu)圖1-6非線性關(guān)系圖數(shù)據(jù)物理結(jié)構(gòu)是數(shù)據(jù)邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示和實(shí)現(xiàn)，故又稱數(shù)據(jù)“存儲結(jié)構(gòu)”。之前對數(shù)據(jù)結(jié)構(gòu)的定義還只是數(shù)學(xué)上的抽象概念，并沒有涉及計(jì)算機(jī)。完整的數(shù)據(jù)結(jié)構(gòu)定義還應(yīng)該包括它在計(jì)算機(jī)中的表示，即數(shù)據(jù)的“存儲結(jié)構(gòu)”。存儲結(jié)構(gòu)有四種方法，它們是順序（Sequential）、鏈?zhǔn)剑↙inked）、索引（Indexed）和散列（Hashing）。在本書后面將要重點(diǎn)講解的分區(qū)結(jié)構(gòu)和文件系統(tǒng)結(jié)構(gòu)中，都會用到這些存儲方法。①順序存儲方法：把邏輯上相鄰的節(jié)點(diǎn)存儲在物理位置相鄰的存儲單元里，節(jié)點(diǎn)間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)，由此得到的存儲表示叫作順序存儲結(jié)構(gòu)。提示在FAT文件系統(tǒng)中對子目錄的管理就用到了這種存儲結(jié)構(gòu)。②鏈?zhǔn)酱鎯Ψ椒ǎ核灰筮壿嬌舷噜彽墓?jié)點(diǎn)在物理位置上也相鄰，節(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的，由此得到的存儲表示叫作鏈?zhǔn)酱鎯Y(jié)構(gòu)。提示在FAT文件系統(tǒng)中對文件所占簇的管理，就是用指針的方式實(shí)現(xiàn)鏈?zhǔn)酱鎯Φ?。③索引存儲方法：除建立?jié)點(diǎn)存儲信息外，還建立附加的索引表來表示節(jié)點(diǎn)的地址，由此得到的存儲表示叫作索引存儲結(jié)構(gòu)。提示NTFS文件系統(tǒng)中對目錄結(jié)構(gòu)的管理就用到了索引存儲結(jié)構(gòu)。④散列存儲方法：根據(jù)節(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該節(jié)點(diǎn)的存儲地址，由此得到的存儲表示叫作散列存儲結(jié)構(gòu)。提示Linux的EXT3文件系統(tǒng)中對目錄結(jié)構(gòu)的管理就用到了散列存儲結(jié)構(gòu)。1.4.2樹前面提到過，數(shù)據(jù)結(jié)構(gòu)按關(guān)系分類有四種：線性結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu)和集合結(jié)構(gòu)，其中樹結(jié)構(gòu)在文件系統(tǒng)中使用最多，所以本書重點(diǎn)講解樹結(jié)構(gòu)。1.樹的定義樹形結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，它是由n（n≥1）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。在樹結(jié)構(gòu)中，用一個(gè)圓圈表示一個(gè)節(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)的后繼。把它叫作樹是因?yàn)樗雌饋硐褚豢玫箳斓臉?，也就是說它是根朝上，而葉朝下的。圖1-7是一個(gè)“樹”結(jié)構(gòu)的示意圖。在圖1-7中，A是根節(jié)點(diǎn)，它一般畫在樹的頂部。其余節(jié)點(diǎn)分成兩個(gè)互不相交的子集：T0={B,D,E,F,I,J,K},T1={C,G,H,L,M,N,O,P}，它們都是根節(jié)點(diǎn)A的子樹。再看T0，它的根是B，其余根節(jié)點(diǎn)又分為3個(gè)互不相交的子集T00={D,I,K},T01={E,J}，T03={F}，它們是T0的子樹。圖1-7“樹”結(jié)構(gòu)的示意圖2.樹結(jié)構(gòu)的基本術(shù)語①節(jié)點(diǎn)。節(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支。例如，在圖1-7中的樹總共有16個(gè)節(jié)點(diǎn)，為方便起見，每個(gè)數(shù)據(jù)項(xiàng)用單個(gè)字母表示。②節(jié)點(diǎn)的度。節(jié)點(diǎn)的度是指節(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)。例如，在圖1-7所示的樹中，根A的度為2，節(jié)點(diǎn)B的度為3，節(jié)點(diǎn)K、J、F、L、O、P的度為0。③樹的度。樹的度指的是樹中各節(jié)點(diǎn)的度的最大值。例如，圖1-7所示的樹的度為3。④葉節(jié)點(diǎn)（終端節(jié)點(diǎn)）。葉節(jié)點(diǎn)指度為0的節(jié)點(diǎn)。例如，在圖1-7所示的樹中，{K,J,F,L,O,P}構(gòu)成樹的葉節(jié)點(diǎn)的集合。⑤分支節(jié)點(diǎn)（非終端節(jié)點(diǎn)）。分支節(jié)點(diǎn)指除葉節(jié)點(diǎn)以外的節(jié)點(diǎn)（度不為0的節(jié)點(diǎn)）。例如，在圖1-7所示的樹中，A、B、C、D、E、G、H、I、M、N就是分支節(jié)點(diǎn)。⑥子女節(jié)點(diǎn)。若節(jié)點(diǎn)x有子樹，則子樹的根節(jié)點(diǎn)即為節(jié)點(diǎn)x的子女。例如，在圖1-7所示的樹中，節(jié)點(diǎn)A有2個(gè)子女，節(jié)點(diǎn)B有3個(gè)子女，節(jié)點(diǎn)K沒有子女。子女節(jié)點(diǎn)也稱作孩子節(jié)點(diǎn)。⑦雙親節(jié)點(diǎn)。若節(jié)點(diǎn)x有子女，x即為子女的雙親。例如，在圖1-7所示的樹中，節(jié)點(diǎn)B、C有一個(gè)雙親A，根節(jié)點(diǎn)A沒有雙親。雙親節(jié)點(diǎn)也叫父節(jié)點(diǎn)。⑧兄弟節(jié)點(diǎn)。同一雙親的子女互稱為兄弟。例如，在圖1-7所示的樹中，節(jié)點(diǎn)B、C稱為兄弟；D、E、F也稱為兄弟；但F、G、H不是兄弟。⑨堂兄弟節(jié)點(diǎn)。雙親在同一層的節(jié)點(diǎn)互為堂兄弟節(jié)點(diǎn)。例如，在圖1-7所示的樹中，G和H是F的堂兄弟節(jié)點(diǎn)。⑩祖先節(jié)點(diǎn)。祖先節(jié)點(diǎn)是指從根節(jié)點(diǎn)到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)。例如，在圖1-7所示的樹中，節(jié)點(diǎn)K的祖先為A、B、D、I。?子孫節(jié)點(diǎn)。某一節(jié)點(diǎn)的子女，以及這些子女的子女都是該節(jié)點(diǎn)的子孫。例如，在圖1-7所示的樹中，節(jié)點(diǎn)B的子孫為D、E、F、I、J、K。?節(jié)點(diǎn)的層次。樹中的每個(gè)節(jié)點(diǎn)都處在一定的層次上，即從根到該節(jié)點(diǎn)所經(jīng)路徑上的分支條數(shù)。例如，在圖1-7所示的樹中，根節(jié)點(diǎn)在第1層，它的子女節(jié)點(diǎn)在第2層，以此類推，樹中任意一節(jié)點(diǎn)的層次為它的雙親節(jié)點(diǎn)的層次加1。?樹的高（深）度。樹的高度是指樹中節(jié)點(diǎn)所處的最大層次，空樹的高度為0，只有一個(gè)根節(jié)點(diǎn)的樹的高度為1。例如，在圖1-7所示的樹中，樹的高度為5。?有序樹。有序樹指樹中各節(jié)點(diǎn)的子樹是按照一定的次序從左向右排列的，且相對次序是不能隨意變換的。?無序樹。無序樹是指樹中各節(jié)點(diǎn)的子樹是沒有一定的排列次序，且相對次序是可以隨意變換的。?森林。森林指n（n≥0）個(gè)互不相交的樹的集合。刪去一棵非空樹的根節(jié)點(diǎn)，樹就變成森林；反之，若增加一個(gè)根節(jié)點(diǎn)，讓森林中每一棵樹的根節(jié)點(diǎn)都變成它的子女，森林就成為一棵樹。3.樹結(jié)構(gòu)的特點(diǎn)樹結(jié)構(gòu)具有以下的特點(diǎn)：①每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)；②每一個(gè)子節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)；③沒有前驅(qū)的節(jié)點(diǎn)為根節(jié)點(diǎn)；④除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為m個(gè)不相交的子樹。1.4.3二叉樹二叉樹是一種應(yīng)用廣泛的樹形結(jié)構(gòu)，它的特點(diǎn)是每個(gè)節(jié)點(diǎn)最多只能有兩個(gè)孩子。在二叉樹中，必須嚴(yán)格區(qū)分左右孩子，次序不能顛倒。1.二叉樹的定義二叉樹是樹形結(jié)構(gòu)的一種，只要對樹結(jié)構(gòu)加以限制就得到二叉樹的定義。首先二叉樹是n（n≥0）個(gè)節(jié)點(diǎn)的有限集合，并且滿足下面的任意一個(gè)條件：①為空二叉樹，即n=0。②由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的被稱為根的左子樹和右子樹所組成。左子樹和右子樹分別為一棵二叉樹。所以，二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的有序樹，通常子樹被稱做“左子樹”和“右子樹”,“左子樹”和“右子樹”的順序不能任意顛倒。例如，圖1-8中的（a）和（b）就是兩個(gè)完全不同的二叉樹。圖1-8兩個(gè)完全不同的二叉樹2.樹和二叉樹的區(qū)別從樹和二叉樹的定義中可以看出它們有三個(gè)主要差別：①樹的節(jié)點(diǎn)個(gè)數(shù)至少為1，而二叉樹的節(jié)點(diǎn)個(gè)數(shù)可以為0；②樹中節(jié)點(diǎn)的最大度數(shù)沒有限制，而二叉樹節(jié)點(diǎn)的最大度數(shù)為2；③樹的節(jié)點(diǎn)無左、右之分，而二叉樹的節(jié)點(diǎn)有左、右之分。3.二叉樹的基本形態(tài)從二叉樹的定義中可以得到二叉樹的5種基本形態(tài)：①空二叉樹，其結(jié)構(gòu)如圖1-9所示。②僅有根節(jié)點(diǎn)的二叉樹，其結(jié)構(gòu)如圖1-10所示。③右子樹為空的二叉樹，其結(jié)構(gòu)如圖1-11所示。圖1-9空二叉樹圖1-10僅有根節(jié)點(diǎn)的二叉樹圖1-11右子樹為空的二叉樹④左子樹為空的二叉樹，其結(jié)構(gòu)如圖1-12所示。⑤左、右子樹均為非空的二叉樹，其結(jié)構(gòu)如圖1-13所示。圖1-12左子樹為空的二叉樹圖1-13左、右子樹均為非空的二叉樹4.二叉樹的類型①滿二叉樹。滿二叉樹是指除了葉節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都有左右子女且葉節(jié)點(diǎn)都處在最底層的二叉樹（見圖1-14）。②完全二叉樹。除最后一層外，每一層上的節(jié)點(diǎn)數(shù)均達(dá)到最大值，并且在最后一層上只缺少右邊的若干節(jié)點(diǎn)，這樣的二叉樹稱為完全二叉樹（見圖1-15）。圖1-14滿二叉樹圖1-15完全二叉樹1.4.4B樹、B-樹、B+樹和B*樹樹結(jié)構(gòu)中除了比較常見的二叉樹外，還有B樹及B樹的一些變種。這些樹結(jié)構(gòu)在文件系統(tǒng)中主要用于對目錄結(jié)構(gòu)的管理，如對目錄及文件的訪問、新建、刪除等，就相當(dāng)于對相應(yīng)的樹結(jié)構(gòu)的查找、插入、刪除。1.B樹（1）B樹的定義B樹也就是二叉搜索樹，需要滿足下列條件：①所有非葉節(jié)點(diǎn)至多擁有兩個(gè)孩子（左孩子和右孩子）；②所有節(jié)點(diǎn)存儲一個(gè)關(guān)鍵字；③非葉節(jié)點(diǎn)的左指針指向小于其關(guān)鍵字的子樹，右指針指向大于其關(guān)鍵字的子樹。如圖1-16所示的就是一個(gè)B樹。圖1-16B樹結(jié)構(gòu)圖（2）B樹的查找B樹的查找，從根節(jié)點(diǎn)開始，如果查詢的關(guān)鍵字與節(jié)點(diǎn)的關(guān)鍵字相等，那么就命中；否則，如果查詢關(guān)鍵字比節(jié)點(diǎn)關(guān)鍵字小，就進(jìn)入左孩子；如果比節(jié)點(diǎn)關(guān)鍵字大，就進(jìn)入右孩子；如果左孩子或右孩子的指針為空，則報(bào)告找不到相應(yīng)的關(guān)鍵字。2.B-樹（1）B?樹的定義B?樹是一種平衡的多叉樹，通常說m階的B?樹，必須滿足如下條件：①每個(gè)節(jié)點(diǎn)至多有m個(gè)孩子節(jié)點(diǎn)；②除根節(jié)點(diǎn)和葉節(jié)點(diǎn)外，其他每個(gè)節(jié)點(diǎn)至少有m/2個(gè)孩子節(jié)點(diǎn)；③若根節(jié)點(diǎn)不是葉節(jié)點(diǎn)，則至少有兩個(gè)孩子節(jié)點(diǎn)；④所有的葉節(jié)點(diǎn)在同一層，葉節(jié)點(diǎn)不包含任何關(guān)鍵字信息；⑤有k個(gè)子節(jié)點(diǎn)的非終端節(jié)點(diǎn)最多包含k?1個(gè)關(guān)鍵字信息。如圖1-17所示的就是一個(gè)B?樹。圖1-17B?樹結(jié)構(gòu)圖（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ù)上面的操作，直到查找成功或者指針為空為止。（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)里去。父節(jié)點(diǎn)也可能是滿的，就需要再分裂，再往上插。最壞的情況，這個(gè)過程可能一直傳到根節(jié)點(diǎn)。如果需要分裂根節(jié)點(diǎn)，由于根節(jié)點(diǎn)是沒有父節(jié)點(diǎn)的，這時(shí)就建立一個(gè)新的根節(jié)點(diǎn)。插入可能導(dǎo)致B?樹朝著根的方向生長。例如，要在圖1-18所示的一個(gè)6階B?樹結(jié)構(gòu)中插入關(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-18一個(gè)6階B?樹結(jié)構(gòu)將關(guān)鍵字“36”成功插入后，該B?樹的結(jié)構(gòu)如圖1-19所示。圖1-19關(guān)鍵字“36”插入后的結(jié)構(gòu)（4）B?樹的刪除B?樹的刪除分兩種情況：①B?樹中的刪除操作與插入操作類似，但要稍微復(fù)雜些。如果刪除的關(guān)鍵字不在葉節(jié)點(diǎn)層，則先把此關(guān)鍵字與它在B?樹里的后繼對換位置，然后再刪除該關(guān)鍵字。②如果刪除的關(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)移若干個(gè)關(guān)鍵字到該節(jié)點(diǎn)中來（這也涉及它們的父節(jié)點(diǎn)中的一個(gè)關(guān)鍵字要做相應(yīng)變化），使兩個(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-20所示的一個(gè)3階B?樹結(jié)構(gòu)中刪除關(guān)鍵字“46”，刪除后該節(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)為“0”，低于規(guī)定的最低限“1”，而它的左兄弟和右兄弟的關(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?樹的結(jié)構(gòu)如圖1-21所示。圖1-20一個(gè)3階B?樹結(jié)構(gòu)圖1-21關(guān)鍵字“46”刪除后的結(jié)構(gòu)3.B+樹（1）B+樹的定義B+樹是B?樹的一種變體，它與B?樹的差異在于：①在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)鍵字對應(yīng)一棵子樹。②在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。③B+樹中的所有葉節(jié)點(diǎn)包含了全部關(guān)鍵字及指向?qū)?yīng)記錄的指針，且所有葉節(jié)點(diǎn)按關(guān)鍵字從小到大的順序依次鏈接。④B+樹中所有非葉節(jié)點(diǎn)僅起到索引的作用，即節(jié)點(diǎn)中的每個(gè)索引項(xiàng)只含有對應(yīng)子樹的最大關(guān)鍵字和指向該子樹的指針，不含有該關(guān)鍵字對應(yīng)記錄的存儲地址。例如，圖1-22所示的一棵3階B+樹，其中葉節(jié)點(diǎn)的每個(gè)關(guān)鍵字下面的指針表示指向?qū)?yīng)記錄的存儲位置。通常在B++樹上有兩個(gè)頭指針：一個(gè)指向根節(jié)點(diǎn)，用于從根節(jié)點(diǎn)起對數(shù)進(jìn)行查找、插入、刪除等操作；另一個(gè)指向關(guān)鍵字最小的葉節(jié)點(diǎn)，用于從最小的關(guān)鍵字起進(jìn)行順序查找和處理每一個(gè)葉節(jié)點(diǎn)中的關(guān)鍵字及記錄。圖1-22一棵3階B+樹結(jié)構(gòu)由于B?樹只適合隨機(jī)檢索，B+樹同時(shí)支持隨機(jī)檢索和順序檢索，在實(shí)際中應(yīng)用比較多，NTFS文件系統(tǒng)就是使用B+樹進(jìn)行動(dòng)態(tài)索引的。（2）B+樹的查找B+樹的查找與B?樹的查找類似，但是也有不同。由于與記錄有關(guān)的信息都存放在葉節(jié)點(diǎn)中，查找時(shí)若在上層已找到待查的關(guān)鍵字，并不停止，而是繼續(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)鍵字個(gè)數(shù)超過m，就必須分裂成關(guān)鍵字?jǐn)?shù)目大致相同的兩個(gè)節(jié)點(diǎn)，并保證上層節(jié)點(diǎn)中有這兩個(gè)節(jié)點(diǎn)的最大關(guān)鍵字。（4）B+樹的刪除B+樹中的關(guān)鍵字在葉節(jié)點(diǎn)層刪除后，其在上層的副本可以保留，作為一個(gè)“分解關(guān)鍵字”存在。如果因?yàn)閯h除而造成節(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)小于m/2?1，其處理過程與B?樹的處理一樣。4.B*樹B*樹是B+樹的變體，在B++樹的非根節(jié)點(diǎn)和非葉節(jié)點(diǎn)中再增加指向兄弟的指針。B*樹定義了非葉節(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為(2/3)×m,B+樹則是(1/2)×m。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)，而不會影響兄弟節(jié)點(diǎn)，所以它不需要指向兄弟的指針。B*樹的分裂方法為，當(dāng)一個(gè)節(jié)點(diǎn)滿時(shí)，如果它的下一個(gè)兄弟節(jié)點(diǎn)未滿，那么將一部分?jǐn)?shù)據(jù)移到兄弟節(jié)點(diǎn)中，再在原節(jié)點(diǎn)插入關(guān)鍵字，最后修改父節(jié)點(diǎn)中兄弟節(jié)點(diǎn)的關(guān)鍵字（因?yàn)樾值芄?jié)點(diǎn)的關(guā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*樹分配新節(jié)點(diǎn)的概率比B+樹要低，空間利用率更高。5.對B樹、B-樹、B+樹和B*樹的總結(jié)B樹：屬于二叉樹，每個(gè)節(jié)點(diǎn)只存儲一個(gè)關(guān)鍵字，等于則命中，小于走左節(jié)點(diǎn)，大于走右節(jié)點(diǎn)。B?樹：屬于多路搜索樹，每個(gè)節(jié)點(diǎn)存儲m/2?1到m?1個(gè)關(guān)鍵字，非葉節(jié)點(diǎn)存儲指向關(guān)鍵字范圍的子節(jié)點(diǎn)，所有關(guān)鍵字在整棵樹中出現(xiàn)，且只出現(xiàn)一次，非葉節(jié)點(diǎn)可以命中。B+樹：每個(gè)節(jié)點(diǎn)存儲m/2到m個(gè)關(guān)鍵字，在B?樹基礎(chǔ)上，為葉子節(jié)點(diǎn)增加鏈表指針，所有關(guān)鍵字都在葉節(jié)點(diǎn)中出現(xiàn)，非葉節(jié)點(diǎn)作為葉節(jié)點(diǎn)的索引。B+樹總是到葉節(jié)點(diǎn)才命中。B*樹：在B++樹基礎(chǔ)上，為非葉節(jié)點(diǎn)也增加鏈表指針，將節(jié)點(diǎn)的最低利用率從1/2提高到2/3。1.4.5樹的遍歷樹的遍歷是樹的一種重要的運(yùn)算。所謂遍歷是指對樹中所有節(jié)點(diǎn)系統(tǒng)地訪問，即依次對樹中每個(gè)節(jié)點(diǎn)訪問一次且僅訪問一次。對于二叉樹，樹的3種最重要的遍歷方式分別稱為先序遍歷、中序遍歷和后序遍歷。以這3種方式遍歷一棵樹時(shí)，若按訪問節(jié)點(diǎn)的先后次序?qū)⒐?jié)點(diǎn)排列起來，就可分別得到樹中所有節(jié)點(diǎn)的先序列表、中序列表和后序列表。相應(yīng)的節(jié)點(diǎn)次序分別稱為節(jié)點(diǎn)的先序、中序和后序。對于多叉樹，數(shù)的遍歷通常有兩種：深度優(yōu)先遍歷、廣度優(yōu)先遍歷。下面以二叉樹為例講解三種遍歷方法。每棵二叉樹由節(jié)點(diǎn)、左子樹、右子樹這三個(gè)基本部分組成，如果遍歷了這三部分，也就遍歷了整個(gè)二叉樹。1.先序遍歷先序遍歷指先訪問根，然后訪問孩子的遍歷方式。若二叉樹為非空，則過程為：①訪問根節(jié)點(diǎn)。②先序遍歷左子樹。③先序遍歷右子樹。2.中序遍歷中序遍歷指先訪問左（右）孩子，然后訪問根，最后訪問右（左）孩子的遍歷方式。若二叉樹為非空，則過程為：①按中序遍歷左子樹。②訪問根節(jié)點(diǎn)。③按中序遍歷右子樹。3.后序遍歷后序遍歷指先訪問孩子，然后訪問根的遍歷方式。若二叉樹為非空，則過程為：①按后序遍歷左子樹。②按后序遍歷右子樹。③訪問根節(jié)點(diǎn)。如圖1-23的二叉樹所示，D為二叉樹中某一節(jié)點(diǎn)，L、R分別為節(jié)點(diǎn)D的左、右子樹，則其遍歷方式有6種：先左后右先右后左先序DLRDRL中序LDRRDL后序LRDRLD例如，以先左后右的方式用三種遍歷方法對圖1-24中的二叉樹進(jìn)行遍歷。圖1-23二叉樹示例1圖1-24二叉樹示例2用先序遍歷的方式，得到結(jié)果為ABDECF。用中序遍歷的方式，得到結(jié)果為DBEACF。用后序遍歷的方式，得到結(jié)果為DEBFCA。第2章現(xiàn)代硬盤結(jié)構(gòu)揭秘?zé)o論對于個(gè)人計(jì)算機(jī)還是服務(wù)器，硬盤都是最重要、最主流的存儲介質(zhì)，是計(jì)算機(jī)數(shù)據(jù)的主要載體，所以認(rèn)識和了解硬盤是學(xué)習(xí)數(shù)據(jù)恢復(fù)技術(shù)的必經(jīng)之路。目前市面上的硬盤主要有三類：機(jī)械硬盤（簡稱HDD，屬于傳統(tǒng)硬盤）、固態(tài)硬盤（簡稱SSD，屬于新式硬盤）、混合硬盤（簡稱HHD，是機(jī)械硬盤與固態(tài)硬盤的技術(shù)結(jié)合體）。雖然固態(tài)硬盤的使用逐漸普及，但機(jī)械硬盤因技術(shù)成熟、性能穩(wěn)定、容量大、價(jià)格低等優(yōu)點(diǎn)，一直在存儲介質(zhì)中占據(jù)最重要的地位，尤其是在服務(wù)器中，更是機(jī)械硬盤的天下，所以本章重點(diǎn)介紹機(jī)械硬盤的結(jié)構(gòu)及特點(diǎn)，對于固態(tài)硬盤則簡要說之。2.1機(jī)械硬盤的物理結(jié)構(gòu)揭秘機(jī)械硬盤是一個(gè)集機(jī)、電、磁于一體的精密設(shè)備，也是目前使用最為普及的一種存儲介質(zhì)，它的發(fā)展已經(jīng)有50多年的歷史了。1956年IBM公司推出了世界上第一個(gè)硬盤驅(qū)動(dòng)器RAMAC（RandomAccessMethodforAccountingandControl），其體積相當(dāng)于兩個(gè)并排放置的200L的大冰箱，容量為5MB，價(jià)格超過5萬美元，按比例計(jì)算后相當(dāng)于每1GB容量的價(jià)格超過1000萬美元。而現(xiàn)在，一個(gè)普通3.5英寸硬盤的容量能達(dá)到2000GB（2TB）以上，市場售價(jià)僅為五百元人民幣左右，折合成美元，平均每1GB容量的價(jià)格僅為0.04美元左右。從這里就可以看出50多年來硬盤的發(fā)展速度是多么快。硬盤有其固有的物理結(jié)構(gòu)，而為了方便程序?qū)τ脖P的訪問，人們又會給硬盤虛擬出一些邏輯結(jié)構(gòu)來。首先看看硬盤的物理結(jié)構(gòu)。2.1.1硬盤的外殼及盤標(biāo)信息硬盤從品牌上分類，有希捷、西部數(shù)據(jù)、邁拓（已被希捷收購）、三星（已被希捷收購）、日立（已被西部數(shù)據(jù)收購）等，從尺寸上分類，有3.5英寸、2.5英寸、1.8英寸等。不管是哪一種品牌和尺寸的硬盤，都會有一個(gè)金屬的外殼保護(hù)著硬盤內(nèi)部的重要構(gòu)造，并且在外殼上貼有一個(gè)盤標(biāo)，注明該硬盤的品牌、型號、容量、產(chǎn)地、序列號等信息。下面來看幾個(gè)實(shí)際的例子。一塊希捷3.5英寸硬盤的外殼如圖2-1所示。該硬盤的盤標(biāo)信息如圖2-2所示。盤標(biāo)信息的含義如下。①Seagate：硬盤的品牌，即“希捷”。②S/N:9QM3SMCW：硬盤的序列號。③ST3500320AS：硬盤的型號。④P/N:9BX154-303：硬盤的部件號。⑤Firmware:8D15：硬盤的固件版本號。⑥Barracuda7200.11：硬盤的屬系，即“酷魚11代”。⑦500Gbytes：硬盤的容量。⑧ProductsofThailand：硬盤的產(chǎn)地。圖2-1希捷3.5英寸硬盤外觀圖2-2希捷3.5英寸硬盤的盤標(biāo)信息一塊三星3.5英寸硬盤的外殼如圖2