數(shù)據(jù)相關(guān)的名詞解釋

數(shù)據(jù)：能輸入到計算機中并被計算機程序處理的符號的總稱

數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，由若干個數(shù)據(jù)項組成

數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集

數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，其中的關(guān)系稱之為"結(jié)構(gòu)"

數(shù)據(jù)元素的邏輯結(jié)構(gòu)

結(jié)構(gòu)類型和數(shù)據(jù)元素之間的關(guān)系特點：

集合

線性結(jié)構(gòu)：1對1

樹形結(jié)構(gòu)：1對多

圖狀結(jié)構(gòu)/網(wǎng)狀結(jié)構(gòu)：多對多

數(shù)據(jù)元素的物理結(jié)構(gòu)/存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu)

鏈式存儲結(jié)構(gòu)

數(shù)據(jù)類型

?原子類型：不可分解的，如基本類型，指針，空類型等

結(jié)構(gòu)類型：可分解的，如數(shù)組等

抽象數(shù)據(jù)類型（ADT）

抽象，是抽取出事物具有的普遍性的本質(zhì)。它是抽出問題的特征而忽略非本質(zhì)的細節(jié)，是對具體事物的一個概括。抽象是一種思考問題的方式，它隱藏繁雜的細節(jié)，只保留實現(xiàn)目標所必需的信息

抽象數(shù)據(jù)類型，是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。例如，我們在編寫計算機繪圖軟件系統(tǒng)時，經(jīng)常會使用到坐標。也就是說，會經(jīng)常使用 xy 來描述橫縱坐標，而在 3D 系統(tǒng)中，z深度就會出現(xiàn)。既然這 3 個整型數(shù)字是始終出現(xiàn)在一起。那就可以定義成一個 Point 的抽象數(shù)據(jù)類型。它有 xyz 三個整型變量。這樣開發(fā)者就非常方便操作Point 數(shù)據(jù)變量

抽象數(shù)據(jù)類型分為以下幾種：

原子類型

固定聚合類型

可變聚合類型

算法概念

算法就是解決特定向題求解步驟的描述，在計算機中表現(xiàn)為指令的有限序列，并且每個指令表示一個或多個操作

算法的特性：

有窮性

確定性

可行性

輸入

輸出

算法的設(shè)計要求：

正確性

可讀性

健壯性

效率與低存儲量需求

算法效率的量度：漸進時間復(fù)雜度

常數(shù)階

對數(shù)階

線性階

nlogn階

平方階

立方階

指數(shù)階

時間復(fù)雜度排行：O(1) < O(log n) < O(n) < O(nlog n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

算法存儲空間的量度：空間復(fù)雜度

算法的空間復(fù)雜度通過計算算法所需的存儲空間實現(xiàn)，算法空間復(fù)雜度的計算公式記做：S(n) = n(f (n)) ，其中 n 為問題的規(guī)模，f(n) 為語句關(guān)于 n 所占存儲空間的函數(shù)