程序設(shè)計(jì)與C語言第8章結(jié)構(gòu)體、共用體及枚舉類型

第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枚舉類型

8.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)容是可選的。例如語句

structdate{

intyear;

intmonth;

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

structstudent{unsignednum;charname［10］；

intage;floatscore;};

(1)兩個(gè)結(jié)構(gòu)體變量的定義是分離的，后者可以把前者作為其分量類型。比如上面已經(jīng)定義了日期類型，則可以用它來定義學(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;};

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

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

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í)定義變量，但沒有結(jié)構(gòu)名。

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

structst

udentstu1,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；p是結(jié)構(gòu)體類型指針。像其它類型的指針一樣，結(jié)構(gòu)體指針只有和某個(gè)結(jié)構(gòu)體變量發(fā)生了聯(lián)系，即得到了結(jié)構(gòu)體變量的首地址之后才能被使用。如

p=&stu1;

這樣就把stu1的首地址，即第一個(gè)分量的地址賦給了p，p于是指向這個(gè)結(jié)構(gòu)體變量。

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ù)組來處理多個(gè)同類型的對(duì)象。例如，定義一個(gè)產(chǎn)品類型的數(shù)組prod：

structproduct{unsignedlongno;charname［15］;

intnum;floatprice;}prod[3];定義結(jié)構(gòu)體變量的其它兩種方法也可以用來定義結(jié)構(gòu)體數(shù)組。對(duì)結(jié)構(gòu)體數(shù)組可以初始化，例如

structstudentprod［3］={{112346,″football″,56,284.5},{112347,″basketball″,108,256},{112348,″valleyball″,35,96.4}};圖8―1結(jié)構(gòu)體數(shù)組的邏輯結(jié)構(gòu)

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

(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)行輸入/輸出操作?！纠?―1】＃include<stdio.h>structproduct{ unsignedlongno; charname［15］;

intnum; floatprice;};main(){

structproductprod; prod.no=117364; prod.num=46; prod.price=287.5

scanf(″%s″,);

printf(″%lu,%s,%d,%f\n″,prod.no,,prod.num, prod.price); return0;}運(yùn)行輸出：

football117364,football,46,287.5

注意：name分量的輸入，因它是字符數(shù)組，所以不能用賦值語句直接賦值，只能用字符串處理函數(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è)整體，中間沒有空格。例如：

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.6117364,valleyball,75,197.6

(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ò)誤的寫法。

【例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[3];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[j].outdate.year,prod[j].outdate.month,prod[j].outdate.day); return0;}運(yùn)行輸出：Inputprod［3］：11111aaaaa8999.2200111922222bbbbb76100.420021833333ccccc96187200284Theprodarrayis：11111aaaaa8999.202001/11/922222bbbbb76100.402002/1/833333ccccc96187.002002/8/4Elementshavinghighestprice:33333ccccc96187.002002/8/4

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

p=prod；

則p指向數(shù)組prod的第1個(gè)元素，p++指向下一個(gè)元素，每個(gè)元素又是結(jié)構(gòu)體，仍要用“->”運(yùn)算符求其分量。如圖8―2所示。圖8―2結(jié)構(gòu)體數(shù)組的指針處理【例8―4】分析下面程序的輸出結(jié)果。＃include<stdio.h>structsinl{ char *s;

int i;

structsinl*slp;};main(){ staticstructsinla［］= {{“abcd″,1,a+1}, {“efgh″,2,a+2}, {“ijkl″,3,a}};

struct

sinl*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[0].s=abcdp->s=abcda[2].slp->s=abcd--a[0].i=0++a[0].s[3]=e--a[1].i=1++a[1].s[3]=i++(p->s)=bcea[(++p)->i].s=efgha[--(p->slp->i)].s=ijkl圖8―3結(jié)構(gòu)體中指針的指向

8.1.3結(jié)構(gòu)體變量作參數(shù)結(jié)構(gòu)體變量和結(jié)構(gòu)體指針都可以作為函數(shù)的參數(shù)及函數(shù)的返回值。若形參為結(jié)構(gòu)體變量，實(shí)參也為結(jié)構(gòu)體變量時(shí)，則參數(shù)傳遞的是結(jié)構(gòu)體的拷貝，屬于函數(shù)的傳值調(diào)用。但這樣做既費(fèi)時(shí)間又費(fèi)空間。如果把形參定義成指針類型，就可以解決這兩方面的問題。這樣實(shí)參傳遞的是結(jié)構(gòu)體變量的地址，函數(shù)中對(duì)形參的處理就是對(duì)實(shí)參的直接處理。下面的例子說明了這種情況。

【例8―5】求兩個(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ù)之外，作為全局類型定義。

8.1.4類型名定義typedef

在上面的例子中，我們定義了一個(gè)復(fù)數(shù)類型

structcomplex,這是個(gè)不能分開的整體，利用這個(gè)類型名可以定義變量、函數(shù)值等。但這個(gè)類型名很長，稍不留心就會(huì)出錯(cuò)。如果程序中有很多的復(fù)數(shù)類型的變量和函數(shù)需要定義，書寫起來更是不勝其煩。能不能簡單一些呢?答案是肯定的。C語言提供了一種機(jī)制，利用保留字typedef就可以用一個(gè)簡單的名字來代替像

structcomplex這樣的長序列。例如：typedefstructcomplexCOMPLEX;

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

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

typedef<原類型名><新類型名>

新類型名一般用大寫表示，以便與原名在性質(zhì)上區(qū)別開來，即它不是新創(chuàng)造的類型，而是原類型的代名詞或化身，它代表了原類型。說明新類型的方法十分簡單，可按下列步驟進(jìn)行：(1)先定義原類型的變量；(2)把變量名大寫，以示它為新類型名；(3)在前面加上typedef保留字。8.2動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)到目前為止我們所使用的數(shù)據(jù)結(jié)構(gòu)如數(shù)組等，其大小是一開始就定義好的，程序中不能改動(dòng)，這對(duì)內(nèi)存的合理使用及某些操作非常不便。而動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)是一開始并不指定大小，可以隨需要不斷增加，不用時(shí)隨時(shí)取消的結(jié)構(gòu)，如鏈表、堆棧、隊(duì)列、樹等，這些動(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í)行過程中可以動(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語言提供了幾個(gè)專用的函數(shù)和運(yùn)算符，它們是函數(shù)malloc、calloc、free和運(yùn)算符sizeof。

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

void*malloc(unsignedsize)

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

2.calloc函數(shù)

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

void*calloc(unsignedn,unsignedsize);

功能：在內(nèi)存中開辟n個(gè)大小為size個(gè)字節(jié)(共n*size字節(jié))的連續(xù)空間。返回值為該段空間的起始地址。若分配不成功，則返回0值。圖8―4返回指針的指向

【例8―6】編一函數(shù)strsave，它可接收一個(gè)字符串，然后動(dòng)態(tà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;}char*strsave(char*s){ char*p; if((p=(char*)calloc(strlen(s)+1,1))!=NULL)

strcpy(p,s);returnp;}運(yùn)行輸出：

str=Chinacp=China

標(biāo)準(zhǔn)函數(shù)calloc分配strlen(s)+1個(gè)大小為1的內(nèi)存空間，這是因?yàn)閟trlen函數(shù)統(tǒng)計(jì)字符串長度時(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ù)來完成拷貝工作。

8.2.2鏈表鏈表是用鏈表指針連在一起的自引用結(jié)構(gòu)(稱為“結(jié)點(diǎn)”)的線性集合，如圖8―5所示。其中，head是指向鏈表第一個(gè)結(jié)點(diǎn)的指針，通過它來訪問鏈表。后面的結(jié)點(diǎn)是通過它前面結(jié)點(diǎn)中的鏈接指針來訪問的。鏈表的最后一個(gè)結(jié)點(diǎn)中的鏈接指針被置為NULL(畫成反斜杠以表示鏈尾)。鏈表中的結(jié)點(diǎn)是在需要時(shí)建立的，鏈表中的數(shù)據(jù)是動(dòng)態(tài)存儲(chǔ)的。圖8―5鏈表的結(jié)構(gòu)我們可以把動(dòng)態(tài)的鏈表和靜態(tài)的數(shù)組作一對(duì)比，以說明它們的特點(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ù)組元素的地址，所以可以立即訪問到任意位置的數(shù)組元素；鏈表中的結(jié)點(diǎn)不能被立即訪問到，因?yàn)殒湵碇械慕Y(jié)點(diǎn)在邏輯上是連續(xù)的，但在內(nèi)存中是不連續(xù)的。下面我們研究鏈表的建立、插入、刪除及輸出等操作。

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

structnode{

intdata;

structnode*next;};

typedefstructnodeNode;Node為新類型名。先建立只有一個(gè)結(jié)點(diǎn)的鏈表，使head、p1、p2都指向它，如圖8―6所示。其操作步驟如下：

(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―6鏈表的建立圖8―7建立兩個(gè)結(jié)點(diǎn)的鏈表

2.輸出鏈表當(dāng)鏈表的頭指針為NULL時(shí)說明鏈表是空的，不采取行動(dòng)。只有當(dāng)鏈表非空時(shí)才從鏈表頭部開始，輸出一個(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″);}}

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

(1)空表情況；

(2)插在表頭；

(3)插在表中；

(4)插在表尾。

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

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

(3)結(jié)點(diǎn)插在表尾：在上表基礎(chǔ)上插入數(shù)值為16的結(jié)點(diǎn)，如圖8―10所示。插在表尾，意味著在while循環(huán)中以p1=NULL為條件而退出循環(huán)。圖8―10結(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); }

else

printf(″%dnotfound\n″,value);}returnh;}圖8―11刪除表頭結(jié)點(diǎn)我們以圖示來說明刪除結(jié)點(diǎn)的操作。

(1)刪除表頭結(jié)點(diǎn)：刪除數(shù)值為8的結(jié)點(diǎn)，如圖8―11所示。

(2)刪除中間結(jié)點(diǎn)：刪除數(shù)值為12的結(jié)點(diǎn)，如圖8―12所示。

(3)刪除表尾結(jié)點(diǎn)：刪除數(shù)值為16的結(jié)點(diǎn)，如圖8―13所示。圖8―12刪除中間結(jié)點(diǎn)圖8―13刪除表尾結(jié)點(diǎn)【例8―7】＃include<stdlib.h>＃include<stdio.h>structnode{intdata;

structnode*next;};typedefstructnodeNode;main(){Node*head1,*head2;

inti;head1=create();

printf(″Thelistisfollows!\n″); printList(head1);

printf(″Inputainteger:\n″);

scanf(″%d″,&i); while(i!=0) {head2=insert(head2,i);

printf(″Inputainteger:\n″);

scanf(″%d″,&i);}

printf(″theorderedlistasfollows:\n″);printList(head2);

printf(″Inputaintegertodelete:\n″);

scanf(″%d″,&i); while(i!=0) {head2=delete(head2,i);

printf(″Inputaintegertodelete:\n″);

scanf(″%d″,&i); }

printf(″thelistafterdeleteasfollow:\n″); printList(head2); return0;}【例8―8】指出下面程序的運(yùn)行結(jié)果。＃include<stdio.h>＃include<stdlib.h>typedefstructnode{intd;

structnode*next;}t-node;intt=0;voidcreate(t-node**h){

inti;t-node*p;

scanf(″%d″,&i); if(i) {p=(t-node*)malloc(sizeof(t-node)); p->d=i+t; t=i; p->next=NULL; *h=p; create(&((*h)->next));}}main(){t-node*h=NULL,*p;puts(″\nInputinteger,0toend:″);create(&h);p=h;

printf(″Theoutputis:\n\n″);while(p){

printf(″%d″,p->d);p=p->next;}}運(yùn)行輸出：Inputinteger,0toend:2233440Theoutputis:225577該程序中定義了一個(gè)全局變量t，將它賦初值為0，在函數(shù)調(diào)用過程中t的值在不斷地變化。函數(shù)create用以產(chǎn)生鏈表，其參數(shù)是一個(gè)指向結(jié)構(gòu)體的二級(jí)指針，因此在調(diào)用時(shí)實(shí)在參數(shù)必須是一級(jí)指針的地址。主函數(shù)中初始調(diào)用時(shí)一級(jí)指針的內(nèi)容為NULL，以后在每次遞歸調(diào)用時(shí)都要保證當(dāng)時(shí)的一級(jí)指針的內(nèi)容均為NULL,這在函數(shù)中是通過&((*h)->next)來實(shí)現(xiàn)的，因?yàn)樵诤瘮?shù)遞歸調(diào)用前已有p->next=NULL和*h=p這樣的操作，這就使得(*h)->next的值為NULL。如圖8―14所示。圖8-14

8.2.3堆棧堆棧是一種受限制的鏈表，即添加和刪除操作只能從一端進(jìn)行的鏈表，其結(jié)構(gòu)如圖8-15所示。進(jìn)行操作的這一端稱為棧頂。向棧中添加對(duì)象只能加在當(dāng)前的棧頂上，使它成為新的棧頂對(duì)象，這種操作稱為“入棧”或“進(jìn)?！薄D8―15堆棧的結(jié)構(gòu)1.堆棧的類型定義類型定義如下：structstackNode

{intdata;

struct

stackNode*next;}typedef

struct

stackNode

snode;typedef

snode*snodep;

(1)進(jìn)棧函數(shù)push:voidpush(snodep*top,intinfo){snodepnewp;

newp=(snodep)malloc(sizeof(snode));if(newp!=NULL){

newp->data=info;

newp->next=*top;*top=newp; }else

printf(″%dnotinserted,Nomemoryavailable.\n″,info);}把新結(jié)點(diǎn)壓入棧頂?shù)牟僮鞑襟E有下列三步：

①調(diào)用malloc函數(shù)，動(dòng)態(tài)地建立一個(gè)新結(jié)點(diǎn)，把該結(jié)點(diǎn)的內(nèi)存地址賦給newp，把要壓入棧頂?shù)臄?shù)值info賦給newp->data(結(jié)點(diǎn)的數(shù)值域)；

②把棧頂指針(*top)賦給newp->next(結(jié)點(diǎn)的指針域)，從而使新結(jié)點(diǎn)的指針域指向原來的棧頂結(jié)點(diǎn)；

③把newp賦給*top，從而使*top指向新的棧頂結(jié)點(diǎn)。其操作示意圖如圖8―16所示。圖8―16push的操作過程(a)push操作前的棧狀態(tài)；(b)操作過程(2)出棧函數(shù)pop：intpop(snodep*top){

snodeptemp;

int value; temp=*top; value=(*top)->data; top=(*top)->next; free(temp); returnvalue;}圖8―17pop的操作過程(a)pop操作前的棧狀態(tài)；(b)出棧過程【例8―9】＃include<stdio.h>＃include<stdlib.h>structstackNode{intdata;

struct

stackNode*next;};typedef

struct

stackNode

Snode;typedef

Snode*Snodep;voidpush(Snodep*,int);intpop(Snodep*);voidprints(Snodep);voidinstruction(void);main(){snodep

stackp=NULL;

inti,v; instruction();

printf(″?″);

scanf(″%d″,&i); while(i!=3) { switch(i) {

case1：/*進(jìn)棧操作*/

printf(″Enteraninteger\n″);

scanf(″%d″,&v); push(&stackp,v); prints(stackp); break; case2/*出棧操作*/

if(stackp!=NULL)

printf(“poppedvalueis:%d\n″,pop(&stackp)); prints(stackp); break; default:

printf(″Invalidchoice\n″); instruction(); break;}

printf(″?″);

scanf(″%d″,&i);}

printf(″Endofrun\n″); return0;} voidinstruction(void) {printf(″Enterchoice:\n″ ″1.topushavalueintostack.\n″″2.topopavaluefromstack.\n″″3.toendprogram\n″);}voidprints(Snodepp){if(p==NULL)

printf(″Thestackisempty.\n\n″);else{printf(″Thestackis:\n″);while(p!=NULL){printf(″%d->″,p->data);p=p->next;}

printf(″NULL\n\n″);}}運(yùn)行輸出：Enteryourchoice:1.Topushavalueintostack2.Topopavaluefromstack3.Toendprogram?1Enteraninteger5Thestackis:5->NULL?18Thestackis:8->5->NULL?111Thestackis:11->8->5->NULL?2Thepoppedvalueis:11Thestackis:8->5->NULL?4InvalidchoiceEnteryourchoice:1.topushavalueintostack2.topopavaluefromstack3.toendprogram?3Endofrun

8.2.4隊(duì)列隊(duì)列也是一種受限的鏈表，即對(duì)它增加新結(jié)點(diǎn)的操作只能在其尾部進(jìn)行，從中刪除結(jié)點(diǎn)的操作只能在頭部進(jìn)行，因而它是一種“先進(jìn)先出(firstin,firstout,即FIFO)”的數(shù)據(jù)結(jié)構(gòu)。插入和刪除的操作分別稱為“入隊(duì)(enqueue)”和“出隊(duì)(dequeue)”操作。因此對(duì)隊(duì)列的操作需要兩個(gè)指針，一個(gè)指向隊(duì)列頭部(headp)，另一個(gè)指向隊(duì)列尾部(tailp)。圖8―18的隊(duì)列中箭頭的指向就是從頭部指向尾部。圖8―18隊(duì)列的結(jié)構(gòu)1.隊(duì)列的類型定義類型定義如下：struct

queuenode{intdata;

struct

queuenode*next;};typedef

struct

queuenode

Qnode;typedefQnode*Qnodep;

2.入隊(duì)和出隊(duì)函數(shù)的定義入隊(duì)和出隊(duì)操作都涉及對(duì)指針值的改變，因此函數(shù)中采用傳引用調(diào)用方法，函數(shù)的形參定義為二級(jí)指針，實(shí)參為指針的地址。

(1)入隊(duì)函數(shù)enqueue：

函數(shù)形參是兩個(gè)指針的指針以及要插入到隊(duì)列中的值。入隊(duì)操作主要有以下六個(gè)步驟：

①建立一個(gè)新結(jié)點(diǎn)，調(diào)用malloc函數(shù)開辟內(nèi)存空間，把新結(jié)點(diǎn)的地址賦給newp;②把要插入隊(duì)列中的數(shù)值賦給結(jié)點(diǎn)的數(shù)值域newp->data;

③對(duì)新結(jié)點(diǎn)的指針域賦以NULL值(這對(duì)插入的每個(gè)結(jié)點(diǎn)都要進(jìn)行，因?yàn)樾陆Y(jié)點(diǎn)是插在隊(duì)尾，而隊(duì)尾的指針域必須是NULL)；④如果原隊(duì)列為空，則新結(jié)點(diǎn)應(yīng)為隊(duì)列中的唯一結(jié)點(diǎn)，指向隊(duì)列頭的指針也必須指向它，即把newp賦給*headp;⑤如果原隊(duì)列不空，則不涉及隊(duì)列頭指針，只對(duì)隊(duì)尾指針進(jìn)行操作就可以了，即把newp賦給(*tailp)->next,則新結(jié)點(diǎn)就加入隊(duì)尾了。

⑥使隊(duì)尾指針指向新結(jié)點(diǎn)，即把newp賦給*tailp。圖8―19入隊(duì)操作的過程(2)出隊(duì)函數(shù)dequeue：intdequeue(Qnodep*headp,Qnodep*tailp){

intvalue;

Qnodeptemp; value=(*headp)->data; tamp=*headp; *headp=(*headp)->next;/*摘除隊(duì)列頭結(jié)點(diǎn)*/

if(*headp==NULL) *tailp=Null;/*隊(duì)列中無結(jié)點(diǎn)*/

free(temp); returnvalue;}圖8―20出隊(duì)操作的過程

8.2.5二叉樹前面討論的數(shù)據(jù)結(jié)構(gòu)都是線性數(shù)據(jù)結(jié)構(gòu)，它們的共同特點(diǎn)是除第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)外，其他結(jié)點(diǎn)都有且只有一個(gè)前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，如圖8―21(a)所示。在這種數(shù)據(jù)結(jié)構(gòu)中，除第一個(gè)結(jié)點(diǎn)(常稱為樹根)外，其他結(jié)點(diǎn)都有且只有一個(gè)前驅(qū)結(jié)點(diǎn)；所有的結(jié)點(diǎn)(包括根結(jié)點(diǎn))都可以有0個(gè)或多個(gè)后繼結(jié)點(diǎn)。在樹結(jié)構(gòu)中，前驅(qū)結(jié)點(diǎn)又稱為“父結(jié)點(diǎn)”；后繼結(jié)點(diǎn)又稱為“子結(jié)點(diǎn)”；具有同一個(gè)父結(jié)點(diǎn)的結(jié)點(diǎn)稱為“兄弟結(jié)點(diǎn)”；沒有子結(jié)點(diǎn)的結(jié)點(diǎn)稱為“葉結(jié)點(diǎn)”；自然，沒有父結(jié)點(diǎn)的結(jié)點(diǎn)即為“根結(jié)點(diǎn)”。圖8―21樹的結(jié)構(gòu)(a)普通樹；(b)二叉樹圖8―22二叉樹的分解對(duì)二叉樹的處理有三種次序：

(1)先根次序：先處理根結(jié)點(diǎn)，再處理子結(jié)點(diǎn)；

(2)中根次序：先處理根的一棵子樹，接著處理根結(jié)點(diǎn)，最后處理另一棵子樹。

(3)后根次序：先處理兩棵子樹，最后再處理根結(jié)點(diǎn)。圖8―23二叉樹的結(jié)構(gòu)圖8―24二叉查找樹在處理二叉查找樹的程序中所用的主要函數(shù)是插入結(jié)點(diǎn)函數(shù)和遍歷結(jié)點(diǎn)函數(shù)。在插入結(jié)點(diǎn)的函數(shù)中，因?yàn)橐獙?duì)指針進(jìn)行修改，所以形參應(yīng)定義成指針的指針，而實(shí)參是指針的地址。

1.定義二叉查找樹的數(shù)據(jù)類型類型定義如下：

structtreeNode

{struct

treeNode*leftp;

intdata;

struct

treeNode*rightp;};

typedef

struct

treeNodetreeN;2.插入結(jié)點(diǎn)函數(shù)和遍歷結(jié)點(diǎn)函數(shù)的定義(1)插入結(jié)點(diǎn)函數(shù)insert如下：voidinsert(treeN**treep,intvalue){if(*treep==NULL){*treep=(treeN*)malloc(sizeof(treeN));if(*treep!=NULL) {(*treep)->data=value; (*treep)->leftp=NULL; (*treep)->rightp=NULL;}else

printf(″%dnotinserted,Nomemoryavailable\n″,value);}else if(value<(*treep)->data) insert(&((*treep)->leftp),value); elseif(value>(*treep)->data) insert(&((*treep)->rightp),value); else

printf(″dup″);/*標(biāo)記重復(fù)*/}

(2)遍歷結(jié)點(diǎn)的函數(shù)因遍歷的次序不同而有三個(gè)，這三個(gè)函數(shù)的構(gòu)成語句都完全一樣，差別只在于語句的次序上。下面以中序遍歷為例說明函數(shù)的構(gòu)成：

voidinorder(treeN*treep){if(treep!=NULL){inorder(treep->leftp);/*遍歷左子樹*/

printf(″%3d″,treep->data);/*輸出根結(jié)點(diǎn)*/

inorder(treep->rightp);/*遍歷右子樹*/}}【例8―10】＃include<stdio.h>＃include<stdlib.h>＃include<time.h>StructtreeNode{struct

treeNode*leftp;

intdata;

struct

treeNode*rightp;}；typedef

struct

treeNodetreeN;voidinsert(treeN**,int);voidinorder(treeN*);voidpreorder(treeN*);voidpostorder(treeN*);main(){

inti,item;

treeN*rootp=NULL;

srand(time(NULL));

printf(″Thenumberbeingplacedinthetreeare:\n″); for(i=1;i<=10;i++) {item=10+rand()%41; printf(″%3d″,item);

insert(&rootp,item);}

printf(″\n\nThepreordertraversalis:\n″); preorder(rootp);

printf(″\n\nThe

inordertraversalis:\n″);

inorder(rootp);

printf(″\n\nThe

postordertraversalis:\n″);

postorder(rootp); return0;}voidpostorder(treeN*treep){if(treep!=NULL) {postorder(treep->leftp);

postorder(treep->rightp); printf(″%3d″,treep->data); }}voidpreorder(treeN*treep){ if(treep!=NULL) {printf(″%3d″,treep->data); preorder(treep->leftp);

preorder(treep->right);}}voidinorder(treeN*treep){if(treep!=NULL) {inorder(treep->leftp); printf(″%3d″,treep->data);

inorder(treep->rightp);}}8.3共用體程序中的變量有兩種情況：一種是變量之間互不相關(guān)，都有自己的名字和存儲(chǔ)空間；另一種是變量之間是相關(guān)的，它們雖然有各自的名字，但共用同一段內(nèi)存空間，讓這段空間輪流地為它們服務(wù)，這樣就可以減少空間的浪費(fèi)。讓這些變量共用同一內(nèi)存空間的方法是把它們組織成共用體。共用體是一種新的數(shù)據(jù)類型，它的定義與結(jié)構(gòu)體的定義相似:

union<共同體名>{成員列表}；例如：unionnumber{

intx; floaty; charc;};圖8―25共用體對(duì)內(nèi)存空間的占用在這個(gè)共用體類型中定義了三個(gè)分量，它們的類型各不相同，但都占用同一內(nèi)存空間，由于各個(gè)分量類型不同，所以這段空間應(yīng)足夠大，以便能放下最大的分量，所以這個(gè)共用體要占用4個(gè)字節(jié)空間，因?yàn)槠渲械姆至縴是float類型，是最長的類型，占4字節(jié)，如圖8―25所示。【例8―11】＃include<stdio.h>main(){ unionnumber {inti; longl; }a; a.i=-32768;

printf(″int:%d,long:%ld\n″,a.i,a.l); a.l=65536;

printf(″int:%d,long:%ld\n″,a.i.,a.l); return0;}運(yùn)行輸出：

int:-32768,long:32768int:0,long:65536

共用體類型和結(jié)構(gòu)體類型可以互相嵌套，即可以互為對(duì)方分量的類型。一般的使用是在結(jié)構(gòu)體中設(shè)一個(gè)類型標(biāo)志分量，由該標(biāo)志確定當(dāng)前對(duì)共用體中哪個(gè)分量進(jìn)行處理。

【例8―12】某單位招聘博士人員，國內(nèi)博士應(yīng)注明取得博士學(xué)位的年份，國外博士要注明取得博士學(xué)位的國家。＃include<stdio.h>main(){structdoctor {charname［15］;

intage;

inttag; union {intdate; charcountry［15］; }catalogue; }person;

printf(″inputname,age,tag:\n″);

scanf(″%s%d%d″,,&person.age,&person.tag); if(person.tag==1) {puts(″inputdate-year:″);

scanf(″%d″,&person.calalogue.date); } if(person.tag==2) {puts(″Inputcountryname:\n″);

scanf(″%s″,person.catalogue.country); }

printf(″\n%s,%5d，″,,person.age); if(person.tag==1) printf(″%10d\n″,person.catalogue.date); if(person.tag==2)

printf(″%s\n″,person.catalogue.country); return0；}運(yùn)行輸出：Inputname,age,tag:Zhangdong351Inputdate-year:2000Zhangdong,35,2000再運(yùn)行：Inputname,age,tag:Zhaotian322Inputcountryname:Francezhaotian，32,France注意：在嵌套的定義中，共用體類型名可以不寫，但其分量名catalogue必須寫，因?qū)ζ浞至窟M(jìn)行引用時(shí)要用到這個(gè)分量；只有對(duì)最底層的分量才能進(jìn)行輸入/輸出操作，如person.catalogue.date,person.catalogue.country等，它們相當(dāng)于兩個(gè)變量，其類型分別是int和char*的類型，因此輸入/輸出的控制字符應(yīng)和它們相一致。標(biāo)志tag取不同值時(shí)進(jìn)行不同的操作，在程序中應(yīng)予以提示說明，不然在輸入時(shí)會(huì)造成困惑，甚至?xí)斎氩徽_的數(shù)值。8.4位段為了節(jié)約內(nèi)存，C語言允許以位而不是以字節(jié)為單位來定義變量的大小。這樣的變量一般用來定義結(jié)構(gòu)體的成員。這些用存儲(chǔ)位表示的變量稱為“位段”。它們定義的一般形式是：

{unsigned|int}<位段名>：<位數(shù)>花括號(hào)中的內(nèi)容是必須的，而“|”兩側(cè)的內(nèi)容任選其一。<位段名>是標(biāo)識(shí)符，<位數(shù)>指二進(jìn)制位。如

unsigneda:4；

則說明位段a占4位。位數(shù)決定了取值范圍。4位二進(jìn)制位的取值范圍是0到15，超過15則a就容納不下了。若位段用int類型定義，則必須留出最高位為符號(hào)位，如

intb:4

則定義b的數(shù)值位只有3位，其所能表示的數(shù)的范圍是-8到7。對(duì)于只有1位的位段，必須定義成unsigned類型，如structex{ unsigneda:12; unsignedb:3; unsignedc:1;

intd:4;}對(duì)于不指定名字的位段表示不用它的空間，如structexam{ unsigneda:3;

unsigned:4; unsignedb:8;};

【例8―13】設(shè)計(jì)一個(gè)打印撲克牌的程序。編程思路：牌的面值(face)共有13種(從Ace到King)，可用4位二進(jìn)制數(shù)表示(4位能表示0到15之間的值)；牌在花色(suit)有4種(方塊Diamonds,紅桃Hearts，梅花Clubs,黑桃Spades),可用2位二進(jìn)制數(shù)表示(2位二進(jìn)制數(shù)可以有4種不同的狀態(tài))；牌的顏色(color)有兩種(紅、黑)，用1位即可。先定義用位段表示的反映牌的特性的結(jié)構(gòu)體類型：struct

bcard{ unsignedface:4; unsignedsuit:2; unsignedcolor:1;};typedef

struct

bcardcard;然后建立有52個(gè)card元素的數(shù)組deck。定義一個(gè)洗牌函數(shù)fillDeck,其功能是在數(shù)組deck中插入52張牌。函數(shù)deal把52張牌打印出來。程序如下：＃include<stdio.h>

struct

bcard

{unsignedface:4;unsignedsuit:2;unsignedcolor:1;};typedefstructbcardcard;voidfillDeck(card*);voiddeal(card*);main(){carddeck［52］;

printf(″\n\n″);

fillDeck(deck); deal(deck); return0;}voidfillDeck(card*wDeck){inti; for(i=0;i<=51;i++) {wDeck［i］.face=i%13;

wDeck［i］.suit=i/13;

wDeck［i］.color=i/26;}}voiddeal(card*wDeck){intk1,k2;for(