数据结构学习

手动实现动态数组

动态数组的要求

动态数组需要实现以下三个要求： 1.自动扩缩容 2.检查索引边界防止数组越界 3.及时删除元素防止内存泄漏

具体实现：

#include <iostream>
#include <stdexcept>

using namespace std;

template<typename E>

class MyArrayList{
  private:
    // 真正存储数据的数组
    E* data;
    // 数组中的元素个数
    int size;
    // 数组的最大容量
    int cap;
    // 初始容量
    static const int INIT_CAP = 1;

  public:
    MyArrayList() {
      this -> data = new E[INIT_CAP];
      this -> size = 0;
      this -> cap = INIT_CAP;
    }

    MyArrayList(int initCapacity) {
      this -> data = new E[initCapacity];
      this -> size = 0;
      this -> cap = initCapacity;
    }

    // 增
    void addLast(E e) {
      if (size == cap) {
       resize(cap * 2);
      }

      data[size] = e;
      size++;
    }

    void add(int index, E e) {
      checkPositionIndex(index);

      if (size == cap) {
        resize(cap * 2);
       }

      for (int i = size - 1; i >= index; i--) {
        data[i + 1] = data[i];
      }

      data[index] = e;
      size++;
    }

    void addFirst(E e) {
      add(0,e);
    }

    // 删
    E removeLast() {
      if (size == 0) {
        throw std::out_of_range("NoSuchElementException");
      }

      if (size == cap / 4) {
        resize(cap / 2);
      }

      E deletedVal = data[size - 1];

      data[size - 1] = E();
      size--;

      return deletedVal;
    }

    E remove(int index) {
      checkElementIndex(index);

      if (size == cap / 4) {
        resize(cap / 2);
      }

    E deletedVal = data[index];

      for (int i = index + 1; i < size; i++) {
        data[i - 1] = data[i];
      }

      data[size - 1] = E();
      size--;

      return deletedVal;
    }

    E removeFirst() {
      return remove(0);
    }

    // 改
    E set(int index, E element) {
      checkElementIndex(index);

      E oldVal = data[index];
      data[index] = element;
      return oldVal;
    }

    // 查
    E get(int index) {
      checkElementIndex(index);

      return data[index];
    }

    // 工具方法
    int getSize() {
      return size;
    }

    bool isEmpty() {
      return size == 0;
    }

    bool isElementIndex(int index) {
      return index >= 0 && index < size;
    }

    bool isPositionIndex(int index) {
      return index >= 0 && index <= size;
    }

    void checkElementIndex(int index) {
      if (!isElementIndex(index)) {
        throw std::out_of_range("Index out of bounds");
      }
    }

    void checkPositionIndex(int index) {
      if (!isPositionIndex(index)) {
        throw std::out_of_range("Index out of bounds");
      }
    }

    void resize(int newCap) {
      E* temp = new E[newCap];

      for (int i = 0; i < size; i++) {
        temp[i] = data[i];
      }

      delete[] data;
      data = temp;
      cap = newCap;
    }

    void display() {
      cout << "size=" << size << "cap=" << cap <<endl;

      for (int i = 0; i < size; i++) {
        cout << data[i] << " ";
      }
      cout << endl;
    }

    ~MyArrayList() {
      delete[] data;
    }
};

int main() {
  MyArrayList<int> arr(3);

  for (int i = 0; i <= 5; i++) {
    arr.addLast(i);
  }

  arr.remove(3);
  arr.add(1,9);
  arr.addFirst(100);

  for (int i = 0; i < arr.getSize(); i++) {
        std::cout << arr.get(i) << std::endl;
    }

    return 0;
}

二叉树

二叉树的实现方法和链表有点像，都由一个个节点组成，节点包含有节点的值和指向下一节点的指针。但和链表不同的是，二叉树每个节点都有两个引用（指针），分别指向左子节点（left-child node）和右子节点（right-child node），该节点被称为这两个子节点的父节点（parent node）。当给定一个二叉树的节点时，我们将该节点的左子节点及其以下节点形成的树称为该结点的左子树（left subtree），同理可得右子树（right subtree）。

在二叉树中，除叶节点外其他节点都包含子节点和非空子树。

二叉树常用术语：根节点（root node）：位于二叉树顶层的节点，没有父节点。叶节点（leaf node）：没有子节点的节点，其两个指针均指向None. 边（edge）：连接两个节点的线段，即节点引用（指针）。节点所在的层（level）：从顶至底递增，根节点所在层为1. 节点的度（degree）：节点的子节点的数量。在二叉树中，度的取值范围0、1、2。二叉树的高度（height）：从根节点到最远叶所经过的边的数量。节点的深度（depth）：从根节点到该节点所经过的边的数量。节点的高度（height）：从距离该节点最远的叶节点到该节点所经过的边的数量。

完整实现二叉树：

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr){}
};

TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->right->left = new TreeNode(5);
root->right->right = new TreeNode(6);

// 构建出来的二叉树是这样的：
//     1
//    / \
//   2   3
//  /   / \
// 4   5   6

初始化一个二叉树：

TreeNode* n1 = new TreeNode(1);
TreeNode* n2 = new TreeNode(2);
TreeNode* n3 = new TreeNode(3);
TreeNode* n4 = new TreeNode(4);
TreeNode* n5 = new TreeNode(5);

n1->left = n2;
n1->right = n3;
n2->left = n4;
n2->right = n5;

向二叉树中插入和删除节点

TreeNode* P = new TreeNode(0);
// 在n1 -> n2 中间插入节点 P
n1->left = P;
P->left = n2;
// 删除节点P
n1->left = n2;
delete P;