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

1.1數(shù)據(jù)結(jié)構(gòu)討論的范疇1.2基本概念及術(shù)語1.3算法和算法的分析教學(xué)內(nèi)容要點：1、數(shù)據(jù)結(jié)構(gòu)的基本概念及有關(guān)術(shù)語2、算法及算法的分析方法重點：1、有關(guān)數(shù)據(jù)結(jié)構(gòu)的名詞和術(shù)語的含義；

2、語句頻度和時間復(fù)雜度、空間復(fù)雜度的估算。

難點：時間復(fù)雜度的估算。NiklausWirth：（著名的瑞士科學(xué)家沃思教授）

Algorithm

+DataStructures=Programs

(算法+數(shù)據(jù)結(jié)構(gòu)=程序）程序:算法:數(shù)據(jù)結(jié)構(gòu):

為計算機處理問題而編制的一組指令集

求解問題的策略（是對數(shù)據(jù)運算的描述）問題的數(shù)學(xué)模型（存儲結(jié)構(gòu)和邏輯結(jié)構(gòu)）1.1

數(shù)據(jù)結(jié)構(gòu)討論的范疇求解問題的基本步驟1.確定求解問題的數(shù)學(xué)模型

(邏輯結(jié)構(gòu))；2.確定存儲結(jié)構(gòu)；3.設(shè)計算法；4.編程并測試結(jié)果。是在于解決兩個主要問題：一是根據(jù)實際問題選擇一種好的存儲結(jié)構(gòu)；二是設(shè)計一個好的算法，而好的算法在很大程度上取決于描述實際問題的存儲結(jié)構(gòu)。程序設(shè)計的實質(zhì)1、數(shù)值計算的程序設(shè)計問題

很多數(shù)值計算問題的數(shù)學(xué)模型通常可用一組線性或非線性的代數(shù)方程組或微分方程組來描述。如“雞免同籠”“橋梁結(jié)構(gòu)設(shè)計”問題。

但大量非數(shù)值計算問題的數(shù)學(xué)模型正是本門課程要討論的數(shù)據(jù)結(jié)構(gòu)。

求解問題舉例2、非數(shù)值計算的程序設(shè)計問題【例一】

求一組(n個)整數(shù)中的最大值算法:?模型：？基本操作是“比較兩個數(shù)的大小”但如果這些整數(shù)的值有可能達到1012，那么對32位的計算機來說，就存在一個如何表示的問題。

求解問題舉例【例二】電話號碼查詢問題算法：?模型：?如何查詢？電話號碼表2、非數(shù)值計算的程序設(shè)計問題求解問題舉例【例三】煤氣管道鋪設(shè)問題算法：?模型：?如何為城市的各小區(qū)之間鋪設(shè)煤氣管道,使投資最小?(對n個小區(qū)只需鋪設(shè)n-1條管線)圖的最小生成樹2、非數(shù)值計算的程序設(shè)計問題求解問題舉例方面過程數(shù)據(jù)表示數(shù)據(jù)處理抽象邏輯結(jié)構(gòu)基本運算實現(xiàn)存儲結(jié)構(gòu)算法評價不同數(shù)據(jù)結(jié)構(gòu)的比較和算法性能分析數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容體系:簡單地說,本課程研究的內(nèi)容包括以下三方面：

1.數(shù)據(jù)的邏輯結(jié)構(gòu)

2.數(shù)據(jù)的存儲結(jié)構(gòu)/物理結(jié)構(gòu)

3.數(shù)據(jù)的運算概括地說：

數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)實世界實體的數(shù)學(xué)模型(非數(shù)值計算)及其上的操作（運算）在計算機中如何表示和實現(xiàn)”的學(xué)科。一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)類型三、抽象數(shù)據(jù)類型1.2基本概念及術(shù)語所有能被輸入到計算機中，且能被計算機處理的符號的總稱。如：實數(shù)、整數(shù)、字符（串）、圖形、聲音和視頻等。對計算機而言，數(shù)據(jù)的含義極為廣泛。如指紋、人體動作等都可以通過編碼而歸之于數(shù)據(jù)的范疇。是計算機操作對象的集合。數(shù)據(jù)(Data):一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)（集合）中的一個“個體”；是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位；不同場合也叫結(jié)點、頂點、記錄（。數(shù)據(jù)元素有兩種類型：“原子”型和“構(gòu)造”型數(shù)據(jù)元素(DataElement):是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位；構(gòu)造型數(shù)據(jù)元素是由若干數(shù)據(jù)項組成。數(shù)據(jù)項(DataItem):

數(shù)據(jù)對象（DataObject）：是性質(zhì)相同的數(shù)據(jù)元素的集合。如整數(shù)、實數(shù)和例1-2中的生產(chǎn)訂單表。行：數(shù)據(jù)元素列：數(shù)據(jù)項

請梳理一下：數(shù)據(jù)、數(shù)據(jù)對象、數(shù)據(jù)元素、數(shù)據(jù)項的概念及其之間的關(guān)系！

歸納總結(jié)數(shù)據(jù)={計算機操作對象}數(shù)據(jù)對象={性質(zhì)相同的數(shù)據(jù)元素的集合}數(shù)據(jù)元素=數(shù)據(jù)項1+數(shù)據(jù)項2+……學(xué)號姓名數(shù)學(xué)分析普通物理高等代數(shù)2000120002200032000420005張三李四丁一馬二王五908067985656876790878967876768行：數(shù)據(jù)元素列：數(shù)據(jù)項數(shù)據(jù)數(shù)據(jù)對象

數(shù)據(jù)對象中的數(shù)據(jù)元素不會是孤立的，而是彼此相關(guān)的，這種彼此之間的關(guān)系稱為“結(jié)構(gòu)”。邏輯結(jié)構(gòu)：

是指從具體問題抽象出來的數(shù)據(jù)模型，是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。如下表是一個數(shù)據(jù)結(jié)構(gòu)：學(xué)號姓名數(shù)學(xué)分析普通物理高等代數(shù)2000120002200032000420005張三李四丁一馬二王五908067985656876790878967876768結(jié)點間的關(guān)系構(gòu)成了這張學(xué)生成績表的邏輯結(jié)構(gòu)

或者說，邏輯結(jié)構(gòu)是描述數(shù)據(jù)元素之間的邏輯關(guān)系。按邏輯關(guān)系來分,

數(shù)據(jù)結(jié)構(gòu)可歸結(jié)為以下四類:線性結(jié)構(gòu)(1:1)樹形結(jié)構(gòu)(1:m)圖狀結(jié)構(gòu)(m:n)集合結(jié)構(gòu)(松散）非線性結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)（DataStructure）：是相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的集合。例，在2行3列的二維數(shù)組{a1,a2,a3,a4,a5,a6}中六個元素之間存在兩個關(guān)系:行的次序關(guān)系:列的次序關(guān)系:row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}col={<a1,a4>,<a2,a5>,<a3,a6>}

a1a3a5

a2a4a6a1a2a3a4a5a6

數(shù)據(jù)結(jié)構(gòu)：再例，在一維數(shù)組{a1,a2,a3,a4,a5,a6}的數(shù)據(jù)元素之間存在如下的次序關(guān)系:{<ai,ai+1>|i=1,2,3,4,5}可見，不同的“關(guān)系”構(gòu)成不同的“結(jié)構(gòu)”數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)的形式定義為:數(shù)據(jù)結(jié)構(gòu)是一個二元組Data_Structures=(D,R)其中:D是數(shù)據(jù)元素的有限集，

R是D上關(guān)系的有限集。所以可用數(shù)據(jù)的邏輯結(jié)構(gòu)圖來形象表示由二元組所描述的結(jié)構(gòu)也稱為邏輯結(jié)構(gòu)例1設(shè)有數(shù)據(jù)結(jié)構(gòu)為：

B=（D，R）

D={k1,k2,k3,….k9}R={<k1,k3>,<k1,k8>,<k2,k3>,<k2,k4>,<k2,k5>,<k3,k9>,<k5,k6>,<k8,k9>,<k9,k7>,<k4,k7>,<k4,k6>}畫出其邏輯結(jié)構(gòu)的圖示，并確定相對于關(guān)系R，哪些結(jié)點是開始結(jié)點，哪些是終端結(jié)點？k2k1k4k5k3k8k6k9k7開始結(jié)點為k1,k2(無前驅(qū)的結(jié)點）終端結(jié)點為k6,k7(無后繼的結(jié)點）例2設(shè)有如圖所示的邏輯圖，給出它的數(shù)據(jù)結(jié)構(gòu)。

k1k2k3k6k4k8k7k5k9

解：本題的結(jié)構(gòu)如下：

B=（D，R）

D={k1,k2,k3,…,k9}R={<k1,k2>,<k1,k3>,<k3,k4>,<k3,k6>,<k6,k8>,<k4,k5>,<k6,k7>,<k8,k9>}

該結(jié)構(gòu)是一個樹形結(jié)構(gòu)，其樹根為K1，葉子結(jié)點為k2,k5,k7,k9.數(shù)據(jù)的存儲結(jié)構(gòu)

——是邏輯結(jié)構(gòu)在計算機中的表示，（即是邏輯結(jié)構(gòu)在存儲器中的映象）“數(shù)據(jù)元素”的映象？“關(guān)系”的映象？數(shù)據(jù)元素的映象方法：用二進制位(bit)的位串表示數(shù)據(jù)元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2關(guān)系的映象方法：（表示

x,y

的方法）1、順序映象以相對的存儲位置表示后繼關(guān)系整個存儲結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息xy順序存儲結(jié)構(gòu)（以邏輯位置關(guān)系與存儲位置關(guān)系一致）鏈?zhǔn)剑ǚ蔷€性）映象以附加信息(指針)表示后繼關(guān)系需要用一個和x附加在一起的指針來指示y的存儲位置yx鏈?zhǔn)酱鎯Y(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示。

1、

順序存儲

把邏輯上相鄰的結(jié)點存儲在物理上相鄰的存儲單元中。

2、

鏈接存儲

對邏輯上相鄰的元素不要求物理位置相鄰，元素之間的邏輯關(guān)系是由附加的指針表示。

3、

索引存儲

在存儲結(jié)點信息的同時，建立附加索引表。

4、

散列存儲

根據(jù)結(jié)點的關(guān)鍵字值直接計算出結(jié)點的存儲地址。

在不同的編程環(huán)境中，存儲結(jié)構(gòu)可有不同的描述方法。

當(dāng)用高級程序設(shè)計語言進行編程時，通常可用高級編程語言中提供的數(shù)據(jù)類型描述之。存儲結(jié)構(gòu)如何實現(xiàn)呢？

在用高級程序語言編寫的程序中，必須對程序中出現(xiàn)的每個變量、常量或表達式，明確說明它們所屬的數(shù)據(jù)類型。二、數(shù)據(jù)類型

其實數(shù)據(jù)類型反映三個方面的內(nèi)容：存儲結(jié)構(gòu)，取值范圍和能進行的操作。

(AbstractDataType

簡稱ADT)

是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。三、抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的形式描述:

ADT=（D，R，P）其中：D是數(shù)據(jù)對象；

R是D上的關(guān)系集；

P是對D的基本操作集。ADT

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

{

數(shù)據(jù)對象：〈數(shù)據(jù)對象的定義〉

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

基本操作：〈基本操作的定義〉}ADT

抽象數(shù)據(jù)類型名其中基本操作的定義格式為:基本操作名（參數(shù)表）初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉

賦值參數(shù)

只為操作提供輸入值。引用參數(shù)

以&打頭，除可提供輸入值外，還將返回操作結(jié)果。初始條件

描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯信息。操作結(jié)果

說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。例如，(參看書P9/例1-6）

抽象數(shù)據(jù)類型復(fù)數(shù)的定義：

數(shù)據(jù)對象：

D＝{e1,e2｜e1,e2∈RealSet}

數(shù)據(jù)關(guān)系：

R＝{<e1,e2>|e1是復(fù)數(shù)的實數(shù)部分

|e2

是復(fù)數(shù)的虛數(shù)部分}ADTComplex{基本操作：

AssignComplex(&Z,v1,v2)

操作結(jié)果：構(gòu)造復(fù)數(shù)Z,其實部和虛部分別被賦以參數(shù)v1和v2的值。

DestroyComplex(&Z)

操作結(jié)果：復(fù)數(shù)Z被銷毀。

GetReal(Z,&realPart)

初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實部值。

GetImag(Z,&ImagPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。

Add(z1,z2,&sum)初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個復(fù)數(shù)z1,z2的和值。

}ADTComplex抽象數(shù)據(jù)類型的表示和實現(xiàn)

存儲結(jié)構(gòu)需要通過固有數(shù)據(jù)類型(高級編程語言中已實現(xiàn)的數(shù)據(jù)類型)來實現(xiàn)。例如，對以上定義的復(fù)數(shù)。typedefstruct{

floatrealpart；

floatimagpart；}complex；//-----存儲結(jié)構(gòu)的定義//-----基本操作的函數(shù)原型說明void

Assign(complex&Z,floatrealval,floatimagval)；//

構(gòu)造復(fù)數(shù)Z,其實部和虛部分別被賦以參數(shù)//realval

和imagval

的值floatGetReal(complexZ)；

//返回復(fù)數(shù)Z的實部值float

Getimag(complexZ)；

//返回復(fù)數(shù)Z的虛部值voidadd(complexz1,complexz2,complex&sum)；

//以sum返回兩個復(fù)數(shù)z1,z2的和//-----基本操作的實現(xiàn)voidadd(complexz1,complexz2,complex&sum){

//以sum返回兩個復(fù)數(shù)z1,z2的和

sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;}

{其它省略}一、算法二、算法設(shè)計的原則四、算法效率的衡量方法和準(zhǔn)則五、算法的存儲空間需求三、算法的描述1.3算法和算法分析

算法是對問題求解過程的一種描述，是為解決一個或一類問題而規(guī)定的一個有限長的操作序列。嚴(yán)格來講，一個算法必須滿足以下五個重要特性：1．有窮性

2．確定性3．可行性4．輸入5．輸出一、何謂“算法”？設(shè)計算法時，通常應(yīng)考慮達到以下目標(biāo)：1．正確性2.可讀性3．健壯性4．高效率與低存儲量需求二、算法設(shè)計的原則三、算法的描述（參看P10）在不同層次上討論的算法有不同的描述方法，本課程討論的數(shù)據(jù)結(jié)構(gòu)和算法主要是面向讀者，為了使算法的描述和討論簡明清晰，容易被人理解，擬采用類C語言，它既不拘泥于某個具體的C語言，又容易轉(zhuǎn)換成可以上機調(diào)試的C程序或C++程序。

本教程擬采用類C語言，它既不拘泥于某個具體的C語言，又容易轉(zhuǎn)換成可以上機調(diào)試的C程序或C++程序。

(1)存儲結(jié)構(gòu)用類型定義(typedef)的方式描述。在不同層次上討論的算法有不同的描述方法，本課程討論的數(shù)據(jù)結(jié)構(gòu)和算法主要是面向讀者，為了使算法的描述和討論簡明清晰，容易被人理解，擬采用類C語言，它既不拘泥于某個具體的C語言，又容易轉(zhuǎn)換成可以上機調(diào)試的C程序或C++程序。

(2)預(yù)定義的常量和類型//函數(shù)結(jié)果狀態(tài)代碼#defineTRUE1#defineFLASE0#defineOK1#defineERROR0#defineINFEASEIBLE-1#defineOVERFLOW-2//約定Status

是函數(shù)類型,其值是函數(shù)結(jié)果狀態(tài)代碼，ElemType基本數(shù)據(jù)元素類型，由用戶在使用該類型時再根據(jù)實際情況自行具體定義。(3)基本操作的算法都用以下形式的函數(shù)描述：

函數(shù)類型函數(shù)名(函數(shù)參數(shù)表)

{//算法說明

語句序列

}//函數(shù)名

除了函數(shù)的參數(shù)需要說明類型外，算法中使用的輔助變量可以不作變量說明，必要時對其作用給予注釋。通常有兩種衡量算法效率的方法:事后統(tǒng)計法事前分析估算法缺點：1．必須執(zhí)行程序

2．其它因素掩蓋算法本質(zhì)四、算法效率的衡量方法和準(zhǔn)則和算法執(zhí)行時間相關(guān)的因素：1．算法選用的策略2．問題的規(guī)模3．編寫程序的語言4．編譯程序產(chǎn)生的機器代碼的質(zhì)量5．計算機執(zhí)行指令的速度

一個特定算法的“運行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。

假如，隨著問題規(guī)模n的增長，算法執(zhí)行時間的增長率和f(n)的增長率相同，則可記作：T(n)=O(f(n))稱T(n)為算法的(漸近)時間復(fù)雜度。如何估算算法的時間復(fù)雜度？算法=控制結(jié)構(gòu)+原操作（固有數(shù)據(jù)類型的操作）算法的執(zhí)行時間

=原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時間

算法的執(zhí)行時間

與

原操作執(zhí)行次數(shù)之和

成正比

從算法中選取一種對于所研究的問題來說是基本操作

的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運行時間的衡量準(zhǔn)則。例一：變量計量x=0;y=0;s=0;

for(k=1;k<=n;++k)

{++x;s+=x;}

for(i=1;i<=n;++i)

for(j=1;j<=n;++j)

{++y;s+=y;}語句頻度n+1nn+1n(n+1)n2T(n)=O(n2)例二兩個矩陣相乘voidmult(inta[],intb[],int&c[]){

//以二維數(shù)組存儲矩陣元素，c為a和b的乘積

for(i=1;i<=n;++i)

for(j=1;j<=n;++j){c[i,j]=0;

for(k=1;k<=n;++k)c[i,j]+=a[i,k]*b[k,j];

}//for}//mult基本操作:

乘法操作時間復(fù)雜度:

O(n3)語句頻度n+1n(n+1)n*nn2*(n+1)n3例三求下列基本操作語句的語句頻度及算法的時間復(fù)雜度for(i=1;i<=n;i=2*i)printf(“i=%d\n”,i);解：設(shè)基本操作語名的執(zhí)行次數(shù)為f(n),則有2f(n)≤n,所以f(n)≤log2n

故:T(n)=O(log2n)例四選擇排序voidselect_sort(int&a[],intn){

//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。

}//select_sortj=i;//

選擇第i個最小元素for(k=i+1;k<n;++k)

if(a[k]<a[j])j=k;for(i=0;i<n-1;++i)

{