廣義數據結構

從字面上來看，廣義數據結構就是指數據問的相互關係。具體到計算機環境時，廣義數據結構，就是由某種邏輯關係組織起來的一批數據，按一定的存儲方法被存儲於計算機中，並在這些數據上定義了一個運算的集合。

基本介紹

• 中文名：廣義數據結構
• 外文名：GDS；generalized data structure
• 實質：指數據問的相互關係
• 常見結構：數組、柞、佇列、鍊表、樹、圖等
• 三個側面：數據的邏輯結構、存儲結構和運算
• 套用領域：計算機科學、教育學、套用經濟學

概述

從字面上來看，廣義數據結構就是指數據問的相互關係。具體到計算機環境，談到任何一種結構時，都自然地聯繫著作用在這種類型的數據上的運算(即函式)，為了在計算機上執行這些運算，我們有必要把這些數據以某種方式存儲在計算機中。因此，我們可以認為，所謂廣義數據結構，就是由某種邏輯關係組織起來的一批數據，按一定的存儲方法被存儲於計算機中，並在這些數據上定義了一個運算的集合。也就是說，數據結構具有三個方面：數據的邏輯結構、數據的存儲結構和數據的運算。

邏輯結構

常見邏輯關係有：線性結構、樹形結構、圖結構和檔案結構。其中，線性結構是最簡單的數據結構，例如，程式設計語言中往往都會介紹的線性表(包括數組和鍊表)、棧、佇列、向量、字元串等。其中，字元串就是每個結點都是單個字元的線性表。實際上多維數組和廣義表也是線性結構的推廣。另外，檔案其本質也是線性結構。不過由於存儲在外存中．對檔案數據的訪問速度非常慢。因此，仔細研究檔案結構和基於檔案的外排序也是很有必要的。

二叉樹和樹是非常重要的數據結構，其套用十分靈活而廣泛。二叉樹可以看作是樹的特例。例如，語言編譯中要用到語法樹，作業系統有目錄樹。資料庫系統需要用索引樹等進行數據管理，而在人工智慧領域，需要用到搜尋樹等。許多真實世界的問題都可以用圖來抽象地定義。例如，一張交通圖可以用數據結構的圖來形象化地表示：用結點表示城市，用邊表示連線城市的高速公路；Web網頁的關係也可以表示為圖：Web網頁作為結點，網頁之間的連結作為邊。圖是一種最通用的邏輯結構，實際上，線性表∈叉樹∈樹∈圖。

存儲結構

常見的存儲方法有：順序方法、連結方法、索引方法、散列方法。其中，索引存儲又分為線性和樹形兩種。檔案結構的索引則往往用樹形結構。

運算

對於一種數據結構，往往需要定義一些運算。例如，建立數據結構，清除數據結構、插入一個新數據元素．刪除某個數據元素、修改某個數據元素、排序、檢索等。作為最常用的算法．排序和檢索歷來是數據結構討論中的重點問題。排序算法最能夠體現算法的魅力，它對算法速度要求非常高，其中內排序主要考慮的是怎樣減少關鍵碼之間的比較次數和記錄交換次數，以提高排序速度。可以證明所有基於比較的排序算法的時間代價是Θ（nIogn），這也是排序問題的時間代價。而外排序則考慮外存的特性，儘量減少訪外操作，以提高排序速度。檢索則考慮怎樣提高檢索速度，這往往是與存儲方法有關的。例如，我們可以利用索引存儲來加快檢索。散列表、B樹和B⁺樹等高效的數據結構都具有極好的檢索性能。

套用領域

數據結構是計算機學科的重要分支研究領域。數據結構和算法在計算機學科中的地位十分重要，其他計算機科學領域及有關的套用軟體都要使用到各種數據結構。數據結構是算法分析與設計、作業系統、軟體工程、資料庫概論、編譯技術、計算機圖形學、人機互動等專業基礎課和專業課程的先行課程。語言編譯要使用棧、散列表及語法樹；作業系統中用佇列、存儲管理表及目錄樹等；資料庫系統運用線性表、多鍊表及索引樹等進行數據管理：而在人工智慧領域，依求解問題性質的差異將涉及到各種不同的數據結構，如廣義表、集合、搜尋樹及各種有向圖等等。

抽象數據類型

事實上，數據結構的三個側面，以數據的邏輯結構和數據的運算定義更為重要。因為很多時候人們並不關心數據的存儲結構和運算的具體實現。1983年Aho等人把數據結構的存儲與實現細節剝離，定義了抽象數據類型(簡稱“ADT“)的概念。抽象數據類型是定義了一組運算的數學模型。例如棧結構，棧中元素的數學特性（即邏輯結構）表現為線性表，它們是有序的；棧的主要運算是進棧(push)、出棧(pop)、判棧空(isEmpty)等。這裡我們並不涉及棧的存儲方式以及棧中元素的類型等。這種抽象的數據類型可以在較高級的算法中直接引用，而不用考慮它的實現細節。這就使得設計者可以在不同的設計階段採用不同的抽象數據類型作為設計的基礎．在適當的抽象層次上考慮程式的結構和算法，從而很好地支持了邏輯設計和物理實現的分離，支持封裝和信息隱蔽。

常用數據結構

數組

在程式設計中，為了處理方便， 把具有相同類型的若干變數按有序的形式組織起來。這些按序排列的同類數據元素的集合稱為數組。在C語言中， 數組屬於構造數據類型。一個數組可以分解為多個數組元素，這些數組元素可以是基本數據類型或是構造類型。因此按數組元素的類型不同，數組又可分為數值數組、字元數組、指針數組、結構數組等各種類別。

棧

是只能在某一端插入和刪除的特殊線性表。它按照先進後出的原則存儲數據，先進入的數據被壓入棧底，最後的數據在棧頂，需要讀數據的時候從棧頂開始彈出數據（最後一個數據被第一個讀出來）。

佇列

一種特殊的線性表，它只允許在表的前端（front）進行刪除操作，而在表的後端（rear）進行插入操作。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。佇列是按照“先進先出”或“後進後出”的原則組織數據的。佇列中沒有元素時，稱為空佇列。

鍊表

是一種物理存儲單元上非連續、非順序的存儲結構，它既可以表示線性結構，也可以用於表示非線性結構，數據元素的邏輯順序是通過鍊表中的指針連結次序實現的。鍊表由一系列結點（鍊表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。

樹

是包含n（n>0）個結點的有窮集合K，且在K中定義了一個關係N，N滿足 以下條件：

（1）有且僅有一個結點 K0，他對於關係N來說沒有前驅，稱K0為樹的根結點。簡稱為根（root）。　 （2）除K0外，K中的每個結點，對於關係N來說有且僅有一個前驅。

（3）K中各結點，對關係N來說可以有m個後繼（m>=0）。

圖

圖是由結點的有窮集合V和邊的集合E組成。其中，為了與樹形結構加以區別，在圖結構中常常將結點稱為頂點，邊是頂點的有序偶對，若兩個頂點之間存在一條邊，就表示這兩個頂點具有相鄰關係。

堆

在計算機科學中，堆是一種特殊的樹形數據結構，每個結點都有一個值。通常我們所說的堆的數據結構，是指二叉堆。堆的特點是根結點的值最小（或最大），且根結點的兩個子樹也是一個堆。

散列表

若結構中存在關鍵字和K相等的記錄，則必定在f(K)的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關係f為散列函式(Hash function)，按這個思想建立的表為散列表。