數(shù)據(jù)結(jié)構(gòu)講義

1、數(shù)據(jù)結(jié)構(gòu),第一章 緒論,本章主要內(nèi)容,學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》的意義基本概念和術(shù)語(yǔ)算法的描述和分析,1.1 什么是數(shù)據(jù)結(jié)構(gòu),圖書(shū)的基本信息登記號(hào)，書(shū)名，作者，分類編號(hào)，出版單位，出版時(shí)間作者簡(jiǎn)介，內(nèi)容簡(jiǎn)介，等等。操作檢索，排序，等等數(shù)據(jù)之間的關(guān)系線性關(guān)系數(shù)據(jù)表示和算法操作的設(shè)計(jì)與需求有關(guān)數(shù)據(jù)的邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)，算法操作邏輯結(jié)構(gòu)是客觀事物特性的一種抽象存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)的計(jì)算機(jī)實(shí)現(xiàn)算法操作是基于存儲(chǔ)結(jié)構(gòu)的操作，反

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

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

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

5、程序的重要基礎(chǔ)。,1.2 基本概念和術(shù)語(yǔ),基本術(shù)語(yǔ),數(shù)據(jù) 被計(jì)算機(jī)加工處理的對(duì)象。數(shù)據(jù)元素（記錄、表目） 數(shù)據(jù)的基本單位，是數(shù)據(jù)集合中的一個(gè)有意義的個(gè)體。數(shù)據(jù)項(xiàng) 一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。,組合項(xiàng),,原子項(xiàng),基本術(shù)語(yǔ)2,數(shù)據(jù)對(duì)象 是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。 學(xué)號(hào) 姓名 班號(hào) 性別 出生日期 入學(xué)成績(jī) 001 劉影 01 女 19840417

6、 623 002 李恒 01 男 19831211 679 003 陳誠(chéng) 02 男 19840910 638 … … … … … …數(shù)據(jù)結(jié)構(gòu) 具有結(jié)構(gòu)的數(shù)據(jù)元素的集合。它包括數(shù)據(jù)元素的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和相適應(yīng)的運(yùn)算。,,,,,,,,,,,,數(shù)據(jù)元素,,數(shù)據(jù)元素

7、之間的邏輯關(guān)系，與計(jì)算機(jī)無(wú)關(guān)。 可用一個(gè)二元組表示：Data_Structure = (D,R) D：數(shù)據(jù)元素的有窮集合，R：集合D上關(guān)系的有窮集合。 [例] 設(shè)有數(shù)據(jù)結(jié)構(gòu) B = (D,R) ， 其中 D= {d1, d2, d3, d4, d5, d6}， R={r}， r={, , , , }， 試畫(huà)出其邏輯結(jié)構(gòu)圖。,邏輯結(jié)構(gòu),（以班級(jí)學(xué)生關(guān)系為例）

8、(1)集合結(jié)構(gòu) 數(shù)據(jù)元素除了“屬于同一集合”的聯(lián)系之外，沒(méi)有其它的關(guān)系。(2)線性結(jié)構(gòu) 數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。(3)樹(shù)型結(jié)構(gòu) 數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。(4)圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,成員關(guān)系,長(zhǎng)幼關(guān)系,管理關(guān)系,朋友關(guān)系,四種基本的邏輯結(jié)構(gòu),數(shù)據(jù)的邏輯結(jié)構(gòu),存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中如何表示。數(shù)

9、據(jù)元素的映象 用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素。 每個(gè)數(shù)據(jù)元素的映象稱為結(jié)點(diǎn) 每個(gè)數(shù)據(jù)項(xiàng)的映象稱為數(shù)據(jù)域關(guān)系的映象兩種基本方法及其組合使用。順序映象：以相對(duì)的存儲(chǔ)位置表示關(guān)系鏈?zhǔn)接诚螅阂愿郊有畔?指針)表示關(guān)系在不同的編程環(huán)境下，存儲(chǔ)結(jié)構(gòu)有不同的描述方式。用高級(jí)程序語(yǔ)言編程時(shí)，直接用其提供的數(shù)據(jù)類型描述。,存儲(chǔ)結(jié)構(gòu),(1)順序存儲(chǔ)：數(shù)據(jù)元素依次放在連續(xù)的存儲(chǔ)單元中。

10、 a1 a2 ... ai ... an (2)鏈?zhǔn)酱鎯?chǔ)：在存儲(chǔ)結(jié)點(diǎn)中增加若干指針域，記錄后繼或者相關(guān)結(jié)點(diǎn)的地址（指針）。 a1 1220 ... a3 1342 ... a21072 ...,,,,,,,,,,1000 1004,,,,,,,,,,,,1000 1004

11、 1072 1076 1220 1224,,,,,指針,,,,,結(jié)點(diǎn),,,,,,結(jié)點(diǎn),順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ),,運(yùn)算（操作）：在數(shù)據(jù)邏輯結(jié)構(gòu)上定義的一組數(shù)據(jù)被使用的方式，其具體實(shí)現(xiàn)要在存儲(chǔ)結(jié)構(gòu)上進(jìn)行。幾種常用的運(yùn)算有： (1)建立數(shù)據(jù)結(jié)構(gòu) (6)檢索* (2)清除數(shù)據(jù)結(jié)構(gòu) (7)更新 (3)插

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

13、總稱。ADT的特點(diǎn)：將它的使用和實(shí)現(xiàn)分離，提高軟件復(fù)用程度。 原子類型 固定聚合類型：值由確定數(shù)目的成分構(gòu)成 結(jié)構(gòu)類型 可變聚合類型：值的成分?jǐn)?shù)目不確定,,,抽象數(shù)據(jù)類型,數(shù)據(jù)的邏輯結(jié)構(gòu)+運(yùn)算的定義-------面向用戶，需求分析 （抽象數(shù)據(jù)類型）

14、 概念層 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)+運(yùn)算的實(shí)現(xiàn)-------面向計(jì)算機(jī) 實(shí)現(xiàn)層,,數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu),其中基本操作的定義格式為:,ADT 抽象數(shù)據(jù)類型名 { 數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉 數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉 基本操作：〈基本

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

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

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

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

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

20、 //語(yǔ)句頻度為：n　 s += x; //語(yǔ)句頻度為：n　 } T(n)=2n+n+1=3n+1算法的時(shí)間復(fù)雜度為：O(n)---線性階,時(shí)間復(fù)雜度計(jì)算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算法的時(shí)間復(fù)雜度：O(n3),時(shí)間復(fù)雜

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

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

24、 平均時(shí)間復(fù)雜度：所有可能的輸入實(shí)例以等概率出現(xiàn)的情況 T(n)=(1+2+...+n)/n算法的時(shí)間復(fù)雜度：O(n),時(shí)間復(fù)雜度曲線,常見(jiàn)的時(shí)間復(fù)雜度： 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),空間復(fù)雜度,算法所需存儲(chǔ)空間的度量記作：S