数据结构基础
一、基本概念
1、數據
數據（Data）是描述客觀事物屬性的數、字符及所有能被輸入到計算機中并被計算機程序識別和處理的符號的集合。
解釋：數據不僅包括整型、字符型等數值類型，還包括字符及聲音、圖像、視頻等非數值類型。 數據必須具備兩個前提：（1）可以輸入到計算機中；（2）能被計算機程序處理。對于整型、字符型等數值類型，可以進行數值計算；而對于字符數據類型，就需要非數值的處理；而聲音、圖像、視頻等可以通過編碼的手段變成字符數據來處理。
2、數據對象
數據對象（Data Object）是性質相同的數據元素的集合，是數據的一個子集。
解釋：什么叫性質相同呢？是指數據元素具有相同數量和類型的數據項，比如人 這個例子，都有姓名、生日、性別等相同的數據項。 既然數據對象是數據的子集，在實際應用中，處理的數據元素通常具有相同性質，在不產生混淆的情況下，我們將數據對象簡稱為數據。
3、數據元素
數據元素（Data Element）是數據元素是組成數據的基本單位，通常稱為記錄。
解釋：比如 畜類 牛、馬、羊、雞、豬、狗等動物當然就是畜類的數據元素。
4、數據項
數據項（Data Item）是描述數據的最小單位，其可以分為組合項和原子項：
a)組合項
如果數據元素可以再度分割，則每一個獨立處理單元就是數據項，數據元素就是數據項的集合。
b)原子項
如果數據元素不能再度分割，則每一個獨立處理的單元就是原子項。
如日期2022年6月25日就是一個組合項，其表示日期，但如果單獨拿25日這個數據出來觀測，這就是一個原子項，因為其不可以再分割。
?數據、數據對象、數據元素、數據項關系圖解（1）
??數據、數據對象、數據元素、數據項關系圖解（2）
5、數據結構
數據結構(Data Structure)：相互之間存在一種或多種特定關系的數據元素的集合。
解釋：數據元素都不是孤立存在的，它們之間存在某種關系，這些數據元素之間的關系稱為結構(structure)。在現實世界中，不同數據元素之間不是獨立的，而是存在特定的關系，這些關系稱為結構。數據結構是相互之間存在一種或多種特定關系的數據元素的集合。
數據結構包括三方面的內容：邏輯結構、存儲結構和數據的運算。數據的邏輯結構和存儲結構是密不可分的兩個方面，一個算法的設計取決于所選定的邏輯結構，而算法的實現依賴于所采用的存儲結構。
?二、數據結構分類
數據結構的三要素：
- 邏輯結構：指數據對象中數據元素之間相互關系（邏輯關系），即從邏輯關系上描述數據。它與數據的存儲無關，是獨立于計算機存儲器的。邏輯結構分為線性結構和非線性結構，線性結構就是線性表、棧、隊列、雙隊列和串，非線性結構是集合、樹型和圖型。
- 存儲結構：數據結構在計算機中的表示（又稱映像，也稱物理結構），存儲結構主要分為順序存儲、鏈式存儲、索引存儲、散列（哈希）存儲。
- 數據的運算：施加在數據上的運算包括運算的定義和實現，運算的定義基于邏輯結構，運算的實現基于存儲結構。
1、邏輯結構
1) 集合結構
集合結構（Set Structure）中所有數據元素除了同屬于一個集合外，并無其他關系。
如圖：
2) 線性結構
線性結構（Linear Structure）指的是數據元素之間存在 “一對一的關系”
如圖:
3) 樹形結構
樹形結構（Tree Structure）指的是數據元素之間存在 “一對多” 的層次關系。
如圖：
4) 圖形結構
圖形結構（Graphic Structure，也稱：網狀結構）指的是數據元素之間存在“多對多的關系”（注：此時的“多對多”中的多表示，至少有一個）
如圖：
2、存儲結構
數據的物理結構是指數據的邏輯結構在計算機中的存儲方式，又稱存儲結構。它研究的是數據結構在計算機中的實現方法，包括數據元素的表示和元素之間的關系。
數據元素的存儲結構形式包括：順序存儲、鏈式存儲、索引存儲和散列（哈希）存儲。
1) 順序存儲結構
是利用數據元素在存儲器中的相對位置來表示數據元素之間的邏輯順序。
順序存儲結構是把數據元素放在地址連續的存儲單元中，程序設計中使用數組類型來實現。（邏輯相鄰物理相鄰）
2) 鏈式存儲結構
利用結點中指針來表示數據元素之間的關系。
把數據元素存儲在任意的存儲單元里，這組存儲單元可以是連續的，也可以是不連續的，程序設計中使用指針類型來實現。（邏輯相鄰物理不一定相鄰）
3) 索引存儲結構?
該方法通常在儲存結點信息的同時，還建立附加的索引表。 索引表由若干索引項組成。若每個結點在索引表中都有一個索引項，則該索引表稱之為稠密索引（Dense Index）。若一組結點在索引表中只對應一個索引項，則該索引表稱為稀疏索引（Spare Index）。索引項的一般形式是關鍵字和地址。
關鍵字是能唯一標識一個結點的那些數據項。稠密索引中索引項的地址指示結點所在的存儲位置；稀疏索引中索引項的地址指示一組結點的起始存儲位置。
4) 散列（哈希）結構?
該方法的基本思想是：根據結點的關鍵字直接計算出該結點的存儲地址。
3、數據的運算
數據的運算是指施加在數據上的運算，包括運算的定義和實現：
a）運算的定義是針對邏輯結構的，指出運算的功能；
b）運算的實現是針對存儲結構的，指出運算的具體操作步驟。
解釋：在這里容易混淆的是邏輯結構與存儲結構的概念。對于邏輯結構，不難看得出邏輯二字，邏輯關系也就是兩者存在數據上的關系而不考慮物理地址的關系，比如線性結構和非線性結構，它描述的是一組數據中聯系的方式和形式，他針對的是數據?？粗械氖菙祿Y構的功能，比如線性表就是前后有序的，我需要一個有序的集合就可以使用線性表。
而存儲結構就是跟物理地址掛鉤的。因為同樣邏輯結構采用不同存儲結構實現適用場景和性能可能不同。比如同樣是線性表,可能有多種存儲結構的實現方式。比如順序表和鏈表(Arraylist,Linkedlist)它們的存儲結構就不同，一個是順序存儲(數組)實現，一個是鏈式存儲(鏈表)實現。它關注的是計算機運行物理地址的關系。但通常同一類存儲結構實現的一些數據結構有一些類似的共同點和缺點(線性易查難插、鏈式易插難查等等)。
數據結構的主要運算包括：
(1) 建立(Create)一個數據結構
(2) 消除(Destroy)一個數據結構
(3) 從一個數據結構中刪除(Delete)一個數據元素
(4) 把一個數據元素插入(Insert)到一個數據結構中
(5) 對一個數據結構進行訪問(Access)
(6) 對一個數據結構(中的數據元素)進行修改(Modify)
(7) 對一個數據結構進行排序(Sort)
(8) 對一個數據結構進行查找(Search)
總結
- 上一篇： qt优点
- 下一篇： EasyPR转qt5-vs2013