一、數(shù)據(jù)結(jié)構(gòu)

1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語

1. 數(shù)據(jù)

   數(shù)據(jù)是信息的載體，是描述客觀事物屬性的數(shù)、字符以及所有能被輸入到計算機中并被計算機程序識別和處理的符號集合。

2. 數(shù)據(jù)元素

   數(shù)據(jù)元素是數(shù)據(jù)的基本單位，通常作為一個整體進行考慮和處理。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成，數(shù)據(jù)項是構(gòu)成數(shù)據(jù)元素的不可分割的最小單位。例如： 學(xué)生記錄就是一個數(shù)據(jù)元素，它是由學(xué)號、姓名、性別等數(shù)據(jù)項組成。

3. 數(shù)據(jù)對象

   數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。

4. 數(shù)據(jù)類型

   數(shù)據(jù)類型是一個值的集合和定義在此集合上一組操作的總稱。

   • 原子類型：其值不可再分的數(shù)據(jù)類型。例如C語言中的整數(shù)類型、浮點類型、字符類型。
   • 結(jié)構(gòu)類型：其值可以分解為若干成分的數(shù)據(jù)類型。例如python中的列表、字典等
   • 抽象數(shù)據(jù)類型：抽象數(shù)據(jù)組織和與之相關(guān)的操作。

5. 抽象數(shù)據(jù)類型

   抽象數(shù)據(jù)類型(ADT)是指一個數(shù)學(xué)模型以及定義在模型上的一組操作。

   image.png

6. 數(shù)據(jù)結(jié)構(gòu)

   在任何問題中，數(shù)據(jù)元素都是不獨立存在的，而是在它們之間存在著某種關(guān)系，這種數(shù)據(jù)元素相互之間的關(guān)系成為結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合。數(shù)據(jù)結(jié)構(gòu)包含三方面的內(nèi)容：邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)運算。算法的設(shè)計依賴數(shù)據(jù)的邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴數(shù)據(jù)的存儲結(jié)構(gòu)。

1.2 數(shù)據(jù)結(jié)構(gòu)的三要素

1. 數(shù)據(jù)的邏輯結(jié)構(gòu)

   邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，即從邏輯關(guān)系上面描述數(shù)據(jù)。它與數(shù)據(jù)的存儲無關(guān)，是獨立與計算機的。

   邏輯結(jié)構(gòu)分類：

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

     結(jié)構(gòu)中數(shù)據(jù)元素之間的關(guān)系只存在一對一關(guān)系

     • 一般線性表
     • 棧和隊列
     • 數(shù)組
     • 廣義表

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

     • 集合

       結(jié)構(gòu)中的數(shù)據(jù)元素除了除了同屬于一個集合的關(guān)系外，再無其它關(guān)系。

     • 樹

       結(jié)構(gòu)中數(shù)據(jù)元素之間的關(guān)系只存在一對多關(guān)系

       • 一般樹
       • 二叉樹

     • 圖

       結(jié)構(gòu)中數(shù)據(jù)元素之間的關(guān)系只存在多對多關(guān)系

       • 有向圖
       • 無向圖

2. 數(shù)據(jù)的存儲結(jié)構(gòu)

   存儲結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)在計算機中的映象，也稱物理結(jié)構(gòu)。包括數(shù)據(jù)元素的表示和關(guān)系的表示。數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)，它依賴于計算機語言。

   物理結(jié)構(gòu)分類：

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

     把邏輯上相鄰的元素存儲在物理位置上也相鄰的儲存單元里，元素之間的關(guān)系由存儲單元的鄰接關(guān)系體現(xiàn)。

     優(yōu)點：

     • 可以實現(xiàn)隨機存取
     • 每個元素占用最小的存儲空間

     缺點：

     • 只能使用相鄰的一整塊存儲單元
     • 產(chǎn)生較多的磁盤碎片

   • 鏈?zhǔn)酱鎯Y(jié)構(gòu)

     不要求邏輯上相鄰的元素在物理結(jié)構(gòu)上也相鄰，借助指示元素存儲地址的指針表示元素之間的邏輯關(guān)系。

     優(yōu)點：

     • 不會出現(xiàn)碎片
     • 充分利用存儲單元

     缺點：

     • 每個元素因為存儲指針而多占用內(nèi)存
     • 只能實現(xiàn)順序存取

   • 索引存儲結(jié)構(gòu)

     在存儲元素信息時，還建立附加的索引表。索引表中的每一項稱之為索引項，索引項一般存儲形式:(關(guān)鍵字, 地址)。

     優(yōu)點：

     • 數(shù)據(jù)檢索速度快

     缺點：

     • 增加索引表，額外占用存儲空間
     • 在增加和刪除數(shù)據(jù)時，要修改索引表，會花費較多的時間。

   • 散列存儲結(jié)構(gòu)

     根據(jù)元素的關(guān)鍵字直接計算出該元素的存儲地址，又稱Hash存儲。

     優(yōu)點：

     • 檢索、增加、刪除的操作都很快

     缺點：

     • 如果散列函數(shù)不好，可能會出現(xiàn)元素存儲單元沖突，而解決沖突會會增加時間和空間開銷

3. 數(shù)據(jù)的運算

   施加在數(shù)據(jù)上的運算包括運算的定義和實現(xiàn)。運算的定義是針對邏輯結(jié)構(gòu)，指出運算的功能；運算的實現(xiàn)是針對存儲結(jié)構(gòu)，指出運算的具體操作步驟。

圖片資料

抽象數(shù)據(jù)類型