資源簡介

(共36張PPT)
數(shù)據(jù)結(jié)構(gòu)的應(yīng)用
查找和排序，與我們的學(xué)習(xí)、生活息息相關(guān)。
如從字典 中查找漢字，從電話號碼本中查找電話，在圖書館中查找圖 書，高考查詢成績等；教師按身高來安排學(xué)生的座位，大學(xué) 按照高考成績高低順序錄取新生，網(wǎng)上商城按照銷量高低排 序來推薦商品等。在信息時代，數(shù)據(jù)的增長速度越來越快， 導(dǎo)致信息量呈幾何級的增長。在龐大的數(shù)據(jù)里進(jìn)行人工查找和排序是非常困難的，甚至是無法辦到的，所以必須依靠計 算機才能快速、準(zhǔn)確地對數(shù)據(jù)進(jìn)行查找和排序。
5.1　迭代與遞歸
在利用計算機解決實際問題中，迭代和遞歸都是非常實用的算法，很多難的問題都是通過迭代或遞歸算法解出來的。
1．迭代法
迭代法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重復(fù)性操作的特點，讓計算機重復(fù)執(zhí)行一組指令（或一定步驟），在每次執(zhí)行這組指令（或這些步驟）時，都從變量的原值推出它的一個新值。
int n,sum=0; //sum初始化為0
for(int i=1; i<=n; i++) //用循環(huán)實現(xiàn)迭代
{
sum=sum+i; //迭代過程
}
用迭代法解決問題，需考慮三個方面的內(nèi)容。
（1）確定迭代變量。在可以用迭代法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量就是迭代變量。在例1中，sum就是迭代變量。
（2）建立關(guān)系式。迭代關(guān)系式是指如何從變量的前一個值推出其下一個值的公式（或關(guān)系）。迭代關(guān)系式的建立是解決迭代問題的關(guān)鍵，通常可以使用順推或倒推的方法來完成。例1中，“sum=sum+i”就是迭代關(guān)系式，通過此式可以進(jìn)行迭代求和。
（3）過程控制。編寫迭代程序必須考慮在什么時候結(jié)束迭代過程，不能讓迭代過程無休止地重復(fù)執(zhí)行下去。迭代過程的控制通常可分為兩種情況：一種是所需的迭代次數(shù)是個確定的值，可以計算出來；另一種是所需的迭代次數(shù)無法預(yù)先確定。對于前一種情況，可以構(gòu)建一個固定次數(shù)的循環(huán)來實現(xiàn)對迭代過程的控制；對于后一種情況，需要進(jìn)一步分析確定迭代過程結(jié)束的條件。在例1中，用了for循環(huán)語句進(jìn)行過程控制。
例：
一對剛出生的小兔子，一個月后就能成長為成年兔，再過一個月后（即第三個 月起）就每月生一對兔子。新生的兔子也按這個規(guī)律繁殖?，F(xiàn)在僅有一對剛出生的小兔子，問在沒有兔子死亡的情況下，一年后總共繁殖成多少對兔子。
f(1)=1,
f(2)=1,
f(n)=f(n-1)+f(n-2) (n>=3)
算法分析：
設(shè)f(n)表示第n個月的兔子對數(shù)，先看前幾個月的情況：第一個月有一對 剛出生的兔子，即f(1)=1；第二個月，這對兔子長成成年兔，兔子對數(shù)還是只有1對， 即f(2)=1；第三個月，這對成年兔生出一對小兔，共有兩對兔子，即f(3)=2；第四個月， 成年兔又生出一對小兔，第三個月出生的兔子長成成年兔，共有三對兔子，即f(4)=3； 第五個月，原成年兔又生出一對小兔，新成年兔也生出一對小兔，共有五對兔子，即 f(5)=5……以此類推，每個月兔子數(shù)為1，1，2，3，5，8，13，21，… 轉(zhuǎn)化為數(shù)學(xué)模型，設(shè)f(n)為第n個月的兔子對數(shù)，則有：
下面是實現(xiàn)求一年后繁殖的兔子總數(shù)的核心代碼，其中f1、f2、fn這三個迭代變量分別代表前兩個月、前一個月、當(dāng)前月的兔子數(shù)，用迭代關(guān)系式“fn = f1 + f2;”計算當(dāng)月的兔子數(shù)，再用“f1 = f2; f2 = fn;”為下一個月的迭代計算做好準(zhǔn)備。
int f1=1,f2=1,fn=0; //迭代變量
for(int i=3; i<=12; i++) //用i的值來控制迭代的次數(shù)
{
fn=f1+f2; //計算當(dāng)月數(shù)量
f1=f2; //f1、f2迭代計算，為下個月迭代賦初值
f2=fn;
}
每個月的兔子對數(shù)組成數(shù)列：1，1，2，3，5，8，13，21，34，55，89，144，…此數(shù)列也稱為斐波那契數(shù)列。
5.1.2　遞歸
1．遞歸的基本概念若一個對象用自己來定義自己或部分地包含自己，則稱這個對象是遞歸的；若一個過程直接地或間接地調(diào)用自己，則稱這個過程是遞歸過程。在程序設(shè)計中，函數(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ù)列，很難求出它的通項公式，但數(shù)列中各項間關(guān)系卻很簡單，于是人們想出另一種辦法來描述這種數(shù)列，即通過初值及與前面臨近幾項之間的關(guān)系來描述。要使用這樣的描述方式，至少要提供兩個信息：一是最前面幾項的數(shù)值，二是數(shù)列間各項的關(guān)系。
這是遞歸函數(shù)的最簡單形式，從中可以明顯看出遞歸函數(shù)一般的寫法特點：先處理一 些特殊情況（遞歸終結(jié)條件），再處理遞歸關(guān)系。 遞歸函數(shù)的執(zhí)行過程總是先通過遞歸關(guān)系不斷地縮小問題的規(guī)模，直到簡單到可以作 為特殊情況處理而得出直接的結(jié)果，再通過遞歸關(guān)系逐層返回到原來的數(shù)據(jù)規(guī)模，最終得出問題的解。
3．遞歸算法的思想與應(yīng)用
（1）遞歸算法的思想。
為求解一個不能或不好直接求解的“大問題”，設(shè)法將它分解成規(guī)模較小但解法相同的“小問題”，并且這些“小問題”也能采用同樣的分解方法再分解成規(guī)模更小的“小問題”，當(dāng)規(guī)模最小的一個或幾個值能直接得出解時，再利用這些“小問題”的解構(gòu)造出“大問題”的解。
（2）遞歸算法解決問題的特點。
遞歸算法有四個特性：
①必須有明確的遞歸終結(jié)條件，否則程序?qū)⑾萑霟o窮循環(huán)而造成棧溢出。
②子問題在規(guī)模上比原問題小，或更接近終止條件。
③子問題可通過再次遞歸調(diào)用求解或因滿足終止條件而直接求解。
④子問題的解應(yīng)能組合為整個問題的解。
（3）遞歸算法一般用于解決的三類問題。
①數(shù)據(jù)的定義是按遞歸定義的。如數(shù)學(xué)上常用的階乘數(shù)列、斐波那契數(shù)列、冪函數(shù)等，它們的定義都是遞歸的。
②問題方便用遞歸算法實現(xiàn)。有些問題用遞歸方法實現(xiàn)更方便，如求階乘函數(shù)的值。
③數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的。如鏈表、樹的遍歷、圖的搜索等。
5.2　查找
在日常生活和學(xué)習(xí)中，我們經(jīng)常要進(jìn)行查找工作，例如從字典中查找漢字、單詞，從電話號碼本中查找電話，在圖書館中查找圖書，高考查詢成績等。其實，“電話號碼本”“字典”等都可以看作一張表，查找則是在一個含有眾多數(shù)據(jù)元素（或記錄）的表中找出某個特定的數(shù)據(jù)元素（或記錄）。在信息時代，由于信息量巨大，人工查找是非常困難的，甚至是無法辦到的，所以必須依靠計算機才能快速、準(zhǔn)確地查找信息。
5 . 2 . 1 　 順序查找
順序表是指采用順序存儲的方式存儲的集合或線性表。在本章，我們主要探討一維數(shù) 組這種順序表的順序查找和二分查找方法。 順序查找也稱為線性查找，它的基本思想是：從順序表的一端開始，將每個元素的關(guān) 鍵字與給定值k進(jìn)行比較，如果相同，則表明查找成功，返回該元素的下標(biāo)；如果在所有 元素都進(jìn)行了比較后，仍找不到關(guān)鍵字為k的元素，則表明查找失敗，返回特定值-1。 在超市中，要實現(xiàn)查詢某商品在哪個貨架，我們可以用數(shù)組存儲商品的編號、存放的 貨架等信息。程序運行時，輸入需查詢商品的編號，然后在數(shù)組中依次查找編號，就可查找出該商品的信息，方便顧客查找商品。下面是順序查找算法的核心代碼：
5 . 2 . 2 　 二分查找
順序查找雖然能幫助顧客查找到所需信息，但由于超市銷售的商品種類繁多，數(shù)據(jù)量比較大，而順序查找每次都要從頭到尾去查找，需要花費不少時間，很多顧客沒有耐心長時間等待查詢結(jié)果。所以查找的速度必須要快，可以考慮用查找速度更快的二分查找來實現(xiàn)。
二分查找又稱折半查找，是針對順序存儲的有序表（有序表是指各元素按關(guān)鍵字的值以升序或降序存放的表）進(jìn)行的查找，它是一種較常用的查找方法。在按升序存儲的順序表a中查找k，其二分查找算法流程如下：
（1） 選取查找范圍a[0]~a[n-1]。
（2） 選定查找范圍的中點元素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ū)間為空（即查找失?。?。
對比
解決同一個問題，我們可以用不同的算法編寫程序，不同的算法對數(shù)據(jù)結(jié)構(gòu)的要求可 能是不同的。對比順序查找與二分查找算法，當(dāng)數(shù)據(jù)量較大時，二分查找會比順序查找快 很多，這是它的主要優(yōu)點，但它要求查找表是有序的，所以在進(jìn)行二分查找之前，必須先 對查找表進(jìn)行排序。另外，二分查找要求表是順序存儲的，為保持表的有序性，在進(jìn)行插 入、刪除操作時，都必須移動大量記錄。因此，二分查找的高查找效率是以排序為代價 的，所以它特別適合一經(jīng)建立就很少移動而且經(jīng)常需要查找的線性表。
了解不同算法的特點，可以幫助我們在解決實際問題時，從不同的算法中選擇出較為 合適的一種，或?qū)ΜF(xiàn)有算法進(jìn)行改進(jìn)或創(chuàng)新，從而設(shè)計出更好的算法
5.3　排序
排序與我們的日常生活息息相關(guān)。例如，教師按身高來安排學(xué)生的座位，試卷和答題 卡按從小號到大號的順序來整理，各類比賽按成績的高低來排名，查詢火車票時會按照出 發(fā)的先后來顯示，到網(wǎng)上購物會參考銷量高低來排序購買等。排序是數(shù)據(jù)處理和分析中最 常用的運算之一，它往往可以提高數(shù)據(jù)處理的效率；排序也是最基本的算法之一，其他很 多算法都是以排序算法為基礎(chǔ)，所以研究和掌握排序算法是非常重要的。在信息時代，面 對龐大的信息量，想要靠人工進(jìn)行排序，會耗費大量時間和精力，甚至無法完成。所以， 依靠計算機快速、準(zhǔn)確地對數(shù)據(jù)進(jìn)行排序，是很有必要的。
5 . 3 . 1 　認(rèn)識排序
1．排序
排序是指把一個任意序列的數(shù)據(jù)元素重新排列成按照某關(guān)鍵字遞增或遞減序列的過程。作為排序依據(jù)的數(shù)據(jù)項稱為排序關(guān)鍵字，簡稱關(guān)鍵字（Key）。排序時選取哪一個數(shù)據(jù)項作為關(guān)鍵字，應(yīng)根據(jù)具體情況而定。
2．排序的分類
假定在待排序的序列中，存在多個具有相同鍵值的數(shù)據(jù)元素，若經(jīng)過排序，這些數(shù)據(jù)
元素的相對次序仍然保持不變，則稱這種排序是穩(wěn)定的排序；否則，稱這種排序是不穩(wěn)定的排序。例如以表5-3中的“銷售數(shù)量”來排列名次：
待排序的序列：25　10　17　13　10　37　6　//給其中一個“10”加底色以區(qū)分
穩(wěn)定的排序：6　10　10　13　17　25　37　//因為10還是在 10 的前面
不穩(wěn)定的排序：6　10　10　13　17　25　37　//因為10已在 10 的后面
在排序過程中，可以使用內(nèi)存儲器，也可以使用外存儲器。如果參加排序的數(shù)據(jù)元素
的數(shù)量不多，能夠全部調(diào)入內(nèi)存中進(jìn)行排序，則稱這種排序為內(nèi)部排序；若參加排序的數(shù)據(jù)元素的數(shù)量較大，需要分批調(diào)入內(nèi)存中進(jìn)行排序，排序后再分批存回外存儲器，則稱這種排序為外部排序。
2．排序的分類
內(nèi)部排序的方法很多，按照排序過程中所用策略的不同，通常分為五大類：
插入排序、選擇排序、交換排序、歸并排序和基數(shù)排序。
其中，交換排序又包含冒泡排序和快速排序，都是常用的排序算法。冒泡排序是一種簡單、常見的排序算法，適合初學(xué)者學(xué)習(xí)；快速排序是對冒泡排序的改進(jìn)，它是目前內(nèi)部排序中平均速度最快的排序算法，也是20世紀(jì)十大算法之一。
3．排序的存儲結(jié)構(gòu)
排序的方法很多，通常都要進(jìn)行兩種基本操作：
（1）比較兩個元素關(guān)鍵字的大小。
（2）根據(jù)比較結(jié)果，將元素從一個位置移到另一個位置。
其中，第（1）種操作對大多數(shù)排序方法來說都是必要的，第（2）種操作可通過改變元素的存儲方式，比如采用鏈表存儲結(jié)構(gòu)存儲的數(shù)據(jù)元素。
從操作角度看，排序是線性結(jié)構(gòu)的一種操作，待排序元素可以用順序存儲結(jié)構(gòu)和鏈
式存儲結(jié)構(gòu)來存儲。
在順序存儲結(jié)構(gòu)中，待排序元素按自然順序存放在連續(xù)的一塊內(nèi)存空間中，元素之間的次序關(guān)系由其存儲位置決定，所以排序過程中一定要移動元素；在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，待排序元素按原始次序鏈接起來，排序時只需要修改鏈表指針，不用移動元素。
5 . 3 . 2 　 冒泡排序
冒泡排序（Bubble Sort）是一種簡單的交換排序算法，它是通過交換相鄰的兩個數(shù)據(jù)元素，逐步將待排序列變成有序序列。它的基本思想如下：
（1）假設(shè)待排序元素有n個，從第一個元素開始，依次交換相鄰的兩個逆序元素，直到最后一個元素為止，當(dāng)?shù)谝惶伺判蚪Y(jié)束，就會將最大（?。┑脑匾苿拥叫蛄械哪┪病?br/>（2）然后按照以上方法進(jìn)行第二趟排序，次大（?。┑脑貙灰苿拥叫蛄械牡箶?shù)第二個位置。
（3）依次類推，經(jīng)過n-1趟排序后，整個元素序列就成了一個有序（升序或降序）的序列。
每趟排序過程中，值小（大）的元素向前移動，值大（?。┑脑叵蚝笠苿?，就像氣泡一樣向上升，因此將這種排序方法稱為冒泡排序。
最少比較n-1次，最多比較n（n-1）/2次
次數(shù)？
例5：假設(shè)有五個元素的待排序列為25、10、17、37、13，將此序列按升序排序的冒泡排序過程如圖5-7所示。
例5：假設(shè)有五個元素的待排序列為25、10、17、37、13，將此序列按升序排序的冒泡排序過程如圖5-7所示。
5 . 3 . 3 　 快速排序
1．快速排序的基本思想
快速排序采用分治法的策略：將原問題劃分成規(guī)模更小但與原問題相似的小問題，然后用遞歸法解決這些小問題，最后將它們組合形成原問題的解。
以關(guān)鍵字升序排列為例，設(shè)待排序列存放在數(shù)組a[1..n]中，n為元素個數(shù)， i、j分別是
待排序列首尾關(guān)鍵字的下標(biāo)，初值分別為1和n，令a[1]作為基準(zhǔn)元素賦給pivotkey：
（1）j從右往左掃描，若i= pivotkey，j=j-1，否則將a[j]與a[i]交換。
（2）i從左往右掃描，若i（3）重復(fù)執(zhí)行（1）和（2），直到出現(xiàn)i≥j，則將基準(zhǔn)元素pivotkey移動到a[i]中。此時整個元素序列在位置i被劃分成兩個部分，前一部分的元素關(guān)鍵字都小于或等于a[i].key，后一部分元素的關(guān)鍵字都等于或大于a[i].key，即完成了一趟快速排序。
（4）繼續(xù)對分割后的子表進(jìn)行上述劃分，直至所有子表的表長不超過1為止，此時的
元素序列就成了一個有序序列。
5 . 3 . 3 　 快速排序
例6：假設(shè)待排序列為39，26，54，83，91，47，18，32，用快速排序算法對該序列
進(jìn)行升序排序，第一趟快速排序的過程如圖5-8所示，快速排序的全部過程如圖5-9所示。
選擇法
選擇排序就是從a[0]開始依次和后面的元素進(jìn)行比較，第一遍把a[0]及其以后中最小的篩選出來并將值賦給a[0]，第二遍把a[1]及其以后中最小的篩選出來并賦值，依次類推，內(nèi)層循環(huán)的j=i+1是為了不讓a[i]和本身比較而浪費時間,選擇排序法是每個元素都要和比自己大的元素進(jìn)行一次比較?？傊簝?nèi)循環(huán)每循環(huán)完一次就會就把最小的值給相應(yīng)的a[i]

展開更多......

收起↑