數(shù)據(jù)結構-數(shù)據(jù)結構的一般概念

大綱：

掌握數(shù)據(jù)結構的基本概念和術語玛追。

了解抽象數(shù)據(jù)類型的概念。

掌握算法的特性闲延，算法的描述和算法的分析痊剖。

數(shù)據(jù)結構的基本概念

數(shù)據(jù)：所有能被輸入到計算機中并被處理的符號的集合
數(shù)據(jù)元素：數(shù)據(jù)的基本單位，通常做一個整體考慮
數(shù)據(jù)項：構成數(shù)據(jù)元素的不可分割的最小單位垒玲，一個數(shù)據(jù)元素由若干數(shù)據(jù)項組成
數(shù)據(jù)對象：相同性質的數(shù)據(jù)元素的集合陆馁，是數(shù)據(jù)的一個子集
數(shù)據(jù)類型：一個值的集合和定義在這個集合上的一組操作的總稱
5.1 原子類型：值不可以再分的數(shù)據(jù)類型
5.2 結構類型：值可以再分解成若干的數(shù)據(jù)類型
5.3 抽象數(shù)據(jù)類型：抽象數(shù)據(jù)組織和與之相關的操作
抽象數(shù)據(jù)類型（ADT）：一個數(shù)學模型以及定義在該模型上的一組操作，其定義只與邏輯特性有關合愈，通常采用（數(shù)據(jù)對象叮贩，數(shù)據(jù)關系，基本操作集）這樣的三元組來表示抽象數(shù)據(jù)類型
數(shù)據(jù)結構：相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合佛析。包括：邏輯結構益老、存儲結構和數(shù)據(jù)的運算

邏輯結構指數(shù)據(jù)元素之間的邏輯關系

數(shù)據(jù)的邏輯結構分類圖

存儲結構指數(shù)據(jù)結構在計算機中的表示寸莫，也稱物理結構

順序存儲：把邏輯上相鄰的元素存儲在物理位置上也相鄰的存儲單元里捺萌，通過存儲單元的鄰接關系來表示元素之間的邏輯關系
- 優(yōu)點：實現(xiàn)隨機存儲，每個元素占用空間小
- 缺點：只能使用相鄰的一整塊存儲單元储狭，會產(chǎn)生較多外部碎片
鏈式存儲：不要求邏輯上相鄰的元素在物理位置上也相鄰互婿，通過指針表示元素之間的邏輯關系
- 優(yōu)點：不會出現(xiàn)碎片現(xiàn)象，充分利用所有的存儲單元
- 缺點：每個元素要存儲指針辽狈，需要多占用部分存儲空間慈参，而且只能順序存取
索引存儲：存儲信息的同時，建立附加的索引表刮萌，索引表中每一項稱為索引項驮配，索引項一般形式是：（關鍵字，地址）
- 優(yōu)點：檢索速度快
- 缺點：增加了索引表着茸，占用較多存儲空間壮锻，增刪數(shù)據(jù)時也要修改索引表，花費較多時間
散列存儲：根據(jù)元素的關鍵字直接計算出該元素的存儲地址涮阔，也稱Hash存儲
- 優(yōu)點：檢索猜绣，增刪結點操作都很快
- 缺點：散列函數(shù)不好可能會出現(xiàn)元素存儲單元的沖突，解決沖突會增加時間敬特、空間的開銷

算法對特定問題求解步驟的一種描述掰邢，它是指令的有限序列，其中每一條指令都表示一個或多個操作

算法效率的度量通過時間復雜度和空間復雜度來描述

時間復雜度：算法中所有語句的頻度（指該語句在算法中被重復執(zhí)行的次數(shù)）之和記作T(n)伟阔，時間復雜度主要分析T(n)的數(shù)量級辣之。算法中基本運算（最深層循環(huán)內(nèi)的語句）的頻度與T(n)同數(shù)量級，所以一般采用算法中基本運算的頻度f(n)來分析算法時間復雜度皱炉。即T(n)=O(f(n))
- 常見的漸進時間復雜度：
  
  O(1) < O(log?n) < O(n) < O(nlog?n) < O(n2) < O(n3) < O(2?) < O(n!) < O(n?)
空間復雜度：算法耗費的存儲空間怀估，記作S(n)=O(g(n))
- 算法原地工作指算法所需輔助空間是常量，即O(1)

最后編輯于：2019.07.20 16:56:46

?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者