c語(yǔ)言第八章 結(jié)構(gòu)和聯(lián)合

8.1結(jié)構(gòu)1.結(jié)構(gòu)：是擁有若干分量的一種構(gòu)造類(lèi)型，而且一個(gè)結(jié)構(gòu)的分量可以有不同的類(lèi)型，包括指針、數(shù)組、其它結(jié)構(gòu)。2.定義：struct

結(jié)構(gòu)類(lèi)型名

{成員列表}；第八章結(jié)構(gòu)和聯(lián)合例:struct

date{unsignedyear;

unsignedmonth;unsignedday;};yearmonthday注:不帶變量的結(jié)構(gòu)說(shuō)明不占存儲(chǔ)空間，結(jié)構(gòu)類(lèi)型集中放到一個(gè)文件中，需要時(shí)用#include3.三種定義結(jié)構(gòu)變量的方法1）先定義結(jié)構(gòu)類(lèi)型，再定義結(jié)構(gòu)變量struct

date{unsignedyear;

unsignedmonth;

unsignedday;};struct

dated1,d2yearmonthdayd1yearmonthdayd22）在定義結(jié)構(gòu)類(lèi)型的同時(shí)定義變量struct

date{unsignedyear;

unsignedmonth;

unsignedday;}d1,d2;3）直接定義結(jié)構(gòu)類(lèi)型變量struct{unsignedyear;

unsignedmonth;

unsignedday;}date,d1,d2;3.三種定義結(jié)構(gòu)變量的方法struct

student{intnum;

charname[20];

charsex;

intage;

struct

datebirthday;charaddr;}student1,student2;4.結(jié)構(gòu)的嵌套struct

date{unsignedyear;unsignedmonth;unsignedday;};numnamesexagebirthdayyearmonthdayaddr8.2訪(fǎng)問(wèn)結(jié)構(gòu)成員舊標(biāo)準(zhǔn)規(guī)定只能對(duì)結(jié)構(gòu)變量中的成員分別訪(fǎng)問(wèn)，而不能對(duì)結(jié)構(gòu)變量進(jìn)行賦值和輸出。新標(biāo)準(zhǔn)允許將一個(gè)結(jié)構(gòu)變量直接賦給另一個(gè)具有相同結(jié)構(gòu)的結(jié)構(gòu)變量。如果結(jié)構(gòu)變量本身又屬于一個(gè)結(jié)構(gòu)類(lèi)型，只能對(duì)最低層的成員進(jìn)行賦值、存取和運(yùn)算。如：

student1.birthday.year=1967；“.”是成員（分量）運(yùn)算符，優(yōu)先級(jí)最高，自左向右結(jié)合。

結(jié)構(gòu)成員可以象普通變量一樣進(jìn)行各種運(yùn)算，例如：

student2.age=student1.age;

student1.age++;++studdent2.age;

可以引用成員的地址，結(jié)構(gòu)變量的地址，例如：&

student1.num&student18.2訪(fǎng)問(wèn)結(jié)構(gòu)成員當(dāng)結(jié)構(gòu)變量為全局變量或靜態(tài)變量時(shí)，可在定義時(shí)初始化，例如：static

struct

student{intnum;

charname[20];charsex;charaddr[20];}a={54,“Jane”,“

M

”,“

123Road

”};8.2訪(fǎng)問(wèn)結(jié)構(gòu)成員8.3結(jié)構(gòu)數(shù)組和指向結(jié)構(gòu)的指針當(dāng)結(jié)構(gòu)中的每一個(gè)元素都是同一結(jié)構(gòu)類(lèi)型時(shí)，稱(chēng)該數(shù)組為結(jié)構(gòu)數(shù)組。定義結(jié)構(gòu)數(shù)組時(shí)，可對(duì)全局或靜態(tài)存儲(chǔ)類(lèi)別的數(shù)組初始化。structstudent{intnum;charname[20];

intage;charaddr[30];}stu[]={{10101,“LiLin”,18,“M”,“beijing”},

{10102,“FuPing”,19,“M”,“shanghai”}};numnamesexageaddr10101LiLinM18beijing10102FuPing19shanghaiMstustructstudent{intnum;charname[20];

intage;charaddr[30];}stu[]={{10101,“LiLin”,18,“M”,“beijing”},

{10102,“FuPing”,19,“M”,“shanghai”}};8.3結(jié)構(gòu)數(shù)組和指向結(jié)構(gòu)的指針struct

value{intkey；

intfreq；}；#defineARRAYSIZE1000；staticstruct

valueset_arr[ARRAYSIZE]；find(x)intx{inti,m；set_arr[m=set_arr[0].freq+1].key=x；set-arr[m].freq=0；for(i=1；set-arr[i].key!=x；i++)；set-arr[i].freq++；if(i==m)set-arr[0].freq++;}例8.1在某集合中查詢(xún)是否存在值x，若不存在，則將x加入集合中。每次查詢(xún)均記錄查詢(xún)的頻率。keyfreqset-arr[0]set-arr[i]set-arr[m]x0

x

freq++字符個(gè)數(shù)指向結(jié)構(gòu)的指針：用一個(gè)指針變量指向結(jié)構(gòu)變量，此時(shí)該指針變量的值是結(jié)構(gòu)變量的起始地址。指針變量也可以用來(lái)指向結(jié)構(gòu)數(shù)組中的元素。例如：

struct

studentstu_1;

/*定義結(jié)構(gòu)變量*/struct

student

stu［4］;/*定義結(jié)構(gòu)數(shù)組*/struct

student

*p;

/*定義指向結(jié)構(gòu)的指針變量*/p=&stu_1;

/*指向結(jié)構(gòu)變量stu_1*/p=stu;

/*指向結(jié)構(gòu)數(shù)組stu*/8.3結(jié)構(gòu)數(shù)組和指向結(jié)構(gòu)的指針structstudent{intnum;charname［20］;charsex;floatscore;};通過(guò)指向結(jié)構(gòu)的指針訪(fǎng)問(wèn)結(jié)構(gòu)成員，訪(fǎng)問(wèn)結(jié)構(gòu)成員的方式：結(jié)構(gòu)變量名.成員名例如：stu_1.num；(*p).num；/*(*p)表示p指向的結(jié)構(gòu)變量，注意*p兩側(cè)的括號(hào)不能省略，因?yàn)槌蓡T運(yùn)算符的優(yōu)先級(jí)高于取內(nèi)容運(yùn)算符的優(yōu)先級(jí)。(*p).num:p指向的結(jié)構(gòu)變量中的成員num。通過(guò)指針變量訪(fǎng)問(wèn)結(jié)構(gòu)成員的一般形式是:指向結(jié)構(gòu)的指針變量->成員名注意“.”和“->”的優(yōu)先級(jí)相同，自左向右結(jié)合。例如：p->num；stu_1.num；(*p)

.num；含義相同。8.3結(jié)構(gòu)數(shù)組和指向結(jié)構(gòu)的指針請(qǐng)分析以下幾種運(yùn)算：p->n；得到p指向的結(jié)構(gòu)變量中成員n的值。

p->n++；得到p指向的結(jié)構(gòu)變量中的成員n的值，用完該值后使它加1。++p->n；得到p指向的結(jié)構(gòu)變量中的成員n的值使之加1。如果p指向結(jié)構(gòu)數(shù)組的某個(gè)元素，那么，(++p)->num；取下一個(gè)數(shù)組元素的成員num的值。(p++)->num取數(shù)組元素的成員num的值，然后將p指向下一個(gè)數(shù)組元素。(

)(

)如果指針p已定義為指向struct

student類(lèi)型的數(shù)據(jù)，它只能指向一個(gè)結(jié)構(gòu)類(lèi)型數(shù)據(jù)。p的值是stu數(shù)組的一個(gè)元素的起始地址。不是指向一個(gè)數(shù)組元素中的某一成員，即p的地址不能是成員的地址。例如：p=&stu［2］.num；/*是不對(duì)的*/8.3結(jié)構(gòu)數(shù)組和指向結(jié)構(gòu)的指針

例8.2在UNIX系統(tǒng)中用結(jié)構(gòu)數(shù)組sptmap來(lái)記錄系統(tǒng)頁(yè)表空間?？梢赃@樣簡(jiǎn)單理解：數(shù)組sptmap的每一個(gè)元素記錄一片連續(xù)的可用空間，其成員分別表示可用空間的首地址和長(zhǎng)度，結(jié)構(gòu)如下：struct

map{shortm_size;/*長(zhǎng)度*/

unsignedshortm_addr;/*地址*/}sptmap［100］;從sptmap[1]開(kāi)始搜索sptmap，sptmap[0].m-addr=0sptmap[0].m-size=整個(gè)stpmap表中未用的map數(shù)，初始化時(shí)將未用表項(xiàng)的成員m-size置0。8.3結(jié)構(gòu)數(shù)組和指向結(jié)構(gòu)的指針m-addrm-sizesptmap[100]0表中未用的map數(shù)0102401023102420472048304730485047504810242048100030482000#definemapstart(x)&x[1]#definemapsize(x)x[0].m-sizemalloc(mp,size)structmap*mp;unsignedsize;{registerunsignedinta;registerstructmap*bp;for(bp=mapstart(mp);bp->m-size;bp++){if(bp->m-size>=size){a=bp->m-addr;

bp->m-addr+=size;

if((bp->m-size-=size)==0){do{bp++;

(bp-1)->m-addr=bp->m-addr;

}while((bp-1)->m-size=bp->m-size);

mapsize(mp)++;}

return(a);}}return(0);}1.sizeof()：“求字節(jié)數(shù)”運(yùn)算符，其優(yōu)先級(jí)別與++、--等運(yùn)算符相同。sizeof的運(yùn)算對(duì)象：數(shù)據(jù)類(lèi)型，返回值：該類(lèi)型數(shù)據(jù)在內(nèi)存中占用的字節(jié)數(shù)量。例如：sizeof(int),

sizeof(double*),

sizeof(structstudent)等等。2.malloc函數(shù)：以一個(gè)無(wú)符號(hào)整數(shù)作為參數(shù)，返回指向字符的指針，例如：char*p;p=malloc(10);從可用空間中分配連續(xù)10個(gè)字節(jié)的存儲(chǔ)空間，返回該片存儲(chǔ)空間的首地址。如果沒(méi)有足夠的可用空間，則返回一個(gè)空指針NULL用以表明分配空間失敗。8.4sizeof運(yùn)算符和Ｃ的動(dòng)態(tài)存儲(chǔ)分配函數(shù)3.free(p)：p是一個(gè)指針，free將p所指向的存儲(chǔ)空間歸還給系統(tǒng)。執(zhí)行free(p)后，不會(huì)變更指針變量p的值，這個(gè)指針仍然指向原來(lái)的存儲(chǔ)空間。若p和q是兩個(gè)指向同一地址的指針變量，則執(zhí)行free(p);后，應(yīng)該跟有如下語(yǔ)句：

p=q=NULL；例如：int*pi；char*pc；語(yǔ)句*pc=‘a(chǎn)’；是錯(cuò)誤的。因?yàn)閜c的初值不確定?？梢园涯硞€(gè)變量的地址賦給pc，或用malloc函數(shù)為它動(dòng)態(tài)地分配存儲(chǔ)空間：pc=malloc(1)；為安全起見(jiàn)，調(diào)用malloc時(shí)應(yīng)該判斷是否成功地分配了存儲(chǔ)空間。形式如下：if((pc=malloc(1))==NULL)假設(shè)調(diào)用malloc分配了位置是10的一個(gè)存儲(chǔ)單元，則語(yǔ)句*pc=‘a(chǎn)’；8.4sizeof運(yùn)算符和Ｃ的動(dòng)態(tài)存儲(chǔ)分配函數(shù)#include“stdio.h”#defineINTSIZEsizeof(int)#defineNODESIZEsizeof(int)+sizeof(char*)#defineERROR{printf(“error\n”);return;}main(){inti;char*p,*q,*first,*malloc();

if((p=malloc(NODESIZE))==NULL)ERROR

first=p;*(int*)p=1;p+=INTSIZE;for(i=2;i<10;i++,p+=INTSIZE)

if((q=malloc(NODESIZE))==NULL)ERROR

else{*(char**)p=q;p=q;*(int*)p=i;}*p=NULL;for(p=first;p;p+=INTSIZE,p=*(char**)p)

printf(“%d”,*(int*)p);putchar(‘\n’);}例8.3建立一個(gè)從1到9的整數(shù)鏈表，然后打印出這些值。P=malloc(sizeof(int)+sizeof(char*))*(int*)p=1p+=sizeof(int)*(char**)p=(q=malloc(sizeof(int)+sizeof(char*)))****(int*)p=2p+=sizeof(int)*(int*)p=8p+=sizeof(int)*(char**)p=(q=malloc(sizeof(int)+sizeof(char*)))****(int*)p=9NULL函數(shù)之間結(jié)構(gòu)體變量的數(shù)據(jù)傳遞向函數(shù)傳遞結(jié)構(gòu)體變量的成員作為成員變量（簡(jiǎn)單變量、數(shù)組或指針變量），它們可以參與所屬類(lèi)型允許的任何操作；向函數(shù)傳遞結(jié)構(gòu)體變量新的ANSIC標(biāo)準(zhǔn)允許把結(jié)構(gòu)體變量作為一個(gè)整體傳送給相應(yīng)的形參；傳遞的是實(shí)參結(jié)構(gòu)體變量的值；系統(tǒng)將為結(jié)構(gòu)體類(lèi)型的形參開(kāi)辟相應(yīng)的存儲(chǔ)單元，并將實(shí)參中各成員的值賦給對(duì)應(yīng)的形參成員。8.5結(jié)構(gòu)作為函數(shù)的參數(shù)結(jié)構(gòu)體變量作為實(shí)參傳遞給函數(shù)，對(duì)應(yīng)形參得到的是它的值；函數(shù)體內(nèi)對(duì)形參結(jié)構(gòu)體變量中任何成員的操作，都不會(huì)影響對(duì)應(yīng)實(shí)參中成員的值；保證了調(diào)用函數(shù)中數(shù)據(jù)的安全；限制了將運(yùn)算結(jié)果返回給調(diào)用函數(shù)。8.5結(jié)構(gòu)作為函數(shù)的參數(shù)8.5結(jié)構(gòu)作為函數(shù)的參數(shù)在舊標(biāo)準(zhǔn)中，在結(jié)構(gòu)上可以執(zhí)行的操作僅有用&來(lái)取得它的地址，和引用它的成員。指向結(jié)構(gòu)的指針變量卻不受這些限制，從而使結(jié)構(gòu)和函數(shù)仍能在一起協(xié)調(diào)工作。函數(shù)的返回值是結(jié)構(gòu)體類(lèi)型；函數(shù)可以返回指向結(jié)構(gòu)的指針；用指向結(jié)構(gòu)的指針變量作參數(shù)。傳遞結(jié)構(gòu)體的地址：將結(jié)構(gòu)體變量的地址作為實(shí)參傳遞對(duì)應(yīng)的形參應(yīng)該是一個(gè)基類(lèi)型相同的結(jié)構(gòu)體類(lèi)型指針；系統(tǒng)只需為形參指針開(kāi)辟一個(gè)存儲(chǔ)單元存放實(shí)參結(jié)構(gòu)體變量的地址值，而不必另行建立一個(gè)結(jié)構(gòu)體變量；通過(guò)函數(shù)調(diào)用，有效地修改結(jié)構(gòu)體中成員的值節(jié)省時(shí)間、提高效率。8.5結(jié)構(gòu)作為函數(shù)的參數(shù)例：通過(guò)函數(shù)給結(jié)構(gòu)體成員賦值structst{chars[10];

intt;}getdata(struct

st

*p){scanf(“%s%d”,p->s,&p->t);}main(){struct

st

a;

getdata(&a);

printf(“%s,%d\n”,a.s,a.t);}8.5結(jié)構(gòu)作為函數(shù)的參數(shù)函數(shù)的返回值是結(jié)構(gòu)體類(lèi)型，例：struct

st

{inta;charb;}structstfun(struct

st

x){x.a=99;x.b=‘S’;returnx;}main(){struct

st

y;y.a=0;y.b=‘A’;

printf(“y.a=%dy.b=%c\n”,y.a,y.b);

y=fun(y);

printf(“y.a=%dy.b=%c\n”,y.a,y.b);}8.5結(jié)構(gòu)作為函數(shù)的參數(shù)運(yùn)行結(jié)果：y.a=0y.b=Ay.a=99y.b=S函數(shù)的返回值可以是指向結(jié)構(gòu)體變量的指針，例：struct

st

{inta;charb;}structst

*fun(struct

st

x){struct

st

*px

x.a=100;x.b=‘C’;px=&x;returnpx;}main(){struct

st

y,*p;

y.a=999;y.b=‘X’;printf(“y.a=%dy.b=%c\n”,y.a,y.b);

p=fun(y);printf(“(*p).a=%d(*p).b=%c\n”,(*p).a,p->b);}8.5結(jié)構(gòu)作為函數(shù)的參數(shù)運(yùn)行結(jié)果：y.a=999y.b=X(*p).a=100(*p).b=C例如：structstudent{longnum;charname[20];};一個(gè)返回結(jié)構(gòu)指針的函數(shù)

structstudent*new(){structstudent*aux;aux=(structstudent*)malloc(sizeof(structstudent));if(aux==NULL)

printf(“Outofmemory\n”);return(aux);}8.5結(jié)構(gòu)作為函數(shù)的參數(shù)也可以把此函數(shù)寫(xiě)成傳遞一個(gè)指向結(jié)構(gòu)的指針的指針作參數(shù)的函數(shù)。

voidnew1(s)

struct

student**s;{struct

student*aux;

aux=(struct

student*)malloc(sizeof(struct

student));if(aux==NULL)

printf(“Outofmemory\n”);else*s=aux;}8.5結(jié)構(gòu)作為函數(shù)的參數(shù)利用結(jié)構(gòu)體變量構(gòu)成鏈表結(jié)構(gòu)體中含有可以指向本結(jié)構(gòu)體的指針成員結(jié)構(gòu)體的自引用：當(dāng)一個(gè)結(jié)構(gòu)體中有一個(gè)或多個(gè)成員是指針，它們的基類(lèi)型就是本結(jié)構(gòu)體類(lèi)型時(shí)，通常把這種結(jié)構(gòu)體稱(chēng)為可以“引用自身的結(jié)構(gòu)體”。例如：struct

link{charch;

struct

link

*p;}a;8.6結(jié)構(gòu)的自引用a.ch

a.p

鏈表：把同一類(lèi)型的結(jié)構(gòu)體變量“鏈接”到一起形成“鏈表”；結(jié)點(diǎn)：被連接在一起的結(jié)構(gòu)體變量；靜態(tài)鏈表：由系統(tǒng)在內(nèi)存中開(kāi)辟了固定的、互不連續(xù)的存儲(chǔ)單元，在程序執(zhí)行的過(guò)程中，不可能人為地再產(chǎn)生新的存儲(chǔ)單元，也不可能人為地使已開(kāi)辟的存儲(chǔ)單元消失。8.6結(jié)構(gòu)的自引用0f04100f0C200f1430NULL0f000f020f040f060f080f0A0f0C0f0E0f100f120f140f16ha.cha.pb.chb.pc.chc.p例：一個(gè)簡(jiǎn)單的鏈表struct

node{intdata;

struct

node

*next;}main(){structnodea,b,c,*h,*p;a.data=10;b.data=20;c.data=30;

h=&a;a.next=&b;b.next=&c;c.next=‘\0’;

p=h;while(p){printf(“%d”,p->data);

p=p->next;}

printf(“\n”);}8.6結(jié)構(gòu)的自引用abc102030h\0ppp動(dòng)態(tài)鏈表：鏈表中的每個(gè)存儲(chǔ)單元都由動(dòng)態(tài)存儲(chǔ)分配函數(shù)獲得。各次動(dòng)態(tài)分配的存儲(chǔ)單元地址不連續(xù)；各數(shù)據(jù)之間存在著接序關(guān)系；每個(gè)結(jié)點(diǎn)由數(shù)據(jù)域和指針域組成指針域：存放下一個(gè)結(jié)點(diǎn)元素的地址每個(gè)結(jié)點(diǎn)元素沒(méi)有自己的名字，只能由指針維系結(jié)點(diǎn)元素之間的接序關(guān)系；一旦某個(gè)元素的指針“斷開(kāi)”，后續(xù)元素就再也無(wú)法找尋。8.6結(jié)構(gòu)的自引用頭指針：指向鏈表的開(kāi)始；頭結(jié)點(diǎn)：該結(jié)點(diǎn)的數(shù)據(jù)域中不存放數(shù)據(jù)；尾結(jié)點(diǎn)：鏈表最后一個(gè)結(jié)點(diǎn)的指針域置成‘\0’，標(biāo)志鏈表的結(jié)束；每個(gè)結(jié)點(diǎn)的指針域存放下一結(jié)點(diǎn)的地址；單向鏈表：只能從當(dāng)前結(jié)點(diǎn)找到后繼結(jié)點(diǎn)。鏈表的建立、結(jié)點(diǎn)數(shù)據(jù)域的輸出、結(jié)點(diǎn)的插入和刪除。8.6結(jié)構(gòu)的自引用頭結(jié)點(diǎn)87頭指針\09建立帶有頭結(jié)點(diǎn)的單向鏈表讀取數(shù)據(jù)生成新結(jié)點(diǎn)將數(shù)據(jù)存入結(jié)點(diǎn)的成員變量中將新結(jié)點(diǎn)插入到鏈表中8.6結(jié)構(gòu)的自引用頭結(jié)點(diǎn)87頭指針\09struct

*create_slist1(){intc;

structslist

*h,*s,*r;

h=(structslist)malloc(sizeof(structslist));

r=h;

scanf(“%d”,&c);while(c!=-1){s=(structslist)malloc(sizeof(structslist));

s->data=c;r->next=s;r=s;

scanf(“%d”,&c);}

r->next=‘\0’;returnh;}main(){

structslist

*head;······

head=create_slist1();······}8.6結(jié)構(gòu)的自引用structslist{intdata;

structslist

*next;}順序訪(fǎng)問(wèn)鏈表中各結(jié)點(diǎn)的數(shù)據(jù)域工作指針p：從頭到尾依次指向鏈表中的每個(gè)結(jié)點(diǎn)當(dāng)指針指向某個(gè)結(jié)點(diǎn)時(shí)，就輸出該結(jié)點(diǎn)數(shù)據(jù)域中的內(nèi)容；直到遇到鏈表結(jié)束標(biāo)志為止；如果是空鏈表，只輸出有關(guān)信息并返回調(diào)用函數(shù)。8.6結(jié)構(gòu)的自引用voidprint_slist(structslist

*head){

structslist

*p;

p=head->next;if(p==‘\0’)printf(“Linklistisnull!\n”);else{printf(“head”);do{printf(“->%d”,p->data);

p=p->next;}while(p!=‘\0’);

printf(“->end\n”);}}8.6結(jié)構(gòu)的自引用structslist{intdata;

structslist

*next;}頭結(jié)點(diǎn)87頭指針\09在單向鏈表中插入結(jié)點(diǎn)確定插入的位置后插：當(dāng)插入結(jié)點(diǎn)插在指針p所指的結(jié)點(diǎn)之后；前插：當(dāng)插入結(jié)點(diǎn)插在指針p所指的結(jié)點(diǎn)之前，當(dāng)進(jìn)行前插操作時(shí)，需要三個(gè)工作指針；s：指向新開(kāi)辟的結(jié)點(diǎn)；p：指向插入的位置；q：指向p的前趨結(jié)點(diǎn)。8.6結(jié)構(gòu)的自引用s879pq例：編寫(xiě)函數(shù)insert_snode，在值為x的結(jié)點(diǎn)前插入值為y的結(jié)點(diǎn)，若值為x的結(jié)點(diǎn)不存在，則插在表尾。在進(jìn)行插入的過(guò)程中，可能遇到三種情況：鏈表非空，值為x的結(jié)點(diǎn)存在，新結(jié)點(diǎn)應(yīng)插在該結(jié)點(diǎn)之前；鏈表非空，但值為x

的結(jié)點(diǎn)不存在，按要求，新結(jié)點(diǎn)應(yīng)插在鏈表的結(jié)尾；鏈表為空表，這種情況相當(dāng)于值為x

的結(jié)點(diǎn)不存在，新結(jié)點(diǎn)應(yīng)插在鏈表的結(jié)尾，即插在頭結(jié)點(diǎn)之后，作為鏈表的第一個(gè)結(jié)點(diǎn)；8.6結(jié)構(gòu)的自引用insert_snode(structslist*head,intx,inty){structslist*s,*p,*q;s=(structslist*)malloc(sizeof(structslist));s->data=y;q=head;p=head->next;while((p!=‘\0’)&&(p->data!=x)){q=p;p=p->next;}s->next=p;q->next=s;}8.6結(jié)構(gòu)的自引用structslist{intdata;

structslist

*next;}刪除單向鏈表中的結(jié)點(diǎn)找到待刪除結(jié)點(diǎn)的前趨結(jié)點(diǎn)q；將此前趨結(jié)點(diǎn)的指針域指向待刪除結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)；釋放被刪結(jié)點(diǎn)所占存儲(chǔ)空間。8.6結(jié)構(gòu)的自引用頭指針h頭結(jié)點(diǎn)78p9q8.6結(jié)構(gòu)的自引用二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。二叉樹(shù)中每個(gè)結(jié)點(diǎn)記錄一個(gè)不同的單詞，結(jié)點(diǎn)內(nèi)容如下：指向該單詞內(nèi)容的指針該單詞出現(xiàn)的次數(shù)指向左孩子結(jié)點(diǎn)的指針指向右孩子結(jié)點(diǎn)的指針定義結(jié)點(diǎn)的結(jié)構(gòu)：

structtnode

{char*word;

intcount;

struct

tnode

*left;

struct

tnode

*right;};這就是結(jié)構(gòu)的自引用。left和right是指向結(jié)構(gòu)的指針，而不是一個(gè)結(jié)點(diǎn)。*left*right*wordcounttnode8.6結(jié)構(gòu)的自引用若輸入如下單詞：C++、Java、Fortran、basic、Foxbase、C++，二叉樹(shù)的生成過(guò)程如下：*left*rightC++count*left*rightBasiccount*left*rightFoxbasecountCount=2*left*rightJavacount*left*rightFortrancount8.6結(jié)構(gòu)的自引用#defineMAXWORD20main(){

struct

tnode

*root,*tree();

char*t;

root=NULL;while((t=getword())!=NULL)

root=tree(root,t);

treeprint(root);}char*getword(){char*p;if((p=malloc(MAXWORD+1))==NULL)

{printf(“Outofmemory\n”);return(NULL);}

scanf(“%MAXWORDs”,p);

if(strlen(p)==0)return(NULL);

return(p);}8.6結(jié)構(gòu)的自引用struct

tnode

*tree(p,w)structtnode

*p;char*w;{struct

tnode

*talloc();

intcond;if(p==NULL){p=talloc();p->word=w;p->count=1;p->left=p->right=NULL;}elseif((cond=strcmp(w,p->word))==0)p->count++;elseif(cond<0)p->left=tree(p->left,w);else8.6結(jié)構(gòu)的自引用

p->right=tree(p->right,w);return(p);}treeprint(p)struct

tnode

*p;{if(p!=NULL){treeprint(p->left);

printf(“%4d%s＼n”,p->count,p->word);

treeprint(p->right);}}struct

tnode

*talloc(){return((struct

tnode*)malloc(sizeof(struct

tnode)));}8.6結(jié)構(gòu)的自引用8.7位域—存儲(chǔ)空間的充分利用為了節(jié)省存儲(chǔ)空間，往往需要把幾個(gè)對(duì)象擠進(jìn)一個(gè)機(jī)器字去。例如：

struct

packed-data{unsigneda:2;

unsignedb:6;

unsignedc:4;unsignedd:4;

inti;}data;struct

packed-data{unsigneda:2;

unsignedb:3;

unsignedc:4;inti;}data;1.若某一位域要從另一個(gè)字開(kāi)始存放，可以用以下形式定義：unsigneda:1;unsignedb:2;

一個(gè)儲(chǔ)存單元unsigned:0;unsignedc:3;（另一個(gè)單元）本來(lái)a,b,c應(yīng)連續(xù)存放在一個(gè)存儲(chǔ)單元（字）中，由于使用了長(zhǎng)度為0的位域，其作用是使下一個(gè)位域從下一個(gè)存儲(chǔ)單元開(kāi)始存放。因此a,b存儲(chǔ)在一個(gè)存儲(chǔ)單元中，而將c存放在另一個(gè)存儲(chǔ)單元中。8.7位域—存儲(chǔ)空間的充分利用2.一個(gè)位域必須存儲(chǔ)在同一存儲(chǔ)單元中，不能跨兩個(gè)單元。如果第一個(gè)存儲(chǔ)單元所?？臻g不能容納下一個(gè)位域，則該空間不用，而從下一個(gè)單元起存放該位域。3.可以定義無(wú)名位域。如：unsigneda:1;unsigned:2;（兩個(gè)空間不用）unsignedb:3;unsignedc:4;4.位域的長(zhǎng)度不能大于存儲(chǔ)單元的長(zhǎng)度，也不能定義位域數(shù)組。8.7位域—存儲(chǔ)空間的充分利用5.位域可以用整型格式輸出。如：printf(“%d,%d,%d”,data.a,data.b,data.c);6.位域可以在數(shù)值表達(dá)式中引用，它會(huì)被系統(tǒng)自動(dòng)地轉(zhuǎn)換成整型數(shù)。如：data.a+5/data.b8.7位域—存儲(chǔ)空間的充分利用8.8聯(lián)合（共用體）聯(lián)合:可以讓幾種不同類(lèi)型的變量存放到同一段內(nèi)存單元中。是一種類(lèi)似于結(jié)構(gòu)的復(fù)合類(lèi)型。任一時(shí)刻只能有一個(gè)變量起作用。聯(lián)合類(lèi)型變量的定義形式是：union

聯(lián)合類(lèi)型名{成員列表}變量名列表；這里變量a,b,c的存儲(chǔ)空間:uniondata{inti;

charch;

floatf;}a,b,c;uniondata{inti;charch;floatf;};union

dataa,b,c;8.8聯(lián)合0f03a.ch0f030f02a.i0f030f020f010f00a.f當(dāng)編譯程序看到關(guān)鍵字union時(shí)，就會(huì)為聯(lián)合中最長(zhǎng)的成員項(xiàng)保留一個(gè)足夠大的空間。聯(lián)合通常用于保存函數(shù)調(diào)用的返回值，以便于為程序的其它部分按不同的數(shù)據(jù)類(lèi)型引用值。聯(lián)合變量的引用方式先定義了聯(lián)合變量才能引用它，而且不能引用聯(lián)合變量，只能引用聯(lián)合變量中的成員。8.8聯(lián)合union

u-tag{intival;floatfval;char*pval;}uval;成員引用時(shí)可用uval.ival、uval.fval聯(lián)合可以出現(xiàn)在結(jié)構(gòu)和數(shù)組中,反之亦然8.8聯(lián)合例如:struct{char*name;

intflags;

intutype;

union{intival;floatfval;char*pval;}uval;}symtab［NSYM］;

*symtab[i].uval.pval8.8聯(lián)合聯(lián)合的特點(diǎn)同一個(gè)內(nèi)存段可用來(lái)存放幾種不同類(lèi)型的成員，但在每一瞬間只能存放其中一種，即每個(gè)瞬間只有一個(gè)成員起作用，其它成員不起作用。聯(lián)合中起作用的是最后一次存放的成員。聯(lián)合變量的地址和它的各成員的地址相同。不能在定義聯(lián)合變量的同時(shí)對(duì)其進(jìn)行初始化。不能把聯(lián)合變量作為函數(shù)的參數(shù)，也不能使函數(shù)帶回聯(lián)合變量，但可以使用指向聯(lián)合變量的指針。使用聯(lián)合比使用結(jié)構(gòu)更能節(jié)省存儲(chǔ)空間，但其代價(jià)是訪(fǎng)問(wèn)成員的速度要慢一些。8.8聯(lián)合例：利用共同體的特點(diǎn)分別取出int變量中高字節(jié)和低字節(jié)中的兩個(gè)數(shù)。unionchange{charc[2];

inta;}un;main(){un.a=16961;

printf(“%d,%c\n”,un.c[0],un.c[0]);

printf(“%d,%c\n”,un.c[1],un.c[1]);}8.8聯(lián)合un.c[1]un.c[0]01000010010000100f010f02un.a66,B65,A例8.4從鍵盤(pán)上讀10個(gè)值，每個(gè)值從一新行開(kāi)始讀起，以字符I或C開(kāi)頭，指出此值是整數(shù)還是字符。把這些值保存在鏈表中，重新顯示。#include“stdio.h”#defineINTEGER‘I’#defineCHARACTER‘C’#defineERROR{printf(“Error\n”);return;}#defineSKIPwhile(getchar()!=‘\n’);8.8聯(lián)合main(){inti;

structitem{union{charc;

inti;}val;

intwhat;

structitem*next;}*p,*temp;if((p=(structitem*)malloc(sizeof(structitem))==NULL)ERRORtemp=p;for(i=0;;i++){switch(getchar()){caseINTEGER:p->what=0;

scanf(“%d”,&(p->vali));break;caseCHARACTER:p->what=1;

scanf(“%c”,&(p->valc));break;default:ERROR}SKIPif(i==9)break;else{if((p->next=(structitem*)malloc(sizeof(structitem)))==NULL)ERRORp=p->next;}}for(i=0,p=temp;i<10;p=p->next,i++)if(p->what)

printf(“%c”,p->valc);elseprintf(“%d”,p->vali);}8.9枚舉類(lèi)型枚舉類(lèi)型是ANSIＣ新標(biāo)準(zhǔn)所增加的。枚舉：將變量的可能取值一一列舉出來(lái)，變量的值只限于列舉出來(lái)的值的范圍。定義枚舉類(lèi)型用關(guān)鍵字enum開(kāi)頭。例如：enum

weekday{sun,mon,tue,wed,thu,fri,sat};enum

weekdayworkday,week-end;weekday和week-end被定義為枚舉類(lèi)型變量，它們的值只能是sun到sat之一。例如：workday=mon;

或week-end=sun;在Ｃ語(yǔ)言編譯中，將枚舉元素按常量處理。它們不是變量，不能對(duì)它們賦值。枚舉元素作為常量，它們是有值的。Ｃ語(yǔ)言編譯時(shí)按定義的順序使它們的值為0，1，2,…,n在上面定義中，sun的值是0，mon的值為1，sat為6。

workday=mon;

printf(“%d”,workday);將輸出整數(shù)1。8.9枚舉類(lèi)型也可以在定義時(shí)由程序員指定枚舉元素的值，如：

enum

weekday{sun=7,mon=1,tue,wed,thu,fri,sat};枚舉值可以進(jìn)行比較運(yùn)算。其比較規(guī)則是：按其在定義時(shí)的順序號(hào)比較。如果定義時(shí)沒(méi)有人為指定序號(hào)，則第一個(gè)枚舉元素值認(rèn)作0。一個(gè)整數(shù)不能直接賦給一個(gè)枚舉變量。但可以通過(guò)強(qiáng)制類(lèi)型轉(zhuǎn)換賦值。如：workday=(enum

weekday)2;8.9枚舉類(lèi)型8.10typedef定義類(lèi)型Ｃ語(yǔ)言中可以用typedef來(lái)定義一個(gè)新的類(lèi)型名。例如：

typedefintLENGTH;LENGTHlen,maxlen;LENGTH*lengths[];同樣，說(shuō)明typedefchar*STRING;STRINGp,lineptr[LINES];也可以定義結(jié)構(gòu)類(lèi)型：typedef

struct{

intmonth;

intday;

intyear;}DATE;用typedef來(lái)定義的類(lèi)型名總是用大寫(xiě)字母書(shū)寫(xiě)的。一個(gè)更復(fù)雜的例子:為本章中的樹(shù)結(jié)點(diǎn)寫(xiě)出類(lèi)型定義:typedef

structtnode{char*word;

intcount;

structtnode*left;

structtnode*right;}TREENODE,*TREEPTR;#define是在預(yù)編譯時(shí)處理的，它只能做簡(jiǎn)單的字符串替換，而typedef是在編譯時(shí)處理的。實(shí)際上它并不是做簡(jiǎn)單的字符串替換。8.10typedef定義類(lèi)型使用typedef有兩個(gè)主要的理由：有利于程序移植。如果把typedef用于可能與機(jī)器有關(guān)的數(shù)據(jù)類(lèi)型，則在程序移植時(shí)僅需改變typedef,從而減少大量的程序修改工作。使用typedef能為程序提供更多的可讀信息，用一個(gè)適當(dāng)?shù)姆?hào)名表示一個(gè)復(fù)雜的結(jié)構(gòu)類(lèi)型會(huì)增強(qiáng)程序的可讀性。8.10typedef定義類(lèi)型寫(xiě)一個(gè)函數(shù)建立一個(gè)有5名學(xué)生數(shù)據(jù)的單向鏈表structstudent{longnum;floatscore;

structstudent

*next;};#defineLENsizeof(st