01-数组

数组概述

数组是最基础的数据结构，用于存储相同类型的元素序列。

一维数组

int a[100];
int b[100] = {0};

// 遍历数组
for(int i = 0; i < n; i++) {
    cin >> a[i];
}

二维数组

int a[100][100];

// 遍历二维数组
for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
        cin >> a[i][j];
    }
}

数组常用操作

查找：O(1)（通过下标访问）
插入：O(n)（需要移动元素）
删除：O(n)（需要移动元素）

02-链表

链表概述

链表是一种线性数据结构，元素通过指针连接，不需要连续的内存空间。

单链表

struct Node {
    int data;
    Node* next;
};

// 创建节点
Node* head = new Node();
head->data = 1;
head->next = nullptr;

链表常用操作

查找：O(n)
插入：O(1)（已知位置）
删除：O(1)（已知位置）

双向链表

每个节点有前驱和后继指针，可以双向遍历。

03-栈和队列

栈（Stack）

栈是一种后进先出（LIFO）的数据结构。

#include <stack>
stack<int> s;

s.push(1);   // 入栈
s.push(2);
s.pop();     // 出栈
s.top();     // 获取栈顶元素
s.empty();   // 判断是否为空
s.size();    // 获取栈大小

队列（Queue）

队列是一种先进先出（FIFO）的数据结构。

#include <queue>
queue<int> q;

q.push(1);   // 入队
q.push(2);
q.pop();     // 出队
q.front();   // 获取队首元素
q.back();    // 获取队尾元素

双端队列（Deque）

可以在两端进行插入和删除操作。

04-哈希表

哈希表概述

哈希表通过哈希函数将键映射到存储位置，实现O(1)的查找效率。

STL中的哈希表

#include <unordered_map>
unordered_map<string, int> mp;

mp["apple"] = 5;
mp["banana"] = 3;

cout << mp["apple"];  // 输出5
mp.find("apple");     // 查找
mp.erase("apple");    // 删除

哈希冲突

当不同的键映射到相同的位置时，需要处理冲突。常见方法：链地址法、开放寻址法。

05-二叉树

二叉树概述

每个节点最多有两个子节点（左子树和右子树）。

二叉树遍历

前序遍历：根 -> 左 -> 右
中序遍历：左 -> 根 -> 右
后序遍历：左 -> 右 -> 根
层序遍历：按层次从上到下遍历

// 递归前序遍历
void preorder(TreeNode* root) {
    if(root == nullptr) return;
    cout << root->val;
    preorder(root->left);
    preorder(root->right);
}

二叉搜索树

左子树所有节点的值小于根节点，右子树所有节点的值大于根节点。

06-图

图的表示方法

邻接矩阵：二维数组表示
邻接表：链表或vector表示

// 邻接表
vector<int> adj[1000];
adj[1].push_back(2);
adj[1].push_back(3);

// 遍历邻接表
for(int i = 0; i < adj[u].size(); i++) {
    int v = adj[u][i];
}

图的遍历

深度优先搜索（DFS）
广度优先搜索（BFS）

STL(标准模板库)

容器分类

序列容器：vector, deque, list, array
关联容器：set, map, multiset, multimap
无序关联容器：unordered_set, unordered_map
适配器：stack, queue, priority_queue

vector

#include <vector>
vector<int> v;

v.push_back(1);
v.pop_back();
v.size();
v.empty();
v[0];        // 访问元素

set

#include <set>
set<int> s;

s.insert(1);
s.erase(1);
s.find(1);   // 返回迭代器

map

#include <map>
map<string, int> m;

m["key"] = 100;
cout << m["key"];