1、第五章 計(jì)算機(jī)軟件技術(shù)基礎(chǔ),硬件是計(jì)算機(jī)系統(tǒng)的基礎(chǔ)，但沒有軟件的計(jì)算機(jī)是無法工作的。計(jì)算機(jī)能廣泛地應(yīng)用于各個(gè)領(lǐng)域完全是因?yàn)橛辛素S富的計(jì)算機(jī)軟件。 本章將學(xué)習(xí)計(jì)算機(jī)軟件和計(jì)算機(jī)軟件開發(fā)的相關(guān)知識(shí)，如什么是軟件，程序設(shè)計(jì)語言的分類及構(gòu)成、數(shù)據(jù)結(jié)構(gòu)與算法、軟件開發(fā)過程等。,需要編寫應(yīng)用軟件,如何讓計(jì)算機(jī)按我們的意志行事？,5.1 計(jì)算機(jī)軟件系統(tǒng),5.1.1 軟件的概念與特點(diǎn),軟件是由程序、數(shù)據(jù)及其相關(guān)文檔三部分組成。, 程序：按照事先設(shè)計(jì)的功能和性能要求執(zhí)行的計(jì)算機(jī)指令序列。 數(shù)據(jù)：使程序能夠正常操縱信息的數(shù)據(jù)結(jié)構(gòu)。 文檔：與程序開發(fā)、維護(hù)和使用有關(guān)的資料。,5.1 計(jì)算機(jī)軟件系統(tǒng),5.1.2 軟件

2、的分類,軟件可以按功能、工作方式、服務(wù)對(duì)象進(jìn)行劃分，其中按軟件功能可劃分為：, 支撐軟件：又稱為軟件開發(fā)環(huán)境。是介于系統(tǒng)軟件和應(yīng)用軟件之間的中間層軟件，是支撐各種軟件的開發(fā)與維護(hù)的軟件。, 應(yīng)用軟件：針對(duì)特定領(lǐng)域開發(fā)，為特定目的服務(wù)的軟件。, 系統(tǒng)軟件：能與計(jì)算機(jī)硬件緊密配合，使計(jì)算機(jī)系統(tǒng)的各個(gè)部件、相關(guān)的軟件和數(shù)據(jù)協(xié)調(diào)、高效工作。,5.1 計(jì)算機(jī)軟件系統(tǒng),計(jì)算機(jī)軟件系統(tǒng)中所包括的各種軟件之間的關(guān)系不是并列的，而是有一定的層次關(guān)系。,5.1.3 計(jì)算機(jī)軟件的層次結(jié)構(gòu),系統(tǒng)軟件,支撐軟件,應(yīng)用軟件,5.2 程序設(shè)計(jì)語言,計(jì)算機(jī)的本質(zhì)是“程序的機(jī)器”，程序和指令的思想是計(jì)算機(jī)系統(tǒng)中最基本的概念。只

3、有懂得程序設(shè)計(jì)，才能懂得計(jì)算機(jī)，真正了解計(jì)算機(jī)是怎樣工作的。,什么人需要學(xué)程序設(shè)計(jì),比爾蓋茨說 最 終 用 戶 Office等 程序開發(fā)人員-Visual Basic等 系統(tǒng)開發(fā)人員-Visual C+等,你聽過用過哪些編程語言？,BASIC、VB、VB.NET C、VC+、C# FORTRAN PASCAL、Delphi COBOL Java ,5.2 程序設(shè)計(jì)語言,簡(jiǎn)單講，程序設(shè)計(jì)就是用計(jì)算機(jī)語言編寫程序。,程序 = 算法 + 數(shù)據(jù)結(jié)構(gòu),編寫計(jì)算機(jī)程序時(shí)使用的語言稱為程序設(shè)計(jì)語言(Programming Language)，程序設(shè)計(jì)語言分為機(jī)器語言、匯編語言和高級(jí)語言三種。,對(duì)數(shù)據(jù)操作的步

4、驟,如何表示、組織和存儲(chǔ)數(shù)據(jù),算法是程序的靈魂，不掌握算法就無法編寫出程序。 語言是實(shí)現(xiàn)算法的工具，是外殼，是表現(xiàn)形式。 要做到二者的高度統(tǒng)一。,5.2 程序設(shè)計(jì)語言,5.2.1 機(jī)器語言,機(jī)器語言是唯一能被計(jì)算機(jī)直接理解和執(zhí)行的程序設(shè)計(jì)語言，屬低級(jí)語言。機(jī)器語言的一條語句就是一條指令，機(jī)器指令的格式如下：,例如：計(jì)算256+16結(jié)果的機(jī)器代碼如下(以十六進(jìn)制表示)：,5.2 程序設(shè)計(jì)語言,5.2.2 匯編語言,為了解決機(jī)器語言難記憶、可讀性差的缺點(diǎn)，人們把機(jī)器指令中的操作碼和操作數(shù)用英文助記符來表示，這種助記符語言稱為匯編語言，也屬于低級(jí)語言。,匯編語言編寫的程序?qū)儆诜?hào)程序，計(jì)算機(jī)不能直接

5、識(shí)別和執(zhí)行，必須翻譯成計(jì)算機(jī)能識(shí)別的機(jī)器指令后才能在計(jì)算機(jī)上執(zhí)行，其翻譯過程如下：,5.2 程序設(shè)計(jì)語言,5.2.3 高級(jí)語言,高級(jí)語言是一類程序設(shè)計(jì)語言的統(tǒng)稱，它采用接近人類自然語言的表示方法，并遵循一定的語法規(guī)則來編寫程序。,實(shí)現(xiàn)求整數(shù)的絕對(duì)值的程序段：,int intVar, result; scanf(“%d”, ,5.2 程序設(shè)計(jì)語言,高級(jí)語言程序的翻譯和執(zhí)行過程如下：,高級(jí)語言編寫的程序也屬于符號(hào)程序，不能直接在計(jì)算機(jī)上執(zhí)行，必須通過程序的翻譯才能執(zhí)行，其翻譯成指令代碼的方法主要有編譯和解釋兩種。,5.2 程序設(shè)計(jì)語言,5.2 程序設(shè)計(jì)語言,5.2.4 程序設(shè)計(jì)語言的構(gòu)成,程序設(shè)計(jì)

6、語言的構(gòu)成主要包括以下幾個(gè)方面：,(1) 數(shù)據(jù)類型,基本數(shù)據(jù)類型：是由程序設(shè)計(jì)語言內(nèi)置的，其特點(diǎn)是不能再分解為其它的類型。在主流的程序設(shè)計(jì)語言中一般包括：整數(shù)類型、實(shí)數(shù)類型、字符類型、布爾類型等。 構(gòu)造數(shù)據(jù)類型：是由基本數(shù)據(jù)類型按照某種方式組合構(gòu)成的。常見的構(gòu)造數(shù)據(jù)類型有：數(shù)組類型、記錄類型(結(jié)構(gòu)體) 等等。,(2) 運(yùn)算符和表達(dá)式,在程序設(shè)計(jì)中使用表達(dá)式可完成各種各樣的運(yùn)算。表達(dá)式通常包括：常量、變量、運(yùn)算符和函數(shù)調(diào)用等。,5.2 程序設(shè)計(jì)語言,(3) 語句,程序是對(duì)計(jì)算機(jī)要執(zhí)行的操作的描述，高級(jí)語言源程序的基本組成單位就是語句。 語句按功能可以分為兩類： 用于描述操作運(yùn)算的語句，如賦值語句

7、； 用于控制操作運(yùn)算流程的語句，如分支控制語句。,(4) 控制結(jié)構(gòu), 順序結(jié)構(gòu)，按照語句出現(xiàn)的先后順序依次執(zhí)行。 分支結(jié)構(gòu)，根據(jù)給定條件判斷，決定程序執(zhí)行的順序。 循環(huán)結(jié)構(gòu)，循環(huán)(重復(fù))是計(jì)算機(jī)解題的一個(gè)重要特征。,5.2 程序設(shè)計(jì)語言,(5) 輸入/輸出,高級(jí)程序設(shè)計(jì)語言中通常以函數(shù)或語句的形式提供輸入輸出操作?，F(xiàn)代高級(jí)程序設(shè)計(jì)語言通常都提供通過窗口、文本框、按鈕、組合框、圖表等圖形組件進(jìn)行輸入輸出。,(6) 子程序,子程序就是將需要重復(fù)使用的程序段或分解的子問題編寫成一個(gè)獨(dú)立的子程序，當(dāng)程序中需要使用子程序時(shí)，再對(duì)其進(jìn)行調(diào)用。 子程序有兩種：函數(shù)(Function)和過程(Procedur

8、e)，它們的主要區(qū)別是函數(shù)有返回值，而過程不能有返回值。,5.3 數(shù)據(jù)結(jié)構(gòu),5.3.1 什么是數(shù)據(jù),數(shù)據(jù)是對(duì)客觀事物的描述，對(duì)計(jì)算機(jī)來說，數(shù)字、字符、圖形、色彩、聲音等都是數(shù)據(jù)。 數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位。一個(gè)數(shù)據(jù)元素可以是一個(gè)單個(gè)數(shù)據(jù)也可以由若干個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位。,例：公司員工數(shù)據(jù)的存儲(chǔ)(一個(gè)員工信息可以構(gòu)造一個(gè)一維數(shù)組的數(shù)據(jù)結(jié)構(gòu)),數(shù)據(jù)項(xiàng),數(shù)據(jù)元素,5.3 數(shù)據(jù)結(jié)構(gòu),5.3.2 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容,數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)間的相互關(guān)系。數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容包括:數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)運(yùn)算。,(1)數(shù)據(jù)的邏輯結(jié)構(gòu),數(shù)據(jù)元素之間的邏輯上的相互關(guān)系稱為數(shù)據(jù)的邏

9、輯結(jié)構(gòu)，它描述數(shù)據(jù)的組織形式。,元素之間是一對(duì)一關(guān)系 例如:公司員工數(shù)據(jù)表中每個(gè)成員關(guān)系,元素之間是多對(duì)多關(guān)系 例如:華農(nóng)與周邊地區(qū)的位置關(guān)系,元素之間是一對(duì)多關(guān)系 例如:一對(duì)夫婦和他們的全部子孫,元素之間是松散關(guān)系 例如:自然數(shù)的全體,5.3 數(shù)據(jù)結(jié)構(gòu),(2) 數(shù)據(jù)的物理結(jié)構(gòu),數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式，稱為數(shù)據(jù)的物理結(jié)構(gòu)或存儲(chǔ)結(jié)構(gòu)。它包括：, 順序存儲(chǔ)方式，把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中。 鏈?zhǔn)酱鎯?chǔ)方式，每個(gè)結(jié)點(diǎn)分為數(shù)據(jù)域和指針域兩部分，數(shù)據(jù)域存儲(chǔ)數(shù)據(jù)元素，指針域存儲(chǔ)與該結(jié)點(diǎn)具有邏輯關(guān)系的結(jié)點(diǎn)的地址。 索引存儲(chǔ)方式，數(shù)據(jù)元素存放在一個(gè)不連續(xù)存儲(chǔ)區(qū)域里。再建一個(gè)附加的

10、索引表，索引表中的第i項(xiàng)表示第i個(gè)元素的存儲(chǔ)地址。 散列存儲(chǔ)方式，數(shù)據(jù)元素均勻地分布在連續(xù)的存儲(chǔ)區(qū)域里，用散列函數(shù)計(jì)算各結(jié)點(diǎn)的存儲(chǔ)地址。,5.3 數(shù)據(jù)結(jié)構(gòu),例如:線性表是一種邏輯結(jié)構(gòu),若采用順序存儲(chǔ)方式，可稱其為順序表；若采用鏈?zhǔn)酱鎯?chǔ)方法，可稱其為鏈表；若采用散列存儲(chǔ)方法，可稱其為散列表。,右圖為某學(xué)生各科成績(jī)表分別采用順序和鏈?zhǔn)酱鎯?chǔ)的情形。前者存儲(chǔ)在一片連續(xù)空間，后者則存儲(chǔ)在非連續(xù)空間。,5.3 數(shù)據(jù)結(jié)構(gòu),(3) 數(shù)據(jù)結(jié)構(gòu)的運(yùn)算,數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是定義在數(shù)據(jù)邏輯結(jié)構(gòu)上的操作，如插入、刪除、查找、排序等。,比如一張表格，可能需要進(jìn)行查找、增加、修改、刪除記錄等，進(jìn)行這樣的操作已不是加減乘除這樣一

11、些算術(shù)運(yùn)算，在數(shù)據(jù)結(jié)構(gòu)中，運(yùn)算常常涉及算法的問題。,5.3 數(shù)據(jù)結(jié)構(gòu),5.3.3 常見數(shù)據(jù)結(jié)構(gòu)介紹 (了解),(1) 數(shù)組,數(shù)組屬于線性數(shù)據(jù)結(jié)構(gòu)，是在計(jì)算機(jī)內(nèi)存中使用一組連續(xù)的存儲(chǔ)單元保存數(shù)據(jù)類型相同的一組數(shù)據(jù)，這些數(shù)據(jù)擁有相同的變量名，稱為數(shù)組名。,5.3 數(shù)據(jù)結(jié)構(gòu),(2) 鏈表,鏈表(Linked List)是采用鏈?zhǔn)酱鎯?chǔ)的線性表。線性鏈表的結(jié)點(diǎn)由數(shù)據(jù)域和指針域兩個(gè)部分組成，數(shù)據(jù)域存儲(chǔ)數(shù)據(jù)元素，指針域存儲(chǔ)一個(gè)指向直接后繼結(jié)點(diǎn)的指針。,5.3 數(shù)據(jù)結(jié)構(gòu),(3) 二叉樹,二叉樹是一種常用的非線性數(shù)據(jù)結(jié)構(gòu)，其定義為：二叉樹是一個(gè)結(jié)點(diǎn)的集合，該集合或者為空，或者滿足下面兩個(gè)條件： 有且僅有一個(gè)稱為

12、根的結(jié)點(diǎn)。 其它結(jié)點(diǎn)分為兩個(gè)互不相交的集合T1、T2。T1和T2均為二叉樹，并且在T1和T2之間存在順序關(guān)系(T1在T2之前)，分別稱為根的左子樹和右子樹。,二叉樹的5種基本形態(tài),5.3 數(shù)據(jù)結(jié)構(gòu),二叉樹的存儲(chǔ)結(jié)構(gòu),5.3 數(shù)據(jù)結(jié)構(gòu),遍歷二叉樹,遍歷二叉樹是非常重要的一種運(yùn)算。“遍歷”的含義是對(duì)結(jié)構(gòu)中的每個(gè)數(shù)據(jù)都訪問一次且僅訪問一次。可以有三種訪問路徑： 前序遍歷:訪問根結(jié)點(diǎn);前序遍歷左子樹;前序遍歷右子樹 中序遍歷:中序遍歷左子樹;訪問根結(jié)點(diǎn);中序遍歷右子樹 后序遍歷:后序遍歷左子樹;后序遍歷右子樹;訪問根結(jié)點(diǎn), 前序遍歷：A B D E F G C 中序遍歷：D B F E G A C 后

13、序遍歷：D F G E B C A,5.4 算法,5.4.1 算法的基本概念,算法是指為解決給定問題而需實(shí)施的有窮操作步驟的描述。,5.4.2 算法的描述方法,(1) 用自然語言描述算法 (2) 用流程圖描述算法 (3) 使用偽代碼描述算法 (4) 用程序設(shè)計(jì)語言描述算法,算法的描述方法有以下四種：,5.4 算法,5.4.3 查找算法(了解),查找(Searching)也稱檢索，設(shè)表F中有n個(gè)結(jié)點(diǎn)，Ki是記錄Ri的關(guān)鍵字，現(xiàn)給定關(guān)鍵字K，在F中尋找關(guān)鍵字與K相同的結(jié)點(diǎn)R的過程，叫做查找。,(1) 順序查找,順序查找是線性表的最簡(jiǎn)單的查找算法。它是用給定的值與表中的每個(gè)結(jié)點(diǎn)的關(guān)鍵字逐個(gè)進(jìn)行比較運(yùn)

14、算，若找到相等的關(guān)鍵字則查找成功，否則查找失敗。 順序查找算法的優(yōu)點(diǎn)是適用范圍廣，對(duì)線性表中結(jié)點(diǎn)邏輯次序無關(guān)，即不要求按關(guān)鍵字排序。對(duì)線性表的物理存儲(chǔ)結(jié)構(gòu)也沒有要求，順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)均可。,5.4 算法,(2) 折半查找,折半查找的基本思想是： 先取表的中間位置的結(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)行，直到查找成功或者查找失敗為止。,5.4 算法,例:,5.4 算法,5.4.4 排序算法(了解),排序(Sort)是數(shù)據(jù)

15、處理中的一種重要運(yùn)算，它的功能是將一組數(shù)據(jù)元素(或記錄)從任意序列排列成一個(gè)按關(guān)鍵字排序的序列。 按照排序過程中涉及的存儲(chǔ)器的不同將排序分為內(nèi)部排序和外部排序兩類，其中內(nèi)部排序是指整個(gè)排序過程都在內(nèi)存中進(jìn)行的排序。,5.4 算法,(1) 直接插入排序,算法的基本思想如下： 開始時(shí)，把第一個(gè)記錄看成是已經(jīng)排好序的子序列，這時(shí)子序列中只有一個(gè)記錄； 從第二個(gè)記錄起到最后一個(gè)記錄，依次將每個(gè)記錄與前面子序列的記錄按關(guān)鍵字比較，確定記錄插入的位置； 將記錄插入到子序列中，子序列記錄個(gè)數(shù)加1，直至子序列長(zhǎng)度與待排序列長(zhǎng)度相等時(shí)結(jié)束。,5.4 算法,(1) 直接插入排序,5.4 算法,5.4.4 排序算法

16、(了解),(2) 冒泡排序,冒泡排序的算法思想是： 將第n個(gè)記錄的關(guān)鍵字與將第n-1個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序則將兩個(gè)記錄進(jìn)行位置的交換，否則保持原來順序； 將第n-1個(gè)記錄的關(guān)鍵字與將第n-2個(gè)記錄的關(guān)鍵字進(jìn)行比較； 重復(fù)上述排序過程，直到全部關(guān)鍵字均比較一遍； 上面三步的比較交換過程稱為第一趟排序，其結(jié)果是使關(guān)鍵字最小的記錄被交換到了第1個(gè)記錄的位置，完成一趟排序； 第二趟排序從第n個(gè)記錄到第2個(gè)記錄進(jìn)行同樣的操作，結(jié)果是使關(guān)鍵字次小的記錄被交換到了第2個(gè)記錄的位置； 依次類推，第i趟排序是從第n個(gè)記錄到第i個(gè)記錄依次比較交換。,5.4 算法,(2) 冒泡排序,5.5 軟件工程簡(jiǎn)介,

17、5.5.1 軟件工程提出,早期,在軟件開發(fā)過程中出現(xiàn)了許多嚴(yán)重阻礙軟件發(fā)展的問題，主要表現(xiàn)在以下幾個(gè)方面： 軟件開發(fā)無計(jì)劃性。 軟件開發(fā)過程無規(guī)范。 軟件產(chǎn)品無評(píng)測(cè)手段。,1990年電氣電子工程師協(xié)會(huì)(IEEE)給出了軟件工程的一個(gè)定義：“軟件工程是把系統(tǒng)化的、規(guī)范的、可度量的方法應(yīng)用于軟件開發(fā)、運(yùn)行和維護(hù)的過程，也就是把工程化運(yùn)用于軟件工程，并對(duì)這樣的方法進(jìn)行研究”。,5.5 軟件工程簡(jiǎn)介,5.5.2 軟件生命周期, 制定計(jì)劃：確定要開發(fā)軟件系統(tǒng)的總體目標(biāo)。 需求分析：對(duì)要開發(fā)軟件提出的需求進(jìn)行分析并給出詳細(xì)定義。 軟件設(shè)計(jì)：設(shè)計(jì)人員首先進(jìn)行概要設(shè)計(jì)，然后進(jìn)行詳細(xì)設(shè)計(jì)，為程序代碼的編寫打下基

18、礎(chǔ)。 程序編碼：使用程序設(shè)計(jì)語言把軟件設(shè)計(jì)轉(zhuǎn)換成計(jì)算機(jī)可以接受的程序代碼，也稱為軟件實(shí)現(xiàn)。 軟件測(cè)試：測(cè)試是保證軟件質(zhì)量的重要手段。 運(yùn)行與維護(hù)：軟件交付后就進(jìn)入它的運(yùn)行時(shí)期，在這個(gè)過程中可能由于多方面的原因需要對(duì)軟件進(jìn)行修改，稱為軟件的維護(hù)。,與其它工業(yè)產(chǎn)品一樣，軟件產(chǎn)品也有一個(gè)生產(chǎn)、使用和消亡的過程，稱為軟件生命周期。軟件生命周期分為六個(gè)步驟：,5.5 軟件工程簡(jiǎn)介,5.5.3 軟件開發(fā)模型,軟件開發(fā)模型也叫軟件過程模型，是軟件系統(tǒng)開發(fā)項(xiàng)目總貌的一種描述，它是從軟件項(xiàng)目計(jì)劃的制定到軟件最后停止使用的整個(gè)過程的結(jié)構(gòu)框架。 到目前為止，已經(jīng)提出了多種軟件生命周期模型，如：瀑布模型、螺旋模型、演化模型、噴泉模型等。,5.5 軟件工程簡(jiǎn)介,軟件開發(fā)方法主要包括以下兩種：,(1) 結(jié)構(gòu)化開發(fā)方法,結(jié)構(gòu)化方