《數據結構》講義

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

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

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

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

5、jectObject）數據對象是性質相同的數據元素的集合，是數據的一個子集。數據對象是性質相同的數據元素的集合，是數據的一個子集。例如：整數數據對象是集合N=0，1，2，…，字母字符數據對象是集合C=′A′，′B′，…，′Z′，表11所示的學籍表也可看作一個數據對象。由此可看出，不論數據元素集合是無限集（如整數集）、有限集（如字符集），還是由多個數據項組成的復合數據元素（如學籍表），只要性質相同，都是同一個數據對象。綜上綜上1~31~

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

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

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

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

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

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