1、1,第一章 數(shù)據(jù)結構概念,數(shù)據(jù)結構電子教案,殷人昆 王 宏,2,什么是數(shù)據(jù)結構 抽象數(shù)據(jù)類型及面向對象概念 算法定義 模板 算法簡單性能分析與度量,第一章 數(shù)據(jù)結構概念,3,“學生”表格,4,“課程”表格,5,學生 (學號,姓名,性別,籍貫),課程 (課程號,課程名,學分),選課 (學號,課程號,成績),“選課單”包含如下信息 學號 課程編號 成績 時間 學生選課系統(tǒng)中實體構成的網(wǎng)狀關系,6,UNIX文件系統(tǒng)的系統(tǒng)結構圖,7,數(shù)據(jù)（data）,數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機中，被計算機程序識別和處理的符號的集合。 數(shù)據(jù)的分類： 數(shù)值性數(shù)據(jù) 非數(shù)值性數(shù)據(jù),8,

2、數(shù)據(jù)元素 (data element),數(shù)據(jù)的基本單位。在計算機程序中常作為一個整體進行考慮和處理。 有時一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項 (Data Item)組成。數(shù)據(jù)項是具有獨立含義的最小標識單位。 數(shù)據(jù)元素又稱為元素、結點、記錄。,9,什么是數(shù)據(jù)結構,定義: 由某一數(shù)據(jù)元素的集合以及該集合中所有數(shù)據(jù)元素之間的關系組成。記為： Data_Structure = D, R 其中，D 是某一數(shù)據(jù)元素的集合，R 是該集合中所有數(shù)據(jù)元素之間的關系的有限集合。,10,例：N 個網(wǎng)點之間的連通關系,樹形關系,網(wǎng)狀關系,11,數(shù)據(jù)結構是數(shù)據(jù)的組織形式,包括三個方面： 數(shù)據(jù)元素間的邏輯關系，即數(shù)據(jù)的邏輯結構

3、； 數(shù)據(jù)元素及其關系在計算機存儲內(nèi)的表示，即數(shù)據(jù)的存儲表示； 數(shù)據(jù)的運算，即對數(shù)據(jù)元素施加的操作。,12,數(shù)據(jù)的邏輯結構,數(shù)據(jù)的邏輯結構從邏輯關系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關； 數(shù)據(jù)的邏輯結構可以看作是從具體問題抽象出來的數(shù)據(jù)模型； 數(shù)據(jù)的邏輯結構與數(shù)據(jù)元素本身的形式、內(nèi)容無關； 數(shù)據(jù)的邏輯結構與數(shù)據(jù)元素的相對存儲位置無關。,13,數(shù)據(jù)的邏輯結構分類,線性結構 線性表 非線性結構 樹 圖（或網(wǎng)絡）,14,線性結構,樹形結構,樹 二叉樹 二叉搜索樹,15,堆結構,“最大”堆 “最小”堆,16,圖結構 網(wǎng)絡結構,17,數(shù)據(jù)的存儲結構,數(shù)據(jù)的存儲結構是邏輯結構用計算機語言的實現(xiàn)； 數(shù)據(jù)的存儲結構依賴

4、于計算機語言。 順序存儲表示 鏈接存儲表示 索引存儲表示 散列存儲表示,主要用于內(nèi)存的存儲表示,主要用于外存 (文件) 的存儲表示,18,抽象數(shù)據(jù)類型及面向對象概念,數(shù)據(jù)類型 定義：一組性質相同的值的集合, 以及定義于這個值集合上的一組操作的總稱. C語言中的數(shù)據(jù)類型 char int float double void 字符型 整型 浮點型 雙精度型 無值,19,構造數(shù)據(jù)類型由基本數(shù)據(jù)類型或構造數(shù)據(jù)類型組成。 構造數(shù)據(jù)類型由不同成分類型構成。 基本數(shù)據(jù)類型可以看作是計算機中已實現(xiàn)的數(shù)據(jù)結構。 數(shù)據(jù)類型就是數(shù)據(jù)結構，不過它是從編程者的角度來使用的。 數(shù)據(jù)類型是模板，必須定義屬于某種數(shù)據(jù)類型的變

5、量，才能參加運算。,20,抽象數(shù)據(jù)類型 (ADTs: Abstract Data Types),抽象數(shù)據(jù)類型是由用戶定義，用以表示應用問題的數(shù)據(jù)模型。 特點是：信息隱蔽和數(shù)據(jù)封裝，使用與實現(xiàn)相分離。 抽象數(shù)據(jù)類型可用（D, S, P）三元組表示，其中，D 是數(shù)據(jù)元素的集合（簡稱數(shù)據(jù)對象），S 是 D上的關系集合，P 是對 D 的基本操作集合。,21,抽象數(shù)據(jù)類型,22,抽象數(shù)據(jù)類型的描述,其中數(shù)據(jù)對象、數(shù)據(jù)之間的關系用偽碼描述；基本操作定義格式為,ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象的定義 數(shù)據(jù)關系：數(shù)據(jù)關系的定義 基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名,基本操作名（參數(shù)表）

6、前置條件：先決條件描述 后置條件：操作結果描述,23,基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以 False, True Boolean, +、-、=、= 等都是可用的服務。 Zero( ) : NaturalNumber /前置條件：無 /后置條件：返回自然數(shù)0,25,IsZero(x) : Boolean /前置條件：x為NaturalNumber /后置條件：if (x = 0) then 返回True else 返回False Add (x, y) : NaturalNumber /前置條件：x, y為NaturalNumber且x+yMaxInt /后置條件：返回 x

7、+y Subtract (x, y) : NaturalNumber /前置條件： x, y為NaturalNumber且xy /后置條件：返回 x- y,26,Equal (x, y) : Boolean /前置條件： x, y為NaturalNumber /后置條件： if (x = y) 返回True else 返回 False Successor (x) : NaturalNumber /前置條件： x為NaturalNumber /后置條件： if (x = MaxInt) 返回 x else 返回 x+1 end NaturalNumber,27,面向對象的概念,面向對象 = 對象

8、類繼承通信 對象 在應用問題中出現(xiàn)的各種實體、事件、規(guī)格說明等。 由一組屬性值和在這組值上的一組服務（或稱操作）構成。 與C中構造數(shù)據(jù)類型不同在于：C中的構造數(shù)據(jù)類型的變量僅涉及屬性值，與操作分離，而C+中的對象則不然。,28,類 (class)，實例 (instance) 具有相同屬性和服務的對象歸于同一類，形成類。 類中的對象為該類的實例。 同一類的實例 共享類的屬性和類的操作； 通過繼承共享其父類的公共的和保護性的屬性和操作； 同一類的不同實例有不同的屬性值。,29,四邊形類及其對象,30,繼承 派生類（子類）：四邊形，三角形， 基類（父類）：多邊形,31,通信 消息傳遞 C+中消息傳遞

9、的方式： 定義：Point p; void move(int x, inty); 使用：p.move(x, y); C中則不同，需使用函數(shù)調用方式： 定義：Point p; void move(Point q, int x, inty); 使用：move(p, x, y);,32,Draw( ) move(x, y) contains(aPoint),Polygon,referencePoint Vertices,Polygon 類,referencePoint Vertices,Draw( ) move(x, y) contains(aPoint),Polygon的子類 Quadrilate

10、ral類,Quadrilateral,33,算法定義,定義：一個有窮的指令集，這些指令為解決某一特定任務規(guī)定了一個運算序列 特性： 輸入 有0個或多個輸入 輸出 有一個或多個輸出(處理結果) 確定性 每步定義都是確切無歧義的 有窮性 算法應在執(zhí)行有窮步后結束 有效性 每一條運算應足夠基本,34,事例學習：選擇排序問題 明確問題：遞增排序 解決方案：逐個選擇最小數(shù)據(jù) 算法框架： for (int i = 0; i n-1; i+) /n-1趟 從ai檢查到an-1; 若最小整數(shù)在ak, 交換ai與ak; 細化程序：程序 SelectSort,算法設計 自頂向下，逐步求精,35,void sele

11、ctSort ( 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; ,36,模板 (template),定義 適合多種數(shù)據(jù)類型的類定義或算法，在特定環(huán)境下通過簡單地代換，變成針對具體某種數(shù)據(jù)類型的類定義或算法。,37,用模板定義用于排序的數(shù)據(jù)表類 #ifndef DATALI

12、ST_H #define DATALIST_H #include /K是表項關鍵碼類型 template / /E是表項類型 class dataList private: E *element; int listSize; void swap (int m1, int m2); int minKey (int low, int high);,38,public: dataList (int size = 10) : listSize (size), element (new Esize) dataList ( ) delete element; void sort ( ); friend o

13、stream #endif,39,類中所有操作作為模板函數(shù)的實現(xiàn) template void dataList : swap (int m1, int m2) /交換由m1, m2為下標的數(shù)組元素的值 E temp = element m1; element m1 = element m2; element m2 = temp; ;,40,template int dataList:minKey (int low, int high) /查找數(shù)組Elementlow到Elementhigh中具 /有最小關鍵碼值的表項，函數(shù)返回其位置 int min = low; for (int i = lo

14、w+1, i = high, i+) if ( elementi elementmin ) min = i; return min; ;,定義的重載操作,41,template ostream ,42,template istream ,43,template void dataList : sort ( ) /按非遞減順序對listSize個關鍵碼element0到 /elementArraySize-1排序 for (int i = 0; i = listSize-2; i+) int j = minKey (i, listSize-1); if (j != i) swap (j, i);

15、 #endif,44,使用模板的選擇排序算法的主函數(shù) #include #include “dataList.h” const int SZ = 10; int main ( ) struct sick /患者 int key; char *name15; int age; char *address30; bool operator (sick x) return key x.key; ;,45,dataList TestList (SZ); cin TestList; cout TestList endl; TestList.Sort ( ); cout TestList endl; re

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

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

18、top; time( 事實上，算法運行時間要受輸入規(guī)模、利用編譯程序生成的目標代碼的質量、計算機程序指令系統(tǒng)的品質和速度等制約。,51,算法的事前估計,算法的事前估計主要包括時間復雜性和空間復雜性的分析： 問題的規(guī)模：如：矩陣的階數(shù)、圖的結點個數(shù)、被分類序列的正整數(shù)個數(shù)等。 時間復雜性：算法所需時間和問題規(guī)模的函數(shù)，記為 T(n)。當 n 時的時間復雜性，稱為漸進時間復雜性。 空間復雜性：算法所需空間和問題規(guī)模的函數(shù)。記為 S(n)。當 n 時的時間復雜性，稱為漸進空間復雜性。,52,空間復雜度度量,存儲空間的固定部分程序指令代碼的空間，常數(shù)、簡單變量、定長成分(如數(shù)組元素、結構成分、對象的數(shù)據(jù)成員等)變量所占空間 可變部分尺寸與實例特性有關的成分變量所占空間、引用變量所占空間、遞歸棧所用空間、通過new和dele