五、数据结构

5.1 线性数据结构

1. 数组和链表的区别？

   • 数组（Array）：

     • 存储方式：连续的内存空间；
     • 访问方式：支持随机访问，通过索引直接访问元素，时间复杂度为O(1)；
     • 插入/删除：在中间位置插入或删除元素时，需要移动其他元素，时间复杂度为O(n)；
     • 空间利用率：内存利用率高，不需要额外的指针开销；
     • 适用场景：需要频繁随机访问元素的场景。

   • 链表（Linked List）：

     • 存储方式：不连续的内存空间，每个节点包含数据和指向下一个（或前一个）节点的指针；
     • 访问方式：不支持随机访问，只能从头开始遍历，时间复杂度为O(n)；
     • 插入/删除：在任意位置插入或删除元素时，只需要修改指针，时间复杂度为O(1)；
     • 空间利用率：内存利用率较低，每个节点需要额外的指针开销；
     • 适用场景：需要频繁在任意位置插入或删除元素的场景。

     // 数组示例
     void test_array() {int arr[5] = {1, 2, 3, 4, 5};  // 静态数组std::vector<int> vec = {1, 2, 3, 4, 5};  // 动态数组// 随机访问，O(1)时间复杂度std::cout << arr[2] << std::endl;  // 输出3std::cout << vec[3] << std::endl;  // 输出4// 插入元素，需要移动后面的元素，O(n)时间复杂度vec.insert(vec.begin() + 2, 10);  // 在索引2处插入10
     }// 链表示例（自定义简单链表）
     struct Node {int data;Node* next;Node(int val) : data(val), next(nullptr) {}
     };void test_linked_list() {// 创建链表：1 -> 2 -> 3Node* head = new Node(1);head->next = new Node(2);head->next->next = new Node(3);// 访问元素，需要遍历，O(n)时间复杂度Node* current = head;while (current) {std::cout << current->data << " ";  // 输出1 2 3current = current->next;}// 在中间插入元素，O(1)时间复杂度（假设已经找到插入位置）Node* new_node = new Node(10);new_node->next = head->next;  // 10的next指向2head->next = new_node;        // 1的next指向10，现在链表变为1->10->2->3// 释放内存current = head;while (current) {Node* temp = current;current = current->next;delete temp;}
     }
     

2. 栈和队列的区别？它们的应用场景有哪些？

   • 栈（Stack）：

     • 特点：后进先出（LIFO, Last In First Out），只能在一端（栈顶）进行插入和删除操作；
     • 基本操作：push（入栈）、pop（出栈）、top（查看栈顶元素）、empty（判断是否为空）；
     • 实现方式：可以用数组或链表实现；
     • 应用场景：函数调用、表达式求值、括号匹配、深度优先搜索（DFS）等。

   • 队列（Queue）：

     • 特点：先进先出（FIFO, First In First Out），只能在一端（队尾）插入，另一端（队头）删除；
     • 基本操作：enqueue（入队）、dequeue（出队）、front（查看队头元素）、empty（判断是否为空）；
     • 实现方式：可以用数组或链表实现；
     • 应用场景：任务调度、缓冲处理、广度优先搜索（BFS）等。

     // 栈示例
     void test_stack() {std::stack<int> st;// 入栈st.push(1);st.push(2);st.push(3);// 访问栈顶元素std::cout << "Top: " << st.top() << std::endl;  // 输出3// 出栈st.pop();std::cout << "After pop, top: " << st.top() << std::endl;  // 输出2// 判断是否为空while (!st.empty()) {std::cout << st.top() << " ";  // 输出2 1st.pop();}
     }// 队列示例
     void test_queue() {std::queue<int> q;// 入队q.push(1);q.push(2);q.push(3);// 访问队头元素std::cout << "Front: " << q.front() << std::endl;  // 输出1// 出队q.pop();std::cout << "After pop, front: " << q.front() << std::endl;  // 输出2// 判断是否为空while (!q.empty()) {std::cout << q.front() << " ";  // 输出2 3q.pop();}
     }// 栈的应用：括号匹配
     bool is_valid_parentheses(const std::string& s) {std::stack<char> st;for (char c : s) {// 左括号入栈if (c == '(' || c == '[' || c == '{') {st.push(c);} else {// 右括号，检查是否匹配if (st.empty()) return false;char top = st.top();st.pop();if ((c == ')' && top != '(') ||(c == ']' && top != '[') ||(c == '}' && top != '{')) {return false;}}}return st.empty();  // 所有括号都应匹配
     }// 队列的应用：简单的任务调度
     void task_scheduler() {std::queue<std::string> tasks;// 添加任务tasks.push("Task 1");tasks.push("Task 2");tasks.push("Task 3");// 处理任务（先进先出）while (!tasks.empty()) {std::string current = tasks.front();tasks.pop();std::cout << "Processing " << current << std::endl;}
     }
     

3. 什么是双端队列（Deque）？它与普通队列的区别？

   • 双端队列（Double-Ended Queue，Deque）：

     • 是一种允许在两端（队首和队尾）进行插入和删除操作的数据结构；
     • 结合了栈和队列的特点，可以在两端高效地进行操作；
     • 在STL中，deque通常实现为分段连续的内存块，通过中央控制结构（如指针数组）管理这些内存块；
     • 基本操作：push_front（队首入队）、push_back（队尾入队）、pop_front（队首出队）、pop_back（队尾出队）、front（查看队首元素）、back（查看队尾元素）、empty（判断是否为空）。

   • 与普通队列的区别：

     • 操作灵活性：普通队列只允许在队尾插入、队首删除；而双端队列允许在两端进行插入和删除；
     • 实现方式：普通队列通常基于链表或循环数组实现；双端队列通常基于分段连续内存实现；
     • 应用场景：双端队列适用于需要在两端频繁操作的场景，如滑动窗口算法、双端栈等。

     // 双端队列示例
     void test_deque() {std::deque<int> dq;// 队尾入队dq.push_back(1);dq.push_back(2);// 队首入队dq.push_front(0);// 遍历双端队列std::cout << "Deque elements: ";for (int val : dq) {std::cout << val << " ";  // 输出0 1 2}std::cout << std::endl;// 访问队首和队尾元素std::cout << "Front: " << dq.front() << std::endl;  // 输出0std::cout << "Back: " << dq.back() << std::endl;    // 输出2// 队首出队dq.pop_front();std::cout << "After pop_front, front: " << dq.front() << std::endl;  // 输出1// 队尾出队dq.pop_back();std::cout << "After pop_back, back: " << dq.back() << std::endl;    // 输出1
     }// 双端队列的应用：滑动窗口最大值
     std::vector<int> max_sliding_window(const std::vector<int>& nums, int k) {std::vector<int> result;std::deque<int> dq;  // 存储索引，保持队首为当前窗口最大值的索引for (int i = 0; i < nums.size(); ++i) {// 移除超出窗口范围的元素（队首）if (!dq.empty() && dq.front() == i - k) {dq.pop_front();}// 移除所有小于当前元素的值（队尾），保持队列单调递减while (!dq.empty() && nums[dq.back()] < nums[i]) {dq.pop_back();}// 添加当前元素的索引dq.push_back(i);// 当窗口形成时，记录最大值（队首元素）if (i >= k - 1) {result.push_back(nums[dq.front()]);}}return result;
     }
     

5.2 非线性数据结构

1. 树的基本概念？二叉树有哪些遍历方式？

   • 树的基本概念：

     • 树是一种非线性的层次结构，由节点组成，没有环路；
     • 根节点：没有父节点的节点；
     • 叶子节点：没有子节点的节点；
     • 父节点/子节点：一个节点的直接前驱/后继节点；
     • 兄弟节点：具有相同父节点的节点；
     • 深度：从根节点到当前节点的路径长度；
     • 高度：从当前节点到最远叶子节点的路径长度；
     • 子树：以某节点为根的子结构。

   • 二叉树（Binary Tree）：每个节点最多有两个子节点（左子节点和右子节点）。

   • 二叉树的遍历方式：

     • 前序遍历（Pre-order Traversal）：根->左->右；
     • 中序遍历（In-order Traversal）：左->根->右；
     • 后序遍历（Post-order Traversal）：左->右->根；
     • 层序遍历（Level-order Traversal）：按层从左到右遍历。

     // 二叉树节点定义
     struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     };// 前序遍历（递归实现）
     void preorder_traversal(TreeNode* root) {if (root == nullptr) return;std::cout << root->val << " ";  // 根preorder_traversal(root->left);  // 左preorder_traversal(root->right); // 右
     }// 中序遍历（递归实现）
     void inorder_traversal(TreeNode* root) {if (root == nullptr) return;inorder_traversal(root->left);   // 左std::cout << root->val << " ";  // 根inorder_traversal(root->right);  // 右
     }// 后序遍历（递归实现）
     void postorder_traversal(TreeNode* root) {if (root == nullptr) return;postorder_traversal(root->left);  // 左postorder_traversal(root->right); // 右std::cout << root->val << " ";   // 根
     }// 层序遍历（非递归实现，使用队列）
     void level_order_traversal(TreeNode* root) {if (root == nullptr) return;std::queue<TreeNode*> q;q.push(root);while (!q.empty()) {int level_size = q.size();// 处理当前层的所有节点for (int i = 0; i < level_size; ++i) {TreeNode* current = q.front();q.pop();std::cout << current->val << " ";// 将子节点入队if (current->left) q.push(current->left);if (current->right) q.push(current->right);}std::cout << std::endl;  // 一层结束，换行}
     }// 测试用例：创建一个二叉树
     //      1
     //     / \
     //    2   3
     //   / \   \
     //  4   5   6
     void test_tree_traversal() {TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);root->right->right = new TreeNode(6);std::cout << "Pre-order traversal: ";preorder_traversal(root);  // 输出：1 2 4 5 3 6std::cout << std::endl;std::cout << "In-order traversal: ";inorder_traversal(root);   // 输出：4 2 5 1 3 6std::cout << std::endl;std::cout << "Post-order traversal: ";postorder_traversal(root); // 输出：4 5 2 6 3 1std::cout << std::endl;std::cout << "Level-order traversal: " << std::endl;level_order_traversal(root);  // 按层输出：1//           2 3//           4 5 6// 释放内存（实际应用中应使用智能指针或递归释放）// 这里简化处理
     }
     

2. 什么是二叉搜索树（BST）？它有什么特点？

   • 二叉搜索树（Binary Search Tree，BST）：

     • 是一种特殊的二叉树，具有以下性质：
       • 左子树上所有节点的值均小于根节点的值；
       • 右子树上所有节点的值均大于根节点的值；
       • 左子树和右子树也分别是二叉搜索树（递归定义）；
       • （可选）不允许有重复的值（某些实现允许重复值）。
     • 特点：
       • 排序特性：中序遍历BST可以得到一个有序的序列；
       • 查找效率：在平衡的BST中，查找、插入、删除的时间复杂度均为O(log n)；
       • 不平衡风险：如果插入的是有序数据，BST可能退化为链表，时间复杂度变为O(n)。
     • 常见操作：查找、插入、删除、求最大值/最小值、求前驱/后继等。

     // 二叉搜索树的实现（简化版）
     class BST {
     private:TreeNode* root;// 递归插入TreeNode* insert_recursive(TreeNode* node, int val) {if (node == nullptr) {return new TreeNode(val);}if (val < node->val) {node->left = insert_recursive(node->left, val);} else if (val > node->val) {node->right = insert_recursive(node->right, val);} // 如果val已存在，可以选择不插入或插入到右子树return node;}// 递归查找TreeNode* search_recursive(TreeNode* node, int val) {if (node == nullptr || node->val == val) {return node;}if (val < node->val) {return search_recursive(node->left, val);} else {return search_recursive(node->right, val);}}// 找到最小值节点TreeNode* find_min(TreeNode* node) {while (node->left != nullptr) {node = node->left;}return node;}// 递归删除TreeNode* delete_recursive(TreeNode* node, int val) {if (node == nullptr) return nullptr;if (val < node->val) {node->left = delete_recursive(node->left, val);} else if (val > node->val) {node->right = delete_recursive(node->right, val);} else {// 节点有0或1个子节点if (node->left == nullptr) {TreeNode* temp = node->right;delete node;return temp;} else if (node->right == nullptr) {TreeNode* temp = node->left;delete node;return temp;}// 节点有2个子节点，找到右子树中的最小值节点（后继）TreeNode* successor = find_min(node->right);node->val = successor->val;  // 替换值node->right = delete_recursive(node->right, successor->val);  // 删除后继节点}return node;}// 递归释放内存void destroy_tree(TreeNode* node) {if (node) {destroy_tree(node->left);destroy_tree(node->right);delete node;}}// 递归中序遍历void inorder_recursive(TreeNode* node) {if (node) {inorder_recursive(node->left);std::cout << node->val << " ";inorder_recursive(node->right);}}public:BST() : root(nullptr) {}~BST() {destroy_tree(root);}void insert(int val) {root = insert_recursive(root, val);}bool search(int val) {return search_recursive(root, val) != nullptr;}void remove(int val) {root = delete_recursive(root, val);}void inorder_traversal() {inorder_recursive(root);std::cout << std::endl;}
     };void test_bst() {BST bst;// 插入元素bst.insert(50);bst.insert(30);bst.insert(70);bst.insert(20);bst.insert(40);bst.insert(60);bst.insert(80);// 中序遍历（应输出有序序列）std::cout << "In-order traversal: ";bst.inorder_traversal();  // 输出：20 30 40 50 60 70 80// 查找元素std::cout << "Search 40: " << (bst.search(40) ? "Found" : "Not found") << std::endl;  // Foundstd::cout << "Search 45: " << (bst.search(45) ? "Found" : "Not found") << std::endl;  // Not found// 删除元素bst.remove(20);  // 删除叶子节点std::cout << "After removing 20: ";bst.inorder_traversal();  // 输出：30 40 50 60 70 80bst.remove(30);  // 删除有一个子节点的节点std::cout << "After removing 30: ";bst.inorder_traversal();  // 输出：40 50 60 70 80bst.remove(50);  // 删除有两个子节点的节点std::cout << "After removing 50: ";bst.inorder_traversal();  // 输出：40 60 70 80
     }
     

3. 什么是平衡二叉树？常见的平衡二叉树有哪些？

   • 平衡二叉树（Balanced Binary Tree）：

     • 是一种特殊的二叉搜索树，通过一定的机制保证树的高度平衡，从而保证基本操作（查找、插入、删除）的时间复杂度为O(log n)；
     • 平衡条件：任意节点的左右子树高度差不超过某个常数（通常为1）。

   • 常见的平衡二叉树：

     • AVL树（Adelson-Velsky and Landis Tree）：
       • 左右子树高度差不超过1；
       • 通过旋转操作（左旋、右旋、左右旋、右左旋）来保持平衡；
       • 适用于查找频繁、插入删除相对较少的场景。
     • 红黑树（Red-Black Tree）：
       • 是一种自平衡的二叉搜索树，每个节点要么是红色，要么是黑色；
       • 通过颜色规则和旋转操作来保持平衡；
       • 相比AVL树，红黑树在插入删除时的旋转操作更少，因此在频繁修改的场景下性能更好；
       • STL中的map、set、multimap、multiset等关联容器底层就是基于红黑树实现的。
     • B树（B-Tree）和B+树（B+Tree）：
       • 是多路平衡查找树，每个节点可以有多个子节点；
       • B树的所有节点都存储数据；B+树只有叶子节点存储数据，非叶子节点仅用于索引；
       • 广泛应用于文件系统和数据库索引。
     • Splay树（伸展树）：
       • 通过频繁访问的节点向上移动（伸展）来保持树的平衡；
       • 不严格保证树的高度平衡，但在实际应用中表现良好。

     // 红黑树的特性（在STL中的应用）
     void test_rb_tree_in_stl() {// std::map底层基于红黑树实现std::map<int, std::string> my_map;// 插入元素（自动排序，保持平衡）my_map[3] = "three";my_map[1] = "one";my_map[4] = "four";my_map[2] = "two";my_map[5] = "five";// 遍历（按键排序）std::cout << "Map elements (ordered):" << std::endl;for (const auto& pair : my_map) {std::cout << pair.first << ": " << pair.second << std::endl;}// 输出顺序：1: one, 2: two, 3: three, 4: four, 5: five// std::set底层也基于红黑树实现std::set<int> my_set = {5, 2, 8, 1, 3};// 遍历（有序）std::cout << "Set elements (ordered):" << std::endl;for (int val : my_set) {std::cout << val << " ";  // 输出：1 2 3 5 8}std::cout << std::endl;
     }
     

4. 什么是哈希表？如何处理哈希冲突？

   • 哈希表（Hash Table）：

     • 是一种根据键（key）直接访问值（value）的数据结构；
     • 通过哈希函数将键映射到表中的一个位置，从而实现快速查找；
     • 理想情况下，查找、插入、删除的时间复杂度为O(1)。

   • 哈希函数（Hash Function）：

     • 用于将键转换为表索引的函数；
     • 好的哈希函数应具有：计算简单、分布均匀（减少冲突）、不可逆性等特性。

   • 哈希冲突（Hash Collision）：

     • 不同的键通过哈希函数计算后得到相同的表索引；
     • 任何哈希表都无法完全避免哈希冲突。

   • 处理哈希冲突的方法：

     • 链地址法（Separate Chaining）：
       • 每个哈希表位置维护一个链表，存储哈希到该位置的所有键值对；
       • 查找时，先通过哈希函数找到对应链表，然后在链表中线性查找；
       • 优点：实现简单，处理冲突灵活；
       • 缺点：需要额外的内存空间存储链表指针。
     • 开放地址法（Open Addressing）：
       • 当发生冲突时，寻找表中的其他空闲位置存储键值对；
       • 常见的探测方法：线性探测（Linear Probing）、二次探测（Quadratic Probing）、双重哈希（Double Hashing）；
       • 优点：不需要额外的指针空间；
       • 缺点：容易出现聚类问题，删除操作复杂。
     • 再哈希法（Rehashing）：
       • 当哈希表负载因子（键值对数量/表大小）超过阈值时，重新分配更大的内存空间，并重新计算所有键的哈希值；
       • 常用于动态调整哈希表大小，保证性能。
     • 建立公共溢出区：
       • 建立一个公共的溢出表，将所有冲突的键值对都存储在溢出表中；
       • 查找时，先在主表中查找，若找不到则到溢出表中查找。

     // 简单的哈希表实现（使用链地址法处理冲突）
     template <typename K, typename V>
     class HashTable {
     private:struct Node {K key;V value;Node* next;Node(const K& k, const V& v) : key(k), value(v), next(nullptr) {}};std::vector<Node*> table;  // 哈希表数组size_t capacity;           // 表容量size_t size;               // 当前元素数量// 简单的哈希函数size_t hash(const K& key) const {// 这里使用std::hash，实际应用中可能需要更复杂的哈希函数return std::hash<K>()(key) % capacity;}// 扩容（再哈希）void rehash() {std::vector<Node*> old_table = table;// 创建新的更大的表capacity *= 2;table.assign(capacity, nullptr);size = 0;// 重新插入所有元素for (Node* head : old_table) {while (head) {Node* temp = head;insert(head->key, head->value);  // 重新插入head = head->next;delete temp;}}}public:HashTable(size_t initial_capacity = 16) : capacity(initial_capacity), size(0) {table.resize(capacity, nullptr);}~HashTable() {// 释放所有内存for (Node* head : table) {while (head) {Node* temp = head;head = head->next;delete temp;}}}void insert(const K& key, const V& value) {// 检查是否需要扩容（负载因子阈值设为0.75）if (size >= capacity * 0.75) {rehash();}size_t index = hash(key);// 检查key是否已存在Node* current = table[index];while (current) {if (current->key == key) {current->value = value;  // 更新已存在的键的值return;}current = current->next;}// 插入新节点（头插法）Node* new_node = new Node(key, value);new_node->next = table[index];table[index] = new_node;size++;}bool find(const K& key, V& value) const {size_t index = hash(key);Node* current = table[index];while (current) {if (current->key == key) {value = current->value;return true;}current = current->next;}return false;  // 未找到}bool remove(const K& key) {size_t index = hash(key);Node* current = table[index];Node* prev = nullptr;while (current) {if (current->key == key) {if (prev) {prev->next = current->next;} else {table[index] = current->next;}delete current;size--;return true;}prev = current;current = current->next;}return false;  // 未找到要删除的键}size_t get_size() const {return size;}
     };void test_hash_table() {HashTable<std::string, int> ht;// 插入元素ht.insert("apple", 5);ht.insert("banana", 7);ht.insert("orange", 3);ht.insert("grape", 10);// 查找元素int value;if (ht.find("banana", value)) {std::cout << "banana: " << value << std::endl;  // 输出：banana: 7}// 测试哈希冲突（假设两个键哈希到同一个索引）// 这里为了演示，我们使用两个可能产生冲突的键ht.insert("test1", 100);ht.insert("test2", 200);  // 假设与test1冲突if (ht.find("test1", value)) {std::cout << "test1: " << value << std::endl;  // 应该能找到test1}if (ht.find("test2", value)) {std::cout << "test2: " << value << std::endl;  // 应该能找到test2}// 删除元素ht.remove("orange");if (!ht.find("orange", value)) {std::cout << "orange has been removed." << std::endl;}// 检查大小std::cout << "Hash table size: " << ht.get_size() << std::endl;  // 输出：4
     }
     

5. 图的基本概念？图的存储方式有哪些？

   • 图的基本概念：

     • 图是由顶点（Vertex）和边（Edge）组成的一种数据结构；
     • 有向图：边有方向，从一个顶点指向另一个顶点；
     • 无向图：边没有方向，连接的两个顶点是相互可达的；
     • 顶点的度：与该顶点相连的边的数量（有向图分为入度和出度）；
     • 路径：从一个顶点到另一个顶点的边的序列；
     • 环：起点和终点相同的路径。

   • 图的存储方式：

     • 邻接矩阵（Adjacency Matrix）：
       • 使用二维数组表示图，matrix[i][j]表示顶点i到顶点j是否有边；
       • 优点：判断两个顶点是否相邻的时间复杂度为O(1)，适合稠密图；
       • 缺点：空间复杂度为O(n²)，不适合稀疏图。
     • 邻接表（Adjacency List）：
       • 每个顶点对应一个链表，链表中存储该顶点的所有邻接顶点；
       • 优点：空间复杂度为O(n + m)（n为顶点数，m为边数），适合稀疏图；
       • 缺点：判断两个顶点是否相邻的时间复杂度为O(d)（d为顶点的度）。
     • 十字链表（Orthogonal List）：
       • 有向图的一种存储方式，每条边用一个节点表示，同时存储入边和出边信息；
       • 适合处理有向图的复杂操作。
     • 邻接多重表（Adjacency Multilist）：
       • 无向图的一种存储方式，每条边用一个节点表示，避免重复存储；
       • 适合处理无向图的边操作。

     // 图的表示方法示例// 邻接矩阵表示
     class GraphMatrix {
     private:int** matrix;  // 邻接矩阵int num_vertices;  // 顶点数bool directed;  // 是否为有向图public:GraphMatrix(int n, bool is_directed = true) : num_vertices(n), directed(is_directed) {// 初始化邻接矩阵matrix = new int*[num_vertices];for (int i = 0; i < num_vertices; ++i) {matrix[i] = new int[num_vertices]();  // 初始化为0}}~GraphMatrix() {// 释放内存for (int i = 0; i < num_vertices; ++i) {delete[] matrix[i];}delete[] matrix;}void add_edge(int from, int to, int weight = 1) {if (from >= 0 && from < num_vertices && to >= 0 && to < num_vertices) {matrix[from][to] = weight;  // 添加边if (!directed) {matrix[to][from] = weight;  // 无向图需要添加反向边}}}void remove_edge(int from, int to) {if (from >= 0 && from < num_vertices && to >= 0 && to < num_vertices) {matrix[from][to] = 0;  // 移除边if (!directed) {matrix[to][from] = 0;  // 无向图需要移除反向边}}}bool has_edge(int from, int to) const {if (from >= 0 && from < num_vertices && to >= 0 && to < num_vertices) {return matrix[from][to] != 0;}return false;}void print() const {for (int i = 0; i < num_vertices; ++i) {for (int j = 0; j < num_vertices; ++j) {std::cout << matrix[i][j] << " ";}std::cout << std::endl;}}
     };// 邻接表表示
     class GraphList {
     private:std::vector<std::vector<std::pair<int, int>>> adj_list;  // 邻接表，存储邻接顶点和权重int num_vertices;  // 顶点数bool directed;  // 是否为有向图public:GraphList(int n, bool is_directed = true) : num_vertices(n), directed(is_directed) {adj_list.resize(num_vertices);}void add_edge(int from, int to, int weight = 1) {if (from >= 0 && from < num_vertices && to >= 0 && to < num_vertices) {adj_list[from].emplace_back(to, weight);  // 添加边if (!directed) {adj_list[to].emplace_back(from, weight);  // 无向图需要添加反向边}}}void remove_edge(int from, int to) {if (from >= 0 && from < num_vertices && to >= 0 && to < num_vertices) {// 移除from到to的边auto& list = adj_list[from];list.erase(std::remove_if(list.begin(), list.end(),[to](const std::pair<int, int>& p) { return p.first == to; }),list.end());if (!directed) {// 移除to到from的边auto& reverse_list = adj_list[to];reverse_list.erase(std::remove_if(reverse_list.begin(), reverse_list.end(),[from](const std::pair<int, int>& p) { return p.first == from; }),reverse_list.end());}}}bool has_edge(int from, int to) const {if (from >= 0 && from < num_vertices && to >= 0 && to < num_vertices) {const auto& list = adj_list[from];return std::any_of(list.begin(), list.end(),[to](const std::pair<int, int>& p) { return p.first == to; });}return false;}void print() const {for (int i = 0; i < num_vertices; ++i) {std::cout << "Vertex " << i << ": ";for (const auto& edge : adj_list[i]) {std::cout << "(" << edge.first << ", " << edge.second << ") ";}std::cout << std::endl;}}
     };void test_graph_representations() {// 测试邻接矩阵std::cout << "Testing GraphMatrix (directed):" << std::endl;GraphMatrix gm(5, true);  // 有向图，5个顶点gm.add_edge(0, 1);gm.add_edge(0, 2);gm.add_edge(1, 3);gm.add_edge(2, 3);gm.add_edge(3, 4);gm.print();std::cout << "Has edge 0->2: " << (gm.has_edge(0, 2) ? "Yes" : "No") << std::endl;// 测试邻接表std::cout << "\nTesting GraphList (undirected):" << std::endl;GraphList gl(5, false);  // 无向图，5个顶点gl.add_edge(0, 1, 2);gl.add_edge(0, 2, 3);gl.add_edge(1, 3, 4);gl.add_edge(2, 3, 1);gl.add_edge(3, 4, 5);gl.print();std::cout << "Has edge 2->0: " << (gl.has_edge(2, 0) ? "Yes" : "No") << std::endl;// 测试删除边gl.remove_edge(1, 3);std::cout << "After removing edge 1-3:\n";gl.print();
     }