程序設(shè)計語言與編譯原理-第二章數(shù)據(jù)類型課件

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

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

)。自Pascal語言開始，語言提供了由用戶定義類型的方法。采用這類方法由用戶自己定義的數(shù)據(jù)類型稱為用戶定義類型(自定義類型)。6語言根據(jù)所面向的機器和應(yīng)用定義了不同的數(shù)據(jù)類型，這些類

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

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

基本表示00011001+00001001

結(jié)果001000108二.內(nèi)部類型的優(yōu)越性1.基本表示的不可見性例：25+9=

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

4.精度控制

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

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

1.笛卡爾積定義：N個集合A1,A2,…,An的笛卡爾積表示為A1

A2

…

An，它是一個集合,其元素為(a1,a2,…,an),其中ai

Ai在語言中對應(yīng)什么構(gòu)造？121.笛卡爾積定義：N個集合A1,A2,…,An的笛卡爾積

任意正多邊形integer

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

注意：語言把笛卡爾積數(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任意正多邊形integerreal表示為邊數(shù)每邊邊長

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

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

例如：Chararray[50]可看成是從0到49的整數(shù)到字符集的有限映像15有限映像（射）的一些特點在高級語言中通常體現(xiàn)為數(shù)組構(gòu)造；

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

DT到相應(yīng)值的特定子集的綁定策略：

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

動態(tài)數(shù)組).對象處理時綁定(對APL，子集范圍可變)16有限映像（射）的一些特點DT到相應(yīng)值的特定子集的綁定策略

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

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

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

situationchen0000012teacherHardworkingZhang2000112student90,88,99,89

20結(jié)構(gòu)、共用體舉例namenumtypeScorechen00結(jié)構(gòu)、共用體舉例Struct{ charname[10]; Intnum; Chartype[8]; Union { floatscore[10]; Charsituation[40]; }state;}person[2];21結(jié)構(gòu)、共用體舉例Struct21

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

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

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

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

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

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

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

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

272.聚合構(gòu)造數(shù)組構(gòu)造元素（值域）的類型；下標(biāo)（定義域）的類

!這樣定義的數(shù)組類型會產(chǎn)生嚴(yán)重問題，使得形式參數(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!這樣定義的數(shù)組類型會產(chǎn)生嚴(yán)重問題，使得形式參數(shù)定義的數(shù)

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

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標(biāo)識符域available，記錄的判定成分

注意：PASCAL允許程序員訪問記錄結(jié)構(gòu)的所有域，包括標(biāo)識符域。例如，如果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;30PASCAL的變體記錄typedept=(house,s

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

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

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

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

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

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

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

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

實型又稱浮點型，其值是實數(shù)的一個子集，分為單精度和雙精度兩種類型字符型數(shù)據(jù)的值是一個有限字符集的元素；在C語言中，int類型與char類型在存儲中沒有本質(zhì)區(qū)別；-308308-10308

1030815168Double雙精度型-3838-1038

103874Float單精度型階的范圍數(shù)值范圍能表示數(shù)值的有效位點用字節(jié)數(shù)類型標(biāo)志符類型浮點型數(shù)據(jù)類型的特性

注意：C語言中沒有布爾（bool)類型；0表示false，非0表示true。39實型又稱浮點型，其值是實數(shù)的一個子集，分為單精度和雙精度兩

用戶自定義的非結(jié)構(gòu)類型用戶自定義的非結(jié)構(gòu)類型在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用戶自定義的非結(jié)構(gòu)類型用戶自定義的非結(jié)構(gòu)類型在C語言中稱為

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

注意：C語言中數(shù)組的下標(biāo)總是從0開始。412.聚合構(gòu)造（1）數(shù)組例如： 注意：C語言中數(shù)組的下標(biāo)總

可以定義多維數(shù)組說明的格式<類型說明符><數(shù)組名>[常量表達式]…[常量表達式]例如：floatfarr[3][4];charc[2][2][2];C語言的數(shù)組按行存放對數(shù)組名的處理相當(dāng)于指針數(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可以定義多維數(shù)組例如：C語言的數(shù)組按行存放數(shù)組a[3]

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

<類型標(biāo)識符><成員名>；例如：structstudent{ intnum; charname[2]; charsex; intage; floatscore; charaddr[30]; }43（2）結(jié)構(gòu)例如：structstudent{43

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

（3）聯(lián)合

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

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

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

typedefstruct{ int_fd; int_cleft; int_mode; char*_next; char*_buf; }FILE;文件名緩沖區(qū)中剩下的字符數(shù)文件操作模式下一個字符指針緩沖區(qū)指針46（4）文件C語言中文件的預(yù)定義格式如下：文件名緩沖區(qū)中剩下

3.指針

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

structtree{ charday; structtree*lchild; structtree*rchild; }; structtree*my_tree;473.指針C語言中的指針是第三種數(shù)據(jù)類型，是非結(jié)構(gòu)類型

4.空類型

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

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

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

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

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

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）?53C++語言中的抽象數(shù)據(jù)類型稱為類（class），類的

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

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

強類型語言；在編譯時進行的檢查在運行時進行的檢查語言沒有類型定義語言的類型檢查不能全部在編譯時完成，有些要在運行時才能完成語言的類型檢查全部在編譯時完成55第九節(jié)類型檢查對數(shù)據(jù)對象的類型和使用的操作是否匹配的一致

理由：編譯時,不能確定一個過程中的過程參數(shù)和子程序參數(shù)類型Pascal的子界類型不能靜態(tài)檢查變體記錄的標(biāo)識符可以在運行時改變Pascal沒有嚴(yán)格規(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是非強類型語言56procedurewho_knows(i,j:integ

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

實型轉(zhuǎn)換之前的類型值的集合包含轉(zhuǎn)換之后的類型值的集合；例如：實型整型1.截斷2.舍入法57第九節(jié)類型轉(zhuǎn)換將一個類型的值轉(zhuǎn)換成另一個類型的值，稱為類

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

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

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

第十節(jié)類型等價若T1和T2是兩個類型，T1的任何值都可以賦予T2類型的變量，反之亦然，T1類型的實參可以對應(yīng)類型T2的形參，反之亦然，則稱T1和T2是相容的，或等價的；61第十節(jié)類型等價若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é)類型等價有兩種類型的相容性概念：62struct不等價第十節(jié)類型等價有兩種類型的相容性概念：②結(jié)構(gòu)等價兩個變量的類型具有相同的結(jié)構(gòu)。63structRec1{charx;inty;charz[10];};structRec2{charx;inty;charz[10];};structRec3{inty;charx;charz[10];};Rec1和Rec2是結(jié)構(gòu)等價，Rec1和Rec3不是結(jié)構(gòu)等價。structRec1{charx;inty;}；structRec2{chara;intb;}；不等價第十節(jié)類型等價有兩種類型的相容性概念：63stru

第十節(jié)類型等價兩種相容性實現(xiàn)時的比較①名字等價的實現(xiàn)比較簡單②結(jié)構(gòu)等價的實現(xiàn)需要的模式匹配過程可能十分復(fù)雜64第十節(jié)類型等價兩種相容性實現(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第十一節(jié)實現(xiàn)模型在實現(xiàn)模型中，數(shù)據(jù)用描述符和數(shù)據(jù)對象來表

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

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

typet=recorda:real；

b:integer；

end；數(shù)據(jù)對象浮點值定點值描述符類型名構(gòu)造符選擇符選擇符類型類型引用引用trecordarealbinteger域1域268typet=recorda:real；數(shù)據(jù)對象浮點值定

有限映像為每一成分分配整數(shù)個可編址的存儲單元描述符包括:類型名、構(gòu)造符、定義域的基類型、下界、上界、成分類型、單元個數(shù)、首地址內(nèi)情向量；69有限映像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;描述符類型名構(gòu)造符基類型成分類型下界單元個數(shù)上界引用aarrayinteger1real1下標(biāo)類型10數(shù)據(jù)對象浮點值浮點值浮點值71例：typea=array[1..10]ofreal

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