13. 集合类型

# 1. 简介

集合类型是计算机编程中常用的数据结构，用于存储多个元素。在不同的编程语言中，集合类型可以有不同的实现方式和特性。本章将介绍常见的集合类型，包括数组、链表、堆栈、队列和散列表。

## 数组

数组是最简单的一种集合类型，它可以存储相同类型的元素，并通过索引来访问元素。数组的优点是访问元素的时间复杂度是O(1)，缺点是插入和删除元素的时间复杂度是O(n)。

# 示例代码：创建和访问数组
arr = [1, 2, 3, 4, 5]
print(arr[0])  # 输出第一个元素

代码总结：数组是一种随机访问的数据结构，可以通过索引来访问元素。

结果说明：上述代码将输出数组的第一个元素1。

## 链表

链表是一种动态的数据结构，它由多个节点构成，每个节点包含数据和指向下一个节点的指针。链表的优点是插入和删除元素的时间复杂度是O(1)，缺点是访问元素的时间复杂度是O(n)。

// 示例代码：创建和访问链表
class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

Node head = new Node(1);
head.next = new Node(2);
System.out.println(head.data);  // 输出头节点的数据

代码总结：链表是一种动态的数据结构，节点之间通过指针相连接。

结果说明：上述代码将输出链表的头节点的数据1。

## 堆栈

堆栈是一种后进先出（LIFO）的数据结构，它只能在一端进行操作。堆栈的优点是插入和删除元素的时间复杂度是O(1)，缺点是访问其他元素的时间复杂度是O(n)。

// 示例代码：创建和操作堆栈
stack := []int{}
stack = append(stack, 1)  // 入栈
stack = append(stack, 2)
top := stack[len(stack)-1]  // 获取栈顶元素

代码总结：堆栈是一种后进先出的数据结构，只能在一端进行操作。

结果说明：上述代码将得到堆栈的栈顶元素2。

## 队列

队列是一种先进先出（FIFO）的数据结构，它可以在一端插入元素，在另一端删除元素。队列的优点是插入和删除元素的时间复杂度是O(1)，缺点是访问其他元素的时间复杂度是O(n)。

// 示例代码：创建和操作队列
const queue = []
queue.push(1)  // 入队
queue.push(2)
const front = queue[0]  // 获取队首元素

代码总结：队列是一种先进先出的数据结构，可以在一端插入元素，在另一端删除元素。

结果说明：上述代码将得到队列的队首元素1。

## 散列表

散列表（哈希表）是一种根据键（Key）直接访问值（Value）的数据结构，它通过哈希函数将键映射到一个位置。散列表的优点是插入、删除和访问元素的平均时间复杂度是O(1)，缺点是空间消耗较大。

# 示例代码：创建和操作散列表
hash_table = {}
hash_table['key1'] = 'value1'  # 插入键值对
hash_table['key2'] = 'value2'
value = hash_table['key1']  # 根据键访问值

代码总结：散列表通过哈希函数将键映射到一个位置，实现了快速访问元素。

结果说明：上述代码将得到散列表中键"key1"对应的值"value1"。

综上所述，数组、链表、堆栈、队列和散列表是常见的集合类型，它们各自有不同的特点和适用场景。了解这些集合类型可以帮助我们在编程中选择合适的数据结构来解决问题。

# 2. 数组

数组是一种用来存储相同类型元素的数据结构。它可以按照索引的顺序访问和操作数组中的元素。

### 2.1 数组的定义和初始化

在Python中，可以使用`list`类型来表示数组。以下是数组的一些常见操作：

1. 定义空数组：`arr = []`
2. 定义带有元素的数组：`arr = [1, 2, 3, 4, 5]`
3. 获取数组的长度：`length = len(arr)`
4. 访问数组元素：可以使用索引来访问数组中的元素，索引从0开始。

arr = [1, 2, 3, 4, 5]
print(arr[0])  # 输出第一个元素，结果为1
print(arr[2])  # 输出第三个元素，结果为3

运行结果：

1
3

### 2.2 数组的常见操作

#### 2.2.1 遍历数组

遍历数组是指按照顺序访问数组中的所有元素。可以使用循环来实现数组的遍历操作。

arr = [1, 2, 3, 4, 5]

# 使用for循环遍历数组
for num in arr:
    print(num)

# 使用while循环遍历数组
i = 0
while i < len(arr):
    print(arr[i])
    i += 1

运行结果：

1
2
3
4
5
1
2
3
4
5

#### 2.2.2 修改数组元素

可以通过索引来修改数组中的元素。

``