第一章工程軟件的基礎(chǔ)元素

1.1工程軟件概述

科學(xué)計算、信息處理、過程控制是計算機(jī)的三大應(yīng)用領(lǐng)域。計算機(jī)最早應(yīng)用于科學(xué)計算，20世紀(jì)70年代，計算機(jī)的應(yīng)用范圍擴(kuò)大到數(shù)據(jù)信息處理，數(shù)據(jù)信息處理是當(dāng)今計算機(jī)應(yīng)用的重要領(lǐng)域。由于計算機(jī)具有邏輯運(yùn)算的能力，從20世紀(jì)60年代起計算機(jī)被廣泛應(yīng)用于工業(yè)生產(chǎn)過程的實時監(jiān)測和控制，這是工程軟件大量出現(xiàn)的開始。伴隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，計算機(jī)應(yīng)用的網(wǎng)絡(luò)化已引起了生產(chǎn)方式的深刻變革。

工程軟件所面向的應(yīng)用領(lǐng)域主要有如下幾個方面：

1、工程輔助系統(tǒng)2、工程事務(wù)處理3、現(xiàn)代工程通信及信息交流工程軟件的三個基本要素是數(shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)和算法，

1.2數(shù)據(jù)結(jié)構(gòu)概述1.2.1數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)運(yùn)算的概念數(shù)據(jù)結(jié)構(gòu)是計算機(jī)科學(xué)的重要基礎(chǔ)，近年來已發(fā)展成為一個專門學(xué)科。根據(jù)各種實際問題的需求，人們提出了許多組織數(shù)據(jù)的方法，從而構(gòu)造了不同的數(shù)據(jù)結(jié)構(gòu)，而且隨著處理實際問題的需要，新的更加復(fù)雜的數(shù)據(jù)結(jié)構(gòu)還在不斷地被提出。

數(shù)據(jù)

是對客觀事物的符號表示，在計算機(jī)科學(xué)中是指所有能輸入到計算機(jī)中并被計算機(jī)程序處理的符號的總稱。數(shù)據(jù)元素

數(shù)據(jù)元素是數(shù)據(jù)的基本單位，是數(shù)據(jù)集合中的個體，是對事物屬性中基本方面的測量。

數(shù)據(jù)項

具有獨(dú)立意義的最小數(shù)據(jù)單位，是對數(shù)據(jù)元素屬性的描述。

數(shù)據(jù)類型

是指某種程序設(shè)計語言所允許使用的變量種類。有關(guān)數(shù)據(jù)結(jié)構(gòu)的概念：

數(shù)據(jù)對象

是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。

數(shù)據(jù)結(jié)構(gòu)

是帶有結(jié)構(gòu)的元素的集合，它是指數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。

數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的描述，它只抽象地反映數(shù)據(jù)元素間的邏輯關(guān)系，而不涉及其在計算機(jī)中的存在方式。

數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機(jī)存儲器中的實際表示，它不僅要存儲數(shù)據(jù)元素的內(nèi)容，還要把數(shù)據(jù)元素間的關(guān)聯(lián)體現(xiàn)出來，它是邏輯結(jié)構(gòu)用計算機(jī)所能理解的方式的具體實現(xiàn)。

算法是為解決特定問題而采取的有限操作步驟，是對解題方案的準(zhǔn)確而完整的描述。在計算機(jī)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)與算法是密不可分，缺一不可的。程序=數(shù)據(jù)結(jié)構(gòu)+算法

強(qiáng)調(diào)了數(shù)據(jù)結(jié)構(gòu)和算法之間的天然聯(lián)系。

有關(guān)算法的概念：有關(guān)運(yùn)算的概念：數(shù)據(jù)結(jié)構(gòu)往往是與施加于其上的運(yùn)算密切相關(guān)的。數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的，運(yùn)算的具體實現(xiàn)要在存儲結(jié)構(gòu)上進(jìn)行。最常用的運(yùn)算有：

1、插入在數(shù)據(jù)結(jié)構(gòu)中增加新的結(jié)點(diǎn)2、刪除把指定的結(jié)點(diǎn)從數(shù)據(jù)結(jié)構(gòu)中去除3、更新改變指定結(jié)點(diǎn)的值或改變指定的某些結(jié)點(diǎn)之間的關(guān)系4、查找在數(shù)據(jù)結(jié)構(gòu)中查找滿足一定條件的結(jié)點(diǎn)5、排序?qū)?shù)據(jù)結(jié)構(gòu)中各個結(jié)點(diǎn)按指定數(shù)據(jù)項的值，以升序或降序等重新排列復(fù)雜的運(yùn)算過程可以是以上各種基本操作的組合。1.2.2數(shù)據(jù)結(jié)構(gòu)的分類

依據(jù)數(shù)據(jù)元素間關(guān)系的特點(diǎn)，數(shù)據(jù)結(jié)構(gòu)可分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件：1、有且有一個根結(jié)點(diǎn)；2、每一個結(jié)點(diǎn)最多有一個前驅(qū)，最多有一個后繼。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。

根據(jù)對線性結(jié)構(gòu)中數(shù)據(jù)元素的存取方式的不同，又可將其分為直接存取結(jié)構(gòu)、順序存取結(jié)構(gòu)和廣義索引結(jié)構(gòu)。對于直接存取結(jié)構(gòu)，可以直接存取某一特定數(shù)據(jù)元素而不需先訪問其前驅(qū)。對于順序存取結(jié)構(gòu)，只能從數(shù)據(jù)序列中的第一個數(shù)據(jù)元素開始，按順序依次查找，直到指定的元素。廣義索引是通過關(guān)鍵碼進(jìn)行索引的。通過設(shè)定數(shù)據(jù)記錄中某一數(shù)據(jù)項或某一組全數(shù)據(jù)項為關(guān)鍵碼，通過關(guān)鍵碼來索引記錄。

在非線性結(jié)構(gòu)中各個數(shù)據(jù)元素不必保持在一個線性序列中，每個數(shù)據(jù)元素可能多個其它數(shù)據(jù)元素發(fā)生關(guān)聯(lián)。在非線性結(jié)構(gòu)中。各數(shù)據(jù)元素之間的前驅(qū)與后繼的關(guān)系要比線性結(jié)構(gòu)復(fù)雜，因此，對非線性結(jié)構(gòu)的存儲與處理比線性結(jié)構(gòu)要復(fù)雜得多。典型的非線性結(jié)構(gòu)（樹結(jié)構(gòu)）實例。典型的非線性結(jié)構(gòu)（圖結(jié)構(gòu)）實例。1.2.3數(shù)據(jù)結(jié)構(gòu)的表示

1、數(shù)據(jù)的邏輯結(jié)構(gòu)對數(shù)據(jù)間關(guān)系的描述即是數(shù)據(jù)的邏輯結(jié)構(gòu)，形式上可以用一個二元組來表示，即：

B=(K，R)

其中K為結(jié)點(diǎn)的有窮集合，即K是由有限個結(jié)點(diǎn)所構(gòu)成的集合；R是K上的的有窮集合，即R是由有限關(guān)系所構(gòu)成的集合，其中的每個關(guān)系都是從K到K的關(guān)系。

2、數(shù)據(jù)的存儲結(jié)構(gòu)

有4種基本的物理存儲映像方法：順序的方法、鏈接的方法、索引的方法和散列的方法。一個數(shù)據(jù)結(jié)構(gòu)的存儲映像都是以上4種基本映像之一或是它們的組合。一個邏輯結(jié)構(gòu)可以有不同的映像方法。

1.2.4數(shù)據(jù)類型及數(shù)據(jù)抽象

數(shù)據(jù)類型則最早出現(xiàn)在高級算法語言中，用以刻畫數(shù)據(jù)操作對象的特性。

數(shù)據(jù)類型可分為簡單型和結(jié)構(gòu)類型兩種。簡單類型中的每個數(shù)據(jù)都是無法再分割的整體。結(jié)構(gòu)類型由簡單類型按照一定的規(guī)則構(gòu)造而成，其數(shù)據(jù)結(jié)構(gòu)就是相應(yīng)元素的集合和元素之間所含關(guān)系的集合，并且結(jié)構(gòu)類型中可以包含結(jié)構(gòu)類型。

所謂數(shù)據(jù)抽象就是提取反映問題本質(zhì)的數(shù)據(jù)結(jié)構(gòu)。抽象數(shù)據(jù)類型的概念其實質(zhì)和高級算法語言中的數(shù)據(jù)類型概念相同。抽象數(shù)據(jù)類型(AbstractDataType,ADT)是指基于一類邏輯關(guān)系的數(shù)據(jù)類型以及定義在這個類型之上的一組操作。抽象數(shù)據(jù)類型的定義取決于客觀存在的一組邏輯特性，而與其在計算機(jī)內(nèi)如何表示及實現(xiàn)無關(guān)。一個線性表的抽象數(shù)據(jù)類型可描述如下：ADTLinear_list其中數(shù)據(jù)元素：所有ai屬于同一數(shù)據(jù)對象，i=1,2,…,n；邏輯結(jié)構(gòu)：所有數(shù)據(jù)元素ai

(i=1,2，…,n-1)存在次序關(guān)系<i,ai+1>，a1無前驅(qū)，an無后繼；操作：設(shè)L為Linear_list類型的線性表Initial(L)為線性表初始化操作；Length(L)為求線性表表長操作；Get(L,i)為取線性表的第i個元素；Insert(L,i,b)在線性表L的第i個位置插入元素b；Delete(L，i)刪除線性表的第i個元素。1.3算法概述

1.3.1算法的概念

算法(Algorithm)是為解決一個問題采取的方法和步驟，也就是說，算法是為實現(xiàn)某種計算過程而規(guī)定的基本動作的執(zhí)行序列。算法分兩大類：數(shù)值計算方法和非數(shù)值計算方法。

算法有如下的特點(diǎn)：

1.算法有有限的操作步驟，即算法的有窮性（finiteness）2.算法的每一步驟都應(yīng)為確定的，即算法的確定性(definiteness)3.執(zhí)行算法時可從外界輸入信息，即算法需要足夠的輸入信息(information)4.算法的目的是為了求解，因此算法要有輸出，即算法的輸出(output)5.算法的每一步都應(yīng)有效地執(zhí)行，即算法的有效性(effectiveness)1.3.2算法的描述

算法的描述方法很多，根據(jù)描述算法語言的不同，可將算法分為以下常用的四種：

1、框圖描述法。

2、非形式描述法。

3、類高級算法語言描述法。

4、高級算法語言描述法。

1.3.3算法分析

判斷一個算法的優(yōu)劣主要有以下幾個標(biāo)準(zhǔn)：1、正確性

2、可使用性

3、健壯性

4、效率

時間代價是常用的評價指標(biāo)，往往用時間復(fù)雜度來衡量。當(dāng)一個算法轉(zhuǎn)換成程序并在計算機(jī)上執(zhí)行時，其運(yùn)行所需要的時間取總是取決于下列因素：1、硬件的速度2、所選用的程序設(shè)計語言

3、編譯程序所生成目標(biāo)代碼的質(zhì)量4、問題的規(guī)模時間復(fù)雜度（Timecomplexity）又稱計算復(fù)雜度，它是一個算法運(yùn)行時間的相對度量。一個程序的時間復(fù)雜度是指程序運(yùn)行從開始到結(jié)束所需要的時間。定義：如果存在兩個正常數(shù)c和n0，使得對所有的n，n≥n0，有f(n)≤cg(n)，則記為T(n)=O(g(n))。使用O記號表示的算法的時間復(fù)雜度稱為算法的漸進(jìn)時間復(fù)雜度(AsymptoticComplexity)。通常用O(1)表示常數(shù)計算時間。常見的漸進(jìn)時間復(fù)雜度有：

O（1）＜O（log2n）＜O(n)＜O(nlog2n)＜O(n2)＜O(n3)＜O(2n)一個程序的空間復(fù)雜度（Space