在C++中，数据结构是用于组织和存储数据的特定方式，以便有效地访问和修改这些数据。不同的数据结构适用于不同的场景，如数组、链表、栈、队列、树、图等。下面我将对其中一些常用的数据结构进行简要的讲解，并提供相关的编程示例。
1. 数组（Array）
数组是一种线性数据结构，用于存储相同类型的数据元素的集合。数组中的元素通过索引进行访问，索引从0开始。
编程示例：
#include <iostream> using namespace std; int main() { int arr[5] = {1, 2, 3, 4, 5}; for (int i = 0; i < 5; i++) { cout << arr[i] << " "; } cout << endl; return 0; }
2. 链表（Linked List）
链表是一种动态数据结构，由一系列节点组成，每个节点包含数据元素和指向下一个节点的指针。与数组不同，链表在内存中的存储不是连续的。
编程示例（单向链表）：
#include <iostream> using namespace std; struct Node { int data; Node* next; }; void printList(Node* head) { Node* temp = head; while (temp != nullptr) { cout << temp->data << " "; temp = temp->next; } cout << endl; } int main() { // 创建链表：1 -> 2 -> 3 Node* head = new Node{1, nullptr}; head->next = new Node{2, nullptr}; head->next->next = new Node{3, nullptr}; printList(head); // 输出：1 2 3 // ... (需要释放内存，这里略去) return 0; }
3. 栈（Stack）
栈是一种后进先出（LIFO）的数据结构，只允许在一端进行插入和删除操作，这一端被称为栈顶。
编程示例（使用数组实现）：
#include <iostream> #include <stack> // 也可以使用STL中的stack using namespace std; const int MAX_SIZE = 100; int stack[MAX_SIZE]; int top = -1; // 栈顶指针初始化为-1 void push(int x) { if (top == MAX_SIZE - 1) { cout << "Stack is full!" << endl; return; } stack[++top] = x; } int pop() { if (top == -1) { cout << "Stack is empty!" << endl; return -1; // 或者抛出一个异常 } return stack[top--]; } int main() { push(1); push(2); push(3); cout << pop() << endl; // 输出：3 cout << pop() << endl; // 输出：2 // ... return 0; }
4. 队列（Queue）
队列是一种先进先出（FIFO）的数据结构，只允许在队尾进行插入操作（入队），在队头进行删除操作（出队）。
编程示例（使用STL中的queue）：
#include <iostream> #include <queue> using namespace std; int main() { queue<int> q; q.push(1); q.push(2); q.push(3); cout << q.front() << endl; // 输出：1（队头元素） q.pop(); // 移除队头元素 cout << q.front() << endl; // 输出：2（新的队头元素） // ... return 0; }
5. 树（Tree）
树是一种非线性的数据结构，由节点和边组成。每个节点可以有一个或多个子节点，但只有一个父节点（根节点除外）。常见的树有二叉树、AVL树、红黑树等。
编程示例（二叉树）：
由于二叉树的实现较为复杂，这里仅展示一个简单的节点定义。
#include <iostream> using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; // ... (二叉树的插入、遍历等操作需要额外实现) int main() { // 创建一个简单的二叉树 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); // ... (需要遍历或操作树) return 0; }
由于篇幅限制，这里仅对每种数据结构进行了简要的讲解和编程示例的展示。在实际应用中，每种数据结构都有其适用的场景和优缺点，需要根据具体需求进行选择和使用。
