【算法&数据结构体系篇class32】:IndexTree & AC自动机

这篇具有很好参考价值的文章主要介绍了【算法&数据结构体系篇class32】:IndexTree & AC自动机。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、IndexTree 

特点:

1)支持区间查询

2)没有线段树那么强,但是非常容易改成一维、二维、三维的结构

3)只支持单点更新

 

二、IndexTree 一维数组代码演示

package class32;

/**IndexTree
 * 特点:
 * 1)支持区间查询
 * 2)没有线段树那么强,但是非常容易改成一维、二维、三维的结构
 * 3)只支持单点更新
 *
 * 时间复杂度 O(logN)
 */
public class IndexTree {
    /**
     * tree数组的赋值演示:
     * 原数组arr[ 2,3,4,6,7,5,9,3,7,9 ] 这里的索引位置对应 1,2,3,4,5,6,7,8,9,10  10个数
     *
     * tree对应索引情况:
     * 1位置包含 原数组1位置    值为2        1位置前面没有位置 所以包含1位置自身
     * 2位置包含      1-2位置   值为2+3      2位置前面1位置 长度都是1个数 合并成一组变成2个数  所以2位置包含1-2
     * 3位置包含       3 位置   值为4        3位置前面是1-2位置组成的长度2个数的组  3位置只有一个数 不能合并 所以只包含3当前位置
     * 4位置包含      1-4位置   值为2+3+4+6  4位置前面是3位置长度1个数的组 与4位置当前一个数长度相等 合并成一组变成2个数 此时是3-4,再往前看 右1-2组成的长度2个数的组 与当前3-4长度一致 所以可以合并 包含1-4的长度4个数的组
     * 5位置包含       5            7        5 同理 只有自己成组
     * 6             5-6           7+5       6 同理  与前面5 的长度一个数组可以合并成为 包含5-6的组长度2个数 再往前是1-4的长度4的组 长度不一致不能合并 所以是5-6范围
     * 7               7           9          7 同理 前面长度2的组 不能合并 只有当前位置本身一个数
     * 8               1-8         2+3+4+6+7+5+9+33   8 同理 与前面位置 长度一个数的7位置合并 包含7-8的组 再往前与5-6组合并 形成5-8的长度4的组 再往前与1-4的长度4个数的组合并 形成包含1-8的长度8的组 所以当前位置8包含1-8的数
     * ...
     */

    public static class iTree{
        private int[] tree;    //树结构数组
        private int n;         //数组实际个数
        public iTree(int size){
            n = size;
            tree = new int[size +1];  //树结构默认去掉0位置 从1位置开始 所以长度+1
        }

        //求和方法 将1...index 累加求和
        public int sum(int index){
            int res = 0;     //定义结果变量

            //开始进行累加 tree[index] 值是包含哪个区间的数 可能就是index本身一个数 也可能是i...index区间的数 也可能是1..i..index包含全部从头至index的数 根据前面的演示来分析
            //比如要求1--8  那么tree[8] 就是1-8的求和值
            //比如要求1-6   那么tree[6] 是5-6的求和值 还有加上 tree[4] 1-4的求和值  就需要分段累加
            //分段累加的位置怎么定义 就有公式 将index 依次减去其二进制位最右侧1的二进制数 直到0 每个值就是各个区间段的求和
            //比如 index = 8  1000  先加上当前位置的值tree[8]  减去最右侧1的二进制 就是1000  得到0 就退出  所以值就是tree[8]
            //比如 index = 6  0110  先加上当前位置的值tree[6]  减去最右侧1的二进制 就是0010  得到0100  还没到0 继续
            // 0100 就是4           先加上当前位置的值tee[4]   减去最右侧1的二进制 就是0100  得到0 就退出  所以值就是tree[6]+tree[4]
            //所以需要依次根据index 的向前移动公式 进行分段累加 直到完成1...index区间累加和
            while (index > 0){
                //结果集累加
                res += tree[index];
                //向前刷新index   依次减去最右侧的二进制位上的1  直到index来到0跳出循环
                //-index 就是 ~index +1 取反+1  接着在与运算index  就能提出index 最右侧1
                //比如index  :           0011001000
                //  -index  (~index+1):  1100111000
                //index &  -index     :  0000001000  就取出了index最右侧1 的二进制数
                index -= index & (-index);
            }
            return res;
        }


        //添加数方法 在index位置加入数num
        //注意 添加到tree数组的时候 由于我们tree数组的定义 index位置的影响 可能有多个位置索引影响 需要对每个影响的位置都加上num
        //比如 在 3位置 加入 2  首先 小于3位置的1 2肯定不会影响 因为 索引的值范围是不会超过当前索引的 最右范围就是包含自身 不会再往右了
        //那么还有哪些位置 包含3    比如 4位置 就是3-4位置的求和 8位置 就是1-8位置的求和  16位 就是1-16位置的求和..最后不超过整个数组n 比如n就在15 那么影响的位置就是 3 4 8 需要对这两个位置刷新
        //所以这个位置 就有对应的公式 需要向后移动的公式 分段进行累加 直到超过n长度范围
        //与求和的公式类似 同样是用到 index二进制最右侧1的二进制数 这里就不是减 而是加  N假设15
        //比如 index = 3  num=2  n= 15
        // 0011  2先加上当前位置的值tree[3]  +最右侧1的二进制 就是0001  得到0100  4<15 继续
        // 0100 就是4           2先加上当前位置的值tee[4]   +最右侧1的二进制 就是0100  得到1000  8<15 继续
        //1000  就是8           2先加上当前位置的值tee[8]   +最右侧1的二进制 就是1000  得到10000 16>15 退出
        //最后得到 影响3位置的 有 3 4 8 三个位置 进行分别加上2

        public void add(int index, int num){
            //index 根据公式向后移动 不超过整个数组最后的索引n  n是个数 同时也可以作为最后一个位置的索引
            while (n >= index){
                //对影响的位置累加num
                tree[index] += num;
                //index位置往后滚动
                index += index & (-index);
            }
        }
    }

    public static class Right {
        private int[] nums;
        private int N;

        public Right(int size) {
            N = size + 1;
            nums = new int[N + 1];
        }

        public int sum(int index) {
            int ret = 0;
            for (int i = 1; i <= index; i++) {
                ret += nums[i];
            }
            return ret;
        }

        public void add(int index, int d) {
            nums[index] += d;
        }

    }

    public static void main(String[] args) {
        int N = 100;
        int V = 100;
        int testTime = 2000000;
        iTree tree = new iTree(N);
        Right test = new Right(N);
        System.out.println("test begin");
        for (int i = 0; i < testTime; i++) {
            int index = (int) (Math.random() * N) + 1;
            if (Math.random() <= 0.5) {
                int add = (int) (Math.random() * V);
                tree.add(index, add);
                test.add(index, add);
            } else {
                if (tree.sum(index) != test.sum(index)) {
                    System.out.println("Oops!");
                }
            }
        }
        System.out.println("test finish");
    }

}

 

三、IndexTree 二维数组代码演示

package class32;

/**
 * IndexTree 改二维数组
 * // 测试链接:https://leetcode.com/problems/range-sum-query-2d-mutable
 *
 * 时间复杂度 O(logN) * O(logM)
 */
public class IndexTree2D {
    private int[][] tree;    //二维数组的树结构数组
    private int[][] nums;    //拷贝题目传递的二维数组保存下来
    private int n;           // nums数组的行数  同时对应tree数组的最后行索引位置
    private int m;           // nums数组的列数  对应tree数组的最后列索引位置

    public IndexTree2D(int[][] matrix) {  //构造函数
        n = matrix.length;
        m = matrix[0].length;
        tree = new int[n + 1][m + 1];  //tree数组下标默认从1开始 0不用 所以长度+1
        nums = new int[n][m];          //深拷贝 入参数组matrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++){
                //遍历传递的二维数组 将每个位置的值,都更新到我们tree 和 nums数组中
                update(i,j,matrix[i][j]);
            }
        }
    }

    //刷新原数组row行 col列的值为val
    public void update(int row, int col, int val){
        if(n == 0 || m == 0) return;   //是否刷新 需要先判断我们数组长度
        int add = val - nums[row][col];  //修改值转换成 添加  用来刷新tree数组值 当前nums[row][col]值修改成matrix[row][col]=val的值 那么加多少 就是可以将修改后的val- 当前的nums[row][col]值
        nums[row][col] = val;           //刷新nums的拷贝数组值

        //二维数组 刷新tree数组 相关的是哪几列几行,就是将每一行 每一列 按照一维数组的相关公式依赖去向右滚动i j 位置 遍历  row * col就有这么多个位置需要累加
        for(int i = row+1; i <= n; i+= i & (-i) ){
            for(int j= col+1; j <= m; j+= j & (-j)){
                //遍历i 行 r列  起始下标要+1 因为定义结果中 tree是索引从1...n/m 对应原数组0...n-1/m-1
                tree[i][j] += add;
            }
        }
    }

    //返回数组 1,1...到row,col 位置的求和值
    public int sum(int row, int col){
        int res = 0;     //定义一个结果集

        //二维数组 累加对应位置的tree数组 相关的是哪几列几行,就是将每一行 每一列 按照一维数组的相关公式依赖去向左滚动i j 位置 遍历  row * col就有这么多个位置需要累加
        for(int i = row +1; i >0; i -= i & (-i)){
            for(int j = col + 1; j >0; j-= j & (-j)){
                //遍历i 行 r列  起始下标要+1 因为定义结果中 tree是索引从1...n/m 对应原数组0...n-1/m-1
                res += tree[i][j];
            }
        }
        return res;
    }

    //求返回数组 某个位置row1,col1 到 row2,col2的 求和数   不再是从1,1开始
    //sum(row2,col2)  值为 1,1 --> row2,col2
    //sum(row1,col1)  值为 1,1 --> row1,col1
    //假设 3,3  -> 4,4  的求和数   那么这个矩阵其实就是在 1,1->4,4大矩阵的内侧
    //需要减去其他位置的值
    //   x x x x
    //   x x x ,
    //   x x 1 2
    //   x . 3 4
    // 如图: sum(4,4) 就是整个矩阵值 而标记x的都是不需要的
    // 另外要减去 sum(4,2) 也就是标记. 到左上角x的矩阵 2*4=8个
    // 再减去 sum(2,4)  也就是标记,  到左上角x的矩阵 4*2=8个
    //这里面 左上角2*2的矩阵 重复减多1次 所以再加上sum(2,)的值
    //就得到了 3,3到4,4的求和值了
    public int sumRegion(int row1, int col1, int row2, int col2){
        return sum(row2,col2) - sum(row2,col1-1) - sum(row1 - 1,col2) + sum(row1 -1,col1-1);
    }


}

 

四、AC自动机

解决在一个大字符串中,找到多个候选字符串的问题  

AC自动机算法核心

1)把所有匹配串生成一棵前缀树

2)前缀树节点增加fail指针

3fail指针的含义:如果必须以当前字符结尾,当前形成的路径是str,剩下哪一个字符串的前缀和str的后缀,拥有最大的匹配长度。fail指针就指向那个字符串的最后一个字符所对应的节点。

 

1、获取候选字符串数组 有多少个字符串 是包含在大文章字符串中的 返回符合的数量

package class32;

import java.util.LinkedList;
import java.util.Queue;

/**AC自动机
 * 解决在一个大字符串中,找到多个候选字符串的问题
 * <p>
 * AC自动机算法核心
 * 1)把所有匹配串生成一棵前缀树
 * <p>
 * 2)前缀树节点增加fail指针
 * <p>
 * 3)fail指针的含义:如果必须以当前字符结尾,当前形成的路径是str,剩下哪一个字符串的前缀和str的后缀,拥有最大的匹配长度。fail指针就指向那个字符串的最后一个字符所对应的节点。
 */
public class AC1 {

    //支持返回候选字符串有多少个是包含在大文章字符串中的 返回数量

    //前缀树节点
    public static class Node{
        private int end;        //end表示当前字符串节点结尾的个数 如果有则当前节点节点 累加
        private Node fail;      // fail指针节点,是AC自动机的一个核心指针   指向下个遍历节点
        private Node[] next;    //前缀树数组节点 记录每个字符串的依次指向

        public Node(){       //构造函数  初始化
            end = 0;
            fail = null;
            next = new Node[26];
        }
    }

    //定义AC自动机的类
    public static class ACAutomation {
        //定义一个前缀树类节点
        private Node root;

        public ACAutomation(){
            root = new Node();
        }

        //添加候选的字符串,构建前缀树数组   比如有多个字符串 abc, edc,ijn等 依次先通过insert方法添加 完善好前缀树数组
        public void insert(String s){
            char[] str = s.toCharArray();        //转换字符数组
            Node cur = root;                     //当前节点指向root
            int index = 0;
            for(int i = 0; i < str.length; i++){
                index = str[i] - 'a';                //遍历当前每个字符的位置
                if(cur.next[index] == null){
                    cur.next[index] = new Node();   //如果当前位置还未构建节点 那就赋值初始化节点
                }
                cur = cur.next[index];              //再将当前节点位置指向来到当前遍历的子字符位置
            }
            cur.end++;    //最后遍历完整个字符之后,再最后的字符节点位置的end值加1 表示当前结尾的字符 是一个候选字符串
        }

        //待我们将需要匹配的候选字符串都通过insert方法都添加到AC自动机类中 构建好前缀树数组后
        //我们再通过build方法 给当前前缀树 完善其 fail的指针指向内容
        public void build() {
            Queue<Node> queue = new LinkedList<>();    //定义队列集合
            queue.add(root);      //增加当前root节点入队列 进行宽度优先遍历前缀树  同时完善fail指针
            Node cur = null;      //定义当前节点  进行辅助遍历
            Node cfail = null;    //定义当前节点的fail指针 辅助
            while(!queue.isEmpty()){
                cur = queue.poll();     //弹出队列节点 此时cur是表示父节点 依次去完善其子节点的 fail指针
                for(int i = 0; i < 26; i++){   //依次遍历每一层节点路径 有26个字符进行遍历
                    if(cur.next[i] != null){   //当下个子节点存在的时候 进行逻辑分析
                        cur.next[i].fail = root;    //先将子节点的fail指向root  后续如果有存在的真实节点指向在后面会修改
                        cfail = cur.fail;           //当前子节点的fail先指向父节点的fail
                        while(cfail != null){     //遍历cfail指向直到空就退出 如果其next[i]位置非空 那么就说明是实际的fail指向 刷新 cur.next[i].fail
                            if(cfail.next[i] != null){
                                cur.next[i].fail = cfail.next[i];
                                break; //找到之后 直接退出循环
                            }
                            cfail = cfail.fail;   //没有找到 就接着遍历fail指向循环下去
                        }
                        queue.add(cur.next[i]); // 最后将当前i位置的子节点存在的 就加入队列 继续下层遍历
                    }
                }
            }

        }

        //当候选要判断的字符串都通过insert方法 构建好了前缀树 以及通过build构建好对应的fail指向节点后 整个AC自动机就已经完成
        //接着就是判断这些字符串 是否都包含在目标大文章字符串内  并返回包含在内的字符串数量
        public int containNum(String content){
            char[] str = content.toCharArray();     //大文章字符串转换字符数组
            Node cur = root;                         //定义cur节点指向root 进行依次遍历
            Node follow = null;                      //定义follow节点用于指向cur 进行fail指向遍历 目的是不影响cur的位置
            int res = 0;                            //结果数量
            int index = 0;                           //nexts数组位置 下个子节点字符位置
            for(int i = 0; i < str.length; i++){           //开始遍历字符路径
                index = str[i] - 'a';              //字符对应的索引
                while(cur.next[index] == null && cur != root){  //开始遍历cur对应的下个子字符next[index]如果空 且cur非根节点 那么就cur指向fail节点进行循环遍历
                    cur = cur.fail;
                }
                //那么来到这里 可能是next[index]非空 存在值  或者cur走回到root 那么就根据两个情况刷新cur
                cur = cur.next[index] != null ? cur.next[index] : root;
                follow = cur;      //此时follow节点指向cur  进行前置的fail指向遍历 去判断是否存在候选字符串
                while(follow != root){    //从当前follow节点开始往前遍历 直到回到root就退出 因为root.fail指向是空 需要再遍历
                    if(follow.end == -1){
                        break;      //如果遍历到当前节点的end值是-1 说明被标记添加过了 后续的就不用再遍历了 直接退出当前循环
                    }
                    {
                        res += follow.end;  //因为end默认值0 可以直接累加 不管是否是字符串结尾
                        follow.end = -1;    //并且将当前位置的end设置-1 再下次的遍历中 就不再重复遍历前面已经走过的fail指针了 节省时间

                    }


                    follow = follow.fail;
                }
            }
            return res;
        }
    }

    public static void main(String[] args) {
        ACAutomation ac = new ACAutomation();
        ac.insert("dhe");
        ac.insert("he");
        ac.insert("c");
        ac.build();
        System.out.println(ac.containNum("cdhe"));
    }
}

2、获取候选字符串数组 有哪些字符串 是包含在大文章字符串中的 返回符合的字符串集合文章来源地址https://www.toymoban.com/news/detail-424903.html

package class32;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**AC自动机
 * 解决在一个大字符串中,找到多个候选字符串的问题
 * <p>
 * AC自动机算法核心
 * 1)把所有匹配串生成一棵前缀树
 * <p>
 * 2)前缀树节点增加fail指针
 * <p>
 * 3)fail指针的含义:如果必须以当前字符结尾,当前形成的路径是str,剩下哪一个字符串的前缀和str的后缀,拥有最大的匹配长度。fail指针就指向那个字符串的最后一个字符所对应的节点。
 */
public class AC2 {
    //支持返回候选字符串有哪些是包含在大文章字符串中的 返回字符串内容

    //定义前缀树的节点
    public static class Node {
        private String end;      //表示当前节点是否作为 候选字符串的结尾  如果是 那么end就是该字符串 否则就是空
        private boolean endUse;  //表示当前节点作为候选字符串结尾时,是否被加入过集合中 true则表示加入 后续循环遍历到则可以减少遍历直接退出
        private Node fail;       //fail指针节点,是AC自动机的一个核心指针   指向下个遍历节点
        private Node[] nexts;    //前缀树数组节点 记录每个字符串的依次指向

        public Node() {           //构造函数 初始化
            end = null;
            endUse = false;
            fail = null;
            nexts = new Node[26];   //数组 定义字符都是小写或大写 一共26个长度
        }
    }


    //定义AC自动机的类
    public static class ACAutomation {
        private Node root;      //定义一个根节点

        public ACAutomation() {  //构造函数  初始化节点
            root = new Node();
        }

        //添加候选的字符串,构建前缀树数组   比如有多个字符串 abc, edc,ijn等 依次先通过insert方法添加 完善好前缀树数组
        public void insert(String s) {
            char[] str = s.toCharArray();      //将候选字符串转换成字符数组
            Node cur = root;                   //将cur节点指向root节点 用来从根节点开始遍历
            int index = 0;                     //遍历前缀树数组nexts的索引
            for (int i = 0; i < str.length; i++) {    // 依次遍历每个字符
                index = str[i] - 'a';               //获取每个字符 转换对应的索引位置
                if (cur.nexts[index] == null) {
                    cur.nexts[index] = new Node();  //如果所加的字符 当前路径数组没有对应节点 那么就给他初始化一个节点对象
                }

                //然后将当前节点往下个节点位置滚动 依次将这个str每个字符都给串起来 指向对应索引位置的nexts数组
                //如果前面cur.nexts[index]已经有路径非空 也是同样的将cur节点来到下个字符位置
                cur = cur.nexts[index];
            }
            //nexts数组遍历填充完成后 在cur来到最后一个字符位置 的end字符串标识 赋值当前添加的字符串s
            cur.end = s;
        }

        //待我们将需要匹配的候选字符串都通过insert方法都添加到AC自动机类中 构建好前缀树数组后
        //我们再通过build方法 给当前前缀树 完善其 fail的指针指向内容
        public void build() {
            Queue<Node> queue = new LinkedList<>();           //构建一个队列集合 用来进行宽度优先遍历前缀树
            queue.add(root);                                  //先将root AC自动机的根节点加入队列集合
            Node cur = null;                                  //定义当前树节点 赋值变量 用来接收遍历的当前节点
            Node cfail = null;                                //定义当前树节点fail指针的指向节点
            while (!queue.isEmpty()) {
                cur = queue.poll();                 //弹出当前这个节点 作为一个父节点
                for (int i = 0; i < 26; i++) {        //遍历全部自负路径
                    if (cur.nexts[i] != null) {       //当遇到当前i字符位置 非空 说明是有节点字符
                        cur.nexts[i].fail = root;   //我们先把当前nexts数组子字符的fail指向到root 节点  后面如果有其对应的一个指向节点 后面会刷新
                        cfail = cur.fail;           //当前这个子节点的fail指向赋值为父节点的fail指向cur.fail
                        while (cfail != null) {       //遍历cfail 依次指向其fail指向 直到回到root root.fail=null 到空则跳出循环
                            if (cfail.nexts[i] != null) {    //如果cfail指向的 下个子节点非空 那么这个就是当前子节点的fail指向
                                cur.nexts[i].fail = cfail.nexts[i];
                                break;   //找到后就直接退出
                            }
                            cfail = cfail.fail;  //没有找到就继续指向fail下个节点 最后如果都没找到cfail指向就是指向null
                        }
                        queue.add(cur.nexts[i]); //接着将当前对应的下个子节点字符加入 队列进行遍历
                    }
                }
            }
        }

        //当候选要判断的字符串都通过insert方法 构建好了前缀树 以及通过build构建好对应的fail指向节点后 整个AC自动机就已经完成
        //接着就是判断这些字符串 是否都包含在目标大文章字符串内  并返回list集合 包含在内的这些字符串
        public List<String> containWords(String content) {
            char[] str = content.toCharArray();                   //字符串转换字符数组
            List<String> res = new ArrayList<>();                 //定义结果集
            Node cur = root;                                      //定义cur节点指向root 进行依次遍历
            Node follow = null;                                   //定义follow节点用于指向cur 进行fail指向遍历 目的是不影响cur的位置
            int index = 0;                                        //nexts数组位置 下个子节点字符位置
            for (int i = 0; i < str.length; i++) {
                index = str[i] - 'a';         // 获取当前字符的位置

                //当前下个字符位置如果为空 且 当前 节点不在根节点时,继续遍历cur节点的fail指针  直到遇到当前下个字符位置i不为空 或者cur 指向返回到了root节点 退出循环
                while (cur.nexts[index] == null && cur != root) {
                    cur = cur.fail;
                }
                //刷新cur 当前来到的节点位置
                //如果是nexts指向不为空退出的情况 那么表示当前这个字符是存在前缀树结果中 接着指向下个字符 如果是cur指向到了root 说明就不存在该字符 那么就是返回root 节点
                cur = cur.nexts[index] != null ? cur.nexts[index] : root;
                //此时 将follow节点 指向cur节点 进行前缀树的遍历 判断其指向fail节点的end是否存在值 若是那么就表示该值字符串是包含在大文章字符串中的 添加到结果集
                //使得cur指向保持不变 对于下次遍历就从cur开始
                follow = cur;
                while (follow != root) {
                    //遍历 直到回到root 就退出循环
                    if (follow.endUse) {
                        break;  //先判断 当前节点是否是已经加入过了的字符串 如果是就直接退出循环 后续的就不用再继续指向了 因为已经加过了
                    }

                    if (follow.end != null) {
                        res.add(follow.end); //如果end字符串非空 说明当前这个字符串包含在大文章中 添加到集合
                        follow.endUse = true; //设置当前字符串已经加入集合 后续再遍历到的时候就可以直接退出   当然这句可以直接放在if外面执行 都是一样的 因为遍历过的当前fail指针节点都不需要下次再重复遍历
                    }
                    follow = follow.fail;   //follow节点继续指向fail指针节点
                }
            }
            return res;  //最后返回该集合

        }
    }

    public static void main(String[] args) {
        ACAutomation ac = new ACAutomation();
        ac.insert("dhe");
        ac.insert("he");
        ac.insert("abcdheks");
        // 设置fail指针
        ac.build();

        List<String> contains = ac.containWords("abcdhekskdjfafhasldkflskdjhwqaeruv");
        for (String word : contains) {
            System.out.println(word);
        }
    }

}

到了这里,关于【算法&数据结构体系篇class32】:IndexTree & AC自动机的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 异地容灾系统和数据仓库系统设计和体系结构

    ( 1)生产系统数据同步到异地容灾系统 生产系统与异地容灾系统之间是通过百兆网连接的;生产系统的数据库是 Oracle 9i RAC,总的数据量大约为 3 TB,涉及五千多张表。对这些表进行分析归 类,发现容灾系统真正需要实时同步的表大约只有五百张,数据量约为 1 TB,只 要能

    2024年02月09日
    浏览(46)
  • mysql从入门到放弃之数据库体系结构与管理

    第一篇文章中主要学习了mysql二进制的基本安装及数据库初始化等操作,本篇文章主要了解mysql的体系结构和管理,例如: mysql的实例组成、逻辑存储结构、物理存储结构等方面展开学习 提示:以下是本篇文章正文内容,下面案例可供参考 3.1、mysqld守护进程结构 3.2、 引入sql语句

    2024年01月21日
    浏览(52)
  • PGSQL(PostgreSQL)数据库基础篇:PostgreSQL 的 主要优点 、 劣势 、体系结构 、核心功能 、安装教程。

    1.维护者是PostgreSQL Global Development Group,首次发布于1989年6月。 2.操作系统支持WINDOWS、Linux、UNIX、MAC OS X、BSD。 3.从基本功能上来看,支持ACID、关联完整性、数据库事务、Unicode多国语言。 4.表和视图方面,PostgreSQL支持临时表,而物化视图,可以使用PL/pgSQL、PL/Perl、PL/Python或其

    2024年04月26日
    浏览(65)
  • 算法 数据结构分类 数据结构类型介绍 数据结构线性非线性结构 算法合集 (一)

     数据结构分为:                            a.线性结构                            b.非线性结构  a.线性结构:                       数据与结构存在一对一的线性关系; a . 线性结构 存储 分为:                                   顺序存储

    2024年02月10日
    浏览(53)
  • 【算法与数据结构】--算法应用--算法和数据结构的案例研究

    一、项目管理中的算法应用 在项目管理中,算法和数据结构的应用涉及项目进度、资源分配、风险管理等方面。以下是一些案例研究,展示了算法在项目管理中的实际应用: 项目进度管理 : 甘特图算法 :甘特图是一种项目进度管理工具,它使用甘特图算法来展示项目任务

    2024年02月08日
    浏览(58)
  • 【Azure】微软 Azure 基础解析(四)Azure核心体系结构组件之数据中心、区域与区域对、可用区和地理区域

    本系列博文还在更新中,收录在专栏:「Azure探秘:构建云计算世界」 专栏中。 本系列文章列表如下: 【Azure】微软 Azure 基础解析(三)描述云计算运营中的 CapEx 与 OpEx,如何区分 CapEx 与 OpEx 【Azure】微软 Azure 基础解析(四)Azure核心体系结构组件之数据中心、区域与区域

    2024年02月15日
    浏览(57)
  • 数据结构与算法设计分析—— 数据结构及常用算法

    1、顺序表与链表 线性表是 线性结构 ,是包含n个数据元素的有限序列,通过顺序存储的线性表称为 顺序表 ,它是将线性表中所有元素按照其逻辑顺序,依次存储到指定存储位置开始的一块连续的存储空间里;而通过链式存储的 链表 中,每个结点不仅包含该元素的信息,还

    2024年02月07日
    浏览(62)
  • 数据结构和算法——数据结构

    目录 线性结构  队列结构的队列 链表结构的队列 链表的面试题 单向链表应用场景 约瑟夫环问题 栈结构 中缀表达式 前缀表达式 后缀表达式 非线性结构 图 递归解决迷宫问题 递归解决八皇后问题 顺序存储方式,顺序表 常见的顺序存储结构有:数组、队列、链表、栈 链式存

    2024年02月07日
    浏览(56)
  • 数据结构与算法 --- 数据结构绪论

    早期人们都把计算机理解为数值计算工具,就是感觉计算机当然是用来计算的,所以计算机解决问题,应该是先从具体问题中抽象出一个适当的数据模型,设计出一个解此数据模型的算法,然后再编写程序,得到一个实际的软件。 可现实中,我们更多的不是解决数值计算的问

    2024年02月14日
    浏览(54)
  • 数据结构与算法——数据结构有哪些,常用数据结构详解

    数据结构是学习数据存储方式的一门学科,那么,数据存储方式有哪几种呢?下面将对数据结构的学习内容做一个简要的总结。 数据结构大致包含以下几种存储结构: 线性表,还可细分为顺序表、链表、栈和队列; 树结构,包括普通树,二叉树,线索二叉树等; 图存储结构

    2024年02月15日
    浏览(63)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包