基础数据结构

· 2021-9-1   · 次阅读   · 字数统计: 1.7k字   · 阅读时长≈ 6分钟

  · 算法   ·

线性表

向量

链表

队列

栈

链表

树

以下是树的一些基本概念:

根(root) : 树的第一个结点

子节点(child) : 一个结点的子树的根结点

节点的度数(degree) : 树中一个结点的子结点个数称为该节点的度数

树的度数 : 树中最大的结点度数称为树的度数

分支结点 : 度不为 0 的结点

父节点和兄弟节点 : 对于结点的子结点来说，该节点为其子结点的父结点，拥有相同父结点的节点互称为兄弟结点

结点的层次 : 从根结点开始定义树的层次，定义根结点为 1 层

树的深度 : 树中节点的最大层次

无序树和有序树 : 树中任意结点之间没有顺序关系，称为 无序树，反之称为 有序树

从以上基本概念可以总结出树的一些性质:

  1. 度为 $n$ 的树第 $x$ 层最多有 $n^{x-1}$ 个结点
  2. 高度为 $h$ 的 $m$ 路树（度为 m）最多有 $m^{h} - 1 / m$
  3. 有 $n$ 个结点的 $m$ 路树的 最小高度 为 $log_{m}((m-1)n)$

二叉树

两种特殊的二叉树

满二叉树

在一棵二叉树中，如果所有分支结点都有两个子结点，且叶子结点均在二叉树的最下一层，则这颗二叉树称为 满二叉树

完全二叉树

在 满二叉树的基础上，最下一层允许在最右侧缺失连续的叶子结点

图

图(Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形，常用来描述某些事物之间的某种特定关系
用顶点来代表事物，连接两顶点的边则用于表示两个事物之间具有这种联系

图是一个二元组 $G = (V(G), E(G))$，其中 $V(G)$ 是非空集合，称为 点集(Vertex set), 对于 $V$ 中的每个元素, 我们称为 顶点(Vertex) 或 结点(Node),简称 点
$E(G)$ 为 $V(G)$ 各节点之间边的机会，称为 边集(Edge set)

常用 $G = (V, E)$ 表示图

几种基本的图

图有多种，这里介绍几种基本的, 有向图(Directed Graph), 无项图(Undirected Graph),混合图(Mixed Graph), 稀疏图(Sparse Graph), 稠密图(Dense Graph)

设 $G$ 为 无向图，则 $E$ 中的每个元素为一个无序二元组 $(u, v)$ ，称作 **无向边 (Undirected Edge)**，简称 边 (Edge)
其中 $u, v \in V$ 。设 $e = (u, v)$ ，则 $u$ 和 $v$ 称为 $e$ 的 端点 (Endpoint)

若 $G$ 为有向图，则 $E$ 中的每一个元素为一个有序二元组 $(u, v)$ ，有时也写作 $u \rightarrow v$，称作 有向边 (Directed Edge) 或 **弧 (Arc)**，在不引起混淆的情况下也可以称作 **边 (Edge)**。设 $e = u \rightarrow v$ ，则此时 $u$ 称为 $e$ 的 **起点 (Tail)**，$v$ 称为 $e$ 的 终点 (Head)(因为边通常用箭头表示，而箭头是从“尾”指向“头”的)，起点和终点也称为 $e$ 的 **端点 (Endpoint)**。并称 $u$ 是 $v$ 的直接前驱，$v$ 是 $u$ 的直接后继

若 $G$ 为混合图，则 $E$ 中既有向边，又有无向边

若一张图的边数远小于其点数的平方，那么它是一张 稀疏图 (Sparse graph)
若一张图的边数接近其点数的平方，那么它是一张 稠密图 (Dense graph)

这两个概念并没有严格的定义，一般用于讨论时间复杂度为  的算法与  的算法的效率差异（在稠密图上这两种算法效率相当，而在稀疏图上  的算法效率明显更高）

若 $G$ 的每条边 $e_{k} = (u_{k}, v_{k})$ 都被赋予一个数作为该边的 权，则称 G 为 **赋权图(带权图)**。如果这些权都是正实数，就称 $G$ 为 正权图

图 $G$ 的点数 $V(G)$ 也被称作图 $G$ 的 阶 (Order)

图的存储结构

在这一小节中，我们使用 $n$ 代指图中点的数量，用 $m$ 代指图中边的数量，用 $d^+ (u)$ 代指图中点 $u$ 的出度，即以 $u$ 为出发点的边数

邻接矩阵

邻接表

链式前向星

当图中边的数量达到 $10^5$ 甚至 $10^6$ 这个级别的时候，用 vector 构造的邻接表的性能也稍显不足，这时候我们就使用一种新的存图方式：前向星

前向星本质上是使用链表实现的邻接表

struct node    // 前向星
{
    int to;    // 这条边的终点
    int weight;     // 这条边的权重
    int next;  // 从该点出发下一条边，也就是前一条记录的边
}edge[N];

head[N];          // 记录每个结点的最后一条边，head[idx]为第idx个结点的最后一条边
int idx = 0;   // 当前边的编号

void init()    // 初始化函数
{
    for(int i = 0; i < N; ++i)
        h[i] = -1;  // 一开始所有结点的最后一条边初始化为 -1
}

void add(int from, int eto, int eweight)  // 加边
{
    edge[idx].to = eto;  // 将新边的终点加入 
    edge[idx].weight = eweight;  // 加入新边的权重
    edge[idx].next = head[from];  
    // 因为h[]数组是每个顶点的最后一条边，所以我们让next = head[from]，将这条边接到链上
    head[from] = idx++;  // 再将现在的边设置为这条边起点的最后一条边
}

但在实际运用中，我们一般会使用数组来存储这个结构

我们创建四个数组，将上面结构体中的三个成员都转为数组来存储

  • to[i]：第 $i$ 条边的终点
  • w[i]：第 $i$ 条边的权值
  • head[i]：第 $i$ 条边的起点最后一条添加的边
  • nxt[i]：第 $i$ 条边的起点的下一条边
int to[N], w[N], next[N], h[N]; // 注意，边的数量和顶点的数量可能不一定相同
int idx = 0;

void init() // 初始化，和上面相同，也是将h[]初始化为 -1
{
    memset(h, -1, sizeof(h));
}

void add(int from, int eto, int weight) // 初始化函数，和上面相同
{
    to[idx] = eto;
    w[idx] = weight;
    nxt[idx] = h[from];
    head[from] = idx++;
}

for(int i = head[u]; ~i; i = ne[i]) // 遍历 u 的出边，~i 表示 i != -1
{
    int v = to[i];
}

用链表的结构来形容，to[i] 和 w[i] 为链表第 $i$ 个节点的数据域，nxt[i] 为链表第 $i$ 个节点指向下一个的指针，head[i] 为以第 $i$ 个点为起点的的链表的头指针

复杂度
  • 查询是否存在 $u$ 到 $v$ 的边：$O(d^+(u))$
  • 遍历点 $u$ 的所有出边：$O(d^+(u))$
  • 遍历整张图：$O(n + m)$
  • 空间复杂度：$O(m)$

映射

集合