第8章 全國(guó)計(jì)算機(jī)等級(jí)考試計(jì)算機(jī)二級(jí)C語(yǔ)言 結(jié)構(gòu)體 和共用體

造富羸等教育“十

第8章結(jié)構(gòu)體和共用體

前面的章節(jié)中已經(jīng)介紹了各種基本數(shù)據(jù)類型、數(shù)組和指針

。但只有這些數(shù)據(jù)類型還難以處理一些比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。本章

將以前面介紹的數(shù)據(jù)類型為基礎(chǔ)，進(jìn)一步介紹結(jié)構(gòu)體類型、共用體

類型和枚舉類型。

普通羸等教育“十

第8章結(jié)構(gòu)體和共用體

8.1結(jié)構(gòu)體

8.2動(dòng)態(tài)內(nèi)存分配與鏈表

8.3共用體類型n

8.4枚舉類型

8.5用戶自定義類型n

8.6程序舉例n

造富羸等教育“十

8.1結(jié)構(gòu)體

SI鼠

修|8.1結(jié)構(gòu)體造翳等教育“十

8.1.1結(jié)構(gòu)類型定義

在實(shí)際問(wèn)題中，一組數(shù)據(jù)往往具有不同的數(shù)據(jù)類型。例如，在學(xué)生登記表

中，姓名應(yīng)為字符型；學(xué)號(hào)可為整型或字符型；年齡應(yīng)為整型;性別應(yīng)為字符型;成

績(jī)可為整型或?qū)嵭?。但這些顯然不能用一個(gè)數(shù)組來(lái)存放這一組數(shù)據(jù)。因?yàn)閿?shù)組中各

元素的類型和長(zhǎng)度都必須一致，以便于編譯系統(tǒng)處理。為了解決這個(gè)問(wèn)題，C語(yǔ)言

中給出了另一種構(gòu)造數(shù)據(jù)類型一“結(jié)構(gòu)體”。

“結(jié)構(gòu)體”是一種構(gòu)造類型，它是由若干“成員”組成的。每一個(gè)成員可

以是一個(gè)基本數(shù)據(jù)類型或者又是一個(gè)構(gòu)造類型。結(jié)構(gòu)體既然是一種“構(gòu)造”而成的

數(shù)據(jù)類型，那么在說(shuō)明和使用之前必須先定義它，也就是構(gòu)造它。如同在說(shuō)明和調(diào)

用函數(shù)之前要先定義函數(shù)一樣。

修|8.1結(jié)構(gòu)體造翳等教育“十

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

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

{

結(jié)構(gòu)成員的說(shuō)明；

）；

成員表由若干個(gè)成員組成，每個(gè)成員都是該結(jié)構(gòu)體的一個(gè)組成部分。對(duì)每個(gè)成員也

必須作類型說(shuō)明，其形式為：

類型說(shuō)明符成員名；

成員名的命名應(yīng)符合標(biāo)識(shí)符的書(shū)寫(xiě)規(guī)定。例如：

structstu

{intnum;

charname[20];

charsex;

floatscore;

）；

修|8.1結(jié)構(gòu)體造翳等教育“十

在這個(gè)結(jié)構(gòu)體定義中，結(jié)構(gòu)體名為stu,該結(jié)構(gòu)體由4個(gè)成員組成。第一

個(gè)成員為num,整型變量；第二個(gè)成員為name,字符數(shù)組變量；第三個(gè)成員為sex

,字符變量；第四個(gè)成員為score,實(shí)型變量。應(yīng)注意在括號(hào)“}”后的分號(hào)是不

可少的。結(jié)構(gòu)體定義之后，即可進(jìn)行變量說(shuō)明。凡說(shuō)明為結(jié)構(gòu)體Stu的變量都由上

述4個(gè)成員組成。由此可見(jiàn)，結(jié)構(gòu)是一種復(fù)雜的數(shù)據(jù)類型，是數(shù)目固定，類型不同

的若干有序變量的集合。

修|8.1結(jié)構(gòu)體造翳等教育“十

8.1.2結(jié)構(gòu)體類型變量的說(shuō)明

說(shuō)明結(jié)構(gòu)體變量有以下三種方法。以上面定義的stu為例來(lái)加以說(shuō)明。

(1)先定義結(jié)構(gòu)體類型，再說(shuō)明結(jié)構(gòu)體變量

例如：

structstu

{intnum;

charname[20];

charsex;

floatscore;

)；

structstuboyl,boy2;

說(shuō)明了兩個(gè)變量boyl和boy2為stu結(jié)構(gòu)類型。也可以用宏定義使用一個(gè)符號(hào)常量來(lái)表示

一個(gè)結(jié)構(gòu)類型，例如：

#defineSTUstructstu

STU

{intnum;

charname[20];

charsex;

floatscore;

）；

STUboyl,boy2;

8.1結(jié)構(gòu)體高等教育“十

(2)在定義結(jié)構(gòu)體類型的同時(shí)說(shuō)明結(jié)構(gòu)體變量

例如:

structstu

{intnum;

charname[20];

charsex;

floatscore;

}boyl,boy2;

(3)直接說(shuō)明結(jié)構(gòu)體變量

例如:

struct

{intnum;

charname[20];

charsex;

floatscore;

}boyl,boy2;

修|8.1結(jié)構(gòu)體造翳等教育“十

第三種方法與第二種方法的區(qū)別在于第三種方法中省去了結(jié)構(gòu)體名，而直

接給出結(jié)構(gòu)體變量。三種方法中說(shuō)明的boyl,boy2變量都具有相同的結(jié)構(gòu)。說(shuō)明了

boyl,boy2變量為stu類型后，即可向這兩個(gè)變量中的各個(gè)成員賦值。

在上述Stu結(jié)構(gòu)體定義中，所有的成員都是基本數(shù)據(jù)類型或數(shù)組類型。成員

也可以又是一個(gè)結(jié)構(gòu)體類型，即構(gòu)成了嵌套的結(jié)構(gòu)體。

修|8.1結(jié)構(gòu)體造翳等教育“十

例如：首先定義一個(gè)結(jié)構(gòu)體date,由

structdate

month（月）、day（日）、year（年）三個(gè)成員組

{intmonth;

intday;成。在定義并說(shuō)明變量boyl和boy2時(shí)，

intyear;其中的成員birthday被說(shuō)明為data結(jié)構(gòu)體類

}；型。成員名可與程序中其它變量同名，互不

struct

{intnum;干擾。結(jié)構(gòu)體變量成員的表示方法，在程序

charname[20];中使用結(jié)構(gòu)體變量時(shí)，往往不把它作為一個(gè)

charsex;整體來(lái)使用。

structdatebirthday;

floatscore;

Jboyl,boy2;

說(shuō)明：結(jié)構(gòu)體在內(nèi)存中存儲(chǔ)容量是各成員容量之和，這是與后面聯(lián)合體的重要區(qū)別。

修|8.1結(jié)構(gòu)體造翳等教育“十

8.1.3結(jié)構(gòu)體變量的引用

一般情況下，不能對(duì)一個(gè)結(jié)構(gòu)體變量作為整體引用，只能引用其中的成員。

結(jié)構(gòu)體變量中成員引用的一般形式為：

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

其中，是域成員運(yùn)算符，是C語(yǔ)言中優(yōu)先級(jí)最高的運(yùn)算符之一。

例如：boyl.num即第一個(gè)人的學(xué)號(hào)，boy2.sex即第二個(gè)人的性別。如果成

員本身又是一個(gè)結(jié)構(gòu)體，則必須逐級(jí)找到最低級(jí)的成員才能使用。

例如：boyl.birthday,month即第一個(gè)人出生的月份。成員可以在程序中單

獨(dú)使用，與普通變量完全相同。

修|8.1結(jié)構(gòu)體造翳等教育“十

8.1.4結(jié)構(gòu)體變量的賦值

對(duì)于結(jié)構(gòu)體變量，只有以下兩種情況可以對(duì)結(jié)構(gòu)體變量賦值。

(1)結(jié)構(gòu)體變量整體賦值

例如：

boy2=boyl;

(2)取結(jié)構(gòu)體變量地址

例如：

&boy2;

&boyl;

注意:結(jié)構(gòu)體變量名是地址常量,含義與數(shù)組名和函數(shù)名相同，不能對(duì)結(jié)構(gòu)體變量做

整體輸入/輸出。例如：

scanf(〃％d,%s,%c,〃，&boyl);

printf(〃％d,%s,%c,%f〃，boyl);

這些語(yǔ)句都是不允許的，只能對(duì)結(jié)構(gòu)體成員進(jìn)行輸入/輸出。

修|8.1結(jié)構(gòu)體造翳等教育“十

例8.1給結(jié)構(gòu)體變量賦值并輸出其值。

ttinclude<stdio.h>

voidmain()

{structstu/*定義結(jié)構(gòu)體stu*/

{intnum;

char*name;

charsex;

floatscore;

}boyl,boy2;/*定義stu類型的變量boyl、boy2

*/

boyl.num=102;

boy1.name=〃Zhangping〃；

printf("inputsexandscore:\n，z);

scanf(z，%c%fz，,&boyl.sex,&boyl.score);/*給boyl的成員sex和score賦值*/

boy2=boyl;/*把boyl整

體賦給boy2*/

printf("number/d\nnaineMs'n”,boy2.num,boy2.name);

printf(〃sex=%c\nscore=%6.2f\n〃，boy2.sex,boy2.score);

修|8.1結(jié)構(gòu)體造翳等教育“十

程序運(yùn)行結(jié)果：

inputsexandscore:

M96Z

number」02

name=Zhangping

sex二M

score=J96.00

本程序中用賦值語(yǔ)句給num和name兩個(gè)成員賦值，name是一個(gè)字符串指針

變量。用scanf()函數(shù)動(dòng)態(tài)地輸入sex和score成員值，然后把boyl的所有成員的值

整體賦予boy2。最后分別輸出boy2的各個(gè)成員值。

修|8.1結(jié)構(gòu)體造翳等教育“十

8.1.5結(jié)構(gòu)體變量的初始化

如果結(jié)構(gòu)體變量為全局變量或者靜態(tài)變量，則可以對(duì)它做初始

化賦值。對(duì)局部或自動(dòng)結(jié)構(gòu)體變量不能做初始化賦值。

修|8.1結(jié)構(gòu)體造翳等教育“十

例8.2外部結(jié)構(gòu)體變量初始化。

ttinclude<stdio.h>

structstu/*定義結(jié)構(gòu)體*/

{intnum;

char*name;

charsex;

floatscore;

}boy2,boy1={102,z/Zhangping〃，'M',78.5};/*對(duì)變量boyl的成員初始化*/

voidmain()

{boy2=boyl;/*把boyl整體賦給boy2*/

printf(〃number=%d\nname二％s\n〃，boy2.num,boy2.name);

printf(〃sex=%c\nscore=%6.2f\n〃，boy2.sex,boy2.score);

修|8.1結(jié)構(gòu)體造翳等教育“十

程序運(yùn)行結(jié)果：

number=102

name=Zhangping

sex=M

score=J*78.50

本程序中，boy2,boyl均被定義為外部結(jié)構(gòu)體變量，并對(duì)boyl作了初始

化賦值。在main。函數(shù)中，把boyl的值整體賦予boy2,然后用兩個(gè)printf()語(yǔ)句

輸出boy2各成員的值。

修|8.1結(jié)構(gòu)體造翳等教育“十

例8.3靜態(tài)結(jié)構(gòu)體變量初始化。

ttinclude<stdio.h>

voidmain()

{staticstructstu/*定義靜態(tài)結(jié)構(gòu)體*/

{intnum;

char*name;

charsex;

floatscore;

}boy2,boyl={102,Zhangping〃，'M',78.5};/*對(duì)變量boyl的成員初始化*/

boy2=boyl;

printf("numberMd\nname或s'n”,boy2.num,boy2.name);

printf(，zsex=%c\nscore=%6.2f\n〃，boy2.sex,boy2.score);

本程序是把boyl,boy2都定義為靜態(tài)局部的結(jié)構(gòu)體變量，同樣可以做初始化賦

值。

修|8.1結(jié)構(gòu)體造翳等教育“十

8.1.6結(jié)構(gòu)體數(shù)組

一個(gè)結(jié)構(gòu)體變量可以處理一個(gè)對(duì)象，如果有多個(gè)對(duì)象，則需要多個(gè)結(jié)構(gòu)體變

量，數(shù)組的元素也可以是結(jié)構(gòu)體類型的，因此可以構(gòu)成結(jié)構(gòu)體數(shù)組。結(jié)構(gòu)體數(shù)組的每

一個(gè)元素都是具有相同結(jié)構(gòu)體類型的下標(biāo)結(jié)構(gòu)體變量。在實(shí)際應(yīng)用中，經(jīng)常用結(jié)構(gòu)體

數(shù)組來(lái)表示具有相同數(shù)據(jù)結(jié)構(gòu)的一個(gè)群體。如一個(gè)班的學(xué)生檔案，一個(gè)車間職工的工

資表等

人、°結(jié)構(gòu)體數(shù)組的定義方法和結(jié)構(gòu)體變量相似，也有三種方式：

(1)先定義結(jié)構(gòu)體類型，再定義結(jié)構(gòu)體數(shù)組。

例如:

structstu

{intnum;

char*name;

charsex;

floatscore;

)；

structstuboy[5];

定義了一個(gè)結(jié)構(gòu)體數(shù)組boy,共有5個(gè)元素，boy[0]-boy[4]每個(gè)數(shù)組元素

都具有structstu的結(jié)構(gòu)體形式。o

8.1結(jié)構(gòu)體高等教育“十

(2)在定義結(jié)構(gòu)體類型的同時(shí)定義結(jié)構(gòu)體數(shù)組。

例如：

structstu

{intnum;

char*name;

charsex;

floatscore;

}boy[5];

(3)直接定義結(jié)構(gòu)體數(shù)組。

例如:

struct

{intnum;

char*name;

charsex;

floatscore;

}boy[5];

修|8.1結(jié)構(gòu)體造翳等教育“十

對(duì)外部結(jié)構(gòu)體數(shù)組或靜態(tài)結(jié)構(gòu)體數(shù)組可以做初始化賦值。例如：

structstu

{intnum;

char*name;

charsex;

floatscore;

}boy[5]={{101,z，Liping〃，'M',45},

{102,z/Zhangping〃,'M',62.5},

{103,"Hefang〃，'F',92.5},

{104,“Chengling〃，'F',87},

{105,z，Wangming〃，'M',58}};

當(dāng)對(duì)全部元素做初始化賦值時(shí)，也可不給出數(shù)組長(zhǎng)度。

修|8.1結(jié)構(gòu)體造翳等教育“十

例8.4計(jì)算學(xué)生的平均成績(jī)和不及格的人數(shù)。

^include<stdio.h>

structstu/*定義

結(jié)構(gòu)體*/

{intnum;

char*name;

charsex;

floatscore;

}boy[5]={{101,Z/Liping",'M',45},{102,“Zhangping〃，'M',62.5},{103,〃He

，，5

fang','F',92.5},{104,“Chengling','F',87},{105,〃Wangming)M*,58}};

/*對(duì)結(jié)構(gòu)體數(shù)組元素初始化*/

voidmain()

{inti,c=0;

floatave,s=0;

for(1=0;i<5;i++)

{s+=boy[i].score;

if(boy[i].score<60)

c+二1;

)

printf(〃s=%6.2f\n〃，s);

ave=s/5;/*計(jì)算

平均成績(jī)*/〃

printf(，zaverage=%6.2f\ncount=%d\n〃，ave,c);

修|8.1結(jié)構(gòu)體造翳等教育“十

程序運(yùn)行結(jié)果：

s=345.00

average=169.00

count=2

本例程序中定義了一個(gè)外部結(jié)構(gòu)體數(shù)組boy,共5個(gè)元素，并作了初

始化賦值。在main函數(shù)中用for語(yǔ)句逐個(gè)累加各元素的score成員值存于s之

中，如score的值小于60（不及格），即計(jì)數(shù)器C加1,循環(huán)完畢后計(jì)算平均成績(jī)

,并輸出全班總分、平均分及不及格人數(shù)。

普通羸等教育“十

8.1結(jié)構(gòu)體

例8.5建立同學(xué)通訊錄。

^include<stdio.h>

ttdefineNUM2

structmem/*定

義結(jié)構(gòu)體*/

{charname[20];

charphone[10];

)；

voidmain()

{structmemman[NUM];

inti;

for(i=0;i<NUM;i++)/*輸

入通訊錄*/〃〃

{printf(z，inputname:");

gets(man[i].name);

printf(z，inputphone:");

gets(man[i].phone);

printf(，，Name\t\tPhone\n，z);

for(i=0;i<NUM;i++)/*輸

出通訊錄*/〃〃

printf(〃％s\t%s\n〃，man[i].name,man.phone);

修|8.1結(jié)構(gòu)體造翳等教育“十

程序運(yùn)行結(jié)果：

inputname:Zhangjun/

inputphone:88888888Z

inputname:Wangfang/

inputphone:99999999Z

NamePhone

Zhangjun88888888

Wangfang99999999

本程序中定義了一個(gè)結(jié)構(gòu)體類型mem,它有兩個(gè)成員name和phone,用來(lái)

表示姓名和電話號(hào)碼。在主函數(shù)中定義man為具有mem類型的結(jié)構(gòu)體數(shù)組。在for

語(yǔ)句中，用gets()函數(shù)分別輸入各個(gè)元素中兩個(gè)成員的值。然后又在for語(yǔ)句中用

printf()語(yǔ)句輸出各元素中兩個(gè)成員值。

修|8.1結(jié)構(gòu)體造翳等教育“十

8.1.7指向結(jié)構(gòu)體變量的指針變量

結(jié)構(gòu)體指針變量是一個(gè)指針變量，用來(lái)指向改變量所分配的存儲(chǔ)區(qū)域的首

地址。結(jié)構(gòu)體指針變量還可以用來(lái)指向結(jié)構(gòu)體數(shù)組中的元素。結(jié)構(gòu)體指針與以前介

紹的各種指針在特性和使用方法上完全相同。結(jié)構(gòu)體指針變量的運(yùn)算也按照C語(yǔ)言的

地址計(jì)算規(guī)則進(jìn)行的。例如，結(jié)構(gòu)體指針變量加1將指向內(nèi)存中下一個(gè)結(jié)構(gòu)體變量，

結(jié)構(gòu)體指針變量自身地址值的增加量取決于它所指向的結(jié)構(gòu)體變量的數(shù)據(jù)長(zhǎng)度(

sizeof()函數(shù)獲取)。總之，結(jié)構(gòu)體指針變量是指向一個(gè)結(jié)構(gòu)體變量的指針變量。

修|8.1結(jié)構(gòu)體造翳等教育“十

1.結(jié)構(gòu)體指針變量的定義

定義結(jié)構(gòu)體指針變量的一般形式為：

struct結(jié)構(gòu)體類型名*結(jié)構(gòu)指針變量名；

例如：

structstu

{intnum;

char*name;

charsex;

floatscore;

}boy,*pstu;

pstu=&boy;

也可以定義結(jié)構(gòu)體類型后再定義結(jié)構(gòu)體指針變量。

結(jié)構(gòu)體名和結(jié)構(gòu)體變量是兩個(gè)不同的概念，不能混淆。結(jié)構(gòu)體名只能表示一

個(gè)結(jié)構(gòu)體形式，編譯系統(tǒng)并不對(duì)它分配內(nèi)存空間。只有當(dāng)某變量被說(shuō)明為這種類型的

結(jié)構(gòu)時(shí)，才對(duì)該變量分配存儲(chǔ)空間。有了結(jié)構(gòu)指針變量，就能更方便地訪問(wèn)結(jié)構(gòu)變量

的各個(gè)成員。

修|8.1結(jié)構(gòu)體造翳等教育“十

2.結(jié)構(gòu)體指針變量的賦值

結(jié)構(gòu)體指針變量必須先賦值后使用。賦值是把結(jié)構(gòu)體變量的首地址賦給該指

針變量，不能把結(jié)構(gòu)名賦給該指針變量。例如，不能寫(xiě)成pstu二&stu;。

注意：pstu已為指向一個(gè)結(jié)構(gòu)體類型的指針變量，它只能指向結(jié)構(gòu)體變量而

不能指向它其中一個(gè)成員。換句話說(shuō):pstu只能存放結(jié)構(gòu)體變量的地址。例如，不能寫(xiě)

成pstu二&stu.num;o

修|8.1結(jié)構(gòu)體造翳等教育“十

3.結(jié)構(gòu)體指針變量的引用

定義好一個(gè)結(jié)構(gòu)體指針變量之后，就可以對(duì)該指針變量進(jìn)行各種操作。例

如，給一個(gè)結(jié)構(gòu)體變量指針賦一個(gè)地址值，輸出一個(gè)結(jié)構(gòu)體變量指針的成員值，訪

問(wèn)結(jié)構(gòu)體變量指針?biāo)赶虻淖兞康某蓡T等。引用結(jié)構(gòu)體指針變量的一般形式為：

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

或

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

例如：

(*pstu).num;

或

pstu-〉num;

應(yīng)該注意0^$的)兩側(cè)的括號(hào)不可少，因?yàn)槌蓡T符的優(yōu)先級(jí)高于

“*”。如去掉括號(hào)寫(xiě)作*pstu.num,則等效于*(pstu.num),這樣，意義就完全不

對(duì)了。

修|8.1結(jié)構(gòu)體造翳等教育“十

例8.6分析下面程序的運(yùn)行結(jié)果。

ttinclude<stdio.h>

structstu/*定義結(jié)構(gòu)體

*/

{intnum;

char*name;

charsex;

floatscore;

}boyl={102,“Zhangping〃，'M',78.5},*pstu;

voidmain()

{pstu=&boyl;

printf(〃nuniber=%d\nnanie二％s\n〃，boyl.num,boyl.name);

printf(〃sex=%c\nscore=%6.2f\n\n〃，boyl.sex,boyl.score);

printf(〃number=%d\nnaine二％s\n〃，(*pstu).num,(*pstu).name);

printf(，，sex=%c\nscore=%6.2f\n\n〃，(*pstu).sex,(*pstu).score);

printf(，，number=%d\nname=%s\n，z,pstu->num,pstu->name);

printf(〃sex=%c\nscore=%6.2f\n\n〃，pstu-〉sex,pstu->score);

修|8.1結(jié)構(gòu)體造翳等教育“十

程序運(yùn)行結(jié)果：

number=102

name=Zhangping

sex二M

score=J*78.50

本程序序定義了一個(gè)結(jié)構(gòu)體類型Stu,定義了Stu類型結(jié)構(gòu)變量boyl并

作了初始化賦值，還定義了一個(gè)指向stu類型結(jié)構(gòu)體的指針變量pstu。在main。

函數(shù)中，pstu被賦予boyl的地址，因此pstu指向boyl。然后在printf()語(yǔ)句內(nèi)用

三種形式輸出boyl的各個(gè)成員值。

造富羸等教育“十

8.2動(dòng)態(tài)內(nèi)存分配與鏈表

我們存儲(chǔ)數(shù)量比較多的同類型或同結(jié)構(gòu)的數(shù)據(jù)時(shí)，一般首先考慮數(shù)組

O然而在實(shí)際應(yīng)用中，當(dāng)處理一些難以確定其數(shù)量的數(shù)據(jù)時(shí)，如果用數(shù)組來(lái)處

理，必須事先分配一個(gè)足夠大的連續(xù)空間，以保證數(shù)組元素?cái)?shù)量充分夠用，但

這樣處理時(shí)對(duì)存儲(chǔ)空間的一種浪費(fèi)。c語(yǔ)言使用動(dòng)態(tài)內(nèi)存分配來(lái)解決這樣的問(wèn)

題，其中常用的就是鏈表。鏈表是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，它動(dòng)態(tài)地進(jìn)行存儲(chǔ)分

配，并且可以方便而又簡(jiǎn)單地進(jìn)行數(shù)據(jù)插入，刪除等操作。

普通羸等教育“十

鎏8.2動(dòng)態(tài)內(nèi)存分配與鏈表

8.2.1鏈表的概念

鏈表是指若干個(gè)數(shù)據(jù)按一定的原則連接起來(lái)。這個(gè)原則為：前一個(gè)數(shù)據(jù)指

向下一個(gè)數(shù)據(jù)，只有通過(guò)前一個(gè)數(shù)據(jù)項(xiàng)才能找到下一個(gè)數(shù)據(jù)項(xiàng)。

鏈表有一個(gè)“頭指針”（head）,它指向鏈表的第一個(gè)元素（數(shù)據(jù)項(xiàng)）。鏈

表的一個(gè)元素稱為一個(gè)“結(jié)點(diǎn)”（node）。結(jié)點(diǎn)中包含兩部分內(nèi)容，第一部分是結(jié)點(diǎn)

數(shù)據(jù)本身，如圖8-1中的A、B、C、D所示。結(jié)點(diǎn)的第二部分是一個(gè)指針，它指

向下一個(gè)結(jié)點(diǎn)。最后一個(gè)結(jié)點(diǎn)稱為“表尾”，表尾結(jié)點(diǎn)的指針不指向任何地址，因

此為空（NULL）o

圖8T鏈表結(jié)構(gòu)圖

8.2動(dòng)態(tài)內(nèi)存分配與鏈表造富暈等教育“十

如果每個(gè)結(jié)點(diǎn)采用一個(gè)指針，將前一個(gè)結(jié)點(diǎn)的指針指向下一個(gè)結(jié)點(diǎn)，這稱為

單鏈表。如果每個(gè)結(jié)點(diǎn)有兩個(gè)指向其他結(jié)點(diǎn)的指針，則稱為雙鏈表。本節(jié)主要討論單

鏈表的運(yùn)算。

由以上簡(jiǎn)單鏈表可以看到，鏈表中的每個(gè)結(jié)點(diǎn)至少包含兩個(gè)域，一個(gè)域用來(lái)

存放數(shù)據(jù)，其類型根據(jù)需存放的數(shù)據(jù)類型定義。另一個(gè)域用來(lái)存放下一個(gè)結(jié)點(diǎn)的地址

,因此必然是一個(gè)指針類型，此指針的類型應(yīng)該是所指向的表結(jié)點(diǎn)的結(jié)構(gòu)體類型。

在C語(yǔ)言中，可以用結(jié)構(gòu)體類型來(lái)實(shí)現(xiàn)鏈表，例如：

structstudent

{intlong;

floatscore;

structstudent*next;/*指向

下一結(jié)點(diǎn)*/

）；

其中next是結(jié)構(gòu)體指針變量，用來(lái)存放下一個(gè)結(jié)點(diǎn)的地址，即next是指向下一個(gè)結(jié)點(diǎn)

造富羸等教育“十

8.2動(dòng)態(tài)內(nèi)存分配與鏈表

，、[1"I,>ie-xr、.*

8.2.2動(dòng)態(tài)存儲(chǔ)分配

C語(yǔ)言允許在函數(shù)執(zhí)行部分的任何地方使用動(dòng)態(tài)存儲(chǔ)分配函數(shù)開(kāi)辟或收回存

儲(chǔ)單元，這樣的存儲(chǔ)分配叫動(dòng)態(tài)存儲(chǔ)分配。動(dòng)態(tài)分配使用自由、節(jié)約內(nèi)存。

鏈表是動(dòng)態(tài)分配存儲(chǔ)空間的，也就是說(shuō)在需要的時(shí)候才開(kāi)辟一個(gè)結(jié)點(diǎn)的存儲(chǔ)

空間。在C語(yǔ)言中提供了以下有關(guān)的函數(shù)來(lái)實(shí)現(xiàn)動(dòng)態(tài)存儲(chǔ)分配和釋放，這些函數(shù)包含

在“stdio.h”或“malloc.h”中。

8.2動(dòng)態(tài)內(nèi)存分配與鏈表造富暈等教育“十

1.mallocO函數(shù)(分配內(nèi)存空間函數(shù))

調(diào)用形式為：

void*malloc(size);

其作用是在內(nèi)存中動(dòng)態(tài)獲取一個(gè)大小為size個(gè)字節(jié)的連續(xù)存儲(chǔ)空間。該函數(shù)將返回

一個(gè)void類型的指針，若分配成功，就返回所分配的空間的起始地址，否則，就返

回空指針(NULL)o

2.calloc函數(shù)(分配內(nèi)存空間函數(shù))

調(diào)用形式為：

void*calloc(unsignedn,unsignedsize);

其作用是在內(nèi)存中動(dòng)態(tài)獲取n個(gè)大小為size個(gè)字節(jié)的存儲(chǔ)空間。該函數(shù)將返回一個(gè)

void類型的指針，若分配成功，就返回內(nèi)存單元的起始地址，否則，返回空指針(

NULL)。用該函數(shù)可以動(dòng)態(tài)地獲取一個(gè)一維數(shù)組空間，其中n為數(shù)組元素個(gè)數(shù)，每個(gè)

數(shù)組元素的大小為size個(gè)字節(jié)。

8.2動(dòng)態(tài)內(nèi)存分配與鏈表造富暈等教育“十

3.free。函數(shù)(釋放內(nèi)存空間函數(shù))

調(diào)用形式為：

voidfree(void*p);

其作用是釋放由P指針?biāo)赶虻膬?nèi)存空間。即系統(tǒng)回收，使這段空間又可以被其他變

量所用。指針變量P是最近一次調(diào)用malloc()或callocO函數(shù)時(shí)返回的值，不能是

任意的地址。

4.realloc函數(shù)

調(diào)用形式為：

void*recalloc(void*p,unsignedsize);

其作用是將P所指的已分配的內(nèi)存空間重新分配成大小為size個(gè)字節(jié)的空間。它用于

改變已分配的空間的大小，可以增減單元數(shù)。函數(shù)返回新內(nèi)存的首地址，如果內(nèi)存

不夠，則返回空指針(NULL)o

造富羸等教育“十

鎏8.2動(dòng)態(tài)內(nèi)存分配與鏈表

例8.7分配一塊區(qū)域，輸入一個(gè)學(xué)生數(shù)據(jù)。

^include<stdio.h>

ttinclude<stdlib.h>

voidmain()

{structstu/*定義結(jié)構(gòu)體*/

{intnum;

char*name;

charsex;

floatscore;

}*ps;/*定義一個(gè)結(jié)構(gòu)體指針變

量ps*/

ps=(structstu*)malloc(sizeof(structstu));

ps->num=102;/*輸入學(xué)生數(shù)據(jù)*/

ps->name=〃Zhangping〃;

ps-〉sex='M';

ps->score=62.5;

printf(〃number=%d\nnanie=%s\rr,ps->num,ps->name);

printf(〃sex=%c\nscore=%6.2f\n〃，ps->sex,ps->score);

free(ps);

造富羸等教育“十

8.2動(dòng)態(tài)內(nèi)存分配與鏈表

，、[1"I,>ie-xr、.*

程序運(yùn)行結(jié)果：

number=102

name=Zhangping

sex=M

score=J*62.50

本程序中，定義了結(jié)構(gòu)體類型Stu,定義了Stu類型指針變量ps。然后分配

一塊Stu大內(nèi)存區(qū)，并把首地址賦予PS,使PS指向該區(qū)域。再以PS為指向結(jié)構(gòu)體的

指針變量對(duì)各成員賦值，并用printf()輸出各成員值。最后用free。函數(shù)釋放ps指

向的內(nèi)存空間。整個(gè)程序包含了申請(qǐng)內(nèi)存空間、使用內(nèi)存空間、釋放內(nèi)存空間三個(gè)

步驟，實(shí)現(xiàn)存儲(chǔ)空間的動(dòng)態(tài)分配。

造富羸等教育“十

8.2動(dòng)態(tài)內(nèi)存分配與鏈表

8.2.3建立和輸出鏈表

所謂動(dòng)態(tài)建立鏈表是指在程序執(zhí)行過(guò)程中從無(wú)到有地建立鏈表，將一個(gè)個(gè)

新生成的結(jié)點(diǎn)順次鏈接入已建立的鏈表上，上一個(gè)結(jié)點(diǎn)的指針域存放下一個(gè)結(jié)點(diǎn)的

起始地址，并給各結(jié)點(diǎn)數(shù)據(jù)域賦值。

所謂輸出鏈表是將鏈表上各個(gè)結(jié)點(diǎn)的數(shù)據(jù)域中的值依次輸出，直到鏈表結(jié)

尾。

造富羸等教育“十

8.2動(dòng)態(tài)內(nèi)存分配與鏈表

例8.8以三個(gè)結(jié)構(gòu)體變量為結(jié)點(diǎn)建立一個(gè)簡(jiǎn)單的鏈表并輸出。

^include<stdio.h>

structnode

{intdata;

structnode*next;

)；

voidmain()

{structnodea,b,c,*head,*p;

head=&a;/*頭結(jié)點(diǎn)指向a結(jié)點(diǎn)*/

a.data=5;a.next=&b;/*a結(jié)點(diǎn)指向b結(jié)點(diǎn)*/

b.data=10;b.next=&c;/*b結(jié)點(diǎn)指向c結(jié)點(diǎn)*/

c.data=15;c.next=NULL;/*c結(jié)點(diǎn)是尾結(jié)點(diǎn)*/

p=head;/*使P指向a結(jié)點(diǎn)*/

while(p!=NULL)

{printf(〃％d—〉〃,p->data);/*輸出指針P所指向結(jié)點(diǎn)的數(shù)據(jù)*/

p=p->next;/*使P指向下一個(gè)結(jié)點(diǎn)

printf(〃NULL\n〃);

程序運(yùn)行結(jié)果：

5—>10—>15—>NULL

8.2動(dòng)態(tài)內(nèi)存分配與鏈表造富暈等教育“十

8.2.4鏈表的基本操作

鏈表的基本操作包括，建立并初始化鏈表，遍歷訪問(wèn)鏈表（包括查找結(jié)點(diǎn)

、輸出結(jié)點(diǎn)等），刪除鏈表中的結(jié)點(diǎn)，在鏈表中插入結(jié)點(diǎn)。鏈表的各種基本操作的

步驟如下。

1.建立鏈表

①建立頭結(jié)點(diǎn)（或定義頭指針變量）。

②讀取數(shù)據(jù)。

③生成新結(jié)點(diǎn)。

④將數(shù)據(jù)存入結(jié)點(diǎn)的數(shù)據(jù)域中。

⑤將新結(jié)點(diǎn)連接到鏈表中（將新結(jié)點(diǎn)地址賦給上一個(gè)結(jié)

點(diǎn)的指針域連接到鏈表）。

⑥重復(fù)步驟②—⑤，直到尾結(jié)點(diǎn)為止。

普通羸等教育“十

鎏8.2動(dòng)態(tài)內(nèi)存分配與鏈表

2.遍歷訪問(wèn)鏈表

輸出鏈表即順序訪問(wèn)鏈表中各結(jié)點(diǎn)的數(shù)據(jù)域，方法是：從頭結(jié)點(diǎn)開(kāi)始，不斷

地讀取數(shù)據(jù)和下移指針變量，直到尾結(jié)點(diǎn)為止。

3.刪除鏈表中的一個(gè)結(jié)點(diǎn)

①找到要?jiǎng)h除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。

②將要?jiǎng)h除結(jié)點(diǎn)的后驅(qū)結(jié)點(diǎn)的地址賦給要?jiǎng)h除結(jié)點(diǎn)的前驅(qū)

結(jié)點(diǎn)的指針域。

③將要?jiǎng)h除結(jié)點(diǎn)的存儲(chǔ)空間釋放。

4.在鏈表的某結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)

①開(kāi)辟一個(gè)新結(jié)點(diǎn)并將數(shù)據(jù)存入該結(jié)點(diǎn)的數(shù)據(jù)域。

②找到插入點(diǎn)結(jié)點(diǎn)。

③將新結(jié)點(diǎn)插入到鏈表中，將新結(jié)點(diǎn)的地址賦給插入點(diǎn)上

一個(gè)結(jié)點(diǎn)的指針域，并將插入點(diǎn)的地址存入新結(jié)點(diǎn)的指

針域。

例8.9建立并輸出一個(gè)學(xué)生成績(jī)鏈表(假設(shè)學(xué)生成績(jī)表中只含姓名和成績(jī))。

ttinclude<stdio.h>

ttinclude<malloc.h>

typedefstructstudent/*自定義鏈表結(jié)點(diǎn)數(shù)據(jù)類型名ST和指針類型

名*STU*/

{charname[20];

intscore;

structstudent*next;/*結(jié)點(diǎn)指針域*/

ST,*STU;

STUcreatelink(intn)/*建立一個(gè)由n個(gè)結(jié)點(diǎn)構(gòu)成的單鏈表函數(shù)，返回結(jié)點(diǎn)指針類型

{inti;

STUp,q,head;

if(n<=0)

return(NULL);

head=(STU)malloc(sizeof(ST));/*生成第一個(gè)結(jié)點(diǎn)*/

pri?nt1fc(/"〃?inpu.t1datas:\n〃\)；

scanf(，z%s%d，z,head->name,&head->score);/*兩個(gè)數(shù)據(jù)之間用一個(gè)空格間隔*/

p=head;

造富羸等教育“十

8.2動(dòng)態(tài)內(nèi)存分配與鏈表

，、[1"I,>ie-xr、.*

for(i=l;i<n;i++)

{q=(STU)malloc(sizeof(ST));

scanf(，z%s%d〃，q->name,&q->score)_2

p->next=q;/*連接q結(jié)點(diǎn)*/、_

、PF；/*P源勤q上，再準(zhǔn)備連接下一個(gè)結(jié)點(diǎn)q*/

p->next=NULL;/*置尾結(jié)點(diǎn)指針域?yàn)榭罩干?/

return(head);滔曲遑立超萊南罩林表頭指針?lè)祷?/

voidlist(STUhead)/*鏈表的輸出*/

(STUp=head;/*從頭軸針由裳，依次輸出各結(jié)點(diǎn)的值，直到遇

到

NULL*/

while(p!=NULL)〃

{printf(〃％s\t%d\n〃，p->name,p->score);

、p=p->next;/*p指針順序后移一個(gè)結(jié)點(diǎn)*/

voidmain()

{STUh;

intn;〃

printf("inputnumberofnode:");

scanf(〃％d〃,&n);

h二create]ink(n);/*調(diào)用建立集鏈表的國(guó)基*/

list(h);耦用輸出鏈蓑的函數(shù)*/

高等教育“十

8.2動(dòng)態(tài)內(nèi)存分配與鏈表

程序運(yùn)行結(jié)果：

inputnumberof

node:4/

inputdatas:

A60Z

B70Z

C80Z

D90Z

A60

B70

C80

D90

造富羸等教育“十

鎏8.2動(dòng)態(tài)內(nèi)存分配與鏈表

例8.10編寫(xiě)一個(gè)函數(shù)，在例8.9中建立的鏈表的前面插入一個(gè)結(jié)點(diǎn)。

^include<stdio.h>

^include<malloc.h>

/*將例8.9中typedefstructstudent直到voidlist(STUhead)函數(shù)全部插入到該

位置*/

STUincreasenodel(STUhead)

{STUs;

s=(STU)malloc(sizeof(ST));

printf(，zInputnewnodedatas:z/);

scanf(〃％s%d〃，s->name,&s->score);

s->next=head;

head's;

return(head);

)

voidmain()

{STUh;intn;

printf("inputnumberofnode:");

scanf(〃%d〃，&n);

h二createlink(n);/*調(diào)用建立單鏈表的函數(shù)*/

list(h);/*詞甬播出鏈表的函數(shù)*/

h=increasenodel(h);

list(h);

高等教育“十

8.2動(dòng)態(tài)內(nèi)存分配與鏈表

程序運(yùn)行結(jié)果：

inputnumberofnode:3Z

inputdatas:

A60Z

B70Z

C80/

A60

B70

C80

inputnewnodedatas:E100/

E100

A10

B20

C30

造富羸等教育“十

鎏8.2動(dòng)態(tài)內(nèi)存分配與鏈表

例8.11編寫(xiě)一個(gè)函數(shù)，在例8.9建立的鏈表的第i個(gè)結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)。

^include<stdio.h>

ttinclude<malloc.h>

/*將例8.9中typedefstructstudent直到voidlist(STUhead)函數(shù)全部插入到該位

置*/

STUincreasenode2(STUhead,inti)

{STUs,p,q;

intj=0;/*查找第i個(gè)結(jié)點(diǎn)計(jì)數(shù)用*/

if(i<0)

returnNULL;/*參數(shù)i值不合理*/

s=(STU)malloc(sizeof(ST));

printf(，zinputnewnodedatas:?，);

scanf(,，%s%d〃，s->name,&s->score);

if(i=0)/*i=0表明是在第一個(gè)結(jié)點(diǎn)之前插入新結(jié)點(diǎn)*/

{s->next=head;

head's;

return(head);

q二head;/*查找新結(jié)點(diǎn)的位置，在P和q之間*/

0⑷造富羸等教育“十

嚓8.2動(dòng)態(tài)內(nèi)存分配與鏈表

while(j<i&&q!=NULL)

{j++；

PF；

q=q->next;

)

if(j<i)

returnNULL;/*i值超過(guò)表長(zhǎng)*/

p->next=s;/*在p和q之間，即第i個(gè)結(jié)點(diǎn)之后插入新結(jié)點(diǎn)

*/

s->next=q;

return(head);

)

voidmain()

{STUh;intn;inti;

printf("inputnumberofnode:");

scanf(〃％d〃，&n);

h二create]ink(n);/*調(diào)用建立單鏈表的函數(shù)*/

list(h),〃/*調(diào)用期出鏈表函函數(shù)*/

printf("inputnewnodenumber:");/*輸入新結(jié)點(diǎn)*/

scanf(〃%d〃,&i);

h=increasenode2(h,i);

list(h);

造富羸等教育“十

8.2動(dòng)態(tài)內(nèi)存分配與鏈表

程序運(yùn)行結(jié)果：

inputnumberofnode:3Z

inputdatas:

A60Z

B70Z

C80Z

A60

B70

C80

inputnewnodenumber:2/

inputnewnodedatas:E100/

A10

B20

E100

C30

造富羸等教育“十

鎏8.2動(dòng)態(tài)內(nèi)存分配與鏈表

例8.12刪除鏈表中的表首結(jié)點(diǎn)函數(shù)。

ttinclude<stdio.h>

^include<malloc.h>

/*將例8.9中typedefstructstudent直到voidlist(STUhead)函數(shù)全部插入到

該位普*/

STUdeletenodel(STUhead)

{STUs;

if(head!=NULL)〃

{printf(''afterdeletedthefirstnode:\n，z);

s=head;

head=s-〉next;

free(s);

return(head);

)

voidmain()

{STUh;intn;

printf("inputnumberofnode:;

scanf(〃%d〃,&n);

h二create]ink(n);用建立單鏈表的函數(shù)*/

list(h);用輸出鏈表的函數(shù)*/

h二deletenodel(h);

list(h);