线性表

栈就是一个线性表,弹出和压入数据都从顶部进行。

栈的本质:先进后出 (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)

例题:P3367 【模板】并查集

#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_1k_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一般取质数:加大有效位数,稀释碰撞概率

最后修改日期:2020年2月7日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。