东莞seo网站管理,百度广州分公司是外包吗,加强网络平台建设,巴楚网站建设1. 线性数据结构
#xff08;1#xff09;数组#xff08;Array#xff09;#xff08;适合静态数据#xff09;
优点#xff1a; 随机访问高效#xff1a;通过索引可以直接访问元素#xff0c;时间复杂度为 O(1)。 内存连续#xff1a;数组在内存中是连续存储的1数组Array适合静态数据
优点 随机访问高效通过索引可以直接访问元素时间复杂度为 O(1)。 内存连续数组在内存中是连续存储的缓存友好访问速度快。 简单易用实现简单适合存储固定大小的数据。
缺点 固定大小数组的大小通常是固定的动态调整需要重新分配内存效率较低。 插入和删除效率低在数组中插入或删除元素需要移动其他元素时间复杂度为 O(n)。 内存浪费如果数组未完全使用会造成内存浪费。
代码示例
#include iostream
using namespace std;int main() {int arr[5] {1, 2, 3, 4, 5}; // 静态数组cout Element at index 2: arr[2] endl; // 随机访问// 插入元素低效for (int i 4; i 2; i--) {arr[i 1] arr[i];}arr[2] 10; // 在索引2处插入10// 打印数组for (int i 0; i 5; i) {cout arr[i] ;}return 0;
} 2链表Linked List适合动态数据
优点 动态大小链表可以动态分配内存无需预先指定大小。 插入和删除高效在已知节点的情况下插入和删除操作的时间复杂度为 O(1)。 内存利用率高链表按需分配内存不会造成内存浪费。
缺点 随机访问效率低链表不支持随机访问查找元素需要遍历时间复杂度为 O(n)。 额外空间开销链表需要额外的指针空间来存储节点之间的关系。 缓存不友好链表节点在内存中不连续访问速度较慢。
代码示例
#include iostream
using namespace std;struct Node {int data;Node* next;
};void printList(Node* head) {while (head ! nullptr) {cout head-data ;head head-next;}cout endl;
}int main() {Node* head new Node{1, nullptr};head-next new Node{2, nullptr};head-next-next new Node{3, nullptr};// 插入元素Node* newNode new Node{10, head-next};head-next newNode;printList(head); // 输出: 1 10 2 3return 0;
} 3栈Stack
优点 简单高效栈只允许在栈顶进行操作实现简单插入和删除的时间复杂度为 O(1)。 适合特定问题栈非常适合解决递归问题、括号匹配、表达式求值等问题。
缺点 功能受限栈只能在一端进行操作无法直接访问中间元素。 容量限制栈的容量通常是固定的如果使用数组实现动态调整需要额外开销。
代码示例
#include iostream
#include stack
using namespace std;int main() {stackint s;s.push(10); // 入栈s.push(20);s.push(30);cout Top element: s.top() endl; // 访问栈顶s.pop(); // 出栈cout Stack size: s.size() endl; // 栈大小return 0;
} 4队列Queue
优点 先进先出FIFO队列适合处理需要按顺序处理的数据如任务调度、缓冲区等。 高效操作在队尾插入和队头删除的时间复杂度为 O(1)。
缺点 功能受限队列只能在一端插入另一端删除无法直接访问中间元素。 容量限制队列的容量通常是固定的如果使用数组实现动态调整需要额外开销。
代码示例
#include iostream
#include queue
using namespace std;int main() {queueint q;q.push(10); // 入队q.push(20);q.push(30);cout Front element: q.front() endl; // 访问队头q.pop(); // 出队cout Queue size: q.size() endl; // 队列大小return 0;
} 5双端队列Deque
优点 灵活操作双端队列允许在两端进行插入和删除操作功能更强大。 高效操作在两端插入和删除的时间复杂度为 O(1)。
缺点 实现复杂相比栈和队列双端队列的实现更复杂。 容量限制如果使用数组实现容量通常是固定的动态调整需要额外开销。
代码示例
#include iostream
#include deque
using namespace std;int main() {dequeint dq;// 在队头和队尾插入元素dq.push_front(10); // 队头插入dq.push_back(20); // 队尾插入dq.push_back(30);cout Front element: dq.front() endl; // 访问队头cout Back element: dq.back() endl; // 访问队尾// 删除队头和队尾元素dq.pop_front(); // 删除队头dq.pop_back(); // 删除队尾cout Size of deque: dq.size() endl; // 输出: 1return 0;
} 2. 非线性数据结构
1树Tree
优点 层次结构树适合表示具有层次关系的数据如文件系统、组织结构等。 高效搜索二叉搜索树BST的搜索、插入和删除操作的时间复杂度为 O(log n)。 动态调整树可以动态调整结构适合频繁插入和删除的场景。
缺点 复杂度高树的实现和操作比线性结构复杂。 平衡问题如果树不平衡如退化为链表性能会下降搜索时间复杂度退化为 O(n)。 额外空间开销树需要额外的指针空间来存储节点之间的关系。
代码示例
#include iostream
using namespace std;struct TreeNode {int data;TreeNode* left;TreeNode* right;TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};// 插入节点
TreeNode* insert(TreeNode* root, int val) {if (root nullptr) {return new TreeNode(val);}if (val root-data) {root-left insert(root-left, val);} else {root-right insert(root-right, val);}return root;
}// 中序遍历左-根-右
void inorderTraversal(TreeNode* root) {if (root nullptr) return;inorderTraversal(root-left);cout root-data ;inorderTraversal(root-right);
}int main() {TreeNode* root nullptr;root insert(root, 10);root insert(root, 5);root insert(root, 15);root insert(root, 3);root insert(root, 7);cout Inorder Traversal: ;inorderTraversal(root); // 输出: 3 5 7 10 15return 0;
} 2二叉树Binary Tree
优点 简单高效二叉树的结构简单适合实现二叉搜索树、堆等数据结构。 搜索效率高在平衡的情况下搜索、插入和删除的时间复杂度为 O(log n)。
缺点 平衡问题如果二叉树不平衡性能会下降。 空间开销需要额外的指针空间来存储左右子节点。
高级数据结构 约等于 基于二叉树的数据结构
代码示例
#include iostream
using namespace std;struct TreeNode {int data;TreeNode* left;TreeNode* right;
};void inorderTraversal(TreeNode* root) {if (root nullptr) return;inorderTraversal(root-left);cout root-data ;inorderTraversal(root-right);
}int main() {TreeNode* root new TreeNode{10, nullptr, nullptr};root-left new TreeNode{5, nullptr, nullptr};root-right new TreeNode{15, nullptr, nullptr};cout Inorder Traversal: ;inorderTraversal(root); // 输出: 5 10 15return 0;
} 3图Graph
优点 表示复杂关系图适合表示多对多的关系如社交网络、地图等。 灵活性强图可以是有向的或无向的可以带权或不带权。
缺点 实现复杂图的实现和操作比线性结构和树更复杂。 空间开销大图的存储如邻接矩阵或邻接表需要较大的空间。 算法复杂度高图的遍历和搜索算法如 DFS、BFS的时间复杂度较高。
代码示例
#include iostream
#include vector
using namespace std;class Graph {int V; // 顶点数vectorvectorint adj; // 邻接表public:Graph(int V) : V(V), adj(V) {}void addEdge(int u, int v) {adj[u].push_back(v);adj[v].push_back(u); // 无向图}void printGraph() {for (int i 0; i V; i) {cout Vertex i : ;for (int j : adj[i]) {cout j ;}cout endl;}}
};int main() {Graph g(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 3);g.printGraph();return 0;
} 4堆Heap
优点 高效获取极值堆可以在 O(1) 时间内获取最大值或最小值。 适合优先级队列堆适合实现优先级队列用于任务调度等场景。 动态调整堆可以动态调整结构插入和删除的时间复杂度为 O(log n)。
缺点 功能受限堆只能快速获取极值无法高效访问其他元素。 实现复杂堆的实现比线性结构复杂。
代码示例
#include iostream
#include vector
#include algorithm
using namespace std;class MaxHeap {vectorint heap;void heapifyUp(int index) {while (index 0) {int parent (index - 1) / 2;if (heap[parent] heap[index]) {swap(heap[parent], heap[index]);index parent;} else {break;}}}void heapifyDown(int index) {int size heap.size();while (true) {int left 2 * index 1;int right 2 * index 2;int largest index;if (left size heap[left] heap[largest]) {largest left;}if (right size heap[right] heap[largest]) {largest right;}if (largest ! index) {swap(heap[index], heap[largest]);index largest;} else {break;}}}public:void push(int val) {heap.push_back(val);heapifyUp(heap.size() - 1);}void pop() {if (heap.empty()) return;heap[0] heap.back();heap.pop_back();heapifyDown(0);}int top() {if (heap.empty()) throw runtime_error(Heap is empty);return heap[0];}bool empty() {return heap.empty();}
};int main() {MaxHeap heap;heap.push(10);heap.push(30);heap.push(20);heap.push(5);cout Max element: heap.top() endl; // 输出: 30heap.pop();cout Max element after pop: heap.top() endl; // 输出: 20return 0;
} 5哈希表Hash Table散列表
优点 高效查找哈希表的查找、插入和删除操作的平均时间复杂度为 O(1)。 适合大规模数据哈希表适合存储和查找大规模数据。
缺点 哈希冲突哈希冲突不同的数据计算出来的哈希值可能相同从而导致冲突会影响性能需要额外的处理如链地址法或开放地址法。 空间开销大哈希表需要较大的空间来减少冲突。 无序性哈希表中的元素是无序的无法直接按顺序访问。
雪崩效应
如果两个数据有一点不同它们的哈希值就会差别很大从而不容易冲突。哈希表的空间效率和时间效率是矛盾的使用的空间越大越容易设计哈希函数。如果空间很小再好的哈希函数也会产生冲突。在使用哈希表时需要在空间和时间效率上取得平衡。 代码示例
#include iostream
#include unordered_map
using namespace std;int main() {unordered_mapstring, int hashMap;hashMap[Alice] 25;hashMap[Bob] 30;cout Age of Alice: hashMap[Alice] endl; // 输出: 25cout Age of Bob: hashMap[Bob] endl; // 输出: 30return 0;
} 总结 线性数据结构适合处理顺序关系明确的数据操作简单高效但功能受限。 非线性数据结构适合处理复杂关系的数据功能强大但实现和操作复杂度较高。
