C++語言教程：第七章 結(jié)構(gòu)與聯(lián)合

第七章:結(jié)構(gòu)與聯(lián)合結(jié)構(gòu)類型定義和結(jié)構(gòu)變量說明在實際問題中，一組數(shù)據(jù)往往具有不同的數(shù)據(jù)類型。例如，在學(xué)生登記表中，姓名應(yīng)為字符型；學(xué)號可為整型或字符型；年齡應(yīng)為整型；性別應(yīng)為字符型；成績可為整型或?qū)嵭?。顯然不能用一個數(shù)組來存放這一組數(shù)據(jù)。因為數(shù)組中各元素的類型和長度都必須一致，以便于編譯系統(tǒng)處理。為了解決這個問題，Ｃ語言中給出了另一種構(gòu)造數(shù)據(jù)類型——“結(jié)構(gòu)”。它相當(dāng)于其它高級語言中的記錄?！敖Y(jié)構(gòu)”是一種構(gòu)造類型，它是由若干“成員”組成的。每一個成員可以是一個基本數(shù)據(jù)類型或者又是一個構(gòu)造類型。結(jié)構(gòu)既是一種“構(gòu)造”而成的數(shù)據(jù)類型，那么在說明和使用之前必須先定義它，也就是構(gòu)造它。如同在說明和調(diào)用函數(shù)之前要先定義函數(shù)一樣。一、結(jié)構(gòu)的定義定義一個結(jié)構(gòu)的一般形式為：struct結(jié)構(gòu)名{成員表列};成員表由若干個成員組成，每個成員都是該結(jié)構(gòu)的一個組成部分。對每個成員也必須作類型說明，其形式為：類型說明符成員名;成員名的命名應(yīng)符合標(biāo)識符的書寫規(guī)定。例如：structstu{intnum;charname[20];charsex;floatscore;};在這個結(jié)構(gòu)定義中，結(jié)構(gòu)名為stu，該結(jié)構(gòu)由4個成員組成。第一個成員為num，整型變量；第二個成員為name，字符數(shù)組；第三個成員為sex，字符變量；第四個成員為score，實型變量。應(yīng)注意在括號后的分號是不可少的。結(jié)構(gòu)定義之后，即可進行變量說明。凡說明為結(jié)構(gòu)stu的變量都由上述4個成員組成。由此可見，結(jié)構(gòu)是一種復(fù)雜的數(shù)據(jù)類型，是數(shù)目固定，類型不同的若干有序變量的集合。二、結(jié)構(gòu)類型變量的說明說明結(jié)構(gòu)變量有以下三種方法。以上面定義的stu為例來加以說明。1.先定義結(jié)構(gòu)，再說明結(jié)構(gòu)變量。如：structstu{intnum;charname[20];charsex;floatscore;};structstuboy1,boy2;說明了兩個變量boy1和boy2為stu結(jié)構(gòu)類型。也可以用宏定義使一個符號常量來表示一個結(jié)構(gòu)類型，例如：#defineSTUstructstuSTU{intnum;charname[20];charsex;floatscore;};STUboy1,boy2;2.在定義結(jié)構(gòu)類型的同時說明結(jié)構(gòu)變量。例如：structstu{intnum;charname[20];charsex;floatscore;}boy1,boy2;3.直接說明結(jié)構(gòu)變量。例如：struct{intnum;charname[20];charsex;floatscore;}boy1,boy2;第三種方法與第二種方法的區(qū)別在于第三種方法中省去了結(jié)構(gòu)名，而直接給出結(jié)構(gòu)變量。三種方法中說明的boy1,boy2變量都具有圖7.1所示的結(jié)構(gòu)。說明了boy1,boy2變量為stu類型后，即可向這兩個變量中的各個成員賦值。在上述stu結(jié)構(gòu)定義中，所有的成員都是基本數(shù)據(jù)類型或數(shù)組類型。成員也可以又是一個結(jié)構(gòu)，即構(gòu)成了嵌套的結(jié)構(gòu)。例如，圖7.2給出了另一個數(shù)據(jù)結(jié)構(gòu)。按圖7.2可給出以下結(jié)構(gòu)定義：structdate{intmonth;intday;intyear;}struct{intnum;charname[20];charsex;structdatebirthday;floatscore;}boy1,boy2;首先定義一個結(jié)構(gòu)date，由month(月)、day(日)、year(年)三個成員組成。在定義并說明變量boy1和boy2時，其中的成員birthday被說明為data結(jié)構(gòu)類型。成員名可與程序中其它變量同名，互不干擾。結(jié)構(gòu)變量成員的表示方法在程序中使用結(jié)構(gòu)變量時，往往不把它作為一個整體來使用。在ANSIC中除了允許具有相同類型的結(jié)構(gòu)變量相互賦值以外，一般對結(jié)構(gòu)變量的使用，包括賦值、輸入、輸出、運算等都是通過結(jié)構(gòu)變量的成員來實現(xiàn)的。表示結(jié)構(gòu)變量成員的一般形式是：結(jié)構(gòu)變量名.成員名例如：boy1.num即第一個人的學(xué)號boy2.sex即第二個人的性別如果成員本身又是一個結(jié)構(gòu)則必須逐級找到最低級的成員才能使用。例如：boy1.birthday.month即第一個人出生的月份成員可以在程序中單獨使用，與普通變量完全相同。結(jié)構(gòu)變量的賦值前面已經(jīng)介紹，結(jié)構(gòu)變量的賦值就是給各成員賦值。可用輸入語句或賦值語句來完成。[例7.1]給結(jié)構(gòu)變量賦值并輸出其值。main(){structstu{intnum;char*name;charsex;floatscore;}boy1,boy2;boy1.num=102;="Zhangping";printf("inputsexandscore\n");scanf("%c%f",&boy1.sex,&boy1.score);boy2=boy1;printf("Number=%d\nName=%s\n",boy2.num,);printf("Sex=%c\nScore=%f\n",boy2.sex,boy2.score);}structstu{intnum;char*name;charsex;floatscore;}boy1,boy2;boy1.num=102;="Zhangping";printf("inputsexandscore\n");scanf("%c%f",&boy1.sex,&boy1.score);boy2=boy1;printf("Number=%d\nName=%s\n",boy2.num,);printf("Sex=%c\nScore=%f\n",boy2.sex,boy2.score);本程序中用賦值語句給num和name兩個成員賦值，name是一個字符串指針變量。用scanf函數(shù)動態(tài)地輸入sex和score成員值，然后把boy1的所有成員的值整體賦予boy2。最后分別輸出boy2的各個成員值。本例表示了結(jié)構(gòu)變量的賦值、輸入和輸出的方法。結(jié)構(gòu)變量的初始化如果結(jié)構(gòu)變量是全局變量或為靜態(tài)變量，則可對它作初始化賦值。對局部或自動結(jié)構(gòu)變量不能作初始化賦值。[例7.2]外部結(jié)構(gòu)變量初始化。structstu/*定義結(jié)構(gòu)*/{intnum;char*name;charsex;floatscore;}boy2,boy1={102,"Zhangping",'M',78.5};main(){boy2=boy1;printf("Number=%d\nName=%s\n",boy2.num,);printf("Sex=%c\nScore=%f\n",boy2.sex,boy2.score);}structstu{intnum;char*name;charsex;floatscore;}boy2,boy1={102,"Zhangping",'M',78.5};main(){boy2=boy1;……}本例中，boy2,boy1均被定義為外部結(jié)構(gòu)變量，并對boy1作了初始化賦值。在main函數(shù)中，把boy1的值整體賦予boy2，然后用兩個printf語句輸出boy2各成員的值。[例7.3]靜態(tài)結(jié)構(gòu)變量初始化。main(){staticstructstu/*定義靜態(tài)結(jié)構(gòu)變量*/{intnum;char*name;charsex;floatscore;}boy2,boy1={102,"Zhangping",'M',78.5};boy2=boy1;printf("Number=%d\nName=%s\n",boy2.num,);printf("Sex=%c\nScore=%f\n",boy2.sex,boy2.score);}staticstructstu{intnum;char*name;charsex;floatscore;}boy2,boy1={102,"Zhangping",'M',78.5};本例是把boy1，boy2都定義為靜態(tài)局部的結(jié)構(gòu)變量，同樣可以作初始化賦值。結(jié)構(gòu)數(shù)組數(shù)組的元素也可以是結(jié)構(gòu)類型的。因此可以構(gòu)成結(jié)構(gòu)型數(shù)組。結(jié)構(gòu)數(shù)組的每一個元素都是具有相同結(jié)構(gòu)類型的下標(biāo)結(jié)構(gòu)變量。在實際應(yīng)用中，經(jīng)常用結(jié)構(gòu)數(shù)組來表示具有相同數(shù)據(jù)結(jié)構(gòu)的一個群體。如一個班的學(xué)生檔案，一個車間職工的工資表等。結(jié)構(gòu)數(shù)組的定義方法和結(jié)構(gòu)變量相似，只需說明它為數(shù)組類型即可。例如：structstu{intnum;char*name;charsex;floatscore;}boy[5];定義了一個結(jié)構(gòu)數(shù)組boy1，共有5個元素，boy[0]～boy[4]。每個數(shù)組元素都具有structstu的結(jié)構(gòu)形式。對外部結(jié)構(gòu)數(shù)組或靜態(tài)結(jié)構(gòu)數(shù)組可以作初始化賦值，例如：structstu{intnum;char*name;charsex;floatscore;}boy[5]={{101,"Liping","M",45},{102,"Zhangping","M",62.5},{103,"Hefang","F",92.5},{104,"Chengling","F",87},{105,"Wangming","M",58};}當(dāng)對全部元素作初始化賦值時，也可不給出數(shù)組長度。[例7.4]計算學(xué)生的平均成績和不及格的人數(shù)。structstu{intnum;char*name;charsex;floatscore;}boy[5]={{101,"Liping",'M',45},{102,"Zhangping",'M',62.5},{103,"Hefang",'F',92.5},{104,"Chengling",'F',87},{105,"Wangming",'M',58},};main(){inti,c=0;floatave,s=0;for(i=0;i<5;i++){s+=boy[i].score;if(boy[i].score<60)c+=1;}printf("s=%f\n",s);ave=s/5;printf("average=%f\ncount=%d\n",ave,c);}本例程序中定義了一個外部結(jié)構(gòu)數(shù)組boy，共5個元素，并作了初始化賦值。在main函數(shù)中用for語句逐個累加各元素的score成員值存于s之中，如score的值小于60(不及格)即計數(shù)器C加1，循環(huán)完畢后計算平均成績，并輸出全班總分，平均分及不及格人數(shù)。[例7.5]建立同學(xué)通訊錄#include"stdio.h"#defineNUM3structmem{charname[20];charphone[10];};main(){structmemman[NUM];inti;for(i=0;i<NUM;i++){printf("inputname:\n");gets(man[i].name);printf("inputphone:\n");gets(man[i].phone);}printf("name\t\t\tphone\n\n");for(i=0;i<NUM;i++)printf("%s\t\t\t%s\n",man[i].name,man[i].phone);}本程序中定義了一個結(jié)構(gòu)mem，它有兩個成員name和phone用來表示姓名和電話號碼。在主函數(shù)中定義man為具有mem類型的結(jié)構(gòu)數(shù)組。在for語句中，用gets函數(shù)分別輸入各個元素中兩個成員的值。然后又在for語句中用printf語句輸出各元素中兩個成員值。結(jié)構(gòu)指針變量結(jié)構(gòu)指針變量的說明和使用一個指針變量當(dāng)用來指向一個結(jié)構(gòu)變量時，稱之為結(jié)構(gòu)指針變量。結(jié)構(gòu)指針變量中的值是所指向的結(jié)構(gòu)變量的首地址。通過結(jié)構(gòu)指針即可訪問該結(jié)構(gòu)變量，這與數(shù)組指針和函數(shù)指針的情況是相同的。結(jié)構(gòu)指針變量說明的一般形式為：struct結(jié)構(gòu)名*結(jié)構(gòu)指針變量名例如，在前面的例7.1中定義了stu這個結(jié)構(gòu)，如要說明一個指向stu的指針變量pstu，可寫為：structstu*pstu;當(dāng)然也可在定義stu結(jié)構(gòu)時同時說明pstu。與前面討論的各類指針變量相同，結(jié)構(gòu)指針變量也必須要先賦值后才能使用。賦值是把結(jié)構(gòu)變量的首地址賦予該指針變量，不能把結(jié)構(gòu)名賦予該指針變量。如果boy是被說明為stu類型的結(jié)構(gòu)變量，則：pstu=&boy是正確的，而：pstu=&stu是錯誤的。結(jié)構(gòu)名和結(jié)構(gòu)變量是兩個不同的概念，不能混淆。結(jié)構(gòu)名只能表示一個結(jié)構(gòu)形式，編譯系統(tǒng)并不對它分配內(nèi)存空間。只有當(dāng)某變量被說明為這種類型的結(jié)構(gòu)時，才對該變量分配存儲空間。因此上面&stu這種寫法是錯誤的，不可能去取一個結(jié)構(gòu)名的首地址。有了結(jié)構(gòu)指針變量，就能更方便地訪問結(jié)構(gòu)變量的各個成員。其訪問的一般形式為：(*結(jié)構(gòu)指針變量).成員名或為：結(jié)構(gòu)指針變量->成員名例如：(*pstu).num或者：pstu->num應(yīng)該注意(*pstu)兩側(cè)的括號不可少，因為成員符“.”的優(yōu)先級高于“*”。如去掉括號寫作*pstu.num則等效于*(pstu.num)，這樣，意義就完全不對了。下面通過例子來說明結(jié)構(gòu)指針變量的具體說明和使用方法。[例7.6]structstu{intnum;char*name;charsex;floatscore;}boy1={102,"Zhangping",'M',78.5},*pstu;main(){pstu=&boy1;printf("Number=%d\nName=%s\n",boy1.num,);printf("Sex=%c\nScore=%f\n\n",boy1.sex,boy1.score);printf("Number=%d\nName=%s\n",(*pstu).num,(*pstu).name);printf("Sex=%c\nScore=%f\n\n",(*pstu).sex,(*pstu).score);printf("Number=%d\nName=%s\n",pstu->num,pstu->name);printf("Sex=%c\nScore=%f\n\n",pstu->sex,pstu->score);}本例程序定義了一個結(jié)構(gòu)stu，定義了stu類型結(jié)構(gòu)變量boy1并作了初始化賦值，還定義了一個指向stu類型結(jié)構(gòu)的指針變量pstu。在main函數(shù)中，pstu被賦予boy1的地址，因此pstu指向boy1。然后在printf語句內(nèi)用三種形式輸出boy1的各個成員值。從運行結(jié)果可以看出：結(jié)構(gòu)變量.成員名(*結(jié)構(gòu)指針變量).成員名結(jié)構(gòu)指針變量->成員名這三種用于表示結(jié)構(gòu)成員的形式是完全等效的。結(jié)構(gòu)數(shù)組指針變量結(jié)構(gòu)指針變量可以指向一個結(jié)構(gòu)數(shù)組，這時結(jié)構(gòu)指針變量的值是整個結(jié)構(gòu)數(shù)組的首地址。結(jié)構(gòu)指針變量也可指向結(jié)構(gòu)數(shù)組的一個元素，這時結(jié)構(gòu)指針變量的值是該結(jié)構(gòu)數(shù)組元素的首地址。設(shè)ps為指向結(jié)構(gòu)數(shù)組的指針變量，則ps也指向該結(jié)構(gòu)數(shù)組的0號元素，ps+1指向1號元素，ps+i則指向i號元素。這與普通數(shù)組的情況是一致的。[例7.7]用指針變量輸出結(jié)構(gòu)數(shù)組。structstu{intnum;char*name;charsex;floatscore;}boy[5]={{101,"Zhouping",'M',45},{102,"Zhangping",'M',62.5},{103,"Lioufang",'F',92.5},{104,"Chengling",'F',87},{105,"Wangming",'M',58},};main(){structstu*ps;printf("No\tName\t\t\tSex\tScore\t\n");for(ps=boy;ps<boy+5;ps++)printf("%d\t%s\t\t%c\t%f\t\n",ps->num,ps->name,ps->sex,ps->score);}在程序中，定義了stu結(jié)構(gòu)類型的外部數(shù)組boy并作了初始化賦值。在main函數(shù)內(nèi)定義ps為指向stu類型的指針。在循環(huán)語句for的表達式1中，ps被賦予boy的首地址，然后循環(huán)5次，輸出boy數(shù)組中各成員值。應(yīng)該注意的是，一個結(jié)構(gòu)指針變量雖然可以用來訪問結(jié)構(gòu)變量或結(jié)構(gòu)數(shù)組元素的成員，但是，不能使它指向一個成員。也就是說不允許取一個成員的地址來賦予它。因此，下面的賦值是錯誤的。ps=&boy[1].sex;而只能是：ps=boy;(賦予數(shù)組首地址)或者是：ps=&boy[0];(賦予0號元素首地址)結(jié)構(gòu)指針變量作函數(shù)參數(shù)在ANSIC標(biāo)準(zhǔn)中允許用結(jié)構(gòu)變量作函數(shù)參數(shù)進行整體傳送。但是這種傳送要將全部成員逐個傳送，特別是成員為數(shù)組時將會使傳送的時間和空間開銷很大，嚴(yán)重地降低了程序的效率。因此最好的辦法就是使用指針，即用指針變量作函數(shù)參數(shù)進行傳送。這時由實參傳向形參的只是地址，從而減少了時間和空間的開銷。[例7.8]題目與例7.4相同，計算一組學(xué)生的平均成績和不及格人數(shù)。用結(jié)構(gòu)指針變量作函數(shù)參數(shù)編程。structstu{intnum;char*name;charsex;floatscore;}boy[5]={{101,"Liping",'M',45},{102,"Zhangping",'M',62.5},{103,"Hefang",'F',92.5},{104,"Chengling",'F',87},{105,"Wangming",'M',58},};main(){structstu*ps;voidave(structstu*ps);ps=boy;ave(ps);}voidave(structstu*ps){intc=0,i;floatave,s=0;for(i=0;i<5;i++,ps++){s+=ps->score;if(ps->score<60)c+=1;}printf("s=%f\n",s);ave=s/5;printf("average=%f\ncount=%d\n",ave,c);}本程序中定義了函數(shù)ave，其形參為結(jié)構(gòu)指針變量ps。boy被定義為外部結(jié)構(gòu)數(shù)組，因此在整個源程序中有效。在main函數(shù)中定義說明了結(jié)構(gòu)指針變量ps，并把boy的首地址賦予它，使ps指向boy數(shù)組。然后以ps作實參調(diào)用函數(shù)ave。在函數(shù)ave中完成計算平均成績和統(tǒng)計不及格人數(shù)的工作并輸出結(jié)果。與例7.4程序相比，由于本程序全部采用指針變量作運算和處理，故速度更快，程序效率更高。.topoic=動態(tài)存儲分配在數(shù)組一章中，曾介紹過數(shù)組的長度是預(yù)先定義好的，在整個程序中固定不變。Ｃ語言中不允許動態(tài)數(shù)組類型。例如：intn;scanf("%d",&n);inta[n];用變量表示長度，想對數(shù)組的大小作動態(tài)說明，這是錯誤的。但是在實際的編程中，往往會發(fā)生這種情況，即所需的內(nèi)存空間取決于實際輸入的數(shù)據(jù)，而無法預(yù)先確定。對于這種問題，用數(shù)組的辦法很難解決。為了解決上述問題，Ｃ語言提供了一些內(nèi)存管理函數(shù)，這些內(nèi)存管理函數(shù)可以按需要動態(tài)地分配內(nèi)存空間，也可把不再使用的空間回收待用，為有效地利用內(nèi)存資源提供了手段。常用的內(nèi)存管理函數(shù)有以下三個：1.分配內(nèi)存空間函數(shù)malloc調(diào)用形式：(類型說明符*)malloc(size)功能：在內(nèi)存的動態(tài)存儲區(qū)中分配一塊長度為"size"字節(jié)的連續(xù)區(qū)域。函數(shù)的返回值為該區(qū)域的首地址?！邦愋驼f明符”表示把該區(qū)域用于何種數(shù)據(jù)類型。(類型說明符*)表示把返回值強制轉(zhuǎn)換為該類型指針。“size”是一個無符號數(shù)。例如：pc=(char*)malloc(100);表示分配100個字節(jié)的內(nèi)存空間，并強制轉(zhuǎn)換為字符數(shù)組類型，函數(shù)的返回值為指向該字符數(shù)組的指針，把該指針賦予指針變量pc。2.分配內(nèi)存空間函數(shù)calloccalloc也用于分配內(nèi)存空間。調(diào)用形式：(類型說明符*)calloc(n,size)功能：在內(nèi)存動態(tài)存儲區(qū)中分配n塊長度為“size”字節(jié)的連續(xù)區(qū)域。函數(shù)的返回值為該區(qū)域的首地址。(類型說明符*)用于強制類型轉(zhuǎn)換。calloc函數(shù)與malloc函數(shù)的區(qū)別僅在于一次可以分配n塊區(qū)域。例如：ps=(struetstu*)calloc(2,sizeof(structstu));其中的sizeof(structstu)是求stu的結(jié)構(gòu)長度。因此該語句的意思是：按stu的長度分配2塊連續(xù)區(qū)域，強制轉(zhuǎn)換為stu類型，并把其首地址賦予指針變量ps。3.釋放內(nèi)存空間函數(shù)free調(diào)用形式：free(void*ptr);功能：釋放ptr所指向的一塊內(nèi)存空間，ptr是一個任意類型的指針變量，它指向被釋放區(qū)域的首地址。被釋放區(qū)應(yīng)是由malloc或calloc函數(shù)所分配的區(qū)域：[例7.9]分配一塊區(qū)域，輸入一個學(xué)生數(shù)據(jù)。main(){structstu{intnum;char*name;charsex;floatscore;}*ps;ps=(structstu*)malloc(sizeof(structstu));ps->num=102;ps->name="Zhangping";ps->sex='M';ps->score=62.5;printf("Number=%d\nName=%s\n",ps->num,ps->name);printf("Sex=%c\nScore=%f\n",ps->sex,ps->score);free(ps);}本例中，定義了結(jié)構(gòu)stu，定義了stu類型指針變量ps。然后分配一塊stu大內(nèi)存區(qū)，并把首地址賦予ps，使ps指向該區(qū)域。再以ps為指向結(jié)構(gòu)的指針變量對各成員賦值，并用printf輸出各成員值。最后用free函數(shù)釋放ps指向的內(nèi)存空間。整個程序包含了申請內(nèi)存空間、使用內(nèi)存空間、釋放內(nèi)存空間三個步驟，實現(xiàn)存儲空間的動態(tài)分配。鏈表的概念在例7.9中采用了動態(tài)分配的辦法為一個結(jié)構(gòu)分配內(nèi)存空間。每一次分配一塊空間可用來存放一個學(xué)生的數(shù)據(jù)，我們可稱之為一個結(jié)點。有多少個學(xué)生就應(yīng)該申請分配多少塊內(nèi)存空間，也就是說要建立多少個結(jié)點。當(dāng)然用結(jié)構(gòu)數(shù)組也可以完成上述工作，但如果預(yù)先不能準(zhǔn)確把握學(xué)生人數(shù)，也就無法確定數(shù)組大小。而且當(dāng)學(xué)生留級、退學(xué)之后也不能把該元素占用的空間從數(shù)組中釋放出來。用動態(tài)存儲的方法可以很好地解決這些問題。有一個學(xué)生就分配一個結(jié)點，無須預(yù)先確定學(xué)生的準(zhǔn)確人數(shù)，某學(xué)生退學(xué)，可刪去該結(jié)點，并釋放該結(jié)點占用的存儲空間。從而節(jié)約了寶貴的內(nèi)存資源。另一方面，用數(shù)組的方法必須占用一塊連續(xù)的內(nèi)存區(qū)域。而使用動態(tài)分配時，每個結(jié)點之間可以是不連續(xù)的(結(jié)點內(nèi)是連續(xù)的)。結(jié)點之間的聯(lián)系可以用指針實現(xiàn)。即在結(jié)點結(jié)構(gòu)中定義一個成員項用來存放下一結(jié)點的首地址，這個用于存放地址的成員，常把它稱為指針域?？稍诘谝粋€結(jié)點的指針域內(nèi)存入第二個結(jié)點的首地址，在第二個結(jié)點的指針域內(nèi)又存放第三個結(jié)點的首地址，如此串連下去直到最后一個結(jié)點。最后一個結(jié)點因無后續(xù)結(jié)點連接，其指針域可賦為0。這樣一種連接方式，在數(shù)據(jù)結(jié)構(gòu)中稱為“鏈表”。圖7.3為鏈表的示意圖。在圖7.3中，第0個結(jié)點稱為頭結(jié)點，它存放有第一個結(jié)點的首地址，它沒有數(shù)據(jù)，只是一個指針變量。以下的每個結(jié)點都分為兩個域，一個是數(shù)據(jù)域，存放各種實際的數(shù)據(jù)，如學(xué)號num，姓名name，性別sex和成績score等。另一個域為指針域，存放下一結(jié)點的首地址。鏈表中的每一個結(jié)點都是同一種結(jié)構(gòu)類型。例如，一個存放學(xué)生學(xué)號和成績的結(jié)點應(yīng)為以下結(jié)構(gòu)：structstu{intnum;intscore;structstu*next;}前兩個成員項組成數(shù)據(jù)域，后一個成員項next構(gòu)成指針域，它是一個指向stu類型結(jié)構(gòu)的指針變量。鏈表的基本操作對鏈表的主要操作有以下幾種：1.建立鏈表；2.結(jié)構(gòu)的查找與輸出；3.插入一個結(jié)點；4.刪除一個結(jié)點；下面通過例題來說明這些操作。[例7.10]建立一個三個結(jié)點的鏈表，存放學(xué)生數(shù)據(jù)。為簡單起見，我們假定學(xué)生數(shù)據(jù)結(jié)構(gòu)中只有學(xué)號和年齡兩項?？删帉懸粋€建立鏈表的函數(shù)creat。程序如下：#defineNULL0#defineTYPEstructstu#defineLENsizeof(structstu)structstu{intnum;intage;structstu*next;};TYPE*creat(intn){structstu*head,*pf,*pb;inti;for(i=0;i<n;i++){pb=(TYPE*)malloc(LEN);printf("inputNumberandAge\n");scanf("%d%d",&pb->num,&pb->age);if(i==0)pf=head=pb;elsepf->next=pb;pb->next=NULL;pf=pb;}return(head);}在函數(shù)外首先用宏定義對三個符號常量作了定義。這里用TYPE表示structstu，用LEN表示sizeof(structstu)主要的目的是為了在以下程序內(nèi)減少書寫并使閱讀更加方便。結(jié)構(gòu)stu定義為外部類型，程序中的各個函數(shù)均可使用該定義。creat函數(shù)用于建立一個有n個結(jié)點的鏈表，它是一個指針函數(shù)，它返回的指針指向stu結(jié)構(gòu)。在creat函數(shù)內(nèi)定義了三個stu結(jié)構(gòu)的指針變量。head為頭指針，pf為指向兩相鄰結(jié)點的前一結(jié)點的指針變量。pb為后一結(jié)點的指針變量。在for語句內(nèi)，用malloc函數(shù)建立長度與stu長度相等的空間作為一結(jié)點，首地址賦予pb。然后輸入結(jié)點數(shù)據(jù)。如果當(dāng)前結(jié)點為第一結(jié)點(i==0)，則把pb值(該結(jié)點指針)賦予head和pf。如非第一結(jié)點，則把pb值賦予pf所指結(jié)點的指針域成員next。而pb所指結(jié)點為當(dāng)前的最后結(jié)點，其指針域賦NULL。再把pb值賦予pf以作下一次循環(huán)準(zhǔn)備。creat函數(shù)的形參n，表示所建鏈表的結(jié)點數(shù)，作為for語句的循環(huán)次數(shù)。圖7.4表示了creat函數(shù)的執(zhí)行過程。[例7.11]寫一個函數(shù)，在鏈表中按學(xué)號查找該結(jié)點。TYPE*search(TYPE*head,intn){TYPE*p;inti;p=head;while(p->num!=n&&p->next!=NULL)p=p->next;/*不是要找的結(jié)點后移一步*/if(p->num==n)return(p);if(p->num!=n&&p->next==NULL)printf("Node%dhasnotbeenfound!\n",n}本函數(shù)中使用的符號常量TYPE與例7.10的宏定義相同，等于structstu。函數(shù)有兩個形參，head是指向鏈表的指針變量，n為要查找的學(xué)號。進入while語句，逐個檢查結(jié)點的num成員是否等于n，如果不等于n且指針域不等于NULL(不是最后結(jié)點)則后移一個結(jié)點，繼續(xù)循環(huán)。如找到該結(jié)點則返回結(jié)點指針。如循環(huán)結(jié)束仍未找到該結(jié)點則輸出“未找到”的提示信息。[例7.12]寫一個函數(shù)，刪除鏈表中的指定結(jié)點。刪除一個結(jié)點有兩種情況：1.被刪除結(jié)點是第一個結(jié)點。這種情況只需使head指向第二個結(jié)點即可。即head=pb->next。其過程如圖7.5所示。2.被刪結(jié)點不是第一個結(jié)點，這種情況使被刪結(jié)點的前一結(jié)點指向被刪結(jié)點的后一結(jié)點即可。即pf->next=pb->next。其過程如圖7.6所示。函數(shù)編程如下：TYPE*delete(TYPE*head,intnum){TYPE*pf,*pb;if(head==NULL)/*如為空表，輸出提示信息*/{printf("\nemptylist!\n");gotoend;}pb=head;while(pb->num!=num&&pb->next!=NULL)/*當(dāng)不是要刪除的結(jié)點，而且也不是最后一個結(jié)點時，繼續(xù)循環(huán)*/{pf=pb;pb=pb->next;}/*pf指向當(dāng)前結(jié)點，pb指向下一結(jié)點*/if(pb->num==num){if(pb==head)head=pb->next;/*如找到被刪結(jié)點，且為第一結(jié)點，則使head指向第二個結(jié)點，否則使pf所指結(jié)點的指針指向下一結(jié)點*/elsepf->next=pb->next;free(pb);printf("Thenodeisdeleted\n");}elseprintf("Thenodenotbeenfoud!\n");end:returnhead;}

函數(shù)有兩個形參，head為指向鏈表第一結(jié)點的指針變量，num刪結(jié)點的學(xué)號。首先判斷鏈表是否為空，為空則不可能有被刪結(jié)點。若不為空，則使pb指針指向鏈表的第一個結(jié)點。進入while語句后逐個查找被刪結(jié)點。找到被刪結(jié)點之后再看是否為第一結(jié)點，若是則使head指向第二結(jié)點(即把第一結(jié)點從鏈中刪去)，否則使被刪結(jié)點的前一結(jié)點(pf所指)指向被刪結(jié)點的后一結(jié)點(被刪結(jié)點的指針域所指)。如若循環(huán)結(jié)束未找到要刪的結(jié)點，則輸出“末找到”的提示信息。最后返回head值。[例7.13]寫一個函數(shù)，在鏈表中指定位置插入一個結(jié)點。在一個鏈表的指定位置插入結(jié)點，要求鏈表本身必須是已按某種規(guī)律排好序的。例如，在學(xué)生數(shù)據(jù)鏈表中，要求學(xué)號順序插入一個結(jié)點。設(shè)被插結(jié)點的指針為pi。可在三種不同情況下插入。1.原表是空表，只需使head指向被插結(jié)點即可。見圖7.7(a)2.被插結(jié)點值最小，應(yīng)插入第一結(jié)點之前。這種情況下使head指向被插結(jié)點，被插結(jié)點的指針域指向原來的第一結(jié)點則可。即：pi->next=pb;head=pi;見圖7.7(b)3.在其它位置插入，見圖7.7(c)。這種情況下，使插入位置的前一結(jié)點的指針域指向被插結(jié)點，使被插結(jié)點的指針域指向插入位置的后一結(jié)點。即為：pi->next=pb;pf->next=pi；4.在表末插入，見圖7.7(d)。這種情況下使原表末結(jié)點指針域指向被插結(jié)點，被插結(jié)點指針域置為NULL。即：pb->next=pi;pi->next=NULL；TYPE*insert(TYPE*head,TYPE*pi){TYPE*pf,*pb;pb=head;if(head==NULL)/*空表插入*/(head=pi;pi->next=NULL;}else{while((pi->num>pb->num)&&(pb->next!=NULL)){pf=pb;pb=pb->next;}/*找插入位置*/if(pi->num<=pb->num){if(head==pb)head=pi;/*在第一結(jié)點之前插入*/elsepf->next=pi;/*在其它位置插入*/pi->next=pb;}else{pb->next=pi;pi->next=NULL;}/*在表末插入*/}

returnhead;}本函數(shù)有兩個形參均為指針變量，head指向鏈表，pi指向被插結(jié)點。函數(shù)中首先判斷鏈表是否為空，為空則使head指向被插結(jié)點。表若不空，則用while語句循環(huán)查找插入位置。找到之后再判斷是否在第一結(jié)點之前插入，若是則使head指向被插結(jié)點被插結(jié)點指針域指向原第一結(jié)點，否則在其它位置插入，若插入的結(jié)點大于表中所有結(jié)點，則在表末插入。本函數(shù)返回一個指針，是鏈表的頭指針。當(dāng)插入的位置在第一個結(jié)點之前時，插入的新結(jié)點成為鏈表的第一個結(jié)點，因此head的值也有了改變，故需要把這個指針返回主調(diào)函數(shù)。[例7.14]將以上建立鏈表，刪除結(jié)點，插入結(jié)點的函數(shù)組織在一起，再建一個輸出全部結(jié)點的函數(shù)，然后用main函數(shù)調(diào)用它們。#defineNULL0#defineTYPEstructstu#defineLENsizeof(structstu)structstu{intnum;intage;structstu*next;};TYPE*creat(intn){structstu*head,*pf,*pb;inti;for(i=0;i<n;i++){pb=(TYPE*)malloc(LEN);printf("inputNumberandAge\n");scanf("%d%d",&pb->num,&pb->age);if(i==0)pf=head=pb;elsepf->next=pb;pb->next=NULL;pf=pb;}return(head);}TYPE*delete(TYPE*head,intnum){TYPE*pf,*pb;if(head==NULL){printf("\nemptylist!\n");gotoend;}pb=head;while(pb->num!=num&&pb->next!=NULL){pf=pb;pb=pb->next;}if(pb->num==num){if(pb==head)head=pb->next;elsepf->next=pb->next;printf("Thenodeisdeleted\n");}elsefree(pb);printf("Thenodenotbeenfound!\n");end:returnhead;}TYPE*insert(TYPE*head,TYPE*pi){TYPE*pb,*pf;pb=head;if(head==NULL){head=pi;pi->next=NULL;}else{while((pi->num>pb->num)&&(pb->next!=NULL)){pf=pb;pb=pb->next;}if(pi->num<=pb->num){if(head==pb)head=pi;elsepf->next=pi;pi->next=pb;}else{pb->next=pi;pi->next=NULL;}}returnhead;}voidprint(TYPE*head){printf("Number\t\tAge\n");while(head!=NULL){printf("%d\t\t%d\n",head->num,head->age);head=head->next;}}main(){TYPE*head,*pnum;intn,num;printf("inputnumberofnode:");scanf("%d",&n);head=creat(n);print(head);printf("Inputthedeletednumber:");scanf("%d",&num);head=delete(head,num);print(head);printf("Inputtheinsertednumberandage:");pnum=(TYPE*)malloc(LEN);scanf("%d%d",&pnum->num,&pnum->age);head=insert(head,pnum);print(head);}本例中，print函數(shù)用于輸出鏈表中各個結(jié)點數(shù)據(jù)域值。函數(shù)的形參head的初值指向鏈表第一個結(jié)點。在while語句中，輸出結(jié)點值后，head值被改變，指向下一結(jié)點。若保留頭指針head，則應(yīng)另設(shè)一個指針變量，把head值賦予它，再用它來替代head。在main函數(shù)中，n為建立結(jié)點的數(shù)目，num為待刪結(jié)點的數(shù)據(jù)域值；head為指向鏈表的頭指針，pnum為指向待插結(jié)點的指針。main函數(shù)中各行的意義是：第六行輸入所建鏈表的結(jié)點數(shù)；第七行調(diào)creat函數(shù)建立鏈表并把頭指針返回給head；第八行調(diào)print函數(shù)輸出鏈表；第十行輸入待刪結(jié)點的學(xué)號；第十一行調(diào)delete函數(shù)刪除一個結(jié)點；第十二行調(diào)print函數(shù)輸出鏈表；第十四行調(diào)malloc函數(shù)分配一個結(jié)點的內(nèi)存空間，并把其地址賦予pnum;第十五行輸入待插入結(jié)點的數(shù)據(jù)域值；第十六行調(diào)insert函數(shù)插入pnum所指的結(jié)點；第十七行再次調(diào)print函數(shù)輸出鏈表。從運行結(jié)果看，首先建立起3個結(jié)點的鏈表，并輸出其值；再刪103號結(jié)點，只剩下105，108號結(jié)點；又輸入106號結(jié)點數(shù)據(jù)，插入后鏈表中的結(jié)點為105，106，108。聯(lián)合“聯(lián)合”也是一種構(gòu)造類型的數(shù)據(jù)結(jié)構(gòu)。在一個“聯(lián)合”內(nèi)可以定義多種不同的數(shù)據(jù)類型，一個被說明為該“聯(lián)合”類型的變量中，允許裝入該“聯(lián)合”所定義的任何一種數(shù)據(jù)。這在前面的各種數(shù)據(jù)類型中都是辦不到的。例如，定義為整型的變量只能裝入整型數(shù)據(jù)，定義為實型的變量只能賦予實型數(shù)據(jù)。在實際問題中有很多這樣的例子。例如在學(xué)校的教師和學(xué)生中填寫以下表格：姓名年齡職業(yè)單位“職業(yè)”一項可分為“教師”和“學(xué)生”兩類。對“單位”一項學(xué)生應(yīng)填入班級編號，教師應(yīng)填入某系某教研室。班級可用整型量表示，教研室只能用字符類型。要求把這兩種類型不同的數(shù)據(jù)都填入“單位”這個變量中，就必須把“單位”定義為包含整型和字符型數(shù)組這兩種類型的“聯(lián)合”?！奥?lián)合”與“結(jié)構(gòu)”有一些相似之處。但兩者有本質(zhì)上的不同。在結(jié)構(gòu)中各成員有各自的內(nèi)存空間，一個結(jié)構(gòu)變量的總長度是各成員長度之和。而在“聯(lián)合”中，各成員共享一段內(nèi)存空間，一個聯(lián)合變量的長度等于各成員中最長的長度。應(yīng)該說明的是，這里所謂的共享不是指把多個成員同時裝入一個聯(lián)合變量內(nèi)，而是指該聯(lián)合變量可被賦予任一成員值，但每次只能賦一種值，賦入新值則沖去舊值。如前面介紹的“單位”變量，如定義為一個可裝入“班級”或“教研室”的聯(lián)合后，就允許賦予整型值（班級)或字符串（教研室)。要么賦予整型值，要么賦予字符串，不能把兩者同時賦予它。聯(lián)合類型的定義和聯(lián)合變量的說明一個聯(lián)合類型必須經(jīng)過定義之后，才能把變量說明為該聯(lián)合類型。一、聯(lián)合的定義定義一個聯(lián)合類型的一般形式為：union聯(lián)合名{成員表};成員表中含有若干成員，成員的一般形式為：類型說明符成員名成員名的命名應(yīng)符合標(biāo)識符的規(guī)定。例如：unionperdata{intclass;charoffice[10];};定義了一個名為perdata的聯(lián)合類型，它含有兩個成員，一個為整型，成員名為class；另一個為字符數(shù)組，數(shù)組名為office。聯(lián)合定義之后，即可進行聯(lián)合變量說明，被說明為perdata類型的變量，可以存放整型量class或存放字符數(shù)組office。二、聯(lián)合變量的說明聯(lián)合變量的說明和結(jié)構(gòu)變量的說明方式相同，也有三種形式。即先定義，再說明；定義同時說明和直接說明。以perdata類型為例，說明如下：unionperdata{intclass;charofficae[10];};unionperdataa,b;/*說明a,b為perdata類型*/或者可同時說明為：unionperdata{intclass;charof