程序設(shè)計(jì)基礎(chǔ)知識(shí)點(diǎn)

1、第三部分 程序設(shè)計(jì)基礎(chǔ)3.1 程序、程序設(shè)計(jì)、程序設(shè)計(jì)語(yǔ)言的定義程序：計(jì)算機(jī)程序，是指為了得到某種結(jié)果而可以由計(jì)算 機(jī)等具有信息處理能力的裝置執(zhí)行的代碼化指令序列，或者可以 被自動(dòng)轉(zhuǎn)換成代碼化指令序列的符號(hào)化指令序列或者符號(hào)化語(yǔ) 句序列。程序設(shè)計(jì)：程序設(shè)計(jì)是給出解決特定問(wèn)題程序的過(guò)程，是 軟件構(gòu)造活動(dòng)中的重要組成部分。程序設(shè)計(jì)往往以某種程序設(shè)計(jì) 語(yǔ)言為工具，給出這種語(yǔ)言下的程序。程序設(shè)計(jì)過(guò)程應(yīng)當(dāng)包括分 析、設(shè)計(jì)、編碼、測(cè)試、排錯(cuò)等不同階段。程序設(shè)計(jì)語(yǔ)言：程序設(shè)計(jì)語(yǔ)言用于書(shū)寫(xiě)計(jì)算機(jī)程序的語(yǔ) 言。語(yǔ)言的基礎(chǔ)是一組記號(hào)和一組規(guī)則。根據(jù)規(guī)則由記號(hào)構(gòu)成的 記號(hào)串的總體就是語(yǔ)言。在程序設(shè)計(jì)語(yǔ)言中，這些記號(hào)

2、串就是程 序。程序設(shè)計(jì)語(yǔ)言有 3個(gè)方面的因素，即語(yǔ)法、語(yǔ)義和語(yǔ)用。3.2 高級(jí)語(yǔ)言和低級(jí)語(yǔ)言的概念及區(qū)別高級(jí)語(yǔ)言： 高級(jí)語(yǔ)言 (High-level programming Ianguage) 是高度封裝了的編程語(yǔ)言，與低級(jí)語(yǔ)言相對(duì)。它是以人類的日常 語(yǔ)言為基礎(chǔ)的一種編程語(yǔ)言，使用一般人易于接受的文字來(lái)表示（例如漢字、不規(guī)則英文或其他外語(yǔ)） ，從而使程序編寫(xiě)員編寫(xiě) 更容易，亦有較高的可讀性，以方便對(duì)電腦認(rèn)知較淺的人亦可以 大概明白其內(nèi)容。低級(jí)語(yǔ)言：低級(jí)語(yǔ)言分機(jī)器語(yǔ)言（二進(jìn)制語(yǔ)言）和匯編語(yǔ) 言（符號(hào)語(yǔ)言） ，這兩種語(yǔ)言都是面向機(jī)器的語(yǔ)言，和具體機(jī)器 的指令系統(tǒng)密切相關(guān)。機(jī)器語(yǔ)言用指令代碼編寫(xiě)程序

3、，而符號(hào)語(yǔ) 言用指令助記符來(lái)編寫(xiě)程序。區(qū)別： 高級(jí)語(yǔ)言：實(shí)現(xiàn)效率高，執(zhí)行效率低，對(duì)硬件的可控性弱， 目標(biāo)代碼大，可維護(hù)性好，可移植性好低級(jí)語(yǔ)言：實(shí)現(xiàn)效率低，執(zhí)行效率高，對(duì)硬件的可控性強(qiáng)， 目標(biāo)代碼小，可維護(hù)性差，可移植性差了解知識(shí)：CPU運(yùn)行的是二進(jìn)制指令，所有的語(yǔ)言編寫(xiě)的程序最終都要翻譯成二進(jìn)制代碼。越低級(jí)的語(yǔ)言，形式上越接近機(jī)器指 令，匯編語(yǔ)言就是與機(jī)器指令一一對(duì)應(yīng)的。而越高級(jí)的語(yǔ)言，一 條語(yǔ)句對(duì)應(yīng)的指令數(shù)越多，其中原因就是高級(jí)語(yǔ)言對(duì)底層操作進(jìn) 行了抽象和封裝，使編寫(xiě)程序的過(guò)程更符合人類的思維習(xí)慣，并 且極大了簡(jiǎn)化了人力勞動(dòng)。也就是說(shuō)用高級(jí)語(yǔ)言寫(xiě)一句，會(huì)被轉(zhuǎn) 換成許多底層操作，大部分的工作

4、交給了負(fù)責(zé)轉(zhuǎn)換的機(jī)器（即編 譯器），從而人力得到了解放。3.3 編譯程序的概念及作用編譯程序（Compiler , compiling program ）也稱為編譯器，是指把用高級(jí)程序設(shè)計(jì)語(yǔ)言書(shū)寫(xiě)的源程序，翻譯成等價(jià)的機(jī) 器語(yǔ)言格式目標(biāo)程序的翻譯程序。作用：它以高級(jí)程序設(shè)計(jì)語(yǔ)言書(shū)寫(xiě)的源程序作為輸入，而以匯編語(yǔ)言或機(jī)器語(yǔ)言表示的目標(biāo)程序作為輸出。3.4 計(jì)算機(jī)求解問(wèn)題的過(guò)程分析問(wèn)題（確定計(jì)算機(jī)做什么）-設(shè)計(jì)算法（尋找解決問(wèn)題 的途徑和方法，即要計(jì)算機(jī)怎么做）-編寫(xiě)程序（將算法翻譯成 計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言）-上機(jī)運(yùn)行和測(cè)試3.5 程序正確性的含義 程序正確性證明就是采用嚴(yán)格的數(shù)學(xué)方法評(píng)價(jià)一個(gè)程序是否

5、達(dá)到了預(yù)定的性能，即對(duì)于任何一組允許的輸入信息，程序執(zhí) 行后能得到一組和這組信息對(duì)應(yīng)的正確的輸出信息。3.6 程序錯(cuò)誤的幾種類型程序錯(cuò)誤，即英文的Bug,也稱為缺陷，是指在軟件運(yùn)行中因?yàn)槌绦虮旧碛绣e(cuò)誤而造成的功能不正常、死機(jī)、數(shù)據(jù)丟失、非 正常中斷等現(xiàn)象。語(yǔ)法錯(cuò)誤邏輯錯(cuò)誤3.7 程序調(diào)試、程序測(cè)試的概念以及區(qū)別程序調(diào)試：是將編制的程序投入實(shí)際運(yùn)行前，用手工或編 譯程序等方法進(jìn)行測(cè)試，修正語(yǔ)法錯(cuò)誤和邏輯錯(cuò)誤的過(guò)程。這是 保證計(jì)算機(jī)信息系統(tǒng)正確性的必不可少的步驟。編完計(jì)算機(jī)程 序，必須送入計(jì)算機(jī)中測(cè)試。程序測(cè)試： (program testing) 是指對(duì)一個(gè)完成了全部或 部分功能、模塊的計(jì)算機(jī)程

6、序在正式使用前的檢測(cè)，以確保該程 序能按預(yù)定的方式正確地運(yùn)行。了解知識(shí)：程序測(cè)試的方法 灰盒測(cè)試，確實(shí)是介于白盒測(cè)試與黑盒測(cè)試之間的，可以這 樣 理解，灰盒測(cè)試關(guān)注輸出對(duì)于輸入的正確性，同時(shí)也關(guān)注內(nèi)部表 現(xiàn)，但這種關(guān)注不象白盒那樣詳細(xì)、完整，只是通過(guò)一些表征性 的現(xiàn)象、事件、標(biāo)志來(lái)判斷內(nèi)部的運(yùn)行狀態(tài)，有時(shí)候輸出是正確 的，但內(nèi)部其實(shí)已經(jīng)錯(cuò)誤了，這種情況非常多，如果每次都通過(guò) 白盒測(cè)試來(lái)操作，效率會(huì)很低，因此需要采取這樣的一種灰盒的 方法。白盒測(cè)試，又稱結(jié)構(gòu)測(cè)試。他的前提是可以把程序看成在一個(gè)透明的白盒子里，測(cè)試者完全知道程序的結(jié)構(gòu)和處理算法。這種方法按照程序內(nèi)部邏輯設(shè)計(jì)測(cè)試用例，檢測(cè)程序中的主

7、要執(zhí)行通路是否能按照預(yù)定要求正確工作。白盒測(cè)試根據(jù)軟件的內(nèi)部邏輯設(shè) 計(jì)設(shè)施用例，常用的技術(shù)是邏輯覆蓋，即考察用測(cè)試數(shù)據(jù)運(yùn)行被 測(cè)程序是對(duì)程序邏輯的覆蓋程度。主要的覆蓋標(biāo)準(zhǔn)有：語(yǔ)句覆蓋、 判定覆蓋、條件覆蓋、判定 / 條件覆蓋、組合條件覆蓋和路徑覆 蓋。黑盒測(cè)試根據(jù)關(guān)鍵需求說(shuō)明書(shū)所規(guī)定的功能來(lái)設(shè)計(jì)測(cè)試用例，它 不考慮軟件的內(nèi)部結(jié)構(gòu)和處理算法。常用的黑盒測(cè)試技術(shù)包括等 價(jià)類劃分、邊值分析、錯(cuò)誤推測(cè)和因果圖等。區(qū)別： 目的不同 軟件測(cè)試的目的是發(fā)現(xiàn)錯(cuò)誤，至于找出錯(cuò)誤的原因和錯(cuò)誤發(fā) 生的地方不是軟件測(cè)試的任務(wù)，而是調(diào)試的任務(wù) . 調(diào)試的目的是 為了證明程序的正確，因此它必須不斷地排除錯(cuò)誤 . 它們的出

8、發(fā) 點(diǎn)不一樣。前者是挑錯(cuò)，是一種挑剔過(guò)程，屬于質(zhì)盤保證活動(dòng)。 后者是排錯(cuò)，是一種排除過(guò)程，是編碼活動(dòng)的一部分。 指導(dǎo)原則和方法不同軟件測(cè)試的輸出是預(yù)知的，其軟件測(cè)試用例必須包括預(yù)期的 結(jié)果，而調(diào)試的輸出大多是不可預(yù)見(jiàn)的，需要調(diào)試者去解釋、去 發(fā)現(xiàn)產(chǎn)生的原因。 操作者不同 因?yàn)樾睦頎顟B(tài)是軟件測(cè)試程序的障礙，所以執(zhí)行軟件測(cè)試的 人一般不是開(kāi)發(fā)人員，以使軟件測(cè)試更客觀、更有效，而調(diào)試人 員一般都是開(kāi)發(fā)人員 .3.8 結(jié)構(gòu)化程序設(shè)計(jì)概念及類型結(jié)構(gòu)化程序設(shè)計(jì)( structured programming )是進(jìn)行以模塊 功能和處理過(guò)程設(shè)計(jì)為主的詳細(xì)設(shè)計(jì)的基本原則。結(jié)構(gòu)化程序設(shè)計(jì)的三種基本結(jié)構(gòu)是 : 順

9、序結(jié)構(gòu)、選擇結(jié)構(gòu)和 循環(huán)結(jié)構(gòu)。順序結(jié)構(gòu)表示程序中的各操作是按照它們出現(xiàn)的先后順序 執(zhí)行的。選擇結(jié)構(gòu)表示程序的處理步驟出現(xiàn)了分支，它需要根據(jù)某一 特定的條件選擇其中的一個(gè)分支執(zhí)行。選擇結(jié)構(gòu)有單選擇、雙選 擇和多選擇三種形式。循環(huán)結(jié)構(gòu)表示程序反復(fù)執(zhí)行某個(gè)或某些操作，直到某條件為 假(或?yàn)檎?時(shí)才可終止循環(huán)。在循環(huán)結(jié)構(gòu)中最主要的是：什么 情況下執(zhí)行循環(huán)？哪些操作需要循環(huán)執(zhí)行？循環(huán)結(jié)構(gòu)的基本形式有兩種：當(dāng)型循環(huán)和直到型循環(huán)當(dāng)型循環(huán)：表示先判斷條件，當(dāng)滿足給定的條件時(shí)執(zhí)行循環(huán) 體，并且在循環(huán)終端處流程自動(dòng)返回到循環(huán)入口；如果條件不滿 足，則退出循環(huán)體直接到達(dá)流程出口處。因?yàn)槭?quot; 當(dāng)條件滿足時(shí)執(zhí)

10、行循環(huán) " ，即先判斷后執(zhí)行，所以稱為當(dāng)型循環(huán)。直到型循環(huán)：表示從結(jié)構(gòu)入口處直接執(zhí)行循環(huán)體，在循環(huán)終 端處判斷條件，如果條件不滿足，返回入口處繼續(xù)執(zhí)行循環(huán)體， 直到條件為真時(shí)再退出循環(huán)到達(dá)流程出口處，是先執(zhí)行后判斷。 因?yàn)槭?quot; 直到條件為真時(shí)為止 " ，所以稱為直到型循環(huán)。3.9 面向?qū)ο蟪绦蛟O(shè)計(jì)概念面向?qū)ο缶幊蹋∣bject Oriented Programming , OOP 面向 對(duì)象程序設(shè)計(jì)）是一種計(jì)算機(jī)編程架構(gòu)。OOP的一條基本原則是 計(jì)算機(jī)程序是由單個(gè)能夠起到子程序作用的單元或?qū)ο蠼M合而 成。OOP達(dá)到了軟件工程的三個(gè)主要目標(biāo)：重用性、靈活性和擴(kuò) 展性

11、。為了實(shí)現(xiàn)整體運(yùn)算，每個(gè)對(duì)象都能夠接收信息、處理數(shù)據(jù) 和向其它對(duì)象發(fā)送信息。面向?qū)ο蟪绦蛟O(shè)計(jì)中的概念主要包括： 對(duì)象、類、數(shù)據(jù)抽象、 繼承、動(dòng)態(tài)綁定、數(shù)據(jù)封裝、多態(tài)性、消息傳遞。通過(guò)這些概念 面向?qū)ο蟮乃枷氲玫搅司唧w的體現(xiàn)。3.10 ASCII 字符集ASCII （ American Standard Code for Information Interchange ，美國(guó)標(biāo)準(zhǔn)信息交換代碼）是基于拉丁字母的一套 電腦編碼系統(tǒng)，主要用于顯示現(xiàn)代英語(yǔ)和其他西歐語(yǔ)言。它是現(xiàn) 今最通用的單字節(jié)編碼系統(tǒng)，并等同于國(guó)際標(biāo)準(zhǔn) ISO/IEC 646 。標(biāo)準(zhǔn) ASCII 碼也叫基礎(chǔ) ASCII 碼，使用 7

12、位二進(jìn)制數(shù)來(lái)表 示所有的大寫(xiě)和小寫(xiě)字母，數(shù)字 0 到 9、標(biāo)點(diǎn)符號(hào)， 以及在美 式英語(yǔ)中使用的特殊控制字符。大小規(guī)則1）數(shù)字 09 比字母要小。如 "7"<"F" ；2）數(shù)字 0 比數(shù)字 9 要小，并按 0 到 9 順序遞增。如 "3"<"8"3）字母A比字母Z要小，并按A到Z順序遞增。如"A"v"Z"4）同個(gè)字母的大寫(xiě)字母比小寫(xiě)字母要小。如 "A"<"a" 。記住幾個(gè)常見(jiàn)字母的 ASCII 碼大小：“換行LF”為10

13、; “回車CR為13;空格為32; "0"為48; "A" 為 65； "a" 為 97。3.11 標(biāo)識(shí)符、關(guān)鍵字的概念 在編程語(yǔ)言中，標(biāo)識(shí)符就是程序員自己規(guī)定的具有特定含義 的詞，比如類名稱，屬性名稱，變量名等。關(guān)鍵字就是程序發(fā)明者規(guī)定的有特殊含義的單詞，又叫保留 字。3.12 注釋語(yǔ)句的作用 注釋語(yǔ)句在程序的開(kāi)始或中間，不具有任何功能實(shí)現(xiàn)的作 用，僅僅是對(duì)程序進(jìn)行說(shuō)明的語(yǔ)句。注釋語(yǔ)句在程序運(yùn)行過(guò)程中 不運(yùn)行，卻是程序編寫(xiě)時(shí)的重要內(nèi)容，對(duì)于理解程序很重要。3.13 表達(dá)式的組成及類型 表達(dá)式，是由數(shù)字、算符、數(shù)字分組符號(hào)（括號(hào)） 、

14、自由變量和約束變量等以能求得數(shù)值的有意義排列方法所得的組合。 類型： 算術(shù)表達(dá)式：是最常用的表達(dá)式，又稱為數(shù)值表達(dá)式。它是通過(guò)算術(shù)運(yùn)算符來(lái)進(jìn)行運(yùn)算的數(shù)學(xué)公式。 加法、減法、乘法、除法、求余 關(guān)系表達(dá)式：用關(guān)系運(yùn)算符將兩個(gè)表達(dá)式連接起來(lái)的式子，稱關(guān)系表達(dá)式。關(guān)系表達(dá)式的值是邏輯值“真”或“假” 。=（等于） 、（小于）、=（小于等于）、（大于）、=（大于 等于）、（不等于）邏輯表達(dá)式：用邏輯運(yùn)算符將關(guān)系表達(dá)式或邏輯量連接起來(lái) 的有意義的式子稱為邏輯表達(dá)式。邏輯表達(dá)式的值是一個(gè)邏輯 值，即“ true ”或“ false ”。NOT（非）、AND（與）、OR（或）3.14 子程序和函數(shù)的概念 子程

15、序：在計(jì)算機(jī)科學(xué)中，子程序（英語(yǔ)： Subroutine, procedure, function, routine, method, subprogram, callable unit ），是一個(gè)大型程序中的某部份代碼，由一個(gè)或多個(gè)語(yǔ)句塊 組成。它負(fù)責(zé)完成某項(xiàng)特定任務(wù)，而且相較于其他代碼，具備相 對(duì)的獨(dú)立性。函數(shù)：在程序設(shè)計(jì)中， 常將一些常用的功能模塊編寫(xiě)成函數(shù)， 放在函數(shù)庫(kù)中供公共選用。要善于利用函數(shù)，以減少重復(fù)編寫(xiě)程 序段的工作量。許多程序設(shè)計(jì)語(yǔ)言中，可以將一段經(jīng)常需要使用 的代碼封裝起來(lái)，在需要使用時(shí)可以直接調(diào)用，所以，函數(shù)也可 以說(shuō)是許多代碼的集合，這就是程序中的函數(shù)。3.15 數(shù)據(jù)

16、、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)項(xiàng)的概念 數(shù)據(jù)：數(shù)據(jù)就是數(shù)值，也就是我們通過(guò)觀察、實(shí)驗(yàn)或計(jì)算得 出的結(jié)果。數(shù)據(jù)有很多種，最簡(jiǎn)單的就是數(shù)字。數(shù)據(jù)也可以是文 字、圖像、聲音等。數(shù)據(jù)可以用于科學(xué)研究、設(shè)計(jì)、查證等。數(shù)據(jù)元素：數(shù)據(jù)元素 （data element） 是計(jì)算機(jī)科學(xué)術(shù)語(yǔ)。它 是數(shù)據(jù)的基本單位，數(shù)據(jù)元素也叫做結(jié)點(diǎn)或記錄。在計(jì)算機(jī)程序 中通常作為一個(gè)整體進(jìn)行考慮和處理。有時(shí)，一個(gè)數(shù)據(jù)元素可由 若干個(gè)數(shù)據(jù)項(xiàng)組成，例如，一本書(shū)的書(shū)目信息為一個(gè)數(shù)據(jù)元素， 而書(shū)目信息的每一項(xiàng)（如書(shū)名、作者名等）為一個(gè)數(shù)據(jù)項(xiàng)。數(shù)據(jù) 項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)對(duì)象：（Data Object ）是性質(zhì)相同的數(shù)據(jù)元素的集合

17、， 是數(shù)據(jù)的一個(gè)子集，數(shù)據(jù)對(duì)象是一種運(yùn)行時(shí)的概念?？梢允峭獠?實(shí)體（例如，產(chǎn)生或使用信息的任何事物 ）、事物（例如，報(bào)表 ）、 行為（例如，打電話 ）、事件（例如，響警報(bào) ） 、角色（例如，教師、 學(xué)生） 、單位（例如，會(huì)計(jì)科 ） 、地點(diǎn)（例如，倉(cāng)庫(kù)）或結(jié)構(gòu)（例如， 文件）等?？傊?，可以由一組屬性來(lái)定義的實(shí)體都可以被認(rèn)為是 數(shù)據(jù)對(duì)象。數(shù)據(jù)項(xiàng)：數(shù)據(jù)項(xiàng)又稱數(shù)據(jù)元素（ data element ），是數(shù)據(jù)的 基本單位，一個(gè)數(shù)據(jù)可由若干個(gè)數(shù)據(jù)項(xiàng)（ data item ）組成，數(shù) 據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。3.16 數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)之間關(guān)系的描述，有時(shí)就把邏輯結(jié) 構(gòu)

18、簡(jiǎn)稱為數(shù)據(jù)結(jié)構(gòu)。邏輯結(jié)構(gòu)形式地定義為（K, R）（或（D, S）, 其中，K是數(shù)據(jù)元素的有限集，R是K上的關(guān)系的有限集。了解知識(shí)：邏輯結(jié)構(gòu)有四種基本類型：集合結(jié)構(gòu)、線性結(jié)構(gòu)、 樹(shù)狀結(jié)構(gòu)和網(wǎng)絡(luò)結(jié)構(gòu)。表和樹(shù)是最常用的兩種高效數(shù)據(jù)結(jié)構(gòu)，許 多高效的算法能夠用這兩種數(shù)據(jù)結(jié)構(gòu)來(lái)設(shè)計(jì)實(shí)現(xiàn)。表是線性結(jié)構(gòu) 的（全序關(guān)系）,樹(shù)（偏序或?qū)哟侮P(guān)系）和圖（局部有序（weak/local order） ）是非線性結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示 （映像）稱為數(shù)據(jù)的物理 （存儲(chǔ)） 結(jié)構(gòu)。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。3.17 數(shù)據(jù)運(yùn)算 數(shù)據(jù)運(yùn)算是對(duì)數(shù)據(jù)依某種模式而建立起來(lái)的關(guān)系進(jìn)行處理 的過(guò)程。最基本的數(shù)據(jù)運(yùn)算有：算術(shù)

19、運(yùn)算，如：加、減、乘、除、乘方、開(kāi)方、取模等； 關(guān)系運(yùn)算，如：等于、不等于、大于、小于等；邏輯運(yùn)算，如：與、或、非、恒等、蘊(yùn)含等。3.18 數(shù)據(jù)結(jié)構(gòu)的兩大邏輯結(jié)構(gòu)和四種常用的存儲(chǔ)表示方法 數(shù)據(jù)的邏輯結(jié)構(gòu)分兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu) 了解知識(shí)：線性結(jié)構(gòu)是一個(gè)有序數(shù)據(jù)元素的集合。常用的線 性結(jié)構(gòu)有：線性表，棧，隊(duì)列，雙隊(duì)列，數(shù)組，串。常見(jiàn)的非線 性結(jié)構(gòu)有：二維數(shù)組，多維數(shù)組，廣義表，樹(shù) （ 二叉樹(shù)等） ，圖。 數(shù)據(jù)的存儲(chǔ)方法有四種：順序存儲(chǔ)方法 、 鏈接存儲(chǔ)方法 索引存儲(chǔ)方法和散列存儲(chǔ)方法了解知識(shí)：(1)順序存儲(chǔ)方法：該方法把邏輯上相鄰的結(jié)點(diǎn) 存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由

20、存儲(chǔ) 單元的鄰接關(guān)系來(lái)體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu) (Sequential Storage Structure )，通常借助程序語(yǔ)言的數(shù)組 描述。該方法主要應(yīng)用于線性的數(shù)據(jù)結(jié)構(gòu)。非線性的數(shù)據(jù)結(jié)構(gòu)也 可通過(guò)某種線性化的方法實(shí)現(xiàn)順序存儲(chǔ)。(2) 鏈接存儲(chǔ)方法：該方法不要求邏輯上相鄰的結(jié)點(diǎn)在物 理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系由附加的指針字段表示。由 此得 到的 存儲(chǔ) 表示稱 為鏈 式存 儲(chǔ) 結(jié)構(gòu)( Linked Storage Structure ), 通常借助于程序語(yǔ)言的指針類型描述。(3) 索引存儲(chǔ)方法：該方法通常在儲(chǔ)存結(jié)點(diǎn)信息的同時(shí)， 還建立附加的索引表。索引表由若干索引項(xiàng)組成。

21、若每個(gè)結(jié)點(diǎn)在 索引表中都有一個(gè)索引項(xiàng)，則該索引表稱之為稠密索引( Dense Index)o若一組結(jié)點(diǎn)在索引表中只對(duì)應(yīng)一個(gè)索引項(xiàng)，貝U該索引表 稱為稀疏索引(Spare Index)。索引項(xiàng)的一般形式是：( 關(guān)鍵字、地址 )關(guān)鍵字是能唯一標(biāo)識(shí)一個(gè)結(jié)點(diǎn)的那些數(shù)據(jù)項(xiàng)。稠密索引中索 引項(xiàng)的地址指示結(jié)點(diǎn)所在的存儲(chǔ)位置；稀疏索引中索引項(xiàng)的地址 指示一組結(jié)點(diǎn)的起始存儲(chǔ)位置。(4) 散列存儲(chǔ)方法：該方法的基本思想是：根據(jù)結(jié)點(diǎn)的關(guān) 鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。四種基本存儲(chǔ)方法，既可單獨(dú)使用，也可組合起來(lái)對(duì)數(shù)據(jù)結(jié) 構(gòu)進(jìn)行存儲(chǔ)映像。同一邏輯結(jié)構(gòu)采用不同的存儲(chǔ)方法，可以得到不同的存儲(chǔ)結(jié) 構(gòu)。選擇何種存儲(chǔ)結(jié)構(gòu)來(lái)表

22、示相應(yīng)的邏輯結(jié)構(gòu)，視具體要求而定， 主要考慮運(yùn)算方便及算法的時(shí)空要求。3.19 算法和程序的關(guān)系 算法是對(duì)特定問(wèn)題求解步驟的描述，它是指令的有限序列。 算法與程序的關(guān)系：算法和程序都是指令的有限序列 ，但 是，程序是算法，而算法不一定是 程序。算法和程序的區(qū)別主要在于：(1) 在語(yǔ)言描述上，程序必須是用規(guī)定的程序設(shè)計(jì)語(yǔ)言來(lái) 寫(xiě)，而算法很隨意；(2) 在執(zhí)行時(shí)間上，算法所描述的步驟一定是有限的，而程 序可以無(wú)限地執(zhí)行下去。所以： 程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法3.20 常用數(shù)據(jù)類型種類及特性 不同的變成語(yǔ)言，數(shù)據(jù)類型的說(shuō)法有差異。一般而言包含：數(shù)字型或者數(shù)值型，常有Integer （整型）、Long （長(zhǎng)整型）、 Single