这个数据结构讲稿是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); } } }