構(gòu)造數(shù)據(jù)類型第一頁，共七十七頁，2022年，8月28日2023/3/161§9.1結(jié)構(gòu)體數(shù)據(jù)類型

前面介紹的變量都只包含一種類型，但在實(shí)際問題中，常常要求把一些屬于不同類型的數(shù)據(jù)作為一個(gè)整體來處理。如：一個(gè)職員的編號(hào)、姓名、年齡、性別、身份證號(hào)碼、民族、文化程度、職務(wù)、住址、聯(lián)系電話等等。

由一些不同類型的數(shù)據(jù)組合而成的數(shù)據(jù)整體，C語言稱之為“結(jié)構(gòu)體”類型，結(jié)構(gòu)體中所包含的數(shù)據(jù)元素稱之為成員。第二頁，共七十七頁，2022年，8月28日2023/3/1629.1.2結(jié)構(gòu)的概念與定義使用結(jié)構(gòu)來表示通訊錄信息：structfriends_list{charname[10];/*姓名*/intage;/*年齡*/chartelephone[13];/*聯(lián)系電話*/};結(jié)構(gòu)：構(gòu)造數(shù)據(jù)類型，把有內(nèi)在聯(lián)系的不同類型的數(shù)據(jù)統(tǒng)一成一個(gè)整體，使它們相互關(guān)聯(lián)結(jié)構(gòu)又是變量的集合，可以單獨(dú)使用其成員第三頁，共七十七頁，2022年，8月28日2023/3/163結(jié)構(gòu)的定義結(jié)構(gòu)類型定義的一般形式為：

struct結(jié)構(gòu)名

{

類型名結(jié)構(gòu)成員名1；類型名結(jié)構(gòu)成員名2；

類型名結(jié)構(gòu)成員名n；

};結(jié)構(gòu)的定義以分號(hào)結(jié)束，被看作一條語句

關(guān)鍵字struct和它后面的結(jié)構(gòu)名一起組成一個(gè)新的數(shù)據(jù)類型名

第四頁，共七十七頁，2022年，8月28日2023/3/164結(jié)構(gòu)體類型的特點(diǎn)：

①結(jié)構(gòu)體名為任何合法的標(biāo)識(shí)符，建議用具有一定意義的單詞或組合作為結(jié)構(gòu)體名。②雖然成員的類型定義形式同簡(jiǎn)單變量，但不能直接使用。③定義結(jié)構(gòu)體類型只是定義類型而不是定義變量。第五頁，共七十七頁，2022年，8月28日2023/3/165結(jié)構(gòu)定義示例定義平面坐標(biāo)結(jié)構(gòu)：structpoint{doublex;doubley;};雖然x、y的類型相同，也可以用數(shù)組的方式表示，但采用結(jié)構(gòu)體描述整體性更強(qiáng)，增加了程序的可讀性，使程序更清晰。第六頁，共七十七頁，2022年，8月28日2023/3/1669.1.3結(jié)構(gòu)的嵌套定義在實(shí)際生活中，一個(gè)較大的實(shí)體可能由多個(gè)成員構(gòu)成，而這些成員中有些又有可能是由一些更小的成員構(gòu)成的實(shí)體。在手機(jī)通訊錄中，增加“通信地址”姓名性別年齡

通信地址聯(lián)系電話電子郵箱城市街道門牌號(hào)郵編第七頁，共七十七頁，2022年，8月28日2023/3/167結(jié)構(gòu)的嵌套定義structaddress{charcity[10];charstreet[20];intcode;intzip;};structnest_friendslist{charname[10];intage;structaddressaddr;chartelephone[13];}nest_friend;在定義嵌套的結(jié)構(gòu)類型時(shí)，必須先定義成員的結(jié)構(gòu)類型，再定義主結(jié)構(gòu)類型。

姓名性別年齡

通信地址聯(lián)系電話電子郵箱城市街道門牌號(hào)郵編第八頁，共七十七頁，2022年，8月28日2023/3/1689.2結(jié)構(gòu)變量9.2.1結(jié)構(gòu)變量的定義和初始化9.2.2結(jié)構(gòu)變量的使用第九頁，共七十七頁，2022年，8月28日2023/3/169結(jié)構(gòu)變量的定義和初始化三種定義結(jié)構(gòu)變量的方式：1.單獨(dú)定義先定義結(jié)構(gòu)類型，再定義具有這種結(jié)構(gòu)類型的變量

structfriends_list{charname[10];/*姓名*/intage;/*年齡*/chartelephone[13];/*聯(lián)系電話*/};structfriends_list

friend1,friend2;第十頁，共七十七頁，2022年，8月28日2023/3/1610結(jié)構(gòu)變量的定義2.混合定義在定義結(jié)構(gòu)體類型的同時(shí)定義結(jié)構(gòu)體變量

structfriends_list{charname[10];intage;chartelephone[13];}friend1,friend2;3.無類型名定義在定義結(jié)構(gòu)體變量時(shí)省略結(jié)構(gòu)體名struct

{charname[10];intage;chartelephone[13];}friend1,friend2;第十一頁，共七十七頁，2022年，8月28日2023/3/1611結(jié)構(gòu)變量的初始化structfriends_list

friend1={"Zhang",26,};nameagetelephone↓↓↓Zhang260571-85271880第十二頁，共七十七頁，2022年，8月28日2023/3/16129.2.2結(jié)構(gòu)變量的使用1.結(jié)構(gòu)變量成員的引用結(jié)構(gòu)變量名

.結(jié)構(gòu)成員名friend1.age=26;strcpy(,"ZhangSan");nest_friend.addr.zip第十三頁，共七十七頁，2022年，8月28日2023/3/16132、將結(jié)構(gòu)體變量作為一個(gè)整體來使用。

可以將一個(gè)結(jié)構(gòu)體變量作為一個(gè)整體賦給另一個(gè)結(jié)構(gòu)體變量，條件是這兩個(gè)變量必須具有相同的結(jié)構(gòu)體類型。例如：structfriend_listdoctor={“LiMing”,24,88753540};

structfriend_listteacher;

teacher=doctor;/*將結(jié)構(gòu)體變量doctor的值賦給teacher*/這樣，變量teacher中各成員的值均與doctor的成員的值相同。第十四頁，共七十七頁，2022年，8月28日2023/3/1614【例9-1】閱讀下面的程序，了解結(jié)構(gòu)體成員的使用/*exam9_1.c結(jié)構(gòu)體成員的使用*/#include<stdio.h>#include<conio.h>structscore{intmath;inteng;intcomp;};structstu{charname[12];charsex;longStuClass;

structscoresub;}第十五頁，共七十七頁，2022年，8月28日2023/3/1615main(){structstustudent1={"LiMing",'M',990324,88,80,90};structstustudent2;student2=student1;[0]='H';[1]='u';student2.StuClass=990325;

student2.sub.math=83;printf("Record1-%s,%c,%ld,%d,%d,%d\n",, student1.sex,student1.StuClass,student1.sub.math, student1.sub.eng,p);printf("Record2-%s,%c,%ld,%d,%d,%d\n",, student2.sex,student2.StuClass,student2.sub.math, student2.sub.eng,p);}程序運(yùn)行結(jié)果:Record1---LiMing,M,990324,88,80,90Record1---HuMing,M,990325,83,80,90

第十六頁，共七十七頁，2022年，8月28日2023/3/1616§9.1.5結(jié)構(gòu)型變量成員的輸入/輸出

對(duì)變量的成員進(jìn)行輸入/輸出，如下所示：scanf(“%s%s%ld”,,stud.addr,&stud.zip);printf(“%s,%s,%ld\n”,,stud.addr,stud.zip);

也可以用gets函數(shù)和puts函數(shù)輸入和輸出一個(gè)結(jié)構(gòu)變量中字符數(shù)組成員。如：

gets();/*輸入一個(gè)字符串給*/

puts();/*將數(shù)組中的字符串輸出到顯示器*/第十七頁，共七十七頁，2022年，8月28日2023/3/1617§9.2結(jié)構(gòu)體數(shù)組

結(jié)構(gòu)體數(shù)組，亦即數(shù)組中每一個(gè)元素都是一個(gè)結(jié)構(gòu)體變量。

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

結(jié)構(gòu)體數(shù)組的定義方法與結(jié)構(gòu)體變量的定義方法相同。

一、先定義結(jié)構(gòu)體，再定義結(jié)構(gòu)體數(shù)組：struct<結(jié)構(gòu)體名>{<成員項(xiàng)表列>}；struct<結(jié)構(gòu)體名><數(shù)組名>[<數(shù)組大小>];第十八頁，共七十七頁，2022年，8月28日2023/3/1618二、在定義結(jié)構(gòu)體的同時(shí)，定義結(jié)構(gòu)體數(shù)組：struct<結(jié)構(gòu)體名>{<成員項(xiàng)表列>}<數(shù)組名>[<數(shù)組大小>]；三、直接定義結(jié)構(gòu)體變量而不定義結(jié)構(gòu)體名；struct{<成員項(xiàng)表列>}<數(shù)組名>[<數(shù)組大小>]；第十九頁，共七十七頁，2022年，8月28日2023/3/1619§9.2.2結(jié)構(gòu)體數(shù)組成員的初始化和引用

結(jié)構(gòu)體數(shù)組成員的值也可以初始化，初始化的形式與二維數(shù)組的初始化形式類似。

例如：structstudentstu[30]={{“LiFei”,“DongFengRoad14”,430038},{“LiMing”,“zhongshanRoad378”,430082},{“LiYong”,“XiaoShanRoad25”,430001}};第二十頁，共七十七頁，2022年，8月28日2023/3/1620

結(jié)構(gòu)體數(shù)組的引用完全類似于結(jié)構(gòu)體變量的引用，只是用結(jié)構(gòu)體數(shù)組元素來代替結(jié)構(gòu)體變量，其他規(guī)則不變，如下面所示：*/引用某一元素的成員*/stu[0].namestu[0].agestu[0]=stu[2];*/將結(jié)構(gòu)體數(shù)組元素作為一個(gè)整體來使用*/第二十一頁，共七十七頁，2022年，8月28日2023/3/1621§9.3結(jié)構(gòu)體變量與函數(shù)

一、函數(shù)的形參與實(shí)參為結(jié)構(gòu)型【例9-2】下面的程序是計(jì)算四種書的購書情況，并輸出統(tǒng)計(jì)結(jié)果。分析，定義一個(gè)結(jié)構(gòu)體類型BookLib，用來描述購書的信息，還定義了一個(gè)函數(shù)list，它的參數(shù)為結(jié)構(gòu)型變量，函數(shù)的作用是計(jì)算購書的總費(fèi)用并輸出所有信息。在主程序中，定義了一個(gè)臨時(shí)字符數(shù)組變量temp[15]，用于將用戶輸入的兩個(gè)數(shù)值：一個(gè)是書的數(shù)目num，另一個(gè)是書的價(jià)格price作為字符串來接收，然后通過atoi()函數(shù)和atof()函數(shù)將temp轉(zhuǎn)成整型值和實(shí)型值。第二十二頁，共七十七頁，2022年，8月28日2023/3/1622/*exam9_2.c函數(shù)的參數(shù)為結(jié)構(gòu)類型*/#include<stdio.h>#include<conio.h>#include<stdlib.h>structBookLib{charname[12];intnum;floatprice;floatSumMoney;};第二十三頁，共七十七頁，2022年，8月28日2023/3/1623main(){

voidlist(structBookLibStuBook);structBookLibBook[4];inti;chartemp[15];for(i=0;i<4;i++) { printf("Pleaseinputdataofbook(%d):NameNumberPrice\n",i+1); gets(Book[i].name); gets(temp); Book[i].num=atoi(temp); gets(temp); Book[i].price=atof(temp); }第二十四頁，共七十七頁，2022年，8月28日2023/3/1624printf("-------------------------------------\n");printf("namenumpriceSumMoney\n");for(i=0;i<4;i++)

list(Book[i]);}voidlist(structBookLibStuBook){StuBook.SumMoney=StuBook.num*StuBook.price;printf("%-12s%5d%6.2f%9.2f\n",StuB,StuBook.num,StuBook.price,StuBook.SumMoney);}第二十五頁，共七十七頁，2022年，8月28日2023/3/1625程序運(yùn)行結(jié)果:

Pleaseinputdataofbook:NameNumberPriceComputer30018.6Pleaseinputdataofbook:NameNumberPriceMathematics60015.5Pleaseinputdataofbook:NameNumberPriceEnglish36022.8Pleaseimputdataofbook:NameNumberPriceChemistry15014.2第二十六頁，共七十七頁，2022年，8月28日2023/3/1626-------------------------------------------------------namenumpriceSumMoneyComputer30018.605580.00Mathematics60015.509300.00English36022.808208.00Chemistry15014.202130.00第二十七頁，共七十七頁，2022年，8月28日2023/3/1627二、函數(shù)的返回值類型為結(jié)構(gòu)型C標(biāo)準(zhǔn)中還允許函數(shù)的返回值為結(jié)構(gòu)體類型的值?！纠?-3】把上面這個(gè)程序例子稍作修改，將數(shù)據(jù)輸入用一個(gè)函數(shù)NewBook()來實(shí)現(xiàn)。/*exam9_3.c函數(shù)的返回值為結(jié)構(gòu)類型*/#include<stdio.h>#include<conio.h>#include<stdlib.h>第二十八頁，共七十七頁，2022年，8月28日2023/3/1628structBookLib{ charname[12]; intnum; floatprice;floatSumMoney;};voidlist(structBookLibStuBook){StuBook.SumMoney=StuBook.num*StuBook.price;printf("%-12s%5d%6.2f%9.2f\n",StuB,StuBook.num,StuBook.price,StuBook.SumMoney);}第二十九頁，共七十七頁，2022年，8月28日2023/3/1629structBookLibNewBook(){ structBookLibbook; chartemp[15]; printf("Pleaseinputdataofbook:NameNumberPrice\n"); gets(); gets(temp); book.num=atoi(temp); gets(temp); book.price=atof(temp); return(book);}第三十頁，共七十七頁，2022年，8月28日2023/3/1630main(){ structBookLibBook[4]; inti; for(i=0;i<4;i++)

Book[i]=NewBook(); printf("----------------------------------\n"); printf("namenumpriceSumMoney\n"); for(i=0;i<4;i++) list(Book[i]);}程序中定義了兩個(gè)函數(shù)：無返回值的函數(shù)list()，返回值為結(jié)構(gòu)體類型變量的函數(shù)NewBook()用來給結(jié)構(gòu)體變量數(shù)組賦值。第三十一頁，共七十七頁，2022年，8月28日2023/3/1631例9-4構(gòu)建簡(jiǎn)單的手機(jī)通訊錄聯(lián)系人的基本信息：姓名、年齡和聯(lián)系電話最多容納50名聯(lián)系人的信息具有新建和查詢功能第三十二頁，共七十七頁，2022年，8月28日2023/3/1632程序解析－程序結(jié)構(gòu)程序結(jié)構(gòu)主函數(shù)main：程序的總體控制函數(shù)new_friend：新建聯(lián)系人功能函數(shù)search_friend：查詢聯(lián)系人功能main()new_friend()search_friend()第三十三頁，共七十七頁，2022年，8月28日2023/3/1633程序解析－數(shù)據(jù)類型/變量數(shù)據(jù)類型/變量結(jié)構(gòu)類型structfriends_list：在程序首部定義，其中的成員分別代表聯(lián)系人的基本信息structfriends_list{charname[10];/*姓名*/intage;/*年齡*/chartelephone[13];/*聯(lián)系電話*/};結(jié)構(gòu)數(shù)組friends：每個(gè)元素就是一個(gè)結(jié)構(gòu)變量，對(duì)應(yīng)一個(gè)聯(lián)系人structfriends_listfriends[50];第三十四頁，共七十七頁，2022年，8月28日2023/3/1634程序解析－全局變量/函數(shù)參數(shù)全局變量Count：記錄當(dāng)前的聯(lián)系人總數(shù)函數(shù)new_friend和search_friend的參數(shù)之一是結(jié)構(gòu)數(shù)組：voidnew_friend(structfriends_listfriends[]);voidsearch_friend(structfriends_listfriends[],char*name);結(jié)構(gòu)數(shù)組名作為函數(shù)實(shí)參與普通數(shù)組名作函數(shù)參數(shù)一樣，將數(shù)組首地址傳遞給函數(shù)形參第三十五頁，共七十七頁，2022年，8月28日2023/3/1635程序解析－源程序#include<stdio.h>#include<string.h>/*手機(jī)通訊錄結(jié)構(gòu)定義*/structfriends_list{charname[10];/*姓名*/intage;/*年齡*/chartelephone[13];/*聯(lián)系電話*/};intCount=0;/*全局變量記錄當(dāng)前聯(lián)系人總數(shù)*/voidnew_friend(structfriends_listfriends[]);voidsearch_friend(structfriends_listfriends[],char*name);第三十六頁，共七十七頁，2022年，8月28日2023/3/1636源程序intmain(void){intchoice;charname[10];structfriends_listfriends[50];/*包含50個(gè)人的通訊錄*/do{printf("手機(jī)通訊錄功能選項(xiàng)：1:新建2:查詢0:退出\n");printf("請(qǐng)選擇功能：");scanf("%d",&choice);switch(choice){ case1:

new_friend(friends);break; case2:printf("請(qǐng)輸入要查找的聯(lián)系人名:");scanf("%s",name);

search_friend(friends,name);break; case0:break; }}while(choice!=0);printf("謝謝使用通訊錄功能!\n");return0;}第三十七頁，共七十七頁，2022年，8月28日2023/3/1637源程序/*新建聯(lián)系人*/voidnew_friend(structfriends_listfriends[]){structfriends_listf;if(Count==50){printf("通訊錄已滿!\n");return;}printf("請(qǐng)輸入新聯(lián)系人的姓名:");scanf("%s",);printf("請(qǐng)輸入新聯(lián)系人的年齡:");scanf("%d",&f.age);printf("請(qǐng)輸入新聯(lián)系人的聯(lián)系電話:");scanf("%s",f.telephone);friends[Count]=f;

Count++;}第三十八頁，共七十七頁，2022年，8月28日2023/3/1638源程序/*查詢聯(lián)系人*/voidsearch_friend(structfriends_listfriends[],char*name){inti,flag=0;if(Count==0){printf("通訊錄是空的!\n");return;}for(i=0;i<Count;i++)if(strcmp(name,friends[i].name)==0){/*找到聯(lián)系人*/flag=1;break;}if(flag){printf("姓名:%s\t",friends[i].name);printf("年齡:%d\t",friends[i].age);printf("電話:%s\n",friends[i].telephone);}elseprintf("無此聯(lián)系人!");}第三十九頁，共七十七頁，2022年，8月28日2023/3/16399.4共用體(聯(lián)合體)一、共用體的概念

二個(gè)以上不同類型的變量采用“覆蓋技術(shù)”占用同一段內(nèi)存單元的結(jié)構(gòu)稱為共用體。共用體類型變量的定義形式如下：

union共用體名

{分量表

}變量表；第四十頁，共七十七頁，2022年，8月28日2023/3/1640說明：雖然“共用體”與“結(jié)構(gòu)體”的定義形式相似，但是：

一個(gè)結(jié)構(gòu)體變量所需的存儲(chǔ)容量為每個(gè)分量所需存儲(chǔ)容量之和。而一個(gè)共用體變量所需的存儲(chǔ)容量為各個(gè)分量中占用存儲(chǔ)容量最多的分量所需的存儲(chǔ)容量。

一個(gè)結(jié)構(gòu)體變量的各個(gè)分量在任何時(shí)刻都同時(shí)存在，且可同時(shí)引用。而一個(gè)共用體變量的各個(gè)分量在同一時(shí)刻只存在其中一個(gè)，也只能引用其中的一個(gè)分量。即起作用的只是最后一次存放的分量，在存入一個(gè)新的分量后，原有分量的值被覆蓋而失去作用。

一個(gè)結(jié)構(gòu)體變量的各個(gè)分量的(起始)地址各不相同,分別擁有各自的存儲(chǔ)空間。而一個(gè)共用體變量的各個(gè)分量的地址(起始)相同，共同擁有同一存儲(chǔ)空間。第四十一頁，共七十七頁，2022年，8月28日2023/3/1641

共用體類型可以出現(xiàn)在結(jié)構(gòu)體類型定義中，也可以定義共用體類型數(shù)組，數(shù)組也可以作為共用體的分量。同樣，結(jié)構(gòu)體類型也可以出現(xiàn)在共用體類型定義中。

不能在定義共用體變量時(shí)對(duì)其初始化，也不能對(duì)共用體變量名賦值，更不能企圖引用共用體變量名去得到分量的值。

共用體變量可作為參數(shù)傳遞給函數(shù)，也可以作函數(shù)的返回值。同樣，可以使用地址傳送方式將共用體變量的地址作為參數(shù)或返回值在函數(shù)間傳遞。第四十二頁，共七十七頁，2022年，8月28日2023/3/16429.4A,共用體變量的存儲(chǔ)形式structmemb{ floatv; intn; charc;}stag;stag占內(nèi)存7個(gè)字節(jié)的空間unionmemb{ floatv; intn; charc;}ustag;ustag占的內(nèi)存空間為4個(gè)字節(jié)100110051007vnc2001vnc200220032004共用體類型變量每次只能存放一個(gè)成員的值第四十三頁，共七十七頁，2022年，8月28日2023/3/1643二、共用體變量的引用

不能引用共用體變量，只能采用分量運(yùn)算符“”引用共用體變量的分量。與引用結(jié)構(gòu)體變量的方法是一致的。

第四十四頁，共七十七頁，2022年，8月28日2023/3/1644例9.4a下述程序的輸出結(jié)果是（9）。(演示9-4a.c)#include<stdio.h>voidmain(){union{charc;unsignedinti[4];}z;z.i[0]=0x39;z.i[1]=0x36;printf(“%c”,z.c);}c;i[0]底8位0x39i[0]高8位0x00i[1]0x360x00i[2]i[4]第四十五頁，共七十七頁，2022年，8月28日2023/3/1645

所謂“枚舉”是指變量的取值只限于所列舉出來的值的范圍內(nèi)。枚舉的定義枚舉類型定義的一般形式為：

enum枚舉名{枚舉值表};

在枚舉值表中應(yīng)羅列出所有可用值。這些值也稱為枚舉元素。

如：

enumweekday{sun,mon,tue,wed,thu,fri,sat};

該枚舉名為weekday，枚舉值共有7個(gè)，即一周中的七天。凡被說明為weekday類型變量的取值只能是七天中的某一天。9.5枚舉類型第四十六頁，共七十七頁，2022年，8月28日2023/3/1646枚舉變量的說明

如同結(jié)構(gòu)和聯(lián)合一樣，枚舉變量也可用不同的方式說明，即先定義后說明，同時(shí)定義說明或直接說明。設(shè)有變量a,b,c被說明為上述的weekday，可采用下述任一種方式：enumweekday{sun,mou,tue,wed,thu,fri,sat};enumweekdaya,b,c;或者為：enumweekday{sun,mou,tue,wed,thu,fri,sat}a,b,c;或者為：enum{sun,mou,tue,wed,thu,fri,sat}a,b,c;第四十七頁，共七十七頁，2022年，8月28日2023/3/16471、枚舉元素本身由系統(tǒng)定義了一個(gè)表示序號(hào)的數(shù)值，從0開始順序定義為0，1，2…。如在weekday中，sun值為0，mon值為1，…,sat值為6。2、只能把枚舉值賦予枚舉變量，不能把元素的數(shù)值直接賦予枚舉變量。如：

a=sum;b=mon;是正確的。而：

a=0;b=1;是錯(cuò)誤的。如一定要把數(shù)值賦予枚舉變量，則必須用強(qiáng)制類型轉(zhuǎn)換。如：

a=(enumweekday)2;其意義是將順序號(hào)為2的枚舉元素賦予枚舉變量a，相當(dāng)于：

a=tue;第四十八頁，共七十七頁，2022年，8月28日2023/3/16483、可用如下定義改變枚舉元素中的序號(hào)值：

enumweekday{sun,mon,tue,wed,thu=7,fri,sat};則枚舉元素的序號(hào)值依次為：

0、1、2、3、7、8、9。4、還應(yīng)該說明的是枚舉元素不是字符常量也不是字符串常量，使用時(shí)不要加單、雙引號(hào)。第四十九頁，共七十七頁，2022年，8月28日2023/3/1649/*9_7.c枚舉類型的用法*/#include<stdio.h>enummonths{JAN=1,FEB,MAR,APR,MAY,JUN,JUL,AUG,SEP,OCT,NOV,DEC};main(){enummonthsmonth;char*monthName[]={"","January","February","March","April", "May","June","July","Auguest","September", "October","November","Dcember"};for(month=JAN;month<=DEC;month++)printf("%2d--%-10s\n",month,monthName[month]);}第五十頁，共七十七頁，2022年，8月28日2023/3/16509.6動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)

靜態(tài)數(shù)據(jù)結(jié)構(gòu)(例如數(shù)組)占據(jù)內(nèi)存空間的位置和大小是在它們被說明的同時(shí)由系統(tǒng)分配的,在程序運(yùn)行期間是不變的,因此可以有效地訪問它們的任何一個(gè)元素。但要?jiǎng)h除和插入一個(gè)元素則比較困難,往往要引起大量的數(shù)據(jù)移動(dòng)。而且數(shù)據(jù)量的擴(kuò)充更受到它們所占用的有限內(nèi)存空間的限制。C中的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)有效地解決了這一問題。動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)中的每個(gè)組成數(shù)據(jù)在邏輯上是連續(xù)排列的，但在物理上即在內(nèi)存中存儲(chǔ)時(shí)并不占用連續(xù)的內(nèi)存空間，它們可以根據(jù)需要隨機(jī)地增加或減少其元素,相應(yīng)地占用或釋放內(nèi)存空間。

動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)中最基本的形式是鏈表和二叉樹,它們?cè)跀?shù)據(jù)處理中起著十分重要的作用。第五十一頁，共七十七頁，2022年，8月28日2023/3/1651一、動(dòng)態(tài)存儲(chǔ)分配C語言實(shí)現(xiàn)動(dòng)態(tài)存儲(chǔ)分配的函數(shù)：

(類型說明符*)malloc(size)功能：在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配一塊長(zhǎng)度為“size”字節(jié)的連續(xù)區(qū)域。函數(shù)的返回值為該區(qū)域的首地址?！邦愋驼f明符”表示把該區(qū)域用于何種數(shù)據(jù)類型。(類型說明符*)表示把返回值強(qiáng)制轉(zhuǎn)換為該類型指針?！皊ize”是一個(gè)無符號(hào)數(shù)。例如：

pc=(char*)malloc(100);表示分配100個(gè)字節(jié)的內(nèi)存空間，并強(qiáng)制轉(zhuǎn)換為字符數(shù)組類型，函數(shù)的返回值為指向該字符數(shù)組的指針，把該指針賦予指針變量pc。第五十二頁，共七十七頁，2022年，8月28日2023/3/1652

(類型說明符*)calloc(n,size)

在內(nèi)存動(dòng)態(tài)存儲(chǔ)區(qū)中分配n塊長(zhǎng)度為“size”字節(jié)的連續(xù)區(qū)域。函數(shù)的返回值為該區(qū)域的首地址。calloc函數(shù)與malloc函數(shù)的區(qū)別僅在于一次可以分配n塊區(qū)域。例如：

ps=(structstu*)calloc(2,sizeof(structstu));free(ptr)

釋放由指針ptr所指向的存儲(chǔ)空間。ptr是最近一次調(diào)用malloc或calloc函數(shù)或鏈表指針返回的值。ptr為字符型指針。第五十三頁，共七十七頁，2022年，8月28日2023/3/1653二、鏈表

鏈表概念

鏈表是一種常見的動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配的數(shù)據(jù)結(jié)構(gòu)。鏈表有“單向鏈表”、“雙向鏈表”、“循環(huán)鏈表”、“雙向循環(huán)鏈表”之分。下圖是一個(gè)“單向鏈表”的示例。

單向鏈表是按照輸入數(shù)據(jù)的順序建立的。它有一個(gè)“頭指針”(圖中為head)，指向第一個(gè)元素；每一個(gè)元素稱為“結(jié)點(diǎn)”，每個(gè)結(jié)點(diǎn)包括兩個(gè)域：數(shù)據(jù)域和指向下一個(gè)結(jié)點(diǎn)的指針域；最后一個(gè)元素的指針域?yàn)椤癗ULL”(“空地址”)，表示鏈表的結(jié)束，稱為“表尾”。第五十四頁，共七十七頁，2022年，8月28日2023/3/1654a1a2an∧a3L…..線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可用C語言中的“結(jié)構(gòu)指針”來描述單向鏈表存儲(chǔ)結(jié)構(gòu)帶頭結(jié)點(diǎn)的線性鏈表datanextstructjd{intdata;Structjd*next;};第五十五頁，共七十七頁，2022年，8月28日2023/3/1655步驟:1、定義鏈表接點(diǎn)數(shù)據(jù)類型；2、建立表頭(亦即建立一個(gè)空表)；3、利用malloc()申請(qǐng)分配一個(gè)節(jié)點(diǎn)空間；4、將新節(jié)點(diǎn)的指針成員的值賦為空,若是空表,將新節(jié)點(diǎn)連接到表頭;若非空,將新節(jié)點(diǎn)連接到表尾;5、若有后續(xù)節(jié)點(diǎn)要接入鏈表,則轉(zhuǎn)3,否則結(jié)束!第五十六頁，共七十七頁，2022年，8月28日2023/3/1656

建立鏈表例9.3建立一個(gè)三個(gè)結(jié)點(diǎn)的鏈表，存放學(xué)生數(shù)據(jù)。為簡(jiǎn)單起見，我們假定學(xué)生數(shù)據(jù)結(jié)構(gòu)中只有學(xué)號(hào)和年齡兩項(xiàng)。head123pbpb0pbpfpf#defineNULL0#defineLENsizeof(structstu)structstu{intnum;intage;structstu*next;};pf第五十七頁，共七十七頁，2022年，8月28日2023/3/1657structstu*creat(intn){structstu*head,*pf,*pb;定義鏈表接點(diǎn)數(shù)據(jù)類型指針*/inti; for(i=0;i<n;i++)

{pb=(structstu*)malloc(LEN);建立新節(jié)點(diǎn)*/

printf("inputNumberandAge\n");scanf("%d%d",&pb->num,&pb->age);

if(i==0)pf=head=pb;/*head為鏈表頭指針,pb為表尾指針*/elsepf->next=pb;

/*連接兩節(jié)點(diǎn)*/

pb->next=NULL;/*表尾指針置為空*/

pf=pb;｝

returnhead;}/*通過結(jié)構(gòu)體指針訪問結(jié)構(gòu)體成員時(shí)，使用->*/

第五十八頁，共七十七頁，2022年，8月28日2023/3/1658打印鏈表函數(shù)voidlist(structstu*head){structstu*p; p=head; printf("nodeaddressnumage\n"); printf("___________________________________________\n"); while(p!=NULL) {printf("%lu%3d%3d\n",p,p->num,p->age); p=p->next;}}main(){structstu*head;intnum=10; head=creat(num);list(head);}第五十九頁，共七十七頁，2022年，8月28日2023/3/1659babaxPP單鏈表的插入運(yùn)算S在P所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn)第六十頁，共七十七頁，2022年，8月28日2023/3/1660babax∧anaia1a2PPai-1xL單鏈表的插入運(yùn)算S第六十一頁，共七十七頁，2022年，8月28日2023/3/1661單鏈表的插入運(yùn)算voidlbcr(stuctstu*p){/*在P所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn)*/structstu*s;/*定義指向結(jié)點(diǎn)類型的指針*/s=(structstu*)malloc(len));/*生成新結(jié)點(diǎn)*/printf("inputNumberandAge\n");scanf("%d%d",&pb->num,&pb->age);

s->next=p->next;p->next=s;return;}第六十二頁，共七十七頁，2022年，8月28日2023/3/1662∧anaia1a2Pai-1L單鏈表的插入運(yùn)算voidlbcr(stu*p){/*在P所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn)*/structstu*s;/*定義指向結(jié)點(diǎn)類型的指針*/s=(structstu*)malloc(len);/*生成新結(jié)點(diǎn)*/scanf("%d%d",&pb->num,&pb->age); s->next=p->next;p->next=s;returnOK;}第六十三頁，共七十七頁，2022年，8月28日2023/3/1663∧anaia1a2Pai-1L單鏈表的插入運(yùn)算voidlbcr(structstu*p){/*在P所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn)*/structstu*s;/*定義指向結(jié)點(diǎn)類型的指針*/

s=(structstu*)malloc(len);/*生成新結(jié)點(diǎn)*/

scanf("%d%d",&pb->num,&pb->age); s->next=p->next;p->next=s;returnOK;}S第六十四頁，共七十七頁，2022年，8月28日2023/3/1664∧anaia1a2Pai-1xL單鏈表的插入運(yùn)算voidlbcr(structstu*p){/*在P所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn)*/structstu*s;/*定義指向結(jié)點(diǎn)類型的指針*/s=(structstu*)malloc(len);/*生成新結(jié)點(diǎn)*/

scanf("%d%d",&pb->num,&pb->age); s->next=p->next;p->next=s;returnOK;}S第六十五頁，共七十七頁，2022年，8月28日2023/3/1665∧anaia1a2Pai-1xL單鏈表的插入運(yùn)算voidlbcr(JD*p,intx){/*在P所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn)*/JD*s;/*定義指向結(jié)點(diǎn)類型的指針*/s=(JD*)malloc(sizeof(JD));/*生成新結(jié)點(diǎn)*/

scanf("%d%d",&pb->num,&pb->age);

s->next=p->next;p->next=s;returnOK;}S第六十六頁，共七十七頁，2022年，8月28日2023/3/1666∧anaia1a2Pai-1xL單鏈表的插入運(yùn)算voidlbcr(structstu*p){/*在P所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn)*/structstu*s;/*定義指向結(jié)點(diǎn)類型的指針*/s=(structstu*)malloc(len);/*生成新結(jié)點(diǎn)*/

scanf("%d%d",&pb->num,&pb->age); s->next=p->next;

p->next=s;returnOK;}第六十七頁，共七十七頁，2022年，8月28日2023/3/1667voidlbsc(structstu*p)/*刪除p指針指向結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)*/{structstu*q;if(p->next!=NULL){q=p->next;/*q指向p的后繼結(jié)點(diǎn)*/p->next=q->next;/*修改p結(jié)點(diǎn)的指針域*/free(q);/*刪除并釋放結(jié)點(diǎn)*/}}單鏈表的刪除運(yùn)算第六十八頁，共七十七頁，2022年，8月28日2023/3/1668ai-1a1aiai+1Lpvoidlbsc(structstu*p)/*刪除p指針指向結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)*/{structstu*q;if(p->next!=NULL){q=p->next;/*q指向p的后繼結(jié)點(diǎn)*/p->next=q->next;/*修改p結(jié)點(diǎn)的指針域*/free(q);/*刪除并釋放結(jié)點(diǎn)*/}}單鏈表的刪除運(yùn)算第六十九頁，共七十七頁，2022年，8月28日2023/3/1669ai-1a1aiai+1Lpvoidlbsc(structstu*p)/*刪除p指針指向結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)*/{structstu*q;

if(p->next!=NULL){q=p->next;