基本概念

數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中的操作對象，以及它們之間的關(guān)系和操作等相關(guān)問題的學(xué)科许起。

• 數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或者多種特定關(guān)系的數(shù)據(jù)元素集合。

• 數(shù)據(jù)：是描述客觀事物的符號，是計算機中可以操作的對象脂新，是能被計算機識別灸撰，并輸入給計算機處理的符號集合谒府，包括數(shù)值拼坎、字符、聲音完疫、圖像等等泰鸡。數(shù)值等可以進行處理，而字符數(shù)據(jù)就需要進行非數(shù)值的處理壳鹤，聲音盛龄、圖像、視頻等也可以通過編碼變成字符數(shù)據(jù)來處理芳誓。

• 數(shù)據(jù)元素：是組成數(shù)據(jù)的余舶、有一定意義的基本單位，在計算機中通常作為整體處理锹淌，也稱為記錄匿值。例如人類中的數(shù)據(jù)元素就是人。

• 數(shù)據(jù)項：一個數(shù)據(jù)元素可以有若干個數(shù)據(jù)項組成赂摆，比如人這樣的數(shù)據(jù)元素可以有眼挟憔、鼻、嘴烟号、耳绊谭、手、腳這些數(shù)據(jù)項汪拥，還可以有姓名龙誊、年齡、性別等數(shù)據(jù)項喷楣，具體有系統(tǒng)決定趟大。是數(shù)據(jù)不可分割的最小單位，但是數(shù)據(jù)元素才是數(shù)據(jù)結(jié)構(gòu)中建立數(shù)據(jù)模型的著眼點铣焊，例如我們會討論一個電影角色逊朽，但不會單獨研究他的姓名。

• 數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合曲伊，是數(shù)據(jù)的子集叽讳。性質(zhì)相同指的是數(shù)據(jù)元素具有相同數(shù)量和類型的數(shù)據(jù)項。數(shù)據(jù)對象時數(shù)據(jù)的子集坟募，處理的數(shù)據(jù)元素通常具有相同性質(zhì)岛蚤，所以將數(shù)據(jù)對象簡稱數(shù)據(jù)。

• 數(shù)據(jù)類型：是指一組性質(zhì)相同的值的集合以及定義在此集合上的一些操作的總稱懈糯。

• 抽象數(shù)據(jù)類型：ADT涤妒，指一個數(shù)學(xué)模型及定義在該模型上的一組操作。它的定義僅取決于一組邏輯特性赚哗，與其在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)她紫。一個抽象數(shù)據(jù)類型定義了一個數(shù)據(jù)對象硅堆、數(shù)據(jù)對象中各數(shù)據(jù)元素之間的關(guān)系及對數(shù)據(jù)元素的操作。

關(guān)系圖如下：

關(guān)系圖

邏輯結(jié)構(gòu)與物理結(jié)構(gòu)

• 結(jié)構(gòu)：不同數(shù)據(jù)之間不是相互獨立的贿讹，而是存在特定的關(guān)系渐逃，這些關(guān)系稱為結(jié)構(gòu)。

• 邏輯結(jié)構(gòu)：是指數(shù)據(jù)對象中數(shù)據(jù)元素之間的相互關(guān)系民褂，針對的是具體問題茄菊。重點關(guān)注的問題。

  1. 集合結(jié)構(gòu)：集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個集合外赊堪，它們之間沒有其他關(guān)系买羞，各個數(shù)據(jù)元素是平等的。

     
     
     集合

  2. 線性結(jié)構(gòu)：線性結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對一的關(guān)系雹食。

線性結(jié)構(gòu)

3. 樹形結(jié)構(gòu)：樹形結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一種一對多的層次關(guān)系畜普。

樹形結(jié)構(gòu)

4. 圖形結(jié)構(gòu)：圖形結(jié)構(gòu)的數(shù)據(jù)元素是多對多的關(guān)系。

圖形結(jié)構(gòu)

• 物理結(jié)構(gòu)：也叫存儲結(jié)構(gòu)，是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的存儲形式赎离。數(shù)據(jù)的存儲結(jié)構(gòu)應(yīng)正確反應(yīng)數(shù)據(jù)元素之間的邏輯關(guān)系逛犹。數(shù)據(jù)是數(shù)據(jù)元素的集合，根據(jù)物理結(jié)構(gòu)的定義梁剔，實際就是如何把數(shù)據(jù)元素存儲到存儲器虽画，主要針對內(nèi)存而言的，硬盤荣病、軟盤码撰、光盤等外部存儲器的數(shù)據(jù)組織通常用文件結(jié)構(gòu)來描述。

  1. 順序存儲結(jié)構(gòu)：把數(shù)據(jù)存放在地址連續(xù)的存儲單元里个盆，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的脖岛。例如數(shù)組。

     
     
     順序存儲結(jié)構(gòu)

  2. 鏈式存儲結(jié)構(gòu)：是把數(shù)據(jù)元素存放在任意的存儲單元里颊亮，這組存儲單元可以是連續(xù)的也可以是不連續(xù)的柴梆。數(shù)據(jù)元素的存儲關(guān)系并不能反映其邏輯關(guān)系，需要有一個指針存放數(shù)據(jù)元素的地址终惑，通過地址就可以找到相關(guān)聯(lián)的數(shù)據(jù)元素的位置绍在。

     
     
     鏈式存儲結(jié)構(gòu)

  邏輯結(jié)構(gòu)是面向問題的，而物理結(jié)構(gòu)是面向計算機的，其基本目標就是將數(shù)據(jù)及其邏輯關(guān)系存儲到計算機的內(nèi)存中揣苏。

注：參考《大話數(shù)據(jù)結(jié)構(gòu)》，文中圖使用Visio 2016繪畫后截圖件舵。