第2章實現基礎§2.1引子還是為每個具體應用都編一個程序?類型名稱：數據集合的基本統計數據對象集：集合S={，

，…，}操作集：ElementType

Average(S)：求S中元素的平均值；ElementType

Max(S)：求S中元素的最大值；ElementType

Min(S)：求S中元素的最小值；ElementType

Median(S)：求S中元素的中位數。從不同的應用中抽象出共性的數據組織與操作方法？[例2.1]在日常數據處理中經常碰到的問題是需要對一組數據進行基本的統計分析。比如，分析一個課程班學生的平均成績、最高成績、最低成績、中位數、標準差等。同樣的統計要求也可能發生在其他領域。1/25如何利用程序設計語言實現上述抽象類型？第2章實現基礎§2.1引子1.數據存儲C語言（包括其他高級語言）提供了數組、結構、鏈表等。數據結構的存儲實現跟所需要的操作密切相關。在數據結構里，是利用數組和鏈表方式來實現的，包括很復雜的數據結構，如圖、樹等。2.操作實現流程控制語句，即分支控制語句（如if-else、switch語句）、循環控制語句（如for、while、do-while語句）。

此外，還有模塊化的程序設計方法——函數ElementType

Average(ElementTypeS[],intN){/*求集合元素的平均值。集合元素存放在數組S中，數組大小為N*/

inti;

ElementTypeSum=0;

for(i=0;i<N;i++)Sum+=S[i];/*將數組元素累加到Sum中*/

returnSum/N;}2/25[方法2]基于問題分解

相近的另一個問題是：求集合中的第K大整數。

當K=N/2時，集合的第K大整數就是中位數。

第2章實現基礎§2.1引子求中位數Median(S)[方法1]

基于排序。首先將集合S從大到小排序，第

N/2（大于等于N/2的最小整數）個元素就是中位數。

求解集合第K大整數問題的一種遞歸思路是：SN個元素S1N1個元素S2N2個元素元素>=e元素<e

當K=N1時，

第K大整數就是e。

當K<N1時，第K大整數是在S1中的第K大整數。

當K>N1時，第K大整數是在S2中的第(K-N1)大整數。

比較慢！3/25ElementType

KthLargest(ElementTypeS[],intK){選取S中的第一個元素e;根據e將集合S分解為大于等于e的元素集合S1和小于e的元素集合S2;while(|S2|==0)另選一個

e;if(|S1|>K)returnKthLargest(S1，K);elseif(|S1|<K)returnKthLargest(S2，K-|S1|);else

returne;}[例2.2]求集合{659821734}的中位數?！痉治觥坑捎谠摷嫌?個元素，所以中位數應該是集合從大到小排序后的第9/2=5個元素。首先，選取集合的第一個元素6，根據這個元素從集合中分解出S1={6，9，8，7}，S2={5，2，1，3，4}。由于|S1|=4<5，所以該中位數應該在集合S2中，且是S2中第(5–4=1)大整數。

繼續選取S2中的第一個整數5，將S2分解出兩個集合S1’={5}，S2’={2,1,3,4}。由于|S1’|=1，所以5就是S2集合的第1大整數，也就是集合{659821734}的中位數。第2章實現基礎§1引子4/25第2章實現基礎§2數據存儲基礎

變量是數據存儲的基本單位。變量的類型決定了存儲和操作。幾種基本的數據類型：整型、實型（浮點型）、字符型等。提供了構造數據類型：數組、結構、指針等。數組數組是最基本的構造類型，它是一組相同類型數據的有序集合。數組中的元素在內存中連續存放，用數組名和下標可以唯一地確定數組元素。[例2.3]求集合元素的最大值。集合元素存放在數組A中，數組大小為N。float

Max(floatA[],intN){/*求N個元素數組中的最大值*/

float

CurMax=A[0];

inti;

for(i=1;i<N;i++)

if(A[i]>CurMax)CurMax=A[i];

return

CurMax;}5/25指針第2章實現基礎§2數據存儲基礎

指針是C語言中一個非常重要的概念。使用指針可以對復雜數據進行處理，能對計算機的內存進行分配控制，在函數調用中使用指針還可以返回多個值。⑴指針與數組

數組名是數組中第1個元素（下標為0）的地址，可以看作是常量指針，不能改變指針常量（數組名）的值。⑵用指針實現內存動態分配①分配函數void*malloc(unsignedsize)。②釋放函數voidfree(void*ptr)。6/25結構結構類型定義的一般形式為：struct

結構名{

類型名結構成員名1;

類型名結構成員名2;

……

類型名結構成員名n;};第2章實現基礎§2數據存儲基礎【定義】結構類型把一些可以是不同類型的數據分量聚合成一個整體。同時，結構又是一個變量的集合，可以單獨使用其變量成員。結構變量的使用使用結構變量就是對其成員進行操作。格式為：結構變量名.結構成員名。此外，結構變量不僅可以作為函數參數，也可以作為函數的返回值。結構數組：結構與數組的結合結構指針：指向結構的指針（1）用*方式訪問，形式：（*結構指針變量名）.結構成員名（2）用指向運算符“->”訪問指針指向的結構成員，形式：結構指針變量名->結構成員名對結構數組元素成員的引用是通過使用數組下標與結構成員操作符“.”相結合的方式來完成的，其一般格式為：結構數組名[下標].結構成員名7/25共用體【定義】共用體類型是指將不同的數據項組織成一個整體，它們在內存中占用同一段存儲單元。第2章實現基礎§2數據存儲基礎共用體類型定義的一般形式為：union共用體名{

類型名成員名1;

類型名成員名2;

……

類型名成員名n;};各個成員變量在內存中都使用同一段存儲空間，因此共用體變量的長度等于最長的成員的長度。共用體的訪問方式同結構體類似。intmain(){

unionkey{

intk;

charch[2];}u;u.k=258；printf(“%d%d\n”,u.ch[0],u.ch[1]);return0;}0000001000000001u.k=258的二進制表示：u.ch[0]=2u.ch[1]=18/25鏈表

鏈表是一種重要的基礎數據結構，也是實現復雜數據結構的重要手段。它不按照線性的順序存儲數據，而是由若干個同一結構類型的“結點”依次串接而成的，即每一個結點里保存著下一個結點的地址（指針）。

鏈表又分單向鏈表，雙向鏈表以及循環鏈表等。單向鏈表的結構使用結構的嵌套來定義單向鏈表結點的數據類型。如：structNode{

ElementTypeData;

structNode*Next;};第2章實現基礎§2數據存儲基礎structNode*p;p=(structNode*)malloc(sizeof(struct

Node));9/25head……（1） 插入結點(p之后插入新結點t)單向鏈表的常見操作（2） 刪除結點第2章實現基礎§2數據存儲基礎ptt->Next=p->Next;p->Next=t;

head……pt=p->Next;p->Next=t->next;

10/25（3）單向鏈表的遍歷p=head;while(p!=NULL){……處理p所指的結點信息；

……p=p->Next;}（4） 鏈表的建立

有兩種常見的插入結點方式：（1）在鏈表的頭上不斷插入新結點；（2）在鏈表的尾部不斷插入新結點。如果是后者，一般需要有一個臨時的結點指針一直指向當前鏈表的最后一個結點，以方便新結點的插入。第2章實現基礎§2數據存儲基礎11/25雙向鏈表如果將雙向鏈表最后一個單元的Next指針指向鏈表的第一個單元，而第一個單元的Previous指針指向鏈表的最后一個單元，這樣構成的鏈表稱為雙向循環鏈表。第2章實現基礎§2數據存儲基礎structNode{

ElementTypeData;

structNode*Next;

structNode*

Previous;};12/25雙向鏈表的插入、刪除和遍歷基本思路與單向鏈表相同，但需要同時考慮前后兩個指針。A1A2A3AN…headpt第2章實現基礎§2數據存儲基礎struct

DNode{

ElementTypeData;

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，請設計函數Reverse將鏈表L就地逆轉，即不需要申請新的結點，將鏈表的第一個元素轉為最后一個元素，第二個元素轉為倒數第二個元素……【分析】基本思路是：利用循環，從鏈表頭開始逐個處理。如何把握住循環不變式。（循環不變式表示一種在循環過程進行時不變的性質，不依賴于前面所執行過程的重復次數的斷言。）在每輪循環開始前我們都面臨兩個序列，其中p是一個待逆轉的序列，而q是一個已經逆轉好的序列，如下圖。每輪循環的目的是把p中的第一個元素插入到q的頭上，使這輪循環執行好后，p和q還是分別指向新的待逆轉序列和已經逆轉好的序列。第2章實現基礎§2數據存儲基礎p->Next=q;q=p;t……qpt=p->Next;p->Next=q;q=p;p=t;

structNode*Reverse(structNode*L){structNode*p,*q,*t;

p=L，q=NULL;

while(p!=NULL){t=p->Next;p->Next=q;q=p;p=t;}

returnq;}14/25類型定義typedef第2章實現基礎§2數據存儲基礎除了使用C語言提供的標準類型和自己定義的一些結構體、枚舉等類型外，還可以用typedef語句來建立已經定義好的數據類型的別名。typedef

原有類型名

新類型名typedef

structNode*NodePtr;這樣，Reverse函數頭就可以寫成：NodePtrReverse(NodePtrL)NodePtrReverse(NodePtrL)/*structNode*Reverse(structNode*L)*/{structNode*p,*q,*t;

p=L，q=NULL;

while(p!=NULL){t=p->Next;p->Next=q;q=p;p=t;}returnq;}15/25第2章實現基礎§3流程控制基礎順序結構是一種自然的控制結構，通過安排語句或模塊的順序就能實現。C語言為分支控制提供了if-else和switch兩類語句，為循環控制提供了for、while和do-while三類語句。三種基本的控制結構是順序、分支和循環。函數定義函數調用函數遞歸語句級控制單位級控制16/25[例2.5]求100到200之間的所有素數。[分析]可以設定兩重循環：大循環（外層循環）控制整數i在100到200之間變化（用for語句），而小循環（內層循環）則用來判別i是否是素數（用while語句）。第2章實現基礎§3流程控制基礎int

main(){

inti,j;

for(i=100;i<=200;i++){/*外層循環*/j=2;

while(j<i&&i%j!=0)j++;

/*內層循環,判別i是否是素數*/

if(j==i)printf(“%d”,i);

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

函數包括庫函數和自定義函數兩種。例如，scanf、printf等庫函數由C語言系統提供定義，編程時只要直接調用即可。

在程序設計中，往往根據模塊化程序設計的需要，用戶可以自己定義函數，屬于自定義函數。先定義復數類型ImgType，以約定何為復數：structImage{doubler;doublei;};typedef

structImageImgType;再定義復數的加法函數：ImgType

ImgAdd(ImgTypea,ImgTypeb){ImgTypec;

c.r=a.r+b.r;c.i=a.i+b.i;/*實部和虛部分別相加*/

returnc;}有了這個函數，以后可以在任何需要計算復數加法的地方調用它！18/25在設計函數時，注意掌握以下原則：第2章實現基礎§3流程控制基礎（1）函數功能的設計原則：結合模塊的獨立性原則，函數的功能要單一，不要設計多用途的函數，否則會降低模塊的聚合度；（2）函數規模的設計原則：函數的規模要小，盡量控制在50行代碼以內，這樣可以使得函數更易于維護；（3）函數接口的設計原則：結合模塊的獨立性原則，函數的接口包括函數的參數（入口）和返回值（出口），不要設計過于復雜的接口，合理選擇、設置并控制參數的數量，盡量不要使用全局變量，否則會增加模塊的耦合度。19/25遞歸函數【定義】一個函數除了可以調用其他函數外，C語言還支持函數直接或間接調用自己。這種函數自己調用自己的形式稱為函數的遞歸調用，帶有遞歸調用的函數也稱為遞歸函數。兩個關鍵點：（1） 遞歸出口：即遞歸的結束條件，到何時不再遞歸調用下去;第2章實現基礎§2.3流程控制基礎（2） 遞歸式子：當前函數結果與準備調用的函數結果之間的關系，如求階乘函數的遞歸式子

Factorial(n)=n*Factorial(n-1)longintFactorial(intn){if(n==0)return1;else

returnn*Factorial(n-1);}注意：程序代碼不能寫成上述式子！！遞歸調用20/25[例2.8]設計函數求n!圖2.7遞歸求解4!的過程第2章實現基礎§2.3流程控制基礎longintFactorial(intn){if(n==0)return1;else

returnn*Factorial(n-1);}遞歸出口遞歸式子Factorial(4)4Factorial(3)3Factorial(2)2Factorial(1)1Factorial(0)11262421/25[例2.9]漢諾塔（TowerofHanoi）問題132132（a）初始狀態（b）中間狀態§3流程控制基礎第2章實現基礎【分析】可以用遞歸方法來求解漢諾塔問題，也就是將n個金片的移動問題轉換為2個n-1個金片的移動問題。當n=1時，就不需要再遞歸了。void

Move(intn,intstart,intgoal,inttemp){

if(n==0)return;Move(n-1,start,temp,goal);

printf(“Movedisk%dfrom%dto%d.\n”,n,start,goal);Move(n-1,temp,goal,start);}遞歸調用22/25§3流程控制基礎第2章實現基礎①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)Movedisk2from1to2Move(1,3,2,1)Move(0,3,1,2)Movedisk3from1to3Move(1,2,1,3)Move(0,1,2,3)Movedisk1from3to2Move(0,3,1,2)Move(1,1,3,2)Move(0,1,2,3)Move(0,2,3,1)Move(0,2,3,1)Move(2,2,3,1)Movedisk1from2to1Movedisk1from1to3Movedisk1from1to3②③④⑤⑥⑦Movedisk2from2to323/25[例2.10]用遞歸方法求集合的中位數。第2章實現基礎§2.3流程控制基礎根據前面求解集合第K大整數問題的遞歸算法思路，還需要解決以下兩個關鍵問題：（1）如何根據元素e將集合S分解為S1和S2兩個集合？可以采用臨時申請空間的方法建立一個臨時數組。（2）如何設計遞歸函數的參數？

將臨時數組作為參數傳遞。#include<malloc.h>ElementType

Median(ElementTypeS[],intN){ElementType*p,m;/*申請臨時數組大小所需要的空間*/p=(