數據類型可分為兩類:一類是非結構的原子類型,另一類是結構類型,結構類型的成分可以使非結構的也可以是結構的。
數據結構(data structure)
數據結構是相互之間存在一種或多種特定關系的數據元素的集合。在任何問題中,數據元素之間都不是孤立的,而是存在著一定的關系,這種關系稱為結構(Structure)。根據數據元素之間關系的不同特性,通常有4類基本數據結構:
(1)集合(Set):該結構中數據元素存在“同屬一個集合”的關系外,不存在任何其他關系
(2)線性結構(Linear Structure):該結構中的數據元素存在著一對一的關系。
(3)樹形結構(Tree Structure):該結構中的數據元素存在著一對多的關系。
(4) 圖狀結構(Graphic Structure):該結構中的數據元素存在著多對多的關系。
數據的存儲結構包括順序存儲結構和鏈式存儲結構兩種。
順序存儲結構(Sequence Storage Structure)是通過數據元素在計算機存儲器中的相對位置來表示出數據元素的邏輯關系,一般把邏輯上相鄰的數據元素存儲在物理位置相鄰的存儲單元中。因為數據所分配的存儲空間是連續的,所以數組天生就具有實現數據順序存儲結構的能力。
鏈式存儲結構(Linked Storage Structure)對邏輯上相鄰的數據元素不要求其存儲位置必須相同。鏈式存儲結構中的數據元素稱為結點(Node),在結點中附近設地址域(Address Domain)來存儲與該節點相鄰的結點的地址來實現結點間的邏輯關系。這個地址稱為引用(Reference),這個地址稱為引用域(Reference Domain)。
評價一個算法優劣的主要標准如下:www.2cto.com
1. 正確性 執行結果滿足要求 最重要最基本的標准
2. 可讀性 為了人閱讀和交流
3. 健壯性 具有很強的容錯能力
4. 運行時間
5. 占用空間
通常把算法在運行過程中臨時占用的存儲空間的大小叫算法的空間復雜度(Space Complexity)。算法的空間復雜度比較容易計算,它主要包括局部變量所占用的存儲空間和系統為實現遞歸所使用的堆棧占用的存儲空間。
一個算法的時間復雜度(Time Complexity)是指算法的運行時間與問題規模的對應關系。為了便於比較同一問題的不同算法,通常把算法中的基本操作重復執行的次數(頻度)作為算法的時間復雜度。
如果一個算法沒有循環語句,則算法中基本操作的執行頻度與問題規模n無關,記作O(1),也稱為常數階。如果算法只有一個一重循環,則算法的基本操作的執行頻度與問題規模n呈線性增大關系。記作O(n),也叫線性階。
摘自 xufei96的專欄