DS02_實現(xiàn)基礎_陳越主編_數(shù)據(jù)結構

1、第第2章章 實現(xiàn)基礎實現(xiàn)基礎 2.1 引子引子 還是還是為每個具體應用都編一個程序為每個具體應用都編一個程序? 類型名稱：類型名稱：數(shù)據(jù)集合的基本統(tǒng)計數(shù)據(jù)集合的基本統(tǒng)計 數(shù)據(jù)對象集：數(shù)據(jù)對象集：集合集合S= ， ， 操作集操作集：ElementType Average(S)：求：求S中元素的平均值；中元素的平均值；ElementType Max(S)：求：求S中元素的最大值；中元素的最大值；ElementType Min(S)：求：求S中元素的最小值；中元素的最小值；1. ElementType Median(S)：求：求S中元素的中位數(shù)。中元素的中位數(shù)。 從不同的從不同的應用中應用中抽象出共

2、性的數(shù)據(jù)組織與操作方法？抽象出共性的數(shù)據(jù)組織與操作方法？例例2.1 在日常數(shù)據(jù)處理中經常碰到的問題是需要對在日常數(shù)據(jù)處理中經常碰到的問題是需要對一組數(shù)據(jù)一組數(shù)據(jù)進進行基本的統(tǒng)計分析。比如，分析一個課程班學生的平均成績、行基本的統(tǒng)計分析。比如，分析一個課程班學生的平均成績、最最高成績、最低成績、中位數(shù)、標準差高成績、最低成績、中位數(shù)、標準差等。同樣的統(tǒng)計要求也可能等。同樣的統(tǒng)計要求也可能發(fā)生在其他領域發(fā)生在其他領域。1/251x2xNx 如何利用程序設計語言實現(xiàn)上述抽象類型？如何利用程序設計語言實現(xiàn)上述抽象類型？第第2章章 實現(xiàn)基礎實現(xiàn)基礎 2.1 引子引子1. 數(shù)據(jù)存儲數(shù)據(jù)存儲 C語言（包括其

3、他高級語言）提供了語言（包括其他高級語言）提供了數(shù)組、結構、鏈表數(shù)組、結構、鏈表等。等。 數(shù)據(jù)結構的數(shù)據(jù)結構的存儲實現(xiàn)存儲實現(xiàn)跟所需要的跟所需要的操作密切相關操作密切相關。 在數(shù)據(jù)結構里，是在數(shù)據(jù)結構里，是利用數(shù)組和鏈表方式來實現(xiàn)利用數(shù)組和鏈表方式來實現(xiàn)的，包括很復雜的，包括很復雜的數(shù)據(jù)結構，如的數(shù)據(jù)結構，如圖、樹圖、樹等。等。2. 操作實現(xiàn)操作實現(xiàn)流程控制語句，即流程控制語句，即分支控制語句分支控制語句（如（如if-else、switch語句）、語句）、循環(huán)控制語句循環(huán)控制語句（如（如for、while、do-while語句）。語句）。 此外，還有模塊化的程序設計方法此外，還有模塊化的程序設

4、計方法函數(shù)函數(shù)ElementType Average(ElementType S, int N)/* 求集合元素的平均值。集合元素存放在數(shù)組求集合元素的平均值。集合元素存放在數(shù)組S中，數(shù)組大小為中，數(shù)組大小為N */ int i; ElementType Sum=0; for(i = 0; i= e元素元素 e 當當K = N1時，時， 第第K大整數(shù)就是大整數(shù)就是e。 當當K N1 時，時，第第K大整數(shù)大整數(shù)是是在在S2中中的第的第(K-N1)大整數(shù)大整數(shù)。 比較慢！比較慢！3/25ElementType KthLargest( ElementType S, int K) 選取選取S中的第一個

5、元素中的第一個元素e;根據(jù)根據(jù)e將集合將集合S分解為大于等于分解為大于等于e 的元素集合的元素集合S1和小于和小于e的元素集合的元素集合S2; while (|S2| =0 ) 另選一個另選一個 e;if (|S1|K) return KthLargest(S1，K);else if (|S1|K) return KthLargest(S2，K-|S1|);else return e; 例例2.2 求集合求集合 6 5 9 8 2 1 7 3 4 的中位數(shù)的中位數(shù)?！痉治龇治觥坑捎谠摷嫌杏捎谠摷嫌?個元素，所以中位數(shù)應該是集合從大到個元素，所以中位數(shù)應該是集合從大到小排序后的第小排序后的第

6、 9/2 = 5個元素。個元素。 首先，選取集合的第一個元素首先，選取集合的第一個元素6，根據(jù)這個元素從集合中分解出，根據(jù)這個元素從集合中分解出S1=6，9，8，7，S2=5，2，1，3，4。 由于由于|S1|=45，所以該中位數(shù)應該在集合，所以該中位數(shù)應該在集合S2中，且是中，且是S2中第中第(5 4 =1)大整數(shù)。大整數(shù)。 繼續(xù)選取繼續(xù)選取S2中的第一個整數(shù)中的第一個整數(shù)5，將，將S2分解出兩個集合分解出兩個集合S1=5，S2=2,1,3,4。由于由于|S1|=1，所以，所以5就是就是S2集合的第集合的第1大整數(shù)，也就是集合大整數(shù)，也就是集合6 5 9 8 2 1 7 3 4的中位數(shù)。的中

7、位數(shù)。第第2章章 實現(xiàn)基礎實現(xiàn)基礎 1 引子引子4/25第第2章章 實現(xiàn)基礎實現(xiàn)基礎 2 數(shù)據(jù)存儲基礎數(shù)據(jù)存儲基礎 變量變量是數(shù)據(jù)存儲的基本單位。變量的類型決定了是數(shù)據(jù)存儲的基本單位。變量的類型決定了存儲和操作存儲和操作。 幾種基本的數(shù)據(jù)類型：幾種基本的數(shù)據(jù)類型：整型、實型（浮點型）、字符型整型、實型（浮點型）、字符型等。等。 提供了構造數(shù)據(jù)類型：提供了構造數(shù)據(jù)類型：數(shù)組、結構、指針數(shù)組、結構、指針等。等。數(shù)組數(shù)組數(shù)組是最基本的構造類型，它是數(shù)組是最基本的構造類型，它是一組相同類型數(shù)據(jù)一組相同類型數(shù)據(jù)的有序集合。的有序集合。數(shù)組中的元素在內存中數(shù)組中的元素在內存中連續(xù)存放連續(xù)存放，用數(shù)組名和下

8、標可以唯一地，用數(shù)組名和下標可以唯一地確定數(shù)組元素。確定數(shù)組元素。例例2.3 求集合元素的最大值。集合元素存放在數(shù)組求集合元素的最大值。集合元素存放在數(shù)組A中，數(shù)組大小中，數(shù)組大小為為N。float Max(float A, int N) /* 求求N個元素數(shù)組中的最大值個元素數(shù)組中的最大值 */ float CurMax = A0; int i; for(i=1; i CurMax) CurMax =Ai; return CurMax;5/25指針指針第第2章章 實現(xiàn)基礎實現(xiàn)基礎 2 數(shù)據(jù)存儲基礎數(shù)據(jù)存儲基礎 指針指針是是C語言中一個非常重要的概念。使用指針可以對語言中一個非常重要的概念。使

9、用指針可以對復雜數(shù)復雜數(shù)據(jù)據(jù)進行處理，能對計算機的進行處理，能對計算機的內存進行分配內存進行分配控制，在函數(shù)調用中使用控制，在函數(shù)調用中使用指針還可以指針還可以返回多個值返回多個值。 指針與數(shù)組指針與數(shù)組 數(shù)組名數(shù)組名是數(shù)組中第是數(shù)組中第1個元素（下標為個元素（下標為0）的地址，可以看作是）的地址，可以看作是常量常量指針指針，不能改變指針常量（數(shù)組名）的值。，不能改變指針常量（數(shù)組名）的值。 用指針實現(xiàn)內存動態(tài)分配用指針實現(xiàn)內存動態(tài)分配 分配函數(shù)分配函數(shù) void *malloc(unsigned size) 。 釋放函數(shù)釋放函數(shù)void free(void *ptr) 。6/25 結構結構結

10、構類型定義的一般形式為：結構類型定義的一般形式為：struct 結構名結構名 類型名類型名 結構成員名結構成員名1; 類型名類型名 結構成員名結構成員名2; 類型名類型名 結構成員名結構成員名n;第第2章章 實現(xiàn)基礎實現(xiàn)基礎 2 數(shù)據(jù)存儲基礎數(shù)據(jù)存儲基礎【定義定義】結構類型把一些可以是不同類型的結構類型把一些可以是不同類型的數(shù)據(jù)分量聚合數(shù)據(jù)分量聚合成一個整體。成一個整體。同時，結構又是一個同時，結構又是一個變量的集合變量的集合，可以單獨使用其變量成員。，可以單獨使用其變量成員。結構變量的使用結構變量的使用使用結構變量就是對其成員進行操作。使用結構變量就是對其成員進行操作。格式為：格式為：結構變

11、量名結構變量名.結構成員名結構成員名。此。此外，外，結構變量不僅可以作為函數(shù)參數(shù)，結構變量不僅可以作為函數(shù)參數(shù)，也可以作為函數(shù)的返回值。也可以作為函數(shù)的返回值。結構數(shù)組：結構與數(shù)組的結合結構數(shù)組：結構與數(shù)組的結合結構指針結構指針：指向結構的指針：指向結構的指針（1）用）用*方式訪問，形式：（方式訪問，形式：（*結構指針變量名結構指針變量名 ）.結構成員名結構成員名（2）用指向運算符）用指向運算符“-”訪問指針指向的結構成員，形式：訪問指針指向的結構成員，形式： 結構指針變量名結構指針變量名-結構成員名結構成員名對結構數(shù)組元素成員的引用是通過使用數(shù)組下標與結構成員操作符對結構數(shù)組元素成員的引用是

12、通過使用數(shù)組下標與結構成員操作符“.”相結合的方式來完成的，其一般格式為：相結合的方式來完成的，其一般格式為：結構數(shù)組名結構數(shù)組名下標下標.結構成員名結構成員名7/25共用體共用體【定義定義】共用體類型是指將共用體類型是指將不同的數(shù)據(jù)項不同的數(shù)據(jù)項組織成一個整體，組織成一個整體，它們在它們在內存中占用同一段存儲單元。內存中占用同一段存儲單元。第第2章章 實現(xiàn)基礎實現(xiàn)基礎 2 數(shù)據(jù)存儲基礎數(shù)據(jù)存儲基礎共用體共用體類型定義的一般形式為：類型定義的一般形式為：union共用體共用體名名 類型名類型名 成員名成員名1; 類型名類型名 成員名成員名2; 類型名類型名 成員名成員名n; 各個成員變量在內存

13、中都使用各個成員變量在內存中都使用同一段同一段存儲空間存儲空間，因此共用體變量的長度等于，因此共用體變量的長度等于最長的成員的長度最長的成員的長度。 共用體的訪問方式同結構體類似。共用體的訪問方式同結構體類似。int main() union key int k; char ch2; u;u.k = 258;printf(%d %dn, u.ch0,u.ch1);return 0;0000001000000001 u.k=258的二進制表示：的二進制表示：u.ch0 = 2u.ch1 = 18/25 鏈表鏈表 鏈表鏈表是一種重要的基礎數(shù)據(jù)結構，也是實現(xiàn)是一種重要的基礎數(shù)據(jù)結構，也是實現(xiàn)復雜數(shù)據(jù)

14、結構復雜數(shù)據(jù)結構的重的重要手段。它不按照線性的順序存儲數(shù)據(jù)，而是由若干個同一結構類要手段。它不按照線性的順序存儲數(shù)據(jù)，而是由若干個同一結構類型的型的“結點結點”依次串接而成的，即每一個結點里保存著依次串接而成的，即每一個結點里保存著下一個結點下一個結點的地址的地址（指針指針）。 鏈表鏈表又分又分單向鏈表單向鏈表，雙向鏈表雙向鏈表以及以及循環(huán)鏈表循環(huán)鏈表等。等。單向鏈表的結構單向鏈表的結構headABCDNULL使用結構的使用結構的嵌套嵌套來定義來定義單向鏈表結點單向鏈表結點的數(shù)據(jù)類型。如：的數(shù)據(jù)類型。如：struct Node ElementType Data; struct Node *Ne

15、xt;第第2章章 實現(xiàn)基礎實現(xiàn)基礎 2 數(shù)據(jù)存儲基礎數(shù)據(jù)存儲基礎struct Node *p;p = (struct Node *) malloc(sizeof(struct Node);(*p).data=A9/25head（1）插入結點插入結點 ( p之后插入新結點之后插入新結點t )單向鏈表的常見操作單向鏈表的常見操作（2）刪除結點刪除結點 第第2章章 實現(xiàn)基礎實現(xiàn)基礎 2 數(shù)據(jù)存儲基礎數(shù)據(jù)存儲基礎ptt-Next = p-Next;p-Next = t; headpt = p-Next;p-Next = t-next; 10/25（3） 單向鏈表的遍歷單向鏈表的遍歷 p = head;

16、while (p!=NULL) 處理處理p所指的結點信息；所指的結點信息； p = p-Next;（4）鏈表的建立鏈表的建立 有兩種常見的插入結點方式：有兩種常見的插入結點方式：（1）在鏈表的）在鏈表的頭上頭上不斷插入新結點；不斷插入新結點；（2）在鏈表的）在鏈表的尾部尾部不斷插入新結點。不斷插入新結點。如果是后者，一般需要有一個如果是后者，一般需要有一個臨時的結點指針臨時的結點指針一直指一直指向當前鏈表的最后一個結點，以方便新結點的插入。向當前鏈表的最后一個結點，以方便新結點的插入。第第2章章 實現(xiàn)基礎實現(xiàn)基礎 2 數(shù)據(jù)存儲基礎數(shù)據(jù)存儲基礎11/25雙向鏈表雙向鏈表 如果將如果將雙向鏈表雙向

17、鏈表最后一個單元的最后一個單元的Next指針指向鏈表的第一個單指針指向鏈表的第一個單元，而第一個單元的元，而第一個單元的Previous指針指向鏈表的最后一個單元，這指針指向鏈表的最后一個單元，這樣構成的鏈表稱為樣構成的鏈表稱為雙向循環(huán)鏈表。雙向循環(huán)鏈表。第第2章章 實現(xiàn)基礎實現(xiàn)基礎 2 數(shù)據(jù)存儲基礎數(shù)據(jù)存儲基礎struct Node ElementType Data; struct Node *Next; struct Node * Previous;12/25 雙向鏈表的插入、刪除和遍歷基本思路與單向鏈表相同，但雙向鏈表的插入、刪除和遍歷基本思路與單向鏈表相同，但需要同時考慮需要同時考慮前

18、后兩個指針前后兩個指針。A1A2A3ANheadpt第第2章章 實現(xiàn)基礎實現(xiàn)基礎 2 數(shù)據(jù)存儲基礎數(shù)據(jù)存儲基礎struct DNode ElementType Data;struct DNode *Next;struct DNode *Previous; *p,*t;指針操作順序：指針操作順序： t-Previous = p; t-Next = p-Next; p-Next-Previous = t; p-Next = t; 13/25例例2.4 給定一個單鏈表給定一個單鏈表L，請設計函數(shù)，請設計函數(shù)Reverse將鏈表將鏈表L就地逆轉就地逆轉，即，即不需要申請新的結點，將鏈表的第一個元素轉為

19、最后一個元素，第二不需要申請新的結點，將鏈表的第一個元素轉為最后一個元素，第二個元素轉為倒數(shù)第二個元素個元素轉為倒數(shù)第二個元素【分析分析】 基本思路是：基本思路是： 利用利用循環(huán)循環(huán)，從鏈表頭開始逐個處理。，從鏈表頭開始逐個處理。 如何把握住如何把握住循環(huán)不變式循環(huán)不變式。（循環(huán)不變式表示一種在循環(huán)過程進行時。（循環(huán)不變式表示一種在循環(huán)過程進行時不變的性質，不變的性質，不依賴于前面所執(zhí)行過程的重復次數(shù)的斷言不依賴于前面所執(zhí)行過程的重復次數(shù)的斷言。）。） 在每輪循環(huán)開始前我們都面臨兩個序列，其中在每輪循環(huán)開始前我們都面臨兩個序列，其中p是一個待逆轉的序是一個待逆轉的序列列，而，而q是一個已經逆轉

20、好的序列是一個已經逆轉好的序列，如下圖。，如下圖。 每輪循環(huán)的目的是把每輪循環(huán)的目的是把p中的第一個元素插入到中的第一個元素插入到q的頭的頭上，使這輪循環(huán)上，使這輪循環(huán)執(zhí)行好后，執(zhí)行好后，p和和 q還是分別指向新的待逆轉序列和已經逆轉好的序列。還是分別指向新的待逆轉序列和已經逆轉好的序列。第第2章章 實現(xiàn)基礎實現(xiàn)基礎 2 數(shù)據(jù)存儲基礎數(shù)據(jù)存儲基礎p-Next = q;q = p;tqpt = p-Next;p-Next = q;q = p;p = t; struct Node *Reverse(struct Node *L) struct Node *p, *q, *t; p = L，q =

21、NULL; while ( p != NULL ) t = p-Next; p-Next = q; q = p; p = t; return q;14/25 類型定義類型定義typedef第第2章章 實現(xiàn)基礎實現(xiàn)基礎 2 數(shù)據(jù)存儲基礎數(shù)據(jù)存儲基礎 除了使用除了使用C語言提供的標準類型和自己定義的一些結構體、枚舉等類語言提供的標準類型和自己定義的一些結構體、枚舉等類型外，還可以型外，還可以用用typedef語句來建立已經定義好的數(shù)據(jù)類型的別名。語句來建立已經定義好的數(shù)據(jù)類型的別名。typedef 原有類型名原有類型名 新類型名新類型名typedef struct Node * NodePtr;這

22、樣，這樣，Reverse函數(shù)頭就可以寫成：函數(shù)頭就可以寫成：NodePtr Reverse( NodePtr L )NodePtr Reverse( NodePtr L )/* struct Node *Reverse(struct Node *L) */ struct Node *p, *q, *t; p = L，q = NULL; while ( p != NULL ) t = p-Next; p-Next = q; q = p; p = t; return q;15/25第第2章章 實現(xiàn)基礎實現(xiàn)基礎 3 流程控制基礎流程控制基礎 順序結構是一種自然的控制結構，通過安排順序結構是一種自然的

23、控制結構，通過安排語句語句或模塊的順序或模塊的順序就能實現(xiàn)。就能實現(xiàn)。 C語言為分支控制提供了語言為分支控制提供了if-else和和switch兩類語句，兩類語句， 為循環(huán)控制提供了為循環(huán)控制提供了for、while和和do-while三類語句。三類語句。 三種基本的控制結構是三種基本的控制結構是順序、分支和循環(huán)順序、分支和循環(huán)。 函數(shù)定義函數(shù)定義 函數(shù)調用函數(shù)調用 函數(shù)遞歸函數(shù)遞歸語句級控制語句級控制單位級控制單位級控制16/25例例2.5 求求100到到200之間的所有素數(shù)。之間的所有素數(shù)。分析分析 可以設定兩重循環(huán)：大循環(huán)（外層循環(huán)）控制整數(shù)可以設定兩重循環(huán)：大循環(huán)（外層循環(huán)）控制整數(shù)i

24、在在100到到200之間變化（用之間變化（用for語句），而小循環(huán)（內層循環(huán)）則用語句），而小循環(huán)（內層循環(huán)）則用來判別來判別i是否是素數(shù)（用是否是素數(shù)（用while語句）。語句）。第第2章章 實現(xiàn)基礎實現(xiàn)基礎 3 流程控制基礎流程控制基礎int main() int i, j; for( i = 100; i = 200; i+ ) /* 外層循環(huán)外層循環(huán)*/ j = 2; while (j i & i%j != 0 ) j+; /* 內層循環(huán)內層循環(huán),判別判別i是否是素數(shù)是否是素數(shù)*/ if (j = i) printf(“%d ”, i); /* j = i 說明說明在上面的在上

25、面的while循環(huán)中循環(huán)中i都不能被都不能被j整除，因此整除，因此i是素數(shù)是素數(shù) */ return 0;17/25 函數(shù)與遞歸函數(shù)與遞歸比如：比如：C語言提供了實數(shù)和整數(shù)的加語言提供了實數(shù)和整數(shù)的加法運算符號法運算符號“+”來完成運算；來完成運算；但是但是“+”不能對復數(shù)做加法運算；不能對復數(shù)做加法運算；可以寫可以寫一個函數(shù)一個函數(shù)來實現(xiàn)這個功能。來實現(xiàn)這個功能。第第2章章 實現(xiàn)基礎實現(xiàn)基礎 3 流程控制基礎流程控制基礎 【定義定義】函數(shù)函數(shù)是一個完成特定工作的是一個完成特定工作的獨立程序模塊獨立程序模塊。 只需只需定義一次定義一次，就可以，就可以多次調用多次調用。 函數(shù)包括函數(shù)包括庫函數(shù)庫

26、函數(shù)和和自定義函數(shù)自定義函數(shù)兩種。例如，兩種。例如，scanf、printf等庫函數(shù)由等庫函數(shù)由C語言系統(tǒng)提供定義，編程時只要直接調用即可。語言系統(tǒng)提供定義，編程時只要直接調用即可。 在程序設計中，往往根據(jù)模塊化程序設計的需要，用戶可以自己定義在程序設計中，往往根據(jù)模塊化程序設計的需要，用戶可以自己定義函數(shù)，屬于自定義函數(shù)。函數(shù)，屬于自定義函數(shù)。先定義復數(shù)類型先定義復數(shù)類型 ImgType，以約定，以約定何為復數(shù)：何為復數(shù)：struct Image double r; double i; ;typedef struct Image ImgType; 再定義復數(shù)的加法函數(shù)：再定義復數(shù)的加法函數(shù)：

27、ImgType ImgAdd(ImgType a, ImgType b) ImgType c; c.r = a.r + b.r; c.i = a.i + b.i; /* 實部和虛部分別相加實部和虛部分別相加 */ return c;有了這個函數(shù)，以有了這個函數(shù)，以后可以在任何需要后可以在任何需要計算復數(shù)加法的地計算復數(shù)加法的地方調用它！方調用它！18/25 在設計函數(shù)時，注意掌握以下原則：在設計函數(shù)時，注意掌握以下原則：第第2章章 實現(xiàn)基礎實現(xiàn)基礎 3 流程控制基礎流程控制基礎（1）函數(shù)）函數(shù)功能的設計原則功能的設計原則：結合模塊的獨立性原則，函數(shù)的：結合模塊的獨立性原則，函數(shù)的功功能要單一能

28、要單一，不要設計多用途的函數(shù)，否則會降低模塊的聚合度；，不要設計多用途的函數(shù)，否則會降低模塊的聚合度； （2）函數(shù)）函數(shù)規(guī)模的設計規(guī)模的設計原則：函數(shù)的原則：函數(shù)的規(guī)模要小規(guī)模要小，盡量控制在，盡量控制在50行行代碼以內，這樣可以使得函數(shù)更易于維護；代碼以內，這樣可以使得函數(shù)更易于維護；（3）函數(shù)）函數(shù)接口的設計接口的設計原則：結合模塊的獨立性原則，函數(shù)的接原則：結合模塊的獨立性原則，函數(shù)的接口包括函數(shù)的參數(shù)（入口）和返回值（出口），口包括函數(shù)的參數(shù)（入口）和返回值（出口），不要設計過于不要設計過于復雜的接口復雜的接口，合理選擇、設置并控制參數(shù)的數(shù)量，盡量不要使，合理選擇、設置并控制參數(shù)的數(shù)量

29、，盡量不要使用全局變量，否則會增加模塊的耦合度。用全局變量，否則會增加模塊的耦合度。19/25 遞歸函數(shù)遞歸函數(shù)【定義定義】一個函數(shù)除了可以調用其他函數(shù)外，一個函數(shù)除了可以調用其他函數(shù)外，C語言還支持語言還支持函數(shù)函數(shù)直接或間接調用自己直接或間接調用自己。這種函數(shù)自己調用自己的形式稱為。這種函數(shù)自己調用自己的形式稱為函數(shù)的函數(shù)的遞歸調用遞歸調用，帶有遞歸調用的函數(shù)也稱為，帶有遞歸調用的函數(shù)也稱為遞歸函數(shù)遞歸函數(shù)。 兩個關鍵點：兩個關鍵點：（1）遞歸出口遞歸出口：即遞歸的結束條件，到何時不再遞歸調用下去：即遞歸的結束條件，到何時不再遞歸調用下去;第第2章章 實現(xiàn)基礎實現(xiàn)基礎 2.3 流程控制基礎

30、流程控制基礎（2）遞歸式子遞歸式子：當前函數(shù)結果與準備調用的函數(shù)結果之間的關：當前函數(shù)結果與準備調用的函數(shù)結果之間的關系，如求階乘函數(shù)的遞歸式子系，如求階乘函數(shù)的遞歸式子 Factorial(n) = n* Factorial(n-1)long int Factorial( int n )if( n = 0 ) return 1;e l s e r e t u r n n * Factorial(n-1);注意：程序代碼不能寫成上述式子！注意：程序代碼不能寫成上述式子！遞歸調用遞歸調用20/25例例2.8 設計函數(shù)求設計函數(shù)求n!圖圖2.7 遞歸求解遞歸求解4!的過程的過程第第2章章 實現(xiàn)基礎

31、實現(xiàn)基礎 2.3 流程控制基礎流程控制基礎long int Factorial( int n )if( n = 0 ) return 1;e l s e r e t u r n n * Factorial(n-1);遞歸出口遞歸出口遞歸式子遞歸式子Factorial(4)4 Factorial (3)3 Factorial (2)2 Factorial (1)1 Factorial (0)11262421/25例例2.9 漢諾塔（漢諾塔（Tower of Hanoi）問題）問題132132 （a）初始狀態(tài)）初始狀態(tài) （b）中間狀態(tài)）中間狀態(tài)3 流程控制基礎流程控制基礎第第2章章 實現(xiàn)基礎實現(xiàn)基

32、礎 【分析分析】可以用遞歸方法來求解漢諾塔問題，也就是可以用遞歸方法來求解漢諾塔問題，也就是將將n個金片的移動個金片的移動問題轉換為問題轉換為2個個n-1個金片的移動問題個金片的移動問題。當。當n=1時，就不需要再遞歸了。時，就不需要再遞歸了。void Move(int n, int start, int goal, int temp) if( n = 0 ) return; Move(n-1, start, temp, goal); printf(“Move disk %d from %d to %d.n”, n, start, goal); Move(n-1, temp, goal, st

33、art);遞歸調用遞歸調用22/253 流程控制基礎流程控制基礎第第2章章 實現(xiàn)基礎實現(xiàn)基礎 Move (3,1,3,2)Move (2,1,2,3)Move (1,1,3,2)Move (0,1,2,3)Move (0,2,3,1)Move disk 2 from 1 to 2Move (1,3,2,1)Move (0,3,1,2)Move disk 3 from 1 to 3Move (1,2,1,3)Move (0,1,2,3)Move disk 1 from 3 to 2Move (0,3,1,2)Move (1,1,3,2)Move (0,1,2,3)Move (0,2,3,1)Mo

34、ve (0,2,3,1)Move (2,2,3,1)Move disk 1 from 2 to 1Move disk 1 from 1 to 3Move disk 1 from 1 to 3Move disk 2 from 2 to 323/25例例2.10 用遞歸方法求集合的中位數(shù)。用遞歸方法求集合的中位數(shù)。第第2章章 實現(xiàn)基礎實現(xiàn)基礎 2.3 流程控制基礎流程控制基礎 根據(jù)前面根據(jù)前面求解集合第求解集合第K大整數(shù)問題的大整數(shù)問題的遞歸算法遞歸算法思路思路，還需要解決，還需要解決以下兩個關鍵問題：以下兩個關鍵問題：（1）如何根據(jù)元素）如何根據(jù)元素e將集合將集合S分解為分解為S1和和S2兩個集