线性表
栈
栈就是一个线性表，弹出和压入数据都从顶部进行。
栈的本质：先进后出 （LIFO表）。手写栈的实现：开一个数组并定义一个指针指向顶端元素。
#include <cstdio>
int s[10005];
int tot=0;
void push(int x)
{
s[++tot]=x;//每次操作将指针往上移再插入
return;
}
void pop()
{
--tot;//出栈的时候直接将tot下移
}
int top()//查询栈顶操作
{
return s[tot];
}
int size()
{
return tot;
}
应用：括号匹配问题，火车进/出站问题等。
例题：后缀表达式
分析：后缀表达式明显满足栈的要求，只需要开一个栈，读入数字并存储，遇到符号就进行操作即可。
实现：
#include <cstdio>
#include <stack>
using namespace std;
stack<int> a;
char s[1200];
int main()
{
scanf("%s",s);
int p=0;
int x,y;
for(int i=0;s[i]!='@';i++)
{
switch(s[i])
{
case '.':
a.push(p);
p=0;
break;
case '*':
x=a.top();
a.pop();
y=a.top();
a.pop();
a.push(x*y);
break;
case '+':
x=a.top();
a.pop();
y=a.top();
a.pop();
a.push(x+y);
break;
case '-':
x=a.top();
a.pop();
y=a.top();
a.pop();
a.push(y-x);
break;
case '/':
x=a.top();
a.pop();
y=a.top();
a.pop();
a.push(y/x);
break;
default:
p*=10;
p+=(s[i]-'0');
break;
}
}
printf("%d",a.top());
return 0;
}
队列
队列可以模拟收银，办事等，越早进入越早离开。
每次弹出操作在队首进行，压入从队尾进行。
本质：先进先出 （FIFO表）
手写队列的实现：使用一个大数组，定义两个指针，一个指向队首，一个指向队尾。
int s[100005],head,tail;
void push(int x)
{
s[++tail]=x;
}
void pop()
{
head++;
}
int front()
{
return s[head];
}
缺点：浪费空间，可能溢出。
解决方案：使用STL或者循环队列
#include<queue>
queue<int> q;
q.front();//（返回第一个元素）
q.push(x);//元素入队
q.empty();//返回一个bool值代表队列是否为空
q.size();//返回队列中元素数量
例题：约瑟夫问题
分析：1…n这些小朋友站在队列里。接下来，队首的人队，然后走到队尾，这样一直循环，直到第k个小朋友。他淘汰出局，不再入队。队内现在只剩下了n-1名小朋友，继续重复刚刚的操作：前k-1个人出队之后走到队尾，接下来那位小朋友直接淘汰。
代码实现：
#include <cstdio>
#include <queue>
using namespace std;
int main()
{
int n,m;
scanf("%d%d",&n,&m);
queue<int> q;
for(int i=1;i<=n;i++)
q.push(i);
for(int i=1;!q.empty();i++)
{
int x=q.front();
q.pop();
if(i%m)
{
q.push(x);
}
else
{
printf("%d ",x);
}
}
return 0;
}
双端队列：deque
#include <deque>
using namespace std;
deque<int> d;
d.push_front();
d.push_back();
d.pop_back();
d.pop_front();
d.front();
d.back();
d[i];//复杂度高，返回第i个元素
链表
链表是一种链式结构，相邻的元素相连接。
- 单向链表
- 双向链表
- 循环链表
单链表的实现：
- 删除任意元素
- 任意查询元素
- 任意插入元素
- 连接两个链表
可以使用指针，也可以使用数组模拟。
并查集&HASH表
并查集
例题：P1551 亲戚
分析：染色法
最开始，每个人都有自己颜色。如果A，B都是亲戚，那么将所有颜色为B的人染成A。查询时只需判断A和B是否同色。
但可以不染色，进行标记数组bin。询问时可以通过查询bin数组，来知道x最后应为什么颜色。
#include <cstdio>
struct unionFind//使用一个结构体代表并查集
{
int bin[100005];
unionFind()//构造初始化时
{
for(int i=1;i<=100003;i++) bin[i]=i;//初始化，每个人一开始是自己的颜色
}
int anc(int x)//查询最终颜色
{
if(bin[x]==x)
return x;
else return anc(bin[x]);//递归查找最终的颜色
}
void uni(int x,int y)//连接操作
{
bin[anc(x)]=anc(y);
}
void ask(int x,int y)//查询操作
{
printf("%s\n",anc(x)==anc(y)?"Yes":"No");//如果x最终颜色与y相同，输出。
}
}u;
int main(void)
{
int n,m,p;
scanf("%d %d %d",&n,&m,&p);
while(m--)
{
int i,j;
scanf("%d %d",&i,&j);
u.uni(i,j);
}
while(p--)
{
int x,y;
scanf("%d %d",&x,&y);
u.ask(x,y);
}
return 0;
}
把一个集合的bin最终指向的元素，叫做该集合的代表。上述操作中实现了合并集合和查询两元素是否在同一集合的操作。
最坏时间复杂度：链式。
解决方法：路径压缩，每次查询回来时直接将该路的元素的bin值直接指向代表元素。时间复杂度约等于O(n)。
#include <cstdio>
using namespace std;
struct Uf
{
int bin[10005];
Uf()
{
for(int i=1;i<=10002;i++)
bin[i]=i;
}
int anc(int x)
{
if(bin[x]==x) return x;
return bin[x]=anc(bin[x]);//改变原bin值，进行路径压缩
}
void uni(int x,int y)
{
bin[anc(x)]=anc(y);
}
void ask(int x,int y)
{
printf("%c\n",anc(x)==anc(y)?'Y':'N');
}
}u;
int main()
{
int n,m;
scanf("%d%d",&n,&m);
while(m--)
{
int z,x,y;
scanf("%d%d%d",&z,&x,&y);
if(z==1) u.uni(x,y);
if(z==2) u.ask(x,y);
}
return 0;
}
总结：并查集的实现：结构体，bin数组，查询祖先操作的同时进行路径压缩。
HASH表
问题：给出你朋友的身份证号，再给出几个号判断是否为好友。
分析：不能直接使用bool数组，会严重MLE。
hash表的本质：映射，定义一函数f(x)，一个关键字k放在一个存储地址f(k)上，可以加快查找的速度，但是如果对于两个不同的关键字k_1和k_2，HASH函数返回了相同的值，此时就发生了HASH碰撞，实现时一定要减小碰撞。
常用的映射方法有取余运算，有定理：期望每\sqrt{p}个朋友有两个人的id%p会相等，为了减少碰撞，p要取尽量大。
减少碰撞的方法：双取余，拉链法
struct zip
{
vector<int> w[ha+5];//ha代表要取模的数
void ins(int x)
{
w[x%ha].push_back(x);//对应的地址插入该数据，避免直接使用bool值带来的碰撞
}
void ask(int x)//查询操作
{
for(auto i=w[x%ha].begin();i!=w[x%ha].end();i++)//遍历对应地址的vector，判断
if(*i==x) {printf("Yes\n");return;}
printf("No\n");
return;
}
};
双模数：两个模数同时认为此人为朋友时，才是朋友（不能避免碰撞）
最常用：STL，复杂度O(n\log n)
//前面加#include <set>
unordered_set <int> S;
S.insert(x);
//判定：
S.count(x);//判断之是否为0
取模的数p一般取质数：加大有效位数，稀释碰撞概率
留言