軟件技術(shù)基礎(chǔ)課件-數(shù)據(jù)結(jié)構(gòu)基本概念

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

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

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

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

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

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

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

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

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

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

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