[計(jì)算機(jī)軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)第1章緒論(已修改)
2024-10-31 04:11 本頁(yè)面
【正文】 1 什么是數(shù)據(jù)結(jié)構(gòu) 基本概念和術(shù)語(yǔ) 算法和算法分析 第一章 緒 論 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn) 2 什么是數(shù)據(jù)結(jié)構(gòu) 用計(jì)算機(jī)解決具體問(wèn)題的步驟 ： 1. 抽象出一個(gè) 數(shù)學(xué)模型 ； 2. 設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的 算法 ； 3. 編程、測(cè)試、調(diào)整。 尋求數(shù)學(xué)模型： 分析 問(wèn)題 、提取 操作 的 對(duì)象 及其對(duì)象之間的 關(guān)系 并進(jìn)行描述。 數(shù)據(jù)結(jié)構(gòu) 是一門研究 非數(shù)值計(jì)算 的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的 操作對(duì)象 以及它們之間的 關(guān)系和操作的學(xué)科。 3 基本概念 ?數(shù)據(jù) ： ?指所 有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的 符號(hào)的集合 。 ?是計(jì)算機(jī)操作的 對(duì)象的總稱 。 ?數(shù)據(jù)元素 : ?是數(shù)據(jù)結(jié)構(gòu)中討論的 基本 單位。 ?在計(jì)算機(jī)程序中作為一個(gè)“ 整體 ”進(jìn)行考慮。 一 . 數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu) 4 ?數(shù)據(jù)項(xiàng)： ?是數(shù)據(jù)結(jié)構(gòu)中討論的 不可分割 的 最小 單位。 ?數(shù)據(jù)對(duì)象 : ?是 具有相同特性 的數(shù)據(jù)元素的集合，如 :一個(gè)班級(jí)的成績(jī)表可以看作一個(gè)數(shù)據(jù)對(duì)象。它是 數(shù)據(jù) 的一個(gè)子集 。 ?數(shù)據(jù)結(jié)構(gòu)： ?若在特性相同的數(shù)據(jù)元素 集合 中的 數(shù)據(jù)元素 之間存在一種或多種 特定的關(guān)系 ，則稱該數(shù)據(jù)元素的集合為“數(shù)據(jù)結(jié)構(gòu)“。 ?數(shù)據(jù)結(jié)構(gòu) 是帶“ 結(jié)構(gòu) ”的 數(shù)據(jù)元素 的集合。 5 數(shù)據(jù)結(jié)構(gòu)的形式定義為 : 數(shù)據(jù)結(jié)構(gòu) 是一個(gè)二元組 Data_Structures = (D, S) 其中 : D 是 數(shù)據(jù)元素的有限集 ， S 是 D上關(guān)系的有限集。 6 二 . 數(shù)據(jù)類型 在用高級(jí)程序語(yǔ)言編寫的程序中，必須對(duì)程序中出現(xiàn)的每個(gè) 變量、常量或表達(dá)式 ，明確說(shuō)明它們 所屬的數(shù)據(jù)類型 。 【 例 】 C/C++語(yǔ)言中提供的基本數(shù)據(jù)類型有 : 整 型 int 浮 點(diǎn) 型 float 字符型 char 邏輯型 bool （ C++語(yǔ)言） 雙精度型 double 基本概念 7 1. 數(shù)據(jù)類型 是一個(gè)“ 值 ”的集合和定義在此集合上的“ 一組操作 ”的總稱。 例： C++語(yǔ)言中的整型，其內(nèi)涵為一定范圍的自然數(shù)集合，及定義在該集合上的加減乘除及取模等算術(shù)運(yùn)算。 數(shù)據(jù)類型 原子類型 :整型、實(shí)型、字符型等 結(jié)構(gòu)類型 :數(shù)組、結(jié)構(gòu)體 2. 數(shù)據(jù)類型 也可以是看成一個(gè) 數(shù)據(jù)結(jié)構(gòu) 和定義在這個(gè)數(shù)據(jù)結(jié)構(gòu)上一組 操作 的總稱。 的變量，其所能取的 值不同 ，所能進(jìn)行的 操作不同 。 8 三 . 抽象數(shù)據(jù)類型 (Abstract Data Type , ADT) ?抽象數(shù)據(jù)類型： 是指一個(gè) 數(shù)學(xué)模型 以及定義在此數(shù)學(xué)模型上的 一組操作 。 ?即： ADT的定義由一個(gè) 值域 和定義在該值域上的一組 操作 組成。 ?ADT的定義僅取決于 數(shù)據(jù)模型 的 邏輯特征 。 ?ADT和 數(shù)據(jù)類型 實(shí)質(zhì)上是一個(gè)概念。 與其在 計(jì)算機(jī)內(nèi)部 的表示和實(shí)現(xiàn)無(wú)關(guān)。 “抽象 ”的意義在于數(shù)據(jù)類型的 數(shù)學(xué)抽象特性 。 不論內(nèi)部結(jié)構(gòu)如何變化，都 不會(huì)影響外部使用 。 9 例：線性表這樣的抽象數(shù)據(jù)類型。 ? 數(shù)學(xué)模型 ：數(shù)據(jù)元素的集合； ? 該集合內(nèi)的元素的 關(guān)系 ：除第一個(gè)和最后一個(gè)外，每個(gè)元素有唯一的前趨和唯一的后繼； ? 操作 ：插入一個(gè)元素、刪除一個(gè)元素等。 10 抽象數(shù)據(jù)類型不僅僅局限于 固有數(shù)據(jù)類型 ，也包括 用戶自定義的 數(shù)據(jù)類型。 ADT 按照其值的不同特性，分為 4種類型： ?原 子 類 型 ： 其值 不可分解的類型；如： int ?固定聚合類型 ： 其值由確定數(shù)目的成分按某種結(jié)構(gòu)組成；如：復(fù)數(shù)； ?可變聚合類型 ： 其值由不固定數(shù)目的成分按某種結(jié)構(gòu)組成；如：學(xué)生基本情況，有序整數(shù)序列； ?多形數(shù)據(jù)類型 ： 其值的成分不確定的數(shù)據(jù)類型；（元素之間的關(guān)系相同，基本操作也相同 ） 11 ADT 有兩個(gè)重要特征 : 2. 數(shù)據(jù)封裝： 將實(shí)體的 外部特性 和其內(nèi)部 實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。 1. 數(shù)據(jù)抽象： 用 ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其 本質(zhì)的特
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1