軟件技術(shù)基礎(chǔ)

主講教師：朱海華機(jī)電學(xué)院15B426Email:zhuhh@軟件技術(shù)基礎(chǔ)1緒

論工程軟件概述計(jì)算機(jī)三大應(yīng)用領(lǐng)域：科學(xué)計(jì)算、信息處理、過程控制。隨著信息技術(shù)的普及，各類計(jì)算機(jī)軟硬件系統(tǒng)在工程應(yīng)用領(lǐng)域的廣泛應(yīng)用。工程軟件在實(shí)際工程應(yīng)用中占有相當(dāng)重要的地位。工程軟件主要應(yīng)用領(lǐng)域包括：

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

工程事務(wù)處理：分為事務(wù)型系統(tǒng)、管理型系統(tǒng)、決策型系統(tǒng)。

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

論工程軟件的基本元素工程軟件的三個(gè)基本要素是數(shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)和算法。

工程數(shù)據(jù)是工程軟件系統(tǒng)的處理對(duì)象。

數(shù)據(jù)結(jié)構(gòu)是對(duì)工程數(shù)據(jù)的組織。組織結(jié)構(gòu)良好的數(shù)據(jù)不僅可以提高工程數(shù)據(jù)處理的效率，而且數(shù)據(jù)的可靠性也能得到有效的保障。

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

數(shù)據(jù)結(jié)構(gòu)+算法＝程序然而,僅有這些還不夠,應(yīng)是:

數(shù)據(jù)結(jié)構(gòu)＋算法＋程序設(shè)計(jì)方法＋語言工具和環(huán)境＝程序程序設(shè)計(jì)算法設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)行為特性的設(shè)計(jì)結(jié)構(gòu)特性的設(shè)計(jì)算法的效率通常與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有直接關(guān)系4第1章算法1.1算法的基本概念1.2算法設(shè)計(jì)基本方法1.3算法的復(fù)雜度分析51.1算法的基本概念概念

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

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

一組嚴(yán)謹(jǐn)定義運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效且明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止并獲得預(yù)期的結(jié)果。91.1.2算法的基本要素對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作針對(duì)算法涉及的數(shù)據(jù)信息最基本的動(dòng)作和步驟單元算法的控制結(jié)構(gòu)針對(duì)算法的過程步驟控制基本操作和步驟的組合順序10算法要素描述系統(tǒng)的組成1.運(yùn)算和操作的描述標(biāo)識(shí)符運(yùn)算符:算術(shù)運(yùn)算符：+，-，*，/等關(guān)系運(yùn)算符：>，<，==，!=，＞=。＜=邏輯運(yùn)算符：&&(邏輯與)，！(邏輯非)，||(邏輯或)

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

a=e;，其中a為變量名或數(shù)組元素，e為算術(shù)表達(dá)式或邏輯表達(dá)式。如果a和b都為變量名或數(shù)組元素，則可用記號(hào)a≒b，表示將a與b的內(nèi)容進(jìn)行交換。(或c=a;a=b;b=c;)15控制轉(zhuǎn)移語句

無條件轉(zhuǎn)移語句用如下形式：

goto標(biāo)號(hào)條件轉(zhuǎn)移語句有以下兩種形式：

IF(C){S}

或

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

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

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

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

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

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

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

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ī)律。適用于存在某種假設(shè)規(guī)律并可驗(yàn)證的模型必須驗(yàn)證：數(shù)學(xué)歸納法3.遞推法求解過程中的中間結(jié)果存在有規(guī)律的順序依賴關(guān)系.直至最后結(jié)果。穩(wěn)定性問題。234.遞歸--算法的自包含性自己調(diào)用自己的算法過程。將問題按規(guī)律逐層分解，直至含有解的最簡形式。按逆過程綜合出終解。直接遞歸P(P(P(……)))間接遞歸P(Q(P(……)))定義的遞歸-->過程的遞歸需要機(jī)器能力的支持效率問題24遞歸設(shè)計(jì)方法把階數(shù)較高的一個(gè)過程，轉(zhuǎn)化為階數(shù)較低同類型的過程。采用遞歸編寫程序能使程序變得非常簡單而清晰。遞歸的主要思想包括三個(gè)方面：a)定義形式是遞歸的。b)數(shù)據(jù)之間的關(guān)系（即數(shù)據(jù)結(jié)構(gòu)）按遞歸定義。c)問題本身沒有明顯的遞歸結(jié)構(gòu)，但用遞歸求解比用迭代求解更簡單。25遞歸設(shè)計(jì)舉例對(duì)于輸入的參數(shù)n，依次打印出自然數(shù)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)；//遞歸前進(jìn)段cout<<n<<endl;}return; //遞歸返回段

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

n皇后問題的解是指：

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

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

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

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

工作量=f(n)

n：問題的規(guī)模時(shí)間復(fù)雜度表示方法：T(n)=O(f(n))39隨著模塊n的增大，算法執(zhí)行時(shí)間的增長率和f(n)增長率成正比。在計(jì)算時(shí)間復(fù)雜度時(shí)，先找出算法的基本操作，然后根據(jù)對(duì)應(yīng)的各語句確定它的執(zhí)行次數(shù)，再找出T(n)的同數(shù)量級(jí)（它的同數(shù)量級(jí)有以下：1，log(2)n，n，nlog(2)n，n的平方，n的三次方，2的n次方，n!），找出后，令f(n)=該數(shù)量級(jí)，若T(n)/f(n)求極限可得到一常數(shù)c，則時(shí)間復(fù)雜度T(n)=O(f(n))時(shí)間復(fù)雜度分析40乘法運(yùn)算是基本操作，因?yàn)椋孩俸诵牟僮?，處于最深層循環(huán)；②花費(fèi)時(shí)間（相對(duì)于加法）。例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í)行次數(shù)均為n3

時(shí)間復(fù)雜度分析舉例41按數(shù)量級(jí)遞增排列，常見的時(shí)間復(fù)雜度有：

常量階：O(1)

對(duì)數(shù)階：O(logn)

線性階：O(n)

線性對(duì)數(shù)階：

O(nlogn)

平方階：O(n2)

立方階：O(n3)

K次方階：O(nk)

指數(shù)階：O(2n)

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

T(n)=O(n3)

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

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

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

數(shù)據(jù)元素的集合，記為D；在D上的一個(gè)關(guān)系，記為R。

數(shù)據(jù)結(jié)構(gòu)＝（D，R）48數(shù)據(jù)類型定義：數(shù)據(jù)類型是指為一種數(shù)據(jù)結(jié)構(gòu)和能夠?qū)υ摂?shù)據(jù)結(jié)構(gòu)進(jìn)行的操作的集合

例如:整型（int）

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

0~+65535longintj;-232~

+232-1unsignedlongintj;49C語言的數(shù)據(jù)類型

┌基本型(int)┌整型│短整型(shortint)││長整型(longint)│└無符號(hào)型(unsignedint)│┌基本類型│實(shí)型(浮點(diǎn)型)┌單精度(float)││

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

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

例11設(shè)數(shù)據(jù)元素的集合為D＝｛di|1＜i＜7的整數(shù)}，畫出對(duì)應(yīng)于下列關(guān)系所構(gòu)成的數(shù)據(jù)結(jié)構(gòu)的圖形：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）｝三個(gè)數(shù)據(jù)結(jié)構(gòu)的圖形如下圖所示。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在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)，如圖（a）中的結(jié)點(diǎn)d1、d2，圖（b）中的結(jié)點(diǎn)d5、d6、d7，圖（C）中的結(jié)點(diǎn)d2；沒有后件的結(jié)點(diǎn)稱為終結(jié)點(diǎn)，如圖（a）中的d5、d6、d7，圖（b）中的d5、d6、d7，圖（c）中的d7。除了根結(jié)點(diǎn)與終結(jié)點(diǎn)以外，其余結(jié)點(diǎn)均稱為內(nèi)部結(jié)點(diǎn)。圖中數(shù)據(jù)結(jié)構(gòu)的圖形表示說明55數(shù)據(jù)結(jié)構(gòu)四個(gè)基本的數(shù)據(jù)結(jié)構(gòu)集合結(jié)構(gòu)：關(guān)系集合是空集

頂點(diǎn)元素間無任何關(guān)系，R={}空集56線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)：元素間的關(guān)系是1對(duì)1

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

一個(gè)結(jié)點(diǎn)可以有多個(gè)直接后繼（除葉子結(jié)點(diǎn)外），

但只有一個(gè)直接前驅(qū)（除根結(jié)點(diǎn)外）57圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)：元素間的關(guān)系是多對(duì)多

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

001 王洪 計(jì)算機(jī)黨員002孫文計(jì)算機(jī)團(tuán)員003 謝軍 計(jì)算機(jī)團(tuán)員004 李輝 計(jì)算機(jī)團(tuán)員005 沈祥福計(jì)算機(jī)黨員006 余斌 計(jì)算機(jī)團(tuán)員007 鞏力計(jì)算機(jī)團(tuán)員008 孔令輝計(jì)算機(jī)團(tuán)員

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

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

2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)每個(gè)節(jié)點(diǎn)由兩部分組成:數(shù)據(jù)域,位置指示域(指針域)即可實(shí)現(xiàn)線性結(jié)構(gòu),又可表示非線性結(jié)構(gòu)特點(diǎn):可以表示任意復(fù)雜的結(jié)構(gòu)存儲(chǔ)空間不連續(xù)存儲(chǔ)順序與結(jié)構(gòu)順序不一致不能隨機(jī)訪問訪問效率不均等主要形式:

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

單元節(jié)點(diǎn)P66鏈?zhǔn)酱鎯?chǔ)示例每個(gè)結(jié)點(diǎn)設(shè)一指針，用以指出其后件的存儲(chǔ)序號(hào)。最后一個(gè)結(jié)點(diǎn)的指針為空，用“0”表示。第一個(gè)結(jié)點(diǎn)專門用一個(gè)指針（稱為頭指針，用HEAD表示）指向它。線性結(jié)構(gòu)B＝（D，R）

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

單元節(jié)點(diǎn)P67數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系1.數(shù)據(jù)的邏輯結(jié)構(gòu)必定要有某種存儲(chǔ)