《數(shù)據(jù)結(jié)構(gòu)》講義

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

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

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

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

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

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

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

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

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

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

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

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

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