計算機C語言教程第10章結(jié)構(gòu)體和共同體

1、結(jié)構(gòu)體與共用體結(jié)構(gòu)體與共用體10.1 結(jié)構(gòu)體類型的定義結(jié)構(gòu)體類型的定義 結(jié)構(gòu)體由若干成員組成，各成員可有不同的類型。結(jié)構(gòu)體由若干成員組成，各成員可有不同的類型。在程序中要使用結(jié)構(gòu)體類型，必須先對結(jié)構(gòu)體的組在程序中要使用結(jié)構(gòu)體類型，必須先對結(jié)構(gòu)體的組成進行描述。例如，學(xué)生信息可用結(jié)構(gòu)體描述為：成進行描述。例如，學(xué)生信息可用結(jié)構(gòu)體描述為： struct studentint num ; /*學(xué)號*/char name20;/*姓名*/char sex; /* 性別*/int age; /*年齡*/float score; /*成績*/char addr40; /*家庭住址*/; 需要特別指出的是“

2、struct student”是程序設(shè)計者自己定義的類型，它與系統(tǒng)預(yù)定義的標(biāo)準(zhǔn)類型(如int、char等)一樣，可以用來定義變量，使變量具有struct student類型。例如： struct student st1,st220; 分別定義了struct student結(jié)構(gòu)體類型的變量st1和struct student結(jié)構(gòu)體類型的數(shù)組變量st2。其中，關(guān)鍵字struct引入結(jié)構(gòu)體類型的定義。struct之后任選的標(biāo)識符是結(jié)構(gòu)體類型的名字。用花括號括起來的是結(jié)構(gòu)體成員說明。 上例說明結(jié)構(gòu)體類型struct student有6個成員，分別命名為num、name、sex、age、score和ad

3、dr。這6個成員分別表示學(xué)生的學(xué)號、姓名、性別、年齡、成績和家庭住址，顯然它們的類型是不同的。結(jié)構(gòu)體類型的定義形式為：struct 結(jié)構(gòu)體類型名結(jié)構(gòu)體類型名成員說明表列成員說明表列;其中，花括號內(nèi)的內(nèi)容是該結(jié)構(gòu)體類型的成員說明，每個成員說明的形式為：類型名類型名 成員名成員名;實際上，凡是相關(guān)的若干數(shù)據(jù)對象都可組合成一個結(jié)構(gòu)體，在一個結(jié)構(gòu)體名下進行管理。例如，由日、月、年組成的結(jié)構(gòu)體類型為：struct dateint day;int month;int year;又如，某職工信息結(jié)構(gòu)體類型為：struct personchar name20;/*姓名*/char address40;/*地址

4、*/ float salary;/*工資*/float cost;/*扣款*/struct date hiredate;/*聘任日期*/;其中，結(jié)構(gòu)體類型struct person含有一個結(jié)構(gòu)體類型成員hiredate。該例子說明結(jié)構(gòu)體類型可以嵌套定義，即一個結(jié)構(gòu)體類型中的某些成員又是其他結(jié)構(gòu)體類型。但是這種嵌套不能包含自身，即不能由自己定義自己。結(jié)構(gòu)體類型說明中，詳細(xì)列出了一個結(jié)構(gòu)體的組成情況、結(jié)構(gòu)體的各成員名及其類型。結(jié)構(gòu)體類型說明了一個數(shù)據(jù)結(jié)構(gòu)的“模式”，但不定義“實物”，并不要求分配實際的存儲空間。程序要實際使用結(jié)構(gòu)體，必須定義結(jié)構(gòu)體變量。編譯程序在為結(jié)構(gòu)體變量分配存儲空間時，其中各成

5、員的存儲格式及其意義與結(jié)構(gòu)體類型保持一致。 10.2 結(jié)構(gòu)體類型變量結(jié)構(gòu)體類型變量 要定義一個結(jié)構(gòu)體類型的變量，可采取以下要定義一個結(jié)構(gòu)體類型的變量，可采取以下3種方法。種方法。 10.2.1 結(jié)構(gòu)體類型變量的定義 1. 先定義結(jié)構(gòu)體類型，再定義變量如上面已定義了一個結(jié)構(gòu)體類型struct student，可以用它來定義變量。例如：struct student student1,student2;定義student1和student2為struct student類型變量，即它們具有struct student類型的結(jié)構(gòu)體變量。 應(yīng)當(dāng)注意，將一個變量定義為標(biāo)準(zhǔn)類型(基本數(shù)據(jù)類型)與定義為結(jié)構(gòu)體

6、類型不同之處在于：后者不僅要求指定變量為結(jié)構(gòu)體類型，而且要求指定為某一特定的結(jié)構(gòu)體類型。例如，對struct student，不能只指定為struct型而不指定結(jié)構(gòu)體名。而在定義變量為整型時，只需指定為int型即可。 例如：struct studentint num;char name20;char sex;int age;float scorechar addr40;student1,student2;2. 在定義類型的同時定義變量在定義類型的同時定義變量：struct結(jié)構(gòu)體類型名結(jié)構(gòu)體類型名成員說明表列成員說明表列變量名表列變量名表列;它的作用與前面定義的相同。即定義了兩個struct s

7、tudent類型的變量student1和student2。這種定義方法的一般形式為：3. 直接定義結(jié)構(gòu)體類型變量直接定義結(jié)構(gòu)體類型變量其一般形式為：struct 成員說明表列成員說明表列變量名表列變量名表列;即在結(jié)構(gòu)體定義時不出現(xiàn)結(jié)構(gòu)體類型名，這種形式雖然簡單，但不能在再需要時，使用所定義的結(jié)構(gòu)體類型。 (1)類型與變量是不同的概念，不要混同。對結(jié)構(gòu)體變量來說，在定義時一般先定義一個結(jié)構(gòu)體類型，然后定義變量為該類型。只能對變量賦值、存取或運算，而不能對一個類型賦值、存取或運算。在編譯時，對類型是不分配存儲空間的，只對變量分配存儲空間。 關(guān)于結(jié)構(gòu)體類型，有幾點需要說明：關(guān)于結(jié)構(gòu)體類型，有幾點需要

8、說明：(2)對結(jié)構(gòu)體中的成員，可以單獨使用，它的作用與地位相當(dāng)于普通變量。 (3)成員也可以是一個結(jié)構(gòu)體變量。例如：struct date int month; int day; int year; ; struct member int num; char name20; char sex; int age; struct date birthday;/*成員變量是一個結(jié)構(gòu)體變量*/ char addr40; stu1,stu2; (4)成員名可以與程序中的其他變量名相同，兩者不代表同一對象。例如，程序中可以另定義一個變量num，它與struct member中的num是兩回事，互不干擾。

9、先定義一個struet date結(jié)構(gòu)體類型，它包括3個成員：month、day、year，分別代表月、日、年。然后在定義struet member結(jié)構(gòu)體類型時，成員birthday的類型定義為struet date類型。已定義的類型struct date與其他類型(如int、char)一樣可以用來定義成員的類型。10.2.2 結(jié)構(gòu)體變量的使用 引用一個結(jié)構(gòu)體變量有兩種方式：通過結(jié)構(gòu)體變量名和通過指向結(jié)構(gòu)體的指針變量。與之對應(yīng)的，引用結(jié)構(gòu)體成員的標(biāo)記形式也有兩種，分別用運算符“”和“”來標(biāo)記。(1)由結(jié)構(gòu)體變量名引用其成員的標(biāo)記形式為：結(jié)構(gòu)體變量名結(jié)構(gòu)體變量名.成員名成員名例如，stu1.num

10、表示引用結(jié)構(gòu)體變量stu1中的num成員，因該成員的類型為int型的， 所以可以對它施行任何int型變量可以施行的運算。例如：stu1.num20312;(2)由指向結(jié)構(gòu)體的指針變量引用結(jié)構(gòu)體成員的標(biāo)記形式為：指針變量名指針變量名-成員名成員名例如，如下變量定義：struct nodefloat x,y;p,u,*pt;定義了兩個結(jié)構(gòu)體變量p、u和一個指向該結(jié)構(gòu)體的指針變量pt，分析以下語句：p.x=12.2;p.y=24.3;pt=&u;pt-x23.7;pt-y=3.5; 語句“pt&u;”使pt指向結(jié)構(gòu)體變量u，可用pt-x和pt-y訪問結(jié)構(gòu)體變量u的兩個成員。上述語句執(zhí)行情況可用圖10

11、.1描述各變量之間的關(guān)系。23.7 3.512.2 24.3ptup圖10.1 通過指向結(jié)構(gòu)體的指針引用結(jié)構(gòu)體 上述例子說明結(jié)構(gòu)體的成員可以像普通變量一樣使用。根據(jù)其類型決定其所有合法的運算。 如果結(jié)構(gòu)體成員本身又是結(jié)構(gòu)體類型的，則可繼續(xù)使用成員運算符取結(jié)構(gòu)體成員的結(jié)構(gòu)體成員，逐級向下，引用最低一級的成員。程序能對最低一級的成員進行賦值或存取;例如，對stu1某些成員的訪問： stu1.birthday.day=23; stu1.birthday.month=8; stu1.birthday.year=2003;在早期的c語言中，程序只能對結(jié)構(gòu)體變量(包括結(jié)構(gòu)體變量的結(jié)構(gòu)體成員)取地址運算，不

12、允許對結(jié)構(gòu)體進行賦值運算。ansi c已經(jīng)取消了這個限制，允許結(jié)構(gòu)體值賦給相同類型的結(jié)構(gòu)體變量。程序也能對結(jié)構(gòu)體的最低一級的成員進行其他運算，包括取地址運算，引用成員的地址。例如： scanf(”%”,&stu1.age);10.2.3 結(jié)構(gòu)體變量的初始化 結(jié)構(gòu)體變量和其他變量一樣，可以在定義變量的同時進行初始化。1. 對外部存儲類型的結(jié)構(gòu)體變量進行初始化例10.1 分析下列程序的輸出結(jié)果。#include struct student long num;char name20;char sex;char addr40;a=3021103, ”jiang linpad”,m, ”123 sha

13、oshan road”;main( )printf(”no:%ldnname:%snsex:%cnaddress:%sn”,a.num,,a.sex,a.addr);程序運行結(jié)果如下：no:3021103name:jiang linpansex;maddress:123 shaoshan road2. 在函數(shù)內(nèi)部的結(jié)構(gòu)體變量進行初始化上面例子的定義部分可以放到main函數(shù)中。程序如下：main( ) static struct student long hum;char name20;char sex;char addr40;a=3021103, ”jiang linpan”,m,

14、 ”123 shaoshan road”;printf(”no:%ldnname:%snsex:%cnaddress:%sn”,a.num,,a.sex,a.addr);程序運行結(jié)果與上面例子程序相同。注意,對自動結(jié)構(gòu)體變量不能在定義時賦初值,只能在函數(shù)執(zhí)行時用賦值語句對各成員分別賦值。 10.2.4 結(jié)構(gòu)體變量的輸入和輸出 c語言不能把一個結(jié)構(gòu)體變量作為一個整體進行輸入或輸出,應(yīng)該按成員變量輸入輸出。例如,若有一個結(jié)構(gòu)體變量：struct char name12;char addr18;long num;stud= ”wang dawei”, ”125 beijing road”

15、,3021118; 變量stud在內(nèi)存中存儲情況如圖10.2所示。是按成員變量存放的。wa n gd a w e i 01 2 5b e i j i n gr o a d 03021118 name12 addr18 圖10.2 結(jié)構(gòu)體變量在內(nèi)存中的存儲情況 為兩個字符串?dāng)?shù)據(jù)和一個長整型數(shù)據(jù),因此輸出stud變量,應(yīng)該使用如下方式：printf(”%s,%s,%1dn”,,stud.addr,stud.num);輸入stud變量的各成員值,則用：scanf(”%s%s%ld”,,stud.addr,&stud.num);由于成員項name和addr是字符數(shù)組

16、,按s字符串格式輸入,故不要寫成&和&stud.addr,而num成員是long型,故應(yīng)當(dāng)用&stud.num。 當(dāng)然也可以用gets函數(shù)和puts函數(shù)輸入和輸出一個結(jié)構(gòu)體變量中的字符數(shù)組成員。例如：gets();puts();gets函數(shù)輸入一個字符串給,puts函數(shù)輸出數(shù)組中的字符串。 10.3 10.3 結(jié)構(gòu)體類型數(shù)組結(jié)構(gòu)體類型數(shù)組 一個結(jié)構(gòu)體變量中可以存放一組數(shù)據(jù)(如一個學(xué)生的學(xué)號、姓名、成績等數(shù)據(jù))。如果有10個學(xué)生的數(shù)據(jù)需要參加運算和處理,顯然應(yīng)該用數(shù)組,這就是結(jié)構(gòu)體數(shù)組。結(jié)構(gòu)體數(shù)組與以前介紹

17、過的數(shù)值型數(shù)組不同之處在于每個數(shù)組元素都是一個結(jié)構(gòu)體類型的數(shù)據(jù),它們都分別包括各個成員項。10.3.1 結(jié)構(gòu)體類型數(shù)組的定義與定義結(jié)構(gòu)體變量的方法一樣,在結(jié)構(gòu)體變量名之后指定元素個數(shù),就能定義結(jié)構(gòu)體數(shù)組。例如：struct student students30;struct person employees100;struct char name20;int num;float price;float quantity;parts200; 以上定義了一個數(shù)組students,它有30個元素,每個元素的類型為struct student的結(jié)構(gòu)體類型。定義數(shù)組employees,有100個元素,每

18、個元素是struct person結(jié)構(gòu)體類型。定義數(shù)組parts,有200個元素,每個元素也是一個結(jié)構(gòu)體類型。它們都是結(jié)構(gòu)體數(shù)組,分別用于表示一個班級的學(xué)生、一個部門的職工、一個倉庫的產(chǎn)品。如同元素為標(biāo)準(zhǔn)數(shù)據(jù)類型的數(shù)組一樣,結(jié)構(gòu)體數(shù)組各元素在內(nèi)存中也按順序存放,也可初始化,對結(jié)構(gòu)體數(shù)組元素的訪問也要利用元素的下標(biāo)。特別地,訪問結(jié)構(gòu)體數(shù)組元素的成員的標(biāo)記方法為：例如,訪問parts數(shù)組元素的成員：parts10.price=37.5;scanf(”%s”,);結(jié)構(gòu)體數(shù)組名結(jié)構(gòu)體數(shù)組名元素下標(biāo)元素下標(biāo)結(jié)構(gòu)體成員名結(jié)構(gòu)體成員名10.3.2 結(jié)構(gòu)體類型數(shù)組的初始化 在對結(jié)構(gòu)體數(shù)組

19、初始化時,要將每個元素的數(shù)據(jù)分別用花括號括起來。例如：struct student char name20;long num;int age;char sex;float score;students5; ”zhu dongfen”,3021101,18,m,93, ”zhang fachong”,3021102,19,m,90.5, ”wang peng”,3021103,16,m,85, ”zhan hong”,3021104,16,f,95, ”li linggou”,3021105,20,f,67; 這樣,在編譯時將一個花括號中的數(shù)據(jù)賦給一個元素,即將第一個花括弧中的數(shù)據(jù)送給stude

20、nts0,第二個花括弧內(nèi)的數(shù)據(jù)送給students1,。如果賦初值的數(shù)據(jù)組的個數(shù)與所定義的數(shù)組元素相等,則數(shù)組元素個數(shù)可以省略不寫。這和前面有關(guān)章節(jié)介紹的數(shù)組初始化相類似。此時系統(tǒng)會根據(jù)初始化時提供的數(shù)據(jù)組的個數(shù)自動確定數(shù)組的大小。如果提供的初始化數(shù)據(jù)組的個數(shù)少于數(shù)組元素的個數(shù),則方括弧內(nèi)的元素個數(shù)不能省略,例如： struct studentstudents3:,;只對前3個元素賦初值,其他元素未賦初值,系統(tǒng)將對數(shù)值型成員賦以零,對字符型數(shù)據(jù)賦以“空”串即“0”。10.3.3 結(jié)構(gòu)體數(shù)組的使用 一個結(jié)構(gòu)體數(shù)組的元素相當(dāng)于一個結(jié)構(gòu)體變量。引用結(jié)構(gòu)體數(shù)組元素有如下規(guī)則：(1)引用某一元素的一個成

21、員。例如：studentsi.num這是序號為i的數(shù)組元素中的num成員。如果數(shù)組已如上初始化,且i=2,則相當(dāng)于students2.num,其值為3021103。 (2)可以將一個結(jié)構(gòu)體數(shù)組元素賦給同一結(jié)構(gòu)體類型數(shù)組中的另一個元素,或賦給同一類型的變量。例如：struct student students3,student1;現(xiàn)在定義了一個結(jié)構(gòu)體數(shù)組students,它有3個元素,又定義了一個結(jié)構(gòu)體變量student1,則下面的賦值合法。student1=students0;students2=students1;students1=student1,(3)不能把結(jié)構(gòu)體數(shù)組元素作為一個整體直

22、接進行輸入或輸出,只能以單個成員對象進行輸入輸出。例如：scanf(”%s”,);printff(”%ld”,&students0.num);10.4 10.4 結(jié)構(gòu)體與函數(shù)結(jié)構(gòu)體與函數(shù)10.4.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編譯都允許用結(jié)構(gòu)體變量作為函數(shù)參數(shù),即直接將實參結(jié)構(gòu)體變量的各個成員的值全部傳遞給形參的結(jié)構(gòu)體變量。當(dāng)然,實參和形參的結(jié)構(gòu)體變量類型應(yīng)當(dāng)完全一致。 例10.2 輸入三個學(xué)生的信息并輸出，其中輸出的功能用一函數(shù)實現(xiàn)。#includ

23、e #include struct stud_type char name20;long num;int age;char sex;main( ) void list(struct stud_type student);struct stud_type student3,*p;int i;for(i=0,p=student;iname,&p-num,&p-age,&p-sex);for(i=0;inum,p-name,p-sex,p-score10.4.2指向結(jié)構(gòu)體變量的指針作為函數(shù)參數(shù) 上一節(jié)介紹的用結(jié)構(gòu)體變量作為函數(shù)參數(shù)，這是ansi c新標(biāo)準(zhǔn)的擴充功能。在過去的c版本中不能這樣用，而是通

24、過指針來傳遞結(jié)構(gòu)體變量的地址給形參，再通過形參指針變量引用結(jié)構(gòu)體變量中成員的值。例10.3 有一結(jié)構(gòu)體變量stu，內(nèi)含學(xué)生學(xué)號、姓名和3門課的成績。要求在main函數(shù)中給變量賦值，在另一函數(shù)print中將它們打印輸出。#include #include struct studentlong num;char name20;float score3;main( )void print(struct student*);struct student stu;stu.num=3021210;strcpy(, ”li dong”);stu.score0=67.5;stu.score1=

25、89;stu.score2=78.6;print(&stu);void print(struct student*p)printf(”%ldn%sn%fn%fn%fn”,p-num,p-name,p-score0,p-score1,p-score2);printf(”n”);程序運行結(jié)果如下：3021210li dong67.50000089.00000078.599998 struct student被定義為外部類型，這樣同一文件中的各個函數(shù)都可以用它來定義變量的類型。main函數(shù)中的stu變量定義為struct student類型，printf函數(shù)中的形參p被定義為指向struct stu

26、dent類型數(shù)據(jù)的指針變量。在main函數(shù)中對stu的各成員賦值。注意在調(diào)用print函數(shù)時，用&stu作實參，&stu是結(jié)構(gòu)體變量stu的地址。在調(diào)用函數(shù)時將該地址傳遞給形參p(p是指針變量)。這樣p就指向stu。在printf函數(shù)中輸出p所指向的結(jié)構(gòu)體變量的各個成員值，它們也就是stu的成員值。main函數(shù)中的對各成員賦值也可以改用scan函數(shù)輸入。即：scanf(”%ld%s%f%f%f”,&stu.num,,&stu.score0,%stu.score1,&stu.score2);輸入時用下面形式輸入：3021210 lidong 67.5 89 78.6注意，輸入項表

27、列中前沒有“&”符號，因為是字符數(shù)組名本身代表地址，不應(yīng)寫成&。ansic允許用整個結(jié)構(gòu)體作為函數(shù)的參數(shù)傳遞，但是必須保證實參與形參的類型相同。上例中的main函數(shù)中的最后一行調(diào)用printf函數(shù)，也可以改用：print(stu);即實參改用結(jié)構(gòu)體變量(而不是指針)。同時print函數(shù)也應(yīng)相應(yīng)改為：void print(struct student stud)printf(”%ldn%sn%fn%fn%fn”,stu.num,,stu.score0,stu.score1,slu.score2);printf(”n”); 把一個完整

28、的結(jié)構(gòu)體變量作為參數(shù)傳遞，雖然合法，但是要將全部成員值一個一個傳遞，費時間又費空間，開銷大。如果結(jié)構(gòu)體類型中的成員很多，或者有一些成員是數(shù)組，則程序運行效率會大大降低。在這種情況下，用指針做函數(shù)參數(shù)比較好，能提高運行效率。 10.4.3 函數(shù)的返回值為結(jié)構(gòu)體類型函數(shù)的返回值可以是結(jié)構(gòu)體類型。例如，定義了結(jié)構(gòu)體數(shù)組：struct student stud100;數(shù)據(jù)輸入可由如下形式的語句實現(xiàn)：for(i=0;i100;i+)studi=input( );函數(shù)input( )的功能是輸入一個結(jié)構(gòu)體數(shù)據(jù)，并將輸入結(jié)構(gòu)體數(shù)據(jù)作為返回值，返回給第i個學(xué)生記錄，實現(xiàn)第i個學(xué)生的數(shù)據(jù)輸入。函數(shù)定義如下：st

29、ruct student input( )/*輸入一個學(xué)生的數(shù)據(jù)*/int i;struct student stud;scanf(”%ld” ,&stud.no);/*輸入學(xué)號*/gets();/*輸入學(xué)生姓名*/for(i=0;i結(jié)構(gòu)體成員名結(jié)構(gòu)體成員名例如,通過pd引用結(jié)構(gòu)體變量date3的day成員,寫成pd-day,引用date3的month,寫在pd-month等?！?指針變量”表示指針變量所指對象,所以通過指向結(jié)構(gòu)體的指針變量引用結(jié)構(gòu)體成員也可寫成以下形式：(*指針變量指針變量)結(jié)構(gòu)體成員名結(jié)構(gòu)體成員名這里圓括號是必須的,因為運算符“*”的優(yōu)先級低于運算符“.”

30、。從表面上看,*pd.day等價于*(pd.day),但這兩種書寫形式都是錯誤的。采用這種標(biāo)記方法,通過pd引用date3的成員可寫成(*pd).day、(*pd).month、(*pd).year。但是很少場合采用這種標(biāo)記方法,習(xí)慣都采用運算符“-”來標(biāo)記。例10.4 寫出下列程序的執(zhí)行結(jié)果。#include #include main( ) struct studentlong num;char name20;char sex;float score;struct student stu1,*p;p=&stu1;stu1.num=3021118;strcpy(, ”li

31、lin”);stu1.sexm;stu1.score=91.5;printf(”no:%ldnname:%snsex:%cnscore:%fn”,stu1.num,,stu1.sex,stu1.score);printf(”no:%ldnname:%snsex:%cnscore:%fn”,(*p).num,(*p).name,(*p).sex,(*p).score); 在主函數(shù)中定義了struct student類型,然后定義一個struct student類型的變量stu1。同時又定義了一個指針變量p,它指向struct student結(jié)構(gòu)體類型。在函數(shù)的執(zhí)行部分,將stu

32、1的起始地址賦給指針變量p,也就是使p指向stu1,然后對stu1中的成員num,其余類推。第二個printf函數(shù)也是用來輸出stu1的各成員的值,但使用的是(*p).num這樣的形式。 程序運行結(jié)果如下：no:3021118name:li linsex:mscore:91.500000no:302lll8name:li linsex:mscore:91.500000可見兩個printf函數(shù)輸出的結(jié)果是相同的。上面程序中最后一個printf函數(shù)中的輸出項列表可改為：p-num,p-name,p-sex,p-score2指向結(jié)構(gòu)體數(shù)組元素的指針一個指針變量可以指向一個結(jié)構(gòu)體數(shù)組元素,也就是將該結(jié)

33、構(gòu)體數(shù)組的數(shù)組元素地址賦給此指針變量。例如：struct int a;float b;arr3,*p;p=arr; 此時使p指向arr數(shù)組的第一個元素,“p=arr;”等價于“p=&arr0”。若執(zhí)行“p+;”則此時指針變量p此時指向arr1,指針指向關(guān)系如圖10.3所示。p p+ arr0arr1arr2圖10.3 指向結(jié)構(gòu)體數(shù)組元素的指針10.5.2 鏈表 到目前為止,程序中的變量都是通過定義引入的,這類變量在其存在期間,它固有的數(shù)據(jù)結(jié)構(gòu)是不能改變的。本節(jié)將介紹系統(tǒng)程序中經(jīng)常使用的動態(tài)數(shù)據(jù)結(jié)構(gòu),其中包括的變量不是通過變量定義建立的,而由程序根據(jù)需要向系統(tǒng)申請獲得。動態(tài)數(shù)據(jù)結(jié)構(gòu)由一組數(shù)據(jù)對象

34、組成,其中數(shù)據(jù)對象之間具有某種特定的關(guān)系。動態(tài)數(shù)據(jù)結(jié)構(gòu)最顯著的特點是它包含的數(shù)據(jù)對象個數(shù)及其相互關(guān)系可以按需要改變。經(jīng)常遇到的動態(tài)數(shù)據(jù)結(jié)構(gòu)有鏈表、樹、圖等,限于程序設(shè)計初學(xué)者,在此只介紹其中簡單的單向鏈表動態(tài)數(shù)據(jù)結(jié)構(gòu)。鏈表概述 鏈表是最簡單也是最常用的一種動態(tài)數(shù)據(jù)結(jié)構(gòu)。它是對動態(tài)獲得的內(nèi)存進行組織的一種結(jié)構(gòu)。我們知道,用數(shù)組存放數(shù)據(jù)時,必須事先定義固定的長度(即數(shù)組元素個數(shù))。比如,有的班級有50人,而有的班只有30人,如果要用同一個數(shù)組先后存放不同班級的學(xué)生數(shù)據(jù),則必須定義長度為50的數(shù)組。如果事先難以確定一個班的最多人數(shù),則必須把數(shù)組定義得足夠大,以能存放任何班級的學(xué)生數(shù)據(jù)

35、。顯然這將會浪費內(nèi)存空間。鏈表則沒有這種缺限,它根據(jù)需要開辟內(nèi)存單元。 圖10.4表示最簡單的一種鏈表(單向鏈表)的結(jié)構(gòu)。鏈表有一個頭指針變量,圖中以head表示,它存放一個地址。該地址指向一個鏈表元素。鏈表中每一個元素稱為結(jié)點,每個結(jié)點都應(yīng)包括兩部分：一是用戶需要用的實際數(shù)據(jù),二是下一個結(jié)點的地址?？梢钥闯?head指向第一個結(jié)點,第一個結(jié)點又指向第二個結(jié)點,一直到最后一個結(jié)點,該結(jié)點不再指向其他結(jié)點,它稱為表尾,它的地址部分放一個null(表示“空地址”)。鏈表到此結(jié)束。head2101圖10.4 鏈表結(jié)構(gòu)示意圖 由圖10.4所示,一個結(jié)點的后繼結(jié)點位置由結(jié)點所包含的指針成員所指,鏈表中各

36、結(jié)點在內(nèi)存中的存放位置是可以任意的。如果尋找鏈表中的某一個結(jié)點,必須從鏈表頭指針?biāo)傅牡谝粋€結(jié)點開始,順序查找。另外,圖10.4所示的鏈表結(jié)構(gòu)是單向的,即每個結(jié)點只知道它的后繼結(jié)點位置,而不能知道它的前驅(qū)結(jié)點。在某些應(yīng)用中,要求鏈表的每個結(jié)點都能方便地知道它的前驅(qū)結(jié)點和后繼結(jié)點,這種鏈表的表示應(yīng)設(shè)有兩個指針成員,分別指向它的前驅(qū)和后繼結(jié)點,這種鏈表稱為雙向鏈表。為適應(yīng)不同問題的特定要求,鏈表結(jié)構(gòu)也有多種變形。 head2101鏈表與數(shù)組的主要區(qū)別是:(1)數(shù)組的元素個數(shù)是固定的,而組成鏈表的結(jié)點個數(shù)可按需要增減;(2)數(shù)組元素的存貯單元在數(shù)組定義時分配,鏈表結(jié)點的存貯單元在程序執(zhí)行時動態(tài)向系統(tǒng)

37、申請;(3)數(shù)組中的元素順序關(guān)系由元素在數(shù)組中的位置(即下標(biāo))確定,鏈表中的結(jié)點順序關(guān)系由結(jié)點所包含的指針來體現(xiàn)。對于不是固定長度的列表,用可能最大長度的數(shù)組來描述,會浪費許多內(nèi)存空間。(4)對于元素的插入、刪除操作非常頻繁的列表處理場合,用數(shù)組表示列表也是不適宜的。若用鏈表實現(xiàn),會使程序結(jié)構(gòu)清晰,處理的方法也較為簡便。例如在一個列表中間要插入一個新元素,如用數(shù)組表示列表,為完成插入工作,插入處之后的全部元素必須向后移動一個位置,空出的位置用于存儲新元素。對于在一個列表中刪除一個元素情況,為保持取組中元素相對位置連續(xù)遞增,刪除處之后的元素都得向前移一個位置。如用鏈表實現(xiàn)列表,鏈表結(jié)點的插入或刪

38、除操作不再需要移動結(jié)點,只需改變相關(guān)的結(jié)點中的后繼結(jié)點指針的值即可,與結(jié)點的實際存儲位置無關(guān)。操作細(xì)節(jié)見有關(guān)鏈表插入和刪除操作的程序例子。 鏈表的結(jié)點是結(jié)構(gòu)體變量,它包含若干成員,其中有些成員可以是任何類型,如標(biāo)準(zhǔn)類型、數(shù)組類型、結(jié)構(gòu)體類型等;另一些成員是指針類型,是用來存放與之相連的結(jié)點的地址。單向鏈表的結(jié)點只包含一個這樣的指針成員。下面是一個單向鏈表結(jié)點的類型說明：struct studentlong num;float score;struct student*next; ;其中next是成員名,它是指針類型的,它指向struct student類型數(shù)據(jù)(這就是next所在的結(jié)構(gòu)體類型)

39、。用這種方法可以建立鏈表,鏈表的每一個節(jié)點都是struct student類型,它的next成員存放下一節(jié)點的地址。這種在結(jié)構(gòu)體類型的定義中引用類型名定義自己的成員的方法只允許定義指針時使用。 內(nèi)存動態(tài)管理函數(shù) 前面已經(jīng)提及,鏈表結(jié)點的存儲空間是程序根據(jù)需要向系統(tǒng)申請的。c系統(tǒng)的函數(shù)庫中提供了程序動態(tài)申請和釋放內(nèi)存存儲塊的庫函數(shù),下面分別介紹。1. malloc函數(shù)它的作用是在內(nèi)存開辟指定大小的存儲空間,并將此存儲空間的起始地址作為函數(shù)值帶回。malloc函數(shù)的原型為：void*malloc(unsigned int size)它的形參size為無符號整型。函數(shù)值為指針(地址)

40、,這個指針是指向void類型的,也就是不規(guī)定指向任何具體的類型。如果想將這個指針值賦給其他類型的指針變量,應(yīng)當(dāng)進行顯式的轉(zhuǎn)換(強制類型轉(zhuǎn)換)。例如：malloc(8)用來開辟一個長度為8個字節(jié)的內(nèi)存空間,如果系統(tǒng)分配的此段空間的起始地址為 81268,則malloc(8)的函數(shù)返回值為81268。如果內(nèi)存缺乏足夠大的空間進行分配,則malloc函數(shù)值為“空指針”,即地址為0。 2. calloc函數(shù)其函數(shù)原型為：vold*calloc(unsigned int num,unsigned int size)它有兩個形參num和size。其作用是分配num個大小為size字節(jié)的空間。例如用call

41、oc(20,30)可以開辟20個(每個大小為30字節(jié))的空間,即總長為600字節(jié)。此函數(shù)返回值為該空間的首地址。成員也可以是一個結(jié)構(gòu)體變量。3. free函數(shù)free函數(shù)的原型為：void free(void*ptr)其作用是將指針變量ptr指向的存儲空間釋放,即交還給系統(tǒng),系統(tǒng)可以另行分配作它用。應(yīng)當(dāng)強調(diào),ptr值不能是任意的地址項,而只能是由在程序中執(zhí)行過的malloc或calloc函數(shù)所返回的地址。如果隨便寫：free(100)是不行的,系統(tǒng)怎么知道釋放多大的存儲空間呢?下面這樣用是可以的： p=(long*)malloc(18);free(p);free函數(shù)它把原先開辟的18個字節(jié)的空

42、間釋放,雖然p是指向long型的,但可以傳給指向void型的指針變量ptr,系統(tǒng)會使其自動轉(zhuǎn)換。free函數(shù)無返回值。 鏈表的基本操作鏈表的基本操作包括建立鏈表、鏈表的插入、刪除、輸出和查找等。1. 建立鏈表 所謂建立鏈表是指一個一個地輸入各結(jié)點數(shù)據(jù),并建立起各結(jié)點前后相鏈的關(guān)系。 建立單向鏈表的方法有插表頭(先進后出)方法和鏈表尾(先進先出)方法兩種。插表頭方法的特點是：新產(chǎn)生的結(jié)點作為新的表頭插入鏈表;鏈表尾方法的特點是：新產(chǎn)生的結(jié)點接到鏈表的表尾。圖10.5a表示用插表頭方法建立鏈表,圖10.5b表示用鏈表尾方法建立鏈表。從圖10.5a可知,用插表頭的方法,鏈表只需要用

43、head指針指示,產(chǎn)生的新結(jié)點的地址存人指針變量p,使用賦值語句：p-next=head;將head指示的鏈表接在新結(jié)點之后;用head=p;使頭指針指向新結(jié)點。插表頭算法抽象描述如下：(1)head=null;/*表頭指向空,表示鏈表為空*/(2)產(chǎn)生新結(jié)點,地址賦給指針變量p;(3)p-next=head;head=p;/*插表頭操作*/(4)循環(huán)執(zhí)行2)可繼續(xù)。 headpheadppnext=headhead=p頂點表頭接在新結(jié)點之后，新結(jié)點作為表頭鏈表已有k個結(jié)點，p指向新結(jié)點圖10.5a 插表頭方法建立鏈表鏈表尾算法抽象描述如下：(1)head=last=null;/*表頭指向空,

44、表示鏈表為空,last是表尾指針*/(2)產(chǎn)生新結(jié)點,地址賦給指針變量p;p-next=null;/*新結(jié)點作為表尾*/(3)如果head為null則head=p;/*新結(jié)點作為表頭,這時鏈表只有一個結(jié)點*/否則last-next=p;/*鏈表操作*/(4)last=p;/*表尾指針1ast指向新結(jié)點*/(5)循環(huán)執(zhí)行(2),可繼續(xù)建立新結(jié)點。用鏈表尾方法建立鏈表如圖10.5b所示。 headlastplast-next=p新結(jié)點接到表尾headlast鏈表已有k個結(jié)點，p指向新結(jié)點。準(zhǔn)備接到表尾，表尾由last指針指示p圖10.5b 鏈表尾方法建立鏈表下面通過一個例子來說明如何建立一個鏈表。

45、例10.5 寫一函數(shù)建立一個有n名學(xué)生數(shù)據(jù)的單向鏈表。鏈表尾方法思路如下：(1)設(shè)3個指針變量：head、p1、p2,它們都指向結(jié)構(gòu)體類型數(shù)據(jù)。(2)head和p2的初始值為null(即等于0),p2作為表尾指針。(3)用malloc函數(shù)開辟一個結(jié)點,并使p1指向它。(4)從鍵盤讀人一個學(xué)生的數(shù)據(jù)給p1所指的結(jié)點。約定學(xué)號不會為零,如果輸入的學(xué)號為0,則表示建立鏈表的過程完成(約定學(xué)號不會為零)。 (5)如果n=1,則p2=head=p1;即把pl的值賦給head和p2,新結(jié)點既是表頭也是表尾, pl所指向的新開辟的結(jié)點就成為鏈表中第1個結(jié)點。(6)重復(fù)(3)、(4)產(chǎn)生新結(jié)點。由于nl,將新

46、結(jié)點鏈接到表尾,表尾指針p2指向新的表尾。當(dāng)新結(jié)點輸入的數(shù)據(jù)為：p1-num=0,此新結(jié)點不被連接到鏈表中,循環(huán)終止。建立鏈表的函數(shù)如下：#delfin null 0#define len sizeof(struct student)struct studentlong num;float score;struct student*next; ;int n;struct student*creat( ) /*此函數(shù)帶回一個指向鏈表頭的指針*/ struct student*head,*p1,*p2;n=0;head=null;pl=(struct student)malloc(len);/*創(chuàng)

47、建第一個結(jié)點*/scanf(“%1d,%f”,&p1-num,&pl-score);p1-next=null;while(p1-num!=0)/*應(yīng)該將結(jié)點加入鏈表*/+n;if(n=1)head=pl;/*是第一個結(jié)點,作表頭*/else p2-next=pl;/*不是第一個結(jié)點,作表尾*/p2=pl;p1=(struct student*)malloc(len); /*開辟下一個結(jié)點*/scanf(“%ld,%f”,&p1-num,&p1-score);p1-next=null;free(p1); /*釋放最后一個結(jié)點所占的內(nèi)存*/return(head);/*返回鏈表的頭指針*/關(guān)于函數(shù)

48、的說明：(1)第一行為#define命令行,令null代表0,用它表示“空地址”。第二行令len代表struct student結(jié)構(gòu)體類型數(shù)據(jù)的長度,sizeof是“求字節(jié)數(shù)運算符”。(2)creat函數(shù)是指針類型,即此函數(shù)帶回一個指針值,它指向一個struct student類型數(shù)據(jù)。實際上treat函數(shù)帶回一個鏈表起始地址。 (3)在一般系統(tǒng)中,malloc帶回的是指向字符型數(shù)據(jù)的指針。而p1、p2是指向structstudent類型數(shù)據(jù)的指針變量,兩者所指的是不同類型的數(shù)據(jù)。因此必須用強制類型轉(zhuǎn)換的方法使之類型一致,在malloc(len)之前加了“(struct student*)”,

49、它的作用是使malloc返回的指針轉(zhuǎn)換為指向struct student類型數(shù)據(jù)的指針。注意“*”號不可省略,否則變成轉(zhuǎn)換成struct student類型了,而不是指針類型了。 (4)函數(shù)返回的是head的值,也就是鏈表的頭地址。n代表結(jié) 點個數(shù)。2. 鏈表的插入操作任務(wù)：將一個結(jié)點插入到二個已有鏈表中的某個位置。該任務(wù)可以分解成兩個步驟：(1)找到插入點。方法：從鏈表頭開始逐一查找要插入位置的一前一后兩個節(jié)點，并分別保存為p2，p1。如果找到鏈表尾都沒找到，說明沒有滿足條件的插入點。算法：最初p1=head;移動指針為p2=p1;p1=p1-next 直到找到插入點。(2)插入結(jié)點。方法：

50、先使待插節(jié)點的指針域指向p1，然后再使p2的指針域指向待插節(jié)點。算法：p0-next=p1(p0為待插入結(jié)點); p2-next=p0;要點：在插入節(jié)點時要注意為什么不能把p0-next=p1和p2-next=p0順序顛倒呢？舉個簡單的例子，我們在放風(fēng)箏的時候，發(fā)現(xiàn)手中的線太短了，想接上一段，如果我們不先連接好與風(fēng)箏相連的一端，風(fēng)箏就會隨風(fēng)飄走。我們在插入節(jié)點的時候，必須先讓待插節(jié)點指向后續(xù)節(jié)點，不然我們在段開p1，p2之間的“線索”時，后續(xù)節(jié)點就不知道跑到什么地方去了。兩個步驟如圖10.6所示。鏈表的插入操作算法描述如下：仍然以例10.5建立一個有n名學(xué)生數(shù)據(jù)的單向鏈表為例。用指針變量p0指

51、向待插入的結(jié)點,設(shè)已有的鏈表各結(jié)點是按學(xué)號由小到大順序排序的。最初p1=head找插入點步驟如下：當(dāng)p0-numpl-num且p1-next!=null p2=p1；p1=p1-next;插入結(jié)點操作如下：如果p1=head則 結(jié)點作為表頭插入否則插入在p2所指的結(jié)點之后;headp2p1p0headp2p1圖10.6 鏈表插入操作 插入結(jié)點的函數(shù)insert如下：struct student *insert(struct student *head,struct student *stud)struct student*p0,*pl,*p2;p1=head;/*p1指向第一個結(jié)點*/p0=s

52、tud;/*p0指向要插入的結(jié)點*/if(head=null) /*原來是空表*/ head=p0; p0-next=null; /*使p0指向的結(jié)點作為鏈表第一個結(jié)點*/else while(p0-nump1-num)&(p1- next!=null) p2=p1; p1=p1-next; /*找插入點*/ if(head=p1) p0-next=head; head=p0; /*作為表頭*/ else p0-next=p1; /*插到p2指向的結(jié)點之后*/ p2-next=p0; +n;/*結(jié)點數(shù)加1*/ return(head); insert函數(shù)參數(shù)是兩個結(jié)構(gòu)體類型指針變量head和s

53、tud,從實參傳來待插入結(jié)點的地址傳給stud,語句p0=stud的作用是使p0指向待插入結(jié)點。函數(shù)類型是指針類型,函數(shù)返回值是鏈表起始地址head。3. 鏈表的刪除操作從一個鏈表中刪去一個結(jié)點,只要改變鏈接關(guān)系即可,即修改結(jié)點指針成員的值,如圖10.7所示。該任務(wù)可以分解成三個步驟：(1)尋找要刪除結(jié)點方法：從鏈表頭開始逐一查找，直到找到節(jié)點p1或者到了鏈表尾結(jié)束，注意保存要刪節(jié)點的前一個節(jié)點p2。算法：p1=head;p2=p1;p1=p1-next;(2)刪除節(jié)點方法：修改鏈接關(guān)系。算法：p2-next= p1-next;(3) 釋放刪除結(jié)點的內(nèi)存算法： free(p1);刪去節(jié)點操作如

54、圖10.7所示。 headp2p1刪去p1指向的節(jié)點headp2p1p2-next=p1-next p1指向的節(jié)點從鏈表中分離圖10.7 刪除結(jié)點操作以例10.5建立的學(xué)生鏈表為例,刪除學(xué)號為num的結(jié)點。判斷條件為：p1-num=num刪除學(xué)生鏈表中一個結(jié)點的函數(shù)delete如下：struct student *delete(struct student *head,long num) /*形參num為需刪除的學(xué)號*/ struct student *p1,*p2;if(head=null)printf(“nlist null!n”);return error;/*鏈表為空*/p 1 = h

55、 e a d ;/*從頭結(jié)點開始查找*/while(num!=p1-num&p1-next!=null)/*p1指向的不是所要找的結(jié)點,并且沒有到表尾*/p2=p1;p1=p1-next;/*后移一個結(jié)點*/if(num=p1-num)/*找到了需刪除的結(jié)點*/ if(p1=head)/*p1指向的是頭結(jié)點*/ head=p1-next;/*第二個結(jié)點成為新的頭結(jié)點*/ else p2-next=p1-next;/*后繼結(jié)點的地址賦給前一結(jié)點*/ printf(“delete:%ldn”,num); free(p1);/*釋放結(jié)點所占的內(nèi)存*/ n-;/*鏈表結(jié)點數(shù)減1*/ elseprint

56、f(”%ld not been found!n”,num); /*找不到刪除結(jié)點*/return(head); delete函數(shù)的類型是指向struet student類型數(shù)據(jù)的指針,它的返回值是鏈表的頭指針。函數(shù)參數(shù)為head和要刪除的學(xué)號num。當(dāng)刪除第一個結(jié)點時,head的值可能在函數(shù)執(zhí)行過程中被改變。4. 鏈表的輸出操作 要依次輸出鏈表中各結(jié)點的數(shù)據(jù)比較容易處理。首先要知道鏈表頭結(jié)點的地址,也就是要知道head的值,然后設(shè)一個指針變量p,先指向第一個結(jié)點,輸出p所指的結(jié)點,然后使p后移一個結(jié)點,再輸出,直到鏈表的尾結(jié)點。 輸出鏈表的函數(shù)print如下：void print(struct

57、 student *head)struct student*p;prinft(”nnow,these%d nodes are:n”,n);p=head;if(head!=null)doprintf(”%d%5.1fn”,p-num,p-score);p=p-next;while(p!=null); p首先指向第一個結(jié)點,在輸出完第一個結(jié)點之后,將p原來所指向的結(jié)點中的next值賦給p(即p=p-next),而p-next的值就是下一個結(jié)點的起始地址。將它賦給p就是p指向下一個結(jié)點。 head的值由實參傳過來也就是將已有的鏈表的頭指針傳給被調(diào)用的函數(shù),在print函數(shù)中從head所指的第一個結(jié)點

58、出發(fā),順序輸出各個結(jié)點。5. 鏈表的查找操作鏈表的查找是指在已知鏈表中查找值為某指定值的結(jié)點。鏈表的查找過程是從鏈表的頭指針?biāo)傅牡谝粋€結(jié)點出發(fā),順序查找?；虬l(fā)現(xiàn)有指定值的結(jié)點,以指向該結(jié)點的指針值為查找結(jié)果;或查找至鏈表結(jié)尾,未發(fā)現(xiàn)有指定值的結(jié)點,查找結(jié)果為null,表示鏈表中沒有指定值的結(jié)點。為簡單起見,以指定的學(xué)號作為查找結(jié)點的標(biāo)志。查找一個結(jié)點的函數(shù)find如下：struct student *find(struct student *head,long num)struct student p1,*p2;if(head=null)printf(”n list null!n”);ret

59、urn error; p1=head;while(num!=p1-num &p1!=null)p2=p1;p1=p1-next;if(p1!=null)printf(”find:%1d%5.2fn”,num,p1-score);elseprintf(”%ld not been found!n”,num);return(head);find函數(shù)的類型是指向struct student類型數(shù)據(jù)的指針,其返回值是鏈表的頭指針,函數(shù)參數(shù)為head和要查找的學(xué)號bum。 10.6 10.6 共用體共用體10.6.1 共用體的概念 到目前為止所介紹的各種數(shù)據(jù)類型的變量,它的值雖能改變,而其類型是不能改變的

60、。在某些特殊應(yīng)用中,要求某存儲區(qū)域中的數(shù)據(jù)對象在程序執(zhí)行的不同時間能存儲不同類型的值。共用體就是為滿足這種需要而引入的。共用體類型的定義形式與結(jié)構(gòu)體類型的定義形式相同,只是其類型關(guān)鍵字不同,共用體的關(guān)鍵字為union。一般形式為：union共用體類型名共用體類型名成員說明表列成員說明表列;例如：union dataint i;char ch;float f;同定義結(jié)構(gòu)體變量一樣,定義共同體變量也有3種方式：(1)先定義共用體類型,再定義共用體類型變量。例如：union dataint i;char ch;float f;union data a,b,c;(2)在定義共用體類型的同時定義共用體類