數據結構的基本概念

---

1 基本概念

1.1 數據 Data

在數據結構中，數據是指一切可以被輸入到計算機中并被計算機程序識別和處理的符號的集合。

1.2 數據元素 Data Element

數據元素是數據的基本單位，通常作為一個整體進行考慮和處理。一個數據元素可以由若干個數據項（Data Item）組成，數據項是構成數據元素的不可分割的最小單位。例如，數據庫中一個學生的登記信息就是一個數據元素，它由學號、姓名、性別等數據項組成。

1.3 數據對象 Data Object

數據對象是具有相同性質的數據元素的集合，是數據的一個子集。例如，正整數數據對象$N?=\{1,2,\dots \}$。

1.4 數據類型 Data Structure

數據類型這個概念最早出現在高級程序語言中，用來描述操作對象的特性。例如，C語言中的整形變量、字符型變量以及枚舉類型變量就是三個不同的數據類型。類型顯式或隱式地規定了變量在程序執行期間的所有可能取值范圍，以及在這些值上允許的操作。因此，數據類型是一個值的集合和定義在這個值集上的一組操作的總稱。例如，C語言中的整形變量，其值集為某個區間上的整數（區間大小依賴于不同的機器），定義在其上的操作為：加、減、乘、除等算數運算。

按“值”的不同類型，數據類型可以分為兩類：

• 原子類型（Atomic Data Type）：值不可再分解。如：C語言中的基本類型（整形變量、字符型變量以及枚舉類型變量等）。
• 結構類型（Construction Data Type）：值是由若干成分按某種結構組成的，因此可以分解。這些成分可以是結構類型，也可以是非結構類型。例如數組的值是由若干分量組成的，可以是整數，也可以是另一個數組。

實際上，數據類型的概念并非局限于高級程序語言中，在計算機的各個層面，我們都引入了數據類型的概念。數據庫、高級程序語言、操作系統以及計算機硬件系統中都提供了一組原子類型或結構類型。例如，計算機硬件系統中有“位”、“字節”等原子類型，他們的操作通過計算機設計的一套指令直接由電路系統完成。引入“數據類型”的好處，從硬件角度來說，是作為解釋計算機內存中信息含義的一種手段，而從用戶角度來看，實現了類型的封裝，用戶只需要知道如何操作即可，不需要了解其他細節。但是對于一些更復雜的問題，用這些基本數據類型也不方便解決時，我們可以引入一個新的，更抽象的概念：抽象數據類型。

抽象數據類型（Abstract Data Type 簡稱 ADT） 是指一個數學模型以及定義在該模型上的一組操作。抽象數據類型的定義僅取決于它的一組邏輯特性。常見的例子就是各種高級程序語言中的類。抽象指的是只要這個模型的數學特性不變，那么不管它內部的結構如何變化，都不影響外部的使用。在概念上來說，抽象數據類型和數據類型實質上是一樣的，各種基本數據類型也都滿足抽象數據類型的定義，但是通常我們將所有高級程序語言已定義并實現的數據類型統稱為基本數據類型，剩下的都屬于抽象數據類型。例如用戶在Python自定義一個Car類，這個類就屬于抽象數據類型。

---

2 數據結構

數據結構是相互之間存在一種或多種特定關系的數據元素的集合，數據元素之間的關系被稱為結構（Structure）。各種數據之間的相互關系決定了我們如何去操作、維護和存儲這些數據，因此數據結構主要包括邏輯結構（數據之間的相互關系）、存儲結構（計算機存儲這些數據的方式）以及對這些數據的操作/運算方法。

數據結構的形式定義為：數據結構是一個二元組
$$\mathrm{D}\mathrm{a}\mathrm{t}\mathrm{a}\mathrm{S}\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{c}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{e}=(D,S)$$
其中：$D$是數據元素的有限集，$S$是$D$上的關系的有限集。但是這個定義僅僅是對操作對象的一種數學描述，其中的“關系”僅僅描述了數據元素之間的邏輯關系，沒有體現出數據的存儲和運算。

某種數據采用何種存儲結構以及如何定義操方法是要依照它的邏輯結構來判斷的。換句話說，數據的邏輯結構是從面向實際問題的角度出發的，只采用抽象表達方式，獨立于存儲結構。數據的存儲方式有很多不同的選擇，它不能獨立于邏輯結構而存在。

2.1 邏輯結構

邏輯結構主要描述數據元素之間的邏輯關系，即各種元素在邏輯上是如何被連接在一起的。

數據的邏輯結構可粗略分為線性數據結構和非線性數據結構，可細分為四種結構：線性結構、集合、樹形結構和圖狀結構或網狀結構

• 線性結構：

  • 最常用的數據結構，其特點是數據元素之間只存在一對一的線性關系。
  • 線性結構可以有兩種不同的數據存儲結構：順序存儲和鏈式存儲。順序存儲中的元素一定是連續的；鏈式存儲的元素不一定連續，元素節點中存放數據元素和相鄰元素的地址信息。
  • 常見的線性結構有：數組、隊列、鏈表和棧。

• 非線性結構：

  • 集合：結構中的元素之間除了“同屬一個集合”的關系外，沒有其他關系。
  • 樹形結構：結構中的數據元素之間存在一對多的關系。
  • 圖狀結構或網狀結構：結構中的數據元素之間存在多對多的關系。
    
    

2.2 存儲結構

在規劃好數據的邏輯結構后，我們還需要研究如何在計算機中表示他們。

數據的存儲結構也被稱為物理結構，包括數據元素以及元素之間的關系在計算機中的表示，通俗來說就是計算機如何在物理層面上存儲這些數據。

存儲結構有四種：順序存儲、鏈式存儲、索引存儲和散列存儲。其中順序存儲和鏈式存儲適用于內存結構中，索引存儲和散列存儲使用于外存和內存交互結構。

• 順序存儲

  • 順序存儲把邏輯上相鄰的元素存儲在物理地址上也相鄰的存儲單元中，元素之間的關系由存儲單元之間的臨接關系來體現。
  • 優點：
  • 節省空間：因為順序存儲方法的存儲空間除了存儲有用數據外，沒有用于存儲其他附加的信息，所以順序存儲結構一般也被稱為緊湊存儲結構。
  • 快捷訪問：順序存儲可以用隨機存取實現，順序存儲法又為使用整數編碼訪問數據結點提供了便利。因此對于順序存儲的數據結構我們可以直接使用下標來訪問。
  • 缺點：
  • 不利于數據修改：插入和刪除操作需要移動一系列元素。
  • 只能使用相鄰的一整塊存儲單元，因此可能產生較多的外部碎片。

• 鏈式存儲 ：

  • 鏈式存儲是在結點的存儲結構中附加指針字段來存儲結點間的邏輯關系，不要求邏輯上相鄰的元素在物理位置上也相鄰。鏈接法中數據結點包括兩部分：數據字段存放結點本身的數據，指針字段存放指向其后繼結點的指針。
  • 優點：
  • 方便修改：對數據元素的插入、刪除運算時，隨機存儲不必移動結點，只要改變結點中的指針。
  • 不會產生磁盤碎片：邏輯上相鄰的節點物理上不必相鄰，因此不會產生磁盤碎片。
  • 缺點：
  • 占用空間大：比順序存儲結構的存儲密度小 (每個節點都由數據域和指針域組成，所以相同空間內假設全存滿的話順序比鏈式存儲更多)。
  • 查找效率低：查找結點時鏈式存儲要比順序存儲慢，只能實現順序存取。

• 索引存儲：

  • 通過建造一個由整數域Z映射到存儲地址域的函數，把整數索引值映射到結點的存儲地址，從而形成一個存儲一串指針的索引表，每個指針指向存儲區域的一個數據結點。
  • 優點：
  • 檢索速度快：直接利用結點的索引號來確定結點存儲地址 。
  • 缺點：
  • 占用空間大：增加了附加的索引表,會占用較多的存儲空間。
  • 同時增刪改查也需要同步修改索引表，花費更多時間。

• 散列存儲：

  • 散列存儲，又稱Hash存儲，是一種將數據元素的存儲位置與關鍵碼之間建立確定對應關系的查找技術，即根據元素的關鍵字直接計算出該元素的存儲地址。
  • 優點：
  • 檢索、增加和刪除節點的操作更快。
  • 缺點：
  • 若散列函數不好，則可能出現元素存儲單元的沖突， 而解決沖突需要增加時間和空間開銷。
    
    

2.3 數據的運算

對于數據的運算包括兩部分：運算的定義和實現。運算的定義是針對數據的邏輯結構的，描述運算的功能；運算的實現是針對存儲結構的，描述運算的具體步驟。

---

3 存儲結構和存取結構

上文在解釋順序存儲時提到了“存取”這一概念，這里記錄一下存儲和存取的區別。

• 存儲結構
  是數據結構的一部分，描述的是數據元素以及元素之間的關系在計算機中的表示。可分為四種：順序存儲、鏈式存儲、索引存儲和散列存儲。
• 存取結構
  描述的是在某種數據結構上對查找操作時間性能的描述?？煞譃閮煞N：隨機存取（Random Access）和順序存取（Sequential Access）
  • 隨機存取： 又稱為直接訪問，指的是當存儲器中的消息被讀取或寫入時，所需要的時間與這段信息所在的位置無關，可以通過下標直接訪問，時間復雜度為$O(1)$。
  • 順序存取：指按照信息的存儲順序來存取，如果想要使用第$n$個信息，那么必須先訪問前$n$-1個信息，所需要的時間和信息的位置有關，時間復雜度為$O(n)$。

可以理解為存儲結構只關注數據的存儲（或寫入），而存取結構關注了數據的存儲（或寫入）和讀取（或查找）。

---

參考資料

相關章節

第一節 【緒論】數據結構的基本概念
第二節 【緒論】算法和算法評價
第三節 【線性表】線性表概述
第四節 【線性表】線性表的順序表示和實現
第五節 【線性表】線性表的鏈式表示和實現
第六節 【線性表】雙向鏈表、循環鏈表和靜態鏈表
第七節 【棧和隊列】棧
第八節 【棧和隊列】棧的應用
第九節 【棧和隊列】棧和遞歸
第十節 【棧和隊列】隊列

舊章節待更新
第八節 遞歸 Recursion
第九節 時間復雜度 Time Complexity
第十節 排序算法 Sort Algorithm
第十一節 冒泡排序 Bubble Sort
第十二節 選擇排序 Select Sort
第十三節 插入排序 Insertion Sort
第十四節 冒泡排序，選擇排序和插入排序的總結
第十五節 希爾排序 Shell’s Sort
第十六節 快速排序 Quick Sort
第十七節 歸并排序 Merge Sort

總結

以上是生活随笔為你收集整理的一、【绪论】数据结构的基本概念的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。