数据结构

各种数据结构应用场景

  • 栈：逆序输出；语法检查，符号成对判断；方法调用
  • 二叉树：表达式树
  • B+/B-树：文件系统；数据库索引
  • 哈夫曼树：数据压缩算法
  • 哈希表：提高查找性能
  • 红黑树：大致平衡的二叉查找树，相对AVL树，插入删除结点较快，查找性能没有提升

    数组

数组的优点:

  • 存取速度快

数组的缺点:

  • 事先必须知道数组的长度
  • 插入删除元素很慢
  • 空间通常是有限制的
  • 需要大块连续的内存块
  • 插入删除元素的效率很低

链表

优点：

  • 空间没有限制
  • 插入删除元素很快

缺点：存取速度很慢

分类

  • 单向链表 一个节点指向下一个节点。
  • 双向链表 一个节点有两个指针域。
  • 循环链表 能通过任何一个节点找到其他所有的节点，将两种(双向/单向)链表的最后一个结点指向第一个结点从而实现循环

哈希表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

栈

我们把类似于弹夹那种先进后出的数据结构称为栈，栈是限定仅在表尾进行插入和删除操作的线性表，我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈，栈又称后进后出的线性表，简称LIFO结构。

栈的特殊之处在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这也就使得：栈底是固定的，最先进栈的只能在栈底。

栈的插入操作，叫做进栈；栈的删除操作叫做出栈。

队列

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表，队列是一种先进先出的线性表，简称FIFO，允许插入的一端称为队尾（Rear），允许删除的一端称为队头(Front)。向队中插入元素称为进队，新元素进队后成为新的队尾元素；向队中删除元素称为出队，元素出队后，其后继元素就成为新的队头元素。

树

树是一种数据结构，它看上去像一棵 “圣诞树”，它的根在上，叶朝下。

树有多个节点(node)，用以储存元素。某些节点之间存在一定的关系，用连线表示，连线称为边(edge)。边的上端节点称为父节点，下端称为子节点。树像是一个不断分叉的树根。

二叉树

最多有两棵子树的树被称为二叉树

满二叉树: 二叉树中所有非叶子结点的度都是2，且叶子结点都在同一层次上

完全二叉树: 如果一个二叉树与满二叉树前m个节点的结构相同，这样的二叉树被称为完全二叉树

二叉查找树

指一棵空树或者具有下列性质的二叉树。

  • 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  • 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  • 任意节点的左、右子树也分别为二叉查找树；
  • 没有键值相等的节点。

AVL树

平衡二叉搜索树，它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1。

  • 左左单旋转
    在这里插入图片描述

  • 左右双旋转
    在这里插入图片描述

  • 四种旋转情况

    在这里插入图片描述

B树

也称B-树，属于多叉树又名平衡多路查找树。规则：

  • 1<子节点数<=m，m代表一个树节点最多有多少个查找路径
  • 每个节点最多有m-1个关键字，非根节点至少有m/2个关键字，根节点最少可以只有1个关键字
  • 每个节点都有指针指向子节点，指针个数=关键字个数+1，叶子节点指针指向null

B-树的特性：

  1. 关键字集合分布在整颗树中；
  2. 任何一个关键字只出现在一个节点中；
  3. 搜索有可能在非叶子结点结束；

B+树是B-树的变体，也是一种多路搜索树。B+的搜索与B-树基本相同，区别是B+树只有达到叶子结点才命中，B-树可以在非叶子结点命中。B+树更适合文件索引系统。

B-和B+树的区别

  • B+树的非叶子结点不包含data，叶子结点使用链表连接，便于区间查找和遍历。B-树需要遍历整棵树，范围查询性能没有B+树好。
  • B-树的非树节点存放数据和索引，搜索可能在非叶子结点结束，访问更快。

红黑树

红黑树是对AVL树的优化，只要求部分平衡，用非严格的平衡来换取增删节点时候旋转次数的降低，提高了插入和删除的性能。查找性能并没有提高，查找的时间复杂度是O(logn)。红黑树通过左旋、右旋和变色维持平衡。

对于插入节点，AVL和红黑树都是最多两次旋转来实现平衡。对于删除节点，avl需要维护从被删除节点到根节点root这条路径上所有节点的平衡，旋转的量级为O(logN)，而红黑树最多只需旋转3次。

特性:
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点和叶子节点是黑色，叶子节点为空。
(4)红色节点的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点，保证没有一条路径会比其他路径长一倍。

优点：相比avl树，红黑树插入删除的效率更高。红黑树维持红黑性质所做的红黑变换和旋转的开销，相较于avl树维持平衡的开销要小得多。

应用：主要用来存储有序的数据，Java中的TreeSet和TreeMap都是通过红黑树实现的。

图

图由顶点集(vertex set)和边集(edge set)所组成。

图的存储结构有邻接矩阵、邻接表和边集数组三种。

1、邻接矩阵

2、邻接表

下面给出建立图的邻接表中所使用的边结点类的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
public class EdgeNode {     //定义邻接表中的边结点类型
    int adjvex;             //邻接点域
    int weight;             //边的权值域，假定为整型，对于无权图，边的权值为1
    EdgeNode next;          //指向下一个边结点的链接域
    public EdgeNode(int adj, EdgeNode nt) 
    {     //对无权图中的边结点进行初始化
        adjvex=adj; next=nt; weight=1;
    }
    public EdgeNode(int adj, int wgt, EdgeNode nt) 
    {     //对有权图中的边结点进行初始化
        adjvex=adj; next=nt; weight=wgt;
    }
}

图的接口类定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public interface Graph
     {
         boolean createGraph(EdgeElement[]d);  //根据边集数组参数d建立一个图
         int graphType();                   //返回图的类型
         int vertices();                    //返回图中的顶点数
         int edges();                       //返回图中的边数
         boolean find(int i, int j);        //从图中查找一条边(i,j)是否存在
         boolean putEdge(EdgeElement theEdge); //向图中插入一条边theEdge
         boolean removeEdge(int i, int j);     //从图中删除一条边(i,j)
         int degree(int i);                 //返回顶点i的度
         int inDegree(int i);               //返回顶点i的入度
         int outDegree(int i);              //返回顶点i的出度
         void output();                     //以图的顶点集和边集的形式输出一个图
         void depthFirstSearch(int v);      //从顶点v开始深度优先搜索遍历图
         void breadthFirstSearch(int v);    //从顶点v开始广度优先搜索遍历图
         void clearGraph();                 //清除图中的所有内容
     }

深度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
private void dfs(int i, boolean[] visited) {
    System.out.printl(i + " ");
    visited[i] = true;
    EdgeNode p = a[i];
    while(p != null) {
        int j = p.adjvex;
        if(!visited[j]) {
            dfs(j, visited);
        }
        p = p.next;
    }
}

广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private void bfs(int i, boolean[] visited) {
    LinkedList<Integer> queue = new LinkedList<>();
    System.out.print(i + " ");
    visited[i] = true;
    queue.offer(i);
    while(!queue.isEmpty()) {
        int k = queue.poll();
        EdgeNode p = a[k];

        while(p != null) {
            int j = p.adjvex;
            if(!visited[j]) {
                System.out.print(j + " ");
                visited[j] = true;
                queue.offer(j);
            }
            p = p.next;
        }
    }
}
阅读量
赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

作为一个IT工作者，没个博客挺过分的<br><br>不过亡羊补牢为时不晚嘛<br><br>记录一些生活学习，共同进步