何謂數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是在整個計算機(jī)科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語。它用來反映一個數(shù)據(jù)的內(nèi)部構(gòu)成，即一個數(shù)據(jù)由那些成分?jǐn)?shù)據(jù)構(gòu)成，以什么方式構(gòu)成，呈什么結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu)和物理上的數(shù)據(jù)結(jié)構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)在計算機(jī)內(nèi)部的存儲安排。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。

數(shù)據(jù)結(jié)構(gòu)是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對應(yīng)，通過這組算法集合可以對數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行某種操作。

數(shù)據(jù)結(jié)構(gòu)主要研究什么？

數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及對數(shù)據(jù)的各種操作。因此，主要有三個方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的物理存儲結(jié)構(gòu)；對數(shù)據(jù)的操作(或算法)。通常，算法的設(shè)計取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實現(xiàn)取決于數(shù)據(jù)的物理存儲結(jié)構(gòu)。

什么是數(shù)據(jù)結(jié)構(gòu)？什么是邏輯結(jié)構(gòu)和物理結(jié)構(gòu)？

數(shù)據(jù)是指由有限的符號(比如，"0"和"1"，具有其自己的結(jié)構(gòu)、操作、和相應(yīng)的語義)組成的元素的集合。結(jié)構(gòu)是元素之間的關(guān)系的集合。通常來說，一個數(shù)據(jù)結(jié)構(gòu)DS 可以表示為一個二元組：

DS=(D,S), //i.e., data-structure=(data-part,logic-structure-part)

這里D是數(shù)據(jù)元素的集合(或者是“結(jié)點”，可能還含有“數(shù)據(jù)項”或“數(shù)據(jù)域”)，S是定義在D(或其他集合)上的關(guān)系的集合，S = { R | R : D×D×...}，稱之為元素的邏輯結(jié)構(gòu)。

邏輯結(jié)構(gòu)有四種基本類型：集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹狀結(jié)構(gòu)和網(wǎng)絡(luò)結(jié)構(gòu)。表和樹是最常用的兩種高效數(shù)據(jù)結(jié)構(gòu)，許多高效的算法可以用這兩種數(shù)據(jù)結(jié)構(gòu)來設(shè)計實現(xiàn)。表是線性結(jié)構(gòu)的(全序關(guān)系)，樹(偏序或?qū)哟侮P(guān)系)和圖(局部有序(weak/local orders))是非線性結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)是指邏輯結(jié)構(gòu)的存儲鏡像(image)。數(shù)據(jù)結(jié)構(gòu) DS 的物理結(jié)構(gòu) P 對應(yīng)于從 DS 的數(shù)據(jù)元素到存儲區(qū)M(維護(hù)著邏輯結(jié)構(gòu)S)的一個映射：

P:(D,S) --> M

存儲器模型：一個存儲器 M 是一系列固定大小的存儲單元，每個單元 U 有一個唯一的地址 A(U)，該地址被連續(xù)地編碼。每個單元 U 有一個唯一的后繼單元 U'=succ(U)。

P 的四種基本映射模型：順序(sequential)、鏈接(linked)、索引(indexed)和散列(hashing)映射。

因此，我們至少可以得到4×4種可能的物理數(shù)據(jù)結(jié)構(gòu)：

??? sequential	(sets)
??? linked	lists
??? indexed	trees
??? hash	graphs

(并不是所有的可能組合都合理)

數(shù)據(jù)結(jié)構(gòu)DS上的操作：所有的定義在DS上的操作在改變數(shù)據(jù)元素(節(jié)點)或節(jié)點的域時必須保持DS的邏輯和物理結(jié)構(gòu)。

DS上的基本操作：任何其他對DS的高級操作都可以用這些基本操作來實現(xiàn)。最好將DS和他的所有基本操作看作一個整體——稱之為模塊。我們可以進(jìn)一步將該模塊抽象為數(shù)據(jù)類型(其中DS的存儲結(jié)構(gòu)被表示為私有成員，基本操作被表示為公共方法)，稱之為ADT。作為ADT，堆棧和隊列都是一種特殊的表，他們擁有表的操作的子集。

對于DATs的高級操作可以被設(shè)計為(不封裝的)算法，利用基本操作對DS進(jìn)行處理。

好的和壞的DS：如果一個DS可以通過某種“線性規(guī)則”被轉(zhuǎn)化為線性的DS(例如線性表)，則稱它為好的DS。好的DS通常對應(yīng)于好的(高效的)算法。這是由計算機(jī)的計算能力決定的，因為計算機(jī)本質(zhì)上只能存取邏輯連續(xù)的內(nèi)存單元，因此如何沒有線性化的結(jié)構(gòu)邏輯上是不可計算的。比如對一個圖進(jìn)行操作，要訪問圖的所有結(jié)點，則必須按照某種順序來依次訪問所有節(jié)點(要形成一個偏序)，必須通過某種方式將圖固有的非線性結(jié)構(gòu)轉(zhuǎn)化為線性結(jié)構(gòu)才能對圖進(jìn)行操作。

樹是好的DS——它有非常簡單而高效的線性化規(guī)則，因此可以利用樹設(shè)計出許多非常高效的算法。樹的實現(xiàn)和使用都很簡單，但可以解決大量特殊的復(fù)雜問題，因此樹是實際編程中最重要和最有用的一種數(shù)據(jù)結(jié)構(gòu)。樹的結(jié)構(gòu)本質(zhì)上有遞歸的性質(zhì)——每一個葉節(jié)點可以被一棵子樹所替代，反之亦然。實際上，每一種遞歸的結(jié)構(gòu)都可以被轉(zhuǎn)化為(或等價于)樹形結(jié)構(gòu)。

總結(jié)

以上是生活随笔為你收集整理的数据结构定义的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。