數(shù)據(jù)結(jié)構(gòu)第1單元(基礎(chǔ)知識(shí))

武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

數(shù)據(jù)結(jié)構(gòu)用C++語(yǔ)言描述算法武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

課程簡(jiǎn)介

課程性質(zhì)

計(jì)算機(jī)相關(guān)專(zhuān)業(yè)的專(zhuān)業(yè)基礎(chǔ)課。

學(xué)習(xí)目的

學(xué)習(xí)如何組織數(shù)據(jù)、如何高效率的處理數(shù)據(jù)。

基本內(nèi)容

學(xué)習(xí)線(xiàn)性表、棧、隊(duì)列、樹(shù)、搜索樹(shù)、散列表、圖等常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，包括它們的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)，以及相關(guān)的算法。武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)抽象和抽象數(shù)據(jù)類(lèi)型如何描述數(shù)據(jù)結(jié)構(gòu)如何描述算法算法分析的基本方法第一單元基礎(chǔ)知識(shí)

數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)基本術(shù)語(yǔ)

數(shù)據(jù)

：計(jì)算機(jī)加工處理的對(duì)象數(shù)值數(shù)據(jù)非數(shù)值數(shù)據(jù)

數(shù)據(jù)元素（結(jié)點(diǎn)、頂點(diǎn)）：組成數(shù)據(jù)的基本單位數(shù)據(jù)項(xiàng)（字段、域）：組成數(shù)據(jù)的最小單位武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

數(shù)據(jù)結(jié)構(gòu)概念涉及三個(gè)方面

數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素間的邏輯關(guān)系數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)在計(jì)算機(jī)中的表示形式數(shù)據(jù)的運(yùn)算：在數(shù)據(jù)上執(zhí)行的操作武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月南京郵電大學(xué)計(jì)算機(jī)學(xué)院陳慧南2006年9月

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

數(shù)據(jù)的邏輯結(jié)構(gòu)對(duì)數(shù)據(jù)元素間邏輯關(guān)系的描述被稱(chēng)為數(shù)據(jù)的邏輯結(jié)構(gòu)

?？梢杂枚M描述數(shù)據(jù)的邏輯結(jié)構(gòu)：DS=（D，R）其中，D是數(shù)據(jù)元素的有限集合，R是D中元素序偶的集合。

（示例：P3）

武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

數(shù)據(jù)邏輯結(jié)構(gòu)的分類(lèi)

（a）集合結(jié)構(gòu)（b）線(xiàn)性結(jié)構(gòu)（c）樹(shù)形結(jié)構(gòu)

（d）圖狀結(jié)構(gòu)

3類(lèi)基本的邏輯結(jié)構(gòu)：線(xiàn)性結(jié)構(gòu)，樹(shù)形結(jié)構(gòu)，圖狀結(jié)構(gòu)2類(lèi)基本的邏輯結(jié)構(gòu)：線(xiàn)性結(jié)構(gòu)，非線(xiàn)性結(jié)構(gòu)武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)用一塊連續(xù)的存儲(chǔ)空間，把邏輯上相鄰的數(shù)據(jù)元素依次存儲(chǔ)在該連續(xù)的存儲(chǔ)區(qū)中。

Loc（ak）＝102＋2*k武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

鏈接存儲(chǔ)

基本存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)鏈接存儲(chǔ)結(jié)構(gòu)索引存儲(chǔ)結(jié)構(gòu)散列存儲(chǔ)結(jié)構(gòu)DataLink

地址信息稱(chēng)為鏈。∧表示空鏈。武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

數(shù)據(jù)的運(yùn)算創(chuàng)建運(yùn)算:創(chuàng)建一個(gè)數(shù)據(jù)結(jié)構(gòu)；清除運(yùn)算:刪除數(shù)據(jù)結(jié)構(gòu)中的全部元素；插入運(yùn)算:在數(shù)據(jù)結(jié)構(gòu)的指定位置上插入一個(gè)新元素；刪除運(yùn)算:將數(shù)據(jù)結(jié)構(gòu)中的某個(gè)元素刪除；……武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

靜態(tài)數(shù)據(jù)結(jié)構(gòu)

一旦創(chuàng)建，其結(jié)構(gòu)不再改變的數(shù)據(jù)結(jié)構(gòu)。動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)允許進(jìn)行插入刪除等操作，其結(jié)構(gòu)是動(dòng)態(tài)變化的數(shù)據(jù)結(jié)構(gòu)。武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)是指：按某種邏輯關(guān)系組織起來(lái)的一組數(shù)據(jù)元素，按一定的存儲(chǔ)方法存儲(chǔ)計(jì)算機(jī)中，并在其上定義了一個(gè)運(yùn)算的集合。

沒(méi)有公認(rèn)的、標(biāo)準(zhǔn)的定義。武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月數(shù)據(jù)抽象和抽象數(shù)據(jù)類(lèi)型數(shù)據(jù)抽象和過(guò)程抽象封裝和信息隱蔽數(shù)據(jù)類(lèi)型和抽象數(shù)據(jù)類(lèi)型數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類(lèi)型

武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

數(shù)據(jù)抽象和過(guò)程抽象抽象：抽取共同的和本質(zhì)的內(nèi)容，忽略非本質(zhì)的細(xì)節(jié)。

數(shù)據(jù)抽象：只關(guān)注數(shù)據(jù)元素間的邏輯關(guān)系，忽略數(shù)據(jù)在計(jì)算機(jī)中的具體表示。

過(guò)程抽象：只關(guān)注數(shù)據(jù)運(yùn)算的定義，忽略運(yùn)算的具體實(shí)現(xiàn)方法。抽象的好處：降低了問(wèn)題求解的難度。武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

封裝與信息隱蔽

封裝:是指把數(shù)據(jù)和操縱數(shù)據(jù)的運(yùn)算組合在一起的機(jī)制。使用者只能通過(guò)一組允許的運(yùn)算訪問(wèn)其中的數(shù)據(jù)。信息隱蔽：對(duì)使用者隱藏了數(shù)據(jù)結(jié)構(gòu)或程序的實(shí)現(xiàn)細(xì)節(jié)。通常將數(shù)據(jù)和操縱數(shù)據(jù)的運(yùn)算組成模塊。每個(gè)模塊有一個(gè)明確定義的界面，模塊內(nèi)部信息只能經(jīng)過(guò)這一界面被外部訪問(wèn)。武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

模塊應(yīng)采用封裝和信息隱蔽原則來(lái)設(shè)計(jì),這樣的模塊被稱(chēng)為黑盒子。

封裝和信息隱蔽的好處：錯(cuò)誤局部化，降低問(wèn)題求解的復(fù)雜性，提高程序的可靠性。C++語(yǔ)言的類(lèi)可以封裝數(shù)據(jù)和運(yùn)算，其公有、保護(hù)和私有成員機(jī)制有利于實(shí)現(xiàn)信息隱蔽。武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

數(shù)據(jù)類(lèi)型和抽象數(shù)據(jù)類(lèi)型

數(shù)據(jù)類(lèi)型是程序設(shè)計(jì)語(yǔ)言中的概念，它是數(shù)據(jù)抽象的一種方式。一個(gè)數(shù)據(jù)類(lèi)型定義了一個(gè)值的集合以及作用于該值集的運(yùn)算集合。程序設(shè)計(jì)語(yǔ)言中，一個(gè)數(shù)據(jù)類(lèi)型不僅規(guī)定了該類(lèi)型的變量（或常量）的取值范圍，還定義了該類(lèi)型允許的運(yùn)算。武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

抽象數(shù)據(jù)類(lèi)型（abstractdatatypeADT）是一個(gè)數(shù)據(jù)類(lèi)型，其主要特征是該類(lèi)型的對(duì)象及其運(yùn)算的規(guī)范,與該類(lèi)型對(duì)象的表示和運(yùn)算的實(shí)現(xiàn)分離，實(shí)行封裝和信息隱蔽，即所謂使用和實(shí)現(xiàn)分離。武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

數(shù)據(jù)結(jié)構(gòu)與抽象數(shù)據(jù)類(lèi)型

數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算定義組成了數(shù)據(jù)結(jié)構(gòu)的規(guī)范。數(shù)據(jù)的存儲(chǔ)表示和運(yùn)算算法的描述構(gòu)成數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。

從規(guī)范和實(shí)現(xiàn)兩方面來(lái)討論數(shù)據(jù)結(jié)構(gòu)的方式是抽象數(shù)據(jù)類(lèi)型的觀點(diǎn)。一種數(shù)據(jù)結(jié)構(gòu)被視為一個(gè)抽象數(shù)據(jù)類(lèi)型。武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

描述數(shù)據(jù)結(jié)構(gòu)和算法

數(shù)據(jù)結(jié)構(gòu)的規(guī)范數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

數(shù)據(jù)結(jié)構(gòu)的規(guī)范

數(shù)據(jù)結(jié)構(gòu)被看成是一個(gè)抽象數(shù)據(jù)類(lèi)型(ADT)，用格式化的自然語(yǔ)言來(lái)描述。數(shù)據(jù)結(jié)構(gòu)可以形式地用一個(gè)C++的抽象模板類(lèi)描述。武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

ADT1.1棧ADTADTStack{

數(shù)據(jù)：

0個(gè)或多個(gè)元素的線(xiàn)性序列（a0,a1,...,an-1）,其最大允許長(zhǎng)度為MaxStackSize。

運(yùn)算：

Create()：建立一個(gè)空棧

Destroy()：撤消一個(gè)棧

Push(x)：值為x的新元素進(jìn)棧，成為棧頂元素

Pop()：從棧中刪除棧頂元素

Top(x)：在x中返回棧頂元素}武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

template<classT>classStack{//棧類(lèi)Stack是一個(gè)模板抽象類(lèi)，其成員函數(shù)為純虛函數(shù)，未定義數(shù)據(jù)成員。

public: virtualboolPush(Tx)=0;virtualboolPop()=0;virtualboolTop(T&x)const=0;……};武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)template<classT>classSeqStack:publicStack<T>{public:

……private:inttop;//top記錄最后入棧的元素在s的下標(biāo)

intmaxTop;//最大棧頂指針

T*s;//s指向動(dòng)態(tài)生成的一維數(shù)組，存放元素};武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

template<classT>SeqStack<T>::SeqStack(intmSize){maxTop=mSize-1;//設(shè)置棧的容量值

s=newT[mSize];//生成存儲(chǔ)棧的數(shù)組

top=-1;//top==－1表示空棧}武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

算法分析的基本方法

算法及其性能標(biāo)準(zhǔn)算法的時(shí)間復(fù)雜度漸近時(shí)間復(fù)雜度算法的空間復(fù)雜度最好、最壞和平均時(shí)間復(fù)雜度武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

算法及其性能標(biāo)準(zhǔn)

計(jì)算機(jī)算法的定義

一個(gè)有窮的指令序列，它規(guī)定了解決某一特定問(wèn)題的一系列運(yùn)算。問(wèn)題：你知道“計(jì)算機(jī)程序”是如何定義的嗎？武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

計(jì)算機(jī)算法具有下列5個(gè)特征輸入：算法有零個(gè)或多個(gè)輸入輸出：算法至少產(chǎn)生一個(gè)輸出確定性：算法的每一條指令都有確切的定義，沒(méi)有二義性。能行性：算法的每一條指令都足夠基本，它們可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)。有窮性：算法能在執(zhí)行有限步之后終止。問(wèn)題：計(jì)算機(jī)程序具有哪些特征？武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

“好算法”的4個(gè)特征正確：執(zhí)行結(jié)果滿(mǎn)足預(yù)先規(guī)定的功能和性能要求。簡(jiǎn)明：思路清晰、層次分明、易讀易懂。健壯：輸入不合法數(shù)據(jù)時(shí)，應(yīng)能做適當(dāng)處理。效率：高的時(shí)間效率、低的空間需求。問(wèn)題：算法和程序是同一個(gè)概念嗎？武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

算法的時(shí)間復(fù)雜度

算法的執(zhí)行時(shí)間

算法的執(zhí)行時(shí)間等于算法中各語(yǔ)句執(zhí)行時(shí)間的總和，而某個(gè)語(yǔ)句的執(zhí)行時(shí)間等于該語(yǔ)句執(zhí)行一次所需時(shí)間與執(zhí)行次數(shù)的乘積。問(wèn)題規(guī)模

算法的執(zhí)行時(shí)間一般都與問(wèn)題規(guī)模有關(guān)。問(wèn)題規(guī)模通常是一個(gè)與輸入有關(guān)的量。算法分析的目標(biāo)找出算法執(zhí)行時(shí)間與問(wèn)題規(guī)模之間的關(guān)系。武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

漸近時(shí)間復(fù)雜度算法的執(zhí)行時(shí)間通常用數(shù)量級(jí)的形式（大O記號(hào)）表示：T(n)=O(f(n))其含義為：當(dāng)問(wèn)題規(guī)模n足夠大時(shí)，算法的執(zhí)行時(shí)間T(n)和函數(shù)f(n)成正比。或者說(shuō)，存在正常數(shù)c和n0，當(dāng)n≥n0時(shí)，有

|T(n)|≤c|f(n)|。如果算法執(zhí)行時(shí)間T(n)與問(wèn)題規(guī)模n無(wú)關(guān)，則記作

T(n)=O(1)。武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月

用數(shù)量級(jí)形式表示的算法的執(zhí)行時(shí)間，通常稱(chēng)為算法的漸近時(shí)間復(fù)雜度，或簡(jiǎn)稱(chēng)為時(shí)間復(fù)雜度。用O(f(n))表示算法執(zhí)行時(shí)間T(n)的時(shí)候，函數(shù)f(n)通常取較簡(jiǎn)單的形式，例如

1、log2n、n、nlog2n、n2、n3、2n

在n較大的情況下，常見(jiàn)的時(shí)間復(fù)雜度之間存在下列關(guān)系：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)

武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月定理1

若T(n)=amnm+am–1nm–1+…+a1n+a0是一個(gè)m次多項(xiàng)式,則

T(n)=O(nm)武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月定理2

若T1(n)、T2(n)分別是算法P1、P2的執(zhí)行時(shí)間，并且T1(n)=O(f(n))T2(n)=O(g(n))則依次執(zhí)行算法P1和P2，總的執(zhí)行時(shí)間

T(n)=O(max(|f(n)|，|g(n)|))武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月定理3

若T1(n)、T2(n)分別是算法P1、P2的執(zhí)行時(shí)間，并且

T1(n)=O(f(n))T2(n)=k(n)T1(n)則

T2(n)=O(k(n)f(n))武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月分析舉例1

假設(shè)A[1]～A[n]中存放了n個(gè)整數(shù)，下面程序段的功能是確定其中值最大的整數(shù)在數(shù)組中的下標(biāo)i。請(qǐng)分析程序段中每個(gè)語(yǔ)句的執(zhí)行次數(shù)，并用數(shù)量級(jí)形式表示這個(gè)程序段的執(zhí)行時(shí)間。i=1;for(j=2;j<=n;j++)if(A[j]>A[i])i=j;1次n次n–1次最多n–1次語(yǔ)句總的執(zhí)行次數(shù)是2n~3n–1次，程序段執(zhí)行時(shí)間是O(n)。武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月分析舉例2

假設(shè)A[1]～A[n]中存放了n個(gè)整數(shù)，其中n>100。下面程序段的功能是求其中前100個(gè)整數(shù)的平均值。請(qǐng)分析程序段中每個(gè)語(yǔ)句的執(zhí)行次數(shù)，并用數(shù)量級(jí)形式表示這個(gè)程序段的執(zhí)行時(shí)間。s=0.0;for(i=1;i<=100;i++)s=s+A[i];cout<<s/100;1次101次100次1次語(yǔ)句的執(zhí)行次數(shù)和n無(wú)關(guān)，程序段的執(zhí)行時(shí)間是O(1)。武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月分析舉例3下面程序段的功能是從n階整型矩陣中找出兩個(gè)值最小的整數(shù)。請(qǐng)分析其時(shí)間復(fù)雜度。m1=32767;m2=m1;for(i=0;i<n;i++)for(j=0;j<n;j++)if(A[i][j]<m1){m2=m1;m1=A[i][j];}elseif(A[i][j]<m2)m2=A[i][j];

執(zhí)行第1行賦值語(yǔ)句所需時(shí)間是O(1)。執(zhí)行一遍內(nèi)循環(huán)體所需時(shí)間也是O(1)。由于內(nèi)循環(huán)體總共執(zhí)行了n2次,因此,程序段的執(zhí)行時(shí)間為O(n2)。武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月分析舉例4

下面的程序段可用于求xn。請(qǐng)分析其時(shí)間復(fù)雜度。y=1;u=x;v=n;while(v>0){

if(v%2==1)y=y*u;u=u*u;v=v/2;}cout<<y;

執(zhí)行時(shí)間主要用在while循環(huán)上。由于v的初始值是n，每循環(huán)一遍，v值被減半，因此，循環(huán)次數(shù)不超過(guò)log2n次。執(zhí)行一遍循環(huán)體所需時(shí)間是O(1)。程序段的執(zhí)行時(shí)間為T(mén)(n)=(log2n)O(1)=O(log2n)問(wèn)題：這是個(gè)“好程序”嗎？請(qǐng)你寫(xiě)一個(gè)功能相同的“好程序”，并分析其時(shí)間復(fù)雜度。武漢大學(xué)國(guó)際軟件學(xué)院薛超英2014年8月分析舉例5