計(jì)算機(jī)軟件技術(shù)基礎(chǔ)綜述

大學(xué)計(jì)算機(jī)基礎(chǔ)第五章計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第五章計(jì)算機(jī)軟件技術(shù)基礎(chǔ)

計(jì)算機(jī)硬件(Hardware)是計(jì)算機(jī)系統(tǒng)的基礎(chǔ)，但是沒(méi)有軟件(Software)的計(jì)算機(jī)是無(wú)法工作的。事實(shí)上，現(xiàn)在計(jì)算機(jī)能廣泛地應(yīng)用于各個(gè)領(lǐng)域，完全是由于有了豐富的計(jì)算機(jī)軟件，人們?yōu)榱擞糜?jì)算機(jī)解決各類(lèi)問(wèn)題，針對(duì)性地開(kāi)發(fā)了各種各樣的軟件。本章將討論關(guān)于計(jì)算機(jī)軟件的相關(guān)知識(shí)：如什么是軟件，程序設(shè)計(jì)語(yǔ)言的分類(lèi)，什么是算法等。5.1計(jì)算機(jī)軟件系統(tǒng)5.1.1軟件的概念與特點(diǎn)

軟件是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一部分，包括程序、數(shù)據(jù)及其相關(guān)文檔的完整集合。軟件通常是為某個(gè)特定目的而開(kāi)發(fā)的產(chǎn)品。①程序：按照事先設(shè)計(jì)的功能和性能要求執(zhí)行的計(jì)算機(jī)指令序列。②數(shù)據(jù)：使程序能夠正常操縱信息的數(shù)據(jù)結(jié)構(gòu)。③文檔：與程序開(kāi)發(fā)、維護(hù)和使用有關(guān)的資料。

軟件的特點(diǎn):①抽象性②復(fù)雜性③維護(hù)長(zhǎng)期性④高成本性5.1計(jì)算機(jī)軟件系統(tǒng)5.1.2軟件的分類(lèi)(1)按軟件功能劃分①系統(tǒng)軟件：能與計(jì)算機(jī)硬件緊密配合在一起，使計(jì)算機(jī)系統(tǒng)的各個(gè)部件、相關(guān)的軟件和數(shù)據(jù)協(xié)調(diào)、高效地工作。②支撐軟件：協(xié)助用戶(hù)開(kāi)發(fā)軟件的工具性軟件，其中包括幫助軟件人員開(kāi)發(fā)軟件產(chǎn)品的工具，也包括幫助管理人員控制開(kāi)發(fā)進(jìn)程的工具。③應(yīng)用軟件：針對(duì)特定領(lǐng)域應(yīng)用開(kāi)發(fā)，為特定目的服務(wù)的軟件。5.1計(jì)算機(jī)軟件系統(tǒng)(2)按軟件工作方式劃分①實(shí)時(shí)處理軟件：對(duì)實(shí)時(shí)過(guò)程進(jìn)行監(jiān)控的軟件。②分時(shí)軟件：允許多個(gè)聯(lián)機(jī)用戶(hù)同時(shí)使用計(jì)算機(jī)。③交互式軟件：能實(shí)現(xiàn)人機(jī)通信的軟件。④批處理軟件：把一組輸入作業(yè)或大量數(shù)據(jù)以成批處理的方式一次運(yùn)行，按順序逐個(gè)處理的軟件。(3)按軟件服務(wù)對(duì)象劃分①項(xiàng)目軟件：也稱(chēng)定制軟件，是受某個(gè)特定客戶(hù)(或少數(shù)客戶(hù))委托，由一個(gè)或多個(gè)軟件開(kāi)發(fā)機(jī)構(gòu)在合同的約束下開(kāi)發(fā)出來(lái)的軟件。②產(chǎn)品軟件：由軟件開(kāi)發(fā)機(jī)構(gòu)開(kāi)發(fā)出來(lái)投入市場(chǎng)或用戶(hù)群體龐大的軟件。5.1計(jì)算機(jī)軟件系統(tǒng)

計(jì)算機(jī)軟件系統(tǒng)包括各種各樣的軟件，這些軟件之間的關(guān)系不是并列的，而是有一定的層次關(guān)系。5.1.3計(jì)算機(jī)軟件的層次結(jié)構(gòu)5.2程序設(shè)計(jì)語(yǔ)言簡(jiǎn)單來(lái)講，程序設(shè)計(jì)就是：用計(jì)算機(jī)語(yǔ)言編寫(xiě)程序。程序=算法+數(shù)據(jù)結(jié)構(gòu)

編寫(xiě)計(jì)算機(jī)程序時(shí)使用的語(yǔ)言稱(chēng)為程序設(shè)計(jì)語(yǔ)言(ProgrammingLanguage)，使用它把人類(lèi)解決問(wèn)題的方法用計(jì)算機(jī)可以識(shí)別的形式表示出來(lái)。對(duì)數(shù)據(jù)操作的步驟如何表示、組織和存儲(chǔ)數(shù)據(jù)5.2程序設(shè)計(jì)語(yǔ)言5.2.1機(jī)器語(yǔ)言

機(jī)器語(yǔ)言是指由二進(jìn)制代碼按照一定規(guī)則組成的命令集合，也稱(chēng)為機(jī)器指令集合。機(jī)器指令的格式如下：操作碼操作數(shù)例如：計(jì)算256+16結(jié)果的機(jī)器代碼如下(以十六進(jìn)制表示)：B80001；把256放入累加器AX051000；把16與AX中值相加，結(jié)果存入AX5.2程序設(shè)計(jì)語(yǔ)言5.2.2匯編語(yǔ)言

為了解決機(jī)器語(yǔ)言難記憶、可讀性差的缺點(diǎn)，人們把機(jī)器指令中的操作碼和操作數(shù)用英文助記符和符號(hào)地址來(lái)表示，這種助記符語(yǔ)言稱(chēng)為匯編語(yǔ)言。MOVAX，256；把256放入累加器AXADDAX，16；把16與AX中值相加，結(jié)果存入AX匯編和連接過(guò)程：5.2程序設(shè)計(jì)語(yǔ)言5.2.3高級(jí)語(yǔ)言

高級(jí)語(yǔ)言是一類(lèi)程序設(shè)計(jì)語(yǔ)言的統(tǒng)稱(chēng)，它采用接近人類(lèi)自然語(yǔ)言和數(shù)學(xué)表達(dá)式的表示方法，并遵循一定的語(yǔ)法規(guī)則來(lái)編寫(xiě)程序。實(shí)現(xiàn)求整數(shù)的絕對(duì)值的程序段：intintVar,result;scanf(“%d”,&intVar);if(intVar>=0)result=intVar;elseresult=-1*intVar;printf(“%d的絕對(duì)值是：%d”,intVar,result);5.2程序設(shè)計(jì)語(yǔ)言高級(jí)語(yǔ)言程序的翻譯和執(zhí)行高級(jí)語(yǔ)言源程序翻譯成指令代碼的方法主要有兩種：解釋和編譯5.2程序設(shè)計(jì)語(yǔ)言5.2程序設(shè)計(jì)語(yǔ)言5.2.4主流高級(jí)語(yǔ)言

高級(jí)語(yǔ)言種類(lèi)多，介紹幾種常用的高級(jí)語(yǔ)言：（1）BASIC語(yǔ)言（2）C語(yǔ)言（3）C++語(yǔ)言（4）JAVA語(yǔ)言（5）C#語(yǔ)言（6）腳本語(yǔ)言5.2程序設(shè)計(jì)語(yǔ)言5.2.5軟件開(kāi)發(fā)工具和開(kāi)發(fā)環(huán)境程序員使用的開(kāi)發(fā)工具，主要有：編輯源程序的編輯軟件。把高級(jí)語(yǔ)言編譯成機(jī)器語(yǔ)言的編譯軟件。調(diào)試程序的調(diào)試軟件。（1）單獨(dú)工具（2）集成的開(kāi)發(fā)環(huán)境5.2程序設(shè)計(jì)語(yǔ)言(不講)5.2.6程序設(shè)計(jì)語(yǔ)言的構(gòu)成(不講)

數(shù)據(jù)和操作是構(gòu)成程序的兩個(gè)基本要素，任何一種程序設(shè)計(jì)語(yǔ)言都必須提供表示數(shù)據(jù)和操作的語(yǔ)法、語(yǔ)義元素。

(1)數(shù)據(jù)類(lèi)型程序設(shè)計(jì)語(yǔ)言中一般分為基本數(shù)據(jù)類(lèi)型和構(gòu)造數(shù)據(jù)類(lèi)型兩大類(lèi)。

基本數(shù)據(jù)類(lèi)型是由程序設(shè)計(jì)語(yǔ)言?xún)?nèi)置的，其特點(diǎn)是不能再分解為其它的類(lèi)型。在主流的程序設(shè)計(jì)語(yǔ)言中一般包括：整數(shù)類(lèi)型、實(shí)數(shù)類(lèi)型、字符類(lèi)型、布爾類(lèi)型等。

構(gòu)造數(shù)據(jù)類(lèi)型是由基本數(shù)據(jù)類(lèi)型按照某種方式組合構(gòu)成的。常見(jiàn)的構(gòu)造數(shù)據(jù)類(lèi)型有：數(shù)組類(lèi)型、記錄類(lèi)型(結(jié)構(gòu)體)、枚舉類(lèi)型、字符串類(lèi)型、文件類(lèi)型等。5.2程序設(shè)計(jì)語(yǔ)言(不講)(2)運(yùn)算符和表達(dá)式

運(yùn)算是程序?qū)?shù)據(jù)進(jìn)行的最基本也是最重要的處理，程序設(shè)計(jì)中使用表達(dá)式完成各種各樣的運(yùn)算。表達(dá)式通常包括：常量、變量、運(yùn)算符和函數(shù)調(diào)用等構(gòu)成。例如：給定圓的半徑r，求其面積的Java語(yǔ)言表達(dá)式是：

s=3.14*r*r(3)語(yǔ)句

程序是對(duì)計(jì)算機(jī)要執(zhí)行的操作的描述。高級(jí)語(yǔ)言源程序的基本組成單位是語(yǔ)句。語(yǔ)句按功能可以分為兩類(lèi)：

1.用于描述操作運(yùn)算，如賦值語(yǔ)句，稱(chēng)為操作運(yùn)算語(yǔ)句；

2.用于控制操作運(yùn)算的執(zhí)行順序，如分支控制語(yǔ)句，稱(chēng)為流程控制語(yǔ)句。5.2程序設(shè)計(jì)語(yǔ)言(不講)(4)控制結(jié)構(gòu)①順序結(jié)構(gòu)，按照語(yǔ)句出現(xiàn)的先后順序依次執(zhí)行。②分支結(jié)構(gòu)，根據(jù)給定條件判斷，決定程序執(zhí)行的順序。③循環(huán)結(jié)構(gòu)，循環(huán)(重復(fù))是計(jì)算機(jī)解題的一個(gè)重要特征。(5)輸入/輸出

程序的輸入是指用戶(hù)將數(shù)據(jù)通過(guò)輸入設(shè)備(如鍵盤(pán)等)輸入到程序中。程序的輸出是指程序把運(yùn)算結(jié)果以用戶(hù)可以理解的形式輸出到輸出設(shè)備(如顯示器、打印機(jī)等)。高級(jí)程序設(shè)計(jì)語(yǔ)言中通常以函數(shù)或語(yǔ)句的形式提供輸入輸出操作。現(xiàn)代高級(jí)程序設(shè)計(jì)語(yǔ)言通常都提供通過(guò)窗口、文本框、按鈕、組合框、圖表等圖形組件進(jìn)行輸入輸出。5.2程序設(shè)計(jì)語(yǔ)言(不講)(6)子程序

子程序就是將需要重復(fù)使用的程序段或分解的子問(wèn)題編寫(xiě)為一個(gè)邏輯上獨(dú)立的子程序，當(dāng)程序中需要使用子程序時(shí)，再對(duì)其進(jìn)行調(diào)用。使用子程序的好處是降低了程序的復(fù)雜度，使程序的結(jié)構(gòu)清晰，提高了程序設(shè)計(jì)的效率。一般程序設(shè)計(jì)語(yǔ)言中有兩種子程序：函數(shù)(Function)和過(guò)程(Procedure)，它們的主要區(qū)別是函數(shù)有返回值，而過(guò)程不能有返回值。5.3問(wèn)題求解過(guò)程

解決問(wèn)題的思維過(guò)程借助計(jì)算機(jī)求解問(wèn)題的過(guò)程5.4算法和數(shù)據(jù)結(jié)構(gòu)5.4.1什么是數(shù)據(jù)，數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介

數(shù)據(jù)是對(duì)客觀事物的描述，對(duì)計(jì)算機(jī)來(lái)說(shuō)，數(shù)據(jù)的含義非常廣泛，如數(shù)字、字符、圖形、色彩、聲音等都是數(shù)據(jù)。數(shù)據(jù)元素(DataElement)是組成數(shù)據(jù)的基本單位。一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位。例：公司員工數(shù)據(jù)的存儲(chǔ)姓名性別出生日期職位工資張軍男1975.5.6總經(jīng)理5080.00李芳女1980.12.12項(xiàng)目經(jīng)理4800.00王明男1979.4.19程序員4500.00劉杰男1974.6.23系統(tǒng)分析員4750.00趙麗女1977.11.9測(cè)試員3900.00

數(shù)據(jù)結(jié)構(gòu)研究的數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)處理這樣的最核心的問(wèn)題。不是幾個(gè)孤立的數(shù)據(jù)，而是大量的相互關(guān)聯(lián)的數(shù)據(jù)。數(shù)據(jù)元素之間的相互關(guān)系稱(chēng)為結(jié)構(gòu)。5.4.1什么是數(shù)據(jù)，數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介5.4算法和數(shù)據(jù)結(jié)構(gòu)5.4.2算法

算法(Algorithm)是指為解決給定問(wèn)題而需實(shí)施的有窮操作步驟的描述。

算法的五個(gè)重要特性：1）有窮性2）確定性3）可行性4）輸入5）輸出評(píng)價(jià)一個(gè)算法優(yōu)劣的標(biāo)準(zhǔn)：1）正確性2）可讀性3）健壯性4）效率性5.4算法和數(shù)據(jù)結(jié)構(gòu)算法的描述方法(1)用自然語(yǔ)言描述算法(2)用流程圖描述算法(3)使用偽代碼描述算法(4)用程序設(shè)計(jì)語(yǔ)言描述算法例1互換兩個(gè)數(shù)據(jù)單元內(nèi)容。（書(shū)上例5.4）例2求兩個(gè)正整數(shù)m和n的最大公約數(shù)的算法。用如上這四種方式描述出來(lái)。（書(shū)上例5.5）5.4算法和數(shù)據(jù)結(jié)構(gòu)第五章計(jì)算思維案例

計(jì)算思維反映的是利用計(jì)算機(jī)技術(shù)解決實(shí)際問(wèn)題的思維方法，如果對(duì)利用計(jì)算機(jī)技術(shù)如何解決實(shí)際問(wèn)題的認(rèn)知出現(xiàn)誤解，那是不可能達(dá)到目的的。很多初學(xué)者以為計(jì)算機(jī)神乎其神，似乎什么都能干。

和人腦相比，它只是會(huì)算，而且算的速度非常快，除此以外計(jì)算機(jī)幾乎沒(méi)有什么更多的優(yōu)越性了。如果你要完成的計(jì)算任務(wù)比較復(fù)雜，又不能(或者不會(huì))分解成計(jì)算機(jī)能接受的基本操作，那就沒(méi)法利用計(jì)算機(jī)求解了。記住，計(jì)算機(jī)永遠(yuǎn)都是在人腦的指揮下工作的！案例1合理分解和分配計(jì)算任務(wù)第五章計(jì)算思維案例

在計(jì)算機(jī)科學(xué)中，將大規(guī)模的復(fù)雜問(wèn)題分解成若干個(gè)較小規(guī)模的、更簡(jiǎn)單的問(wèn)題加以解決，是一種常用的計(jì)算思維。運(yùn)用問(wèn)題分解這種思維方法進(jìn)行問(wèn)題求解，首先需對(duì)問(wèn)題本身做出明確描述，并對(duì)問(wèn)題解法做出全局性決策，把問(wèn)題分解成相對(duì)獨(dú)立的子問(wèn)題，再以同樣的方式對(duì)每個(gè)子問(wèn)題進(jìn)一步精確化，直到獲得對(duì)問(wèn)題的明確的解答。在本章中，結(jié)構(gòu)化程序設(shè)計(jì)采取了計(jì)算思維中的典型方法——分解。按照“分而治之”的策略，將頂層問(wèn)題的求解目標(biāo)逐層分解成子目標(biāo)，每個(gè)子目標(biāo)用相應(yīng)的程序模塊進(jìn)行實(shí)現(xiàn)，這樣構(gòu)成求解整個(gè)問(wèn)題的程序。案例2大事化小、小事化了第五章計(jì)算思維案例

結(jié)構(gòu)化程序設(shè)計(jì)方法的一個(gè)重要原則就是“自頂向下、逐步求精”，它是指程序設(shè)計(jì)時(shí)，先描述頂層問(wèn)題的求解目標(biāo)，然后步步深入，設(shè)計(jì)一些比較粗略的子目標(biāo)作為過(guò)渡，再逐層細(xì)分，直到整個(gè)問(wèn)題可用程序設(shè)計(jì)語(yǔ)言明確地描述出來(lái)為止。程序的模塊化設(shè)計(jì)，則是針對(duì)任何一個(gè)大系統(tǒng)都可以按子結(jié)構(gòu)之間的疏密程度分解成較小的模塊，每個(gè)模塊完成一定問(wèn)題的求解。整個(gè)程序是由層次的、逐級(jí)細(xì)化的諸模塊組成。一個(gè)復(fù)雜的問(wèn)題可以看成由若干稍簡(jiǎn)單的問(wèn)題構(gòu)成。案例2大事化小、小事化了第五章計(jì)算思維案例

對(duì)于可以用計(jì)算機(jī)求解的問(wèn)題，所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)，問(wèn)題規(guī)模越小，解題所需的計(jì)算時(shí)間也越少，也越容易求解。因此可以將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破、分而治之。模塊化與自頂可下、逐步求精緊密聯(lián)系。日常工作中的層次化管理也是一種對(duì)分解方法的運(yùn)用。以企業(yè)運(yùn)行為例，一個(gè)大型企業(yè)也是一個(gè)非常復(fù)雜的系統(tǒng)，采取“金字塔”型的管理層次是常用的策略，將企業(yè)逐層分解，越上層的機(jī)構(gòu)越少，越向下功能分解越細(xì)、機(jī)構(gòu)數(shù)目越多。各級(jí)機(jī)構(gòu)管理好自己的下屬機(jī)構(gòu)，完成上級(jí)機(jī)構(gòu)制定的目標(biāo)，最終整個(gè)企業(yè)實(shí)現(xiàn)自己的整體目標(biāo)。案例2大事化小、小事化了第五章計(jì)算思維案例

計(jì)算思維是利用海量數(shù)據(jù)來(lái)加快計(jì)算，在時(shí)間和空間之間、在處理能力和存儲(chǔ)容量之間進(jìn)行折中的思維方法。計(jì)算機(jī)問(wèn)題求解是以計(jì)算機(jī)為工具，利用計(jì)算思維解決問(wèn)題的實(shí)踐活動(dòng)。計(jì)算機(jī)解題的核心是算法設(shè)計(jì)，設(shè)計(jì)算法是計(jì)算機(jī)問(wèn)題求解中非常重要的步驟。查找(Searching)也稱(chēng)檢索，計(jì)算機(jī)最重要的功能之一就是在浩瀚的數(shù)據(jù)中找到用戶(hù)所要的信息。但是計(jì)算機(jī)的速度還并沒(méi)有快到能瞬間完成這一過(guò)程的程度，而且等待計(jì)算機(jī)查找的數(shù)據(jù)集往往是異常龐大的，因此我們需要更快捷更有效的搜索方式。案例3海量查找第五章計(jì)算思維案例

世界上最龐大的搜索問(wèn)題是在網(wǎng)絡(luò)世界中搜索信息，網(wǎng)絡(luò)搜索引擎能實(shí)現(xiàn)同時(shí)為大量在線用戶(hù)在數(shù)以百萬(wàn)計(jì)的網(wǎng)頁(yè)中進(jìn)行高速查詢(xún)，這無(wú)疑是一個(gè)令人驚訝的事實(shí)，而它們能做到這點(diǎn)無(wú)非是因?yàn)槭褂昧苏_的算法。查找的結(jié)果有兩種：一種是查找到滿(mǎn)足條件的結(jié)點(diǎn)，稱(chēng)為查找成功；否則稱(chēng)為查找失敗。查找的方法很多，針對(duì)線性表的查找算法有順序查找和折半查找。案例3海量查找

查找(Searching)也稱(chēng)檢索，設(shè)表F中有n個(gè)結(jié)點(diǎn)，Ki是記錄Ri的關(guān)鍵字，現(xiàn)給定關(guān)鍵字K，在F中尋找關(guān)鍵字與K相同的結(jié)點(diǎn)R的過(guò)程，叫做查找。(1)順序查找

順序查找是線性表的最簡(jiǎn)單的查找算法。它是用給定的值與表中的每個(gè)結(jié)點(diǎn)的關(guān)鍵字逐個(gè)進(jìn)行比較運(yùn)算，若找到相等的關(guān)鍵字則查找成功，否則查找失敗。順序查找算法的優(yōu)點(diǎn)是適用范圍廣，對(duì)線性表中結(jié)點(diǎn)邏輯次序無(wú)關(guān)，即不要求按關(guān)鍵字排序。對(duì)線性表的物理存儲(chǔ)結(jié)構(gòu)也沒(méi)有要求，順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)均可。(2)折半查找

折半查找要求：線性表必須按關(guān)鍵字大小排好順序（可以假設(shè)從小到大排序），并且采用順序存儲(chǔ)方式。折半查找的基本思想是：先取表的中間位置的結(jié)點(diǎn)關(guān)鍵字與所給定的關(guān)鍵字進(jìn)行比較，如果相等，則查找成功。如果給定值比該結(jié)點(diǎn)的關(guān)鍵字大，則所找結(jié)點(diǎn)在表的后半部分；否則所找結(jié)點(diǎn)在表的前半部分，然后再把選定的部分表的中間結(jié)點(diǎn)的關(guān)鍵字與給定關(guān)鍵字進(jìn)行比較。如此反復(fù)進(jìn)行，直到查找成功或者查找失敗為止。例:第五章計(jì)算思維案例

排序(Sort)是數(shù)據(jù)處理中的一種重要運(yùn)算，它的功能是將一組數(shù)據(jù)元素(或記錄)從任意序列排列成一個(gè)按關(guān)鍵字排序的序列。這是一種常用的計(jì)算思維方法。幾乎所有計(jì)算機(jī)中的序列都是被排過(guò)序的，電子郵件列表按照日期排序，最新的郵件被放置在最頂端；播放器中的歌曲按照名字或歌手名排列在一起，以便你快速查找到最喜歡的那首歌，文件名則往往是按照字母順序排列的。那么計(jì)算機(jī)是如何進(jìn)行排序的呢？計(jì)算機(jī)科學(xué)家設(shè)計(jì)了很多排序的算法，直接插入排序、冒泡排序等。案例4排序第五章計(jì)算思維案例

人們?cè)谌粘Ｉ钪袑⑽锲酚幸?guī)律的擺放，如水果由小到大擺放，圖書(shū)按書(shū)名或?qū)W科順序排序等。將物品按照某種規(guī)律順