數據結構的應用查找和排序，與我們的學習、生活息息相關。如從字典

中查找漢字，從電話號碼本中查找電話，在圖書館中查找圖

書，高考查詢成績等；教師按身高來安排學生的座位，大學

按照高考成績高低順序錄取新生，網上商城按照銷量高低排

序來推薦商品等。在信息時代，數據的增長速度越來越快，

導致信息量呈幾何級的增長。在龐大的數據里進行人工查找和排序是非常困難的，甚至是無法辦到的，所以必須依靠計

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

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

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

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

些特殊情況（遞歸終結條件），再處理遞歸關系。

遞歸函數的執行過程總是先通過遞歸關系不斷地縮小問題的規模，直到簡單到可以作

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

能是不同的。對比順序查找與二分查找算法，當數據量較大時，二分查找會比順序查找快

很多，這是它的主要優點，但它要求查找表是有序的，所以在進行二分查找之前，必須先

對查找表進行排序。另外，二分查找要求表是順序存儲的，為保持表的有序性，在進行插

入、刪除操作時，都必須移動大量記錄。因此，二分查找的高查找效率是以排序為代價

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

了解不同算法的特點，可以幫助我們在解決實際問題時，從不同的算法中選擇出較為

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

假定在待排序的序列中，存在多個具有相同鍵值的數據元素，若經過排序，這些數據元素的相對次序仍然保持不變，則稱這種排序是穩定的排序；否則，稱這種排序是不穩定的排序。例如以表5-3中的“銷售數量”來排列名次：待排序的序列：2510171310376//給其中一個“10”加底色以區分穩定的排序：6101013172537//因為10還是在10的前面不穩定的排序：6101013172537//因為10已在10的后面在排序過程中，可以使用內存儲器，也可以使用外存儲器。如果參加排序的數據元素的數量不多，能夠全部調入內存中進行排序，則稱這種排序為內部排序；若參加排序的數據元素的數量較大，需要分批調入內存中進行排序，排序后再分批存回外存儲器，則稱這種排序為外部排序。2．排序的分類內部排序的方法很多，按照排序過程中所用策略的不同，通常分為五大類：插入排序、選擇排序、交換排序、歸并排序和基數排序。其中，交換排序又包含冒泡排序和快速排序，都是常用的排序算法。冒泡排序是一種簡單、常見的排序算法，適合初學者學習；快速排序是對冒泡排序的改進，它是目前內部排序中平均速度最快的排序算法，也是20世紀十大算法之一。3．排序的存儲結構排序的方法很多，通常都要進行兩種基本操作：（1）比較兩個元素關鍵字的大小。（2）根據比較結果，將元素從一個位置移到另一個位置。其中，第（1）種操作對大多數排序方法來說都是必要的，第（2）種操作可通過改變元素的存儲方式，比如采用鏈表存儲結構存儲的數據元素。從操作角度看，排序是線性結構的一種操作，待排序元素可以用順序存儲結構和鏈式存儲結構來存儲。在順序存儲結構中，待排序元素按自然順序存放在連續的一塊內存空間中，元素之間的次序關系由其存儲位置決定，所以排序過程中一定要移動元素；在鏈式存儲結構中，待排序元素按原始次序鏈接起來，排序時只需要修改鏈表指針，不用移動元素。5.3.2冒泡排序冒泡排序（BubbleSort）是一種簡單的交換排序算法，它是通過交換相鄰的兩個數據元素，逐步將待排序列變成有序序列。它的基本思想如下：（1）假設待排序元素有n個，從第一個元素開始，依次交換相鄰的兩個逆序元素，直到最后一個元素為止，當第一趟排序結束，就會將最大（?。┑脑匾苿拥叫蛄械哪┪?。（2）然后按照以上方法進行第二趟排序，次大（?。┑脑貙灰苿拥叫蛄械牡箶档诙€位置。（3）依次類推，經過n-1趟排序后，整個元素序列就成了一個有序（升序或降序）的序列。每趟排序過程中，值?。ù螅┑脑叵蚯耙苿樱荡螅ㄐ。┑脑叵蚝笠苿樱拖駳馀菀粯酉蛏仙虼藢⑦@種排序方法稱為冒泡排序。最少比較n-1次，最多比較n（n-1）/2次次數？例5：假設有五個元素的待排序列為25、10、17、37、13，將此序列按升序排序的冒泡排序過程如圖5-7所示。例5：假設有五個元素的待排序列為25、10、17、37、13，將此序列按升序排序的冒泡排序過程如圖5-7所示。5.3.3快速排序1．快速排序的基本思想快速排序采用分治法的策略：將原問題劃分成規模更小但與原問題相似的小問題，然后用遞歸法解決這些小問題，最后將它們組合形成原問題的解。以關鍵字升序排列為例，設待排序列存放在數組a[1..n]中，n為元素個數，i、j分別是待排序列首尾關鍵字的下標，初值分別為1