常见数据结构

*问题类型：

• 数组、链表、栈、队列、树（二叉树、B树、B+树、红黑树）、图、哈希表？

• 各自的特点、优缺点、适用场景以及基本操作的复杂时间？

  数据结构	特点	优点	缺点	适用场景	常用操作时间复杂度（平均/最坏）
  数组	连续存储，定长，索引访问	随机访问快 (O(1))	插入/删除慢 (O(n))，大小固定	频繁随机访问，数据量固定	访问: O(1)； 插入/删除: O(n)； 查找: O(n)
  链表	离散存储，节点通过指针连接	插入/删除快 (O(1))	随机访问慢 (O(n))	频繁插入/删除，数据量不确定	访问: O(n)； 插入/删除: O(1)； 查找: O(n)
  栈	后进先出 (LIFO)，只在栈顶操作	操作简单高效	只能访问栈顶元素	函数调用栈，表达式求值，撤销/重做	压栈/弹栈/查看栈顶: O(1)
  队列	先进先出 (FIFO)，在队尾入，队头出	操作简单高效	只能访问队头元素	任务调度，打印队列，BFS	入队/出队/查看队头: O(1)
  二叉树	每个节点最多两个子节点	结构相对简单	可能退化为链表 (O(n))	层级关系，二叉搜索树，表达式树	搜索/插入/删除: O(h) (h为树高，最坏 O(n)，最好 O(logn))
  B树	多路平衡搜索树，节点多子，所有叶子同层	适合I/O密集型操作，减少磁盘寻道	实现复杂	文件系统，数据库索引	搜索/插入/删除: O(logmn)
  B+树	B树变体，数据只在叶子节点，叶子链表相连	范围查询效率高，查询稳定	实现复杂	数据库索引（尤其范围查询），文件系统	搜索/插入/删除: O(logmn)
  红黑树	自平衡二叉搜索树，节点有颜色	最坏情况 O(logn) 性能保证	实现相对复杂	map/set实现，Linux进程调度	搜索/插入/删除: O(logn)
  图	节点和边，表示复杂关系	适用于复杂连接关系，路径查找	实现和算法复杂，存储大	社交网络，地图导航，路由算法	取决于算法和表示 (邻接矩阵/邻接表)
  哈希表	哈希函数映射键到存储位置	平均查找/插入/删除 O(1)	最坏 O(n)，需处理冲突	字典，缓存，数据库索引，去重	插入/删除/查找: 平均 O(1)，最坏 O(n)

• 如何实现一个链表、栈、队列？

  1. 栈 (Stack)

  栈可以使用 std::vector 或者链表来实现。这里我们用 std::vector 实现，因为它在尾部操作（push_back 和 pop_back）效率很高。

  #include <iostream>
  #include <vector>
  #include <stdexcept> // For std::out_of_range
  
  // 栈的简要实现
  class Stack {
  private:
      std::vector<int> data;
  
  public:
      // 压栈
      void push(int item) {
          data.push_back(item);
      }
  
      // 弹栈
      int pop() {
          if (is_empty()) {
              throw std::out_of_range("Stack is empty, cannot pop.");
          }
          int top_item = data.back();
          data.pop_back();
          return top_item;
      }
  
      // 查看栈顶元素
      int peek() {
          if (is_empty()) {
              throw std::out_of_range("Stack is empty, no top element.");
          }
          return data.back();
      }
  
      // 判断栈是否为空
      bool is_empty() const {
          return data.empty();
      }
  
      // 获取栈的大小
      size_t size() const {
          return data.size();
      }
  };
  
  // 示例使用
  /*
  int main() {
      Stack myStack;
      myStack.push(10);
      myStack.push(20);
      std::cout << "Stack top: " << myStack.peek() << std::endl; // 20
      std::cout << "Popped: " << myStack.pop() << std::endl;      // 20
      std::cout << "Stack empty? " << (myStack.is_empty() ? "Yes" : "No") << std::endl; // No
      std::cout << "Popped: " << myStack.pop() << std::endl;      // 10
      std::cout << "Stack empty? " << (myStack.is_empty() ? "Yes" : "No") << std::endl; // Yes
      // myStack.pop(); // This would throw an exception
      return 0;
  }
  */
  

  2. 链表 (Linked List)

  这里我们实现一个单向链表，包含添加元素到末尾、添加到头部、删除元素和打印链表的功能。

  #include <iostream>
  #include <stdexcept> // For std::out_of_range
  
  // 链表节点定义
  struct Node {
      int data;
      Node* next;
  
      // 构造函数
      Node(int val) : data(val), next(nullptr) {}
  };
  
  // 链表的简要实现
  class LinkedList {
  private:
      Node* head; // 链表的头节点
  
  public:
      // 构造函数
      LinkedList() : head(nullptr) {}
  
      // 析构函数：释放所有节点内存，防止内存泄漏
      ~LinkedList() {
          Node* current = head;
          while (current != nullptr) {
              Node* next_node = current->next;
              delete current;
              current = next_node;
          }
          head = nullptr; // 确保head指向nullptr
      }
  
      // 在链表末尾添加元素
      void append(int val) {
          Node* new_node = new Node(val);
          if (head == nullptr) {
              head = new_node;
              return;
          }
          Node* current = head;
          while (current->next != nullptr) {
              current = current->next;
          }
          current->next = new_node;
      }
  
      // 在链表头部添加元素
      void prepend(int val) {
          Node* new_node = new Node(val);
          new_node->next = head;
          head = new_node;
      }
  
      // 删除指定值的第一个节点
      void remove(int val) {
          if (head == nullptr) {
              return; // 链表为空
          }
  
          if (head->data == val) {
              Node* temp = head;
              head = head->next;
              delete temp;
              return;
          }
  
          Node* current = head;
          while (current->next != nullptr && current->next->data != val) {
              current = current->next;
          }
  
          if (current->next != nullptr) { // 找到了要删除的节点
              Node* temp = current->next;
              current->next = current->next->next;
              delete temp;
          }
      }
  
      // 打印链表所有元素
      void display() const {
          Node* current = head;
          std::cout << "Linked List: ";
          while (current != nullptr) {
              std::cout << current->data << " -> ";
              current = current->next;
          }
          std::cout << "nullptr" << std::endl;
      }
  
      // 判断链表是否为空
      bool is_empty() const {
          return head == nullptr;
      }
  };
  
  // 示例使用
  /*
  int main() {
      LinkedList myList;
      myList.append(1);
      myList.append(2);
      myList.prepend(0);
      myList.display(); // Linked List: 0 -> 1 -> 2 -> nullptr
  
      myList.remove(1);
      myList.display(); // Linked List: 0 -> 2 -> nullptr
  
      myList.remove(0);
      myList.display(); // Linked List: 2 -> nullptr
  
      myList.remove(2);
      myList.display(); // Linked List: nullptr
  
      std::cout << "List empty? " << (myList.is_empty() ? "Yes" : "No") << std::endl; // Yes
      return 0;
  }
  */
  

  3. 队列 (Queue)

  队列可以使用 std::deque 或者链表来实现。这里我们用链表实现，更能体现队列的底层结构，head 作为队头，tail 作为队尾。

  #include <iostream>
  #include <stdexcept> // For std::out_of_range
  
  // 队列节点定义 (与链表节点相同)
  struct QNode {
      int data;
      QNode* next;
  
      QNode(int val) : data(val), next(nullptr) {}
  };
  
  // 队列的简要实现
  class Queue {
  private:
      QNode* head; // 队头
      QNode* tail; // 队尾
      size_t current_size;
  
  public:
      // 构造函数
      Queue() : head(nullptr), tail(nullptr), current_size(0) {}
  
      // 析构函数：释放所有节点内存
      ~Queue() {
          QNode* current = head;
          while (current != nullptr) {
              QNode* next_node = current->next;
              delete current;
              current = next_node;
          }
          head = nullptr;
          tail = nullptr;
      }
  
      // 入队
      void enqueue(int item) {
          QNode* new_node = new QNode(item);
          if (is_empty()) {
              head = new_node;
              tail = new_node;
          } else {
              tail->next = new_node;
              tail = new_node;
          }
          current_size++;
      }
  
      // 出队
      int dequeue() {
          if (is_empty()) {
              throw std::out_of_range("Queue is empty, cannot dequeue.");
          }
          int front_item = head->data;
          QNode* temp = head;
          head = head->next;
          if (head == nullptr) { // 如果队列为空了，更新tail
              tail = nullptr;
          }
          delete temp;
          current_size--;
          return front_item;
      }
  
      // 查看队头元素
      int front() const {
          if (is_empty()) {
              throw std::out_of_range("Queue is empty, no front element.");
          }
          return head->data;
      }
  
      // 判断队列是否为空
      bool is_empty() const {
          return head == nullptr; // 或者 current_size == 0;
      }
  
      // 获取队列的大小
      size_t size() const {
          return current_size;
      }
  };
  
  // 示例使用
  /*
  int main() {
      Queue myQueue;
      myQueue.enqueue(100);
      myQueue.enqueue(200);
      std::cout << "Queue front: " << myQueue.front() << std::endl; // 100
      std::cout << "Dequeued: " << myQueue.dequeue() << std::endl;  // 100
      std::cout << "Queue empty? " << (myQueue.is_empty() ? "Yes" : "No") << std::endl; // No
      std::cout << "Dequeued: " << myQueue.dequeue() << std::endl;  // 200
      std::cout << "Queue empty? " << (myQueue.is_empty() ? "Yes" : "No") << std::endl; // Yes
      // myQueue.dequeue(); // This would throw an exception
      return 0;
  }
  */
  

  ---

  代码说明：

  • 头文件: 引入了 iostream 用于输入输出，vector 用于栈的实现，stdexcept 用于抛出异常。
  • 栈: 使用 std::vector 作为底层存储，利用 push_back() 和 pop_back() 实现 push 和 pop 操作，效率高。
  • 链表:
    • 定义了 Node 结构体表示链表中的每个节点。
    • head 指针指向链表的第一个节点。
    • append 在链表末尾添加节点。
    • prepend 在链表头部添加节点。
    • remove 删除指定值的第一个节点。
    • 析构函数 ~LinkedList() 非常重要：它负责遍历链表并释放所有动态分配的 Node 对象的内存，防止内存泄漏。
  • 队列:
    • 同样定义了 QNode 结构体。
    • head 指向队头，tail 指向队尾，方便进行两端操作。
    • enqueue 在队尾添加元素。
    • dequeue 在队头删除元素。
    • 析构函数 ~Queue() 也很重要：同样负责释放所有节点内存。

  注意:

  • 为了简洁，这些实现只处理 int 类型的数据。在实际应用中，可以通过模板（template <typename T>）使其支持任意数据类型。
  • 异常处理是简单的 std::out_of_range。在生产代码中，可能需要更健壮的错误处理。
  • 对于链表和队列，手动管理内存 (使用 new 和 delete) 需要非常小心，确保所有分配的内存都被正确释放，否则会导致内存泄漏。在现代 C++ 中，通常会使用智能指针（如 std::unique_ptr 或 std::shared_ptr）来简化内存管理。