數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

1數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)基本概念復(fù)雜度每秒操作次數(shù):約10^7在這個限制下時間復(fù)雜度一定的算法存在能處理的規(guī)模上限復(fù)雜度數(shù)量級最大規(guī)模O(logN)>>10^20很大O(N^1/2)10^1210^14O(N)10^610^7O(NlogN)10^510^6O(N^2)10002500O(N^3)100500O(N^4)5050O(2^N)2020O(3^N)1415O(N!)910刪除和查找一個 薄，方便進行操作： ，刪除，查找O(n)邏輯結(jié)構(gòu)：無序線性表結(jié)構(gòu)：數(shù)組：插到尾部比較方便，O(1)刪除：“合并兩半”導(dǎo)致元素移動，查找：

O(n)結(jié)構(gòu)：鏈表：插到頭部比較方便，O(1)刪除：（找到被刪除元素后）O(1)查找：

O(n)棧/隊列棧Stack后進先出(Last

In只在一端進行操作7531Out,

LIFO)Push棧頂指針top入棧：stack[++top]=x

top出棧：top--Pop應(yīng)用括號匹配表達式求值遞歸(系統(tǒng)棧，手寫棧)e.g.括號匹配：求最長的合法括號串))[{}]] The

answer

is

4

(“[{}]”)棧應(yīng)用–括號匹配算法：記錄每個下標(biāo)向左延伸的最大合法序列長度dp[x]一個棧，棧內(nèi)記錄下標(biāo)for(int

i

=

1;

i

<=

len;

++i)

{if(s[i]是左括號)

{stack[++top]=

i;}else

if

(s[i]與棧頂括號匹配)

{dp[i]

=

dp[stack[top]-1]

+

i

–

stack[top]

+

1;--top;}else

top

=

0;}隊列Queue先進先出

(

In,headOut,

FIFO)入隊queue[tail++]=x;出隊head++;隊列為空:

head>=tail7

5

3

1頭尾指針head和tailpoppushtail應(yīng)用廣度優(yōu)先搜索循環(huán)隊列：head=(head+1)%SIZE;tail=(tail+1)%SIZE;隊滿：head==(tail+1)%SIZE應(yīng)用:優(yōu)化Bellman-Ford算法->SPFA最短路算法單調(diào)隊列雙端隊列：隊列的兩端都可以刪除元素Sliding

Windows：

一段區(qū)間最值DP優(yōu)化形如dp[x]=min(dp[k],x-A<=k<x)的轉(zhuǎn)移方程可以使用上述技巧優(yōu)化，其中A是一個定值例：Sliding

WindowWindow

positionum

value[13-1]

-3

5

3

6

731[3-1

-3]

5

3

6

7313[-1

-3 5]

3

6

7513-1

[-3

5 3]

6

7513-1

-3[5

3 6]

7613-1

-3 5

[3

6

7]7并查集有根樹N個點通過N-1條邊相連通除根以外，每個節(jié)點有唯一確定的父節(jié)點并查集(Disjoint-Set)合并兩個集合查詢某個結(jié)點屬于的集合每個節(jié)點屬于一棵有根樹，樹的根節(jié)點即為集合并查集(Disjoint-Set)12326789101232134334set(i)表示i號節(jié)點的父節(jié)點rootiSet(i)并查集(Disjoint-set)Step

1:有5個元素，最開始每個元素各自構(gòu)成一個集合，即有5個集合，他們自己就構(gòu)成了各自集合的代表元。i12345set[i]12345并查集(Disjoint-set)Step2:合并元素1和2所在的集合，找到各自集合的代表元（分別為1和2），將1作為這個新合并生成集合的代表元，即作為這棵有根樹的根。i12345set[i]11345并查集(Disjoint-set)Step

3:合并5和4所在的集合，找到各自集合的代表元（分別為5和4），將5作為新合并生成集合的代表元。i12345set[i]11355并查集(Disjoint-set)Step

4:合并元素2和4所在的集合，找到各自集合的代表元（分別為1和5），將1作為這個新合并生成集合的代表元。i12345set[i]11351并查集(Disjoint-Set)定義集合 所在節(jié)點的父節(jié)點是它本身其它點令i=set(i)向上尋找即可int

findSet(int

x){if

(x

==

set[x])return

x;elsereturn

findSet(set[x]);}void

unionSet(int

x,

int

y){int

fx

=

findSet(x);int

fy

=

findSet(y);set[fy]

=

fx;}這段程序有什么問題？復(fù)雜度Step1Step2…UnionSet(2,1)UnionSet(3,1)findSet將被執(zhí)行近n^2次Step

n-1UnionSet(n,1)123458671、啟發(fā)式合并（每次將深度小的向大的合并）（略為復(fù)雜，而且效果不好）2、路徑壓縮（并查集中非常重要的優(yōu)化）路徑壓縮路徑壓縮（Path

Compression）思想：每次查找的時候，把經(jīng)過路徑上的點的父親都設(shè)為根步驟:第一步，找到根結(jié)點第二步，修改查找路徑上的所有節(jié)點，將它們都指向根結(jié)點可以證明m次操作的總時間復(fù)雜度為k*O(m)，k是一個接近1的常數(shù)，即幾乎是線性的。使用路徑壓縮的并查集算法不需要再使用啟發(fā)式合并。int

findSet(int

x){if

(x

==set[x])return

x;elsereturn

set[x]=findSet(set[x]);}void

unionSet(int

x,

int

y){int

fx

=

findSet(x);int

fy

=findSet(y);set[fy]

=

fx;}應(yīng)用無向圖最小生成樹的Kruskal算法（請自行參考相應(yīng)書籍）圖的連通性判斷，求兩點是否屬于同一集合應(yīng)用Almost

Union-Find（UVA

11987）n個數(shù)，從1到n，初始狀態(tài)分屬不同集合操作1：如果數(shù)字p和數(shù)字q不屬于同一集合，則合并它們所在的集合操作2：如果數(shù)字p和數(shù)字q不屬于同一集合，則把p

q所在的集合（并在p原來所在的集合中刪除p）操作3：詢問某個數(shù)字p所在集合的元素個數(shù)以及總和應(yīng)用在根節(jié)點記錄

個數(shù)

和

總和 （很好

）合并兩個集合（操作1） （很好完成）怎樣刪除一個元素？Solution改刪除操作為合并操作操作2：把9合并入集合1，新建10號節(jié)點代替9號，從此9號點作廢89Others字典樹Trie設(shè)計一個數(shù)據(jù)結(jié)構(gòu)，能夠 大量字符串判斷某個特定字符串是否存在（不是子串）類似于在字典中查詢某個特定單詞是否出現(xiàn)字典樹Trie每條邊代表一個特定的字符從根節(jié)點到每個節(jié)點的路徑就是某個字符串的前綴Trie一個字符串從根節(jié)點出發(fā)，判斷字母所對應(yīng)的邊是否存在存在

對應(yīng)子節(jié)點不存在新建子節(jié)點對于終點做特殊標(biāo)記查詢一個字符串直接尋找是否存在對應(yīng)路徑，并且查看路徑的終點是否有特殊標(biāo)記Triestruct

Trie

{Trie

*ch[26];//記錄從這個節(jié)點出發(fā)對應(yīng)26個字母的子節(jié)點

bool

End;//表示這個節(jié)點是否是一個字符串的結(jié)尾};Trie

tr[MAXN];二叉堆目標(biāo):

元素O(logn),

取最大值O(1),

刪除元素O(logn)第一特點(形態(tài)):完全二叉樹(用數(shù)組表示)第二特點(數(shù)據(jù)):每子樹最大值在根上:維持第一特點:插到最后維持第二特點:遞歸向上交換(判斷是否比父親大)刪除最大值維持第一特點:根與最后節(jié)點交換,再刪除維持第二特點:遞歸向下交換(如果需要,和較大兒子交換)二叉堆平衡二叉搜索樹(Self-balancing

Binary

Search

Tree)元素，刪除元素，查找某個元素，查詢剛好比x大的元素，查詢剛好比x小的元素，查找元素，查詢?yōu)閗的元素。所有操作為O(logn)。size域）STL：map,

set，但不能實現(xiàn)最后兩個操作（沒有樹種：SBT,

Treap,

Splay-Tree,

RB-Tree…STL簡介STLStandard

Templa

ibrary封裝了一些常用的數(shù)據(jù)結(jié)構(gòu)類型棧stack#include

<stack>using

namespace

std;stack

<int>

s;s.top();s.push(x);s.pop();s.empty();s.size();//取棧頂//入棧//出棧//是否為空//棧中元素個數(shù)隊列queue#include

<queue>using

namespace

std;queue

<int>

q;q.front();q.push(x);q.pop();q.empty();q.size();//取隊頭//入隊//出隊//是否為空//隊列中元素個數(shù)優(yōu)先隊列類似于堆的特性#include

<queue>using

namespace

std;priority_queue