黑馬程式設計師：程式設計師必學之大資料資料結構介紹（第一部分）

涉及內容主要有：

1、資料結構（基本概念）

2、資料結構與其他語言關係

3、資料結構與演算法關係

4、資料結構包含的內容

5、資料結構具體實現

目錄：

第一部分：基本概念

第一部分(基本概念)

1

、資料結構

1.1

基本概念

資料：

描述客觀事物的符號，是計算機中可以操作的物件，是能被計算機識別並輸入給計算機處理的符號集合。數值型別（整型、實型等）和非數值型別（字元、聲音、影象等）。

資料物件（記錄）：

是性質相同資料元素的集合，是資料的子集。

資料元素：

組成資料的、有一定含義的

基本單位

，在計算機中通常作為整體處理。

資料項：

一個數據元素由若干個資料項組成。資料項是資料不可分割的最小單位。

資料、資料物件、資料元素、資料項之間關係

1.2

資料結構

資料結構：

是相互之間存在一種或多種特定關係的資料元素的集合。（資料元素+關係）

（程式設計 = 資料結構 + 演算法）

邏輯結構：

是指資料物件中資料元素之間的相互關係。（四種：集合、線性、樹形、圖形）

集合結構：集合結構中的資料元素同屬一個集合外，他們沒有其他關係。元素是平等的。

線性結構：資料元素是一對一的關係。（對應前後）

樹形結構：資料元素之間存在一種一對多的層次關係。

圖形結構：資料元素多對多關係。

物理（儲存）結構：

是指資料的邏輯結構在計算機中的儲存形式。兩種：鏈式儲存，順序儲存。

順序儲存結構：

是把元素存放在地址連續的儲存單元裡，其資料之間的邏輯關係和物理關係是一致的。

鏈式儲存結構：

資料元素存放在任意的儲存單元中，這組儲存單元可以是連續的也可以是不連續的。需指標儲存地址。

資料型別：

是指一組性質相同的值的集合及定義在此集合上的一組操作的總稱。

抽象資料型別：

是指一個數學模型及定義在該模型上的一組操作。（主要指的是邏輯上的，抽象資料型別體現了程式設計中問題分解、抽象和資訊隱藏的特性）

資料結構

2

、與其他語言的關係

資料結構本身與語言無關。（java\c\python等等）

例如：勾股定理。

3

、演算法

解決特定問題求解步驟的描述，在計算機中表現為指令的有限序列，並且每條指令都表示一個或多個操作。此處演算法是為了更好地理解資料結構。（包含演算法特徵、設計要求等）

例子：1+2+3+。。。。+100

方法一、普通計算

int sum=0；

for（int i=1，n=100；i<=n；i++）{

sum+=i；

}

System。out。println（sum）；

方法二、等差數列

int sum=0，n=100；

sum=（1+n）*n/2；

System。out。println（sum）；

時間複雜度：

在進行演算法分析時，語句總執行次數T（n）是關於問題規模n的函式，進而分析T（n）隨n變化情況確定T（n）的數量級。

空間複雜度：

計算演算法所需的儲存空間。

常見時間複雜度比較：

大小關係