1、第一章：緒論課程 課程：數(shù)據(jù)結(jié)構(gòu)課題 課題：第一章 1.1—1.4 小節(jié)（共 4 個課時）1.1 什么是數(shù)據(jù)結(jié)構(gòu)1.2 基本概念和術語1.3 抽象數(shù)據(jù)類型的表現(xiàn)與實現(xiàn)1.4 算法和算法分析目的要求 目的要求：理解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項的概念；掌握邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的關系；理解算法的基本概念；學會分析算法的時間復雜性和空間復雜性。新課重點、難點 新課重點、難點：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、時間復雜性和空間復雜性教學方法 教學方法：課堂講解、

2、例題演示，課件演示教學內(nèi)容及過程 教學內(nèi)容及過程：……………………………第 1-2 課時……………………………計算機的應用不再局限于科學計算，更多地用于控制，管理，數(shù)據(jù)處理等非數(shù)值計算的處理工作。計算機加工處理的對象：數(shù)值，字符，表格，圖形聲音，圖象等具有一定結(jié)構(gòu)的數(shù)據(jù)。進行程序設計時必須分析待處理的對象的特性及各對象之間存在的關系———產(chǎn)生背景。1.1 1.1 什么是數(shù)據(jù)結(jié)構(gòu) 什么是數(shù)據(jù)結(jié)構(gòu) 計算機解題步驟：建立數(shù)學模型——設計解此數(shù)

3、學模型的算法——編制程序——進行測試調(diào)整——解答。其中建立數(shù)學模型的實質(zhì)：找出操作對象之間的關系。例 1. 圖書館書目檢索 ——對應線性關系例 2. 博奕樹 ——對應樹型關系例 3. 交叉路口交通燈管理 ——對應圖狀結(jié)構(gòu)。 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算 非數(shù)值計算的程序設計問題中計算機的操作對象及它們之間的關系和操作 操作對象及它們之間的關系和操作等的學科。（地位） 1.2 1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念和術語 數(shù)據(jù)結(jié)構(gòu)的基本概念和

4、術語 1. 1. 數(shù)據(jù)（ 數(shù)據(jù)（Data Data） ）數(shù)據(jù)是描述客觀事物的數(shù)值、字符以及能輸入機器且能被處理的各種符號集合。換句話說，數(shù)據(jù)是對客觀事物采用計算機能夠識別、存儲和處理的形式所進行的描述；是計算機加工處理的對象。包括數(shù)值、字符、聲音、圖象等。 2. 2. 數(shù)據(jù)元素（ 數(shù)據(jù)元素（Data Data Element Element） ）數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位, 是數(shù)據(jù)集合的個體，在計算機中通常作為一個邏輯整體

5、進行考慮和處理。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成（Data Item） 。 3. 3. 數(shù)據(jù)對象（ 數(shù)據(jù)對象（Data Data Object Object）數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。 數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如：整數(shù)數(shù)據(jù)對象是集合 N={0， ±1， ±2， …}，字母字符數(shù)據(jù)對象是集合 C={′A′，′B′，…，′Z′}，表 1-1 所示的學籍表也可看

6、作一個數(shù)據(jù)對象。由此可看出，不論數(shù)據(jù)元素集合是無限集（如整數(shù)集） 、有限集（如字符集） ，還是由多個數(shù)據(jù)項組成的復合數(shù)據(jù)元素（如學籍表） ，只要性質(zhì)相同， 都是同一個數(shù)據(jù)對象。 綜上 綜上 1~3 1~3 所述，再分析數(shù)據(jù)概念： 所述，再分析數(shù)據(jù)概念： 構(gòu)。 構(gòu)。 數(shù)據(jù)類型 數(shù)據(jù)類型(Data (Data Type) Type)數(shù)據(jù)類型是一組性質(zhì)相同的值集合以及定義在這個值集合上的一組操作的總稱 數(shù)據(jù)類型是一組性質(zhì)相同的值集合以及定義

7、在這個值集合上的一組操作的總稱。數(shù)據(jù)類型中定義了兩個集合，即該類型的取值范圍，以及該類型中可允許使用的一組運算。例如高級語言中的數(shù)據(jù)類型就是已經(jīng)實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)的實例。 從這個意義上講，數(shù)據(jù)類型是高級語言中允許的變量種類， 是程序語言中已經(jīng)實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)（即程序中允許出現(xiàn)的數(shù)據(jù)形式） 。在高級語言中，整型類型可能的取值范圍是-32 768~+32 767， 可用的運算符集合為加、 減、 乘、 除、 取模（如 C 語言中+， -， *

8、， /， %） 。 抽象數(shù)據(jù)類型 抽象數(shù)據(jù)類型 １） 數(shù)據(jù)的抽象計算機中使用的是二進制數(shù)，匯編語言中則可給出各種數(shù)據(jù)的十進制表示，如 98.65、 9.6E3 等, 它們是二進制數(shù)據(jù)的抽象; 使用者在編程時可以直接使用, 不必考慮實現(xiàn)細節(jié)。在高級語言中，則給出更高一級的數(shù)據(jù)抽象，出現(xiàn)了數(shù)據(jù)類型， 如整型、 實型、字符型等。到抽象數(shù)據(jù)類型出現(xiàn)，可以進一步定義更高級的數(shù)據(jù)抽象，如各種表、隊、棧、樹、圖、窗口、管理器等，這種數(shù)據(jù)

9、抽象的層次為設計者提供了更有利的手段，使得設計者可以從抽象的概念出發(fā)，從整體考慮，然后自頂向下、逐步展開，最后得到所需結(jié)果?？梢赃@樣看，高級語言中提供整型、實型、字符、記錄、文件、指針等多種數(shù)據(jù)類型，可以利用這些類型構(gòu)造出像棧、隊列、樹、圖等復雜的抽象數(shù)據(jù)類型。 ２） ２） 抽象數(shù)據(jù)類型 抽象數(shù)據(jù)類型 (Abstract (Abstract Data Data Type) Type)抽象數(shù)據(jù)類型（簡稱 ADT）是指基于一類邏輯關系的數(shù)

10、據(jù)類型以及定義在這個類型之上的一組操作。抽象數(shù)據(jù)類型的定義取決于客觀存在的一組邏輯特性，而與其在計算機內(nèi)如何表示和實現(xiàn)無關，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學特性不變，都不影響其外部使用。從某種意義上講，抽象數(shù)據(jù)類型和數(shù)據(jù)類型實質(zhì)上是一個概念。整數(shù)類型就是一個簡單的抽象數(shù)據(jù)類型實例?！俺橄蟆钡囊饬x在于教學特性的抽象。一個 ADT 定義了一個數(shù)據(jù)對象，數(shù)據(jù)對象中各元素間的結(jié)構(gòu)關系，以及一組處理數(shù)據(jù)的操作。ADT 通常是指由用戶定義且用

11、以表示應用問題的數(shù)據(jù)模型，通常由基本的數(shù)據(jù)類型組成，并包括一組相關服務操作。 抽象數(shù)據(jù)類型是近年來計算機科學中提出的最重要的概念之一，它集中體現(xiàn)了程序設計中一些最基本的原則：分解、抽象和信息隱藏。 一個抽象數(shù)據(jù)類型確定了一個模型，但將模型的實現(xiàn)細節(jié)隱藏起來；它定義了一組運算，但將運算的實現(xiàn)過程隱藏起來。 數(shù)學模型→抽象數(shù)據(jù)類型→數(shù)據(jù)結(jié)構(gòu)，恰好反應了信息結(jié)構(gòu)轉(zhuǎn)換的三個重要階段，而在這個轉(zhuǎn)換過程中，數(shù)據(jù)結(jié)構(gòu)是基礎，抽象數(shù)據(jù)類型是中樞。 一

12、個線性表的抽象數(shù)據(jù)類型的描述如下： ADT Linear-list數(shù)據(jù)元素 所有 ai 屬于同一數(shù)據(jù)對象，i=1，2，…，n, n≥0；邏輯結(jié)構(gòu) 所有數(shù)據(jù)元素 ai（i=1，2，…，n-1）存在次序關系，ai 無前趨，an 無后繼； 操作 操作 設 L 為 Linear-list:Initial(L): 初始化空線性表;Length(L): 求線性表的表長;Get(L, i): 取線性表的第 i 個元素；

13、 Insert(L, i, b): 在線性表的第 i 個位置插入元素 b； Delete(L, i): 刪除線性表的第 i 個元素。３） ３） 抽象數(shù)據(jù)類型實現(xiàn) 抽象數(shù)據(jù)類型實現(xiàn) 第一種情況： 傳統(tǒng)的面向過程的程序設計。第二種情況： “包” 、 “模型”的設計方法。第三種情況： 面向?qū)ο蟮某绦蛟O計（Object Oriented Programming，簡稱 OOP） 。 ４） ４） ADT ADT 的定義 的定義ADT 的