DS02_實(shí)現(xiàn)基礎(chǔ)_陳越主編_數(shù)據(jù)結(jié)構(gòu)

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

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

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

4、計(jì)方法函數(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 當(dāng)當(dāng)K = N1時(shí)，時(shí)， 第第K大整數(shù)就是大整數(shù)就是e。 當(dāng)當(dāng)K N1 時(shí)，時(shí)，第第K大整數(shù)大整數(shù)是是在在S2中中的第的第(K-N1)大整數(shù)大整數(shù)。 比較慢！比較慢！3/25ElementType KthLargest( ElementType S, int K) 選取選取S中的第一個(gè)

5、元素中的第一個(gè)元素e;根據(jù)根據(jù)e將集合將集合S分解為大于等于分解為大于等于e 的元素集合的元素集合S1和小于和小于e的元素集合的元素集合S2; while (|S2| =0 ) 另選一個(gè)另選一個(gè) 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ù)?！痉治龇治觥坑捎谠摷嫌杏捎谠摷嫌?個(gè)元素，所以中位數(shù)應(yīng)該是集合從大到個(gè)元素，所以中位數(shù)應(yīng)該是集合從大到小排序后的第小排序后的第

6、 9/2 = 5個(gè)元素。個(gè)元素。 首先，選取集合的第一個(gè)元素首先，選取集合的第一個(gè)元素6，根據(jù)這個(gè)元素從集合中分解出，根據(jù)這個(gè)元素從集合中分解出S1=6，9，8，7，S2=5，2，1，3，4。 由于由于|S1|=45，所以該中位數(shù)應(yīng)該在集合，所以該中位數(shù)應(yīng)該在集合S2中，且是中，且是S2中第中第(5 4 =1)大整數(shù)。大整數(shù)。 繼續(xù)選取繼續(xù)選取S2中的第一個(gè)整數(shù)中的第一個(gè)整數(shù)5，將，將S2分解出兩個(gè)集合分解出兩個(gè)集合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章章 實(shí)現(xiàn)基礎(chǔ)實(shí)現(xiàn)基礎(chǔ) 1 引子引子4/25第第2章章 實(shí)現(xiàn)基礎(chǔ)實(shí)現(xiàn)基礎(chǔ) 2 數(shù)據(jù)存儲(chǔ)基礎(chǔ)數(shù)據(jù)存儲(chǔ)基礎(chǔ) 變量變量是數(shù)據(jù)存儲(chǔ)的基本單位。變量的類型決定了是數(shù)據(jù)存儲(chǔ)的基本單位。變量的類型決定了存儲(chǔ)和操作存儲(chǔ)和操作。 幾種基本的數(shù)據(jù)類型：幾種基本的數(shù)據(jù)類型：整型、實(shí)型（浮點(diǎn)型）、字符型整型、實(shí)型（浮點(diǎn)型）、字符型等。等。 提供了構(gòu)造數(shù)據(jù)類型：提供了構(gòu)造數(shù)據(jù)類型：數(shù)組、結(jié)構(gòu)、指針數(shù)組、結(jié)構(gòu)、指針等。等。數(shù)組數(shù)組數(shù)組是最基本的構(gòu)造類型，它是數(shù)組是最基本的構(gòu)造類型，它是一組相同類型數(shù)據(jù)一組相同類型數(shù)據(jù)的有序集合。的有序集合。數(shù)組中的元素在內(nèi)存中數(shù)組中的元素在內(nèi)存中連續(xù)存放連續(xù)存放，用數(shù)組名和下

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

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

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

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

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

13、中都使用各個(gè)成員變量在內(nèi)存中都使用同一段同一段存儲(chǔ)空間存儲(chǔ)空間，因此共用體變量的長(zhǎng)度等于，因此共用體變量的長(zhǎng)度等于最長(zhǎng)的成員的長(zhǎng)度最長(zhǎng)的成員的長(zhǎng)度。 共用體的訪問方式同結(jié)構(gòu)體類似。共用體的訪問方式同結(jié)構(gòu)體類似。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的二進(jìn)制表示：的二進(jìn)制表示：u.ch0 = 2u.ch1 = 18/25 鏈表鏈表 鏈表鏈表是一種重要的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，也是實(shí)現(xiàn)是一種重要的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，也是實(shí)現(xiàn)復(fù)雜數(shù)據(jù)

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

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

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

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

18、后兩個(gè)指針前后兩個(gè)指針。A1A2A3ANheadpt第第2章章 實(shí)現(xiàn)基礎(chǔ)實(shí)現(xiàn)基礎(chǔ) 2 數(shù)據(jù)存儲(chǔ)基礎(chǔ)數(shù)據(jù)存儲(chǔ)基礎(chǔ)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 給定一個(gè)單鏈表給定一個(gè)單鏈表L，請(qǐng)?jiān)O(shè)計(jì)函數(shù)，請(qǐng)?jiān)O(shè)計(jì)函數(shù)Reverse將鏈表將鏈表L就地逆轉(zhuǎn)就地逆轉(zhuǎn)，即，即不需要申請(qǐng)新的結(jié)點(diǎn)，將鏈表的第一個(gè)元素轉(zhuǎn)為

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

20、好的序列是一個(gè)已經(jīng)逆轉(zhuǎn)好的序列，如下圖。，如下圖。 每輪循環(huán)的目的是把每輪循環(huán)的目的是把p中的第一個(gè)元素插入到中的第一個(gè)元素插入到q的頭的頭上，使這輪循環(huán)上，使這輪循環(huán)執(zhí)行好后，執(zhí)行好后，p和和 q還是分別指向新的待逆轉(zhuǎn)序列和已經(jīng)逆轉(zhuǎn)好的序列。還是分別指向新的待逆轉(zhuǎn)序列和已經(jīng)逆轉(zhuǎn)好的序列。第第2章章 實(shí)現(xiàn)基礎(chǔ)實(shí)現(xiàn)基礎(chǔ) 2 數(shù)據(jù)存儲(chǔ)基礎(chǔ)數(shù)據(jù)存儲(chǔ)基礎(chǔ)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章章 實(shí)現(xiàn)基礎(chǔ)實(shí)現(xiàn)基礎(chǔ) 2 數(shù)據(jù)存儲(chǔ)基礎(chǔ)數(shù)據(jù)存儲(chǔ)基礎(chǔ) 除了使用除了使用C語(yǔ)言提供的標(biāo)準(zhǔn)類型和自己定義的一些結(jié)構(gòu)體、枚舉等類語(yǔ)言提供的標(biāo)準(zhǔn)類型和自己定義的一些結(jié)構(gòu)體、枚舉等類型外，還可以型外，還可以用用typedef語(yǔ)句來建立已經(jīng)定義好的數(shù)據(jù)類型的別名。語(yǔ)句來建立已經(jīng)定義好的數(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章章 實(shí)現(xiàn)基礎(chǔ)實(shí)現(xiàn)基礎(chǔ) 3 流程控制基礎(chǔ)流程控制基礎(chǔ) 順序結(jié)構(gòu)是一種自然的控制結(jié)構(gòu)，通過安排順序結(jié)構(gòu)是一種自然的

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

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

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

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

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

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

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

30、流程控制基礎(chǔ)（2）遞歸式子遞歸式子：當(dāng)前函數(shù)結(jié)果與準(zhǔn)備調(diào)用的函數(shù)結(jié)果之間的關(guān)：當(dāng)前函數(shù)結(jié)果與準(zhǔn)備調(diào)用的函數(shù)結(jié)果之間的關(guān)系，如求階乘函數(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);注意：程序代碼不能寫成上述式子！注意：程序代碼不能寫成上述式子！遞歸調(diào)用遞歸調(diào)用20/25例例2.8 設(shè)計(jì)函數(shù)求設(shè)計(jì)函數(shù)求n!圖圖2.7 遞歸求解遞歸求解4!的過程的過程第第2章章 實(shí)現(xiàn)基礎(chǔ)

31、實(shí)現(xiàn)基礎(chǔ) 2.3 流程控制基礎(chǔ)流程控制基礎(chǔ)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 流程控制基礎(chǔ)流程控制基礎(chǔ)第第2章章 實(shí)現(xiàn)基礎(chǔ)實(shí)現(xiàn)基

32、礎(chǔ) 【分析分析】可以用遞歸方法來求解漢諾塔問題，也就是可以用遞歸方法來求解漢諾塔問題，也就是將將n個(gè)金片的移動(dòng)個(gè)金片的移動(dòng)問題轉(zhuǎn)換為問題轉(zhuǎn)換為2個(gè)個(gè)n-1個(gè)金片的移動(dòng)問題個(gè)金片的移動(dòng)問題。當(dāng)。當(dāng)n=1時(shí)，就不需要再遞歸了。時(shí)，就不需要再遞歸了。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);遞歸調(diào)用遞歸調(diào)用22/253 流程控制基礎(chǔ)流程控制基礎(chǔ)第第2章章 實(shí)現(xiàn)基礎(chǔ)實(shí)現(xiàn)基礎(chǔ) 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章章 實(shí)現(xiàn)基礎(chǔ)實(shí)現(xiàn)基礎(chǔ) 2.3 流程控制基礎(chǔ)流程控制基礎(chǔ) 根據(jù)前面根據(jù)前面求解集合第求解集合第K大整數(shù)問題的大整數(shù)問題的遞歸算法遞歸算法思路思路，還需要解決，還需要解決以下兩個(gè)關(guān)鍵問題：以下兩個(gè)關(guān)鍵問題：（1）如何根據(jù)元素）如何根據(jù)元素e將集合將集合S分解為分解為S1和和S2兩個(gè)集