《計(jì)算機(jī)導(dǎo)論》第8章 計(jì)算機(jī)軟件

1、8.1計(jì)算機(jī)軟件的概念8.2算法與數(shù)據(jù)結(jié)構(gòu)8.3程序設(shè)計(jì)第8章 計(jì)算機(jī)軟件8.1計(jì)算機(jī)軟件的概念任務(wù)1 初步認(rèn)識(shí)計(jì)算機(jī)軟件任務(wù)描述本任務(wù)學(xué)習(xí)軟件、程序、文檔資料等概念。相關(guān)知識(shí)與技能計(jì)算機(jī)系統(tǒng)主要由軟件和硬件兩大部分組成。硬件是計(jì)算機(jī)系統(tǒng)的機(jī)器部分，即中央處理機(jī)、存儲(chǔ)器及各種外圍設(shè)備的總稱。軟件則是為使計(jì)算機(jī)高效地工作所配置的各種程序及相關(guān)的文檔資料的總稱。程序是經(jīng)過(guò)組織的計(jì)算機(jī)指令序列，指令是組成計(jì)算機(jī)程序的基本單位。文檔資料包括：軟件開發(fā)過(guò)程中的需求分析、方案設(shè)計(jì)、編程方法等的文檔及使用說(shuō)明書、用戶手冊(cè)、維護(hù)手冊(cè)等。 控制器 中央處理器CPU 運(yùn)算器 主機(jī) ROM（只讀存儲(chǔ)器） 內(nèi)存 RA

2、M（讀寫存儲(chǔ)器） 硬件系統(tǒng) Cache（高速緩沖存儲(chǔ)器） 計(jì) 輸入設(shè)備鍵盤、鼠標(biāo)、掃描儀等 算 外設(shè) 輸出設(shè)備顯示器、打印機(jī)、音響等 機(jī) 外存硬盤、軟盤、光盤、閃存等 系 操作系統(tǒng) 統(tǒng) 系統(tǒng)軟件 編譯程序和解釋程序 數(shù)據(jù)庫(kù)管理 軟件系統(tǒng) 應(yīng)用軟件 各種字處理系統(tǒng)、各種軟件包支撐軟件環(huán)境數(shù)據(jù)庫(kù)、各種接口軟件、工具組8.2算法與數(shù)據(jù)結(jié)構(gòu)任務(wù)2 算法及其描述任務(wù)描述本任務(wù)通過(guò)案例學(xué)習(xí)算法的概念及算法的描述。案例8-1 求計(jì)算1+2+3+4+5的算法。相關(guān)知識(shí)與技能做任何事情都要有一個(gè)步驟，廣義地講，為解決一個(gè)問(wèn)題而采取的方法和步驟，就稱為“算法”。算法有兩大類別： 數(shù)值計(jì)算：求方程的根、求函數(shù)的定積

3、分等。 非數(shù)值計(jì)算：查找、排序、圖書檢索、人事管理、文字處理等。算法的設(shè)計(jì)師在設(shè)計(jì)一個(gè)算法后，不能只是自己明白，應(yīng)該準(zhǔn)確清楚地將自己設(shè)計(jì)的解題步驟記錄下來(lái)，或提供交流，或編寫程序供計(jì)算機(jī)執(zhí)行。步驟1：先計(jì)算1+2，得到3步驟2：將步驟1得到的結(jié)果加上3，得到6步驟3：將步驟2得到的結(jié)果加上4，得到10步驟4：將步驟3得到的結(jié)果加上5，得到15，計(jì)算結(jié)果為15按照同樣的思路可寫出計(jì)算1+2+.100的步驟，可知是非常繁瑣的。方法與步驟知識(shí)拓展瑞士著名計(jì)算機(jī)科學(xué)家尼克萊沃思（Niklaus Wirth）早在1976年提出了這樣一個(gè)公式： 算法數(shù)據(jù)結(jié)構(gòu)程序1974年，圖靈獎(jiǎng)的獲得者、著名計(jì)算機(jī)科學(xué)家

4、、算法大師克努特（Donald E。 Knuth）說(shuō)：“計(jì)算機(jī)科學(xué)是算法的學(xué)習(xí)”?？梢?，算法是計(jì)算機(jī)科學(xué)中非常重要的概念，是計(jì)算機(jī)學(xué)科的核心內(nèi)容，在程序編制、軟件開發(fā)，乃至整個(gè)計(jì)算機(jī)科學(xué)中都占有重要地位。所謂算法（Algorithm），是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。描述算法需要一種語(yǔ)言，可以是自然語(yǔ)言、數(shù)學(xué)語(yǔ)言或者是計(jì)算機(jī)語(yǔ)言。一個(gè)算法一般具有下列5個(gè)重要特性：輸入：一個(gè)算法應(yīng)該有一個(gè)或多個(gè)輸入。有窮性：一個(gè)算法必須在執(zhí)行有窮步驟之后正常結(jié)束，而不能形成無(wú)限循環(huán)。確定性：算法中的每一條指令都必須有確切的含義，不能有二義性?？尚行裕核惴ㄖ械拿恳粭l指令都必須是切實(shí)可行的，即原則

5、上可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)。輸出：一個(gè)算法應(yīng)該有0個(gè)或多個(gè)輸出，這些輸出是與輸入有某種特定關(guān)系的量。任務(wù)3 用程序設(shè)計(jì)語(yǔ)言描述算法任務(wù)描述本任務(wù)通過(guò)案例進(jìn)一步學(xué)習(xí)算法的概念，理解用程序設(shè)計(jì)語(yǔ)言（C語(yǔ)言）進(jìn)行算法描述的方法。案例8-2 用程序設(shè)計(jì)語(yǔ)言（C語(yǔ)言）描述計(jì)算1+2+100的算法。相關(guān)知識(shí)與技能求解1+2+100的過(guò)程如圖8-1所示，可得出以下規(guī)律：1+2=33+3=66+4=1010+5=15.4851+99=49504950+100=5050重復(fù)地進(jìn)行相加運(yùn)算本次的和作為下一次相加運(yùn)算的被加數(shù)加數(shù)有規(guī)律地變化著規(guī)律圖8-1 1+2+100 運(yùn)算過(guò)程用C語(yǔ)言對(duì)算法描述

6、如下：main() int x, y; x = 1; y=2; while(y=100) x = x + y; y=y+1; printf(“%d”, x);方法與步驟任務(wù)4 用偽代碼描述算法任務(wù)描述本任務(wù)通過(guò)案例進(jìn)一步學(xué)習(xí)算法的概念，理解用偽代碼進(jìn)行算法描述的方法。案例8-3 用偽代碼語(yǔ)言描述求1+2+100的算法。相關(guān)知識(shí)與技能 偽代碼是用文字（數(shù)字、字母）和符號(hào)來(lái)描述算法的，用偽代碼描述的算法結(jié)構(gòu)清晰，格式緊湊，簡(jiǎn)單易懂。它為程序員提供了以特定編程語(yǔ)言編寫指令的模板。偽代碼表明了程序細(xì)節(jié)，在偽代碼階段檢測(cè)并修復(fù)錯(cuò)誤是簡(jiǎn)單。在校驗(yàn)并接受偽代碼之后，就可以把偽代碼表示的指令轉(zhuǎn)換成高級(jí)編程語(yǔ)言

7、。方法與步驟用偽代碼對(duì)算法描述如下：beginy 2x 1while(y=100) x x+y y y+1print xend任務(wù)5 用流程圖描述算法任務(wù)描述本任務(wù)通過(guò)案例進(jìn)一步學(xué)習(xí)算法的概念，理解用流程圖進(jìn)行算法描述的方法。案例8-4 用流程圖描述求1+2+100的算法。相關(guān)知識(shí)與技能用流程圖表示算法ANSI規(guī)定的一些常用的流程圖符號(hào)起/止點(diǎn)輸入/輸出處理準(zhǔn)備預(yù)定義處理判斷控制流外接內(nèi)接流程圖的基本符號(hào)1+2=33+3=66+4=1010+5=15.4851+99=49504950+100=50500+1=1令s表示被加數(shù)（初始值為0），令I(lǐng)表示加數(shù)（初始值為1）進(jìn)行100次加法后結(jié)束，或者

8、當(dāng)加數(shù)大于100時(shí)結(jié)束S中存放計(jì)算結(jié)果重復(fù)地進(jìn)行相加運(yùn)算本次的和作為下一次相加運(yùn)算的被加數(shù)加數(shù)有規(guī)律地變化著計(jì)算1+2+.+100下面的算法中S表示被加數(shù)，也表示累加和，I表示加數(shù)步驟1：S 0; I 1步驟2：若I小于等于100，則轉(zhuǎn)向步驟3；否則，轉(zhuǎn)向步驟6；步驟3： S S + I; 步驟4： I I + 1;步驟5：轉(zhuǎn)向步驟2；步驟6：S的值就是計(jì)算結(jié)果，算法結(jié)束。推廣該算法，即修改算法中步驟2的100為n，可得到計(jì)算1+2+.+n的算法。計(jì)算1+2+.+100的算法方法與步驟用流程圖對(duì)算法描述如圖8-2所示。圖8-2 求1+2+100算法的流程圖算法思想：例如，計(jì)算1+2+.+100

9、時(shí)先計(jì)算1100, 2+99, ., 49+52, 50+51, 然后用10150即可得到運(yùn)算結(jié)果。類推，要計(jì)算1+2+.+n，只要知道有多少個(gè)n+1，就可以得到計(jì)算結(jié)果。步驟1：S n+1步驟2：若n是偶數(shù)，則 S (S n) 2; 否則， S S ( n-1) 2 + (n + 1) 2 步驟3：S的值就是計(jì)算結(jié)果，算法結(jié)束。同一個(gè)問(wèn)題可用不同的方法解決，即用不同算法解決同一個(gè)問(wèn)題。因此，就存在一個(gè)算法的比較(分析)和選擇問(wèn)題，比較的依據(jù)是算法的效率。計(jì)算1+2+.+n的另一種算法任務(wù)6 初步認(rèn)識(shí)數(shù)據(jù)結(jié)構(gòu)任務(wù)描述 本任務(wù)了解數(shù)據(jù)結(jié)構(gòu)的基本概念和常用的幾種數(shù)據(jù)結(jié)構(gòu)，如線性表、數(shù)組、樹和二叉樹

10、以及圖等。相關(guān)知識(shí)與技能數(shù)據(jù)結(jié)構(gòu)（Data Structure）是計(jì)算機(jī)專業(yè)的一門重要專業(yè)基礎(chǔ)課，主要研究三部分內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)以及對(duì)各種結(jié)構(gòu)進(jìn)行的運(yùn)算。 1. 順序存儲(chǔ)結(jié)構(gòu)在程序設(shè)計(jì)中，由若干個(gè)數(shù)據(jù)元素組成的線性結(jié)構(gòu)稱為線性表。線性表是最簡(jiǎn)單和最常用的數(shù)據(jù)結(jié)構(gòu)。例如，考慮一副撲克牌中相同花色的13張紅桃，為了要在程序中引用每一張紅桃，可以建立13個(gè)變量Card1,Card2,Card13。每一張牌有確定的值，如“紅桃2”、“紅桃9”等。 圖 8-3 線性結(jié)構(gòu)：一維數(shù)組2. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)每個(gè)結(jié)點(diǎn)除包含一個(gè)數(shù)據(jù)域外，還包含一個(gè)指針域，用以存放下一個(gè)結(jié)點(diǎn)的指針，這樣的鏈表稱為單

11、鏈表。圖8-4是一個(gè)具有附加頭結(jié)點(diǎn)的單鏈表，指針變量h中存放的是附加頭結(jié)點(diǎn)的指針，附加頭結(jié)點(diǎn)只用來(lái)存放第一個(gè)具有數(shù)據(jù)的結(jié)點(diǎn)的指針，而第一個(gè)結(jié)點(diǎn)的指針域存放第二個(gè)結(jié)點(diǎn)的指針，如此下去，最后一個(gè)結(jié)點(diǎn)的指針域要置空（NULL），以表示它位于鏈表的尾部。圖 8-4 單鏈表的結(jié)構(gòu)圖 8-6 單鏈表的刪除操作圖 8-5 單鏈表的插入操作3. 棧與隊(duì)列 對(duì)于一般的線性表，可以在任何位置上插入元素，也可以刪除任何位置上的元素。如果限定插入和刪除都只能在線性表的一端進(jìn)行，這樣的線性表稱為棧；如果限定插入在線性表的一端，刪除在另一端，這樣的線性表稱為隊(duì)列。棧是一個(gè)按“后進(jìn)先出”（last in first out

12、）方式工作的數(shù)據(jù)列表。表中允許進(jìn)行插入、刪除操作的一端稱作棧頂；另一端稱作棧底。棧頂?shù)奈恢檬莿?dòng)態(tài)的，對(duì)棧頂當(dāng)前位置的標(biāo)記稱為棧頂指針。當(dāng)棧中沒有數(shù)據(jù)元素時(shí)，稱為空棧。棧的插入操作通常稱為進(jìn)?；蛉霔?；棧的刪除操作則稱為退棧或出棧。圖8-7是一個(gè)棧的動(dòng)態(tài)示意圖，圖中箭頭代表當(dāng)前棧頂?shù)闹羔樜恢?，用top表示。 圖8-7 棧的動(dòng)態(tài)示意圖隊(duì)列與棧非常相似，隊(duì)列按“先進(jìn)先出”（first in first out）方式工作。插入元素的那一端稱為隊(duì)尾，刪除操作的那一端稱為隊(duì)頭。隊(duì)列的插入操作通常稱為進(jìn)隊(duì)列或入隊(duì)列；隊(duì)列的刪除操作稱為退隊(duì)列或出隊(duì)列。圖8-8 隊(duì)列的動(dòng)態(tài)示意圖4. 樹和二叉樹樹（tree）是數(shù)

13、據(jù)結(jié)構(gòu)中的一種非線性結(jié)構(gòu)。樹在我們周圍隨處可見。這里討論的樹結(jié)構(gòu)形同大自然中的樹，也有樹根、樹葉和樹枝。不同之處是：前者樹根在上，后者樹根在下。圖8-9 樹結(jié)構(gòu)示意圖如果樹結(jié)構(gòu)每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)個(gè)數(shù)最多為2個(gè)，這種樹就是二叉樹，如圖8-10所示。 圖8-10 二叉樹圖8-11 圖8-9樹對(duì)應(yīng)的二叉樹8.3 程序設(shè)計(jì)任務(wù)7 初步認(rèn)識(shí)程序設(shè)計(jì)任務(wù)描述本任務(wù)學(xué)習(xí)程序及計(jì)算機(jī)程序的基本概念。相關(guān)知識(shí)與技能本書中所說(shuō)的程序指的是計(jì)算機(jī)程序，它實(shí)際上表示的是一種處理事務(wù)的時(shí)間順序和處理步驟。由于組成計(jì)算機(jī)程序的基本單位是指令，因此，計(jì)算機(jī)程序就是按照工作步驟事先編排好的、具有特殊功能的指令序列。 一個(gè)程序

14、具有一個(gè)單一的、不可分的結(jié)構(gòu)，它規(guī)定了某個(gè)數(shù)據(jù)結(jié)構(gòu)上的一個(gè)算法。于是有以下公式：算法+數(shù)據(jù)結(jié)構(gòu)=程序任務(wù)8 常見程序設(shè)計(jì)語(yǔ)言任務(wù)描述本任務(wù)了解一些常見的程序設(shè)計(jì)語(yǔ)言的特點(diǎn)。相關(guān)知識(shí)與技能1. 面向機(jī)器語(yǔ)言機(jī)器語(yǔ)言：機(jī)器語(yǔ)言是計(jì)算機(jī)的第一代語(yǔ)言。 例如，用機(jī)器語(yǔ)言寫的某一段程序?yàn)椋?000 0110 0000 00110011 1110 0000 01000000其中，每一條機(jī)器指令都是用二進(jìn)制代碼表示的。以上由“0”、“1”組成的三條指令對(duì)Z80機(jī)器而言就是完成3加4的運(yùn)算。匯編語(yǔ)言匯編語(yǔ)言是計(jì)算機(jī)的第二代語(yǔ)言。 例如，把上述用機(jī)器語(yǔ)言書寫的三條指令用匯編語(yǔ)言來(lái)表示，即成為：LD B, 03L

15、D A, 04ADD A, B從英文字母的含義可知，第一條指令是把3送到寄存器B中（LD是load的縮寫）。同理，第二條是把4送到寄存器A中，第三條則是把B中的數(shù)加到A中去。2. 面向過(guò)程語(yǔ)言FORTRAN語(yǔ)言（公式翻譯語(yǔ)言）ALGOL 60（算法語(yǔ)言）COBOL（用于事務(wù)處理的通用語(yǔ)言）BASIC（初學(xué)者通用符號(hào)指令碼）PL/1（程序設(shè)計(jì)語(yǔ)言1）Ada語(yǔ)言 PASCAL語(yǔ)言C語(yǔ)言3. 面向?qū)ο笳Z(yǔ)言C+程序設(shè)計(jì)語(yǔ)言Visual Basic程序設(shè)計(jì)語(yǔ)言4. 網(wǎng)絡(luò)編程語(yǔ)言網(wǎng)絡(luò)編程語(yǔ)言是計(jì)算機(jī)的第五代語(yǔ)言。進(jìn)入20世紀(jì)90年代，網(wǎng)絡(luò)技術(shù)得到了飛速發(fā)展，尤其進(jìn)到21世紀(jì)后，Internet得到了更為廣

16、泛的應(yīng)用。Java語(yǔ)言（Java language）是一種簡(jiǎn)捷的、面向?qū)ο蟮?、用于網(wǎng)絡(luò)環(huán)境的程序設(shè)計(jì)語(yǔ)言，由SUN公司（漢語(yǔ)簡(jiǎn)稱“太陽(yáng)公司”）于1995年5月正式對(duì)外發(fā)布。 任務(wù)9 面向過(guò)程程序設(shè)計(jì)任務(wù)描述本任務(wù)通過(guò)案例學(xué)習(xí)簡(jiǎn)單的面向過(guò)程程序設(shè)計(jì)。案例8-5 用C語(yǔ)言編寫程序：輸入一個(gè)年份，判斷該年份是否是潤(rùn)年。相關(guān)知識(shí)與技能單分支選擇語(yǔ)句格式：If(條件表達(dá)式) 語(yǔ)句塊語(yǔ)句功能：當(dāng)條件為True（真）時(shí)，執(zhí)行后面的語(yǔ)句塊。方法與步驟兩分支選擇結(jié)構(gòu)語(yǔ)句格式：If(條件表達(dá)式)語(yǔ)句塊1else語(yǔ)句塊2本案例可采用選擇結(jié)構(gòu)來(lái)實(shí)現(xiàn)。單分支選擇結(jié)構(gòu)有兩種語(yǔ)句格式：C語(yǔ)言的歷史背景C語(yǔ)言是AT&T貝爾實(shí)

17、驗(yàn)室的Dennis Ritchie和Ken Thompson 在B語(yǔ)言的基礎(chǔ)上開發(fā)出來(lái)的(1972 or 1973)UNIX操作系統(tǒng)是用C語(yǔ)言編寫的1982年ANSI工作小組開始建立C語(yǔ)言的標(biāo)準(zhǔn)美國(guó)國(guó)家標(biāo)準(zhǔn)協(xié)會(huì)ANSI:American National Standards Institute1990年ANSI C被接受為國(guó)際標(biāo)準(zhǔn)ANSI C標(biāo)準(zhǔn)規(guī)定了用C編寫的程序的格式，并確定了如何解釋這些程序ANSI C的目的是促進(jìn)C程序在各種機(jī)器上的可移植性、可靠性、可維護(hù)性和有效執(zhí)行目前所有主要的C編譯器都遵循ANSI C標(biāo)準(zhǔn)任務(wù)10 面向?qū)ο蟪绦蛟O(shè)計(jì)任務(wù)描述本任務(wù)通過(guò)案例學(xué)習(xí)簡(jiǎn)單的面向?qū)ο蟪绦蛟O(shè)計(jì)。

18、案例8-6 用VB6.0編寫程序，該應(yīng)用程序由一個(gè)圖像框控件、一個(gè)定時(shí)器控件和兩個(gè)命令按鈕組成，運(yùn)行程序時(shí)，若單擊start按鈕，則地球滾動(dòng)；基單擊end按鈕，則結(jié)束運(yùn)行。相關(guān)知識(shí)與技能面向?qū)ο?，是基于?duì)象概念，以對(duì)象為中心，以類和繼承為構(gòu)造機(jī)制，來(lái)認(rèn)識(shí)、理解、刻畫客觀世界和設(shè)計(jì)、構(gòu)建相應(yīng)的軟件系統(tǒng)。對(duì)象是由屬性（即數(shù)據(jù))和事件（即程序）組成的封裝體，與客觀實(shí)體有直接的對(duì)應(yīng)關(guān)系。一個(gè)對(duì)象類定義了具有相似性質(zhì)（屬性）的一組對(duì)象。而繼承性是對(duì)具有層次關(guān)系的類的屬性和操作進(jìn)行共享的一種方式。方法與步驟知識(shí)拓展VB 應(yīng)用程序的基礎(chǔ)構(gòu)件是對(duì)象（如窗體和控件）。通過(guò)把類實(shí)例化，就可以得到對(duì)象。對(duì)象的屬性、

19、方法和事件對(duì)象的三要素。對(duì)象的屬性：用來(lái)描述和反映對(duì)象特征的參數(shù)在設(shè)計(jì)階段，通過(guò)屬性窗口進(jìn)行設(shè)置；也可通過(guò)程序代碼，在程序運(yùn)行時(shí)設(shè)置。語(yǔ)句格式：對(duì)象名. 屬性=屬性值對(duì)象的方法：指對(duì)象的行為和動(dòng)作。方法實(shí)質(zhì)是一些封裝起來(lái)的過(guò)程和函數(shù)，使用方法即調(diào)用過(guò)程或函數(shù)。調(diào)用方法的語(yǔ)句格式： 對(duì)象名. 方法參數(shù)表對(duì)象的事件：即發(fā)生在對(duì)象上的事情。事件過(guò)程：對(duì)象的事件被激發(fā)后，應(yīng)用程序處理事件的步驟事件過(guò)程的格式： SUB 對(duì)象名_事件名( 參數(shù)表 ) 。 END SUB8.4 軟件的開發(fā)任務(wù)11 軟件的開發(fā)過(guò)程任務(wù)描述 本任務(wù)學(xué)習(xí)軟件開發(fā)的基本過(guò)程。相關(guān)知識(shí)與技能軟件開發(fā)的過(guò)程基本包括需求分析、設(shè)計(jì)、編程、測(cè)試等。其中：需求分析：不僅僅是用戶需求，應(yīng)該是開發(fā)中遇到的所有的需求。例如，首先要知道項(xiàng)目所要解決的問(wèn)題；測(cè)試案例中應(yīng)該輸入的數(shù)據(jù)，等等。為了清楚地知道這些需求，經(jīng)常要和