第六章封裝PPT課件

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

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

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

4、結(jié)構(gòu)數(shù)據(jù)對象和數(shù)據(jù)類型n結(jié)構(gòu)數(shù)據(jù)對象結(jié)構(gòu)數(shù)據(jù)對象一組其他數(shù)據(jù)對象構(gòu)成的聚集，這一組其他數(shù)據(jù)對象構(gòu)成的聚集，這些數(shù)據(jù)對象稱為元素或部件，可以是基本類型，也可些數(shù)據(jù)對象稱為元素或部件，可以是基本類型，也可以是結(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ī)約和和類型實現(xiàn)類型實現(xiàn)，只是更為，只是更為復(fù)雜。復(fù)雜。n兩個方面是特別重要的：兩個方面是特別重要的：n結(jié)構(gòu)信息的規(guī)約和實現(xiàn)變成了中心問題，用于指出部件對象結(jié)構(gòu)信息的規(guī)約和實現(xiàn)變成

5、了中心問題，用于指出部件對象及其間關(guān)系，以便于部件的直接及其間關(guān)系，以便于部件的直接選取選取（或訪問）。（或訪問）。n結(jié)構(gòu)上的很多操作帶來的存儲管理問題。結(jié)構(gòu)上的很多操作帶來的存儲管理問題。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也可能是變長的，數(shù)量可以動態(tài)變化，如：棧、也可能是變長的，數(shù)量可以動態(tài)變化，如：棧、列表、集合、文件、表格等。列表、集合、文件、表格等。n變長結(jié)構(gòu)通常需定義插入和刪去部件的操作

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

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

8、。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有兩種類型：有兩種類型： 隨機選擇隨機選擇可任意選擇結(jié)構(gòu)中某一部件可任意選擇結(jié)構(gòu)中某一部件順序選擇順序選擇以預(yù)定好的順序選擇部

9、件。以預(yù)定好的順序選擇部件。n數(shù)據(jù)對象中部件或數(shù)據(jù)值的選擇和相關(guān)的引用操作數(shù)據(jù)對象中部件或數(shù)據(jù)值的選擇和相關(guān)的引用操作是有區(qū)別的。如：是有區(qū)別的。如：V4選擇選擇V中第中第4個元素，分兩個元素，分兩步：步：n先引用（確定先引用（確定V的位置（的位置（l-值），返回一個指針），值），返回一個指針），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ù)語言中，這樣的整體性操作是有限大多數(shù)語言中，這樣的整體性操作是有限的

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

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

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

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

14、的實現(xiàn)n鏈接表示鏈接表示n隨機選擇需要沿指針鏈從頭查找，需知道在隨機選擇需要沿指針鏈從頭查找，需知道在部件塊中鏈指針的位置。部件塊中鏈指針的位置。n部件序列的選取相對容易，沿指針向前即可。部件序列的選取相對容易，沿指針向前即可。返回18數(shù)據(jù)對象的訪問數(shù)據(jù)對象的訪問n數(shù)據(jù)對象一旦創(chuàng)建，需同時創(chuàng)建它的數(shù)據(jù)對象一旦創(chuàng)建，需同時創(chuàng)建它的訪問路徑訪問路徑，使得，使得對象可被程序中的操作訪問。對象可被程序中的操作訪問。n訪問路徑的創(chuàng)建方式：訪問路徑的創(chuàng)建方式：n將標(biāo)識符（名字）和對象相關(guān)聯(lián)將標(biāo)識符（名字）和對象相關(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)建一個新指針創(chuàng)建一個新指針 n訪問路徑也可以被刪除訪問路徑也可以被刪除n如：賦新值給一個新指針變量如：賦新值給一個新指針變量 從子程序返回。從子程序返回。19數(shù)據(jù)對象的訪問數(shù)據(jù)對象的訪問n與數(shù)據(jù)對象的生命周期及訪問路徑相關(guān)的兩個與數(shù)據(jù)對象的生命周期及訪問路徑相關(guān)的兩個中心問題：中心問題：1、垃圾：、垃圾：n當(dāng)所有訪問路徑被消除，但數(shù)據(jù)對象仍然存在，它將不可當(dāng)所有訪問路徑被消除，但數(shù)據(jù)對象仍然存在，它將不可再被訪問。因此，其和存儲位置的綁

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

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

18、定第二個部件，依此類推。下標(biāo)可以是給出一個值的范圍，也可以是只給出上界，給出一個值的范圍，也可以是只給出上界，而下界是隱含的。而下界是隱含的。 22向量：聲明向量：聲明n典型的向量聲明：典型的向量聲明：V : array 1.10 of real;-PASCAL語言語言float a10;-C語言語言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)大都是可計算值，固可用表達式作下標(biāo)：由于下標(biāo)大都是可計算值，固可用表達式作下標(biāo)：VI + 2n其它操作包括：向量的創(chuàng)建和消除，向量元素的賦其它操作包括：向量的創(chuàng)建和消除，向量元素的賦值，相同大小的兩個向量間的算術(shù)操作等。通常插值，相同大小的兩個向量間的算術(shù)操作等。通常插入和刪除向量元素是不允許的。入和刪除向量元素是不允許的。nAPL是專門基于數(shù)組的語言，允許大量向量操作。是專門基于數(shù)組的語言，允許大量向量操作。24向量：實現(xiàn)向量：實現(xiàn)n由于向量的同構(gòu)性和由于向量

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

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

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

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

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

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

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

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

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

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

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

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

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

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

34、的元素混雜在一起。如：一個向量的每個元素都是一個記錄，在個向量的每個元素都是一個記錄，在C中有如下聲明：中有如下聲明：struct EmployeeType int ID;int Age;float Salary;char Dept; Employee500;n這樣一個復(fù)合數(shù)據(jù)結(jié)構(gòu)的元素的選擇需要一系列選擇這樣一個復(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、使用層次編號來語法使用層次編號來語法地指定這種層次結(jié)構(gòu)。地指定這種層次結(jié)構(gòu)。如，一個如，一個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ù)組：實現(xiàn)含結(jié)構(gòu)元素的記錄和數(shù)組

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

37、共同的部分，但各個變體同的部分，但各個變體又有自己獨有的部件。又有自己獨有的部件。如，雇員可以分為按月如，雇員可以分為按月和按小時領(lǐng)工資兩種情和按小時領(lǐng)工資兩種情況，從而呈現(xiàn)兩個變體。況，從而呈現(xiàn)兩個變體。n例如，一個例如，一個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變體記錄的選擇操作和一般記錄相同，但由于變體問變體記錄的選擇操作和一般記錄相同，但由于變體問題，有的部件的存在性會在運行中發(fā)生變化，因此，題，有的部件的存在性會在運行中發(fā)生變化，因此，有的選擇操作可能在運行中某時刻找不到希望的部件，有的選擇操作可能在運行中某時刻找不到希望的部件，如：如：Emp

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

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

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

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

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ī)約和語法：列表類似于向量，都由數(shù)據(jù)對象規(guī)約和語法：列表類似于向量，都由數(shù)據(jù)對象的有序序列構(gòu)成，即可以訪問列表的第一個元的有序序列構(gòu)成，即可以訪問列表的第一個元素、第二個元素、依此類推。它們的不同主要素、第二個元素、依此類推。它們的不同主要體現(xiàn)在：體現(xiàn)在：1、列表基本上不會固定長度，通常用于表示任意的、列表基本上不會固定長度，通常用于表示任意的數(shù)據(jù)結(jié)構(gòu)，并在運行中增長和縮小。數(shù)據(jù)結(jié)構(gòu)，并在運行中增長和縮小。2、列表基本上都是異構(gòu)的，列表的每個成員的數(shù)據(jù)、列表基本上都是異構(gòu)的，列表的每

44、個成員的數(shù)據(jù)類型均可以不同。類型均可以不同。3、使用列表的語言典型地通過隱式的方式聲明這樣、使用列表的語言典型地通過隱式的方式聲明這樣的數(shù)據(jù)，其成員沒有顯式的屬性。的數(shù)據(jù)，其成員沒有顯式的屬性。48列表：實例列表：實例nLISP語法是典型的列表結(jié)構(gòu)：語法是典型的列表結(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的一個重要特征是：所有參數(shù)需先計值。如上式的一個重要特征是：所有參數(shù)需先計值

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

46、性，向量、數(shù)組所用的存儲表現(xiàn)的動態(tài)性，向量、數(shù)組所用的存儲表示將不適用于列表。通常適用鏈接列表示將不適用于列表。通常適用鏈接列表存儲組織結(jié)構(gòu)。表項是基本元素，通常存儲組織結(jié)構(gòu)。表項是基本元素，通常由固定長度的數(shù)據(jù)對象構(gòu)成。由固定長度的數(shù)據(jù)對象構(gòu)成。50列表：存儲表示（列表：存儲表示（1）n在在LISP中，通常含有三個信息域：一個類型域，兩個中，通常含有三個信息域：一個類型域，兩個表指針。如果類型域指明為原子，則剩下的域為描述表指針。如果類型域指明為原子，則剩下的域為描述該原子的描述子。如果類型域指明為表，則第一個指該原子的描述子。如果類型域指明為表，則第一個指針為表頭，第二個指針為表的尾。針為

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

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

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

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

51、56集合的表示：位串集合的表示：位串n位串存儲表示適合于已經(jīng)知道集合元素域的大小較小的情形。假位串存儲表示適合于已經(jīng)知道集合元素域的大小較小的情形。假定在域中有定在域中有N個元素，這些元素任意排序為個元素，這些元素任意排序為e1、e2、eN，從該域選擇出的一組元素可以用長度為從該域選擇出的一組元素可以用長度為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)位，并、交及差的操作可實現(xiàn)為位串上的布爾操作，通常有硬件位，并、交及差的操作可實現(xiàn)為位串上的布爾操作，通常有硬件支持。支持。n如果提供了對位串操作的硬件支持，則集合的位串表示的操作將如果提供了對位串操作的硬件支持，則集合的位串表示的操作將是非常高效的。然而，硬件操作通常僅僅應(yīng)用到某固定長度的位是非常高效的。然而，硬件操作通常僅僅應(yīng)用到某固定長度的位串（如：字的長度）。如果串的長度大于最大值，則軟件仿真將串（如：字的長度）。如果串的長度大于最大值，則軟件仿真將是需要的，用于將位串分為較小的、可被硬件直接操作的單元。是需要的，用于將

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

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

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

56、是將集合中元素順序地存放在存儲塊中，而是將元不是將集合中元素順序地存放在存儲塊中，而是將元素隨機地散列在塊中。其技巧在于以這種方式存放每素隨機地散列在塊中。其技巧在于以這種方式存放每一個元素，而其存在與否在以后將可以立即地確定，一個元素，而其存在與否在以后將可以立即地確定，而不需要搜索整個存儲塊。而不需要搜索整個存儲塊。n考慮加入元素考慮加入元素X到集合到集合S，位串，位串Bx表示表示X，存儲塊，存儲塊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對對HASH函數(shù)的要求一是計算速度，二是分布的隨機函數(shù)的要求一是計算速度，二是分布的隨機性。假定性。假定Ms為為1024個字，需要存放的數(shù)據(jù)項是表示個字，需要存放的數(shù)據(jù)項是表示為雙字位串的字符串，則我們可以表示一個可含為雙字位串的字符串，則我們可以表示一個可含511個不同元素的集合。假定塊的起始地址為個不同元素的集合。假定塊的起始地址為 ，一個合適，一個合適的

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

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

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