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

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

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

3、—解答。其中建立數(shù)學(xué)模型的實質(zhì)：找出操作對象之間的關(guān)系。例1.圖書館書目檢索——對應(yīng)線性關(guān)系例2.博奕樹——對應(yīng)樹型關(guān)系例3.交叉路口交通燈管理——對應(yīng)圖狀結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算非數(shù)值計算的程序設(shè)計問題中計算機的操作對象及它們之間的關(guān)系和操作操作對象及它們之間的關(guān)系和操作等的學(xué)科。（地位）1.21.2數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語1.1.數(shù)據(jù)（數(shù)據(jù)（DataData））數(shù)據(jù)是描述客觀事物的數(shù)值、字符以及

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

5、jectObject）數(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′，表11所示的學(xué)籍表也可看作一個數(shù)據(jù)對象。由此可看出，不論數(shù)據(jù)元素集合是無限集（如整數(shù)集）、有限集（如字符集），還是由多個數(shù)據(jù)項組成的復(fù)合數(shù)據(jù)元素（如學(xué)籍表），只要性質(zhì)相同，都是同一個數(shù)據(jù)對象。綜上綜上1~31~

6、3所述，再分析數(shù)據(jù)概念：所述，再分析數(shù)據(jù)概念：3數(shù)據(jù)類型數(shù)據(jù)類型(Data(DataType)Type)數(shù)據(jù)類型是一組性質(zhì)相同的值集合以及定義在這個值集合上的一組操作的總稱數(shù)據(jù)類型是一組性質(zhì)相同的值集合以及定義在這個值集合上的一組操作的總稱。數(shù)據(jù)類型中定義了兩個集合，即該類型的取值范圍，以及該類型中可允許使用的一組運算。例如高級語言中的數(shù)據(jù)類型就是已經(jīng)實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)的實例。從這個意義上講，數(shù)據(jù)類型是高級語言中允許的變量種類，是程序語言

7、中已經(jīng)實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)（即程序中允許出現(xiàn)的數(shù)據(jù)形式）。在高級語言中，整型類型可能的取值范圍是32768~32767，可用的運算符集合為加、減、乘、除、取模（如C語言中，，，，%）。抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型１）數(shù)據(jù)的抽象計算機中使用的是二進制數(shù)，匯編語言中則可給出各種數(shù)據(jù)的十進制表示，如98.65、9.6E3等它們是二進制數(shù)據(jù)的抽象使用者在編程時可以直接使用不必考慮實現(xiàn)細節(jié)。在高級語言中，則給出更高一級的數(shù)據(jù)抽象，出現(xiàn)了數(shù)據(jù)類型，如整型、

8、實型、字符型等。到抽象數(shù)據(jù)類型出現(xiàn)，可以進一步定義更高級的數(shù)據(jù)抽象，如各種表、隊、棧、樹、圖、窗口、管理器等，這種數(shù)據(jù)抽象的層次為設(shè)計者提供了更有利的手段，使得設(shè)計者可以從抽象的概念出發(fā)，從整體考慮，然后自頂向下、逐步展開，最后得到所需結(jié)果?？梢赃@樣看，高級語言中提供整型、實型、字符、記錄、文件、指針等多種數(shù)據(jù)類型，可以利用這些類型構(gòu)造出像棧、隊列、樹、圖等復(fù)雜的抽象數(shù)據(jù)類型。２）２）抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(Abstract(Abst

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

10、據(jù)對象，數(shù)據(jù)對象中各元素間的結(jié)構(gòu)關(guān)系，以及一組處理數(shù)據(jù)的操作。ADT通常是指由用戶定義且用以表示應(yīng)用問題的數(shù)據(jù)模型，通常由基本的數(shù)據(jù)類型組成，并包括一組相關(guān)服務(wù)操作。抽象數(shù)據(jù)類型是近年來計算機科學(xué)中提出的最重要的概念之一，它集中體現(xiàn)了程序設(shè)計中一些最基本的原則：分解、抽象和信息隱藏。一個抽象數(shù)據(jù)類型確定了一個模型，但將模型的實現(xiàn)細節(jié)隱藏起來；它定義了一組運算，但將運算的實現(xiàn)過程隱藏起來。數(shù)學(xué)模型→抽象數(shù)據(jù)類型→數(shù)據(jù)結(jié)構(gòu)，恰好反應(yīng)了信息結(jié)

11、構(gòu)轉(zhuǎn)換的三個重要階段，而在這個轉(zhuǎn)換過程中，數(shù)據(jù)結(jié)構(gòu)是基礎(chǔ)，抽象數(shù)據(jù)類型是中樞。一個線性表的抽象數(shù)據(jù)類型的描述如下：ADTLinearlist數(shù)據(jù)元素所有ai屬于同一數(shù)據(jù)對象，i=1，2，…，nn≥0；邏輯結(jié)構(gòu)所有數(shù)據(jù)元素ai（i=1，2，…，n1）存在次序關(guān)系，ai無前趨，an無后繼；操作操作設(shè)L為Linearlist:Initial(L):初始化空線性表Length(L):求線性表的表長Get(Li):取線性表的第i個元