第02章數(shù)據(jù)類型

1、1第2章 數(shù)據(jù)類型數(shù)據(jù)類型數(shù)據(jù)類型實(shí)質(zhì)上是對存儲器中所存儲的數(shù)據(jù)進(jìn)行的抽象。數(shù)據(jù)類型作為數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的抽象表示，可以分為三個層次的抽象，即內(nèi)部類型內(nèi)部類型、用戶定義類型用戶定義類型和抽抽象數(shù)據(jù)類型象數(shù)據(jù)類型。數(shù)據(jù)類型包含一組值值和一組操作操作。22.1 引言1. 數(shù)據(jù)類型的作用實(shí)現(xiàn)了數(shù)據(jù)抽象從機(jī)器的具體特征中解脫出來提高了編程效率32. 數(shù)據(jù)類型的分類內(nèi)部類型內(nèi)部類型語言根據(jù)所面向的機(jī)器和應(yīng)用定義了不同的數(shù)據(jù)類型，這些類型稱為內(nèi)部類型（語言定義類型）。用戶定義類型用戶定義類型語言提供了由用戶定義類型的方法。采用這類方法由用戶自己定義的數(shù)據(jù)類型稱為用戶定義類型（自定義類型） 。42.2 內(nèi)部

2、類型1. 內(nèi)部類型的特點(diǎn)反映基本硬件特性硬件特性在語言級，同一類型數(shù)據(jù)的操作操作使用共用的抽象抽象表示表示（如+、-、*、/）。52. 內(nèi)部類型的優(yōu)越性1) 基本表示基本表示的不可見性不可見性基本位串對程序員是不可見的。兩個整數(shù)相加25+9，結(jié)果為34基本表示：00011001+00001001 結(jié)果：00100010 62) 編譯時編譯時能檢查變量使用的正確性能夠進(jìn)行靜態(tài)靜態(tài)類型檢查如：非法運(yùn)算；形參、實(shí)參類型匹配73) 編譯時可以確定無二義的操作操作超載（多態(tài)）：運(yùn)算符的意義依賴于操作數(shù)的類型。如：“+”可以表示整數(shù)或?qū)崝?shù)加。編譯時，拒絕混合運(yùn)算，或提供類型轉(zhuǎn)換指令合理地使用超載，可以提高

3、可讀性和可用性。84) 精度精度控制可以通過數(shù)據(jù)類型顯式定義數(shù)據(jù)的精度如：float、double92.3 用戶定義類型語言除內(nèi)部類型外，還允許用戶借助于語言提供的數(shù)據(jù)的組合（聚合）組合（聚合）機(jī)制，自己定義自己定義新的數(shù)據(jù)類型。許多語言允許程序員規(guī)定基本數(shù)據(jù)對象的聚合基本數(shù)據(jù)對象的聚合（乃至聚合的聚合聚合的聚合）。101. 笛卡爾積n個集合A1，A2，An的笛卡兒積： A1A2An它是一個集合，其元素是有序的n元式（a1，a2，an）11例：一個正多邊形用一個整數(shù)(正多邊形邊數(shù))和一個實(shí)數(shù)(邊的長度)來描述，那么任意正多邊形都是笛卡兒積 integerreal的一個元素。12笛卡兒積：Pas

4、cal語言的記錄C語言的結(jié)構(gòu)132. 有限映像1) 定義：從定義域定義域類型的值的有限集合，到值域值域類型的值的有限集合的函數(shù)（映射）稱為有限映像。array1.50 of char整數(shù)1至50到字符集的有限映像142) 值域?qū)ο笸ㄟ^下標(biāo)下標(biāo)選取3) 下標(biāo)越界越界會出錯，動態(tài)檢查4) 有些語言不要求值域集的所有元素元素是同一類型類型155) 定義域定義域到值域值域的綁定策略：編譯時綁定 (靜態(tài)靜態(tài)數(shù)組 C)對象建立時綁定 (半動態(tài)半動態(tài)數(shù)組 ALGOL)對象處理時綁定 (動態(tài)動態(tài)數(shù)組 APL)163. 序列1) 任意多個數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)稱為該序列的成分，且類型相同類型相同2) 文件的思

5、想來自序列的概念， 按順序進(jìn)行讀寫174. 遞歸若數(shù)據(jù)類型T包含屬于同一類型同一類型T的成分遞歸類型。1) 允許在類型定義中使用被定義類型的名字2) 指針是建立遞歸數(shù)據(jù)對象的重要手段185. 判定或一個選擇對象結(jié)構(gòu)的構(gòu)造機(jī)制，規(guī)定在兩個不同選不同選擇對象擇對象之間作出適當(dāng)?shù)倪x擇。每一選擇對象結(jié)構(gòu)稱為變體。C的聯(lián)合(union) PASCAL的變體記錄196. 冪集類型T的元素所有子集子集的集合，稱為冪集, T稱為基基類型類型。202.4 C語言數(shù)據(jù)類型212.5 Pascal語言數(shù)據(jù)類型222.6 Ada語言數(shù)據(jù)類型232.7 Java語言數(shù)據(jù)類型自學(xué)自學(xué)242.8 抽象數(shù)據(jù)類型用戶定義類型用

6、戶定義類型與內(nèi)部類型內(nèi)部類型的異同1. 都建立了某種基本表示基本表示的抽象抽象內(nèi)部類型：對二進(jìn)制位串二進(jìn)制位串的抽象。用戶定義類型：對內(nèi)部類型內(nèi)部類型和已定義的用戶定已定義的用戶定義類型義類型作為基本表示的抽象。252. 都關(guān)聯(lián)了一組操作操作3. 隱蔽性隱蔽性不同內(nèi)部類型：基本表示是不可見不可見的，不能對它的成分進(jìn)行操作；用戶定義類型：基本表示是可見可見的，可以對它的成分進(jìn)行操作。26抽象數(shù)據(jù)類型滿足下述特性的用戶定義類型稱為抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型1. 在實(shí)現(xiàn)（定義）實(shí)現(xiàn)（定義）這個新類型的程序中（內(nèi)部），基本表示是可見的可見的。2. 對使用使用這個新類型的程序中（外部），基本表示是不可見的

7、不可見的。272.8.1 SIMULA 67語言的類機(jī)制自學(xué)自學(xué)282.8.2 CLU語言的抽象數(shù)據(jù)類型自學(xué)自學(xué)292.8.3 Ada語言的抽象數(shù)據(jù)類型自學(xué)自學(xué)302.8.4 Modula 2語言的抽象數(shù)據(jù)類型自學(xué)自學(xué)312.8.5 C+語言的抽象數(shù)據(jù)類型自學(xué)自學(xué)322.8.6 Java抽象數(shù)據(jù)類型自學(xué)自學(xué)332.9 類型檢查對數(shù)據(jù)對象的類型類型和使用的操作操作是否匹配匹配的一致性檢查稱為類型檢查類型檢查。34靜態(tài)檢查和動態(tài)檢查靜態(tài)靜態(tài)檢查使程序更正確，更有效。動態(tài)動態(tài)檢查使編程方便，但影響了可靠性，且降低了執(zhí)行效率。35語言按數(shù)據(jù)類型分類語言可以按數(shù)據(jù)類型進(jìn)行分類，可分為：無類型無類型語言：

8、沒有類型定義。強(qiáng)類型強(qiáng)類型語言：所有類型檢查都在編譯時編譯時完成。弱類型弱類型語言：類型檢查全部或部分要在運(yùn)行時運(yùn)行時完成。362.10 類型轉(zhuǎn)換某種類型的值轉(zhuǎn)換為另一種類型的值。1. 語言應(yīng)該提供類型轉(zhuǎn)換機(jī)制隱式隱式（自動自動）轉(zhuǎn)換顯式顯式（強(qiáng)制強(qiáng)制）轉(zhuǎn)換372.兩種轉(zhuǎn)換方式拓展拓展：轉(zhuǎn)換之后的類型值集合包含轉(zhuǎn)換之前類型值集合（整型實(shí)型）收縮收縮：若轉(zhuǎn)換之前類型值集合包含轉(zhuǎn)換之后類型值集合（實(shí)型整型）38在某些語言中，類型轉(zhuǎn)換的要求和規(guī)則都是隱式隱式的FORTRAN 語言；在某些語言中，類型轉(zhuǎn)換的要求和規(guī)則都是顯式顯式的 ADA語言。在某些語言中，類型轉(zhuǎn)換的要求和規(guī)則有隱式隱式、顯式顯式的兩

9、類 C語言。393. 隱式轉(zhuǎn)換隱式轉(zhuǎn)換常發(fā)生在下述的情況下?；旌线\(yùn)算混合運(yùn)算：級別低的類型向級別高的類型轉(zhuǎn)換。將表達(dá)式的值賦給變量將表達(dá)式的值賦給變量：表達(dá)式的值向變量類型的值轉(zhuǎn)換。40實(shí)參向函數(shù)形參傳值實(shí)參向函數(shù)形參傳值：實(shí)參的值向形參的值進(jìn)行轉(zhuǎn)換。函數(shù)返回值函數(shù)返回值：返回的值向函數(shù)返回類型的值進(jìn)行轉(zhuǎn)換。412.11 類型等價T1和T2是兩個類型T1的任何值都可以賦予T2的變量，反之亦然；T1實(shí)參可對應(yīng)T2形參，反之亦然，則T1和T2類型等價等價（相容相容）。42兩種類型等價，1. 名字等價名字等價兩個變量的類型名相同。2. 結(jié)構(gòu)等價結(jié)構(gòu)等價兩個變量的類型具有相同的結(jié)構(gòu)。驗(yàn)證：用用戶定義類

10、型的定義來代替用戶定義名，重復(fù)這一過程，直到?jīng)]有用戶定義類型名為止。432.12 實(shí)現(xiàn)模型在實(shí)現(xiàn)模型中，一個數(shù)據(jù)用描述符描述符和數(shù)據(jù)對象數(shù)據(jù)對象來表示。數(shù)據(jù)對象：存儲區(qū)及其值描述符：描述數(shù)據(jù)對象的屬性44內(nèi)部類型描述符一般由類型描述類型描述和一個指針指針組成。如整數(shù)類型：45實(shí)數(shù)類型：46結(jié)構(gòu)類型1. 笛卡兒積Pascal記錄的類型說明type t = record a : real； b : integer end 47482. 有限映像Pascal的數(shù)組說明type a = array0.10 of real49503. 序列可變長串的表示514. 判定或Pascal的變體記錄 type v = record a : integer; case b : boolean of true :( c : integer ); false :( d : integer； e : real ) end 52535. 冪集對冪集可以通過訪問的存儲空間（例如機(jī)器字）來有效地實(shí)現(xiàn)。若在某個集合S中出現(xiàn)基類型的第i個元素，那么與 S相關(guān)聯(lián)的字的第i個位置為“1”。54兩個集合的操作操作：聯(lián)合聯(lián)合通過它們相關(guān)聯(lián)的字的“或”操作來實(shí)現(xiàn)。交集交集通過“與”操作來實(shí)現(xiàn)。556. 指針指針變量的表示類似于內(nèi)部類型，只是其值為地址地址。567. 層次結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)對象的