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

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

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

基本概念和術(shù)語(yǔ)

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

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

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

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

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

第二節(jié)

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

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

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

上述程序的時(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，則時(shí)間復(fù)雜度為（

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

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

若處理器速度增長(zhǎng)10倍

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

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

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

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