數據結構講義

1、數據結構,第一章 緒論,本章主要內容,學習《數據結構》的意義基本概念和術語算法的描述和分析,1.1 什么是數據結構,圖書的基本信息登記號，書名，作者，分類編號，出版單位，出版時間作者簡介，內容簡介，等等。操作檢索，排序，等等數據之間的關系線性關系數據表示和算法操作的設計與需求有關數據的邏輯結構，存儲結構，算法操作邏輯結構是客觀事物特性的一種抽象存儲結構是邏輯結構的計算機實現算法操作是基于存儲結構的操作，反

2、映客觀事物的變化,問題1：圖書檢索自動化,問題2：井子棋,問題2：井子棋（續(xù)）,如何表示一個棋局數據之間的邏輯結構表示棋局之間的演化關系 樹型結構算法如何設計基于數據表示的基礎上算法設計,拼盤游戲：空盤,,拼盤游戲：拼件,,,拼盤游戲：拼出的一種方案,,,,,拼盤游戲：指定動作的習題,,,,,,問題3：鋪設通信管線，投資最少,,,,,,,,,邏輯結構：圖狀結構,數據結構課程的主要任務,研究和解決非數值數據的組織和處理描述非數

3、值計算問題的數學模型，不再是數學方程例如：前述的三個例子：數據的線性結構，樹型結構，圖算法+數據結構=程序算法和數據結構之間的關系軟件系統(tǒng)的框架應當建立在數據之上，而不是建立在操作之上數據結構的作用范疇抽象數據對象的數學模型（邏輯結構）例：圖狀結構明確操作（運算的定義） 例：查找、插入、……在存儲結構上映射數據（存儲結構） 例：順序存儲實現操作,數據結構課程的發(fā)展,1968年斯坦福的Knut

4、h教授開創(chuàng)了數據結構的最初體系，在他所著的《計算機程序設計技巧》第一卷《基本算法》中第一次較系統(tǒng)地闡述了數據的邏輯結構和存儲結構及其操作。 Donald Ervin Knuth 《The Art of Computer Programming》 Art Evans數據結構在計算機科學中是一門綜合性的專業(yè)基礎課，也是計算機專業(yè)的必修課，是其它許多課程的先修課程，是設計編譯程序、操作系統(tǒng)、數據庫系統(tǒng)等系統(tǒng)程序和大型應用

5、程序的重要基礎。,1.2 基本概念和術語,基本術語,數據 被計算機加工處理的對象。數據元素（記錄、表目） 數據的基本單位，是數據集合中的一個有意義的個體。數據項 一個數據元素可由若干個數據項組成。,組合項,,原子項,基本術語2,數據對象 是性質相同的數據元素的集合，是數據的一個子集。 學號 姓名 班號 性別 出生日期 入學成績 001 劉影 01 女 19840417

6、 623 002 李恒 01 男 19831211 679 003 陳誠 02 男 19840910 638 … … … … … …數據結構 具有結構的數據元素的集合。它包括數據元素的邏輯結構、存儲結構和相適應的運算。,,,,,,,,,,,,數據元素,,數據元素

7、之間的邏輯關系，與計算機無關。 可用一個二元組表示：Data_Structure = (D,R) D：數據元素的有窮集合，R：集合D上關系的有窮集合。 [例] 設有數據結構 B = (D,R) ， 其中 D= {d1, d2, d3, d4, d5, d6}， R={r}， r={, , , , }， 試畫出其邏輯結構圖。,邏輯結構,（以班級學生關系為例）

8、(1)集合結構 數據元素除了“屬于同一集合”的聯系之外，沒有其它的關系。(2)線性結構 數據元素之間存在一對一的關系。(3)樹型結構 數據元素之間存在一對多的關系。(4)圖狀結構或網狀結構 數據元素之間存在多對多的關系。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,成員關系,長幼關系,管理關系,朋友關系,四種基本的邏輯結構,數據的邏輯結構,存儲結構：數據的邏輯結構在計算機中如何表示。數

9、據元素的映象 用二進制位(bit)的位串表示數據元素。 每個數據元素的映象稱為結點 每個數據項的映象稱為數據域關系的映象兩種基本方法及其組合使用。順序映象：以相對的存儲位置表示關系鏈式映象：以附加信息(指針)表示關系在不同的編程環(huán)境下，存儲結構有不同的描述方式。用高級程序語言編程時，直接用其提供的數據類型描述。,存儲結構,(1)順序存儲：數據元素依次放在連續(xù)的存儲單元中。

10、 a1 a2 ... ai ... an (2)鏈式存儲：在存儲結點中增加若干指針域，記錄后繼或者相關結點的地址（指針）。 a1 1220 ... a3 1342 ... a21072 ...,,,,,,,,,,1000 1004,,,,,,,,,,,,1000 1004

11、 1072 1076 1220 1224,,,,,指針,,,,,結點,,,,,,結點,順序存儲和鏈式存儲,,運算（操作）：在數據邏輯結構上定義的一組數據被使用的方式，其具體實現要在存儲結構上進行。幾種常用的運算有： (1)建立數據結構 (6)檢索* (2)清除數據結構 (7)更新 (3)插

12、入數據元素 (8)判空和判滿* (4)刪除數據元素 (9)求長* (5)排序 *操作為引用型操作，即數據值不發(fā)生變化； 其它為加工型操作。,數據運算,抽象數據類型 ADT（ Abstract Data Type ）： 數據類型概念的引伸。指一個數學模型以及在其上定義的操作集合，與計算機無關。 數據類型：一組值的集合和定義在其上的一組操作的

13、總稱。ADT的特點：將它的使用和實現分離，提高軟件復用程度。 原子類型 固定聚合類型：值由確定數目的成分構成 結構類型 可變聚合類型：值的成分數目不確定,,,抽象數據類型,數據的邏輯結構+運算的定義-------面向用戶，需求分析 （抽象數據類型）

14、 概念層 數據的存儲結構+運算的實現-------面向計算機 實現層,,數據的邏輯結構與存儲結構,其中基本操作的定義格式為:,ADT 抽象數據類型名 { 數據對象：〈數據對象的定義〉 數據關系：〈數據關系的定義〉 基本操作：〈基本

15、操作的定義〉} ADT 抽象數據類型名,基本操作名（參數表） 初始條件：〈初始條件描述〉 操作結果：〈操作結果描述〉,抽象數據類型的描述方法,參數賦值參數 只為操作提供輸入值。引用參數 除可提供輸入值外，還將返回該參數值在操作后的變化結果初始條件 描述了操作執(zhí)行之前數據結構和參數應滿足的條件，若不滿足，則操作失敗，并返回相應出錯信息。操作結果 說明了操作正常完成之后，數據結構的變化狀況和應返回的結果。,,抽象數

16、據類型的描述方法（續(xù)）,1.3 抽象數據類型的表示與實現,1.4 算法和算法分析,算法的概念 建立在數據結構基礎上的、求解問題的一系列確切的步驟。一個算法必須滿足以下五個重要特性有窮性：對任何合法輸入執(zhí)行有窮步后能結束。確定性：每條指令必須有確切的含義?？尚行裕核惴ǖ拿恳粭l指令均能執(zhí)行。輸入：有零個或多個輸入。輸出：有一個或多個輸出。,算法的概念和特性,,正確性(Correctness)算法應滿足具

17、體問題的需求對于典型的、苛刻而帶有刁難性的一組有效輸入得到正確的結果可讀性(Readability)算法應該好讀。以有利于閱讀者對程序的理解。健壯性(Robustness) 算法應具有容錯處理。當輸入非法數據時，算法應對其作出反應，而不是產生莫名其妙或隨機的輸出結果。高效性(Efficiency)算法效率的度量時間復雜度空間復雜度,評價算法優(yōu)劣的基本標準,算法效率的度量,時間復雜度空間復雜度,算法執(zhí)行的時間,事

18、后統(tǒng)計的方法先運行依據算法的程序所得時間的統(tǒng)計量依賴于計算機的硬件、軟件等環(huán)境因素收集此算法的執(zhí)行時間和實際占用空間的統(tǒng)計資料事前分析估算的方法求出該算法的一個時間界限函數；,時間復雜度,n問題規(guī)模，一般為數據的輸入量f(n)算法中基本操作重復執(zhí)行的次數—頻度是問題規(guī)模n的某個函數算法的時間量度、時間復雜度算法中各語句的頻度之和T(n)T(n)=O( f(n) )隨問題規(guī)模的增大，算法執(zhí)行時間的增長率和f(n)

19、的增長率相同O的含義 存在正的常數c和n0，使得當n ? n0時， 0? T(n) ? c* f(n),時間復雜度計算,例1： x++; s = 0;將x++看成是基本操作，語句頻度為１T(n)=2算法的時間復雜度：O(1)---常量階例2: for (i = 0; i<n; i++) { //執(zhí)行n+1次 x++;

20、 //語句頻度為：n　 s += x; //語句頻度為：n　 } T(n)=2n+n+1=3n+1算法的時間復雜度為：O(n)---線性階,時間復雜度計算2,例3: 矩陣相乘C=AxB for (i =0; i < n; i++)//n+1 for (j = 0; j < n; j++) {

21、 //n*(n+1) c[i][j] = 0;//n2 for (k = 0; k <n; k++) //n2 *(n+1) c[i][j] += a[i][k] * b[k][j]; //n3 }T(n)= 2n3 +3n2+2n+1算法的時間復雜度：O(n3),時間復雜

22、度計算3,在難以精確計算基本操作執(zhí)行次數的情況下，只求出關于n的增長率即可。例4: for (i = 2; i <= n; ++i) for (j = 2; j <= i - 1; ++j){ ++x; a[i][j]=x;}算法的時

23、間復雜度：O(n2),時間復雜度計算4,算法中基本操作重復執(zhí)行的次數隨問題的輸入數據集不同而不同例5：在數組A[n]查找給定值K(1) i=n-1;(2) while ( i>=0 && A[i]!=K ) (3) i=i-1;(4) RETURN(i);最好情況的時間復雜度 T(n)=O(1) 最壞情況的時間復雜度 T(n)=O(n)

24、 平均時間復雜度：所有可能的輸入實例以等概率出現的情況 T(n)=(1+2+...+n)/n算法的時間復雜度：O(n),時間復雜度曲線,常見的時間復雜度： O(1), O(log2n), O(n), O(n log2n), O(n2), O(n3), O(2n)O(1)<O(log2n)＜O(n)＜O(nlog2n)＜(n2)＜O(n3)＜＜O(2n),空間復雜度,算法所需存儲空間的度量記作：S