第一章 數據結構緒論
基本概念和術語
數據
描述客觀事物的符號，計算機中可以操作的對象，能被計算機識別并輸入給計算機處理的符號的集合。包括整型、實型等數值類型和字符、聲音、圖像、視頻等非數值類型。
數據元素
組成數據的、有一定意義的基本單位，在計算機中通常作為整體處理。也被稱為記錄。
- 例如：禽類的數據元素為雞、鴨、鵝等。
數據項
一個數據元素可以由若干個數據項組成，數據項是數據不可分割的最小單位。
- 例如：對于人這個數據元素，可以有眼、耳、嘴、鼻等數據項，也可以有姓名、年齡、性別等數據項，具體選取哪些數據項視所構建的系統決定。
數據對象
是性質相同的數據元素的集合，是數據的子集。其中“性質相同”指數據元素具有相同數量和類型的數據項。通常將數據對象簡稱為數據。
數據結構
是相互之間存在一種或多種特定關系的數據元素的集合。計算機中的數據元素并不是孤立、雜亂無序的，而是具有內在聯系的數據集合。
邏輯結構與物理結構
邏輯結構
是指數據對象中數據元素之間的相互關系。
用示意圖表示數據的邏輯結構時：
- 將每一個數據元素看作一個節點，用圓圈表示；
- 元素之間的邏輯關系用節點之間的連線表示，如果這個關系是有方向的，那么用帶箭頭的連線表示。
集合結構
集合結構中的數據元素除了同屬于一個集合外，互相之間沒有其他關系。
線性結構
線性結構中數據元素之間是一對一的關系。
樹形結構
樹形結構中數據元素之間存在一種一對多的層次關系。
圖形結構
圖形結構的數據元素是多對多的關系
物理結構(存儲結構)
物理結構是指數據的邏輯結構在計算機中的存儲形式。數據的存儲結構應正確反映數據元素之間的邏輯關系，如何存儲數據元素之間的邏輯關系是實現物理結構的重點和難點。
順序存儲結構
把數據元素存放在地址連續的存儲單元里，其數據間的邏輯關系和物理關系是一致的。如數組。
數據結構中經常會需要添加新的數據元素、去掉舊的數據元素，面對這種時刻變化的情況，順序結構不夠科學。
鏈式存儲結構
鏈式存儲結構把數據元素存放在任意的存儲單元里，這組存儲單元可以是連續的，也可以是不連續的。數據元素的存儲關系并不能反應其邏輯關系，需要用一個指針存放數據元素的地址，這樣通過地址就可以找到相關聯的數據元素的位置。
邏輯結構是面向問題的，物理結構則是面向計算機的，其基本目標就是將數據及其邏輯關系存儲到計算機的內存中。
抽象數據類型
數據類型
數據類型是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱。例如在高級語言中，每個變量、常量和表達式都有各自的取值范圍，類型就用來說明變量或表達式的取值范圍和所能進行的操作。
在C語言中，按照取值的不同，數據類型可以分成兩類：
- 原子類型：是不可以再分解的基本類型，包括整型、實型、字符型等；
- 結構類型：由若干個類型組合而成，是可以再分解的。例如。整型數組是由若干整型數據組成的。
抽象數據類型
對已有數據類型進行抽樣，就得到了抽象數據類型。
抽象數據類型(Abstract Data Type, ADT)是指一個數學模型及定義在該模型上的一組操作。抽象數據類型的定義僅取決于它的一組邏輯特性，與其在計算機內部如何表示和實現無關。
例如各種計算機，無論是超算、PC、平板、智能手機等，都擁有“整數”類型，也需要整數間的運算，那么整型就是一個抽象數據類型，盡管它在上面提到的各種計算機中的實現方法可能不一樣，但由于其定義的數學特征相同，在編程者看來，它們就是相同的。因此，抽象的意義在于數據類型的數學抽象特性。
抽象數據類型體現了程序設計中問題分解、抽象和信息隱藏的特性。抽象數據類型把實際生活中的問題分解為多個規模小且容易處理的問題，然后建立一個計算機能處理的數據模型，并把每個功能模塊的實現細節作為一個獨立的單元，從而使具體實現過程隱藏起來。
這里給出描述抽象數據類型的標準格式：
ADT 抽象數據類型名
Data數據元素之間邏輯關系的定義
Operation 操作1初始條件操作結果描述操作2......操作n......
endADT總結回顧
數據結構相關概念
數據結構定義
數據結構是相互之間存在一種或多種特定關系的數據元素的集合。
數據結構分類
抽象數據類型及其描述方法
ADT 抽象數據類型名
Data數據元素之間邏輯關系的定義
Operation 操作1初始條件操作結果描述操作2......操作n......
endADT
