-
數據結構
(計算機存儲、組織數據方式)
鎖定
數據結構是計算機存儲、組織數據的方式。數據結構是指相互之間存在一種或多種特定關係的數據元素的集合。通常情況下,精心選擇的數據結構可以帶來更高的運行或者存儲效率。數據結構往往同高效的檢索算法和索引技術有關。
[1]
數據結構定義
數據結構(data structure)是帶有結構特性的數據元素的集合,它研究的是數據的邏輯結構和數據的物理結構以及它們之間的相互關係,並對這種結構定義相適應的運算,設計出相應的算法,並確保經過這些運算以後所得到的新結構仍保持原來的結構類型。簡而言之,數據結構是相互之間存在一種或多種特定關係的數據元素的集合,即帶“結構”的數據元素的集合。“結構”就是指數據元素之間存在的關係,分為邏輯結構和存儲結構。
[2]
數據結構的研究內容是構造複雜軟件系統的基礎,它的核心技術是分解與抽象。通過分解可以劃分出數據的3個層次;再通過抽象,捨棄數據元素的具體內容,就得到邏輯結構。類似地,通過分解將處理要求劃分成各種功能,再通過抽象捨棄實現細節,就得到運算的定義。上述兩個方面的結合可以將問題變換為數據結構。這是一個從具體(即具體問題)到抽象(即數據結構)的過程。然後,通過增加對實現細節的考慮進一步得到存儲結構和實現運算,從而完成設計任務。這是一個從抽象(即數據結構)到具體(即具體實現)的過程。
[3]
數據結構研究對象
數據結構數據邏輯結構
數據結構數據物理結構
數據的物理結構是數據結構在計算機中的表示(又稱映像),它包括數據元素的機內表示和關係的機內表示。由於具體實現的方法有順序、鏈接、索引、散列等多種,所以,一種數據結構可表示成一種或多種存儲結構。
[1]
數據元素的機內表示(映像方法): 用二進制位(bit)的位串表示數據元素。通常稱這種位串為節點(node)。當數據元素有若干個數據項組成時,位串中與各個數據項對應的子位串稱為數據域(data field)。因此,節點是數據元素的機內表示(或機內映像)。
[1]
關係的機內表示(映像方法):數據元素之間的關係的機內表示可以分為順序映像和非順序映像,常用兩種存儲結構:順序存儲結構和鏈式存儲結構。順序映像藉助元素在存儲器中的相對位置來表示數據元素之間的邏輯關係。非順序映像藉助指示元素存儲位置的指針(pointer)來表示數據元素之間的邏輯關係。
[1]
數據結構數據存儲結構
數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的物理結構(也稱為存儲結構)。一般來説,一種數據結構的邏輯結構根據需要可以表示成多種存儲結構,常用的存儲結構有順序存儲、鏈式存儲、索引存儲和哈希存儲等。
[4]
數據結構分類
數據結構線性結構
數據結構非線性結構
數據結構常用數據結構
數組(Array)
數組是一種聚合數據類型,它是將具有相同類型的若干變量有序地組織在一起的集合。數組可以説是最基本的數據結構,在各種編程語言中都有對應。一個數組可以分解為多個數組元素,按照數據元素的類型,數組可以分為整型數組、字符型數組、浮點型數組、指針數組和結構數組等。數組還可以有一維、二維以及多維等表現形式。
[5]
棧( Stack)
棧是一種特殊的線性表,它只能在一個表的一個固定端進行數據結點的插入和刪除操作。棧按照先進後出或後進先出的原則來存儲數據,也就是説,先插入的數據將被壓入棧底,最後插入的數據在棧頂,讀出數據時,從棧頂開始逐個讀出。棧在彙編語言程序中,經常用於重要數據的現場保護。棧中沒有數據時,稱為空棧。
[5]
隊列(Queue)
隊列和棧類似,也是一種特殊的線性表。和棧不同的是,隊列只允許在表的一端進行插入操作,而在另一端進行刪除操作。一般來説,進行插入操作的一端稱為隊尾,進行刪除操作的一端稱為隊頭。隊列中沒有元素時,稱為空隊列。
[5]
鏈表( Linked List)
鏈表是一種數據元素按照鏈式存儲結構進行存儲的數據結構,這種存儲結構具有在物理上存在非連續的特點。鏈表由一系列數據結點構成,每個數據結點包括數據域和指針域兩部分。其中,指針域保存了數據結構中下一個元素存放的地址。鏈表結構中數據元素的邏輯順序是通過鏈表中的指針鏈接次序來實現的。
[5]
樹( Tree)
圖(Graph)
堆(Heap)
散列表(Hash)