一、数组与链表
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;
}
}
}
}
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/190061.html
微信扫一扫 
支付宝扫一扫 