1、第11章 結(jié)構(gòu)體與共用體1 概述2 定義結(jié)構(gòu)體類型變量的方法3 結(jié)構(gòu)體變量的引用4 結(jié)構(gòu)體變量的初始化5 結(jié)構(gòu)體數(shù)組6 指向結(jié)構(gòu)體類型數(shù)據(jù)的指針7 用指針處理鏈表8 共用體9 枚舉類型10 用typedef定義類型本章學(xué)習(xí)目標(biāo)本章學(xué)習(xí)目標(biāo)理解結(jié)構(gòu)體的概念和它對(duì)于編程的重要性；理解結(jié)構(gòu)體的概念和它對(duì)于編程的重要性；理解理解定義結(jié)構(gòu)體類型定義結(jié)構(gòu)體類型和和定義結(jié)構(gòu)體變量定義結(jié)構(gòu)體變量的區(qū)的區(qū)別；別；能夠用能夠用“ . ”和和“-”分量運(yùn)算符操作結(jié)構(gòu)體變分量運(yùn)算符操作結(jié)構(gòu)體變量和指向結(jié)構(gòu)體的指針變量；量和指向結(jié)構(gòu)體的指針變量；能夠定義并使用結(jié)構(gòu)體數(shù)組；能夠定義并使用結(jié)構(gòu)體數(shù)組；了解共用體數(shù)據(jù)類型了解

2、共用體數(shù)據(jù)類型 ；自學(xué)了解枚舉類型的使用；自學(xué)了解枚舉類型的使用；了解用了解用typedef定義數(shù)據(jù)類型。定義數(shù)據(jù)類型。 概述概述v 數(shù)據(jù)的基本類型：整、實(shí)、字符。數(shù)據(jù)的基本類型：整、實(shí)、字符。v 數(shù)組是構(gòu)造類型：每個(gè)元素為同一類型數(shù)組是構(gòu)造類型：每個(gè)元素為同一類型v 有些問(wèn)題僅用基本類型和數(shù)組來(lái)描述，無(wú)法反映有些問(wèn)題僅用基本類型和數(shù)組來(lái)描述，無(wú)法反映其內(nèi)在聯(lián)系，如學(xué)生情況：其內(nèi)在聯(lián)系，如學(xué)生情況： numnamesexagescoreaddr整字符串字符整實(shí)字符串11001Zhang xinm1996. 5Shang hai12001Wang lif2098. 5Bei jing 上述數(shù)據(jù)互

3、相獨(dú)立又相互關(guān)聯(lián)，如：均與學(xué)號(hào)和姓上述數(shù)據(jù)互相獨(dú)立又相互關(guān)聯(lián)，如：均與學(xué)號(hào)和姓名關(guān)聯(lián)。需要將其組合成一個(gè)有機(jī)的整體，名關(guān)聯(lián)。需要將其組合成一個(gè)有機(jī)的整體，C語(yǔ)言可以將語(yǔ)言可以將由不同類型數(shù)據(jù)組成的這種數(shù)據(jù)結(jié)構(gòu)組織成一個(gè)組合項(xiàng)，由不同類型數(shù)據(jù)組成的這種數(shù)據(jù)結(jié)構(gòu)組織成一個(gè)組合項(xiàng)，稱為稱為結(jié)構(gòu)體結(jié)構(gòu)體（structure）。）。結(jié)構(gòu)體結(jié)構(gòu)體v結(jié)構(gòu)體是一種結(jié)構(gòu)體是一種構(gòu)造構(gòu)造數(shù)據(jù)類型。數(shù)據(jù)類型。 與其他高級(jí)語(yǔ)言中的與其他高級(jí)語(yǔ)言中的“記錄記錄”類似。類似。v定義：由定義：由相互關(guān)聯(lián)相互關(guān)聯(lián)的的不同數(shù)據(jù)類型不同數(shù)據(jù)類型的數(shù)據(jù)組成的的數(shù)據(jù)組成的有機(jī)整體。有機(jī)整體。v用途：為處理復(fù)雜的數(shù)據(jù)結(jié)構(gòu)提供了手段。用

4、途：為處理復(fù)雜的數(shù)據(jù)結(jié)構(gòu)提供了手段。 為函數(shù)間傳遞不同類型的參數(shù)提供了便利。為函數(shù)間傳遞不同類型的參數(shù)提供了便利。v關(guān)鍵字：關(guān)鍵字：struct 結(jié)構(gòu)體類型定義結(jié)構(gòu)體類型定義struct 結(jié)構(gòu)體名結(jié)構(gòu)體名 類型標(biāo)識(shí)符類型標(biāo)識(shí)符 成員名成員名1； 類型標(biāo)識(shí)符類型標(biāo)識(shí)符 成員名成員名2； .；成員類型可以是成員類型可以是基本型或構(gòu)造型基本型或構(gòu)造型struct是是關(guān)鍵字關(guān)鍵字,不能省略不能省略合法標(biāo)識(shí)符合法標(biāo)識(shí)符可省可省:無(wú)名結(jié)構(gòu)體無(wú)名結(jié)構(gòu)體；不能省略不能省略struct student int num; char name20; char sex; int age; float score; c

5、har addr30; namenumsexagescoreaddr2字節(jié)字節(jié)2字節(jié)字節(jié)20字節(jié)字節(jié)1字節(jié)字節(jié)4字節(jié)字節(jié)30字節(jié)字節(jié).結(jié)構(gòu)體類型結(jié)構(gòu)體類型定義定義僅描述結(jié)構(gòu)體的組成僅描述結(jié)構(gòu)體的組成,不分配內(nèi)存空間不分配內(nèi)存空間 定義結(jié)構(gòu)體類型變量的方法定義結(jié)構(gòu)體類型變量的方法 聲明結(jié)構(gòu)體類型時(shí)不分配存儲(chǔ)單元，使用該類型定聲明結(jié)構(gòu)體類型時(shí)不分配存儲(chǔ)單元，使用該類型定義變量時(shí)才分配存儲(chǔ)單元。定義變量方法義變量時(shí)才分配存儲(chǔ)單元。定義變量方法3種：種：先聲明先聲明結(jié)構(gòu)體結(jié)構(gòu)體類型類型，再定義再定義結(jié)構(gòu)體結(jié)構(gòu)體變量變量struct student int num; char name20; char

6、sex; int age; float score; char addr30; struct student stu1,stu2; 定義結(jié)構(gòu)體定義結(jié)構(gòu)體類型類型定義結(jié)構(gòu)體定義結(jié)構(gòu)體變量變量真正可以使用的變量真正可以使用的變量struct 結(jié)構(gòu)體名結(jié)構(gòu)體名 類型標(biāo)識(shí)符類型標(biāo)識(shí)符 成員名；成員名； 類型標(biāo)識(shí)符類型標(biāo)識(shí)符 成員名；成員名； .；struct 結(jié)構(gòu)體名結(jié)構(gòu)體名 變量名表列變量名表列；聲明結(jié)構(gòu)體聲明結(jié)構(gòu)體類型類型的的同時(shí)同時(shí)定義結(jié)構(gòu)體定義結(jié)構(gòu)體變量變量只有在定義了只有在定義了結(jié)構(gòu)結(jié)構(gòu)體變量體變量后系統(tǒng)才為后系統(tǒng)才為其其分配內(nèi)存分配內(nèi)存。struct student int num; ch

7、ar name20; char sex; int age; float score; char addr30; stu1,stu2 ; 定義結(jié)構(gòu)體定義結(jié)構(gòu)體類型類型定義結(jié)構(gòu)體定義結(jié)構(gòu)體變量變量struct 結(jié)構(gòu)體名結(jié)構(gòu)體名 類型標(biāo)識(shí)符類型標(biāo)識(shí)符 成員名；成員名； 類型標(biāo)識(shí)符類型標(biāo)識(shí)符 成員名；成員名； .變量名表列變量名表列；直接定義結(jié)構(gòu)體類型變量直接定義結(jié)構(gòu)體類型變量用用無(wú)名結(jié)構(gòu)體無(wú)名結(jié)構(gòu)體直接直接定義變量定義變量只能一次只能一次struct 類型標(biāo)識(shí)符類型標(biāo)識(shí)符 成員名；成員名； 類型標(biāo)識(shí)符類型標(biāo)識(shí)符 成員名；成員名； .變量名表列變量名表列；struct int num; char na

8、me20; char sex; int age; float score; char addr30; stu1,stu2 ; 說(shuō)明說(shuō)明v結(jié)構(gòu)體類型與結(jié)構(gòu)體變量概念不同結(jié)構(gòu)體類型與結(jié)構(gòu)體變量概念不同l類型類型:不分配內(nèi)存；不分配內(nèi)存； 變量變量:分配內(nèi)存分配內(nèi)存l類型類型:不能賦值、存取、運(yùn)算不能賦值、存取、運(yùn)算; 變量變量:可以可以v結(jié)構(gòu)體變量中的成員可單獨(dú)使用，方法如普通變量；結(jié)構(gòu)體變量中的成員可單獨(dú)使用，方法如普通變量；v結(jié)構(gòu)體可嵌套結(jié)構(gòu)體可嵌套struct date int month; int day; int year;struct student int num; char nam

9、e20; struct date birthday; stu;numnamebirthdaymonthdayyearprintf (%d , sizeof (stu) ); struct student int num; char name20; struct date int month; int day; int year; birthday; stu;結(jié)果：結(jié)果：28v結(jié)構(gòu)體成員名與程序結(jié)構(gòu)體成員名與程序中變量名可相同中變量名可相同v結(jié)構(gòu)體成員名與程序中變量名可相同，兩者不代結(jié)構(gòu)體成員名與程序中變量名可相同，兩者不代表同一個(gè)對(duì)象。表同一個(gè)對(duì)象。 struct student int nu

10、m; char name20; float score; stu;int num;stu. numnum11.3 結(jié)構(gòu)體變量的引用結(jié)構(gòu)體變量的引用引用規(guī)則引用規(guī)則v 結(jié)構(gòu)體變量結(jié)構(gòu)體變量不能整體引用不能整體引用,只能引用變量只能引用變量成員成員結(jié)構(gòu)體變量名結(jié)構(gòu)體變量名.成員名成員名 成員成員(分量分量)運(yùn)算符運(yùn)算符優(yōu)先級(jí)優(yōu)先級(jí): 1結(jié)合性結(jié)合性:從左向右從左向右struct student int num; char name20; char sex; int age; float score; char addr30;stu1,stu2; stu1.num=10; stu1.age+;stu

11、1.score=85.5;stu1.score+=stu2.score;void main() struct student int No; float score; stu1,stu2; scanf(“%d,%f”,&stu1); ( )scanf(“%d,%f”,); () printf(“%d,%f”,stu1); ( )printf(“%d,%f” ,); () stu2=stu1; () v結(jié)構(gòu)體成員本身又是一個(gè)結(jié)構(gòu)體類型，則需要找結(jié)構(gòu)體成員本身又是一個(gè)結(jié)構(gòu)體類型，則需要找到最低一級(jí)的成員。到最低一級(jí)的成員。 struct student int num; char name

12、20; struct date int month; int day; int year; birthday;stu1,stu2;numnamebirthdaymonthdayyearstu1.birthday.month=12;v結(jié)構(gòu)體變量的成員與普通變量用法相同。結(jié)構(gòu)體變量的成員與普通變量用法相同。 結(jié)構(gòu)體變量的初始化結(jié)構(gòu)體變量的初始化形式一形式一struct 結(jié)構(gòu)體名結(jié)構(gòu)體名 類型標(biāo)識(shí)符類型標(biāo)識(shí)符 成員名成員名1； 類型標(biāo)識(shí)符類型標(biāo)識(shí)符 成員名成員名2； .；struct 結(jié)構(gòu)體名結(jié)構(gòu)體名 結(jié)構(gòu)體變量結(jié)構(gòu)體變量=初始數(shù)據(jù)初始數(shù)據(jù)；struct stu int num; char name

13、20; int age; char addr30; struct stu a=112,“Wang Lin”, 19, “200 Beijing Road”;形式二形式二struct 結(jié)構(gòu)體名結(jié)構(gòu)體名 類型標(biāo)識(shí)符類型標(biāo)識(shí)符 成員名成員名1； 類型標(biāo)識(shí)符類型標(biāo)識(shí)符 成員名成員名2； . 結(jié)構(gòu)體變量結(jié)構(gòu)體變量=初始數(shù)據(jù)初始數(shù)據(jù)；struct stu int num; char name20; int age; char addr30; a=112,“Wang Lin”, 19, “200 Beijing Road”;形式三形式三 struct 類型標(biāo)識(shí)符類型標(biāo)識(shí)符 成員名；成員名； 類型標(biāo)識(shí)符類型標(biāo)

14、識(shí)符 成員名；成員名； .結(jié)構(gòu)體變量結(jié)構(gòu)體變量=初始數(shù)據(jù)初始數(shù)據(jù)；struct int num; char name20; char sex; int age; char addr30;stu1=112,“Wang Lin”,M,19, “200 Beijing Road”; #include void main() struct student long int num; char name20; char sex; char addr20; a=89031,“Li Lin”,M, “123 Beijing Road”; printf(No. :%ldnname:%snsex:%cnaddr

15、ess:%sn, a.num,,a.sex,a.addr);例例11.1 對(duì)結(jié)構(gòu)體變量初始化對(duì)結(jié)構(gòu)體變量初始化運(yùn)行結(jié)果：運(yùn)行結(jié)果：No. :89301 name:Li Lin sex:M address:123 Beijing Road 結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體數(shù)組具有相同結(jié)構(gòu)的結(jié)構(gòu)體也可以組成數(shù)組具有相同結(jié)構(gòu)的結(jié)構(gòu)體也可以組成數(shù)組定義結(jié)構(gòu)體數(shù)組：定義結(jié)構(gòu)體數(shù)組：3種形式種形式形式一形式一:間接定義間接定義struct student int num; char name20; char sex; int age; ; struct student stu2;numnamesexagenu

16、mnamesexagestu0stu125B形式二形式二:直接定義直接定義struct student int num; char name20; char sex; int age; stu2;形式三形式三:直接定義直接定義struct int num; char name20; char sex; int age; stu2;結(jié)構(gòu)體數(shù)組初始化結(jié)構(gòu)體數(shù)組初始化struct 結(jié)構(gòu)名結(jié)構(gòu)名 結(jié)構(gòu)數(shù)組名結(jié)構(gòu)數(shù)組名數(shù)組長(zhǎng)度數(shù)組長(zhǎng)度=初始數(shù)據(jù)初始數(shù)據(jù);定義數(shù)組時(shí)初始化定義數(shù)組時(shí)初始化:struct student int num; char name20; char sex; int age; ;st

17、ruct student stu3=100,“Wang Lin”,M,20, 101,“Li Gang”,M,19, 110,“Liu Yan”,F,19; 全部初始化時(shí)維數(shù)可省全部初始化時(shí)維數(shù)可省按順序定義時(shí)：按順序定義時(shí)：內(nèi)層括號(hào)內(nèi)層括號(hào)可以省略可以省略聲明結(jié)構(gòu)體時(shí)，對(duì)結(jié)構(gòu)體數(shù)組初始化聲明結(jié)構(gòu)體時(shí)，對(duì)結(jié)構(gòu)體數(shù)組初始化:struct student int num; char name20; char sex; int age; stu3=100,“Wang Lin”,M,20, 101,“Li Gang”,M,19, 110,“Liu Yan”,F,19; 全部初始化時(shí)維數(shù)可省全部初始化時(shí)

18、維數(shù)可省按順序定義時(shí)：按順序定義時(shí)：內(nèi)層括號(hào)內(nèi)層括號(hào)可以省略可以省略結(jié)構(gòu)體數(shù)組應(yīng)用結(jié)構(gòu)體數(shù)組應(yīng)用struct student int num; char name20; char sex; int age; ;struct student stu =100,“Wang Lin”,M,20, ; stu0.age+;strcpy(, “ ZhaoDa”);#include #include struct person char name20; int count; leader3=“Li”,0,“Zhang”,0,”Wang“,0; void main() int i,j; c

19、har leader_name20; for(i=1;i=10;i+) scanf(%s,leader_name); for(j=0;j3;j+) if(strcmp(leader_name,)=0) leaderj.count+; printf(n); for(i=0;i3;i+) printf(%5s:%dn,,leaderi.count);例例11.2 統(tǒng)計(jì)候選人選票統(tǒng)計(jì)候選人選票namecountLiZhangWang000namecountLiZhangWang433 指向結(jié)構(gòu)體類型數(shù)據(jù)的指針指向結(jié)構(gòu)體類型數(shù)據(jù)的指針v存放結(jié)構(gòu)體首地址存

20、放結(jié)構(gòu)體首地址v結(jié)構(gòu)指針的運(yùn)算按照結(jié)構(gòu)指針的運(yùn)算按照C語(yǔ)言的地址運(yùn)算原則進(jìn)行語(yǔ)言的地址運(yùn)算原則進(jìn)行.例如，結(jié)構(gòu)指針加一將指向內(nèi)存中下一個(gè)結(jié)構(gòu)體。例如，結(jié)構(gòu)指針加一將指向內(nèi)存中下一個(gè)結(jié)構(gòu)體。指向結(jié)構(gòu)體變量的指針指向結(jié)構(gòu)體變量的指針v定義形式：定義形式： struct 結(jié)構(gòu)體名結(jié)構(gòu)體名 *結(jié)構(gòu)體指針名結(jié)構(gòu)體指針名;例例 struct student *p;存放結(jié)構(gòu)體變量在存放結(jié)構(gòu)體變量在內(nèi)存的起始地址內(nèi)存的起始地址numnamesexagestupstruct student int num; char name20; char sex; int age; stu;struct student *

21、p=&stu;v使用結(jié)構(gòu)體指針變量引用成員形式使用結(jié)構(gòu)體指針變量引用成員形式 例例 int n; int *p=&n; *p=10; n=10struct student stu1;struct student *p=&stu1;stu1.num=101; (*p).num=101以下三種形式等價(jià)：以下三種形式等價(jià)：結(jié)構(gòu)體變量名結(jié)構(gòu)體變量名.成員名成員名 =101;(*結(jié)構(gòu)體指針名結(jié)構(gòu)體指針名).成員名成員名 (*p).num=101結(jié)構(gòu)體指針名結(jié)構(gòu)體指針名成員名成員名 pnum =101指向運(yùn)算符指向運(yùn)算符優(yōu)先級(jí)優(yōu)先級(jí): 1結(jié)合方向：從左向右結(jié)合方向：從左向右( )不

22、能少！不能少！#include #include void main() struct student long int num; char name20; char sex; float score; stu_1,*p; p=&stu_1; stu_1.num=89101; strcpy(stu_1.name,Li Lin); (*p).sex=M; pscore=89.5; printf(nNo:%ldnname:%snsex:%cnscore:%fn, (*p).num,pname,pscore);例例11.3 指向結(jié)構(gòu)體變量的指針的應(yīng)用指向結(jié)構(gòu)體變量的指針的應(yīng)用v注意區(qū)分以下三

23、種運(yùn)算注意區(qū)分以下三種運(yùn)算 p n p n+ +p nstruct s int x; int y;data4=10,100,20,200,30,300,40,400;main( ) struct s *pointer=data; printf(“%dn”, +pointerx); printf(“%dn”,(+pointer)y); printf(“%dn”, (pointer+)x); printf(“%dn”, (pointer)y+); 運(yùn)行結(jié)果：運(yùn)行結(jié)果：11200 20 300 指向結(jié)構(gòu)體數(shù)組的指針指向結(jié)構(gòu)體數(shù)組的指針v結(jié)構(gòu)體數(shù)組及其元素可用指針變量來(lái)指向結(jié)構(gòu)體數(shù)組及其元素可用指針變

24、量來(lái)指向v數(shù)組首地址賦給指向結(jié)構(gòu)體類型的指針變量時(shí)，數(shù)組首地址賦給指向結(jié)構(gòu)體類型的指針變量時(shí)，當(dāng)指針變量增當(dāng)指針變量增1時(shí)，指向下一個(gè)數(shù)組元素。時(shí)，指向下一個(gè)數(shù)組元素。#include struct student int num; char name20; char sex; int age; stu3=10101,Li Lin,M,18, 10102,Zhang Fun,M,19, 10104,Wang Min,F,20;void main() struct student *p; for(p=stu;pstu+3;p+) printf(%d%s%c%dn,pnum,pname,psex,

25、page);numnamesexagestu0pstu1stu2p+1例例11.4 指向結(jié)構(gòu)體數(shù)組的指針的應(yīng)用指向結(jié)構(gòu)體數(shù)組的指針的應(yīng)用用結(jié)構(gòu)體變量和指向結(jié)構(gòu)體的指針作函數(shù)參數(shù)用結(jié)構(gòu)體變量和指向結(jié)構(gòu)體的指針作函數(shù)參數(shù)將一個(gè)結(jié)構(gòu)體變量的值傳遞給另一函數(shù)將一個(gè)結(jié)構(gòu)體變量的值傳遞給另一函數(shù) ，方法有，方法有3種：種：v用結(jié)構(gòu)體變量的成員作函數(shù)實(shí)參用結(jié)構(gòu)體變量的成員作函數(shù)實(shí)參-值傳遞值傳遞l注意形、實(shí)的類型要一致。注意形、實(shí)的類型要一致。v用指向結(jié)構(gòu)體變量或數(shù)組的指針作實(shí)參用指向結(jié)構(gòu)體變量或數(shù)組的指針作實(shí)參-地址傳遞地址傳遞l傳遞的是結(jié)構(gòu)體變量的地傳遞的是結(jié)構(gòu)體變量的地 址。址。v用結(jié)構(gòu)體變量作參數(shù)用

26、結(jié)構(gòu)體變量作參數(shù)-多值傳遞多值傳遞，效率低，效率低l將結(jié)構(gòu)體變量所占的內(nèi)存單元的內(nèi)容全部順序傳遞給形參，要將結(jié)構(gòu)體變量所占的內(nèi)存單元的內(nèi)容全部順序傳遞給形參，要求形參與實(shí)參同類型。函數(shù)調(diào)用是單值傳遞，且形參占用內(nèi)存求形參與實(shí)參同類型。函數(shù)調(diào)用是單值傳遞，且形參占用內(nèi)存單元，若形參的值被改變，不會(huì)返回主調(diào)函數(shù)。單元，若形參的值被改變，不會(huì)返回主調(diào)函數(shù)。 #include #include #define FORMAT %dn%sn%fn%fn%fnstruct student /*定義為外部結(jié)構(gòu)體類型定義為外部結(jié)構(gòu)體類型*/ int num; char name20; float score3;

27、void main() void print(struct student); struct student stu; /*定義為局部結(jié)構(gòu)體類型變量定義為局部結(jié)構(gòu)體類型變量*/ stu.num=12345; strcpy(,Li Li); stu.score0=67.5;stu.score1=89;stu.score2=78.6; print(stu); /*結(jié)構(gòu)體變量作實(shí)參結(jié)構(gòu)體變量作實(shí)參*/void print(struct student stu) printf(FORMAT,stu.num,,stu.score0,stu.score1,stu.score

28、2); printf(“n”);例例11.5 結(jié)構(gòu)體變量結(jié)構(gòu)體變量stu有學(xué)號(hào)、姓名和有學(xué)號(hào)、姓名和3門(mén)課成績(jī)，門(mén)課成績(jī)， 在在main函數(shù)中賦值，在函數(shù)中賦值，在print函數(shù)中打印輸出。函數(shù)中打印輸出。 /* 對(duì)成員賦值也可以改為對(duì)成員賦值也可以改為scanf函數(shù)輸入函數(shù)輸入*/scanf(%d%s%f%f%f,&stu.num,, &stu.score0,&stu.score1,&stu.score2);無(wú)無(wú)&#include #define FORMAT %dn%sn%fn%fn%fnstruct student /*定義為外部結(jié)

29、構(gòu)體類型定義為外部結(jié)構(gòu)體類型*/ int num; char name20; float score3; stu=12345, Li Li,67.5,89,78.6;void main() void print(struct student * ); /*形參指向結(jié)構(gòu)體的指針變量形參指向結(jié)構(gòu)體的指針變量*/ print(&stu); /*實(shí)參為實(shí)參為stu的起始地址的起始地址*/void print(struct student *p) printf(FORMAT,pnum,pname,pscore0,pscore1, pscore2); /*用指針變量調(diào)用成員之值用指針變量調(diào)用成員之

30、值*/ printf(“n”); 結(jié)構(gòu)體變量的指針作實(shí)參結(jié)構(gòu)體變量的指針作實(shí)參 用指針處理鏈表用指針處理鏈表鏈表概述鏈表概述v數(shù)組：靜態(tài)分配存儲(chǔ)單元，容易造成內(nèi)存浪費(fèi)。數(shù)組：靜態(tài)分配存儲(chǔ)單元，容易造成內(nèi)存浪費(fèi)。v鏈表：是重要的數(shù)據(jù)結(jié)構(gòu)，它根據(jù)需要，動(dòng)態(tài)分鏈表：是重要的數(shù)據(jù)結(jié)構(gòu)，它根據(jù)需要，動(dòng)態(tài)分配內(nèi)存單元配內(nèi)存單元 。head1249135614751021A 1356B 1475C 1021D NULL 1249v特征：頭指針變量，存放鏈表首地址，鏈表中每特征：頭指針變量，存放鏈表首地址，鏈表中每個(gè)元素稱結(jié)點(diǎn)，其內(nèi)容：個(gè)元素稱結(jié)點(diǎn)，其內(nèi)容： l數(shù)據(jù)部分：可有若干項(xiàng)（整、實(shí)、字符、結(jié)構(gòu)體類型等

31、）數(shù)據(jù)部分：可有若干項(xiàng)（整、實(shí)、字符、結(jié)構(gòu)體類型等）l指針變量：下一結(jié)點(diǎn)的地址，最后一個(gè)結(jié)點(diǎn)（表尾）的指針變量：下一結(jié)點(diǎn)的地址，最后一個(gè)結(jié)點(diǎn)（表尾）的地址部分為地址部分為NULL。 v鏈表各結(jié)點(diǎn)的特點(diǎn)：鏈表各結(jié)點(diǎn)的特點(diǎn)：l在內(nèi)存中可以不連續(xù)，訪問(wèn)某結(jié)點(diǎn)應(yīng)找上一結(jié)點(diǎn)提供的地址，在內(nèi)存中可以不連續(xù)，訪問(wèn)某結(jié)點(diǎn)應(yīng)找上一結(jié)點(diǎn)提供的地址，每一結(jié)點(diǎn)有一指針變量存放下一結(jié)點(diǎn)的地址。每一結(jié)點(diǎn)有一指針變量存放下一結(jié)點(diǎn)的地址。l鏈表的每個(gè)結(jié)點(diǎn)實(shí)際上是一個(gè)結(jié)構(gòu)體變量，它有若干成員組鏈表的每個(gè)結(jié)點(diǎn)實(shí)際上是一個(gè)結(jié)構(gòu)體變量，它有若干成員組成，包括的內(nèi)容有兩部分：成，包括的內(nèi)容有兩部分：u數(shù)據(jù)部分：整、實(shí)、字符、結(jié)構(gòu)體等類

32、型。數(shù)據(jù)部分：整、實(shí)、字符、結(jié)構(gòu)體等類型。u指針變量：通常具有指向自身結(jié)構(gòu)體類型的指針變量，指針變量：通常具有指向自身結(jié)構(gòu)體類型的指針變量，此指針變量用來(lái)存放下一結(jié)點(diǎn)的地址，以便一環(huán)扣一環(huán)而此指針變量用來(lái)存放下一結(jié)點(diǎn)的地址，以便一環(huán)扣一環(huán)而形成鏈表。形成鏈表。 struct student int num; float score; struct student *next; ;其中：其中：next是成員名，是指針類型，是成員名，是指針類型， 它指向它指向struct student數(shù)據(jù)類型數(shù)據(jù)類型. 9910189. 599103909910785NULLnumscorenext簡(jiǎn)單鏈表簡(jiǎn)單

33、鏈表#include #define NULL 0 struct student long num; float score; struct student *next; ; void main( ) struct student a,b,c,*head,*p; a.num=99101;a.score=89.5; b.num=99102;b.score=90; c.num=99103;c.score=85; head=&a;a.next=&b;b.next=&c; c.next=NULL; p=head; do printf(“%ld %5.1fn”,pnum,psco

34、re); p=pnext; while(p!=NULL); 例例11.7 建立簡(jiǎn)單鏈表，它由建立簡(jiǎn)單鏈表，它由3個(gè)學(xué)生數(shù)據(jù)的結(jié)點(diǎn)組成。個(gè)學(xué)生數(shù)據(jù)的結(jié)點(diǎn)組成。 輸出各結(jié)點(diǎn)中的數(shù)據(jù)。輸出各結(jié)點(diǎn)中的數(shù)據(jù)。 每個(gè)結(jié)點(diǎn)都屬于每個(gè)結(jié)點(diǎn)都屬于struct student類型，它的類型，它的next成員存成員存放下一個(gè)結(jié)點(diǎn)的地址，這樣一環(huán)扣一環(huán)，將各結(jié)節(jié)緊密的放下一個(gè)結(jié)點(diǎn)的地址，這樣一環(huán)扣一環(huán)，將各結(jié)節(jié)緊密的扣在一起，最后一次循環(huán)，將扣在一起，最后一次循環(huán)，將p=pnext是將是將c結(jié)點(diǎn)的地址結(jié)點(diǎn)的地址賦給賦給p，這時(shí)，這時(shí)p指向指向c結(jié)點(diǎn)，然后將結(jié)點(diǎn)，然后將c結(jié)點(diǎn)的結(jié)點(diǎn)的num,score輸出，輸出，之后將

35、之后將p=pnext實(shí)際上是將實(shí)際上是將c結(jié)點(diǎn)的結(jié)點(diǎn)的next內(nèi)容，即內(nèi)容，即NULL賦給賦給p 再進(jìn)行判斷，再進(jìn)行判斷， p!=NULL條件不成立，循環(huán)結(jié)束。條件不成立，循環(huán)結(jié)束。 本例所有結(jié)點(diǎn)是在程序中定義的，不是臨時(shí)開(kāi)辟的，本例所有結(jié)點(diǎn)是在程序中定義的，不是臨時(shí)開(kāi)辟的，用完也不能釋放，這種鏈表稱用完也不能釋放，這種鏈表稱“靜態(tài)鏈表靜態(tài)鏈表”。處理動(dòng)態(tài)鏈表所需的函數(shù)處理動(dòng)態(tài)鏈表所需的函數(shù)為處理動(dòng)態(tài)鏈表，為處理動(dòng)態(tài)鏈表，C提供了開(kāi)辟和釋放存儲(chǔ)單元的函數(shù)：提供了開(kāi)辟和釋放存儲(chǔ)單元的函數(shù)：vmalloc函數(shù)函數(shù)l函數(shù)原型：函數(shù)原型：void *malloc(unsigned int size);

36、l作用：在動(dòng)態(tài)區(qū)分配一個(gè)長(zhǎng)度為作用：在動(dòng)態(tài)區(qū)分配一個(gè)長(zhǎng)度為size的連續(xù)空間，函數(shù)的連續(xù)空間，函數(shù)返回值是一個(gè)指向分配域起始地址的指針，如內(nèi)存空間返回值是一個(gè)指向分配域起始地址的指針，如內(nèi)存空間不足，返回空指針不足，返回空指針NULL。 (此處：此處：void為無(wú)確定類型為無(wú)確定類型) vcalloc函數(shù)函數(shù)l函數(shù)原型：函數(shù)原型：void *calloc(unsigned n,unsigned size);l作用：在內(nèi)存動(dòng)態(tài)區(qū)分配作用：在內(nèi)存動(dòng)態(tài)區(qū)分配n個(gè)長(zhǎng)度為個(gè)長(zhǎng)度為size的連續(xù)空間，函的連續(xù)空間，函數(shù)返回指向分配域起始地址的指針，若分?jǐn)?shù)返回指向分配域起始地址的指針，若分 配不成功，返配不

37、成功，返回回NULL值。值。vfree函數(shù)函數(shù)l函數(shù)原型：函數(shù)原型：void free(void *p);l作用：釋放由作用：釋放由p指向的內(nèi)存區(qū)，使這部分內(nèi)存區(qū)能被其指向的內(nèi)存區(qū)，使這部分內(nèi)存區(qū)能被其它變量使用。它變量使用。P所指向的是最近一次所指向的是最近一次calloc或或malloc分配分配的存儲(chǔ)區(qū)域。的存儲(chǔ)區(qū)域。 free函數(shù)無(wú)返回值。函數(shù)無(wú)返回值。 v注：舊版本提供的注：舊版本提供的malloc和和calloc函數(shù)得到的是指函數(shù)得到的是指向字符型數(shù)據(jù)的指針。向字符型數(shù)據(jù)的指針。vANSI C提供的提供的malloc和和calloc函數(shù)規(guī)定為函數(shù)規(guī)定為void *類類型，這并不是說(shuō)該

38、函數(shù)調(diào)用后無(wú)返回值，而是返回型，這并不是說(shuō)該函數(shù)調(diào)用后無(wú)返回值，而是返回一個(gè)結(jié)點(diǎn)的地址，該地址的類型為一個(gè)結(jié)點(diǎn)的地址，該地址的類型為void(無(wú)類型或類無(wú)類型或類型不確定）型不確定）,即一段存儲(chǔ)區(qū)的首址，其具體類型無(wú)即一段存儲(chǔ)區(qū)的首址，其具體類型無(wú)法確定，只有使用時(shí)根據(jù)各個(gè)域值數(shù)據(jù)再確定。法確定，只有使用時(shí)根據(jù)各個(gè)域值數(shù)據(jù)再確定。建立動(dòng)態(tài)鏈表建立動(dòng)態(tài)鏈表v建立動(dòng)態(tài)鏈表：是指在程序執(zhí)行過(guò)程中從無(wú)到有建立動(dòng)態(tài)鏈表：是指在程序執(zhí)行過(guò)程中從無(wú)到有地建立起一個(gè)鏈表，即一個(gè)一個(gè)地開(kāi)辟結(jié)點(diǎn)和輸?shù)亟⑵鹨粋€(gè)鏈表，即一個(gè)一個(gè)地開(kāi)辟結(jié)點(diǎn)和輸入各結(jié)點(diǎn)數(shù)據(jù)，并建立起前后相鏈的關(guān)系。入各結(jié)點(diǎn)數(shù)據(jù)，并建立起前后相鏈的關(guān)系

39、。 例例11.8 寫(xiě)一函數(shù)建立一個(gè)有寫(xiě)一函數(shù)建立一個(gè)有3名學(xué)生數(shù)據(jù)的單向動(dòng)態(tài)鏈表。名學(xué)生數(shù)據(jù)的單向動(dòng)態(tài)鏈表。 v思路：思路： 設(shè)置設(shè)置3個(gè)指針變量個(gè)指針變量head、p1、p2head：指向鏈表頭的指針變量，初始化：指向鏈表頭的指針變量，初始化head=NULL。p1：指向后繼結(jié)點(diǎn)的首地址的指針變量：指向后繼結(jié)點(diǎn)的首地址的指針變量p2：指向結(jié)點(diǎn)成員：指向結(jié)點(diǎn)成員next的指針變量。的指針變量。 next的值是下一個(gè)結(jié)點(diǎn)的首地址。的值是下一個(gè)結(jié)點(diǎn)的首地址。 循環(huán)方式用循環(huán)方式用malloc函數(shù)開(kāi)辟第函數(shù)開(kāi)辟第1個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。n=1p1、p2指向第指向第1結(jié)點(diǎn)首地址（見(jiàn)下頁(yè)插圖）結(jié)點(diǎn)首地址（見(jiàn)下

40、頁(yè)插圖）輸入數(shù)據(jù)，如果輸入數(shù)據(jù)，如果p1num !=0， 則則head=p1結(jié)點(diǎn)鏈入鏈表，反之不鏈入。結(jié)點(diǎn)鏈入鏈表，反之不鏈入。 開(kāi)辟第開(kāi)辟第2個(gè)結(jié)點(diǎn)：個(gè)結(jié)點(diǎn)：n=2p1指向第指向第2結(jié)點(diǎn)首地址。結(jié)點(diǎn)首地址。輸入數(shù)據(jù)。輸入數(shù)據(jù)。如果如果p1num !=0，鏈入，鏈入2結(jié)點(diǎn)，結(jié)點(diǎn)，方法：方法： p2next=p1(n=1)9910189.5headp1p2 為建立第為建立第3個(gè)結(jié)點(diǎn)做準(zhǔn)備：個(gè)結(jié)點(diǎn)做準(zhǔn)備：p2=p1，騰出，騰出p1 。(a)(n=2)headp2p19910189.59910390headp2p19910189.59910390(b)(n=2)headp2p19910189.599

41、10390(c) (n=2) 重復(fù)重復(fù)兩步開(kāi)辟第兩步開(kāi)辟第3個(gè)結(jié)點(diǎn)，并鏈入鏈表。個(gè)結(jié)點(diǎn)，并鏈入鏈表。 9910189.59910390headp2p19910785(a) n=39910189.59910390headp2p19910785(b) n=3n=n+1n=1 head=p1 p2next=p1 真真 假假(把把p1所指結(jié)點(diǎn)作所指結(jié)點(diǎn)作為第一個(gè)結(jié)點(diǎn)為第一個(gè)結(jié)點(diǎn))(把把p1所指結(jié)點(diǎn)所指結(jié)點(diǎn)連接到表尾連接到表尾)p2=p1 (p2移到表尾）移到表尾）再開(kāi)辟一個(gè)新結(jié)點(diǎn)，使再開(kāi)辟一個(gè)新結(jié)點(diǎn)，使p1指向它指向它讀入一個(gè)學(xué)生數(shù)據(jù)給讀入一個(gè)學(xué)生數(shù)據(jù)給p1所指結(jié)點(diǎn)所指結(jié)點(diǎn)表尾結(jié)點(diǎn)的指針變量置表尾結(jié)點(diǎn)

42、的指針變量置NULL開(kāi)辟一個(gè)新結(jié)點(diǎn)，并使開(kāi)辟一個(gè)新結(jié)點(diǎn)，并使p1, p2指向它指向它讀入一個(gè)學(xué)生數(shù)據(jù)給讀入一個(gè)學(xué)生數(shù)據(jù)給p1所指向的結(jié)點(diǎn)所指向的結(jié)點(diǎn)head=NULL, n=0當(dāng)讀入的當(dāng)讀入的p1 num 不是零不是零 再開(kāi)辟新結(jié)點(diǎn)，由于再開(kāi)辟新結(jié)點(diǎn)，由于num數(shù)據(jù)為數(shù)據(jù)為0，退出循環(huán)。，退出循環(huán)。并使并使p2next=NULL，雖然，雖然p1指向新結(jié)點(diǎn)但沒(méi)有指向新結(jié)點(diǎn)但沒(méi)有鏈入鏈表。鏈入鏈表。 9910189.59910390p2p19910785(a) n=3head00009910189.59910390p2p19910785NULL(b) n=3head#include “stdio.

43、h”#include “malloc.h”#define NULL 0 #define LEN sizeof (struct student) struct student long num; float score; struct student *next; ; int n;struct student *creat(void) struct student *head; struct student *p1, *p2; n=0; p1=p2=(struct student *) malloc(LEN); scanf(“%ld,%f”,&p1 num, &p1 score)

44、; head=NULL; while(p1 num !=0) n=n+1; if(n=1)head=p1; else p2 next=p1; p2=p1; p1=(struct student *)malloc (LEN); scanf(“%ld,%f”,&p1 num, & p1 score); p2 next=NULL; return(head); #include “stdio.h” /*改進(jìn)后改進(jìn)后*/#include “stdlib.h”#define NULL 0 #define LEN sizeof (struct student) struct student

45、long num; float score; struct student *next; ; int n;struct student *creat(void) struct student *head; struct student *p1, *p2; flot s; n=0; p1=p2=(struct student *) malloc(LEN); scanf(“%ld,%f”,&p1 num,&s); p1 score=s; head=NULL; while(p1 num !=0) n=n+1; if(n=1)head=p1; else p2 next=p1; p2=p

46、1; p1=(struct student *)malloc (LEN); scanf(“%ld ,%f”,&p1 num,&s); p1 score=s; p2 next=NULL; return(head); 輸出鏈表輸出鏈表思路：思路： 設(shè)一個(gè)指針變量設(shè)一個(gè)指針變量p，找到鏈表第，找到鏈表第1個(gè)結(jié)點(diǎn)的地址個(gè)結(jié)點(diǎn)的地址（head的值），的值），p指向該結(jié)點(diǎn)，輸出結(jié)點(diǎn)各成員的數(shù)指向該結(jié)點(diǎn)，輸出結(jié)點(diǎn)各成員的數(shù)據(jù)，再據(jù)，再p后移后移指向下一結(jié)點(diǎn)。指向下一結(jié)點(diǎn)。NULLheadPPP=head,使使p指向第一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn) P指向的不是尾結(jié)點(diǎn)指向的不是尾結(jié)點(diǎn) 真真 假假輸出輸

47、出p所指向的結(jié)點(diǎn)所指向的結(jié)點(diǎn)p=p next當(dāng)當(dāng)p指的不是表尾指的不是表尾例例11.9 寫(xiě)一個(gè)輸出鏈表的函數(shù)寫(xiě)一個(gè)輸出鏈表的函數(shù)print。 void print( struct student *head) struct student *p; printf(“n Now, these %d records are :n”, n); p=head; if(head) !=NULL) do printf(“%ld, %5.2fn”, p num, p score); p=p next; while(p !=NULL); 對(duì)鏈表的刪除操作對(duì)鏈表的刪除操作并不真從內(nèi)存中抹掉，只是把它分離，再前后結(jié)

48、點(diǎn)相鏈接。并不真從內(nèi)存中抹掉，只是把它分離，再前后結(jié)點(diǎn)相鏈接。 例例11.10 寫(xiě)一函數(shù)刪除動(dòng)態(tài)鏈表中指定的結(jié)點(diǎn)。寫(xiě)一函數(shù)刪除動(dòng)態(tài)鏈表中指定的結(jié)點(diǎn)。 思路：本例以學(xué)號(hào)作為刪除結(jié)點(diǎn)的標(biāo)志（查找對(duì)象）。思路：本例以學(xué)號(hào)作為刪除結(jié)點(diǎn)的標(biāo)志（查找對(duì)象）。 設(shè)兩個(gè)指針變量設(shè)兩個(gè)指針變量p1和和p2。從。從head開(kāi)始，開(kāi)始，p1依次指向各結(jié)點(diǎn)查依次指向各結(jié)點(diǎn)查找找num值是否等于要?jiǎng)h除結(jié)點(diǎn)的學(xué)號(hào)。每次下移前使值是否等于要?jiǎng)h除結(jié)點(diǎn)的學(xué)號(hào)。每次下移前使p2=p1。學(xué)號(hào)相等刪除該結(jié)點(diǎn)，直至查到表尾。學(xué)號(hào)相等刪除該結(jié)點(diǎn)，直至查到表尾。99101headp19910399107NULL(a) 初始狀態(tài)初始狀態(tài)p2

49、(b) 下移一個(gè)結(jié)點(diǎn)下移一個(gè)結(jié)點(diǎn) headp199107NULL9910199103p2=p1找到要?jiǎng)h除的結(jié)點(diǎn)后：找到要?jiǎng)h除的結(jié)點(diǎn)后：如果要?jiǎng)h除的是第如果要?jiǎng)h除的是第1結(jié)點(diǎn)，則結(jié)點(diǎn)，則head=p1next 。head指指向第二結(jié)點(diǎn)，第一結(jié)點(diǎn)脫離。向第二結(jié)點(diǎn)，第一結(jié)點(diǎn)脫離。head=p1 nextheadp1(c) 選中第一個(gè)結(jié)點(diǎn)選中第一個(gè)結(jié)點(diǎn)9910199107NULL99103如果要?jiǎng)h除的不是第如果要?jiǎng)h除的不是第1結(jié)點(diǎn)，則結(jié)點(diǎn)，則p2next=p1next 。P1指向的結(jié)點(diǎn)脫離。指向的結(jié)點(diǎn)脫離。還要考慮鏈表為空和鏈表中沒(méi)有要?jiǎng)h除的結(jié)點(diǎn)的情況。還要考慮鏈表為空和鏈表中沒(méi)有要?jiǎng)h除的結(jié)點(diǎn)的情況。

50、headp2p1p2 next=p1 next (d) 第二個(gè)結(jié)點(diǎn)被刪除第二個(gè)結(jié)點(diǎn)被刪除99107NULL9910199103 p1是要?jiǎng)h除的結(jié)點(diǎn)是要?jiǎng)h除的結(jié)點(diǎn) 是是 否否 鏈表是一個(gè)空表鏈表是一個(gè)空表真真 假假輸出輸出 空表空表p1=head 當(dāng)當(dāng)num p1 num 以及以及p1 所指的結(jié)點(diǎn)不是表尾結(jié)點(diǎn)所指的結(jié)點(diǎn)不是表尾結(jié)點(diǎn)p2=p1 (p2后移一個(gè)位置）后移一個(gè)位置） p1 = p1 next (p1后移一個(gè)位置）后移一個(gè)位置）輸出輸出“找不找不 到到”的信息的信息 P1所指是頭結(jié)點(diǎn)所指是頭結(jié)點(diǎn) 是是 否否head=p1 next (刪除頭結(jié)點(diǎn)）刪除頭結(jié)點(diǎn)）p2next=p1next (

51、刪除一個(gè)結(jié)點(diǎn)）刪除一個(gè)結(jié)點(diǎn)）struct student *del(struct student *head,long num) struct student *p1,*p2; if(head = = NULL) printf(“n list null ! n”); goto end; p1=head; while(num !=p1 num & p1 next != NULL) p2=p1; p1=p1 next; if(num = p1 num) if(p1 = = head) head=p1 next; else p2 next = p1 next; printf(“delete:

52、 %dn”,num); n=n-1; else printf(“%ld not been found ! n”,num); return(head); 對(duì)鏈表的插入操作對(duì)鏈表的插入操作v假設(shè)結(jié)點(diǎn)按成員的學(xué)號(hào)從小到大排列，按排序順假設(shè)結(jié)點(diǎn)按成員的學(xué)號(hào)從小到大排列，按排序順序插入結(jié)點(diǎn)。序插入結(jié)點(diǎn)。思路：思路：找到插入點(diǎn)后，將該點(diǎn)的找到插入點(diǎn)后，將該點(diǎn)的next值指向新結(jié)點(diǎn)，并使新值指向新結(jié)點(diǎn)，并使新結(jié)點(diǎn)的結(jié)點(diǎn)的next值等于斷點(diǎn)后面結(jié)點(diǎn)的首地址。值等于斷點(diǎn)后面結(jié)點(diǎn)的首地址。 設(shè)置設(shè)置p0、p1、p2三個(gè)指針變量。創(chuàng)建一個(gè)新結(jié)點(diǎn)，三個(gè)指針變量。創(chuàng)建一個(gè)新結(jié)點(diǎn)，p0指向其起始位置地址。指向其起始位置地

53、址。p1指向第指向第1個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。head991019910399107NULL99102p0p1(a)準(zhǔn)備將準(zhǔn)備將p0插入鏈表中插入鏈表中 如果如果p0num大于大于p1num，則，則p2=p1，然后，然后p1后移一個(gè)后移一個(gè)結(jié)點(diǎn)。直至結(jié)點(diǎn)。直至p0num小于或等于小于或等于p1num。這時(shí)。這時(shí)p0所指結(jié)所指結(jié)點(diǎn)插在點(diǎn)插在p1所指結(jié)點(diǎn)之前。所指結(jié)點(diǎn)之前。head991019910399107NULL99102p0p1p2(b) 插入點(diǎn)位于鏈表中間插入點(diǎn)位于鏈表中間 p0nump1nump2=p1, p1=p1next 如果插入點(diǎn)在鏈表中間，則如果插入點(diǎn)在鏈表中間，則p2next=p0，

54、p0next=p1，新結(jié)點(diǎn)插入了鏈表。新結(jié)點(diǎn)插入了鏈表。9910399107NULLp1head9910199102p0p2(c) 鏈接新結(jié)點(diǎn)鏈接新結(jié)點(diǎn) p0num p1nump2next=p0, p0next=p1 如果插入點(diǎn)位于最前面，則如果插入點(diǎn)位于最前面，則head=p0，p0 next=p1。99107NULLhead991009910399101p0p1(d) 結(jié)點(diǎn)插在表首結(jié)點(diǎn)插在表首 p0num p1num head=p0, p0next=p1 如果插入點(diǎn)位于最后面，如果插入點(diǎn)位于最后面，則則p1不再后移，不再后移，p1next=p0， p0next=NULLp199101991