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

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

學(xué)業(yè)基礎(chǔ)：本課程的先修課程為離散數(shù)學(xué)和高級語言程序設(shè)計。學(xué)習(xí)本課程必須具備高級語言程序設(shè)計(比如Pascal語言或C語言)的基礎(chǔ)知識與基本技能。它的后續(xù)課程有操作系統(tǒng)和數(shù)據(jù)庫原理等。進度安排：總學(xué)時108，其中課堂講授72學(xué)時，實驗教學(xué)36學(xué)時。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)會數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項的概念及其相互間的關(guān)系；

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

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

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

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

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

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

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

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

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

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

3學(xué)時第一章緒論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ù)語數(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)在計算機發(fā)展的初期，人們使用計算機的目的主要是處理數(shù)值計算問題。當(dāng)我們使用計算機來解決一個具體問題時，一般需要經(jīng)過下列幾個步驟：首先要從該具體問題抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計或選擇一個解此數(shù)學(xué)模型的算法，最后編出程序進行調(diào)試、測試，直至得到最終的解答。例如，求解梁架結(jié)構(gòu)中應(yīng)力的數(shù)學(xué)模型的線性方程組，該方程組可以使用迭代算法來求解。由于當(dāng)時所涉及的運算對象是簡單的整型、實型或布爾類型數(shù)據(jù)，所以程序設(shè)計者的主要精力是集中于程序設(shè)計的技巧上，而無須重視數(shù)據(jù)結(jié)構(gòu)。隨著計算機應(yīng)用領(lǐng)域的擴大和軟、硬件的發(fā)展，非數(shù)值計算問題越來越顯得重要。據(jù)統(tǒng)計，當(dāng)今處理非數(shù)值計算性問題占用了90%以上的機器時間。這類問題涉及到的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜，數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程式加以描述。因此，解決這類問題的關(guān)鍵不再是數(shù)學(xué)分析和計算方法，而是要設(shè)計出合適的數(shù)據(jù)結(jié)構(gòu)，才能有效地解決問題。例1例2例32/5/20235數(shù)據(jù)結(jié)構(gòu)講義例1學(xué)生信息檢索系統(tǒng)當(dāng)我們需要查找某個學(xué)生的有關(guān)情況的時候；或者想查詢某個專業(yè)或年級的學(xué)生的有關(guān)情況的時候，只要我們建立了相關(guān)的數(shù)據(jù)結(jié)構(gòu)，按照某種算法編寫了相關(guān)程序，就可以實現(xiàn)計算機自動檢索。由此，可以在學(xué)生信息檢索系統(tǒng)中建立一張按學(xué)號順序排列的學(xué)生信息表和分別按姓名、專業(yè)、年級順序排列的索引表，由這四張表構(gòu)成的文件便是學(xué)生信息檢索的數(shù)學(xué)模型，計算機的主要操作便是按照某個特定要求（如給定姓名）對學(xué)生信息文件進行查詢。（b）姓名索引表崔文靖8何文穎6李淑芳2劉麗3，9石寶國5魏永鳴10吳承志1趙勝利7張會有42000級6，7，82001級9，1098級1，2，399級4，5計算機科學(xué)與技術(shù)1，5，6，9信息與計算科學(xué)2，4，8數(shù)學(xué)與應(yīng)用數(shù)學(xué)3，7，10記錄號學(xué)號姓名性別專業(yè)年級1980001吳承志男計算機科學(xué)與技術(shù)98級2980002李淑芳女信息與計算科學(xué)98級3990301劉麗女?dāng)?shù)學(xué)與應(yīng)用數(shù)學(xué)99級4990302張會友男信息與計算科學(xué)99級5990303石寶國男計算機科學(xué)與技術(shù)99級6000801何文穎女計算機科學(xué)與技術(shù)2000級7000802趙勝利男數(shù)學(xué)與應(yīng)用數(shù)學(xué)2000級8000803崔文靖男信息與計算科學(xué)2000級9010601劉麗女計算機科學(xué)與技術(shù)2001級10010602魏永鳴男數(shù)學(xué)與應(yīng)用數(shù)學(xué)2001級（a）學(xué)生信息表（c）專業(yè)索引表（d）年級索引表圖1.1學(xué)生信息查詢系統(tǒng)中的數(shù)據(jù)結(jié)構(gòu)2/5/20236數(shù)據(jù)結(jié)構(gòu)講義在八皇后問題中，處理過程不是根據(jù)某種確定的計算法則，而是利用試探和回溯的探索技術(shù)求解。為了求得合理布局，在計算機中要存儲布局的當(dāng)前狀態(tài)。從最初的布局狀態(tài)開始，一步步地進行試探，每試探一步形成一個新的狀態(tài)，整個試探過程形成了一棵隱含的狀態(tài)樹。如圖1.2所示（為了描述方便，將八皇后問題簡化為四皇后問題）。回溯法求解過程實質(zhì)上就是一個遍歷狀態(tài)樹的過程。在這個問題中所出現(xiàn)的樹也是一種數(shù)據(jù)結(jié)構(gòu)，它可以應(yīng)用在許多非數(shù)值計算的問題中。例2八皇后問題2/5/20237數(shù)據(jù)結(jié)構(gòu)講義例3教學(xué)計劃編排問題一個教學(xué)計劃包含許多課程，在教學(xué)計劃包含的許多課程之間，有些必須按規(guī)定的先后次序進行，有些則沒有次序要求。即有些課程之間有先修和后續(xù)的關(guān)系，有些課程可以任意安排次序。這種各個課程之間的次序關(guān)系可用一個稱作圖的數(shù)據(jù)結(jié)構(gòu)來表示，如圖1.3所示。有向圖中的每個頂點表示一門課程，如果從頂點vi到vj之間存在有向邊<vi，vj>，則表示課程i必須先于課程j進行。2/5/20238數(shù)據(jù)結(jié)構(gòu)講義由以上三個例子可見，描述這類非數(shù)值計算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)。因此，可以說數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的計算機操作對象以及它們之間的關(guān)系和操作的學(xué)科。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的目的是為了了解計算機處理對象的特性，將實際問題中所涉及的處理對象在計算機中表示出來并對它們進行處理。與此同時，通過算法訓(xùn)練來提高學(xué)生的思維能力，通過程序設(shè)計的技能訓(xùn)練來促進學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。2/5/20239數(shù)據(jù)結(jié)構(gòu)講義1.1.2有關(guān)概念和術(shù)語數(shù)據(jù)（Data）是信息的載體，它能夠被計算機識別、存儲和加工處理。它是計算機程序加工的原料，應(yīng)用程序處理各種各樣的數(shù)據(jù)。計算機科學(xué)中，所謂數(shù)據(jù)就是計算機加工處理的對象，它可以是數(shù)值數(shù)據(jù)，也可以是非數(shù)值數(shù)據(jù)。數(shù)值數(shù)據(jù)是一些整數(shù)、實數(shù)或復(fù)數(shù)，主要用于工程計算、科學(xué)計算和商務(wù)處理等；非數(shù)值數(shù)據(jù)包括字符、文字、圖形、圖像、語音等。數(shù)據(jù)元素（DataElement）是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點、頂點、記錄等。例如，學(xué)生信息檢索系統(tǒng)中學(xué)生信息表中的一個記錄、八皇后問題中狀態(tài)樹的一個狀態(tài)、教學(xué)計劃編排問題中的一個頂點等，都被稱為一個數(shù)據(jù)元素。有時，一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項（DataItem）組成，例如，學(xué)籍管理系統(tǒng)中學(xué)生信息表的每一個數(shù)據(jù)元素就是一個學(xué)生記錄。它包括學(xué)生的學(xué)號、姓名、性別、籍貫、出生年月、成績等數(shù)據(jù)項。這些數(shù)據(jù)項可以分為兩種：一種叫做初等項，如學(xué)生的性別、籍貫等，這些數(shù)據(jù)項是在數(shù)據(jù)處理時不能再分割的最小單位；另一種叫做組合項，如學(xué)生的成績，它可以再劃分為數(shù)學(xué)、物理、化學(xué)等更小的項。通常，在解決實際應(yīng)用問題時是把每個學(xué)生記錄當(dāng)作一個基本單位進行訪問和處理的。2/5/202310數(shù)據(jù)結(jié)構(gòu)講義數(shù)據(jù)對象（DataObject）或數(shù)據(jù)元素類（DataElementClass）是具有相同性質(zhì)的數(shù)據(jù)元素的集合。在某個具體問題中，數(shù)據(jù)元素都具有相同的性質(zhì)（元素值不一定相等），屬于同一數(shù)據(jù)對象（數(shù)據(jù)元素類），數(shù)據(jù)元素是數(shù)據(jù)元素類的一個實例。例如，在交通咨詢系統(tǒng)的交通網(wǎng)中，所有的頂點是一個數(shù)據(jù)元素類，頂點A和頂點B各自代表一個城市，是該數(shù)據(jù)元素類中的兩個實例，其數(shù)據(jù)元素的值分別為A和B。數(shù)據(jù)結(jié)構(gòu)（DataStructure）是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。在任何問題中，數(shù)據(jù)元素之間都不會是孤立的，在它們之間都存在著這樣或那樣的關(guān)系，這種數(shù)據(jù)元素之間的關(guān)系稱為結(jié)構(gòu)。根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通常有下列四類基本的結(jié)構(gòu)：⑴集合結(jié)構(gòu)。⑵線性結(jié)構(gòu)。⑶樹型結(jié)構(gòu)。⑷圖形結(jié)構(gòu)。圖1.4為表示上述四類基本結(jié)構(gòu)的示意圖。（a）集合結(jié)構(gòu)（b）線性結(jié)構(gòu)（c）樹型結(jié)構(gòu)（d）圖形結(jié)構(gòu)圖1.4四類基本結(jié)構(gòu)的示意圖2/5/202311數(shù)據(jù)結(jié)構(gòu)講義一個數(shù)據(jù)結(jié)構(gòu)有兩個要素。一個是數(shù)據(jù)元素的集合，另一個是關(guān)系的集合。在形式上，數(shù)據(jù)結(jié)構(gòu)通?？梢圆捎靡粋€二元組來表示。

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

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