第七章:結構與聯(lián)合結構類(lèi)型定義和結構變量說(shuō)明 在實(shí)際問(wèn)題中，一組數據往往具有不同的數據類(lèi)型。例如， 在學(xué)生登記表中，姓名應為字符型；學(xué)號可為整型或字符型； 年齡應為整型；性別應為字符型；成績(jì)可為整型或實(shí)型。 顯然不能用一個(gè)數組來(lái)存放這一組數據。 因為數組中各元素的類(lèi)型和長(cháng)度都必須一致，以便于編譯系統處理。為了解決這個(gè)問(wèn)題，Ｃ語(yǔ)言中給出了另一種構造數據類(lèi)型——“結構”。 它相當于其它高級語(yǔ)言中的記錄?！ ?#8220;結構”是一種構造類(lèi)型，它是由若干“成員”組成的。 每一個(gè)成員可以是一個(gè)基本數據類(lèi)型或者又是一個(gè)構造類(lèi)型。 結構既是一種“構造”而成的數據類(lèi)型， 那么在說(shuō)明和使用之前必須先定義它，也就是構造它。如同在說(shuō)明和調用函數之前要先定義函數一樣。一、結構的定義定義一個(gè)結構的一般形式為：struct 結構名{成員表列};成員表由若干個(gè)成員組成， 每個(gè)成員都是該結構的一個(gè)組成部分。對每個(gè)成員也必須作類(lèi)型說(shuō)明，其形式為：類(lèi)型說(shuō)明符 成員名;成員名的命名應符合標識符的書(shū)寫(xiě)規定。例如：struct stu{int num;char name[20];char sex;float score;}; 在這個(gè)結構定義中，結構名為stu，該結構由4個(gè)成員組成。 第一個(gè)成員為num，整型變量；第二個(gè)成員為name，字符數組；第三個(gè)成員為sex，字符變量；第四個(gè)成員為score，實(shí)型變量。 應注意在括號后的分號是不可少的。結構定義之后，即可進(jìn)行變量說(shuō)明。 凡說(shuō)明為結構stu的變量都由上述4個(gè)成員組成。由此可見(jiàn)， 結構是一種復雜的數據類(lèi)型，是數目固定，類(lèi)型不同的若干有序變量的集合。二、結構類(lèi)型變量的說(shuō)明說(shuō)明結構變量有以下三種方法。以上面定義的stu為例來(lái)加以說(shuō)明。1. 先定義結構，再說(shuō)明結構變量。如：struct stu{int num;char name[20];char sex;float score;};struct stu boy1,boy2;說(shuō)明了兩個(gè)變量boy1和boy2為stu結構類(lèi)型。也可以用宏定義使一個(gè)符號常量來(lái)表示一個(gè)結構類(lèi)型，例如：#define STU struct stuSTU{int num;char name[20];char sex;float score;};STU boy1,boy2;2. 在定義結構類(lèi)型的同時(shí)說(shuō)明結構變量。例如：struct stu{int num;char name[20];char sex;float score;}boy1,boy2;3. 直接說(shuō)明結構變量。例如：struct{int num;char name[20];char sex;float score;}boy1,boy2; 第三種方法與第二種方法的區別在于第三種方法中省去了結構名，而直接給出結構變量。三種方法中說(shuō)明的boy1,boy2變量都具有圖7.1所示的結構。說(shuō)明了boy1,boy2變量為stu類(lèi)型后，即可向這兩個(gè)變量中的各個(gè)成員賦值。在上述stu結構定義中，所有的成員都是基本數據類(lèi)型或數組類(lèi)型。成員也可以又是一個(gè)結構， 即構成了嵌套的結構。例如，圖7.2給出了另一個(gè)數據結構。 按圖7.2可給出以下結構定義：struct date{int month;int day;int year;}struct{int num;char name[20];char sex;struct date birthday;float score;}boy1,boy2; 首先定義一個(gè)結構date，由month(月)、day(日)、year(年) 三個(gè)成員組成。 在定義并說(shuō)明變量 boy1 和 boy2 時(shí)， 其中的成員birthday被說(shuō)明為data結構類(lèi)型。成員名可與程序中其它變量同名，互不干擾。結構變量成員的表示方法在程序中使用結構變量時(shí)， 往往不把它作為一個(gè)整體來(lái)使用?！ ≡贏(yíng)NSI C中除了允許具有相同類(lèi)型的結構變量相互賦值以外， 一般對結構變量的使用，包括賦值、輸入、輸出、 運算等都是通過(guò)結構變量的成員來(lái)實(shí)現的?！ ”硎窘Y構變量成員的一般形式是： 結構變量名.成員名 例如：boy1.num 即第一個(gè)人的學(xué)號 boy2.sex 即第二個(gè)人的性別 如果成員本身又是一個(gè)結構則必須逐級找到最低級的成員才能使用。例如：boy1.birthday.month 即第一個(gè)人出生的月份成員可以在程序中單獨使用，與普通變量完全相同。結構變量的賦值前面已經(jīng)介紹，結構變量的賦值就是給各成員賦值。 可用輸入語(yǔ)句或賦值語(yǔ)句來(lái)完成。[例7.1]給結構變量賦值并輸出其值。main(){struct stu{int num;char *name;char sex;float score;} boy1,boy2;boy1.num=102;boy1.name="Zhang ping";printf("input sex and score\n");scanf("%c %f",&boy1.sex,&boy1.score);boy2=boy1;printf("Number=%d\nName=%s\n",boy2.num,boy2.name);printf("Sex=%c\nScore=%f\n",boy2.sex,boy2.score);}struct stu{int num;char *name;char sex;float score;}boy1,boy2;boy1.num=102;boy1.name="Zhang ping";printf("input sex and score\n");scanf("%c %f",&boy1.sex,&boy1.score);boy2=boy1;printf("Number=%d\nName=%s\n",boy2.num,boy2.name);printf("Sex=%c\nScore=%f\n",boy2.sex,boy2.score); 本程序中用賦值語(yǔ)句給num和name兩個(gè)成員賦值，name是一個(gè)字符串指針變量。用scanf函數動(dòng)態(tài)地輸入sex和score成員值，然后把boy1的所有成員的值整體賦予boy2。最后分別輸出boy2 的各個(gè)成員值。本例表示了結構變量的賦值、輸入和輸出的方法。結構變量的初始化 如果結構變量是全局變量或為靜態(tài)變量， 則可對它作初始化賦值。對局部或自動(dòng)結構變量不能作初始化賦值。[例7.2]外部結構變量初始化。struct stu /*定義結構*/{int num;char *name;char sex;float score;} boy2,boy1={102,"Zhang ping",‘M‘,78.5};main(){boy2=boy1;printf("Number=%d\nName=%s\n",boy2.num,boy2.name);printf("Sex=%c\nScore=%f\n",boy2.sex,boy2.score);}struct stu{int num;char *name;char sex;float score;}boy2,boy1={102,"Zhang ping",‘M‘,78.5};main(){boy2=boy1;……}本例中，boy2,boy1均被定義為外部結構變量，并對boy1作了初始化賦值。在main函數中，把boy1的值整體賦予boy2， 然后用兩個(gè)printf語(yǔ)句輸出boy2各成員的值。[例7.3]靜態(tài)結構變量初始化。main(){static struct stu /*定義靜態(tài)結構變量*/{int num;char *name;char sex;float score;}boy2,boy1={102,"Zhang ping",‘M‘,78.5};boy2=boy1;printf("Number=%d\nName=%s\n",boy2.num,boy2.name);printf("Sex=%c\nScore=%f\n",boy2.sex,boy2.score);}static struct stu{int num;char *name;char sex;float score;}boy2,boy1={102,"Zhang ping",‘M‘,78.5}; 本例是把boy1，boy2都定義為靜態(tài)局部的結構變量， 同樣可以作初始化賦值。結構數組數組的元素也可以是結構類(lèi)型的。 因此可以構成結構型數組。結構數組的每一個(gè)元素都是具有相同結構類(lèi)型的下標結構變量。 在實(shí)際應用中，經(jīng)常用結構數組來(lái)表示具有相同數據結構的一個(gè)群體。如一個(gè)班的學(xué)生檔案，一個(gè)車(chē)間職工的工資表等。結構數組的定義方法和結構變量相似，只需說(shuō)明它為數組類(lèi)型即可。例如：struct stu{int num;char *name;char sex;float score;}boy[5];定義了一個(gè)結構數組boy1，共有5個(gè)元素，boy[0]～boy[4]。每個(gè)數組元素都具有struct stu的結構形式。 對外部結構數組或靜態(tài)結構數組可以作初始化賦值，例如：struct stu{int num;char *name;char sex;float score;}boy[5]={{101,"Li ping","M",45},{102,"Zhang ping","M",62.5},{103,"He fang","F",92.5},{104,"Cheng ling","F",87},{105,"Wang ming","M",58};}當對全部元素作初始化賦值時(shí)，也可不給出數組長(cháng)度。[例7.4]計算學(xué)生的平均成績(jì)和不及格的人數。struct stu{int num;char *name;char sex;float score;}boy[5]={{101,"Li ping",‘M‘,45},{102,"Zhang ping",‘M‘,62.5},{103,"He fang",‘F‘,92.5},{104,"Cheng ling",‘F‘,87},{105,"Wang ming",‘M‘,58},};main(){int i,c=0;float ave,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);}本例程序中定義了一個(gè)外部結構數組boy，共5個(gè)元素， 并作了初始化賦值。在main函數中用for語(yǔ)句逐個(gè)累加各元素的score 成員值存于s之中，如score的值小于60(不及格)即計數器C加1， 循環(huán)完畢后計算平均成績(jì)，并輸出全班總分，平均分及不及格人數。[例7.5]建立同學(xué)通訊錄#include"stdio.h"#define NUM 3struct mem{char name[20];char phone[10];};main(){struct mem man[NUM];int i;for(i=0;i<NUM;i++){printf("input name:\n");gets(man[i].name);printf("input phone:\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);} 本程序中定義了一個(gè)結構mem，它有兩個(gè)成員name和phone 用來(lái)表示姓名和電話(huà)號碼。在主函數中定義man為具有mem 類(lèi)型的結構數組。在for語(yǔ)句中，用gets函數分別輸入各個(gè)元素中兩個(gè)成員的值。然后又在for語(yǔ)句中用printf語(yǔ)句輸出各元素中兩個(gè)成員值。結構指針變量結構指針變量的說(shuō)明和使用一個(gè)指針變量當用來(lái)指向一個(gè)結構變量時(shí)， 稱(chēng)之為結構指針變量。結構指針變量中的值是所指向的結構變量的首地址。 通過(guò)結構指針即可訪(fǎng)問(wèn)該結構變量， 這與數組指針和函數指針的情況是相同的。結構指針變量說(shuō)明的一般形式為：struct 結構名*結構指針變量名例如，在前面的例7.1中定義了stu這個(gè)結構， 如要說(shuō)明一個(gè)指向stu的指針變量pstu，可寫(xiě)為：struct stu *pstu; 當然也可在定義stu結構時(shí)同時(shí)說(shuō)明pstu。與前面討論的各類(lèi)指針變量相同，結構指針變量也必須要先賦值后才能使用。賦值是把結構變量的首地址賦予該指針變量， 不能把結構名賦予該指針變量。如果boy是被說(shuō)明為stu類(lèi)型的結構變量，則： pstu=&boy是正確的，而： pstu=&stu是錯誤的?！ 〗Y構名和結構變量是兩個(gè)不同的概念，不能混淆。 結構名只能表示一個(gè)結構形式，編譯系統并不對它分配內存空間。 只有當某變量被說(shuō)明為這種類(lèi)型的結構時(shí)，才對該變量分配存儲空間。 因此上面&stu這種寫(xiě)法是錯誤的，不可能去取一個(gè)結構名的首地址。 有了結構指針變量，就能更方便地訪(fǎng)問(wèn)結構變量的各個(gè)成員。其訪(fǎng)問(wèn)的一般形式為： (*結構指針變量).成員名 或為：結構指針變量->成員名例如： (*pstu).num或者： pstu->num應該注意(*pstu)兩側的括號不可少， 因為成員符“.”的優(yōu)先級高于“*”。如去掉括號寫(xiě)作*pstu.num則等效于*(pstu.num)，這樣，意義就完全不對了。 下面通過(guò)例子來(lái)說(shuō)明結構指針變量的具體說(shuō)明和使用方法。[例7.6]struct stu{int num;char *name;char sex;float score;} boy1={102,"Zhang ping",‘M‘,78.5},*pstu;main(){pstu=&boy1;printf("Number=%d\nName=%s\n",boy1.num,boy1.name);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);} 本例程序定義了一個(gè)結構stu，定義了stu類(lèi)型結構變量boy1 并作了初始化賦值，還定義了一個(gè)指向stu類(lèi)型結構的指針變量pstu。在main函數中，pstu被賦予boy1的地址，因此pstu指向boy1 。然后在printf語(yǔ)句內用三種形式輸出boy1的各個(gè)成員值。 從運行結果可以看出：結構變量.成員名(*結構指針變量).成員名結構指針變量->成員名 這三種用于表示結構成員的形式是完全等效的。結構數組指針變量結構指針變量可以指向一個(gè)結構數組， 這時(shí)結構指針變量的值是整個(gè)結構數組的首地址。 結構指針變量也可指向結構數組的一個(gè)元素，這時(shí)結構指針變量的值是該結構數組元素的首地址。設ps為指向結構數組的指針變量，則ps也指向該結構數組的0號元素，ps+1指向1號元素，ps+i則指向i號元素。 這與普通數組的情況是一致的。[例7.7]用指針變量輸出結構數組。struct stu{int num;char *name;char sex;float score;}boy[5]={{101,"Zhou ping",‘M‘,45},{102,"Zhang ping",‘M‘,62.5},{103,"Liou fang",‘F‘,92.5},{104,"Cheng ling",‘F‘,87},{105,"Wang ming",‘M‘,58},};main(){struct stu *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結構類(lèi)型的外部數組boy 并作了初始化賦值。在main函數內定義ps為指向stu類(lèi)型的指針。在循環(huán)語(yǔ)句for的表達式1中，ps被賦予boy的首地址，然后循環(huán)5次，輸出boy數組中各成員值。 應該注意的是， 一個(gè)結構指針變量雖然可以用來(lái)訪(fǎng)問(wèn)結構變量或結構數組元素的成員，但是，不能使它指向一個(gè)成員。 也就是說(shuō)不允許取一個(gè)成員的地址來(lái)賦予它。因此，下面的賦值是錯誤的。 ps=&boy[1].sex;而只能是：ps=boy;(賦予數組首地址)或者是：ps=&boy[0];(賦予0號元素首地址)結構指針變量作函數參數 在A(yíng)NSI C標準中允許用結構變量作函數參數進(jìn)行整體傳送。 但是這種傳送要將全部成員逐個(gè)傳送， 特別是成員為數組時(shí)將會(huì )使傳送的時(shí)間和空間開(kāi)銷(xiāo)很大，嚴重地降低了程序的效率。 因此最好的辦法就是使用指針，即用指針變量作函數參數進(jìn)行傳送。 這時(shí)由實(shí)參傳向形參的只是地址，從而減少了時(shí)間和空間的開(kāi)銷(xiāo)。[例7.8]題目與例7.4相同，計算一組學(xué)生的平均成績(jì)和不及格人數。用結構指針變量作函數參數編程。struct stu{int num;char *name;char sex;float score;}boy[5]={{101,"Li ping",‘M‘,45},{102,"Zhang ping",‘M‘,62.5},{103,"He fang",‘F‘,92.5},{104,"Cheng ling",‘F‘,87},{105,"Wang ming",‘M‘,58},};main(){struct stu *ps;void ave(struct stu *ps);ps=boy;ave(ps);}void ave(struct stu *ps){int c=0,i;float ave,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);} 本程序中定義了函數ave，其形參為結構指針變量ps。boy 被定義為外部結構數組，因此在整個(gè)源程序中有效。在main 函數中定義說(shuō)明了結構指針變量ps，并把boy的首地址賦予它，使ps指向boy 數組。然后以ps作實(shí)參調用函數ave。在函數ave 中完成計算平均成績(jì)和統計不及格人數的工作并輸出結果。與例7.4程序相比，由于本程序全部采用指針變量作運算和處理，故速度更快，程序效率更高。.topoic=動(dòng)態(tài)存儲分配 在數組一章中，曾介紹過(guò)數組的長(cháng)度是預先定義好的， 在整個(gè)程序中固定不變。Ｃ語(yǔ)言中不允許動(dòng)態(tài)數組類(lèi)型。例如： int n;scanf("%d",&n);int a[n]; 用變量表示長(cháng)度，想對數組的大小作動(dòng)態(tài)說(shuō)明， 這是錯誤的。但是在實(shí)際的編程中，往往會(huì )發(fā)生這種情況， 即所需的內存空間取決于實(shí)際輸入的數據，而無(wú)法預先確定。對于這種問(wèn)題， 用數組的辦法很難解決。為了解決上述問(wèn)題，Ｃ語(yǔ)言提供了一些內存管理函數，這些內存管理函數可以按需要動(dòng)態(tài)地分配內存空間， 也可把不再使用的空間回收待用，為有效地利用內存資源提供了手段。 常用的內存管理函數有以下三個(gè)：1.分配內存空間函數malloc調用形式： (類(lèi)型說(shuō)明符*) malloc (size) 功能：在內存的動(dòng)態(tài)存儲區中分配一塊長(cháng)度為"size" 字節的連續區域。函數的返回值為該區域的首地址。 “類(lèi)型說(shuō)明符”表示把該區域用于何種數據類(lèi)型。(類(lèi)型說(shuō)明符*)表示把返回值強制轉換為該類(lèi)型指針。“size”是一個(gè)無(wú)符號數。例如： pc=(char *) malloc (100); 表示分配100個(gè)字節的內存空間，并強制轉換為字符數組類(lèi)型， 函數的返回值為指向該字符數組的指針， 把該指針賦予指針變量pc。2.分配內存空間函數 calloccalloc 也用于分配內存空間。調用形式： (類(lèi)型說(shuō)明符*)calloc(n,size) 功能：在內存動(dòng)態(tài)存儲區中分配n塊長(cháng)度為“size”字節的連續區域。函數的返回值為該區域的首地址。(類(lèi)型說(shuō)明符*)用于強制類(lèi)型轉換。calloc函數與malloc 函數的區別僅在于一次可以分配n塊區域。例如： ps=(struet stu*) calloc(2,sizeof (struct stu)); 其中的sizeof(struct stu)是求stu的結構長(cháng)度。因此該語(yǔ)句的意思是：按stu的長(cháng)度分配2塊連續區域，強制轉換為stu類(lèi)型，并把其首地址賦予指針變量ps。3.釋放內存空間函數free調用形式： free(void*ptr); 功能：釋放ptr所指向的一塊內存空間，ptr 是一個(gè)任意類(lèi)型的指針變量，它指向被釋放區域的首地址。被釋放區應是由malloc或calloc函數所分配的區域：[例7.9]分配一塊區域，輸入一個(gè)學(xué)生數據。main(){struct stu{int num;char *name;char sex;float score;} *ps;ps=(struct stu*)malloc(sizeof(struct stu));ps->num=102;ps->name="Zhang ping";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);} 本例中，定義了結構stu，定義了stu類(lèi)型指針變量ps。 然后分配一塊stu大內存區，并把首地址賦予ps，使ps指向該區域。再以ps為指向結構的指針變量對各成員賦值，并用printf 輸出各成員值。最后用free函數釋放ps指向的內存空間。 整個(gè)程序包含了申請內存空間、使用內存空間、釋放內存空間三個(gè)步驟， 實(shí)現存儲空間的動(dòng)態(tài)分配。鏈表的概念在例7.9中采用了動(dòng)態(tài)分配的辦法為一個(gè)結構分配內存空間。每一次分配一塊空間可用來(lái)存放一個(gè)學(xué)生的數據， 我們可稱(chēng)之為一個(gè)結點(diǎn)。有多少個(gè)學(xué)生就應該申請分配多少塊內存空間， 也就是說(shuō)要建立多少個(gè)結點(diǎn)。當然用結構數組也可以完成上述工作， 但如果預先不能準確把握學(xué)生人數，也就無(wú)法確定數組大小。 而且當學(xué)生留級、退學(xué)之后也不能把該元素占用的空間從數組中釋放出來(lái)。 用動(dòng)態(tài)存儲的方法可以很好地解決這些問(wèn)題。 有一個(gè)學(xué)生就分配一個(gè)結點(diǎn)，無(wú)須預先確定學(xué)生的準確人數，某學(xué)生退學(xué)， 可刪去該結點(diǎn)，并釋放該結點(diǎn)占用的存儲空間。從而節約了寶貴的內存資源。 另一方面，用數組的方法必須占用一塊連續的內存區域。 而使用動(dòng)態(tài)分配時(shí)，每個(gè)結點(diǎn)之間可以是不連續的(結點(diǎn)內是連續的)。 結點(diǎn)之間的聯(lián)系可以用指針實(shí)現。 即在結點(diǎn)結構中定義一個(gè)成員項用來(lái)存放下一結點(diǎn)的首地址，這個(gè)用于存放地址的成員，常把它稱(chēng)為指針域?？稍诘谝粋€(gè)結點(diǎn)的指針域內存入第二個(gè)結點(diǎn)的首地址， 在第二個(gè)結點(diǎn)的指針域內又存放第三個(gè)結點(diǎn)的首地址， 如此串連下去直到最后一個(gè)結點(diǎn)。最后一個(gè)結點(diǎn)因無(wú)后續結點(diǎn)連接，其指針域可賦為0。這樣一種連接方式，在數據結構中稱(chēng)為“鏈表”。圖7.3為鏈表的示意圖?！ ≡趫D7.3中，第0個(gè)結點(diǎn)稱(chēng)為頭結點(diǎn)， 它存放有第一個(gè)結點(diǎn)的首地址，它沒(méi)有數據，只是一個(gè)指針變量。 以下的每個(gè)結點(diǎn)都分為兩個(gè)域，一個(gè)是數據域，存放各種實(shí)際的數據，如學(xué)號num，姓名name，性別sex和成績(jì)score等。另一個(gè)域為指針域， 存放下一結點(diǎn)的首地址。鏈表中的每一個(gè)結點(diǎn)都是同一種結構類(lèi)型。例如， 一個(gè)存放學(xué)生學(xué)號和成績(jì)的結點(diǎn)應為以下結構：struct stu{ int num;int score;struct stu *next;} 前兩個(gè)成員項組成數據域，后一個(gè)成員項next構成指針域， 它是一個(gè)指向stu類(lèi)型結構的指針變量。鏈表的基本操作對鏈表的主要操作有以下幾種：1.建立鏈表；2.結構的查找與輸出；3.插入一個(gè)結點(diǎn)；4.刪除一個(gè)結點(diǎn)；下面通過(guò)例題來(lái)說(shuō)明這些操作。[例7.10]建立一個(gè)三個(gè)結點(diǎn)的鏈表，存放學(xué)生數據。 為簡(jiǎn)單起見(jiàn)， 我們假定學(xué)生數據結構中只有學(xué)號和年齡兩項?？删帉?xiě)一個(gè)建立鏈表的函數creat。程序如下：#define NULL 0#define TYPE struct stu#define LEN sizeof (struct stu)struct stu{int num;int age;struct stu *next;};TYPE *creat(int n){struct stu *head,*pf,*pb;int i;for(i=0;i<n;i++){pb=(TYPE*) malloc(LEN);printf("input Number and Age\n");scanf("%d%d",&pb->num,&pb->age);if(i==0)pf=head=pb;else pf->next=pb;pb->next=NULL;pf=pb;}return(head);} 在函數外首先用宏定義對三個(gè)符號常量作了定義。這里用TYPE表示struct stu，用LEN表示sizeof(struct stu)主要的目的是為了在以下程序內減少書(shū)寫(xiě)并使閱讀更加方便。結構stu定義為外部類(lèi)型，程序中的各個(gè)函數均可使用該定義?！ reat函數用于建立一個(gè)有n個(gè)結點(diǎn)的鏈表，它是一個(gè)指針函數，它返回的指針指向stu結構。在creat函數內定義了三個(gè)stu結構的指針變量。head為頭指針，pf 為指向兩相鄰結點(diǎn)的前一結點(diǎn)的指針變量。pb為后一結點(diǎn)的指針變量。在for語(yǔ)句內，用malloc函數建立長(cháng)度與stu長(cháng)度相等的空間作為一結點(diǎn)，首地址賦予pb。然后輸入結點(diǎn)數據。如果當前結點(diǎn)為第一結點(diǎn)(i==0)，則把pb值 (該結點(diǎn)指針)賦予head和pf。如非第一結點(diǎn)，則把pb值賦予pf 所指結點(diǎn)的指針域成員next。而pb所指結點(diǎn)為當前的最后結點(diǎn)，其指針域賦NULL。 再把pb值賦予pf以作下一次循環(huán)準備?！ reat函數的形參n，表示所建鏈表的結點(diǎn)數，作為for語(yǔ)句的循環(huán)次數。圖7.4表示了creat函數的執行過(guò)程。[例7.11]寫(xiě)一個(gè)函數，在鏈表中按學(xué)號查找該結點(diǎn)。TYPE * search (TYPE *head,int n){TYPE *p;int i;p=head;while (p->num!=n && p->next!=NULL)p=p->next; /* 不是要找的結點(diǎn)后移一步*/if (p->num==n) return (p);if (p->num!=n&& p->next==NULL)printf ("Node %d has not been found!\n",n} 本函數中使用的符號常量TYPE與例7.10的宏定義相同，等于struct stu。函數有兩個(gè)形參，head是指向鏈表的指針變量，n為要查找的學(xué)號。進(jìn)入while語(yǔ)句，逐個(gè)檢查結點(diǎn)的num成員是否等于n，如果不等于n且指針域不等于NULL(不是最后結點(diǎn))則后移一個(gè)結點(diǎn)，繼續循環(huán)。如找到該結點(diǎn)則返回結點(diǎn)指針。 如循環(huán)結束仍未找到該結點(diǎn)則輸出“未找到”的提示信息。[例7.12]寫(xiě)一個(gè)函數，刪除鏈表中的指定結點(diǎn)。刪除一個(gè)結點(diǎn)有兩種情況：1. 被刪除結點(diǎn)是第一個(gè)結點(diǎn)。這種情況只需使head指向第二個(gè)結點(diǎn)即可。即head=pb->next。其過(guò)程如圖7.5所示。2. 被刪結點(diǎn)不是第一個(gè)結點(diǎn)，這種情況使被刪結點(diǎn)的前一結點(diǎn)指向被刪結點(diǎn)的后一結點(diǎn)即可。即pf->next=pb->next。其過(guò)程如圖7.6所示。函數編程如下：TYPE * delete(TYPE * head,int num){TYPE *pf,*pb;if(head==NULL) /*如為空表， 輸出提示信息*/{ printf("\nempty list!\n");goto end;}pb=head;while (pb->num!=num && pb->next!=NULL)/*當不是要刪除的結點(diǎn)，而且也不是最后一個(gè)結點(diǎn)時(shí)，繼續循環(huán)*/{pf=pb;pb=pb->next;}/*pf指向當前結點(diǎn)，pb指向下一結點(diǎn)*/if(pb->num==num){if(pb==head) head=pb->next;/*如找到被刪結點(diǎn)，且為第一結點(diǎn)，則使head指向第二個(gè)結點(diǎn)，否則使pf所指結點(diǎn)的指針指向下一結點(diǎn)*/else pf->next=pb->next;free(pb);printf("The node is deleted\n");}elseprintf("The node not been foud!\n");end:return head;} 函數有兩個(gè)形參，head為指向鏈表第一結點(diǎn)的指針變量，num刪結點(diǎn)的學(xué)號。 首先判斷鏈表是否為空，為空則不可能有被刪結點(diǎn)。若不為空，則使pb指針指向鏈表的第一個(gè)結點(diǎn)。進(jìn)入while語(yǔ)句后逐個(gè)查找被刪結點(diǎn)。找到被刪結點(diǎn)之后再看是否為第一結點(diǎn)，若是則使head指向第二結點(diǎn)(即把第一結點(diǎn)從鏈中刪去)，否則使被刪結點(diǎn)的前一結點(diǎn)(pf所指)指向被刪結點(diǎn)的后一結點(diǎn)(被刪結點(diǎn)的指針域所指)。如若循環(huán)結束未找到要刪的結點(diǎn)， 則輸出“末找到”的提示信息。最后返回head值。[例7.13]寫(xiě)一個(gè)函數，在鏈表中指定位置插入一個(gè)結點(diǎn)。在一個(gè)鏈表的指定位置插入結點(diǎn)， 要求鏈表本身必須是已按某種規律排好序的。例如，在學(xué)生數據鏈表中， 要求學(xué)號順序插入一個(gè)結點(diǎn)。設被插結點(diǎn)的指針為pi。 可在三種不同情況下插入。1. 原表是空表，只需使head指向被插結點(diǎn)即可。見(jiàn)圖7.7(a)2. 被插結點(diǎn)值最小，應插入第一結點(diǎn)之前。這種情況下使head指向被插結點(diǎn)，被插結點(diǎn)的指針域指向原來(lái)的第一結點(diǎn)則可。即：pi->next=pb;head=pi; 見(jiàn)圖7.7(b)3. 在其它位置插入，見(jiàn)圖7.7(c)。這種情況下，使插入位置的前一結點(diǎn)的指針域指向被插結點(diǎn)，使被插結點(diǎn)的指針域指向插入位置的后一結點(diǎn)。即為：pi->next=pb;pf->next=pi；4. 在表末插入，見(jiàn)圖7.7(d)。這種情況下使原表末結點(diǎn)指針域指向被插結點(diǎn)，被插結點(diǎn)指針域置為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;/*在第一結點(diǎn)之前插入*/else pf->next=pi;/*在其它位置插入*/pi->next=pb; }else{pb->next=pi;pi->next=NULL;} /*在表末插入*/}return head;} 本函數有兩個(gè)形參均為指針變量，head指向鏈表，pi 指向被插結點(diǎn)。函數中首先判斷鏈表是否為空，為空則使head指向被插結點(diǎn)。表若不空，則用while語(yǔ)句循環(huán)查找插入位置。找到之后再判斷是否在第一結點(diǎn)之前插入，若是則使head 指向被插結點(diǎn)被插結點(diǎn)指針域指向原第一結點(diǎn)，否則在其它位置插入， 若插入的結點(diǎn)大于表中所有結點(diǎn)，則在表末插入。本函數返回一個(gè)指針， 是鏈表的頭指針。 當插入的位置在第一個(gè)結點(diǎn)之前時(shí)， 插入的新結點(diǎn)成為鏈表的第一個(gè)結點(diǎn)，因此head的值也有了改變， 故需要把這個(gè)指針?lè )祷刂髡{函數。[例7.14]將以上建立鏈表，刪除結點(diǎn)，插入結點(diǎn)的函數組織在一起，再建一個(gè)輸出全部結點(diǎn)的函數，然后用main函數調用它們。#define NULL 0#define TYPE struct stu#define LEN sizeof(struct stu)struct stu{int num;int age;struct stu *next;};TYPE * creat(int n){struct stu *head,*pf,*pb;int i;for(i=0;i<n;i++){pb=(TYPE *)malloc(LEN);printf("input Number and Age\n");scanf("%d%d",&pb->num,&pb->age);if(i==0)pf=head=pb;else pf->next=pb;pb->next=NULL;pf=pb;}return(head);}TYPE * delete(TYPE * head,int num){TYPE *pf,*pb;if(head==NULL){ printf("\nempty list!\n");goto end;}pb=head;while (pb->num!=num && pb->next!=NULL){pf=pb;pb=pb->next;}if(pb->num==num){ if(pb==head) head=pb->next;else pf->next=pb->next;printf("The node is deleted\n"); }elsefree(pb);printf("The node not been found!\n");end:return head;}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;else pf->next=pi;pi->next=pb; }else{ pb->next=pi;pi->next=NULL; }}return head;}void print(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;int n,num;printf("input number of node: ");scanf("%d",&n);head=creat(n);print(head);printf("Input the deleted number: ");scanf("%d",&num);head=delete(head,num);print(head);printf("Input the inserted number and age: ");pnum=(TYPE *)malloc(LEN);scanf("%d%d",&pnum->num,&pnum->age);head=insert(head,pnum);print(head);} 本例中，print函數用于輸出鏈表中各個(gè)結點(diǎn)數據域值。函數的形參head的初值指向鏈表第一個(gè)結點(diǎn)。在while語(yǔ)句中，輸出結點(diǎn)值后，head值被改變，指向下一結點(diǎn)。若保留頭指針head， 則應另設一個(gè)指針變量，把head值賦予它，再用它來(lái)替代head。在main函數中，n為建立結點(diǎn)的數目， num為待刪結點(diǎn)的數據域值；head為指向鏈表的頭指針，pnum為指向待插結點(diǎn)的指針。 main函數中各行的意義是：第六行輸入所建鏈表的結點(diǎn)數；第七行調creat函數建立鏈表并把頭指針?lè )祷亟ohead；第八行調print函數輸出鏈表；第十行輸入待刪結點(diǎn)的學(xué)號；第十一行調delete函數刪除一個(gè)結點(diǎn)；第十二行調print函數輸出鏈表；第十四行調malloc函數分配一個(gè)結點(diǎn)的內存空間， 并把其地址賦予pnum;第十五行輸入待插入結點(diǎn)的數據域值；第十六行調insert函數插入pnum所指的結點(diǎn)；第十七行再次調print函數輸出鏈表?！ 倪\行結果看，首先建立起3個(gè)結點(diǎn)的鏈表，并輸出其值；再刪103號結點(diǎn)，只剩下105，108號結點(diǎn)；又輸入106號結點(diǎn)數據， 插入后鏈表中的結點(diǎn)為105，106，108。聯(lián)合“聯(lián)合”也是一種構造類(lèi)型的數據結構。 在一個(gè)“聯(lián)合”內可以定義多種不同的數據類(lèi)型， 一個(gè)被說(shuō)明為該“聯(lián)合”類(lèi)型的變量中，允許裝入該“聯(lián)合”所定義的任何一種數據。 這在前面的各種數據類(lèi)型中都是辦不到的。例如， 定義為整型的變量只能裝入整型數據，定義為實(shí)型的變量只能賦予實(shí)型數據?！ ≡趯?shí)際問(wèn)題中有很多這樣的例子。 例如在學(xué)校的教師和學(xué)生中填寫(xiě)以下表格： 姓 名 年 齡 職 業(yè) 單位 “職業(yè)”一項可分為“教師”和“學(xué)生”兩類(lèi)。 對“單位”一項學(xué)生應填入班級編號，教師應填入某系某教研室。 班級可用整型量表示，教研室只能用字符類(lèi)型。 要求把這兩種類(lèi)型不同的數據都填入“單位”這個(gè)變量中， 就必須把“單位”定義為包含整型和字符型數組這兩種類(lèi)型的“聯(lián)合”?！ ?#8220;聯(lián)合”與“結構”有一些相似之處。但兩者有本質(zhì)上的不同。在結構中各成員有各自的內存空間， 一個(gè)結構變量的總長(cháng)度是各成員長(cháng)度之和。而在“聯(lián)合”中，各成員共享一段內存空間， 一個(gè)聯(lián)合變量的長(cháng)度等于各成員中最長(cháng)的長(cháng)度。應該說(shuō)明的是， 這里所謂的共享不是指把多個(gè)成員同時(shí)裝入一個(gè)聯(lián)合變量?jì)龋?而是指該聯(lián)合變量可被賦予任一成員值，但每次只能賦一種值， 賦入新值則沖去舊值。如前面介紹的“單位”變量， 如定義為一個(gè)可裝入“班級”或“教研室”的聯(lián)合后，就允許賦予整型值（班級)或字符串（教研室)。要么賦予整型值，要么賦予字符串，不能把兩者同時(shí)賦予它。聯(lián)合類(lèi)型的定義和聯(lián)合變量的說(shuō)明一個(gè)聯(lián)合類(lèi)型必須經(jīng)過(guò)定義之后， 才能把變量說(shuō)明為該聯(lián)合類(lèi)型。一、聯(lián)合的定義定義一個(gè)聯(lián)合類(lèi)型的一般形式為：union 聯(lián)合名{成員表};成員表中含有若干成員，成員的一般形式為： 類(lèi)型說(shuō)明符 成員名 成員名的命名應符合標識符的規定。例如：union perdata{int class;char office[10];}; 定義了一個(gè)名為perdata的聯(lián)合類(lèi)型，它含有兩個(gè)成員，一個(gè)為整型，成員名為class；另一個(gè)為字符數組，數組名為office。聯(lián)合定義之后，即可進(jìn)行聯(lián)合變量說(shuō)明，被說(shuō)明為perdata類(lèi)型的變量，可以存放整型量class或存放字符數組office。二、聯(lián)合變量的說(shuō)明 聯(lián)合變量的說(shuō)明和結構變量的說(shuō)明方式相同， 也有三種形式。即先定義，再說(shuō)明；定義同時(shí)說(shuō)明和直接說(shuō)明。以perdata類(lèi)型為例，說(shuō)明如下：union perdata{int class;char officae[10];};union perdata a,b; /*說(shuō)明a,b為perdata類(lèi)型*/或者可同時(shí)說(shuō)明為：union perdata{ int class;char office[10]; }a,b;或直接說(shuō)明為： union{ int class;char office[10]; }a,b經(jīng)說(shuō)明后的a,b變量均為perdata類(lèi)型。 它們的內存分配示意圖如圖7—8所示。a,b變量的長(cháng)度應等于 perdata 的成員中最長(cháng)的長(cháng)度， 即等于office數組的長(cháng)度，共10個(gè)字節。從圖中可見(jiàn)，a,b變量如賦予整型值時(shí)，只使用了2個(gè)字節，而賦予字符數組時(shí)，可用10個(gè)字節。聯(lián)合變量的賦值和使用 對聯(lián)合變量的賦值，使用都只能是對變量的成員進(jìn)行。 聯(lián)合變量的成員表示為： 聯(lián)合變量名.成員名 例如，a被說(shuō)明為perdata類(lèi)型的變量之后，可使用 a.class a.office 不允許只用聯(lián)合變量名作賦值或其它操作。 也不允許對聯(lián)合變量作初始化賦值，賦值只能在程序中進(jìn)行。還要再強調說(shuō)明的是，一個(gè)聯(lián)合變量， 每次只能賦予一個(gè)成員值。換句話(huà)說(shuō)，一個(gè)聯(lián)合變量的值就是聯(lián)合變員的某一個(gè)成員值。[例7.15]設有一個(gè)教師與學(xué)生通用的表格，教師數據有姓名，年齡，職業(yè)，教研室四項。學(xué)生有姓名，年齡，職業(yè)，班級四項。編程輸入人員數據， 再以表格輸出。main(){struct{char name[10];int age;char job;union{int class;char office[10];} depa;}body[2];int n,i;for(i=0;i<2;i++){printf("input name,age,job and department\n");scanf("%s %d %c",body[i].name,&body[i].age,&body[i].job);if(body[i].job==‘s‘)scanf("%d",&body[i].depa.class);elsescanf("%s",body[i].depa.office);}printf("name\tage job class/office\n");for(i=0;i<2;i++){if(body[i].job==‘s‘)printf("%s\t%3d %3c %d\n",body[i].name,body[i].age,body[i].job,body[i].depa.class);elseprintf("%s\t%3d %3c %s\n",body[i].name,body[i].age,body[i].job,body[i].depa.office);}} 本例程序用一個(gè)結構數組body來(lái)存放人員數據， 該結構共有四個(gè)成員。其中成員項depa是一個(gè)聯(lián)合類(lèi)型， 這個(gè)聯(lián)合又由兩個(gè)成員組成，一個(gè)為整型量class，一個(gè)為字符數組office。在程序的第一個(gè)for語(yǔ)句中，輸入人員的各項數據，先輸入結構的前三個(gè)成員name,age和job，然后判別job成員項，如為"s"則對聯(lián)合depa·class輸入(對學(xué)生賦班級編號)否則對depa·office輸入(對教師賦教研組名)?！ ≡谟胹canf語(yǔ)句輸入時(shí)要注意，凡為數組類(lèi)型的成員，無(wú)論是結構成員還是聯(lián)合成員，在該項前不能再加"&"運算符。如程序第18行中body[i].name是一個(gè)數組類(lèi)型，第22行中的body[i].depa.office也是數組類(lèi)型，因此在這兩項之間不能加"&"運算符。程序中的第二個(gè)for語(yǔ)句用于輸出各成員項的值：本章小結1. 結構和聯(lián)合是兩種構造類(lèi)型數據，是用戶(hù)定義新數據類(lèi)型的重要手段。結構和聯(lián)合有很多的相似之處，它們都由成員組成。成員可以具有不同的數據類(lèi)型。成員的表示方法相同。都可用三種方式作變量說(shuō)明。2. 在結構中，各成員都占有自己的內存空間，它們是同時(shí)存在的。一個(gè)結構變量的總長(cháng)度等于所有成員長(cháng)度之和。在聯(lián)合中，所有成員不能同時(shí)占用它的內存空間，它們不能同時(shí)存在。聯(lián)合變量的長(cháng)度等于最長(cháng)的成員的長(cháng)度。3. “.”是成員運算符，可用它表示成員項，成員還可用“->”運算符來(lái)表示。4. 結構變量可以作為函數參數，函數也可返回指向結構的指針變量。而聯(lián)合變量不能作為函數參數，函數也不能返回指向聯(lián)合的指針變量。但可以使用指向聯(lián)合變量的指針，也可使用聯(lián)合數組。5. 結構定義允許嵌套，結構中也可用聯(lián)合作為成員，形成結構和聯(lián)合的嵌套。6. 鏈表是一種重要的數據結構，它便于實(shí)現動(dòng)態(tài)的存儲分配。本章介紹是單向鏈表，還可組成雙向鏈表，循環(huán)鏈表等。
聯(lián)系客服
