數(shù)據(jù)結(jié)構(gòu)分類

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)中組織和存儲(chǔ)數(shù)據(jù)的方式。

數(shù)據(jù)結(jié)構(gòu)分類-原始與非原始

數(shù)據(jù)結(jié)構(gòu)分類-線性與非線性

原始數(shù)據(jù)結(jié)構(gòu)

基本數(shù)據(jù)結(jié)構(gòu)不能進(jìn)一步劃分。

• 具有算術(shù)運(yùn)算的 8 位整數(shù)（字節(jié)）— 最小值為 -128，最大值為 127（含）。
• 具有算術(shù)運(yùn)算的 16 位整數(shù)（短整型）— 最小值為 -32,768，最大值為 32,767（含）。
• 具有算術(shù)運(yùn)算的 32 位整數(shù) (Int) — 最小值為 -231，最大值為 230。
• 具有算術(shù)運(yùn)算的 64 位整數(shù)（長(zhǎng)整型）— 最小值為 -263，最大值為 262。
• 16 位 Unicode 字符/字母數(shù)字字符/符號(hào) (char) — 最小值'\u0000'（或 0）和最大值'\uffff'（或 65,535（含））。
• 帶算術(shù)運(yùn)算的單精度 32 位 IEEE 754 實(shí)數(shù)（浮點(diǎn)型）。
• 帶算術(shù)運(yùn)算的雙精度 64 位 IEEE 754 實(shí)數(shù) (Double)。
• 布爾值（具有邏輯運(yùn)算（布爾）的值 { true, false} 的集合 - 只有兩個(gè)可能的值：true和false。

非原始數(shù)據(jù)結(jié)構(gòu)

• 數(shù)據(jù)結(jié)構(gòu)可用于其他復(fù)雜的存儲(chǔ)。

線性

• 元素組成一個(gè)序列

數(shù)組（Array）

• 它是相同類型元素的集合。
• 元素按順序連續(xù)存儲(chǔ)。
• 利用索引可以計(jì)算出元素對(duì)應(yīng)的地址。

Array

• 一維數(shù)組——元素是線性存儲(chǔ)的，可以通過(guò)指定數(shù)組中存儲(chǔ)的每個(gè)元素的索引值來(lái)單獨(dú)訪問(wèn)
• int a[n]，string a[n]
• 多維數(shù)組——具有多個(gè)維度的數(shù)組
• int a[m][n]，string a[m][n]

特征

• 所請(qǐng)求的內(nèi)存空間的大小是固定的并且不能改變。使用前必須提前申請(qǐng)內(nèi)存空間。
• 數(shù)組實(shí)現(xiàn)數(shù)學(xué)向量和矩陣，以及其他類型的矩形表。

優(yōu)點(diǎn)

• 按索引讀取效率高（支持隨機(jī)訪問(wèn)應(yīng)用）
• 搜索：時(shí)間復(fù)雜度為O(1)

缺點(diǎn)

• 寫入效率低（刪除和插入效率比較低，因?yàn)槿Q于插入和刪除的位置，需要做大量的數(shù)據(jù)移動(dòng)，除非插入和刪除的位置是最后一位
• 插入/刪除：時(shí)間復(fù)雜度為O(n)

鏈表（Linked List）

• 它是一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其中前一個(gè)元素的引用指向下一個(gè)元素，鏈表通過(guò)指針將元素與元素連接起來(lái)。所以，它不是按順序?qū)崿F(xiàn)的，而是用指針實(shí)現(xiàn)的。
• 鏈表由一系列節(jié)點(diǎn)組成（每個(gè)節(jié)點(diǎn)由2部分組成：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)字段，另一個(gè)是存儲(chǔ)下一個(gè)節(jié)點(diǎn)地址的指針字段
• 單鏈表、雙向鏈表和循環(huán)鏈表
• 鏈表中元素的插入和刪除比較簡(jiǎn)單，因?yàn)椴恍枰苿?dòng)元素和實(shí)現(xiàn)長(zhǎng)度擴(kuò)展，但查詢一個(gè)元素比較困難
• 搜索：時(shí)間復(fù)雜度為O(n)
• 插入/刪除：時(shí)間復(fù)雜度為O(1)

優(yōu)點(diǎn)

• 可以任意添加或減少元素。

缺點(diǎn)

• 包含大量的指針字段，占用內(nèi)存空間大

堆棧（Stack）

Stack

• 它是一種特殊的線性表，只能在一端插入和刪除。
• 它按照后進(jìn)先出（LIFO）的原則存儲(chǔ)數(shù)據(jù)。
• 最先輸入的數(shù)據(jù)被壓入棧底，最后一個(gè)數(shù)據(jù)元素在棧頂。
• 最后一個(gè)數(shù)據(jù)元素首先被讀出或從堆棧頂部彈出。
• 插入=Push
• 刪除=Pop
• 棧中元素個(gè)數(shù)為零=空棧
• 插入/刪除：時(shí)間復(fù)雜度為O(1)

隊(duì)列（Queue）

Queue

• 它是一個(gè)線性列表，允許在一端插入并在另一端刪除。
• 它的運(yùn)行原理是先進(jìn)先出（FIFO）

基本操作

Enqueue：向隊(duì)列中插入一個(gè)元素。

Dequeue：移除一個(gè)元素并返回隊(duì)列的第一個(gè)元素。

• 插入/刪除：時(shí)間復(fù)雜度為O(1)
• 循環(huán)隊(duì)列、優(yōu)先隊(duì)列

非線性

• 它是一種數(shù)據(jù)結(jié)構(gòu)形式，其中數(shù)據(jù)元素不保持線性或順序排列

樹（Tree）

Tree

• 它是一種非線性存儲(chǔ)，由n（n≥1）個(gè)有限節(jié)點(diǎn)組成具有層次關(guān)系的集合
• 它顯示具有“一對(duì)多”關(guān)系的數(shù)據(jù)元素的集合
• 每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)
• 沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)=根節(jié)點(diǎn)
• 每個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)
• 每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹
• 節(jié)點(diǎn)深度=從根節(jié)點(diǎn)到x節(jié)點(diǎn)的路徑長(zhǎng)度。根節(jié)點(diǎn)深度為0，第二層節(jié)點(diǎn)深度為1，以此類推
• 節(jié)點(diǎn)高度=葉子節(jié)點(diǎn)到x節(jié)點(diǎn)的路徑長(zhǎng)度
• 節(jié)點(diǎn)的度=節(jié)點(diǎn)的子樹數(shù)量
• 葉節(jié)點(diǎn)= 度數(shù)為零的節(jié)點(diǎn)

二叉樹

• 每個(gè)節(jié)點(diǎn)最多有2個(gè)子樹，節(jié)點(diǎn)的最大度數(shù)為2
• 左子樹和右子樹是有序的，順序不能顛倒
• 即使一個(gè)節(jié)點(diǎn)只有1個(gè)子樹，也需要區(qū)分左右子樹
• AVL樹、紅黑樹、拉伸樹、替罪羊樹、B樹、B+樹、B*樹、字典樹（Trie樹）

哈希表（Hash table）

Hash table

• 它是一種根據(jù)映射函數(shù)直接訪問(wèn)的特殊數(shù)據(jù)結(jié)構(gòu)，以key:value的形式存儲(chǔ)數(shù)據(jù)。
• f(key) = 存儲(chǔ)位置。
• 哈希表就是通過(guò)哈希函數(shù)將唯一標(biāo)識(shí)轉(zhuǎn)換成對(duì)應(yīng)的位置。
• 查找、插入：時(shí)間復(fù)雜度為O(1)。
• 但是，如果哈希值都映射到同一個(gè)地址，則查找的時(shí)間復(fù)雜度為O(n)。
• 鏈接尋址——哈希函數(shù)將鍵值映射到哈希表中的每個(gè)位置。
• 開放尋址— 如果存在位置映射沖突，其中鍵 1 和鍵 2 共享相同位置，則將鍵 2 放入空空間并啟動(dòng)尋找空閑位置的過(guò)程。
• 檢測(cè)方法 = 線性探測(cè)、二次探測(cè)、雙重散列。

堆（Heap）

Heap

• 它是一個(gè)完全二叉樹。
• 它是一個(gè)圖樹結(jié)構(gòu)，用于實(shí)現(xiàn)“優(yōu)先級(jí)隊(duì)列”。
• 堆中節(jié)點(diǎn)的值始終不大于或小于其父節(jié)點(diǎn)的值。
• Min Heap = 根節(jié)點(diǎn)最小的堆，滿足 ki ≤ K2i+1 且 ki ≤ k2i+2。
• Max Heap = 根節(jié)點(diǎn)最大的堆，滿足 ki ≥ k2i+1 且 ki ≥ k2i+2。

圖表（Graph）

圖形術(shù)語(yǔ)的可視化

• 它是一種相對(duì)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，具有相對(duì)復(fù)雜且高效的數(shù)據(jù)存儲(chǔ)算法。
• 它展示了對(duì)象與對(duì)象之間復(fù)雜的“多對(duì)多”關(guān)系。
• 它由有限的頂點(diǎn)集 V 和邊集 E 組成。

可分為無(wú)向圖和有向圖：

• (v,w)表示無(wú)向邊，即v和w是互連的。
• <v, w> 表示從 v 開始到 w 結(jié)束的有向邊。

圖可以分為加權(quán)圖和未加權(quán)圖：

• 加權(quán)圖：每條邊都有一定的權(quán)重，通常是一個(gè)數(shù)字。
• 無(wú)權(quán)圖：每條邊沒(méi)有權(quán)重，也可以理解為權(quán)重為1。

圖可以分為連通圖和非連通圖：

• 連通圖：所有點(diǎn)都通過(guò)路徑連接。
• 斷開圖：有兩個(gè)點(diǎn)沒(méi)有通過(guò)路徑連接。

圖中的頂點(diǎn)有度的概念：

• 度數(shù)——與其相連的所有點(diǎn)的總和。
• 入度 — 存在于有向圖中，訪問(wèn)該點(diǎn)的所有邊的總和。
• 出度——存在于有向圖中，與該點(diǎn)相連的邊數(shù)之和。

圖表的表示

• 鄰接矩陣— 具有 n 個(gè)頂點(diǎn)的圖需要具有大小為 nxn 的矩陣。
• 鄰接表- 具有鏈表數(shù)組的圖。
• 算法：圖的搜索算法、廣度優(yōu)先搜索（BFS）、深度優(yōu)先搜索（DFS）等。

大O復(fù)雜性