数据结构: 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