數(shù)據(jù)結(jié)構(gòu)與算法 課件 第一章緒論

全國高等教育自學(xué)考試指定教材

計算機應(yīng)用專業(yè)（本科段）數(shù)據(jù)結(jié)構(gòu)與算法第一章緒論學(xué)習(xí)目標了解數(shù)據(jù)結(jié)構(gòu)在計算機應(yīng)用領(lǐng)域中的作用掌握數(shù)據(jù)結(jié)構(gòu)中的基本概念和術(shù)語，了解4類基本的數(shù)據(jù)結(jié)構(gòu)，理解邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的含義及相互關(guān)系，了解數(shù)據(jù)結(jié)構(gòu)的4種基本存儲方法掌握抽象數(shù)據(jù)類型的表示與描述，能夠用抽象數(shù)據(jù)類型表示實際問題掌握算法的基本概念及重要特性，能夠使用類C語言描述算法掌握算法評估和復(fù)雜性度量的基本概念，能夠?qū)唵嗡惴ㄟM行復(fù)雜性評估理解算法的基本設(shè)計策略的特點，使用基本的算法策略實現(xiàn)簡單程序本章主要內(nèi)容基本概念和術(shù)語12算法和算法分析3算法設(shè)計策略簡介數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法是計算機專業(yè)的必修課程之一，在課程體系中占據(jù)非常重要的地位，起著承上啟下的作用，是學(xué)習(xí)其他計算機專業(yè)課程的基礎(chǔ)本章將介紹數(shù)據(jù)結(jié)構(gòu)的基本概念，還將介紹算法及其特性，介紹時間、空間復(fù)雜度的概念，在此基礎(chǔ)上，介紹對算法進行復(fù)雜度評估的基本方法第一節(jié)

基本概念和術(shù)語需求推動技術(shù)的發(fā)展，程序設(shè)計語言內(nèi)置的數(shù)據(jù)類型越來越多樣，提供的處理手段也越來越方便快捷當(dāng)需要方便地處理眾多同類型的數(shù)據(jù)時，出現(xiàn)了數(shù)組，“結(jié)構(gòu)”的雛形顯現(xiàn)了數(shù)組——例如，可以表示多個同類型的數(shù)據(jù)二元組——例如，可以表示復(fù)數(shù)記錄——例如，可以表示學(xué)生信息經(jīng)典著作數(shù)據(jù)結(jié)構(gòu)作為獨立的一門課程已經(jīng)有很多年了世界著名的計算機科學(xué)家DonaldE.Knuth教授的巨著《計算機程序設(shè)計藝術(shù)》著名的計算機科學(xué)家N.Wirth編寫的《算法+數(shù)據(jù)結(jié)構(gòu)=程序》

基本概念和術(shù)語

20世紀80年代以后出現(xiàn)了抽象數(shù)據(jù)類型概念數(shù)據(jù)對數(shù)據(jù)進行操作的定義但不涉及操作的具體實現(xiàn)數(shù)據(jù)是指所有能輸入計算機并被計算機程序處理的符號的集合數(shù)據(jù)是各種各樣的復(fù)雜的數(shù)據(jù)往往由簡單的數(shù)據(jù)構(gòu)成構(gòu)成數(shù)據(jù)的基本單位稱為數(shù)據(jù)元素數(shù)據(jù)元素還可以細分為數(shù)據(jù)項

學(xué)生信息示例——“線性”的關(guān)系某班30名同學(xué)的基本信息學(xué)號姓名性別出生日期籍貫M2022103001王義平男2004.11.22山東M2022103002陸東男2004.02.05河南M2022103003李曉敏女2005.01.15江蘇┇┇┇┇┇M2022103030楊志強男2004.10.30陜西章節(jié)目錄示例——“上下級”的關(guān)系“結(jié)構(gòu)”是什么數(shù)據(jù)元素之間的相互關(guān)系構(gòu)成結(jié)構(gòu)，帶有結(jié)構(gòu)特性的數(shù)據(jù)元素集合構(gòu)成數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關(guān)系物理結(jié)構(gòu)。指數(shù)據(jù)結(jié)構(gòu)在計算機中的表示及存儲方式數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯上描述數(shù)據(jù)，表明數(shù)據(jù)元素之間的關(guān)系是什么樣的，這與數(shù)據(jù)的存儲方式無關(guān)，既獨立于計算機，也獨立于程序設(shè)計語言數(shù)據(jù)的最小不可分割的單位是數(shù)據(jù)項邏輯上相關(guān)的、具有物理意義的若干數(shù)據(jù)項構(gòu)成一個數(shù)據(jù)元素數(shù)據(jù)元素作為一個完整的對象（整體）是構(gòu)成數(shù)據(jù)的基本單位

基本的數(shù)據(jù)結(jié)構(gòu)基本的數(shù)據(jù)結(jié)構(gòu)包括4類集合線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu)示意圖

集合線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)常用的存儲方法

順序存儲方法鏈式存儲方法索引存儲方法散列存儲方法例1-3下列關(guān)于順序存儲結(jié)構(gòu)與鏈式存儲結(jié)構(gòu)的敘述中，正確的是（A）。A．順序存儲結(jié)構(gòu)的存儲空間是連續(xù)的，鏈式存儲結(jié)構(gòu)的存儲空間不一定連續(xù)B．順序存儲結(jié)構(gòu)只用于線性結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)只用于非線性結(jié)構(gòu)C．順序存儲結(jié)構(gòu)一定比鏈式存儲結(jié)構(gòu)節(jié)省存儲空間D．鏈式存儲結(jié)構(gòu)一定比順序存儲結(jié)構(gòu)節(jié)省存儲空間抽象數(shù)據(jù)類型除了程序設(shè)計語言中提供的基本類型外，還可以定義抽象意義下的類型，并為該類型定義一組相關(guān)的操作。這樣定義的數(shù)據(jù)類型稱為抽象數(shù)據(jù)類型（AbstractDataType，ADT）抽象數(shù)據(jù)類型的定義包括類型的名字及對各個操作的刻畫，也就是要明確“做什么”對于每個操作，要規(guī)定操作的名字、操作執(zhí)行的前提條件、輸入和輸出分別是什么等等。每個操作通常表示為一個函數(shù)或是方法定義抽象數(shù)據(jù)類型Triangle

第二節(jié)

算法和算法分析算法的概念在計算機科學(xué)與技術(shù)領(lǐng)域幾乎無處不在算法的設(shè)計與實現(xiàn)往往處于核心地位算法的思想是計算機程序的靈魂算法規(guī)定的流程決定著程序的執(zhí)行步驟算法的基本概念算法（Algorithm）概念的出現(xiàn)與計算機及程序設(shè)計無關(guān)使用輾轉(zhuǎn)相除法求兩個正整數(shù)最大公因子的歐幾里得（Euclid）算法，早在2300多年前就提出了，這是目前已知的最古老的算法算法定義定義1-1算法是一個由若干確定的（無二義性的）、可執(zhí)行的步驟組成的肯定能夠終止的有序步驟集合算法是描述一個問題的求解過程，它由一系列解決問題的清晰指令構(gòu)成可以使用自然語言表示可以使用計算機程序設(shè)計語言表示可以混合使用自然語言與計算機程序設(shè)計語言溫度轉(zhuǎn)換將攝氏溫標值C轉(zhuǎn)換為華氏溫標值F已知計算公式為：F=(9/5)C+32轉(zhuǎn)換的過程可以這樣描述輸入一個攝氏溫標值CC乘以常數(shù)9/5（或1.8）前一步的乘積與常數(shù)32相加，得到F輸出結(jié)果F，即轉(zhuǎn)換后的華氏溫標值溫度轉(zhuǎn)換算法的程序算法特性算法必須滿足如下的5個重要特性輸入：有0或多個輸入值輸出：有1或多個輸出值有窮性：一個算法必須在執(zhí)行有窮步驟之后結(jié)束確定性：算法的每一個步驟必須是有確切含義的可行性：算法中要做的運算都是相當(dāng)基本的、能夠精確進行的算法的評估和復(fù)雜性度量算法必須要正確，所以算法的正確性成為評判算法的首要指標還要評判算法的其他方面，包括它的執(zhí)行效率時間復(fù)雜度空間復(fù)雜度時間復(fù)雜度

計算機中最重要的資源之一是CPU，顯然，花費的時間與處理的數(shù)據(jù)個數(shù)有很大的關(guān)系，這個數(shù)據(jù)個數(shù)稱為問題規(guī)模，也稱問題大小。執(zhí)行算法花費的時間表示為問題規(guī)模的一個函數(shù)統(tǒng)計一個程序執(zhí)行期間需要執(zhí)行的語句總數(shù)，并且約定，程序設(shè)計語言中一條基本語句的執(zhí)行時間為1個單位時長時間復(fù)雜度一個算法的時間效率可以用問題規(guī)模及關(guān)鍵的處理步驟的多少來定義將算法的運行效率表示為問題規(guī)模n的一個解析式，對于規(guī)模為n的問題，解析式計算的值，應(yīng)該是算法處理的步驟數(shù)將關(guān)于n的這個解析式稱為增長函數(shù)，表示為T(n)對于一個具體的算法，其增長函數(shù)是一個近似的表達式查找給定數(shù)組中的最大值

當(dāng)數(shù)組中元素個數(shù)為10n時，執(zhí)行的語句個數(shù)最多為10n+1，即問題規(guī)模擴大10倍，所花費的時間也增大約10倍程序段sum=0; //賦初值for(i=0;i<n;i++) //對每個n for(j=0;j<n;j++) //對每個n sum++; //累加returnsum;主體是一個二重循環(huán)，外層循環(huán)每執(zhí)行一次，內(nèi)層循環(huán)都執(zhí)行n次，所以sum++的總執(zhí)行次數(shù)為n2，語句執(zhí)行的總數(shù)是n2+2，即增長函數(shù)T(n)=n2+2當(dāng)問題規(guī)模擴大10倍時，所花的時間需要增加約100倍漸近時間復(fù)雜度考查增長函數(shù)時，只關(guān)心增長函數(shù)表達式中的主項，并且不再考慮主項的系數(shù)表達式的主項使用記號O來表示例1.4中增長函數(shù)表示為O(n)例1.5中增長函數(shù)表示為O(n2)這稱為漸近時間復(fù)雜度，也稱為算法的階定義定義1-2稱（復(fù)雜度）函數(shù)T(n)是O(f(n))的，即T(n)=O(f(n))，如果存在常數(shù)c>0與n0，當(dāng)n>n0時有T(n)≤cf(n)T1(n)=(n+1)/2=O(n2)T2(n)=3n2+4n+5=O(n3)當(dāng)然T1(n)=O(n2)，T2(n)=O(n3)也是對的，但一般取最低階表示T(n)=O(f(n))說明T(n)的階不大于f(n)的階定義定義1-3稱（復(fù)雜度）函數(shù)T(n)是Ω(f(n))的，即T(n)=Ω(f(n))，如果存在常數(shù)c>0與n0，當(dāng)n>n0時有T(n)≥cf(n)T1(n)=(n+1)/2=Ω(n)T2(n)=3n2+4n+5=Ω(n2)當(dāng)然T1(n)=Ω(1)，T2(n)=Ω(n)，T2(n)=Ω(nlogn)也都是對的，同樣地，取它們之中的最高階T(n)=Ω(f(n))說明T(n)的階不小于f(n)的階大O表示法和大Ω表示法使我們能夠描述某一算法的上限（如果能找到某一類輸入下開銷最大的函數(shù)）和下限（如果能找到某一類輸入下開銷最小的函數(shù)）當(dāng)上、下限相等時，可用Θ表示法。如果一種算法既是O(f(n))，又是Ω(f(n))，則稱其是Θ(f(n))的若增長函數(shù)不隨算法問題規(guī)模變化，則增長函數(shù)稱為O(1)階，或稱常數(shù)復(fù)雜度與問題規(guī)模成正比的問題求解算法稱為線性操作許多算法具有l(wèi)og2n對數(shù)復(fù)雜度其他的算法有n的某次冪的多項式復(fù)雜度，如O(n2)或O(n3)更壞的算法是指數(shù)復(fù)雜度，n是指數(shù)，如O(2n)一些增長函數(shù)的漸近時間復(fù)雜增長函數(shù)階時間復(fù)雜度T(n)=17O(1)常數(shù)T(n)=20n-4O(n)線性T(n)=12nlogn+100nO(nlogn)線性對數(shù)T(n)=3n2+5n-2O(n2)多項式（平方）T(n)=2n+18n2+3nO(2n)指數(shù)示例

上述程序的時間復(fù)雜度是（

）A．O(log2n) B．O(n)C．O(nlog2n) D．O(n2)解：答案是B程序段intx=m;while(x>1){ x=x/2;}其中m>1，則時間復(fù)雜度為（

）A．O(logm) B．O(m2)C．O(m1/2)

D．O(m1/3)解：答案是A

若處理器速度增長10倍

算法時間復(fù)雜度提升前最大問題規(guī)模提升后最大問題規(guī)模A1O(n)s110s1A2O(n2)s23.16s2A3O(n3)s32.15s3A4O(2n)s4s4+3.3除了要評判算法的時間復(fù)雜度外，算法在運行過程中臨時占用的空間大小也要考慮，這稱為空間復(fù)雜度。一般地，空間復(fù)雜度也表示為問題規(guī)模的一個函數(shù)?？紤]空間存儲量時，算法代碼占用的空間、算法中初始數(shù)據(jù)占用的存儲空間，都不包含在內(nèi)第三節(jié)

算法設(shè)計策略簡介算法可以分為多種不同的類型，每種類型都有特定的應(yīng)用場景和解決問題的方法設(shè)計算法時，可以配合采用一些設(shè)計策略，使得算法的實現(xiàn)更方便設(shè)計策略有時也可以稱為設(shè)計方法，是指在解決特定問題時所采用的一類方法算法分為遞推法、迭代法、遞歸法、貪心法、分治法、動態(tài)規(guī)劃法等遞推法遞推法是一種直接求解的算法設(shè)計策略，利用問題本身所具有的一種遞推關(guān)系進行求解。找到問題本身的遞推關(guān)系是問題求解的前提遞推法的思想是，根據(jù)遞推關(guān)系，能從已求得的問題規(guī)模為1,2,…,i-1的一系列解，構(gòu)造出問題規(guī)模為i的解。求解規(guī)模為i的解時，有時可能僅需規(guī)模為1,2,…,i-1的系列解中的一部分，而不是全部示例

由遞推公式可計算出數(shù)列的第三項，為2再由第二項和第三項，得到第四項的值3再由第三項和第四項，得到第五項的值5以此類推得到數(shù)列的前10項為：1,1,2,3,5,8,13,21,34,55程序迭代法是一種直接求解的方法，往往需要建立迭代關(guān)系式即根據(jù)前一個值推出下一個值的公式初始時設(shè)定初始值（原值），然后根據(jù)迭代關(guān)系式和原值，求出新值，并用新值替代原值迭代過程不能無限進行下去或者設(shè)定一個迭代次數(shù)，當(dāng)達到這個次數(shù)時迭代過程停止或者設(shè)定一個結(jié)束條件，當(dāng)滿足這個條件時，迭代過程停止程序遞歸法

貪心法貪心算法也稱貪婪算法，這是一種通過每一步選擇局部最優(yōu)解來達到整體最優(yōu)解的算法，適用于求某些最優(yōu)解問題求解過程中，一步一步地進行，根據(jù)當(dāng)前的情況選擇最優(yōu)的可能實際上，這個最優(yōu)是在當(dāng)前條件下的最優(yōu)，稱為局部最優(yōu)第四章構(gòu)造哈夫曼樹的過程采用了貪心法策略，第六章求最小生成樹的兩個算法也采用了貪心法求解分治法當(dāng)求解一個輸入規(guī)模為n并且n的取值又很大的問題時，可以把這個大規(guī)模的問題分解為若干個規(guī)模更小且可以獨立求解的問題，然后把各個小問題的解進行合并，得到原問題的解。這就是分治法的思想一般來說，分治法的求解過程分為三個階段即劃分、求解小問題及小問題解的合并第七章介紹的快速排序和歸并排序都采用了分治法求解它們是將大問題