1、第12章 結(jié)構(gòu)體與共用體,哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 蘇小紅,本章學(xué)習(xí)內(nèi)容, 結(jié)構(gòu)體數(shù)據(jù)類型，共用體數(shù)據(jù)類型、枚舉數(shù)據(jù)類型、定義數(shù)據(jù)類型的別名 結(jié)構(gòu)體變量、結(jié)構(gòu)體數(shù)組、結(jié)構(gòu)體指針的定義和初始化 結(jié)構(gòu)體成員的引用、成員選擇運(yùn)算符、指向運(yùn)算符 向函數(shù)傳遞結(jié)構(gòu)體變量、結(jié)構(gòu)體數(shù)組、結(jié)構(gòu)體指針 動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)、動(dòng)態(tài)鏈表,二進(jìn)制數(shù)類型本不存在 內(nèi)存里存的內(nèi)容，你認(rèn)為它是什么，它就是什么 在早期的機(jī)器指令及匯編語(yǔ)言中，數(shù)據(jù)對(duì)象均用二進(jìn)制數(shù)表示，沒有類型的概念 一般的CPU只支持兩種類型 整數(shù)、浮點(diǎn)數(shù),12.1從基本數(shù)據(jù)類型到抽象數(shù)據(jù)類型,在高級(jí)語(yǔ)言引入了基本數(shù)據(jù)類型 整型、浮點(diǎn)型、字符型等 不同語(yǔ)言

2、會(huì)定義不同的基本類型 基本數(shù)據(jù)類型并不能方便地解決所有問題 有些語(yǔ)言（如PL/1）中試圖規(guī)定較多的類型，如數(shù)組、樹、棧等，但實(shí)踐證明不是個(gè)好辦法,12.1從基本數(shù)據(jù)類型到抽象數(shù)據(jù)類型,用戶自己構(gòu)造數(shù)據(jù)類型復(fù)合數(shù)據(jù)類型 由基本數(shù)據(jù)類型迭代派生而來，表示復(fù)雜的數(shù)據(jù)對(duì)象 典型的代表就是“結(jié)構(gòu)體” 抽象數(shù)據(jù)類型（Abstract Data Type，ADT） 在復(fù)合數(shù)據(jù)類型基礎(chǔ)上增加了對(duì)數(shù)據(jù)的操作 抽象數(shù)據(jù)類型進(jìn)而進(jìn)化為“類(Class)” 這是一個(gè)跨時(shí)代的進(jìn)步 Class是Object-Oriented的一個(gè)重要概念,12.1從基本數(shù)據(jù)類型到抽象數(shù)據(jù)類型,12.2 結(jié)構(gòu)體的定義12.2.1為什么要定

3、義結(jié)構(gòu)體類型,在程序里表示一個(gè)人（姓名、年齡、性別），怎么表示？ 想表示多個(gè)人呢？ 如何用計(jì)算機(jī)程序?qū)崿F(xiàn)下述表格的管理？,數(shù)組的解決方法,數(shù)組的解決方法,數(shù)據(jù)的內(nèi)存管理方式,數(shù)組的解決方法,分配內(nèi)存不集中，尋址效率不高 對(duì)數(shù)組賦初值時(shí)，易發(fā)生錯(cuò)位 結(jié)構(gòu)顯得零散，不易管理,希望的內(nèi)存分配圖,結(jié)構(gòu)體類型的聲明,聲明了一個(gè)結(jié)構(gòu)體類型,構(gòu)成結(jié)構(gòu)體的變量稱為結(jié)構(gòu)體的成員(Structure Member),結(jié)構(gòu)體的名字稱為結(jié)構(gòu)體標(biāo)簽(Structure Tag),結(jié)構(gòu)體類型的聲明,結(jié)構(gòu)體模板(Structure Template),Dont forget the semicolon!,形成一個(gè)類型聲明的

4、樣板 用于生成結(jié)構(gòu)體變量 但并未聲明結(jié)構(gòu)體變量 因而編譯器不為其分配內(nèi)存,（1）先定義結(jié)構(gòu)體類型，再定義變量名,（2）在定義類型的同時(shí)定義變量,（3）直接定義結(jié)構(gòu)體變量（不指定結(jié)構(gòu)體標(biāo)簽）,12.2.2結(jié)構(gòu)體變量的定義,12.2.3用typedef定義數(shù)據(jù)類型,struct student stu1, stu2;/*It works*/ student stu1, stu2; /*Can this work?*/ struct stu1, stu2; /*Can this work?*/ STUDENT stu1, stu2; /*It works!*/,關(guān)鍵字typedef為一種已存在的類型

5、定義一個(gè)別名，并未定義新類型,STUDENT與struct student類型是同義詞,等價(jià)于,12.2.4結(jié)構(gòu)體變量的初始化,等價(jià)于,注意！,嵌套的結(jié)構(gòu)體（Nested Structure）就是在一個(gè)結(jié)構(gòu)體內(nèi)包含了另一個(gè)結(jié)構(gòu)體作為其成員,12.2.5嵌套的結(jié)構(gòu)體,結(jié)構(gòu)體定義 可以嵌套,訪問結(jié)構(gòu)體變量的成員必須使用成員選擇運(yùn)算符（也稱圓點(diǎn)運(yùn)算符）,12.2.6結(jié)構(gòu)體變量的引用,當(dāng)出現(xiàn)結(jié)構(gòu)體嵌套時(shí)，必須以級(jí)聯(lián)方式訪問結(jié)構(gòu)體成員,【例12.1】演示結(jié)構(gòu)體變量的賦值和引用方法,12.2.6結(jié)構(gòu)體變量的引用,按結(jié)構(gòu)體的成員順序逐一對(duì)相應(yīng)成員進(jìn)行賦值,格式符%02d中2d前面的前導(dǎo)符0表示輸出數(shù)據(jù)時(shí)，若

6、左邊有多余位，則補(bǔ)0,【例12.1】若要從鍵盤輸入結(jié)構(gòu)體變量stu1的內(nèi)容，那么程序如何修改？,兩個(gè)地址有何不同？,【例12.1】若要從鍵盤輸入結(jié)構(gòu)體變量stu1的內(nèi)容，那么程序如何修改？,結(jié)構(gòu)體成員的地址與該成員在結(jié)構(gòu)體中所處的位置及其所占內(nèi)存的字節(jié)數(shù)相關(guān),結(jié)構(gòu)體變量的地址,用運(yùn)算符sizeof獲得結(jié)構(gòu)體大小 sizeof(變量或表達(dá)式) sizeof(類型),12,Why?,printf(%dn, sizeof(SAMPLE);,【例12.2】,12.2.7結(jié)構(gòu)體所占內(nèi)存的字節(jié)數(shù),事實(shí)上，所有數(shù)據(jù)類型在內(nèi)存中都是從偶數(shù)地址開始存放的 且結(jié)構(gòu)所占的實(shí)際空間一般是按照機(jī)器字長(zhǎng)對(duì)齊的 不同的編譯

7、器、平臺(tái)，對(duì)齊方式會(huì)有變化 結(jié)構(gòu)體變量的成員的存儲(chǔ)對(duì)齊規(guī)則是與機(jī)器相關(guān)的 具有特定數(shù)據(jù)類型的數(shù)據(jù)項(xiàng)大小也是與機(jī)器相關(guān)的 所以一個(gè)結(jié)構(gòu)體在內(nèi)存中的存儲(chǔ)格式也是與機(jī)器相關(guān)的,非所有成員變量的內(nèi)存總和,12個(gè)字節(jié),12.3結(jié)構(gòu)體數(shù)組的定義和初始化,12.3結(jié)構(gòu)體數(shù)組的定義和初始化,建立了數(shù)據(jù)庫(kù)中的多條記錄，每條對(duì)應(yīng)一個(gè)學(xué)生信息,【例12.3】利用結(jié)構(gòu)體數(shù)組計(jì)算每個(gè)學(xué)生的平均分,12.4結(jié)構(gòu)體指針的定義和初始化,pt,stu1,STUDENT stu1; STUDENT *pt; pt = ,如何定義指向結(jié)構(gòu)體變量的指針？,STUDENT *pt = ,等價(jià)于,12.4結(jié)構(gòu)體指針的定義和初始化,如何訪

8、問結(jié)構(gòu)體指針變量所指向的結(jié)構(gòu)體成員呢？,STUDENT stu1; STUDENT *pt = ,pt,stu1,通過stu1和成員選擇運(yùn)算符訪問結(jié)構(gòu)體成員 stu1. studentID = 1; 通過pt和指向運(yùn)算符訪問結(jié)構(gòu)體成員 (*pt). studentID = 1; pt - studentID = 1;,12.4結(jié)構(gòu)體指針的定義和初始化,pt,stu1,當(dāng)結(jié)構(gòu)體嵌套時(shí)，如何訪問結(jié)構(gòu)體指針變量所指向的結(jié)構(gòu)體成員？,stu1. birthday. year = 1999; (*pt). birthday. year = 1999; pt - birthday. year = 1999

9、;,STUDENT stu1; STUDENT *pt = ,12.4結(jié)構(gòu)體指針的定義和初始化,STUDENT stu30; STUDENT *pt; pt = stu;,如何定義指向結(jié)構(gòu)體數(shù)組的指針？,STUDENT *pt = stu;,等價(jià)于,STUDENT *pt = ,等價(jià)于,pt,stu30,使用pt+，使pt指向stu1 pt - studentID 等價(jià)于 stu1. studentID,pt,12.4結(jié)構(gòu)體指針的定義和初始化,STUDENT stu30; STUDENT *pt = stu;,如何訪問結(jié)構(gòu)體數(shù)組指針指向的結(jié)構(gòu)體成員？,stu30,12.5向函數(shù)傳遞結(jié)構(gòu)體,向函

10、數(shù)傳遞結(jié)構(gòu)體的單個(gè)成員 復(fù)制單個(gè)成員的內(nèi)容 函數(shù)內(nèi)對(duì)結(jié)構(gòu)內(nèi)容的修改不影響原結(jié)構(gòu) 向函數(shù)傳遞結(jié)構(gòu)體的完整結(jié)構(gòu) 向函數(shù)傳遞結(jié)構(gòu)體的首地址,struct date int year; int month; int day; ; void Func(struct date p) p.year = 2000; p.month = 5; p.day = 22; ,Before function call:1999/04/23,After function call:1999/04/23,結(jié)構(gòu)體變量作函數(shù)參數(shù),【例12.4】,struct date int year; int month; int day;

11、 ; void Func(struct date *p) p-year = 2000; p-month = 5; p-day = 22; ,Before function call:1999/04/23,After function call:2000/05/22,結(jié)構(gòu)體指針作函數(shù)參數(shù),指針作函數(shù)形參 實(shí)參必須為地址值,【例12.5】,struct date int year; int month; int day; ; struct date Func(struct date p) p.year = 2000; p.month = 5; p.day = 22; return p; ,Befo

12、re function call:1999/04/23,After function call:2000/05/22,結(jié)構(gòu)體變量作函數(shù)返回值,【例12.6】,12.5向函數(shù)傳遞結(jié)構(gòu)體,向函數(shù)傳遞結(jié)構(gòu)體的完整結(jié)構(gòu) 復(fù)制整個(gè)結(jié)構(gòu)體成員的內(nèi)容，多個(gè)值 函數(shù)內(nèi)對(duì)結(jié)構(gòu)內(nèi)容的修改不影響原結(jié)構(gòu) 內(nèi)容傳遞更直觀，但開銷大 向函數(shù)傳遞結(jié)構(gòu)體的首地址 用結(jié)構(gòu)體數(shù)組/結(jié)構(gòu)體指針作函數(shù)參數(shù) 僅復(fù)制結(jié)構(gòu)體的首地址，一個(gè)值 修改結(jié)構(gòu)體指針?biāo)赶虻慕Y(jié)構(gòu)體的內(nèi)容 指針傳遞效率高,12.5向函數(shù)傳遞結(jié)構(gòu)體,【例12.7】修改例12.3程序，用結(jié)構(gòu)體數(shù)組作函數(shù)參數(shù)編程并輸出計(jì)算學(xué)生的平均分,12.5向函數(shù)傳遞結(jié)構(gòu)體,【例12.7

13、】修改例12.3程序，用結(jié)構(gòu)體數(shù)組作函數(shù)參數(shù)編程并輸出計(jì)算學(xué)生的平均分,12.5向函數(shù)傳遞結(jié)構(gòu)體,【例12.7】修改例12.3程序，用結(jié)構(gòu)體數(shù)組作函數(shù)參數(shù)編程并輸出計(jì)算學(xué)生的平均分,12.5向函數(shù)傳遞結(jié)構(gòu)體,【例12.7】修改例12.3程序，用結(jié)構(gòu)體數(shù)組作函數(shù)參數(shù)，編程并輸出計(jì)算學(xué)生的平均分,用戶自定義的數(shù)據(jù)類型,結(jié)構(gòu)體（Struct） 把關(guān)系緊密且邏輯相關(guān)的多種不同類型的變量，組織到統(tǒng)一的名字之下 占用相鄰的一段內(nèi)存單元 共用體，也稱聯(lián)合（Union） 把情形互斥但邏輯相關(guān)的多種不同類型的變量，組織到統(tǒng)一的名字之下 占用同一段內(nèi)存單元，每一時(shí)刻只有一個(gè)數(shù)據(jù)起作用,12.6共用體,struct

14、 sample short i; char ch; float f; ;,union sample short i; char ch; float f; ;,printf(%dn, sizeof(struct sample);,8個(gè)字節(jié),i,ch,f,4個(gè)字節(jié),printf(%dn, sizeof(union sample);,【例12.8】,12.6共用體,sizeof(union number)取決于占空間最多的那個(gè)成員變量,同一內(nèi)存單元在每一瞬時(shí)只能存放其中一種類型的成員 起作用的成員是最后一次存放的成員，不能作為函數(shù)參數(shù) 不能進(jìn)行比較操作，只能對(duì)第一個(gè)成員初始化,f,4個(gè)字節(jié),12.6

15、共用體,12.6共用體,12.7 枚舉數(shù)據(jù)類型,枚舉（Enumeration）數(shù)據(jù)類型 描述的是一組整型值的集合 用于當(dāng)某些量?jī)H由有限個(gè)數(shù)據(jù)值組成時(shí) enum weeks SUN, MON, TUE, WED, THU, FRI, SAT; enum weeks today; enum response no, yes, none; enum response answer; today = TUE; answer = yes; enum response no = -1, yes = 1, none = 0;,其值為2,其值為1,下面的結(jié)構(gòu)是什么意思？ struct temp int dat

16、a; struct temp pt; CB下的錯(cuò)誤提示： field pt has incomplete type VC下的錯(cuò)誤提示： pt uses undefined struct temp 下面的結(jié)構(gòu)是什么意思呢？ struct temp int data; struct temp *pt;,可包含指向本結(jié)構(gòu)體類型的指針變量,問題的提出,12.8 動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu) 單向鏈表,struct Link int data; struct Link *next; ;,鏈表（Linked Table）:線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 特點(diǎn)：用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)；存儲(chǔ)單元可以是連續(xù)的，也可是不連續(xù)

17、的,鏈表的定義,鏈表（Linked table）:線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 為表示每個(gè)元素與后繼元素的邏輯關(guān)系，除存儲(chǔ)元素本身信息外，還要存儲(chǔ)其直接后繼信息,兩部分信息組成一個(gè)節(jié)點(diǎn),struct Link int data; struct Link *next; ;,數(shù)據(jù)域：存儲(chǔ)數(shù)據(jù)元素信息,指針域：存儲(chǔ)直接后繼的節(jié)點(diǎn)信息,鏈表的定義,鏈表（Linked Table）:線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 為表示每個(gè)元素與后繼元素的邏輯關(guān)系，除存儲(chǔ)元素本身信息外，還要存儲(chǔ)其直接后繼信息,struct Link int data; struct Link *next; ;,n個(gè)節(jié)點(diǎn)鏈接成一個(gè)鏈表（因?yàn)橹话粋€(gè)指針

18、域，故又稱線性鏈表或單向鏈表）,鏈表的建立,向鏈表中添加一個(gè)新節(jié)點(diǎn),空指針NULL表示鏈表結(jié)尾,鏈表的頭指針：訪問鏈表的關(guān)鍵,鏈表的建立,若原鏈表為空表(head = NULL) ，則將新建節(jié)點(diǎn)p置為頭節(jié)點(diǎn),(1)head = p,(2) pr = p,(3) pr-next = NULL,鏈表的建立,若原鏈表為非空，則將新建節(jié)點(diǎn)p添加到表尾,(1) pr-next = p,(2) pr = p,(3) pr-next = NULL,next,鏈表的刪除操作,若原鏈表為空表，則退出程序 若待刪除節(jié)點(diǎn)p是頭節(jié)點(diǎn)，則將head指向當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)即可刪除當(dāng)前節(jié)點(diǎn),(1) head = p-next,head,(2) free(p),鏈表的刪除操作,若待刪除節(jié)點(diǎn)不是頭節(jié)點(diǎn)，則將前一節(jié)點(diǎn)的指針域指向當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)即可刪除當(dāng)前節(jié)點(diǎn),(1) pr-next = p-next,若已搜索到表尾（p-next = NULL）仍未找到待刪除節(jié)點(diǎn)，則顯示“未找到”,(2) free(p),鏈表的插入操作,若原鏈表為空表，則將新節(jié)點(diǎn)p作為頭節(jié)點(diǎn)，讓head指向新節(jié)點(diǎn)p,(1) head = p,p = (struct link *)malloc(sizeof(struct link); p-next = NULL; p-data = nodeData;