BB728資訊網(wǎng)——每日最新資訊28at.com
數(shù)據(jù)結(jié)構(gòu)分類
數(shù)據(jù)結(jié)構(gòu)是計算機(jī)中組織和存儲數(shù)據(jù)的方式。BB728資訊網(wǎng)——每日最新資訊28at.com
BB728資訊網(wǎng)——每日最新資訊28at.com
數(shù)據(jù)結(jié)構(gòu)分類-原始與非原始BB728資訊網(wǎng)——每日最新資訊28at.com
BB728資訊網(wǎng)——每日最新資訊28at.com
數(shù)據(jù)結(jié)構(gòu)分類-線性與非線性BB728資訊網(wǎng)——每日最新資訊28at.com
原始數(shù)據(jù)結(jié)構(gòu)
基本數(shù)據(jù)結(jié)構(gòu)不能進(jìn)一步劃分。BB728資訊網(wǎng)——每日最新資訊28at.com
- 具有算術(shù)運算的 8 位整數(shù)（字節(jié)）— 最小值為 -128，最大值為 127（含）。
- 具有算術(shù)運算的 16 位整數(shù)（短整型）— 最小值為 -32,768，最大值為 32,767（含）。
- 具有算術(shù)運算的 32 位整數(shù) (Int) — 最小值為 -231，最大值為 230。
- 具有算術(shù)運算的 64 位整數(shù)（長整型）— 最小值為 -263，最大值為 262。
- 16 位 Unicode 字符/字母數(shù)字字符/符號 (char) — 最小值'/u0000'（或 0）和最大值'/uffff'（或 65,535（含））。
- 帶算術(shù)運算的單精度 32 位 IEEE 754 實數(shù)（浮點型）。
- 帶算術(shù)運算的雙精度 64 位 IEEE 754 實數(shù) (Double)。
- 布爾值（具有邏輯運算（布爾）的值 { true, false} 的集合 - 只有兩個可能的值：true和false。
非原始數(shù)據(jù)結(jié)構(gòu)
- 數(shù)據(jù)結(jié)構(gòu)可用于其他復(fù)雜的存儲。
線性
數(shù)組（Array）
- 它是相同類型元素的集合。
- 元素按順序連續(xù)存儲。
- 利用索引可以計算出元素對應(yīng)的地址。
BB728資訊網(wǎng)——每日最新資訊28at.com
ArrayBB728資訊網(wǎng)——每日最新資訊28at.com
- 一維數(shù)組——元素是線性存儲的，可以通過指定數(shù)組中存儲的每個元素的索引值來單獨訪問
- int a[n]，string a[n]
- 多維數(shù)組——具有多個維度的數(shù)組
- int a[m][n]，string a[m][n]
特征
- 所請求的內(nèi)存空間的大小是固定的并且不能改變。使用前必須提前申請內(nèi)存空間。
- 數(shù)組實現(xiàn)數(shù)學(xué)向量和矩陣，以及其他類型的矩形表。
優(yōu)點
- 按索引讀取效率高（支持隨機(jī)訪問應(yīng)用）
- 搜索：時間復(fù)雜度為O(1)
缺點
- 寫入效率低（刪除和插入效率比較低，因為取決于插入和刪除的位置，需要做大量的數(shù)據(jù)移動，除非插入和刪除的位置是最后一位
- 插入/刪除：時間復(fù)雜度為O(n)
鏈表（Linked List）
BB728資訊網(wǎng)——每日最新資訊28at.com
- 它是一種鏈?zhǔn)酱鎯Y(jié)構(gòu)，其中前一個元素的引用指向下一個元素，鏈表通過指針將元素與元素連接起來。所以，它不是按順序?qū)崿F(xiàn)的，而是用指針實現(xiàn)的。
- 鏈表由一系列節(jié)點組成（每個節(jié)點由2部分組成：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)字段，另一個是存儲下一個節(jié)點地址的指針字段
- 單鏈表、雙向鏈表和循環(huán)鏈表
- 鏈表中元素的插入和刪除比較簡單，因為不需要移動元素和實現(xiàn)長度擴(kuò)展，但查詢一個元素比較困難
- 搜索：時間復(fù)雜度為O(n)
- 插入/刪除：時間復(fù)雜度為O(1)
優(yōu)點
缺點
堆棧（Stack）
BB728資訊網(wǎng)——每日最新資訊28at.com
QueueBB728資訊網(wǎng)——每日最新資訊28at.com
- 它是一個線性列表，允許在一端插入并在另一端刪除。
- 它的運行原理是先進(jìn)先出（FIFO）
基本操作
Enqueue：向隊列中插入一個元素。BB728資訊網(wǎng)——每日最新資訊28at.com
Dequeue：移除一個元素并返回隊列的第一個元素。BB728資訊網(wǎng)——每日最新資訊28at.com
- 插入/刪除：時間復(fù)雜度為O(1)
- 循環(huán)隊列、優(yōu)先隊列
非線性
- 它是一種數(shù)據(jù)結(jié)構(gòu)形式，其中數(shù)據(jù)元素不保持線性或順序排列
樹（Tree）
BB728資訊網(wǎng)——每日最新資訊28at.com
TreeBB728資訊網(wǎng)——每日最新資訊28at.com
- 它是一種非線性存儲，由n（n≥1）個有限節(jié)點組成具有層次關(guān)系的集合
- 它顯示具有“一對多”關(guān)系的數(shù)據(jù)元素的集合
- 每個節(jié)點有零個或多個子節(jié)點
- 沒有父節(jié)點的節(jié)點=根節(jié)點
- 每個非根節(jié)點有且只有一個父節(jié)點
- 每個子節(jié)點可以分為多個不相交的子樹
- 節(jié)點深度=從根節(jié)點到x節(jié)點的路徑長度。根節(jié)點深度為0，第二層節(jié)點深度為1，以此類推
- 節(jié)點高度=葉子節(jié)點到x節(jié)點的路徑長度
- 節(jié)點的度=節(jié)點的子樹數(shù)量
- 葉節(jié)點= 度數(shù)為零的節(jié)點
二叉樹
- 每個節(jié)點最多有2個子樹，節(jié)點的最大度數(shù)為2
- 左子樹和右子樹是有序的，順序不能顛倒
- 即使一個節(jié)點只有1個子樹，也需要區(qū)分左右子樹
- AVL樹、紅黑樹、拉伸樹、替罪羊樹、B樹、B+樹、B*樹、字典樹（Trie樹）
哈希表（Hash table）
BB728資訊網(wǎng)——每日最新資訊28at.com
Hash tableBB728資訊網(wǎng)——每日最新資訊28at.com
- 它是一種根據(jù)映射函數(shù)直接訪問的特殊數(shù)據(jù)結(jié)構(gòu)，以key:value的形式存儲數(shù)據(jù)。
- f(key) = 存儲位置。
- 哈希表就是通過哈希函數(shù)將唯一標(biāo)識轉(zhuǎn)換成對應(yīng)的位置。
- 查找、插入：時間復(fù)雜度為O(1)。
- 但是，如果哈希值都映射到同一個地址，則查找的時間復(fù)雜度為O(n)。
- 鏈接尋址——哈希函數(shù)將鍵值映射到哈希表中的每個位置。
- 開放尋址— 如果存在位置映射沖突，其中鍵 1 和鍵 2 共享相同位置，則將鍵 2 放入空空間并啟動尋找空閑位置的過程。
- 檢測方法 = 線性探測、二次探測、雙重散列。
堆（Heap）
BB728資訊網(wǎng)——每日最新資訊28at.com
HeapBB728資訊網(wǎng)——每日最新資訊28at.com
- 它是一個完全二叉樹。
- 它是一個圖樹結(jié)構(gòu)，用于實現(xiàn)“優(yōu)先級隊列”。
- 堆中節(jié)點的值始終不大于或小于其父節(jié)點的值。
- Min Heap = 根節(jié)點最小的堆，滿足 ki ≤ K2i+1 且 ki ≤ k2i+2。
- Max Heap = 根節(jié)點最大的堆，滿足 ki ≥ k2i+1 且 ki ≥ k2i+2。
圖表（Graph）
BB728資訊網(wǎng)——每日最新資訊28at.com
圖形術(shù)語的可視化BB728資訊網(wǎng)——每日最新資訊28at.com
- 它是一種相對復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，具有相對復(fù)雜且高效的數(shù)據(jù)存儲算法。
- 它展示了對象與對象之間復(fù)雜的“多對多”關(guān)系。
- 它由有限的頂點集 V 和邊集 E 組成。
可分為無向圖和有向圖：BB728資訊網(wǎng)——每日最新資訊28at.com
- (v,w)表示無向邊，即v和w是互連的。
- <v, w> 表示從 v 開始到 w 結(jié)束的有向邊。
圖可以分為加權(quán)圖和未加權(quán)圖：BB728資訊網(wǎng)——每日最新資訊28at.com
- 加權(quán)圖：每條邊都有一定的權(quán)重，通常是一個數(shù)字。
- 無權(quán)圖：每條邊沒有權(quán)重，也可以理解為權(quán)重為1。
圖可以分為連通圖和非連通圖：BB728資訊網(wǎng)——每日最新資訊28at.com
- 連通圖：所有點都通過路徑連接。
- 斷開圖：有兩個點沒有通過路徑連接。
圖中的頂點有度的概念：BB728資訊網(wǎng)——每日最新資訊28at.com
- 度數(shù)——與其相連的所有點的總和。
- 入度 — 存在于有向圖中，訪問該點的所有邊的總和。
- 出度——存在于有向圖中，與該點相連的邊數(shù)之和。
圖表的表示BB728資訊網(wǎng)——每日最新資訊28at.com
- 鄰接矩陣— 具有 n 個頂點的圖需要具有大小為 nxn 的矩陣。
- 鄰接表- 具有鏈表數(shù)組的圖。
- 算法：圖的搜索算法、廣度優(yōu)先搜索（BFS）、深度優(yōu)先搜索（DFS）等。
大O復(fù)雜性
BB728資訊網(wǎng)——每日最新資訊28at.com
本文鏈接：http://www.www897cc.com/showinfo-26-16000-0.html數(shù)據(jù)結(jié)構(gòu)分類以及數(shù)據(jù)結(jié)構(gòu)特點、優(yōu)缺點
聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
上一篇： 萬字詳解 TypeScript 高級用法
下一篇： Java項目：服務(wù)之間調(diào)用超時或連接池配置不合理，導(dǎo)致服務(wù)不可用
津公網(wǎng)安備 12010102000574號