C++中的数组、链表与哈希表

C++中的数组、链表与哈希表

数组

数组是一种数据结构，它存储的是一组相同类型的值。数组中每个元素的类型都是相同的，而且数组中的元素是按照一定的顺序排列的。C++中的数组是有序的，并且可以通过下标来访问数组中的元素。

数组的定义和初始化

在C++中定义数组的语法如下：

type arr_name[arr_size];

其中，type表示数组元素的类型，arr_name为数组名，arr_size表示数组的大小。例如：

int arr[5];

这样就定义了一个有5个整数元素的数组。

在定义数组时，也可以对其进行初始化。初始化可以在定义数组时进行，也可以在定义完成后再手动进行。例如：

int arr1[5] = {1, 2, 3, 4, 5};
int arr2[] = {1, 2, 3, 4, 5};
int arr3[5] = {1, 2};

第一种方式中，数组的大小为5且每个元素的值为{1, 2, 3, 4, 5}。第二种方式中，由于数组的大小被省略了，所以编译器会根据初始化列表中的元素数量来计算数组的大小，这里的大小也是5。第三种方式中，数组的大小为5，但是只有前两个元素为1和2，后面三个元素会被默认初始化为0。

数组的访问和修改

由于数组是有序的，可以通过下标访问数组中的元素，下标从0开始。例如：

int arr[5] = {1, 2, 3, 4, 5};
cout << arr[0] << endl; // 输出1
cout << arr[2] << endl; // 输出3

也可以通过下标修改数组中的元素。例如：

int arr[5] = {1, 2, 3, 4, 5};
arr[0] = 10;
cout << arr[0] << endl; // 输出10

链表

链表是一种常见的数据结构，在链表中，每个元素包含了对下一个元素的引用，因此链表中的元素是可以动态添加和删除的。链表中的元素称为节点，每个节点中包含了当前节点的值和指向下一个节点的指针。C++中的链表是由指针实现的。

链表的定义和访问

在C++中定义链表的语法如下：

class Node {
public:
    int val;
    Node* next;
    Node(int x) : val(x), next(NULL) {}
};

其中，每个节点包含了一个整数val和指向下一个节点的指针next。链表实际上是由若干个Node节点组成的。

在定义链表时，一般需要定义一个头节点，其next指针指向第一个节点。例如：

Node* head = new Node(0);
head->next = new Node(1);
head->next->next = new Node(2);

这样就定义了一个包含三个节点、值为{0, 1, 2}的链表。可以通过遍历链表来访问每个节点：

Node* p = head;
while (p != NULL) {
    cout << p->val << endl;
    p = p->next;
}

链表的插入和删除

链表可以动态添加和删除节点，因此其长度是可以动态变化的。在链表中插入一个节点时，需要将前一个节点的next指针指向新的节点，新的节点的next指针指向后面的节点。例如，在链表中插入一个元素3：

Node* new_node = new Node(3);
new_node->next = head->next->next;
head->next->next = new_node;

这样会将3插入到1和2的中间。

在链表中删除一个节点时，需要将前一个节点的next指针指向后一个节点。例如，删除元素2：

head->next->next = head->next->next->next;

这样会将2从链表中删除。

哈希表

哈希表是一种高效的数据结构，可以用来存储键-值对。哈希表是由若干个桶（bucket）组成的，每个桶中包含了一个键-值对的链表。哈希表的键被哈希函数映射为一个索引，这个索引指向了具体的某个桶。当需要查找某个键对应的值时，先将键通过哈希函数计算出索引，然后再在相应的桶中查找。如果哈希函数设计得好，就能保证对于不同的键，它们被哈希到不同的桶中，这样就能保证查找的效率。

哈希表的定义和初始化

C++中的unordered_map实现了哈希表的功能，其定义语法如下：

unordered_map<key_type, value_type> mp;

其中，key_type为键的类型，value_type为值的类型。可以通过以下方式初始化哈希表：

unordered_map<int, int> mp = {{1, 2}, {3, 4}, {5, 6}};

这样就创建了一个包含三个键值对的哈希表，其中键为{1, 3, 5}，值为{2, 4, 6}。

哈希表的插入和删除

向哈希表中插入一个键-值对时，可以使用map的insert函数，例如：

mp.insert({7, 8});

这样就可以将键为7、值为8的键值对插入哈希表中。如果该键已经存在，则不会进行插入操作。

删除一个键-值对时，可以使用map的erase函数。例如：

mp.erase(3);

这样就可以将键为3的键值对从哈希表中删除。如果该键不存在，则不会进行删除操作。

示例说明

数组示例：

int arr[] = {1, 2, 3, 4, 5};
int sum = 0;
for (int i = 0; i < 5; i++) {
    sum += arr[i];
}
cout << sum << endl; // 输出15

这个示例演示了如何遍历数组，求出数组中所有元素的和。

链表示例：

Node* head = new Node(0);
head->next = new Node(1);
head->next->next = new Node(2);
Node* p = head->next->next;
head->next->next = head->next->next->next;
delete p;

这个示例演示了如何在链表中删除一个节点。首先创建了一个链表，然后找到链表中的第三个节点，并删除它。

哈希表示例

unordered_map<string, string> mp;
mp.insert({"apple", "red"});
mp.insert({"banana", "yellow"});
mp.erase("apple");
mp.insert({"grape", "purple"});
cout << mp["banana"] << endl; // 输出yellow

这个示例演示了如何创建一个字符串到字符串的哈希表，并进行插入和删除操作。最后输出了键为"banana"的值。