第二章數(shù)據(jù)結(jié)構(gòu)與算法-實現(xiàn)基礎

復習計算下列代碼的時間復雜度：1.{++x;s=0;}2.for(i=1;i<=n;++i){++x;s+=x;}3.for(i=1;i<=n;++i)for(j=1;j<=n;++j){++x;s+=x;}引子

數(shù)據(jù)存儲基礎

流程控制基礎

應用實例第二章數(shù)據(jù)結(jié)構(gòu)實現(xiàn)基礎第2章實現(xiàn)基礎§2.1引子還是為每個具體應用都編一個程序?類型名稱：數(shù)據(jù)集合的基本統(tǒng)計數(shù)據(jù)對象集：集合S={，

，…，

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

此外，還有模塊化的程序設計方法——函數(shù)2/25ElementTypeAverage(ElementTypeS[],intN){/*求集合元素的平均值。集合元素存放在數(shù)組S中，數(shù)組大小為N*/inti;ElementTypeSum=0;for(i=0;i<N;i++)Sum+=S[i];/*將數(shù)組元素累加到Sum中*/returnSum/N;}第2章實現(xiàn)基礎§2數(shù)據(jù)存儲基礎

變量是數(shù)據(jù)存儲的基本單位。變量的類型決定了存儲和操作。幾種基本的數(shù)據(jù)類型：整型、實型（浮點型）、字符型等。提供了構(gòu)造數(shù)據(jù)類型：數(shù)組、結(jié)構(gòu)、指針等。數(shù)組數(shù)組是最基本的構(gòu)造類型，它是一組相同類型數(shù)據(jù)的有序集合。數(shù)組中的元素在內(nèi)存中連續(xù)存放，用數(shù)組名和下標可以唯一地確定數(shù)組元素。5/25floatMax(floatA[],intN){/*求N個元素數(shù)組中的最大值*/floatCurMax=A[0];inti;for(i=1;i<N;i++)if(A[i]>CurMax)CurMax=A[i];returnCurMax;}[例2.1]求集合元素的最大值。集合元素存放在數(shù)組A中，數(shù)組大小為N。指針第2章實現(xiàn)基礎§2數(shù)據(jù)存儲基礎

指針是C語言中一個非常重要的概念。使用指針可以對復雜數(shù)據(jù)進行處理，能對計算機的內(nèi)存進行分配控制，在函數(shù)調(diào)用中使用指針還可以返回多個值。一個定義一整型指針變量的語句如下：int*pi；pi是一個指針，其實，它也只過是一個存放變量的地址而已。通過變量的指針可以找到該變量。6/25（1）指針與數(shù)組第2章實現(xiàn)基礎§2數(shù)據(jù)存儲基礎

數(shù)組名是數(shù)組中第1個元素（下標為0）的地址，可以看作是常量指針，不能改變指針常量（數(shù)組名）的值。⑵用指針實現(xiàn)內(nèi)存動態(tài)分配①分配函數(shù)

void*malloc(unsigned

size)。②釋放函數(shù)voidfree(void

*ptr)。6/25第2章實現(xiàn)基礎§2數(shù)據(jù)存儲基礎注意：1.指針只有在被賦值以后才能被正確使用。2.在C語言中，指針的算術運算只包括兩個相同類型的指針相減以及指針加上或減去一個整數(shù)。6/25結(jié)構(gòu)結(jié)構(gòu)類型定義的一般形式為：struct結(jié)構(gòu)名{

類型名結(jié)構(gòu)成員名1;

類型名結(jié)構(gòu)成員名2;

……

類型名結(jié)構(gòu)成員名n;};第2章實現(xiàn)基礎§2數(shù)據(jù)存儲基礎【定義】結(jié)構(gòu)類型把一些可以是不同類型的數(shù)據(jù)分量聚合成一個整體。同時，結(jié)構(gòu)又是一個變量的集合，可以單獨使用其變量成員。7/25結(jié)構(gòu)名是結(jié)構(gòu)的標識符不是變量名。構(gòu)成結(jié)構(gòu)的每一個類型變量稱為結(jié)構(gòu)成員,它象數(shù)組的元素一樣,但數(shù)組中元素是以下標來訪問的,而結(jié)構(gòu)是按變量名字來訪問成員的。structstring{charname[8];intage;charsex[2];chardepart[20];floatwage1,wage2,wage3,wage4,wage5;}person;

structstring{charname[8];intage;charsex[2];chardepart[20];floatwage1,wage2,wage3,wage4,wage5;};structstringperson;第2章實現(xiàn)基礎§2數(shù)據(jù)存儲基礎結(jié)構(gòu)變量的使用使用結(jié)構(gòu)變量就是對其成員進行操作。格式為：結(jié)構(gòu)變量名.結(jié)構(gòu)成員名。此外，結(jié)構(gòu)變量不僅可以作為函數(shù)參數(shù)，也可以作為函數(shù)的返回值。結(jié)構(gòu)數(shù)組：結(jié)構(gòu)與數(shù)組的結(jié)合7/25對結(jié)構(gòu)數(shù)組元素成員的引用是通過使用數(shù)組下標與結(jié)構(gòu)成員操作符“.”相結(jié)合的方式來完成的，其一般格式為：結(jié)構(gòu)數(shù)組名[下標].結(jié)構(gòu)成員名structstring{charname[8];charsex[2];intage;charaddr[40];}*student;或者structstring*student;strcpy(student->name,"LuG.C");student->age=18;structstring{charname[8];charsex[2];intage;charaddr[40];};structstringstudent[40];student[0].namestudent[30].age結(jié)構(gòu)指針：指向結(jié)構(gòu)的指針（1）用*方式訪問，形式：（*結(jié)構(gòu)指針變量名）.結(jié)構(gòu)成員名（2）用指向運算符“->”訪問指針指向的結(jié)構(gòu)成員，形式：結(jié)構(gòu)指針變量名->結(jié)構(gòu)成員名共用體【定義】共用體類型是指將不同的數(shù)據(jù)項組織成一個整體，它們在內(nèi)存中占用同一段存儲單元。第2章實現(xiàn)基礎§2數(shù)據(jù)存儲基礎共用體類型定義的一般形式為：union共用體名{

類型名成員名1;

類型名成員名2;

……

類型名成員名n;};intmain(){

unionkey{

intk;

charch[2];}u;u.k=258；printf(“%d%d\n”,u.ch[0],u.ch[1]);return0;}8/25第2章實現(xiàn)基礎§2數(shù)據(jù)存儲基礎各個成員變量在內(nèi)存中都使用同一段存儲空間，因此共用體變量的長度等于最長的成員的長度。共用體的訪問方式同結(jié)構(gòu)體類似。0000001000000001u.k=258的二進制表示：u.ch[0]=2u.ch[1]=18/25鏈表

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

鏈表又分單向鏈表，雙向鏈表以及循環(huán)鏈表等。單向鏈表的結(jié)構(gòu)使用結(jié)構(gòu)的嵌套來定義單向鏈表結(jié)點的數(shù)據(jù)類型。如：struct

Node{ElementTypeData;

struct

Node*Next;};第2章實現(xiàn)基礎§2數(shù)據(jù)存儲基礎struct

Node*p;p=(struct

Node*)malloc(sizeof(structNode));9/25head……（1） 插入結(jié)點(p之后插入新結(jié)點t)單向鏈表的常見操作（2） 刪除結(jié)點

第2章實現(xiàn)基礎§2數(shù)據(jù)存儲基礎ptt->Next=p->Next;p->Next=t;

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

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

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

有兩種常見的插入結(jié)點方式：①在鏈表的頭上不斷插入新結(jié)點；②在鏈表的尾部不斷插入新結(jié)點。如果是后者，一般需要有一個臨時的結(jié)點指針一直指向當前鏈表的最后一個結(jié)點，以方便新結(jié)點的插入。第2章實現(xiàn)基礎§2數(shù)據(jù)存儲基礎11/25雙向鏈表

如果將雙向鏈表最后一個單元的Next指針指向鏈表的第一個單元，而第一個單元的Previous指針指向鏈表的最后一個單元，這樣構(gòu)成的鏈表稱為雙向循環(huán)鏈表。第2章實現(xiàn)基礎§2數(shù)據(jù)存儲基礎struct

Node{ElementTypeData;

struct

Node*Next;

struct

Node*

Previous;};12/25雙向鏈表的插入、刪除和遍歷基本思路與單向鏈表相同，但需要同時考慮前后兩個指針。A1A2A3AN…h(huán)eadpt第2章實現(xiàn)基礎§2數(shù)據(jù)存儲基礎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類型定義typedef第2章實現(xiàn)基礎§2數(shù)據(jù)存儲基礎

除了使用C語言提供的標準類型和自己定義的一些結(jié)構(gòu)體、枚舉等類型外，還可以用typedef語句來建立已經(jīng)定義好的數(shù)據(jù)類型的別名。typedef

原有類型名

新類型名typedef

struct

Node*NodePtr;這樣，Reverse函數(shù)頭就可以寫成：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章實現(xiàn)基礎§3流程控制基礎順序結(jié)構(gòu)是一種自然的控制結(jié)構(gòu)，通過安排語句或模塊的順序就能實現(xiàn)。C語言為分支控制提供了if-else和switch兩類語句，為循環(huán)控制提供了for、while和do-while三類語句。三種基本的控制結(jié)構(gòu)是順序、分支和循環(huán)。函數(shù)定義函數(shù)調(diào)用函數(shù)遞歸語句級控制單位級控制16/25[例2.5]求100到200之間的所有素數(shù)。[分析]可以設定兩重循環(huán)：大循環(huán)（外層循環(huán)）控制整數(shù)i在100到200之間變化（用for語句），而小循環(huán)（內(nèi)層循環(huán)）則用來判別i是否是素數(shù)（用while語句）。第2章實現(xiàn)基礎§3流程控制基礎intmain(){

inti,j;

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

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

/*內(nèi)層循環(huán),判別i是否是素數(shù)*/

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

/*j==i說明在上面的while循環(huán)中i都不能被j整除，因此i是素數(shù)*/}return0;}17/25函數(shù)與遞歸比如：C語言提供了實數(shù)和整數(shù)的加法運算符號“+”來完成運算；但是“+”不能對復數(shù)做加法運算；可以寫一個函數(shù)來實現(xiàn)這個功能。第2章實現(xiàn)基礎§3流程控制基礎

【定義】函數(shù)是一個完成特定工作的獨立程序模塊。只需定義一次，就可以多次調(diào)用。

函數(shù)包括庫函數(shù)和自定義函數(shù)兩種。例如，scanf、printf等庫函數(shù)由C語言系統(tǒng)提供定義，編程時只要直接調(diào)用即可。

在程序設計中，往往根據(jù)模塊化程序設計的需要，用戶可以自己定義函數(shù)，屬于自定義函數(shù)。先定義復數(shù)類型ImgType，以約定何為復數(shù)：struct

Image{double

r;

double

i;};typedefstruct

ImageImgType;再定義復數(shù)的加法函數(shù)：ImgTypeImgAdd(ImgTypea,ImgTypeb){ImgTypec;

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

return

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

遞歸出口：即遞歸的結(jié)束條件，到何時不再遞歸調(diào)用下去;第2章實現(xiàn)基礎§2.3流程控制基礎（2）

遞歸式子：當前函數(shù)結(jié)果與準備調(diào)用的函數(shù)結(jié)果之間的關系，如求階乘函數(shù)的遞歸式子

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

returnn*Factorial(n-1);}注意：程序代碼不能寫成上述式子??！遞歸調(diào)用20/25[例2.8]設計函數(shù)求n!圖2.7遞歸求解4!的過程第2章實現(xiàn)基礎§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）初始狀態(tài)（b）中間狀態(tài)§3流程控制基礎第2章實現(xiàn)基礎【分析】可以用遞歸方法來求