第五章 數(shù)據(jù)結(jié)構(gòu)的應(yīng)用 課件 2023-2024學(xué)年粵教版（2019）高中信息技術(shù)選修1

數(shù)據(jù)結(jié)構(gòu)的應(yīng)用查找和排序，與我們的學(xué)習(xí)、生活息息相關(guān)。如從字典

中查找漢字，從電話號(hào)碼本中查找電話，在圖書館中查找圖

書，高考查詢成績(jī)等；教師按身高來安排學(xué)生的座位，大學(xué)

按照高考成績(jī)高低順序錄取新生，網(wǎng)上商城按照銷量高低排

序來推薦商品等。在信息時(shí)代，數(shù)據(jù)的增長(zhǎng)速度越來越快，

導(dǎo)致信息量呈幾何級(jí)的增長(zhǎng)。在龐大的數(shù)據(jù)里進(jìn)行人工查找和排序是非常困難的，甚至是無法辦到的，所以必須依靠計(jì)

算機(jī)才能快速、準(zhǔn)確地對(duì)數(shù)據(jù)進(jìn)行查找和排序。5.1迭代與遞歸在利用計(jì)算機(jī)解決實(shí)際問題中，迭代和遞歸都是非常實(shí)用的算法，很多難的問題都是通過迭代或遞歸算法解出來的。1．迭代法迭代法是用計(jì)算機(jī)解決問題的一種基本方法。它利用計(jì)算機(jī)運(yùn)算速度快、適合做重復(fù)性操作的特點(diǎn)，讓計(jì)算機(jī)重復(fù)執(zhí)行一組指令（或一定步驟），在每次執(zhí)行這組指令（或這些步驟）時(shí)，都從變量的原值推出它的一個(gè)新值。intn,sum=0;//sum初始化為0for(inti=1;i<=n;i++)//用循環(huán)實(shí)現(xiàn)迭代{sum=sum+i;//迭代過程}用迭代法解決問題，需考慮三個(gè)方面的內(nèi)容。

（1）確定迭代變量。在可以用迭代法解決的問題中，至少存在一個(gè)直接或間接地不斷由舊值遞推出新值的變量，這個(gè)變量就是迭代變量。在例1中，sum就是迭代變量。（2）建立關(guān)系式。迭代關(guān)系式是指如何從變量的前一個(gè)值推出其下一個(gè)值的公式（或關(guān)系）。迭代關(guān)系式的建立是解決迭代問題的關(guān)鍵，通?？梢允褂庙樛苹虻雇频姆椒▉硗瓿?。例1中，“sum=sum+i”就是迭代關(guān)系式，通過此式可以進(jìn)行迭代求和。（3）過程控制。編寫迭代程序必須考慮在什么時(shí)候結(jié)束迭代過程，不能讓迭代過程無休止地重復(fù)執(zhí)行下去。迭代過程的控制通?？煞譃閮煞N情況：一種是所需的迭代次數(shù)是個(gè)確定的值，可以計(jì)算出來；另一種是所需的迭代次數(shù)無法預(yù)先確定。對(duì)于前一種情況，可以構(gòu)建一個(gè)固定次數(shù)的循環(huán)來實(shí)現(xiàn)對(duì)迭代過程的控制；對(duì)于后一種情況，需要進(jìn)一步分析確定迭代過程結(jié)束的條件。在例1中，用了for循環(huán)語句進(jìn)行過程控制。例：一對(duì)剛出生的小兔子，一個(gè)月后就能成長(zhǎng)為成年兔，再過一個(gè)月后（即第三個(gè)月起）就每月生一對(duì)兔子。新生的兔子也按這個(gè)規(guī)律繁殖?，F(xiàn)在僅有一對(duì)剛出生的小兔子，問在沒有兔子死亡的情況下，一年后總共繁殖成多少對(duì)兔子。

f(1)=1,f(2)=1,f(n)=f(n-1)+f(n-2)(n>=3)算法分析：設(shè)f(n)表示第n個(gè)月的兔子對(duì)數(shù)，先看前幾個(gè)月的情況：第一個(gè)月有一對(duì)剛出生的兔子，即f(1)=1；第二個(gè)月，這對(duì)兔子長(zhǎng)成成年兔，兔子對(duì)數(shù)還是只有1對(duì)，即f(2)=1；第三個(gè)月，這對(duì)成年兔生出一對(duì)小兔，共有兩對(duì)兔子，即f(3)=2；第四個(gè)月，成年兔又生出一對(duì)小兔，第三個(gè)月出生的兔子長(zhǎng)成成年兔，共有三對(duì)兔子，即f(4)=3；第五個(gè)月，原成年兔又生出一對(duì)小兔，新成年兔也生出一對(duì)小兔，共有五對(duì)兔子，即f(5)=5……以此類推，每個(gè)月兔子數(shù)為1，1，2，3，5，8，13，21，…轉(zhuǎn)化為數(shù)學(xué)模型，設(shè)f(n)為第n個(gè)月的兔子對(duì)數(shù)，則有：下面是實(shí)現(xiàn)求一年后繁殖的兔子總數(shù)的核心代碼，其中f1、f2、fn這三個(gè)迭代變量分別代表前兩個(gè)月、前一個(gè)月、當(dāng)前月的兔子數(shù)，用迭代關(guān)系式“fn=f1+f2;”計(jì)算當(dāng)月的兔子數(shù)，再用“f1=f2;f2=fn;”為下一個(gè)月的迭代計(jì)算做好準(zhǔn)備。

intf1=1,f2=1,fn=0;//迭代變量for(inti=3;i<=12;i++)//用i的值來控制迭代的次數(shù){fn=f1+f2;//計(jì)算當(dāng)月數(shù)量f1=f2;//f1、f2迭代計(jì)算，為下個(gè)月迭代賦初值f2=fn;}每個(gè)月的兔子對(duì)數(shù)組成數(shù)列：1，1，2，3，5，8，13，21，34，55，89，144，…此數(shù)列也稱為斐波那契數(shù)列。5.1.2遞歸1．遞歸的基本概念若一個(gè)對(duì)象用自己來定義自己或部分地包含自己，則稱這個(gè)對(duì)象是遞歸的；若一個(gè)過程直接地或間接地調(diào)用自己，則稱這個(gè)過程是遞歸過程。在程序設(shè)計(jì)中，函數(shù)直接調(diào)用函數(shù)本身，稱為直接遞歸調(diào)用；在函數(shù)中調(diào)用其他函數(shù)，其他函數(shù)又調(diào)用原函數(shù)，構(gòu)成了函數(shù)自身的間接調(diào)用，則稱為間接遞歸調(diào)用。2．遞歸在數(shù)學(xué)中的應(yīng)用:在數(shù)學(xué)中，有這樣一種數(shù)列，很難求出它的通項(xiàng)公式，但數(shù)列中各項(xiàng)間關(guān)系卻很簡(jiǎn)單，于是人們想出另一種辦法來描述這種數(shù)列，即通過初值及與前面臨近幾項(xiàng)之間的關(guān)系來描述。要使用這樣的描述方式，至少要提供兩個(gè)信息：一是最前面幾項(xiàng)的數(shù)值，二是數(shù)列間各項(xiàng)的關(guān)系。這是遞歸函數(shù)的最簡(jiǎn)單形式，從中可以明顯看出遞歸函數(shù)一般的寫法特點(diǎn)：先處理一

些特殊情況（遞歸終結(jié)條件），再處理遞歸關(guān)系。

遞歸函數(shù)的執(zhí)行過程總是先通過遞歸關(guān)系不斷地縮小問題的規(guī)模，直到簡(jiǎn)單到可以作

為特殊情況處理而得出直接的結(jié)果，再通過遞歸關(guān)系逐層返回到原來的數(shù)據(jù)規(guī)模，最終得出問題的解。3．遞歸算法的思想與應(yīng)用（1）遞歸算法的思想。為求解一個(gè)不能或不好直接求解的“大問題”，設(shè)法將它分解成規(guī)模較小但解法相同的“小問題”，并且這些“小問題”也能采用同樣的分解方法再分解成規(guī)模更小的“小問題”，當(dāng)規(guī)模最小的一個(gè)或幾個(gè)值能直接得出解時(shí)，再利用這些“小問題”的解構(gòu)造出“大問題”的解。（2）遞歸算法解決問題的特點(diǎn)。遞歸算法有四個(gè)特性：①必須有明確的遞歸終結(jié)條件，否則程序?qū)⑾萑霟o窮循環(huán)而造成棧溢出。②子問題在規(guī)模上比原問題小，或更接近終止條件。③子問題可通過再次遞歸調(diào)用求解或因滿足終止條件而直接求解。④子問題的解應(yīng)能組合為整個(gè)問題的解。（3）遞歸算法一般用于解決的三類問題。①數(shù)據(jù)的定義是按遞歸定義的。如數(shù)學(xué)上常用的階乘數(shù)列、斐波那契數(shù)列、冪函數(shù)等，它們的定義都是遞歸的。②問題方便用遞歸算法實(shí)現(xiàn)。有些問題用遞歸方法實(shí)現(xiàn)更方便，如求階乘函數(shù)的值。③數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的。如鏈表、樹的遍歷、圖的搜索等。5.2查找在日常生活和學(xué)習(xí)中，我們經(jīng)常要進(jìn)行查找工作，例如從字典中查找漢字、單詞，從電話號(hào)碼本中查找電話，在圖書館中查找圖書，高考查詢成績(jī)等。其實(shí)，“電話號(hào)碼本”“字典”等都可以看作一張表，查找則是在一個(gè)含有眾多數(shù)據(jù)元素（或記錄）的表中找出某個(gè)特定的數(shù)據(jù)元素（或記錄）。在信息時(shí)代，由于信息量巨大，人工查找是非常困難的，甚至是無法辦到的，所以必須依靠計(jì)算機(jī)才能快速、準(zhǔn)確地查找信息。5.2.1順序查找順序表是指采用順序存儲(chǔ)的方式存儲(chǔ)的集合或線性表。在本章，我們主要探討一維數(shù)組這種順序表的順序查找和二分查找方法。順序查找也稱為線性查找，它的基本思想是：從順序表的一端開始，將每個(gè)元素的關(guān)鍵字與給定值k進(jìn)行比較，如果相同，則表明查找成功，返回該元素的下標(biāo)；如果在所有元素都進(jìn)行了比較后，仍找不到關(guān)鍵字為k的元素，則表明查找失敗，返回特定值-1。在超市中，要實(shí)現(xiàn)查詢某商品在哪個(gè)貨架，我們可以用數(shù)組存儲(chǔ)商品的編號(hào)、存放的貨架等信息。程序運(yùn)行時(shí)，輸入需查詢商品的編號(hào)，然后在數(shù)組中依次查找編號(hào)，就可查找出該商品的信息，方便顧客查找商品。下面是順序查找算法的核心代碼：5.2.2二分查找順序查找雖然能幫助顧客查找到所需信息，但由于超市銷售的商品種類繁多，數(shù)據(jù)量比較大，而順序查找每次都要從頭到尾去查找，需要花費(fèi)不少時(shí)間，很多顧客沒有耐心長(zhǎng)時(shí)間等待查詢結(jié)果。所以查找的速度必須要快，可以考慮用查找速度更快的二分查找來實(shí)現(xiàn)。二分查找又稱折半查找，是針對(duì)順序存儲(chǔ)的有序表（有序表是指各元素按關(guān)鍵字的值以升序或降序存放的表）進(jìn)行的查找，它是一種較常用的查找方法。在按升序存儲(chǔ)的順序表a中查找k，其二分查找算法流程如下：（1）選取查找范圍a[0]~a[n-1]。（2）選定查找范圍的中點(diǎn)元素a[mid]，與k值比較。（3）若相等，則查找成功，返回該元素的下標(biāo)。（4）若k<a[mid]，則將范圍縮小到左子表a[0]~a[mid-1]。（5）若k>a[mid]，則將范圍縮小到右子表a[mid+1]~a[n-1]。（6）迭代以上過程，直到找到k或當(dāng)前查找區(qū)間為空（即查找失?。?。對(duì)比解決同一個(gè)問題，我們可以用不同的算法編寫程序，不同的算法對(duì)數(shù)據(jù)結(jié)構(gòu)的要求可

能是不同的。對(duì)比順序查找與二分查找算法，當(dāng)數(shù)據(jù)量較大時(shí)，二分查找會(huì)比順序查找快

很多，這是它的主要優(yōu)點(diǎn)，但它要求查找表是有序的，所以在進(jìn)行二分查找之前，必須先

對(duì)查找表進(jìn)行排序。另外，二分查找要求表是順序存儲(chǔ)的，為保持表的有序性，在進(jìn)行插

入、刪除操作時(shí)，都必須移動(dòng)大量記錄。因此，二分查找的高查找效率是以排序?yàn)榇鷥r(jià)

的，所以它特別適合一經(jīng)建立就很少移動(dòng)而且經(jīng)常需要查找的線性表。

了解不同算法的特點(diǎn)，可以幫助我們?cè)诮鉀Q實(shí)際問題時(shí)，從不同的算法中選擇出較為

合適的一種，或?qū)ΜF(xiàn)有算法進(jìn)行改進(jìn)或創(chuàng)新，從而設(shè)計(jì)出更好的算法5.3排序排序與我們的日常生活息息相關(guān)。例如，教師按身高來安排學(xué)生的座位，試卷和答題卡按從小號(hào)到大號(hào)的順序來整理，各類比賽按成績(jī)的高低來排名，查詢火車票時(shí)會(huì)按照出發(fā)的先后來顯示，到網(wǎng)上購物會(huì)參考銷量高低來排序購買等。排序是數(shù)據(jù)處理和分析中最常用的運(yùn)算之一，它往往可以提高數(shù)據(jù)處理的效率；排序也是最基本的算法之一，其他很多算法都是以排序算法為基礎(chǔ)，所以研究和掌握排序算法是非常重要的。在信息時(shí)代，面對(duì)龐大的信息量，想要靠人工進(jìn)行排序，會(huì)耗費(fèi)大量時(shí)間和精力，甚至無法完成。所以，依靠計(jì)算機(jī)快速、準(zhǔn)確地對(duì)數(shù)據(jù)進(jìn)行排序，是很有必要的。5.3.1認(rèn)識(shí)排序1．排序排序是指把一個(gè)任意序列的數(shù)據(jù)元素重新排列成按照某關(guān)鍵字遞增或遞減序列的過程。作為排序依據(jù)的數(shù)據(jù)項(xiàng)稱為排序關(guān)鍵字，簡(jiǎn)稱關(guān)鍵字（Key）。排序時(shí)選取哪一個(gè)數(shù)據(jù)項(xiàng)作為關(guān)鍵字，應(yīng)根據(jù)具體情況而定。2．排序的分類

假定在待排序的序列中，存在多個(gè)具有相同鍵值的數(shù)據(jù)元素，若經(jīng)過排序，這些數(shù)據(jù)元素的相對(duì)次序仍然保持不變，則稱這種排序是穩(wěn)定的排序；否則，稱這種排序是不穩(wěn)定的排序。例如以表5-3中的“銷售數(shù)量”來排列名次：待排序的序列：2510171310376//給其中一個(gè)“10”加底色以區(qū)分穩(wěn)定的排序：6101013172537//因?yàn)?0還是在10的前面不穩(wěn)定的排序：6101013172537//因?yàn)?0已在10的后面在排序過程中，可以使用內(nèi)存儲(chǔ)器，也可以使用外存儲(chǔ)器。如果參加排序的數(shù)據(jù)元素的數(shù)量不多，能夠全部調(diào)入內(nèi)存中進(jìn)行排序，則稱這種排序?yàn)閮?nèi)部排序；若參加排序的數(shù)據(jù)元素的數(shù)量較大，需要分批調(diào)入內(nèi)存中進(jìn)行排序，排序后再分批存回外存儲(chǔ)器，則稱這種排序?yàn)橥獠颗判颉?．排序的分類內(nèi)部排序的方法很多，按照排序過程中所用策略的不同，通常分為五大類：插入排序、選擇排序、交換排序、歸并排序和基數(shù)排序。其中，交換排序又包含冒泡排序和快速排序，都是常用的排序算法。冒泡排序是一種簡(jiǎn)單、常見的排序算法，適合初學(xué)者學(xué)習(xí)；快速排序是對(duì)冒泡排序的改進(jìn)，它是目前內(nèi)部排序中平均速度最快的排序算法，也是20世紀(jì)十大算法之一。3．排序的存儲(chǔ)結(jié)構(gòu)排序的方法很多，通常都要進(jìn)行兩種基本操作：（1）比較兩個(gè)元素關(guān)鍵字的大小。（2）根據(jù)比較結(jié)果，將元素從一個(gè)位置移到另一個(gè)位置。其中，第（1）種操作對(duì)大多數(shù)排序方法來說都是必要的，第（2）種操作可通過改變?cè)氐拇鎯?chǔ)方式，比如采用鏈表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的數(shù)據(jù)元素。從操作角度看，排序是線性結(jié)構(gòu)的一種操作，待排序元素可以用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來存儲(chǔ)。在順序存儲(chǔ)結(jié)構(gòu)中，待排序元素按自然順序存放在連續(xù)的一塊內(nèi)存空間中，元素之間的次序關(guān)系由其存儲(chǔ)位置決定，所以排序過程中一定要移動(dòng)元素；在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，待排序元素按原始次序鏈接起來，排序時(shí)只需要修改鏈表指針，不用移動(dòng)元素。5.3.2冒泡排序冒泡排序（BubbleSort）是一種簡(jiǎn)單的交換排序算法，它是通過交換相鄰的兩個(gè)數(shù)據(jù)元素，逐步將待排序列變成有序序列。它的基本思想如下：（1）假設(shè)待排序元素有n個(gè)，從第一個(gè)元素開始，依次交換相鄰的兩個(gè)逆序元素，直到最后一個(gè)元素為止，當(dāng)?shù)谝惶伺判蚪Y(jié)束，就會(huì)將最大（?。┑脑匾苿?dòng)到序列的末尾。（2）然后按照以上方法進(jìn)行第二趟排序，次大（?。┑脑貙?huì)被移動(dòng)到序列的倒數(shù)第二個(gè)位置。（3）依次類推，經(jīng)過n-1趟排序后，整個(gè)元素序列就成了一個(gè)有序（升序或降序）的序列。每趟排序過程中，值?。ù螅┑脑叵蚯耙苿?dòng)，值大（?。┑脑叵蚝笠苿?dòng)，就像氣泡一樣向上升，因此將這種排序方法稱為冒泡排序。最少比較n-1次，最多比較n（n-1）/2次次數(shù)？例5：假設(shè)有五個(gè)元素的待排序列為25、10、17、37、13，將此序列按升序排序的冒泡排序過程如圖5-7所示。例5：假設(shè)有五個(gè)元素的待排序列為25、10、17、37、13，將此序列按升序排序的冒泡排序過程如圖5-7所示。5.3.3快速排序1．快速排序的基本思想快速排序采用分治法的策略：將原問題劃分成規(guī)模更小但與原問題相似的小問題，然后用遞歸法解決這些小問題，最后將它們組合形成原問題的解。以關(guān)鍵字升序排列為例，設(shè)待排序列存放在數(shù)組a[1..n]中，n為元素個(gè)數(shù)，i、j分別是待排序列首尾關(guān)鍵字的下標(biāo)，初值分別為1