構(gòu)造數(shù)據(jù)類型

構(gòu)造數(shù)據(jù)類型2023/8/211第1頁，課件共77頁，創(chuàng)作于2023年2月§9.1結(jié)構(gòu)體數(shù)據(jù)類型

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

由一些不同類型的數(shù)據(jù)組合而成的數(shù)據(jù)整體，C語言稱之為“結(jié)構(gòu)體”類型，結(jié)構(gòu)體中所包含的數(shù)據(jù)元素稱之為成員。2023/8/212第2頁，課件共77頁，創(chuàng)作于2023年2月9.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)一成一個整體，使它們相互關(guān)聯(lián)結(jié)構(gòu)又是變量的集合，可以單獨(dú)使用其成員2023/8/213第3頁，課件共77頁，創(chuàng)作于2023年2月結(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)的定義以分號結(jié)束，被看作一條語句

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

2023/8/214第4頁，課件共77頁，創(chuàng)作于2023年2月結(jié)構(gòu)體類型的特點(diǎn)：

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

通信地址聯(lián)系電話電子郵箱城市街道門牌號郵編2023/8/217第7頁，課件共77頁，創(chuàng)作于2023年2月結(jié)構(gòu)的嵌套定義structaddress{charcity[10];charstreet[20];intcode;intzip;};structnest_friendslist{charname[10];intage;structaddressaddr;chartelephone[13];}nest_friend;在定義嵌套的結(jié)構(gòu)類型時，必須先定義成員的結(jié)構(gòu)類型，再定義主結(jié)構(gòu)類型。

姓名性別年齡

通信地址聯(lián)系電話電子郵箱城市街道門牌號郵編2023/8/218第8頁，課件共77頁，創(chuàng)作于2023年2月9.2結(jié)構(gòu)變量9.2.1結(jié)構(gòu)變量的定義和初始化9.2.2結(jié)構(gòu)變量的使用2023/8/219第9頁，課件共77頁，創(chuàng)作于2023年2月9.2.1結(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;2023/8/2110第10頁，課件共77頁，創(chuàng)作于2023年2月結(jié)構(gòu)變量的定義2.混合定義在定義結(jié)構(gòu)體類型的同時定義結(jié)構(gòu)體變量

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

{charname[10];intage;chartelephone[13];}friend1,friend2;2023/8/2111第11頁，課件共77頁，創(chuàng)作于2023年2月結(jié)構(gòu)變量的初始化structfriends_list

friend1={"Zhang",26,};nameagetelephone↓↓↓Zhang260571-852718802023/8/2112第12頁，課件共77頁，創(chuàng)作于2023年2月9.2.2結(jié)構(gòu)變量的使用1.結(jié)構(gòu)變量成員的引用結(jié)構(gòu)變量名

.結(jié)構(gòu)成員名friend1.age=26;strcpy(friend1.name,"ZhangSan");nest_friend.addr.zip2023/8/2113第13頁，課件共77頁，創(chuàng)作于2023年2月2、將結(jié)構(gòu)體變量作為一個整體來使用。

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

structfriend_listteacher;

teacher=doctor;/*將結(jié)構(gòu)體變量doctor的值賦給teacher*/這樣，變量teacher中各成員的值均與doctor的成員的值相同。2023/8/2114第14頁，課件共77頁，創(chuàng)作于2023年2月【例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;}2023/8/2115第15頁，課件共77頁，創(chuàng)作于2023年2月main(){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

2023/8/2116第16頁，課件共77頁，創(chuàng)作于2023年2月§9.1.5結(jié)構(gòu)型變量成員的輸入/輸出

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

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

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

puts();/*將數(shù)組中的字符串輸出到顯示器*/2023/8/2117第17頁，課件共77頁，創(chuàng)作于2023年2月§9.2結(jié)構(gòu)體數(shù)組

結(jié)構(gòu)體數(shù)組，亦即數(shù)組中每一個元素都是一個結(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ù)組大小>];2023/8/2118第18頁，課件共77頁，創(chuàng)作于2023年2月二、在定義結(jié)構(gòu)體的同時，定義結(jié)構(gòu)體數(shù)組：struct<結(jié)構(gòu)體名>{<成員項(xiàng)表列>}<數(shù)組名>[<數(shù)組大小>]；三、直接定義結(jié)構(gòu)體變量而不定義結(jié)構(gòu)體名；struct{<成員項(xiàng)表列>}<數(shù)組名>[<數(shù)組大小>]；2023/8/2119第19頁，課件共77頁，創(chuàng)作于2023年2月§9.2.2結(jié)構(gòu)體數(shù)組成員的初始化和引用

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

例如：structstudentstu[30]={{“LiFei”,“DongFengRoad14”,430038},{“LiMing”,“zhongshanRoad378”,430082},{“LiYong”,“XiaoShanRoad25”,430001}};2023/8/2120第20頁，課件共77頁，創(chuàng)作于2023年2月

結(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ù)組元素作為一個整體來使用*/2023/8/2121第21頁，課件共77頁，創(chuàng)作于2023年2月§9.3結(jié)構(gòu)體變量與函數(shù)

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

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); }2023/8/2124第24頁，課件共77頁，創(chuàng)作于2023年2月printf("-------------------------------------\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);}2023/8/2125第25頁，課件共77頁，創(chuàng)作于2023年2月程序運(yùn)行結(jié)果:

Pleaseinputdataofbook:NameNumberPriceComputer

300

18.6

Pleaseinputdataofbook:NameNumberPriceMathematics

600

15.5

Pleaseinputdataofbook:NameNumberPriceEnglish

360

22.8

Pleaseimputdataofbook:NameNumberPriceChemistry

150

14.2

2023/8/2126第26頁，課件共77頁，創(chuàng)作于2023年2月-------------------------------------------------------namenumpriceSumMoneyComputer30018.605580.00Mathematics60015.509300.00English36022.808208.00Chemistry15014.202130.002023/8/2127第27頁，課件共77頁，創(chuàng)作于2023年2月二、函數(shù)的返回值類型為結(jié)構(gòu)型C標(biāo)準(zhǔn)中還允許函數(shù)的返回值為結(jié)構(gòu)體類型的值?！纠?-3】把上面這個程序例子稍作修改，將數(shù)據(jù)輸入用一個函數(shù)NewBook()來實(shí)現(xiàn)。/*exam9_3.c函數(shù)的返回值為結(jié)構(gòu)類型*/#include<stdio.h>#include<conio.h>#include<stdlib.h>2023/8/2128第28頁，課件共77頁，創(chuàng)作于2023年2月structBookLib{ 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);}2023/8/2129第29頁，課件共77頁，創(chuàng)作于2023年2月structBookLibNewBook(){ structBookLibbook; chartemp[15]; printf("Pleaseinputdataofbook:NameNumberPrice\n"); gets(); gets(temp); book.num=atoi(temp); gets(temp); book.price=atof(temp); return(book);}2023/8/2130第30頁，課件共77頁，創(chuàng)作于2023年2月main(){ 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]);}程序中定義了兩個函數(shù)：無返回值的函數(shù)list()，返回值為結(jié)構(gòu)體類型變量的函數(shù)NewBook()用來給結(jié)構(gòu)體變量數(shù)組賦值。2023/8/2131第31頁，課件共77頁，創(chuàng)作于2023年2月例9-4構(gòu)建簡單的手機(jī)通訊錄聯(lián)系人的基本信息：姓名、年齡和聯(lián)系電話最多容納50名聯(lián)系人的信息具有新建和查詢功能2023/8/2132第32頁，課件共77頁，創(chuàng)作于2023年2月程序解析－程序結(jié)構(gòu)程序結(jié)構(gòu)主函數(shù)main：程序的總體控制函數(shù)new_friend：新建聯(lián)系人功能函數(shù)search_friend：查詢聯(lián)系人功能main()new_friend()search_friend()2023/8/2133第33頁，課件共77頁，創(chuàng)作于2023年2月程序解析－數(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：每個元素就是一個結(jié)構(gòu)變量，對應(yīng)一個聯(lián)系人structfriends_listfriends[50];2023/8/2134第34頁，課件共77頁，創(chuàng)作于2023年2月程序解析－全局變量/函數(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ù)形參2023/8/2135第35頁，課件共77頁，創(chuàng)作于2023年2月程序解析－源程序#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);2023/8/2136第36頁，課件共77頁，創(chuàng)作于2023年2月源程序intmain(void){intchoice;charname[10];structfriends_listfriends[50];/*包含50個人的通訊錄*/do{printf("手機(jī)通訊錄功能選項(xiàng)：1:新建2:查詢0:退出\n");printf("請選擇功能：");scanf("%d",&choice);switch(choice){ case1:

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

search_friend(friends,name);break; case0:break; }}while(choice!=0);printf("謝謝使用通訊錄功能!\n");return0;}2023/8/2137第37頁，課件共77頁，創(chuàng)作于2023年2月源程序/*新建聯(lián)系人*/voidnew_friend(structfriends_listfriends[]){structfriends_listf;if(Count==50){printf("通訊錄已滿!\n");return;}printf("請輸入新聯(lián)系人的姓名:");scanf("%s",);printf("請輸入新聯(lián)系人的年齡:");scanf("%d",&f.age);printf("請輸入新聯(lián)系人的聯(lián)系電話:");scanf("%s",f.telephone);friends[Count]=f;

Count++;}2023/8/2138第38頁，課件共77頁，創(chuàng)作于2023年2月源程序/*查詢聯(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)系人!");}2023/8/2139第39頁，課件共77頁，創(chuàng)作于2023年2月9.4共用體(聯(lián)合體)一、共用體的概念

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

union共用體名

{分量表

}變量表；2023/8/2140第40頁，課件共77頁，創(chuàng)作于2023年2月說明：雖然“共用體”與“結(jié)構(gòu)體”的定義形式相似，但是：

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

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

一個結(jié)構(gòu)體變量的各個分量的(起始)地址各不相同,分別擁有各自的存儲空間。而一個共用體變量的各個分量的地址(起始)相同，共同擁有同一存儲空間。2023/8/2141第41頁，課件共77頁，創(chuàng)作于2023年2月

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

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

共用體變量可作為參數(shù)傳遞給函數(shù)，也可以作函數(shù)的返回值。同樣，可以使用地址傳送方式將共用體變量的地址作為參數(shù)或返回值在函數(shù)間傳遞。2023/8/2142第42頁，課件共77頁，創(chuàng)作于2023年2月9.4A,共用體變量的存儲形式structmemb{ floatv; intn; charc;}stag;stag占內(nèi)存7個字節(jié)的空間unionmemb{ floatv; intn; charc;}ustag;ustag占的內(nèi)存空間為4個字節(jié)100110051007vnc2001vnc200220032004

共用體類型變量每次只能存放一個成員的值2023/8/2143第43頁，課件共77頁，創(chuàng)作于2023年2月二、共用體變量的引用

不能引用共用體變量，只能采用分量運(yùn)算符“

”引用共用體變量的分量。與引用結(jié)構(gòu)體變量的方法是一致的。

2023/8/2144第44頁，課件共77頁，創(chuàng)作于2023年2月例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]2023/8/2145第45頁，課件共77頁，創(chuàng)作于2023年2月

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

enum枚舉名{枚舉值表};

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

如：

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

該枚舉名為weekday，枚舉值共有7個，即一周中的七天。凡被說明為weekday類型變量的取值只能是七天中的某一天。9.5枚舉類型2023/8/2146第46頁，課件共77頁，創(chuàng)作于2023年2月枚舉變量的說明

如同結(jié)構(gòu)和聯(lián)合一樣，枚舉變量也可用不同的方式說明，即先定義后說明，同時定義說明或直接說明。設(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;2023/8/2147第47頁，課件共77頁，創(chuàng)作于2023年2月1、枚舉元素本身由系統(tǒng)定義了一個表示序號的數(shù)值，從0開始順序定義為0，1，2…。如在weekday中，sun值為0，mon值為1，…,sat值為6。2、只能把枚舉值賦予枚舉變量，不能把元素的數(shù)值直接賦予枚舉變量。如：

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

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

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

a=tue;2023/8/2148第48頁，課件共77頁，創(chuàng)作于2023年2月3、可用如下定義改變枚舉元素中的序號值：

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

0、1、2、3、7、8、9。4、還應(yīng)該說明的是枚舉元素不是字符常量也不是字符串常量，使用時不要加單、雙引號。2023/8/2149第49頁，課件共77頁，創(chuàng)作于2023年2月/*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]);}2023/8/2150第50頁，課件共77頁，創(chuàng)作于2023年2月9.6動態(tài)數(shù)據(jù)結(jié)構(gòu)

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

動態(tài)數(shù)據(jù)結(jié)構(gòu)中最基本的形式是鏈表和二叉樹,它們在數(shù)據(jù)處理中起著十分重要的作用。2023/8/2151第51頁，課件共77頁，創(chuàng)作于2023年2月一、動態(tài)存儲分配C語言實(shí)現(xiàn)動態(tài)存儲分配的函數(shù)：

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

pc=(char*)malloc(100);表示分配100個字節(jié)的內(nèi)存空間，并強(qiáng)制轉(zhuǎn)換為字符數(shù)組類型，函數(shù)的返回值為指向該字符數(shù)組的指針，把該指針賦予指針變量pc。2023/8/2152第52頁，課件共77頁，創(chuàng)作于2023年2月

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

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

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

free(ptr)

釋放由指針ptr所指向的存儲空間。ptr是最近一次調(diào)用malloc或calloc函數(shù)或鏈表指針返回的值。ptr為字符型指針。2023/8/2153第53頁，課件共77頁，創(chuàng)作于2023年2月二、鏈表

鏈表概念

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

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

建立鏈表例9.3建立一個三個結(jié)點(diǎn)的鏈表，存放學(xué)生數(shù)據(jù)。為簡單起見，我們假定學(xué)生數(shù)據(jù)結(jié)構(gòu)中只有學(xué)號和年齡兩項(xiàng)。head123pbpb0pbpfpf#defineNULL0#defineLENsizeof(structstu)structstu{intnum;intage;structstu*next;};pf2023/8/2157第57頁，課件共77頁，創(chuàng)作于2023年2月structstu*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)體成員時，使用->*/

2023/8/2158第58頁，課件共77頁，創(chuàng)作于2023年2月打印鏈表函數(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);}2023/8/2159第59頁，課件共77頁，創(chuàng)作于2023年2月babaxPP單鏈表的插入運(yùn)算S在P所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn)2023/8/2160第60頁，課件共77頁，創(chuàng)作于2023年2月babax∧anaia1a2PPai-1xL單鏈表的插入運(yùn)算S2023/8/2161第61頁，課件共77頁，創(chuàng)作于2023年2月單鏈表的插入運(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;}2023/8/2162第62頁，課件共77頁，創(chuàng)作于2023年2月∧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;}2023/8/2163第63頁，課件共77頁，創(chuàng)作于2023年2月∧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;}S2023/8/2164第64頁，課件共77頁，創(chuàng)作于2023年2月∧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;}S2023/8/2165第65頁，課件共77頁，創(chuàng)作于2023年2月∧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;}S2023/8/2166第66頁，課件共77頁，創(chuàng)作于2023年2月∧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;}2023/8/2167第67頁，課件共77頁，創(chuàng)作于2023年2月voidlbsc(structstu*p)/*刪除p指針指向結(jié)點(diǎn)的后一個結(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)算2023/8/2168第68頁，課件共77頁，創(chuàng)作于2023年2月ai-1a1aiai+1Lpvoidlbsc(structstu*p)/*刪除p指針指向結(jié)點(diǎn)的后一個結(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)算2023/8/2169第69頁，課件共77頁，創(chuàng)作于2023年2月ai-1a1aiai+1Lpvoidlbsc(structstu*p)/*刪除p指針指向結(jié)點(diǎn)的后一個結(jié)點(diǎn)*/{structstu*q;

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