数据结构讲稿

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

[pdf-embedder url=”https://mhy12345.xyz/wp-content/uploads/2018/07/数据结构-讲义.pdf” title=”数据结构 讲义”]

[pdf-embedder url=”https://mhy12345.xyz/wp-content/uploads/2018/07/数据结构.pdf” download=’on’]

#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;
}
#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() {
}

#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();
}
#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;
		}
	}
}
#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;
}
#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]的最大值
#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));
		}
	}
}
#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;
	}
}
#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() {
}
#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);
		}
	}
}
#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来减少垃圾评论。了解我们如何处理您的评论数据