1、數(shù) 據(jù) 結(jié) 構(gòu)主講人：李志芳主講單位：軟件技術(shù)教研室時間：20082009第二學(xué)期第一章 緒論 知 識 點 數(shù)據(jù)結(jié)構(gòu)中常用的基本概念和術(shù)語 算法描述和分析方法 難 點 算法復(fù)雜性的分析方法 要 求 了解數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，算法的基本概念，它們對于程序設(shè)計的重要性以及相互關(guān)系 掌握算法復(fù)雜性的概念及分析方法 基本概念數(shù)據(jù)結(jié)構(gòu) 用計算機(jī)解決一個具體問題時，大致需要經(jīng)過下列幾個步驟：抽象數(shù)學(xué)模型設(shè)計數(shù)學(xué)模型編程測試、調(diào)整最終解決方法分析過程實施過程基本概念 數(shù)據(jù)結(jié)構(gòu)可以應(yīng)用于問題的整個解決過程即分析過程和實施過程。 首先分析過程中有一個步驟：數(shù)據(jù)的分析與設(shè)計，為了更好地對問題的數(shù)據(jù)進(jìn)行組織和處

2、理，常常要借助于數(shù)據(jù)結(jié)構(gòu)的思想來完成。 例：汽車的故障診斷系統(tǒng) 餐飲管理系統(tǒng) 人機(jī)對弈問題 其次在具體的實施過程當(dāng)中，經(jīng)常需要對數(shù)據(jù)進(jìn)行處理，在數(shù)據(jù)結(jié)構(gòu)課程當(dāng)中，給出了各種數(shù)據(jù)的各種處理方法。 基本概念 數(shù)據(jù)(Data)：一切能夠由計算機(jī)接受和處理的對象 數(shù)據(jù)元素(Data element)：是數(shù)據(jù)的基本單位，在程序中作為一個整體加以考慮和處理。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。 數(shù)據(jù)項(Data item)：是數(shù)據(jù)的不可分割的最小單位，在有些場合下，數(shù)據(jù)項又稱為字段或域。 字段（域）：字段是對元素詳細(xì)地描述，是指元素的具體信息。 基本概念 數(shù)據(jù)結(jié)構(gòu)(Data structure)：數(shù)據(jù)之間的

3、相互關(guān)系，即數(shù)據(jù)的組織形式。 數(shù)據(jù)結(jié)構(gòu)根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特征，通常有下列4類基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖或網(wǎng)狀結(jié)構(gòu)，通常這幾類結(jié)構(gòu)稱為邏輯結(jié)構(gòu)。 研究數(shù)據(jù)結(jié)構(gòu)，是指研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系。 數(shù)據(jù)的物理結(jié)構(gòu)：數(shù)據(jù)元素在計算機(jī)存儲器中是如何存儲的，所以又叫做存儲結(jié)構(gòu)。 運算：解決問題的算法?；靖拍?由此可見，對一種數(shù)據(jù)結(jié)構(gòu)，需要涉及到其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運算三個方面，也就是說，對每種結(jié)構(gòu)都要注意三方面的聯(lián)系。 由于不同的存儲形式對算法的時間性能、空間性能等的影響比較大，即是具有相同的存儲結(jié)構(gòu)，也可能會存在不同的算法實現(xiàn)，所以需要對

4、算法進(jìn)行分析?；靖拍?算法(Algorithm)：對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。 特征：1）有窮性 2）確定性 3）可行性 4）輸入 5）輸出 算法是一個有窮的規(guī)則序列，這些規(guī)則決定了解決某一特定問題的一系列運算。 由此問題相關(guān)的一定輸入，計算機(jī)依照這些規(guī)則進(jìn)行計算和處理，經(jīng)過有限的計算步驟后能得到一定的輸出。 算法的評價原則一個好的算法應(yīng)考慮達(dá)到以下目標(biāo)：正確性：算法應(yīng)能正確地實現(xiàn)處理要求 。易讀性：有助于對算法的理解，便于糾正和擴(kuò)充 。簡單性：使證明其正確性比較容易，對算法進(jìn)行修改也比較方便。健壯性：算法應(yīng)該具有糾錯的能力，當(dāng)輸入非法

5、數(shù)據(jù)時，算法應(yīng)適當(dāng)做出反應(yīng)或進(jìn)行處理。高效率：達(dá)到所需的時、空性能。 算法效率的度量算法的復(fù)雜性包括時間復(fù)雜性（所需運算時間）和空間復(fù)雜性（所占存儲空間），重點是時間復(fù)雜性 。 一個算法所需的運算時間通常與所解決問題的規(guī)模大小、書寫程序的語言等有關(guān)。 算法的時間的度量是以問題當(dāng)中的原操作的重復(fù)執(zhí)行的次數(shù)來計算的。 用n 表示問題規(guī)模的量 ，算法中基本操作執(zhí)行的次數(shù)是問題規(guī)模的某個函數(shù)f(n)，算法的時間度量記作： T( n ) = O( f( n ) ) 表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的時間復(fù)雜度。 (a) +x;s=0 (b) for(i=1;i

6、=n,+i) +x; s+=x; (c) for(j=1;j=n;+j) for(k=1;k=n;+k) +x; s+=x;以上三個程序段含操作“x增1”的語句的執(zhí)行次數(shù)分別為1、n、n2則這3個程序段的時間復(fù)雜度分別為 O(1)、O(n)、 O(n2) ，分別稱為常量階、線性階和平方階。 算法的時間復(fù)雜度考慮的只是對于問題規(guī)模n的增長率，在難以精確計算基本操作次數(shù)的情況下，只需要求出他關(guān)于n的增長率即可。 for(I=2;I=n;+i) for(j=2;j=i-1;+j) +x; aij=x T(n)=O(n2)算法效率的度量當(dāng)T(n)為多項式時,可只取其最高次冪項,且它的系數(shù)也可略去不寫。

7、一般地，對于足夠大的n，常用的時間復(fù)雜性存在以下順序： O(1) O(logn) O(n) O(n*logn) O(n2) O(n3)O(2n)O(3n)O(n!) 其中,O(1)為常數(shù)數(shù)量級,即算法的時間復(fù)雜性與輸入規(guī)模n無關(guān)。算法效率的度量算法的運行時間往往還與具體輸入的數(shù)據(jù)有關(guān)，通常用以下兩種方法來確定一個算法的運算時間：1. 平均時間復(fù)雜性：研究同樣的n值時各種可能的輸入，取它們運算時間的平均值。2. 最壞時間復(fù)雜性：研究各種輸入中運算最慢的一種情況下的運算時間。 算法效率的度量算法的描述 本書將采用類C語言描述算法 類C語言是標(biāo)準(zhǔn)C語言的簡化 ，與標(biāo)準(zhǔn)C語言的主要區(qū)別如下：1. 所有

8、算法都以如下所示的函數(shù)形式表示： 函數(shù)類型 函數(shù)名（參數(shù)表） 語句序列 類C語言的形參書寫比標(biāo)準(zhǔn)C語言簡單，如，int fun(int a,int b,int c)可以簡單寫成int fun(int a,b,c)算法的描述2. 局部量的說明可以省略，必要時對其作用給予注釋 。3. 不含go to語句，增加一個出錯處理語句error(字符串)，其功能是終止算法的執(zhí)行并給出表示出錯信息的字符串。4. 輸入/輸出語句有： 輸入語句 scanf(格式串),變量1，變量N）； 輸出語句 printf(格式串),變量1，變量N）； 通常省略格式串 。 例題計算下面交換i和j內(nèi)容程序段的時間復(fù)雜性。 tem

9、p=i; i=j; j=temp; 解：以上三條單個語句均執(zhí)行1次，因此算法的時間復(fù)雜度為常數(shù)階,記作T(n)=O(1).計算下面求累加和程序段的時間復(fù)雜性 （1） sum=0； （一次） （2） for(i=1;i=n;i+) （n次 ） （3） for(j=1;j=n;j+) （n2次 ） （4） sum+； （n2次 ） 解：T(n)=2n2+n+1 =O(n2) 分析下列算法的時間復(fù)雜性: 1sum=0; for (i=1;i=n;i+) sum=sum+i; 2i=1; while(i=n) i=i*10;3sum=0; for(i=0;in;i+) for(j=0;jn;j+) sum=sum+Arrayij; 作業(yè)