數(shù)據(jù)結(jié)構(gòu)(第1章)-清華大學(xué)

授課教師：聯(lián)絡(luò)電話：Email:數(shù)據(jù)結(jié)構(gòu)2/5/20231數(shù)據(jù)結(jié)構(gòu)講義

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)及相關(guān)專業(yè)中一門重要的專業(yè)基礎(chǔ)課程。當(dāng)用計(jì)算機(jī)來(lái)解決實(shí)際問(wèn)題時(shí)，就要涉及到數(shù)據(jù)的表示及數(shù)據(jù)的處理，而數(shù)據(jù)表示及數(shù)據(jù)處理正是數(shù)據(jù)結(jié)構(gòu)課程的主要研究對(duì)象，通過(guò)這兩方面內(nèi)容的學(xué)習(xí)，為后續(xù)課程，特別是軟件方面的課程打下了厚實(shí)的知識(shí)基礎(chǔ)，同時(shí)也提供了必要的技能訓(xùn)練。因此，數(shù)據(jù)結(jié)構(gòu)課程在計(jì)算機(jī)應(yīng)用專業(yè)中具有舉足輕重的作用。

本課程的任務(wù)是：在基礎(chǔ)方面，要求學(xué)生掌握常用數(shù)據(jù)結(jié)構(gòu)的基本概念及其不同的實(shí)現(xiàn)方法；在技能方面，通過(guò)系統(tǒng)學(xué)習(xí)能夠在不同存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)不同的運(yùn)算，并對(duì)算法設(shè)計(jì)的方式和技巧有所體會(huì)。

學(xué)業(yè)基礎(chǔ)：本課程的先修課程為離散數(shù)學(xué)和高級(jí)語(yǔ)言程序設(shè)計(jì)。學(xué)習(xí)本課程必須具備高級(jí)語(yǔ)言程序設(shè)計(jì)(比如Pascal語(yǔ)言或C語(yǔ)言)的基礎(chǔ)知識(shí)與基本技能。它的后續(xù)課程有操作系統(tǒng)和數(shù)據(jù)庫(kù)原理等。進(jìn)度安排：總學(xué)時(shí)108，其中課堂講授72學(xué)時(shí)，實(shí)驗(yàn)教學(xué)36學(xué)時(shí)。2/5/20232數(shù)據(jù)結(jié)構(gòu)講義⒈教學(xué)內(nèi)容：1.1數(shù)據(jù)結(jié)構(gòu)的概念；

1.2抽象數(shù)據(jù)類型；

1.3算法和算法分析。⒉教學(xué)目的：⑴領(lǐng)會(huì)數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)的概念及其相互間的關(guān)系；

⑵清楚數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的聯(lián)系與區(qū)別，以及在數(shù)據(jù)結(jié)構(gòu)上施加的運(yùn)算及其實(shí)現(xiàn)；

⑶理解抽象數(shù)據(jù)類型的概念；

⑷掌握進(jìn)行簡(jiǎn)單算法分析的方法。⒊教學(xué)重點(diǎn)：⑴數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)；

⑵邏輯結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)在概念上的聯(lián)系與區(qū)別；

⑶存儲(chǔ)結(jié)構(gòu)及其三個(gè)組成部分；

⑷抽象數(shù)據(jù)類型和數(shù)據(jù)抽象；

⑸評(píng)價(jià)算法優(yōu)劣的標(biāo)準(zhǔn)及方法。⒋教學(xué)難點(diǎn)：⑴區(qū)別算法與程序；

⑵邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的聯(lián)系與區(qū)別；

⑶抽象數(shù)據(jù)類型與數(shù)據(jù)抽象；

⑷算法的時(shí)間復(fù)雜度分析。⒌學(xué)時(shí)安排：

3學(xué)時(shí)第一章緒論2/5/20233數(shù)據(jù)結(jié)構(gòu)講義1.1數(shù)據(jù)結(jié)構(gòu)的概念為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)有關(guān)概念和術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容2/5/20234數(shù)據(jù)結(jié)構(gòu)講義1.1.1為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)在計(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ì)的技巧上，而無(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)題。例1例2例32/5/20235數(shù)據(jù)結(jié)構(gòu)講義例1學(xué)生信息檢索系統(tǒng)當(dāng)我們需要查找某個(gè)學(xué)生的有關(guān)情況的時(shí)候；或者想查詢某個(gè)專業(yè)或年級(jí)的學(xué)生的有關(guān)情況的時(shí)候，只要我們建立了相關(guān)的數(shù)據(jù)結(jié)構(gòu)，按照某種算法編寫了相關(guān)程序，就可以實(shí)現(xiàn)計(jì)算機(jī)自動(dòng)檢索。由此，可以在學(xué)生信息檢索系統(tǒng)中建立一張按學(xué)號(hào)順序排列的學(xué)生信息表和分別按姓名、專業(yè)、年級(jí)順序排列的索引表，由這四張表構(gòu)成的文件便是學(xué)生信息檢索的數(shù)學(xué)模型，計(jì)算機(jī)的主要操作便是按照某個(gè)特定要求（如給定姓名）對(duì)學(xué)生信息文件進(jìn)行查詢。（b）姓名索引表崔文靖8何文穎6李淑芳2劉麗3，9石寶國(guó)5魏永鳴10吳承志1趙勝利7張會(huì)有42000級(jí)6，7，82001級(jí)9，1098級(jí)1，2，399級(jí)4，5計(jì)算機(jī)科學(xué)與技術(shù)1，5，6，9信息與計(jì)算科學(xué)2，4，8數(shù)學(xué)與應(yīng)用數(shù)學(xué)3，7，10記錄號(hào)學(xué)號(hào)姓名性別專業(yè)年級(jí)1980001吳承志男計(jì)算機(jī)科學(xué)與技術(shù)98級(jí)2980002李淑芳女信息與計(jì)算科學(xué)98級(jí)3990301劉麗女?dāng)?shù)學(xué)與應(yīng)用數(shù)學(xué)99級(jí)4990302張會(huì)友男信息與計(jì)算科學(xué)99級(jí)5990303石寶國(guó)男計(jì)算機(jī)科學(xué)與技術(shù)99級(jí)6000801何文穎女計(jì)算機(jī)科學(xué)與技術(shù)2000級(jí)7000802趙勝利男數(shù)學(xué)與應(yīng)用數(shù)學(xué)2000級(jí)8000803崔文靖男信息與計(jì)算科學(xué)2000級(jí)9010601劉麗女計(jì)算機(jī)科學(xué)與技術(shù)2001級(jí)10010602魏永鳴男數(shù)學(xué)與應(yīng)用數(shù)學(xué)2001級(jí)（a）學(xué)生信息表（c）專業(yè)索引表（d）年級(jí)索引表圖1.1學(xué)生信息查詢系統(tǒng)中的數(shù)據(jù)結(jié)構(gòu)2/5/20236數(shù)據(jù)結(jié)構(gòu)講義在八皇后問(wèn)題中，處理過(guò)程不是根據(jù)某種確定的計(jì)算法則，而是利用試探和回溯的探索技術(shù)求解。為了求得合理布局，在計(jì)算機(jī)中要存儲(chǔ)布局的當(dāng)前狀態(tài)。從最初的布局狀態(tài)開(kāi)始，一步步地進(jìn)行試探，每試探一步形成一個(gè)新的狀態(tài)，整個(gè)試探過(guò)程形成了一棵隱含的狀態(tài)樹(shù)。如圖1.2所示（為了描述方便，將八皇后問(wèn)題簡(jiǎn)化為四皇后問(wèn)題）?；厮莘ㄇ蠼膺^(guò)程實(shí)質(zhì)上就是一個(gè)遍歷狀態(tài)樹(shù)的過(guò)程。在這個(gè)問(wèn)題中所出現(xiàn)的樹(shù)也是一種數(shù)據(jù)結(jié)構(gòu)，它可以應(yīng)用在許多非數(shù)值計(jì)算的問(wèn)題中。例2八皇后問(wèn)題2/5/20237數(shù)據(jù)結(jié)構(gòu)講義例3教學(xué)計(jì)劃編排問(wèn)題一個(gè)教學(xué)計(jì)劃包含許多課程，在教學(xué)計(jì)劃包含的許多課程之間，有些必須按規(guī)定的先后次序進(jìn)行，有些則沒(méi)有次序要求。即有些課程之間有先修和后續(xù)的關(guān)系，有些課程可以任意安排次序。這種各個(gè)課程之間的次序關(guān)系可用一個(gè)稱作圖的數(shù)據(jù)結(jié)構(gòu)來(lái)表示，如圖1.3所示。有向圖中的每個(gè)頂點(diǎn)表示一門課程，如果從頂點(diǎn)vi到vj之間存在有向邊<vi，vj>，則表示課程i必須先于課程j進(jìn)行。2/5/20238數(shù)據(jù)結(jié)構(gòu)講義由以上三個(gè)例子可見(jiàn)，描述這類非數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹(shù)、圖之類的數(shù)據(jù)結(jié)構(gòu)。因此，可以說(shuō)數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中所出現(xià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ì)的提高。2/5/20239數(shù)據(jù)結(jié)構(gòu)講義1.1.2有關(guān)概念和術(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ù)元素（DataElement）是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。例如，學(xué)生信息檢索系統(tǒng)中學(xué)生信息表中的一個(gè)記錄、八皇后問(wèn)題中狀態(tài)樹(shù)的一個(gè)狀態(tài)、教學(xué)計(jì)劃編排問(wèn)題中的一個(gè)頂點(diǎn)等，都被稱為一個(gè)數(shù)據(jù)元素。有時(shí)，一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)（DataItem）組成，例如，學(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)和處理的。2/5/202310數(shù)據(jù)結(jié)構(gòu)講義數(shù)據(jù)對(duì)象（DataObject）或數(shù)據(jù)元素類（DataElementClass）是具有相同性質(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)（DataStructure）是指互相之間存在著一種或多種關(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ù)型結(jié)構(gòu)。⑷圖形結(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)的示意圖2/5/202311數(shù)據(jù)結(jié)構(gòu)講義一個(gè)數(shù)據(jù)結(jié)構(gòu)有兩個(gè)要素。一個(gè)是數(shù)據(jù)元素的集合，另一個(gè)是關(guān)系的集合。在形式上，數(shù)據(jù)結(jié)構(gòu)通?？梢圆捎靡粋€(gè)二元組來(lái)表示。

數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組

Data_Structure＝（D，R）其中，D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)。數(shù)據(jù)的邏輯結(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)系的表示。2/5/202312數(shù)據(jù)結(jié)構(gòu)講義1.1.3數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件之間的一門計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的核心課程，是高級(jí)程序設(shè)計(jì)語(yǔ)言、編譯原理、操作系統(tǒng)、數(shù)據(jù)庫(kù)、人工智能等課程的基礎(chǔ)。同時(shí)，數(shù)據(jù)結(jié)構(gòu)技術(shù)也廣泛應(yīng)用于信息科學(xué)、系統(tǒng)工程、應(yīng)用數(shù)學(xué)以及各種工程技術(shù)領(lǐng)域。數(shù)據(jù)結(jié)構(gòu)課程集中討論軟件開(kāi)發(fā)過(guò)程中的設(shè)計(jì)階段、同時(shí)涉及編碼和分析階段的若干基本問(wèn)題。此外，為了構(gòu)造出好的數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)，還需考慮數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)的評(píng)價(jià)與選擇。因此，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容包括三個(gè)層次的五個(gè)“要素”，如圖1.5所示。2/5/202313數(shù)據(jù)結(jié)構(gòu)講義數(shù)據(jù)結(jié)構(gòu)作為一門獨(dú)立的課程在國(guó)外是從1968年才開(kāi)始的，但在此之前其有關(guān)內(nèi)容已散見(jiàn)于編譯原理及操作系統(tǒng)之中。20世紀(jì)60年代中期，美國(guó)的一些大學(xué)開(kāi)始設(shè)立有關(guān)課程，但當(dāng)時(shí)的課程名稱并不叫數(shù)據(jù)結(jié)構(gòu)。1968年美國(guó)唐.歐.克努特教授開(kāi)創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其操作的著作。從20世紀(jì)60年代末到70年代初，出現(xiàn)了大型程序，軟件也相對(duì)獨(dú)立，結(jié)構(gòu)程序設(shè)計(jì)成為程序設(shè)計(jì)方法學(xué)的主要內(nèi)容，人們?cè)絹?lái)越重視數(shù)據(jù)結(jié)構(gòu)。從70年代中期到80年代，各種版本的數(shù)據(jù)結(jié)構(gòu)著作相繼出現(xiàn)。目前，數(shù)據(jù)結(jié)構(gòu)的發(fā)展并未終結(jié)，一方面，面向各專門領(lǐng)域中特殊問(wèn)題的數(shù)據(jù)結(jié)構(gòu)得到研究和發(fā)展，如多維圖形數(shù)據(jù)結(jié)構(gòu)等；另一方面，從抽象數(shù)據(jù)類型和面向?qū)ο蟮挠^點(diǎn)來(lái)討論數(shù)據(jù)結(jié)構(gòu)已成為一種新的趨勢(shì)，越來(lái)越被人們所重視。2/5/202314數(shù)據(jù)結(jié)構(gòu)講義1.2抽象數(shù)據(jù)類型數(shù)據(jù)類型抽象數(shù)據(jù)類型2/5/202315數(shù)據(jù)結(jié)構(gòu)講義1.2.1數(shù)據(jù)類型數(shù)據(jù)類型是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個(gè)概念。它最早出現(xiàn)在高級(jí)程序設(shè)計(jì)語(yǔ)言中，用以刻劃程序中操作對(duì)象的特性。在用高級(jí)語(yǔ)言編寫的程序中，每個(gè)變量、常量或表達(dá)式都有一個(gè)它所屬的確定的數(shù)據(jù)類型。類型顯式地或隱含地規(guī)定了在程序執(zhí)行期間變量或表達(dá)式所有可能的取值范圍，以及在這些值上允許進(jìn)行的操作。因此，數(shù)據(jù)類型（DataType）是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。在高級(jí)程序設(shè)計(jì)語(yǔ)言中，數(shù)據(jù)類型可分為兩類：一類是原子類型，另一類則是結(jié)構(gòu)類型。原子類型的值是不可分解的。如C語(yǔ)言中整型、字符型、浮點(diǎn)型、雙精度型等基本類型，分別用保留字int、char、float、double標(biāo)識(shí)。而結(jié)構(gòu)類型的值是由若干成分按某種結(jié)構(gòu)組成的，因此是可分解的，并且它的成分可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的。例如，數(shù)組的值由若干分量組成，每個(gè)分量可以是整數(shù)，也可以是數(shù)組等。在某種意義上，數(shù)據(jù)結(jié)構(gòu)可以看成是“一組具有相同結(jié)構(gòu)的值”，而數(shù)據(jù)類型則可被看成是由一種數(shù)據(jù)結(jié)構(gòu)和定義在其上的一組操作所組成的。2/5/202316數(shù)據(jù)結(jié)構(gòu)講義抽象數(shù)據(jù)類型（AbstructDataType，簡(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é)特性不變，都不影響其外部的使用。1.2.2抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型和數(shù)據(jù)類型實(shí)質(zhì)上是一個(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ì)軟件系統(tǒng)時(shí)自己定義的數(shù)據(jù)類型。為了提高軟件的重用性，在近代程序設(shè)計(jì)方法學(xué)中，要求在構(gòu)成軟件系統(tǒng)的每個(gè)相對(duì)獨(dú)立的模塊上，定義一組數(shù)據(jù)和施于這些數(shù)據(jù)上的一組操作，并在模塊的內(nèi)部給出這些數(shù)據(jù)的表示及其操作的細(xì)節(jié)，而在模塊的外部使用的只是抽象的數(shù)據(jù)及抽象的操作。這也就是面向?qū)ο蟮某绦蛟O(shè)計(jì)方法。抽象數(shù)據(jù)類型的定義可以由一種數(shù)據(jù)結(jié)構(gòu)和定義在其上的一組操作組成，而數(shù)據(jù)結(jié)構(gòu)又包括數(shù)據(jù)元素及元素間的關(guān)系，因此抽象數(shù)據(jù)類型一般可以由元素、關(guān)系及操作三種要素來(lái)定義。抽象數(shù)據(jù)類型的特征是使用與實(shí)現(xiàn)相分離，實(shí)行封裝和信息隱蔽。就是說(shuō)，在抽象數(shù)據(jù)類型設(shè)計(jì)時(shí)，把類型的定義與其實(shí)現(xiàn)分離開(kāi)來(lái)。2/5/202317數(shù)據(jù)結(jié)構(gòu)講義1.3算法和算法分析算法特性算法描述算法性能分析與度量2/5/202318數(shù)據(jù)結(jié)構(gòu)講義1.3.1算法特性算法（Algorithm）是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個(gè)或多個(gè)操作。一個(gè)算法應(yīng)該具有下列特性：⑴有窮性。一個(gè)算法必須在有窮步之后結(jié)束，即必須在有限時(shí)間內(nèi)完成。⑵確定性。算法的每一步必須有確切的定義，無(wú)二義性。算法的執(zhí)行對(duì)應(yīng)著的相同的輸入僅有唯一的一條路經(jīng)。⑶可行性。算法中的每一步都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算的有限次執(zhí)行得以實(shí)現(xiàn)。⑷輸入。一個(gè)算法具有零個(gè)或多個(gè)輸入，這些輸入取自特定的數(shù)據(jù)對(duì)象集合。⑸輸出。一個(gè)算法具有一個(gè)或多個(gè)輸出，這些輸出同輸入之間存在某種特定的關(guān)系。算法與數(shù)據(jù)結(jié)構(gòu)是相輔相承的。解決某一特定類型問(wèn)題的算法可以選定不同的數(shù)據(jù)結(jié)構(gòu)，而且選擇恰當(dāng)與否直接影響算法的效率。反之，一種數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣由各種算法的執(zhí)行來(lái)體現(xiàn)。要設(shè)計(jì)一個(gè)好的算法通常要考慮以下的要求。⑴正確。算法的執(zhí)行結(jié)果應(yīng)當(dāng)滿足預(yù)先規(guī)定的功能和性能要求。⑵可讀。一個(gè)算法應(yīng)當(dāng)思路清晰、層次分明、簡(jiǎn)單明了、易讀易懂。⑶健壯。當(dāng)輸入不合法數(shù)據(jù)時(shí)，應(yīng)能作適當(dāng)處理，不至引起嚴(yán)重后果。⑷高效。有效使用存儲(chǔ)空間和有較高的時(shí)間效率。2/5/202319數(shù)據(jù)結(jié)構(gòu)講義1.3.2算法描述算法可以使用各種不同的方法來(lái)描述。最簡(jiǎn)單的方法是使用自然語(yǔ)言。用自然語(yǔ)言來(lái)描述算法的優(yōu)點(diǎn)是簡(jiǎn)單且便于人們對(duì)算法的閱讀。缺點(diǎn)是不夠嚴(yán)謹(jǐn)?？梢允褂贸绦蛄鞒虉D、N-S圖等算法描述工具。其特點(diǎn)是描述過(guò)程簡(jiǎn)潔、明了。用以上兩種方法描述的算法不能夠直接在計(jì)算機(jī)上執(zhí)行，若要將它轉(zhuǎn)換成可執(zhí)行的程序還有一個(gè)編程的問(wèn)題?？梢灾苯邮褂媚撤N程序設(shè)計(jì)語(yǔ)言來(lái)描述算法，不過(guò)直接使用程序設(shè)計(jì)語(yǔ)言并不容易，而且不太直觀，常常需要借助于注釋才能使人看明白。為了解決理解與執(zhí)行這兩者之間的矛盾，人們常常使用一種稱為偽碼語(yǔ)言的描述方法來(lái)進(jìn)行算法描述。偽碼語(yǔ)言介于高級(jí)程序設(shè)計(jì)語(yǔ)言和自然語(yǔ)言之間，它忽略高級(jí)程序設(shè)計(jì)語(yǔ)言中一些嚴(yán)格的語(yǔ)法規(guī)則與描述細(xì)節(jié)，因此它比程序設(shè)計(jì)語(yǔ)言更容易描述和被人理解，而比自然語(yǔ)言更接近程序設(shè)計(jì)語(yǔ)言。它雖然不能直接執(zhí)行但很容易被轉(zhuǎn)換成高級(jí)語(yǔ)言。2/5/202320數(shù)據(jù)結(jié)構(gòu)講義1.3.3算法性能分析與度量將一個(gè)算法轉(zhuǎn)換成程序并在計(jì)算機(jī)上執(zhí)行時(shí)，其運(yùn)行所需要的時(shí)間取決于下