《計算機基礎(chǔ)與C語言程序設(shè)計》課件第10章

第10章結(jié)構(gòu)體與共用體10.1結(jié)構(gòu)體10.2鏈表10.3共用體10.4枚舉類型10.5typedef結(jié)構(gòu)體類型和共用體類型都是用戶定義的構(gòu)造數(shù)據(jù)類型，是實現(xiàn)對不同類型數(shù)據(jù)封裝的一種方法。在比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)中，結(jié)構(gòu)體和共用體都有著廣泛的應(yīng)用。枚舉類型的引入，使得程序中的一些含義清楚的標(biāo)識符可作為數(shù)據(jù)使用，增加了程序的靈活性和可讀性。typedef語句可以為程序提供較好的說明信息，便于理解，可以使程序參數(shù)化，便于移植。

在實際應(yīng)用中，一組相關(guān)的數(shù)據(jù)可能是相同類型的，也可能是不同類型的。例如，表示一個學(xué)生的信息可能包括學(xué)號、姓名、出生年月和成績這四項。為了相關(guān)數(shù)據(jù)的封裝性，需要采用可以包含不同數(shù)據(jù)類型成員的類型來定義這樣的數(shù)據(jù)，這種數(shù)據(jù)類型稱為“結(jié)構(gòu)體”類型。10.1結(jié)構(gòu)體結(jié)構(gòu)體類型是一種用戶自定義的構(gòu)造數(shù)據(jù)類型。它是由若干成員組成的，每個成員可以是一個基本數(shù)據(jù)類型，也可以是一個構(gòu)造數(shù)據(jù)類型。結(jié)構(gòu)體類型的各個成員可以是不同的類型，也可以是相同的類型。10.1.1結(jié)構(gòu)體類型的定義

結(jié)構(gòu)體類型定義的一般形式為

struct結(jié)構(gòu)體類型名{

類型名1成員名1；

類型名2成員名2；

……

類型名n成員名n；

}；說明：

(1)

struct是定義結(jié)構(gòu)體類型的關(guān)鍵字。struct后面跟的是所定義的結(jié)構(gòu)體類型的名字，其命名應(yīng)符合標(biāo)識符的命名規(guī)則。

(2)結(jié)構(gòu)體類型的所有成員用花括號括起來，結(jié)構(gòu)體類型成員的定義方式和變量的定義方式一樣，成員名的命名規(guī)則和變量名的命名相同，各成員之間用分號分隔。結(jié)構(gòu)體類型定義最后以分號結(jié)束。

(3)結(jié)構(gòu)體類型成員的數(shù)據(jù)類型可以是基本類型，也可以是構(gòu)造類型，比如數(shù)組，當(dāng)然也可以是結(jié)構(gòu)體類型。如上述關(guān)于學(xué)生情況的結(jié)構(gòu)體類型可按如下定義：

structstudent_type{

intnumber;

charname[8];

structdate_typebirthday;

floatscore[3];

};它包含4個成員，其中出生年月又是一個如下的結(jié)構(gòu)體類型：

structdate_type{

intyear;

intmonth;

intday;

};

注意：在實際應(yīng)用程序中，結(jié)構(gòu)體類型structdate_type的定義應(yīng)出現(xiàn)在結(jié)構(gòu)體類型structstudent_type的定義之前。10.1.2結(jié)構(gòu)體變量與指向結(jié)構(gòu)體變量的指針變量的定義

結(jié)構(gòu)體類型的定義說明了一種有若干個特定成員組成的模型，像int類型、float類型一樣，類型并不是實體，不占內(nèi)存空間，只有結(jié)構(gòu)體變量才能存放結(jié)構(gòu)體類型的數(shù)據(jù)，是占用內(nèi)存空間的實體。結(jié)構(gòu)體變量占用內(nèi)存空間，所以它是有地址的，結(jié)構(gòu)體變量的地址就是它在內(nèi)存中存儲單元的首地址，用來存放結(jié)構(gòu)體變量地址的變量就是指向結(jié)構(gòu)體變量的指針變量。

結(jié)構(gòu)體變量初始化是指在定義結(jié)構(gòu)體變量的同時為結(jié)構(gòu)體內(nèi)的各成員變量賦初值。

結(jié)構(gòu)體變量和指向結(jié)構(gòu)體變量的指針變量的定義方法有3種。

(1)用已定義的結(jié)構(gòu)體類型定義結(jié)構(gòu)體變量和指向結(jié)構(gòu)體變量的指針變量。例如：

structperson{

intnum;

charname[8];

intage;

floatwage;

}; /*定義結(jié)構(gòu)體類型。*/

structpersonmember; /*定義結(jié)構(gòu)體變量member。*/

structperson*pm=&member; /*定義指向結(jié)構(gòu)體變量的指針變量pm，并初始化使其指向member。*/結(jié)構(gòu)體的各成員順次占用連續(xù)的存儲空間，結(jié)構(gòu)體變量member中有4個成員，它們各占2、8、2、4個字節(jié)，因此member共需占16個字節(jié)(假設(shè)int型占用2個字節(jié)，char型占用1個字型，float型占用4個字節(jié))。指向結(jié)構(gòu)體變量member的指針變量pm中存放的是member的首地址。

(2)定義結(jié)構(gòu)體類型的同時定義結(jié)構(gòu)體變量和指向結(jié)構(gòu)體變量的指針變量。

structperson{

intnum;

charname[8];

intage;

floatwage;

}member,*pm=&member; /*定義結(jié)構(gòu)體類型變量member和指向member的指針變量pm。*/

(3)定義無名結(jié)構(gòu)體類型的同時定義結(jié)構(gòu)體變量和指向結(jié)構(gòu)體變量的指針變量。

struct{

intnum;

charname[8];

intage;

floatwage;

}member,*pm=&member; /*定義結(jié)構(gòu)體類型變量member和指向member的指針變量pm。*/

這種定義形式和第二種方式相比，僅是省略了結(jié)構(gòu)體名，一般用于不再需要定義此種類型的結(jié)構(gòu)體變量的情況。10.1.3結(jié)構(gòu)體變量的引用

對于結(jié)構(gòu)體變量，只能通過引用其成員來使用結(jié)構(gòu)體變量。結(jié)構(gòu)體變量成員的引用方式為

結(jié)構(gòu)體變量名.成員名

其中“.”稱為成員運算符。

也可以通過指向結(jié)構(gòu)體變量的指針變量來引用結(jié)構(gòu)體變量的成員，其引用方式為

(*結(jié)構(gòu)體指針變量名).成員名

或

結(jié)構(gòu)體指針變量名->成員名

這兩種表示形式是完全等價的。例如，若有定義：

structdate_type{

intyear;

intmonth;

intday;

};

structstudent_type{

intnumber;

charname[8];

structdate_typebirthday;

floatscore[3];

}student,*ps=&student;

那么，對于變量student的成員number可以有如下幾種引用方式：

student.number

(*ps).number

ps->number

這幾種引用方式是完全等價的。

對于結(jié)構(gòu)體變量的成員仍然是結(jié)構(gòu)體類型的，則需要逐級引用，直至最低級的成員。

例如：

student.birthday.year

(*ps).birthday.year

ps->birthday.year

注意：只能對最低級的成員進(jìn)行存取和運算。

對于結(jié)構(gòu)體變量的成員是數(shù)組類型的，只能引用其元素，而不能整體引用。

例如：

student.score[1]

(*ps).score[1]

ps->score[1]特別地，對于結(jié)構(gòu)體變量的成員是字符數(shù)組類型的，雖然也可以像以上方法一樣引用其元素，但是，由于字符數(shù)組存放的是字符串，字符數(shù)組名表示的是字符串的首地址，因此可引用字符數(shù)組名來對字符數(shù)組進(jìn)行操作。

例如：

(*ps).name

ps->name

注意：數(shù)值型數(shù)組是不可以這樣使用的。

結(jié)構(gòu)體成員的運算規(guī)則與同類型的變量的運算規(guī)則相同。10.1.4結(jié)構(gòu)體變量的初始化

和其它類型的變量一樣，定義結(jié)構(gòu)體變量的同時可以對其賦以初值，即對結(jié)構(gòu)體變量初始化。

例如：

structdate_type{

intyear;

intmonth;

intday;

};

structstudent_type{

intnumber;

charname[8];

structdate_typebirthday;

floatscore[3];

}student={1001,"ZHANG",{1992,11,20},{89,90,91}};10.1.5結(jié)構(gòu)體數(shù)組

1.結(jié)構(gòu)體數(shù)組的定義和初始化

結(jié)構(gòu)體數(shù)組的定義與結(jié)構(gòu)體變量的定義類似，可以定義結(jié)構(gòu)體類型后再定義數(shù)組，也可以在定義結(jié)構(gòu)體類型的同時定義數(shù)組。結(jié)構(gòu)體數(shù)組也具有一般數(shù)組的性質(zhì)：結(jié)構(gòu)體數(shù)組是由固定數(shù)目的相同結(jié)構(gòu)體類型的變量按照一定的順序組成的數(shù)據(jù)類型。例如：

structstudent{

intnum;

charname[8]；

floatsc[3];

floatave;

}st[3]={{2001,"zhang",{81,77,88}},{2002,"li",{83,89,82}},{2003,"chang",{67,75,86}}};

表示定義了結(jié)構(gòu)體數(shù)組變量st，其中含有3個元素，每一個元素都是structstudent這種結(jié)構(gòu)體類型的，并且定義數(shù)組的同時對其成員進(jìn)行了初始化。圖10-1給出的是結(jié)構(gòu)體數(shù)組st的邏輯存儲結(jié)構(gòu)。圖10-1結(jié)構(gòu)體數(shù)組st的邏輯存儲結(jié)構(gòu)和基本類型的數(shù)組一樣，對于結(jié)構(gòu)體類型的一維數(shù)組、二維數(shù)組，也可以定義指向它們的指針變量。例如：

structstudent*ps=st;

即指針變量ps指向結(jié)構(gòu)體數(shù)組變量st的第0個元素，那么，ps+1表示st[1]的地址，ps++表示指針向后移動一個數(shù)組元素的空間，即指向下一個數(shù)組元素。

2.結(jié)構(gòu)體數(shù)組的引用

結(jié)構(gòu)體數(shù)組元素也是通過數(shù)組名和下標(biāo)來引用的，但其元素是結(jié)構(gòu)體類型的數(shù)據(jù)，因此，對結(jié)構(gòu)體數(shù)組元素引用與結(jié)構(gòu)體變量的引用一樣，也要逐級引用，只能對最低級的成員進(jìn)行存取和運算。一般的引用形式為

結(jié)構(gòu)體數(shù)組名[下標(biāo)].成員名

如對于上面定義的數(shù)組st而言，下列是合法的引用方式：

st[1].num /*表示第1個學(xué)生的學(xué)號。*/

st[0].name /*表示第0個學(xué)生的姓名(字符串首地址)。*/

st[0].sc[2] /*表示第0個學(xué)生的第2門課程的成績。*/

st[1].ave /*表示第1個學(xué)生的平均成績。*/

還可以通過指向結(jié)構(gòu)體數(shù)組的指針來引用數(shù)組元素及成員，如果ps指向st，那么：

(*ps).num /*表示第0個學(xué)生的學(xué)號。*/

ps->name /*表示第0個學(xué)生的姓名。*/

(ps+1)->sc[2]; /*表示第1個學(xué)生的第2門課程的成績。*/

++ps->ave; /*表示使第0個學(xué)生的平均成績增1(“->”運算符的優(yōu)先級高于“++”運算)。*/

(++ps)->ave; /*表示指針ps向后移動一個數(shù)組元素空間，指向st[1]，即該式子表示第1個學(xué)生的平均成績。*/

需要注意的是，ps表示數(shù)組元素(結(jié)構(gòu)體變量)的地址，雖然它與其第一個成員的地址的值相同，但它們的類型是不同的，它們之間不能直接相互賦值。若需要將其成員的地址賦值給結(jié)構(gòu)體指針，可以先將其用強制類型轉(zhuǎn)換轉(zhuǎn)換為結(jié)構(gòu)體指針的類型，如：

ps=(structstudent*)(&st[1].ave);

這時，若執(zhí)行“ps++;”，那么ps指向的是st[2].ave，也就是說ps還是向后移動了一個結(jié)構(gòu)體類型structstudent那么大的空間。

【例10.1】

編寫程序，輸入若干個學(xué)生的有關(guān)信息(包括學(xué)號、姓名、出生日期、課程1成績、課程2成績、課程3成績)，計算出平均成績。

#defineN3

#include<stdio.h>

structstudent{

intnum;

charname[8];

struct{

intyear;

intmonth;

intday;

}birthday;

intsc[3];

floatave;

};

main()

{

structstudentst[N],*p;

intj,k;

printf(“\n”);

for(j=0;j<N;j++){/*輸入學(xué)生的有關(guān)信息*/

printf(“The%dstudent:\n”,j);

printf(“number:”);

scanf(“%d”,&st[j].num);

printf(“name:”);

scanf(“%s”,st[j].name);

printf(“birthday(year,month,day):”);

scanf("%d%d%d",&st[j].birthday.year,&st[j].birthday.

month,&st[j].birthday.day);

st[j].ave=0;

for(k=0;k<3;k++){

printf("score[%d]:",k);

scanf("%d",&st[j].sc[k]);

st[j].ave+=st[j].sc[k];/*計算總成績*/

}

st[j].ave/=3;

}

printf("\n");

printf("NumberNameYYYY/MM/DDScore[0]--Score[3]Average\n");

for(p=st;p<st+N;p++){

printf("%6d",p->num);

printf("%8s",p->name);

printf("%4d/%2d/%2d",p->birthday.year,p->birthday.month,p->birthday.day);

for(k=0;k<3;k++)

printf("%6d",p->sc[k]);

printf("%10.2f\n",p->ave);

}

}程序運行結(jié)果：

The0student:

number:1↙

name:a↙

birthday(year,month,day):198011↙

score[0]:67↙

score[1]:78↙

score[2]:80↙

The1student:

number:2↙

name:b↙

birthday(year,month,day):198125↙

score[0]:87↙

score[1]:79↙

score[2]:90↙

The2student:

number:3↙

name:c↙

birthday(year,month,day):197951↙

score[0]:85↙

score[1]:79↙

score[2]:93↙

NumberNameYYYY/MM/DDScore[0]-Score[3]Average

1a1980/1/167788075.00

2b1981/2/587799085.33

3c1979/5/185799385.6710.1.6結(jié)構(gòu)體變量作為函數(shù)的參數(shù)

用結(jié)構(gòu)體變量的成員作函數(shù)的實參的用法與普通變量作函數(shù)的實參的用法相同，要注意作為實參的結(jié)構(gòu)體變量的成員的類型要與形參的類型相匹配。形參與實參之間仍然是“值傳遞”的方式。

1.結(jié)構(gòu)體變量作為函數(shù)的參數(shù)

舊版的C編譯系統(tǒng)不允許結(jié)構(gòu)體變量作函數(shù)的參數(shù)，ANSIC標(biāo)準(zhǔn)取消了此限制，允許函數(shù)之間傳遞結(jié)構(gòu)體變量，若實參是結(jié)構(gòu)體變量，那么形參也應(yīng)是同類型的結(jié)構(gòu)體變量。

在發(fā)生函數(shù)調(diào)用時，形參結(jié)構(gòu)體變量也要占用空間，接受實參結(jié)構(gòu)體變量傳來的信息，因此函數(shù)之間傳遞結(jié)構(gòu)體變量會帶來時間和空間的巨大開銷。而且，形參與實參之間是“值傳遞”的方式，被調(diào)函數(shù)對形參結(jié)構(gòu)體變量的修改并不能傳遞給實參，即主調(diào)函數(shù)無法得到處理后的數(shù)據(jù)，所以雖然語法上允許，但一般很少采用這種傳遞方式。

2.結(jié)構(gòu)體指針作為函數(shù)的參數(shù)

結(jié)構(gòu)體指針作為函數(shù)的參數(shù)，向函數(shù)傳遞結(jié)構(gòu)體變量的地址，被調(diào)函數(shù)中可以通過實參傳來的結(jié)構(gòu)體變量的地址引用結(jié)構(gòu)體變量，從而在被調(diào)函數(shù)中對結(jié)構(gòu)體變量進(jìn)行修改，也就間接地達(dá)到了改變主調(diào)函數(shù)中的結(jié)構(gòu)體變量的值的目的。

【例10.2】

職工的信息包含職工號、姓名、年齡和工資，編寫程序?qū)⑦@名職工的工資增加100元。要求在函數(shù)input()中輸入職工的各項信息，在函數(shù)process()中修改職工的工資，在函數(shù)output()中輸出職工的信息，在main()函數(shù)中調(diào)用以上3個函數(shù)。

#include<stdio.h>

structperson{

intnumber;

charname[8];

intage;

intwage;

};

voidinput(structperson*p)/*輸入職工信息*/

{

printf("\nnumber:");

scanf("%d",&p->number);

printf("name:");

scanf("%s",p->name);

printf("age:");

scanf("%d",&p->age);

printf("wage:");

scanf("%d",&p->wage);

return;

}

voidprocess(structperson*p)/*修改工資*/

{

p->wage+=100;

return;

}

voidoutput(structperson*p)/*輸出職工信息*/

{

printf("\n%6d,%8s,%2d,%6d",p->number,p->name,p->age,p->wage);

return;

}

main()

{

structpersonw;

printf("\nPleaseinputthedata:");

input(&w);

process(&w);

printf("\nThedatais:");

output(&w);

}

程序運行結(jié)果：

Pleaseinputthedata:

number:1↙

name:a↙

age:25↙

wage:1500↙

Thedatais:

1,a,25,1600本程序中，作為實參的是結(jié)構(gòu)體變量的地址，發(fā)生函數(shù)調(diào)用時，將結(jié)構(gòu)體變量的地址賦給形參指針，這樣形參指針就指向了結(jié)構(gòu)體變量w，因此在各被調(diào)函數(shù)中的各項操作的結(jié)果，在主調(diào)函數(shù)中都能得到。

3.結(jié)構(gòu)體數(shù)組作為函數(shù)的參數(shù)

向函數(shù)傳遞結(jié)構(gòu)體數(shù)組與傳遞其他的數(shù)組一樣，實質(zhì)上傳遞的是數(shù)組的首地址，形參數(shù)組與實參數(shù)組共同占用同一段內(nèi)存單元。

【例10.3】

利用結(jié)構(gòu)體數(shù)組作為函數(shù)的參數(shù)重新編寫例10.1。

#defineN3

#include<stdio.h>

structstudent{

intnum;

charname[8];

struct{

intyear;

intmonth;

intday;

}birthday;

intsc[3];

floatave;

};

voidinput(structstudentst[

],intn)/*輸入學(xué)生的信息*/

{

intj,k;

printf("\n");

for(j=0;j<n;j++){

printf("The%dstudent:\n",j);

printf("number:");

scanf("%d",&st[j].num);

printf("name:");

scanf("%s",st[j].name);

printf("birthday(year,month,day):");

scanf("%d%d%d",&st[j].birthday.year,&st[j].birthday

.month,&st[j].birthday.day);

for(k=0;k<3;k++){

printf("score[%d]:",k);

scanf("%d",&st[j].sc[k]);

}

}

return;

}

voidaverage(structstudentst[

],intn) /*計算學(xué)生的平均成績*/

{

intj,k;

for(j=0;j<n;j++)

{

st[j].ave=0;

for(k=0;k<3;k++)

st[j].ave+=st[j].sc[k]; /*計算總成績*/

st[j].ave/=3; /*計算平均成績*/

}

return;

}

voidoutput(structstudentst[

],intn) /*輸出學(xué)生的信息*/

{

structstudent*p=st;

intk;

printf("\n");

printf("NumberNameYYYY/MM/DDScore[0]--Score[3]Average\n");

for(p=st;p<st+n;p++)

{

printf("%6d",p->num);

printf("%8s",p->name);

printf("%4d/%2d/%2d",p->birthday.year,p->birthday.month,p->birthday.day);

for(k=0;k<3;k++)

printf("%6d",p->sc[k]);

printf("%10.2f\n",p->ave);

}

return;

}

main()

{

structstudentst[N];

input(st,N);

average(st,N);

output(st,N);

}

程序運行結(jié)果：

The0student:

number:1↙

name:aaa↙

birthday(year,month,day):198018↙

score[0]:80↙

score[1]:79↙

score[2]:85↙

The1student:

number:2↙

name:bbb↙

birthday(year,month,day):197959↙

score[0]:87↙

score[1]:85↙

score[2]:90↙

The2student:

number:3↙

name:ccc↙

birthday(year,month,day):198135↙

score[0]:78↙

score[1]:76↙

score[2]:85↙

NumberNameYYYY/MM/DDScore[0]--Score[3]Average

1aaa1980/1/880798581.33

2bbb1979/5/987859087.33

3ccc1981/3/578768579.67

鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu)，是一種動態(tài)分配存儲空間的數(shù)據(jù)結(jié)構(gòu)，應(yīng)用非常廣泛。鏈表是指將若干個稱為結(jié)點的數(shù)據(jù)項按一定的規(guī)則連接起來的表。鏈表的連接原則是：前一個結(jié)點指向后一個結(jié)點，只有通過前一個結(jié)點才能找到后一個結(jié)點。因此，一個鏈表必須已知其表頭指針。10.2鏈表10.2.1內(nèi)存分配函數(shù)和回收函數(shù)

鏈表是一種動態(tài)的存儲結(jié)構(gòu)，根據(jù)需要動態(tài)地分配和釋放結(jié)點。C語言中提供了以下函數(shù)來實現(xiàn)對內(nèi)存空間的申請和釋放。

1.?malloc()函數(shù)

函數(shù)的調(diào)用格式為

malloc(字節(jié)數(shù))

函數(shù)的功能是：在內(nèi)存的動態(tài)存儲區(qū)中分配“字節(jié)數(shù)”個字節(jié)的連續(xù)空間。函數(shù)調(diào)用成功其返回值是所分配的內(nèi)存空間的首地址；函數(shù)調(diào)用失敗(沒有足夠的內(nèi)存)則返回一個空指針NULL。說明：

(1)當(dāng)函數(shù)調(diào)用格式里的“字節(jié)數(shù)”為0時，函數(shù)的返回值為NULL。

(2)使用返回值時，需要檢查返回值是否為NULL。

malloc()函數(shù)的返回值是void類型指針，在使用該函數(shù)時，需要強制類型轉(zhuǎn)換為所需的類型。例如：

structnode{

intdata;

structnode*next;

} /*定義結(jié)構(gòu)體類型*/

structnode*pnode; /*定義指向structnode類型指針變量*/

pnode=(structnode*)malloc(sizeof(structnode)); /*pnode指向函數(shù)malloc分配的內(nèi)存*/

這里，sizeof是C語言中的運算符，其功能是計算類型或變量所占的字節(jié)數(shù)，sizeof(structnode)就是計算structnode這種類型所占的字節(jié)數(shù)。那么，malloc(sizeof(structnode))的功能就是分配一個structnode這種變量所占的內(nèi)存空間，malloc()函數(shù)的返回值是void類型的指針，而指針pnode的基類型為structnode類型，因此需要在malloc(sizeof(structnode))之前加上強制類型轉(zhuǎn)換(structnode*)，將malloc()函數(shù)的返回值轉(zhuǎn)換為指向structnode類型的指針。

malloc()函數(shù)在頭文件malloc.h和stdlib.h中定義。若要使用，必須在程序的開始將這兩個頭文件用文件包含命令包含到本文件中。

2.?calloc()函數(shù)

函數(shù)的調(diào)用格式為

calloc(存儲單元的個數(shù)，存儲類型的字節(jié)數(shù))

函數(shù)的功能是：在內(nèi)存分配大小為“存儲單元的個數(shù)

×

存儲類型的字節(jié)數(shù)”的存儲空間，且新分配的內(nèi)存空間全部初始化為0。函數(shù)調(diào)用成功其返回值是所分配內(nèi)存的首地址；函數(shù)調(diào)用失敗(沒有足夠的內(nèi)存空間)其返回值是NULL。說明：

(1)當(dāng)函數(shù)調(diào)用格式里的“存儲單元的字節(jié)數(shù)”為0時，函數(shù)的返回值為NULL。

(2)使用返回值時，需檢查返回值是否為NULL。

(3)

calloc函數(shù)的返回值是void類型指針，在使用函數(shù)時，需用強制類型轉(zhuǎn)換為所需要的類型。

calloc函數(shù)常用來為一維數(shù)組分配空間。例如：

int*a;那么，下面語句實現(xiàn)長度為10的一維整型數(shù)組申請空間，并且讓a指向數(shù)組的首地址：

a=(int*)calloc(10，sizeof(int));

calloc函數(shù)在頭文件malloc.h和stdlib.h中定義。若要使用，必須在程序的開始將該文件用文件包含命令包含到本文件中。

3.?free()函數(shù)

函數(shù)的調(diào)用格式為

free(指針)

函數(shù)的功能是：釋放由“指針”所指向的內(nèi)存區(qū)域，函數(shù)free沒有返回值。

注意：free()函數(shù)只能用于已由malloc()函數(shù)或calloc()函數(shù)分配地址的指針。

free()函數(shù)在頭文件malloc.h和stdlib.h中定義。若要使用，必須在程序的開始將這兩個頭文件用文件包含命令包含到本文件中。10.2.2用指針和結(jié)構(gòu)體構(gòu)成鏈表

鏈表是一種動態(tài)存儲分配的數(shù)據(jù)結(jié)構(gòu)，它與數(shù)組不同，在定義數(shù)組時必須定義數(shù)組的長度，即數(shù)組一旦定義，則它就含有固定個數(shù)的元素。在實際應(yīng)用中，有時很難預(yù)先確定數(shù)據(jù)元素的個數(shù)，其個數(shù)是不斷變化的，這時若數(shù)組長度定義過小，會沒有足夠的空間來存放數(shù)據(jù)；若數(shù)組長度定義過大，則會造成空間的浪費。那么，在程序的執(zhí)行過程中，若能夠在需要時開辟存儲空間，在不需要時釋放存儲單元，就能合理地使用存儲空間。C語言中提供了動態(tài)分配和釋放內(nèi)存的功能，能夠滿足這種需要。鏈表是由若干個稱為結(jié)點的數(shù)據(jù)項構(gòu)成的，每個結(jié)點都包含數(shù)據(jù)域和指針域，數(shù)據(jù)域用來保存該結(jié)點的數(shù)據(jù)信息，指針域用來保存該結(jié)點的后繼結(jié)點或前驅(qū)結(jié)點的地址。

在此僅介紹單向鏈表，即每個結(jié)點只包含一個指向后繼結(jié)點的鏈域的鏈表類型，關(guān)于其它的鏈表請參考“數(shù)據(jù)結(jié)構(gòu)”的相關(guān)書籍。

鏈表都有一個頭指針，用來保存該鏈表的首地址，即第一個結(jié)點的地址。頭指針是鏈表的標(biāo)志，圖10-2是一個單向鏈表的邏輯示意圖。

圖10-2一個單向鏈表的邏輯示意圖其中，head是指向頭結(jié)點的指針變量，用來保存單向鏈表的第1個結(jié)點的地址，第1個結(jié)點的指針域中又保存著第2個結(jié)點的地址，第2個結(jié)點的指針域中又保存著第3個結(jié)點的地址，直到最后一個結(jié)點，該結(jié)點沒有后繼結(jié)點，它的指針域為空，其值為NULL，在圖中用“^”表示。

單向鏈表的結(jié)點可以定義為結(jié)構(gòu)體類型，結(jié)構(gòu)體中除了表示數(shù)據(jù)信息的若干成員外，還需要一個指向自身結(jié)構(gòu)體類型的指針變量來保存后繼結(jié)點的地址。例如，設(shè)結(jié)點中的信息只有一個整型成員，那么結(jié)點的類型應(yīng)定義為

structnode{

intdata;

structnode*next;

};

該類型的第二個成員next是一個基類型為structnode類型的指針，即next是指向自身結(jié)構(gòu)體類型的指針變量。

【例10.4】

給結(jié)點的指針域賦值，建立一個單向鏈表。

#include<stdio.h>

main()

{

structnode{

struct{

intnum;

floatsc;

}data;

structnode*next;

}node1,node2,node3,*head,*p;

head=&node1;

node1.data.num=1;

node1.data.sc=89;

node1.next=&node2;

node2.data.num=2;

node2.data.sc=78;

node2.next=&node3;

node3.data.num=3;

node3.data.sc=92;

node3.next=NULL;

for(p=head;p!=NULL;p=p->next)

printf("%3d%4.1f\n",p->data.num,p->data.sc);

}

程序中的結(jié)點由數(shù)據(jù)域data和指針域next構(gòu)成；而數(shù)據(jù)域由整型num和單精度型sc兩部分構(gòu)成；指針域是structnode類型的。

程序運行結(jié)果：

189.0

278.0

392.010.2.3單向鏈表的建立

創(chuàng)建鏈表的過程就是從無到有建立鏈表的過程，建立鏈表需要逐個分配結(jié)點的存儲空間，建立結(jié)點間的鏈接關(guān)系。

為方便在鏈表上進(jìn)行各種操作，一般在含有有效信息的所有結(jié)點之間再附加一個“頭結(jié)點”。頭結(jié)點的數(shù)據(jù)域一般不包含任何信息，頭結(jié)點只起方便操作的作用。

建立單向鏈表的主要步驟如下：

(1)生成只含有頭結(jié)點的空鏈表。

(2)讀取數(shù)據(jù)信息，生成新結(jié)點，將數(shù)據(jù)存放于新結(jié)點中，插入新結(jié)點到單向鏈表中。

(3)重復(fù)(2)，直到輸入結(jié)束。

根據(jù)新結(jié)點插入到鏈表位置的不同，建立鏈表的方式分為在表尾插入和在表頭插入兩種，下面分別舉例說明。

【例10.5】

在表尾插入結(jié)點生成單向鏈表。

#include<stdio.h>

#include<malloc.h>

structnode{

chardata;

structnode*next;

};

structnode*create1()

{

structnode*head,*tem,*rear;

charch[80];

inti=0;

head=(structnode*)malloc(sizeof(structnode));

rear=head;

gets(ch);

while(ch[i]!='\0'){

tem=(structnode*)malloc(sizeof(structnode));

tem->data=ch[i];

rear->next=tem;

rear=tem;

i++;

}

rear->next=NULL;

return(head);

}

main()

{

structnode*np;

np=create1();

while((np->next)!=NULL){

np=np->next;

printf("%c",np->data);

}

}程序運行結(jié)果：

xy↙

xy

程序的執(zhí)行過程如下：

main函數(shù)調(diào)用函數(shù)create1，在create1函數(shù)中：

(1)生成頭結(jié)點，讓頭指針head指向頭結(jié)點，此時鏈表中只有一個結(jié)點，當(dāng)前它既是頭結(jié)點也是最后一個結(jié)點(尾結(jié)點)，因此讓尾指針rear也指向這個結(jié)點，如圖10-3(a)所示。

(2)輸入字符串

'xy'

給字符數(shù)組ch，ch[i](i=0)中的字符

'x'

非

'\0'，進(jìn)入循環(huán)體。這時生成新結(jié)點tem，給tem->data賦值為ch[i]的值，如圖10-3(b)所示。

(3)修改尾結(jié)點的指針域指向新結(jié)點，此時tem是新的尾結(jié)點，所以修改rear指針指向rear結(jié)點，如圖10-3(c)所示。

(4)

i++;后，ch[i](i=1)為

'y'

非

'\0'，生成新結(jié)點tem，tem的數(shù)據(jù)域賦值為

'y'，插入tem到表尾，修改rear指針，保持其指向尾結(jié)點，插入

'y'

后鏈表如圖10-3(d)所示。

(5)

i++;后，ch[i](i=2)為

'\0'，循環(huán)結(jié)束，將尾結(jié)點的指針域設(shè)置為空。

圖10-3插入鏈表的結(jié)點

【例10.6】

在表頭結(jié)點插入結(jié)點生成單向鏈表。

#include<stdio.h>

#include<malloc.h>

structnode{

chardata;

structnode*next;

};

structnode*create2()

{

structnode*head,*tem;

charch[80];

inti=0;

head=(structnode*)malloc(sizeof(structnode));

head->next=NULL;

gets(ch);

while(ch[i]!='\0'){

tem=(structnode*)malloc(sizeof(structnode));

tem->data=ch[i];

tem->next=head->next;

head->next=tem;

i++;

}

return(head);

}

main()

{

structnode*np;

np=create2();

while(np->next!=NULL){

np=np->next;

printf("%c",np->data);

}

}

程序的運行結(jié)果：

xy↙

yx

采用表尾插入結(jié)點的方式創(chuàng)建的鏈表，在生成過程中需要始終使用一個尾指針指向最后一個結(jié)點來表示插入的位置，最后表中結(jié)點的次序與生成的次序相一致；而采用表頭插入結(jié)點，最后表中結(jié)點的次序與生成的次序相反。10.2.4鏈表的刪除操作

在一個單向鏈表中刪除指定結(jié)點，首先要找到該結(jié)點的前驅(qū)結(jié)點，然后修改前驅(qū)結(jié)點的指針域指向待刪除結(jié)點的后繼結(jié)點，最后釋放被刪結(jié)點。

【例10.7】編寫函數(shù)實現(xiàn)在已經(jīng)創(chuàng)建的單向鏈表中刪除值為u的結(jié)點(u為參數(shù))。

structnode*delete(structnode*head,intu)

{

structnode*p,*q;

q=head;/*q指向頭結(jié)點，p指向第一個結(jié)點*/

p=head->next;

while(p&&(q->data!=u)){/*查找值為u的結(jié)點p*/

q=p;/*查找過程中，q指向p的前驅(qū)*/

p=p->next;

}

if(p){/*若找到，修改q的指針域指向p的后繼結(jié)點，釋放p*/

q->next=p->next;

free(p);

}

else/*若未找到，輸出相應(yīng)的信息*/

printf("\notfound!");

return(head);

}

找到結(jié)點后，刪除結(jié)點的示意圖如圖10-4所示。

圖10-4刪除鏈表的結(jié)點10.2.5鏈表的插入操作

在鏈表中插入結(jié)點，首先要找到插入位置，再進(jìn)行插入。假設(shè)指針變量s指向待插入結(jié)點，那么根據(jù)插入位置的不同，分為將s插入到結(jié)點之后和將s插入到結(jié)點s之前。

假設(shè)p所指為指定結(jié)點，那么將s所指結(jié)點插入到p所指結(jié)點之后可用這兩句C語句描述：

s->next=p->next; /*s所指結(jié)點的指針域指向p所指結(jié)點的后繼結(jié)點。*/

p->next=s; /*p所指結(jié)點的指針域指向s所指結(jié)點，即新插入結(jié)點。*/

要在指定結(jié)點p之前插入新結(jié)點，除了使得新結(jié)點的指針域指向p外，還需要修改p的前驅(qū)結(jié)點的指針域指向新結(jié)點。因為單向鏈表的結(jié)點中只有保存后繼結(jié)點地址的指針域，所以插入到指定結(jié)點p之前，首先要找到p的前驅(qū)結(jié)點q，那么，這時插入到p結(jié)點之前，就相當(dāng)于插入q結(jié)點之后。

【例10.8】

編寫函數(shù)實現(xiàn)在已經(jīng)創(chuàng)建的單向鏈表中的值為u的結(jié)點之前插入一個值為v的結(jié)點(其中u、v為參數(shù))。

structnode*insert(structnode*head,intu,intv)

{

structnode*p,*q,*s;

s=(structnode*)malloc(sizeof(structnode)); /*生成新結(jié)點s*/

s->data=v; /*將v存放在新結(jié)點中*/

q=head; /*q指向頭結(jié)點，p指向第一個節(jié)點*/

p=head->next;

while(p&&(p->data!=u)){ /*查找值為u的結(jié)點*/

q=p; /*查找過程中q指向p的前驅(qū)*/

p=p->next;

}

s->next=p; /*插入s結(jié)點到p結(jié)點之前，若未找到則插入到表尾*/

q->next=s;

return(head);

}

10.3.1共用體類型的定義

共用體類型是一種用戶自定義構(gòu)造型數(shù)據(jù)類型，和結(jié)構(gòu)體一樣，是由類型不同的、固定個數(shù)的成員所組成，但結(jié)構(gòu)體的成員是同時存在的，分別占用不同的內(nèi)存單元；而對于共用體而言，其所有成員共同占用同一段內(nèi)存。從微觀上看，某一時刻只能有某一個成員起作用，其它成員是不存在的。10.3共用體共用體類型定義的一般形式為

union共用體名{

類型名1成員名1；

類型名2成員名2；

……

類型名n成員名n；

}說明:

(1)

union是關(guān)鍵字，標(biāo)志共用體類型。union后面跟的是共用體類型的名字，共用體的命名應(yīng)符合標(biāo)識符的命名規(guī)則。

(2)花括號后面是共用體的各個成員，定義成員的方式和定義變量相同，各個成員之間用分號分隔，共用體類型的定義以分號結(jié)束。

(3)共用體類型的成員可以是基本類型，也可以是構(gòu)造類型，但通常情況下共用體的成員是基本類型。

(4)共用體的所有成員共同占用同一段內(nèi)存，所有成員的起始地址是相同的，整個共用體所占的內(nèi)存單元的大小等于所有成員中占用內(nèi)存單元最多的那個成員所占的字節(jié)數(shù)。

例如：

unionun{

charc;

intk;

floatf;

};上述定義表示定義共用體類型un，它有3個成員c、k、f，其中c是字符型，需占一個字節(jié)；k是整型，需占兩個字節(jié)；f是單精度實型的，需占4個字節(jié)；那么，這種共用體共占4個字節(jié)。c占用第1個字節(jié)；k占用第1個和第2個字節(jié)；f占用所有的4個字節(jié)。在使用時，某一時刻只能使用c、k、f中的一個，不能同時使用。10.3.2共用體變量的定義

和結(jié)構(gòu)體一樣，共用體類型的定義只是表示定義了一種模型，變量才是存放數(shù)據(jù)的實體。定義共用體變量的方式和定義結(jié)構(gòu)體變量的方式類似，也有3種方式。

(1)用已定義的共用體類型定義共用體變量。

unionun{

charc;

intk；

floatf；

}; /*定義共用體類型。*/

unionunun1,un2; /*定義共用體變量un1、un2。*/

(2)定義共用體類型的同時定義共用體變量。

unionun{

charc；

intk；

floatf；

}un1,un2;

(3)定義無名共用體類型的同時定義共用體變量。

union{

charc;

intk;

floatf;

}un1,un2;

指向共用體的指針變量的定義，與指向結(jié)構(gòu)體的指針變量的定義方式是相同的，在此不再贅述。10.3.3共用體變量的引用

對于共用體變量，只能引用它的成員，而不能引用整個共用體變量。引用共用體變量的方式和引用結(jié)構(gòu)體變量的方式類似，其引用方式為

共用體變量名.成員名

例如：un1.c、un2.f和un1.k。

若共用體的成員是構(gòu)造類型的，則需要逐級應(yīng)用至最低級的成員。

同樣，也可以通過指向共用體變量的指針變量來引用共用體變量的成員，其引用方式為

(*共用體指針變量名).成員名

或

共用體指針變量名->成員名

這兩種表示形式是完全等價的。例如，若已有定義：

unionun*pu=&unl;

那么以下是合法的引用方式：

(*pu).c

pu->k

共用體變量的地址與共用體成員的地址是相同的，如對上面定義的共用體變量unl而言，&ul、&ul.c、&ul.k、&ul.f是相等的，但是它們的類型是不同的。在給共用體變量賦值時，只能對共用體的一個成員賦值，而不能對整個共用體變量賦值，也不能對共用體變量在定義時初始化。因為共用體的成員共用一段連續(xù)的內(nèi)存單元，若多次給共用體的成員賦值，那么，每次賦值都會覆蓋原來的值，也就是說，對共用體變量而言，只有最近一次的賦值是有效的，而再去使用原來的成員的值是不合適的。10.3.4共用體類型數(shù)據(jù)在內(nèi)存中的存儲

共用體類型變量和結(jié)構(gòu)體類型變量的定義形式相同，但有著本質(zhì)區(qū)別。區(qū)別表現(xiàn)為：結(jié)構(gòu)體類型變量的不同成員分別使用不同的內(nèi)存空間，一個結(jié)構(gòu)體類型變量所占用的內(nèi)存空間的大小，至少為該變量各個成員所占用的內(nèi)存大小的總和(有可能有對齊要求)，結(jié)構(gòu)體變量中的各個成員相互獨立，彼此不占用同一內(nèi)存空間；而共用體類型變量中的各個成員則共同使用同一內(nèi)存空間(但不在同一時刻)，共用體變量中的各個成員都有相同的起始地址，這個起始地址就是該共用體變量的起始地址。一個共用體變量所占用的內(nèi)存空間的大小與它的某一成員所需的存儲空間的大小相同，該成員是各個成員中占用存儲空間最大的那一個。

例如：

union{

charc;

intk;

floatf;

}un1;共用體變量un1是由字符型變量c、整型變量k和實型變量f三個成員構(gòu)成的，三個成員的起始地址相同，共用體變量un1所占用的存儲空間的大小為三個成員中占用存儲空間最大的那個，即為實型變量f，共4個字節(jié)。

【例10.9】

分析下列程序的輸出結(jié)果，進(jìn)而說明共用體的成員是共址的。

#include<stdio.h>

uniondata{

charc_data;

inti_data;

floatf_data;

};

main()

{

uniondatad1;

d1.c_data='a';

d1.i_data=5;

d1.f_data=3.7;

printf("%c%d%f\n",d1.c_data,d1.i_data,d1.f_data);

printf("%d\n",sizeof(d1));

printf("%p%p%p%p\n",&d1.c_data,&d1.i_data,&d1.f_data,&d1);

}

程序運行結(jié)果(注：系統(tǒng)不同，輸出結(jié)果會有差異)：

=-131073.700000

4

FFD4FFD4FFD4FFD4

說明：

(1)該程序中，首先定義了一個data類型，其擁有3個成員，分別為字符型、整型和實型。由該共用體類型定義了共用體變量d1，并給其成員分別賦值。當(dāng)輸出d1的3個成員的值時，前兩個成員的輸出值顯然是無意義的，只有最后一個成員是有意義的，其值為3.7。這說明：某一時刻一個共用體變量中只有一個成員起作用，其它成員不起作用。

(2)輸出sizeof(d1)的值為4，這說明共用體變量d1占內(nèi)存4個字節(jié)。在多個共用體成員共占一個內(nèi)存地址時，該地址所指向的內(nèi)存空間是所有成員中占內(nèi)存空間最大的成員所占的內(nèi)存空間。該例中的3個成員所占內(nèi)存字節(jié)數(shù)分別為1、2和4，最大的是4，因此，共用體變量d1所占內(nèi)存空間為4個字節(jié)。

(3)輸出共用體變量d1的3個成員的內(nèi)存地址都是相同的，并且與共用體變量d1的地址值也是相同的，可見共用體變量各成員是共址的。

當(dāng)然，程序稍加修改，便可得到3個成員變量及變量d1的地址。修改后的程序如下：

#include<stdio.h>

uniondata{

charc_data;

inti_data;

floatf_data;

};

main()

{

uniondatad1;

d1.c_data='a';

printf("%c",d1.c_data);

d1.i_data=5;

printf("%d",d1.i_data);

d1.f_data=3.7;

printf("%f\n",d1.f_data);

printf("%d\n",sizeof(d1));

printf("%p%p%p%p\n",&d1.c_data,&d1.i_data,&d1.f_data,&d1);

}程序運行結(jié)果：

a53.700000

4

FFD2FFD2FFD2FFD2

10.4.1枚舉類型的定義

在實際問題中，有些數(shù)據(jù)的取值用有意義的名字表示更直觀，比如，月份、星期用相應(yīng)的英文單詞來表示比用整型數(shù)據(jù)表示更能增加程序的可讀性，并且它們的取值應(yīng)該限定在合理的范圍內(nèi)。10.4枚舉類型在C語言中，枚舉類型就是若干個采用標(biāo)識符表示的整型常量的集合。枚舉類型的定義方式如下：

enum枚舉類型名{枚舉常量1，枚舉常量2，……，枚舉類型n};

說明：

enum是用來定義枚舉類型的關(guān)鍵字，枚舉類型名是用戶定義的類型名，枚舉常量是用戶定義的有意義的標(biāo)識符，即羅列出該枚舉類型各種可能的、合法的取值。例如：

定義表示月份的枚舉類型：

enummonths{jan,feb,mar,apr,may,jun,jul,aug,sep,oct,nov,dec};

定義表示星期的枚舉類型：

enumweek{sun,mon,tue,wed,thu,fri,sat};

枚舉常量是有確定值的，每一個枚舉常量隱含著一個整型的值，在默認(rèn)的情況下，第一個枚舉常量的值是0，以后每一個枚舉常量的值是前一個常量的值加1的結(jié)果。如上面月份的定義，各枚舉常量的值是0～11。也可以人為地指定枚舉常量的值，如：

enummonths{jan=1,feb,mar,apr,may,jun,jul,aug,sep,oct,nov,dec};

枚舉常量jan被顯式地賦值為1，那么，沒有被顯式賦值的枚舉常量的值和前一個相比逐個增1，即在本類型中，各枚舉常量的值為1～12。

再如：enumweek{sun=7,mon=1,tue,wed,thu,fri,sat};

sun被指定為7，mon被指定為1，后面的常量tue的值為2，wed的值為3，thu的值為4，fri的值為5，sat的值為6。定義時，顯式地指定枚舉常量的值，其實是指定枚舉常量間的順序。在定義枚舉類型后，對于已定義的枚舉常量是不能賦值的，因為常量的值是確定的，不能被修改。10.4.2枚舉類型變量的定義和引用

1.枚舉類型變量的定義

定義枚舉類型變量的方式和定義結(jié)構(gòu)體變量的方式類似，也有3種方式：

(1)用已定義的枚舉類型定義枚舉類型變量：

enumweek{sun,mon,tue,wed,thu,fri,sat};

enumweekw1,w[3];

(2)定義枚舉類型的同時定義枚舉類型變量：

enumweek{sun,mon,tue,wed,thu,fri,sat}w1,w[3];

(3)定義無名枚舉類型的同時定義枚舉類型變量：

enum{sun,mon,tue,wed,thu,fri,sat}w1,w[3];

2.枚舉類型變量的引用

枚舉類型變量的引用方式和普通變量一樣，但枚舉類型變量的取值只能是其枚舉類型所枚舉的各個常量，一般給枚舉類型變量賦值枚舉常量。

注意：

雖然編譯系統(tǒng)將枚舉類型處理為整型，但整型和枚舉類型之間不能相互賦值；若要賦值，需進(jìn)行強制類型轉(zhuǎn)換。如：

w1=mon;

we[0]=(enumweek)1;

以上都是合法的賦值方式。

we[2]=3;

這不是合法的賦值方式。說明：

(1)可以比較枚舉類型變量的大小，枚舉類型變量的比較相當(dāng)于比較它們所隱含的整數(shù)值，如已有賦值：we[0]=mon;we[1]=sat;，那么，we[0]的值小于we[1]的值。

(2)枚舉類型變量的值在該枚舉類型中枚舉的常量所代表的整數(shù)值范圍內(nèi)，因此枚舉類型變量可以作為循環(huán)變量來控制循環(huán)。

【例10.10】

編程實現(xiàn)輸出12個月份的英文名稱。

#include<stdio.h>

enummonths{jan=1,feb,mar,apr,may,jun,jul,aug,sep,oct,nov,dec};

main()

{

enummonthsm;

char*name[]={"January","February","March","April","May","June","July","August","September",

"October","November","December"};

for(m=jan;m<=dec;m++)

printf("%2d:%s\n",m,name[m-1]);

}

程序運行結(jié)果：

1:January

2:February

3:March

4:April

5:May

6:June

7:July

8:August

9:September

10:October

11:November

12:December

本程序中，在函數(shù)體外定義了枚舉類型enummonths，其中的枚舉常量是12個月份的英文縮寫，并且指定第一個枚舉常量的值為1，則后面的枚舉常量順次得到值2、3、4、…、12。

對于枚舉常量，并不能采用什么方法來輸出枚舉常量名，就像符號常量一樣，輸出的只能是它的值，而不能輸出常量名。采用d格式符輸出的是枚舉常量所隱含的整數(shù)值。因此，要輸出這12個字符串，本程序采用輸出指針數(shù)組元素所指向的字符串的方