目錄

一、什么是數據結構

二、常用數據結構有哪些

2.1 基本數據結構

2.2 常用數據結構 (邏輯結構）

2.2.1 數組（靜態數組、動態數組）

2.2.2 線性表

2.2.3 隊列

2.2.4 棧

2.2.5 樹（二叉樹、查找樹、平衡樹、線索、堆）

2.2.6 圖(Graph)

2.2.7?堆 (Heap)

2.2.8 散列表(哈希表）?(Hash)

2.3 數據存儲結構比較

2.4 數據結構的操作

2.5 算法的空間復雜度與時間復雜度

---

數據結構可以從兩個方面分析：邏輯結構與物理結構(存儲結構)。

其中邏輯結構指的是數據的組織方式，物理結構指的是數據在內存上的存儲方式。

邏輯結構分為四種類型：集合結構，線性結構，樹形結構，圖形結構。

物理結構又叫存儲結構，分為四種種，順序存儲結構、鏈式存儲結構、索引結構、散列結構。

一、什么是數據結構

數據結構是計算機存儲、組織數據的方式。數據結構是指相互之間存在一種或多種特定關系的數據元素的集合。
?

數據結構與算法的關系：

數據結構指的是“一組數據的存儲結構”，算法指的是“操作數據的一組方法”。
數據結構是為算法服務的，算法是要作用再特定的數據結構上的。

二、常用數據結構有哪些

2.1 基本數據結構

數據元素相互之間的關系稱為結構。有四類基本結構：集合、線性結構、樹形結構、圖狀結構。 集合結構:除了同屬于一種類型外，別無其它關系 ；

線性結構:元素之間存在一對一關系常見類型有: 數組,鏈表,隊列,棧,它們之間在操作上有所區別。例如:鏈表可在任意位置插入或刪除元素, 而隊列在隊尾插入元素,隊頭刪除元素,棧只能在棧頂進行插入,刪除操作；

樹形結構:元素之間存在一對多的關系,常見類型有:樹(有許多特例:二叉樹、平衡二叉樹、查找樹等) 圖形結構:元素之間存在多對多的關系,圖形結構中每個結點的前驅結點數和后續結點多個數可以任意。

2.2 常用數據結構 (邏輯結構）

本文作者：https://www.zhihu.com/people/san-hao-bai-du-ren-79

(由于文章總是被三無號到處復制發布，選擇這種方式插入原文鏈接影響閱讀實在抱歉！)

本文原文鏈接：https://blog.csdn.net/qq_41687938/article/details/118227614

2.2.1 數組（靜態數組、動態數組）

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

2.2.2 線性表

線性表并不是一種具體的存儲結構，它包含順序存儲結構和鏈式存儲結構，是順序表和鏈表的統稱。順序表、鏈表（單向鏈表、雙向鏈表、循環鏈表）

2.2.3 隊列

棧隸屬于線性表，是特殊的線性表，因為它對線性表中元素的進出做了明確的要求只能從線性表的一端進，從另一端出，且要遵循“先入先出”的特點，即先進隊列的元素也要先出隊列。即只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列中沒有元素 時，稱為隊空。

2.2.4 棧

棧隸屬于線性表，是特殊的線性表，因為它對線性表中元素的進出做了明確的要求。棧中的元素只能從線性表的一端進出（另一端封死），且要遵循“先入后出”的原則，即先進棧的元素后出棧。即先進入的數據被壓入棧底，最后的數據在棧頂，需要讀數據的時候從棧頂開始彈出數據，最后一 個數據被第一個讀出來。

2.2.5 樹（二叉樹、查找樹、平衡樹、線索、堆）

樹是包含n（n>0）個結點的有窮集合K，且在K中定義了一個關系N，N滿足以下條件：
1）有且僅有一個結點K0，他對于關系N來說沒有前驅，稱K0為樹的根結點。簡稱為根（root）。
2）除K0外，K中的每個結點，對于關系N來說有且僅有一個前驅。
3）K中各結點，對關系N來說可以有m個后繼（m>=0）。

2.2.6 圖(Graph)

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

2.2.7?堆 (Heap)

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

2.2.8 散列表(哈希表）?(Hash)

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

2.3 數據存儲結構比較

順序結構：一段連續的內存空間。
????優點：隨機訪問
????缺點：插入刪除效率低，大小固定
鏈式結構：不連續的內存空間
????優點：大小動態擴展，插入刪除效率高
????缺點：不能隨機訪問。
索引結構：為了方便查找，整體無序，但索引塊之間有序，需要額外空間，存儲索引表。
????優點：對順序查找的一種改進，查找效率高
????缺點：需額外空間存儲索引表
散列結構：選取某個函數，數據元素根據函數計算存儲位置。可能存在多個數據元素存儲在同一位置，引起地址沖突。
????優點：查找基于數據本身即可找到，查找效率高。存取效率高
????缺點：存取隨機，不便于順序查找。

2.4 數據結構的操作

查詢、刪除、插入等

2.5 算法的空間復雜度與時間復雜度

大O復雜度表示法

總結

以上是生活随笔為你收集整理的数据结构有哪些？数据结构的特点？算法与数据结构的全部內容，希望文章能夠幫你解決所遇到的問題。

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