数据结构讲稿

这个数据结构讲稿是NOIP普及组-提高组难度的。下放附了部分常用的数据结构的代码实现。

数据结构v1.1

数据结构 讲义 v1.1

栈
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 10000
 
int stack[MAXN],tops=-1;
 
void push_stack(int x) {
stack[++tops] = x;
}
 
int pop_stack() {
return stack[tops--];
}
 
int main() {
push_stack(1);
push_stack(2);
cout<<pop_stack()<<endl;
cout<<pop_stack()<<endl;
}

队列
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 10000
 
int queue[MAXN],head=-1,tail=-1;
 
//++tail 表示把tail值加1，然后返回tail值
//tail++ 表示把tail值加1，然后返回之前的tail值
 
void push_queue(int x) {
queue[++head] = x;
}
 
int pop_queue() {
return queue[++tail];
}
 
bool is_empty() {
return head == tail;
}
 
int main() {
}

优先队列
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
 
int main() {
priority_queue<int> PQ;
PQ.push(1);
PQ.push(3);
PQ.push(2);
cout<<PQ.top()<<endl;PQ.pop();
cout<<PQ.top()<<endl;PQ.pop();
cout<<PQ.top()<<endl;PQ.pop();
}

领接表
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXV 10000 //最大点数
#define MAXE 200000 //最大边数
 
struct Edge {
int np;//下一个顶点的编号
int val;//边权
Edge *next;//链表里面的指针
}E[MAXE],*V[MAXV];
int tope = -1;
 
void add_edge(int x,int y,int v) {
E[++tope].val = v;
E[tope].next = V[x];
E[tope].np = y;
V[x] = &E[tope];
}
 
// V[1] = (np=3,val=3) -> (np=2,val=2) -> NULL
// V[2] = (np=3,val=1) -> NULL
// V[3] = (np=1,val=3) -> NULL
 
int main() {
freopen("input.txt","r",stdin);
int n;//点数
int m;//边数
scanf("%d %d",&n,&m);
for (int i=0;i<m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add_edge(x,y,z);
}
for (int now=1;now<=n;now++){
for (Edge *ne=V[now];ne;ne=ne->next){
cout<<"EDGE "<<now<<"->"<<ne->np<<"("<<ne->val<<")"<<endl;
}
}
}

指针
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
using namespace std;
 
//0x12341234
//...........................................
//                   aaaa
//                   ^
//       bbbbbbbb
//       ^
//      ^
// cccc
//
//
struct aaa{
int val,a2;
}sa;
 
int main() {
int a,c;
int b[2];
b[0] = 123;
b[1] = 312;
a = 1;
c = 2;
 
int *ptr_a = &a;
cout<<"PTR_A = "<<ptr_a<<endl;
cout<<"A = "<<a<<endl;
cout<<"*PTR_A = "<<(*ptr_a)<<endl;
(*ptr_a) = -1;
cout<<"*PTR_A = "<<(*ptr_a)<<endl;
cout<<"A = "<<a<<endl;
 
cout<<"B = "<<b<<endl;
cout<<"*B = "<<*b<<endl;
cout<<"B[1] = "<<b[1]<<endl;
cout<<"*(B+1) = "<<*(b+1)<<endl;
 
cout<<"(A+1) = "<<*(ptr_a+1)<<endl;
 
//一个struct的指针可以使用->访问成员变量
aaa *ptr_sa = &sa;
cout<<"(*ptr_sa).val"<<((*ptr_sa).val)<<endl;
cout<<"ptr_sa -> val"<<ptr_sa->val<<endl;
}

ST表
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
using namespace std;
#define MAXN 100000
int jump[MAXN][20];
int a[MAXN];
int ff[MAXN];
 
//  a << b
//  a >> b
//
//  00000000000011
//  00000000000001
//  00000000000110
//  00000000001100
 
int main() {
scanf("%d",&n);
for (int i=0;i<n;i++)
scanf("%d",a+i);
 
memset(ff,-1,sizeof(ff));
for (int i=0;(1<<i)<MAXN;i++)
ff[1<<i] = 1<<i;
for (int i=1;i<MAXN;i++)
if (ff[i] == -1)
ff[i] = ff[i-1];
 
// 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
// . . . . . . . . . .  .  .  .  .  .  .  .  .
//   1 2   4       8                     16
// - 1 2 2 4 4 4 4 8 8  8  8  8  8  8  8 16 16
for (int i=0;i<n;i++)
jump[i][0] = a[i];
for (int i=1;i<20;i++)
for (int j=0;j+(1<<i)-1<n;j++)
jump[j][i] = max(jump[j][i-1],jump[j+(1<<(i-1))][i-1]);
//jump[i][0]->[i,i]
//jump[i][j]
//[3,3+2^4-1]
//[3,3+2^3-1] [3+2^3,3+2^4-1]
//
// . . . . . . . . . . q q q q q q q q q q q . . . . .
// . . . . . . . . . . a a a a a a a a
// . . . . . . . . . . . . . a a a a a a a a . . . . .
scanf("%d",&m);
for (int i=0;i<m;i++) {
scanf("%d%d",&l,&r);
int len = r-l+1;
int k = ff[len];
int ans = max(jump[l][k],jump[r-(1<<k)+1][r]);
printf("%d\n",ans);
}
}
 
//jump[i][j] 表示区间[i,i+2^j-1]的最大值

树状数组
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 100000
#define lowbit(x) ((x) & (-(x)))
int tarr[MAXN];//树状数组
 
void AddTarr(int pos,int v) {
while (pos < MAXN) {
tarr[pos] += v;
pos += lowbit(pos);
}
}
 
int QryTarr(int pos) {
int res = 0;
while (pos) {
res += tarr[pos];
pos -= lowbit(pos);
}
return res;
}
 
int main() {
int n;
scanf("%d",&n);
for (int i=1;i<=n;i++) { int x; scanf("%d",&x); AddTarr(i,x); }
int m; scanf("%d",&m);
for (int i=0;i<m;i++) {
int cid; scanf("%d",&cid);
if (cid == 0) {//单点加操作
int x,v;
scanf("%d%d",&x,&v);
AddTarr(x,v);
}else if (cid == 1) {//区间和查询
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",QryTarr(r) - QryTarr(l-1));
}
}
}

字典树
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXS 10000
#define MAXT 100000
char buffer[MAXS];
 
struct TrieNode {
int total;
int nxt[26];
}trie[MAXT];
int topt = 1;
int root = 1;
 
void AddTrie(char* ptr) {
int now = root;
while (*ptr) {
//*ptr-'a'
if (!trie[now].nxt[*ptr-'a'])
trie[now].nxt[*ptr-'a'] = ++topt;
now = trie[now].nxt[*ptr-'a'];
trie[now].total ++;
ptr++;
}
}
 
int QryTrie(char *ptr) {
int now = root;
while (*ptr) {
if (!trie[now].nxt[*ptr-'a'])
return 0;
now = trie[now].nxt[*ptr-'a'];
ptr++;
}
return trie[now].total;
}
int main() {
freopen("input.txt","r",stdin);
int n,m;
scanf("%d%d\n",&n,&m);
for (int i=0;i<n;i++) {
scanf("%s\n",buffer);
AddTrie(buffer);
}
for (int i=0;i<m;i++) {
scanf("%s\n",buffer);
cout<<QryTrie(buffer)<<endl;
}
}

并查集
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;
#define MAXN 101000
int uf[MAXN];
 
void init() {
for (int i=0;i<n;i++)
uf[i] = i;
}
 
int get_uf(int x) {
return uf[x] == x ? x : uf[x] = get_uf(uf[x]);
}
 
bool join(int x,int y) {
if (get_uf(x) == get_uf(y))
return false;
uf[get_uf(x)] = get_uf(y);
return true;
}
 
int main() {
}

线段树（堆式建树）
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<algorithm>
#include<cassert>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 100000
#define MAXT MAXN*4
#define root 1
#define lch ((now<<1))
#define rch ((now<<1)^1)
#define smid ((l+r)>>1) //(l+r)/2
 
//堆式线段树
struct sgt_node {
int sum;
int l,r;
}sgt[MAXT];
int a[MAXN];
 
void update(int now) {
sgt[now].sum = sgt[lch].sum + sgt[rch].sum;
}
 
void build_sgt(int now,int l,int r) {//建立一个以now为根的线段树，这个线段树对应区间l,r
sgt[now].l = l;
sgt[now].r = r;
if (l == r) {
sgt[now].sum = a[l];
return ;
}
build_sgt(lch,l,smid);
build_sgt(rch,smid+1,r);
update(now);
}
 
int query_sgt(int now,int l,int r,int x,int y) {//查询以now为根的线段树，线段树now节点对应区间为[l,r]，而查询区间为[x,y]
assert(l == sgt[now].l  && r == sgt[now].r);
if (l == x && r == y)
return sgt[now].sum;
if (y <= smid)
return query_sgt(lch,l,smid,x,y);
else if (smid < x) // smid+1 <= x
return query_sgt(rch,smid+1,r,x,y);
else
return query_sgt(lch,l,smid,x,smid) + query_sgt(rch,smid+1,r,smid+1,y);
}
 
void modify_sgt(int now,int l,int r,int pos,int val) {//修改位置pos的值为val
assert(l == sgt[now].l  && r == sgt[now].r);
if (l == r) { //l == r && r == pos
sgt[now].sum = val;
return ;
}
if (pos <= smid)
modify_sgt(lch,l,smid,pos,val);
else
modify_sgt(rch,smid+1,r,pos,val);
update(now);
}
 
int main() {
freopen("input.txt","r",stdin);
int n;
scanf("%d",&n);
for (int i=0;i<n;i++)
scanf("%d",a+i);
build_sgt(root,0,n-1);
int m;
scanf("%d",&m);
for (int i=0;i<m;i++) {
int cid;
scanf("%d",&cid);
if (cid == 1) {
int x,y;
scanf("%d%d",&x,&y);x--,y--;
int res = query_sgt(root,0,n-1,x,y);
printf("%d\n",res);
}else if (cid == 2) {
int p,v;
scanf("%d%d",&p,&v);p--;
modify_sgt(root,0,n-1,p,v);
}
}
}

动态数组
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 100000
#define MAXT MAXN*4
#define smid ((l+r)>>1)
int a[MAXN];
 
struct sgt_node {
int lch,rch;
int sum;
int pls;
}sgt[MAXT];
int topt = 0;
 
void update(int now) {
sgt[now].sum = sgt[sgt[now].lch].sum + sgt[sgt[now].rch].sum;
}
 
void do_plus(int &now,int l,int r,int v) {//给now整棵子树都加上v
if (!now)now = ++topt;
sgt[now].pls += v;
sgt[now].sum += (r-l+1)*v;
}
 
void push_down(int now,int l,int r) {
if (sgt[now].pls) {
do_plus(sgt[now].lch,l,smid,sgt[now].pls);
do_plus(sgt[now].rch,smid+1,r,sgt[now].pls);
sgt[now].pls = 0;
}
}
 
 
int query_sgt(int &now,int l,int r,int x,int y) {
if (!now)now=++topt;
if (l == x && r == y)
return sgt[now].sum;
push_down(now,l,r);
if (y <= smid)
return query_sgt(sgt[now].lch,l,smid,x,y);
else if (smid < x)
return query_sgt(sgt[now].rch,smid+1,r,x,y);
else
return query_sgt(sgt[now].lch,l,smid,x,smid) + query_sgt(sgt[now].rch,smid+1,r,smid+1,y);
}
 
void modify_sgt(int &now,int l,int r,int pos,int v) {
if (!now)now=++topt;
if (l ==  r) {
sgt[now].sum = v;
return ;
}
push_down(now,l,r);
if (pos <= smid)
modify_sgt(sgt[now].lch,l,smid,pos,v);
else
modify_sgt(sgt[now].rch,smid+1,r,pos,v);
update(now);
}
 
void plus_sgt(int &now,int l,int r,int x,int y,int v) {
if (!now)now=++topt;
if (l ==  x && r == y) {
do_plus(now,l,r,v);
return ;
}
push_down(now,l,r);
if (y <= smid)
plus_sgt(sgt[now].lch,l,smid,x,y,v);
else if (smid < x)
plus_sgt(sgt[now].rch,smid+1,r,x,y,v);
else
plus_sgt(sgt[now].lch,l,smid,x,smid,v),plus_sgt(sgt[now].rch,smid+1,r,smid+1,y,v);
update(now);
}
 
 
int main() {
freopen("input.txt","r",stdin);
int n;
scanf("%d",&n);
int root = 0;
int m;
scanf("%d",&m);
for (int i=0;i<m;i++) {
int cid;
scanf("%d",&cid);
if (cid == 1) {
int x,y;
scanf("%d%d",&x,&y);x--,y--;
int res = query_sgt(root,0,n-1,x,y);
printf("%d\n",res);
}else if (cid == 2) {
int p,v;
scanf("%d%d",&p,&v);p--;
modify_sgt(root,0,n-1,p,v);
}else if (cid == 3) {
int x,y,v;
scanf("%d%d%d",&x,&y,&v);x--,y--;
plus_sgt(root,0,n-1,x,y,v);
}
}
}

 

oi课件合集

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。