数据结构基础

数据结构基础

1 数据结构介绍

数据结构是计算机存储、组织数据的方式。数据结构往往同高效的检索算法和索引技术有关。其实只要是用来存储数据的结构,都可以叫做数据结构。这里介绍的数据结构都是一些比较常用的数据结构。

2 数组

2.1 介绍

所谓数组,是有序的元素序列。若将有限个类型相同的变量的集合命名,那么这个名称为数组名。组成数组的各个变量称为数组的分量,也称为数组的元素,有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中,为了处理方便,把具有相同类型的若干元素按无序的形式组织起来的一种形式。这些无序排列的同类数据元素的集合称为数组。

数组是用于储存多个相同类型数据的集合。基础的数组相信大家已经玩的很溜了,下面介绍动态数组vector

2.2 C++STL Vector

C++的vector库提供了动态数组vector类型。vector的存储是自动管理的,按需扩张收缩。所以它不像普通的数组一样需要先开好一定的空间,并且耗空间资源小,适合一些题目的数据存储。下面用代码来简洁描述一些比较常用的vector的功能。

// vector<type> v;创建元素类型为type的vector类型变量v

// 创建空的 vector
vector<int> a;

// 创建含有整数的 vector
vector<int> b={7,5,16,8};
 
// 添加一个整数到 vector 的末尾
a.push_back(25);
b.push_back(13);

// 删除 vector 末尾的整数
a.pop_back();
b.pop_back();

// 判断 vector 是否为空
cout<<a.empty();    //1
cout<<b.empty();    //0

// 输出 vector 的元素个数
cout<<a.size();    //0
cout<<b.size();    //4

// 返回指向容器第一个元素的迭代器
b.begin();

// 返回指向容器尾端的迭代器
b.end();
 
// 迭代并打印 vector 的值
for (int i=0;i<b.size();i++)    //原始方法
    cout<<b[i]<<' ';
for (vector<int>::iterator i=b.begin();i!=b.end();i++)    //迭代器写法
    cout<<*i<<' ';
for (auto i:b)    //C++11新增,不可改变元素的值
    cout<<i<<' ';
for (auto &i:b)    //C++11新增,可改变元素的值
    cout<<i<<' ';

// 规定 vector 的大小
b.resize(2);

// 清空 vector
b.clear();

除了上述描述的一些内容之外,vector类型的变量还可以直接进行比较:

  • 两个vector类型的变量a,b
  • ==:若vector内容相等则为true,否则为false
  • !=vector内容不相等则为true,否则为false
  • <:若a的内容按字典序小于b的内容则为true,否则为false
  • <=:若a的内容按字典序小于或等于b的内容则为true,否则为false
  • >:若a的内容按字典序大于b的内容则为true,否则为false
  • >=:若a的内容按字典序大于或等于b的内容则为true,否则为 false

关于操作的复杂度,请自行查阅cppreference

3 FILO-栈

3.1 介绍

假设你在做兼职洗一堆盘子,你有以下两种操作:

  • 取出最顶端的盘子,拿去洗
  • 其他人把需要清洗的脏盘子,放在最顶端

不难注意到,我们永远是在顶端进行操作。在顶端加入,在顶端
弹出。这就是一个特性:后进先出(LIFO)。生活中有大量遵循“后进先出”规则的结构,我们将之抽象为

后进先出(Last In First Out):越晚进来的,越早出去。对于所有的 a,b 都有:若 a 比 b 晚进入,那么 a 比 b 先出去。

3.2 实现

一个栈应该支持以下操作:

  • 查询栈顶
  • 弹出栈顶
  • 向顶部压入元素
  • 判断栈是否为空

如何实现这些操作?

创建数组a和变量tot,a用来直接存放栈里面的每一个元素。tot用来记录栈里面的元素个数。(tot初始化为0)

  • 查询栈顶:返回 a[tot]
  • 弹出栈顶:tot- -
  • 向顶部压入元素:a[++tot]=x
  • 判断栈是否为空:返回 !tot?1:0

代码实现也很简单:

int s[1000005],tot=0;

#define top (s[tot])
#define pop (tot--)
#define push(x) (s[++tot]=(x))
#define empty (!tot?1:0)

3.3 C++STL Stack

C++的stack库提供了stack类型。空间占用是动态的,比起自己手写的栈稍慢。下面用代码来简洁描述一些比较常用的stack的功能。

// stack<type> sta;创建元素类型为type的stack类型变量sta

// 创建空的 stack
stack<int> s;

// 向顶部压入元素
s.push(25);
s.push(13);

// 查询栈顶
cout<<s.top();

// 弹出栈顶
s.pop();

// 判断 stack 是否为空
cout<<s.empty();    //0

// 输出 stack 的元素个数
cout<<s.size();    //1

除了上述描述的一些内容之外,stack类型的变量还可以直接进行比较,方法与vector的相同。

关于操作的复杂度,请自行查阅cppreference

3.4 单调栈

问题:今有一群人排队膜拜wwj。每个人想知道站在自己前面的、比自己高的人中,离自己最近的是谁。

这个问题维护一个栈,保存“观测者现在能看到的人”。从左到右扫描队列。对每个元素x执行如下操作:

  1. 弹栈,直到栈尾比自己高。
  2. 将栈尾作为自己的答案。若栈空,则自己的答案为0。然后x入栈。

来模拟一组数据[2,6,7,4,3]验证正确性:

  • 2的答案一定是0,2入栈
  • 弹栈,栈空,6的答案是0,6入栈
  • 弹栈,栈空,7的答案是0,7入栈
  • 弹栈,栈尾为7,4的答案是7,4入栈
  • 弹栈,栈尾为4,3的答案是4

由于这种栈永远单调递减,故称为“单调栈”。整个的时间复杂度是$O(n)$,因为每个元素顶多入栈一次、出栈一次。请看代码。

  • 例3.4.1
struct node
{
    int h,i;
};
stack<node> s;
int op[2];

void monotonic_stack()
{
    for (int i=1;i<=n;i++)
    {
        cin>>h;
        int pd=0,pi;
        while (!s.empty())
        {
            if (s.top().h>a[i]) {pd=1; op[1]=s.top().i; break;}
            else s.pop();
        }
        s.push((node){h,i});
        cout<<op[pd];
    }
}

4 FIFO-队列

4.1 介绍

今有一群人排队膜拜wwj,人在队尾入队,而每次放人都是在队首。

超市收银台前的队列,食堂打饭的队列都是如此。在计算机中我们把这种结构称为“队列”。队列是符合先入先出的数据结构。

先入先出(First In First Out):越早进来的,越早出去。对于所有的 a,b 均有:若 a 比 b 早进入队列,则 a 比 b 早离开队列。

4.2 实现

一个队列应该支持以下操作:

  • 查询队首
  • 弹出队首
  • 向队尾压入元素
  • 判断队列是否为空

如何实现这些操作?

创建数组a和变量fntend,a用来直接存放栈里面的每一个元素。fnt用来记录头指针,end用来记录尾指针。(fnt初始化为1,end初始化为0)

  • 查询队首:返回 a[fnt]
  • 弹出队首:fnt++
  • 向队尾压入元素:a[++end]=x
  • 判断队列是否为空:返回 end>=fnt?1:0

可以发现,a[fnt]之前的所有空间都被浪费了!一但入队的元素数量太多,数组a的空间开的不够,就会爆空间。所以我们需要一个可以循环使用数组的方法。于是就有了循环队列。设数组开的大小为size,那么实现是这样的。

  • 查询队首:返回 a[fnt%size]
  • 弹出队首:fnt++
  • 向队尾压入元素:a[(++end)%size]=x
  • 判断队列是否为空:返回 end>=fnt?1:0

代码实现也很简单:

int q[1000005],fnt=1,end=0;    //size为1000000

#define top (q[fnt%1000000])
#define pop (fnt++)
#define push(x) (q[(++end)%1000000]=(x))
#define empty (end>=fnt?1:0)

4.3 C++STL Queue

C++的queue库提供了queue类型。空间占用是动态的;比起自己手写的栈稍慢。下面用代码来简洁描述一些比较常用的queue的功能。

// queue<type> que;创建元素类型为type的queue类型变量que

// 创建空的 queue
queue<int> q;

// 向队尾压入元素
q.push(25);
q.push(13);

// 查询队首
cout<<q.front();

// 弹出队首
q.pop();

// 判断 queue 是否为空
cout<<q.empty();    //0

// 输出 queue 的元素个数
cout<<q.size();    //1

除了上述描述的一些内容之外,queue类型的变量还可以直接进行比较,方法与vector的相同。

关于操作的复杂度,请自行查阅cppreference

5 链表

5.1 介绍

数组是顺序表。相邻元素在内存上的地址是连续的,这提供了:

  • 快速随机访问。可以在 O(1) 的时间内找到位于数组某个位置的元素
  • 无需额外信息,就可以查前驱后继。只需要下标加减任意数字即可

虽然有上述好处,但数组也有显著缺陷:

  • 插入/删除的代价极高。为 O(n)
  • 固定的空间占用

链表是一种崭新的数据结构。它不以下标来寻址,而是通过相邻元素之间的联系。通俗地讲,数组是一群人在内存上排了个队。链表不需要每个人都相邻,但是需要每个人都记住自己旁边的人。

这里讲述单向链表的构造,在单向链表中,每个人需要记住自己右边的人(加入数据从左往右存)。

5.2 数组&指针

指针构造的方法是用new/delete来动态分配内存,数组构造的方法是预留一个庞大的数组作为内存池,然后自己手动分配空间。存放对某个元素的索引时,指针构造的方法用指针指过去;数组构造的方法存储目标元素的内存池下标。

这里只介绍指针构造的方法,数组构造的方法是类似的,建议自行尝试来熟练使用。

5.3 实现

一个链表应该支持以下操作:

  • 查询(不是随机访问)
  • 插入
  • 删除

如何实现这些操作?

  • 基本框架

我们需要先写好一个基本框架。

  1. 建立一个struct结构体,包含两个元素,int类型的变量key和指向我们创建的struct类型的指针类型的变量lt
  2. 写一个结构体的构造函数
  3. 建立一个假结点root

请看代码实现。

struct node
{
    int key;
    node* rt;

    node(int _key,node* _rt)    //构造函数
    {
        key=_key;
        rt=_rt;
    }
};
node *root=new node(-1,NULL);    //root是一个假结点
  • 查询

接下来实现第一个功能:查询。如何查询?跟遍历数组的思路一致,从链表的root结点出发,一个结点一个结点遍历直到找到存有我们要查询的值的那个结点。代码实现如下。

bool find_key(int key)    //查找key
{
    for(node* p=root->rt;p;p=p->rt)
        if(p->key==key) return 1;
    return 0;
}
  • 插入

再接下来实现第二个功能:插入。如何插入?我们先要找到需要插入的位置,跟遍历数组的思路一致,从链表的root结点出发,一个结点一个结点遍历直到找到我们要插入的那个位置的前一个位置的结点,删除该结点保存的指针值,然后创建一个新结点,将该结点的指针值改为新结点的地址,再将新结点与后面的结点连起来。代码实现如下。

void insert_key(int key,int pos)    //插入key,需保证pos输入合法
{
    node* p=root;
    while (--pos)
        p=p->rt;
    node* target=new node(key,p->rt);
    p->rt=target;
}
  • 删除

最后实现第三个功能:删除。如何删除?我们先要找到需要删除的位置,跟遍历数组的思路一致,从链表的root结点出发,一个结点一个结点遍历直到找到我们要插入那个的位置的前一个位置的结点,用一个指针变量先存储该结点保存的指针值,然后修改该结点保存的指针值为下个结点的保存的指针值,最后删除指针变量保存的地址的内存空间。代码实现如下。

void delete_key(int pos)    //删除key,需保证pos输入合法
{
    node* p=root;
    while (--pos)
        p=p->rt;
    node* target=p->rt;
    p->rt=target->rt;
    delete target;    //释放节点
}
  • Debug

链表写起来十分复杂,可能会出错,这时写一个Debug函数就很有必要了,代码如下。

void debug()    //检查运行是否正确
{
    for(node* p=root->rt; p; p=p->rt)
        printf("Node[%p] key=%d rt=%p\n", p, p->key, p->rt);
}

5.4 总结

数组链表
查询$O(n)$/$O(logn)$$O(n)$
随机访问$O(1)$$O(n)$
插入/删除$O(n)$有时$O(1)$

6 集合&&C++STL Set

集合,等同于数学上的集合,这个数据结构里面的元素不会重复。

C++的set库提供了set类型。set通常以红黑树实现。下面用代码来简洁描述一些比较常用的set的功能。

// set<type> Set;创建元素类型为type的set类型变量Set

// 创建空的 set
set<int> s;

// 插入元素
s.insert(25);
s.insert(13);

// 判断 set 是否为空
cout<<s.empty();    //0

// 输出 set 的元素个数
cout<<s.size();    //2

// 返回匹配特定键的元素数量
cout<<s.count(13);    //1

// 清空 set
s.clear();

还有一些位于alogrithm库中的操作函数,请自行查阅cppreference获知用法。

  • includes:若一个集合是另一个的子集则返回 true
  • set_difference:计算两个集合的差集
  • set_intersection: 计算两个集合的交集
  • set_union:计算两个集合的并集

除了上述描述的一些内容之外,set类型的变量还可以直接进行比较,方法与vector的相同。

关于操作的复杂度,请自行查阅cppreference

7 字符串哈希

7.1 引子

  • 问题:给n个正整数,求出有多少种正整数。

这个问题第一时间可以想到用映射来做,也就是计数排序。只需要判断a[x]是否为0就可以了,a[x]==0时总计数不增加,反之增加。代码如下。

  • 例7.1.1
bool a[100000005];
    
int main()
{
    int n;
    cin>>n;

    int cnt=0;
    for (int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        a[x]=1;
    }
    
    for (int i=1;i<=100000005;i++)
        if (a[i]) cnt++;
    cout<<cnt<<'\n';   
    return 0;
}

但是可以发现,这样需要使用大量空间,当正整数的上线达到了1e9的级别就会MLE,并且也会TLE。所以需要另外的方法。可以使用取余的方式来解决数组空间的问题。代码如下。

  • 例7.1.2
bool a[10005];
    
int main()
{
    int n;
    cin>>n;

    int cnt=0;
    for (int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        a[x%(10000+1)]=1;
    }

    for (int i=0;i<=10000;i++)
        if (a[i]) cnt++;
    cout<<cnt<<'\n';
    return 0;
}

但这样还是有问题,有些正整数取余的值会相等,我们需要加多一个判断,在原先的数组上加多一维,使得可以存储取余的值相同的正整数。

  • 例7.1.3
set<int> a[10005];
    
int main()
{
    int n;
    cin>>n;

    int cnt=0;
    for (int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        if (!a[x%10000].count(x))
            {cnt++; a[x%10000].insert(x);}
        else continue;
    }

    cout<<cnt<<'\n';
    return 0;
}

这样,我们就解决了这个问题。

7.2 介绍

  • 问题:给n个字符串,求出有多少种字符串。

字符串哈希表就是能解这道题的一种数据结构。

字符串哈希的过程,其实可以看作对一个串的单向加密过程,并且需要保证所加的密不能高概率重复(每个门只能通过一把独一无二的钥匙打开)。

字符串哈希操作很简单,就是对于每个串,我们通过一个固定的转换方式,将相同的串使其的“key”一定相同,不同的串尽量不同。

你可能会疑惑,不能先比对字符串长度,然后比对ASCLL码之和吗?事实上肯定是不行的(比如ab和ba)。这种情况就叫做哈希冲突,并且在如此的单向加密哈希中,hash冲突的情况在所难免。

这里介绍的,即是最常见的一种哈希:进制哈希。进制哈希的核心便是给出一个固定进制base,将一个串的每一个元素看做一个进制位上的数字,所以这个串就可以看做一个base进制的数,那么这个数就是这个串的哈希值;则我们通过比对每个串的的哈希值,即可判断两个串是否相同。

  • 例7.2.1
set<string> a[100005];
    
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin>>n;

    int cnt=0;
    for (int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        int key=0;

        for (auto i:s)
            key=(key*256+(long long)i)%10000;
        
        if (!a[key].count(s))
            {cnt++; a[key].insert(s);}
        else continue;
    }

    cout<<cnt<<'\n';
    return 0;
}

哈希优化将在以后的文章中讲述。

8 并查集

8.1 介绍

  • 问题:今有n个人,初始时互相没有关系。要支持两个操作:
    • 查询:x,y是不是亲戚。
    • 合并:x与y是亲戚。

怎么解决这个问题?我们需要使用并查集并查集就是一种能描述关系的数据结构。

8.2 实现

如何实现两个操作?

创建一个数组fa。fa存储该下标的父亲。

  • 合并:如果x,y已经在同一家族,则忽略。否则,将y的祖先设为x的祖先的父亲。
  • 查询:查询x,y是不是亲戚时,找到x,y各自的祖先。如果相同,则返回true。如果不同,则返回false.

代码如下。

  • 例8.2.1
int fa[100005];    //存储祖先

int check_anc(int x)    //寻找祖先
{
    if (fa[x]) return check_anc(fa[x]);
    return x;
}
void union_anc(int x,int y)    //合并
{
    x=check_anc(x); y=check_anc(y);
    if (x!=y)
    fa[x]=y;
}
bool is_same_anc(int x,int y)    //是否有相同祖先
{
    if (check_anc(x)==check_anc(y)) return 1;
    else return 0;
}

容易发现,复杂度的瓶颈在于“找到某人的祖先”。每次找祖先都要付出$O(n)$的复杂度。有办法加速吗?有。我们自始至终只关心“x的祖先是谁”,而不关心“x的父亲是谁”。所以我们应当让fa存储该下标的祖先。这种方法类似于记忆化搜索,叫做路径压缩。代码如下。

  • 例8.2.2
int fa[100005];    //存储祖先

int check_anc(int x)    //寻找祖先
{
    if (fa[x]) return fa[x]=check_anc(fa[x]);    //路径压缩
    return x;
}
void union_anc(int x,int y)    //合并
{
    x=check_anc(x); y=check_anc(y);
    if (x!=y)
    fa[x]=y;
}
bool is_same_anc(int x,int y)    //是否有相同祖先
{
    if (check_anc(x)==check_anc(y)) return 1;
    else return 0;
}

9 二叉树

二叉树已在树论入门(一)-2 二叉树中讲述过,这里不再过多赘述。


感谢浏览😝!

此文章可能会在后续更新,欢迎纠错。