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

武漢大學國際軟件學院薛超英2014年8月

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

課程簡介

課程性質(zhì)

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

學習目的

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

基本內(nèi)容

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

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

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

數(shù)據(jù)

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

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

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

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

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

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

。可以用二元組描述數(shù)據(jù)的邏輯結(jié)構(gòu)：DS=（D，R）其中，D是數(shù)據(jù)元素的有限集合，R是D中元素序偶的集合。

（示例：P3）

武漢大學國際軟件學院薛超英2014年8月

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

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

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

3類基本的邏輯結(jié)構(gòu)：線性結(jié)構(gòu)，樹形結(jié)構(gòu)，圖狀結(jié)構(gòu)2類基本的邏輯結(jié)構(gòu)：線性結(jié)構(gòu)，非線性結(jié)構(gòu)武漢大學國際軟件學院薛超英2014年8月

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

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

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

鏈接存儲

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

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

地址信息稱為鏈?！谋硎究真?。武漢大學國際軟件學院薛超英2014年8月

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

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

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

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

沒有公認的、標準的定義。武漢大學國際軟件學院薛超英2014年8月數(shù)據(jù)抽象和抽象數(shù)據(jù)類型數(shù)據(jù)抽象和過程抽象封裝和信息隱蔽數(shù)據(jù)類型和抽象數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型

武漢大學國際軟件學院薛超英2014年8月

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

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

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

封裝與信息隱蔽

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

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

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

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

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

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

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

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

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

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

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

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

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

ADT1.1棧ADTADTStack{

數(shù)據(jù)：

0個或多個元素的線性序列（a0,a1,...,an-1）,其最大允許長度為MaxStackSize。

運算：

Create()：建立一個空棧

Destroy()：撤消一個棧

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

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

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

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

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

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

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

intmaxTop;//最大棧頂指針

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

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

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

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

算法分析的基本方法

算法及其性能標準算法的時間復雜度漸近時間復雜度算法的空間復雜度最好、最壞和平均時間復雜度武漢大學國際軟件學院薛超英2014年8月

算法及其性能標準

計算機算法的定義

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

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

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

算法的時間復雜度

算法的執(zhí)行時間

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

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

漸近時間復雜度算法的執(zhí)行時間通常用數(shù)量級的形式（大O記號）表示：T(n)=O(f(n))其含義為：當問題規(guī)模n足夠大時，算法的執(zhí)行時間T(n)和函數(shù)f(n)成正比?；蛘哒f，存在正常數(shù)c和n0，當n≥n0時，有

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

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

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

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

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

武漢大學國際軟件學院薛超英2014年8月定理1

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

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

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

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

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

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

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

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

假設(shè)A[1]～A[n]中存放了n個整數(shù)，其中n>100。下面程序段的功能是求其中前100個整數(shù)的平均值。請分析程序段中每個語句的執(zhí)行次數(shù)，并用數(shù)量級形式表示這個程序段的執(zhí)行時間。s=0.0;for(i=1;i<=100;i++)s=s+A[i];cout<<s/100;1次101次100次1次語句的執(zhí)行次數(shù)和n無關(guān)，程序段的執(zhí)行時間是O(1)。武漢大學國際軟件學院薛超英2014年8月分析舉例3下面程序段的功能是從n階整型矩陣中找出兩個值最小的整數(shù)。請分析其時間復雜度。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行賦值語句所需時間是O(1)。執(zhí)行一遍內(nèi)循環(huán)體所需時間也是O(1)。由于內(nèi)循環(huán)體總共執(zhí)行了n2次,因此,程序段的執(zhí)行時間為O(n2)。武漢大學國際軟件學院薛超英2014年8月分析舉例4

下面的程序段可用于求xn。請分析其時間復雜度。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í)行時間主要用在while循環(huán)上。由于v的初始值是n，每循環(huán)一遍，v值被減半，因此，循環(huán)次數(shù)不超過log2n次。執(zhí)行一遍循環(huán)體所需時間是O(1)。程序段的執(zhí)行時間為T(n)=(log2n)O(1)=O(log2n)問題：這是個“好程序”嗎？請你寫一個功能相同的“好程序”，并分析其時間復雜度。武漢大學國際軟件學院薛超英2014年8月分析舉例5