程序設(shè)計基礎(chǔ)學(xué)習(xí)知識

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

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

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

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

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

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

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

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

9、結(jié)構(gòu)表示程序中的各操作是按照它們出現(xiàn)的先 后順序執(zhí)行的。選擇結(jié)構(gòu)表示程序的處理步驟出現(xiàn)了分支，它需要 根據(jù)某一特定的條件選擇其中的一個分支執(zhí)行。選擇結(jié) 構(gòu)有單選擇、雙選擇和多選擇三種形式。循環(huán)結(jié)構(gòu)表示程序反復(fù)執(zhí)行某個或某些操作，直到 某條件為假（或為真）時才可終止循環(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)滿足給定的條件時 執(zhí)行循環(huán)體，并且在循環(huán)終端處流程自動返回到循環(huán)入 口；如果條件不滿足，則退出循環(huán)體直接到達(dá)流程出口 處。因為是"當(dāng)條件滿足時執(zhí)行循環(huán)"，即先判斷

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

11、息、處理數(shù)據(jù)和向其它對象發(fā)送 信息。面向?qū)ο蟪绦蛟O(shè)計中的概念主要包括：對象、類、 數(shù)據(jù)抽象、繼承、動態(tài)綁定、數(shù)據(jù)封裝、多態(tài)性、消息 傳遞。通過這些概念面向?qū)ο蟮乃枷氲玫搅司唧w的體現(xiàn)。3.10 ASCII字符集ASCII （American Standard Code for InformationInterchange ，美國標(biāo)準(zhǔn)信息交換代碼）是基于拉丁字母 的一套電腦編碼系統(tǒng)，主要用于顯示現(xiàn)代英語和其他西歐語言。它是現(xiàn)今最通用的單字節(jié)編碼系統(tǒng)，并等同于 國際標(biāo)準(zhǔn)ISO/IEC 646。標(biāo)準(zhǔn)ASCII碼也叫基礎(chǔ)ASCII碼，使用7位二進(jìn)制數(shù)來表示所有的大寫和小寫字母，數(shù)字0到9、標(biāo)點符 號，以

12、及在美式英語中使用的特殊控制字符。大小規(guī)則1)數(shù)字09比字母要小。女口 "7"<"F"；2)數(shù)字0比數(shù)字9要小，并按0到9順序遞增"3"<"8"3)字母A比字母Z要小，并按A到Z順序遞增"A"v"Z"同個字母的大寫字母比小寫字母要小"A"v"a"記住幾個常見字母的 ASCII碼大?。骸皳Q行LF”為10； “回車CR”為13;空格為32;"0"為 48； "A"為 65； "a

13、"為 97。3.11標(biāo)識符、關(guān)鍵字的概念在編程語言中，標(biāo)識符就是程序員自己規(guī)定的具有 特定含義的詞，比如類名稱，屬性名稱，變量名等。關(guān)鍵字就是程序發(fā)明者規(guī)定的有特殊含義的單詞，又叫保留字。3.12注釋語句的作用注釋語句在程序的開始或中間，不具有任何功能實 現(xiàn)的作用，僅僅是對程序進(jìn)行說明的語句。注釋語句在 程序運行過程中不運行，卻是程序編寫時的重要內(nèi)容， 對于理解程序很重要。3.13表達(dá)式的組成及類型表達(dá)式，是由數(shù)字、算符、數(shù)字分組符號（括號） 自由變量和約束變量等以能求得數(shù)值的有意義排列方法 所得的組合。類型：算術(shù)表達(dá)式：是最常用的表達(dá)式，又稱為數(shù)值表達(dá)式。它是通過算術(shù)運算符來進(jìn)行運

14、算的數(shù)學(xué)公式。加法、減法、乘法、除法、求余關(guān)系表達(dá)式：用關(guān)系運算符將兩個表達(dá)式連接起來 的式子，稱關(guān)系表達(dá)式。關(guān)系表達(dá)式的值是邏輯值“真” 或“假”。=（等于）、 （小于）、=（小于等于）、 （大于）、=（大于等于）、<> （不等于）邏輯表達(dá)式：用邏輯運算符將關(guān)系表達(dá)式或邏輯量 連接起來的有意義的式子稱為邏輯表達(dá)式。邏輯表達(dá)式 的值是一個邏輯值，即“ true ”或“ false ”。NOT（非）、AND（與）、0R（或）3.14子程序和函數(shù)的概念子程序：在計算機科學(xué)中，子程序（英語：Subroutine,procedure, fun cti on, routi ne, metho

15、d, subprogram, callable unit ），是一個大型程序中的某部份代碼，由 一個或多個語句塊組成。它負(fù)責(zé)完成某項特定任務(wù)，而 且相較于其他代碼，具備相對的獨立性。函數(shù)：在程序設(shè)計中，常將一些常用的功能模塊編 寫成函數(shù)，放在函數(shù)庫中供公共選用。要善于利用函數(shù)， 以減少重復(fù)編寫程序段的工作量。許多程序設(shè)計語言中， 可以將一段經(jīng)常需要使用的代碼封裝起來，在需要使用 時可以直接調(diào)用，所以，函數(shù)也可以說是許多代碼的集 合，這就是程序中的函數(shù)。3.15數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)項的概念數(shù)據(jù)：數(shù)據(jù)就是數(shù)值，也就是我們通過觀察、實驗 或計算得出的結(jié)果。數(shù)據(jù)有很多種，最簡單的就是數(shù)字。

16、數(shù)據(jù)也可以是文字、圖像、聲音等。數(shù)據(jù)可以用于科學(xué) 研究、設(shè)計、查證等。數(shù)據(jù)元素：數(shù)據(jù)元素（data element）是計算機科學(xué) 術(shù)語。它是數(shù)據(jù)的基本單位，數(shù)據(jù)元素也叫做結(jié)點或記 錄。在計算機程序中通常作為一個整體進(jìn)行考慮和處理。 有時，一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成，例如，一 本書的書目信息為一個數(shù)據(jù)元素，而書目信息的每一項（如書名、作者名等）為一個數(shù)據(jù)項。數(shù)據(jù)項是數(shù)據(jù)的 不可分割的最小單位。數(shù)據(jù)對象：（Data Object ）是性質(zhì)相同的數(shù)據(jù)元素 的集合，是數(shù)據(jù)的一個子集，數(shù)據(jù)對象是一種運行時的 概念。可以是外部實體（例如，產(chǎn)生或使用信息的任何事 物）、事物（例如，報表）、行為（例如，

17、打電話）、事件（例 如，響警報）、角色（例如，教師、學(xué)生）、單位（例如， 會計科）、地點（例如，倉庫）或結(jié)構(gòu)（例如，文件）等?？?之，可以由一組屬性來定義的實體都可以被認(rèn)為是數(shù)據(jù) 對象。數(shù)據(jù)項：數(shù)據(jù)項又稱數(shù)據(jù)元素（data element），是數(shù)據(jù)的基本單位，一個數(shù)據(jù)可由若干個數(shù)據(jù)項（dataitem ）組成，數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。3.16數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是對數(shù)據(jù)之間關(guān)系的描述，有時就 把邏輯結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)。邏輯結(jié)構(gòu)形式地定義為（K, R）（或（D, S）,其中，K是數(shù)據(jù)元素的有限集，R是K 上的關(guān)系的有限集。了解知識：邏輯結(jié)構(gòu)有四種基本類型：集合結(jié)構(gòu)、線

18、性結(jié)構(gòu)、樹狀結(jié)構(gòu)和網(wǎng)絡(luò)結(jié)構(gòu)。表和樹是最常用的兩 種高效數(shù)據(jù)結(jié)構(gòu)，許多高效的算法能夠用這兩種數(shù)據(jù)結(jié) 構(gòu)來設(shè)計實現(xiàn)。表是線性結(jié)構(gòu)的（全序關(guān)系），樹（偏序 或?qū)哟侮P(guān)系）和圖（局部有序（weak/local order）是非 線性結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)在計算機中的表示（映像）稱為數(shù)據(jù)的物理（存儲）結(jié)構(gòu)。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。3.17數(shù)據(jù)運算數(shù)據(jù)運算是對數(shù)據(jù)依某種模式而建立起來的關(guān)系進(jìn)行處理的過程。最基本的數(shù)據(jù)運算有：算術(shù)運算，如：加、減、 乘、除、乘方、開方、取模等；關(guān)系運算，如：等于、 不等于、大于、小于等；邏輯運算，如：與、或、非、 恒等、蘊含等。3.18數(shù)據(jù)結(jié)構(gòu)的兩大邏輯結(jié)構(gòu)和四種常用的存儲

19、表示 方法數(shù)據(jù)的邏輯結(jié)構(gòu)分兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)了解知識：線性結(jié)構(gòu)是一個有序數(shù)據(jù)元素的集合。 常用的線性結(jié)構(gòu)有：線性表，棧，隊列，雙隊列，數(shù)組， 串。常見的非線性結(jié)構(gòu)有：二維數(shù)組，多維數(shù)組，廣義 表，樹（二叉樹等），圖。數(shù)據(jù)的存儲方法有四種：順序存儲方法、鏈接存 儲方法、索引存儲方法和散列存儲方法了解知識：（1）順序存儲方法：該方法把邏輯上相 鄰的結(jié)點存儲在物理位置上相鄰的存儲單元里，結(jié)點間 的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的 存儲表示稱為順序存儲結(jié)構(gòu)（Seque ntial StorageStructure），通常借助程序語言的數(shù)組描述。該方法主 要應(yīng)用于線性的數(shù)據(jù)結(jié)構(gòu)。

20、非線性的數(shù)據(jù)結(jié)構(gòu)也可通過 某種線性化的方法實現(xiàn)順序存儲。(2) 鏈接存儲方法：該方法不要求邏輯上相鄰的結(jié) 點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系由附加的指 針字段表示。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)(Linked Storage Structure ),通常借助于程序語言的 指針類型描述。(3) 索引存儲方法：該方法通常在儲存結(jié)點信息的同時，還建立附加的索引表。索引表由若干索引項組成。 若每個結(jié)點在索引表中都有一個索引項，則該索引表稱 之為稠密索引(Dense Index)。若一組結(jié)點在索引表中 只對應(yīng)一個索引項，則該索引表稱為稀疏索引(SpareIndex)。索引項的一般形式是：(關(guān)鍵字

21、、地址)關(guān)鍵字是能唯一標(biāo)識一個結(jié)點的那些數(shù)據(jù)項。稠密 索引中索引項的地址指示結(jié)點所在的存儲位置；稀疏索 引中索引項的地址指示一組結(jié)點的起始存儲位置。(4) 散列存儲方法：該方法的基本思想是：根據(jù)結(jié) 點的關(guān)鍵字直接計算出該結(jié)點的存儲地址。四種基本存儲方法，既可單獨使用，也可組合起來 對數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲映像。同一邏輯結(jié)構(gòu)采用不同的存儲方法，可以得到不同 的存儲結(jié)構(gòu)。選擇何種存儲結(jié)構(gòu)來表示相應(yīng)的邏輯結(jié)構(gòu)， 視具體要求而定，主要考慮運算方便及算法的時空要求。 3.19算法和程序的關(guān)系算法是對特定問題求解步驟的描述，它是指令的有 限序列。算法與程序的關(guān)系：算法和程序都是指令的有限序列，但是，程序是算法，而算法不一定是 程序。算法和程序的區(qū)別主要在于：（1）在語言描述上，程序必須是用規(guī)定的程序設(shè)計 語言來寫，而算法很隨意；（2）在執(zhí)行時間上，算法所描述的步驟一定是有限 的，而程序可以無限地執(zhí)行下去。所以：程序二數(shù)據(jù)結(jié)構(gòu)+算法3.20常用數(shù)據(jù)類型種類及特性不同的變成語言，數(shù)據(jù)類型的說法有差異。一般而言包含：數(shù)字型或者數(shù)值型，常有 Integer （整型）、Long （長整型）、Single （