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

第1章緒論數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容數(shù)據(jù)結(jié)構(gòu)的基本概念抽象數(shù)據(jù)類型及其實現(xiàn)算法和算法分析1.1數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容2對于數(shù)值計算問題的求解，一般經(jīng)過以下幾個步驟：首先從具體問題抽象出數(shù)學模型，然后設(shè)計一個求解此數(shù)學模型的算法，最后編寫程序，并進行測試、調(diào)試，直到解決問題。在此過程中尋求數(shù)學模型的實質(zhì)是分析問題，從中提取操作的對象，并找出這些操作對象之間的關(guān)系，然后用數(shù)學語言加以描述，即建立相應(yīng)的數(shù)學方程。例如，預測人口增長情況的數(shù)學模型為常微分方程，求解數(shù)學方程的方法是計算數(shù)學研究的范疇。數(shù)據(jù)結(jié)構(gòu)主要研究非數(shù)值計算問題，非數(shù)值計算問題無法用數(shù)學方程建立數(shù)學模型。非數(shù)值計算問題的數(shù)學模型不再是數(shù)學方程，而是線性表、樹、圖等數(shù)據(jù)結(jié)構(gòu)。因此，簡單地說，數(shù)據(jù)結(jié)構(gòu)的研究范疇主要是非數(shù)值計算問題的操作對象和它們之間的關(guān)系以及在計算機中的表示和實現(xiàn)。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)數(shù)據(jù)是客觀事物的符號表示，是所有能輸入到計算機中并能被計算機處理的符號的總稱。數(shù)據(jù)可以指數(shù)值型數(shù)據(jù)，如整數(shù)、實數(shù)、復數(shù)等；也可以是非數(shù)值型數(shù)據(jù)，如文字、圖形、圖像、聲音、動畫等。數(shù)據(jù)元素數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機中通常作為一個整體進行處理。在有些情況下，數(shù)據(jù)元素也稱為元素、記錄、結(jié)點、頂點等。數(shù)據(jù)元素用于完整地描述一個對象，例如，學生基本信息表中每個學生記錄是一個數(shù)據(jù)元素。數(shù)據(jù)項數(shù)據(jù)項是組成數(shù)據(jù)元素的、有獨立含義的、不可分割的最小單位，是對數(shù)據(jù)元素屬性的描述。例如，學生基本信息表中，每個數(shù)據(jù)元素（即學生記錄）是由學號、姓名、性別、出生日期、籍貫和專業(yè)等數(shù)據(jù)項組成的數(shù)據(jù)對象數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如，整數(shù)數(shù)據(jù)對象是集合N={0，±1，±2，?}，字母字符數(shù)據(jù)對象是集合C={‘A’，‘B’，?，‘Z’，‘a(chǎn)’，‘b’，?，‘z’}，學生基本信息表也是一個數(shù)據(jù)對象。1.數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項和數(shù)據(jù)對象31.2數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)（DataStructure）是相互之間存在著一定關(guān)系的數(shù)據(jù)元素的集合。換句話說，數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合，結(jié)構(gòu)就是指數(shù)據(jù)元素之間存在的關(guān)系。數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩個層次。2.數(shù)據(jù)結(jié)構(gòu)4邏輯結(jié)構(gòu)存儲結(jié)構(gòu)1.2數(shù)據(jù)結(jié)構(gòu)的基本概念邏輯結(jié)構(gòu)2.數(shù)據(jù)結(jié)構(gòu)5數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素以及數(shù)據(jù)元素之間的邏輯關(guān)系，是從實際問題抽象出的數(shù)據(jù)模型，形式上可定義為一個二元組：DataStructure＝（D，R）其中D是一個數(shù)據(jù)元素的有限集合，R是定義在D中的數(shù)據(jù)元素之間的關(guān)系的集合。根據(jù)數(shù)據(jù)元素之間邏輯關(guān)系的不同，通常有四類基本結(jié)構(gòu)：(1)集合結(jié)構(gòu)：數(shù)據(jù)元素之間就是“屬于同一個集合”，除此之外，沒有任何關(guān)系。(2)線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對一的關(guān)系。(3)樹結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對多的關(guān)系。(4)圖結(jié)構(gòu)：數(shù)據(jù)元素之間存在多對多的關(guān)系。樹結(jié)構(gòu)和圖結(jié)構(gòu)也稱為非線性結(jié)構(gòu)。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念存儲結(jié)構(gòu)2.數(shù)據(jù)結(jié)構(gòu)6數(shù)據(jù)的存儲結(jié)構(gòu)又稱為物理結(jié)構(gòu)，是數(shù)據(jù)對象在計算機中的存儲表示。把數(shù)據(jù)對象存儲到計算機時，除了存儲數(shù)據(jù)元素之外，還必須隱式或顯式地存儲數(shù)據(jù)元素之間的邏輯關(guān)系。通常有兩種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)使用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素，元素之間的邏輯關(guān)系由元素在存儲器中的相對位置來表示。鏈式存儲結(jié)構(gòu)是用一組任意的存儲單元存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系用指針來表示。1.3抽象數(shù)據(jù)類型71.數(shù)據(jù)類型數(shù)據(jù)類型是一組性質(zhì)相同的值的集合以及定義在此集合上的一組操作的總稱，是程序設(shè)計語言中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。在程序設(shè)計語言中，每一個數(shù)據(jù)都屬于某種數(shù)據(jù)類型。類型顯式或隱式地規(guī)定了數(shù)據(jù)的取值范圍、存儲方式以及允許進行的運算。2.抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型一般指由用戶定義的、表示應(yīng)用問題的數(shù)學模型，以及定義在這個模型上的一組操作的總稱。一個具體問題的抽象數(shù)據(jù)類型的定義通常采用簡潔、嚴謹?shù)奈淖置枋?，一般包括?shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作三方面的內(nèi)容，描述格式如下：ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：數(shù)據(jù)對象的聲明 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的聲明 基本操作：基本操作的聲明}1.3抽象數(shù)據(jù)類型類的定義3.C++的類和對象8類的定義格式一般分為兩大部分：聲明部分和實現(xiàn)兩部分，聲明部分用來聲明該類中的成員，包括數(shù)據(jù)成員和成員函數(shù)（方法或操作）。實現(xiàn)部分用來給出說明部分中所說明的成員函數(shù)的實現(xiàn)和定義。class<類名>{private:

私有數(shù)據(jù)成員和成員函數(shù);public:公有數(shù)據(jù)成員和成員函數(shù);protected:

保護數(shù)據(jù)成員和成員函數(shù);};C++中用關(guān)鍵字class來聲明類，格式如下：類的成員函數(shù)是類的行為，是程序算法的具體實現(xiàn)。成員函數(shù)必須在類體內(nèi)進行原型說明，一般情況下，不寫出函數(shù)體，它們的實現(xiàn)寫在類外。在類外定義成員函數(shù)的格式為：函數(shù)類型類名::成員函數(shù)名([參數(shù)表>]) {

函數(shù)體;}【例1.4】Complex類的定義對象的定義類名對象名;或類名對象名([實參表]);【例1.5】使用Complex類實現(xiàn)復數(shù)的加減運算1.3抽象數(shù)據(jù)類型C++提供了動態(tài)存儲分配機制，使得程序在運行期間根據(jù)需要動態(tài)地申請和釋放內(nèi)存空間。4.C++的動態(tài)存儲分配9C++使用new運算符分配存儲空間，格式如下：new數(shù)據(jù)類型;

//建立單個數(shù)據(jù)元素或new數(shù)據(jù)類型[元素個數(shù)];//建立數(shù)組例如：int*p1=newint; int*p2=newint[3]; 釋放存儲空間用new運算符開辟的內(nèi)存空間，如果程序不主動收回，那么這段空間就一直存在，直到程序結(jié)束。分配存儲空間C++中使用delete運算符釋放動態(tài)分配的內(nèi)存空間，格式如下：delete指針變量; //釋放單個數(shù)據(jù)元素或delete[]指針變量; //釋放數(shù)組1.3抽象數(shù)據(jù)類型C++中的模板有兩種形式：函數(shù)模板和類模板。5.C++的模板10定義函數(shù)模板的一般形式為：template<模板形參表>函數(shù)定義模板形參表中可以包含一個或多個模板形參，如果有多個，必須用逗號分隔。模板形參的格式為：typename模板類型標識符或class模板類型標識符例如，求兩個數(shù)中最大值的函數(shù)模板定義：函數(shù)模板template<typenameT>Tmax(Ta,Tb){ return(a>b)?a:b;}在主函數(shù)中使用函數(shù)模板：intmain(){inta=10,b=25;doublec=20.8,d=13.4;cout<<max(a,b)<<endl;cout<<max(c,d)<<endl;return0;}1.3抽象數(shù)據(jù)類型C++中的模板有兩種形式：函數(shù)模板和類模板。5.C++的模板11類模板聲明的語法形式為：template<模板參數(shù)表>class類名{

類成員聲明;}如果需要在類模板以外定義其成員函數(shù)，則采用以下形式：template<模板參數(shù)表>類型名類名<模板類型標識符>::函數(shù)名([形參表])程序中使用模板類定義對象變量，一般采用以下形式：模板類名<模板參數(shù)>對象名1,對象名2,…,對象名n;其中模板參數(shù)是確定的數(shù)據(jù)類型，編譯器根據(jù)模板參數(shù)創(chuàng)建相應(yīng)類型的對象變量，并以適當?shù)男问秸{(diào)用模板函數(shù)?！纠?.6】類模板應(yīng)用示例類模板1.

4算法和算法分析1.算法12算法是對特定問題求解步驟的一種描述，它是指令的有限序列。算法的定義及特性有窮性確定性可行性輸入輸出算法的特性：評價算法優(yōu)劣的基本標準正確性可讀性健壯性高效性1.

4算法和算法分析2.算法分析13(1)問題規(guī)模和語句頻度時間復雜度問題規(guī)模是指輸入量的多少，一般可以從問題描述中得到。語句的重復執(zhí)行次數(shù)稱作語句頻度。個算法的執(zhí)行時間大致上等于其所有語句執(zhí)行時間的總和，而語句的執(zhí)行時間則為該條語句的頻度和執(zhí)行一次所需時間的乘積。

1.

4算法和算法分析2.算法分析14(2)算法的時間復雜度定義時間復雜度為了客觀地反映一個算法的執(zhí)行時間，可以只用算法中基本語句的執(zhí)行次數(shù)來度量算法的工作量。基本語句是執(zhí)行次數(shù)與整個算法的執(zhí)行次數(shù)成正比的語句，基本語句對算法運行時間的貢獻最大。通常，算法的執(zhí)行時間是隨問題規(guī)模增長而增長的，因此對算法的評價通常只需考慮其隨問題規(guī)模增長的趨勢。

1.

4算法和算法分析時間復雜度分析示例15【例1.8】常數(shù)階示例。 intsum=0; for(inti=1;i<=100;i++) sum+=i; 【例1.9】線性階示例。 intsum=0; for(inti=1;i<=n;i++) sum+=i;【例1.10】平方階示例。 ints=0; for(inti=1;i<=n;i++) for(intj=1;j<=2*i;j++) s++;

1.

4算法和算法分析2.算法分析16算法在運行過程中所需的存儲空間包括：(1)輸入輸出數(shù)據(jù)占用的空間；(2)算法本身占用的空間；(3)執(zhí)行算法需要的輔助空間。空間復雜度其中，輸入輸出數(shù)據(jù)占用的空間取決于問題，與算法無關(guān)；算法本身占用的空間雖然與算法相關(guān)，但一般其大小是固定的。所以，算法的空間復雜性是指在算法的執(zhí)行過程中需要的輔助空間數(shù)量，也就是除算法本身和輸入輸出數(shù)據(jù)所占用的空間外，算法臨時開辟的存儲空間，這個輔助存儲空間數(shù)量也應(yīng)該是輸入規(guī)模的函數(shù)，通常記作：S(n)=O(f(n))其中，n為輸入輸出規(guī)模，分析方法與算法的時間復雜度類似。本章小結(jié)(1)數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算程序設(shè)計中的操作對象，以及這些對象之間的關(guān)系和操作的學科。(2)數(shù)據(jù)結(jié)構(gòu)包括：數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。邏輯結(jié)構(gòu)是指數(shù)據(jù)元素以及數(shù)據(jù)元素之間的邏輯關(guān)系，是從實際問題抽象出的數(shù)據(jù)模型。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有四類基本邏輯結(jié)構(gòu)：集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)。存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機中的存儲表示，通常有兩種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。(3)抽象數(shù)據(jù)類型是指由用戶定義的、表示應(yīng)用問題的數(shù)學模型，以及定義在這個模型上的一組操作的總稱，一般包括數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作三方面的內(nèi)容。