線性資料結構

線性結構是一個有序資料元素的集合，

常用的線性結構

線性表，堆疊，佇列，雙佇列，串(一維陣列)，

非線性資料結構

關于廣義表、陣列(高維)，是一種非線性的資料結構，

常見的非線性結構有：二維陣列，多維陣列，廣義表，樹(二叉樹等)，圖

線性表（線性存盤結構）

1、將具有“一對一”關系的資料“線性”地存盤到物理空間中，這種存盤結構就稱為線性存盤結構（簡稱線性表），

2、使用線性表存盤的資料，如同向陣列中存盤資料那樣，要求資料型別必須一致，也就是說，線性表存盤的資料，要么全部都是整形，要么全部都是字串，一半是整形，另一半是字串的一組資料無法使用線性表存盤，

3、將資料依次存盤在連續的整塊物理空間中，這種存盤結構稱為順序存盤結構（簡稱順序表）；資料分散的存盤在物理空間中，通過一根線保存著它們之間的邏輯關系，這種存盤結構稱為鏈式存盤結構（簡稱鏈表）

4、某一元素的左側相鄰元素稱為“直接前驅”，位于此元素左側的所有元素都統稱為“前驅元素”；某一元素的右側相鄰元素稱為“直接后繼”，位于此元素右側的所有元素都統稱為“后繼元素”

堆疊

堆疊又名堆疊，它是一種運算受限的線性表，限定僅在表尾進行插入和洗掉操作的線性表，這一端被稱為堆疊頂，相對地，把另一端稱為堆疊底，向一個堆疊插入新元素又稱作進堆疊、入堆疊或壓堆疊，它是把新元素放到堆疊頂元素的上面，使之成為新的堆疊頂元素；從一個堆疊洗掉元素又稱作出堆疊或退堆疊，它是把堆疊頂元素洗掉掉，使其相鄰的元素成為新的堆疊頂元素，

單調堆疊

單調堆疊中存放的資料應該是有序的，所以單調堆疊也分為單調遞增堆疊和單調遞減堆疊，

單調遞增堆疊：單調遞增堆疊就是從堆疊底到堆疊頂資料是從大到小，

單調遞減堆疊：單調遞減堆疊就是從堆疊底到堆疊頂資料是從小到大，

括號序列

括號序列是指由 ‘(’和‘)’ 組成的序列,假如一個括號序列中,包含相同數量的左括號和右括號,并且對于每一個右括號,在它的左側都有左括號和他匹配,則這個括號序列就是一個合法括號序列,如(())( )就是一個合法括號序列,但(())(( )不是合法括號序列.

空串是合法的括號序列，

若S是合法的括號序列，則(S)是合法的括號序列，

若S和T分別是合法的括號序列，則ST也是合法的括號序列，

佇列

佇列是一種特殊的線性表，特殊之處在于它只允許在表的前端進行洗掉操作，而在表的后端進行插入操作，和堆疊一樣，佇列是一種操作受限制的線性表，進行插入操作的端稱為隊尾，進行洗掉操作的端稱為隊頭，

單調佇列

單調佇列顧名思義就是一個有規律的佇列，這個佇列的規律是：所有在佇列里的數都必須按遞增（或遞減）的順序列隊，

單調佇列只能解決一個叫滑動視窗的問題，

雙端佇列

雙端佇列是一種具有佇列和堆疊性質的資料結構，即可（也只能）在線性表的兩端進行插入和洗掉，

折半搜索（二分）

前綴和

前綴和是一個陣列的某項下標之前(包括此項元素)的所有陣列元素的和，

差分

差分，一般在大資料里用在以時間為統計維度的分析中，其實就是下一個數值 ，減去上一個數值 ，

二維前綴和：b[x,y]=b[x-1,y]+b[x,y-1]-b[x-1,y-1]+a[x,y]

矩陣求和：S(x1,y1,x2,y2)=b[x2,y2]-b[x1-1,y2]-b[x2,y1-1]+b[x1-1,x2-1]

二維差分：b[x,y]=a[x,y]+a[x-1,y-1]-a[x-1,y]-a[x,y-1]

修改矩形[x1,y1,x2,y2]等價于b[x1,y1]+=v,b[x2+1,y2+1]+=v,b[x1,y2+1]-=v,b[x2+1,y1]-=v，

基數排序（松氏基排）

基本解法

第一步

以LSD為例，假設原來有一串數值如下所示：

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根據個位數的數值，在走訪數值時將它們分配至編號0到9的桶子中：

0

1 81

2 22

3 73 93 43

4 14

5 55 65

6

7

8 28

9 39

第二步

接下來將這些桶子中的數值重新串接起來，成為以下的數列：

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接著再進行一次分配，這次是根據十位數來分配：

0

1 14

2 22 28

3 39

4 43

5 55

6 65

7 73

8 81

9 93

第三步

接下來將這些桶子中的數值重新串接起來，成為以下的數列：

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

這時候整個數列已經排序完畢；如果排序的物件有三位數以上，則持續進行以上的動作直至最高位數為止，

LSD的基數排序適用于位數小的數列，如果位數多的話，使用MSD的效率會比較好，MSD的方式與LSD相反，是由高位數為基底開始進行分配，但在分配之后并不馬上合并回一個陣列中，而是在每個“桶子”中建立“子桶”，將每個桶子中的數值按照下一數位的值分配到“子桶”中，在進行完最低位數的分配后再合并回單一的陣列中，

區間演算法

區間計算與傳統的以數為物件的運算(即點計算)不同，它的運算物件是區間，

由于數字計算機只能使用有限位數表示實數，不能精確表達數學意義上的數值，所以數值的每一步計算都會產生誤差，億萬次計算之后，計算機的“舍入規則”效應可能累積相當大的計算誤差，導致數值計算結果精度嚴重損失，而區間計算的整個程序以“區間”為運算物件，提供區間形式的計算結果，這些運算區間在構造上保證包含資料的真實值，使得結果區間也能夠保證包含資料運算的真實結果，

O(n)-O(1)

四毛子演算法

一種（非常規）分塊后暴力預處理以此來優化復雜度的思想，

RMQ

RMQ，即區間最值查詢，這是一種在線演算法，所謂在線演算法，是指用戶每次輸入一個查詢，便馬上處理一個查詢，RMQ演算法一般用較長時間做預處理，時間復雜度為O(nlogn)，然后可以在O(1)的時間內處理每次查詢，

RMQ標準演算法：先規約成LCA（最近公共祖先），再規約成約束RMQ，O(n)-O(q) online，

首先根據原數列，建立笛卡爾樹，從而將問題在線性時間內規約為LCA問題，LCA問題可以在線性時間內規約為約束RMQ，也就是數列中任意兩個相鄰的數的差都是+1或-1的RMQ問題，約束RMQ有O(n)-O(1)的在線解法，故整個演算法的時間復雜度為O(n)-O(1)，

哈希表

unordered-map（基于哈希實作的映射）

除留余數法

取關鍵字被某個不大于散串列表長m的數p除后所得的余數為散列地址，即 H(key) = key MOD p,p<=m，不僅可以對關鍵字直接取模，也可在折疊、平方取中等運算之后取模，對p的選擇很重要，一般取素數或m，若p選的不好，容易產生同義詞，

雙向平方試判（雙平方探測法 ）
為了解決二次聚集現象發明了雙平方探測法 當沖突產生時 向該沖突點的雙向以步長i^2（1 4 9 16 25…） 探測 若保證散串列的長度是素數且滿足4K+3則可以遍歷整個散串列從而不存在二次聚集現象，

STL

STL 是“Standard Template Library”的縮寫，中文譯為“標準模板庫”，

#include<algorithm>

#include<bits/stdc++.h>（推薦）

stack堆疊

queue佇列

deque雙端佇列

priority_queue優先佇列（堆）

默認是大根堆，如果想讓他是小根堆的話有兩種辦法，其中一種是多載小于號，

pq.swap(pq²)

vector

向量（Vector）是一個封裝了動態大小陣列的順序容器，跟任意其它型別容器一樣，它能夠存放各種型別的物件，可以簡單的認為，向量是一個能夠存放任意型別的動態陣列，

容器特性：

1.順序序列

順序容器中的元素按照嚴格的線性順序排序，可以通過元素在序列中的位置訪問對應的元素，

2.動態陣列

支持對序列中的任意元素進行快速直接訪問，甚至可以通過指標算述進行該操作，提供了在序列末尾相對快速地添加/洗掉元素的操作，

3.能夠感知記憶體分配器的（Allocator-aware）

容器使用一個記憶體分配器物件來動態地處理它的存盤需求，

相當于是個動態陣列，每次可以往末端插入一個元素，下標從0開始，

實作方式是每次不夠大的時候暴力倍長，可以發現均攤是線性的，

v.size()

這個一個unsigned int型別，也就是說對空的vector的size()-1會得到2^32-1，因此寫代碼的時候應帶盡量避免這種寫法，（或者強制型別轉化成int）

v.resize()

其復雜度是O(max(1, resize()中的引數-原來的size()))的，

如果是大小變大的resize()，且可以指定新擴展的位置的值，若未指定則呼叫其默認建構式，例如int之類的會默認是0，

v.clear()和vector<int>().swap(v)的區別，

前者是假裝清空了，實際記憶體沒有被回收，

后者是真的回收了，不過需要和v.size()的大小成正比的時間，

后者的意思是使用vector<>()這句話呼叫無參的建構式生成一個vector<>型別的物件，然后和v交換，之后其生存期結束被銷毀會自動呼叫其~vector<>()解構式，注意<>里面要寫v一樣的型別（例如int）

set/map

分別是集合/映射

內部使用紅黑樹（一種平衡樹）實作，

同樣的當set<>和map<,>中的第一個引數是自定義型別的時候

需要重新定義小于號，

復雜度基本上是O(log(當前大小))

map相當于是一個下標可以是任何數值的陣列，如果訪問時沒有賦值就會回傳零，

m[x]

哪怕你什么也不干只寫一個m[x];也會新建一個點，

因此當你想知道map中是否存在這個映射的時候最好使用m.count(x)，

很多時候可以有效卡常，

multiset和multimap

是可重集合和可重映射，

有兩個注意的：第一個是count函式復雜度變成了O(lg(集合大小)+答案)的，也就是如果有很多相同元素，那么count函式代價很大，

第二個是洗掉x的話，使用s.erase(x)會把所有權值為x的洗掉，

如果只想刪掉一個需要s.erase(s.find(x))，

unordered_set和unordered_map

基于哈希實作的集合和映射，

基本上里面的型別只能是int,long long,double這種非自定義型別， 因為其基于哈希）

在c++11及以后存在，之前沒有，亂用可能會CE，

空間常數比較大，時間常數不小，比陣列訪問慢很多，慎用，

不能順序遍歷，不支持lower_bound，

迭代器

只介紹set/map的迭代器，

bitset

高精度壓位二進制，

所有時間復雜度是線性的操作，常數都是1/32大概，

下標從0開始，

補充

namespace

命名空間，之后寫代碼長的時候用來避免變數名或者函式名重名的，主要是同一個namespace里面默認使用自己名字空間的東西，

std一般是教師專用賬號，

對于10⁷~10⁸的資料，一般運行1s左右，

標籤：C++

上一篇：需要解釋為什么我的luaoop回傳不正確的值/資料

下一篇：Java將彩色PDF轉為灰度