編譯技術(shù)DS02實(shí)現(xiàn)基礎(chǔ)教學(xué)課件

編譯技術(shù)DS02實(shí)現(xiàn)基礎(chǔ)1、舟遙遙以輕飏，風(fēng)飄飄而吹衣。2、秋菊有佳色，裛露掇其英。3、日月擲人去，有志不獲騁。4、未言心相醉，不再接杯酒。5、黃發(fā)垂髫，并怡然自樂。編譯技術(shù)DS02實(shí)現(xiàn)基礎(chǔ)編譯技術(shù)DS02實(shí)現(xiàn)基礎(chǔ)1、舟遙遙以輕飏，風(fēng)飄飄而吹衣。2、秋菊有佳色，裛露掇其英。3、日月擲人去，有志不獲騁。4、未言心相醉，不再接杯酒。5、黃發(fā)垂髫，并怡然自樂。第2章實(shí)現(xiàn)基礎(chǔ)§2.1引子還是為每個(gè)具體應(yīng)用都編一個(gè)程序?類型名稱：數(shù)據(jù)集合的基本統(tǒng)計(jì)數(shù)據(jù)對(duì)象集：集合S={，，…，}操作集：ElementTypeAverage(S)：求S中元素的平均值；ElementTypeMax(S)：求S中元素的最大值；ElementTypeMin(S)：求S中元素的最小值；ElementTypeMedian(S)：求S中元素的中位數(shù)。從不同的應(yīng)用中抽象出共性的數(shù)據(jù)組織與操作方法？[例2.1]在日常數(shù)據(jù)處理中經(jīng)常碰到的問題是需要對(duì)一組數(shù)據(jù)進(jìn)行基本的統(tǒng)計(jì)分析。比如，分析一個(gè)課程班學(xué)生的平均成績(jī)、最高成績(jī)、最低成績(jī)、中位數(shù)、標(biāo)準(zhǔn)差等。同樣的統(tǒng)計(jì)要求也可能發(fā)生在其他領(lǐng)域。1/25如何利用程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)上述抽象類型？第2章實(shí)現(xiàn)基礎(chǔ)§2.1引子1.數(shù)據(jù)存儲(chǔ)C語(yǔ)言（包括其他高級(jí)語(yǔ)言）提供了數(shù)組、結(jié)構(gòu)、鏈表等。數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)實(shí)現(xiàn)跟所需要的操作密切相關(guān)。在數(shù)據(jù)結(jié)構(gòu)里，是利用數(shù)組和鏈表方式來(lái)實(shí)現(xiàn)的，包括很復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，如圖、樹等。2.操作實(shí)現(xiàn)流程控制語(yǔ)句，即分支控制語(yǔ)句（如if-else、switch語(yǔ)句）、循環(huán)控制語(yǔ)句（如for、while、do-while語(yǔ)句）。此外，還有模塊化的程序設(shè)計(jì)方法——函數(shù)2/25指針第2章實(shí)現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲(chǔ)基礎(chǔ)

指針是C語(yǔ)言中一個(gè)非常重要的概念。使用指針可以對(duì)復(fù)雜數(shù)據(jù)進(jìn)行處理，能對(duì)計(jì)算機(jī)的內(nèi)存進(jìn)行分配控制，在函數(shù)調(diào)用中使用指針還可以返回多個(gè)值。⑴指針的基本運(yùn)算

取地址運(yùn)算符&

間接訪問運(yùn)算符*指針的加、減操作。6/25第2章實(shí)現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲(chǔ)基礎(chǔ)（2）指針與數(shù)組

數(shù)組名是數(shù)組中第1個(gè)元素（下標(biāo)為0）的地址，可以看作是常量指針，不能改變指針常量（數(shù)組名）的值。（3）用指針實(shí)現(xiàn)內(nèi)存動(dòng)態(tài)分配分配函數(shù)void*malloc(unsigned

size)。該函數(shù)分配了size個(gè)字節(jié)，并返回了指向這塊內(nèi)存的指針。如果分配失敗，則返回一個(gè)空指針（NULL）。關(guān)于分配失敗的原因，應(yīng)該有多種，比如說空間不足就是一種。釋放函數(shù)voidfree(void*ptr)。該函數(shù)是將之前用malloc分配的空間還給程序或者是操作系統(tǒng)，也就是釋放了這塊內(nèi)存，讓它重新得到自由。6/25注意事項(xiàng)：A、申請(qǐng)了內(nèi)存空間后，必須檢查是否分配成功。B、當(dāng)不需要再使用申請(qǐng)的內(nèi)存時(shí)，記得釋放；釋放后應(yīng)該把原本指向這塊內(nèi)存的指針變量指向NULL，防止程序后面不小心使用了該指針。（釋放的是內(nèi)存，不是指針變量）C、這兩個(gè)函數(shù)應(yīng)該是配對(duì)使用。如果申請(qǐng)后不釋放就是內(nèi)存泄露；如果無(wú)故釋放（還未使用就釋放）那就是什么也沒有做。釋放只能一次，如果釋放兩次及兩次以上會(huì)出現(xiàn)錯(cuò)誤（釋放空指針例外，釋放空指針其實(shí)也等于啥也沒做，所以釋放空指針釋放多少次都沒有問題）。D、雖然malloc()函數(shù)的類型是(void*),任何類型的指針都可以轉(zhuǎn)換成(void*),但是最好還是在前面進(jìn)行強(qiáng)制類型轉(zhuǎn)換，因?yàn)檫@樣可以躲過一些編譯器的檢查。第2章實(shí)現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲(chǔ)基礎(chǔ)（4）用指針實(shí)現(xiàn)動(dòng)態(tài)順序存儲(chǔ)結(jié)構(gòu)

int*p;p=(int*)malloc(10*sizeof(int));if(p==NULL)return;intp[10];

第2章實(shí)現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲(chǔ)基礎(chǔ)結(jié)構(gòu)結(jié)構(gòu)類型定義的一般形式為：struct

結(jié)構(gòu)名{

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

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

……

類型名結(jié)構(gòu)成員名n;};第2章實(shí)現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲(chǔ)基礎(chǔ)【定義】結(jié)構(gòu)類型把一些可以是不同類型的數(shù)據(jù)分量聚合成一個(gè)整體。同時(shí)，結(jié)構(gòu)又是一個(gè)變量的集合，可以單獨(dú)使用其變量成員。7/25structstudent//學(xué)生信息結(jié)構(gòu)體{intnum;//學(xué)號(hào)

charname[20];//姓名

chargender;//性別

intage;//年齡}stu={97001,"LinLin",'F',19};typedef

structstudent//學(xué)生信息結(jié)構(gòu)體{intnum;//學(xué)號(hào)

……

intage;//年齡}Student；第2章實(shí)現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲(chǔ)基礎(chǔ)結(jié)構(gòu)數(shù)組：結(jié)構(gòu)與數(shù)組的結(jié)合結(jié)構(gòu)指針：指向結(jié)構(gòu)的指針（1）用*方式訪問，形式：（*結(jié)構(gòu)指針變量名）.結(jié)構(gòu)成員名（2）用指向運(yùn)算符“->”訪問指針指向的結(jié)構(gòu)成員，形式：結(jié)構(gòu)指針變量名->結(jié)構(gòu)成員名對(duì)結(jié)構(gòu)數(shù)組元素成員的引用是通過使用數(shù)組下標(biāo)與結(jié)構(gòu)成員操作符“.”相結(jié)合的方式來(lái)完成的，其一般格式為：結(jié)構(gòu)數(shù)組名[下標(biāo)].結(jié)構(gòu)成員名7/25結(jié)構(gòu)變量的使用使用結(jié)構(gòu)變量就是對(duì)其成員進(jìn)行操作。格式為：結(jié)構(gòu)變量名.結(jié)構(gòu)成員名。此外，結(jié)構(gòu)變量不僅可以作為函數(shù)參數(shù)，也可以作為函數(shù)的返回值。共用體【定義】共用體類型是指將不同的數(shù)據(jù)項(xiàng)組織成一個(gè)整體，它們?cè)趦?nèi)存中占用同一段存儲(chǔ)單元。第2章實(shí)現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲(chǔ)基礎(chǔ)共用體類型定義的一般形式為：union共用體名{

類型名成員名1;

類型名成員名2;

……

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

unionkey{

intk;

charch[2];}u;u.k=258；printf(“%d%d\n”,u.ch[0],u.ch[1]);return0;}0000001000000001u.k=258的二進(jìn)制表示：u.ch[0]=2u.ch[1]=18/25枚舉類型的聲明形式如下：enum枚舉類型名{變量值列表};⑤枚舉類型【定義】將需要的變量值一一列舉出來(lái)，便構(gòu)成了一個(gè)枚舉類型例如：enumweekday{sun,mon,tue,wed,thu,fri,sat};枚舉類型應(yīng)用說明：

對(duì)枚舉元素按常量處理，不能對(duì)它們賦值。如，不能寫：sun=0;

枚舉元素具有缺省值，它們依次為：0,1,2,......。也可以在聲明時(shí)另行指定枚舉元素的值，如：enumweekday{sun=7,mon=1,tue,wed,thu,fri,sat};枚舉值可以進(jìn)行關(guān)系運(yùn)算。如：

weekdaytoday；

if(today==tue);整數(shù)值不能直接賦給枚舉變量，如需要將整數(shù)賦值給枚舉變量，應(yīng)進(jìn)行強(qiáng)制類型轉(zhuǎn)換。如：today=(weekday)3;鏈表

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

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

structNode*Next;};第2章實(shí)現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲(chǔ)基礎(chǔ)structNode*p;p=(structNode*)malloc(sizeof(structNode));9/25head……（1） 插入結(jié)點(diǎn)(p之后插入新結(jié)點(diǎn)t)單向鏈表的常見操作（2） 刪除結(jié)點(diǎn)第2章實(shí)現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲(chǔ)基礎(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é)點(diǎn)信息；

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

有兩種常見的插入結(jié)點(diǎn)方式：（1）在鏈表的頭上不斷插入新結(jié)點(diǎn)；（2）在鏈表的尾部不斷插入新結(jié)點(diǎn)。如果是后者，一般需要有一個(gè)臨時(shí)的結(jié)點(diǎn)指針一直指向當(dāng)前鏈表的最后一個(gè)結(jié)點(diǎn)，以方便新結(jié)點(diǎn)的插入。第2章實(shí)現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲(chǔ)基礎(chǔ)11/25雙向鏈表如果將雙向鏈表最后一個(gè)單元的Next指針指向鏈表的第一個(gè)單元，而第一個(gè)單元的Previous指針指向鏈表的最后一個(gè)單元，這樣構(gòu)成的鏈表稱為雙向循環(huán)鏈表。第2章實(shí)現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲(chǔ)基礎(chǔ)structNode{ElementTypeData;

structNode*Next;

structNode*

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

structDNode*Next;

structDNode*Previous;}*p,*t;指針操作順序：①t->Previous=p;②t->Next=p->Next;③p->Next->Previous=t;④p->Next=t;①②③④13/25[例2.4]給定一個(gè)單鏈表L，請(qǐng)?jiān)O(shè)計(jì)函數(shù)Reverse將鏈表L就地逆轉(zhuǎn)，即不需要申請(qǐng)新的結(jié)點(diǎn)，將鏈表的第一個(gè)元素轉(zhuǎn)為最后一個(gè)元素，第二個(gè)元素轉(zhuǎn)為倒數(shù)第二個(gè)元素，……。【分析】基本思路是：利用循環(huán)，從鏈表頭開始逐個(gè)處理。如何把握住循環(huán)不變式。（循環(huán)不變式表示一種在循環(huán)過程進(jìn)行時(shí)不變的性質(zhì)，不依賴于前面所執(zhí)行過程的重復(fù)次數(shù)的斷言。）在每輪循環(huán)開始前我們都面臨兩個(gè)序列，其中p是一個(gè)待逆轉(zhuǎn)的序列，而q是一個(gè)已經(jīng)逆轉(zhuǎn)好的序列，如下圖。每輪循環(huán)的目的是把p中的第一個(gè)元素插入到q的頭上，使這輪循環(huán)執(zhí)行好后，p和q還是分別指向新的待逆轉(zhuǎn)序列和已經(jīng)逆轉(zhuǎn)好的序列。第2章實(shí)現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲(chǔ)基礎(chǔ)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章實(shí)現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲(chǔ)基礎(chǔ)除了使用C語(yǔ)言提供的標(biāo)準(zhǔn)類型和自己定義的一些結(jié)構(gòu)體、枚舉等類型外，還可以用typedef語(yǔ)句來(lái)建立已經(jīng)定義好的數(shù)據(jù)類型的別名。typedef

原有類型名

新類型名typedef

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

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

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

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

在程序設(shè)計(jì)中，往往根據(jù)模塊化程序設(shè)計(jì)的需要，用戶可以自己定義函數(shù)，屬于自定義函數(shù)。先定義復(fù)數(shù)類型ImgType，以約定何為復(fù)數(shù)：structImage{doubler;doublei;};typedefstructImageImgType;再定義復(fù)數(shù)的加法函數(shù)：ImgTypeImgAdd(ImgTypea,ImgTypeb){ImgTypec;c.r=a.r+b.r;c.i=a.i+b.i;/*實(shí)部和虛部分別相加*/

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

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

returnn*Factorial(n-1);}注意：程序代碼不能寫成上述式子?。∵f歸調(diào)用20/25[例2.8]設(shè)計(jì)函數(shù)求n!圖2.7遞歸求解4!的過程第2章實(shí)現(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章實(shí)現(xiàn)基礎(chǔ)【分析】可以用遞歸方法來(lái)求解漢諾塔問題，也就是將n個(gè)金片的移動(dòng)問題轉(zhuǎn)換為2個(gè)n-1個(gè)金片的移動(dòng)問題。當(dāng)n=1時(shí)，就不需要再遞歸了。voidMove(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);}遞歸調(diào)用22/25§3流程控制基礎(chǔ)第2章實(shí)現(xiàn)基礎(chǔ)①M(fèi)ove(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②③④⑤⑥⑦M(jìn)ovedisk2from2to323/25[例2.10]用遞歸方法求集合的中位數(shù)。第2章實(shí)現(xiàn)基礎(chǔ)§2.3流程控制基礎(chǔ)根據(jù)前面求解集合第K大整數(shù)問題的遞歸算法思路，還需要解決以下兩個(gè)關(guān)鍵問題：（1）如何根據(jù)元素e將集合S分解為S1和S2兩個(gè)集合？可以采用臨時(shí)申請(qǐng)空間的方法建立一個(gè)臨時(shí)數(shù)組。（2）如何設(shè)計(jì)遞歸函數(shù)的參數(shù)？將臨時(shí)數(shù)組作為參數(shù)傳遞。#include<malloc.h>ElementTypeMedian(ElementTypeS[],intN){ElementType*p,m;/*申請(qǐng)臨時(shí)數(shù)組大小所需要的空間*/p=(ElementType*)malloc(sizeof(ElementType)*N);m=FindKthLargest(S,(N+1)/2,0,N-1,p);free(p);/*釋放臨時(shí)數(shù)組空間*/returnm;}24/25ElementTypeFindKthLargest(Element