數(shù)據(jù)結構與算法：第一章 學習指導材料

第一章緒論第一部分知識點及例題1.1數(shù)據(jù)結構的概念數(shù)據(jù)結構是計算機科學與技術專業(yè)的專業(yè)基礎課，是十分重要的核心課程。所有的計算機系統(tǒng)軟件和應用軟件都要用到各種類型的數(shù)據(jù)結構。1.1.1數(shù)據(jù)（Data）是信息的載體，它能夠被計算機識別、存儲和加工處理。它是計算機程序加工的原料，應用程序處理各種各樣的數(shù)據(jù)。計算機科學中，所謂數(shù)據(jù)就是計算機加工處理的對象，它可以是數(shù)值數(shù)據(jù)，也可以是非數(shù)值數(shù)據(jù)。數(shù)據(jù)元素（DataElement）是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結點、頂點、記錄等。有時，一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項（DataItem）組成，例如，學籍管理系統(tǒng)中學生信息表的每一個數(shù)據(jù)元素就是一個學生記錄。它包括學生的學號、姓名、性別、籍貫、出生年月、成績等數(shù)據(jù)項數(shù)據(jù)結構（DataStructure）是指互相之間存在著一種或多種關系的數(shù)據(jù)元素的集合。在任何問題中，數(shù)據(jù)元素之間都不會是孤立的，在它們之間都存在著這樣或那樣的關系，這種數(shù)據(jù)元素之間的關系稱為結構。根據(jù)數(shù)據(jù)元素間關系的不同特性，通常有下列四類基本的結構：⑴集合結構。在集合結構中，數(shù)據(jù)元素間的關系是“屬于同一個集合”。⑵線性結構。該結構的數(shù)據(jù)元素之間存在著一對一的關系。⑶樹型結構。該結構的數(shù)據(jù)元素之間存在著一對多的關系。⑷圖形結構。該結構的數(shù)據(jù)元素之間存在著多對多的關系，圖形結構也稱作網(wǎng)狀結構。圖1.4為表示上述四類基本結構的示意圖。（a）集合結構（b）線性結構（c）樹型結構（d）圖形結構圖1.4四類基本結構的示意圖從上面所介紹的數(shù)據(jù)結構的概念中可以知道，一個數(shù)據(jù)結構有兩個要素。一個是數(shù)據(jù)元素的集合，另一個是關系的集合。在形式上，數(shù)據(jù)結構通?？梢圆捎靡粋€二元組來表示。數(shù)據(jù)結構的形式定義為：數(shù)據(jù)結構是一個二元組Data_Structure＝（D，R）其中，D是數(shù)據(jù)元素的有限集，R是D上關系的有限集。數(shù)據(jù)結構包括數(shù)據(jù)的邏輯結構和數(shù)據(jù)的物理結構。數(shù)據(jù)的邏輯結構可以看作是從具體問題抽象出來的數(shù)學模型，它與數(shù)據(jù)的存儲無關。我們研究數(shù)據(jù)結構的目的是為了在計算機中實現(xiàn)對它的操作，為此還需要研究如何在計算機中表示一個數(shù)據(jù)結構。數(shù)據(jù)結構在計算機中的標識（又稱映像）稱為數(shù)據(jù)的物理結構，或稱存儲結構。它所研究的是數(shù)據(jù)結構在計算機中的實現(xiàn)方法，包括數(shù)據(jù)結構中元素的表示及元素間關系的表示。數(shù)據(jù)的存儲結構可采用順序存儲或鏈式存儲的方法。順序存儲方法是把邏輯上相鄰的元素存儲在物理位置相鄰的存儲單元中，由此得到的存儲表示稱為順序存儲結構。順序存儲結構是一種最基本的存儲表示方法，通常借助于程序設計語言中的數(shù)組來實現(xiàn)。鏈式存儲方法對邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關系通過附設的指針字段來表示，由此得到的存儲表示稱為鏈式存儲結構，鏈式存儲結構通常借助于程序設計語言中的指針類型來實現(xiàn)。除了通常采用的順序存儲方法和鏈式存儲方法外，有時為了查找的方便還采用索引存儲方法和散列存儲方法。1.1.2數(shù)據(jù)結構課程的內容數(shù)據(jù)結構與數(shù)學、計算機硬件和軟件有十分密切的關系。數(shù)據(jù)結構是介于數(shù)學、計算機硬件和計算機軟件之間的一門計算機科學與技術專業(yè)的核心課程，是高級程序設計語言、編譯原理、操作系統(tǒng)、數(shù)據(jù)庫、人工智能等課程的基礎。同時，數(shù)據(jù)結構技術也廣泛應用于信息科學、系統(tǒng)工程、應用數(shù)學以及各種工程技術領域。1.2抽象數(shù)據(jù)類型1.2.1數(shù)據(jù)類型數(shù)據(jù)類型是和數(shù)據(jù)結構密切相關的一個概念。它最早出現(xiàn)在高級程序設計語言中，用以刻劃程序中操作對象的特性。在用高級語言編寫的程序中，每個變量、常量或表達式都有一個它所屬的確定的數(shù)據(jù)類型。類型顯式地或隱含地規(guī)定了在程序執(zhí)行期間變量或表達式所有可能的取值范圍，以及在這些值上允許進行的操作。因此，數(shù)據(jù)類型（DataType）是一個值的集合和定義在這個值集上的一組操作的總稱。在高級程序設計語言中，數(shù)據(jù)類型可分為兩類：一類是原子類型，另一類則是結構類型。原子類型的值是不可分解的。如C語言中整型、字符型、浮點型、雙精度型等基本類型，分別用保留字int、char、float、double標識。而結構類型的值是由若干成分按某種結構組成的，因此是可分解的，并且它的成分可以是非結構的，也可以是結構的。例如，數(shù)組的值由若干分量組成，每個分量可以是整數(shù)，也可以是數(shù)組等。在某種意義上，數(shù)據(jù)結構可以看成是“一組具有相同結構的值”，而數(shù)據(jù)類型則可被看成是由一種數(shù)據(jù)結構和定義在其上的一組操作所組成的。1.2.2抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型（AbstructDataType，簡稱ADT）是指一個數(shù)學模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義取決于它的一組邏輯特性，而與其在計算機內部如何表示和實現(xiàn)無關。即不論其內部結構如何變化，只要它的數(shù)學特性不變，都不影響其外部的使用。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實質上是一個概念。例如，各種計算機都擁有的整數(shù)類型就是一個抽象數(shù)據(jù)類型，盡管它們在不同處理器上的實現(xiàn)方法可以不同，但由于其定義的數(shù)學特性相同，在用戶看來都是相同的。因此，“抽象”的意義在于數(shù)據(jù)類型的數(shù)學抽象特性。抽象數(shù)據(jù)類型的定義可以由一種數(shù)據(jù)結構和定義在其上的一組操作組成，而數(shù)據(jù)結構又包括數(shù)據(jù)元素及元素間的關系，因此抽象數(shù)據(jù)類型一般可以由元素、關系及操作三種要素來定義。抽象數(shù)據(jù)類型的特征是使用與實現(xiàn)相分離，實行封裝和信息隱蔽。就是說，在抽象數(shù)據(jù)類型設計時，把類型的定義與其實現(xiàn)分離開來。1.3算法和算法分析1.3.1算法特性算法（Algorithm）是對特定問題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個或多個操作。一個算法應該具有下列特性：⑴有窮性。一個算法必須在有窮步之后結束，即必須在有限時間內完成。⑵確定性。算法的每一步必須有確切的定義，無二義性。算法的執(zhí)行對應著的相同的輸入僅有唯一的一條路經(jīng)。⑶可行性。算法中的每一步都可以通過已經(jīng)實現(xiàn)的基本運算的有限次執(zhí)行得以實現(xiàn)。⑷輸入。一個算法具有零個或多個輸入，這些輸入取自特定的數(shù)據(jù)對象集合。⑸輸出。一個算法具有一個或多個輸出，這些輸出同輸入之間存在某種特定的關系。算法的含義與程序十分相似，但又有區(qū)別。一個程序不一定滿足有窮性。例如，操作系統(tǒng)，只要整個系統(tǒng)不遭破壞，它將永遠不會停止，即使沒有作業(yè)需要處理，它仍處于動態(tài)等待中。因此，操作系統(tǒng)不是一個算法。另一方面，程序中的指令必須是機器可執(zhí)行的，而算法中的指令則無此限制。算法代表了對問題的解，而程序則是算法在計算機上的特定的實現(xiàn)。一個算法若用程序設計語言來描述，則它就是一個程序。算法與數(shù)據(jù)結構是相輔相承的。解決某一特定類型問題的算法可以選定不同的數(shù)據(jù)結構，而且選擇恰當與否直接影響算法的效率。反之，一種數(shù)據(jù)結構的優(yōu)劣由各種算法的執(zhí)行來體現(xiàn)。要設計一個好的算法通常要考慮以下的要求。⑴正確。算法的執(zhí)行結果應當滿足預先規(guī)定的功能和性能要求。⑵可讀。一個算法應當思路清晰、層次分明、簡單明了、易讀易懂。⑶健壯。當輸入不合法數(shù)據(jù)時，應能作適當處理，不至引起嚴重后果。⑷高效。有效使用存儲空間和有較高的時間效率。1.3.2我們可以從一個算法的時間復雜度與空間復雜度來評價算法的優(yōu)劣。⒈時間復雜度一個程序的時間復雜度（Timecomplexity）是指程序運行從開始到結束所需要的時間。一個算法是由控制結構和原操作構成的，其執(zhí)行時間取決于兩者的綜合效果。為了便于比較同一問題的不同的算法，通常的做法是：從算法中選取一種對于所研究的問題來說是基本運算的原操作，以該原操作重復執(zhí)行的次數(shù)作為算法的時間度量。一般情況下，算法中原操作重復執(zhí)行的次數(shù)是規(guī)模n的某個函數(shù)T(n)。許多時候要精確地計算T(n)是困難的，我們引入漸進時間復雜度在數(shù)量上估計一個算法的執(zhí)行時間，也能夠達到分析算法的目的。定義（大Ο記號）：如果存在兩個正常數(shù)c和n0，使得對所有的n，n≥n0，有：f(n)≤cg(n)則有：f(n)＝Ο(g(n))例如，一個程序的實際執(zhí)行時間為T(n)＝2.7n3+3.8n2+5.3。則T(n)＝Ο(n3)。使用大Ο記號表示的算法的時間復雜度，稱為算法的漸進時間復雜度（AsymptoticComplexity）。通常用Ο(1)表示常數(shù)計算時間。常見的漸進時間復雜度有：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n)⒉空間復雜度一個程序的空間復雜度（Spacecomplexity）是指程序運行從開始到結束所需的存儲量。程序的一次運行是針對所求解的問題的某一特定實例而言的。例如，求解排序問題的排