第9章結(jié)構(gòu)體和動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)哈爾濱工業(yè)大學(xué)9.1結(jié)構(gòu)體類型本節(jié)主要討論如下問(wèn)題：（1）如何聲明結(jié)構(gòu)體類型？如何定義結(jié)構(gòu)體變量、數(shù)組或指針？（2）如何訪問(wèn)結(jié)構(gòu)體的成員？對(duì)結(jié)構(gòu)體可以執(zhí)行哪些運(yùn)算？（3）如何計(jì)算結(jié)構(gòu)體在內(nèi)存中占用的字節(jié)數(shù)？9.1.1結(jié)構(gòu)體類型的聲明和結(jié)構(gòu)體變量的定義如何表示多個(gè)學(xué)生的信息呢？9.1.1結(jié)構(gòu)體類型的聲明和結(jié)構(gòu)體變量的定義內(nèi)存分配不集中，結(jié)構(gòu)零散，內(nèi)存管理困難，尋址效率不高對(duì)數(shù)組賦初值時(shí)，易發(fā)生錯(cuò)位相同類型的數(shù)據(jù)單獨(dú)放在一起存儲(chǔ)邏輯相關(guān)但類型不同的數(shù)據(jù)放在一起存儲(chǔ)structstudent{

longID;

charname[10];

chargender;

intbirthyear;

intscore[4];};structstudent{

longID;

charname[10];

chargender;

intbirthyear;

intscore[3];};結(jié)構(gòu)體成員(StructureMember)結(jié)構(gòu)體標(biāo)簽(StructureTag)，可省略結(jié)構(gòu)體模板(StructureTemplate)編譯器不為其分配內(nèi)存

關(guān)鍵字typedef為已存在的類型定義一個(gè)別名structstudent{

longID;

charname[10];

chargender;

intbirthyear;

intscore[3];

};typedef

structstudentSTUDENT;typedefstructstudent{

longID;

charname[10];

chargender;

intbirthyear;

intscore[3];

}STUDENT;9.1.1結(jié)構(gòu)體類型的聲明和結(jié)構(gòu)體變量的定義（1）先定義結(jié)構(gòu)體類型

再定義變量名structstudentstu1;structstudent{ longID; charname[10]; chargender; intbirthyear; intscore[3];};（2）在定義結(jié)構(gòu)體類型

的同時(shí)定義變量structstudent{ longID; charname[10]; chargender; intbirthyear; intscore[3];}stu1;9.1.1結(jié)構(gòu)體類型的聲明和結(jié)構(gòu)體變量的定義結(jié)構(gòu)體變量的定義（3）直接定義結(jié)構(gòu)體變量（不指定結(jié)構(gòu)體標(biāo)簽）struct{ longID; charname[10]; chargender; intbirthyear; intscore[3];}stu1;在定義結(jié)構(gòu)體變量的同時(shí)對(duì)其進(jìn)行初始化STUDENT

stu1={100310121,"張三",'M',{2001,5,19},{72,83,82}};structstudent

stu1={100310121,"張三",'M',{2001,5,19},{72,83,82}};初始化列表中成員的順序必須和結(jié)構(gòu)體類型定義的順序一致9.1.2結(jié)構(gòu)體成員的初始化和訪問(wèn)typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[3];}STUDENT;結(jié)構(gòu)體數(shù)組的定義和初始化typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[4];}STUDENT;typedefstructdate{ intyear;

intmonth; intday;}DATE;9.1.2結(jié)構(gòu)體成員的初始化和訪問(wèn)結(jié)構(gòu)體指針的定義和初始化

STUDENT

stu1;

STUDENT

*pt;pt=&stu1;如何定義指向結(jié)構(gòu)體變量的指針？

STUDENT

*pt=&stu1;等價(jià)于9.1.2結(jié)構(gòu)體成員的初始化和訪問(wèn)typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[3];}STUDENT;typedefstructdate{ intyear; intmonth; intday;}DATE;inta[5];訪問(wèn)數(shù)組的元素通過(guò)下標(biāo)（位置）選擇數(shù)組元素訪問(wèn)結(jié)構(gòu)體變量的成員通過(guò)名字訪問(wèn)結(jié)構(gòu)體的成員typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[3];}STUDENT;STUDENTstu;9.1.2結(jié)構(gòu)體成員的初始化和訪問(wèn)訪問(wèn)結(jié)構(gòu)體變量的成員成員選擇運(yùn)算符（圓點(diǎn)運(yùn)算符）對(duì)嵌套的結(jié)構(gòu)體成員，必須以級(jí)聯(lián)方式訪問(wèn)stu1.studentID=100310121;stu1.studentName="張三";//errorstrcpy(stu1.studentName,"張三");stu1.studentSex='M';stu1.birthday.year=2001;stu1.birthday.month=5;stu1.birthday.day=19;9.1.2結(jié)構(gòu)體成員的初始化和訪問(wèn)typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[3];}STUDENT;STUDENTstu;如何訪問(wèn)結(jié)構(gòu)體指針變量指向的結(jié)構(gòu)體成員呢？ptstu1成員1成員2成員3成員4成員5通過(guò)成員選擇運(yùn)算符訪問(wèn)stu1.studentID=1;(*pt).studentID=1;

通過(guò)指向運(yùn)算符訪問(wèn)pt->studentID=1;通過(guò)結(jié)構(gòu)體指針訪問(wèn)結(jié)構(gòu)體成員

STUDENT

stu1;

STUDENT

*pt=&stu1;如何定義指向結(jié)構(gòu)體變量的指針？

9.1.2結(jié)構(gòu)體成員的初始化和訪問(wèn)typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[3];}STUDENT;typedefstructdate{ intyear; intmonth; intday;}DATE;當(dāng)結(jié)構(gòu)體嵌套時(shí)，如何訪問(wèn)結(jié)構(gòu)體指針變量指向的結(jié)構(gòu)體成員？

stu1.

birthday.

year=2001;(*pt).

birthday.

year=2001;

pt->

birthday.

year=2001;通過(guò)結(jié)構(gòu)體指針訪問(wèn)結(jié)構(gòu)體成員typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[3];}STUDENT;typedefstructdate{ intyear; intmonth; intday;}DATE;9.1.2結(jié)構(gòu)體成員的初始化和訪問(wèn)在一個(gè)結(jié)構(gòu)體內(nèi)包含了另一個(gè)結(jié)構(gòu)體作為其成員9.1.2結(jié)構(gòu)體成員的初始化和訪問(wèn)typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[3];}STUDENT;typedefstructdate{ intyear;

intmonth; intday;}DATE;typedefstructdate{ intyear;

charmonth[10]; intday;}DATE;STUDENT

stu1={100310121,"張三",'M’,{2001,5,19},{72,83,90,82}};STUDENT

stu1={100310121,"張三",'M’,{2001,"May",19},{72,83,90,82}};

STUDENT

stu[30];

STUDENT

*pt;pt=stu;

如何定義指向結(jié)構(gòu)體數(shù)組的指針？

STUDENT

*pt=stu;等價(jià)于STUDENT

*pt=&stu[0];等價(jià)于ptstu[30]stu[0]stu[1]stu[2]stu[3]stu[4]......stu[29]typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[3];}STUDENT;typedefstructdate{ intyear; intmonth; intday;}DATE;9.1.2結(jié)構(gòu)體成員的初始化和訪問(wèn)pt->studentID等價(jià)于(*pt).studentIDstu[0].studentID如何訪問(wèn)結(jié)構(gòu)體指針指向的結(jié)構(gòu)體數(shù)組成員？stu[30]ptstu[0]stu[1]stu[2]stu[3]stu[4]......stu[29]pt++是什么意思？

STUDENT

stu[30];

STUDENT

*pt=stu;pt=&stu[0];

typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[3];}STUDENT;typedefstructdate{ intyear; intmonth; intday;}DATE;9.1.2結(jié)構(gòu)體成員的初始化和訪問(wèn)9.1.3結(jié)構(gòu)體占內(nèi)存的字節(jié)數(shù)結(jié)構(gòu)體類型占用內(nèi)存字節(jié)數(shù)是所有成員占內(nèi)存的總和嗎？#include<stdio.h>typedefstructsample{charm1;intm2;charm3;}SAMPLE;//定義結(jié)構(gòu)體類型SAMPLEintmain(void){SAMPLEs={'a',2,'b'}; //定義結(jié)構(gòu)體變量s并對(duì)其進(jìn)行初始化

printf("bytes=%d\n",sizeof(s));//打印結(jié)構(gòu)體變量s所占內(nèi)存字節(jié)數(shù)

return0;}內(nèi)存對(duì)齊（Memory-alignment）對(duì)于大多數(shù)計(jì)算機(jī)，數(shù)據(jù)項(xiàng)要求從某個(gè)數(shù)量字節(jié)的倍數(shù)開(kāi)始存放short型數(shù)據(jù)從偶數(shù)地址開(kāi)始存放，而int型數(shù)據(jù)則被對(duì)齊在4字節(jié)地址邊界為了滿足內(nèi)存地址對(duì)齊的要求，需要在較小的成員后加入補(bǔ)位結(jié)構(gòu)體在內(nèi)存中所占的字節(jié)數(shù)不僅與所定義的結(jié)構(gòu)體類型有關(guān)，還與計(jì)算機(jī)系統(tǒng)本身有關(guān)9.1.4結(jié)構(gòu)體占內(nèi)存的字節(jié)數(shù)1.結(jié)構(gòu)體變量的賦值操作typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[3];}STUDENT;STUDENT

stu1={100310121,"張三",

'M’,{2001,5,19},{72,83,90,82}};STUDENTstu2;stu2=stu1;只能在相同類型的結(jié)構(gòu)體變量之間進(jìn)行賦值stu2.ID=stu1.ID;strcpy(,);stu2.gender=stu1.gender;stu2.birthday.year=stu1.birthday.year;stu2.birthday.month=stu1.birthday.month;stu2.birthday.day=stu1.birthday.day;for(i=0;i<3;i++){ stu2.score[i]=stu1.score[i];}9.1.5結(jié)構(gòu)體的相關(guān)計(jì)算和操作2.結(jié)構(gòu)體變量的取地址值操作9.1.5結(jié)構(gòu)體的相關(guān)計(jì)算和操作&stu1.ID是結(jié)構(gòu)體變量stu1的ID成員即stu1.ID的地址。不是stu1的地址。雖然&stu1.ID與&stu1具有相同的地址值，但二者的實(shí)際內(nèi)涵是不同的，前者是結(jié)構(gòu)體成員的地址，后者是結(jié)構(gòu)體變量的地址，這兩個(gè)地址的基類型是不同的。9.2結(jié)構(gòu)體做函數(shù)參數(shù)向函數(shù)傳遞結(jié)構(gòu)體的單個(gè)成員復(fù)制單個(gè)成員的內(nèi)容向函數(shù)傳遞結(jié)構(gòu)體的完整結(jié)構(gòu)復(fù)制結(jié)構(gòu)體的所有成員【例9.1】復(fù)數(shù)乘法。方法1：#include<stdio.h>typedefstructcomplex{intreal;intim;}COMPLEX;COMPLEXComplexMultiply(COMPLEXza,COMPLEXzb);intmain(void){COMPLEXx,y,z;scanf("%d+%di",&x.real,&x.im);scanf("%d+%di",&y.real,&y.im);z=ComplexMultiply(x,y);printf("%d+%di\n",z.real,z.im);return0;}//函數(shù)功能：計(jì)算兩個(gè)復(fù)數(shù)之積COMPLEXComplexMultiply(COMPLEXza,COMPLEXzb){COMPLEXzc;zc.real=za.real*zb.real-za.im*zb.im;zc.im=za.real*zb.im+za.im*zb.real;returnzc;}復(fù)制結(jié)構(gòu)體的所有成員給函數(shù)函數(shù)對(duì)結(jié)構(gòu)體內(nèi)容的修改不影響原結(jié)構(gòu)體9.2.1在函數(shù)之間傳遞結(jié)構(gòu)體數(shù)據(jù)用結(jié)構(gòu)體變量作函數(shù)參數(shù)，并將函數(shù)返回類型定義為結(jié)構(gòu)體類型，以便從函數(shù)返回結(jié)構(gòu)體變量的值【例9.1】復(fù)數(shù)乘法。方法2：#include<stdio.h>typedefstructcomplex{intreal;intim;}COMPLEX;voidComplexMultiply(constCOMPLEXza,constCOMPLEXzb,COMPLEX*zc);intmain(void){COMPLEXx,y,z;scanf("%d+%di",&x.real,&x.im);scanf("%d+%di",&y.real,&y.im);ComplexMultiply(x,y,&z);printf("%d+%di\n",z.real,z.im);return0;}//函數(shù)功能：計(jì)算兩個(gè)復(fù)數(shù)之積voidComplexMultiply(constCOMPLEXza,constCOMPLEXzb,COMPLEX*zc){zc->real=za.real*zb.real-za.im*zb.im;zc->im=za.real*zb.im+za.im*zb.real;}將從函數(shù)返回結(jié)構(gòu)體zc修改為用指針變量作函數(shù)參數(shù)，通過(guò)將實(shí)參變量z的地址傳給形參結(jié)構(gòu)體指針zc，即讓zc指向z，從而獲得在函數(shù)中修改的結(jié)構(gòu)體變量z的值。9.2.1在函數(shù)之間傳遞結(jié)構(gòu)體數(shù)據(jù)【例9.1】復(fù)數(shù)乘法。方法3：#include<stdio.h>typedefstructcomplex{intreal;intim;}COMPLEX;voidComplexMultiply(constCOMPLEX*za,constCOMPLEX*zb,COMPLEX*zc);intmain(void){COMPLEXx,y,z;scanf("%d+%di",&x.real,&x.im);scanf("%d+%di",&y.real,&y.im);ComplexMultiply(&x,&y,&z);printf("%d+%di\n",z.real,z.im);return0;}//函數(shù)功能：計(jì)算兩個(gè)復(fù)數(shù)之積voidComplexMultiply(constCOMPLEX*za,constCOMPLEX*zb,COMPLEX*zc){zc->real=za->real*zb->real-za->im*zb->im;zc->im=za->real*zb->im+za->im*zb->real;}如果不希望被調(diào)函數(shù)修改結(jié)構(gòu)體變量的值，但又希望采用傳地址的方式提高數(shù)據(jù)傳遞的效率，那么同樣可以使用const限定符來(lái)保護(hù)結(jié)構(gòu)體指針形參指向的數(shù)據(jù)。9.2.1在函數(shù)之間傳遞結(jié)構(gòu)體數(shù)據(jù)【例9.2】奧運(yùn)獎(jiǎng)牌排行榜V2.0。修改例8.5程序，用結(jié)構(gòu)體編程，按國(guó)名的字典序輸出奧運(yùn)獎(jiǎng)牌排行榜。方法1:9.2.2結(jié)構(gòu)體應(yīng)用實(shí)例intmain(void){intn;structcountrycountries[N];printf("Howmanycountries?");scanf("%d",&n);Input(countries,n);StructSort(countries,n);//按國(guó)名字典序排序

Output(countries,n);return0;}//函數(shù)功能：輸入n個(gè)國(guó)家的名字和獎(jiǎng)牌數(shù)voidInput(structcountryc[],intn){printf("Inputnamesandmedals:\n");for(inti=0;i<n;i++){ scanf("%s%d",c[i].name,&c[i].medals);}}//函數(shù)功能：輸出n個(gè)國(guó)家的名字和獎(jiǎng)牌數(shù)voidOutput(structcountryc[],intn){printf("Sortedresults:\n");for(inti=0;i<n;i++){printf("%s:%d\n",c[i].name,c[i].medals);}}//函數(shù)功能：用結(jié)構(gòu)體數(shù)組做函數(shù)參數(shù)，交換法實(shí)現(xiàn)按國(guó)名字典序排序voidStructSort(structcountryc[],intn){for(inti=0;i<n-1;i++){for(intj=i+1;j<n;j++){if(strcmp(c[j].name,c[i].name)<0)//字符串比較

{SwapStruct(&c[i],&c[j]);}}}}//函數(shù)功能：兩個(gè)structcountry類型的結(jié)構(gòu)體數(shù)據(jù)互換voidSwapStruct(structcountry*x,structcountry*y){structcountryt;t=*x;*x=*y;*y=t;}9.2.2結(jié)構(gòu)體應(yīng)用實(shí)例【例9.2】奧運(yùn)獎(jiǎng)牌排行榜V2.0。修改例8.5程序，用結(jié)構(gòu)體編程，按國(guó)名的字典序輸出奧運(yùn)獎(jiǎng)牌排行榜。方法2：9.2.2結(jié)構(gòu)體應(yīng)用實(shí)例//函數(shù)功能：輸入n個(gè)國(guó)家的名字和獎(jiǎng)牌數(shù)voidInput(structcountry*p,intn){printf("Inputnamesandmedals:\n");structcountry*pEnd=p+n;//指向結(jié)構(gòu)體數(shù)組最后一個(gè)元素的指針

for(;p<pEnd;p++){ scanf("%s%d",p->name,&p->medals);}}//函數(shù)功能：輸出n個(gè)國(guó)家的名字和獎(jiǎng)牌數(shù)voidOutput(structcountry*p,intn){printf("Sortedresults:\n");structcountry*pEnd=p+n;//指向結(jié)構(gòu)體數(shù)組最后一個(gè)元素的指針

for(;p<pEnd;p++){printf("%s:%d\n",p->name,p->medals);}}//函數(shù)功能：用結(jié)構(gòu)體指針做函數(shù)參數(shù)，交換法實(shí)現(xiàn)按國(guó)名字典序排序voidStructSort(structcountry*p,intn){for(inti=0;i<n-1;i++){for(intj=i+1;j<n;j++){if(strcmp((p+j)->name,(p+i)->name)<0)//字符串比較

{SwapStruct(p+i,p+j);}}}}9.2.2結(jié)構(gòu)體應(yīng)用實(shí)例如何向函數(shù)傳遞結(jié)構(gòu)體這樣的大數(shù)據(jù)對(duì)象小結(jié)向函數(shù)傳遞結(jié)構(gòu)體的完整結(jié)構(gòu)向函數(shù)傳遞結(jié)構(gòu)體的首地址向函數(shù)傳遞結(jié)構(gòu)體的完整結(jié)構(gòu)向函數(shù)傳遞結(jié)構(gòu)體的首地址用結(jié)構(gòu)體變量作函數(shù)參數(shù)用結(jié)構(gòu)體數(shù)組/結(jié)構(gòu)體指針作函數(shù)參數(shù)向函數(shù)傳遞結(jié)構(gòu)體的完整結(jié)構(gòu)向函數(shù)傳遞結(jié)構(gòu)體的首地址用結(jié)構(gòu)體變量作函數(shù)參數(shù)用結(jié)構(gòu)體數(shù)組/結(jié)構(gòu)體指針作函數(shù)參數(shù)復(fù)制整個(gè)結(jié)構(gòu)體成員的內(nèi)容，一組數(shù)據(jù)僅復(fù)制結(jié)構(gòu)體的首地址，一個(gè)數(shù)據(jù)向函數(shù)傳遞結(jié)構(gòu)體的完整結(jié)構(gòu)向函數(shù)傳遞結(jié)構(gòu)體的首地址用結(jié)構(gòu)體變量作函數(shù)參數(shù)用結(jié)構(gòu)體數(shù)組/結(jié)構(gòu)體指針作函數(shù)參數(shù)復(fù)制整個(gè)結(jié)構(gòu)體成員的內(nèi)容，一組數(shù)據(jù)僅復(fù)制結(jié)構(gòu)體的首地址，一個(gè)數(shù)據(jù)參數(shù)傳遞直觀，但開(kāi)銷大，效率低參數(shù)傳遞效率高向函數(shù)傳遞結(jié)構(gòu)體的完整結(jié)構(gòu)向函數(shù)傳遞結(jié)構(gòu)體的首地址用結(jié)構(gòu)體變量作函數(shù)參數(shù)用結(jié)構(gòu)體數(shù)組/結(jié)構(gòu)體指針作函數(shù)參數(shù)復(fù)制整個(gè)結(jié)構(gòu)體成員的內(nèi)容，一組數(shù)據(jù)僅復(fù)制結(jié)構(gòu)體的首地址，一個(gè)數(shù)據(jù)參數(shù)傳遞直觀，但開(kāi)銷大，效率低參數(shù)傳遞效率高函數(shù)內(nèi)對(duì)結(jié)構(gòu)內(nèi)容的修改不影響原結(jié)構(gòu)體可修改結(jié)構(gòu)體指針?biāo)赶虻慕Y(jié)構(gòu)體的內(nèi)容9.3共用體類型和枚舉類型用戶自定義數(shù)據(jù)類型結(jié)構(gòu)體，也稱結(jié)構(gòu)（struct）把關(guān)系緊密且邏輯相關(guān)的多種不同類型的的變量，組織到一個(gè)統(tǒng)一的名字之下共用體，也稱聯(lián)合（union）把情形互斥但邏輯相關(guān)的多種不同類型的變量，組織到一個(gè)統(tǒng)一的名字之下structperson

{charname[20];chargender;intage;

union

maritalStatemarital;intmarryFlag;};unionmaritalState{intsingle;/*未婚*/

structmarriedStatemarried;/*已婚*/

structdivorceStatedivorce;/*離婚*/};9.3共用體類型和枚舉類型unionmaritalState{intsingle;/*未婚*/

structmarriedStatemarried;/*已婚*/

structdivorceStatedivorce;/*離婚*/};structmarriedState{

structdatemarryDay; charspouseName[20]; intchild;};structdivorceState{

structdatedivorceDay; intchild;};structdate{ intyear; intmonth; intday;};9.3共用體類型和枚舉類型structperson{charname[20];charsex;intage;unionmaritalStatemarital;

intmarryFlag;//婚姻狀態(tài)標(biāo)記字段};structpersonp1;共用體的一個(gè)主要問(wèn)題：如何標(biāo)記共用體中當(dāng)前起作用的成員是哪一個(gè)？if(p1.marryFlag==1){ //未婚}elseif(p1.marryFlag==2){ //已婚}else{//離婚}

每次對(duì)共用體的成員賦值時(shí)，程序負(fù)責(zé)改變標(biāo)記字段的內(nèi)容9.3共用體類型和枚舉類型枚舉標(biāo)簽9.4枚舉類型及其應(yīng)用枚舉（Enumeration）——一一列舉應(yīng)用場(chǎng)合當(dāng)某些量?jī)H由有限個(gè)整型數(shù)據(jù)值組成時(shí)枚舉類型的聲明

enum

weeks{SUN,MON,TUE,WED,THU,FRI,SAT};

enum

weeks{SUN=7,MON=1,TUE,WED,THU,FRI,SAT}; typedefenumweeks{SUN,MON,TUE,WED,THU,FRI,SAT}WEEKS; enum

weeks

today;

WEEKStoday;值為0值為1枚舉常量值為29.4枚舉類型及其應(yīng)用用枚舉類型聲明結(jié)構(gòu)體中的標(biāo)記字段structperson{charname[20];chargender;intage;unionmaritalStatemarital;enum{SINGLE,MARRIED,DIVORCE}marryFlag;};structpersonp1;

structperson{charname[20];chargender;intage;unionmaritalStatemarital;intmarryFlag;};structpersonp1;小結(jié)兩種新的數(shù)據(jù)類型結(jié)構(gòu)體（struct）共用體（union）關(guān)系緊密且邏輯相關(guān)的多種不同類型的數(shù)據(jù)的集合情形互斥但邏輯相關(guān)的多種不同類型的數(shù)據(jù)的集合可以做函數(shù)參數(shù)和返回值不能做函數(shù)參數(shù)，不能進(jìn)行比較操作各成員占相鄰的存儲(chǔ)單元，用sizeof來(lái)計(jì)算占用內(nèi)存的總字節(jié)數(shù)每一瞬時(shí)只能存其中一種類型的成員最后一次賦值的成員起作用對(duì)所有成員初始化只能對(duì)第一個(gè)成員初始化9.5動(dòng)態(tài)內(nèi)存分配和動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)本節(jié)主要討論如下問(wèn)題：（1）什么是動(dòng)態(tài)內(nèi)存分配？如何進(jìn)行動(dòng)態(tài)內(nèi)存分配？（2）常見(jiàn)的內(nèi)存錯(cuò)誤有哪些？如何避免這些內(nèi)存錯(cuò)誤？9.5.1動(dòng)態(tài)內(nèi)存分配C程序中變量的內(nèi)存分配方式有以下3種：（1）從靜態(tài)存儲(chǔ)區(qū)分配（2）在棧上分配（3）從堆上分配1.函數(shù)malloc()函數(shù)malloc()的原型為：void*malloc(unsignedintsize);2.函數(shù)calloc()函數(shù)calloc()的函數(shù)原型為：void*calloc(unsignedintnum,unsignedintsize);3.函數(shù)free()函數(shù)free()的函數(shù)原型為：voidfree(void*p);4.函數(shù)realloc()函數(shù)realloc()的函數(shù)原型為：void*realloc(void*p,unsignedintsize);9.5.1動(dòng)態(tài)內(nèi)存分配void*型指針不指定其指向變量的類型，可指向任意類型的變量是一種generic（通用）或typeless（無(wú)類型）的指針

使用時(shí)，需強(qiáng)轉(zhuǎn)(Type*)為其他類型9.5.1動(dòng)態(tài)內(nèi)存分配void*

malloc(unsignedintsize);向系統(tǒng)申請(qǐng)size字節(jié)的連續(xù)內(nèi)存塊，系統(tǒng)找到一塊未占用的內(nèi)存，將其標(biāo)記為已占用，把首地址返回p=(float*)malloc(n*sizeof(float));free(p);//釋放p指向的內(nèi)存頻繁申請(qǐng)/釋放，速度慢，易造成內(nèi)存碎片程序員不釋放

內(nèi)存泄漏釋放仍繼續(xù)使用

野指針空指針的用途

定義指針時(shí)進(jìn)行初始化在程序中常用作狀態(tài)比較指針不能與非指針類型變量進(jìn)行比較但可與NULL（即0值）進(jìn)行相等或不等的關(guān)系運(yùn)算

p=(int*)malloc(n*sizeof(int));if(p==NULL)//判斷內(nèi)存申請(qǐng)是否成功{printf("Noenoughmemory!\n");exit(0);}int*p;Heap（堆區(qū)）若申請(qǐng)不成功則返回NULL9.5.1動(dòng)態(tài)內(nèi)存分配9.5.2動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)之鏈表本節(jié)主要討論如下問(wèn)題：（1）何為單向鏈表？何為單向循環(huán)鏈表？（2）如何對(duì)鏈表進(jìn)行遍歷以及增、刪節(jié)點(diǎn)的操作？在C語(yǔ)言中，指針之所以重要，原因主要有以下幾點(diǎn)：（1）指針作函數(shù)參數(shù)，提供了一種從函數(shù)返回修改的變量值的手段。（2）利用指針的增1和減1運(yùn)算來(lái)尋址數(shù)組元素，可以提高程序的執(zhí)行效率。（3）指針為動(dòng)態(tài)內(nèi)存分配系統(tǒng)提供了支持。（4）利用指針和動(dòng)態(tài)內(nèi)存分配實(shí)現(xiàn)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)（如鏈表、隊(duì)列、二叉樹(shù)等）。9.5.2動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)之鏈表數(shù)組（包括結(jié)構(gòu)體數(shù)組）實(shí)際上是一種線性表的順序存儲(chǔ)方式，像這種用一組地址連續(xù)的存儲(chǔ)單元存放一個(gè)線性表，稱為順序表。優(yōu)點(diǎn)表中的數(shù)據(jù)元素在邏輯上和物理上都是相鄰的，使用直觀，便于實(shí)現(xiàn)線性表中任一元素的快速隨機(jī)存取。缺點(diǎn)插入和刪除操作時(shí)需要移動(dòng)大量的數(shù)組元素?cái)?shù)組屬于靜態(tài)數(shù)據(jù)結(jié)構(gòu)，數(shù)組的長(zhǎng)度不能在程序運(yùn)行時(shí)改變數(shù)組的長(zhǎng)度，實(shí)際使用的數(shù)組元素個(gè)數(shù)不能超過(guò)定義數(shù)組時(shí)指定的數(shù)組長(zhǎng)度的限制，否則就會(huì)發(fā)生下標(biāo)越界錯(cuò)誤，而低于所設(shè)定的最大長(zhǎng)度時(shí)，又會(huì)造成系統(tǒng)資源的浪費(fèi)，因而空間效率差CB下的錯(cuò)誤提示：field'next'hasincompletetypeVC下的錯(cuò)誤提示：'next'usesundefinedstruct'link'不能包含本結(jié)構(gòu)體類型的成員系統(tǒng)無(wú)法預(yù)知占據(jù)多少內(nèi)存

9.5.2動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)之鏈表可以包含指向本結(jié)構(gòu)體類型的指針變量structlink

{

intdata;

structlink*next;

};//遞歸數(shù)據(jù)結(jié)構(gòu)structlink

{

int data;

structlinknext;

};structlink{

int

data;//數(shù)據(jù)域：存儲(chǔ)節(jié)點(diǎn)的數(shù)據(jù)信息

structlink*next;//指針域：存儲(chǔ)其直接后繼信息};典型代表——單向鏈表（LinkedTable）用一組任意的存儲(chǔ)單元（不一定連續(xù)）鏈?zhǔn)酱鎯?chǔ)線性表數(shù)據(jù)9.5.2動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)之鏈表只包含一個(gè)指針域，又稱線性鏈表或單向鏈表9.5.2動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)之鏈表向單向鏈表中添加節(jié)點(diǎn)分兩種情況：原鏈表為空表、非空表若原鏈表為空表(head==NULL)，則將新建節(jié)點(diǎn)p置為頭節(jié)點(diǎn)若原鏈表為非空，則將新建節(jié)點(diǎn)newP添加到表尾if(head==NULL)//若鏈表為空表

{ head=newP; }else { p=head; while(pr->next!=NULL)//若未到表尾 { p=p->next;//pr指向下一節(jié)點(diǎn) } p->next=newP;//末節(jié)點(diǎn)指針指向新建節(jié)點(diǎn)}newP=(structlink*)malloc(sizeof(structlink));newP->data=nodeData;newP->next=NULL;9.5.2動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)之鏈表刪除節(jié)點(diǎn)分兩種情況：空表、非空表（待刪節(jié)點(diǎn)為頭節(jié)點(diǎn)、非頭節(jié)點(diǎn)）datanextheaddatanextpr//找待刪除節(jié)點(diǎn)while(p->data!=nodeData&&p->next!=NULL)//未找到且未到表尾{

pr=p;//在pr中保存當(dāng)前節(jié)點(diǎn)的指針

p=p->next;//p指向當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)}pp待刪除節(jié)點(diǎn)9.5.2動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)之鏈表分兩種情況：空表、非空表（待刪節(jié)點(diǎn)為頭節(jié)點(diǎn)、非頭節(jié)點(diǎn)）若原鏈表為空表，則退出程序若待刪節(jié)點(diǎn)p是頭節(jié)點(diǎn)，則將head指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)即可datanexthead待刪除節(jié)點(diǎn)datanextp頭節(jié)點(diǎn)if(p->data==nodeData)//找到待刪節(jié)點(diǎn){

if(p==head)//若待刪節(jié)點(diǎn)p為頭節(jié)點(diǎn){ head=p->next;//head指向待刪除節(jié)點(diǎn)p的后繼節(jié)點(diǎn)}

else//若待刪節(jié)點(diǎn)不是頭節(jié)點(diǎn){ pr->next=p->next;//前驅(qū)節(jié)點(diǎn)指向待刪節(jié)點(diǎn)的后繼} free(p); //釋放為已刪除節(jié)點(diǎn)分配的內(nèi)存}9.5.2動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)之鏈表若待刪節(jié)點(diǎn)不是頭節(jié)點(diǎn)，則前驅(qū)節(jié)點(diǎn)指向后繼節(jié)點(diǎn)datanextdatanext待刪除節(jié)點(diǎn)datanextp中間節(jié)點(diǎn)datanext若已搜到表尾（p->next==NULL）仍未找到待刪除節(jié)點(diǎn)，則顯示“未找到”prif(p->data==nodeData)//找到待刪節(jié)點(diǎn){ if(p==head)//若待刪節(jié)點(diǎn)p為頭節(jié)點(diǎn){ head=p->next;//head指向待刪除節(jié)點(diǎn)p的后繼節(jié)點(diǎn)} else//若待刪節(jié)點(diǎn)不是頭節(jié)點(diǎn){ pr->next=p->next;//前驅(qū)節(jié)點(diǎn)指向待刪節(jié)點(diǎn)的后繼} free(p); //釋放為已刪除節(jié)點(diǎn)分配的內(nèi)存}else//找到表尾仍未找到{printf("Notfound!\n");}9.5.2動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)之鏈表在升序的鏈表中插入節(jié)點(diǎn)分兩種情況：空表、非空有序表非空表分三種情況：在頭節(jié)點(diǎn)前、中間節(jié)點(diǎn)、表尾節(jié)點(diǎn)后插入新節(jié)點(diǎn)若原鏈表為空表，則將新節(jié)點(diǎn)p作為頭節(jié)點(diǎn)，讓head指向新節(jié)點(diǎn)phead待插入節(jié)點(diǎn)datap∧if(head==NULL)//若原鏈表為空表{ head=p;//待插入節(jié)點(diǎn)作為頭節(jié)點(diǎn)}else//若原鏈表為非空{(diào)//找待插入位置while(nodeData>pr->data&&pr->next!=NULL){ temp=pr;//在temp中保存當(dāng)前節(jié)點(diǎn)的指針 pr=pr->next;//pr指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)

} ……}p=(structlink*)malloc(sizeof(structlink));p->data=nodeData;p->next=NULL;head9.5.2動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)之鏈表待插入節(jié)點(diǎn)nodeDatanextpdatanextdata∧prprtemp待插入位置p=(structlink*)malloc(sizeof(structlink));p->data=nodeData;p->next=NULL;pr=head;if(head==NULL)//若原鏈表為空表{ head=p;//待插入節(jié)點(diǎn)作為頭節(jié)點(diǎn)}else//若原鏈表為非空{(diào)

//找待插入位置

while(nodeData>pr->data&&pr->next!=NULL)

{ temp=pr;//在temp中保存當(dāng)前節(jié)點(diǎn)的指針 pr=pr->next;//pr指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)

} ……}若原鏈表非空，則按節(jié)點(diǎn)值大?。僭O(shè)升序）確定插入新節(jié)點(diǎn)的位置9.5.2動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)之鏈表head待插入節(jié)點(diǎn)datanextpdatanextdatanextdata∧if(nodeData<=pr->data)//不在表尾插入{

if(pr==head)//若在頭節(jié)點(diǎn)前插入新節(jié)點(diǎn) { p->next=head;//將新節(jié)點(diǎn)指向鏈頭

head=p;//head指向新節(jié)點(diǎn) } else//若在鏈表中間插入新節(jié)點(diǎn) { pr=temp;