类库与数据结构具体操作解析

Ch2: 容器与数据结构

数组（Array）实现容器
- 代码示例：
  1
  2
  3
  4
  5
  int arr[5] = {1, 2, 3, 4, 5};
  // 访问元素
  for (int i = 0; i < 5; i++) {
  cout << arr[i] << " ";
  }
- 操作：数组支持高效的随机访问，但不适合频繁的插入和删除操作。

链表（Linked List）实现容器

代码示例：

struct Node {
    int data;
    Node* next;
};

// 插入到链表头部
void push(Node** head, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = *head;
    *head = new_node;
}

// 遍历链表
void printList(Node* node) {
    while (node != nullptr) {
        cout << node->data << " ";
        node = node->next;
    }
}

迭代器的使用
- 代码示例：
  1
  2
  3
  4
  vector<int> v = {1, 2, 3, 4, 5};
  for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
  cout << *it << " ";
  }
- 操作：迭代器提供一种通用的遍历容器的方法，使得代码可以独立于具体容器。

Ch3: 算法复杂度

时间复杂度分析
- 代码示例：
  1
  2
  3
  4
  5
  // O(n)复杂度
  int sum = 0;
  for (int i = 1; i <= n; i++) {
  sum += i;
  }
- 操作：通过循环次数和嵌套关系可以计算代码的时间复杂度。

Ch4: 递归

递归实现阶乘
- 代码示例：
  1
  2
  3
  4
  int factorial(int n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
  }
- 操作：递归方法计算阶乘，基于n! = n * (n-1)!定义递归关系。

递归计算斐波那契数列

代码示例：

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Ch5: Vector 和 Deque

Vector的使用

代码示例：

vector<int> vec;
vec.push_back(10);
vec.push_back(20);
for (int i = 0; i < vec.size(); i++) {
    cout << vec[i] << " ";
}

操作：push_back用于向Vector末尾添加元素，size()返回元素个数。

Deque的使用

代码示例：

deque<int> deq;
deq.push_back(10);
deq.push_front(20);
for (deque<int>::iterator it = deq.begin(); it != deq.end(); ++it) {
    cout << *it << " ";
}

操作：push_front和push_back支持在头部和尾部插入元素，deque适合双向插入删除操作。

Ch6: List

List容器的使用

代码示例：

list<int> lst;
lst.push_back(10);
lst.push_front(20);
for (list<int>::iterator it = lst.begin(); it != lst.end(); ++it) {
    cout << *it << " ";
}

操作：List使用双向链表实现，适合频繁的插入和删除操作。

Ch7: 容器适配器

栈（Stack）的使用
- 代码示例：
  1
  2
  3
  4
  5
  stack<int> stk;
  stk.push(10);
  stk.push(20);
  cout << stk.top(); // 输出20
  stk.pop();
- 操作：栈的push、pop和top操作分别用于插入、删除和访问栈顶元素。
队列（Queue）的使用
- 代码示例：
  1
  2
  3
  4
  5
  queue<int> q;
  q.push(10);
  q.push(20);
  cout << q.front(); // 输出10
  q.pop();
- 操作：队列的push、pop和front操作用于插入、删除和访问队首元素。

Ch8: 二叉树

二叉树的前序遍历

代码示例：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

void preorder(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

操作：前序遍历依次访问根节点、左子树和右子树。

二叉搜索树（BST）的插入

代码示例：

TreeNode* insert(TreeNode* root, int val) {
    if (root == nullptr) return new TreeNode(val);
    if (val < root->val) root->left = insert(root->left, val);
    else if (val > root->val) root->right = insert(root->right, val);
    return root;
}

操作：在BST中，左子树节点值小于根节点，右子树节点值大于根节点。

Ch9: 平衡二叉树

AVL树的左旋和右旋

代码示例（以右旋为例）：

TreeNode* rightRotate(TreeNode* y) {
    TreeNode* x = y->left;
    TreeNode* T2 = x->right;
    x->right = y;
    y->left = T2;
    return x;
}

操作：通过旋转保持AVL树的平衡，在插入或删除节点后进行调整。

Ch10: 红黑树

红黑树的插入和调整
- 代码示例（逻辑复杂，以下为红黑树插入的简化步骤）：
  1
  2
  3
  void insert(TreeNode* root, int val) {
  // 插入节点后，进行颜色和旋转调整，保持红黑树性质
  }
- 操作：红黑树插入操作需要调整颜色和结构，确保树满足红黑树的五个性质。

Ch11: 优先级队列

优先级队列的使用
- 代码示例：
  1
  2
  3
  4
  5
  priority_queue<int> pq;
  pq.push(10);
  pq.push(20);
  cout << pq.top(); // 输出20
  pq.pop();
- 操作：优先级队列使用堆实现，top操作用于访问优先级最高的元素。

Ch13: 哈希

哈希表的插入和查找
- 代码示例：
  1
  2
  3
  4
  unordered_map<int, string> hashTable;
  hashTable[1] = "apple";
  hashTable[2] = "banana";
  cout << hashTable[1]; // 输出 "apple"
- 操作：哈希表提供常数时间的插入和查找操作，通过哈希函数将键映射到特定位置。

链式哈希处理冲突

代码示例：

// 链式哈希的实现可以使用链表
vector<list<int>> hashTable(size);
int hash(int key) { return key % size; }

void insert(int key) {
    int index = hash(key);
    hashTable[index].push_back(key);
}

操作：使用链表处理哈希冲突，每个哈希位置存储一个链表。