二，数据结构与算法 - 348052148/learnGraph GitHub Wiki

  1. 数据结构
  2. 算法

数据结构概念

  1. 数据 对客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称
  2. 数据项 数据项是指不能再分的最新单位
  3. 数据元素 是指包含数据项的集合
  4. 数据对象 性质相同的数据元素的集合，是数据的一个子集。

数据结构

  1. 集合 ， 线型 , 树型 , 图型

数据类型

  1. 原子类型：值不可再分割。比如Java中的int，char，String等。
  2. 结构类型：由若干成分按某种结构组成，可以被分解。比如一个整型数组，可以循环分割成多个整型元素。
  3. 抽象数据类型（ADT） 指一个数学模型以及定义在该模型上的一组操作

存储结构

  1. 顺序存储
  2. 链式存储

串结构

优先队列

中缀表达式转后缀

从左到右查找

  1. 如果是数字直接 输出
  2. 如果是操作符 和 （ 放入栈中
  3. 如果遇到 ） 将栈元素弹出直到遇到 （ 为止
  4. 遇到任何其他操作符，从栈中探出元素直到遇到更低优先级元素为止
  5. 到末尾依次弹出栈

后缀表达式计算

  1. 遇到数字压入栈
  2. 遇到操作符从栈中弹出2个数字进行计算后压入栈

树

AVL 树， 二叉平衡树

  1. 本身首先是一棵二叉搜索树。
  2. 带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。

红黑树

B树

B+ B*树

后缀树

相关树的算法

  • 有序链表转二叉树

利用快慢指针， 找到 n / 2 节点作为 root , 再找到 [0, n / 2] 中的 (n/2) / 2 节点作为 left 节点， 再找到 [n /2, n ] 中的 (n/2 + n) / 2 节点作为 right 节点，按此递归

  • 一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表
    // 中序遍历
    //双向链表的左边头结点和右边头结点
    TreeNode leftNode = null;
    TreeNode rightNode = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        //递归调用叶子节点的左右节点时返回null
        if(pRootOfTree == null){
            return null;
        }

        Convert(pRootOfTree.left);
        //第一次遍历左子树里的最小值，把节点赋值给左边头结点和右边头结点
        if(rightNode == null){
            leftNode = rightNode = pRootOfTree;
        }else{
            //把遍历到的节点放到rightNode后边，把rightNode往后移一位
            rightNode.right = pRootOfTree;
            pRootOfTree.left = rightNode;
            rightNode = pRootOfTree;

        }
        Convert(pRootOfTree.right);

        return leftNode;

    }