第二章數(shù)據(jù)類型數(shù)據(jù)類型實質上是對存儲器中所存儲的數(shù)據(jù)進行的抽象。它包含了一組值的集合和一組操作。1本章內容1、將類型作為數(shù)據(jù)結構的抽象表示可以分為三個層次的抽象，即

內部類型、用戶定義類型和抽象數(shù)據(jù)類型2、數(shù)據(jù)類型與編譯有關的幾個問題3、類型的實現(xiàn)模型22.1引言1.數(shù)據(jù)類型的作用實現(xiàn)了數(shù)據(jù)抽象從機器的具體特征中解脫出來提高了編程效率3語言的某種特定的數(shù)據(jù)抽象受到兩個因素的影響：語言所面向的機器（只提供定點運算或同時提供浮點運算）；語言所面向的應用領域。42.數(shù)據(jù)類型的分類內部類型自定義類型5語言根據(jù)所面向的機器和應用定義了不同的數(shù)據(jù)類型，這些類型稱為內部類型(語言定義類型

)。自Pascal語言開始，語言提供了由用戶定義類型的方法。采用這類方法由用戶自己定義的數(shù)據(jù)類型稱為用戶定義類型(自定義類型)。6

第二節(jié)內部類型一.內部類型的特點內部類型反映基本硬件特性在語言級,內部類型是共用某些操作的數(shù)據(jù)對象的抽象表示7

二.內部類型的優(yōu)越性1.基本表示的不可見性基本位串對程序員是不可見的。優(yōu)點：導致不同的程序設計風格可寫性可讀性可修改性例：25+9=34

基本表示00011001+00001001

結果001000108

進行靜態(tài)類型檢查,如非法運算,形實參類型匹配（某些動態(tài)特性不一定能查出，如i/j中j=0）2.編譯時能檢查變量使用的正確性3.編譯時可以確定無二義的操作超載(多態(tài))的概念:運算符的意義依賴于操作數(shù)的類型。如“+”可以表示整數(shù)加或實數(shù)加編譯時,可拒絕混合運算,或提供類型轉換指令合理地使用超載,可以提高語言的可讀性和可用性9

4.精度控制

可以通過數(shù)據(jù)類型顯式定義數(shù)據(jù)的精度精度說明有利于空間優(yōu)化精度說明可作為檢查的一種手段精度說明有利于程序的修改10

第三節(jié)用戶定義類型許多語言除了定義內部類型外，還允許程序員定義新的數(shù)據(jù)類型，規(guī)定基本數(shù)據(jù)對象的聚合,乃至聚合的聚合。Howtodefine?11

1.笛卡爾積定義：N個集合A1,A2,…,An的笛卡爾積表示為A1A2…An，它是一個集合,其元素為(a1,a2,…,an),其中aiAi在語言中對應什么構造？12

任意正多邊形integer

real表示為邊數(shù)每邊邊長在COBOL和PASCAL中稱為記錄；在ALGOL中稱為結構。

注意：語言把笛卡爾積數(shù)據(jù)對象看成由若干個域組成，每個域有一個唯一的名字；通常用域名來選取域，對它進行修改；例：對于如前定義的多邊形，有兩個域no-of-edges和edge-size，Structpolygon{intno-of-edges;doubleedge-size}t1;若t1是一個邊長為7.53的等邊三角形(3,3.75)，則可以寫為：t1.no-of-edges=3;t1.edge-size=3.75;13

2.有限映像（射）定義：從定義域類型DT（domaintype）的值的有限集合，到值域類型RT（rangetype）的值的有限集合的函數(shù)稱為有限映像（射）。在語言中對應什么構造？14

有限映像（射）的一些特點在高級語言中通常體現(xiàn)為數(shù)組構造；值域對象通過下標選取下標越界會出錯，動態(tài)檢查下標可用來選取值域的多個元素（如數(shù)組的分割、切片）SNOBOL4的ARRAY構造符并不要求值域集的所有元素是同一類型的

例如：Chararray[50]可看成是從0到49的整數(shù)到字符集的有限映像15

有限映像（射）的一些特點

DT到相應值的特定子集的綁定策略：

.編譯時綁定(靜態(tài)數(shù)組).對象建立時綁定(執(zhí)行到分程序時,

動態(tài)數(shù)組).對象處理時綁定(對APL，子集范圍可變)16

3.序列定義：序列由任意多個數(shù)據(jù)項組成,這些數(shù)據(jù)項稱為該序列的成分,且類型相同（記為CT）。串的一般操作有4種：連接首項選取尾項選取子串例：串是從所周知的序列，其成分類型為字符；順序文件的思路也來自序列的概念17

4.遞歸定義：若數(shù)據(jù)類型T包含屬于同一類型T的成份，那么類型T稱為遞歸類型。遞歸類型的特點：允許在類型定義中使用被定義類型的名字指針是建立遞歸數(shù)據(jù)對象的重要手段例：二叉樹可通過遞歸類型來定義。它的左子樹和右子樹分別是另一棵二叉樹。18

5.判定或定義：判定或是一個選擇對象結構的構造機制,規(guī)定在兩個不同選擇對象之間作出適當?shù)倪x擇;每一選擇對象結構稱為變體。例如：PASCAL和ADA中的變體記錄;C和ALGOL68中的聯(lián)合。19結構、共用體舉例namenumtypeScore

situationchen0000012teacherHardworkingZhang2000112student90,88,99,89

20結構、共用體舉例Struct{ charname[10]; Intnum; Chartype[8]; Union { floatscore[10]; Charsituation[40]; }state;}person[2];21

定義：類型T的元素所有子集的集合，稱為冪集,記為Powerset(T),T稱為基類型。冪集類型的操作：

由于具有該類型的變量的值是一個子集，因此它們的基本操作是集合的操作，比如：聯(lián)合、與、以及測試某個元素是否在一個集合中等。6.冪集22

小結1.程序語言允許程序員以上六種機制來定義復雜的數(shù)據(jù)對象（新的類型）；2.新的類型可以通過非顯式的方式說明；3.也可通過顯式的方式說明；4.顯示定義有如下優(yōu)點：可讀性（選擇名字）可修改性（不修改變量說明）可分性（重復使用）一致性檢查例如：struct{double:radius;doubleangle;}complexc1,c2,c3;例如：structcomplex{double:radius;doubleangle;}complexc1,c2,c3;23structstudent{charname[48];intage;…};可分性可分性概念用得比較普遍，C語言的函數(shù)就使用了可分性。把程序中相同的代碼“分離”出來，用一個名字來標識，待使用這段代碼時，通過該名字調用該段代碼即可。

內容回顧2.數(shù)據(jù)類型1.編譯時-源程序2.運行時-代碼段+活動記錄3.活動記錄4.別名、副作用1.程序單元1.值的集合+操作的集合2.六種數(shù)據(jù)類型聚合方式笛卡爾積有限映射序列遞歸冪集判定或記錄、結構數(shù)組字符串、順序文件二叉樹聯(lián)合、變體記錄集合25

第四節(jié)PASCAL語言數(shù)據(jù)類型結構1.非結構類型內部類型integer,real,boolean,char有序類型每一元素都有唯一的前驅和后繼如:整型,布爾型,字符型定義新的有序類型的方法枚舉型其值不能直接讀/寫子界型動態(tài)檢查范圍例：typeday=(sunday,monday,tuseday,wednesday,thursday,friday,saturday);//枚舉typework_day=monday..friday;//子界varclass_day:work_day;class_day:=succ(class_day); //后繼……26

2.聚合構造數(shù)組構造構造符ARRAY允許程序員定義有限映像；數(shù)組構造的一般形式為：

array[t1]of[t2]元素（值域）的類型；下標（定義域）的類型；

注意：PASCAL把下標類型不同的數(shù)組看成不同的類型typea1=array[1..50]ofinteger;typea2=array[1..70]ofinteger;=?27

!這樣定義的數(shù)組類型會產生嚴重問題，使得形式參數(shù)定義的數(shù)組和實際參數(shù)的數(shù)組類型不一致；解決辦法：引入符合數(shù)組概念--維數(shù)相同，成分類型相同的數(shù)組；符合數(shù)組可以形、實參數(shù)匹配。例：proceduresort(vara:array[low..high:integer]ofctype);vari:integer;more:boolean;begin{sort}……end{sort}28

2)記錄構造構造符RECORD用以定義笛卡爾積，一般形式為：Recordfield_1:type_1;field_2:type_2;… field_n:type_n;end記錄可以整體訪問，也可用圓點“.”作為選擇符訪問單個的域；假設t，p是前面定義的多邊形，t.no_of_edges:=3;t.edge_size:=7.53;p:=t;29

PASCAL的變體記錄typedept=(house,sports,drugs,food,liquor);month=1..12;item=recordprice:real;caseavailable:booleanoftrue:(amount:integer;where:dept);false:(month_expected:month)end;變體記錄item標識符域available，記錄的判定成分

注意：PASCAL允許程序員訪問記錄結構的所有域，包括標識符域。例如，如果i1和i2被說明，則可對它們進行如下操作：vari1,i2:item:……i1.price:=5.24;i1.available:=true;i1.amount:=29;i1.where:=liquor;i2.price:=324.99;i2.available:=false;i2.month_expect:=8;30

程序的執(zhí)行結果priceavailableamountwhere5.24true29liquori1priceavailablemonth_expected324.99false8i231

變體記錄的特點改變一個變體記錄的標識符，在概念上建立了一個新記錄；變體記錄在同一塊存儲區(qū)上重疊存放所有變體；變體記錄允許程序員根據(jù)每個變體的類型，以不同的觀點來解釋存儲在該區(qū)域中的位串；PASCAL變體記錄的缺點使用變體記錄不安全可以對變體賦值可以改變變體標識符標識符域的標識符可省缺recordprice:realcasebooleanoftrue:(amount:integer;where:dept);false:(mouth_expected:month)end32

集合構造PASCAL語言的SET構造符是冪集構造受限制的形式，基類型只能是有序類型，而不能是實數(shù)、集合類型。例:typevegetable=(bean,cabbage,carrot,celery,lettuce,onion,mushroom,zucchizi);varmy_salad,leftover:setofvegetable;33

文件構造PASCAL文件是任意類型的諸元素的序列；PASCAL文件僅能順序處理；只能進行PUT和GET操作；例:typepattern=record…end;tape=fileof

pattern;vart1,t2:tape;Get操作把下一個元素讀到緩沖區(qū)put操作把緩沖區(qū)中的元素附加到文件末尾34

指針是PASCAL的第三類數(shù)據(jù)類型，是非結構的，可用來構造遞歸結構；指針可引用匿名數(shù)據(jù)對象，這類對象由建立語句NEW顯示分配在堆上；空指針nil的使用；指針的操作:賦值,比較(相等或不等)PASCAL指針只能指向匿名數(shù)據(jù)對象，不能指向在棧上分配的的單元3.指針35typetree_ref=binary_tree_node;binary_tree_node=recordinfo:char;left,right:tree_refend;pointer=node;node=recorddata:integer;next:pointerend;指針例子36

Pascal類型非結構類型指針類型(遞歸)結構類型內部類型整型實型字符型布爾型枚舉類型子界類型記錄類型(迪卡爾積)變體記錄(判定或)數(shù)組集合文件4.小結37

第六節(jié)C語言數(shù)據(jù)類型結構1.非結構類型：分為內部類型和用戶自定義類型非結構內部類型有整型、實型和字符型類型類型標志符數(shù)值范圍占用字節(jié)數(shù)基本型int-32768327672短整型Short-32768327672長整型Long-231(231-1)4無符號整型Unsigned0655352無符號短整型Unsignedshort0655352無符號長整型Unsignedlong0(232-1)438

實型又稱浮點型，其值是實數(shù)的一個子集，分為單精度和雙精度兩種類型字符型數(shù)據(jù)的值是一個有限字符集的元素；在C語言中，int類型與char類型在存儲中沒有本質區(qū)別；-308308-103081030815168Double雙精度型-3838-1038103874Float單精度型階的范圍數(shù)值范圍能表示數(shù)值的有效位點用字節(jié)數(shù)類型標志符類型浮點型數(shù)據(jù)類型的特性

注意：C語言中沒有布爾（bool)類型；0表示false，非0表示true。39

用戶自定義的非結構類型用戶自定義的非結構類型在C語言中稱為枚舉類型（enum）enumbool{false,true};或typedefenum{false,true}bool;（1）定義了一個新類型bool（2）bool數(shù)據(jù)類型的取值為false和true（3）定義了一個順序：false<true（4）可對這個類型的變量進行賦值和比較等操作enumbool{false,true};boolb;b=true;if(b==true){……}40

2.聚合構造（1）數(shù)組實現(xiàn)有限映像說明的格式<類型說明符><數(shù)組名>[常量表達式]例如：intintarr[5];charchararr[255];boolboolarr[3];

注意：C語言中數(shù)組的下標總是從0開始。41

可以定義多維數(shù)組說明的格式<類型說明符><數(shù)組名>[常量表達式]…[常量表達式]例如：floatfarr[3][4];charc[2][2][2];C語言的數(shù)組按行存放對數(shù)組名的處理相當于指針數(shù)組a[3][4]的存放次序為：a[0][0]a[0][1]a[0][2]a[0][3]a[1][0]a[1][1]a[1][2]a[1][3]a[2][0]a[2][1]a[2][2]a[2][3]inta[10];int*pa;pa=a;42

（2）結構C語言中構造符struct支持笛卡爾積說明的格式struct<結構體名>{成員表列}；成員表列由若干個成員類型說明組成：

<類型標識符><成員名>；例如：structstudent{ intnum; charname[2]; charsex; intage; floatscore; charaddr[30]; }43

注意：C語言中結構不能整體賦值和輸出，只能對其中的各個成員分別進行操作。在內存中，結構的各成員依次存放；結構體可以嵌套；例如：structstudentme,you;strcpy(,“john”);me.sex=‘M’;me.age=21;me.score=80;strcpy(me.addr,“UESTC”);44

（3）聯(lián)合

C語言中構造符union（聯(lián)合）支持判定或聯(lián)合結構舉例：

uniondata{ inti; charc; floatf; } uniondataa,b,c;a.i=2;a.c=‘s’;a.f=3.14;（1）C語言中聯(lián)合中沒有標識符域；（2）單元中的值的類型，取決于程序員的使用；45

（4）文件C語言中文件是一個字符序列；分為ASCII碼文件和二進制文件；C語言中文件的預定義格式如下：

typedefstruct{ int_fd; int_cleft; int_mode; char*_next; char*_buf; }FILE;文件名緩沖區(qū)中剩下的字符數(shù)文件操作模式下一個字符指針緩沖區(qū)指針46

3.指針

C語言中的指針是第三種數(shù)據(jù)類型，是非結構類型；可用來構造結構類型；支持遞歸；利用指針定義遞歸結構的例子：

structtree{ charday; structtree*lchild; structtree*rchild; }; structtree*my_tree;47

4.空類型

C語言中有一種特殊的數(shù)據(jù)類型void，稱為空類型；是一種非結構類型；有兩個主要用途：用來表示一個無返回值的函數(shù)用來表示不確定類型的指針例：voidmain(){ inti; i=1;}例如：void*p;表示這是一個指針，它的值是一個地址，但不指明p指向的值是什么類型。48

5.C數(shù)據(jù)類型小結C數(shù)據(jù)類型非結構型結構型指針類型(遞歸)內部類型枚舉類型數(shù)組類型（有限映象）聯(lián)合類型（判定或）結構類型（笛卡爾積）（文件）（序列）整型空類型實型字符型單精度型雙精度型49

第八節(jié)抽象數(shù)據(jù)類型1.用戶定義類型與內部類型的異同都建立某種基本表示的抽象內部類型:對二進制位串的抽象；用戶定義類型:對內部類型和已定義的用戶定義類型的數(shù)據(jù)作為基本表示的抽象每一類型都關聯(lián)一組操作內部類型隱蔽了基本表示，不能對它的成分進行操作;用戶定義類型具有更高級別的抽象，可以對其基本表示的成分進行操作。能不能仿照內部類型，隱藏用戶自定義類型的內部信息？50

2.抽象數(shù)據(jù)類型的定義滿足下述特性的用戶定義類型稱為抽象數(shù)據(jù)類型:在實現(xiàn)該類型的程序單元中,建立與表示有關的基本操作;對使用該類型的程序單元來說,該類型的表示是隱蔽的。3.在描述實現(xiàn)的程序單元中進行修改1.對象的表示是被保護的，外界不能對它進行直接操作2.隱蔽了表示的細節(jié)，通過過程來訪問抽象數(shù)據(jù)對象51

1.SIMULA67的類機制2.CLU的抽象數(shù)據(jù)類型-簇3.Ada的抽象數(shù)據(jù)類型4.Modula-2的抽象數(shù)據(jù)類型52

C++語言中的抽象數(shù)據(jù)類型稱為類（class），類的實例稱為對象（object）；class<類名>{private:

私有段數(shù)據(jù)定義；私有段函數(shù)定義；

protected:

保護段數(shù)據(jù)定義；保護段函數(shù)定義；

public:

公有段數(shù)據(jù)定義；公有段函數(shù)定義；

}C++語言類定義的一般形式5.C++語言的抽象數(shù)據(jù)類型C++的類滿足抽象數(shù)據(jù)類型的條件（1）和（2）?53

類的實例是對象，對象繼承類中的數(shù)據(jù)和方法封裝、繼承、多態(tài)C++支持重載和多態(tài)C++的繼承性通過派生類來實現(xiàn)虛函數(shù)、抽象類54

第九節(jié)類型檢查對數(shù)據(jù)對象的類型和使用的操作是否匹配的一致性檢查稱為類型檢查；語言的類型檢查分為靜態(tài)檢查（staticchecking）和動態(tài)檢查（dynamicchecking）;靜態(tài)檢查使程序更正確更有效動態(tài)檢查使編程方便,但影響了可讀性,且降低了執(zhí)行效率語言按類型可分為無類型語言、弱類型語言和

強類型語言；在編譯時進行的檢查在運行時進行的檢查語言沒有類型定義語言的類型檢查不能全部在編譯時完成，有些要在運行時才能完成語言的類型檢查全部在編譯時完成55

理由：編譯時,不能確定一個過程中的過程參數(shù)和子程序參數(shù)類型Pascal的子界類型不能靜態(tài)檢查變體記錄的標識符可以在運行時改變Pascal沒有嚴格規(guī)定類型的一致性規(guī)則procedurewho_knows(i,j:integer;proceduref);vark:boolean;begink:=j<i;ifkthenf(k)elsef(j)end;如:a:=b+c;且a、b、c均屬于子界類型1..10PASCAL是非強類型語言56

第九節(jié)類型轉換將一個類型的值轉換成另一個類型的值，稱為類型轉換；類型轉換分為拓展（widening）和收縮（narrowing）；在某些語言中，類型轉換的要求和規(guī)則是隱式的，它由編譯器自動生成類型轉換的代碼；一般來說，語言對基本類型提供適當?shù)念愋娃D換，而對復合類型或用戶自定義類型不提供轉換；轉換之后的類型值的集合包含轉換之前的類型值的集合；例如：整型實型轉換之前的類型值的集合包含轉換之后的類型值的集合；例如：實型整型1.截斷2.舍入法57

一些語言規(guī)定的轉換規(guī)則：FORTRAN語言：轉換規(guī)則隱式給出；轉換規(guī)則根據(jù)類型和類型之間的優(yōu)先級來確定；由低級類型向高級類型轉換；FORTRAN的類型優(yōu)先級為：COMPLEX>DOUBLEPRECISION>REAL>INTEGERPASCAL語言：只允許整數(shù)到實數(shù)，以及子界類型到整數(shù)的轉換；其他的轉換必須顯示處理varr:real;i:integer;i:=r;？應寫為varr:real;i:integer;i:=round(r);58

ALGOL68語言：完全的、形式化的隱式轉換規(guī)則；它一共給出6種隱式轉換規(guī)則；Ada語言：必須顯示轉換；59

隱式轉換發(fā)生在下述的情況下：混合運算：級別低的類型向級別高的類型值轉換。將表達式的值賦給變量：表達式的值向變量類型的值轉換。實參向函數(shù)形參傳值：實參的值向形參的值進行轉換。函數(shù)返回值：返回值向函數(shù)返回類型的值進行轉換。注意語言規(guī)定的轉換規(guī)則

第十節(jié)類型等價若T1和T2是兩個類型，T1的任何值都可以賦予T2類型的變量，反之亦然，T1類型的實參可以對應類型T2的形參，反之亦然，則稱T1和T2是相容的，或等價的；61

第十節(jié)類型等價有兩種類型的相容性概念：①名字等價:兩個變量的類型名相同62structRecA{charx;inty;};typedefstructRecARecA;structRecAa;RecAb;structRecAc;struct{charx;inty;}d;a和c是名字等價，b和d與其他任何變量都不是名字等價。struct{charx;inty;}d，e;struct{charx;inty;}d;struct{charx;inty;}e;不等價第十節(jié)類型等價有兩種類型的相容性概念：②結構等價兩個變量的類型具有相同的結構。63structRec1{charx;inty;charz[10];};structRec2{charx;inty;charz[10];};structRec3{inty;charx;charz[10];};Rec1和Rec2是結構等價，Rec1和Rec3不是結構等價。structRec1{charx;inty;}；structRec2{chara;intb;}；

第十節(jié)類型等價兩種相容性實現(xiàn)時的比較①名字等價的實現(xiàn)比較簡單②結構等價的實現(xiàn)需要的模式匹配過程可能十分復雜64

第十一節(jié)實現(xiàn)模型在實現(xiàn)模型中，數(shù)據(jù)用描述符和數(shù)據(jù)對象來表示；描述符用來描述數(shù)據(jù)對象的所有屬性只考慮原理性的實現(xiàn)，不考慮效率以PASCAL語言為例

描述符:描述數(shù)據(jù)對象的所有屬性數(shù)據(jù)數(shù)據(jù)對象(存儲區(qū)及其值)65

1.內部類型和用戶定義的非結構類型的實現(xiàn)模型描述符一般由“類型”和一個指針組成integer描述符數(shù)據(jù)對象整數(shù)變量的表示real描述符實型變量的表示數(shù)據(jù)對象子界的描述符必須包括子界的界值布爾型和字符型可以壓縮存儲66

2.結構類型的實現(xiàn)模型笛卡爾積各成分順序排列（數(shù)據(jù)）描述符包含:類型名、構造符、若干三元式。每個域對應一個三元式(選擇符名,域類型,指針)每個成分占整數(shù)個可編址的存儲單元(字編址或字節(jié)編址）67

typet=recorda:real；

b:integer；

end；數(shù)據(jù)對象浮點值定點值描述符類型名構造符選擇符選擇符類型類型引用引用trecordarealbinteger域1域268

有限映像為每一成分分配整數(shù)個可編址的存儲單元描述符包括:類型名、構造符、定義域的基類型、下界、上界、成分類型、單元個數(shù)、首地址內情向量；69地址公式的計算若定義域類型是子界m..n，每個元素占k個存儲單元，那么，按照k*(i-m)計算a[i]從首地址b到所分配的存儲之間的位移。

a[i]的地址可以寫成

b+k*(i-m）=b-k*m+k*i=b'+k*i其中，b’=b-k*m是編譯時能計算出的

例：typea=array[1..10]ofreal;描述符類型名構造符基類型成分類型下界單元個數(shù)上界引用aarrayinteger1real1下標類型10數(shù)據(jù)對象浮點值浮點值浮點值71

序列PASCAL中的串長度靜態(tài)可定；靜態(tài)分配；其他語言中（如SNOBOL4和ALGOL68中），可變長串的表示:靜