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

1、1第7章 構(gòu)造數(shù)據(jù)類型第7章 構(gòu)造數(shù)據(jù)類型7.1 7.1 構(gòu)造數(shù)據(jù)類型概述構(gòu)造數(shù)據(jù)類型概述7.2 7.2 結(jié)構(gòu)體與結(jié)構(gòu)體變量的定義結(jié)構(gòu)體與結(jié)構(gòu)體變量的定義7.3 7.3 結(jié)構(gòu)體變量的使用與初始化結(jié)構(gòu)體變量的使用與初始化7.4 7.4 結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體數(shù)組7.5 7.5 結(jié)構(gòu)體指針結(jié)構(gòu)體指針7.6 7.6 結(jié)構(gòu)體作函數(shù)參數(shù)結(jié)構(gòu)體作函數(shù)參數(shù)7.7 7.7 線性表線性表7.8 7.8 共用體共用體7.9 7.9 枚舉類型枚舉類型7.10 7.10 用用typedeftypedef定義類型定義類型7.11 7.11 位段結(jié)構(gòu)類型位段結(jié)構(gòu)類型本章要點(diǎn)：1. 掌握構(gòu)造類型數(shù)據(jù)的定義方法和引掌握構(gòu)造類型數(shù)據(jù)

2、的定義方法和引用方法；用方法；2. 了解了解用用typedeftypedef定義類型的定義類型的方法。方法。 一個(gè)學(xué)生的信息有一個(gè)學(xué)生的信息有學(xué)號(hào)學(xué)號(hào)、姓名姓名、性別性別、年齡年齡、成成績(jī)績(jī)、住址住址等。等。 一本圖書的信息有一本圖書的信息有分類編號(hào)分類編號(hào)、書名書名、作者作者、出版出版社社、出版日期出版日期、價(jià)格價(jià)格、庫存量庫存量等。等。 如何描述這些類型不同的相關(guān)數(shù)據(jù)？如何描述這些類型不同的相關(guān)數(shù)據(jù)？7.1 構(gòu)造數(shù)據(jù)類型概述一種構(gòu)造類型數(shù)據(jù)。一種構(gòu)造類型數(shù)據(jù)。 結(jié)構(gòu)體結(jié)構(gòu)體由若干不同類型的數(shù)據(jù)項(xiàng)組成，由若干不同類型的數(shù)據(jù)項(xiàng)組成， 構(gòu)成結(jié)構(gòu)體的各個(gè)數(shù)據(jù)項(xiàng)稱為構(gòu)成結(jié)構(gòu)體的各個(gè)數(shù)據(jù)項(xiàng)稱為結(jié)構(gòu)體成

3、員結(jié)構(gòu)體成員。 struct 結(jié)構(gòu)體名結(jié)構(gòu)體名 數(shù)據(jù)類型數(shù)據(jù)類型1 成員名成員名1; 數(shù)據(jù)類型數(shù)據(jù)類型2 成員名成員名2; 數(shù)據(jù)類型數(shù)據(jù)類型n 成員名成員名n; ;7.2 結(jié)構(gòu)體與結(jié)構(gòu)體變量的定義結(jié)構(gòu)體類型定義的一般形式：結(jié)構(gòu)體類型定義的一般形式： lstruct為關(guān)鍵字，不能省；為關(guān)鍵字，不能??；l結(jié)構(gòu)體名結(jié)構(gòu)體名是用戶定義的是用戶定義的類型標(biāo)識(shí)，類型標(biāo)識(shí)，可?。o名可省（無名結(jié)構(gòu)體）結(jié)構(gòu)體）；l 中是組成該結(jié)構(gòu)體的中是組成該結(jié)構(gòu)體的成員成員。成員的。成員的數(shù)據(jù)類型數(shù)據(jù)類型可以是可以是C語言所允許的語言所允許的任何數(shù)據(jù)類型。任何數(shù)據(jù)類型。例如圖書類型的定義：例如圖書類型的定義： struct

4、 bookcard char num10; /*圖書分類編號(hào)是字符數(shù)組類型圖書分類編號(hào)是字符數(shù)組類型*/ char name30; /*書名是字符數(shù)組類型書名是字符數(shù)組類型*/ char author30; /*作者是字符數(shù)組類型作者是字符數(shù)組類型*/ char publisher60; /*出版社是字符數(shù)組類型出版社是字符數(shù)組類型*/ float price; /*價(jià)格是單精度實(shí)型價(jià)格是單精度實(shí)型*/ int n; /*庫存量是整型庫存量是整型*/ ;例如學(xué)生類型的定義：例如學(xué)生類型的定義：struct student int num; /* 學(xué)號(hào)是整型類型學(xué)號(hào)是整型類型 */ char n

5、ame20; /* 姓名是字符數(shù)組類型姓名是字符數(shù)組類型 */ char sex; /* 性別是字符型性別是字符型 */ int age; /* 年齡是整型年齡是整型 */ float score6; /* 成績(jī)是實(shí)型數(shù)組類型成績(jī)是實(shí)型數(shù)組類型 */ char addr30; /* 住址是字符數(shù)組類型住址是字符數(shù)組類型 */ ;7.2 結(jié)構(gòu)體與結(jié)構(gòu)體變量的定義7.2 結(jié)構(gòu)體與結(jié)構(gòu)體變量的定義1、利用已定義的結(jié)構(gòu)體類型名定義變量、利用已定義的結(jié)構(gòu)體類型名定義變量 struct 結(jié)構(gòu)體名結(jié)構(gòu)體名 變量名表列；變量名表列；例如：例如： struct student st30, t1, t2; str

6、uct bookcard book1100; 按照結(jié)構(gòu)體類型的組成，系統(tǒng)為定義的結(jié)構(gòu)體按照結(jié)構(gòu)體類型的組成，系統(tǒng)為定義的結(jié)構(gòu)體變量分配內(nèi)存單元。結(jié)構(gòu)體變量的各個(gè)成員在內(nèi)存變量分配內(nèi)存單元。結(jié)構(gòu)體變量的各個(gè)成員在內(nèi)存中占用連續(xù)存儲(chǔ)區(qū)域，中占用連續(xù)存儲(chǔ)區(qū)域，結(jié)構(gòu)體變量結(jié)構(gòu)體變量所占內(nèi)存所占內(nèi)存結(jié)構(gòu)體中結(jié)構(gòu)體中每個(gè)成員每個(gè)成員所占用內(nèi)存的所占用內(nèi)存的長(zhǎng)度之和長(zhǎng)度之和。struct studentnum2個(gè)字節(jié)name20個(gè)字節(jié)sex1個(gè)字節(jié)age2個(gè)字節(jié)score24個(gè)字節(jié)addr30個(gè)字節(jié)例例 struct student int num; char name20; char sex; int a

7、ge; float score6; char addr30; ; struct student stu1,stu2; 結(jié)構(gòu)體變量的定義形式：結(jié)構(gòu)體變量的定義形式： 7.2 結(jié)構(gòu)體與結(jié)構(gòu)體變量的定義2 2、在定義結(jié)構(gòu)體類型的同時(shí)定義變量、在定義結(jié)構(gòu)體類型的同時(shí)定義變量例如：例如： struct student int num； char name20,sex,addr30; int age; float score6; st30; struct 結(jié)構(gòu)體名結(jié)構(gòu)體名 成員定義表列；成員定義表列； 變量名表列；變量名表列；7.2 結(jié)構(gòu)體與結(jié)構(gòu)體變量的定義3、直接定義結(jié)構(gòu)體類型變量、直接定義結(jié)構(gòu)體類型變

8、量 例如：例如： struct int num； char name20,sex,addr30; int age; float score6; st30, a, b, c; struct 成員定義表列；成員定義表列； 變量名表列；變量名表列；用用無名結(jié)構(gòu)體無名結(jié)構(gòu)體直接定義直接定義變量變量只能一次。只能一次。7.2 結(jié)構(gòu)體與結(jié)構(gòu)體變量的定義結(jié)構(gòu)體類型與結(jié)構(gòu)體變量的說明結(jié)構(gòu)體類型與結(jié)構(gòu)體變量的說明 類型類型與與變量變量是不同的概念。是不同的概念。應(yīng)先定義一個(gè)結(jié)構(gòu)體類型，而后再定義結(jié)構(gòu)體應(yīng)先定義一個(gè)結(jié)構(gòu)體類型，而后再定義結(jié)構(gòu)體變量。變量。系統(tǒng)對(duì)類型不分配空間，僅對(duì)變量分配空間。系統(tǒng)對(duì)類型不分配空間

9、，僅對(duì)變量分配空間。只能對(duì)變量賦值、存取或運(yùn)算，而不能對(duì)一個(gè)只能對(duì)變量賦值、存取或運(yùn)算，而不能對(duì)一個(gè)類型賦值、存取或運(yùn)算。類型賦值、存取或運(yùn)算。 成員成員也可以是也可以是結(jié)構(gòu)變量（嵌套）結(jié)構(gòu)變量（嵌套）。 對(duì)結(jié)構(gòu)中的對(duì)結(jié)構(gòu)中的成員（域）成員（域），可以單獨(dú)使用，它的作，可以單獨(dú)使用，它的作用與地位相當(dāng)于用與地位相當(dāng)于普通變量普通變量。 成員名成員名可與程序中的變量名相同，也可與可與程序中的變量名相同，也可與不同結(jié)不同結(jié)構(gòu)體類型的成員名相同，構(gòu)體類型的成員名相同，二者代表不同的對(duì)象。二者代表不同的對(duì)象。 struct date int year,month,day; struct student

10、 int num; char name20; char sex; birthday; /* 成員為結(jié)構(gòu)體類型成員為結(jié)構(gòu)體類型 */ float score6; char addr30; ;num2個(gè)字節(jié)name20個(gè)字節(jié)sex1個(gè)字節(jié)birthdayyear2個(gè)字節(jié)month2個(gè)字節(jié)day2個(gè)字節(jié)score24個(gè)字節(jié)addr30個(gè)字節(jié)7.3 結(jié)構(gòu)體變量的引用及初始化引用規(guī)則：引用規(guī)則： 結(jié)構(gòu)體變量結(jié)構(gòu)體變量不能整體引用不能整體引用, ,只能引用只能引用成員成員變量。變量。引用方式：引用方式：結(jié)構(gòu)體變量名結(jié)構(gòu)體變量名. .成員名成員名可以將一個(gè)結(jié)構(gòu)體變量可以將一個(gè)結(jié)構(gòu)體變量賦值賦值給另一個(gè)結(jié)構(gòu)體

11、變量。給另一個(gè)結(jié)構(gòu)體變量。結(jié)構(gòu)體嵌套時(shí)結(jié)構(gòu)體嵌套時(shí)逐級(jí)引用。逐級(jí)引用。成員成員(分量分量)運(yùn)算符運(yùn)算符優(yōu)先級(jí)優(yōu)先級(jí): 1結(jié)合性結(jié)合性:從左向右從左向右例 struct student int num; char name20; char sex; int age; float score; char addr30; stu1,stu2; stu1.num=10;stu1.score=85.5;stu1.score+=stu2.score; stu1.age+;例 struct student int num; char name20; char sex; int age; float scor

12、e; char addr30; stu1,stu2; printf(“%d,%s,%c,%d,%f,%sn”,stu1); ( )stu1=101,“Wan Lin”,M,19,87.5,“DaLian”; ( )例 struct student int num; char name20; char sex; int age; float score; char addr30; stu1,stu2; if(stu1=stu2). ()例 struct student int num; char name20; char sex; int age; float score; char addr3

13、0; stu1,stu2; stu2=stu1; ( )例 struct student int num; char name20; struct date int month; int day; int year; birthday; stu1,stu2;numnamebirthdaymonthdayyearstu1.birthday.month=12;7.3 結(jié)構(gòu)體變量的引用及初始化初始化：初始化：形式一：形式一：struct 結(jié)構(gòu)體名結(jié)構(gòu)體名 類型名類型名 成員名；成員名； 類型名類型名 成員名；成員名； .；struct 結(jié)構(gòu)體名結(jié)構(gòu)體名 結(jié)構(gòu)體變量結(jié)構(gòu)體變量=初始數(shù)據(jù)初始數(shù)據(jù)；例例

14、struct student int num; char name20; char sex; int age; char addr30; ; struct student stu1=112,“Wang Lin”,M,19, “200 Beijing Road”;7.3 結(jié)構(gòu)體變量的引用及初始化形式二：形式二：struct 結(jié)構(gòu)體名結(jié)構(gòu)體名 類型名類型名 成員名；成員名； 類型名類型名 成員名；成員名； .結(jié)構(gòu)體變量結(jié)構(gòu)體變量=初始數(shù)據(jù)初始數(shù)據(jù)；例例 struct student int num; char name20; char sex; int age; char addr30; stu1

15、=112,“Wang Lin”,M,19, “200 Beijing Road”; 7.3 結(jié)構(gòu)體變量的引用及初始化形式三：形式三：struct 類型名類型名 成員名；成員名； 類型名類型名 成員名；成員名； .結(jié)構(gòu)體變量結(jié)構(gòu)體變量=初始數(shù)據(jù)初始數(shù)據(jù)；例例 struct int num; char name20; char sex; int age; char addr30; stu1=112,“Wang Lin”,M,19, “200 Beijing Road”; 7.3 結(jié)構(gòu)體變量的引用及初始化【例【例7.1】結(jié)構(gòu)體變量的初始化。】結(jié)構(gòu)體變量的初始化。 struct date int ye

16、ar, month, day; struct student char num8, name20, sex; struct date birthday; float score; a=“0506011,Li ming,M,1977,12,9,83, b=“0508025,Zhang li,F,1978,5,10,87, c; 如果初值個(gè)數(shù)少于結(jié)構(gòu)體成員個(gè)數(shù)，如果初值個(gè)數(shù)少于結(jié)構(gòu)體成員個(gè)數(shù)，則將無初值對(duì)應(yīng)的成員賦以則將無初值對(duì)應(yīng)的成員賦以0值。值。 如果初值個(gè)數(shù)多于結(jié)構(gòu)體成員個(gè)數(shù)，如果初值個(gè)數(shù)多于結(jié)構(gòu)體成員個(gè)數(shù)，則編譯出錯(cuò)。則編譯出錯(cuò)。7.4 結(jié)構(gòu)體數(shù)組 7.4.1結(jié)構(gòu)體數(shù)組的定義結(jié)構(gòu)體數(shù)組的定

17、義三種形式：三種形式：形式一形式一: : struct student int num; char name20; char sex; int age; ;struct student stu2;形式二形式二: : struct student int num; char name20; char sex; int age; stu2;形式三形式三: struct int num; char name20; char sex; int age; stu2;numnamesexagenumnamesexagestu0stu125B7.4 結(jié)構(gòu)體數(shù)組分行初始化分行初始化: struct stude

18、nt int num; char name20; char sex; int age; ;struct student stu =100,“Wang Lin”,M,20, 101,“Li Gang”,M,19, 110,“Liu Yan”,F,19; 全部初始化時(shí)維數(shù)可省全部初始化時(shí)維數(shù)可省順序初始化順序初始化: struct student int num; char name20; char sex; int age; ;struct student stu =100,“Wang Lin”,M,20, 101,“Li Gang”,M,19, 110,“Liu Yan”,F,19; 例例 s

19、truct student int num; char name20; char sex; int age; stu =,; 7.4.2 結(jié)構(gòu)體數(shù)組初始化結(jié)構(gòu)體數(shù)組初始化7.4 結(jié)構(gòu)體數(shù)組7.4.3 結(jié)構(gòu)體數(shù)組引用結(jié)構(gòu)體數(shù)組引用引用方式：引用方式：結(jié)構(gòu)體數(shù)組名結(jié)構(gòu)體數(shù)組名下標(biāo)下標(biāo).成員名成員名 struct student int num; char name20; char sex; int age; str3;stu1.age+;strcpy(,”ZhaoDa”);例7.2a 統(tǒng)計(jì)后選人選票struct person char name20; int count;lead

20、er3=“Li”,0,“Zhang”,0,”Wang“,0; main() int i,j; char leader_name20; for(i=1;i=10;i+) scanf(%s,leader_name); for(j=0;j3;j+)if(strcmp(leader_name,)=0) leaderj.count+; for(i=0;i=1 & n=5) listn.count+; /* 有效票，則相應(yīng)候選人計(jì)票成員加有效票，則相應(yīng)候選人計(jì)票成員加1 1 */ else printf(invalidn); list0.count+; /* 無效票無效票，

21、list0的計(jì)票成員加的計(jì)票成員加1 */ scanf(%d,&n); /* 輸入所投候選人編號(hào)輸入所投候選人編號(hào) */ for (i=1; i成員名成員名結(jié)構(gòu)體變量名結(jié)構(gòu)體變量名. .成員名成員名指向運(yùn)算符優(yōu)先級(jí): 1結(jié)合方向：從左向右p=&例7.3 指向結(jié)構(gòu)體的指針變量main() struct student long int num; char name20; char sex; float score; stu_1,*p; p=&stu_1; stu_1.num=10212; strcpy(stu_1.name,Li Lin); p-sex=

22、M; p-score=89.5; printf(nNo:%ldnname:%snsex:%cnscore:%fn, (*p).num,p-name,stu_1.sex,p-score); 舉例 例例7.4 輸入今天的日期，然后輸出該日期。輸入今天的日期，然后輸出該日期。 main( ) struct date /* 在函數(shù)中定義結(jié)構(gòu)體類型在函數(shù)中定義結(jié)構(gòu)體類型 */ int year, month, day;today,*p=&today; /* 定義結(jié)構(gòu)體變量及其指針定義結(jié)構(gòu)體變量及其指針 */ printf (Enter today date(YYYY/MM/DD):); scan

23、f(%d/%d/%d,&today.year,&today.month, &today.day); printf(Today:%d/%d/%dn,p-year,p-month, p-day); 7.5.2 指向結(jié)構(gòu)體數(shù)組的指針例例7.5 指向結(jié)構(gòu)體數(shù)組的指針指向結(jié)構(gòu)體數(shù)組的指針struct student int num; char name20; char sex; int age;stu3=10101,Li Lin,M,18, 10102,Zhang Fun,M,19, 10104,Wang Min,F,20;main() struct student *p; fo

24、r(p=stu;pnum,p-name,p-sex,p-age);numnamesexagestu0pstu1stu2p+17.5.2 指向結(jié)構(gòu)體數(shù)組的指針例例7.6 利用結(jié)構(gòu)體指針輸出一組化學(xué)利用結(jié)構(gòu)體指針輸出一組化學(xué) 元素名稱及其原子量。元素名稱及其原子量。 struct list int i; char name4; float w; tab4=1,H,1.008,2,He,4.0026, 3,Li,6.941,4,Be,9.01218;tab數(shù)組1Htab01.0082Hetab14.00263Litab26.9414Betab39.012187.5.2 指向結(jié)構(gòu)體數(shù)組的指針main(

25、 ) struct list *p; printf(NotNametAtomic Weightn); for (p=tab; p-i, p-name, p-w); tab數(shù)組1Htab01.0082Hetab14.00263Litab26.9414Betab39.01218ppppp1 H 1.0082 He 4.00263 Li 6.9414 Be 9.012187.5.2 指向結(jié)構(gòu)體數(shù)組的指針例例7.7 分析自增自減運(yùn)算對(duì)程序結(jié)果的影響。分析自增自減運(yùn)算對(duì)程序結(jié)果的影響。 struct code int i; char c; a =100,A,200,B, 300,C,400,D;a數(shù)組1

26、00a0A200a1B300a2C400a3D7.5.2 指向結(jié)構(gòu)體數(shù)組的指針main( ) struct code *p=a; printf(%dt,+p-i); printf(%ct,(+p)-c); printf(%dt,(p+)-i); printf(%ct,+p-c); printf(%dt,p-i+); printf(%dn,p-i); a數(shù)組100a0A200a1B300a2C400a3Dp101301101B200D3003017.6 結(jié)構(gòu)體作函數(shù)參數(shù)方法一：方法一： 用結(jié)構(gòu)體變量的成員作參數(shù)用結(jié)構(gòu)體變量的成員作參數(shù)-值傳遞值傳遞 函數(shù)的函數(shù)的形參形參定義為定義為普通變量普通變

27、量。函數(shù)調(diào)用時(shí)，。函數(shù)調(diào)用時(shí)，可可將主調(diào)函數(shù)的將主調(diào)函數(shù)的結(jié)構(gòu)體變量的成員值作結(jié)構(gòu)體變量的成員值作實(shí)參實(shí)參傳遞給傳遞給被調(diào)函數(shù)的被調(diào)函數(shù)的形參形參。 如果如果將函數(shù)定義為將函數(shù)定義為結(jié)構(gòu)體類型函數(shù)結(jié)構(gòu)體類型函數(shù)，可，可利用利用returnreturn語句將一個(gè)結(jié)構(gòu)體數(shù)據(jù)結(jié)果返回到主調(diào)函語句將一個(gè)結(jié)構(gòu)體數(shù)據(jù)結(jié)果返回到主調(diào)函數(shù)數(shù)中中。7.6 結(jié)構(gòu)體作函數(shù)參數(shù)方法二：方法二：用指向結(jié)構(gòu)體變量或數(shù)組的指針作參數(shù)用指向結(jié)構(gòu)體變量或數(shù)組的指針作參數(shù)-地址傳遞地址傳遞 形參形參定義為定義為指向結(jié)構(gòu)體類型的指向結(jié)構(gòu)體類型的指針指針變量變量，可可將主調(diào)函將主調(diào)函數(shù)的數(shù)的結(jié)構(gòu)體指針結(jié)構(gòu)體指針傳遞給被調(diào)函數(shù)的傳遞給

28、被調(diào)函數(shù)的形參形參變量變量，通過指針形，通過指針形參的指向域的擴(kuò)展，操作主調(diào)函數(shù)中參的指向域的擴(kuò)展，操作主調(diào)函數(shù)中結(jié)構(gòu)體變量及其成員結(jié)構(gòu)體變量及其成員。 如果如果將函數(shù)定義為將函數(shù)定義為結(jié)構(gòu)體指針型函數(shù)結(jié)構(gòu)體指針型函數(shù)，可可利用利用returnreturn語語句將被調(diào)函數(shù)中結(jié)構(gòu)體變量的句將被調(diào)函數(shù)中結(jié)構(gòu)體變量的指針指針返回給主調(diào)函數(shù)的返回給主調(diào)函數(shù)的結(jié)構(gòu)結(jié)構(gòu)體指針變量體指針變量。方法三：方法三： 利用利用結(jié)構(gòu)體變量結(jié)構(gòu)體變量傳遞結(jié)構(gòu)體數(shù)據(jù)傳遞結(jié)構(gòu)體數(shù)據(jù)-多值傳遞多值傳遞（效率低）（效率低）例7.8 用結(jié)構(gòu)體變量作函數(shù)參數(shù)struct data int a, b, c; ;main() void

29、 func(struct data); struct data arg; arg.a=27; arg.b=3; arg.c=arg.a+arg.b; printf(arg.a=%d arg.b=%d arg.c=%dn,arg.a,arg.b,arg.c); printf(Call Func().n); func(arg); printf(arg.a=%d arg.b=%d arg.c=%dn,arg.a,arg.b,arg.c);void func(struct data parm) printf(parm.a=%d parm.b=%d parm.c=%dn,parm.a,parm.b,pa

30、rm.c); printf(Process.n); parm.a=18; parm.b=5; parm.c=parm.a*parm.b; printf(parm.a=%d parm.b=%d parm.c=%dn,parm.a,parm.b,parm.c); printf(Return.n);arga :27b: 3c :30(main)(func)parma :27b: 3c :30copyarga :27b: 3c :30(main)(func)parma :18b: 5c :90arga :27b: 3c :30(main)arga :27b: 3c :30(main)例7.9 結(jié)構(gòu)體指

31、針作函數(shù)參數(shù)struct data int a, b, c; ;main() void func(struct data *parm); struct data arg; arg.a=27; arg.b=3; arg.c=arg.a+arg.b; printf(arg.a=%d arg.b=%d arg.c=%dn,arg.a,arg.b,arg.c); printf(Call Func().n); func(&arg); printf(arg.a=%d arg.b=%d arg.c=%dn,arg.a,arg.b,arg.c);void func(struct data *parm)

32、 printf(parm-a=%d parm-b=%d parm-c=%dn,parm-a,parm-b,parm-c); printf(Process.n); parm-a=18; parm-b=5; parm-c=parm-a*parm-b; printf(parm-a=%d parm-b=%d parm-c=%dn,parm-a,parm-b,parm-c); printf(Return.n);arga :18b: 5c :90(main)arga :27b: 3c :30(main)arga :27b: 3c :30(main)(func)parm*arga :18b: 5c :90(

33、main)(func)parm*7.7 線性表7.7.1 7.7.1 線性表的順序存儲(chǔ)與實(shí)現(xiàn)線性表的順序存儲(chǔ)與實(shí)現(xiàn) 順序表中所有結(jié)點(diǎn)類型相同，每個(gè)結(jié)點(diǎn)占用存儲(chǔ)順序表中所有結(jié)點(diǎn)類型相同，每個(gè)結(jié)點(diǎn)占用存儲(chǔ)空間也相同?？臻g也相同。 LOC(aLOC(ai i)=LOC(a)=LOC(a1 1)+(i-1)+(i-1)* *c (1=i=n)c (1=inum,p-score); p=p-next; while(p!=NULL); C語言提供了相關(guān)的存儲(chǔ)管理庫函數(shù)。這里僅介語言提供了相關(guān)的存儲(chǔ)管理庫函數(shù)。這里僅介紹其中三個(gè)，它們的原型說明在紹其中三個(gè)，它們的原型說明在“stdlib.h”頭文頭文件和件

34、和“alloc.h”頭文件中，使用這三個(gè)函數(shù)時(shí)，頭文件中，使用這三個(gè)函數(shù)時(shí)，應(yīng)選擇其中一個(gè)頭文件包含到源程序中。應(yīng)選擇其中一個(gè)頭文件包含到源程序中。 動(dòng)態(tài)分配存儲(chǔ)區(qū)函數(shù)動(dòng)態(tài)分配存儲(chǔ)區(qū)函數(shù)malloc( ) 函數(shù)原型：函數(shù)原型：void *malloc(unsigned size); 調(diào)用格式：調(diào)用格式：malloc(size) 功能：在動(dòng)態(tài)存儲(chǔ)區(qū)分配一個(gè)長(zhǎng)度為功能：在動(dòng)態(tài)存儲(chǔ)區(qū)分配一個(gè)長(zhǎng)度為size字節(jié)的字節(jié)的連續(xù)存儲(chǔ)區(qū)。調(diào)用結(jié)果為新分配的存儲(chǔ)區(qū)的首地連續(xù)存儲(chǔ)區(qū)。調(diào)用結(jié)果為新分配的存儲(chǔ)區(qū)的首地址，是一個(gè)址，是一個(gè)void 類型指針。若分配類型指針。若分配失敗失敗，則返回，則返回NULL（即（即

35、0）。 處理鏈表所需的函數(shù) 在在ANSI C標(biāo)準(zhǔn)中，關(guān)鍵字標(biāo)準(zhǔn)中，關(guān)鍵字void有兩種用法。有兩種用法。第一種用法，可將無返回值的函數(shù)定義為第一種用法，可將無返回值的函數(shù)定義為void類型類型第二種用法，用第二種用法，用void * 定義指針，這是一個(gè)指向定義指針，這是一個(gè)指向非具體數(shù)據(jù)類型的指針，稱為無類型指針。非具體數(shù)據(jù)類型的指針，稱為無類型指針。 【例【例7.11】調(diào)用】調(diào)用malloc函數(shù)分配所需存儲(chǔ)單元。函數(shù)分配所需存儲(chǔ)單元。 #include main( ) struct st int n; struct st *next; *p; p=(struct st *)malloc(si

36、zeof(struct st); p-n=5; p-next=NULL; printf(p-n=%dtp-next=%xn,p-n,p-next); 處理鏈表所需的函數(shù)將函數(shù)返回值轉(zhuǎn)換將函數(shù)返回值轉(zhuǎn)換成結(jié)構(gòu)體指針成結(jié)構(gòu)體指針 動(dòng)態(tài)分配存儲(chǔ)區(qū)函數(shù)動(dòng)態(tài)分配存儲(chǔ)區(qū)函數(shù)calloc( ) 函數(shù)原型：函數(shù)原型： void *calloc(unsigned int n,unsigned int size); 調(diào)用格式：調(diào)用格式：calloc(n,size) 功能：在動(dòng)態(tài)存儲(chǔ)區(qū)分配功能：在動(dòng)態(tài)存儲(chǔ)區(qū)分配n個(gè)長(zhǎng)度為個(gè)長(zhǎng)度為size字節(jié)的連字節(jié)的連續(xù)存儲(chǔ)區(qū)。調(diào)用結(jié)果為新分配的存儲(chǔ)區(qū)的首地址，續(xù)存儲(chǔ)區(qū)。調(diào)用結(jié)果為

37、新分配的存儲(chǔ)區(qū)的首地址，是一個(gè)是一個(gè)void類型指針。若分配類型指針。若分配失敗失敗，則返回，則返回NULL（即（即0）。 處理鏈表所需的函數(shù)【例【例7.12】調(diào)用】調(diào)用calloc函數(shù)分配所需存儲(chǔ)單元。函數(shù)分配所需存儲(chǔ)單元。 #include main( ) int i,*ip; ip=(int *)calloc(10,2); for (i=0; i10; i+) scanf(%d,ip+i); for (i=0; iname,name) gets(p-tel) p-next=NULL h=NULL T F h指向第一個(gè)指向第一個(gè) 連接新結(jié)點(diǎn)連接新結(jié)點(diǎn) 結(jié)點(diǎn)結(jié)點(diǎn) h=p q-next=p q

38、指向新的尾結(jié)點(diǎn)指向新的尾結(jié)點(diǎn) q=p 讀入一個(gè)學(xué)生姓名讀入一個(gè)學(xué)生姓名NULLhpChang62783410NULLWang63212986NULLpq strcpy(p-name,name); /* 為新結(jié)點(diǎn)中的成員賦值為新結(jié)點(diǎn)中的成員賦值 */ printf(tel: ); gets(p-tel); p-next=NULL; if (h=NULL) /* h為空，表示新結(jié)點(diǎn)為第一個(gè)結(jié)點(diǎn)為空，表示新結(jié)點(diǎn)為第一個(gè)結(jié)點(diǎn) */ h=p; /* 頭指針指向第一個(gè)結(jié)點(diǎn)頭指針指向第一個(gè)結(jié)點(diǎn) */ else /* h不為空不為空 */ q-next=p; /* 新結(jié)點(diǎn)與尾結(jié)點(diǎn)相連接新結(jié)點(diǎn)與尾結(jié)點(diǎn)相連接 *

39、/ q=p; /* 使使q指向新的尾結(jié)點(diǎn)指向新的尾結(jié)點(diǎn) */ printf(name: ); gets(name); return h; struct node *create( ) static struct node *h; struct node *p,*q; char name20; h=NULL; printf(name: ); gets(name); while (strlen(name)!=0) /* 當(dāng)輸入的姓名不是空串循環(huán)當(dāng)輸入的姓名不是空串循環(huán) */ p=NEW; /* 開辟新結(jié)點(diǎn)開辟新結(jié)點(diǎn) */ if (p=NULL) /* p為為NULL，新結(jié)點(diǎn)分配失敗新結(jié)點(diǎn)分配失敗

40、*/ printf(Allocation failuren); exit(0); /* 結(jié)束程序運(yùn)行結(jié)束程序運(yùn)行 */ #include #include #define NEW (struct node *)malloc(sizeof(struct node)struct node char name20,tel9; struct node *next; ;單鏈表的基本操作main( ) struct node *head; head=create( ); 【例【例7.14】輸出學(xué)生電話簿鏈表函數(shù)?！枯敵鰧W(xué)生電話簿鏈表函數(shù)。 單鏈表的基本操作輸出單向鏈表中各結(jié)點(diǎn)信息輸出單向鏈表中各結(jié)點(diǎn)信息

41、hpChang62783410Li68752341NULLWang63212986 p指向第一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn) p=head 當(dāng)當(dāng)p不為不為NULL 輸出結(jié)點(diǎn)數(shù)據(jù)輸出結(jié)點(diǎn)數(shù)據(jù) p指向下一個(gè)結(jié)點(diǎn)指向下一個(gè)結(jié)點(diǎn) p=p-nextpppNULLNULLvoid prlist(struct node *head) struct node *p; p=head; while (p!=NULL) printf(%st%sn,p-name,p-tel); p=p-next; #include #include #define NEW (struct node *)malloc(sizeof(struct

42、 node)struct node char name20,tel9; struct node *next; ;單鏈表的基本操作main( ) struct node *head; head=create( ); prlist(head); 在鏈表中，如果要?jiǎng)h除第在鏈表中，如果要?jiǎng)h除第i個(gè)結(jié)點(diǎn)，一般是將個(gè)結(jié)點(diǎn)，一般是將第（第（i-1）個(gè)結(jié)點(diǎn)直接與第（）個(gè)結(jié)點(diǎn)直接與第（i+1）個(gè)結(jié)點(diǎn)相連接，）個(gè)結(jié)點(diǎn)相連接，然后再釋放第然后再釋放第i個(gè)結(jié)點(diǎn)的存儲(chǔ)單元個(gè)結(jié)點(diǎn)的存儲(chǔ)單元 。對(duì)鏈表的刪除操作hNULLNULL第第i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) 第第i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) 第第i+1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) 【例【例7.15】刪除學(xué)生電

43、話簿鏈】刪除學(xué)生電話簿鏈 表中指定學(xué)生的信息。表中指定學(xué)生的信息。對(duì)鏈表的刪除操作 p=head while(strcmp(x,p-name)!=0 & p-next!=NULL) q指針跟隨指針跟隨p指針后移查找指針后移查找 (q=p;p=p-next;) strcmp(x,p-name)=0 T F p=head T F head=p-next q-next=p-next 沒找到?jīng)]找到 free(p)刪除刪除第一個(gè)第一個(gè)結(jié)點(diǎn)結(jié)點(diǎn) 刪除中間結(jié)刪除中間結(jié)點(diǎn)或尾結(jié)點(diǎn)點(diǎn)或尾結(jié)點(diǎn) 刪除結(jié)點(diǎn)工刪除結(jié)點(diǎn)工作分兩步：作分兩步：查找結(jié)點(diǎn)查找結(jié)點(diǎn)刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)學(xué)生姓名學(xué)生姓名當(dāng)姓名不同并且當(dāng)姓名不同

44、并且不是尾結(jié)點(diǎn)循環(huán)不是尾結(jié)點(diǎn)循環(huán)【例【例7.15】刪除學(xué)生電話簿鏈表中指定學(xué)生的信息?！縿h除學(xué)生電話簿鏈表中指定學(xué)生的信息。對(duì)鏈表的刪除操作hpChang62783410Li68752341NULLWang63212986(a) 刪除刪除第一個(gè)結(jié)點(diǎn)第一個(gè)結(jié)點(diǎn) (head=p-next)【例【例7.15】刪除學(xué)生電話簿鏈表中指定學(xué)生的信息?！縿h除學(xué)生電話簿鏈表中指定學(xué)生的信息。對(duì)鏈表的刪除操作hpChang62783410Li68752341NULLWang63212986(b) 刪除刪除中間結(jié)點(diǎn)或尾結(jié)點(diǎn)中間結(jié)點(diǎn)或尾結(jié)點(diǎn) (q-next=p-next)p q【例【例7.15】刪除學(xué)生電話簿鏈表中

45、指定學(xué)生的信息。】刪除學(xué)生電話簿鏈表中指定學(xué)生的信息。 對(duì)鏈表的刪除操作hpChang62783410Li68752341NULLWang63212986pp(c) 未找到指定的結(jié)點(diǎn)未找到指定的結(jié)點(diǎn) (strcmp(x,p-name)!=0) qq if (strcmp(x,p-name)=0) if (p=head) head=p-next; /* 刪除頭結(jié)點(diǎn)刪除頭結(jié)點(diǎn) */ else q-next=p-next; /* 刪除中間或尾結(jié)點(diǎn)刪除中間或尾結(jié)點(diǎn) */ free(p); /* 釋放被刪除的結(jié)點(diǎn)釋放被刪除的結(jié)點(diǎn) */ else printf(Not found.); /* 未找到指定的

46、結(jié)點(diǎn)未找到指定的結(jié)點(diǎn) */ h=head; return h;#include #include #define NEW (struct node *)malloc(sizeof(struct node)struct node char name20,tel9; struct node *next; ; 對(duì)鏈表的刪除操作struct node *delnode(struct node *head, char *x) struct node *p,*q; static struct node *h; if (head=NULL) printf(This is a empty list.); /*

47、 空鏈表情況空鏈表情況 */ return head; p=head; while (strcmp(x,p-name)!=0 & p-next!=NULL) q=p;p=p-next; /* q指針尾隨指針尾隨p指針向表尾移動(dòng)指針向表尾移動(dòng) */查找結(jié)點(diǎn)查找結(jié)點(diǎn) 將一個(gè)新結(jié)點(diǎn)插入到鏈表中，首先要尋找插入的將一個(gè)新結(jié)點(diǎn)插入到鏈表中，首先要尋找插入的位置。如果要求在第位置。如果要求在第i個(gè)結(jié)點(diǎn)前插入，可設(shè)置三個(gè)工個(gè)結(jié)點(diǎn)前插入，可設(shè)置三個(gè)工作指針作指針p0、p和和q，p0是指向待插入結(jié)點(diǎn)的指針。利是指向待插入結(jié)點(diǎn)的指針。利用用p和和q指針查找第指針查找第i個(gè)結(jié)點(diǎn)，找到后再將新結(jié)點(diǎn)鏈接個(gè)結(jié)點(diǎn)，

48、找到后再將新結(jié)點(diǎn)鏈接到鏈表上。到鏈表上。 對(duì)鏈表的插入操作 在單向鏈表中插入結(jié)點(diǎn)在單向鏈表中插入結(jié)點(diǎn) hNULL第第i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)ppqqp0p新的第新的第i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) head=NULL T F p=head head=p0 while(strcmp(x,p-name)!=0 & p-next!=NULL) p0-next q指針跟隨指針跟隨p指針后移查找指針后移查找 (q=p;p=p-next;) =NULL strcmp(x,p-name)=0 T F p=head T F p-next=p0 head=p0 q-next=p0 p0-next=NULL p0-next=p【例

49、【例7.16】在學(xué)生電話簿鏈表中插入一個(gè)學(xué)生的信息。】在學(xué)生電話簿鏈表中插入一個(gè)學(xué)生的信息。要求將新的信息插入在指定學(xué)生信息之前，如果未要求將新的信息插入在指定學(xué)生信息之前，如果未找到指定學(xué)生，則追加在鏈表尾部。找到指定學(xué)生，則追加在鏈表尾部。 對(duì)鏈表的插入操作當(dāng)姓名不同并且當(dāng)姓名不同并且不是尾結(jié)點(diǎn)循環(huán)不是尾結(jié)點(diǎn)循環(huán)空表時(shí)空表時(shí)插入插入結(jié)點(diǎn)結(jié)點(diǎn)在表尾在表尾追加結(jié)點(diǎn)追加結(jié)點(diǎn) 插入結(jié)點(diǎn)工插入結(jié)點(diǎn)工作分兩步：作分兩步：查找插查找插入位置入位置連接連接新結(jié)點(diǎn)新結(jié)點(diǎn)在表頭在表頭插入結(jié)點(diǎn)插入結(jié)點(diǎn) 在表中間在表中間插入結(jié)點(diǎn)插入結(jié)點(diǎn) 【例【例11.16】在學(xué)生電話簿鏈表中插入一個(gè)學(xué)生的信息。要】在學(xué)生電話簿鏈

50、表中插入一個(gè)學(xué)生的信息。要求將新的信息插入在指定學(xué)生信息之前，如果未找到指求將新的信息插入在指定學(xué)生信息之前，如果未找到指定學(xué)生，則追加在鏈表尾部。定學(xué)生，則追加在鏈表尾部。對(duì)鏈表的插入操作hpChang62783410Li68752341NULLWang63212986(a) 在在表頭表頭插入結(jié)點(diǎn)插入結(jié)點(diǎn) (head=p0; p0-next=p)Zhao62758421p0【例【例7.16】在學(xué)生電話簿鏈表中插入一個(gè)學(xué)生的信息。要求】在學(xué)生電話簿鏈表中插入一個(gè)學(xué)生的信息。要求將新的信息插入在指定學(xué)生信息之前，如果未找到指將新的信息插入在指定學(xué)生信息之前，如果未找到指定學(xué)生，則追加在鏈表尾部。

51、定學(xué)生，則追加在鏈表尾部。對(duì)鏈表的插入操作hChang62783410Li68752341NULLWang63212986(b) 在表中間插入結(jié)點(diǎn)在表中間插入結(jié)點(diǎn) (q-next=p0; p0-next=p)pqZhao62758421p0【例【例7.16】在學(xué)生電話簿鏈表中插入一個(gè)學(xué)生的信息。要求】在學(xué)生電話簿鏈表中插入一個(gè)學(xué)生的信息。要求將新的信息插入在指定學(xué)生信息之前，如果未找到指定將新的信息插入在指定學(xué)生信息之前，如果未找到指定學(xué)生，則追加在鏈表尾部。學(xué)生，則追加在鏈表尾部。對(duì)鏈表的插入操作hpChang62783410Li68752341NULLWang63212986pp(c) 在

52、表尾追加結(jié)點(diǎn)在表尾追加結(jié)點(diǎn) (p-next=p0; p0-next=NULLNULL) qq Zhao62758421p0Zhao62758421NULL if (strcmp(x,p-name)=0) if (p=head) head=p0; /* 在表頭插入結(jié)點(diǎn)在表頭插入結(jié)點(diǎn) */ else q-next=p0; /* 在表中間插入結(jié)點(diǎn)在表中間插入結(jié)點(diǎn) */ p0-next=p; else p-next=p0; /* 在表尾插入結(jié)點(diǎn)在表尾插入結(jié)點(diǎn) */ p0-next=NULL; h=head; return h; struct node *insert(struct node *head

53、, struct node *p0, char *x) struct node *p,*q; static struct node *h; if (head=NULL) head=p0; /* 空表時(shí)，插入結(jié)點(diǎn)空表時(shí)，插入結(jié)點(diǎn) */ p0-next=NULL; else p=head; while (strcmp(x,p-name)!=0 & p-next!=NULL) q=p;p=q-next; 查找插入點(diǎn)查找插入點(diǎn) 對(duì)鏈表的插入操作#include #include #define NEW (struct node *)malloc(sizeof(struct node)struc

54、t node char name20,tel9; struct node *next; ;對(duì)鏈表的綜合操作【例【例7.17】學(xué)生電話簿鏈表管理程序。】學(xué)生電話簿鏈表管理程序。 編制此程序可利用例編制此程序可利用例7.13至例至例7.16的的4個(gè)函數(shù)完成鏈表個(gè)函數(shù)完成鏈表的建立、輸出、刪除和插入等功能，這里只需編制一個(gè)的建立、輸出、刪除和插入等功能，這里只需編制一個(gè)main函數(shù)完成對(duì)這函數(shù)完成對(duì)這4個(gè)函數(shù)的調(diào)用。個(gè)函數(shù)的調(diào)用。 #include #define NEW (struct node *)malloc(sizeof(struct node) struct node char name2

55、0,tel9; struct node *next; ;11.7.8 對(duì)鏈表的綜合操作main( ) struct node *create( ),*delnode(struct node *, char *); struct node *insert(struct node *, struct node *, char *); void prlist(struct node *); struct node *head=NULL,*stu; char s80,name20; int c;11.7.8 對(duì)鏈表的綜合操作do do printf(n * * * * MENU * * * * n);

56、 printf( 1. Create a list n); printf( 2. Print a list n); printf( 3. Delete a node n); printf( 4. Insert a node n); printf( 0. Quit n); printf( Enter your choice(0-4): ); gets(s); c=atoi(s); while(c4); 可以先選擇可以先選擇1 1建建立一個(gè)鏈表，然立一個(gè)鏈表，然后根據(jù)需要選擇后根據(jù)需要選擇功能功能2 2、功能、功能3 3、功能功能4 4、直到選、直到選擇擇0 0退出程序的退出程序的運(yùn)行運(yùn)行 11.

57、7.8 對(duì)鏈表的綜合操作 switch(c) case 1: head=create( ); break; case 2: prlist(head); break; case 3: printf(nInput a name deleted:n); gets(name); head=delnode(head,name); break; case 4: stu=NEW; printf(nInput a new noden); printf(name: ); gets(stu- -name); printf(tel: ); gets(stu- -tel); stu- -next=NULL; prin

58、tf(nInsert positionn); printf(name: ); gets(name); head=insert(head,stu,name); while (c); 結(jié)構(gòu)體類型解決了如何描述一個(gè)邏輯上相關(guān)，但結(jié)構(gòu)體類型解決了如何描述一個(gè)邏輯上相關(guān)，但數(shù)據(jù)類型不同的一組分量的集合。數(shù)據(jù)類型不同的一組分量的集合。 在需要節(jié)省內(nèi)存儲(chǔ)空間時(shí)，在需要節(jié)省內(nèi)存儲(chǔ)空間時(shí)，c c語言還提供了一種語言還提供了一種由若干個(gè)不同類型的數(shù)據(jù)項(xiàng)組成，但由若干個(gè)不同類型的數(shù)據(jù)項(xiàng)組成，但共享同一存儲(chǔ)空共享同一存儲(chǔ)空間間的構(gòu)造類型。的構(gòu)造類型。7.8 共用體7.8.1 7.8.1 共用體及共用體變量的定義共用體

59、及共用體變量的定義一種構(gòu)造類型數(shù)據(jù)一種構(gòu)造類型數(shù)據(jù) 共用體共用體由若干不同類型的數(shù)據(jù)項(xiàng)組成，由若干不同類型的數(shù)據(jù)項(xiàng)組成， 構(gòu)成共用體的各個(gè)數(shù)據(jù)項(xiàng)稱為構(gòu)成共用體的各個(gè)數(shù)據(jù)項(xiàng)稱為共用體成員共用體成員。由于共享的特性，由于共享的特性，只有最新只有最新存儲(chǔ)的數(shù)存儲(chǔ)的數(shù)據(jù)是有效的。據(jù)是有效的。 union 共用共用體名體名 數(shù)據(jù)類型數(shù)據(jù)類型1 成員名成員名1; 數(shù)據(jù)類型數(shù)據(jù)類型2 成員名成員名2; 數(shù)據(jù)類型數(shù)據(jù)類型n 成員名成員名n; ;7.8.1 共用體及共用體變量的定義lunion為關(guān)鍵字；為關(guān)鍵字；l共用體名共用體名是用戶定義是用戶定義的的類型標(biāo)識(shí)類型標(biāo)識(shí)。l 中是組成該共用體中是組成該共用體的的

60、成員成員。成員的。成員的數(shù)據(jù)數(shù)據(jù)類型類型可以是可以是C語言所允語言所允許的任何數(shù)據(jù)類型。許的任何數(shù)據(jù)類型。共用體類型定義的一般形式：共用體類型定義的一般形式：例如：例如： union utype int i; char ch; long l; char c4; ;7.8.1 共用體及共用體變量的定義 定義了一個(gè)定義了一個(gè)union utypeunion utype共用體共用體類型，類型，共用體類型定義不分配內(nèi)存共用體類型定義不分配內(nèi)存空間空間，只是說明此類型數(shù)據(jù)的組成，只是說明此類型數(shù)據(jù)的組成情況。情況。 共用體變量的定義形式一形式一: : union data int i; char ch; float f; a,b;形式二形式二: : union data int i; char