C語(yǔ)言程序設(shè)計(jì)-09結(jié)構(gòu)體

第9章結(jié)構(gòu)體

9.1結(jié)構(gòu)體類(lèi)型的定義

9.2結(jié)構(gòu)體變量

9.3結(jié)構(gòu)體數(shù)組

9.4結(jié)構(gòu)體類(lèi)型的指針

9.5結(jié)構(gòu)體與函數(shù)

9.6鏈表

9.7結(jié)構(gòu)體應(yīng)用舉例

本章小結(jié)

9.1結(jié)構(gòu)體類(lèi)型的定義

結(jié)構(gòu)體類(lèi)型的定義格式為：

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

{

成員說(shuō)明列表

};

其中，花括號(hào)內(nèi)的內(nèi)容是該結(jié)構(gòu)體類(lèi)型的成員說(shuō)明。每個(gè)成員說(shuō)明的形式為：

類(lèi)型符成員名;

9.2結(jié)構(gòu)體變量

9.2.1結(jié)構(gòu)體變量的定義

要定義一個(gè)結(jié)構(gòu)體類(lèi)型的變量，可以采取以下3種方法。

（1）先定義結(jié)構(gòu)體類(lèi)型，再定義體類(lèi)型變量。

（2）在定義類(lèi)型的同時(shí)定義變量。

它的作用與前面定義的相同。即定義了兩個(gè)STRUCTSTUDENT類(lèi)型的變量STUDENT1和STUDENT2。這種定義方法的一般格式為：

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

{

成員說(shuō)明列表

}變量名列表;

（3）直接定義結(jié)構(gòu)體類(lèi)型變量。

其一般格式為：

STRUCT

{

成員說(shuō)明列表

}變量名列表;

即在結(jié)構(gòu)體定義時(shí)不出現(xiàn)結(jié)構(gòu)體類(lèi)型名。這種形式雖然簡(jiǎn)單，但不能在再需要使用時(shí)，使用所定義的結(jié)構(gòu)體類(lèi)型。關(guān)于結(jié)構(gòu)體類(lèi)型，有幾點(diǎn)需要說(shuō)明：

（1）類(lèi)型與變量是不同的概念，不要混同。對(duì)結(jié)構(gòu)體變量來(lái)說(shuō)，在定義時(shí)一般先定義一個(gè)結(jié)構(gòu)體類(lèi)型，然后定義變量為該類(lèi)型。只能對(duì)變量賦值、存取或運(yùn)算，而不能對(duì)一個(gè)類(lèi)型賦值、存取或運(yùn)算。在編譯時(shí)，對(duì)類(lèi)型是不分配存儲(chǔ)空間的，只對(duì)變量分配存儲(chǔ)空間。

（2）對(duì)結(jié)構(gòu)體中的成員，可以單獨(dú)使用，它的作用與地位相當(dāng)于普通變量。

（3）成員也可以是一個(gè)結(jié)構(gòu)體變量。

（4）成員名可以與程序中的變量名相同，兩者代表不同的對(duì)象。

9.2.2結(jié)構(gòu)體變量的使用

由結(jié)構(gòu)體變量名引用其成員的標(biāo)記形式為：

結(jié)構(gòu)體變量名.成員名

由指向結(jié)構(gòu)體的指針變量引用結(jié)構(gòu)體成員的標(biāo)記形式為：

指針變量名->成員名9.2.3結(jié)構(gòu)體變量的初始化

結(jié)構(gòu)體變量和其他變量一樣，可以在變量定義的同時(shí)進(jìn)行初始化。

1．對(duì)外部存儲(chǔ)類(lèi)型的結(jié)構(gòu)體變量進(jìn)行初始化

【例9.1】分析下列程序的輸出結(jié)果。

2．對(duì)靜態(tài)存儲(chǔ)類(lèi)型的結(jié)構(gòu)體變量進(jìn)行初始化

9.2.4結(jié)構(gòu)體變量的輸入和輸出

C語(yǔ)言不允許把一個(gè)結(jié)構(gòu)體變量作為一個(gè)整體進(jìn)行輸入或輸出，而應(yīng)按成員變量輸入或輸出。例如，若有一個(gè)結(jié)構(gòu)體變量：

STRUCT

{

CHARNAME[15];

CHARADDR[20];

LONGNUM;

}STUD={“WANGDAWEI”,“125BEIJINGROAD”,3021118};

變量STUD在內(nèi)存中存儲(chǔ)情況如圖9-2所示，是按成員變量存放的。由于變量STUD包含兩個(gè)字符串?dāng)?shù)據(jù)和一個(gè)長(zhǎng)整型數(shù)據(jù)，因此輸出STUD變量，應(yīng)該使用如下方式：

PRINTF(“%S,%S,%LD\N”,STUD.NAME,STUD.ADDR,STUD.NUM);

輸入STUD變量的各成員值，則用：

SCANF(“%S%S%LD”,STUD.NAME,STUD.ADDR,&STUD.NUM);

由于成員項(xiàng)NAME和ADDR是字符數(shù)組，按%S字符串格式輸入，故不要寫(xiě)成&STUD.NAME和&STUD.ADDR，而NUM成員是LONG型，故應(yīng)當(dāng)用&STUD.NUM。

當(dāng)然也可以用GETS函數(shù)和PUTS函數(shù)輸入和輸出一個(gè)結(jié)構(gòu)體變量中的字符數(shù)組成員。例如：

GETS(STUD.NAME);

PUTS(STUD.NAME);

GETS函數(shù)輸入一個(gè)字符串給STUD.NAME，PUTS函數(shù)輸出STUD.NAME數(shù)組中的字符串。

9.3結(jié)構(gòu)體數(shù)組

9.3.1結(jié)構(gòu)體數(shù)組的定義

與定義結(jié)構(gòu)體變量的方法一樣，在結(jié)構(gòu)體變量名之后指定元素個(gè)數(shù)，就能定義結(jié)構(gòu)體數(shù)組。結(jié)構(gòu)體數(shù)組定義的一般格式為：

結(jié)構(gòu)體類(lèi)型名數(shù)組名[常量表達(dá)式];

如同元素為標(biāo)準(zhǔn)數(shù)據(jù)類(lèi)型的數(shù)組一樣，結(jié)構(gòu)體數(shù)組各元素在內(nèi)存中也按順序存放，也可初始化，對(duì)結(jié)構(gòu)體數(shù)組元素的訪(fǎng)問(wèn)也要利用元素的下標(biāo)。訪(fǎng)問(wèn)結(jié)構(gòu)體數(shù)組元素的成員的標(biāo)記方法為：

結(jié)構(gòu)體數(shù)組名[元素下標(biāo)].結(jié)構(gòu)體成員名

9.3.2結(jié)構(gòu)體數(shù)組的初始化

在對(duì)結(jié)構(gòu)體數(shù)組初始化時(shí)，要將每個(gè)元素的數(shù)據(jù)分別用花括弧括起來(lái)，一般格式是：

結(jié)構(gòu)類(lèi)型數(shù)組名[常量表達(dá)式]={初始化表};

9.3.3結(jié)構(gòu)體數(shù)組的使用

一個(gè)結(jié)構(gòu)體數(shù)組的元素相當(dāng)于一個(gè)結(jié)構(gòu)體變量，引用結(jié)構(gòu)體數(shù)組元素有如下規(guī)則。

（1）引用某一元素的一個(gè)成員。

（2）可以將一個(gè)結(jié)構(gòu)體數(shù)組元素賦給同一結(jié)構(gòu)體類(lèi)型數(shù)組中的另一個(gè)元素，或賦給同一類(lèi)型的變量。

（3）不能把結(jié)構(gòu)體數(shù)組元素作為一個(gè)整體直接進(jìn)行輸入或輸出，只能以單個(gè)成員對(duì)象進(jìn)行輸入或輸出。

【例9.2】結(jié)構(gòu)體數(shù)組的應(yīng)用。

9.4結(jié)構(gòu)體類(lèi)型的指針

9.4.1指向結(jié)構(gòu)體變量的指針

指向結(jié)構(gòu)體的指針變量定義的一般格式為：

STRUCT類(lèi)型名*指針變量名;

通過(guò)指向結(jié)構(gòu)體的指針變量引用結(jié)構(gòu)體成員的方法是：

指針變量->結(jié)構(gòu)體成員名

“*指針變量”表示指針變量所指對(duì)象，所以通過(guò)指向結(jié)構(gòu)體的指針變量引用結(jié)構(gòu)體成員也可寫(xiě)成以下形式：

(*指針變量).結(jié)構(gòu)體成員名

【例9.3】寫(xiě)出下列程序的執(zhí)行結(jié)果。

9.4.2指向結(jié)構(gòu)體數(shù)組元素的指針

一個(gè)指針變量可以指向一個(gè)結(jié)構(gòu)體數(shù)組元素，也就是將該結(jié)構(gòu)體數(shù)組的數(shù)組元素地址賦給此指針變量。例如：

STRUCT

{

INTA;

FLOATB;

}ARR[3],*P;

P=ARR;

此時(shí)使P指向ARR數(shù)組的第一個(gè)元素，

“P=ARR;”等價(jià)于“P=&ARR[0];”。

若執(zhí)行“P++;”則此時(shí)指針變量P

此時(shí)指向ARR[1]，指針指向關(guān)系如

圖9-3所示。

【例9.4】輸入3個(gè)學(xué)生的信息并輸出。

9.5結(jié)構(gòu)體與函數(shù)

9.5.1結(jié)構(gòu)體變量作為函數(shù)參數(shù)

舊的C標(biāo)準(zhǔn)不允許用結(jié)構(gòu)體變量作為函數(shù)參數(shù)，只允許指向結(jié)構(gòu)體變量的指針作為函數(shù)參數(shù)，即傳遞結(jié)構(gòu)體變量的首地址。新的標(biāo)準(zhǔn)以及許多C語(yǔ)言編譯系統(tǒng)都允許用結(jié)構(gòu)體變量作為函數(shù)參數(shù)，即直接將實(shí)參結(jié)構(gòu)體變量的各個(gè)成員的值全部傳遞給形參的結(jié)構(gòu)體變量。當(dāng)然，實(shí)參和形參的結(jié)構(gòu)體變量類(lèi)型應(yīng)當(dāng)完全一致。

【例9.5】將例9.4中的輸出的功能用函數(shù)實(shí)現(xiàn)。

9.5.2指向結(jié)構(gòu)體變量的指針作為函數(shù)參數(shù)

用結(jié)構(gòu)體變量作為函數(shù)參數(shù)，這是ANSIC新標(biāo)準(zhǔn)的擴(kuò)充功能。在過(guò)去的C版本中不能這樣使用，而是通過(guò)指針來(lái)傳遞結(jié)構(gòu)體變量的地址給形參，再通過(guò)形參指針變量引用結(jié)構(gòu)體變量中成員的值。

【例9.6】有一結(jié)構(gòu)體變量STU，內(nèi)含學(xué)生學(xué)號(hào)、姓名和3門(mén)課的成績(jī)。要求在MAIN函數(shù)中給變量賦值，在另一函數(shù)PRINT中將它們輸出。

9.5.3返回結(jié)構(gòu)體類(lèi)型值的函數(shù)

函數(shù)的返回值可以是結(jié)構(gòu)體類(lèi)型。例如，定義了結(jié)構(gòu)體數(shù)組：

STRUCTSTUDENTSTUD[100];

數(shù)據(jù)輸入可由如下形式的語(yǔ)句實(shí)現(xiàn)：

FOR(I=0;I<100;I++)

STUD[I]=INPUT();

函數(shù)INPUT的功能是輸入一個(gè)結(jié)構(gòu)體數(shù)據(jù)，并將輸入結(jié)構(gòu)體數(shù)據(jù)作為返回值，返回給第I個(gè)學(xué)生記錄，實(shí)現(xiàn)第I個(gè)學(xué)生的數(shù)據(jù)輸入。

函數(shù)INPUT定義如下：

STRUCTSTUDENTINPUT()

{

INTI;

STRUCTSTUDENTSTUD;

SCANF(“%LD”,&STUD.NO);

/*輸入學(xué)號(hào)*/

GETS(STUD.NAME);

/*輸入學(xué)生姓名*/

FOR(I=0;I<3;I++)

/*輸入學(xué)生的3門(mén)成績(jī)*/

SCANF(“%F”,&STUD.SCORE[I]);

RETURNSTUD; /*返回結(jié)構(gòu)體數(shù)據(jù)*/

}

9.6鏈表

9.6.1鏈表概述

鏈表是最簡(jiǎn)單也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。它是對(duì)動(dòng)態(tài)獲得的內(nèi)存進(jìn)行組織的一種結(jié)構(gòu)。如圖9-4所示為最簡(jiǎn)單的一種鏈表（單向鏈表）結(jié)構(gòu)。鏈表有一個(gè)頭指針變量，圖中以HEAD表示，它存放一個(gè)地址。該地址指向一個(gè)鏈表元素。鏈表中每一個(gè)元素稱(chēng)為結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)都包括兩部分：一是用戶(hù)需要用的實(shí)際數(shù)據(jù)，二是下一個(gè)結(jié)點(diǎn)的地址（指針）?？梢钥闯?，HEAD指向第一個(gè)結(jié)點(diǎn)，第一個(gè)結(jié)點(diǎn)又指向第二個(gè)結(jié)點(diǎn)，一直到最后一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)不再指向其他結(jié)點(diǎn)，它稱(chēng)為表尾，它的地址部分放一個(gè)NULL（表示“空地址”），鏈表到此結(jié)束。

圖9-4鏈表結(jié)構(gòu)示意圖

由圖9-4可見(jiàn)，一個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)位置由結(jié)點(diǎn)所包含的指針成員所指，鏈表中各結(jié)點(diǎn)在內(nèi)存中的存放位置是任意的。如果尋找鏈表中的某一個(gè)結(jié)點(diǎn)，必須從鏈表頭指針?biāo)傅牡谝粋€(gè)結(jié)點(diǎn)開(kāi)始，順序查找。另外，圖9-4所示的鏈表結(jié)構(gòu)是單向的，即每個(gè)結(jié)點(diǎn)只知道它的后繼結(jié)點(diǎn)位置，而不能知道它的前驅(qū)結(jié)點(diǎn)。在某些應(yīng)用中，要求鏈表的每個(gè)結(jié)點(diǎn)都能方便地知道它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)，這種鏈表的表示應(yīng)設(shè)有兩個(gè)指針成員，分別指向它的前驅(qū)和后繼結(jié)點(diǎn)，這種鏈表稱(chēng)為雙向鏈表。為適應(yīng)不同問(wèn)題的特定要求，鏈表結(jié)構(gòu)也有多種變形。

9.6.2鏈表的基本操作

鏈表的基本操作包括建立鏈表，鏈表的插入、刪除、輸出和查找等。鏈表結(jié)點(diǎn)的存儲(chǔ)空間是程序根據(jù)需要向系統(tǒng)動(dòng)態(tài)申請(qǐng)的，這時(shí)要用到8.7節(jié)中介紹的動(dòng)態(tài)內(nèi)存管理函數(shù)。

1．建立鏈表

如圖9-5所示為用插表頭方法建立鏈表，如圖9-6所示為用鏈表尾方法建立鏈表。

圖9-5用插表頭方法建立鏈表

插表頭算法抽象描述如下：

（1）HEAD=NULL; /*表頭指向空，表示鏈表為空*/

（2）產(chǎn)生新結(jié)點(diǎn)，地址賦給指針變量P。

（3）P->NEXT=HEAD;HEAD=P; /*插表頭操作*/

（4）循環(huán)執(zhí)行（2），繼續(xù)建立新結(jié)點(diǎn)。

圖9-6用鏈表尾方法建立鏈表

鏈表尾算法抽象描述如下：

（1）HEAD=LAST=NULL;

/*表頭指向空，表示鏈表為空,LAST是表尾指針*/

（2）產(chǎn)生新結(jié)點(diǎn)，地址賦給指針變量P，P->NEXT=NULL; /*新結(jié)點(diǎn)作為表尾*/

（3）如果HEAD為NULL，則

HEAD=P; /*新結(jié)點(diǎn)作為表頭，這時(shí)鏈表只有一個(gè)結(jié)點(diǎn)*/

否則

LAST->NEXT=P;

/*鏈表操作*/

（4）LAST=P;

/*表尾指針指向新結(jié)點(diǎn)*/

（5）循環(huán)執(zhí)行（2），繼續(xù)建立新結(jié)點(diǎn)。

【例9.7】編寫(xiě)一個(gè)函數(shù)，建立一個(gè)有N名學(xué)生數(shù)據(jù)的單向鏈表。2．鏈表的插入操作

鏈表的插入操作是要將一個(gè)結(jié)點(diǎn)插入到一個(gè)已有鏈表中的某個(gè)位置。該操作可以分兩步完成，先找到插入點(diǎn)，再插入結(jié)點(diǎn)。操作步驟如圖9-8所示。圖9-8鏈表的插入操作

鏈表的插入操作算法描述如下：

指針HEAD指向鏈表的頭結(jié)點(diǎn)，P0指向待插入的結(jié)點(diǎn)，P1和P2一前一后指示插入點(diǎn)。

（1）最初P1=HEAD;。

（2）移動(dòng)指針P2=P1，P1=P1->NEXT，直到找到插入點(diǎn)。

（3）插入結(jié)點(diǎn)P0->NEXT=P1，P2->NEXT=P0。

仍然以例9.7建立的有N名學(xué)生數(shù)據(jù)的單向鏈表為例，設(shè)已有的鏈表各結(jié)點(diǎn)是按學(xué)號(hào)由小到大順序排列的。

用指針變量P0指向待插入的結(jié)點(diǎn)，最初P1=HEAD，找插入點(diǎn)的操作如下：

當(dāng)P0->NUM>P1->NUM且P1->NEXT!=NULL

{

P2=P1;

P1=P1->NEXT;

}

插入結(jié)點(diǎn)操作如下：

IFP1==HEAD則

結(jié)點(diǎn)作為表頭插入

ELSEIFP1->NEXT==NULL則

結(jié)點(diǎn)作為表尾插入

ELSE

插入在P2所指結(jié)點(diǎn)之后3．鏈表的刪除操作

從一個(gè)鏈表中刪去一個(gè)結(jié)點(diǎn)，只要改變鏈接關(guān)系即可，即修改結(jié)點(diǎn)指針成員的值，如圖9-9所示。圖9-9刪除結(jié)點(diǎn)操作

刪除結(jié)點(diǎn)算法描述如下：

用指針P1指向待刪結(jié)點(diǎn)，P2指向待刪結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)。

（1）P1=HEAD，從第一個(gè)結(jié)點(diǎn)開(kāi)始檢查。

（2）當(dāng)P1指向的結(jié)點(diǎn)不是滿(mǎn)足刪除條件的結(jié)點(diǎn)且沒(méi)有到表尾時(shí)，P2=P1，P1=P1->NEXT（移動(dòng)指針P1，繼續(xù)查找）。

（3）如果找到了刪除結(jié)點(diǎn)P1!=NULL，則要分兩種情形：

如果P1==HEAD（刪除的是頭結(jié)點(diǎn)）則

HEAD=HEAD->NEXT;

/*刪除頭結(jié)點(diǎn)*/

否則

P2->NEXT=P1->NEXT;

/*刪除P1指向的結(jié)點(diǎn)*/

（4）FREE(PL)，釋放被刪除結(jié)點(diǎn)的內(nèi)存空間。

4．鏈表的輸出操作

要依次輸出鏈表中各結(jié)點(diǎn)的數(shù)據(jù)比較容易處理。首先要知道鏈表頭結(jié)點(diǎn)的地址，也就是要知道HEAD的值，然后設(shè)一個(gè)指針變量P，先指向第一個(gè)結(jié)點(diǎn)，輸出P所指的結(jié)點(diǎn)，然后使P后移一個(gè)結(jié)點(diǎn)，再輸出。直到鏈表的尾結(jié)點(diǎn)。

5．鏈表的查找操作

鏈表的查找是指在已知鏈表中查找值為某指定值的結(jié)點(diǎn)。鏈表的查找過(guò)程是從鏈表的頭指針?biāo)傅牡谝粋€(gè)結(jié)點(diǎn)出發(fā)，順序查找。若發(fā)現(xiàn)有指定值的結(jié)點(diǎn)，以指向該結(jié)點(diǎn)的指針值為查找結(jié)果；如果查找至鏈表結(jié)尾，未發(fā)現(xiàn)指定值的結(jié)點(diǎn)，查找結(jié)果為NULL，表示鏈表中沒(méi)有指定值的結(jié)點(diǎn)。為簡(jiǎn)單起見(jiàn)，以指定的學(xué)號(hào)作為查找結(jié)點(diǎn)的關(guān)鍵字。

9.7結(jié)構(gòu)體應(yīng)用舉例

【例9.8】用結(jié)構(gòu)體類(lèi)型描述復(fù)數(shù)，編一程序，計(jì)算并輸出復(fù)數(shù)四則運(yùn)算的結(jié)果，要求復(fù)數(shù)加、減、乘和除分別用4個(gè)函數(shù)實(shí)現(xiàn)。

【例9.9】設(shè)計(jì)一個(gè)洗牌和發(fā)牌的程序，用H代表紅桃，D代表方片，C代表梅花，S代表黑桃，用1～13代表每一種花色的面值。

【例9.10】結(jié)構(gòu)體數(shù)組排序。

【例9.11】鏈表的結(jié)點(diǎn)信息包括學(xué)生學(xué)號(hào)、成績(jī)，結(jié)點(diǎn)定義如下：

STRUCTPLIST

{

INTNO;

FLOATSCORE;

STRUCTPLIST*NEXT;

};

設(shè)已經(jīng)建立兩個(gè)具有上述結(jié)構(gòu)的鏈表，且兩個(gè)鏈表都是按學(xué)號(hào)升序排列的，要求編寫(xiě)一個(gè)函數(shù)，將兩個(gè)鏈表合并，仍按學(xué)號(hào)升序排列。

編寫(xiě)程序時(shí)要考慮以下幾點(diǎn)：

（1）函數(shù)應(yīng)有兩個(gè)鏈表指針形參P1、P2，它們指向各自的表頭。

（2）最初新鏈表的頭指針HEAD=NULL，新鏈表的當(dāng)前結(jié)點(diǎn)指針P=NULL。

（3）產(chǎn)生新鏈表的頭結(jié)點(diǎn)。

IF(P1->NO<P2->NO)/*比較兩個(gè)鏈表中當(dāng)前結(jié)點(diǎn)的學(xué)號(hào)*/

{HEAD=P=P1;P1=P1->NEXT;}

ELSE

{HEAD=P=P2;P2=P2->NEXT;}

（4）當(dāng)兩個(gè)鏈表的指針均沒(méi)指向表尾，則選擇兩個(gè)鏈表中的結(jié)點(diǎn)并入到新鏈表。

IF(PL->NO<P2->NO)

將P1指向的結(jié)點(diǎn)接到新鏈表的表尾：P->NEXT=P1;

并移動(dòng)P和P1;

ELSE

將P2指示的結(jié)點(diǎn)接到新鏈表的表尾：P->NEXT=P2;

并移動(dòng)P和P2;

（5）當(dāng)某一個(gè)鏈表已到表尾，則另一個(gè)鏈表的剩余部分直接鏈接到新鏈表的表尾。

IF(P1!=NULL)

P->NEXT=P1;

ELSE

P->NEXT=P2;

本章小結(jié)

1．結(jié)構(gòu)體是一種構(gòu)造類(lèi)型，它由若干成員組成。每一個(gè)成員既可以是一個(gè)基本數(shù)據(jù)類(lèi)型也可以是