数据结构: C++实现常用算法及数据结构

一、数组与链表

1、数组是一组连续的内存空间，可以进行随机访问，其增删操作较为低效。链表是由一系列结点组成，每个结点包含数据和指向下一个结点的指针，其插入删除操作较为高效，但是访问元素时需要遍历整个链表，时间复杂度为O(n)。

2、示例代码：

//定义一个数组
int arr[5] = {1,2,3,4,5};

//定义一个链表结点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

//创建链表
ListNode* head = new ListNode(1);
ListNode* node1 = new ListNode(2);
ListNode* node2 = new ListNode(3);
ListNode* node3 = new ListNode(4);
ListNode* node4 = new ListNode(5);
head->next = node1;
node1->next = node2;
node2->next = node3;
node3->next = node4;

二、栈和队列

1、栈是一种后进先出的数据结构，其存储方式可以使用数组或链表实现。可以使用栈来实现一些逆序输出的问题，如字符串逆置、括号匹配等。队列是一种先进先出的数据结构，其存储方式同样可以使用数组或链表实现。队列可以用来解决广度优先遍历的问题。

2、示例代码：

//定义一个栈
stack stk;
stk.push(1);
stk.push(2);
stk.push(3);
int x = stk.top(); //获取栈顶元素
stk.pop(); //弹出栈顶元素

//定义一个队列
queue q;
q.push(1);
q.push(2);
q.push(3);
int x = q.front(); //获取队首元素
q.pop(); //弹出队首元素

三、哈希表

哈希表是一种根据键(key)直接访问内存地址的数据结构，其查找、插入、删除操作的平均时间复杂度为O(1)。哈希函数是实现哈希表的关键，决定了如何将键转化为内存地址。哈希函数需要满足以下两个条件：（1）散列均匀；（2）尽量避免哈希冲突。常用的哈希函数包括取模法、乘法哈希等。

2、示例代码：

//定义一个哈希表
unordered_map mp;
mp["apple"] = 10;
mp["orange"] = 3;

//查找元素
if (mp.find("apple") != mp.end()) {
    int x = mp["apple"];
}

//遍历哈希表
for (auto& it : mp) {
    cout << it.first << ":" << it.second << endl;
}

四、堆

堆是一种动态的数据结构，它分为最大堆和最小堆。其中最大堆要求父结点的值大于或等于子结点的值，最小堆要求父结点的值小于或等于子结点的值。堆可以用于解决一些查找最大/小值的问题，如Top K 问题、求中位数等。

2、示例代码：

//定义一个最小堆
priority_queue<int, vector, greater> pq;
pq.push(3);
pq.push(1);
pq.push(4);
int x = pq.top(); //获取堆顶元素
pq.pop(); //弹出堆顶元素

五、图

图由结点和边组成，其中结点可以包含任意信息，边可以包含权值等信息。图的遍历方式有深度优先遍历和广度优先遍历。深度优先遍历可以使用递归或栈来实现，广度优先遍历可以使用队列来实现。图的常见算法包括最短路径算法、最小生成树算法、网络流算法等。

2、示例代码：

//定义一个图（使用邻接表表示）
vector<vector> graph(n);
graph[0].push_back(1);
graph[0].push_back(2);
graph[1].push_back(3);
graph[2].push_back(3);

//DFS遍历
vector visited(n); //标记是否访问过
void DFS(int node) {
    visited[node] = true;
    //访问当前结点
    for (int i = 0; i < graph[node].size(); i++) {
        int next_node = graph[node][i];
        if (!visited[next_node]) {
            DFS(next_node);
        }
    }
}

//BFS遍历
queue q;
vector visited(n); //标记是否访问过
void BFS(int start) {
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        //访问当前结点
        for (int i = 0; i < graph[node].size(); i++) {
            int next_node = graph[node][i];
            if (!visited[next_node]) {
                q.push(next_node);
                visited[next_node] = true;
            }
        }
    }
}