第二章數據結構與算法-實現基礎

復習計算下列代碼的時間復雜度：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;}引子

數據存儲基礎

流程控制基礎

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

，…，

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

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

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

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

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

void*malloc(unsigned

size)。②釋放函數voidfree(void

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

類型名結構成員名1;

類型名結構成員名2;

……

類型名結構成員名n;};第2章實現基礎§2數據存儲基礎【定義】結構類型把一些可以是不同類型的數據分量聚合成一個整體。同時，結構又是一個變量的集合，可以單獨使用其變量成員。7/25結構名是結構的標識符不是變量名。構成結構的每一個類型變量稱為結構成員,它象數組的元素一樣,但數組中元素是以下標來訪問的,而結構是按變量名字來訪問成員的。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章實現基礎§2數據存儲基礎結構變量的使用使用結構變量就是對其成員進行操作。格式為：結構變量名.結構成員名。此外，結構變量不僅可以作為函數參數，也可以作為函數的返回值。結構數組：結構與數組的結合7/25對結構數組元素成員的引用是通過使用數組下標與結構成員操作符“.”相結合的方式來完成的，其一般格式為：結構數組名[下標].結構成員名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結構指針：指向結構的指針（1）用*方式訪問，形式：（*結構指針變量名）.結構成員名（2）用指向運算符“->”訪問指針指向的結構成員，形式：結構指針變量名->結構成員名共用體【定義】共用體類型是指將不同的數據項組織成一個整體，它們在內存中占用同一段存儲單元。第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;}8/25第2章實現基礎§2數據存儲基礎各個成員變量在內存中都使用同一段存儲空間，因此共用體變量的長度等于最長的成員的長度。共用體的訪問方式同結構體類似。0000001000000001u.k=258的二進制表示：u.ch[0]=2u.ch[1]=18/25鏈表

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

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

Node{ElementTypeData;

struct

Node*Next;};第2章實現基礎§2數據存儲基礎struct

Node*p;p=(struct

Node*)malloc(sizeof(structNode));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） 鏈表的建立

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

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

Node{ElementTypeData;

struct

Node*Next;

struct

Node*

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

除了使用C語言提供的標準類型和自己定義的一些結構體、枚舉等類型外，還可以用typedef語句來建立已經定義好的數據類型的別名。typedef

原有類型名

新類型名typedef

struct

Node*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兩類語句，為循環(huán)控制提供了for、while和do-while三類語句。三種基本的控制結構是順序、分支和循環(huán)。函數定義函數調用函數遞歸語句級控制單位級控制16/25[例2.5]求100到200之間的所有素數。[分析]可以設定兩重循環(huán)：大循環(huán)（外層循環(huán)）控制整數i在100到200之間變化（用for語句），而小循環(huán)（內層循環(huán)）則用來判別i是否是素數（用while語句）。第2章實現基礎§3流程控制基礎intmain(){

inti,j;

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

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

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

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

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

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

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

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

Image{double

r;

double

i;};typedefstruct

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

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

return

c;}有了這個函數，以后可以在任何需要計算復數加法的地方調用它！18/25在設計函數時，注意掌握以下原則：第2章實現基礎§3流程控制基礎（1）函數功能的設計原則：結合模塊的獨立性原則，函數的功能要單一，不要設計多用途的函數，否則會降低模塊的聚合度；（2）函數規(guī)模的設計原則：函數的規(guī)模要小，盡量控制在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);}注意：程序代碼不能寫成上述式子?。∵f歸調用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）初始狀態(tài)（b）中間狀態(tài)§3流程控制基礎第2章實現基礎【分析】可以用遞歸方法來求