一、数组与链表
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、示例代码:
//定义一个栈 stackstk; 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_mapmp; 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, greater > pq; pq.push(3); pq.push(1); pq.push(4); int x = pq.top(); //获取堆顶元素 pq.pop(); //弹出堆顶元素
五、图
图由结点和边组成,其中结点可以包含任意信息,边可以包含权值等信息。图的遍历方式有深度优先遍历和广度优先遍历。深度优先遍历可以使用递归或栈来实现,广度优先遍历可以使用队列来实现。图的常见算法包括最短路径算法、最小生成树算法、网络流算法等。
2、示例代码:
//定义一个图(使用邻接表表示) 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; } } } }