- 初级数据结构
-
1、链表、双向链表（
估计考试前是不会用了） -
定义链表：
struct LinkList {
int value;
LinkList *next;
};
-
根据输入建立单链表
将输入的节点插入到链表头部。
LinkList *BuildList() {
LinkList *head = NULL;
int data;
int i = 0;
while (scanf("%d", &data) != EOF) {
//scanf("%d", &data);++i;
LinkList *new_node = (LinkList *)malloc(sizeof(LinkList));
if (NULL == new_node) {
fprintf(stderr, "malloc failed");
return head;
}
new_node->value = data;
if (head == NULL) {
new_node->next = NULL;
head = new_node;
}
else {
new_node->next = head;
head = new_node;
}
}
return head;
}
-
插入
//在链表头部插入节点
LinkList *InsertToHead(int value, LinkList *head) {
LinkList *new_node = (LinkList *)malloc(sizeof(LinkList));
if (new_node == NULL) {
fprintf(stderr, "malloc failed");
return head;
}
new_node->value = value;
new_node->next = NULL;
if (head == NULL) {
head = new_node;
}
else {
new_node->next = head;
head = new_node;
}
return head;
}
//链表尾部插入节点
LinkList *InsertToTail(int value, LinkList *head) {
LinkList *new_node = (LinkList *)malloc(sizeof(LinkList));
if (new_node == NULL) {
fprintf(stderr, "malloc failed");
return head;
}
new_node->value = value;
new_node->next = NULL;
if (head == NULL)
head = new_node;
else {
LinkList *pnode = head;
while (pnode->next != NULL)
pnode = pnode->next;
pnode->next = new_node;
}
return head;
}
-
删除
//删除某节点
LinkList *DeletebyValue(int value, LinkList* head) {
if (head == NULL)
return head;
LinkList *pToDelete = NULL;
if (head->value == value) {
pToDelete = head;
head = head->next;
}
else {
LinkList *p = head;
while (p->next != NULL && p->next->value != value)
p = p->next;
if (p->next != NULL) {
pToDelete = p->next;
p->next = pToDelete->next;
}
}
if (pToDelete != NULL) {
free(pToDelete);
pToDelete = NULL;
}
return head;
}
-
求单链表中结点的个数
注意检查链表是否为空。时间复杂度为O（n）。该操作不用特意检查链表是否为空，如下代码，链表为空会返回0。
unsigned int Length(LinkList *head) {
unsigned int length = 0;
LinkList *p = head;
while (p) {
++length;
p = p->next;
}
return length;
}
-
打印链表元素
//打印单链表 顺序
void PrintList(LinkList *head) {
LinkList *p = head;
while (p) {
printf("%d ", p->value);
p = p->next;
}
printf("\n");
}
//逆序打印单链表：非递归
void RPrintList(LinkList* head) {
if (NULL == head)
return;
stack<int> list_stack;
while (head) {
list_stack.push(head->value);
head = head->next;
}
while (!list_stack.empty()) {
printf("%d ", list_stack.top());
list_stack.pop();
}
printf("\n");
}
//逆序打印单链表：递归
void RPrintListRecursively(LinkList* head) {
if (NULL == head)
return;
else {
RPrintListRecursively(head->next);
printf("%d ", head->value);
}
}
双向链表是什么
-
2、队列、单调队列、栈、单调栈
-
队列：
遵循先进先出的原则（FIFO）的数据结构。
-
STL：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int main() {
queue <int> qu;
int a;
scanf("%d",&a);
qu.push(a); //插入元素
if(!qu.empty()) { //判断队列是否为空
cout<<qu.size()<<endl; //输出队列中元素个数
cout<<qu.front(); //输出队首元素
qu.pop(); //弹出队首元素
}
return 0;
}
-
手写队列：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct queue {
int Q[500005],head,tail;
queue() {
head=0,tail=0;
}
void push(int a) {
Q[++tail]=a;
return ;
}
void pop() {
head++;
return ;
}
bool empty() {
return head>=tail;
}
int front() {
return Q[head+1];
}
int size() {
if(head<=tail) return tail-head;
}
};
int main() {
queue qu;
int a;
scanf("%d",&a);
qu.push(a); //插入元素
if(!qu.empty()) { //判断队列是否为空
cout<<qu.size()<<endl; //输出队列中元素个数
cout<<qu.front(); //输出队首元素
qu.pop(); //弹出队首元素
}
return 0;
}
-
单调队列：
给定一个队列，维护三个操作。
1：将一个数x压入队列中。
2：求队列中数的最大值。
3：弹出队列尾的数。
这就要用到单调队列。
在每次进入队伍时，判断当前元素与队尾元素的大小关系，若小于队尾元素，则队尾不可能成为最小值，直接删除即可。
每次查询的答案一定在队首位置。
由于每个元素至多进队列和出队列一次，时间复杂度为O(n)。
下面以Sliding Window为例
STL（用deque（双端队列））
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
using namespace std;
typedef pair<int,int> P;
#define maxn 1000000 + 10
deque<P> Q1;
deque<P> Q2;
int n,k;
int Min[maxn], Max[maxn];
int main() {
while(~scanf("%d%d", &n, &k)) {
while(!Q1.empty()) Q1.pop_back();
while(!Q2.empty()) Q2.pop_back();
int x;
for(int i=1; i<=n; i++) {
scanf("%d", &x);
while(!Q1.empty() && Q1.back().first >= x) Q1.pop_back();
Q1.push_back(P(x,i));
if(i >= k) {
while(!Q1.empty() && Q1.front().second <= i-k) Q1.pop_front();
Min[i] = Q1.front().first;
}
while(!Q2.empty() && Q2.back().first <= x) Q2.pop_back();
Q2.push_back(P(x,i));
if(i >= k) {
while(!Q2.empty() && Q2.front().second <= i-k) Q2.pop_front();
Max[i] = Q2.front().first;
}
}
for(int i=k; i<=n; i++)
i == n ? printf("%d\n", Min[i]) : printf("%d ", Min[i]);
for(int i=k; i<=n; i++)
i == n ? printf("%d\n", Max[i]) : printf("%d ", Max[i]);
}
return 0;
}
手写
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAXN 1000005
using namespace std;
struct s {
int v,p;
void f(int a,int b) {
v=a,p=b;
}
}Q1[MAXN],Q2[MAXN];
int h1,t1,h2,t2,Min[MAXN],Max[MAXN];
int n,k;
int main() {
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) {
int x;
scanf("%d",&x);
while(h1<t1 && Q1[t1].v>=x) t1--;
Q1[++t1].f(x,i);
if(i>=k) {
while(h1<t1 && Q1[h1+1].p<=i-k) h1++;
Min[i]=Q1[h1+1].v;
}
while(h2<t2 && Q2[t2].v<=x) t2--;
Q2[++t2].f(x,i);
if(i>=k) {
while(h2<t2 && Q2[h2+1].p<=i-k) h2++;
Max[i]=Q2[h2+1].v;
}
}
for(int i=k;i<=n;i++) printf("%d ",Min[i]);
printf("\n");
for(int i=k;i<=n;i++) printf("%d ",Max[i]);
return 0;
}
-
栈：
遵循先进后出的原则（FILO）的数据结构。
-
STL:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
int main() {
stack <int> st;
int a;
scanf("%d",&a);
st.push(a); //插入元素
if(!st.empty()) { //判断栈是否为空
cout<<st.size()<<endl; //输出栈中元素个数
cout<<st.top(); //输出栈顶元素
st.pop(); //弹出栈顶元素
}
return 0;
}
-
手写：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct stack {
int a[23333],pos;
stack() {
pos=0;
}
void push(int x) {
a[++pos]=x;
}
void pop() {
pos--;
}
bool empty() {
return !pos;
}
int top() {
return a[pos];
}
int size() {
return pos;
}
};
int main() {
stack st;
int a;
scanf("%d",&a);
st.push(a); //插入元素
if(!st.empty()) { //判断栈是否为空
cout<<st.size()<<endl; //输出栈中元素个数
cout<<st.top(); //输出栈顶元素
st.pop(); //弹出栈顶元素
}
return 0;
}
-
单调栈 -
3、堆
STL多好用
#include <queue>
priority_queue <int> big_heap; //大根堆
priority_queue <int,vector<int>,greater<int> > small_heap; //小根堆
heap.top();
heap.push();
heap.pop();
heap.empty();
heap.size();
手写：
struct priority_queue {
int a[23333],size;
priority_queue() {
size=0;
}
void push(int x) {
a[++size]=x;
int son=size,dad;
while(son!=1) {
dad=son>>1;
if(a[dad]>a[son]) swap(a[dad],a[son]);
son=dad;
}
return ;
}
int top() {
return a[1];
}
void pop() {
a[1]=a[size--];
int dad=1,son=2;
while(son<=size) {
son=dad<<1;
if(son<size && a[son]>a[son+1]) son++;
if(a[dad]>a[son]) swap(a[son],a[dad]);
dad=son;
}
return ;
}
bool empty() {
return !size;
}
};
- 基础数据结构
-
1、线段树
二分的思想把区间内的点分成若干个线段然后处理问题，查询和修改都是O（nlogn）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define maxn 1000005
#define ll long long
using namespace std;
inline ll read() {
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll a[maxn],sum[maxn<<2],col[maxn<<2];
void updata(ll rt) {
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void color(ll l,ll r,ll rt,ll c) {
col[rt]+=c;
sum[rt]+=c*(r-l+1);
}
void push_col(ll l,ll r,ll rt) {
if(col[rt]) {
ll m=(l+r)>>1;
color(lson,col[rt]);
color(rson,col[rt]);
col[rt]=0;
}
}
void build(ll l,ll r,ll rt) {
if(l==r) {
sum[rt] = a[l];
return ;
}
ll m=(l+r)>>1;
build(lson);
build(rson);
updata(rt);
}
ll query(ll l,ll r,ll rt,ll L,ll R) {
if(L<=l && R>=r)return sum[rt];
push_col(l,r,rt);
ll ret=0;
ll m=(l+r)>>1;
if(L<=m) ret+=query(lson,L,R);
if(m<R) ret+=query(rson,L,R);
return ret;
}
void modify(ll l,ll r,ll rt,ll L,ll R,ll v) {
if(L<=l && R>=r) {
color(l,r,rt,v);
return ;
}
push_col(l,r,rt);
ll m=(l+r)>>1;
if(L<=m) modify(lson,L,R,v);
if(m<R) modify(rson,L,R,v);
updata(rt);
}
ll n,m;
int main() {
n=read(),m=read();
for(ll i=1;i<=n;i++)a[i]=read();
build(1,n,1);
while(m--) {
ll id=read();
if(id==2) {
ll x=read(),y=read();
printf("%lld\n",query(1,n,1,x,y));
}
else {
ll x=read(),y=read(),z=read();
modify(1,n,1,x,y,z);
}
}
return 0;
}
-
2、树状数组
前缀和和差分的思想，利用二进制，反正就是跳来跳去。反正背过就行。
就当存一下模板。
/*
1.将某一个数加上x
2.求出某区间每一个数的和
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAXN 500005
using namespace std;
int a[MAXN],c[MAXN],n,m;
int lowbit(int x) {
return x&(-x);
}
void modify(int p,int x) {
while(p<=n) {
c[p]+=x;
p+=lowbit(p);
}
return ;
}
int sum(int p) {
int sum=0;
while(p) {
sum+=c[p];
p-=lowbit(p);
}
return sum;
}
int query(int l,int r) {
return sum(r)-sum(l-1);
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),modify(i,a[i]);
for(int i=1;i<=m;i++) {
int id,x,y;
scanf("%d%d%d",&id,&x,&y);
if(id==1) modify(x,y);
else printf("%d\n",query(x,y));
}
return 0;
}
/*
1.将某区间每一个数数加上x
2.求出某一个数的和
*/
#include <iostream>
#include <cstdio>
#define maxn 500000+5
using namespace std;
int n,m,pre,c[maxn];
int lowbit(int x) {
return x&(-x);
}
void modify(int pos,int x) {
while(pos<=n) {
c[pos]+=x;
pos+=lowbit(pos);
}
return ;
}
int query(int pos) {
int ans=0;
while(pos>0) {
ans+=c[pos];
pos-=lowbit(pos);
}
return ans;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) {
int x;
scanf("%d",&x);
modify(i,x-pre);
pre=x;
}
while(m--) {
int id;
scanf("%d",&id);
if(id==1) {
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
modify(l,k);
modify(r+1,-k);
} else {
int pos;
scanf("%d",&pos);
printf("%d\n",query(pos));
}
}
return 0;
}
-
ST表
给定一个数列a，O(nlogn)预处理，O(1)查询数列在区间[l,r]的最值。
这里介绍求最大值。
int st[N][K],a[N],log_2[N];
inline void ini_st(){
log_2[1]=0;
for(int i=2;i<=n;++i){
log_2[i]=log_2[i-1];
if((1<<log_2[i]+1)==i)
++log_2[i];
}
for(int i=n;i;--i){
st[i][0]=a[i];
for(int j=1;(i+(1<<j)-1)<=n;++j)
st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
}
}
inline int ask(int l,int r){
int k=log_2[r-l+1];
return max(st[l][k],st[r-(1<<k)+1][k]);
}
-
并查集
貌似我在图伦里写过了。
-
带权并查集
-
hash表
这个主要用于字符串hash，整理字符串的时候在写吧。
-
分块
把问题分成许多（一般是根号n）块，在块中完成。时间复杂度为O（m根号n）
int belong[maxn],block,num,l[1000],r[1000];
int n,m;
void build() {
block=sqrt(n);
num=block;
if(n%num)num++;
for(int i=0;i<n;i++) {
belong[i]=(i-1)/block;
}
for(int i=1;i<=num;i++) {
l[i]=(i-1)*block;
r[i]=i*block-1;
}
r[num]=n;
}
