數(shù)據(jù)結(jié)構(gòu)緒論課件(與“算法”有關(guān)文檔共29張)

第一章緒論知識(shí)點(diǎn)數(shù)據(jù)結(jié)構(gòu)中常用的基本概念和術(shù)語(yǔ)算法描述和分析方法難點(diǎn)

算法復(fù)雜性的分析方法要求

了解數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，算法的基本概念，它們對(duì)于程序設(shè)計(jì)的重要性以及相互關(guān)系掌握算法復(fù)雜性的概念及分析方法第1頁(yè)，共29頁(yè)。第一章目錄1.1基本概念1.2算法的設(shè)計(jì)描述1.3算法的性能分析1.4應(yīng)用舉例及分析小結(jié)

習(xí)題與練習(xí)第2頁(yè)，共29頁(yè)。一個(gè)算法有下列重要的特性：一般地，對(duì)于足夠大的n，常用的時(shí){t=a[i];a[i]=a[j];a[j]=t}(3n2次）解：以上三條單個(gè)語(yǔ)句均執(zhí)行1次，掌握算法復(fù)雜性的概念及分析方法由此問(wèn)題相關(guān)的一定輸入，計(jì)算機(jī)步驟的一種描述。4應(yīng)用舉例及分析規(guī)則決定了解決某一特定問(wèn)題的一E2：[余數(shù)為0？]若R=0，則算法結(jié)束，N即為答案。類C與標(biāo)準(zhǔn)C的主要區(qū)別(續(xù))算法是一個(gè)有窮的規(guī)則序列，這些輸出語(yǔ)句printf([格式串]),變量1，…，變量N）；{t=a[i];a[i]=a[j];a[j]=t}(3n2次）的字頭，f(n)為函數(shù)形式，如T(n)=O(n2)。}第一章緒論該課程是1968年由美國(guó)科學(xué)家Knuth首先提出的，他在《計(jì)算機(jī)程序設(shè)計(jì)技巧》第1卷和第3卷中有詳細(xì)的描述。它是計(jì)算機(jī)專業(yè)的基礎(chǔ)課程，是程序設(shè)計(jì)的基礎(chǔ)。瑞士科學(xué)家Wirth在其著作中這樣描述：

算法+數(shù)據(jù)結(jié)構(gòu)=程序，由此可見(jiàn)數(shù)據(jù)結(jié)構(gòu)的重要性。第3頁(yè)，共29頁(yè)。1.1基本概念例1：計(jì)算機(jī)管理圖書(shū)目錄問(wèn)題。第4頁(yè)，共29頁(yè)。1.1基本概念例2：人機(jī)對(duì)弈問(wèn)題第5頁(yè)，共29頁(yè)。1.1基本概念通過(guò)以上例子可以看出，這些問(wèn)題不能用一個(gè)數(shù)學(xué)公式描述，而是要用書(shū)目表，對(duì)弈樹(shù)等帶結(jié)構(gòu)的數(shù)據(jù)來(lái)描述。數(shù)據(jù)結(jié)構(gòu)要解決的問(wèn)題：分析實(shí)際問(wèn)題，從中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型；設(shè)計(jì)一個(gè)解決此問(wèn)題的算法。第6頁(yè)，共29頁(yè)。1.1基本概念數(shù)據(jù)(Data)：一切能夠由計(jì)算機(jī)接受和處理的對(duì)象。數(shù)據(jù)元素(Dataelement)：是數(shù)據(jù)的基本單位，在程序中作為一個(gè)整體加以考慮和處理。數(shù)據(jù)項(xiàng)(Dataitem)：是數(shù)據(jù)的不可分割的最小單位，在有些場(chǎng)合下，數(shù)據(jù)項(xiàng)又稱為字段或域。第7頁(yè)，共29頁(yè)。1.1基本概念數(shù)據(jù)結(jié)構(gòu)(Datastructure)：數(shù)據(jù)之間的相互關(guān)系，包含3個(gè)方面的問(wèn)題：1。數(shù)據(jù)元素之間的邏輯關(guān)系，即邏輯結(jié)構(gòu)2。數(shù)據(jù)在機(jī)內(nèi)的存儲(chǔ)形式，即存儲(chǔ)結(jié)構(gòu)或物理結(jié)構(gòu)。3在數(shù)據(jù)上進(jìn)行的運(yùn)算，即對(duì)數(shù)據(jù)的操作。第8頁(yè)，共29頁(yè)。1.1基本概念數(shù)據(jù)邏輯結(jié)構(gòu)又分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性的：線性表，對(duì)列，棧等非線性的：樹(shù)，圖等第9頁(yè)，共29頁(yè)。1.1基本概念數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)有：順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)索引存儲(chǔ)散列存儲(chǔ)第10頁(yè)，共29頁(yè)。能用一個(gè)數(shù)學(xué)公式描述，而是要用書(shū)的操作。2算法的設(shè)計(jì)與描述sum=sum+i;由此問(wèn)題相關(guān)的一定輸入，計(jì)算機(jī)非線性的：樹(shù)，圖等輸入/輸出語(yǔ)句有：{一般地，對(duì)于足夠大的n，常用的時(shí)該課程是1968年由美國(guó)科學(xué)家Knuth首（1）sum=0;(1次）類C與標(biāo)準(zhǔn)C的主要區(qū)別(續(xù))1.1基本概念算法(Algorithm)：對(duì)特定問(wèn)題求解步驟的一種描述。算法是一個(gè)有窮的規(guī)則序列，這些規(guī)則決定了解決某一特定問(wèn)題的一系列運(yùn)算。由此問(wèn)題相關(guān)的一定輸入，計(jì)算機(jī)依照這些規(guī)則進(jìn)行計(jì)算和處理，經(jīng)過(guò)有限的計(jì)算步驟后能得到一定的輸出。返回第11頁(yè)，共29頁(yè)。1.2算法的設(shè)計(jì)與描述算法的定義算法是對(duì)特定問(wèn)題求解的一種描述，是有窮的規(guī)則序列，這些規(guī)則決定了解決該問(wèn)題的一系列運(yùn)算，是指令的有窮序列。例：算法E（歐幾里得算法）：給定兩個(gè)正整數(shù)M和N，求它們的最大公因子，即能同時(shí)整除M和N的最大正整數(shù)。E1：[求余數(shù)]以N除M，并令R為所得的余數(shù)。E2：[余數(shù)為0？]若R=0，則算法結(jié)束，N即為答案。E3：[互換]置M←N，N←R，并返回E1。第12頁(yè)，共29頁(yè)。1.2算法的設(shè)計(jì)與描述一個(gè)算法有下列重要的特性：有窮性確定性可行性輸入輸出

第13頁(yè)，共29頁(yè)。1.2算法的設(shè)計(jì)與描述本書(shū)將采用類C語(yǔ)言描述算法類C語(yǔ)言是標(biāo)準(zhǔn)C語(yǔ)言的簡(jiǎn)化，與標(biāo)準(zhǔn)C語(yǔ)言的主要區(qū)別如下：1.所有算法都以如下所示的函數(shù)形式表示：函數(shù)類型函數(shù)名（參數(shù)表）{語(yǔ)句序列

}類C語(yǔ)言的形參書(shū)寫(xiě)比標(biāo)準(zhǔn)C語(yǔ)言簡(jiǎn)單，如，intxyz(inta,intb,intc)可以簡(jiǎn)單寫(xiě)成intxyz(inta,b,c)第14頁(yè)，共29頁(yè)。類C與標(biāo)準(zhǔn)C的主要區(qū)別(續(xù))2.局部量的說(shuō)明可以省略，必要時(shí)對(duì)其作用給予注釋。3.不含goto語(yǔ)句，增加一個(gè)出錯(cuò)處理語(yǔ)句error(字符串)，其功能是終止算法的執(zhí)行并給出表示出錯(cuò)信息的字符串。4.輸入/輸出語(yǔ)句有：輸入語(yǔ)句scanf([格式串]),變量1，…，變量N）；輸出語(yǔ)句printf([格式串]),變量1，…，變量N）；通常省略格式串。返回第15頁(yè)，共29頁(yè)。1.3算法的性能分析正確性：算法應(yīng)能正確地實(shí)現(xiàn)處理要求。易讀性：有助于對(duì)算法的理解，便于糾正和擴(kuò)充。簡(jiǎn)單性：使證明其正確性比較容易，對(duì)算法進(jìn)行修改也比較方便。高效率：達(dá)到所需的時(shí)、空性能。第16頁(yè)，共29頁(yè)。1.3.1評(píng)價(jià)算法的一般原則正確性：算法應(yīng)能正確地實(shí)現(xiàn)處理要求。易讀性：有助于對(duì)算法的理解，便于糾正和擴(kuò)充。簡(jiǎn)單性：使證明其正確性比較容易，對(duì)算法進(jìn)行修改也比較方便。高效率：達(dá)到所需的時(shí)、空性能。第17頁(yè)，共29頁(yè)。1.3.2算法復(fù)雜性的分析算法的復(fù)雜性包括時(shí)間復(fù)雜性（所需運(yùn)算時(shí)間）和空間復(fù)雜性（所占存儲(chǔ)空間），重點(diǎn)是時(shí)間復(fù)雜性。一個(gè)算法所需的運(yùn)算時(shí)間通常與所解決問(wèn)題的規(guī)模大小有關(guān)。用n表示問(wèn)題規(guī)模的量，把算法運(yùn)行所需的時(shí)間T表示為n的函數(shù)，記為T(mén)(n)。不同的T(n)算法，當(dāng)n增長(zhǎng)時(shí)，運(yùn)算時(shí)間增長(zhǎng)的快慢很不相同。第18頁(yè)，共29頁(yè)。一個(gè)算法所需的執(zhí)行時(shí)間就是該算法中所有語(yǔ)句執(zhí)行次數(shù)之和。漸進(jìn)時(shí)間復(fù)雜性：當(dāng)n逐漸增大時(shí)T(n)的極限情況，一般簡(jiǎn)稱為時(shí)間復(fù)雜性。時(shí)間復(fù)雜性常用數(shù)量級(jí)的形式來(lái)表示，記作T(n)=O(f(n))。其中，大寫(xiě)字母O為Order(數(shù)量級(jí))的字頭，f(n)為函數(shù)形式，如T(n)=O(n2)。第19頁(yè)，共29頁(yè)。當(dāng)T(n)為多項(xiàng)式時(shí),可只取其最高次冪項(xiàng),且它的系數(shù)也可略去不寫(xiě)。一般地，對(duì)于足夠大的n，常用的時(shí)間復(fù)雜性存在以下順序：O(1)<O(logn)<O(n)<O(n*logn)<O(n2)<O(n3)…<O(2n)<O(3n)<…<O(n!)其中,O(1)為常數(shù)數(shù)量級(jí),即算法的時(shí)間復(fù)雜性與輸入規(guī)模n無(wú)關(guān)。第20頁(yè)，共29頁(yè)。算法的運(yùn)行時(shí)間往往還與具體輸入的數(shù)據(jù)有關(guān)，通常用以下兩種方法來(lái)確定一個(gè)算法的運(yùn)算時(shí)間：1.平均時(shí)間復(fù)雜性：研究同樣的n值時(shí)各種可能的輸入，取它們運(yùn)算時(shí)間的平均值。2.最壞時(shí)間復(fù)雜性：研究各種輸入中運(yùn)算最慢的一種情況下的運(yùn)算時(shí)間。返回第21頁(yè)，共29頁(yè)。1.3.2算法復(fù)雜性的分析空間復(fù)雜度的計(jì)算一維數(shù)組a[n]：空間復(fù)雜度為o(n)二維數(shù)組a[m][n]：空間復(fù)雜度為o(m*n)

第22頁(yè)，共29頁(yè)。1.4應(yīng)用舉例與分析：計(jì)算下面交換i和j內(nèi)容程序段的時(shí)間復(fù)雜性。temp=i;i=j;j=temp;解：以上三條單個(gè)語(yǔ)句均執(zhí)行1次，該程序段的執(zhí)行時(shí)間是一個(gè)與問(wèn)題n無(wú)關(guān)的常數(shù)，因此，算法的時(shí)間復(fù)雜度為常數(shù)階,記作T(n)=O(1).第23頁(yè)，共29頁(yè)。例1.2計(jì)算下面求累加和程序段的時(shí)間復(fù)雜性（1）sum=0;(1次）（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)返第24頁(yè)，共29頁(yè)。計(jì)算下面求累加和程序段的時(shí)間復(fù)雜性

for(i=1;i<n;i++)(n次）for(i=1;i<=n;i++)（n*n次）ifa[j]>a[i](n*n次）{t=a[i];a[i]=a[j];a[j]=t}(3n2次）

解：T(n)=3n2+n=O(n2)第25頁(yè)，共29頁(yè)。小結(jié)本章介紹了貫穿全書(shū)的基本概念和基本思想。數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu)算法算法的時(shí)間復(fù)雜性返回第26頁(yè)，共29頁(yè)。習(xí)題與練習(xí)一、名詞解釋數(shù)據(jù)數(shù)據(jù)項(xiàng)數(shù)據(jù)元素?cái)?shù)據(jù)結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu)數(shù)據(jù)物理結(jié)構(gòu)算法算法的時(shí)間復(fù)雜性有關(guān)時(shí)間復(fù)雜度的幾個(gè)常用量二、簡(jiǎn)答1.算法分析的目的是什么？2.什么是算法的最壞和平均時(shí)間復(fù)雜性？第27頁(yè)，共29頁(yè)。三、分析下列算法的時(shí)間復(fù)雜性:

1．sum=0;for(i=1;i<=n;i++)