數(shù)據(jù)結(jié)構(gòu)課堂講義2-chapte1概念

1、數(shù)據(jù)結(jié)構(gòu)與算法2015年秋季第一章 數(shù)據(jù)結(jié)構(gòu)概念目 錄什么是數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)類型及面向?qū)ο蟾拍钏惴ǘx模板算法簡單性能分析與度量數(shù)據(jù)（data）數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機中，被計算機程序識別和處理的符號的集合。數(shù)據(jù)的分類： 數(shù)值性數(shù)據(jù) 非數(shù)值性數(shù)據(jù)數(shù)據(jù)元素 (data element)數(shù)據(jù)的基本單位。在計算機程序中常作為一個整體進行考慮和處理。有時一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項 (Data Item)組成。數(shù)據(jù)項是具有獨立含義的最小標(biāo)識單位。數(shù)據(jù)元素又稱為元素、結(jié)點、記錄。姓名所在院系性別出生日期 年 月職務(wù)業(yè)績什么是數(shù)據(jù)結(jié)構(gòu)定義: 由某一數(shù)據(jù)元素的集合以

2、及該集合中所有數(shù)據(jù)元素之間的關(guān)系組成。記為： Data_Structure = D, R 其中，D 是某一數(shù)據(jù)元素的集合，R 是該集合中所有數(shù)據(jù)元素之間的關(guān)系的有限集合。例：N 個網(wǎng)點之間的連通關(guān)系 樹形關(guān)系網(wǎng)狀關(guān)系156152436243數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織形式包括三個方面：數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)元素及其關(guān)系在計算機存儲內(nèi)的表示，即數(shù)據(jù)的存儲表示；數(shù)據(jù)的運算，即對數(shù)據(jù)元素施加的操作。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)；數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)據(jù)模型；數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容無關(guān)；數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元

3、素的相對存儲位置無關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)分類線性結(jié)構(gòu) 線性表非線性結(jié)構(gòu) 樹 圖（或網(wǎng)絡(luò)）線性結(jié)構(gòu)樹形結(jié)構(gòu)樹 二叉樹 二叉搜索樹bindevetclibuser14131211234567891031587101199874566231311堆結(jié)構(gòu) “最大”堆 “最小”堆123548711102916410121151236987圖結(jié)構(gòu) 網(wǎng)絡(luò)結(jié)構(gòu)12543611331814665161921125634數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)；數(shù)據(jù)的存儲結(jié)構(gòu)依賴于計算機語言。 順序存儲表示 鏈接存儲表示 索引存儲表示 散列存儲表示主要用于內(nèi)存的存儲表示主要用于外存 (文件) 的存儲表

4、示抽象數(shù)據(jù)類型及面向?qū)ο蟾拍顢?shù)據(jù)類型 定義：一組性質(zhì)相同的值的集合, 以及定義于這個值集合上的一組操作的總稱.C語言中的數(shù)據(jù)類型 char int float double void 字符型 整型 浮點型 雙精度型 無值 構(gòu)造數(shù)據(jù)類型由基本數(shù)據(jù)類型或構(gòu)造數(shù)據(jù)類型組成。構(gòu)造數(shù)據(jù)類型由不同成分類型構(gòu)成?；緮?shù)據(jù)類型可以看作是計算機中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)類型就是數(shù)據(jù)結(jié)構(gòu)，不過它是從編程者的角度來使用的。數(shù)據(jù)類型是模板，必須定義屬于某種數(shù)據(jù)類型的變量，才能參加運算。 抽象數(shù)據(jù)類型(ADTs: Abstract Data Types)抽象數(shù)據(jù)類型是由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。特點是：信息隱

5、蔽和數(shù)據(jù)封裝，使用與實現(xiàn)相分離。抽象數(shù)據(jù)類型可用（D, S, P）三元組表示，其中，D 是數(shù)據(jù)元素的集合（簡稱數(shù)據(jù)對象），S 是 D上的關(guān)系集合，P 是對 D 的基本操作集合。 抽象數(shù)據(jù)類型的描述其中數(shù)據(jù)對象、數(shù)據(jù)之間的關(guān)系用偽碼描述；基本操作定義格式為ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義 基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名基本操作名（參數(shù)表）前置條件：先決條件描述后置條件：操作結(jié)果描述基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果。 “前置條件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的先

6、決條件，若不滿足，則操作失敗，并返回相應(yīng)出錯信息。 “后置條件”說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若前置條件為空，則省略之。自然數(shù)的抽象數(shù)據(jù)類型定義ADT NaturalNumber isobjects: 一個整數(shù)的有序子集合,它開始于0, 結(jié)束于機器能表示的最大整數(shù)(MaxInt)。Function: 對于所有的 x, y NaturalNumber; False, True Boolean, +、-、=、= 等都是可用的服務(wù)。 Zero( ) : NaturalNumber /前置條件：無 /后置條件：返回自然數(shù)0 IsZero(x) : Boolean /前置條件

7、：x為NaturalNumber /后置條件：if (x = 0) then 返回True else 返回False Add (x, y) : NaturalNumber /前置條件：x, y為NaturalNumber且x+yMaxInt /后置條件：返回 x+y Subtract (x, y) : NaturalNumber /前置條件： x, y為NaturalNumber且xy /后置條件：返回 x- y Equal (x, y) : Boolean /前置條件： x, y為NaturalNumber /后置條件： if (x = y) 返回True else 返回 False Suc

8、cessor (x) : NaturalNumber /前置條件： x為NaturalNumber /后置條件： if (x = MaxInt) 返回 x else 返回 x+1end NaturalNumber算法定義定義：一個有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個運算序列特性：輸入 有0個或多個輸入輸出 有一個或多個輸出(處理結(jié)果)確定性 每步定義都是確切無歧義的有窮性 算法應(yīng)在執(zhí)行有窮步后結(jié)束有效性 每一條運算應(yīng)足夠基本算法設(shè)計 自頂向下，逐步求精 事例學(xué)習(xí)：選擇排序問題明確問題：遞增排序解決方案：逐個選擇最小數(shù)據(jù)算法框架： for ( int i = 0; i n-1; i

9、+ ) /n-1趟 從ai檢查到an-1; 若最小整數(shù)在ak, 交換ai與ak; 細化程序：程序 SelectSort void selectSort ( int a , const int n ) /對n個整數(shù)a0,a1,an-1按遞增順序排序 for ( int i = 0; i n-1; i+ ) int k = i; /從ai查到an-1, 找最小整數(shù), 在ak for ( int j = i+1; j n; j+ ) if ( aj ak ) k = j; int temp = ai; ai = ak; ak = temp; 模板 (template)定義 適合多種數(shù)據(jù)類型的類定義或

10、算法，在特定環(huán)境下通過簡單地代換，變成針對具體某種數(shù)據(jù)類型的類定義或算法。用模板定義用于排序的數(shù)據(jù)表類#ifndef DATALIST_H#define DATALIST_H#include /K是表項關(guān)鍵碼類型template / /E是表項類型class dataList private: E *element; int listSize; void swap (int m1, int m2); int minKey (int low, int high); public: dataList (int size = 10) : listSize (size), element (new E

11、size) dataList ( ) delete element; void sort ( ); friend ostream& operator (ostream& outStream, dataList& outList); friend istream& operator (istream& inStream, dataList& inList); ; #endif 類中所有操作作為模板函數(shù)的實現(xiàn)#ifndef SELECTSORT_H#define SELECTSORT_H #include “dataList.h”template void dataList : swap (int

12、 m1, int m2) /交換由m1, m2為下標(biāo)的數(shù)組元素的值 E temp = element m1; element m1 = element m2; element m2 = temp; ;template int dataList:minKey (int low, int high) /查找數(shù)組Elementlow到Elementhigh中具/有最小關(guān)鍵碼值的表項，函數(shù)返回其位置 int min = low; for (int i = low+1, i = high, i+) if ( elementi elementmin ) min = i; return min;定義的重載操

13、作template ostream& operator (ostream& outStream, dataList outList) outStream “輸出數(shù)組內(nèi)容 : n”; for (int i = 0; i outList.listSize; i+) outStream outList.elementi; outStream endl; ouStream “輸出數(shù)組當(dāng)前大小 : ” outList.listSize endl; return outStream; template istream& operator (istream& inStream, dataList inLis

14、t) /輸入對象為inList，輸入流對象為inStream cout inList.listSize; cout “輸入數(shù)組元素值 : n”; for (int i = 0; i inList.listSize; i+) cout “元素” i inList.elementi; return inStream; template void dataList : sort ( ) /按非遞減順序?qū)istSize個關(guān)鍵碼element0到/elementArraySize-1排序 for ( int i = 0; i = listSize-2; i+ ) int j = minKey (i,

15、listSize-1); if ( j != i ) swap (j, i); #endif 使用模板的選擇排序算法的主函數(shù) #include #include “selectsort.h” const int SIZE = 10; int main ( ) struct sick /患者 int key; char *name15; int age; char *address30; bool operator (sick x) return key x.key; ; dataList TestList (SIZE); cin TestList; cout TestList endl; Te

16、stList.Sort ( ); cout TestList endl; return 0; 定義對象時，代入實際數(shù)據(jù)類型重載友元操作標(biāo)準(zhǔn)IO操作消息通信算法簡單性能分析與度量算法的性能標(biāo)準(zhǔn)算法的后期測試算法的事前估計算法的性能標(biāo)準(zhǔn)正確性 (Correctness ) 算法應(yīng)滿足具體問題的需求?？勺x性(Readability) 算法應(yīng)該容易閱讀。以有利于閱讀者對程序的理解。效率 效率指的是算法執(zhí)行的時間和空間利用率。通常這兩者與問題的規(guī)模有關(guān)。健壯性 (Robustness) 算法應(yīng)具有容錯處理的功能。當(dāng)輸入非法數(shù)據(jù)時，算法應(yīng)對其作出反應(yīng)，而不應(yīng)產(chǎn)生莫名其妙的輸出結(jié)果。算法的后期測試對一個算法

17、要作出全面的分析可分成兩個階段進行，即事前分析和事后測試事前分析要求事前求出該算法的一個時間界限函數(shù)。事后測試則要求在算法執(zhí)行后通過算法執(zhí)行的時間和實際占用空間的統(tǒng)計資料來分析。事后分析要求在算法中的某些部位插裝時間函數(shù) time ( )，測定算法完成某一功能所花費時間。例如，給出順序搜索 (Sequenial Search)算法int seqsearch ( int a , int n, int x ) /在a0,an-1中搜索與給定值 x 相等的元/素，函數(shù)返回其位置，失敗返回-1。 int i = 0; while ( i n & ai != x ) i+; if ( i = n ) r

18、eturn -1; return i; 插裝 time( ) 的計時程序 double start, stop; time(&start); int k = seqsearch (a, n, x); time(&stop); double runTime = stop - start; cout n runTime endl;事實上，算法運行時間要受輸入規(guī)模、利用編譯程序生成的目標(biāo)代碼的質(zhì)量、計算機程序指令系統(tǒng)的品質(zhì)和速度等制約。算法的事前估計算法的事前估計主要包括時間復(fù)雜性和空間復(fù)雜性的分析：問題的規(guī)模：如：矩陣的階數(shù)、圖的結(jié)點個數(shù)、被分類序列的正整數(shù)個數(shù)等。時間復(fù)雜性：算法所需時間和問題規(guī)

19、模的函數(shù)，記為 T(n)。當(dāng) n 時的時間復(fù)雜性，稱為漸進時間復(fù)雜性?？臻g復(fù)雜性：算法所需空間和問題規(guī)模的函數(shù)。記為 S(n)。當(dāng) n 時的時間復(fù)雜性，稱為漸進空間復(fù)雜性?？臻g復(fù)雜度度量存儲空間的固定部分程序指令代碼的空間，常數(shù)、簡單變量、定長成分(如數(shù)組元素、結(jié)構(gòu)成分、對象的數(shù)據(jù)成員等)變量所占空間可變部分尺寸與實例特性有關(guān)的成分變量所占空間、引用變量所占空間、遞歸棧所用空間、通過new和delete命令動態(tài)使用空間算法的執(zhí)行時間 =(基本操作(i)的執(zhí)行次數(shù)基本操作(i)的執(zhí)行時間 )c* 基本操作(i)的執(zhí)行次數(shù) 算法的執(zhí)行時間與基本操作執(zhí)行次數(shù)之和成正比。 如何估計時間復(fù)雜度思考精確估

20、算CPU計算步數(shù)可行嗎？精確估算CPU計算步數(shù)有意義嗎？如何粗略估計？粗略到什么程度就足夠？時間復(fù)雜度度量編譯時間運行時間程序步語法上或語義上有意義的一段指令序列；執(zhí)行時間與問題規(guī)模無關(guān)；例如：聲明語句：程序步數(shù)為0; 表達式：程序步數(shù)為1程序步確定方法插入計數(shù)全局變量count建表，列出每個語句的程序步例 以迭代方式求累加和的函數(shù) float sum ( float a , int n ) float s = 0.0; for ( int i = 0; i n; i+ ) s = s + ai; return s; 在求累加和程序中加入 count 語句 float sum ( float

21、a , int n ) float s = 0.0; count+; /count 統(tǒng)計執(zhí)行語句條數(shù) for ( int i = 0; i n; i+ ) count += 2; /針對 for 語句 s += ai; count+; /針對賦值語句 count += 2; /針對 for 的最后一次 count+; /針對 return 語句 return s; 執(zhí)行結(jié)束得 程序步數(shù) count = 3*n+4程序的簡化形式 void sum ( float a , int n ) for ( int i = 0; i n; i+ ) count += 3; count += 4; 注意：

22、一個語句本身的程序步數(shù)可能不等于該語句一次執(zhí)行所具有的程序步數(shù)。 例如：賦值語句x = sum (R, n) 本身程序步數(shù)為 1；一次執(zhí)行對函數(shù) sum (R, n) 的調(diào)用需要的程序步數(shù)為 3*n+4；一次執(zhí)行的程序步數(shù)為 1+3*n+4 = 3*n+5計算累加和程序程序步數(shù)計算工作表格漸近時間復(fù)雜度上限定義Big“oh”: f(n) = O(g(n) 若且為若存在正的常數(shù)c與n0使得所有的n,當(dāng)nn0時f(n) cg(n).C.C. YaoExamples of Asymptotic Notation3n + 2 = O(n)3n + 24n for all n 3100n + 6 = O

23、(n)100n + 6101n for all n 1010n2+ 4n + 2 = O(n2) 10n2+ 4n + 211n2for all n 5時間復(fù)雜度的漸進表示法例 求兩個n階方陣的乘積C = ABvoid MatrixMultiply ( int Ann, int Bnn, int Cnn ) for ( int i = 0; i n; i+ ) 2n+2 for ( int j = 0; j n; j+ ) n(2n+2) Cij = 0; n2 for ( int k = 0; k n; k+ ) n2(2n+2) Cij = Cij + Aik * Bkj; n3 3n3

24、+ 5n2 + 4n +2時間復(fù)雜度的漸進表示法算法中所有語句的頻度之和是矩陣階數(shù)n的函數(shù) T(n) = 3n3 + 5n2 + 4n +2一般地，稱 n 是問題的規(guī)模。則時間復(fù)雜度 T(n) 是問題規(guī)模 n 的函數(shù)。當(dāng)n趨于無窮大時，把時間復(fù)雜度的數(shù)量級（階）稱為算法的漸進時間復(fù)雜度 T(n) = O(n3) 大O表示法加法規(guī)則 針對并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m)各種函數(shù)的增長趨勢 c log2n n nlog2n n2 n3 2n 3n n!Function Valueslog nnn log nn2n32n010

25、11212248424816641638246451225641664256409665536532160102432768 常見函數(shù)增長率T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2)變量計數(shù)for ( int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) y +;T1 (n) = O(1)T2(n) = O(n)T3(n) = O(n2)x = 0; y = 0;for ( int k = 0; k n; k + ) x +;乘法規(guī)則 針對嵌套程序段 T (n, m) = T1 (n) * T2 (