掌握算法設(shè)計(jì)與分析的基本知識(shí)和基本概念

1、.第一章緒論1掌握算法設(shè)計(jì)與分析的基本知識(shí)和基本概念摘要：數(shù)據(jù)結(jié)構(gòu)與算法的基本概念的理解.教學(xué)難點(diǎn):抽象數(shù)據(jù)類型及其操作.授課內(nèi)容計(jì)算機(jī)科學(xué)是一門(mén)研究數(shù)據(jù)表示和數(shù)據(jù)處理的科學(xué).數(shù)據(jù)是計(jì)算機(jī)化的信息,它是計(jì)算機(jī)可以直接.關(guān)鍵詞：算法,計(jì)算機(jī)類別：專題技術(shù)來(lái)源：牛檔搜索（Niudown.COM）本文系牛檔搜索（Niudown.COM）根據(jù)用戶的指令自動(dòng)搜索的結(jié)果，文中內(nèi)涉及到的資料均來(lái)自互聯(lián)網(wǎng)，用于學(xué)習(xí)交流經(jīng)驗(yàn)，作品其著作權(quán)歸原作者所有。不代表牛檔搜索（Niudown.COM）贊成本文的內(nèi)容或立場(chǎng)，牛檔搜索（Niudown.COM）不對(duì)其付相應(yīng)的法律責(zé)任！;第一講 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ) 1掌握

2、算法設(shè)計(jì)與分析的基本知識(shí)和基本概念， 2.從總體上了解基本數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用，各種數(shù)據(jù)結(jié)構(gòu)的優(yōu) ，以及如何選擇常用的數(shù)據(jù)結(jié)構(gòu)，如何應(yīng)用抽象數(shù)據(jù)結(jié)構(gòu)類型進(jìn)行數(shù)據(jù)抽象，高級(jí)語(yǔ)言對(duì)數(shù)據(jù)結(jié)構(gòu)及抽象數(shù)據(jù)類型的支持。從總體上了解基本數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用，各種數(shù)據(jù)結(jié)構(gòu)的優(yōu) ，以及如何選擇常用的數(shù)據(jù)結(jié)構(gòu)，如何應(yīng)用抽象數(shù)據(jù)結(jié)構(gòu)類型進(jìn)行數(shù)據(jù)抽象，高級(jí)語(yǔ)言對(duì)數(shù)據(jù)結(jié)構(gòu)及抽象數(shù)據(jù)類型的支持。Ø 教學(xué)重點(diǎn)： 數(shù)據(jù)結(jié)構(gòu)與算法的基本概念的理解。Ø 教學(xué)難點(diǎn)：抽象數(shù)據(jù)類型及其操作。Ø 授課內(nèi)容計(jì)算機(jī)科學(xué)是一門(mén)研究數(shù)據(jù)表示和數(shù)據(jù)處理的科學(xué)。數(shù)據(jù)是計(jì)算機(jī)化的信息，它是計(jì)算機(jī)可以直接處理的最基本和最重要的對(duì)象

3、。無(wú)論是進(jìn)行科學(xué)計(jì)算或數(shù)據(jù)處理、過(guò)程控制以及對(duì)文件的存儲(chǔ)和檢索及數(shù)據(jù)庫(kù)技術(shù)等計(jì)算機(jī)應(yīng)用領(lǐng)域中，都是對(duì)數(shù)據(jù)進(jìn)行加工處理的過(guò)程。因此，要設(shè)計(jì)出一個(gè)結(jié)構(gòu)好效率高的程序，必須研究數(shù)據(jù)的特性及數(shù)據(jù)間的相互關(guān)系及其對(duì)應(yīng)的存儲(chǔ)表示，并利用這些特性和關(guān)系設(shè)計(jì)出相應(yīng)的算法和程序。11 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的專業(yè)基礎(chǔ)課，是十分重要的核心課程。所有的計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。因此，要想更好地運(yùn)用計(jì)算機(jī)來(lái)解決實(shí)際問(wèn)題，僅掌握幾種計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言是難以應(yīng)付眾多復(fù)雜的課題的。要想有效地使用計(jì)算機(jī)、充分發(fā)揮計(jì)算機(jī)的性能，還必須學(xué)習(xí)和掌握好數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識(shí)。打好

4、“數(shù)據(jù)結(jié)構(gòu)”這門(mén)課程的扎實(shí)基礎(chǔ)，對(duì)于學(xué)習(xí)計(jì)算機(jī)專業(yè)的其他課程，如操作系統(tǒng)、編譯原理、數(shù)據(jù)庫(kù)管理系統(tǒng)、軟件工程、人工智能等都是十分有益的。1.1.1 引言在計(jì)算機(jī)發(fā)展的初期，人們使用計(jì)算機(jī)的目的主要是處理數(shù)值計(jì)算問(wèn)題。當(dāng)我們使用計(jì)算機(jī)來(lái)解決一個(gè)具體問(wèn)題時(shí)，一般需要經(jīng)過(guò)下列幾個(gè)步驟：首先要從該具體問(wèn)題抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)或選擇一個(gè)解此數(shù)學(xué)模型的算法，最后編出程序進(jìn)行調(diào)試、測(cè)試，直至得到最終的解答。例如，求解梁架結(jié)構(gòu)中應(yīng)力的數(shù)學(xué)模型的線性方程組，該方程組可以使用迭代算法來(lái)求解。由于當(dāng)時(shí)所涉及的運(yùn)算對(duì)象是簡(jiǎn)單的整型、實(shí)型或布爾類型數(shù)據(jù)，所以程序設(shè)計(jì)者的主要精力是集中于程序設(shè)計(jì)的技巧上，而

5、無(wú)須重視數(shù)據(jù)結(jié)構(gòu)。隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大和軟、硬件的發(fā)展，非數(shù)值計(jì)算問(wèn)題越來(lái)越顯得重要。據(jù)統(tǒng)計(jì)，當(dāng)今處理非數(shù)值計(jì)算性問(wèn)題占用了90%以上的機(jī)器時(shí)間。這類問(wèn)題涉及到的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜，數(shù)據(jù)元素之間的相互關(guān)系一般無(wú)法用數(shù)學(xué)方程式加以描述。因此，解決這類問(wèn)題的關(guān)鍵不再是數(shù)學(xué)分析和計(jì)算方法，而是要設(shè)計(jì)出合適的數(shù)據(jù)結(jié)構(gòu)，才能有效地解決問(wèn)題。下面所列舉的就是屬于這一類的具體問(wèn)題?！纠?】 學(xué)生信息檢索系統(tǒng)。當(dāng)我們需要查找某個(gè)學(xué)生的有關(guān)情況的時(shí)候；或者想查詢某個(gè)專業(yè)或年級(jí)的學(xué)生的有關(guān)情況的時(shí)候，只要我們建立了相關(guān)的數(shù)據(jù)結(jié)構(gòu)，按照某種算法編寫(xiě)了相關(guān)程序，就可以實(shí)現(xiàn)計(jì)算機(jī)自動(dòng)檢索。由此，可以在學(xué)生信息檢索系統(tǒng)

6、中建立一張按學(xué)號(hào)順序排列的學(xué)生信息表和分別按姓名、專業(yè)、年級(jí)順序排列的索引表，如圖1.1所示。由這四張表構(gòu)成的文件便是學(xué)生信息檢索的數(shù)學(xué)模型，計(jì)算機(jī)的主要操作便是按照某個(gè)特定要求（如給定姓名）對(duì)學(xué)生信息文件進(jìn)行查詢。諸如此類的還有電話自動(dòng)查號(hào)系統(tǒng)、考試查分系統(tǒng)、倉(cāng)庫(kù)庫(kù)存管理系統(tǒng)等。在這類文檔管理的數(shù)學(xué)模型中，計(jì)算機(jī)處理的對(duì)象之間通常存在著的是一種簡(jiǎn)單的線性關(guān)系，這類數(shù)學(xué)模型可稱為線性的數(shù)據(jù)結(jié)構(gòu)。學(xué)號(hào)姓名性別專 業(yè)年 級(jí)980001吳承志男計(jì)算機(jī)科學(xué)與技術(shù)98級(jí)980002李淑芳女信息與計(jì)算科學(xué)98級(jí)990301劉 麗女?dāng)?shù)學(xué)與應(yīng)用數(shù)學(xué)99級(jí)990302張會(huì)友男信息與計(jì)算科學(xué)99級(jí)990303石寶

7、國(guó)男計(jì)算機(jī)科學(xué)與技術(shù)99級(jí)000801何文穎女計(jì)算機(jī)科學(xué)與技術(shù)2000級(jí)000802趙勝利男數(shù)學(xué)與應(yīng)用數(shù)學(xué)2000級(jí)000803崔文靖男信息與計(jì)算科學(xué)2000級(jí)010601劉 麗女計(jì)算機(jī)科學(xué)與技術(shù)2001級(jí)010602魏永鳴男數(shù)學(xué)與應(yīng)用數(shù)學(xué)2001級(jí)崔文靖8何文穎6李淑芳2劉 麗3，9石寶國(guó)5魏永鳴10吳承志1趙勝利7張會(huì)有4計(jì)算機(jī)科學(xué)與技術(shù)1，5，6，9信息與計(jì)算科學(xué)2，4，8數(shù)學(xué)與應(yīng)用數(shù)學(xué)3，7，102000級(jí)6，7，82001級(jí)9，1098級(jí)1，2，399級(jí)4，5（a）學(xué)生信息表（b）姓名索引表（c）專業(yè)索引表（d）年級(jí)索引表圖 1.1 學(xué)生信息查詢系統(tǒng)中的數(shù)據(jù)結(jié)構(gòu)【例2】計(jì)算機(jī)和人對(duì)奕

8、問(wèn)題 在對(duì)奕問(wèn)題中，計(jì)算機(jī)操作的對(duì)象是對(duì)奕過(guò)程中可能出現(xiàn)的棋盤(pán)狀態(tài)稱為格局。例如下圖1.2所示為井字棋的一個(gè)格局，而格局之間的關(guān)系是由比賽規(guī)則決定的。通常，這個(gè)關(guān)系不是線性的，因?yàn)閺囊粋€(gè)棋盤(pán)格局可以派生出幾個(gè)格局，例如從1.2所示的格局可以派生出五個(gè)格局，如下圖所示，而從每一個(gè)新的格局又可派生出四個(gè)可能出現(xiàn)的格局。 圖1.2因此，若將從對(duì)奕開(kāi)始到結(jié)束的過(guò)程中所有可能出現(xiàn)的格局都畫(huà)在一張圖上，則可得到一棵倒長(zhǎng)的“樹(shù)”。“樹(shù)根”是對(duì)奕開(kāi)始之前的棋盤(pán)格局，而所有的“葉子”就是可能出現(xiàn)的結(jié)局，對(duì)奕的過(guò)程就是從樹(shù)根沿樹(shù)叉到某個(gè)葉子的過(guò)程。“樹(shù)”可以是某些非數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型，它也是一種數(shù)據(jù)結(jié)構(gòu)。 【

9、例3】多叉路口交通燈的管理問(wèn)題 通常，在十字交叉路口只需設(shè)紅、綠兩色的交通燈便可保持正常的交通秩序，而在多交叉路口需設(shè)幾種顏色的交通燈才能使車輛相互之間不碰撞，又能達(dá)到車輛的最大流通。 假設(shè)有一個(gè)如圖13(a)所示的五叉路口，其中C和E為單行道。在路口有13條可行的通路，其中有的可以同時(shí)通行，如AB和EC，而有的不能同時(shí)通行，如EB和AD。那末，在路口應(yīng)如何設(shè)置交通燈進(jìn)行車輛的管理呢? 通常，這類交通、道路問(wèn)題的數(shù)學(xué)模型是一種稱謂“圖”的數(shù)據(jù)結(jié)構(gòu)。例如在此例題中，可以用圖中一個(gè)頂點(diǎn)表示一條通路，而通路之間互相矛盾的關(guān)系以兩個(gè)頂點(diǎn)之間的連線表示。設(shè)置交通燈的問(wèn)題等價(jià)為對(duì)圖的頂點(diǎn)的染色問(wèn)題，要求對(duì)

10、圖上的每個(gè)頂點(diǎn)染一種顏色，并且要求有線相連的兩個(gè)頂點(diǎn)不能具有相同顏色，而總的顏色種類應(yīng)盡可能地少。 綜上三個(gè)例子可見(jiàn)，描述這類非數(shù)值問(wèn)題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹(shù)和圖之類的數(shù)據(jù)結(jié)構(gòu)。因此簡(jiǎn)單說(shuō)來(lái)，數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的目的是為了了解計(jì)算機(jī)處理對(duì)象的特性，將實(shí)際問(wèn)題中所涉及的處理對(duì)象在計(jì)算機(jī)中表示出來(lái)并對(duì)它們進(jìn)行處理。與此同時(shí)，通過(guò)算法訓(xùn)練來(lái)提高學(xué)生的思維能力，通過(guò)程序設(shè)計(jì)的技能訓(xùn)練來(lái)促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。1.1.2 有關(guān)概念和術(shù)語(yǔ)在系統(tǒng)地學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)知識(shí)之前，先對(duì)一些基本概念

11、和術(shù)語(yǔ)賦予確切的含義。第一章緒論數(shù)據(jù)（Data）是信息的載體，它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。它是計(jì)算機(jī)程序加工的原料，應(yīng)用程序處理各種各樣的數(shù)據(jù)。計(jì)算機(jī)科學(xué)中，所謂數(shù)據(jù)就是計(jì)算機(jī)加工處理的對(duì)象，它可以是數(shù)值數(shù)據(jù)，也可以是非數(shù)值數(shù)據(jù)。數(shù)值數(shù)據(jù)是一些整數(shù)、實(shí)數(shù)或復(fù)數(shù)，主要用于工程計(jì)算、科學(xué)計(jì)算和商務(wù)處理等；非數(shù)值數(shù)據(jù)包括字符、文字、圖形、圖像、語(yǔ)音、光和電等。數(shù)據(jù)元素（Data Element）是數(shù)據(jù)的基本單位。在計(jì)算機(jī)程序中作為一個(gè)整體競(jìng)相考慮和處理。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。例如，學(xué)生信息檢索系統(tǒng)中學(xué)生信息表中的一個(gè)記錄、人機(jī)對(duì)弈問(wèn)題中狀態(tài)樹(shù)的一個(gè)狀態(tài)、交

12、通問(wèn)題中的一個(gè)頂點(diǎn)等，都被稱為一個(gè)數(shù)據(jù)元素。有時(shí)，一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)（Data Item）組成，例如，學(xué)籍管理系統(tǒng)中學(xué)生信息表的每一個(gè)數(shù)據(jù)元素就是一個(gè)學(xué)生記錄。它包括學(xué)生的學(xué)號(hào)、姓名、性別、籍貫、出生年月、成績(jī)等數(shù)據(jù)項(xiàng)。這些數(shù)據(jù)項(xiàng)可以分為兩種：一種叫做初等項(xiàng)，如學(xué)生的性別、籍貫等，這些數(shù)據(jù)項(xiàng)是在數(shù)據(jù)處理時(shí)不能再分割的最小單位；另一種叫做組合項(xiàng)，如學(xué)生的成績(jī)，它可以再劃分為數(shù)學(xué)、物理、化學(xué)等更小的項(xiàng)。通常，在解決實(shí)際應(yīng)用問(wèn)題時(shí)是把每個(gè)學(xué)生記錄當(dāng)作一個(gè)基本單位進(jìn)行訪問(wèn)和處理的。如下圖學(xué)生成績(jī)表中所示：數(shù)據(jù)對(duì)象（Data Object）或數(shù)據(jù)元素類（Data Element Class）是

13、具有相同性質(zhì)的數(shù)據(jù)元素的集合。在某個(gè)具體問(wèn)題中，數(shù)據(jù)元素都具有相同的性質(zhì)（元素值不一定相等），屬于同一數(shù)據(jù)對(duì)象（數(shù)據(jù)元素類），數(shù)據(jù)元素是數(shù)據(jù)元素類的一個(gè)實(shí)例。例如，在交通咨詢系統(tǒng)的交通網(wǎng)中，所有的頂點(diǎn)是一個(gè)數(shù)據(jù)元素類，頂點(diǎn)A和頂點(diǎn)B各自代表一個(gè)城市，是該數(shù)據(jù)元素類中的兩個(gè)實(shí)例，其數(shù)據(jù)元素的值分別為A和B。數(shù)據(jù)結(jié)構(gòu)（Data Structure）是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。在任何問(wèn)題中，數(shù)據(jù)元素之間都不會(huì)是孤立的，在它們之間都存在著這樣或那樣的關(guān)系，這種數(shù)據(jù)元素之間的關(guān)系稱為結(jié)構(gòu)。根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通常有下列四類基本的結(jié)構(gòu)：集合結(jié)構(gòu)。在集合結(jié)構(gòu)中，數(shù)據(jù)元素間的關(guān)

14、系是“屬于同一個(gè)集合”。集合是元素關(guān)系極為松散的一種結(jié)構(gòu)。線性結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系。樹(shù)型結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。圖形結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系，圖形結(jié)構(gòu)也稱作網(wǎng)狀結(jié)構(gòu)。圖1.4為表示上述四類基本結(jié)構(gòu)的示意圖。 （a）集合結(jié)構(gòu) （b）線性結(jié)構(gòu) （c）樹(shù)型結(jié)構(gòu) （d）圖形結(jié)構(gòu)圖1. 4 四類基本結(jié)構(gòu)的示意圖由于集合是數(shù)據(jù)元素之間關(guān)系極為松散的一種結(jié)構(gòu)，因此也可用其他結(jié)構(gòu)來(lái)表示它。從上面所介紹的數(shù)據(jù)結(jié)構(gòu)的概念中可以知道，一個(gè)數(shù)據(jù)結(jié)構(gòu)有兩個(gè)要素。一個(gè)是數(shù)據(jù)元素的集合，另一個(gè)是關(guān)系的集合。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)。數(shù)據(jù)的邏

15、輯結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型，它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)。我們研究數(shù)據(jù)結(jié)構(gòu)的目的是為了在計(jì)算機(jī)中實(shí)現(xiàn)對(duì)它的操作，為此還需要研究如何在計(jì)算機(jī)中表示一個(gè)數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的標(biāo)識(shí)（又稱映像）稱為數(shù)據(jù)的物理結(jié)構(gòu)，或稱存儲(chǔ)結(jié)構(gòu)。它所研究的是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)方法，包括數(shù)據(jù)結(jié)構(gòu)中元素的表示及元素間關(guān)系的表示。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可采用順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)的方法。順序存儲(chǔ)方法是把邏輯上相鄰的元素存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元中，由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)是一種最基本的存儲(chǔ)表示方法，通常借助于程序設(shè)計(jì)語(yǔ)言中的數(shù)組來(lái)實(shí)現(xiàn)。鏈?zhǔn)酱鎯?chǔ)方法對(duì)邏輯上相鄰的元素不要求其物理位置相鄰，元

16、素間的邏輯關(guān)系通過(guò)附設(shè)的指針字段來(lái)表示，由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語(yǔ)言中的指針類型來(lái)實(shí)現(xiàn)。除了通常采用的順序存儲(chǔ)方法和鏈?zhǔn)酱鎯?chǔ)方法外，有時(shí)為了查找的方便還采用索引存儲(chǔ)方法和散列存儲(chǔ)方法。數(shù)據(jù)類型（Data Type）是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個(gè)概念，它最早出現(xiàn)在高級(jí)程序語(yǔ)言中，用以刻畫(huà) (程序)操作對(duì)象的特性。在用高級(jí)程序語(yǔ)言編寫(xiě)的程序中，每個(gè)變量、常量或表達(dá)式都有一個(gè)它所屬的確定的數(shù)據(jù)類型。類型明顯或隱含地規(guī)定了在程序執(zhí)行期間變量或表達(dá)式所有可能取值的范圍，以及在這些值上允許進(jìn)行的操作。因此數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。例如，

17、C語(yǔ)言中的整型變量，其值集為某個(gè)區(qū)間上的整數(shù)(區(qū)間大小依賴于不同的機(jī)器)，定義在其上的操作為：加、減、乘、除和取模等算術(shù)運(yùn)算。 數(shù)據(jù)類型的種類：特征例原子類型值在邏輯上不可分解int float結(jié)構(gòu)類型值由若干成分按某種結(jié)構(gòu)組成struct stu數(shù)據(jù)類型封裝了數(shù)據(jù)存儲(chǔ)與操作的具體細(xì)節(jié)。抽象數(shù)據(jù)類型(Abstract Data Type 簡(jiǎn)稱ADT) 是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作，面向邏輯層次。抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無(wú)關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部的使用。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)

18、概念。例如，各個(gè)計(jì)算機(jī)都擁有的“整數(shù)”類型是一個(gè)抽象數(shù)據(jù)類型，盡管它們?cè)诓煌幚砥魃蠈?shí)現(xiàn)的方法可以不同，但由于其定義的數(shù)學(xué)特性相同，在用戶看來(lái)都是相同的。因此，“抽象”的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。另一方面，抽象數(shù)據(jù)類型的范疇更廣，它不再局限于前述各處理器中已定義并實(shí)現(xiàn)的數(shù)據(jù)類型(也可稱這類數(shù)據(jù)類型為固有數(shù)據(jù)類型)，還包括用戶在設(shè)計(jì)軟件系統(tǒng)時(shí)自己定義的數(shù)據(jù)類型。為了提高軟件的復(fù)用率，在近代程序設(shè)計(jì)方法學(xué)中指出，一個(gè)軟件系統(tǒng)的框架應(yīng)建立在數(shù)據(jù)之上，而不是建立在操作之上(后者是傳統(tǒng)的軟件設(shè)計(jì)方法所為)。即在構(gòu)成軟件系統(tǒng)的每個(gè)相對(duì)獨(dú)立的模塊上，定義一組數(shù)據(jù)和施于這些數(shù)據(jù)上的一組操作，并在模塊內(nèi)部給出這些數(shù)據(jù)的表示及其操作的細(xì)節(jié)，而在模塊外部使用的只是抽象的數(shù)據(jù)和抽象的操作。顯然，所定義的數(shù)據(jù)類型的抽象層次越高，含有該抽象數(shù)據(jù)類型的軟件模塊的復(fù)用程度也就越高。 如前所述，抽象數(shù)據(jù)類型的定義由一個(gè)值域和定義在該值域上的一組操作組成。和數(shù)據(jù)結(jié)構(gòu)的形式定義相對(duì)應(yīng)，抽象數(shù)據(jù)類型可用以下三元組示: (D，S，P) (14) 其中，D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。 抽象數(shù)據(jù)類型定義