使用C++实现的数据结构示例，涵盖链表、数组、树和图的基本操作：
- 链表（单向链表）
#include <iostream>
using namespace std;struct Node {int data;Node* next;Node(int val) : data(val), next(nullptr) {}
};class LinkedList {
private:Node* head;
public:LinkedList() : head(nullptr) {}void insert(int val) {Node* newNode = new Node(val);if (!head) {head = newNode;return;}Node* temp = head;while (temp->next) {temp = temp->next;}temp->next = newNode;}void remove(int val) {if (!head) return;if (head->data == val) {Node* temp = head;head = head->next;delete temp;return;}Node* curr = head;while (curr->next && curr->next->data != val) {curr = curr->next;}if (curr->next) {Node* temp = curr->next;curr->next = curr->next->next;delete temp;}}void print() {Node* temp = head;while (temp) {cout << temp->data << " ";temp = temp->next;}cout << endl;}
};
- 动态数组
class DynamicArray {
private:int* arr;int capacity;int size;void resize() {capacity *= 2;int* newArr = new int[capacity];for (int i = 0; i < size; i++) {newArr[i] = arr[i];}delete[] arr;arr = newArr;}public:DynamicArray() : capacity(2), size(0) {arr = new int[capacity];}void push_back(int val) {if (size == capacity) resize();arr[size++] = val;}void pop_back() {if (size > 0) size--;}int& operator[](int index) {return arr[index];}int getSize() {return size;}
};
- 二叉树（二叉搜索树）
class TreeNode {
public:int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};class BinarySearchTree {
private:TreeNode* root;TreeNode* insertNode(TreeNode* node, int val) {if (!node) return new TreeNode(val);if (val < node->val) {node->left = insertNode(node->left, val);} else {node->right = insertNode(node->right, val);}return node;}void inorder(TreeNode* node) {if (!node) return;inorder(node->left);cout << node->val << " ";inorder(node->right);}public:BinarySearchTree() : root(nullptr) {}void insert(int val) {root = insertNode(root, val);}void printInorder() {inorder(root);cout << endl;}
};
- 图（邻接矩阵实现）
#include <vector>
class Graph {
private:vector<vector<bool>> adjMatrix;int numVertices;void DFSutil(int v, vector<bool>& visited) {visited[v] = true;cout << v << " ";for (int i = 0; i < numVertices; i++) {if (adjMatrix[v][i] && !visited[i]) {DFSutil(i, visited);}}}public:Graph(int n) : numVertices(n) {adjMatrix.resize(n, vector<bool>(n, false));}void addEdge(int i, int j) {adjMatrix[i][j] = true;adjMatrix[j][i] = true;}void DFS(int start) {vector<bool> visited(numVertices, false);DFSutil(start, visited);cout << endl;}
};
使用示例：
int main() {// 链表测试LinkedList list;list.insert(1);list.insert(2);list.insert(3);list.remove(2);list.print(); // 输出: 1 3// 动态数组测试DynamicArray arr;arr.push_back(10);arr.push_back(20);cout << arr[1] << endl; // 输出: 20// 二叉搜索树测试BinarySearchTree bst;bst.insert(5);bst.insert(3);bst.insert(7);bst.printInorder(); // 输出: 3 5 7// 图测试Graph g(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 3);g.DFS(0); // 输出: 0 1 3 2return 0;
}
这些实现展示了数据结构的基本操作：
- 链表的插入、删除和遍历
- 动态数组的自动扩容机制
- 二叉搜索树的递归插入和中序遍历
- 图的邻接矩阵存储和深度优先搜索
每个实现都遵循数据结构的核心原理，同时保持了代码的简洁性和可读性。可以根据具体需求在这些基础实现上添加更多功能或进行优化。
