主講教師：朱海華機電學院15B426Email:zhuhh@軟件技術基礎1緒

論工程軟件概述計算機三大應用領域：科學計算、信息處理、過程控制。隨著信息技術的普及，各類計算機軟硬件系統在工程應用領域的廣泛應用。工程軟件在實際工程應用中占有相當重要的地位。工程軟件主要應用領域包括：

工程輔助系統：工程數值計算（EngineeringComputation）、計算機輔助設計CAD、計算機輔助制造CAM、計算機輔助工程教育CAEE、計算機集成制造系統CIMS、計算機輔助測試CAT、工業(yè)控制IC、計算機仿真CS等。

工程事務處理：分為事務型系統、管理型系統、決策型系統。

現代工程通信及信息交流：通過支持計算機網絡的工程軟件不僅可以實現遠程的數據傳輸、狀態(tài)監(jiān)控和現場資源配置等工作，而且還能異地共享和交流各種生產信息資源。2緒

論工程軟件的基本元素工程軟件的三個基本要素是數據、數據結構和算法。

工程數據是工程軟件系統的處理對象。

數據結構是對工程數據的組織。組織結構良好的數據不僅可以提高工程數據處理的效率，而且數據的可靠性也能得到有效的保障。

算法提供處理數據的手段和方法，是提取數據內涵的一系列行為的總稱。3緒論著名計算機科學家Wirth(沃思)提出:

數據結構+算法＝程序然而,僅有這些還不夠,應是:

數據結構＋算法＋程序設計方法＋語言工具和環(huán)境＝程序程序設計算法設計數據結構行為特性的設計結構特性的設計算法的效率通常與數據的存儲結構有直接關系4第1章算法1.1算法的基本概念1.2算法設計基本方法1.3算法的復雜度分析51.1算法的基本概念概念

算法是為解決一個問題采取的方法和步驟。也就是說，算法是為實現某種計算過程而規(guī)定的基本動作的執(zhí)行序列。算法的實現–自動機器解--指令的有限序列。自動機的能力：對于執(zhí)行體系來說是一種制約描述形式的理解能力實現描述的執(zhí)行能力算法的有限自動機解--在有限的存儲空間和有限的時間內通過有限的步驟得到預期的結果。61.1.1算法的基本特征1.能行性(effectiveness):

每一操作都可以通過可實現的基本運算執(zhí)行有限次來實現步驟合理性步驟可操作性達到預期目的與具體實現方式和環(huán)境有關。2.確定性(definiteness):在所指定的范疇內無模糊性在所指定的范疇內無多義性。檢驗：相同輸入相同輸出。7算法的基本特征（續(xù)）3.有窮性(finiteness)步驟有窮性時間有限性4.完備性(self-contained)初始條件應明確限定范圍內條件應齊備結果可展現對異常情況的容錯性8算法的定義

一組嚴謹定義運算順序的規(guī)則，并且每一個規(guī)則都是有效且明確的，此順序將在有限的次數下終止并獲得預期的結果。91.1.2算法的基本要素對數據對象的運算和操作針對算法涉及的數據信息最基本的動作和步驟單元算法的控制結構針對算法的過程步驟控制基本操作和步驟的組合順序10算法要素描述系統的組成1.運算和操作的描述標識符運算符:算術運算符：+，-，*，/等關系運算符：>，<，==，!=，＞=。＜=邏輯運算符：&&(邏輯與)，！(邏輯非)，||(邏輯或)

位運算符：&，|，~，…數據傳輸：賦值，輸入，輸出等。11算法描述方式算法描述方式：框圖描述法：用流程圖的方式來描述、輸入輸出、判斷、處理分別用不同的框圖表示，用箭頭表示流程的流向。非形式描述法：用自然語言，同時還使用一些程序設計語言中的語句來描述算法。類高級算法語言描述法：常采用類C或C++的所謂偽語言，具有容易編寫、閱讀和格式統一的特點。高級算法語言描述法：這是可以在計算機上運行并獲得結果的算法描述，使給定的問題能在有限的時間內被計算機執(zhí)行。12算法描述方式（續(xù)）以求兩個整數m、n（m≥n）的最大公因子為例來說明不同算法描述方法。非形式算法描述該問題的非形式算法描述為：①[求余數]以n除m，并令r為余數(0≤r＜n)；②[余數是否為0]若r=0則結束算法，n就是最大公因子；③[替換并返回a]若r≠0則m←n，n←r返回a。框圖法C語言描述intmax_common_factor(intm,intn){intr;r=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}13算法要素描述系統的組成2.控制結構—控制基本運算的執(zhí)行順序賦值選擇--條件轉移(多分枝選擇)循環(huán)語句以上三種動作語句的組合可以完成任何復雜的過程序列14賦值語句賦值語句的形式為

a=e;，其中a為變量名或數組元素，e為算術表達式或邏輯表達式。如果a和b都為變量名或數組元素，則可用記號a≒b，表示將a與b的內容進行交換。(或c=a;a=b;b=c;)15控制轉移語句

無條件轉移語句用如下形式：

goto標號條件轉移語句有以下兩種形式：

IF(C){S}

或

IF(C){S1}ELSE{S2}16循環(huán)語句WHILE語句的形式為：

while(){};do{}while();FOR語句的形式為:for(i=1;i<=end;i++){};17其他輔助語句：

break;終止整個循環(huán)continue；退出本次循環(huán)

return()語句用于結束算法的執(zhí)行

READ（或INPUT）語句用于輸入OUTPUT（或PRINT，或WRITE）語句用于輸出。

181.2計算機算法設計的基本方法1.列舉法(枚舉法)首先依據問題的部分條件確定答案的大致范圍，然后在此范圍內對所有可能的情況逐一驗證，直到全部情況驗證完。若某個情況使驗證符合問題的條件，則為本題的一個答案；若全部情況驗證完后均不符合題目的條件，則問題無解確定枚舉的集合(范圍）確定枚舉的條件和驗證方法（起止，順序，相關性，過程）優(yōu)化枚舉的條件和范圍。優(yōu)點：簡單。弱點：低效19列舉法實例求不定方程的百雞問題：設x

，y，z分別為母雞、公雞和小雞的只數。母雞每只三元、公雞每只二元、小雞兩只一元。問百元買百雞有幾種解法？寫代數方程：

x+y+z=1003x+2y+z/2=10020用列舉法寫算法就十分方便：voidBuyChicks(){intx,y,z;for(x=0,x<=100,x++)for(y=0,y<=100,y++) for(z=0,z<=100,z++){ m=x+y+z; n=3*x+2*y+0.5*z;if((m==100)&(n==100))cout<<x,y,z;};}如何優(yōu)化?21優(yōu)化后的程序：voidBuyChicks(){intx,y,z;for(x=0;x<=33;x++) //最多可以買33只母雞

for(y=0;y<=50-1.5*x;y++) //最多可買50只公雞

{ z=100-x-y; if((3*x+2*y+0.5*z)==100)cout<<x,y,z;};}222.歸納法列舉少量特殊情況，從而找出一般規(guī)律。適用于存在某種假設規(guī)律并可驗證的模型必須驗證：數學歸納法3.遞推法求解過程中的中間結果存在有規(guī)律的順序依賴關系.直至最后結果。穩(wěn)定性問題。234.遞歸--算法的自包含性自己調用自己的算法過程。將問題按規(guī)律逐層分解，直至含有解的最簡形式。按逆過程綜合出終解。直接遞歸P(P(P(……)))間接遞歸P(Q(P(……)))定義的遞歸-->過程的遞歸需要機器能力的支持效率問題24遞歸設計方法把階數較高的一個過程，轉化為階數較低同類型的過程。采用遞歸編寫程序能使程序變得非常簡單而清晰。遞歸的主要思想包括三個方面：a)定義形式是遞歸的。b)數據之間的關系（即數據結構）按遞歸定義。c)問題本身沒有明顯的遞歸結構，但用遞歸求解比用迭代求解更簡單。25遞歸設計舉例對于輸入的參數n，依次打印出自然數1至n。非遞歸解：#include<iostream>Usingnamespacestd;voidwrite(intn){intk;for(k=1;k<=n;k++)cout<<k<<endl;return;}遞歸解：#include<iostream>Usingnamespacestd;voidwrite1(intn){if(n!=0) //邊界條件，遞歸入口{write1(n-1)；//遞歸前進段cout<<n<<endl;}return; //遞歸返回段

}26遞歸設計方法一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件滿足時，遞歸前進；當邊界條件不滿足時，遞歸返回?？紤]使用遞歸算法編寫程序時，應滿足兩點：1）該問題能夠被遞歸形式描述；2）存在遞歸結束的邊界條件。遞歸的能力在于用有限的語句來定義對象的未知集合。27Hanoi塔問題XYZXYZXYZ123原始問題：Hanoi(n,X,Y,Z)Hanoi(n-1,Y,X,Z)Hanoi(n-1,X,Z,Y)nmove(X,n,Z)有三根桿子A，B，C。A桿上有N個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規(guī)則將所有圓盤移至C桿：每次只能移動一個圓盤；大盤不能疊在小盤上面。28算法描述：Hanoi(n,X,Y,Z)ifn=1thenmove(X,1,Z)elseHanoi(n-1,X,Z,Y)move(X,n,Z)Hanoi(n-1,Y,X,Z)endifreturn前進段?返回段?邊界條件?29遞推與遞歸的區(qū)別遞推：基于數據的遞歸：基于方法的一個遞推算法總可以轉換為一個遞歸算法。遞歸算法往往比非遞歸算法要付出更多的計算機資源。306.回溯法試探法無法總結出求解規(guī)律。無法列舉可能的條件和解集。逐步試探局部成功，則繼續(xù)試探。若失敗，沿原路退回若干步，改變條件和方向再試，直至找到解。八后問題31皇后問題N皇后問題自然語言描述：在n行n列的國際象棋棋盤上，若兩個皇后位于同一行、同一列、同一對角線上，則稱為它們?yōu)榛ハ喙簟?/p>

n皇后問題的解是指：

找到這n個皇后的互不攻擊的布局思考：1）如何表示棋盤、棋子和布棋？2）如何描述布棋規(guī)則？3）如何設計布棋步驟？?????32基本思路

依次為每一行確定該行皇后的合法位置安放第i行皇后時，需要在列的方向從0到n-1試探(j=0,…,n-1)在第j列安放一個皇后如果在列、主對角線、次對角線方向有其它皇后，則出現攻擊，撤消在第j列安放的皇后：如果沒有出現攻擊，在第j列安放的皇后不動

遞歸安放第i+1行皇后如果第i行不能安放皇后，則回溯到第i-1行，撤銷該行的皇后，并從其所在的下一個列(j+1)繼續(xù)試探。程序實現的要素？33皇后問題對于皇后問題來說，由于每一行、每一列和每一個對角線，都只能放一個皇后，當一個皇后放到棋盤上后，不管它放在棋盤的什么位置，它所影響的行和列方向上的棋盤位置是固定的，因此在行、列方面沒有什么信息可以利用。但在不同的位置，在對角線方向所影響的棋盤位置數則是不同的?？梢韵胂螅绻岩粋€皇后放在棋盤的某個位置后，它所影響的棋盤位置數少，那么給以后放皇后留下的余地就太大，找到解的可能性也大；反之留有余地就小，找到解的可能性也小。34思考題解的唯一性?123n12in?????解的完備性--全部解集?無解的證明?END35361.3算法的復雜度分析算法的評價算法的復雜度算法的最優(yōu)性快速算法的設計制約算法效率的要素時間空間37算法評價標準算法評價標準正確性程序不含語法錯誤對于幾組輸入數據能夠得出滿足要求的結果對于精心挑選的典型、苛刻的幾組輸入數據能夠得出滿足要求的結果----一般作為衡量標準對于一切合法的輸入數據都能產生滿足規(guī)格說明要求的結果---------很難滿足(無法枚舉)可讀性:

容易閱讀理解，模塊化，可以犧牲效率健壯性：異常處理機制高效率與低存儲量需求381.3.1算法的時間復雜度1.時間復雜度--一個算法運行時間的相對度量。一個程序的時間復雜度是指程序從開始到結束運行所需要的時間。算法執(zhí)行時間:算法執(zhí)行時間=原操作的執(zhí)行次數之和*原操作的執(zhí)行時間算法執(zhí)行所需考慮因素:與非關鍵性細節(jié)無關與執(zhí)行算法的機器速度無關與輔助環(huán)境無關時間復雜度度量方法:算法基本操作重復執(zhí)行的次數是模塊n的某一個函數f(n)。

工作量=f(n)

n：問題的規(guī)模時間復雜度表示方法：T(n)=O(f(n))39隨著模塊n的增大，算法執(zhí)行時間的增長率和f(n)增長率成正比。在計算時間復雜度時，先找出算法的基本操作，然后根據對應的各語句確定它的執(zhí)行次數，再找出T(n)的同數量級（它的同數量級有以下：1，log(2)n，n，nlog(2)n，n的平方，n的三次方，2的n次方，n!），找出后，令f(n)=該數量級，若T(n)/f(n)求極限可得到一常數c，則時間復雜度T(n)=O(f(n))時間復雜度分析40乘法運算是基本操作，因為：①核心操作，處于最深層循環(huán)；②花費時間（相對于加法）。例n階矩陣相乘的算法for(i=1;i<=n;++i)

for(j=1;j<=n;++j){

c[i][j]=0;

for(k=1;k<=n;++k)

c[i][j]+=a[i][k]*b[k][j]}乘法、加法執(zhí)行次數均為n3

時間復雜度分析舉例41按數量級遞增排列，常見的時間復雜度有：

常量階：O(1)

對數階：O(logn)

線性階：O(n)

線性對數階：

O(nlogn)

平方階：O(n2)

立方階：O(n3)

K次方階：O(nk)

指數階：O(2n)

T(n)=O(f(n))時間復雜度的表示基本操作執(zhí)行次數為n3，與整個運行時間成正比因此以n的函數作為效率衡量標準。記作：

T(n)=O(n3)

一般而言，基本操作重復執(zhí)行的次數是問題規(guī)模n的函數T(n)，當n趨于無窮大時，T(n)的數量級（價）稱為算法的漸近時間復雜度，記作：42算法的最優(yōu)性最優(yōu)性定義:執(zhí)行的基本運算相對最少。尋優(yōu)過程設計算法A，確定響應的上界W(n)[最壞]改進算法,確定響應的下界F(n)[至少]若W(n)=F(n),則已獲得最優(yōu)算法,否則繼續(xù)改進.即F(n)同時具備必要性和充分性,則算法為最優(yōu).快速算法時間復雜度最小431.3.2算法的空間復雜度空間復雜度：是指程序運行從開始到結束所需的存儲空間。執(zhí)行算法所需要的存儲空間包括：算法程序所占空間輸入數據所占空間執(zhí)行過程所需的額外空間通常以算法的空間復雜度作為算法所需存儲空間的量度?？臻g復雜度的表示：

S(n)=O(g(n))

空間復雜度也是問題規(guī)模n的函數。表示隨問題規(guī)模n的增大，算法運行所需存儲量的增長率與g(n)的增長率相同。44算法分析舉例求和的例子，intn=100;intsum=0;for(inti=1;i<=n;i++){ sum=sum+i;}時間復雜度T(n)=O(n)空間復雜度S(n)=O(1)使用函數迭代intsum(intn){ if(n==1)returnn; returnn+sum(n-1);}main(){ intn=100; intS=sum(n);}時間復雜度T(n)=O(n)空間復雜度S(n)=O(n)END45第2章基本數據結構2.1數據結構的基本概念1.什么是數據結構2.數據結構的表示46數據、數據元素、數據項和數據結構1.基本術語數據(data)--反映客觀事物的信息的集合，是信息的載體，它能夠被計算機識別、存儲和加工處理。例如數、字符。數據元素(dataelement)--集合中的個體，數據的基本單位，例如數據集合中的某個特定的數值。一個數據元素可以由多個數據項組成（字段、域、屬性）數據項—是具有獨立含義的最小數據單位。數據＞數據元素＞數據項（班級通訊錄＞個人記錄＞姓名，年齡，聯系地址）數據對象(dataobject)相同特性的數據元素的集合--數據的子集。例如，整數的數據對象是N＝{0，士1，士2，…}2.1數據結構的基本概念47數據、數據元素、數據項和數據結構數據結構(datastructure)—互相關聯的數據元素的集合，例如，向量和矩陣，圖書卡片。

數據元素的集合，記為D；在D上的一個關系，記為R。

數據結構＝（D，R）48數據類型定義：數據類型是指為一種數據結構和能夠對該數據結構進行的操作的集合

例如:整型（int）

、浮點型（float，double）、字符型（char）、指針型、空類型（void）。intj;-32768~+32767unsignedintj;

0~+65535longintj;-232~

+232-1unsignedlongintj;49C語言的數據類型

┌基本型(int)┌整型│短整型(shortint)││長整型(longint)│└無符號型(unsignedint)│┌基本類型│實型(浮點型)┌單精度(float)││

└雙精度(double)數據類型││字符型(char)│└枚舉型(enum)││┌數組類型(inta[])│構造類型│結構體類型(struct)│└共用體類型(union)│指針類型(int*pa)└空類型50數據舉例：身份證數據的管理在身份證管理應用層次的視圖數據元素：每個身份證信息是一個數據元素，包括姓名、性別、身份證號和相片等數據項數據項：姓名、性別、身份證號和相片都是數據項數據結構：身份證信息之間的關系：邏輯結構：（線性）表結構物理結構：數組操作：增加、刪除、查找數據結構的嵌套：例如：相片是一個圖象數據，具有圖象數據結構，它可以作為一個數據項嵌套在每個人的數據項中。51數據結構與算法一個算法的效率往往與數據的表示形式有著直接的關系。數據結構的選擇，對程序質量的影響極大。學習數據結構的目的也就是為了更好地進行程序設計。521.3.2

數據結構的表示

例11設數據元素的集合為D＝｛di|1＜i＜7的整數}，畫出對應于下列關系所構成的數據結構的圖形：R1＝{(d1，d3)，（d1，d7），（d4，d5），（d3，d6），（d2，d4）}R2＝{(di，dj)|i十j＝5}R3＝｛（d2，d3），（d3，d1），（d1，d4），（d4，d6），（d6，d5），（d5，d7）｝三個數據結構的圖形如下圖所示。53R1＝{(d1，d3)，（d1，d7），（d4，d5），（d3，d6），（d2，d4）}R2＝{(di，dj)|i十j＝5}R3＝｛（d2，d3），（d3，d1），（d1，d4），（d4，d6），（d6，d5），（d5，d7）｝54在數據結構的圖形表示中，沒有前件的結點稱為根結點，如圖（a）中的結點d1、d2，圖（b）中的結點d5、d6、d7，圖（C）中的結點d2；沒有后件的結點稱為終結點，如圖（a）中的d5、d6、d7，圖（b）中的d5、d6、d7，圖（c）中的d7。除了根結點與終結點以外，其余結點均稱為內部結點。圖中數據結構的圖形表示說明55數據結構四個基本的數據結構集合結構：關系集合是空集

頂點元素間無任何關系，R={}空集56線性結構和非線性結構線性結構：元素間的關系是1對1

1)有且只有一個初始節(jié)點2)最多有一個前區(qū)驅,最多有一個后繼(也可以無)3)插入或刪除一個節(jié)點后仍滿足1),2)非線性結構:元素間的關系是1對多不滿足線性結構特點的通稱為非線性結構樹型結構：一般樹、二叉樹、森林

一個結點可以有多個直接后繼（除葉子結點外），

但只有一個直接前驅（除根結點外）57圖狀結構圖狀結構：元素間的關系是多對多

一個結點可以有多個直接后繼，也可以有多個直接前驅581.數據的邏輯結構數據結構的表示包括兩個方面：一是邏輯結構的表示：二是存儲結構的表示：數據的邏輯結構：數據元素之間的邏輯關系特征從邏輯關系上描述數據，與數據的存儲無關從具體問題抽象出來的數據模型與數據元素本身的形式、內容無關分類線性結構：線性表非線性結構：樹、圖59邏輯結構舉例以班級數據為例，數據元素是學生，學生有學號、姓名和性別等數據項。學生同屬于一個班級的關系構成集合結構按學號排列的學生關系構成線性結構如果學生分組管理，班長-組長-普通學生，那么學生的上下級關系則構成層次結構學生之間的朋友關系構成一個網狀結構60例1、學生基本情況登記表。學號姓名 專業(yè)政治面藐

001 王洪 計算機黨員002孫文計算機團員003 謝軍 計算機團員004 李輝 計算機團員005 沈祥福計算機黨員006 余斌 計算機團員007 鞏力計算機團員008 孔令輝計算機團員

00100300200400600500007學號關系是一種線性結構關系邏輯結構舉例612.數據的存儲結構數據存儲結構——數據元素極其關系在計算機存儲器內的表示數據結構在計算機中的表示—為數據元素分配存儲單元將數據元素間的邏輯關系映射到存儲位置關系上依賴于程序設計語言所提供的數據類型和存儲形式1.順序存儲結構等長；等間隔邏輯上相鄰-->物理上相鄰,關系自然確定易于描述線性結構，也可存儲經過線性化處理的非線性結構主要數據類型:向量（表格存儲結構）,數組高級計算機語言以數據類型的方式提供了一個基本數據結構集的存儲和操作。影響選擇的因素：數據的訪問效率和存儲空間占用的權衡。6263順序結構數據的存取64順序存儲結構分析線性結構B＝（D，R）

D＝{a，b，c，d，e，f}R＝{(b，c),(c，d),(d，a),(a，f),（f，e）}順序存儲的示意圖（假設每一個數據元素占一個存儲單元），數據元素的存儲空間是連續(xù)的。1005b1006c1007d1008a1009f1010e65

2.鏈式存儲結構每個節(jié)點由兩部分組成:數據域,位置指示域(指針域)即可實現線性結構,又可表示非線性結構特點:可以表示任意復雜的結構存儲空間不連續(xù)存儲順序與結構順序不一致不能隨機訪問訪問效率不均等主要形式:

單鏈表、雙鏈表、多重鏈表、循環(huán)鏈表data

單元節(jié)點P66鏈式存儲示例每個結點設一指針，用以指出其后件的存儲序號。最后一個結點的指針為空，用“0”表示。第一個結點專門用一個指針（稱為頭指針，用HEAD表示）指向它。線性結構B＝（D，R）

D＝{a，b，c，d，e，f}R＝{(b，c),(c，d),(d，a),(a，f),（f，e）}data

單元節(jié)點P67數據的邏輯結構與存儲結構的關系1.數據的邏輯結構必定要有某種存儲