2計算機科學(xué)導(dǎo)論筆記要點

計算機科學(xué)導(dǎo)論1緒論圖靈模型是一個可編程的數(shù)據(jù)處理器，在圖靈模型中，輸出數(shù)據(jù)依賴于兩方面因素的結(jié)合作用：輸入數(shù)據(jù)和程序。通用圖靈機是對現(xiàn)代計算機的首次描述，該機器只要提供了了合適的程序就能做任何運算。基于馮？諾依曼模型建造的計算機分為4個子系統(tǒng)：存儲器、算術(shù)運算單元（ALU）、控制單元和輸入/輸出單元。存儲器用來存儲數(shù)據(jù)和程序；算術(shù)運算單元進行計算和邏輯運算；輸入/輸出單元負(fù)責(zé)從計算機外部接收數(shù)據(jù)和程序，并把計算機的處理結(jié)果輸出到計算機外部，控制單元是對其他子系統(tǒng)進行控制操作。馮？諾依曼模型中的程序和指令在計算機中都以二進制比特存儲，在計算機中，指令按順序執(zhí)行。計算機由3大部分組成：計算機硬件、數(shù)據(jù)和計算機軟件。硬件基于馮 ？諾依曼模型，且包含四部分。數(shù)據(jù)以0/1比特進行存儲。圖靈和馮？諾依曼模型的主要特征是程序的概念。程序被存儲在計算機的存儲器中，且必須是有序的指令集。指令集的作用實現(xiàn)重用。算法是按步驟解決問題的辦法，計算機語言可以提高編程的效率，軟件工程是指結(jié)構(gòu)化程序的設(shè)計和編寫，它不僅包括要完成某一任務(wù)的應(yīng)用程序，還包括程序設(shè)計要嚴(yán)格遵循的原理和規(guī)則。而操作系統(tǒng)的誕生，是有一系列指令對所有程序來說是公用的，因此它是程序訪問計算機部分提供方便的一種管理程序。2數(shù)字系統(tǒng)在將十進制數(shù)轉(zhuǎn)換到其他底的數(shù)值時，分為兩部分，整數(shù)部分是進行連除，余數(shù)作為本位的數(shù)值，商進行下一步計算；小數(shù)部分是進行連乘，整數(shù)值作為本位的數(shù)值，小數(shù)值進行下一步計算。3數(shù)據(jù)存儲數(shù)據(jù)類型分為5種：數(shù)字、文本、音頻、圖像和視頻。所有的數(shù)據(jù)類型都轉(zhuǎn)換為稱作位模式的統(tǒng)一表現(xiàn)形式。數(shù)字在存儲到計算機內(nèi)存中之前被轉(zhuǎn)換成二進制系統(tǒng)。 有多種方法來處理符號。有兩種方法來處理小數(shù)點：定點和浮點。整數(shù)可以被當(dāng)作小數(shù)點位置固定的數(shù)字。無符號整數(shù)是永遠(yuǎn)不會為負(fù)的整數(shù)。存儲有符號整數(shù)的方法之一是符號加絕對值格式。這種格式中，最左邊用于顯示符號且其余位定義絕對值。 符號和絕對值互相分開。幾乎所有的計算機都使用*二進制補碼表示法*來存儲位于n位存儲單元中的有符號整數(shù)。在該方法中，無符號整數(shù)有有效范圍被分為兩個相等的子范圍。每一個子范圍用來表示非負(fù)整數(shù)，每二個子范圍用來表示負(fù)整數(shù)。在二進制補碼表示法中，最左邊決定整數(shù)的符號。但符號和絕對值互相分開。實數(shù)是帶有整數(shù)部分和小數(shù)部分的數(shù)字。實數(shù)使用浮點表示法存儲在計算機中。在浮點表示法中數(shù)字由3部分組成：符號、位移量和定點數(shù)。文本的片斷是用來表示該語言中某個意思的一系列符號。我們可用位模式來表示每一個符號。不同的位模式集合被設(shè)計用于表示文本符號。硬件和軟件制造商聯(lián)合進來共同設(shè)計了一種名為Unicode的代碼，這種代碼使用32位表示一個符號?？偠奖硎韭曇艋蛞魳?。音頻是模擬數(shù)據(jù)，我們不能夠在一段時間記錄無限數(shù)量的值，我們只能記錄一些樣本。樣本數(shù)依賴于模擬信號中變化的最大數(shù)量。從每個樣本測量得到的值是真實的數(shù)字。量化指的是將樣本的值截取為最接近的整數(shù)值的一種過程。存儲在計算機中的圖像使用兩種不同的技術(shù)：光柵圖或適量圖。當(dāng)我們需要存儲模擬圖像（如照片）時，就用到了光柵圖。圖像被掃描（采樣）然后存儲像素。用矢量圖方法，圖像被分解成幾何圖形的組合，諸如線段、矩形或圓形。每個幾何形狀由數(shù)學(xué)公式表達(dá)。視頻是圖像（稱為幀）在時間上的表示。一部電影就是一系列的幀逐個播放而形成運動的圖像。換言之，視頻是隨空間（單個圖像）和時間（一系列圖像）變化的信息表現(xiàn)。需要注意的地方是：符號加絕對值的表示方法有兩個0，分別是+0和-0，而二進制補碼的表示法只有一個0。因此范圍也不一樣。科學(xué)戶數(shù)法中的規(guī)范化表示存儲該數(shù)的3部分信息：符號、指數(shù)和尾數(shù)。小數(shù)點左邊的1并沒有存儲，它們是隱含的。尾數(shù)是帶符號的小數(shù)部分，像以符號加絕對值表示法存儲的整數(shù)那樣對待。在余碼系統(tǒng)中，正的和負(fù)的都以無符號數(shù)存儲，將正整數(shù)添加到每個數(shù)字中，，統(tǒng)一按偏移量把數(shù)向右移。在IEEE標(biāo)準(zhǔn)中，單精度數(shù)用32位來存儲，符號1位、指數(shù)8位（偏移量為127）、尾數(shù)為23位，也稱為余127碼。雙精度數(shù)彩共64位來存儲，符號1位、指數(shù)11位（偏移量為1023）、尾數(shù)使用52位，也稱為余1023碼。圖像的表示中對像素的編碼使用的是RG瞰，共24位，稱為真彩色，每個8位表示0~256之間的一個數(shù)；除了真彩色之外，另一種方法是用索引色，通常只有256個索引，只用8位來存儲同樣的像素。JPEG格式使用的是真彩色模式，但壓縮了圖像，gif格式使用的是索引色模式。4數(shù)據(jù)運算數(shù)據(jù)運算分成三大類：邏輯運算、移位運算和算術(shù)運算。 NOT!算符的唯一應(yīng)用是求反，AND運算符的一個應(yīng)用是對指定位進行置位（置0），OR運算符的一個應(yīng)用是對指定位置位（置1），XOR1算符可以對指定位進行翻轉(zhuǎn)。移位運算分為邏輯移位和算術(shù)移位，邏輯移位應(yīng)用于不表示為符號數(shù)的模式，移動的空缺補 0,其中循環(huán)移位會將移出的位補到空缺位。；算術(shù)移位假定模式為二進制補碼的符號整數(shù)，向右移符號位保留，向左移符號位刪除，空位補0。計算機中對整數(shù)的加減法使用的是二進制補碼進行運算，減法轉(zhuǎn)化為補碼的加法進行運算，而用符號加絕對值的形式非常復(fù)雜，要考慮8種情況。浮點數(shù)的實數(shù)的加減法簡化為小數(shù)點對齊后的以符號加絕對值柳芽存儲的兩整數(shù)的加減法。5計算機組成計算機的組成分成三大類（或子系統(tǒng)）：CPU主存和輸入/輸出子系統(tǒng)。中央處理單元（CPU執(zhí)行數(shù)據(jù)上的操作，它有三部分：算術(shù)運算單元（ALU、控制單元和一系列寄存器。算術(shù)邏輯單元（ALL）負(fù)責(zé)算術(shù)、移位和邏輯運算。寄存器是快速獨立的存儲設(shè)備，它可暫時地保留數(shù)據(jù)。控制單元控制CPU中每個部分的操作。主存是存儲單元的集合。每一個單元有一個稱為地址的標(biāo)識符。數(shù)據(jù)被傳輸?shù)絻?nèi)存或從內(nèi)存取出是以稱為字的二進制位組的方式。 內(nèi)存中唯一可標(biāo)識的單元總數(shù)稱為地址空間。有兩種內(nèi)存可用：隨機存取存儲器（RAM和只讀存儲器（ROM。輸入輸出（I/O）子系統(tǒng)的設(shè)備集合允許計算機與外界交流，存儲程序和數(shù)據(jù)，即使在計算機已關(guān)機時也可以。輸入/輸出設(shè)備分成兩大類：非存儲設(shè)備和存儲設(shè)備。非存儲設(shè)備允許CPU內(nèi)存與外界通信；存儲設(shè)備可以存儲以后被檢索的大量信息。存儲設(shè)備被分成磁的和光的。計算機中三個子系統(tǒng)的連接起重要的作為，因為在這些子系統(tǒng)間需要進行信息的通信。CPU和內(nèi)存通常被三個連接連在一起（每個稱為總線）：數(shù)據(jù)總線、地址總線和控制總線。輸入/輸出設(shè)備通過輸入/輸出控制器或接口與總線相連，使用的控制器有多種，如今最常見的有： SCSI、火線和USB有兩種方法輸入/輸出設(shè)備的尋址：I/O獨立尋址和I/O存儲器映射尋址。在I/O獨立尋址方法中，用來從內(nèi)存讀/寫的指令完全不同于用來從輸入/輸出設(shè)備的讀寫指令。在I/O存儲器映射尋址方法中，CPU把I/O控制器中的每個寄存器看成是內(nèi)存中的字。如今，通用計算機使用稱為程序的一組指令來處理數(shù)據(jù)。計算機執(zhí)行程序，從輸入數(shù)據(jù)創(chuàng)建輸出數(shù)據(jù)。程序和數(shù)據(jù)都存儲在內(nèi)存中， CPU使用重復(fù)的機器周期一條接一條，從頭到尾執(zhí)行程序中的指令。簡化的周期由三階段組成：取指令、譯碼和執(zhí)行。有三種使CPU和輸入/輸出設(shè)備同步的方法：程序控制輸入/輸出、中斷控制輸入/輸出和直接存儲器存?。―MA>在最近向十年中，計算機的體系結(jié)構(gòu)和組織經(jīng)歷了許多變化。計算機體系結(jié)構(gòu)分成兩大類：CISC（復(fù)雜指令集計算機）和RISC（精簡指令集計算機）。現(xiàn)代計算機使用流水線技術(shù)來提高吞吐量。這個理念允許控制單元同時執(zhí)行兩個或三個階段，這意味著下一條指令的處理可以在前一條結(jié)束前開始。計算機傳統(tǒng)上有一個控制單元、一個算術(shù)邏輯單元和一個內(nèi)存單元。并行處理通過使用多指令流處理多數(shù)據(jù)流來改善吞吐量。6計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)是把數(shù)據(jù)從一個地方傳送到另一個地方的硬件和軟件的組合。 網(wǎng)絡(luò)的標(biāo)準(zhǔn)中最重要的是性能、可靠性和安全。網(wǎng)絡(luò)中有種連接：點對點連接和多點連接。有四種常見的拓?fù)浣Y(jié)構(gòu)：網(wǎng)狀型、星型、總線型和環(huán)型。其中最常用的是星型。網(wǎng)絡(luò)可以分為三大類：局域網(wǎng)（LAN、廣域網(wǎng)（WAN和城域網(wǎng)（MAIN?；ヂ?lián)網(wǎng)是能夠互相通信的兩個或多個網(wǎng)絡(luò)，因特網(wǎng)是所有網(wǎng)絡(luò)的總和。控制因特網(wǎng)的協(xié)議集合稱為TCP/IP協(xié)議族，由五層組成：應(yīng)用層、傳輸層、網(wǎng)絡(luò)層、數(shù)據(jù)鏈路層和物理層。路由器只使用下三層。應(yīng)用層負(fù)責(zé)向用戶提供服務(wù)。應(yīng)用層的地址是特定于應(yīng)用程序的。傳輸層負(fù)責(zé)整個消息的進程到進程的分發(fā)，意味著傳輸層的客戶端與服務(wù)器間創(chuàng)建了一種邏輯連接。傳輸層中用端口號來標(biāo)識進程。傳輸層的一個職責(zé)是多路復(fù)用和解多路復(fù)用。服務(wù)器使用眾所周知的端口號，計算機使用傳輸層分配的臨時端口號。另外，傳輸層負(fù)責(zé)擁塞控制、流量控制與差錯控制。在 TCP/IP協(xié)議族的發(fā)展歷程中，有三種傳輸層協(xié)議：UDPTCP和SCTPUDP不提供屬于單個消息的數(shù)據(jù)包間的邏輯連接，因此屬于無連接協(xié)議。 TCP支持傳輸層所有職責(zé)的協(xié)議，也被稱為面向連接的協(xié)議。UDP速度最快，TCP速度最慢，不適合實時傳輸。SCTP適合于實時傳輸。網(wǎng)絡(luò)層負(fù)責(zé)單個數(shù)據(jù)包從源主機到目的主機的發(fā)送， 網(wǎng)絡(luò)層有一個特殊的職責(zé)一一路由選擇。網(wǎng)絡(luò)層的協(xié)議主要是IP協(xié)議，另外還有輔助協(xié)議如ICMRIGMRIP協(xié)議提供的是盡力而為服務(wù)，差錯控制等功能由上層協(xié)議完成。數(shù)據(jù)鏈路層負(fù)責(zé)數(shù)據(jù)幀的節(jié)點到節(jié)點的發(fā)送。 數(shù)據(jù)鏈路層還負(fù)責(zé)跳之間的差錯控制和流量控制。它使用物理或MAC地址來標(biāo)識節(jié)點。物理層完成在物理設(shè)備上的二進制比特的傳輸。TCP/IP層從上到下進行封裝，每一層都會在上一層的數(shù)據(jù)基礎(chǔ)上加上頭或尾。因此實際上物理層傳輸?shù)臄?shù)據(jù)會遠(yuǎn)遠(yuǎn)多于應(yīng)用層的數(shù)據(jù)。電子郵件（E-mail）使用的主要協(xié)議是簡單郵件傳輸協(xié)議（STMP。電子郵件使用的其他協(xié)議是POP和IMAP文件傳輸協(xié)議（FTF）是因特網(wǎng)上最常見任務(wù)的標(biāo)準(zhǔn)機制，用于計算機的文件傳輸。FTP與其他客戶/服務(wù)器應(yīng)用的不同之處在于，它建立了兩個連接：一個用于數(shù)據(jù)傳輸，另一個用于控制命令的交換。TELNET是允許用戶訪問遠(yuǎn)程計算機上任何應(yīng)用程序的通用客戶 /服務(wù)器程序。換言之，它允許用戶登錄到遠(yuǎn)程的計算機上。登錄后，用戶可以使用遠(yuǎn)程計算機上可用的服務(wù)，并把結(jié)果傳回本地計算機上。萬維網(wǎng)（WWW是分頁在全球并連在一起的信息存儲庫。為了使用WWW我們需要三個組件：瀏覽器、Wet服務(wù)器和超文本傳輸協(xié)議（HTTP。WW上的文檔可以分成三大類：靜態(tài)、動態(tài)和活動。靜態(tài)文檔是內(nèi)容固定的文檔，客戶端只能得到文檔的副本。動態(tài)文檔是瀏覽器請求文檔時由Web服務(wù)器創(chuàng)建的。通用網(wǎng)關(guān)接口（CGI）是創(chuàng)建和處理動態(tài)文檔的技術(shù)?；顒游臋n是運行在客戶端的一個程序。7操作系統(tǒng)計算機系統(tǒng)由部分組成：硬件和軟件。軟件分成兩大類：操作系統(tǒng)和應(yīng)用程序。操作系統(tǒng)是計算機硬件和用戶（程序和人）和人一個接口，它便利其他程序更加方便有效地運行，并能方便地對計算機硬件和軟件資源進行訪問。 操作系統(tǒng)的兩個主要設(shè)計目標(biāo)是硬件的高效使用和資源的使用方便。操作系統(tǒng)的載人是一個自舉過程，自舉程序放在ROM中,開機之后載入ROM然后把操作系統(tǒng)載入RAM內(nèi)存。操作系統(tǒng)經(jīng)歷了一處長期的演化歷史：批處理操作系統(tǒng)、分時操作系統(tǒng)、單用戶操作系統(tǒng)、并行系統(tǒng)和分頁式系統(tǒng)?，F(xiàn)代操作系統(tǒng)至少有四個功能區(qū)域：內(nèi)存管理器、進程管理器、設(shè)備管理器、文件管理器。操作系統(tǒng)還提供與用戶交互的功能，稱為圖形界面或者命令解釋程序?，F(xiàn)代操作系統(tǒng)的第一職責(zé)是內(nèi)存管理。內(nèi)存必須由操作系統(tǒng)控制，以避免內(nèi)存溢出。內(nèi)存管理技術(shù)可以分為兩類：單道程序和多道程序。在單道程序中，內(nèi)存的大部分容量都為一個程序獨享。在多道程序中，多個程序同時在內(nèi)存中?，F(xiàn)代操作系統(tǒng)的第二職責(zé)是進程管理。進行是運行的程序。進程管理使用調(diào)度器和隊列來管理進程。進程管理涉及具有不同資源的不同進程間的同步問題。這可能潛在地造成死鎖和餓死。死鎖是指一個進程由于其他進程無限制地使用資源導(dǎo)致無法運行的情況。餓死是指一個進程由于資源分配限制太多而不能執(zhí)行的情況?，F(xiàn)代操作系統(tǒng)的第三職責(zé)是設(shè)備或I/O管理。在計算機系統(tǒng)中，輸入/輸出設(shè)備在數(shù)目和速度上都有限制。因為這些設(shè)備與CPU和內(nèi)存相比，速度很慢，所以，當(dāng)一個進程訪問輸入/輸出設(shè)備時，它對其他進程就不可用。設(shè)備管理器負(fù)責(zé)輸入/輸出設(shè)備的高效使用?，F(xiàn)代操作系統(tǒng)的第四職責(zé)是文件管理。操作系統(tǒng)使用文件管理器來控制對文件的訪問。只有進程或用戶被允許訪問指定文件時，訪問才被允許。訪問的類型可以改變。具有一些類似性的兩個常見的操作系統(tǒng)是UNIX和Linux。UNIX是多用戶、多進程、可移植的操作系統(tǒng)，它由四部分構(gòu)成：內(nèi)核、命令解釋器、一組標(biāo)準(zhǔn)工具和應(yīng)用程序。Linux由三部分組成：內(nèi)核、系統(tǒng)工具和系統(tǒng)庫。微軟流行的操作系統(tǒng)家族是WindowsNTWindowsNT是面向?qū)ο蟮?、多層的操作系統(tǒng)。它使用幾個層，包括：硬件抽象層（HAL、執(zhí)行層和環(huán)境子系統(tǒng)層。8算法算法是一組明確步驟的有序集合，它產(chǎn)生結(jié)果并在有限的時間內(nèi)終結(jié)。結(jié)構(gòu)化的程序或算法由三種結(jié)構(gòu)組成：順序、判斷（選擇）和重復(fù)（循環(huán)）。常用的表示算法的工具是UML（統(tǒng)一建模語言，即流程圖）、偽代碼和結(jié)構(gòu)圖。結(jié)構(gòu)圖是顯示算法和子算法之間關(guān)系的高級設(shè)計工具。結(jié)構(gòu)化編程的原則要求算法被分解成稱為子算法的小單元。每個子算法依次又可以分成更小的子算法。通常有兩種方法編寫求解問題的算法：迭代和遞歸。如果一個算法不涉及算法的本身，即引用算法自身，那它就是迭代，如果算法出現(xiàn)在它的定義中，也就是引用自身，那就是遞歸定義。遞歸定義本身包含循環(huán)。9程序設(shè)計語言計算機語言是指編寫程序時，根據(jù)事先定義的規(guī)則（語法）而寫出的預(yù)定語句的集合。經(jīng)過多年的發(fā)展，計算機語言已經(jīng)從機器語言演化為局級語言。計算機唯一識別的語言是機器語言。機器語言的缺點是依賴于計算機，不同的硬件的機器語言不一樣。另外就是編寫程序不方便。匯編語言通過引入符號或助記符的指令和地址來代替二進制代碼。 稱為匯編程序的特殊程序用于將匯編語言代碼翻譯成機器語言。高級語言使程序員專注于應(yīng)用程序，而不是計算機組織的復(fù)雜性。高級語言必須轉(zhuǎn)化為機器語言，這個轉(zhuǎn)化的過程稱為解釋或編譯。高級語言程序稱為源程序，翻譯過來的機器語言程序稱為目標(biāo)程序。編譯程序是把整個源程序翻譯成目標(biāo)程序。解釋分為兩種方法，Java語言之前的解釋是把源程序的每一行翻譯成相應(yīng)目標(biāo)程序行，并執(zhí)行，如果遇到錯誤就中止，再重新解釋和執(zhí)行。 Java語言之后，為取得了可移植性，翻譯過程分成兩步進行：編譯和解釋，編譯創(chuàng)建的是Java虛擬機（JVM的目標(biāo)代碼，再通過JVM模擬器來進行編譯或解釋。編譯和解釋的不同在于編譯在執(zhí)行前翻譯整個代碼，而解釋一次只翻譯和執(zhí)行源代碼中的一行。但兩種方法的翻譯過程都是一樣的：先由**詞法分析器**創(chuàng)建助記符表。再由**語法分析器**來找出指令，然后由**語義分析器**確保不會有二義性，最后由**代碼生成器**生成代碼。模式是計算機用來處理問題的方法，計算機語言可分為4種模式：過程式（強制性）、面向?qū)ο?、函?shù)式和說明式。在過程式模式中，程序是操縱被動對象的活動主體，被動對象本身不能開始動作，它從活動主體接收動作。數(shù)據(jù)或數(shù)據(jù)項就是被動對象?；顒又黧w發(fā)布的動作稱為過程。在過程式模式中，對象和過程是完全分開的實體。過程與程序觸發(fā)不同，程序不定義過程，它只觸發(fā)或調(diào)用過程，過程必須已經(jīng)存在。當(dāng)使用過程式高級語言時，程序只是由許多過程調(diào)用構(gòu)成，除此之外沒有任何東西。所以考慮過程和被作用的對象后，過程式模式的程序?qū)嶋H上由三部分構(gòu)成：對象創(chuàng)建部分、一組過程調(diào)用和每個過程的一組代碼。開發(fā)者可以建立新的過程。FORTRANCOBOLPascal、C和Ada都是高級過程式語言的例子。面向?qū)ο竽Ｊ教幚砘顒訉ο?，而不是被動對象，對象可以進行的動作都包含在這些對象中，只需要接收合適的外部刺激來執(zhí)行其中的動作就可以。 與面向過程不同，過程式模式中的過程是獨立的實體，而面向?qū)ο竽Ｊ街械倪^程（稱為方法）是屬于對象領(lǐng)域的。在面向?qū)ο竽Ｊ街?，相同類型的對象需要一組方法，要創(chuàng)建這組方法，面向?qū)ο笳Z言使用了稱為類的單元。方法的格式與過程式語言中的函數(shù)非常相似，有頭、局部變量和語句。在面向?qū)ο笳Z言中，一個對象能從另一個對象繼承，稱為繼承性。如果定義了一個類，可以定義繼承一些特性的更具體的類。在面向?qū)ο竽Ｊ街?，多態(tài)性是指可以定義一些具有相同名字的操作， 而這些操作在相關(guān)類中做不同的事情。C++和Java是面向?qū)ο笳Z言的例子，C+口的設(shè)計遵循三條基本原則：封裝、繼承和多態(tài)。而 Java是完全面向類操作的，在C++中可以不用定義類就能解決問題，而Java中每個數(shù)據(jù)項都屬于類。Java中類的方法的調(diào)用由編譯器來完成。Java另一有趣的特點的多線程，線程是按順序執(zhí)行的動作序列，C++只允許單線程地執(zhí)行（整個程序作為單線程），而Java允許多線程執(zhí)行（幾行代碼同時執(zhí)行）。在函數(shù)式模式中，程序被看成一個數(shù)學(xué)函數(shù)，函數(shù)是把一組輸入映射到一組輸出的黑盒子，函數(shù)式語言主要實現(xiàn)以下功能定義一系列可供任何程序員調(diào)用的原始（原子）函數(shù)允許程序員通過若干原始函數(shù)的組合來創(chuàng)建新的函數(shù)函數(shù)式語言相對過程式語言具有兩方面的優(yōu)勢：它支持模塊化的編程并且允許程序員使用已經(jīng)存在的函數(shù)來開發(fā)新的函數(shù)。這兩個因素使得程序員能夠編寫出龐大而且不易出錯的程序。函數(shù)式語言的代表是 LISP和Scheme說明式模式依據(jù)邏輯推理原則響應(yīng)查詢。由希臘數(shù)學(xué)家定義的規(guī)范的邏輯基礎(chǔ)上發(fā)展而來，后來發(fā)展成為一階謂詞演算。說明性的語言的缺憾是要收集大量的論據(jù)信息，因此迄今也只局限于人工智能領(lǐng)域。代表語言是Prolog。過程式與面向?qū)ο笫降囊恍┏Ｒ姼拍钣校簶?biāo)識符、數(shù)據(jù)類型、變量、字面量、常量、輸入和輸出、表達(dá)式和語句。標(biāo)識符可以用來代表數(shù)據(jù)的位置從而不用直接操作數(shù)據(jù)的地址。大多數(shù)語言使用兩類控制語句：判斷和重復(fù)。結(jié)構(gòu)化的編程中強烈推薦三種結(jié)構(gòu)：順序、選擇和重復(fù)。子程序在過程式語言中相當(dāng)重要。子程序中的變量在子程序返回時被銷毀，程序和子程序之間進行通信是通過參數(shù)，在主程序中稱為實際參數(shù)，在子程序中稱為形式參數(shù)。參數(shù)的傳遞方式有兩種：傳值和傳引用。在傳值參數(shù)中，參數(shù)是以副本的形式由主程序單向傳給子程序，從子程序到主程序沒有參數(shù)的通信。其優(yōu)點是不會改變主程序中的值。傳引用則用于在子程序中改變主程序的值，在傳引用的時候，實際上傳遞的是變量在內(nèi)存的地址。在C和C++中，子程序被設(shè)計為函數(shù)。10軟件工程軟件生命周期是軟件工程中的一個基礎(chǔ)概念，和其他產(chǎn)品一樣，軟件也周期性地重復(fù)著一些階段。在軟件的生命歷程中，軟件在被開發(fā)之后，使用和修改這兩個步驟會一直持續(xù)到軟件過時。過時是指軟件失去它的有效性。在軟件的生命周期中，開發(fā)過程包括四個階段：分析、設(shè)計、實現(xiàn)和測試。開發(fā)過程有多種模型，最常見的兩種是瀑布模型和增量模型。在瀑布模型中，開發(fā)過程只有一個方向的流動，意味著前一階段不結(jié)束，后一階段不能開始。如設(shè)計階段應(yīng)該在實現(xiàn)階段開始前完成。瀑布模型的優(yōu)點在于下一階段開始前前一階段已經(jīng)完成，因此設(shè)計階段能準(zhǔn)確知道要做什么，因為有分析階段的全部結(jié)果；測試階段能測試整個系統(tǒng)，因為整個項目已經(jīng)完成，缺點就是難于定位問題，因為過程中的一部分有問題，必須檢查整個過程。增量模型中，開發(fā)者首先要完成整個系統(tǒng)的簡化版本，這個版本表示了整個系統(tǒng)，但不包括具體的細(xì)節(jié)。在第二個版本中，，更多的細(xì)節(jié)被加入，然后測試，只有現(xiàn)有系統(tǒng)正確之后，再加入新的功能，ADIT的過程一直持續(xù)下去，直到要求的功能全部被加入。-開發(fā)過程始于分析階段，這個階段生成規(guī)格說明文檔，說明軟件要實現(xiàn)的目標(biāo)，而沒有說明如何去做。分析階段可以使用兩種方法：面向過程分析和面向?qū)ο蠓治?。面向過程分析也稱為結(jié)構(gòu)化分析或經(jīng)典分析，使用過程式語言，可以使用的建模工具有：數(shù)據(jù)流圖、實體關(guān)系圖和狀態(tài)圖。數(shù)據(jù)流圖顯示系統(tǒng)中數(shù)據(jù)的流動，使用了4種符號：方形盒表示數(shù)據(jù)源或數(shù)據(jù)目的、帶圓角的矩形表示過程（數(shù)據(jù)中的動作或操作）、末端開口的矩形表示數(shù)據(jù)存儲的地方、箭頭表示數(shù)據(jù)流。實體關(guān)系圖是使用的另一個工具。狀態(tài)圖通常用于系統(tǒng)中的實體狀態(tài)在響應(yīng)事件時將會改變的情況。面向?qū)ο蠓治鍪褂妹嫦驅(qū)ο笳Z言，使用的工具有：用例圖、類圖、狀態(tài)圖。用例圖給出系統(tǒng)的用戶視圖，它顯示用戶與系統(tǒng)間的交互，用例圖使用四種組件：系統(tǒng)、用例、動作者和關(guān)系。系統(tǒng)（用矩形表示）執(zhí)行功能。系統(tǒng)中的行動用用例顯示，它用圓角矩形表示，動作是使用系統(tǒng)的某人或某事。類圖考慮的系統(tǒng)涉及的實體。狀態(tài)圖與面向過程中的狀態(tài)圖起相同作用。設(shè)計階段定義了系統(tǒng)如何完成在分析階段所定義的，在設(shè)計階段，系統(tǒng)所有的組成部分都被定義。面向過程設(shè)計既要設(shè)計過程，也要設(shè)計數(shù)據(jù)。在面向過程設(shè)計中，整個系統(tǒng)被分解為一組過程或模塊。說明模塊間關(guān)系的常用工具是結(jié)構(gòu)圖。模塊化則是將大項目分解成較小的部分，把大程序分解成能互相通信的小程序。在分解模塊時，主要關(guān)心的是耦合和內(nèi)聚。耦合是兩個模塊互相綁定緊密程度的度量，為了便于模塊重用、不容易影響相關(guān)模塊以及便于修改，軟件系統(tǒng)中的模塊間的耦合必須最小化。內(nèi)聚是程序中處理過程相關(guān)緊密程度的度量，軟件系統(tǒng)模塊間的內(nèi)聚必須最大化。面向?qū)ο笤O(shè)計中，設(shè)計階段通過詳細(xì)描述類的細(xì)節(jié)來繼續(xù)，要列出類的屬性和方法的細(xì)節(jié)。在實現(xiàn)階段，程序員為面向過程設(shè)計中的模塊編寫代碼，或編寫程序單元實現(xiàn)面向?qū)ο笤O(shè)計的類。對面向過程設(shè)計，一般使用純過程語言如 C,而面向?qū)ο笤O(shè)計中C++和Java的使用都很普遍。軟件質(zhì)量非常重要，可以劃分成三個廣義的度量：可操作性、可維護性和可遷移性?？刹僮餍缘亩攘繕?biāo)準(zhǔn)有：準(zhǔn)確性、高效性、可靠性、安全性、及時性和適用性。準(zhǔn)確性一般用故障平均時間、每千行代碼錯誤數(shù)、用戶請求變更數(shù)等度量。高效性可用性能指標(biāo)?？煽啃宰铒@著的是故障平均時間。適用性通常是通過用戶訪談來完成。可維護性以保持系統(tǒng)正常運行并及時更新為參照。通常用可變性、可修正性、適應(yīng)性和可測試性來度量?？蛇w移性是指代碼重用的能力，一般用重用性、互用性、可移植性來度量。測試階段的目標(biāo)是發(fā)現(xiàn)錯誤，好的測試策略可以發(fā)現(xiàn)最多錯誤，常用測試是白盒測試和黑盒測試。白盒測試（或玻璃盒測試）是基于知道軟件是內(nèi)部結(jié)構(gòu)的，測試的目標(biāo)是檢查軟件所有的部分是否全部設(shè)計出來。它假定測試者知道有關(guān)軟件的一切。白盒測試由軟件工程師或一個專門的團隊來完成，要求滿足下面 4符標(biāo)準(zhǔn)：每個模塊中的所有獨立路徑至少被測試過一次所有判斷結(jié)構(gòu)的每個分支都被測試每個循環(huán)都被測試④所有數(shù)據(jù)結(jié)構(gòu)都被測試常見的測試方法有基本路徑測試和控制結(jié)構(gòu)測試?；韭窂綔y試是創(chuàng)建一組測試用例，要求執(zhí)行軟件中的每條語句至少一次?；韭窂綔y試使用略論和圈復(fù)雜性找到必須被走過的獨立路徑?？刂平Y(jié)構(gòu)測試分為條件測試，用來檢查是否所有的條件都被正確設(shè)置；數(shù)據(jù)流測試用來檢查賦值語言的左值；循環(huán)測試是用來檢查循環(huán)的正確性。黑盒測試是在不知道程序的內(nèi)部也不知道程序是如何工作的情況下測試程序。黑盒測試按照軟件應(yīng)該完成的功能來測試軟件。最好的測試方法是窮盡測試，用輸入域所有可能的值去測試軟件，但一般不現(xiàn)實。隨機測試則是用輸入域的子集來測試，子集選擇的方式非常重要，隨機數(shù)生成器非常有用。邊界值測試是測試輸入域的邊界值。文檔關(guān)乎軟件的正確使用和有效維護。軟件通常有三種獨立的文檔：用戶文檔、系統(tǒng)文檔和技術(shù)文檔。文檔是一個持續(xù)的過程，直到軟件包過時后才停止編寫。用戶文檔告訴用戶如何使用軟件包和熟悉軟件包的各種特性，一個好的用戶手冊對于軟件的銷售非常重要。系統(tǒng)文檔定義軟件本身，其目的是為了讓其他人員也能維護和修改軟件包，系統(tǒng)文檔在開發(fā)的的個階段都應(yīng)該存在。分析階段用于記錄收集的信息，需求和使用的方法必須基于它們的推論來清楚描述。設(shè)計階段中記錄最終版本中使用的工具和最終的結(jié)構(gòu)圖。實現(xiàn)階段中記錄代碼的每個模塊，包含注釋和描述。測試階段中包含對最終產(chǎn)品的每種測試及結(jié)果，即使是令人不快的結(jié)果。技術(shù)文檔描述軟件系統(tǒng)的安裝和服務(wù)，應(yīng)該如何安裝到服務(wù)器和客戶端，應(yīng)該如何維護和更新。11數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)代表了有特殊關(guān)系的數(shù)據(jù)的集合，本章討論了三種數(shù)據(jù)結(jié)構(gòu)：數(shù)組、記錄和鏈表，大多數(shù)編程語言內(nèi)置了前兩種，第三種通過指針和記錄來模擬。數(shù)組是元素的順序集合，通常這些元素具有相同的數(shù)據(jù)類型。使用索引可以訪問數(shù)組中的元素。數(shù)組一般與循環(huán)一起使用，數(shù)組的索引從0開始。使用數(shù)組不會減少指令執(zhí)行的次數(shù)，實際上還有增加，但大大減少了需要寫的程序的數(shù)目。在數(shù)組中有兩種不同類型的標(biāo)識符：數(shù)組的的名字和各個元素的名字，元素的名字是數(shù)組名加索引。多維數(shù)組可以提供一些方便的操作，如按行平均、按列平均等。一維數(shù)組的索引直接定義了元素在實際存儲上的相對位置， 多維數(shù)組在內(nèi)存中可以使用行主序存儲或列主序存儲，第一種更為常見。數(shù)組上常見的操作有：查找、插入、刪除、檢索和遍歷。無序數(shù)組的查找是順序查找，有序查找的使用折半查找。數(shù)組大小一般不可變。對于插入操作，分為尾部插入和其他位置插入，尾部插入可以直接操作，其他位置插入需要進行查找之后，再將插入位置之后的元素從后開始向后移動完成之后再插入。 刪除操作也是查找之后，將刪除位置的元素向前移動；檢索操作直接使用索引號就可以完成。數(shù)組的遍歷使用循環(huán)完成。當(dāng)刪除和插入的量較少，而需要大量的查找和檢索時，數(shù)組是一種合適的結(jié)構(gòu)。數(shù)組是一種靜態(tài)數(shù)組結(jié)構(gòu)，所以當(dāng)數(shù)據(jù)項的數(shù)目記錄是一個相關(guān)元素的集合，這些元素可能是不同的類型，但整個記錄有一個名稱。記錄中的每個元素稱為一個域，域是記錄中有意義的命名數(shù)據(jù)的最小元素。域不同于變量主要在于它是記錄的一部分。記錄中的元素可以是相同類型或者不同類型，但記錄中所有元素必須是關(guān)聯(lián)的。大多數(shù)編程語言中使用 來分隔結(jié)構(gòu)名和它成員的名字。數(shù)組定義了元素的集合，而記錄定義了元素可以確認(rèn)的部分，如數(shù)組可以定義一個班的學(xué)生，而記錄定義了學(xué)生不同的屬性，如標(biāo)識、姓名或成績等。如果我們需要定義元素的集合，且同時還需要定義元素的屬性，那可以使用記錄數(shù)組。如'student[1].id′ 等。數(shù)組和記錄數(shù)組都可以看成是數(shù)據(jù)項的列表，數(shù)組可以被看成是記錄數(shù)組一種特例，其中每個元素是只帶一個域的記錄。鏈表是一個有序數(shù)據(jù)的集合，其中每個元素包含兩部分：數(shù)據(jù)和鏈。鏈?zhǔn)窍乱粋€元素的地址。列表的名字標(biāo)識該列表中的第一個元素。鏈表最后一個元素包含一個空指針表示鏈表的結(jié)束。如果頭指針為空，則此鏈表為空鏈表。鏈表中的元素習(xí)慣上稱為節(jié)點。數(shù)組與鏈表都能表示內(nèi)存中的數(shù)據(jù)項列表，區(qū)別在于數(shù)據(jù)項連接在一起的方式，在記錄數(shù)組中，連接工具是索引，而鏈表中的連接工具是指向下一元素的鏈。數(shù)組的元素在內(nèi)存中是連續(xù)存儲的，而鏈表中的存儲是有間隔的，節(jié)點的鏈把數(shù)據(jù)項膠在一起。鏈表的鏈表名是頭指針的名字，而節(jié)點名沒有明顯的名字，這就導(dǎo)致了鏈表的操作與數(shù)組的區(qū)別，鏈表也有與數(shù)組相同的操作。鏈表的搜索只能是順序搜索，從頭指針開始依次向后。插入操作是在找到插入位置之后，改變此位置指向的位置及原來指向的位置即可，操作分在空表中插入、在表開始的位置插入、在表的末尾插入和在表中間插入四種。刪除操作是找到待刪除的節(jié)點之后，改變前一個位置的指向即可，分為刪除首節(jié)點和刪除其他任何節(jié)點。檢索鏈表則是依次檢索。遍歷鏈表需要用到步行指針來依次處理，到空指針時結(jié)束。當(dāng)數(shù)據(jù)將要進行大量的插入和刪除操作時，鏈表是非常高效的結(jié)構(gòu)，但搜索一個鏈表比搜索一個數(shù)組要慢。鏈表是一種動態(tài)的數(shù)據(jù)結(jié)構(gòu)，表可以從無節(jié)點開始，當(dāng)需要新的節(jié)點時，表逐漸增長。12抽象數(shù)據(jù)結(jié)構(gòu)雖然多種簡單的抽象數(shù)據(jù)類型（如整數(shù)、實數(shù)、字符、指針等）在所有的編程語言中已經(jīng)被實現(xiàn)，但大多數(shù)語言并沒有定義復(fù)雜的數(shù)據(jù)類型。抽象數(shù)據(jù)類型（ADT是一個定義新數(shù)據(jù)類型、定義該數(shù)據(jù)類型以及封裝數(shù)據(jù)和操作的包。程序員應(yīng)該知道抽象數(shù)據(jù)類型以及可以應(yīng)用的操作，而不用關(guān)心這些操作是如何完成的。即這些操作的實現(xiàn)是隱藏的。抽象概念意味著知道一個數(shù)據(jù)類型能做什么，如何去做是隱藏的。抽象數(shù)據(jù)類型是對該數(shù)據(jù)類型有意義的操作封裝在一起的數(shù)據(jù)聲明，然后，用它封裝數(shù)據(jù)和操作并對用戶隱藏。抽象數(shù)據(jù)類型包括數(shù)據(jù)的定義、操作的定義、封裝數(shù)據(jù)和操作三部分。抽象數(shù)據(jù)類型的模型包括兩部分，數(shù)據(jù)結(jié)構(gòu)和操作函數(shù)（公有操作和私有操作）。應(yīng)用程序只能通過接口訪問公有操作，私有操作是抽象數(shù)據(jù)類型內(nèi)部用戶使用的，公有操作和接口應(yīng)該獨立于實現(xiàn)，但私有操作依賴于抽象數(shù)據(jù)類型實現(xiàn)時所選擇的數(shù)據(jù)結(jié)構(gòu)。棧是一種限制線性列表，該列表中的添加和刪除被限制在稱為棧頂?shù)囊欢诉M行。棧的特性是后進先出（LIFO），如果一組數(shù)據(jù)入棧再出棧，那它的順序就顛倒了。棧的基本操作有四種：建棧、入棧、出棧和空。棧的應(yīng)用包括四大類：倒轉(zhuǎn)數(shù)據(jù)、配對數(shù)據(jù)、數(shù)據(jù)延遲使用和回溯步驟。倒轉(zhuǎn)數(shù)據(jù)的應(yīng)用如將一個十進制數(shù)轉(zhuǎn)化為二進制數(shù)，余數(shù)先入棧再出棧，這樣順序就是正確的。配對數(shù)據(jù)的常見操作是括號配對，左括號入棧，當(dāng)有右括號時出棧。通過檢查棧是否為空可以確定是否完全配對。棧的實現(xiàn)可以用數(shù)組或者隊列。隊列是一種限制線性列表，數(shù)據(jù)的插入只能在尾部進行，數(shù)據(jù)的刪除只能在頭部進行。隊列的特性是先進先出（FIFO）,保證了通過隊列的數(shù)據(jù)被處理的次序就是數(shù)據(jù)被接收的次序。隊列的基本操作有四種：建隊列、入列、出列和空。隊列的應(yīng)用非常廣泛，如處理用戶需求、任務(wù)和指令。完成對作業(yè)或?qū)ο到y(tǒng)設(shè)備的處理等等。隊列的實現(xiàn)可以用數(shù)組或鏈表來實現(xiàn)。廣義線性表是一種像插入和刪除等操作可以在表其中任何位置進行的表。 可以在頭部、中間或尾部。廣義線性表是具有如下特性的元素集合元素具有相同的類型元素按順序排列，這意味著有第一個元素和最后一個元素。除第一個元素外每個元素都有唯一的前驅(qū)；除最后一個元素外每個元素都有后繼。每個元素是一個帶有關(guān)鍵字段的記錄。元素按關(guān)鍵字值排序。廣義線性表的基本操作有：建表、插入、刪除、檢索、遍歷和空。廣義線性表的搜索是在實現(xiàn)層上進行的，不是在抽象數(shù)據(jù)類型層上。廣義線性表可應(yīng)用于元素被隨機存取或順序存取的情況。廣義線性表可以用數(shù)組或者鏈表來實現(xiàn)。樹包括一組有限的元素，稱為節(jié)點（或頂點）。同時包括一組有限的有向線段，用來連接節(jié)點，稱為弧。如果樹非空，則有一個沒有進入弧的節(jié)點稱為根。樹中的其他節(jié)點都可以沿著從根開始的唯一路徑到達(dá)，該路徑是指一系列相鄰連接的節(jié)點序列。樹中的節(jié)點可以分成三類：根、葉子和內(nèi)部。根的進入弧為 0，外出弧為0或更多，葉子的進入弧為1，外出弧為0，內(nèi)部節(jié)點的進入弧為1，外出弧為1或更多。節(jié)點之間的關(guān)系有子節(jié)點、雙親、兄弟節(jié)點、祖先。樹中的每個節(jié)點都有可能有子樹。每個節(jié)點的子樹含有子節(jié)點中的一個和這個子節(jié)點的所有子孫。二叉對是一棵樹，且其中沒有一個節(jié)點所含有的子樹的個數(shù)超過兩個，每個節(jié)點只有有0、1、2棵子樹。這些樹稱為左子樹和右子樹。二叉樹的遞歸定義是：二叉樹是一棵空樹或由一個根節(jié)點和兩棵子樹構(gòu)成， 而每棵子樹也是二叉樹。二叉樹的常用運算是：建樹、插入、刪除、檢索、空和遍歷。二叉樹的遍歷要求按照預(yù)定的順序處理每一個節(jié)點且僅處理一次。 兩種常用的遍歷次序是深度優(yōu)先和廣度優(yōu)先。深度優(yōu)先遍歷三種標(biāo)準(zhǔn)次序是：前序遍歷（根->左子樹->右子樹）、中序遍歷（左子樹->根->右子樹）、后序遍歷（左子樹->右子樹->根）。注意這三種遍歷都是遞歸定義的。在廣度優(yōu)先遍歷中，是先處理節(jié)點的所有子節(jié)點，再處理下一層。處理次序是（根->左節(jié)點一>右節(jié)點），其定義也是遞歸定義的。二叉樹的應(yīng)用如Hoffman編碼和表達(dá)式樹。Hoffman編碼是用二叉樹來生成一個符號串可變長度的二進制編碼。表達(dá)式樹是將一個算術(shù)表達(dá)式建為一個表達(dá)式樹，根和內(nèi)部節(jié)點是操作符，而葉子是操作數(shù)。三種標(biāo)準(zhǔn)遍歷（前序、中序、后續(xù)）分別產(chǎn)生三種不同的表達(dá)式格式：中綴、后綴、前綴。其中只有中綴表達(dá)式需要括號。我們在編程語言里面使用中綴表示，而編譯程序通常是使用后綴表示。二叉樹的實現(xiàn)用鏈表實現(xiàn)的效率更高，所以也更流行。二叉搜索樹（BST）是一種具有額外特性的二叉樹，每個節(jié)點的關(guān)鍵字值大于左子樹中的所有節(jié)點的關(guān)鍵字值，而小于右子樹中所有節(jié)點的關(guān)鍵字值。 BST一個非常有趣的特性是：如果對BST進行中序遍歷，被訪問的元素以升序排列。BST的另一個有起的特性是可以使用折半查找，這個效率非常高。 BST表比廣義線性表更為常見，原因就是搜索效率高。廣義線性表中只能使用順序查找。 BST可以使用數(shù)組或鏈表來實現(xiàn)，但鏈表的效率更高。圖是由一組節(jié)點（稱為頂點）和一組頂點間的連線（稱為邊或?。?gòu)成的一種抽象數(shù)據(jù)類型。樹是定義成層次結(jié)構(gòu)的，節(jié)點只能有一個雙親，而圖中的節(jié)點可以有一個或多個雙親。圖可能是有向的或無向的。圖的應(yīng)用如計算機網(wǎng)絡(luò)中路徑的選擇等。13文件結(jié)構(gòu)文件是作為一個單元看待的相關(guān)數(shù)據(jù)的外部集合， 文件的主要目的是存儲數(shù)據(jù)。因為當(dāng)計算機關(guān)機后，主存的內(nèi)容將丟失，所以我們需要文件用更永久的形式存儲數(shù)據(jù)。文件被存儲在輔助或二級存儲設(shè)備上。文件在二級設(shè)備上可讀寫，文件也可以只能寫不能讀，如系統(tǒng)顯示器上顯示的信息，廣義上，鍵盤也是文件，雖然它不能存儲數(shù)據(jù)。文件是數(shù)據(jù)記錄的集合，每一個記錄都由一個或多個域組成。存取方法決定了記錄如何被檢索：順序的或隨機的。如果需要順序地存取文件，那么使用順序文件結(jié)構(gòu)；如果需要存取一指定的記錄而無需檢索出該記錄前的所有記錄，那么使用隨機文件結(jié)構(gòu)。隨機存取結(jié)構(gòu)有索引文件和散列文件。順序文件是一種在其中每個數(shù)據(jù)必須按順序從頭到尾一個接一個地進行存取的文件。順序文件必須周期性地更新，以反映出信息的變體。與更新程序相關(guān)聯(lián)的文件有4個：新主文件、舊主文件、事務(wù)文件和錯誤報告文件。新的永久數(shù)據(jù)文件稱為新主文件，需要更新的永久文件是舊主文件，即使在更新后，舊主文件作為參考將繼續(xù)保留。事務(wù)文件包含將要對主文件作的改變。改變分為三類：添加事務(wù)、刪除事務(wù)和更改事務(wù)。處理事務(wù)需要鍵，鍵是文件中一個或多個能唯一標(biāo)識數(shù)據(jù)的字段。錯誤報告文件是更新過程中的錯誤清單。索引文件由數(shù)據(jù)文件構(gòu)成，該數(shù)據(jù)文件是順序文件且是一個索引。索引本身是一個只有兩個域的非常小的文件，兩個域是順序文件的鍵和磁盤上相應(yīng)記錄的地址。索引是根據(jù)數(shù)據(jù)文件的鍵值排序的。在散列文件中，散列函數(shù)將鍵映射成記錄地址。存取文件中的記錄按如下步驟進行：將索引文件載入到內(nèi)存中，用高效算法（如折半查找）來搜索項目，檢索記錄的地址，按照地址檢索數(shù)據(jù)記錄并返回給用戶。索引文件的好處之一就是可以有多個索引，每個索引有不同的鍵。多鍵索引文件稱為倒排文件。在索引文件中，索引將鍵映射為地址，而散列文件中，散列函數(shù)將鍵映射成記錄地址。散列文件無需額外的文件（索引），但散列文件自身也有問題。散列可以采用多種方法。在直接方法中，鍵就是地址，不需要任何的算法運算。它的好處是不會有同義詞或沖突問題。不好的是不是文件中全體元素都有數(shù)據(jù)，因此會造成空間浪費。在求模法中，鍵被文件的大小除，得到的余數(shù)加上1就是地址。在數(shù)字析取散列法中，選擇的數(shù)據(jù)是從鍵中被析取出來的用作地址。在散列過程中，有可能會出現(xiàn)多個鍵值散列到文件中的相同地址，這樣就產(chǎn)生了沖突。常見的幾種沖突解決辦法是：開放尋址解決法（主區(qū)地址查找開放的或者空閑的記錄來用于存放新數(shù)據(jù)，如把沖突的數(shù)據(jù)存在下一個地址中去，不好的是增加了未來沖突的可能性），鏈表解決法是在一個地址中包含了指向下一條記錄的指針，桶散列法是把沖突的記錄散列到桶（桶是一能接納多個記錄的節(jié)點，這種缺點是可能有很多浪費的存儲單元）。目錄是大多數(shù)操作系統(tǒng)提供的用來組織文件的。目錄的作用就像文件柜中的文件夾。但是，在大多數(shù)操作系統(tǒng)中的目錄被表示成為一個包含關(guān)于其他文件的信息的特殊文件類型。目錄不僅像一種索引文件用于告訴操作系統(tǒng)文件在輔助存儲設(shè)備上的位置，還包含了關(guān)于它所包含的文件的其他信息，如訪問權(quán)限、創(chuàng)建者、存取日期和修改日期。在大多數(shù)操作系統(tǒng)中目錄被組織成像樹的抽象數(shù)據(jù)類型。Unix系統(tǒng)下的特殊目錄類型有：根目錄、主目錄、工作目錄和父目錄。文存儲在存儲設(shè)備中的文件是一個二進制位的序列，它可以被應(yīng)用程序翻譯成文件文件或二進制文件。文本文件是字符文件，在它們的內(nèi)存儲器格式中不能包含整數(shù)、浮點數(shù)或其他數(shù)據(jù)結(jié)構(gòu)。二進制文件是用計算機的內(nèi)部格式存儲的數(shù)據(jù)集合。二進制文件中的數(shù)據(jù)只有當(dāng)被程序正確地解釋時才有意義。14數(shù)據(jù)庫數(shù)據(jù)庫是一個組織內(nèi)被應(yīng)用程序使用的邏輯相一致的相關(guān)數(shù)據(jù)的集合。 數(shù)據(jù)庫的優(yōu)點有：冗余較少、避免不一致性、效率、數(shù)據(jù)完整性、機密性。數(shù)據(jù)庫管理系統(tǒng)（DBM）是定義、創(chuàng)建、維護數(shù)據(jù)庫的一種工具。數(shù)據(jù)庫管理系統(tǒng)由 5部分構(gòu)成：硬件、軟件、數(shù)據(jù)、用戶和規(guī)程。數(shù)據(jù)庫是邏輯上相關(guān)的數(shù)據(jù)集合，而不是物理上的，它的各個部分在物理上是可以分開的。數(shù)據(jù)是獨立于軟件的一個實體。用戶可以分為兩類：最終用戶和應(yīng)用程序。最終用戶又可以分為兩類：數(shù)據(jù)庫管理員（DBA）和普通用戶。應(yīng)用程序需要存取和處理數(shù)據(jù)。數(shù)據(jù)庫管理系統(tǒng)的最后一個部分是必須被明確定義并由數(shù)據(jù)庫用戶遵循的規(guī)程或規(guī)則的集合。ANSI/SPAR（為數(shù)據(jù)庫管理系統(tǒng)建立了三層體系結(jié)構(gòu)：內(nèi)層、概念層和外層。內(nèi)層直接與硬件交互。概念層或稱公用層定義數(shù)據(jù)的邏輯視圖。外層直接與用戶交互。傳統(tǒng)的三種數(shù)據(jù)庫模型是層次模型、網(wǎng)狀模型和關(guān)系模型。最終只有關(guān)系模型存活下來。成為數(shù)據(jù)庫設(shè)計中最常用的模型。另外兩種派生于關(guān)系模型的數(shù)據(jù)庫模型是分布式數(shù)據(jù)庫和面向?qū)ο髷?shù)據(jù)庫。在關(guān)系數(shù)據(jù)庫管理系統(tǒng)（RDBMS中，數(shù)據(jù)通過關(guān)系的集合來表示。從表面上看，關(guān)系就是二維表。但這并不代表數(shù)據(jù)以表的形式存儲。關(guān)系有下列特征：名稱（每一種關(guān)系具有唯一的名稱）、屬性（關(guān)系中的每一列都稱為屬性，屬性在表中是列的頭，表示數(shù)據(jù)的含義，每一列在關(guān)系范圍內(nèi)有唯一的名稱。關(guān)系中屬性的總數(shù)稱為關(guān)系的度）、元組（關(guān)系中的行叫做元組。關(guān)系中行的總數(shù)叫做關(guān)系的基數(shù)）。在關(guān)系數(shù)據(jù)庫中，我們能定義幾個操作，根據(jù)現(xiàn)有的關(guān)系建立新的關(guān)系。在結(jié)構(gòu)化查詢語言SQL的上下文中，提到了9種操作：插入、刪除、更新、選擇、投影、連接、并、交和差。插入是一元操作，用于插入新的元組，插入的格式如下：insertintoRELATION-NAMEvalues ，注意插入的值中字符串要用引號括起來，而數(shù)值就不需要了。刪除也是一元操作，用于插入相應(yīng)的元組。刪除的格式如下：deletefromRELATION-NAMEwhereCRITERIA更新也是一元操作，用來更新元組中的部分屬性值，更新格式如下：updateRELATION-NAMEsetattribute1=value1,attribute2=value2,...whereCRITERIA選擇也是一元操作，它應(yīng)用于一個關(guān)系并產(chǎn)生另外一個關(guān)系，新關(guān)系中的元組是原關(guān)系元組的子集，選擇的格式如下'select*fromRELATION-NAMEwhereCRITERIA'.選擇的屬性可以少一些。投影也是一元操作，它應(yīng)用于一個關(guān)系并產(chǎn)生另外一個新關(guān)系，新關(guān)系中的屬性是原關(guān)系屬性的子集。屬性數(shù)減少，但元組的數(shù)量保持不變。操作格式如下'selectattribute-listfromRELATION-NAME'.連接是二元操作，它基于共有的屬性把兩個關(guān)系組合起來，連接操作的格式如下'selectattribute-listfromRELATION1,RELATION2whereCRITERIA'并也是二元操作，它將兩個關(guān)系組合并成一個新的關(guān)系，限制條件是它們必須擁有相同的屬性。操作格式如下'select*fromRELATION1unionselect*fromRELATION2'交也是二元操作，它對兩個關(guān)系進行操作，創(chuàng)建一個新關(guān)系，這兩個關(guān)系必須具有相同的屬性。操作格式如下 'select*fromRELATION1intersectionselect*fromRELATION2'差也是二元操作，它應(yīng)用于具有相同屬性的兩個關(guān)系，生成的關(guān)系中的元組是那些存在于第一個關(guān)系中而不在第二個關(guān)系中的元組。操作格式如下 'select*fromRELATION1minusselect*fromRELATION2'數(shù)據(jù)庫的設(shè)計是一個冗長且只能一步步來完成的任務(wù)。 第一步通常涉及與數(shù)據(jù)庫潛在用戶的面談，去收集需要存儲的信息和每個部門的存取需求。第二步就是建立一個實體關(guān)系模型（ERM），這種模型定義了一些信息需要維護的實體。下一步就是建立基于ERM的關(guān)系。在實體關(guān)系圖（ER圖）使用的幾何圖形中，矩形表示實體集，橢圓形表示屬性，菱形表示關(guān)系集，線連接屬性和實體以及連接實體集和關(guān)系集。規(guī)范化是一個處理過程，通過此過程給定的一組關(guān)系轉(zhuǎn)化成一組具有更堅固結(jié)構(gòu)的新關(guān)系。規(guī)范化要允許數(shù)據(jù)庫中表示的任何關(guān)系，要允許像SQL這樣的語言去使用由原子操作組成的恢復(fù)操作，要移除插入、刪除和更新操作中的不規(guī)則，要減少不嫻的數(shù)據(jù)類型被加入時對數(shù)據(jù)庫重建的需要。 規(guī)范化的過程定義了一組層次范式，包括1NF2NF3NFBCNF4NF和5NF等，這些范式組成一個層次結(jié)構(gòu)，層次越高，難度越大。關(guān)系數(shù)據(jù)庫不是當(dāng)今唯一的數(shù)據(jù)模型，兩個其他常見模型是分布式數(shù)據(jù)庫和面向?qū)ο髷?shù)據(jù)庫。15數(shù)據(jù)壓縮數(shù)據(jù)壓縮方法分為無損壓縮（所有信息都可恢復(fù)）和有損壓縮（部分信息丟失）。在無損壓縮方法中，接收的數(shù)據(jù)是發(fā)送數(shù)據(jù)的完全復(fù)制。三種無損壓縮方法分別是流程長度編碼、Hoffman編碼和LZ編碼。游程長度編碼不需要知道字符出現(xiàn)頻率的相關(guān)知識，并且當(dāng)數(shù)據(jù)僅由 0和1表示時十分有效。大致思想是將數(shù)據(jù)中連續(xù)重復(fù)出現(xiàn)的符號用一個字符和這個字符重復(fù)的次數(shù)來代替。在位模式中，如果數(shù)據(jù)只有兩種符號，且一種符號比另一種符號使用更為頻繁，那么這種壓縮方法就更有效，如標(biāo)記在兩個1之間有多少個0,個數(shù)用4位二進制數(shù)來表示，多于15默認(rèn)下一個仍表示0的數(shù)目，剛好15是加一個0000。Hoffman編碼是對出現(xiàn)更為頻繁的字符分配較短的編碼，對于出現(xiàn)較少的字符分配較長的編碼。分配過程是建立一個二叉樹，將最小概率的兩個點組成二叉樹，將頂點值（二者之和）作為新值，再建樹。Hoffman編碼是一種即時的編碼，它的特點是沒有一個編碼是其他編碼的前綴。這樣譯碼器可以即時明確地翻譯出編碼。LZ編碼是基于字典編碼的算法的例子。在壓縮階段，需要同時做兩件事：建立字典索引和壓縮字符串。算法從未壓縮的字符串中選取最小的子字符串， 這些子字符串在字典中不存在。然后把子符串復(fù)制到字典并分配索引值，壓縮時，除了最后一個字母之外，其他所有字符被字典中的索引代替，然后將索引和最后一個字母插入壓縮字符串。在有損壓縮中，接收的數(shù)據(jù)并不需要是所發(fā)送數(shù)據(jù)的完全復(fù)制。本意討論的三種有效有損壓縮方法分別是JPEGMPE（和MP3聯(lián)合圖像專家組（JPEG）是一種用來壓縮圖形和圖像的方法。JPEG過程包括劃分塊、離散余弦變換、量化及無損壓縮。有損壓縮的損耗出現(xiàn)在量化這一步上。運動圖像專家組（MPEG是一種用來壓縮視頻的方法。MPEG包括空間和時間壓縮。前者和JPEG相似，后者則去掉了多余的幀。MPEGS三代音頻壓縮格式（MP3）是MPEGS準(zhǔn)的一部分。MP3使用感知編碼技術(shù)壓縮CD質(zhì)量的音頻。16安全我們提到的三個安全目標(biāo)：機密性、完整性和可用性。安全攻擊分成三大類：為了實現(xiàn)安全目標(biāo)和防止相應(yīng)的攻擊，ITU-U定義了下列的服務(wù)：數(shù)據(jù)機密性、數(shù)據(jù)完整性、身份驗證、不可否認(rèn)性和訪問控制。兩種技術(shù)被用來提供這些服務(wù)：密碼術(shù)和隱寫術(shù)。對稱密鑰密碼術(shù)使用一個密碼進行加密和解密。 Alice和Bob首先要認(rèn)可一個共享的秘密，這個秘密構(gòu)成了他們的密鑰。為了發(fā)消息給 Bob,Alice使用密鑰加密消息；為了發(fā)消息給Alice，Bob使用相同的密鑰加密消息。傳統(tǒng)對稱密鑰密碼是面向字符的，使用兩種技術(shù)向入侵者隱藏信息：替換和置換。現(xiàn)代對稱密鑰密碼是面向二進制位的，使用非常復(fù)雜的算法來加密和解密二進制位塊。非對角密鑰密碼術(shù)使用兩個不同的密鑰：私鑰和公鑰。Bob首先創(chuàng)建一對密鑰，然后保存私鑰，聲明公鑰。如果有人需要給Bob發(fā)送消息，那他就可以使用Bob的公鑰進行加密，為了閱讀消息，Bob使用他的私鑰解密消息。完整性就是保護信息免受修改。為了保持消息的完整性，消息要經(jīng)過一個稱為密碼散列函數(shù)的算法。這個函數(shù)創(chuàng)建了消息的壓縮影像，稱為消息摘要。為了提供消息驗證，需要消息驗證代碼（MACKMAC包含發(fā)送者和接收者共享的秘密。數(shù)字簽名是電子地簽署文檔的過程。它提供消息完整性、消息驗證和不可否認(rèn)性。實體驗證是一種用來讓一方證明另一方身份的技術(shù)。實體驗證使用三類驗證：所知道的、所擁有的和所固有的。我們提到了四種驗證技術(shù)：基于口令、質(zhì)詢-響應(yīng)、零知識和生物測定。對于對稱密鑰或非對稱密鑰密碼術(shù)，雙方都需要交換密鑰。密鑰管理方法允許我們交換密鑰，而不需要面對面的密鑰交換。在對稱密鑰密碼術(shù)中，實用的解決方案是密鑰分發(fā)中心（KDC）的使用。在非對稱的密鑰密碼術(shù)中，實用的解決方案是使用誰機構(gòu)（CA）的證書。17計算理論我們可以定義一種只有三種語句的計算機語言：遞增語句、遞減語句和循環(huán)語句。遞增語句給變量加1，遞減語句給變量減1，循環(huán)語句是在變量的值不為0時，重復(fù)一個動作或一系列動作。我們可以證明這種簡單的語言能模擬一些流行語言中的多個語句。我們把每個模擬稱為一個宏，它可以在其他模擬中使用，而不需要重復(fù)編碼。圖靈機是為解決可計算問題而設(shè)計的，它是現(xiàn)代計算機的基礎(chǔ)。圖靈機由三部分組成：磁帶、控制器和讀寫頭。圖靈機可以模擬簡單語言的操作。邱奇 -圖靈論題是說：如果存在一個能完成一個符號操縱任務(wù)的算法，那么也存在一臺完成這個任務(wù)的圖靈機。這個論題無法得到證明，但是已經(jīng)有論題支持，首先是尚未發(fā)現(xiàn)有圖靈機不能模擬的算法，其次，所有在數(shù)學(xué)上已經(jīng)得到證明的計算機模型都與圖靈機等價。在計算機科學(xué)理論中，在具體的計算機語言中，一個分配給任何程序的無符號數(shù)稱為歌德爾數(shù)，這種分配有許多優(yōu)點，首先，程序可以作為單一數(shù)據(jù)項輸入給其他程序，第二，程序可以通過它的整數(shù)表示來引用，第三，該編號方式可以用來證明有一些問題計算機并不能解決，從而說明世界上問題的數(shù)量遠(yuǎn)遠(yuǎn)比曾經(jīng)編寫的程序數(shù)量要多得多。一個經(jīng)典的編程問題是：能否編寫一個程序來測試任何可以用歌德爾