第一章緒論

1.1 什么是數據結構

數據結構是一門研究非數值計算的程序設計問題中，計算機的操作對象以及他們之間的關系和操作的學科。

面向過程程序=數據結構+算法

數據結構是介于數學、計算機硬件、計算機軟件三者之間的一門核心課程。

數據結構是程序設計、編譯、數據庫、操作系統的基礎。

1.2 基本概念和術語

數據 data：對客觀事物的符號表示，在計算機中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。

數據對象 data object：性質相同的數據元素的集合，是數據的一個子集。

數據元素 data element：數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。

一個數據元素可以由若干個數據項(data item)組成，數據項是不可分割的最小單位。

數據結構 data structure：相互之間存在一種或多種特定關系的數據元素的集合。

?

數據元素相互之間的關系稱為結構(structure)。

集合

線性結構 ?一對一

樹形結構 ?一對多

圖狀結構/網狀結構 ?多對多

?

數據結構的形式定義（邏輯結構）：

數據結構是一個二元組

其中：D是數據元素的有限集，S是D上關系的有限集。

?

物理結構/存儲結構：數據結構在計算機中的表示（映像），包括數據元素的表示和關系的表示。

數據元素 <--> 元素(element)/結點(node)

? ?數據項 <--> 數據域(data field)

?

數據元素之間的關系在計算機中有兩種不同的表示方法：

順序映像 --> 順序存儲結構 ? ?借助元素在存儲器中的相對位置來表示數據元素之間的邏輯關系。

非順序映像 --> 鏈式存儲結構 ? ?借助指示元素存儲地址的指針(pointer)表示數據元素之間的邏輯關系。

?

邏輯結構 --> 算法設計

物理結構 --> 算法實現

?

數據類型 data type：是一個值的集合?和定義在這個值集上的一組操作的總稱。

按值得類型，可將數據類型分為兩類：

原子類型

結構類型

在某種意義上，數據結構可以看成是“一組具有相同結構的值”；

則結構類型可以看成由一種數據結構和定義在其上的一組操作組成。

軟件系統的框架應建立在數據之上，而不是建立在操作之上。即，面向對象。

?

抽象數據類型 Abstract Data Type，簡稱ADT：是指一個數學模型以及定義在該模型上的一組操作。

??|--值域：

??????|--原子類型 atomic data type ? ?原子類型的變量值是不可分解的，如基本數據類型

??????|--固定聚合類型 fixed-aggregate data type ? ?其值由確定數目的成分由某種結構組成，如復數

??????|--可變聚合類型:表、樹、圖 variable-aggregate data type ? ?值的數目不確定

??????|--多形數據類型 ploymorphic data type ? ?多型數據類型，就是泛型，如Triplet

??|--操作

?

抽象數據類型可用以下三元組表示：

? ? ? ? ? ? ? ? ? ? ? ? ??

其中：D是數據對象，S是D上的關系集，P是對D的基本操縱。

?

基本操作有兩種參數：

賦值參數--只為操作提供輸入值；

引用參數--以&打頭，為操作提供輸入值，并且返回操作結果。

?

1.4 算法和算法分析

算法：有窮性、確定性、可行性、輸入、輸出

設計要求：正確性、可讀性、健壯性、時間復雜度、空間復雜度

?

算法效率的度量：

一個特定算法的運行工作量的大小，只依賴于問題的規模n，即它是問題規模n的函數。

一個算法是由控制語句（順序、選擇、循環）和原操作（固有數據類型的操作）構成的，算法的時間取決于兩者的綜合效果。

最深層循環內的語句中的原操作

T(n) = O(f(n))

隨問題規模n的增大，算法執行時間的增長率和f(n)的增長率相同，稱作算法的漸進時間復雜度（asymptotic time complexity）,簡稱時間復雜度。

最壞情況下的時間復雜度。

??常量階

??對數階

??線性階

??平方階

??指數階

?

算法的存儲空間需求：

空間復雜度（space complexity）

若額外空間相對于輸入數據量來說是常數，則稱此算法為原地工作。

?