第六章封裝PPT課件

1、第六章第六章 封裝封裝2抽象抽象n大型程序的構(gòu)造中，程序員不可避免要涉及到大型程序的構(gòu)造中，程序員不可避免要涉及到新數(shù)據(jù)類型的設(shè)計(jì)和實(shí)現(xiàn)。新數(shù)據(jù)類型的設(shè)計(jì)和實(shí)現(xiàn)。n如：大學(xué)中，表示一堂課的數(shù)據(jù)對(duì)象如：大學(xué)中，表示一堂課的數(shù)據(jù)對(duì)象section，包，包含的信息有：老師名、教室、最大注冊(cè)數(shù)等，還可含的信息有：老師名、教室、最大注冊(cè)數(shù)等，還可以包含一個(gè)注冊(cè)學(xué)生列表作為部件。以包含一個(gè)注冊(cè)學(xué)生列表作為部件。n操作包括：創(chuàng)建一個(gè)操作包括：創(chuàng)建一個(gè)section、注冊(cè)一個(gè)學(xué)生、消、注冊(cè)一個(gè)學(xué)生、消除一個(gè)除一個(gè)section等。等。n其實(shí)現(xiàn)主要涉及其表示以及對(duì)應(yīng)相關(guān)操作的子程序其實(shí)現(xiàn)主要涉及其表示以及對(duì)應(yīng)相

2、關(guān)操作的子程序設(shè)計(jì)。設(shè)計(jì)。n語(yǔ)言實(shí)現(xiàn)的目標(biāo)是使得數(shù)據(jù)的各種形式的不同語(yǔ)言實(shí)現(xiàn)的目標(biāo)是使得數(shù)據(jù)的各種形式的不同對(duì)程序員透明。因此，基本類型和用戶定義類對(duì)程序員透明。因此，基本類型和用戶定義類型對(duì)程序員的使用來說應(yīng)不存在差別。型對(duì)程序員的使用來說應(yīng)不存在差別。3抽象機(jī)制抽象機(jī)制n有四種機(jī)制可被程序員用來創(chuàng)建新類型和類型有四種機(jī)制可被程序員用來創(chuàng)建新類型和類型上的操作。上的操作。1、結(jié)構(gòu)化數(shù)據(jù)結(jié)構(gòu)化數(shù)據(jù)n幾乎所有語(yǔ)言都能夠用基本數(shù)據(jù)對(duì)象創(chuàng)建復(fù)雜的數(shù)據(jù)對(duì)象。幾乎所有語(yǔ)言都能夠用基本數(shù)據(jù)對(duì)象創(chuàng)建復(fù)雜的數(shù)據(jù)對(duì)象。2、子程序子程序n可用子程序來定義實(shí)現(xiàn)類型的操作，但如何正確地使用，可用子程序來定義實(shí)現(xiàn)類型的

3、操作，但如何正確地使用，卻是程序員的責(zé)任。卻是程序員的責(zé)任。3、類型聲明類型聲明n語(yǔ)言包含有定義新類型及其操作的能力。抽象數(shù)據(jù)類型即語(yǔ)言包含有定義新類型及其操作的能力。抽象數(shù)據(jù)類型即是這種機(jī)制，它提供了檢測(cè)錯(cuò)誤使用的能力。是這種機(jī)制，它提供了檢測(cè)錯(cuò)誤使用的能力。4、繼承、繼承n基于已有類型創(chuàng)建新類型的機(jī)制?；谝延蓄愋蛣?chuàng)建新類型的機(jī)制。 46.1 結(jié)構(gòu)數(shù)據(jù)類型結(jié)構(gòu)數(shù)據(jù)類型n數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)包含其他數(shù)據(jù)對(duì)象作為元包含其他數(shù)據(jù)對(duì)象作為元素或部件的數(shù)據(jù)對(duì)象。素或部件的數(shù)據(jù)對(duì)象。n基本概念基本概念n常見結(jié)構(gòu)化數(shù)據(jù)常見結(jié)構(gòu)化數(shù)據(jù)n向量和數(shù)組向量和數(shù)組n記錄記錄n列表列表n集合集合5結(jié)構(gòu)數(shù)據(jù)對(duì)象和數(shù)據(jù)類型

4、結(jié)構(gòu)數(shù)據(jù)對(duì)象和數(shù)據(jù)類型n結(jié)構(gòu)數(shù)據(jù)對(duì)象結(jié)構(gòu)數(shù)據(jù)對(duì)象一組其他數(shù)據(jù)對(duì)象構(gòu)成的聚集，這一組其他數(shù)據(jù)對(duì)象構(gòu)成的聚集，這些數(shù)據(jù)對(duì)象稱為元素或部件，可以是基本類型，也可些數(shù)據(jù)對(duì)象稱為元素或部件，可以是基本類型，也可以是結(jié)構(gòu)。以是結(jié)構(gòu)。n很多和數(shù)據(jù)結(jié)構(gòu)相關(guān)的問題和概念與基本類型數(shù)據(jù)是很多和數(shù)據(jù)結(jié)構(gòu)相關(guān)的問題和概念與基本類型數(shù)據(jù)是相同的，但數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜。相同的，但數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜。n數(shù)據(jù)結(jié)構(gòu)類型也涉及數(shù)據(jù)結(jié)構(gòu)類型也涉及類型規(guī)約類型規(guī)約和和類型實(shí)現(xiàn)類型實(shí)現(xiàn)，只是更為，只是更為復(fù)雜。復(fù)雜。n兩個(gè)方面是特別重要的：兩個(gè)方面是特別重要的：n結(jié)構(gòu)信息的規(guī)約和實(shí)現(xiàn)變成了中心問題，用于指出部件對(duì)象結(jié)構(gòu)信息的規(guī)約和實(shí)現(xiàn)變成

5、了中心問題，用于指出部件對(duì)象及其間關(guān)系，以便于部件的直接及其間關(guān)系，以便于部件的直接選取選取（或訪問）。（或訪問）。n結(jié)構(gòu)上的很多操作帶來的存儲(chǔ)管理問題。結(jié)構(gòu)上的很多操作帶來的存儲(chǔ)管理問題。6數(shù)據(jù)結(jié)構(gòu)類型的規(guī)約數(shù)據(jù)結(jié)構(gòu)類型的規(guī)約n規(guī)約的主要屬性包括：規(guī)約的主要屬性包括：1、部件數(shù)量、部件數(shù)量n結(jié)構(gòu)的部件數(shù)量可能是固定的，在其生命期中不結(jié)構(gòu)的部件數(shù)量可能是固定的，在其生命期中不變，如：數(shù)組、記錄等。變，如：數(shù)組、記錄等。n也可能是變長(zhǎng)的，數(shù)量可以動(dòng)態(tài)變化，如：棧、也可能是變長(zhǎng)的，數(shù)量可以動(dòng)態(tài)變化，如：棧、列表、集合、文件、表格等。列表、集合、文件、表格等。n變長(zhǎng)結(jié)構(gòu)通常需定義插入和刪去部件的操作

6、。而變長(zhǎng)結(jié)構(gòu)通常需定義插入和刪去部件的操作。而且可變長(zhǎng)數(shù)據(jù)對(duì)象經(jīng)常使用指針類型。且可變長(zhǎng)數(shù)據(jù)對(duì)象經(jīng)常使用指針類型。7數(shù)據(jù)結(jié)構(gòu)類型的規(guī)約數(shù)據(jù)結(jié)構(gòu)類型的規(guī)約2、每個(gè)部件的類型、每個(gè)部件的類型n同構(gòu)的同構(gòu)的所有部件為相同類型，如：數(shù)組、字所有部件為相同類型，如：數(shù)組、字符串、集合、文件等。符串、集合、文件等。n異構(gòu)的異構(gòu)的部件有不同類型，如：記錄，列表等。部件有不同類型，如：記錄，列表等。 3、用于選取部件的名字、用于選取部件的名字n結(jié)構(gòu)類型需要有標(biāo)識(shí)結(jié)構(gòu)中個(gè)體部件的選擇機(jī)制。結(jié)構(gòu)類型需要有標(biāo)識(shí)結(jié)構(gòu)中個(gè)體部件的選擇機(jī)制。n對(duì)數(shù)組，個(gè)體部件的名字可以是整數(shù)下標(biāo)或下標(biāo)對(duì)數(shù)組，個(gè)體部件的名字可以是整數(shù)下標(biāo)

7、或下標(biāo)序列。序列。n對(duì)列表，名字可以是用戶定義的標(biāo)識(shí)符。對(duì)列表，名字可以是用戶定義的標(biāo)識(shí)符。n有的結(jié)構(gòu)，只允許訪問特定部件，如棧頂元素。有的結(jié)構(gòu)，只允許訪問特定部件，如棧頂元素。8數(shù)據(jù)結(jié)構(gòu)類型的規(guī)約數(shù)據(jù)結(jié)構(gòu)類型的規(guī)約4、部件的最大數(shù)量、部件的最大數(shù)量n對(duì)有的變長(zhǎng)結(jié)構(gòu)，結(jié)構(gòu)的最大尺寸可以指定。對(duì)有的變長(zhǎng)結(jié)構(gòu)，結(jié)構(gòu)的最大尺寸可以指定。5、部件的組織、部件的組織n最常見的組織是簡(jiǎn)單的線性序列，如：向量、記最常見的組織是簡(jiǎn)單的線性序列，如：向量、記錄、字符串、棧、列表、文件等。錄、字符串、棧、列表、文件等。n然而，數(shù)組、記錄和列表類型也可以擴(kuò)展為多維然而，數(shù)組、記錄和列表類型也可以擴(kuò)展為多維形式。形式

8、。n多維形式可以看成單獨(dú)的類型，也可以簡(jiǎn)單地看成同多維形式可以看成單獨(dú)的類型，也可以簡(jiǎn)單地看成同類結(jié)構(gòu)部件的順序類型（其元素類型為結(jié)構(gòu)）。類結(jié)構(gòu)部件的順序類型（其元素類型為結(jié)構(gòu)）。n如如A(i,j) 和和Aij的差異。的差異。9數(shù)據(jù)結(jié)構(gòu)上的操作數(shù)據(jù)結(jié)構(gòu)上的操作n結(jié)構(gòu)上操作的定義域和值域規(guī)約的方法和基本結(jié)構(gòu)上操作的定義域和值域規(guī)約的方法和基本類型操作是類似的，但是，有些新的操作類型類型操作是類似的，但是，有些新的操作類型特別重要。特別重要。1、部件選擇操作、部件選擇操作n有兩種類型：有兩種類型： 隨機(jī)選擇隨機(jī)選擇可任意選擇結(jié)構(gòu)中某一部件可任意選擇結(jié)構(gòu)中某一部件順序選擇順序選擇以預(yù)定好的順序選擇部

9、件。以預(yù)定好的順序選擇部件。n數(shù)據(jù)對(duì)象中部件或數(shù)據(jù)值的選擇和相關(guān)的引用操作數(shù)據(jù)對(duì)象中部件或數(shù)據(jù)值的選擇和相關(guān)的引用操作是有區(qū)別的。如：是有區(qū)別的。如：V4選擇選擇V中第中第4個(gè)元素，分兩個(gè)元素，分兩步：步：n先引用（確定先引用（確定V的位置（的位置（l-值），返回一個(gè)指針），值），返回一個(gè)指針），n后選擇（得到部件的位置）。后選擇（得到部件的位置）。10數(shù)據(jù)結(jié)構(gòu)上的操作數(shù)據(jù)結(jié)構(gòu)上的操作2、整體數(shù)據(jù)結(jié)構(gòu)操作、整體數(shù)據(jù)結(jié)構(gòu)操作n以完整的數(shù)據(jù)結(jié)構(gòu)為參數(shù)，產(chǎn)生新的數(shù)據(jù)以完整的數(shù)據(jù)結(jié)構(gòu)為參數(shù)，產(chǎn)生新的數(shù)據(jù)結(jié)構(gòu)為結(jié)果。結(jié)構(gòu)為結(jié)果。n大多數(shù)語(yǔ)言中，這樣的整體性操作是有限大多數(shù)語(yǔ)言中，這樣的整體性操作是有限的

10、。如：的。如：n兩個(gè)數(shù)組相加、記錄間的賦值、集合的并等。兩個(gè)數(shù)組相加、記錄間的賦值、集合的并等。n少數(shù)語(yǔ)言提供了大量整體操作，然而，程少數(shù)語(yǔ)言提供了大量整體操作，然而，程序員很少去選擇個(gè)體部件。如：序員很少去選擇個(gè)體部件。如：APL和和SNOBOL4語(yǔ)言。語(yǔ)言。11數(shù)據(jù)結(jié)構(gòu)上的操作數(shù)據(jù)結(jié)構(gòu)上的操作3、部件的插入、部件的插入/刪除刪除n這種操作將改變部件數(shù)量，從而影響存儲(chǔ)這種操作將改變部件數(shù)量，從而影響存儲(chǔ)表示和存儲(chǔ)管理。表示和存儲(chǔ)管理。4、數(shù)據(jù)結(jié)構(gòu)的創(chuàng)建、數(shù)據(jù)結(jié)構(gòu)的創(chuàng)建/消除消除n這類操作將對(duì)存儲(chǔ)管理有很大影響。這類操作將對(duì)存儲(chǔ)管理有很大影響。返回12數(shù)據(jù)結(jié)構(gòu)類型的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)類型的實(shí)現(xiàn)n實(shí)現(xiàn)

11、中需要考慮的兩個(gè)問題：實(shí)現(xiàn)中需要考慮的兩個(gè)問題：n結(jié)構(gòu)中部件的高效選擇，結(jié)構(gòu)中部件的高效選擇，n高效的存儲(chǔ)管理。高效的存儲(chǔ)管理。n存儲(chǔ)表示存儲(chǔ)表示n結(jié)構(gòu)的存儲(chǔ)管理包括：結(jié)構(gòu)的存儲(chǔ)管理包括：結(jié)構(gòu)中部件的存儲(chǔ)；結(jié)構(gòu)中部件的存儲(chǔ)；可選的描述子（用于存儲(chǔ)結(jié)構(gòu)的屬性）。可選的描述子（用于存儲(chǔ)結(jié)構(gòu)的屬性）。13數(shù)據(jù)結(jié)構(gòu)類型的實(shí)現(xiàn)：存儲(chǔ)表示數(shù)據(jù)結(jié)構(gòu)類型的實(shí)現(xiàn)：存儲(chǔ)表示n有兩種基本表示：有兩種基本表示：1、順序表示、順序表示n結(jié)構(gòu)存放在單個(gè)連續(xù)塊中（包括描述符和部件）。結(jié)構(gòu)存放在單個(gè)連續(xù)塊中（包括描述符和部件）。n常用于固定長(zhǎng)的結(jié)構(gòu)，有時(shí)也用于同構(gòu)變長(zhǎng)結(jié)構(gòu)。常用于固定長(zhǎng)的結(jié)構(gòu)，有時(shí)也用于同構(gòu)變長(zhǎng)結(jié)構(gòu)。2、鏈接

12、表示、鏈接表示n結(jié)構(gòu)被存放在幾個(gè)非連續(xù)的存儲(chǔ)塊中，這些塊用結(jié)構(gòu)被存放在幾個(gè)非連續(xù)的存儲(chǔ)塊中，這些塊用指針鏈接在一起，該指針稱為鏈（指針鏈接在一起，該指針稱為鏈（link）。）。n通常用于變長(zhǎng)結(jié)構(gòu)。通常用于變長(zhǎng)結(jié)構(gòu)。 14兩種基本存儲(chǔ)表示兩種基本存儲(chǔ)表示15數(shù)據(jù)結(jié)構(gòu)操作的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)操作的實(shí)現(xiàn)n大多數(shù)結(jié)構(gòu)的實(shí)現(xiàn)中，部件選擇是最重大多數(shù)結(jié)構(gòu)的實(shí)現(xiàn)中，部件選擇是最重要的，需要較高的隨機(jī)和順序訪問效率。要的，需要較高的隨機(jī)和順序訪問效率。對(duì)對(duì)順序順序和和鏈接鏈接存儲(chǔ)表示，這兩種類型的存儲(chǔ)表示，這兩種類型的選擇的實(shí)現(xiàn)有所不同。選擇的實(shí)現(xiàn)有所不同。16數(shù)據(jù)結(jié)構(gòu)操作的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)操作的實(shí)現(xiàn)n順序表示順序表示

13、n部件的隨機(jī)訪問通常涉及部件的隨機(jī)訪問通常涉及“基地址（完整塊的開始位基地址（完整塊的開始位置）置）+位移量（部件在塊中的位移量（部件在塊中的相對(duì)位置）相對(duì)位置）”的計(jì)算。的計(jì)算。n對(duì)一個(gè)順序存儲(chǔ)的同構(gòu)結(jié)構(gòu)，對(duì)一個(gè)順序存儲(chǔ)的同構(gòu)結(jié)構(gòu)，部件序列的選擇按如下步驟：部件序列的選擇按如下步驟：1、要選擇序列的第一個(gè)部件，使、要選擇序列的第一個(gè)部件，使用用“基地址基地址+位移量位移量”。2、要選擇下一個(gè)部件，在當(dāng)前部、要選擇下一個(gè)部件，在當(dāng)前部件位置上加上當(dāng)前部件的大小，件位置上加上當(dāng)前部件的大小，對(duì)同構(gòu)結(jié)構(gòu)，每個(gè)部件的大小對(duì)同構(gòu)結(jié)構(gòu)，每個(gè)部件的大小是相同的。是相同的。17數(shù)據(jù)結(jié)構(gòu)操作的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)操作

14、的實(shí)現(xiàn)n鏈接表示鏈接表示n隨機(jī)選擇需要沿指針鏈從頭查找，需知道在隨機(jī)選擇需要沿指針鏈從頭查找，需知道在部件塊中鏈指針的位置。部件塊中鏈指針的位置。n部件序列的選取相對(duì)容易，沿指針向前即可。部件序列的選取相對(duì)容易，沿指針向前即可。返回18數(shù)據(jù)對(duì)象的訪問數(shù)據(jù)對(duì)象的訪問n數(shù)據(jù)對(duì)象一旦創(chuàng)建，需同時(shí)創(chuàng)建它的數(shù)據(jù)對(duì)象一旦創(chuàng)建，需同時(shí)創(chuàng)建它的訪問路徑訪問路徑，使得，使得對(duì)象可被程序中的操作訪問。對(duì)象可被程序中的操作訪問。n訪問路徑的創(chuàng)建方式：訪問路徑的創(chuàng)建方式：n將標(biāo)識(shí)符（名字）和對(duì)象相關(guān)聯(lián)將標(biāo)識(shí)符（名字）和對(duì)象相關(guān)聯(lián)n存放指向結(jié)構(gòu)的指針于其他可訪問的結(jié)構(gòu)中，使成為其部存放指向結(jié)構(gòu)的指針于其他可訪問的結(jié)構(gòu)中

15、，使成為其部件元素。件元素。n在生命期中，還可能產(chǎn)生其他的訪問路徑。在生命期中，還可能產(chǎn)生其他的訪問路徑。n如：作為參數(shù)傳遞給子程序如：作為參數(shù)傳遞給子程序 創(chuàng)建一個(gè)新指針創(chuàng)建一個(gè)新指針 n訪問路徑也可以被刪除訪問路徑也可以被刪除n如：賦新值給一個(gè)新指針變量如：賦新值給一個(gè)新指針變量 從子程序返回。從子程序返回。19數(shù)據(jù)對(duì)象的訪問數(shù)據(jù)對(duì)象的訪問n與數(shù)據(jù)對(duì)象的生命周期及訪問路徑相關(guān)的兩個(gè)與數(shù)據(jù)對(duì)象的生命周期及訪問路徑相關(guān)的兩個(gè)中心問題：中心問題：1、垃圾：、垃圾：n當(dāng)所有訪問路徑被消除，但數(shù)據(jù)對(duì)象仍然存在，它將不可當(dāng)所有訪問路徑被消除，但數(shù)據(jù)對(duì)象仍然存在，它將不可再被訪問。因此，其和存儲(chǔ)位置的綁

16、定必須解除。再被訪問。因此，其和存儲(chǔ)位置的綁定必須解除。2、Dangling reference：懸空引用。：懸空引用。n某個(gè)訪問路徑，它在關(guān)聯(lián)的數(shù)據(jù)對(duì)象消除后仍然存在。某個(gè)訪問路徑，它在關(guān)聯(lián)的數(shù)據(jù)對(duì)象消除后仍然存在。n這對(duì)存儲(chǔ)管理是一個(gè)嚴(yán)重的問題，因?yàn)樗赡芷茐倪\(yùn)行時(shí)這對(duì)存儲(chǔ)管理是一個(gè)嚴(yán)重的問題，因?yàn)樗赡芷茐倪\(yùn)行時(shí)結(jié)構(gòu)的完整性，如：修改不相關(guān)的數(shù)據(jù)和修改存儲(chǔ)管理數(shù)結(jié)構(gòu)的完整性，如：修改不相關(guān)的數(shù)據(jù)和修改存儲(chǔ)管理數(shù)據(jù)等。據(jù)等。返回20數(shù)據(jù)結(jié)構(gòu)：向量和數(shù)組數(shù)據(jù)結(jié)構(gòu)：向量和數(shù)組n向量由固定數(shù)量的同類型部件組成，按向量由固定數(shù)量的同類型部件組成，按簡(jiǎn)單的線性序組織，向量部件由下標(biāo)選簡(jiǎn)單的線性序組織

17、，向量部件由下標(biāo)選擇。擇。n向量也稱一維數(shù)組或線性數(shù)組。向量也稱一維數(shù)組或線性數(shù)組。n二維數(shù)組或矩陣，其部件被組織為行、二維數(shù)組或矩陣，其部件被組織為行、列的矩形格。列的矩形格。21向量：屬性向量：屬性n向量的屬性包括：向量的屬性包括：1、部件的數(shù)量，通常由一組下標(biāo)范圍隱式地、部件的數(shù)量，通常由一組下標(biāo)范圍隱式地指定。指定。2、部件的類型，所有部件具有相同的類型。、部件的類型，所有部件具有相同的類型。3、用于選擇每個(gè)部件的下標(biāo)，通常是一個(gè)整、用于選擇每個(gè)部件的下標(biāo)，通常是一個(gè)整數(shù)域，第一個(gè)整數(shù)指定第一個(gè)部件，第二個(gè)數(shù)域，第一個(gè)整數(shù)指定第一個(gè)部件，第二個(gè)數(shù)指定第二個(gè)部件，依此類推。下標(biāo)可以是數(shù)指

18、定第二個(gè)部件，依此類推。下標(biāo)可以是給出一個(gè)值的范圍，也可以是只給出上界，給出一個(gè)值的范圍，也可以是只給出上界，而下界是隱含的。而下界是隱含的。 22向量：聲明向量：聲明n典型的向量聲明：典型的向量聲明：V : array 1.10 of real;-PASCAL語(yǔ)言語(yǔ)言float a10;-C語(yǔ)言語(yǔ)言n如果允許指定下標(biāo)域，則可以使用枚舉為下如果允許指定下標(biāo)域，則可以使用枚舉為下標(biāo)，如：標(biāo)，如：type class = (Fresh, Soph, Junior, Senior)var ClassAverage: array class of real;23向量：操作向量：操作n向量上的操作：向量

19、上的操作：n選擇元素的操作通常稱為下標(biāo)操作，如：選擇元素的操作通常稱為下標(biāo)操作，如：V2， ClassAverageSophn由于下標(biāo)大都是可計(jì)算值，固可用表達(dá)式作下標(biāo)：由于下標(biāo)大都是可計(jì)算值，固可用表達(dá)式作下標(biāo)：VI + 2n其它操作包括：向量的創(chuàng)建和消除，向量元素的賦其它操作包括：向量的創(chuàng)建和消除，向量元素的賦值，相同大小的兩個(gè)向量間的算術(shù)操作等。通常插值，相同大小的兩個(gè)向量間的算術(shù)操作等。通常插入和刪除向量元素是不允許的。入和刪除向量元素是不允許的。nAPL是專門基于數(shù)組的語(yǔ)言，允許大量向量操作。是專門基于數(shù)組的語(yǔ)言，允許大量向量操作。24向量：實(shí)現(xiàn)向量：實(shí)現(xiàn)n由于向量的同構(gòu)性和由于向量

20、的同構(gòu)性和固定大小，其存儲(chǔ)和固定大小，其存儲(chǔ)和訪問相同簡(jiǎn)單。同構(gòu)訪問相同簡(jiǎn)單。同構(gòu)性意味著每個(gè)元素的性意味著每個(gè)元素的大小和結(jié)構(gòu)相同，固大小和結(jié)構(gòu)相同，固定大小意味著元素?cái)?shù)定大小意味著元素?cái)?shù)量及每個(gè)元素的位置量及每個(gè)元素的位置保持不變。保持不變。n順序存儲(chǔ)表示是很好順序存儲(chǔ)表示是很好的選擇，描述子用于的選擇，描述子用于存放一些運(yùn)行時(shí)必要存放一些運(yùn)行時(shí)必要的屬性信息。的屬性信息。用于越界檢查25向量：實(shí)現(xiàn)（訪問）向量：實(shí)現(xiàn)（訪問）n元素的隨機(jī)訪問，即向量元素的左值訪問公式：元素的隨機(jī)訪問，即向量元素的左值訪問公式：lvalue(AI) = + (I LB) En這里這里 為基地址，為基地址，E為

21、元素所占的存儲(chǔ)大小。亦即：為元素所占的存儲(chǔ)大小。亦即：lvalue(AI) = ( LB E) + (I E)lvalue(AI) = K + (I E) -K表示常數(shù)表示常數(shù)n有的語(yǔ)言（如有的語(yǔ)言（如FORTRAN ）中）中K為常量，故可在編譯時(shí)計(jì)算為常量，故可在編譯時(shí)計(jì)算出來。出來。n即使在有的語(yǔ)言（如即使在有的語(yǔ)言（如PASCAL）中，）中，K可能發(fā)生變化，也只需可能發(fā)生變化，也只需要在存儲(chǔ)分配時(shí)計(jì)算一次。要在存儲(chǔ)分配時(shí)計(jì)算一次。n由于由于E和和I均是在編譯時(shí)可知，因此，訪問公式的計(jì)算完全可均是在編譯時(shí)可知，因此，訪問公式的計(jì)算完全可在編譯時(shí)完成。在編譯時(shí)完成。n如如C語(yǔ)言中，字符數(shù)組的

22、語(yǔ)言中，字符數(shù)組的E為為1，LB總為總為0，訪問公式為：，訪問公式為：lvalue(AI) = + I。26向量：實(shí)現(xiàn)（訪問）向量：實(shí)現(xiàn)（訪問）n虛原點(diǎn)：虛原點(diǎn)：lvalue(A0) = ( LB E) + (0 E) = Kn即即K為向量中元素為向量中元素0的地址，如果的地址，如果0元素存在。如果向量的下元素存在。如果向量的下界大于界大于0，則這個(gè)地址稱為虛原點(diǎn)，則這個(gè)地址稱為虛原點(diǎn)VO。因此，構(gòu)建向量并產(chǎn)。因此，構(gòu)建向量并產(chǎn)生訪問公式的算法為：生訪問公式的算法為：1、向量存儲(chǔ)的創(chuàng)建：為、向量存儲(chǔ)的創(chuàng)建：為N個(gè)大小為個(gè)大小為E的向量元素分配的向量元素分配D(NE)，D為描述子的大小。為描述子

23、的大小。2、計(jì)算虛原點(diǎn)：、計(jì)算虛原點(diǎn)：VO LB E3、訪問具體元素：、訪問具體元素：lvalue(AI) = VO + I En上面公式假定上面公式假定I為為A的有效下標(biāo)，即，的有效下標(biāo)，即，LB = I = UB。通常。通常越界檢查是必須的，因此越界檢查是必須的，因此LB和和UB應(yīng)該存放在描述子中。應(yīng)該存放在描述子中。n如果虛原點(diǎn)也存放在描述子中，則數(shù)組和描述子可不必存放如果虛原點(diǎn)也存放在描述子中，則數(shù)組和描述子可不必存放在一起。這是為什么通常描述子作為參數(shù)傳遞給子程序，而在一起。這是為什么通常描述子作為參數(shù)傳遞給子程序，而數(shù)據(jù)的數(shù)組卻存放在別的地方。數(shù)據(jù)的數(shù)組卻存放在別的地方。27向量：

24、實(shí)現(xiàn)（訪問）向量：實(shí)現(xiàn)（訪問）這里描述子類型和元素類型均未在描述子中給出。通常，這些信息在編譯時(shí)已知。28向量：實(shí)現(xiàn)向量：實(shí)現(xiàn)n打包及未打包存儲(chǔ)表示：打包及未打包存儲(chǔ)表示：n通常每個(gè)數(shù)組元素占用完整的可編址存儲(chǔ)單通常每個(gè)數(shù)組元素占用完整的可編址存儲(chǔ)單元。但是，有的類型只占用一個(gè)字中的一小元。但是，有的類型只占用一個(gè)字中的一小部分，此時(shí)，需要將幾個(gè)向量元素打包存放部分，此時(shí)，需要將幾個(gè)向量元素打包存放在在一個(gè)編址單元中。打包存儲(chǔ)帶來的問題在在一個(gè)編址單元中。打包存儲(chǔ)帶來的問題是訪問公式更加復(fù)雜。是訪問公式更加復(fù)雜。29向量：實(shí)現(xiàn)向量：實(shí)現(xiàn)n全向量操作：全向量操作：n將向量作為整體的操作是基于順序

25、存儲(chǔ)表示而實(shí)現(xiàn)將向量作為整體的操作是基于順序存儲(chǔ)表示而實(shí)現(xiàn)的。的。n一個(gè)向量到另一個(gè)向量的賦值即是簡(jiǎn)單的內(nèi)容拷貝，一個(gè)向量到另一個(gè)向量的賦值即是簡(jiǎn)單的內(nèi)容拷貝，而描述子不需要拷貝。而描述子不需要拷貝。n向量上的算術(shù)操作實(shí)現(xiàn)為向量中元素循環(huán)順序處理。向量上的算術(shù)操作實(shí)現(xiàn)為向量中元素循環(huán)順序處理。n全向量操作實(shí)現(xiàn)的最大問題是結(jié)果的存儲(chǔ)。需要臨全向量操作實(shí)現(xiàn)的最大問題是結(jié)果的存儲(chǔ)。需要臨時(shí)分配存儲(chǔ)來存放結(jié)果的右值，除非它被立即賦給時(shí)分配存儲(chǔ)來存放結(jié)果的右值，除非它被立即賦給一個(gè)左值位置。一個(gè)左值位置。n當(dāng)涉及的全向量操作過多時(shí)，臨時(shí)存儲(chǔ)的管理可能當(dāng)涉及的全向量操作過多時(shí)，臨時(shí)存儲(chǔ)的管理可能會(huì)增加復(fù)雜

26、性和成本。會(huì)增加復(fù)雜性和成本。30多維數(shù)組多維數(shù)組n多維數(shù)組實(shí)際上是一維數(shù)組的推廣。多維數(shù)組實(shí)際上是一維數(shù)組的推廣。n規(guī)約和語(yǔ)法：和向量在屬性上的差別只規(guī)約和語(yǔ)法：和向量在屬性上的差別只是需要指定每個(gè)維的下標(biāo)范圍。如：是需要指定每個(gè)維的下標(biāo)范圍。如：B : array1.10, -5.5 of real;n數(shù)組元素的選擇需給定每一維，如：數(shù)組元素的選擇需給定每一維，如：B2, 4。31多維數(shù)組：實(shí)現(xiàn)多維數(shù)組：實(shí)現(xiàn)n矩陣可以方便地實(shí)現(xiàn)為向量的向量，三維數(shù)組矩陣可以方便地實(shí)現(xiàn)為向量的向量，三維數(shù)組的元素是向量的向量，依此類推。所有子向量的元素是向量的向量，依此類推。所有子向量必須有相同數(shù)量的元素，

27、而且是相同類型。必須有相同數(shù)量的元素，而且是相同類型。n矩陣是實(shí)現(xiàn)為矩陣是實(shí)現(xiàn)為“行之列行之列”還是還是“列之行列之行”是語(yǔ)是語(yǔ)境敏感的，特別是在不同語(yǔ)言的程序間作為參境敏感的，特別是在不同語(yǔ)言的程序間作為參數(shù)傳遞時(shí)。最常見的實(shí)現(xiàn)是數(shù)傳遞時(shí)。最常見的實(shí)現(xiàn)是“行之列行之列”，此即，此即所謂的所謂的“行為主序行為主序”。n多維數(shù)組的存儲(chǔ)表示類似于向量。如對(duì)矩陣，多維數(shù)組的存儲(chǔ)表示類似于向量。如對(duì)矩陣，先存第一行的數(shù)據(jù)對(duì)象，再存第二行的數(shù)據(jù)，先存第一行的數(shù)據(jù)對(duì)象，再存第二行的數(shù)據(jù)，依此類推。依此類推。32多維數(shù)組：實(shí)現(xiàn)多維數(shù)組：實(shí)現(xiàn)n二二維維數(shù)數(shù)組組的的存存儲(chǔ)儲(chǔ)表表示示33多維數(shù)組：實(shí)現(xiàn)（訪問）多維

28、數(shù)組：實(shí)現(xiàn)（訪問）n下標(biāo)操作及訪問公式：下標(biāo)操作及訪問公式：n對(duì)對(duì)MN的的“行為主序行為主序”二維數(shù)組，有：二維數(shù)組，有：lvalue(AI, J) = + (ILB1) S (J LB2) En這里這里 是基地址，是基地址，S是一個(gè)行的長(zhǎng)度，即是一個(gè)行的長(zhǎng)度，即nS(UB2LB2+1)En考慮常量項(xiàng)：考慮常量項(xiàng)：VO LB1SLB2En則：則： lvalue(AI, J) VOISJEn更多維數(shù)組：更多維數(shù)組：AL1:U1, , Ln:Un1、乘數(shù)的計(jì)算：、乘數(shù)的計(jì)算：mn=e，mi=(Ui+1Li+1+1)mi+12、虛原點(diǎn)的計(jì)算：、虛原點(diǎn)的計(jì)算：VO (Limi)3、數(shù)組元素的訪問：、數(shù)

29、組元素的訪問：lvalue(As1, , sn)=VO+ (simi)返回34記錄記錄n由固定數(shù)量的不同類型部件組成。由固定數(shù)量的不同類型部件組成。n規(guī)約和語(yǔ)法：記錄和向量都是定長(zhǎng)的線規(guī)約和語(yǔ)法：記錄和向量都是定長(zhǎng)的線性結(jié)構(gòu)，其不同在于：性結(jié)構(gòu)，其不同在于：1、記錄的元素可能是異構(gòu)的，是不同類型、記錄的元素可能是異構(gòu)的，是不同類型的混合。的混合。2、記錄的元素用符號(hào)命名，而不是用下標(biāo)。、記錄的元素用符號(hào)命名，而不是用下標(biāo)。35記錄：聲明記錄：聲明n例如，例如，C語(yǔ)言中的記錄聲明為：語(yǔ)言中的記錄聲明為：struct EmployeeType int ID;int Age;float Salary

30、;char Dept; Employee;n從聲明中可看出：從聲明中可看出：1、部件的數(shù)量、部件的數(shù)量2、每個(gè)部件的數(shù)據(jù)類型、每個(gè)部件的數(shù)據(jù)類型3、用于命名每個(gè)部件的選擇子、用于命名每個(gè)部件的選擇子n部件也稱域。部件也稱域。36記錄：實(shí)現(xiàn)記錄：實(shí)現(xiàn)n記錄的存儲(chǔ)表示包含一個(gè)順序的存儲(chǔ)塊，其記錄的存儲(chǔ)表示包含一個(gè)順序的存儲(chǔ)塊，其中元素順序存放。每個(gè)元素可能需要描述子中元素順序存放。每個(gè)元素可能需要描述子去指定它們的數(shù)據(jù)類型或其它屬性，但通常去指定它們的數(shù)據(jù)類型或其它屬性，但通常對(duì)記錄本身沒有運(yùn)行時(shí)描述子。對(duì)記錄本身沒有運(yùn)行時(shí)描述子。37記錄：元素的訪問（選擇）記錄：元素的訪問（選擇）n部件選擇是記

31、錄的基本操作，但不是使用計(jì)算部件選擇是記錄的基本操作，但不是使用計(jì)算值，而是使用文字部件名。很少有針對(duì)整個(gè)記值，而是使用文字部件名。很少有針對(duì)整個(gè)記錄的操作。例如，記錄元素的選擇：錄的操作。例如，記錄元素的選擇：Employee.IDEmployee.Salaryn元素的選擇相對(duì)容易實(shí)現(xiàn)，因?yàn)樵诜g時(shí)域名元素的選擇相對(duì)容易實(shí)現(xiàn)，因?yàn)樵诜g時(shí)域名就已經(jīng)知道，記錄的聲明也使得每個(gè)元素的大就已經(jīng)知道，記錄的聲明也使得每個(gè)元素的大小和位置在翻譯時(shí)可確定。因此，在翻譯時(shí)可小和位置在翻譯時(shí)可確定。因此，在翻譯時(shí)可以計(jì)算出任意元素的位移量。以計(jì)算出任意元素的位移量。38記錄：元素的訪問（選擇）記錄：元素的訪

32、問（選擇）n基本的訪問公式：基本的訪問公式：Lvalue(R.I) = + (size of R.j) j=1.I-1 = + KI -KI為元素為元素I的位移的位移量量39記錄：存儲(chǔ)記錄：存儲(chǔ)n有些數(shù)據(jù)類型的存儲(chǔ)必須從特定的地址邊界開始。例有些數(shù)據(jù)類型的存儲(chǔ)必須從特定的地址邊界開始。例如，整數(shù)可能必須從字的邊界開始存放，對(duì)可字節(jié)編如，整數(shù)可能必須從字的邊界開始存放，對(duì)可字節(jié)編址的機(jī)器而言，該地址必須能夠被址的機(jī)器而言，該地址必須能夠被4除。在除。在C語(yǔ)言中，語(yǔ)言中，struct EmployeeDivision char Division;int IdNumber; Employeen如果如

33、果IdNumber必須從字邊界開始，則在必須從字邊界開始，則在Division和和IdNumber間有三個(gè)字節(jié)未用，稱為填料間有三個(gè)字節(jié)未用，稱為填料（padding）。存儲(chǔ)表示就好象如下聲明一樣：）。存儲(chǔ)表示就好象如下聲明一樣：struct EmployeeDivision char Division;char UnusedPadding3;int IdNumber; Employee40含結(jié)構(gòu)元素的記錄和數(shù)組含結(jié)構(gòu)元素的記錄和數(shù)組n如果語(yǔ)言同時(shí)提供數(shù)組和記錄類型，則這兩種類型的如果語(yǔ)言同時(shí)提供數(shù)組和記錄類型，則這兩種類型的元素可能和其它基本類型的元素混雜在一起。如：一元素可能和其它基本類型

34、的元素混雜在一起。如：一個(gè)向量的每個(gè)元素都是一個(gè)記錄，在個(gè)向量的每個(gè)元素都是一個(gè)記錄，在C中有如下聲明：中有如下聲明：struct EmployeeType int ID;int Age;float Salary;char Dept; Employee500;n這樣一個(gè)復(fù)合數(shù)據(jù)結(jié)構(gòu)的元素的選擇需要一系列選擇這樣一個(gè)復(fù)合數(shù)據(jù)結(jié)構(gòu)的元素的選擇需要一系列選擇操作，如：操作，如：Employee3.Salary。41含結(jié)構(gòu)元素的記錄和數(shù)組含結(jié)構(gòu)元素的記錄和數(shù)組n記錄的部件也可以是記錄的部件也可以是數(shù)組或其它記錄，導(dǎo)數(shù)組或其它記錄，導(dǎo)致記錄具有層次結(jié)構(gòu)。致記錄具有層次結(jié)構(gòu)。COBOL和和PL/1中，中，

35、使用層次編號(hào)來語(yǔ)法使用層次編號(hào)來語(yǔ)法地指定這種層次結(jié)構(gòu)。地指定這種層次結(jié)構(gòu)。如，一個(gè)如，一個(gè)PL/1聲明：聲明：1 Employee,2 Name,3 Last CHARACTER(10),3 First CHARACTER(15),3 Middle CHARACTER(1),2 Age FIXED(2),2 Address,3 Street,4 Number FIXED(5),4 St-Name CHARACTER(20),3 City CHARACTER(15),3 State CHARACTER(10),3 Zip FIXED(5);42含結(jié)構(gòu)元素的記錄和數(shù)組：實(shí)現(xiàn)含結(jié)構(gòu)元素的記錄和數(shù)組

36、：實(shí)現(xiàn)n存儲(chǔ)表示類似于簡(jiǎn)存儲(chǔ)表示類似于簡(jiǎn)單的數(shù)組和記錄類單的數(shù)組和記錄類型。記錄構(gòu)成的向型。記錄構(gòu)成的向量的存儲(chǔ)表示相對(duì)量的存儲(chǔ)表示相對(duì)簡(jiǎn)單，每個(gè)行被記簡(jiǎn)單，每個(gè)行被記錄的存儲(chǔ)表示替代。錄的存儲(chǔ)表示替代。類似地，記錄的記類似地，記錄的記錄保持相同的實(shí)現(xiàn)錄保持相同的實(shí)現(xiàn)結(jié)構(gòu)，但每個(gè)元素結(jié)構(gòu)，但每個(gè)元素是一個(gè)子塊，子塊是一個(gè)子塊，子塊本身是一個(gè)完整記本身是一個(gè)完整記錄的表示。錄的表示。43可變記錄（可變記錄（variant records）n可使用一個(gè)記錄來表示可使用一個(gè)記錄來表示相似的、但不同的數(shù)據(jù)相似的、但不同的數(shù)據(jù)對(duì)象。這樣的記錄類型對(duì)象。這樣的記錄類型有幾個(gè)變體，它們有共有幾個(gè)變體，它們有

37、共同的部分，但各個(gè)變體同的部分，但各個(gè)變體又有自己獨(dú)有的部件。又有自己獨(dú)有的部件。如，雇員可以分為按月如，雇員可以分為按月和按小時(shí)領(lǐng)工資兩種情和按小時(shí)領(lǐng)工資兩種情況，從而呈現(xiàn)兩個(gè)變體。況，從而呈現(xiàn)兩個(gè)變體。n例如，一個(gè)例如，一個(gè)PASCAL聲明如下：聲明如下：type PayType = (Salaried, Hourly)var Employee: record ID: integer; Dept: array 1.3 of char; Age: integer; case PayClass: PayType of Salaried: (MonthlyRate: real; StartDat

38、e: integer); Hourly: (HourRate: real; Reg: integer; Overtime: integer) endPayClass稱為標(biāo)記稱為標(biāo)記或判別子，用于指或判別子，用于指定被采用的變體。定被采用的變體。44可變記錄：元素的訪問（選擇）可變記錄：元素的訪問（選擇）n變體記錄的選擇操作和一般記錄相同，但由于變體問變體記錄的選擇操作和一般記錄相同，但由于變體問題，有的部件的存在性會(huì)在運(yùn)行中發(fā)生變化，因此，題，有的部件的存在性會(huì)在運(yùn)行中發(fā)生變化，因此，有的選擇操作可能在運(yùn)行中某時(shí)刻找不到希望的部件，有的選擇操作可能在運(yùn)行中某時(shí)刻找不到希望的部件，如：如：Emp

39、loyee.Reg。這類似于下標(biāo)越界問題，解決。這類似于下標(biāo)越界問題，解決方案為：方案為：1、動(dòng)態(tài)檢查：在訪問部件前檢查標(biāo)記以保證該部件存在。如果、動(dòng)態(tài)檢查：在訪問部件前檢查標(biāo)記以保證該部件存在。如果標(biāo)記值不對(duì)，則出現(xiàn)運(yùn)行時(shí)錯(cuò)。標(biāo)記值不對(duì)，則出現(xiàn)運(yùn)行時(shí)錯(cuò)。2、不檢查：語(yǔ)言設(shè)計(jì)可能允許變體記錄的定義沒有顯式的可在、不檢查：語(yǔ)言設(shè)計(jì)可能允許變體記錄的定義沒有顯式的可在運(yùn)行時(shí)檢查的標(biāo)記，因此，變體記錄的部件選擇總被假定為運(yùn)行時(shí)檢查的標(biāo)記，因此，變體記錄的部件選擇總被假定為合法的。由于變體記錄的實(shí)現(xiàn)方式，這樣的選擇總是可能的，合法的。由于變體記錄的實(shí)現(xiàn)方式，這樣的選擇總是可能的，但是，如果部件不存在，

40、當(dāng)前變體的值可能會(huì)被不經(jīng)意地取但是，如果部件不存在，當(dāng)前變體的值可能會(huì)被不經(jīng)意地取出或覆寫。出或覆寫。C語(yǔ)言中的語(yǔ)言中的union類型就不允許標(biāo)記，從而不能提類型就不允許標(biāo)記，從而不能提供檢查。供檢查。n具有變體的記錄也稱為具有變體的記錄也稱為union類型，可視為一組數(shù)據(jù)類型，可視為一組數(shù)據(jù)對(duì)象集合的對(duì)象集合的“和和”。如果不允許標(biāo)記，則稱為。如果不允許標(biāo)記，則稱為“自由自由和和”類型（類型（free-union），如果允許標(biāo)記，則稱為），如果允許標(biāo)記，則稱為“判別和判別和”類型（類型（discriminated-union）。）。45可變記錄：實(shí)現(xiàn)可變記錄：實(shí)現(xiàn)n可變記錄的實(shí)現(xiàn)比正確地使用

41、它要容易。在翻譯時(shí)，可變記錄的實(shí)現(xiàn)比正確地使用它要容易。在翻譯時(shí)，每個(gè)變體的部件的存儲(chǔ)需要量是確定的，存儲(chǔ)的分配每個(gè)變體的部件的存儲(chǔ)需要量是確定的，存儲(chǔ)的分配根據(jù)最大的可能變體來安排。在存儲(chǔ)塊內(nèi)，每個(gè)變體根據(jù)最大的可能變體來安排。在存儲(chǔ)塊內(nèi)，每個(gè)變體根據(jù)部件的類型和數(shù)量具有不同的布局。布局在編譯根據(jù)部件的類型和數(shù)量具有不同的布局。布局在編譯時(shí)確定，并用于計(jì)算被選擇部件的位移。運(yùn)行時(shí)，不時(shí)確定，并用于計(jì)算被選擇部件的位移。運(yùn)行時(shí)，不需要特殊的描述子。需要特殊的描述子。n如果不進(jìn)行檢查的話，變體中部件的選擇相同于普通記錄的如果不進(jìn)行檢查的話，變體中部件的選擇相同于普通記錄的部件選擇。在翻譯時(shí)，被選

42、擇部件在存儲(chǔ)塊中的位移被計(jì)算部件選擇。在翻譯時(shí)，被選擇部件在存儲(chǔ)塊中的位移被計(jì)算出來，在運(yùn)行時(shí)，位移被加到塊的基地址上以形成部件的地出來，在運(yùn)行時(shí)，位移被加到塊的基地址上以形成部件的地址。此時(shí)，部件存在與否十分重要，如不存在，則將取出不址。此時(shí)，部件存在與否十分重要，如不存在，則將取出不是所期望的值，而對(duì)該部件位置的修改也有可能帶來災(zāi)難性是所期望的值，而對(duì)該部件位置的修改也有可能帶來災(zāi)難性后果。后果。n如果提供動(dòng)態(tài)檢查，則先檢查標(biāo)記部件的內(nèi)容，以保證標(biāo)記如果提供動(dòng)態(tài)檢查，則先檢查標(biāo)記部件的內(nèi)容，以保證標(biāo)記指示出所需的變體確實(shí)存在。指示出所需的變體確實(shí)存在。46可可變變記記錄：錄：存存儲(chǔ)儲(chǔ)表表示

43、示返回47列表（列表（ List ）n由數(shù)據(jù)結(jié)構(gòu)的有序序列組成的數(shù)據(jù)結(jié)構(gòu)。由數(shù)據(jù)結(jié)構(gòu)的有序序列組成的數(shù)據(jù)結(jié)構(gòu)。n規(guī)約和語(yǔ)法：列表類似于向量，都由數(shù)據(jù)對(duì)象規(guī)約和語(yǔ)法：列表類似于向量，都由數(shù)據(jù)對(duì)象的有序序列構(gòu)成，即可以訪問列表的第一個(gè)元的有序序列構(gòu)成，即可以訪問列表的第一個(gè)元素、第二個(gè)元素、依此類推。它們的不同主要素、第二個(gè)元素、依此類推。它們的不同主要體現(xiàn)在：體現(xiàn)在：1、列表基本上不會(huì)固定長(zhǎng)度，通常用于表示任意的、列表基本上不會(huì)固定長(zhǎng)度，通常用于表示任意的數(shù)據(jù)結(jié)構(gòu)，并在運(yùn)行中增長(zhǎng)和縮小。數(shù)據(jù)結(jié)構(gòu)，并在運(yùn)行中增長(zhǎng)和縮小。2、列表基本上都是異構(gòu)的，列表的每個(gè)成員的數(shù)據(jù)、列表基本上都是異構(gòu)的，列表的每

44、個(gè)成員的數(shù)據(jù)類型均可以不同。類型均可以不同。3、使用列表的語(yǔ)言典型地通過隱式的方式聲明這樣、使用列表的語(yǔ)言典型地通過隱式的方式聲明這樣的數(shù)據(jù)，其成員沒有顯式的屬性。的數(shù)據(jù)，其成員沒有顯式的屬性。48列表：實(shí)例列表：實(shí)例nLISP語(yǔ)法是典型的列表結(jié)構(gòu)：語(yǔ)法是典型的列表結(jié)構(gòu)：(FunctionName Data1 Data2 Datan)n在在LISP中，大多數(shù)操作以列表為參數(shù)并返回列表值。中，大多數(shù)操作以列表為參數(shù)并返回列表值。如：如：(cons (a b c) (d e f) = (a b c) d e f)nLISP的一個(gè)重要特征是：所有參數(shù)需先計(jì)值。如上式的一個(gè)重要特征是：所有參數(shù)需先計(jì)值

45、。如上式寫為：寫為：(cons (a b c) (d e f) = (a b c) d e f)n則首先計(jì)值函數(shù)則首先計(jì)值函數(shù)a，然后計(jì)值函數(shù)，然后計(jì)值函數(shù)d，這可能產(chǎn)生錯(cuò)誤。而函，這可能產(chǎn)生錯(cuò)誤。而函數(shù)數(shù)(quote x)，或，或x，只返回變量的文字值，從而避免不適，只返回變量的文字值，從而避免不適當(dāng)?shù)挠?jì)值。當(dāng)?shù)挠?jì)值。nML屬于賦類型的函數(shù)語(yǔ)言，因此，其表是同構(gòu)的。如：屬于賦類型的函數(shù)語(yǔ)言，因此，其表是同構(gòu)的。如：1, 2, 3、a, b, c、“abc”, “def”, “ghi”等。等。49列表：實(shí)現(xiàn)列表：實(shí)現(xiàn)n由于列表元素的異構(gòu)性和大多數(shù)列表實(shí)由于列表元素的異構(gòu)性和大多數(shù)列表實(shí)現(xiàn)的動(dòng)態(tài)

46、性，向量、數(shù)組所用的存儲(chǔ)表現(xiàn)的動(dòng)態(tài)性，向量、數(shù)組所用的存儲(chǔ)表示將不適用于列表。通常適用鏈接列表示將不適用于列表。通常適用鏈接列表存儲(chǔ)組織結(jié)構(gòu)。表項(xiàng)是基本元素，通常存儲(chǔ)組織結(jié)構(gòu)。表項(xiàng)是基本元素，通常由固定長(zhǎng)度的數(shù)據(jù)對(duì)象構(gòu)成。由固定長(zhǎng)度的數(shù)據(jù)對(duì)象構(gòu)成。50列表：存儲(chǔ)表示（列表：存儲(chǔ)表示（1）n在在LISP中，通常含有三個(gè)信息域：一個(gè)類型域，兩個(gè)中，通常含有三個(gè)信息域：一個(gè)類型域，兩個(gè)表指針。如果類型域指明為原子，則剩下的域?yàn)槊枋霰碇羔槨Ｈ绻愋陀蛑该鳛樵?，則剩下的域?yàn)槊枋鲈撛拥拿枋鲎印Ｈ绻愋陀蛑该鳛楸?，則第一個(gè)指該原子的描述子。如果類型域指明為表，則第一個(gè)指針為表頭，第二個(gè)指針為表的尾。針為

47、表頭，第二個(gè)指針為表的尾。51列表：存儲(chǔ)表示（列表：存儲(chǔ)表示（2）n這種表示的中間和底層結(jié)構(gòu)的類似性顯示了這種實(shí)現(xiàn)方式的功效：這種表示的中間和底層結(jié)構(gòu)的類似性顯示了這種實(shí)現(xiàn)方式的功效：1、cons：cons或或join操作通過創(chuàng)建一個(gè)新表節(jié)點(diǎn)而實(shí)現(xiàn)，該節(jié)點(diǎn)的操作通過創(chuàng)建一個(gè)新表節(jié)點(diǎn)而實(shí)現(xiàn)，該節(jié)點(diǎn)的頭域指向第一個(gè)參數(shù)，尾域指向第二個(gè)參數(shù)。頭域指向第一個(gè)參數(shù)，尾域指向第二個(gè)參數(shù)。2、head：表的頭是表項(xiàng)的頭域的內(nèi)容（右值）。：表的頭是表項(xiàng)的頭域的內(nèi)容（右值）。3、tail：表的尾是表項(xiàng)的尾域的內(nèi)容。：表的尾是表項(xiàng)的尾域的內(nèi)容。52列表的變種列表的變種(1)n棧和隊(duì)列：棧是一種列表，其中部件的棧和

48、隊(duì)列：棧是一種列表，其中部件的選擇、插入和刪除被限制在一端進(jìn)行。選擇、插入和刪除被限制在一端進(jìn)行。隊(duì)列的部件選擇和刪除被限制在一端，隊(duì)列的部件選擇和刪除被限制在一端，而插入被限制在另一端。而插入被限制在另一端。n樹：其中的部件可以是列表以及基本數(shù)樹：其中的部件可以是列表以及基本數(shù)據(jù)對(duì)象，而每個(gè)列表只能最多是另一個(gè)據(jù)對(duì)象，而每個(gè)列表只能最多是另一個(gè)列表的部件。大多數(shù)列表的部件。大多數(shù)LISP例子實(shí)際上是例子實(shí)際上是樹。樹。53列表的變種列表的變種(2)n有向圖：其中的部件可以被任意的鏈接有向圖：其中的部件可以被任意的鏈接模式鏈接在一起，而不僅僅是線性序。模式鏈接在一起，而不僅僅是線性序。n性質(zhì)表

49、：具有可變數(shù)量部件的記錄通常性質(zhì)表：具有可變數(shù)量部件的記錄通常稱為性質(zhì)表，如果部件的數(shù)量可以無限稱為性質(zhì)表，如果部件的數(shù)量可以無限變化。在性質(zhì)表中，部件名及其值均需變化。在性質(zhì)表中，部件名及其值均需被存儲(chǔ)，分別稱為性質(zhì)名和性質(zhì)值。性被存儲(chǔ)，分別稱為性質(zhì)名和性質(zhì)值。性質(zhì)表通常表示為鏈接表。質(zhì)表通常表示為鏈接表。54性性質(zhì)質(zhì)表表的的存存儲(chǔ)儲(chǔ)表表示示返回55集合集合n集合是一個(gè)數(shù)據(jù)對(duì)象，它包含不同值的無序集合。而集合是一個(gè)數(shù)據(jù)對(duì)象，它包含不同值的無序集合。而列表中元素是可以重復(fù)的。集合上的基本操作有：列表中元素是可以重復(fù)的。集合上的基本操作有：1、成員關(guān)系：、成員關(guān)系：X是否為是否為S中的成員？中的

50、成員？X S？2、單個(gè)值的插入和刪除。如果、單個(gè)值的插入和刪除。如果X不是不是S中的成員，則可以插入中的成員，則可以插入X；如果如果X是是S中的成員，則可從中的成員，則可從S中刪除中刪除X。3、并、交和差。、并、交和差。n集合中成員的訪問不能使用下標(biāo)或相對(duì)位置。集合中成員的訪問不能使用下標(biāo)或相對(duì)位置。n實(shí)現(xiàn)：在程序設(shè)計(jì)語(yǔ)言中，集合有時(shí)是指表示有序集實(shí)現(xiàn)：在程序設(shè)計(jì)語(yǔ)言中，集合有時(shí)是指表示有序集合的數(shù)據(jù)結(jié)構(gòu)。一個(gè)有序集合實(shí)際上是一個(gè)列表，只合的數(shù)據(jù)結(jié)構(gòu)。一個(gè)有序集合實(shí)際上是一個(gè)列表，只是不允許元素的重復(fù)。而無序集合則需要兩種不同的是不允許元素的重復(fù)。而無序集合則需要兩種不同的存儲(chǔ)表示。存儲(chǔ)表示。

51、56集合的表示：位串集合的表示：位串n位串存儲(chǔ)表示適合于已經(jīng)知道集合元素域的大小較小的情形。假位串存儲(chǔ)表示適合于已經(jīng)知道集合元素域的大小較小的情形。假定在域中有定在域中有N個(gè)元素，這些元素任意排序?yàn)閭€(gè)元素，這些元素任意排序?yàn)閑1、e2、eN，從該域選擇出的一組元素可以用長(zhǎng)度為從該域選擇出的一組元素可以用長(zhǎng)度為N的位串來表示，其中，的位串來表示，其中，如果如果ei存在于集合中，則串的第存在于集合中，則串的第i位為位為1，否則為，否則為0。n位串表示了集合的特征函數(shù)。元素的插入表現(xiàn)為相應(yīng)位的設(shè)置，位串表示了集合的特征函數(shù)。元素的插入表現(xiàn)為相應(yīng)位的設(shè)置，元素的刪除表現(xiàn)為相應(yīng)位的清除，成員關(guān)系判斷表現(xiàn)

52、為檢查相應(yīng)元素的刪除表現(xiàn)為相應(yīng)位的清除，成員關(guān)系判斷表現(xiàn)為檢查相應(yīng)位，并、交及差的操作可實(shí)現(xiàn)為位串上的布爾操作，通常有硬件位，并、交及差的操作可實(shí)現(xiàn)為位串上的布爾操作，通常有硬件支持。支持。n如果提供了對(duì)位串操作的硬件支持，則集合的位串表示的操作將如果提供了對(duì)位串操作的硬件支持，則集合的位串表示的操作將是非常高效的。然而，硬件操作通常僅僅應(yīng)用到某固定長(zhǎng)度的位是非常高效的。然而，硬件操作通常僅僅應(yīng)用到某固定長(zhǎng)度的位串（如：字的長(zhǎng)度）。如果串的長(zhǎng)度大于最大值，則軟件仿真將串（如：字的長(zhǎng)度）。如果串的長(zhǎng)度大于最大值，則軟件仿真將是需要的，用于將位串分為較小的、可被硬件直接操作的單元。是需要的，用于將

53、位串分為較小的、可被硬件直接操作的單元。有的語(yǔ)言為此而限定集合的大小。有的語(yǔ)言為此而限定集合的大小。57集合的表示：集合的表示：HASH編碼編碼n另一種常見的集合表示方法為另一種常見的集合表示方法為HASH編碼或散編碼或散列存儲(chǔ)。該方法可以用于集合的域較大時(shí)。列存儲(chǔ)。該方法可以用于集合的域較大時(shí)。n該方法可允許集合的成員測(cè)試、插入、刪除高該方法可允許集合的成員測(cè)試、插入、刪除高效地完成。效地完成。n然而，并、交及差等操作效率不高，必須實(shí)現(xiàn)為一然而，并、交及差等操作效率不高，必須實(shí)現(xiàn)為一系列個(gè)體元素的成員測(cè)試、插入、刪除等操作。系列個(gè)體元素的成員測(cè)試、插入、刪除等操作。n為了有效，為了有效，HA

54、SH編碼方法需要實(shí)質(zhì)性的存儲(chǔ)編碼方法需要實(shí)質(zhì)性的存儲(chǔ)分配。分配。58集合的表示：集合的表示：HASH編碼編碼n語(yǔ)言并不向用戶提供集合數(shù)據(jù)類型的這語(yǔ)言并不向用戶提供集合數(shù)據(jù)類型的這種表示方式，但語(yǔ)言的實(shí)現(xiàn)在翻譯或執(zhí)種表示方式，但語(yǔ)言的實(shí)現(xiàn)在翻譯或執(zhí)行中使用這種表示來實(shí)現(xiàn)一些系統(tǒng)定義行中使用這種表示來實(shí)現(xiàn)一些系統(tǒng)定義的數(shù)據(jù)。的數(shù)據(jù)。n如，大多數(shù)如，大多數(shù)LISP實(shí)現(xiàn)使用這種存儲(chǔ)表示來實(shí)現(xiàn)使用這種存儲(chǔ)表示來實(shí)現(xiàn)名為實(shí)現(xiàn)名為object list的集合，它包含的集合，它包含LISP程序執(zhí)行中所有原子數(shù)據(jù)對(duì)象的名字。程序執(zhí)行中所有原子數(shù)據(jù)對(duì)象的名字。n幾乎所有的編譯器使用幾乎所有的編譯器使用HASH編碼

55、來查編碼來查找符號(hào)表的名字。找符號(hào)表的名字。59集合的表示：集合的表示：HASH編碼編碼n在一個(gè)向量中，每個(gè)下標(biāo)指定一個(gè)唯一的部件，可以在一個(gè)向量中，每個(gè)下標(biāo)指定一個(gè)唯一的部件，可以使用簡(jiǎn)單的訪問函數(shù)來達(dá)到該目標(biāo)。使用簡(jiǎn)單的訪問函數(shù)來達(dá)到該目標(biāo)。nHASH編碼的目標(biāo)就是要盡可能地達(dá)到這樣的效果。編碼的目標(biāo)就是要盡可能地達(dá)到這樣的效果。問題是：潛在的合法名字的集合相對(duì)于可用的存儲(chǔ)而問題是：潛在的合法名字的集合相對(duì)于可用的存儲(chǔ)而言是大的。如果我們分配言是大的。如果我們分配HASH表至少為我們所期望表至少為我們所期望使用的兩倍大，則使用的兩倍大，則HASH編碼將是非常高效的。編碼將是非常高效的。n不

56、是將集合中元素順序地存放在存儲(chǔ)塊中，而是將元不是將集合中元素順序地存放在存儲(chǔ)塊中，而是將元素隨機(jī)地散列在塊中。其技巧在于以這種方式存放每素隨機(jī)地散列在塊中。其技巧在于以這種方式存放每一個(gè)元素，而其存在與否在以后將可以立即地確定，一個(gè)元素，而其存在與否在以后將可以立即地確定，而不需要搜索整個(gè)存儲(chǔ)塊。而不需要搜索整個(gè)存儲(chǔ)塊。n考慮加入元素考慮加入元素X到集合到集合S，位串，位串Bx表示表示X，存儲(chǔ)塊，存儲(chǔ)塊Ms表示表示S。應(yīng)用應(yīng)用HASH函數(shù)到函數(shù)到Bx得到得到Bx在在Ms中的位置中的位置Ix，稱為，稱為HASH地地址，用為指向塊中位置的索引。如果址，用為指向塊中位置的索引。如果X不在不在S中，則

57、中，則Bx將被存將被存入到入到Ms中由中由Ix指定的位置。指定的位置。X的查找是方便的，提供使用同的查找是方便的，提供使用同樣的樣的HASH函數(shù)可找到其在函數(shù)可找到其在Ms中的位置。中的位置。60集合的表示：集合的表示：HASH編碼編碼n對(duì)對(duì)HASH函數(shù)的要求一是計(jì)算速度，二是分布的隨機(jī)函數(shù)的要求一是計(jì)算速度，二是分布的隨機(jī)性。假定性。假定Ms為為1024個(gè)字，需要存放的數(shù)據(jù)項(xiàng)是表示個(gè)字，需要存放的數(shù)據(jù)項(xiàng)是表示為雙字位串的字符串，則我們可以表示一個(gè)可含為雙字位串的字符串，則我們可以表示一個(gè)可含511個(gè)不同元素的集合。假定塊的起始地址為個(gè)不同元素的集合。假定塊的起始地址為 ，一個(gè)合適，一個(gè)合適的

58、的HASH地址將是地址將是9位的串位的串Ix，因?yàn)楣?，因?yàn)楣?2Ix將將總是產(chǎn)生在塊內(nèi)的地址?？偸钱a(chǎn)生在塊內(nèi)的地址。Ix由由Bx產(chǎn)生，假定產(chǎn)生，假定Bx存放在存放在字字a和和b中。中。1、a乘以乘以b，得到，得到c（兩個(gè)字長(zhǎng)）（兩個(gè)字長(zhǎng)）2、將、將c的兩個(gè)字相加，得到的兩個(gè)字相加，得到d（一個(gè)字長(zhǎng)）（一個(gè)字長(zhǎng)）3、將、將d平方，得到平方，得到e4、取、取e的中間的中間9位，得到位，得到Ix61集合的表示：集合的表示：HASH編碼編碼n即使最好的即使最好的HASH函數(shù)也不能保證對(duì)不同的數(shù)據(jù)項(xiàng)產(chǎn)函數(shù)也不能保證對(duì)不同的數(shù)據(jù)項(xiàng)產(chǎn)生不同的地址。幾乎不可避免地會(huì)產(chǎn)生沖突。生不同的地址。幾乎不可避免地會(huì)

59、產(chǎn)生沖突。n處理沖突的解決辦法：處理沖突的解決辦法：1、重新、重新HASH?？梢钥紤]修改初始的位串?？梢钥紤]修改初始的位串Bx，如：乘以某，如：乘以某常量。然后重新常量。然后重新HASH。直至無沖突為止。直至無沖突為止。2、順序掃描。從塊中的沖突點(diǎn)開始進(jìn)行順序搜索，直至找、順序掃描。從塊中的沖突點(diǎn)開始進(jìn)行順序搜索，直至找到某到某Bx，或遇到一個(gè)空位置。，或遇到一個(gè)空位置。3、使用桶（、使用桶（bucketing）。在塊中的位置上用一個(gè)指針來）。在塊中的位置上用一個(gè)指針來指向具有相同指向具有相同HASH地址的一個(gè)鏈接桶表。地址的一個(gè)鏈接桶表。n不同的不同的HASH函數(shù)合適于不同的將被存放的位串表

60、函數(shù)合適于不同的將被存放的位串表示。如果有一個(gè)好的示。如果有一個(gè)好的HASH函數(shù)，且表是半滿的，函數(shù)，且表是半滿的，則沖突較少發(fā)生。則沖突較少發(fā)生。n前面例子中前面例子中512個(gè)項(xiàng)只用了個(gè)項(xiàng)只用了511個(gè)的原因就是為了個(gè)的原因就是為了解決沖突。解決沖突。返回626.2 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 n數(shù)據(jù)類型概念的演化數(shù)據(jù)類型概念的演化n早期類型定義為值的集合，該類型的變量可在該集早期類型定義為值的集合，該類型的變量可在該集合中取值。合中取值。n70年代初，年代初，Pascal擴(kuò)展類型定義為：變量的集合。擴(kuò)展類型定義為：變量的集合。n70年代早期，概念進(jìn)一步演化，類型不僅僅是類型年代早期，概念進(jìn)一