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

復習計算下列代碼的時間復雜度：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ù)存儲基礎(chǔ)

流程控制基礎(chǔ)

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

，…，

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

變量是數(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)基礎(chǔ)§2數(shù)據(jù)存儲基礎(chǔ)

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

數(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)基礎(chǔ)§2數(shù)據(jù)存儲基礎(chǔ)注意：1.指針只有在被賦值以后才能被正確使用。2.在C語言中，指針的算術(shù)運算只包括兩個相同類型的指針相減以及指針加上或減去一個整數(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)基礎(chǔ)§2數(shù)據(jù)存儲基礎(chǔ)【定義】結(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)基礎(chǔ)§2數(shù)據(jù)存儲基礎(chǔ)結(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)基礎(chǔ)§2數(shù)據(jù)存儲基礎(chǔ)共用體類型定義的一般形式為：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)基礎(chǔ)§2數(shù)據(jù)存儲基礎(chǔ)各個成員變量在內(nèi)存中都使用同一段存儲空間，因此共用體變量的長度等于最長的成員的長度。共用體的訪問方式同結(jié)構(gòu)體類似。0000001000000001u.k=258的二進制表示：u.ch[0]=2u.ch[1]=18/25鏈表

鏈表是一種重要的基礎(chǔ)數(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)基礎(chǔ)§2數(shù)據(jù)存儲基礎(chǔ)struct

Node*p;p=(struct

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

第2章實現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲基礎(chǔ)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)基礎(chǔ)§2數(shù)據(jù)存儲基礎(chǔ)11/25雙向鏈表

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

Node{ElementTypeData;

struct

Node*Next;

struct

Node*

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

除了使用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)基礎(chǔ)§3流程控制基礎(chǔ)順序結(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ù)。[分析]可以設(shè)定兩重循環(huán)：大循環(huán)（外層循環(huán)）控制整數(shù)i在100到200之間變化（用for語句），而小循環(huán)（內(nèi)層循環(huán)）則用來判別i是否是素數(shù)（用while語句）。第2章實現(xiàn)基礎(chǔ)§3流程控制基礎(chǔ)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)基礎(chǔ)§3流程控制基礎(chǔ)

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

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

在程序設(shè)計中，往往根據(jù)模塊化程序設(shè)計的需要，用戶可以自己定義函數(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è)計函數(shù)時，注意掌握以下原則：第2章實現(xiàn)基礎(chǔ)§3流程控制基礎(chǔ)（1）函數(shù)功能的設(shè)計原則：結(jié)合模塊的獨立性原則，函數(shù)的功能要單一，不要設(shè)計多用途的函數(shù)，否則會降低模塊的聚合度；（2）函數(shù)規(guī)模的設(shè)計原則：函數(shù)的規(guī)模要小，盡量控制在50行代碼以內(nèi)，這樣可以使得函數(shù)更易于維護；（3）函數(shù)接口的設(shè)計原則：結(jié)合模塊的獨立性原則，函數(shù)的接口包括函數(shù)的參數(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ù)。兩個關(guān)鍵點：（1）

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

遞歸式子：當前函數(shù)結(jié)果與準備調(diào)用的函數(shù)結(jié)果之間的關(guān)系，如求階乘函數(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è)計函數(shù)求n!圖2.7遞歸求解4!的過程第2章實現(xiàn)基礎(chǔ)§2.3流程控制基礎(chǔ)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流程控制基礎(chǔ)第2章實現(xiàn)基礎(chǔ)【分析】可以用遞歸方法來求