1、數(shù)據(jù)結構的基本概念,秦臻 寬帶光纖傳輸與通信系統(tǒng)技術教育部重點實驗室 Key Laboratory of Broadband Optical Fiber Transmission and Communication Networks,制作：段景山 廖丹 秦臻 主講：秦臻,Outline,數(shù)據(jù)結構定義 數(shù)據(jù)的邏輯結構 數(shù)據(jù)的存儲結構 算法,Outline,數(shù)據(jù)結構定義 數(shù)據(jù)的邏輯結構 數(shù)據(jù)的存儲結構 算法,什么是數(shù)據(jù)結構,Niklaus Wirth :算法十數(shù)據(jù)結構=程序(Algorithms Data Structures Programs，Prentice-Hall，1976) 什么是程序？

2、 什么是算法？ 什么是數(shù)據(jù)結構？,數(shù)據(jù)結構,數(shù)據(jù)結構的概念 數(shù)據(jù)及數(shù)據(jù)元素的概念 數(shù)據(jù)是客觀事物在計算機內的抽象描述 數(shù)據(jù)指一些事實，或一些數(shù)，或一些符號集合 組成數(shù)據(jù)的“事實”、“數(shù)值”或“符號”稱為數(shù)據(jù)元素 數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成,數(shù)據(jù)及數(shù)據(jù)元素,例1、學生花名冊,數(shù)據(jù)元素,數(shù)據(jù),學生名字的集合,每個學生的名字,例2、學生成績表,數(shù)據(jù),數(shù)據(jù)元素,數(shù)據(jù)項,學生成績的集合,每個學生的成績,名字,成績,數(shù)據(jù)結構的概念,數(shù)據(jù)結構的概念 數(shù)據(jù)結構討論計算機系統(tǒng)中數(shù)據(jù)的組織形式及其相互關系 是相互之間存在一種和多種特定關系的數(shù)據(jù)元素的集合,例：大樓中的電梯,電梯在樓層中只能逐層移動,例：公司的組

3、織關系,樓層間的關系是線性的,員工間形成樹型關系,涉及,元素的集合,元素間的關系,在關系里的操作,電梯的運動,人員的管理,例：用數(shù)據(jù)結構描述整數(shù)I*,1、組成整數(shù)數(shù)據(jù)的全部元素的集合I I 0，1，2，3,2、I中元素的關系集合RE,3、I*的運算集合P，比如算術四則運算,4、P中諸運算的運算規(guī)則RU， 如乘、除法優(yōu)先于加、減法等,I* I，RE，P，RU,數(shù)據(jù)結構的概念,RE -10,01,12,數(shù)據(jù)結構的概念,例：用數(shù)據(jù)結構的思想分析以下實物： 一個十字路口的紅綠燈管制 包含兩部電梯的管理系統(tǒng) 一條公交路線 成都市公交系統(tǒng),元素 關系 運算,數(shù)據(jù)結構的概念,元素集合,元素間的關系,運算,計

4、 算 機 系 統(tǒng),元素在計算機系統(tǒng)里的表示 字符？字串？整數(shù)？ 元素間的邏輯關系邏輯結構 元素在計算機系統(tǒng)中的存儲方式，物理空間關系存儲結構 操作指令的集合 算法,數(shù)據(jù)的邏輯結構與數(shù)據(jù)的存儲結構,例：班級里的同學,可能有各種各樣的邏輯關系。比如班長、班委、群眾等。形成相應的邏輯結構。,上課時，大家的座次形成存儲結構,座次（存儲結構）可能與邏輯關系有關，也可能無關。,數(shù)據(jù)結構的概念,此外，數(shù)據(jù)的運算也是數(shù)據(jù)結構不可分割的一個方面,Outline,數(shù)據(jù)結構定義 數(shù)據(jù)的邏輯結構 數(shù)據(jù)的存儲結構 算法,數(shù)據(jù)的邏輯結構 數(shù)據(jù)元素之間關系的描述 描述法 二元組 關系：一般抽象為前驅與后繼關系， 即表明結構

5、中，一個元素的前一個元素是誰，它的后一個元素又是誰,B （ K， R ）,K：元素集合,R：元素間關系的集合,數(shù)據(jù)的邏輯結構,圖示法 圖形要素： 結點和有向線段 結點：表示一個數(shù)據(jù)元素，一般以方形框代表 不管多么復雜的結點，都看作是一個結點 有向線段：表示元素之間的關系。 箭尾指向的結點是前驅。 箭頭指向的結點是后繼,K i,K h,K j,Ki的前驅,Ki的后繼,數(shù)據(jù)的邏輯結構,研究為什么一個結點是 另一個結點的前驅或后繼,數(shù)據(jù)的邏輯結構,線性結構 線性表 隊列 堆棧 非線性結構 樹 圖 集合結構,Outline,數(shù)據(jù)結構定義 數(shù)據(jù)的邏輯結構 數(shù)據(jù)的存儲結構 算法,數(shù)據(jù)的存儲結構（物理結構）

6、 是數(shù)據(jù)元素在計算機系統(tǒng)存儲器中的存放方式 也可以說，是數(shù)據(jù)邏輯結構在存儲器中的存放方式,數(shù)據(jù)的存儲結構,存儲器的特點：由地址連續(xù)的單元構成,K1,K2,K3,K4,數(shù)據(jù)的存儲結構,邏輯結構,K1,K2,K3,K4,K5,K6,數(shù)據(jù)的存儲結構,邏輯結構,數(shù)據(jù)的存儲結構,思考：為什么數(shù)據(jù)邏輯結構與物理結構沒有完全統(tǒng)一？,存儲器的特點：由地址連續(xù)的單元構成。線性關系,單元間的線性關系有時不能直接反映復雜的邏輯關系,幾種物理存儲方式 順序存儲方法 連續(xù)順序地存放數(shù)據(jù)元素 若數(shù)據(jù)的邏輯結構也是順序（線性）的，則邏輯結構和物理結構完全統(tǒng)一了 連續(xù)存放的數(shù)據(jù)元素可以在內存中容易找到,數(shù)據(jù)的存儲結構,鏈接存

7、儲方法 元素在內存中不一定連續(xù)存放 在元素中附加指針項，通過指針可以找到關系元素,元素指針,結點,元素,指針,數(shù)據(jù)的存儲結構,K1,K2,K3,K4,K5,K6,數(shù)據(jù)的存儲結構,邏輯結構,索引存儲方法 為放在內存中的元素建立索引表 元素可以離散存放 通過查索引表找到需要的元素,數(shù)據(jù)的存儲結構,散列存儲方法 結點中設一關鍵值，利用關鍵值和相應算式算出結點位置（地址）,例：以用戶姓名為關鍵值,DJS,算式：字母的序號相加,041019 33,ZXM,262413 63,數(shù)據(jù)的存儲結構,所以，DJS放在33號地址單元 ZXM放在63號地址單元,小結：數(shù)據(jù)的邏輯結構與物理結構 1、物理結構是元素在內存

8、中的存儲方式，與元素間固有的邏輯關系是相對獨立的兩個問題 物理結構著眼于結點在內存中的定位 2、簡單的邏輯結構可能和物理結構一致 例：線性邏輯關系與順序存儲方法 3、利用物理結構在內存中找到一個結點，而為什么要找這個結點卻由元素間的邏輯關系決定 任何一個算法的設計取決于選定的數(shù)據(jù)邏輯結構，而算法的實現(xiàn)依賴于采用的存儲結構 4、邏輯結構與存儲結構是一個問題的兩個方面,數(shù)據(jù)的邏輯結構和存儲結構,Outline,數(shù)據(jù)結構定義 數(shù)據(jù)的邏輯結構 數(shù)據(jù)的存儲結構 算法,算法 算法的概念及特點 算法是為解決某一特定類型問題規(guī)定的運算規(guī)則的有窮集合 有窮性：非無限執(zhí)行，必須在有限步驟內結束 確定性：非二義，下

9、一步必須是明確的 有效性：每一步是可執(zhí)行的 輸入：外部輸入零個或多個 輸出：至少一個,特 點,算法,算法與程序 相似：都是解決問題的方法和步驟，是指令的集合 區(qū)別： 描述方法 聯(lián)系：程序用某種程序設計語言來實現(xiàn)算法,程序使用程序設計語言,算法可以使用框圖及其他語言,算法,要求描述一個算法時必須滿足： 對輸入和輸出的描述 描述語句準確、無二義 保證算法的有窮性和有效性,算法,在數(shù)據(jù)結構中常見的問題 創(chuàng)建、插入、刪除、更新、檢索、排序 注意：每個問題都有一種和多種算法 找到效率最高的，消耗存儲空間最小的 以最容易理解的方式設計 設計的算法不容易出錯或出錯情況較少,算法,數(shù)據(jù)結構研究什么,數(shù)據(jù)之間的

10、邏輯關系，建模 數(shù)據(jù)的存儲，如何在計算機中儲存 如何高效的處理數(shù)據(jù)，算法的設計,一些補充內容,在其它一些參考文獻中使用的一些常見概念，作一些簡單的描述，方便閱讀相關資料： ADT 時間復雜度 空間復雜度,ADT,抽象數(shù)據(jù)類型（Abstract Data Types簡稱ADT） ADT是指抽象數(shù)據(jù)的組織和與之相關的操作?？梢钥醋魇菙?shù)據(jù)的邏輯結構及其在邏輯結構上定義的操作。 抽象數(shù)據(jù)類型可以看作是描述問題的模型，它獨立于具體實現(xiàn)。它的優(yōu)點是將數(shù)據(jù)和操作封裝在一起，使得用戶程序只能通過在ADT里定義的某些操作來訪問其中的數(shù)據(jù)，從而實現(xiàn)了信息隱藏。 舉例：食堂的隊列如果抽象出來，對外部來說，服務的師傅

11、只需要知道服務隊頭，而隊列內部怎么排的并不需要關心。,時間復雜度,按照不同算法，編寫程序，比較其運行時的時間效率； 需要實際的代碼實現(xiàn)，且受到軟件實現(xiàn)等因素影響，所以一般采用事先對算法進行分析估算； 只考慮問題的規(guī)模（一般用自然數(shù)n表示，例如需要處理的數(shù)據(jù)個數(shù)），認為一個特定的算法的時間復雜度，只取決于問題的規(guī)模，或者說它是問題的規(guī)模的函數(shù)； 為了方便比較，通常的做法是，從算法選取一種對于所研究的問題（或算法模型）來說是基本運算的操作（例如比較），以其重復執(zhí)行的次數(shù)作為評價算法時間 時間復雜度一般用O(f(n)來表示 漸進符號（O）的定義：當且僅當存在一個正的常數(shù) C，使得對所有的 n n0 ，有 f(n) = Cg(n)則 f(n) = O(g(n),空間復雜度,空