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

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

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

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

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

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

//建立單個(gè)數(shù)據(jù)元素或new數(shù)據(jù)類型[元素個(gè)數(shù)];//建立數(shù)組例如：int*p1=newint; int*p2=newint[3]; 釋放存儲(chǔ)空間用new運(yùn)算符開辟的內(nèi)存空間，如果程序不主動(dòng)收回，那么這段空間就一直存在，直到程序結(jié)束。分配存儲(chǔ)空間C++中使用delete運(yùn)算符釋放動(dòng)態(tài)分配的內(nèi)存空間，格式如下：delete指針變量; //釋放單個(gè)數(shù)據(jù)元素或delete[]指針變量; //釋放數(shù)組1.3抽象數(shù)據(jù)類型C++中的模板有兩種形式：函數(shù)模板和類模板。5.C++的模板10定義函數(shù)模板的一般形式為：template<模板形參表>函數(shù)定義模板形參表中可以包含一個(gè)或多個(gè)模板形參，如果有多個(gè)，必須用逗號(hào)分隔。模板形參的格式為：typename模板類型標(biāo)識(shí)符或class模板類型標(biāo)識(shí)符例如，求兩個(gè)數(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類模板聲明的語(yǔ)法形式為：template<模板參數(shù)表>class類名{

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

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

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

1.

4算法和算法分析2.算法分析14(2)算法的時(shí)間復(fù)雜度定義時(shí)間復(fù)雜度為了客觀地反映一個(gè)算法的執(zhí)行時(shí)間，可以只用算法中基本語(yǔ)句的執(zhí)行次數(shù)來(lái)度量算法的工作量?；菊Z(yǔ)句是執(zhí)行次數(shù)與整個(gè)算法的執(zhí)行次數(shù)成正比的語(yǔ)句，基本語(yǔ)句對(duì)算法運(yùn)行時(shí)間的貢獻(xiàn)最大。通常，算法的執(zhí)行時(shí)間是隨問(wèn)題規(guī)模增長(zhǎng)而增長(zhǎng)的，因此對(duì)算法的評(píng)價(jià)通常只需考慮其隨問(wèn)題規(guī)模增長(zhǎng)的趨勢(shì)。

1.

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