《程序設(shè)計(jì)與C語(yǔ)言》課件第8章

第8章結(jié)構(gòu)體、共用體及枚舉類型8.1結(jié)構(gòu)體類型8.2動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)8.3共用體8.4位段8.5枚舉類型習(xí)題88.1結(jié)構(gòu)體類型8.1.1結(jié)構(gòu)體變量的定義及初始化

1.結(jié)構(gòu)體類型的定義要定義結(jié)構(gòu)體變量，首先要定義結(jié)構(gòu)體類型。結(jié)構(gòu)體類型定義的一般形式是：

struct［〈結(jié)構(gòu)名〉］

{〈成員表〉；

};〈成員表〉∷=〈分量1〉；［〈分量2〉；…］

〈分量〉∷=〈類型標(biāo)識(shí)符〉〈分量名〉其中，符號(hào)“∷=”表示“定義為”，方括號(hào)中的內(nèi)容是可選的。例如語(yǔ)句

structdate{intyear;intmonthintday;};就定義了一個(gè)表示日期的結(jié)構(gòu)體類型，類型名為structdate。它的三個(gè)分量的類型均為整型。對(duì)結(jié)構(gòu)體來(lái)說(shuō)，分量的類型可以互不相同，這是它與數(shù)組的區(qū)別。數(shù)組也是構(gòu)造類型，但它要求各元素具有相同的類型。再如

structstudent{ unsignednum; charname［10］；

intage; loatscore;};定義了一個(gè)學(xué)生的結(jié)構(gòu)體類型，名字為structstudent，它有4個(gè)分量，類型各不相同。結(jié)構(gòu)體類型可以嵌套定義，即結(jié)構(gòu)體的分量類型是另一個(gè)結(jié)構(gòu)體類型。以下兩種情況都可以定義嵌套的結(jié)構(gòu)體類型：

(1)兩個(gè)結(jié)構(gòu)體類型的定義是分離的，后者可以把前者作為其分量類型。比如上面已經(jīng)定義了日期類型，則可以用它來(lái)定義學(xué)生類型：

structstudent{unsignednum;charname［10］;intage;floatscore;structdatebirthday;};

(2)還可以在一個(gè)結(jié)構(gòu)體內(nèi)部直接嵌套定義：

structstudent{unsignednum;charname［10］;intage;floatscore;struct{intyear;intmonth;intday;}birthday;}

注意：①結(jié)構(gòu)體類型不能遞歸定義，即分量的類型不能是正在定義的結(jié)構(gòu)體類型。如：

structwrong{inti;structwrongw;}；這樣的定義是錯(cuò)誤的。②定義結(jié)構(gòu)體類型時(shí)，常犯的錯(cuò)誤是忽略了最后的分號(hào)。

2.結(jié)構(gòu)體變量的定義在定義了類型名之后，就可以定義該類型的變量了。定義結(jié)構(gòu)體變量的方法有三種：

(1)如結(jié)構(gòu)體類型已定義好，則可以用來(lái)定義變量。如：

structdatedate1,date2;structstudentstu1,stu2;

注意：在使用結(jié)構(gòu)體類型名時(shí)，初學(xué)者往往會(huì)忽略保留字struct,其實(shí)structdate和structstudent都是一個(gè)統(tǒng)一的整體，二者缺一不可。

(2)定義結(jié)構(gòu)類型的同時(shí)直接定義變量，如

structdate { intyear; intmonth; intday; } date1,date2;

(3)定義結(jié)構(gòu)體類型的同時(shí)定義變量，但沒(méi)有結(jié)構(gòu)名。第(2)和(3)種的差別在于：第(2)種方法既定義了類型名又定義了變量，以后需要時(shí)還可以繼續(xù)定義新的變量，而第(3)種就不能再定義新的變量了，因?yàn)樗鼪](méi)有結(jié)構(gòu)名。

3.結(jié)構(gòu)體變量賦初值結(jié)構(gòu)體變量可以在定義時(shí)賦初值，如語(yǔ)句

structstudentstu1,stu2={63001,″zhang″,18,642.5}；就對(duì)結(jié)構(gòu)體變量stu2進(jìn)行了初始化，實(shí)際上是用右邊的值對(duì)stu2各分量進(jìn)行初始化，因此提供的初值必須和相應(yīng)分量的類型一致。兩個(gè)相同類型的結(jié)構(gòu)體變量之間可以進(jìn)行賦值操作。如：

stu1=stu2;則使stu1的各分量具有了和stu2各分量一樣的值。

4.結(jié)構(gòu)體指針變量的定義除了定義結(jié)構(gòu)體變量之外，還可定義結(jié)構(gòu)體指針變量。如：

structstudentstu1,*p；定義了結(jié)構(gòu)體類型指針p。像其他類型的指針一樣，結(jié)構(gòu)體指針只有和某個(gè)結(jié)構(gòu)體變量發(fā)生了聯(lián)系，即得到了結(jié)構(gòu)體變量的首地址之后才能被使用。如：

p=&stu1;就把stu1的首地址，即第一個(gè)分量的地址賦給了p，p于是指向這個(gè)結(jié)構(gòu)體變量，如下圖所示。這之后對(duì)stu1和對(duì)*p的操作效果都是一樣的。stu1pnumnameagescore

5.結(jié)構(gòu)體變量的內(nèi)存分配結(jié)構(gòu)體變量由各分量組成。各分量分配內(nèi)存的次序和規(guī)則與普通變量有所不同。如：structstudent{charname［7］;intage;charsex;floatscore;}stu,*p=&stu;則其內(nèi)存分配情況如圖8-1所示。圖8-1結(jié)構(gòu)體變量各分量的內(nèi)存分配情況從圖8-1中可以看出：

(1)結(jié)構(gòu)體變量中各分量?jī)?nèi)存分配的情況是：按照各分量出現(xiàn)的先后次序，先出現(xiàn)的分量在上面，地址小；后出現(xiàn)的分量在下面，地址大。

(2)數(shù)組分量中，下標(biāo)小的元素在上面，地址??；下標(biāo)大的元素在下面，地址大。

(3)各分量之間的關(guān)系依系統(tǒng)的不同而有所不同。對(duì)TurboC來(lái)說(shuō)，各分量之間沒(méi)有空洞，即不要求各分量按整字邊界存放，它們之間是緊湊的。因此，當(dāng)用sizeof運(yùn)算符求結(jié)構(gòu)體變量的大小時(shí)，其值等于各分量實(shí)際字節(jié)數(shù)之和，此處有：sizeof(stu)=14。而對(duì)VisualC++而言，要求各分量按整字邊界存放，這樣在各分量之間就有可能存在空洞，因此在用sizeof運(yùn)算符求結(jié)構(gòu)體變量的大小時(shí)，必須將這些空洞計(jì)算進(jìn)來(lái)，此處有：sizeof(stu)=20。由此可知，在求結(jié)構(gòu)體變量的大小時(shí)，必須首先明確是在什么系統(tǒng)中進(jìn)行的。8.1.2結(jié)構(gòu)體數(shù)組及結(jié)構(gòu)體分量的引用

1.結(jié)構(gòu)體數(shù)組一個(gè)結(jié)構(gòu)體變量可以處理一個(gè)對(duì)象，如果有多個(gè)對(duì)象，則需要多個(gè)結(jié)構(gòu)體變量，這時(shí)應(yīng)該用結(jié)構(gòu)體數(shù)組來(lái)處理多個(gè)同類型的對(duì)象。例如，定義一個(gè)產(chǎn)品類型的數(shù)組prod：

structproduct{unsignedlongno;charname［15］;intnum;floatprice;}prod［3］；定義結(jié)構(gòu)體變量的其他兩種方法也可以用來(lái)定義結(jié)構(gòu)體數(shù)組。對(duì)結(jié)構(gòu)體數(shù)組可以初始化，例如

structproductprod［3］={{112346,″football″,56,284.5},{112347,″basketball″,108,256},{112348,″valleyball″,35,96.4}};其邏輯結(jié)構(gòu)如圖8-2所示。圖8-2結(jié)構(gòu)體數(shù)組的邏輯結(jié)構(gòu)這個(gè)結(jié)構(gòu)像是二維數(shù)組，但它不是真正的數(shù)組，它沒(méi)有行地址和列地址之說(shuō)，因此對(duì)它用指針進(jìn)行操作時(shí)也就沒(méi)有所謂行指針和列指針的問(wèn)題，只有一種指向結(jié)構(gòu)體的指針。例如，若定義結(jié)構(gòu)體指針變量p：

structproduct*p;則經(jīng)過(guò)賦值運(yùn)算“p=prod；”之后，就使p指向了prod數(shù)組的第1個(gè)元素prod［0］。p++后指向prod［１］，即沿垂直方向向下走一步，指向下一個(gè)結(jié)構(gòu)體，而不能說(shuō)指向下一行。并且它也只能沿著垂直方向前進(jìn)，而不能沿水平方向前進(jìn)。至于水平方向的引用則涉及到對(duì)結(jié)構(gòu)體分量引用的問(wèn)題。

2.對(duì)結(jié)構(gòu)體分量的引用對(duì)結(jié)構(gòu)體分量的引用有三種方法：用點(diǎn)運(yùn)算符引用；用指向運(yùn)算符引用；對(duì)數(shù)組元素的分量用下標(biāo)加點(diǎn)或指向運(yùn)算符引用。下面分別加以說(shuō)明。

(1)用點(diǎn)運(yùn)算符引用結(jié)構(gòu)體變量的分量的方法，有兩種引用形式：

〈結(jié)構(gòu)體變量名〉.〈分量名〉 (*〈結(jié)構(gòu)體指針〉).〈分量名〉即在結(jié)構(gòu)體變量和其分量名之間加一個(gè)點(diǎn)運(yùn)算符。例如：

structproductprod,*p=∏則

prod.num=35; /*等價(jià)于(*p).num=35;*/ strcpy(,″football″)；就是對(duì)結(jié)構(gòu)體變量prod的分量進(jìn)行賦值的運(yùn)算。這時(shí)prod.num(或(*p).num)、作為一個(gè)獨(dú)立的變量使用，可以直接進(jìn)行輸入/輸出操作。

【例8-1】對(duì)結(jié)構(gòu)體分量的引用。＃include<stdio.h>structproduct{unsignedlongno;charname［15］;intnum;floatprice;};main(){structproductprod;prod.no=117364;prod.num=46;prod.price=287.5scanf(″%s″,);printf(″%lu,%s,%d,%f＼n″,prod.no,,prod.num,prod.price);return0;}運(yùn)行輸出：

football↙

117364,football,46,287.5

注意：因?yàn)閚ame分量是字符數(shù)組，所以不能用賦值語(yǔ)句直接賦值，只能用字符串處理函數(shù)strcpy或用scanf函數(shù)的控制符“%s”控制輸入。

(2)用指向運(yùn)算符引用結(jié)構(gòu)體指針?biāo)笇?duì)象的分量的方法，是用結(jié)構(gòu)體指針處理結(jié)構(gòu)體的常用形式，其引用形式為：

〈結(jié)構(gòu)體指針變量〉->〈分量名〉指向運(yùn)算符由兩個(gè)字符“-”和“>”組成，它是一個(gè)整體，中間沒(méi)有空格。例如：

p->no=117368;strcpy(p->name,″basketball″);

【例8-2】用指針重做例8-1。＃include<stdio.h>structproduct{unsignedlongno;charname［15］;intnum;floatprice;};main(){structproductprod,*p;p=∏scanf(″%lu%s%d%f″,&p->no,p->name,&p->num,&p->price);printf(″%lu,%s,%d,%f＼n″,p->no,p->name,p->num,p->price);return0;}運(yùn)行輸出：

117364valleyball75197.6↙

117364valleyball75197.6輸入時(shí)應(yīng)注意，數(shù)字和后面的字符串之間可以不留空格，編譯器會(huì)自動(dòng)識(shí)別數(shù)字的終結(jié)，但字符串和后面的數(shù)字之間必須有空格，否則編譯器會(huì)把數(shù)字也當(dāng)作字符看待。

(3)用下標(biāo)加點(diǎn)運(yùn)算符引用結(jié)構(gòu)體數(shù)組元素的分量的方法，其引用形式為：

〈數(shù)組名〉［〈下標(biāo)〉］.〈分量名〉

注意：下標(biāo)和數(shù)組名緊密相連，不可分離，不能把下標(biāo)放在分量名后面。例如：

structproductprod［３］；則

prod［2］.price=78.5;是正確的引用，而prod.price［２］則是錯(cuò)誤的寫(xiě)法。

【例8-3】建立和輸出有3個(gè)元素的產(chǎn)品結(jié)構(gòu)體數(shù)組，并輸出價(jià)格最高的產(chǎn)品的所有信息。＃include<stdio.h>structproduct{unsignedlongno;charname［15］;intnum;floatprice;struct{intyear,month,day;}}outdate;}prod［３］；main(){inti,j;floatmax=0;structproduct*p=prod;puts(″Inputprod［3］:＼n″);for(i=0;i<=2;i++)scanf(″%lu%s%d%f%d%d%d″,&prod［i］.nu,prod［i］.name,&prod［i］.num,&prod［i］.price,&prod［i］.outdate.year,&prod［i］.outdate.month,&prod［i］.outdate.day);printf(″Theprod［３］arrayis:＼n″);for(i=0;i<=2;i++){print(″%lu,%s,%d,%.2f,&d/%d/%d＼n″,p->no,p->name,p->num,p->price,p->outdate.year,p->outdate.month,p->outdate.day);p++;printf(″＼n″);}for(i=0;i<=2;i++)if(prod［i］.price>max){max=prod［i］.price;j=i;}printf(″Elementhavinghighestprice:＼n″);printf(″%lu,%s,%d,%.2f,%d,%d,%d＼n″,prod［j］.no,prod［j］.name,prod［j］.num,prod［j］.price,prod

［i］.outdate.year,prod［j］.outdate.month,prod［j］,outdate.day);return0;}運(yùn)行輸出：

Inputprod［3］：

11111aaaaa8999.22001119↙

22222bbbbb76100.4200218↙33333ccccc96187200284Theprod［3］arrayis：

11111aaaaa8999.202001/11/922222bbbbb76100.402002/1/833333ccccc96187.002002/8/4Elementhavinghighestprice:33333ccccc96187.002002/8/4本例中prod［３］是一個(gè)嵌套的結(jié)構(gòu)體類型數(shù)組，其中出廠日期分量outdate是一個(gè)結(jié)構(gòu)體類型。在對(duì)嵌套的結(jié)構(gòu)體分量進(jìn)行引用時(shí)，必須連續(xù)使用點(diǎn)運(yùn)算符，以達(dá)到分量的最底層，這時(shí)才可以對(duì)各分量進(jìn)行輸入/輸出操作。比如第i個(gè)元素的出廠年份的表示為：prod［i］.outdate.year,這個(gè)序列是個(gè)整體，相當(dāng)于一個(gè)整型變量，可以對(duì)它進(jìn)行讀/寫(xiě)。

(4)用指向運(yùn)算符也可以引用結(jié)構(gòu)體數(shù)組元素的分量，因?yàn)閷?duì)結(jié)構(gòu)體數(shù)組可以用指針進(jìn)行處理。例如有定義：

structproductprod［3］,*p;令p=prod，則p指向數(shù)組prod的第1個(gè)元素，p++指向下一個(gè)元素，每個(gè)元素又是結(jié)構(gòu)體,仍要用“->”運(yùn)算符求其分量,如圖8-3所示。用指針來(lái)引用結(jié)構(gòu)體分量時(shí)，要注意“->”運(yùn)算符的優(yōu)先級(jí)最高，它把前后兩部分連成一個(gè)不可分割的整體，因此，p->num++等價(jià)于(p->num)++，即先取出p所指結(jié)構(gòu)體的num分量的當(dāng)前值，然后對(duì)它加1；++p->num等價(jià)于++(p->num)，即對(duì)num分量加1；(++p)->num是先把p移向數(shù)組的下一個(gè)元素，再求該元素的num分量；(p++)->num是先把p所指結(jié)構(gòu)的num分量取出，再把p向下移一個(gè)元素。為了加深對(duì)結(jié)構(gòu)體指針和結(jié)構(gòu)體數(shù)組的理解，我們可以分析下面的程序。圖8-3結(jié)構(gòu)體數(shù)組的指針處理

【例8-4】分析下面程序的輸出結(jié)果。＃include<stdio.h>structsinl{char*s;inti;structsinl*slp;};main(){staticstructsinla［］= {{″abcd″,1,a+1}, {″e(cuò)fgh″,2,a+2}, {″ijkl″,3,a}};structsinl*p=a;inti; printf(″a［0］.s=%s＼tp->s=%s＼ta［2］.slp->s=%s＼n＼n″,a［0］.s,p->s,a［2］.slp->s);for(i=0;i<2;i++)printf(″--a［%d］.i=%d＼t++a［%d］.s［3］=%c＼n″,i,--a［i］.i,i,++a［i］.s［3］)；

printf(″++(p->s)=%s＼ta［(++p)->i］.s=%s＼t″″a［--(p->slp->i)］.s=%s＼n″,++(p->s)，

a［(++p)->i］.s,a［--(p->slp->i)］.s);return0;}運(yùn)行輸出：

a［０］.s=abcdp->s=abcda［2］.slp->s=abcd--a［0］.i=0++a［0］.s［3］=e--a［1］.i=1++a［１］.s［3］=i++(p->s)=fgia[(++p)->i].s=abcea[--(p->slp->i)].s=abce程序中定義了一個(gè)結(jié)構(gòu)體數(shù)組a并初始化。從初始化的數(shù)據(jù)看有三個(gè)結(jié)構(gòu)體。圖8-4畫(huà)出了這三個(gè)結(jié)構(gòu)體中指針的指向。圖8-4結(jié)構(gòu)體中指針的指向在定義的結(jié)構(gòu)體中，分量slp是指向自身結(jié)構(gòu)的指針，這種結(jié)構(gòu)稱為自引用結(jié)構(gòu)。slp又稱為“鏈接”，它能夠把一個(gè)structsinl結(jié)構(gòu)體與另一個(gè)同樣的結(jié)構(gòu)體鏈接在一起。因?yàn)閟lp是指針，所以這不是遞歸定義。結(jié)構(gòu)體中有一個(gè)分量的名字為i，而在主函數(shù)中，i又被定義成一個(gè)新的整型變量，兩者是否會(huì)沖突?答案是不會(huì)，因?yàn)樗鼈兯幍牡胤讲煌?，作用也不同。①由圖8-3可知，a［０］的s分量是指向字符串的指針；p->s為p所指對(duì)象的s分量，即a［0］的s分量，是一個(gè)指針；a［2］.slp->s為a［２］的slp分量所指對(duì)象的s分量，也即a［０］的s分量。這三種表示是等價(jià)的，因而輸出也相同，為“abcd”。②因?yàn)?-a［i］.i等價(jià)于--(a［i］.i)，即以a［i］的i分量的值減1作為輸出結(jié)果，所以--a［0］.i=0,--a［1］.i=1，于是a［0］.i=0,a［i］.i=1。③因?yàn)?+a［i］.s［3］=++(a［i］.s［3］)，s是指向字符串中第一個(gè)字符的指針，s+3為指向該串第3+1個(gè)字符的指針，又因?yàn)閟［3］=*(s+3)，即s［3］為該串第3+1個(gè)字符，所以++a［i］.s［3］表示a［i］的s分量指向的字符串中的第3+1個(gè)字符加1(即其后繼字符)，所以++a［0］.s［3］=e,++a［1］.s［3］=i，于是a［0］.s指向“abce”，a［1］.s指向“efgi”。在下面的輸出中，以TurboC對(duì)函數(shù)參數(shù)由右向左進(jìn)行求值的順序，先計(jì)算并輸出a［--(p->slp->i)］.s,然后是a［(++p)->i］.s，最后是++(p->s)，且左邊的求值受右邊求值的影響。④求a［--(p->slp->i)］.s：這時(shí)p指向a［0］,p->slp->i，即a［1］.i,它的值已變?yōu)?，再對(duì)它進(jìn)行自減運(yùn)算得a［1］.i=0,于是a［0］.s指向“abce”。⑤求a［(++p)->i］.s：因p指向a［0］,則++p使p指向a［1］，而a［1］的i分量的值已變?yōu)?，則a［(++p)->i］.s仍是求a［0］.s所指字符串，即“abce”。⑥求++(p->s)：因此時(shí)p已指向a［1］,p->s即為a［1］的s分量，它指向字符串“efgi”的第1個(gè)字符e，則++(p->s)指向“efgi”的第2個(gè)字符f，故輸出為“fgi”。

注意：在循環(huán)語(yǔ)句中，a［i］.i中的兩個(gè)i代表不同的對(duì)象，方括號(hào)中的i是循環(huán)控制變量，代表數(shù)組元素的下標(biāo)，而小數(shù)點(diǎn)后面的i則是結(jié)構(gòu)體的分量名。

3.二維結(jié)構(gòu)體數(shù)組二維結(jié)構(gòu)體數(shù)組和其他類型的二維數(shù)組一樣，由行和列組成，只不過(guò)它的每個(gè)元素是一個(gè)結(jié)構(gòu)體，每個(gè)結(jié)構(gòu)體又有自己的分量，因此，在對(duì)二維結(jié)構(gòu)體數(shù)組賦初值和進(jìn)行存取的過(guò)程中，必須考慮到行、列及分量等特點(diǎn)。設(shè)有定義structcid{charch;inti;doublex;}a［3］［3］；則結(jié)構(gòu)體類型cid有三個(gè)分量，二維數(shù)組a有3行，每行有3列，共有9個(gè)元素，即有9個(gè)結(jié)構(gòu)體。它的組織形式如圖8-5所示。圖8-5二維結(jié)構(gòu)體數(shù)組在對(duì)二維數(shù)組賦初值時(shí)，為了清晰起見(jiàn)，應(yīng)適當(dāng)?shù)厥褂美ㄌ?hào)，以便于把每行、每個(gè)元素都清楚地表示出來(lái)。例如：structcida［3］［3］={{{′a′,1,1.1},{′b′,2,2.2},{′c′,3,3.3}},{{′d′,4,4.4},{′e′,5,5.5},{′f′,6,6.6}},{{′g′,7,7.7},{′h′,8,8.8},{′i′,9,9.9}},}在賦初值時(shí)應(yīng)注意，每行之間、每列之間及結(jié)構(gòu)體的分量之間都不能留有空洞，或簡(jiǎn)單地講，不能連續(xù)地出現(xiàn)兩個(gè)逗號(hào)，即在兩個(gè)逗號(hào)之間必須有具體內(nèi)容。但在每對(duì)括號(hào)內(nèi)部，后面的部分可以省略，該處的變量自動(dòng)具有初值：字符型數(shù)據(jù)的初值為空字符，數(shù)值型數(shù)據(jù)的初值為零。要引用二維數(shù)組中元素的分量，必須在數(shù)組名的后面帶兩個(gè)下標(biāo)，后跟點(diǎn)運(yùn)算符加分量名。比如要引用上述定義中的字符′f′，則其表示為a［1］［2］.ch，對(duì)其中元素2.2的引用是a［0］［1］.x。若數(shù)組名只帶一個(gè)下標(biāo)，如a［1］，則它表示第2行第1個(gè)元素的地址，此時(shí)對(duì)′f′的引用應(yīng)表示成(*(a［1］+2)).ch。注意:點(diǎn)運(yùn)算符的優(yōu)先級(jí)高于間接引用運(yùn)算符*，所以必須把*(a［1］+2)用括號(hào)括起來(lái)。

【例8-5】設(shè)有I個(gè)班，每班有J名學(xué)生，每個(gè)學(xué)生有N個(gè)成績(jī)，請(qǐng)輸入學(xué)生的姓名和4科成績(jī)，并計(jì)算每個(gè)學(xué)生的平均分，所有學(xué)生全部成績(jī)的平均分、最高分和最低分。

編程思路：一個(gè)學(xué)生的信息用一個(gè)結(jié)構(gòu)體描述，所有班、所有學(xué)生可用二維數(shù)組加以組織，因此這是一個(gè)二維結(jié)構(gòu)體數(shù)組，可用上面敘述的方法加以處理。程序如下：＃include<stdio.h>＃defineI2＃defineJ3＃defineN4structstudent{charname［10］;floatscore［N］;floatave;}a［I］［J］;main(){inti,j,n;floatmax,min,average,sum,sumi;max=average=sum=0;min=100;for(i=0;i<I;i++)for(j=0;j<J;j++){sumi=0;printf(″Inputaname:″);scanf(″%s″,&a［i］［j］.name);printf(″Input%dscores:″,N):for(n=0;n<N;n++){scanf(″%f″,&a［i］［j］.score［n］);if(a［i］［j］.score［n］>max)max=a［i］［j］.score［n］;if(a［i］［j］.score［n］<min)min=a［i］［j］.score［n］;sum+=a［i］［j］.score［n］;sumi+=a［i］［j］.score［n］;}a［i］［j］.ave=sumi/N;}for(i=0;i<I;i++){printf(″＼n＼nclass%d:＼n″,i+1);printf(″Namescore1score2score3score4average\n″);for(j=0;j<J;j++){printf(″%-5s″,(*(a［i］+j)).name);for(n=0;n<N;n++)printf(″%.1f″,(*(a［i］+j)).score［n］);printf(″%.1f＼n″,(*(a［i］+j)).ave);}}average=sum/(I*J*N);printf(″\nmax=%.1f\nmin=%.1f\ntotalaverage=%.1f\n\n″,max,min,average);return0;}運(yùn)行輸出：Inputaname:zhaoInput4scores:88898768Inputaname:qianInput4scores:78899786Inputaname:sunInput4scores:89978659Inputaname:liInput4scores:89979668Inputaname:zhouInput4scores:87766989Inputaname:wuInput4scores:85839691class1:Namescore1score2score3score4averagezhao88.089.087.068.083.0qian78.089.097.086.087.5sun89.097.086.059.082.8class2:Namescore1score2score3score4averageli89.097.096.068.087.5zhou87.076.069.089.080.3wu85.083.096.091.088.8max=97.0min=59.0totalaverage=85.08.1.3結(jié)構(gòu)體變量和結(jié)構(gòu)體指針作參數(shù)結(jié)構(gòu)體變量和結(jié)構(gòu)體指針都可以作為函數(shù)的參數(shù)及函數(shù)的返回值。若形參和實(shí)參均為結(jié)構(gòu)體變量，則參數(shù)傳遞的是結(jié)構(gòu)體的拷貝，屬于函數(shù)的傳值調(diào)用。但這樣做既費(fèi)時(shí)間又費(fèi)空間。如果把形參定義成指針類型，就可以解決這兩方面的問(wèn)題。這時(shí)實(shí)參傳遞的是結(jié)構(gòu)體變量的地址，函數(shù)中對(duì)形參的處理就是對(duì)實(shí)參的直接處理。下面的例子說(shuō)明了這種情況。

【例8-6】求兩個(gè)復(fù)數(shù)的和與積。

編程思路：復(fù)數(shù)相加的公式為：(a+bi)+(c+di)=(a+c)+(b+d)i即兩個(gè)復(fù)數(shù)相加結(jié)果仍為一復(fù)數(shù)，結(jié)果的實(shí)部為兩個(gè)復(fù)數(shù)的實(shí)部之和，結(jié)果的虛部為兩個(gè)復(fù)數(shù)的虛部之和。復(fù)數(shù)相乘的公式為：(a+bi)*(c+di)=(ac-bd)+(bc+ad)i復(fù)數(shù)可以設(shè)計(jì)成一個(gè)結(jié)構(gòu)體類型。復(fù)數(shù)相加與相乘用兩個(gè)函數(shù)表示。復(fù)數(shù)結(jié)構(gòu)體類型在各個(gè)函數(shù)中都要使用，因此把它放到所有函數(shù)之外，作為全局類型定義。

＃include<stdio.h>structcomplex{floatre,im;};structcomplex*cadd(structcomplex*,structcomplex*,structcomplex*);structcomplexcmul(structcomplex,structcomplex);main(){structcomplexa,b,c,d,*pa=&a,*pb=&b;*pc=&c;printf(″Inputa.re=?,a.im=?＼n″);scanf(″%f%f″,&a.re,&a.im);printf(″Inputb.re=?,b.im=?＼n″);scanf(″%f%f″,&b.re,&b.im);pc=cadd(pa,&b,&c);d=cmul(a,b);printf(″sumof2complexnumber:＼n″);printf(″c.re=%.1f,c.im=%.1f＼n″,c.re,(*pc).im);printf(″＼n＼nmultipleof2complexnumber:＼n″);printf(″d.re=%.1f,d.im=%.1f＼n″,d.re,d.im);return0;}}structcomplex*cadd(structcomplex*x,structcomplex*y,structcomplex*t){(*t).re=(*x).re+(*y).re;(*t).im=(*x).im+(*y).im;returnt;}structcomplexcmul(structcomplexx,structcomplexy){structcomplexc;c.re=x.re*y.re-x.im*y.im;c.im=x.im*y.re+x.re*y.im;returnc;}運(yùn)行輸出：

Inputa.re=?a.im=?23↙

Inputb.re=?b.im=?34↙sumof2complexnumber:c.re=5.0,c.im=7.0multipleof2complexnumber:d.re=-6.0，d.im=17.0對(duì)于cmul函數(shù)，兩個(gè)參數(shù)都是結(jié)構(gòu)體類型，實(shí)參也是兩個(gè)結(jié)構(gòu)體變量，返回值也是結(jié)構(gòu)體類型。函數(shù)cadd有3個(gè)參數(shù)，全是結(jié)構(gòu)體指針，實(shí)參有結(jié)構(gòu)體指針，也有結(jié)構(gòu)體變量的地址，它們都是等價(jià)形式。函數(shù)以一個(gè)形參t作為返回值，調(diào)用時(shí)把結(jié)構(gòu)體變量c的地址賦給形參t，則在函數(shù)中對(duì)t的處理也就是對(duì)實(shí)參c的處理。函數(shù)返回的t也被指向c的指針pc所接收。

討論：根據(jù)cadd函數(shù)的處理情況，能否去掉形參t,而把它作為函數(shù)體內(nèi)定義的指針變量呢?這是不允許的，因?yàn)樽鳛榕R時(shí)指針變量，在它和具體的結(jié)構(gòu)體建立聯(lián)系之前，它的指向是隨機(jī)的，對(duì)它指向的內(nèi)存空間的賦值有可能引起破壞性的后果。但是可以對(duì)cadd函數(shù)作如下變形：

voidcadd(structcomplex*x,structcomplex*y,structcomplex*t){(*t).re=(*x).re+(*y).re；(*t).im=(*x).im+(*y).im;}即函數(shù)中可以不要返回語(yǔ)句，因?yàn)閷?duì)形參t的處理也是對(duì)實(shí)參的處理，所以這里可以用函數(shù)語(yǔ)句的形式對(duì)函數(shù)cadd進(jìn)行調(diào)用。

cadd(pa,pb,pc)；思考：cadd函數(shù)能作如下定義嗎?structcomplex*cadd(structcomplex*x,structcomplex*y){structcomplext,*p=&t;t.re=(*x).re+(*y).re;t.im=(*x).im+(*y).im;returnp;}

注意：函數(shù)中定義的變量都是內(nèi)部變量或臨時(shí)變量，它們只在函數(shù)內(nèi)部起作用，一旦到了函數(shù)外部就失去了作用，臨時(shí)為它開(kāi)辟的內(nèi)存也被收回。

【例8-7】日期倒計(jì)時(shí)。計(jì)算今天距北京2008年奧運(yùn)會(huì)開(kāi)幕還剩多少天。編程思路：日期由年、月、日組成，可用結(jié)構(gòu)體表示。倒計(jì)時(shí)的計(jì)算由三部分組成：當(dāng)年所余天數(shù)+下一年距開(kāi)幕前一年的天數(shù)+開(kāi)幕當(dāng)年的天數(shù)。

(1)當(dāng)年所余天數(shù)=當(dāng)月所余天數(shù)+下個(gè)月至年底的天數(shù)。

·當(dāng)月所余天數(shù)=當(dāng)月總天數(shù)-當(dāng)天號(hào)數(shù)；

·下月至年底天數(shù)=各個(gè)月份的天數(shù)累加。

(2)下一年距開(kāi)幕前一年的天數(shù)=各年天數(shù)累加。累加時(shí)閏年為366天，非閏年為365天。

(3)開(kāi)幕當(dāng)年的天數(shù)=開(kāi)幕那月前數(shù)月的天數(shù)+開(kāi)幕那天的號(hào)數(shù)。設(shè)北京奧運(yùn)會(huì)開(kāi)幕時(shí)間為2008年8月8日，可用宏定義表示具體數(shù)值，若改為其他日期，只需修改宏值即可。對(duì)當(dāng)前日期的輸入，可以用一個(gè)函數(shù)實(shí)現(xiàn)，函數(shù)的參數(shù)為一個(gè)指向結(jié)構(gòu)體的指針，函數(shù)調(diào)用時(shí)的實(shí)參為主調(diào)函數(shù)中定義的指針，在使用以前它已指向了一個(gè)結(jié)構(gòu)體變量。所以函數(shù)中對(duì)形參指針的操作，也就是對(duì)結(jié)構(gòu)體變量的操作。程序如下：＃include<stdio.h>＃include<dos.h>＃defineYEAR2008＃defineMON8＃defineDAY8intdays［2］［12］={{31,28,31,30,31,30,31,31,30,31,30,31},{31,29,31,30,31,30,31,31,30,31,30,31}};structdate{intda_year;intda_mon;intda_day;};main(){inti,l,sum=0;intleap(int);voidgetdate(structdate*);structdatetoday;structdate*p1=&today;getdate(p1);printf(″today:%d.%d.%d＼n″,p1->da_year,p1->da_mon,p1->da_day);for(i=p1->da_year+1;i<=YEAR-1;i++)if(leap(i))sum+=366;elsesum+=365;l=leap(YEAR);for(i=0;i<MON-1;i++)sum+=days［1］［i］;sum+=DAY;sum+=days［l］［p1->da_mon-1］-p1->da_day;for(i=p1->da_mon;i<=11;i++)sum+=days［leap(p1->da_year)］［i］;printf(″＼nToBeijingOlympic,i1rest%ddays!＼n＼n″,sum);return0;}intleap(intm){if(m%4==0&&m%100!=0||m%400==0)return1;elsereturn0;}voidgetdate(structdate*p){printf(″Inputcurrentyear:＼n″);scanf(″%d″,&p->da_year);printf(″Inputcurrentmonth:＼n″);scanf(″%d″,&p->da_mon);printf(″Inputcurrentday:＼n″);scanf(″%d″,&p->da_day);}運(yùn)行輸出：Inputcurrentyear:2006↙

Inputcurrentmonth:7↙Inputcurrentday:20↙today:2006.7.20ToBeijingOlympic,ilrest750days!8.1.4類型名定義typedef在上面的例子中，我們定義了一個(gè)復(fù)數(shù)類型structcomplex,這是個(gè)不能分開(kāi)的整體，利用這個(gè)類型名可以定義變量、函數(shù)的返回值等。但這個(gè)類型名很長(zhǎng)，稍不留心就會(huì)出錯(cuò)。如果程序中有很多的復(fù)數(shù)類型的變量和函數(shù)需要定義，書(shū)寫(xiě)起來(lái)更是不勝其煩。能不能簡(jiǎn)單一些呢?答案是肯定的。C語(yǔ)言提供了一種機(jī)制，利用保留字typedef就可以用一個(gè)簡(jiǎn)單的名字來(lái)代替像structcomplex這樣的長(zhǎng)序列。例如：

typedefstructcomplexCOMPLEX;則COMPLEX即是和structcomplex等價(jià)的類型名，可以用它定義變量：

COMPLEXa,b,c,*pa；這樣用起來(lái)就方便多了。用typedef說(shuō)明類型名的一般形式如下：

typedef〈原類型名〉〈新類型名〉新類型名一般用大寫(xiě)表示，以便與原名在性質(zhì)上區(qū)別開(kāi)來(lái)，即它不是新創(chuàng)造的類型，而是原類型的代名詞或化身，它代表了原類型。原類型名可以是構(gòu)造類型，也可以是標(biāo)準(zhǔn)類型，如：

typedeffloatREAL;就為標(biāo)準(zhǔn)類型float起了個(gè)新名REAL。以后在程序中，原名和別名可以同時(shí)使用。如有語(yǔ)句

REALf1,f2;就定義了兩個(gè)浮點(diǎn)型的變量f1和f2。說(shuō)明新類型的方法十分簡(jiǎn)單，可按下列步驟進(jìn)行：

(1)先定義原類型的變量。

(2)把變量名大寫(xiě)，以示它為新類型名。

(3)在前面加上typedef保留字。例如：

structstudentstu;structstudentSTU;typedefstructstudentSTU;于是STU即成為structstudent的新名字，可用來(lái)定義變量了，如

STUstud1,stud2;

注意：在用新類型名定義變量時(shí)，新類型說(shuō)明中的附加部分不能寫(xiě)上，如

typedefintARRAY［10］；則新類型名為ARRAY，它代表有10個(gè)整型元素的數(shù)組，可以用它來(lái)這樣定義數(shù)組：

ARRAYa,b;而不能寫(xiě)成：

ARRAY［10］a,b；說(shuō)明：用typedef說(shuō)明新類型名的目的是為了簡(jiǎn)化書(shū)寫(xiě)，便于閱讀，這對(duì)簡(jiǎn)化結(jié)構(gòu)體類型名尤為有用，應(yīng)該學(xué)會(huì)使用。但不要把簡(jiǎn)單的問(wèn)題復(fù)雜化，比如要定義有10個(gè)整型元素的數(shù)組，完全可以寫(xiě)成：

inta［10］,b［10］,c［10］；這樣的定義相當(dāng)直觀明了，大可不必先去定義個(gè)ARRAY,再用ARRAY來(lái)定義有10個(gè)元素的數(shù)組，那樣做既麻煩又違背了簡(jiǎn)化程序的初衷。用typedef定義的新類型名不一定要大寫(xiě)，小寫(xiě)也可以，大寫(xiě)是為了突出新類型名。8.2動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)到目前為止我們所使用的數(shù)據(jù)結(jié)構(gòu)如數(shù)組等，其大小是一開(kāi)始就定義好的，在程序中不能改動(dòng)，這對(duì)內(nèi)存的合理使用及某些操作非常不便。而動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)是一開(kāi)始并不指定大小，可以隨需要不斷增加，不用時(shí)隨時(shí)取消的結(jié)構(gòu)，如鏈表、堆棧、隊(duì)列、樹(shù)等，這些動(dòng)態(tài)結(jié)構(gòu)在信息科學(xué)中非常有用。8.2.1動(dòng)態(tài)分配內(nèi)存建立和維護(hù)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)需要進(jìn)行動(dòng)態(tài)的內(nèi)存分配，即在程序執(zhí)行過(guò)程中可以動(dòng)態(tài)地得到內(nèi)存和回收內(nèi)存。動(dòng)態(tài)分配內(nèi)存的極限是計(jì)算機(jī)中可用的物理內(nèi)存空間。為實(shí)現(xiàn)動(dòng)態(tài)分配內(nèi)存，C語(yǔ)言提供了幾個(gè)專用的函數(shù)和運(yùn)算符，它們是函數(shù)malloc、calloc、free和運(yùn)算符sizeof。

1.malloc函數(shù)該函數(shù)原型為：

void*malloc(unsignedsize);功能：在內(nèi)存中開(kāi)辟size個(gè)字節(jié)大小的連續(xù)空間。返回值為該空間的起始地址。若分配不成功，則返回0值。

2.calloc函數(shù)

calloc函數(shù)的原型為：

void*calloc(unsignedn,unsignedsize);功能：在內(nèi)存中開(kāi)辟n個(gè)大小為size個(gè)字節(jié)(共n×size字節(jié))的連續(xù)空間。返回值為該段空間的起始地址。若分配不成功，則返回0值。這兩個(gè)函數(shù)返回值的類型都是void*，稱為空類型或抽象類型的指針。它具有某個(gè)內(nèi)存空間的地址值，一般用作指針類型轉(zhuǎn)換時(shí)的過(guò)渡形式。如果想讓開(kāi)辟的內(nèi)存空間中存放某種類型的數(shù)據(jù)，就把void*強(qiáng)制轉(zhuǎn)換成指向該類型的指針，以滿足不同調(diào)用環(huán)境的需要。如

char*cp；

cp=(char*)malloc(100)；這里用malloc函數(shù)開(kāi)辟出100個(gè)字節(jié)的空間，用于存放字符，返回值為指向第一個(gè)字符的指針。注意：不經(jīng)過(guò)強(qiáng)制轉(zhuǎn)換，則開(kāi)辟的內(nèi)存不可用。如定義：char*p;p=malloc(7);則編譯時(shí)會(huì)給出錯(cuò)誤提示：cannotconvertfrom′void*′to′char*′，而定義為p=(char*)malloc(7);就正確了。

double*dp=(double*)calloc(10,sizeof(double));則共開(kāi)辟出10×sizeof(double)個(gè)(即10×8=80個(gè))字節(jié)的空間，返回的指針指向第1個(gè)double單元，如圖8-6所示。

注意：NULL和void*是不同的，NULL是空指針，即值為0的指針，它常用作某種標(biāo)志。比如鏈表結(jié)尾處的結(jié)構(gòu)體的鏈接指針值為NULL，表示該指針不指向其他結(jié)構(gòu)體。圖8-6返回指針的指向

3.free函數(shù)

free函數(shù)的原型為：

voidfree(void*p)；功能：釋放p所指的內(nèi)存空間，無(wú)返回值。以上三個(gè)函數(shù)的原型在<stdlib.h>頭文件中，因此使用它們時(shí)應(yīng)把該頭文件包含進(jìn)來(lái)。

【例8-8】編一函數(shù)strsave，它可接收一個(gè)字符串，然后動(dòng)態(tài)地開(kāi)辟一個(gè)能放得下這個(gè)字符串的內(nèi)存空間，把接收到的字符串復(fù)制到其中，并返回該空間的起始地址。＃include<stdio.h>

＃include<stdlib.h>

＃include<string.h>char*strsave(char*);main(){char*str=″China″,*cp;cp=strsave(srt);printf(″str=%s,cp=%s＼n″,str,cp);return0;}charstrsave*(char*s){char*p;if((p=(char*)calloc(strlen(s)+1,1))!=NULL)strcpy(p,s);returnp;}運(yùn)行輸出：

str=China，cp=China標(biāo)準(zhǔn)函數(shù)calloc分配strlen(s)+1個(gè)大小為1的內(nèi)存空間。因?yàn)閟trlen函數(shù)統(tǒng)計(jì)字符串長(zhǎng)度時(shí)不包含′＼0′字符，但在復(fù)制字符串中還需要把′＼0′加進(jìn)去，所以分配空間時(shí)要加1。原calloc函數(shù)返回的是空類型指針，現(xiàn)在把它強(qiáng)制轉(zhuǎn)換成char型指針，再把該指針值賦給p，然后判斷p是否為NULL(0)，若不為NULL，就調(diào)用字符串拷貝函數(shù)來(lái)完成拷貝工作。函數(shù)中開(kāi)辟的內(nèi)存空間不會(huì)隨函數(shù)調(diào)用的結(jié)束而取消，因此p指針?lè)祷貋?lái)的值是有意義的。相反，如果不開(kāi)辟內(nèi)存空間，則p無(wú)所指向，不可使用。

4.sizeof運(yùn)算符

sizeof運(yùn)算符在本書(shū)第3章的3.3.6節(jié)中已有介紹，這里不再贅述。

【例8-9】學(xué)生的信息包括姓名、所在系名及三科成績(jī)。請(qǐng)輸入多個(gè)系的學(xué)生的信息，打印輸出指定系的學(xué)生的最高分和平均成績(jī)。＃include<stdio.h>＃include<string.h>＃include<stdlib.h>typedefstruct{charname［20］;char*dep;intscore［3］;}STUTP;voidstuscore(STUTP*s,char*depart,int*max,float*ave,intm){intn,i;floatsum=0;n=0;while(m!=0){if(strcmp(s->dep,depart)==0){for(i=0;i<3;i++){ sum+=(*s).score［i］; if((*s).score［i］>*max) *max=(*s).score［i］;}n++;}s++;m--;}*ave=sum/(3*n);printf(″In＼′%s＼′department,thereis%dstudents.＼n″,depart,n);}voidmain(){STUTPx［50］;inti=0,max,j;floatave;chardep［20］,depbuf［20］;while(1){puts(″Inputname:″);//scanf(″%s″,x［i］.name);getchar();gets(x［i］.name);if(strcmp(x［i］.name,″***″)==0){printf(″Inputend!＼n″);break;}puts(″Inputdepartment:″);x［i］.dep=(char*)malloc(strlen(depbuf)+1);gets(x［i］.dep);printf(″Input3scoresinteger:＼n″);for(j=0;j<3;j++)scanf(″%d″,&x［i］.score［j］);getchar();i++;}printf(″Youinput%dstudent!＼n″,i);puts(″Inputdepartnametoconsider:″);gets(dep);max=0;ave=0.0;stuscore(x,dep,&max,&ave,i);printf(″max=%d,ave=%.1f＼n″,max,ave);}程序說(shuō)明：①程序中求最高分及平均分的工作由一個(gè)函數(shù)完成，函數(shù)的形參為指針，實(shí)參為主程序中定義的變量的地址，用這種方式可以從函數(shù)調(diào)用中獲取多個(gè)數(shù)值。②結(jié)構(gòu)體類型中的系名分量是指向字符的指針，不是字符數(shù)組，因此不能直接向它拷貝字符串。因?yàn)橹羔樕形粗赶蚓唧w的內(nèi)存空間，這就需要首先調(diào)用動(dòng)態(tài)分配內(nèi)存的函數(shù)malloc分配內(nèi)存，并將此內(nèi)存空間的起始地址賦給該指針?lè)至浚缓笤儆盟M(jìn)行字符串輸入。③main函數(shù)中while循環(huán)的條件永遠(yuǎn)是真，它的循環(huán)控制是由輸入的姓名字符串決定的，如果輸入的姓名是三個(gè)*號(hào)，則循環(huán)終止。④程序中使用typedef定義了一個(gè)類型名STUPT，這樣可以使程序簡(jiǎn)潔。⑤在用scanf函數(shù)輸入姓名和分?jǐn)?shù)之后，接著調(diào)用一個(gè)getchar函數(shù)，目的是為了接收前面輸入操作中的回車符，為的是不影響下面的輸入。如果不用getchar吃掉前面留下來(lái)的回車符，則下面的輸入語(yǔ)句就會(huì)將此回車符作為輸入的內(nèi)容而出現(xiàn)錯(cuò)誤。但是，如果用gets函數(shù)輸入字符串，則不需要再用getchar去消除輸入字符串時(shí)回車符的影響，因?yàn)間ets會(huì)自動(dòng)地將回車符變?yōu)樽址Y(jié)束標(biāo)志附加到輸入字符串的末尾。運(yùn)行輸出：Inputname:aaaInputdepartment:xxxInput3scoresinteger:809070Inputname:bbbInputdepartment:xxxInput3scoresinteger:4510055Inputname:cccInputdepartment:jsjxInput3scoresinteger:889977Inputname:dddInputdepartment:xxxInput3scoresinteger:12080100Inputname:***Inputend!Youinput4student!Inputdepartnametoconsider:xxxIn′xxx′department,thereis3students.max=120,ave=82.28.2.2鏈表鏈表是用鏈表指針連在一起的自引用結(jié)構(gòu)(稱為“結(jié)點(diǎn)”)的線性集合，如圖8-7所示。其中，head是指向鏈表第一個(gè)結(jié)點(diǎn)的指針，通過(guò)它來(lái)訪問(wèn)鏈表。后面的結(jié)點(diǎn)是通過(guò)它前面結(jié)點(diǎn)中的鏈接指針來(lái)訪問(wèn)的。鏈表的最后一個(gè)結(jié)點(diǎn)中的鏈接指針被置為NULL(畫(huà)成反斜杠以表示鏈尾)。鏈表中的結(jié)點(diǎn)是在需要時(shí)建立的，鏈表中的數(shù)據(jù)是動(dòng)態(tài)存儲(chǔ)的。圖8-7鏈表的結(jié)構(gòu)我們可以把動(dòng)態(tài)的鏈表和靜態(tài)的數(shù)組作一對(duì)比，以說(shuō)明它們的特點(diǎn)。

(1)在數(shù)據(jù)元素的個(gè)數(shù)不可預(yù)知時(shí)，使用鏈表是合適的，因?yàn)榭稍谛枰獣r(shí)增加或減少鏈表中結(jié)點(diǎn)的個(gè)數(shù)；數(shù)組是在編譯時(shí)分配內(nèi)存的，其大小是不可改變的。

(2)當(dāng)數(shù)組定義得很大以備不時(shí)之需時(shí)會(huì)造成空間的浪費(fèi)；鏈表隨用隨增，不會(huì)造成空間的浪費(fèi)。

(3)對(duì)于插入和刪除操作，使用數(shù)組費(fèi)時(shí)費(fèi)力，而使用鏈表卻可以方便地在合適的位置插入和刪除結(jié)點(diǎn)，只要把有關(guān)結(jié)點(diǎn)的鏈接指針修改一下即可。

(4)數(shù)組中的元素在內(nèi)存中是連續(xù)存放的，根據(jù)相對(duì)于數(shù)組的起始位置可以計(jì)算出數(shù)組元素的地址，所以可以立即訪問(wèn)到任意位置的數(shù)組元素；鏈表中的結(jié)點(diǎn)不能被立即訪問(wèn)到，因?yàn)殒湵碇械慕Y(jié)點(diǎn)在邏輯上是連續(xù)的，但在內(nèi)存中是不連續(xù)的。雖然從總體上說(shuō)，動(dòng)態(tài)分配內(nèi)存能節(jié)省空間，但每個(gè)結(jié)點(diǎn)中的指針也要占用存儲(chǔ)空間，并且動(dòng)態(tài)分配內(nèi)存也需要一些函數(shù)調(diào)用的開(kāi)銷。下面我們研究鏈表的建立、插入、刪除及輸出等操作。

1.建立鏈表首先定義鏈表中結(jié)點(diǎn)的類型，它應(yīng)該是一個(gè)自引用的結(jié)構(gòu)體。如

structnode{intdata;structnode*next;};typedefstructnodeNode;Node為新類型名。所定義的結(jié)構(gòu)體中有兩個(gè)分量，形成兩個(gè)域：數(shù)值域和指針域。對(duì)鏈表進(jìn)行操作，需要三個(gè)指針：指向鏈表頭的指針head，指向當(dāng)前結(jié)點(diǎn)的指針p1,指向當(dāng)前結(jié)點(diǎn)前一結(jié)點(diǎn)的指針p2。先建立只有一個(gè)結(jié)點(diǎn)的鏈表，使head、p1、p2都指向它，如圖8-8所示。其操作步驟如下：

(1)產(chǎn)生一個(gè)結(jié)點(diǎn)，用p1指向它：

p1=(Node*)malloc(sizeof(Node));

(2)把p1賦給head和p2:p2=head=p1。

(3)對(duì)新結(jié)點(diǎn)的數(shù)據(jù)域輸入數(shù)據(jù)，而把其指針域置為NULL。圖8-8鏈表的建立下面建立只有兩個(gè)結(jié)點(diǎn)的鏈表，即把第二個(gè)結(jié)點(diǎn)連到第一個(gè)結(jié)點(diǎn)之后作為鏈表尾，如圖8-9所示。要達(dá)到這樣的格局，需要進(jìn)行如圖8-9所示的五步操作：①用p1指向新產(chǎn)生的結(jié)點(diǎn)：

p1=(Node*)malloc(sizeof(Node));②把新結(jié)點(diǎn)的指針域置空：

p1->next=NULL；③輸入新結(jié)點(diǎn)的數(shù)值域：

scanf(″%d″,&p->data)；④把新結(jié)點(diǎn)連到鏈表尾部：

p2->next=p1;圖8-9建立兩個(gè)結(jié)點(diǎn)的鏈表⑤讓p2也指向新結(jié)點(diǎn)：

p2=p1；以后再加入新結(jié)點(diǎn)時(shí)，操作與此類似，但沒(méi)有必要每產(chǎn)生一個(gè)新結(jié)點(diǎn)都將其指針域置為NULL，而完全可以在最后一個(gè)結(jié)點(diǎn)中實(shí)行?？梢园演斎霐?shù)值0作為鏈表建立的結(jié)束。數(shù)值域?yàn)?的結(jié)點(diǎn)不在鏈表內(nèi)。于是可寫(xiě)出如下函數(shù)：

Node*create(){Node*h=NULL,*p1,*p2;printf(″Inputintegertocreatealist,0toend:＼n″);p1=(Node*)malloc(sizeof(Node));scanf(″%d″,&p1->data);if(p1->data!=0)h=p1;

while(p1->data!=0){p2=p1;p1=(Node*)malloc(sizeof(Node));scanf(″%d″,&p1->data);p2->next=p1;}p2->next=NULL;returnh;}循環(huán)體內(nèi)的操作是在當(dāng)前結(jié)點(diǎn)的數(shù)值域不為0時(shí)才讓p2指向它。如當(dāng)前結(jié)點(diǎn)的數(shù)值域?yàn)?，則不讓p2指向它，那么p2所指的結(jié)點(diǎn)就是最后一個(gè)結(jié)點(diǎn)，因此把它的next域置為NULL。雖然在循環(huán)體中進(jìn)行過(guò)p2->next=p1的操作，但在循環(huán)體之后通過(guò)p2->next=NULL又把數(shù)值部分為0的那個(gè)結(jié)點(diǎn)從表中摘除了。這個(gè)函數(shù)的參數(shù)為空，返回值為指向結(jié)構(gòu)體的指針。

2.輸出鏈表當(dāng)鏈表的頭指針為NULL時(shí)說(shuō)明鏈表是空的，不采取行動(dòng)。只有當(dāng)鏈表非空時(shí)才從鏈表頭部開(kāi)始，輸出一個(gè)結(jié)點(diǎn)的值，然后移動(dòng)指針，再輸出下一個(gè)結(jié)點(diǎn)的值……直至表尾結(jié)束?？捎孟旅娴暮瘮?shù)完成此項(xiàng)功能：voidprintList(Node*h){Node*p;p=h;if(h==NULL)printf(″Listisempty!＼n＼n″);else{while(p!=NULL){printf(″%d->″,p->data);p=p->next;}printf(″Null＼n＼n″);}}在函數(shù)體內(nèi)定義了一個(gè)工作指針p，起流動(dòng)哨的作用，在輸出它所指結(jié)點(diǎn)的數(shù)值域之后，它就再向后移一位以指向下一個(gè)結(jié)點(diǎn)。這是由指針傳遞操作p=p->next來(lái)完成的。這個(gè)函數(shù)以結(jié)構(gòu)體指針作參數(shù)，不返回值。

3.插入結(jié)點(diǎn)在一個(gè)鏈表中插入結(jié)點(diǎn)，首先要確定插入的位置，這里要考慮幾種情況：

(1)空表情況。

(2)插在表頭。

(3)插在表中。

(4)插在表尾。完成該功能的函數(shù)中使用了三個(gè)工作指針：newp，指向要被插入的結(jié)點(diǎn)；p1，指向當(dāng)前結(jié)點(diǎn)；p2，指向當(dāng)前結(jié)點(diǎn)的前一結(jié)點(diǎn)。這里設(shè)該鏈表已經(jīng)排序且按升序插入結(jié)點(diǎn)，則從鏈表的頭部開(kāi)始，只要指向當(dāng)前結(jié)點(diǎn)的指針p1不空且要插入的結(jié)點(diǎn)的數(shù)值又比當(dāng)前結(jié)點(diǎn)的數(shù)值大，就繼續(xù)向后查找合適的位置，向后移動(dòng)的方法是修改p1和p2的值。該函數(shù)如下：Node*insert(Node*h,intvalue){Node*newp,*p1,*p2;newp=(Node*)malloc(sizeof(Node));if(newp!=NULL){newp->data=value;newp->next=NULL;p2=Null;p1=h;while(p1!=Null&&value>p1->data){p2=p1； /*移到…*/p1=p1→next; /*下一結(jié)點(diǎn)*/}if(p2==NULL) /*插在表頭*/{newp->next=h;h=newp;}else{p2->next=newp;newp->next=p1;}}elseprintf(″%dnotinserted,Nomemoryavailable＼n″,value);returnh;}該函數(shù)返回一個(gè)指向結(jié)構(gòu)體的指針，其參數(shù)為一個(gè)鏈表的頭指針和要插入的數(shù)值，最后返回的仍然是鏈表的頭指針，但鏈表在函數(shù)調(diào)用的過(guò)程中發(fā)生了變化。我們以圖示來(lái)說(shuō)明插入結(jié)點(diǎn)的操作。

(1)結(jié)點(diǎn)插在表頭。設(shè)原頭結(jié)點(diǎn)數(shù)值為8，把數(shù)值為6的結(jié)點(diǎn)插入其前，如圖8-10所示。圖8-10結(jié)點(diǎn)插在表頭

(2)結(jié)點(diǎn)插在表中間。在上面鏈表的基礎(chǔ)上插入數(shù)值為9的結(jié)點(diǎn)，如圖8-11所示。

(3)結(jié)點(diǎn)插在表尾。在上面鏈表的基礎(chǔ)上在表尾插入數(shù)值為16的結(jié)點(diǎn)，如圖8-12所示。插在表尾，意味著在while循環(huán)中以p1=NULL為條件而退出循環(huán)。圖8-11結(jié)點(diǎn)插在表中間圖8-12結(jié)點(diǎn)插在表尾

4.刪除結(jié)點(diǎn)從一個(gè)鏈表中刪除結(jié)點(diǎn)也應(yīng)考慮以下幾種情況：

(1)刪除表頭結(jié)點(diǎn)。

(2)刪除表中或表尾結(jié)點(diǎn)。

(3)找不到要?jiǎng)h的結(jié)點(diǎn)。完成該功能的函數(shù)中使用了三個(gè)工作指針：p1，指向當(dāng)前考查結(jié)點(diǎn)；p2，指向當(dāng)前結(jié)點(diǎn)的前一結(jié)點(diǎn)；temp，指向被刪結(jié)點(diǎn)。函數(shù)如下：

Node*delete(Node*h,intvalue){Node*p1,*p2,*temp;if(value==h->data) /*刪除表頭結(jié)點(diǎn)*/{temp=h;h=h->next; /*解除表頭與鏈表的連接*/free(temp); /*釋放該結(jié)點(diǎn)的內(nèi)存*/}else{p2=h;p1=h->next;while(p1!=NULL&&p1->data!=value){p2=p1; /*移到…*/p1=p1->next; /*…下一個(gè)結(jié)點(diǎn)*/}if(p1!=NULL) /*即p1->data==value*/{temp=p1;p2->next=p1->next;free(temp);