線性數(shù)據(jù)結(jié)構(gòu)
沙河網(wǎng)站制作公司哪家好，找成都創(chuàng)新互聯(lián)！從網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、響應(yīng)式網(wǎng)站建設(shè)等網(wǎng)站項(xiàng)目制作，到程序開發(fā)，運(yùn)營維護(hù)。成都創(chuàng)新互聯(lián)于2013年開始到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選成都創(chuàng)新互聯(lián)。
線性結(jié)構(gòu)是一個(gè)有序數(shù)據(jù)元素的集合。
常用的線性結(jié)構(gòu)
線性表，棧，隊(duì)列，雙隊(duì)列，串(一維數(shù)組)。
非線性數(shù)據(jù)結(jié)構(gòu)
關(guān)于廣義表、數(shù)組(高維)，是一種非線性的數(shù)據(jù)結(jié)構(gòu)。
常見的非線性結(jié)構(gòu)有：二維數(shù)組，多維數(shù)組，廣義表，樹(二叉樹等)，圖
線性表（線性存儲結(jié)構(gòu)）
將具有“一對一”關(guān)系的數(shù)據(jù)“線性”地存儲到物理空間中，這種存儲結(jié)構(gòu)就稱為線性存儲結(jié)構(gòu)（簡稱線性表）。
使用線性表存儲的數(shù)據(jù)，如同向數(shù)組中存儲數(shù)據(jù)那樣，要求數(shù)據(jù)類型必須一致，也就是說，線性表存儲的數(shù)據(jù)，要么全部都是整形，要么全部都是字符串。一半是整形，另一半是字符串的一組數(shù)據(jù)無法使用線性表存儲。
將數(shù)據(jù)依次存儲在連續(xù)的整塊物理空間中，這種存儲結(jié)構(gòu)稱為順序存儲結(jié)構(gòu)（簡稱順序表）；數(shù)據(jù)分散的存儲在物理空間中，通過一根線保存著它們之間的邏輯關(guān)系，這種存儲結(jié)構(gòu)稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)（簡稱鏈表）
某一元素的左側(cè)相鄰元素稱為“直接前驅(qū)”，位于此元素左側(cè)的所有元素都統(tǒng)稱為“前驅(qū)元素”；某一元素的右側(cè)相鄰元素稱為“直接后繼”，位于此元素右側(cè)的所有元素都統(tǒng)稱為“后繼元素”
棧
棧又名堆棧，它是一種運(yùn)算受限的線性表。限定僅在表尾進(jìn)行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個(gè)棧插入新元素又稱作進(jìn)棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個(gè)棧刪除元素又稱作出?；蛲藯?，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。
單調(diào)棧
單調(diào)棧中存放的數(shù)據(jù)應(yīng)該是有序的，所以單調(diào)棧也分為單調(diào)遞增棧和單調(diào)遞減棧。
單調(diào)遞增棧：單調(diào)遞增棧就是從棧底到棧頂數(shù)據(jù)是從大到小。
單調(diào)遞減棧：單調(diào)遞減棧就是從棧底到棧頂數(shù)據(jù)是從小到大。
括號序列
括號序列是指由 ‘(’和‘)’ 組成的序列,假如一個(gè)括號序列中,包含相同數(shù)量的左括號和右括號,并且對于每一個(gè)右括號,在它的左側(cè)都有左括號和他匹配,則這個(gè)括號序列就是一個(gè)合法括號序列,如(())( )就是一個(gè)合法括號序列,但(())(( )不是合法括號序列.
空串是合法的括號序列。
若S是合法的括號序列，則(S)是合法的括號序列。
若S和T分別是合法的括號序列，則ST也是合法的括號序列。
隊(duì)列
隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端進(jìn)行刪除操作，而在表的后端進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。
單調(diào)隊(duì)列
單調(diào)隊(duì)列顧名思義就是一個(gè)有規(guī)律的隊(duì)列，這個(gè)隊(duì)列的規(guī)律是：所有在隊(duì)列里的數(shù)都必須按遞增（或遞減）的順序列隊(duì)。
單調(diào)隊(duì)列只能解決一個(gè)叫滑動(dòng)窗口的問題。
雙端隊(duì)列
雙端隊(duì)列是一種具有隊(duì)列和棧性質(zhì)的數(shù)據(jù)結(jié)構(gòu)，即可（也只能）在線性表的兩端進(jìn)行插入和刪除。
折半搜索（二分）
前綴和
前綴和是一個(gè)數(shù)組的某項(xiàng)下標(biāo)之前(包括此項(xiàng)元素)的所有數(shù)組元素的和。
差分
差分，一般在大數(shù)據(jù)里用在以時(shí)間為統(tǒng)計(jì)維度的分析中，其實(shí)就是下一個(gè)數(shù)值 ，減去上一個(gè)數(shù)值 。
二維前綴和：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]等價(jià)于b[x1,y1]+=v,b[x2+1,y2+1]+=v,b[x1,y2+1]-=v,b[x2+1,y1]-=v。
基數(shù)排序（松氏基排）
基本解法
第一步
以LSD為例，假設(shè)原來有一串?dāng)?shù)值如下所示：
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根據(jù)個(gè)位數(shù)的數(shù)值，在走訪數(shù)值時(shí)將它們分配至編號0到9的桶子中：
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
第二步
接下來將這些桶子中的數(shù)值重新串接起來，成為以下的數(shù)列：
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接著再進(jìn)行一次分配，這次是根據(jù)十位數(shù)來分配：
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
第三步
接下來將這些桶子中的數(shù)值重新串接起來，成為以下的數(shù)列：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
這時(shí)候整個(gè)數(shù)列已經(jīng)排序完畢；如果排序的對象有三位數(shù)以上，則持續(xù)進(jìn)行以上的動(dòng)作直至最高位數(shù)為止。
LSD的基數(shù)排序適用于位數(shù)小的數(shù)列，如果位數(shù)多的話，使用MSD的效率會(huì)比較好。MSD的方式與LSD相反，是由高位數(shù)為基底開始進(jìn)行分配，但在分配之后并不馬上合并回一個(gè)數(shù)組中，而是在每個(gè)“桶子”中建立“子桶”，將每個(gè)桶子中的數(shù)值按照下一數(shù)位的值分配到“子桶”中。在進(jìn)行完最低位數(shù)的分配后再合并回單一的數(shù)組中。
區(qū)間算法
區(qū)間計(jì)算與傳統(tǒng)的以數(shù)為對象的運(yùn)算(即點(diǎn)計(jì)算)不同，它的運(yùn)算對象是區(qū)間。
由于數(shù)字計(jì)算機(jī)只能使用有限位數(shù)表示實(shí)數(shù)，不能精確表達(dá)數(shù)學(xué)意義上的數(shù)值，所以數(shù)值的每一步計(jì)算都會(huì)產(chǎn)生誤差。億萬次計(jì)算之后，計(jì)算機(jī)的“舍入規(guī)則”效應(yīng)可能累積相當(dāng)大的計(jì)算誤差，導(dǎo)致數(shù)值計(jì)算結(jié)果精度嚴(yán)重?fù)p失。而區(qū)間計(jì)算的整個(gè)過程以“區(qū)間”為運(yùn)算對象，提供區(qū)間形式的計(jì)算結(jié)果。這些運(yùn)算區(qū)間在構(gòu)造上保證包含數(shù)據(jù)的真實(shí)值，使得結(jié)果區(qū)間也能夠保證包含數(shù)據(jù)運(yùn)算的真實(shí)結(jié)果。
O(n)-O(1)
四毛子算法
一種（非常規(guī)）分塊后暴力預(yù)處理以此來優(yōu)化復(fù)雜度的思想。
RMQ
RMQ，即區(qū)間最值查詢，這是一種在線算法，所謂在線算法，是指用戶每次輸入一個(gè)查詢，便馬上處理一個(gè)查詢。RMQ算法一般用較長時(shí)間做預(yù)處理，時(shí)間復(fù)雜度為O(nlogn)，然后可以在O(1)的時(shí)間內(nèi)處理每次查詢。
RMQ標(biāo)準(zhǔn)算法：先規(guī)約成LCA（最近公共祖先），再規(guī)約成約束RMQ，O(n)-O(q) online。
首先根據(jù)原數(shù)列，建立笛卡爾樹，從而將問題在線性時(shí)間內(nèi)規(guī)約為LCA問題。LCA問題可以在線性時(shí)間內(nèi)規(guī)約為約束RMQ，也就是數(shù)列中任意兩個(gè)相鄰的數(shù)的差都是+1或-1的RMQ問題。約束RMQ有O(n)-O(1)的在線解法，故整個(gè)算法的時(shí)間復(fù)雜度為O(n)-O(1)。
哈希表
unordered-map（基于哈希實(shí)現(xiàn)的映射）
除留余數(shù)法
取關(guān)鍵字被某個(gè)不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址。即 H(key) = key MOD p,p<=m。不僅可以對關(guān)鍵字直接取模，也可在折疊、平方取中等運(yùn)算之后取模。對p的選擇很重要，一般取素?cái)?shù)或m，若p選的不好，容易產(chǎn)生同義詞。
雙向平方試判（雙平方探測法）
為了解決二次聚集現(xiàn)象發(fā)明了雙平方探測法 當(dāng)沖突產(chǎn)生時(shí) 向該沖突點(diǎn)的雙向以步長i^2（1 4 9 16 25…） 探測若保證散列表的長度是素?cái)?shù)且滿足4K+3則可以遍歷整個(gè)散列表從而不存在二次聚集現(xiàn)象。
STL
STL 是“Standard Template Library”的縮寫，中文譯為“標(biāo)準(zhǔn)模板庫”。
#include
#include
sort()
sort函數(shù)用于給一個(gè)數(shù)組進(jìn)行排序,在algorithm庫里。
使用方法為sort(v.begin(),v.end(),cmp)),這里的v.begin()是開始的指針位置，v.end()是結(jié)束的指針位置（這里的表示是左閉右開，也就是說v.end()并不在排序內(nèi)容里），cmp可要可不要，如果使用的是自定義類型且沒有重載運(yùn)算符就一定需要。
這個(gè)數(shù)組的類型可以是自定義類型或者STL中的vector，需要注意的是如果采用的是自定義類型則需要重載運(yùn)算符（也可以如上面說的一樣用cmp）。
stack
模擬棧，在
stack
常用函數(shù)
A.push(a)；
入棧
A.pop()；
出棧
A.top()；
返回棧頂元素（但不出棧）
queue
模擬隊(duì)列，在
queue
常用函數(shù)
A.push(a)；
入隊(duì)
A.pop()；
出隊(duì)
A.front()；
返回隊(duì)首元素（但不出隊(duì)）
deque
雙端隊(duì)列
priority queue
優(yōu)先隊(duì)列，一個(gè)類似于堆的數(shù)據(jù)結(jié)構(gòu),在
默認(rèn)是大根堆，如果想讓他是小根堆的話有兩種辦法，其中一種是重載小于號。
能以O(shè)(logN)復(fù)雜度完成插入元素，刪除最值，尋找最值。
Priority_queue
常用函數(shù)
A.push(a)；
插入
A.pop()；
刪除最值（默認(rèn)為最大值）
A.top()；
返回最值（但不刪除）
pair
一個(gè)包含兩個(gè)可以不同的數(shù)據(jù)值的類型。
pair
往往Type1,Type2都是標(biāo)準(zhǔn)類型，但如果是自定義類型，需要重定義運(yùn)算符；
常用函數(shù)
賦值:make_pair(t1,t2)；
返回對應(yīng)的值:A.first,A.second；
vector
向量（Vector）是一個(gè)封裝了動(dòng)態(tài)大小數(shù)組的順序容器。跟任意其它類型容器一樣，它能夠存放各種類型的對象?？梢院唵蔚恼J(rèn)為，向量是一個(gè)能夠存放任意類型的不定長的動(dòng)態(tài)數(shù)組，在vector庫里。
定義方式:vector
容器特性
順序序列
順序容器中的元素按照嚴(yán)格的線性順序排序?？梢酝ㄟ^元素在序列中的位置訪問對應(yīng)的元素。
動(dòng)態(tài)數(shù)組
支持對序列中的任意元素進(jìn)行快速直接訪問，甚至可以通過指針?biāo)闶鲞M(jìn)行該操作。提供了在序列末尾相對快速地添加/刪除元素的操作。
能夠感知內(nèi)存分配器的（Allocator-aware）
容器使用一個(gè)內(nèi)存分配器對象來動(dòng)態(tài)地處理它的存儲需求。
相當(dāng)于是個(gè)動(dòng)態(tài)數(shù)組，每次可以往末端插入一個(gè)元素，下標(biāo)從0開始。
實(shí)現(xiàn)方式是每次不夠大的時(shí)候暴力倍長，可以發(fā)現(xiàn)均攤是線性的。
常用操作
A.clear()；
清空
A.push_back(a)；
尾部添加元素
A.pop_back()；
尾部刪除元素
A.empty()；
檢查是否為空，空返回true
v.size()
這個(gè)一個(gè)unsigned int類型。也就是說對空的vector的size()-1會(huì)得到2^32-1。因此寫代碼的時(shí)候應(yīng)帶盡量避免這種寫法。（或者強(qiáng)制類型轉(zhuǎn)化成int）
v.resize()
其復(fù)雜度是O(max(1, resize()中的參數(shù)-原來的size()))的。
如果是大小變大的resize()，且可以指定新擴(kuò)展的位置的值。若未指定則調(diào)用其默認(rèn)構(gòu)造函數(shù)，例如int之類的會(huì)默認(rèn)是0。
v.clear()和vector
前者是假裝清空了，實(shí)際內(nèi)存沒有被回收。
后者是真的回收了，不過需要和v.size()的大小成正比的時(shí)間。
后者的意思是使用vector<>()這句話調(diào)用無參的構(gòu)造函數(shù)生成一個(gè)vector<>類型的對象，然后和v交換，之后其生存期結(jié)束被銷毀會(huì)自動(dòng)調(diào)用其~vector<>()析構(gòu)函數(shù)。注意<>里面要寫v一樣的類型（例如int）
set
一個(gè)存儲集合的容器，在set庫里。
map相當(dāng)于是一個(gè)下標(biāo)可以是任何數(shù)值的數(shù)組，如果訪問時(shí)沒有賦值就會(huì)返回零。
內(nèi)部使用紅黑樹（一種平衡樹）實(shí)現(xiàn)。
當(dāng)set<>中的第一個(gè)參數(shù)是自定義類型的時(shí)候需要重新定義小于號。
復(fù)雜度基本上是O(log(當(dāng)前大小))。
定義方式:set
常用函數(shù)
A.insert(a)；
插入a
A.erase(a)；
刪除a:
A.find(a)；
查找a，如果查找成功，返回對應(yīng)指針，查找失敗返回尾指針
A.begin(),A.end()；
返回頭指針與尾指針，尾指針不存儲具體內(nèi)容
map
存儲一個(gè)從key到value的映射。某種意義上就是“廣義”數(shù)組，在map庫里。
map相當(dāng)于是一個(gè)下標(biāo)可以是任何數(shù)值的數(shù)組，如果訪問時(shí)沒有賦值就會(huì)返回零。
內(nèi)部使用紅黑樹（一種平衡樹）實(shí)現(xiàn)。
當(dāng)map<,>中的第一個(gè)參數(shù)是自定義類型的時(shí)候需要重新定義小于號。
復(fù)雜度基本上是O(log(當(dāng)前大小))
map
可以通過A[B]=C這種形式賦值，B為Type1，C為Type2。
常用函數(shù)
A.clear()；
清空
A.empty()；
判斷是否為空
A.insert(pair
插入（不建議這么寫）
A.erase(B)；
刪除，B可以是key值也可以是指針
A.begin(),A.end()；
頭指針，尾指針
m[x]
哪怕你什么也不干只寫一個(gè)m[x];也會(huì)新建一個(gè)點(diǎn)。
因此當(dāng)你想知道m(xù)ap中是否存在這個(gè)映射的時(shí)候最好使用m.count(x)。
很多時(shí)候可以有效卡常。
multiset和multimap
是可重集合和可重映射。
有兩個(gè)注意的：第一個(gè)是count函數(shù)復(fù)雜度變成了O(lg(集合大小)+答案)的，也就是如果有很多相同元素，那么count函數(shù)代價(jià)很大。
第二個(gè)是刪除x的話，使用s.erase(x)會(huì)把所有權(quán)值為x的刪除。
如果只想刪掉一個(gè)需要s.erase(s.find(x))。
unordered_set和unordered_map
基于哈希實(shí)現(xiàn)的集合和映射。
基本上里面的類型只能是int,long long,double這種非自定義類型。 因?yàn)槠浠诠＃?/p>
在c++11及以后存在，之前沒有，亂用可能會(huì)CE。
空間常數(shù)比較大，時(shí)間常數(shù)不小，比數(shù)組訪問慢很多，慎用。
不能順序遍歷，不支持lower_bound。
迭代器
只介紹set/map的迭代器。
bitset
高精度壓位二進(jìn)制。
一個(gè)用于處理二進(jìn)制串的“數(shù)組”,在
所有時(shí)間復(fù)雜度是線性的操作，常數(shù)都是1/32大概。
下標(biāo)從0開始。
bitset
支持所有位運(yùn)算： << , >> , & , | , ^ ；
常用函數(shù)
A.count()；
統(tǒng)計(jì)1的個(gè)數(shù)
A.reset()；
清0
A.set()；
全賦為1
A.size()；
返回位數(shù)
lower bound()/upper bound()
lower_bound(v.begin(),v.end(),c)可以在一個(gè)有序數(shù)組當(dāng)中找出剛好大于或等于c的數(shù)，在algorithm庫里,可以使用自定義類型，用法與sort相類似。
upper_bound函數(shù)類似，這個(gè)函數(shù)則是在有序數(shù)組中找出剛好大于c的數(shù)。
next permutation/prev permutation(全排列算法)
algorithm頭文件中包含了next_permutation(v.begin(),v.end())和prev_permutation(v.begin(),v.end())兩個(gè)全排列函數(shù)，分別給出一個(gè)序列在全排列中的下一個(gè)和上一個(gè)序列(按字典序)，如果存在這樣的序列則返回true，不存在則返回false，但仍會(huì)得到一個(gè)序列。
對于一個(gè)任意元素不相同的序列來說，正序排列是最小的排列方式，相應(yīng)的逆序排列是最大的排列方式，以整數(shù)序列{1,2,3}為例，{1,2,3}是第一個(gè)排列，{3,2,1}則是最后一個(gè)排列，因此序列{1,2,3}沒有上一個(gè)序列，{3,2,1}沒有下一個(gè)序列。
pq.swap(pq2)
補(bǔ)充
namespace
命名空間，之后寫代碼長的時(shí)候用來避免變量名或者函數(shù)名重名的。主要是同一個(gè)namespace里面默認(rèn)使用自己名字空間的東西。
std一般是教師專用賬號。
對于107~108的數(shù)據(jù)，一般運(yùn)行1s左右。
并非原創(chuàng)，僅是整理，請見諒
重慶分公司
重慶分公司
