數(shù)據(jù)結(jié)構(gòu)與算法：第一章 學(xué)習(xí)指導(dǎo)材料

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