數(shù)據(jù)結(jié)構(gòu)--第一章-緒論-文庫(kù)吧
2025-01-03 19:01 本頁(yè)面
【正文】 型、實(shí)型、字符型等， 還可以進(jìn)一步定義更高級(jí)的數(shù)據(jù)抽象，如各種表、隊(duì)、棧、樹、圖、窗口、管理器等復(fù)雜的抽象數(shù)據(jù)類型。 16 抽象數(shù)據(jù)類型 (Abstract Data Type) ? 定義： 抽象數(shù)據(jù)類型（簡(jiǎn)稱 ADT）是指基于一類邏輯關(guān)系的數(shù)據(jù)類型以及定義在這個(gè)類型之上的一組操作 。 一個(gè)抽象數(shù)據(jù)類型確定了一個(gè)模型 ， 但將模型的實(shí)現(xiàn)細(xì)節(jié)隱藏起來；它定義了一組運(yùn)算 ， 但將運(yùn)算的實(shí)現(xiàn)過程隱藏起來 。 數(shù)學(xué)模型 抽象數(shù)據(jù)模型 數(shù)據(jù)結(jié)構(gòu) 非形式算法 偽語言程序 可執(zhí)行程序 用抽象數(shù)據(jù)類型的概念來指導(dǎo)問題的求解過程： 17 抽象數(shù)據(jù)類型 (Abstract Data Type) ? 線性表的抽象數(shù)據(jù)類型的描述 ： ADT Linear_list 數(shù)據(jù)元素 所有 ai屬于同一數(shù)據(jù)對(duì)象 ， i=1， 2， …… ， n n≥ 0； 邏輯結(jié)構(gòu) 所有數(shù)據(jù)元素 ai（ i=1， 2， … ， n1） 存在次序關(guān)系 ai， ai+1， ai無前趨 ， an無后繼； 操作 設(shè) L為 Linear_list Initial(L)初始化空線性表； Length(L)求線性表的表長(zhǎng)； Get(L,i)取線性表的第 i個(gè)元素； Insert(L,i,b)在線性表的第 i個(gè)位置插入元素 b； Delete(L,i)刪除線性表的第 i個(gè)元素； 18 抽象數(shù)據(jù)類型實(shí)現(xiàn) ? 傳統(tǒng)的面向過程的程序設(shè)計(jì) 實(shí)現(xiàn)的三種方法： ?―包 ” 、 “ 模型 ” 的設(shè)計(jì)方法 ?面向?qū)ο蟮某绦蛟O(shè)計(jì) （ Object Oriented Programming，簡(jiǎn)稱 OOP） 19 ADT的表示與實(shí)現(xiàn) ? ADT的定義 ： ADT ADT名 { 數(shù)據(jù)對(duì)象 :數(shù)據(jù)對(duì)象的定義 結(jié)構(gòu)關(guān)系 :結(jié)構(gòu)關(guān)系的定義 基本操作 :基本操作的定義 }ADT ADT名 基本操作的定義格式為： 操作名稱 (參數(shù)表 ) 操作前提 :操作前提描述 操作結(jié)果 :操作結(jié)果描述 20 ? 關(guān)于參數(shù)傳遞 ： 參數(shù)表中的參數(shù)有 值參 和 變參兩種。 用標(biāo)準(zhǔn) C語言表示和實(shí)現(xiàn) ADT描述時(shí)，主要有 兩個(gè)方面 ： 二、 用 C語言函數(shù)實(shí)現(xiàn)各操作。 一、通過結(jié)構(gòu)體將 int、 float等固有類型組合到一起 ,構(gòu)成一個(gè)結(jié)構(gòu)類型 ,再用 typedef為該類型或該類型指針重新起一個(gè)名字。 ADT的表示與實(shí)現(xiàn) 21 面向?qū)ο蟮母拍? ? 面向?qū)ο蟮母拍?： 面向?qū)ο?=對(duì)象 +類 +繼承 +通信 對(duì)象 ： 指在應(yīng)用問題中出現(xiàn)的各種實(shí)體、事件、規(guī)格說明等 。 類 ： 具有相同屬性和服務(wù)的對(duì)象 繼承 ： 是 面向?qū)ο蠓椒ǖ淖钣刑厣姆矫妗? 22 結(jié)構(gòu)化與面向?qū)ο箝_發(fā)方法的不同點(diǎn) ? 結(jié)構(gòu)化的開發(fā)方法 ： 是面向過程的開發(fā)方法，首先著眼于系統(tǒng)要實(shí)現(xiàn)的功能。 ?面向?qū)ο蟮拈_發(fā)方法 ： 首先著眼于應(yīng)用問題所涉及的對(duì)象，包括對(duì)象、對(duì)象屬性和要求的操作，從而建立對(duì)象結(jié)構(gòu)和為解決問題需要執(zhí)行的時(shí)間序列。 23 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容 ? 邏輯結(jié)構(gòu) ? 存儲(chǔ)結(jié)構(gòu) ? 運(yùn)算集合 24 邏輯結(jié)構(gòu) ? 定義： 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間邏輯關(guān)系描述。 ?形式化描述： Data_Structure=（ D,R） 其中 D是數(shù)據(jù)元素的有限集， R是 D上關(guān)系的有限集。 ?四類基本的結(jié)構(gòu) 集合結(jié)構(gòu) 、 線性結(jié)構(gòu) 、 樹型結(jié)構(gòu) 、 圖狀結(jié)構(gòu) 。 25 集合結(jié)構(gòu) ? 定義 ： 結(jié)構(gòu)中的數(shù)據(jù)元素之間除了同屬于一個(gè)集合的關(guān)系外，無任何其它關(guān)系。 集合 例如： 26 線性結(jié)構(gòu) ? 定義： 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著 一對(duì)一的線性關(guān)系 。 例如： 線性表 27 樹型結(jié)構(gòu) ? 定義： 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著 一對(duì)多的層次關(guān)系。 例如： 樹 28 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) ? 定義： 結(jié)構(gòu)中的數(shù)據(jù)元素 之間存在著多對(duì)多的任意關(guān)系。 例如： 圖 29 綜上所述，數(shù)據(jù)的邏輯結(jié)構(gòu)可概括為 ： 線性結(jié)構(gòu) ——線性表、棧、隊(duì)、字符串 數(shù)組、廣義表 邏輯結(jié)構(gòu) 非線性結(jié)構(gòu) ——樹、圖 邏輯結(jié)構(gòu) 30 存儲(chǔ)結(jié)構(gòu) ? 定義： 存儲(chǔ)結(jié)構(gòu)（又稱物理結(jié)構(gòu)）是邏輯結(jié)構(gòu)在計(jì)算機(jī)中存儲(chǔ)映象 ，是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，它包括數(shù)據(jù)元素的表示和關(guān)系的表示。 ?形式化描述： D要存入機(jī)器中，建立
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1