数据结构专题 讲座

程序=数据结构+算法数据

结构分为两类：物理结构【数组、链表】，逻辑结构【树的结点关系、并查集】
一般用数组不用指针

栈 Stack

//STL Standard Template Library
//Windows Stack: 8M
//Unix Stack: 8M

stack<int> s;
int x = 1;
s.push(1);
x = s.top(); s.pop();
int s.size();
bool s.empty();

队列 Queue

stack<int> s;
int x = 1;
s.push(1);
x = s.front(); s.pop();
int s.size();
bool s.empty();

实现一个栈：入栈、出栈、取最小元素的时间复杂度为O(1)
运用两个栈，第二个栈存小于栈首的元素的下标
//这是个栈，只会出最顶层的值（逃

vector

方便但不高效
开一片内存，不够用就开更大的一片，然后复制过去

priority_queue

实现：堆排序
堆：ki<=k2i && k1<=k2i+1
//二叉搜索树：k2i<=ki<=k2i+1
入队、出队：log(2n)

树 Tree

一种重要的非线性数据结构
数据按分支关系组织起来
没有环

二叉树是最简单的树结构
二叉树链表
二叉搜索树

红黑树是一种自平衡的二叉查找树

更多特性：

• 结点：红色、黑色
• 根结点：黑色
• 红色子结点是黑色，黑色非空子结点是红色
• 空结点是黑色，在黑色的子结点

字典树 Trie （AC自动机）

插入一个字符串

• 从根结点出发，判断字母对应边是否存在
• 存在：访问；不存在：新建
• 对终点做特殊标记

查询字符串

struct Trie{
    int next[MAX];
    int v; //结束标志
}

void createTrie(char *str)
{
    int len = strlen(str);

    Trie *p = root, *q;
    for(int i=0; i<len; ++i)
    {
        int id = str[i]-'0';
        if(p->next[id] == NULL)
        {
            q = (Trie *)malloc(sizeof(Trie));
            q->v = 1;//初始v==1
            for(int j=0; j<MAX; ++j)
                q->next[j] = NULL;
            p->next[id] = q;
            p = p->next[id];
        }
        else
        {
            p->next[id]->v++;
            p = p->next[id];
        }
    }
    p->v = -1; //若为结尾，则将v改成-1表示
}

int findTrie(char *str)
{
    int len = strlen(str);
    Trie *p = root;
    for(int i=0; i<len; ++i)
    {
    int id = str[i]-'0';
    p = p->next[id];
    if(p == NULL)   //若为空集，表示不存以此为前缀的串
        return 0;
    if(p->v == -1)   //字符集中已有串是此串的前缀
        return -1;
    }
    return 1;   //此串是字符集中某串的前缀
}

并查集

小巧高效有用
压缩路径以后，没有必要启发式合并
可以用递归压缩路径(logn也没有什么问题，gcd递归也是logn)
Kruskal 无向图最小生成树

线段树 Interval Tree

三个小时肯定讲不完

n次查询某一区间的和（最大值）——n*O(logn)

• 区间查询（极值、求和、etc）
• 区间更新（同一加一个值）
• 分为三类（更新点，查询区间；更新区间，查询点；更新区间，查询区间
• 线段树空间应开为原数组长度的四倍

但是线段树可没这么简单。。。“懒操作”在更更新区间的有关问题上⾄至关重要。（然而我不会啊wsl）

经典问题：
a[1]~a[n]
操作：修改一个值；求区间最大值；求区间和

线段树的结点是区间结构图？

树状数组

树状数组已在其他文章进行拓展讲解。