一、數據結構到底是什么
數據結構是相互之間存在一種或多種特定關系的數據元素的集合。
數據結構包括三方面的內容:邏輯結構、存儲結構和數據的運算。數據的邏輯結構和存儲結構是密不可分的兩個方面,一個算法的設計取決于所選定的邏輯結構,而算法的實現依賴于所采用的存儲結構。
邏輯結構和物理結構(存儲結構)
1.邏輯結構
1)定義
邏輯結構是指數據對象中數據元素之間相互關系(邏輯關系),即從邏輯關系上描述數據。它與數據的存儲無關,是獨立于計算機存儲器的。
2)分類(線性結構和非線性結構)
根據數據元素之間關系的不同特征,通常有下列4類基本結構,復雜程度依次遞進。
①集合:結構中的數據元素之間除了同屬于一個集合外,沒有其他的關系。
②線性結構:線性結構中的數據元素之間是一對一的關系。
③樹形結構:樹形結構中的數據元素之間是一對多的關系。
④圖狀結構或網狀結構:結構中的元素之間是多對多的關系。
2.物理結構(存儲結構)
1)定義
數據的物理結構是指數據的邏輯結構在計算機中的存儲方式。又稱存儲結構。
它研究的是數據結構在計算機中的實現方法,包括數據元素的表示和元素之間的關系。
數據元素的存儲結構形式主要有兩種:順序存儲和鏈式存儲
2)順序存儲和鏈式存儲
①順序存儲結構
是利用數據元素在存儲器中的相對位置來表示數據元素之間的邏輯順序。
順序存儲結構是把數據元素放在地址連續的存儲單元中,程序設計中使用數組類型來實現。(邏輯相鄰物理相鄰)
②鏈式存儲結構
利用結點中指針來表示數據元素之間的關系。
把數據元素存儲在任意的存儲單元里,這組存儲單元可以是連續的,也可以是連續的,程序設計中使用指針類型來實現。(邏輯相鄰物理不一定相鄰)
3)其他存儲方式
索引存儲:類似于目錄,以后可以聯系操作系統的文件系統章節來理解。
散列存儲:通過關鍵字直接計算出元素的物理地址。
抽象數據類型
1.定義
①數據類型:是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱。
例如:C語言中數據類型分為基本類型和構造類型
基本類型:整型、浮點型、字符型等
構造類型:數組、結構、聯合、指針、枚舉型、自定義類型等
②抽象數據類型(abstract data type,ADT):是指一個數學模型及定義在該模型上的一組操作。
延伸閱讀:
二、散列(哈希)存儲結構
就是根據數據元素的關鍵字通過哈希函數計算出一個數值用做數據元素的存儲地址,優點在于查找速度快,只需要給出關鍵字可立即計算出該數據元素的地址 特點是指存儲數據元素不存儲數據之間的邏輯關系,只適合進行快速查找和插入的場合。