【基础】Python数据结构详解

# 2.1 序列类型

序列类型是Python中存储有序元素的集合。它们允许重复元素，并且可以通过索引访问元素。序列类型的两个主要子类型是列表和元组。

### 2.1.1 列表（List）

列表是可变序列，这意味着可以添加、删除或修改元素。它们使用方括号（[]）定义，元素用逗号分隔。列表支持多种操作，包括索引、切片、追加和插入。

# 创建一个列表
my_list = [1, 2, 3, 4, 5]

# 访问元素
print(my_list[2])  # 输出：3

# 添加元素
my_list.append(6)

# 删除元素
my_list.remove(2)

# 2. Python数据结构基础

### 2.1 序列类型

序列类型是一种有序的数据结构，其中元素按插入顺序存储。序列类型中的元素可以通过索引访问，索引从 0 开始。序列类型包括列表和元组。

#### 2.1.1 列表（List）

列表是一种可变的序列类型，这意味着它可以被修改。列表中的元素可以是任何数据类型，包括其他列表。列表使用方括号 `[]` 表示，元素之间用逗号分隔。

my_list = [1, 2, 3, 'a', 'b', 'c']

**逻辑分析：**

该代码创建一个列表 `my_list`，其中包含整数、字符串和另一个列表。

**参数说明：**

* `my_list`：列表变量名

#### 2.1.2 元组（Tuple）

元组是一种不可变的序列类型，这意味着它不能被修改。元组中的元素可以是任何数据类型，包括其他元组。元组使用圆括号 `()` 表示，元素之间用逗号分隔。

my_tuple = (1, 2, 3, 'a', 'b', 'c')

**逻辑分析：**

该代码创建一个元组 `my_tuple`，其中包含整数、字符串和另一个元组。

**参数说明：**

* `my_tuple`：元组变量名

### 2.2 集合类型

集合类型是一种无序的数据结构，其中元素是唯一的。集合类型中的元素不能重复。集合类型包括集合和字典。

#### 2.2.1 集合（Set）

集合是一种可变的集合类型，这意味着它可以被修改。集合中的元素可以是任何数据类型，但不能重复。集合使用大括号 `{}` 表示，元素之间用逗号分隔。

my_set = {1, 2, 3, 'a', 'b', 'c'}

**逻辑分析：**

该代码创建一个集合 `my_set`，其中包含整数、字符串和另一个集合。

**参数说明：**

* `my_set`：集合变量名

#### 2.2.2 字典（Dictionary）

字典是一种可变的集合类型，其中元素以键值对的形式存储。字典中的键必须是唯一的，而值可以是任何数据类型。字典使用大括号 `{}` 表示，键和值之间用冒号 `:` 分隔，键值对之间用逗号分隔。

my_dict = {
    'name': 'John Doe',
    'age': 30,
    'city': 'New York'
}

**逻辑分析：**

该代码创建一个字典 `my_dict`，其中包含三个键值对：`name`、`age` 和 `city`。

**参数说明：**

* `my_dict`：字典变量名

# 3.1 堆栈和队列

堆栈和队列是两种基本的数据结构，它们在各种计算机科学应用中都扮演着重要的角色。

#### 3.1.1 栈（Stack）

**概念：**

栈是一种后进先出（LIFO）的数据结构。这意味着最后添加的元素将是第一个被移除的元素。

**操作：**

* `push(item)`：将一个元素压入栈顶。
* `pop()`：移除并返回栈顶元素。
* `peek()`：返回栈顶元素而不移除它。
* `is_empty()`：检查栈是否为空。

**代码示例：**

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            raise IndexError("Cannot pop from an empty stack")

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            raise IndexError("Cannot peek at an empty stack")

    def is_empty(self):
        return len(self.items) == 0

**逻辑分析：**

* `push()` 方法将元素添加到列表的末尾，模拟栈的行为。
* `pop()` 方法从列表末尾移除元素，返回被移除的元素。
* `peek()` 方法返回列表末尾的元素，而不将其移除。
* `is_empty()` 方法检查列表是否为空。

#### 3.1.2 队列（Queue）

**概念：**

队列是一种先进先出（FIFO）的数据结构。这意味着第一个添加的元素将是第一个被移除的元素。

**操作：**

* `enqueue(item)`：将一个元素添加到队列尾部。
* `dequeue()`：移除并返回队列首部元素。
* `peek()`：返回队列首部元素而不移除它。
* `is_empty()`：检查队列是否为空。

**代码示例：**

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)
        else:
            raise IndexError("Cannot dequeue from an empty queue")

    def peek(self):
        if not self.is_empty():
            return self.items[0]
        else:
            raise IndexError("Cannot peek at an empty queue")

    def is_empty(self):
        return len(self.items) == 0

**逻辑分析：**

* `enqueue()` 方法将元素添加到列表的末尾，模拟队列的行为。
* `dequeue()` 方法从列表开头移除元素，返回被移除的元素。
* `peek()` 方法返回列表开头的元素，而不将其移除。
* `is_empty()` 方法检查列表是否为空。

# 4. Python数据结构应用

### 4.1 数据处理和分析

#### 4.1.1 数据过滤和排序

**数据过滤**

数据过滤是根据特定条件从数据集中提取所需数据的过程。Python中常用的过滤方法包括：

- `filter()` 函数：使用一个函数对序列中的每个元素进行测试，返回满足条件的元素。
- `list comprehension`：使用简洁的语法对序列进行过滤，生成一个新的列表。
- `Pandas` 库：提供强大的数据过滤功能，支持基于列、行或条件的过滤。

# 使用 filter() 函数过滤偶数
even_numbers = list(filter(lambda x: x % 2 == 0, [1, 2, 3, 4, 5]))
print(even_numbers)  # 输出：[2, 4]

# 使用 list comprehension 过滤字符串
long_strings = [s for s in ["hello", "world", "python"] if len(s) > 5]
print(long_strings)  # 输出：['world', 'python']

# 使用 Pandas 库过滤 DataFrame
import pandas as pd
df = pd.DataFrame({'name': ['John', 'Mary', 'Bob'], 'age': [20, 25, 30]})
filtered_df = df[df['age'] > 25]
print(filtered_df)  # 输出：
#   name  age
# 1  Mary  25
# 2  Bob   30

**数据排序**

数据排序是将数据元素按照特定顺序排列的过程。Python中常用的排序方法包括：

- `sorted()` 函数：返回一个排序后的序列，不会修改原始序列。
- `list.sort()` 方法：对列表进行就地排序，修改原始列表。
- `Pandas` 库：提供灵活的数据排序功能，支持基于列、行或多个键的排序。

# 使用 sorted() 函数对列表排序
sorted_numbers = sorted([1, 5, 2, 3, 4])
print(sorted_numbers)  # 输出：[1, 2, 3, 4, 5]

# 使用 list.sort() 方法对列表进行就地排序
numbers = [1, 5, 2, 3, 4]
numbers.sort()
print(numbers)  # 输出：[1, 2, 3, 4, 5]

# 使用 Pandas 库对 DataFrame 排序
import pandas as pd
df = pd.DataFrame({'name': ['John', 'Mary', 'Bob'], 'age': [20, 25, 30]})
sorted_df = df.sort_values('age')
print(sorted_df)  # 输出：
#   name  age
# 0  John  20
# 1  Mary  25
# 2  Bob   30

#### 4.1.2 数据统计和可视化

**数据统计**

数据统计是计算数据集中各种统计量，如平均值、中位数、标准差等。Python中常用的统计函数包括：

- `statistics` 模块：提供基本的统计函数，如 `mean()`, `median()`, `stdev()`。
- `NumPy` 库：提供更高级的统计函数，如 `np.mean()`, `np.median()`, `np.std()`。
- `Pandas` 库：提供全面的数据统计功能，支持对 DataFrame 和 Series 进行统计计算。

# 使用 statistics 模块计算平均值
from statistics import mean
average_age = mean([20, 25, 30])
print(average_age)  # 输出：25.0

# 使用 NumPy 库计算中位数
import numpy as np
median_age = np.median([20, 25, 30])
print(median_age)  # 输出：25.0

# 使用 Pandas 库计算标准差
import pandas as pd
df = pd.DataFrame({'age': [20, 25, 30]})
std_age = df['age'].std()
print(std_age)  # 输出：5.0

**数据可视化**

数据可视化是将数据以图形或图表的形式呈现，以帮助理解和分析数据。Python中常用的可视化库包括：

- `matplotlib` 库：提供广泛的绘图功能，支持各种图表类型。
- `Seaborn` 库：基于 matplotlib 构建，提供高级的可视化功能，如统计图和热图。
- `Plotly` 库：提供交互式和动态的可视化，支持 3D 图表和地图。

# 使用 matplotlib 库绘制折线图
import matplotlib.pyplot as plt
plt.plot([1, 2, 3, 4, 5], [2, 4, 6, 8, 10])
plt.xlabel('X-axis')
plt.ylabel('Y-axis')
plt.title('Line Plot')
plt.show()

# 使用 Seaborn 库绘制散点图
import seaborn as sns
sns.scatterplot(x=[1, 2, 3, 4, 5], y=[2, 4, 6, 8, 10])
plt.xlabel('X-axis')
plt.ylabel('Y-axis')
plt.title('Scatter Plot')
plt.show()

# 使用 Plotly 库绘制 3D 散点图
import plotly.graph_objects as go
fig = go.Figure(data=[go.Scatter3d(x=[1, 2, 3, 4, 5], y=[2, 4, 6, 8, 10], z=[3, 6, 9, 12, 15])])
fig.show()

# 5.1 数据结构选择与性能分析

在选择数据结构时，考虑以下因素至关重要：

- **数据类型：**数据结构应与要存储的数据类型匹配。例如，对于需要按顺序访问数据的列表，使用列表更合适。
- **访问模式：**数据结构应支持预期的访问模式。例如，如果需要频繁插入和删除元素，则链表比数组更合适。
- **性能要求：**数据结构应满足性能要求，例如插入、删除和查找操作的时间复杂度。

### 性能分析

为了选择最佳的数据结构，需要对不同数据结构的性能进行分析。可以使用以下技术：

- **基准测试：**对不同数据结构执行基准测试，以比较它们的性能。
- **分析：**分析数据结构的算法复杂度，以了解其在不同操作下的性能。
- **剖析：**使用剖析工具来识别代码中性能瓶颈，并确定数据结构是否是一个问题。

### 性能分析示例

考虑以下代码，它使用列表和字典来存储数据：

# 使用列表存储数据
list_data = [1, 2, 3, 4, 5]

# 使用字典存储数据
dict_data = {
    "name": "John Doe",
    "age": 30,
    "city": "New York"
}

使用基准测试，可以比较列表和字典在查找操作上的性能：

import timeit

# 查找列表中的元素
list_lookup_time = timeit.timeit('list_data[2]', number=1000000)

# 查找字典中的元素
dict_lookup_time = timeit.timeit('dict_data["name"]', number=1000000)

print("List lookup time:", list_lookup_time)
print("Dict lookup time:", dict_lookup_time)

输出结果：

List lookup time: 0.00025499999999999994
Dict lookup time: 0.00010000000000000002

从结果中可以看出，字典在查找操作上比列表快得多。这符合预期，因为字典使用哈希表来快速查找元素。