C++实现的数据结构示例，涵盖链表、数组、树和图

利用C++实现的数据结构示例，涵盖链表、数组、树和图的根本操纵：

• 链表（单向链表）
  

1. #include <iostream>
2. using namespace std;
4. struct Node {
5.     int data;
6.     Node* next;
7.     Node(int val) : data(val), next(nullptr) {}
8. };
10. class LinkedList {
11. private:
12.     Node* head;
13. public:
14.     LinkedList() : head(nullptr) {}
16.     void insert(int val) {
17.         Node* newNode = new Node(val);
18.         if (!head) {
19.             head = newNode;
20.             return;
21.         }
22.         Node* temp = head;
23.         while (temp->next) {
24.             temp = temp->next;
25.         }
26.         temp->next = newNode;
27.     }
29.     void remove(int val) {
30.         if (!head) return;
31.         if (head->data == val) {
32.             Node* temp = head;
33.             head = head->next;
34.             delete temp;
35.             return;
36.         }
37.         Node* curr = head;
38.         while (curr->next && curr->next->data != val) {
39.             curr = curr->next;
40.         }
41.         if (curr->next) {
42.             Node* temp = curr->next;
43.             curr->next = curr->next->next;
44.             delete temp;
45.         }
46.     }
48.     void print() {
49.         Node* temp = head;
50.         while (temp) {
51.             cout << temp->data << " ";
52.             temp = temp->next;
53.         }
54.         cout << endl;
55.     }
56. };

复制代码

• 动态数组
  

1. class DynamicArray {
2. private:
3.     int* arr;
4.     int capacity;
5.     int size;
6.    
7.     void resize() {
8.         capacity *= 2;
9.         int* newArr = new int[capacity];
10.         for (int i = 0; i < size; i++) {
11.             newArr[i] = arr[i];
12.         }
13.         delete[] arr;
14.         arr = newArr;
15.     }
17. public:
18.     DynamicArray() : capacity(2), size(0) {
19.         arr = new int[capacity];
20.     }
22.     void push_back(int val) {
23.         if (size == capacity) resize();
24.         arr[size++] = val;
25.     }
27.     void pop_back() {
28.         if (size > 0) size--;
29.     }
31.     int& operator[](int index) {
32.         return arr[index];
33.     }
35.     int getSize() {
36.         return size;
37.     }
38. };

复制代码

• 二叉树（二叉搜索树）
  

1. class TreeNode {
2. public:
3.     int val;
4.     TreeNode* left;
5.     TreeNode* right;
6.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
7. };
9. class BinarySearchTree {
10. private:
11.     TreeNode* root;
13.     TreeNode* insertNode(TreeNode* node, int val) {
14.         if (!node) return new TreeNode(val);
15.         if (val < node->val) {
16.             node->left = insertNode(node->left, val);
17.         } else {
18.             node->right = insertNode(node->right, val);
19.         }
20.         return node;
21.     }
23.     void inorder(TreeNode* node) {
24.         if (!node) return;
25.         inorder(node->left);
26.         cout << node->val << " ";
27.         inorder(node->right);
28.     }
30. public:
31.     BinarySearchTree() : root(nullptr) {}
33.     void insert(int val) {
34.         root = insertNode(root, val);
35.     }
37.     void printInorder() {
38.         inorder(root);
39.         cout << endl;
40.     }
41. };

复制代码

• 图（毗邻矩阵实现）
  

1. #include <vector>
2. class Graph {
3. private:
4.     vector<vector<bool>> adjMatrix;
5.     int numVertices;
7.     void DFSutil(int v, vector<bool>& visited) {
8.         visited[v] = true;
9.         cout << v << " ";
10.         for (int i = 0; i < numVertices; i++) {
11.             if (adjMatrix[v][i] && !visited[i]) {
12.                 DFSutil(i, visited);
13.             }
14.         }
15.     }
17. public:
18.     Graph(int n) : numVertices(n) {
19.         adjMatrix.resize(n, vector<bool>(n, false));
20.     }
22.     void addEdge(int i, int j) {
23.         adjMatrix[i][j] = true;
24.         adjMatrix[j][i] = true;
25.     }
27.     void DFS(int start) {
28.         vector<bool> visited(numVertices, false);
29.         DFSutil(start, visited);
30.         cout << endl;
31.     }
32. };

复制代码

利用示例：

1. int main() {
2.     // 链表测试
3.     LinkedList list;
4.     list.insert(1);
5.     list.insert(2);
6.     list.insert(3);
7.     list.remove(2);
8.     list.print();  // 输出: 1 3
10.     // 动态数组测试
11.     DynamicArray arr;
12.     arr.push_back(10);
13.     arr.push_back(20);
14.     cout << arr[1] << endl;  // 输出: 20
16.     // 二叉搜索树测试
17.     BinarySearchTree bst;
18.     bst.insert(5);
19.     bst.insert(3);
20.     bst.insert(7);
21.     bst.printInorder();  // 输出: 3 5 7
23.     // 图测试
24.     Graph g(4);
25.     g.addEdge(0, 1);
26.     g.addEdge(0, 2);
27.     g.addEdge(1, 3);
28.     g.DFS(0);  // 输出: 0 1 3 2
30.     return 0;
31. }

复制代码

这些实现展示了数据结构的根本操纵：

• 链表的插入、删除和遍历
  
• 动态数组的主动扩容机制
  
• 二叉搜索树的递归插入和中序遍历
  
• 图的毗邻矩阵存储和深度优先搜索
  

每个实现都遵照数据结构的焦点原理，同时保持了代码的简便性和可读性。可以根据具体需求在这些根本实现上添加更多功能或举行优化。