資料結構是資訊的組織方式。對於相同的演算法，用不同的資料結構表示其中的抽象資料型別會造成不同的執行效率。這就有必要研究各種抽象資料型別用不同的資料結構表示的效率差異，以及其適用場合。
何謂資料結構
資料結構是在整個電腦科學與技術領域上廣泛被使用的術語。它用來反映乙個資料的內部構成，即乙個資料由那些成分資料構成，以什麼方式構成，呈什麼結構。資料結構有邏輯上的資料結構和物理上的資料結構之分。
邏輯上的資料結構反映成分資料之間的邏輯關係，而物理上的資料結構反映成分資料在計算機內部的儲存安排。資料結構是資料存在的形式。
資料是指由有限的符號（比如，"0"和"1"，具有其自己的結構、操作、和相應的語義）組成的元素的集合。結構是元素之間的關係的集合。通常來說，乙個資料結構ds 可以表示為乙個二元組：
ds=(d,s), data-structure=(data-part,logic-structure-part)
這裡d是資料元素的集合（或者是「結點」，可能還含有「資料項」或「資料域」），s是定義在d（或其他集合）上的關係的集合，s = ，稱之為元素的邏輯結構。
邏輯結構有四種基本型別：集合結構、線性結構、樹狀結構和網路結構。表和樹是最常用的兩種高效資料結構，許多高效的演算法可以用這兩種資料結構來設計實現。
表是線性結構的（全序關係），樹(偏序或層次關係)和圖（區域性有序(weak/local orders)）是非線性結構。
資料結構的物理結構是指邏輯結構的儲存映象(image)。資料結構 ds 的物理結構 p 對應於從 ds 的資料元素到儲存區m（維護著邏輯結構s）的乙個對映：
p:(d,s) --> m
儲存器模型：乙個儲存器 m 是一系列固定大小的儲存單元，每個單元 u 有乙個唯一的位址 a(u)，該位址被連續地編碼。每個單元 u 有乙個唯一的後繼單元 u'=succ(u)。
p 的四種基本對映模型：順序（sequential）、鏈結（linked）、索引（indexed）和雜湊（hashing）對映。
因此，我們至少可以得到4×4種可能的物理資料結構：
（並不是所有的可能組合都合理）
資料結構ds上的操作：所有的定義在ds上的操作在改變資料元素（節點）或節點的域時必須保持ds的邏輯和物理結構。
ds上的基本操作：任何其他對ds的高階操作都可以用這些基本操作來實現。最好將ds和他的所有基本操作看作乙個整體——稱之為模組。
我們可以進一步將該模組抽象為資料型別（其中ds的儲存結構被表示為私有成員，基本操作被表示為公共方法），稱之為adt。作為adt，堆疊和佇列都是一種特殊的表，他們擁有表的操作的子集。
對於dats的高階操作可以被設計為（不封裝的）演算法，利用基本操作對ds進行處理。
好的和壞的ds：如果乙個ds可以通過某種「線性規則」被轉化為線性的ds（例如線性表），則稱它為好的ds。好的ds通常對應於好的（高效的）演算法。
這是由計算機的計算能力決定的，因為計算機本質上只能訪問邏輯連續的記憶體單元，因此如何沒有線性化的結構邏輯上是不可計算的。比如對乙個圖進行操作，要訪問圖的所有結點，則必須按照某種順序來依次訪問所有節點（要形成乙個偏序），必須通過某種方式將圖固有的非線性結構轉化為線性結構才能對圖進行操作。
樹是好的ds——它有非常簡單而高效的線性化規則，因此可以利用樹設計出許多非常高效的演算法。樹的實現和使用都很簡單，但可以解決大量特殊的複雜問題，因此樹是實際程式設計中最重要和最有用的一種資料結構。樹的結構本質上有遞迴的性質——每乙個葉節點可以被一棵子樹所替代，反之亦然。
實際上，每一種遞迴的結構都可以被轉化為（或等價於）樹形結構。
公式化描述借助數學公式來確定元素表中的每個元素分別儲存在何處，也就通過公式計算元素的儲存器位址。最簡單的情形就是把所有元素依次連續儲存在一片連續的儲存空間中，這就是通常所說的連續線性表，即陣列。複雜一點的情形是利用複雜的函式關係根據元素的某些特徵來計算元素在記憶體中的位置，這種技術稱為雜湊技術(hash，經常音譯為雜湊技術)。
在鏈結描述中，元素表中的每個元素可以儲存在儲存器的不同區域中，每個元素都包含乙個指向下乙個元素的指標。這就是通常所說的鍊錶。這種描述方法的好處是，知道了第乙個元素的位置，就可以依次找到第n個元素的位置，而且在其中插入元素非常方便，缺點是查詢某個元素要遍歷所有在該元素之前的元素，實際應用中經常和公式化描述結合起來使用。
在間接定址方式中，元素表中的每個元素也可以儲存在儲存器的不同區域中，不同的是，此時必須儲存一張表，該錶的第i項指向元素表中的第i個元素，所以這張表是乙個用來儲存元素位址的表。指標陣列（元素為指標的陣列）就是這種描述法的應用。這種描述方法是公式化描述和鏈結描述的一種折衷方案，同時具有兩種描述方法的優點，但是需要額外的記憶體開銷。
模擬指標非常類似於鏈結描述，區別在於它用整數代替了指標，整數所扮演的角色與指標所扮演的角色完全相同。模擬指標的描述方式是鏈結描述和公式化描述的結合，元素被儲存在不同的區域中，每個元素包含乙個指示下乙個元素位置的整數，可以通過某種公式由該整數計算出下乙個元素的儲存器位址。線性表的游標實現就是模擬指標描述法。
資料結構概念
線性表的特徵 1 有且僅有乙個開始結點 表頭結點 a1，它沒有直接前驅，只有乙個直接後繼 2 有且僅有乙個終端結點 表尾結點 an，它沒有直接後繼，只有乙個直接前驅 3 其它結點都有乙個直接前驅和直接後繼 4 元素之間為一對一的線性關係。在順序儲存結構中為 o 1 在鏈式儲存結構中為 o n 棧 先...
資料結構基礎概念
第一章緒論 程式設計的一般過程是 問題 想法 演算法 程式 其實質是資料表示和資料處理。資料結構是研究非數值問題中計算機的操作物件以及它們之間關係和操作的學科。資料元素是資料的基本單位，在電腦程式中通常作為乙個整體進行考慮和處理。資料項是資料的最小單位，資料元素是討論資料結構時涉及的最小資料單位。從...
資料結構與拓撲資料結構
資料結構在gis中對於資料的採集 儲存 查詢 檢索和應用分析等操作方式有著重要的影響，一種高效率的資料結構應該具備以下幾個要求 1 組織的資料能夠表示要素之間的層次關係，便於不同資料聯絡於覆蓋 2 正確反映地理實體之間的空間排列方式和各實體之間的相互關係 3 便於訪問與檢索 4 節省儲存空間，減少資...