數(shù)據(jù)結(jié)構(gòu) 課件 第1章 緒論

第1章緒論總體要求：理解什么是數(shù)據(jù)、數(shù)據(jù)對象、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)理解數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)和邏輯結(jié)構(gòu)與物理結(jié)構(gòu)間的關(guān)系理解什么是數(shù)據(jù)類型、抽象數(shù)據(jù)類型理解算法的定義、算法的特性、算法的時間代價和算法的空間代價熟悉用C語言描述算法的方法，能夠使用C語言編寫程序核心技能點：具有抽象數(shù)據(jù)的能力具有C語言編程的能力具有算法的時間代價和算法的空間代價靜態(tài)分析能力1第1章緒論2擴(kuò)展技能點：抽象數(shù)據(jù)類型的應(yīng)用能力算法的時間代價和算法的空間代價方法應(yīng)用實際的能力相關(guān)知識點：C語言的基本語句C語言函數(shù)的編寫格式及功能C語言標(biāo)識符的命名規(guī)則C語言類型定義數(shù)學(xué)極限的知識第1章緒論3學(xué)習(xí)重點：熟練掌握算法的定義、算法的特性、算法的時間代價和算法的空間代價分析掌握數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)和邏輯結(jié)構(gòu)與物理結(jié)構(gòu)間的關(guān)系熟悉用C語言描述算法的方法第1章緒論41.1數(shù)據(jù)結(jié)構(gòu)的概念及分類1.1.1數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)(Data)是信息的載體，是描述客觀事物的數(shù)、字符，以及所有能輸入到計算機(jī)中并被計算機(jī)程序識別和處理的符號的集合。數(shù)據(jù)大致可分為兩類：一類是數(shù)值性數(shù)據(jù)，包括整數(shù)、浮點數(shù)、復(fù)數(shù)、雙精度數(shù)等，主要用于工程和科學(xué)計算，以及商業(yè)事務(wù)處理；另一類是非數(shù)值數(shù)據(jù)，主要包括字符和字符串，以及文字、圖形、圖像、語音等的數(shù)據(jù)。從傳統(tǒng)的觀點來看，在解決應(yīng)用問題時，總把數(shù)據(jù)按其性質(zhì)歸類到一些稱之為數(shù)據(jù)對象(DataObject)的集合中。在數(shù)據(jù)對象中所有數(shù)據(jù)成員，即數(shù)據(jù)元素，都具有相同的性質(zhì)，它們是數(shù)據(jù)的子集。例如，整數(shù)數(shù)據(jù)對象可以是集合N={0,1,2,3,…}。英文字母數(shù)據(jù)對象可以是集合LETTER={A,B,…,Z}。第1章緒論5

綜合考慮數(shù)據(jù)對象及其所有數(shù)據(jù)成員之間的關(guān)系，就可得到數(shù)據(jù)結(jié)構(gòu)的定義：據(jù)結(jié)構(gòu)由某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)成員之間的關(guān)系組成。記為：

Data

Structure={D，R}

其中，D是某一數(shù)據(jù)對象，R是該對象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。第1章緒論61.1.2數(shù)據(jù)結(jié)構(gòu)的分類依據(jù)數(shù)據(jù)成員之間關(guān)系的不同，數(shù)據(jù)結(jié)構(gòu)分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)也稱為線性表，在這種結(jié)構(gòu)中所有數(shù)據(jù)成員(也稱為數(shù)據(jù)元素)都按某種次序排列在一個序列中，如圖1.2所示。對于線性結(jié)構(gòu)中每一數(shù)據(jù)元素，除第一個元素外，其它每一個元素都有一個且僅有一個直接前驅(qū)，第一個數(shù)據(jù)元素沒有直接前驅(qū)；除最后一個元素外，其他每一個元素都有一個且僅有一個直接后繼。第1章緒論7圖1.2線性結(jié)構(gòu)中各數(shù)據(jù)成員之間的線性關(guān)系第1章緒論8

在非線性結(jié)構(gòu)中各個數(shù)據(jù)成員不再保持在一個線性序列中，每個數(shù)據(jù)成員可能與零個或多個其他數(shù)據(jù)成員發(fā)生聯(lián)系。根據(jù)關(guān)系的不同，可分為層次結(jié)構(gòu)和群結(jié)構(gòu)。層次結(jié)構(gòu)是按層次劃分的數(shù)據(jù)元素的集合，指定層次上的元素，可以有零個或多個處于下一個層次上的、直接的所屬下層元素。在第7章將重點討論樹形結(jié)構(gòu)，它是典型的層次結(jié)構(gòu)。樹中的元素叫做結(jié)點。樹可以為空，也可以不為空。若樹不為空，它有一個叫做根的結(jié)點，其他結(jié)點都是從它派生出來的。除根以外，每一個結(jié)點都有一個處于該結(jié)點直接上層的結(jié)點。樹的結(jié)構(gòu)如圖1.3所示。第1章緒論9圖1.3樹形結(jié)構(gòu)圖1．4群聚集(a)圖結(jié)構(gòu)(b)網(wǎng)絡(luò)結(jié)構(gòu)

群結(jié)構(gòu)中所有元素之間無順序關(guān)系。集合就是一種群結(jié)構(gòu)，在本教材中不討論。在集合中沒有重復(fù)的元素。另一種群結(jié)構(gòu)就是圖結(jié)構(gòu)，如圖1．4(a)所示。它是由圖的頂點集合和連接頂點的邊集合組成。還有一種圖的特殊形式，即網(wǎng)絡(luò)結(jié)構(gòu)。它給每條邊賦予一個權(quán)值，這個權(quán)值指明了在遍歷圖時經(jīng)過此邊時的耗費。例如，在圖1．4(b)中，頂點代表城市，賦予邊的權(quán)值表示兩個城市之間的距離。第1章緒論101.2抽象數(shù)據(jù)類型1.2.1數(shù)據(jù)類型在程序設(shè)計語言中介紹過各種數(shù)據(jù)類型。以C語言為例，有5種基本的數(shù)據(jù)類型：字符型、整型、浮點型、雙精度型和無值，分別用保留字char，int，float，double和void標(biāo)識。這些數(shù)據(jù)類型不但規(guī)定了使用該類型時的取值范圍，而且還規(guī)定了該類型可以用的一組操作。例如，與整型相關(guān)的操作有+，-，*，／，與浮點型相關(guān)的操作也有+，-，*，／。然而整型的“／”操作與浮點型的“／”操作雖然形式一樣，卻是兩個不同的操作。如整型運(yùn)算3／2的運(yùn)算結(jié)果為1，浮點型運(yùn)算3／2的運(yùn)算結(jié)果為1.5。因為操作“／”用于幾個數(shù)據(jù)類型，故稱它是一種重載操作。事實上，數(shù)據(jù)類型是對數(shù)據(jù)的取值范圍、每一數(shù)據(jù)的結(jié)構(gòu)，以及允許執(zhí)行操作的一種描述。第1章緒論1.2.2數(shù)據(jù)抽象與抽象數(shù)據(jù)類型一、抽象數(shù)據(jù)類型定義（ADT）作用：抽象數(shù)據(jù)類型可以使我們更容易描述現(xiàn)實世界。例：用線性表描述學(xué)生成績表，用樹或圖描述遺傳關(guān)系。定義：一個數(shù)學(xué)模型以及定義在該模型上的一組操作。關(guān)鍵：使用它的人可以只關(guān)心它的邏輯特征，不需要了解它的存儲方式。定義它的人同樣不必要關(guān)心它如何存儲。11第1章緒論抽象數(shù)據(jù)類型表示法：

ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>

數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>

基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名例：線性表的表示名稱線性表

數(shù)據(jù)對象D={ai|ai(-ElemSet,i=0,1,2,...,n-1,n>=0}任意數(shù)據(jù)元素的集合數(shù)據(jù)關(guān)系R1={<ai-1,ai>|ai-1,ai(-D,i=1,...,n-1}除第一個和最后一個外，每個元素有唯一的直接前趨和唯一的直接后繼?；静僮鱈istInsert(&L,i,e)L為線性表，i為位置，e為數(shù)據(jù)元素。ListDelete(&L,i,e)...12第1章緒論1.2.3用于描述數(shù)據(jù)結(jié)構(gòu)的語言

數(shù)據(jù)結(jié)構(gòu)的描述可以有多種方式，如語言方式、圖形方式和表格方式。從面向?qū)ο笥^點方便地描述數(shù)據(jù)結(jié)構(gòu)的程序設(shè)計語言有Delphi、Java、C++等。從面向過程觀點方便地描述數(shù)據(jù)結(jié)構(gòu)的程序設(shè)計語言有標(biāo)準(zhǔn)Pascal、標(biāo)準(zhǔn)C、基本BASIC語言等。從另一個角度來看，很多算法是面向過程的。對于熟悉面向過程開發(fā)方法的讀者，可方便地從傳統(tǒng)的面向過程方法過渡到用面向?qū)ο蠓椒ㄩ_發(fā)程序。因此，本書采用C語言來描述各種數(shù)據(jù)結(jié)構(gòu)。13第1章緒論

1.3算法定義什么是算法(Algorithm)?通常人們將算法定義為一個有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個運(yùn)算序列。一個算法應(yīng)當(dāng)具有以下特性：

⑴有輸入。一個算法必須有0個或多個輸入，它們是算法開始運(yùn)算前給予算法的量。這些輸入取自于特定的對象的集合。它們可以使用輸入語句由外部提供，也可以使用賦值語句在算法內(nèi)給定。

⑵有輸出。一個算法應(yīng)有一個或多個輸出，輸出的量是算法計算的結(jié)果。

⑶確定性。算法的每一步都應(yīng)確切地、無歧義地定義。對于每一種情況，需要執(zhí)行的動作都應(yīng)嚴(yán)格地、清晰地規(guī)定。

⑷有窮性。一個算法無論在什么情況下都應(yīng)在執(zhí)行有窮步后結(jié)束。

⑸有效性。算法中每一條運(yùn)算都必須是足夠基本的。就是說，它們原則上都能精確地執(zhí)行，甚至人們僅用筆和紙做有限次運(yùn)算就能完成。14第1章緒論1.4算法性能分析與度量1.4.1算法的性能標(biāo)準(zhǔn)判斷一個算法的優(yōu)劣，主要有以下幾個標(biāo)準(zhǔn)：

⑴正確性。要求算法能夠正確地執(zhí)行預(yù)定的功能和性能要求。這是最重要的標(biāo)準(zhǔn)。要求算法的編寫者對問題的要求有正確的理解，并能正確地、無歧義地描述和利用某種編程語言正確地實現(xiàn)算法。

⑵可使用性。要求算法能夠很方便地使用。此特性亦稱用戶友好性。為便于用戶使用，要求該算法具有良好的界面，完備的用戶文檔。因此，算法的設(shè)計必須符合抽象數(shù)據(jù)類型和模塊化的要求，最好所有的輸入和輸出都通過參數(shù)表顯式地傳遞，少用公用變量或全局變量，每個算法只完成一個功能。

⑶可讀性。算法應(yīng)當(dāng)是可讀的。這是理解、測試和修改算法的需要。為了達(dá)到這一要求，算法的邏輯必須是清晰的、簡單的和結(jié)構(gòu)化的。所有的變量名和函數(shù)名的命名必須有實際含義，讓人見名知義。在算法中必須加入注釋，簡要說明算法的功能、輸入與輸出參數(shù)的使用規(guī)則、重要數(shù)據(jù)的作用和算法中各程序段完成的功能等。15第1章緒論1.4算法性能分析與度量1.4.1算法的性能標(biāo)準(zhǔn)⑴正確性。要求算法能夠正確地執(zhí)行預(yù)定的功能和性能要求。這是最重要的標(biāo)準(zhǔn)。要求算法的編寫者對問題的要求有正確的理解，并能正確地、無歧義地描述和利用某種編程語言正確地實現(xiàn)算法。

⑵可使用性。要求算法能夠很方便地使用。此特性亦稱用戶友好性。為便于用戶使用，要求該算法具有良好的界面，完備的用戶文檔。因此，算法的設(shè)計必須符合抽象數(shù)據(jù)類型和模塊化的要求，最好所有的輸入和輸出都通過參數(shù)表顯式地傳遞，少用公用變量或全局變量，每個算法只完成一個功能。

⑶可讀性。算法應(yīng)當(dāng)是可讀的。這是理解、測試和修改算法的需要。為了達(dá)到這一要求，算法的邏輯必須是清晰的、簡單的和結(jié)構(gòu)化的。所有的變量名和函數(shù)名的命名必須有實際含義，讓人見名知義。在算法中必須加入注釋，簡要說明算法的功能、輸入與輸出參數(shù)的使用規(guī)則、重要數(shù)據(jù)的作用和算法中各程序段完成的功能等。16第1章緒論⑷效率。算法的效率主要指算法執(zhí)行時計算機(jī)資源的消耗，包括存儲和運(yùn)行時間的開銷，前者叫做算法的空間代價，后者叫做算法的時間代價。算法的效率與多種因素有關(guān)。例如，所用的計算機(jī)系統(tǒng)、可用的存儲容量和算法的復(fù)雜性等。下面將重點地討論算法的效率，其他判斷標(biāo)準(zhǔn)在以后的章節(jié)中再加以討論。

⑸健壯性。要求在算法中加入對輸參數(shù)、打開文件、讀文件記錄，以及子程序調(diào)用狀態(tài)進(jìn)行自動檢錯和報錯并通過與用戶對話來糾錯的功能。這也叫做容錯性或例外處理。一個完整的算法必須具有健壯性，能夠?qū)Σ缓侠淼臄?shù)據(jù)進(jìn)行檢查。但在算法初寫時可以暫不管它，集中精力考慮如何實現(xiàn)必要的功能，待到算法成熟時再追加它。17第1章緒論1.4.2算法的后期測試算法效率的度量分為事前估計和后期測試。后期測試主要通過在算法中的某些部位插裝時間函數(shù)(如clock())來測定算法完成某一規(guī)定功能所需的時間。下面程序給出測試的示例。

程序清單程序演示

但是，一個算法運(yùn)行與環(huán)境有關(guān)，同樣的算法在速度不同的計算機(jī)運(yùn)行，執(zhí)行速度相差非常大；此外，一個算法用不同的編譯器編譯出的目標(biāo)代碼也不一樣長，完成同樣的功能所需時間也不同。對于一個存儲需求極大的算法，如果可用的存儲空間不夠，在運(yùn)行時將不得不頻繁地進(jìn)行內(nèi)外存交換，需要的運(yùn)行時間就很多。因此，算法的運(yùn)行時間依賴于所用的計算機(jī)系統(tǒng)、編譯器、可用存儲空間大小等。可以對算法的運(yùn)行時間進(jìn)行測量，以評估算法的正確性和可使用性，但在不同的機(jī)型、不同的編譯器版本和不同的硬軟件配置情況下，想通過測量結(jié)果來判斷算法的優(yōu)劣是不行的。18第1章緒論1.4.3算法的事前估計算法復(fù)雜性的度量屬于事前估計。它可分為空間復(fù)雜度度量和時間復(fù)雜度度量?？臻g復(fù)雜度(SpaceComplexity)是指當(dāng)問題的規(guī)模以某種單位從1增加到n時，解決這個問題的算法在執(zhí)行時所占用的存儲空間也以某種單位由1增加到S(n)，則稱此算法的空間復(fù)雜度為S(n)；時間復(fù)雜度(TimeComplexity)是指當(dāng)問題的規(guī)模以某種單位從1增加到n時，解決這個問題的算法在執(zhí)行時所耗費的時間也以某種單位由1增加到T(n)，則稱此算法的時間復(fù)雜度為T(n)。

1.空間復(fù)雜度度量⑴固定部分。這部分空間的大小與輸入輸出個數(shù)多少和數(shù)值大小無關(guān)。主要包括存放程序指令代碼的空間，常數(shù)、簡單變量、定長成分(如數(shù)組元素、結(jié)構(gòu)成員等)變量所占的空間等。這部分屬于靜態(tài)空間，只要做簡單的統(tǒng)計就可估算。⑵可變部分。這部分空間主要包括與問題規(guī)模(即實例特性)有關(guān)的成分變量所占空間、遞歸工作棧所用空間，以及在算法運(yùn)行過程中動態(tài)使用的空間。19第1章緒論2.時間復(fù)雜度度量算法的運(yùn)行時間涉及加、減、乘、除、轉(zhuǎn)移、存和取等基本運(yùn)算。要想準(zhǔn)確地計算總運(yùn)算時間是不可行的，因此，度量算法的運(yùn)行時間，主要從程序結(jié)構(gòu)著手，統(tǒng)計算法的程序步數(shù)。簡單地說，程序步是指在語法上或語義上有意義的一段指令序列，而且這段指令序列的執(zhí)行時間與實例特性無關(guān)。

程序步的統(tǒng)計

程序步統(tǒng)計程序清單程序演示1.4.4漸進(jìn)的時間復(fù)雜度算法的時間效率是通過依據(jù)該算法編制的程序在計算機(jī)上運(yùn)行所消耗的時間來度量的。程序在計算機(jī)上運(yùn)行所消耗的時間與下列因素有關(guān)：⑴書寫算法的程序設(shè)計語言；⑵編譯產(chǎn)生的機(jī)器語言代碼質(zhì)量；⑶機(jī)器執(zhí)行指令的速度；

⑷問題的規(guī)模，即算法的時間效率與算法處理的數(shù)據(jù)個數(shù)n的關(guān)系。在這四個因素中，前三個都與具體的機(jī)器有關(guān)。我們分析算法的效率應(yīng)拋開具體的機(jī)器，僅考慮算法本身的因素，因此，算法的時間效率只與問題的規(guī)模有關(guān)，算法的時間效率是問題規(guī)模的函數(shù)。算法的時間效率也稱作算法的時間復(fù)雜度。20第1章緒論算法的時間效率分析通常采用O(f(n))表示法(O(f(n))讀作大O的f(n))。定義：T(n)=O(f(n))當(dāng)且僅當(dāng)存在正常數(shù)c和n0，對所有的n(n≥n0)滿足T(n)≤cf(n)。換句話說，O(f(n))給出了函數(shù)f(n)的上界。由于上述定義中對所有的n(n≥n0)，只要n比較大一般均成立，而我們考慮的算法的時間效率也主要是在數(shù)據(jù)個數(shù)n相當(dāng)大時的情況。所以，我們具體分析一個算法的時間效率T(n)時，一般不考慮n為一個較小的數(shù)時了T(n)≤f(n)不成立的情況。令函數(shù)T(n)為算法的時間復(fù)雜度，其中n為算法處理的數(shù)據(jù)個數(shù)。則T(n)=O(f(n))表示算法的時間復(fù)雜度隨數(shù)據(jù)個數(shù)n的增長率和函數(shù)f(n)的增長率相同，或者說兩者具有相同的數(shù)量級。當(dāng)算法的時間復(fù)雜度T(n)和數(shù)據(jù)個數(shù)n無關(guān)系時，T(n)≤c*l，所以此時算法的時間復(fù)雜度T(n)=O(1)；當(dāng)算法的時間復(fù)雜度了T(n)和數(shù)據(jù)個數(shù)n為線性關(guān)系時，T(n)≤c*n，所以此時算法的時間復(fù)雜度T(n)=O(n)；當(dāng)算法的時間復(fù)雜度T(n)和數(shù)據(jù)個數(shù)n為平方關(guān)系時，T(n)≤c*n2，所以此時算法的時間復(fù)雜度T(n)=O(n2)；依此類推，還有，O(n3)、O(1bn)、O(2n)，等等。因此，分析一個算法中基本語句的執(zhí)行次數(shù)就可求出算法的時間復(fù)雜度。21第1章緒論例1.1設(shè)數(shù)組a和b在前邊部分已賦值，求如下兩個n階矩陣相乘運(yùn)算程序段的時間復(fù)雜度。for(i=0;i<n;i++)for(j=0;j<n;j++){c[i][j]=0;/*基本語句1*/for(k=0;k<n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];/*基本語句2*/}解：設(shè)基本語句的執(zhí)行次數(shù)為f(n)，有

f(n)=n2+n3

因程序段的時間復(fù)雜度T(n)=O(f(n))=n2+n3≤c*n3=O(n3)，其中c為常數(shù)，所以該程序段的時間復(fù)雜度為O(n3)。22第1章緒論例1.2設(shè)n為如下程序段處理的數(shù)據(jù)個數(shù)，求如下程序段的時間復(fù)雜度。

for(i=1;i<=n;i=2*i)printf(“i=％d\n”,i);／*基本語句*／解：設(shè)基本語句的執(zhí)行次數(shù)為f(n)，有2f(n)≤n，即有f(n)≤lbn

因程序段的時間復(fù)雜度T(n)=f(n)≤lbn≤c*1bn=O(1bn)，其中c為常數(shù)，所以該程序段的時間復(fù)雜度為O(1bn)。在很多情況中，算法中數(shù)據(jù)元素的取值情況不同算法的時間復(fù)雜度也會不同。此時算法的時間復(fù)雜度應(yīng)是數(shù)據(jù)元素最壞情況下取值的時間復(fù)雜度或數(shù)據(jù)元素等概率取值情況下的平均(或稱期望)時間復(fù)雜度。23第1章緒論24解：這個算法的時間復(fù)雜度隨待排序數(shù)據(jù)的不同而不同。當(dāng)某次排序過程中沒有任何兩個數(shù)組元素交換位置，則表明數(shù)組元素已排序完畢，此時算法將因標(biāo)記flag=0不滿足循環(huán)條件而結(jié)束。但是，在最壞情況下，每次排序過程中都至少有兩個數(shù)組元素交換位置，因此，應(yīng)按最壞情況計算該算法的時間復(fù)雜度。設(shè)基本語句的執(zhí)行次數(shù)為f(n)，最壞情況下有f(n)≈n+4*n2/2因算法的時間復(fù)雜度T(n)=f(n)≈n+n2≤c*n2=O(n2)，其中。為常數(shù)，所以該算法的時間復(fù)雜度為O(n2)。例1.3下邊的算法是用冒泡排序法對數(shù)組a中的n個整數(shù)類型的數(shù)據(jù)元素(a[0]～a[n-1])從小到大排序的算法，求該算法的時間復(fù)雜度。VoidBubbleSort(inta[],intn){inti,j,flag=l;inttemp;for(i=1;i<n&&flag==l;i++){flag=0;for(j=0;j<n-i;j++){if(a[j]>a[j+1]){flag=1;temp=a[j];a[j]=a[j+1]a[j+1]=temp;}}}}第1章緒論25例1.4下邊算法是在一個有n個數(shù)據(jù)元素的數(shù)組a中刪除第i個位置的數(shù)組元素，要求當(dāng)刪除成功時數(shù)組元素個數(shù)減1，求該算法的時間復(fù)雜度。其中，數(shù)組下標(biāo)從0至n-1。intDelete(inta[],int*n,inti){intj;if(i<0||i>*n)return0;

/*刪除位置錯誤，失敗返回*/for(j=i+1;j<*n;j++)a[j-1]=a[j];／*移位填補(bǔ)*/(*n)--;／*數(shù)組元素個數(shù)減l*/return1;／*刪除成功返回*/}解：這個算法的時間復(fù)雜度隨刪除數(shù)據(jù)的位置不同而不同。當(dāng)刪除最后一個位置的數(shù)組元素時有i=n-1，j=i+1=n,此時因不需移位填補(bǔ)而循環(huán)次數(shù)為0；當(dāng)刪除倒數(shù)第2個位置的數(shù)組元素時有i=n-2，j=i+1=n-1，此時因只需移位填補(bǔ)一次而循環(huán)次數(shù)為1依此類推，當(dāng)刪除第一個位置的數(shù)組元素時有i=0，j=i+1=1，此時因需移位填補(bǔ)n-1次而循環(huán)次數(shù)為n-1。此時算法的時間復(fù)雜度應(yīng)是刪除數(shù)據(jù)的位置等概率取值情況下的平均時間復(fù)雜度。第1章緒論

假設(shè)刪除任何位置上的數(shù)據(jù)元素都是等概率的(一般情況下均可作等概率假設(shè))，設(shè)pi為刪除第i個位置上數(shù)據(jù)元素的概率，則有pi=1／n，設(shè)E為刪除數(shù)組元素的平均次數(shù)，則有:

因該算法的時間復(fù)雜度T(n)=E≤(n+1)／2≤c*n=O(n)，其中c為常數(shù)，所以該算法的時間復(fù)雜度為O(n)。26第1章緒論27常見的時間復(fù)雜度有以下幾種情形：O（1）常數(shù)時間O（lbn）對數(shù)時間O（n）線性時間O（nlbn）線性對數(shù)時間O（n2）平方時間O（n3）立方時間O（2n）指數(shù)時間上述的時間復(fù)雜度的優(yōu)劣次序如下（n≥16）O（1）<O（lbn）<O（n）<O（nlbn）<O（n2）<O（n3）<O（2n）變化曲線如圖1.5所示圖1.5常見的時間復(fù)雜度曲線第1章緒論1.4.5漸進(jìn)的空間復(fù)雜度當(dāng)實例特性n充分大時，需要的存儲空間體積將如何隨之變化，也可以像分析時間復(fù)雜度一樣，用大O表示法來表示。設(shè)S(n)是算法的漸進(jìn)空間復(fù)雜度，在最壞情況下它可以表示為實例特性n的某個函數(shù)f(n)的數(shù)量級，記為：

S(n)=O(f(n))

這里所說的不是程序指令、常數(shù)、指針等所需要的存儲空間，也不是輸入數(shù)據(jù)所占用的存儲空間。而是為解決問題所需要的輔助存儲空間。例如，在排序算法中為移動數(shù)據(jù)所需的臨時工作單元，在遞歸算法中所需的遞歸工作棧等。通常，只有完成同一功能的幾個算法之間才具有可比性。例如，同樣是排序算法，待排序數(shù)據(jù)都是n個，作為輸入和存放這些數(shù)據(jù)的數(shù)組或鏈表結(jié)點也同樣都是n個，因此這些輸入數(shù)據(jù)所占用的存儲空間不用進(jìn)行比較，可比較的只有那些輔助的或附加的存儲空間?？梢允褂么驩表示法來標(biāo)記這些空間，用以比較各算法的優(yōu)劣。28第1章緒論29本章小結(jié)

本章介紹的主要內(nèi)容是應(yīng)用于整個數(shù)據(jù)結(jié)構(gòu)課程的基本概念和性能分析方法。學(xué)習(xí)本章內(nèi)容，將為后續(xù)章節(jié)的學(xué)習(xí)打下良好的基礎(chǔ)。1.基本概念和術(shù)語⑴數(shù)據(jù)(Data)是信息的載體，是描述客觀事物的數(shù)、字符，以及所有能輸入到計算機(jī)中并被計算機(jī)程序識別和處理的符號的集合。⑵數(shù)據(jù)對象(DataObject)具有相同屬性的數(shù)據(jù)元素集合。在數(shù)據(jù)對象中所有數(shù)據(jù)成員，即數(shù)據(jù)元素，都具有相同的性質(zhì)，它們是數(shù)據(jù)的子集。⑶數(shù)據(jù)結(jié)構(gòu)由某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)成員之間的關(guān)系組成。記為：DataStructure={D，R)其中，D是某一數(shù)據(jù)對象，R是該對象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。第1章緒論30⑷數(shù)據(jù)邏輯結(jié)構(gòu)分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。是指從解決問題的需要出發(fā)，為實現(xiàn)必要的功能所建立的數(shù)據(jù)結(jié)構(gòu)。它屬于用戶的視圖，是面向問題的。⑸數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)應(yīng)該如何在計算機(jī)中存放，是數(shù)據(jù)邏輯結(jié)構(gòu)的物理存儲方式，是屬于具體實現(xiàn)的視圖，是面向計算機(jī)的。⑹數(shù)據(jù)類型是對數(shù)據(jù)的取值范圍、每一數(shù)據(jù)的結(jié)構(gòu)，以及允許執(zhí)行操作的一種描述。⑺抽象數(shù)據(jù)類型通常是指由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。例如，線性表數(shù)據(jù)類型的ADT定義由數(shù)據(jù)元素、結(jié)構(gòu)及操作三部分組成。⑻算法(Algorithm)通常人們將算法定義為一個有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個運(yùn)算序列。一個算法應(yīng)當(dāng)具有以下特性：①有輸入。②有輸出。③確定性。④有窮性。⑤有效性。第1章緒論31

2.算法的分析⑴正確性。要求算法能夠正確地執(zhí)行預(yù)定的功能和性能要求。這是最重要的標(biāo)準(zhǔn)。⑵算法的效率主要指算法執(zhí)行時計算機(jī)資源的消耗，包括存儲和運(yùn)行時間的開銷，前者叫做算法的空間代價，后者叫做算法的時間代價。⑶算法效率的度量分為事前估計和后期測試。算法復(fù)雜性的度量屬于事前估計。它可分為空間復(fù)雜度度量和時間復(fù)雜度度量?？臻g復(fù)雜度(SpaceComplexity)是指當(dāng)問題的規(guī)模以某種單位從1增加到n時，解決這個問題的算法在執(zhí)行時所占用的存儲空間也以某種單位由1增加到S(n)，則稱此算法的空間復(fù)雜度為S(n)；時間復(fù)雜度(TimeComplexity)是指當(dāng)問題的規(guī)模以某種單位從1增加到n時，解決這個問題的算法在執(zhí)行時所耗費的時間也以某種單位由1增加到T(n)，則稱此算法的時間復(fù)雜度為T(n)。后期測試主要通過在算法中的某些部位插裝時間函數(shù)(如clock())來測定算法完成某一規(guī)定功能所需的時間。

第1章緒論32

⑷算法的時間效率分析通常采用O(f(n))表示法(O(f(n))讀作大O的f(n))。定義：T(n)=O(f(n))當(dāng)且僅當(dāng)存在正常數(shù)c和n0，對所有的n(n≥n0)滿足T(n)≤cf(n)。換句話說，O(f(n))給出了函數(shù)f(n)的上界。⑸算法的時間復(fù)雜度是衡量一個算法好壞的重要指標(biāo)。一般來說，具有多項式時間復(fù)雜度的算法是可接受、可實際使用的算法；具有指數(shù)時間復(fù)雜度的算法是只有當(dāng)n足夠小時才可使用的算法。常見的時間復(fù)雜度有以下幾種情形：O（1）常數(shù)時間、O（lbn）對數(shù)時間、O（n）線性時間、O（nlbn）線性對數(shù)時間、O（n2）平方時間、O（n3）立方時間、O（2n）指數(shù)時間。上述的時間復(fù)雜度的優(yōu)劣次序如下（n≥16）O（1）<O（lbn）<O（n）<O（nlbn）<O（n2）<O（n3）<O（2n）第1章緒論33

習(xí)題一、填空題1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的

以及它們之間的

和運(yùn)算等的學(xué)科。2.數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D是

的有限集合，R是D上的

有限集合。3.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的

、數(shù)據(jù)的

和數(shù)據(jù)的

這三個方面的內(nèi)容。4.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是

和

。5.線性結(jié)構(gòu)中元素之間存在

關(guān)系，樹形結(jié)構(gòu)中元素之間存在

關(guān)系，圖形結(jié)構(gòu)中元素之間存在

關(guān)系。6.在線性結(jié)構(gòu)中，第一個結(jié)點

前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個前驅(qū)結(jié)點；最后一個結(jié)點

后續(xù)結(jié)點，其余每個結(jié)點有且只有1個后續(xù)結(jié)點。7.在樹形結(jié)構(gòu)中，樹根結(jié)點