Python数据结构教程

本文概述

• 抽象数据类型和数据结构
• 原始数据结构
• 数据类型转换
• 非原始数据结构
• 你做到了！

数据结构是一种组织和存储数据的方式, 因此可以高效地访问和使用它们。它们定义了数据与可以对数据执行的操作之间的关系。定义了许多种数据结构, 这些数据结构使数据科学家和计算机工程师更容易集中精力解决更大的问题, 而不是迷失在数据描述和访问的细节中。

在本教程中, 你将学习各种Python数据结构, 并了解如何实现它们：

• 抽象数据类型和数据结构
• 原始数据结构
  • 整数
  • float
  • 弦乐
  • boolean
• 非原始数据结构
  • 数组
  • 清单
  • 元组
  • 字典
  • 套装
  • 档案

在srcmini的免费的Python数据科学入门课程中, 你可以了解有关在数据科学环境中专门使用Python的更多信息。该课程介绍了Python的基本概念。有了它, 你将发现方法, 函数和NumPy包。

抽象数据类型和数据结构

正如你在简介中所读到的那样, 数据结构可帮助你着眼于大局, 而不是迷失在细节上。这称为数据抽象。

现在, 数据结构实际上是抽象数据类型或ADT的实现。此实现需要使用一些编程构造和基本数据类型的集合来对数据进行物理查看。

通常, 在计算机科学中, 数据结构可分为两类：原始数据结构和非原始数据结构。前者是表示数据的最简单形式, 而后者则是高级的：为了特殊目的, 它们在更复杂的数据结构中包含原始数据结构。

原始数据结构

这些是最原始或最基本的数据结构。它们是数据操作的基础, 并且包含纯净的简单数据值。 Python有四种原始变量类型：

• 整数
• float
• 弦乐
• boolean

在下一部分中, 你将了解有关它们的更多信息！

整数

你可以使用整数表示数值数据, 更具体地说, 可以使用从负无穷大到无穷大的整数, 例如4、5或-1。

float

“浮点数”代表”浮点数”。你可以将其用于有理数, 通常以十进制数字结尾, 例如1.11或3.14。

看看下面的srcmini Light Chunk, 并尝试一些整数和浮点运算！

请注意, 在Python中, 你不必显式声明变量或数据的类型。那是因为它是一种动态类型的语言。动态类型化语言是对象可以存储的数据类型可变的语言。

String

字符串是字母, 单词或其他字符的集合。在Python中, 你可以通过将一系列字符括在一对单引号或双引号中来创建字符串。例如：”蛋糕”, “饼干”等。

你还可以在两个或多个字符串上应用+操作来串联它们, 就像下面的示例一样：

x = 'Cake'
y = 'Cookie'
x + ' & ' + y

'Cake & Cookie'

这是你可以对字符串执行的其他一些基本操作；例如, 你可以使用*重复一个字符串一定次数：

# Repeat
x * 2

'CakeCake'

你还可以对字符串进行切片, 这意味着你选择了字符串的一部分：

# Range Slicing
z1 = x[2:] 

print(z1)

# Slicing
z2 = y[0] + y[1] 

print(z2)

ke
Co

请注意, 字符串也可以是字母数字字符, 但是+操作仍用于连接字符串。

x = '4'
y = '2'

x + y

'42'

Python有许多内置方法或辅助函数来操纵字符串。一些常见的字符串操作是替换子字符串, 将段落中的某些单词大写, 在另一个字符串中找到一个字符串的位置。查看其中一些：

• 大写字符串

str.capitalize('cookie')

'Cookie'

• 检索字符串的长度(以字符为单位)。请注意, 空格也计入最终结果：

str1 = "Cake 4 U"
str2 = "404"
len(str1)

8

• 检查字符串是否仅包含数字

str1.isdigit()

False

str2.isdigit()

True

• 用其他弦代替弦的一部分

str1.replace('4 U', str2)

'Cake 404'

• 查找其他字符串中的子字符串；返回找到子字符串的字符串中最低的索引或位置：

str1 = 'cookie'
str2 = 'cook'
str1.find(str2)

0

子字符串” cook”位于” cookie”的开头。结果, 你引用” cookie”中找到该子字符串的位置。在这种情况下, 因为你从0开始计数位置, 所以返回0！

str1 = 'I got you a cookie'
str2 = 'cook'
str1.find(str2)

12

同样, 子字符串” cook”位于”我为你提供cookie”中的位置12。请记住, 你从0开始计数, 而空格从位置开始计数！

你可以在这里找到Python中字符串方法的详尽列表。

boolean

这种内置数据类型可以使用以下值：True和False, 通常使它们可以与整数1和0互换。布尔值在条件表达式和比较表达式中很有用, 就像以下示例中所示：

x = 4
y = 2
x == y

False

x > y

True

x = 4
y = 2
z = (x==y) # Comparison expression (Evaluates to false)
if z: # Conditional on truth/false value of 'z'
    print("Cookie")
else: print("No Cookie")

No Cookie

数据类型转换

有时, 你会发现自己正在处理其他人的代码, 例如, 你需要将整数转换为浮点数, 反之亦然。或者, 当你真正需要的是浮点数时, 你可能发现自己一直在使用整数。在这种情况下, 你可以转换变量的数据类型！

要检查Python中对象的类型, 请使用内置的type()函数, 就像下面的代码行一样：

i = 4.0
type(i)

float

当你将实体的类型从一种数据类型更改为另一种数据类型时, 这称为”类型转换”。可能有两种数据转换：隐式称为强制转换和显式转换, 通常称为强制转换。

隐式数据类型转换

这是自动的数据转换, 编译器会为你处理。看下面的例子：

# A float
x = 4.0 

# An integer
y = 2 

# Divide `x` by `y`
z = x/y

# Check the type of `z`
type(z)

float

在上面的示例中, 你不必显式更改y的数据类型即可执行浮点值除法。编译器暗中为你完成了此操作。

这很简单！

显式数据类型转换

这种类型的数据类型转换是用户定义的, 这意味着你必须显式通知编译器更改某些实体的数据类型。考虑下面的代码块以完全理解这一点：

x = 2
y = "The Godfather: Part "
fav_movie = y + x

---------------------------------------------------------------------------

TypeError                                 Traceback (most recent call last)

<ipython-input-51-b8fe90df9e0e> in <module>()
      1 x = 2
      2 y = "The Godfather: Part "
----> 3 fav_movie = y + x


TypeError: Can't convert 'int' object to str implicitly

上面的示例给你一个错误, 因为由于混合的数据类型, 编译器无法理解你正在尝试执行串联或加法。你有一个整数和一个字符串, 试图将它们加在一起。

有明显的不匹配。

为了解决这个问题, 你首先需要将int转换为字符串, 然后才能执行串联。

请注意, 并非总是可能将数据类型转换为另一种。你可以在此处使用一些内置的数据转换函数：int(), float()和str()。

x = 2
y = "The Godfather: Part "
fav_movie = (y) + str(x)
print(fav_movie)

The Godfather: Part 2

非原始数据结构

非基本类型是数据结构族的复杂成员。它们不仅存储值, 而且还存储各种格式的值的集合。

在传统的计算机科学世界中, 非原始数据结构分为：

• 数组
• 清单
• 档案

Array

首先, Python中的数组是一种收集基本数据类型的紧凑方式, 数组中的所有条目都必须具有相同的数据类型。但是, 与其他编程语言(例如C ++或Java)不同, 数组在Python中并不是很流行。

通常, 当人们谈论Python中的数组时, 他们实际上是在指列表。但是, 它们之间有根本的区别, 你将很快看到这一点。对于Python, 可以将数组视为存储某种列表的更有效方法。但是, 这种类型的列表具有相同数据类型的元素。

在Python中, 数组受数组模块支持, 并且在开始初始化和使用它们之前需要将其导入。数组中存储的元素的数据类型受到限制。数据类型是在数组创建期间指定的, 并使用类型代码指定, 该类型代码是单个字符, 如你在以下示例中看到的I：

import array as arr
a = arr.array("I", [3, 6, 9])
type(a)

array.array

Python Array文档页面提供了有关可用的各种类型代码和数组模块提供的功能的更多信息。

list

Python中的列表用于存储异构项目的集合。这些都是可变的, 这意味着你可以更改其内容而无需更改其标识。你可以通过方括号[和]来识别列表, 该方括号包含用逗号分隔的元素。列表内置在Python中：你无需单独调用它们。

x = [] # Empty list
type(x)

list

x1 = [1, 2, 3]
type(x1)

list

x2 = list([1, 'apple', 3])
type(x2)

list

print(x2[1])

apple

x2[1] = 'orange'
print(x2)

[1, 'orange', 3]

注意：就像你在上面的示例中看到的x1一样, 列表也可以容纳同类项目, 因此可以满足数组的存储功能。除非你要对该集合应用某些特定操作, 否则就可以了。

Python提供了许多操作和使用列表的方法。将新项目添加到列表, 从列表中删除一些项目, 对列表进行排序或反转是常见的列表操作。让我们看看其中的一些动作：

• 使用append()将11添加到list_num列表中。默认情况下, 此数字将添加到列表的末尾。

list_num = [1, 2, 45, 6, 7, 2, 90, 23, 435]
list_char = ['c', 'o', 'o', 'k', 'i', 'e']

list_num.append(11) # Add 11 to the list, by default adds to the last position
print(list_num)

[1, 2, 45, 6, 7, 2, 90, 23, 435, 11]

• 使用insert()在list_num列表的索引或位置0处插入11

list_num.insert(0, 11)
print(list_num)

[11, 1, 2, 45, 6, 7, 2, 90, 23, 435, 11]

• 借助remove()从list_char中删除首次出现的” o”

list_char.remove('o') 
print(list_char)

['c', 'o', 'k', 'i', 'e']

• 从list_char删除索引为-2的项目

list_char.pop(-2) # Removes the item at the specified position
print(list_char)

['c', 'o', 'k', 'e']

list_num.sort() # In-place sorting
print(list_num)

[1, 2, 2, 6, 7, 11, 11, 23, 45, 90, 435]

list.reverse(list_num)
print(list_num)

[435, 90, 45, 23, 11, 11, 7, 6, 2, 2, 1]

如果你想了解有关Python列表的更多信息, 可以轻松浏览18个最常见的Python列表问题教程！

数组与列表

既然你已经在Python中看到了列表, 你可能想知道为什么根本需要数组。原因是它们在可对其执行的操作方面根本不同。使用数组, 你可以轻松地单独对其所有项目执行操作, 列表可能并非如此。这是一个例子：

array_char = array.array("u", ["c", "a", "t", "s"])
array_char.tostring()
print(array_char)

array('u', 'cats')

你能够应用array_char的tostring()函数, 因为Python知道数组中的所有项目都是相同的数据类型, 因此该操作在每个元素上的行为方式相同。因此, 在处理大量同类数据类型集合时, 数组可能非常有用。由于Python不必记住每个元素的数据类型详细信息, 因此, 在某些情况下, 与列表相比, 数组可能会更快并且使用更少的内存。

在讨论数组主题时, 还值得一提的是NumPy数组。 NumPy数组在数据科学世界中非常广泛地用于处理多维数组。通常, 它们比数组模块和Python列表更有效。 NumPy数组中元素的读取和写入速度更快, 并且它们支持”向量化”操作, 例如逐元素加法。同样, NumPy数组可有效处理大型稀疏数据集。要了解更多信息, 请查看srcmini的Python Numpy Array Tutorial。

以下是一些代码, 可帮助你开始使用NumPy Array：

import numpy as np

arr_a = np.array([3, 6, 9])
arr_b = arr_a/3 # Performing vectorized (element-wise) operations 
print(arr_b)

[ 1.  2.  3.]

arr_ones = np.ones(4)
print(arr_ones)

[ 1.  1.  1.  1.]

multi_arr_ones = np.ones((3, 4)) # Creating 2D array with 3 rows and 4 columns
print(multi_arr_ones)

[[ 1.  1.  1.  1.]
 [ 1.  1.  1.  1.]
 [ 1.  1.  1.  1.]]

传统上, 列表数据结构可以进一步分为线性和非线性数据结构。堆栈和队列称为”线性数据结构”, 而图和树则称为”非线性数据结构”。这些结构及其概念可能相对复杂, 但由于它们与实际模型相似而被广泛使用。你将在本教程中瞥见这些主题。

注意：在线性数据结构中, 数据项是按顺序组织的, 或者说是线性组织的。依次逐个遍历这些数据项, 并且可以在一次运行中遍历线性数据结构中的所有数据项。但是, 在非线性数据结构中, 数据项不是按顺序组织的。这意味着这些元素可以连接到多个元素, 以反映这些项目之间的特殊关系。非线性数据结构中的所有数据项在单次运行期间可能不会遍历。

堆栈

堆栈是根据后进先出(LIFO)概念插入和删除对象的容器。想一想在一个宴会上有一堆盘子的情况, 总是总是从盘子的顶部添加或删除盘子。在计算机科学中, 此概念用于评估表达式和语法分析, 调度算法/例程等。

可以使用Python中的列表来实现堆栈。当你将元素添加到堆栈中时, 这称为推入操作, 而当你删除或删除元素时, 则称为弹出操作。请注意, 在Python中使用堆栈时, 实际上可以使用pop()方法：

# Bottom -> 1 -> 2 -> 3 -> 4 -> 5 (Top)
stack = [1, 2, 3, 4, 5] 
stack.append(6) # Bottom -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 (Top)
print(stack)

[1, 2, 3, 4, 5, 6]

stack.pop() # Bottom -> 1 -> 2 -> 3 -> 4 -> 5 (Top)
stack.pop() # Bottom -> 1 -> 2 -> 3 -> 4 (Top)
print(stack)

[1, 2, 3, 4]

队列

队列是根据先进先出(FIFO)原理插入和删除的对象的容器。现实世界中排队的一个很好的例子是售票柜台的排队, 人们根据他们的到达顺序迎合他们的饮食, 因此首先到达的人也是最早离开的人。队列可以有许多种。

列表对实现队列的效率不高, 因为从列表末尾开始的append()和pop()不够快, 并且会产生内存移动成本。同样, 在列表的末尾插入和从列表的开头删除也不是那么快, 因为它需要元素位置的移位。

图表

数学和计算机科学中的图形是由节点组成的网络, 这些节点也可以彼此连接, 也可以不相互连接。连接两个节点的线或路径称为边。如果边缘具有特定的流动方向, 则它是有向图, 该方向的边缘称为圆弧。否则, 如果未指定方向, 则该图称为无向图。

这听起来可能非常理论化, 而且当你深入研究时可能变得相当复杂。但是, 图是数据科学中一个特别重要的概念, 通常用于对现实生活中的问题进行建模。社会网络, 化学和生物学领域的分子研究, 地图, 推荐系统都依赖于图和图论原理。

在这里, 你将找到一个使用Python词典的简单图形实现, 以帮助你入门：

graph = { "a" : ["c", "d"], "b" : ["d", "e"], "c" : ["a", "e"], "d" : ["a", "b"], "e" : ["b", "c"]
        }

def define_edges(graph):
    edges = []
    for vertices in graph:
        for neighbour in graph[vertices]:
            edges.append((vertices, neighbour))
    return edges

print(define_edges(graph))

[('a', 'c'), ('a', 'd'), ('b', 'd'), ('b', 'e'), ('c', 'a'), ('c', 'e'), ('e', 'b'), ('e', 'c'), ('d', 'a'), ('d', 'b')]

你可以对图形做一些很酷的事情, 例如尝试查找两个节点之间是否存在路径, 或者查找两个节点之间的最短路径, 从而确定图形中的周期。

实际上, 著名的”旅行推销员问题”是找到一条尽可能短的路线, 该路线只精确地访问每个节点一次并返回到起点。有时, 已为图形的节点或弧线分配了权重或成本, 你可以将其视为分配行走的难度级别, 并且有兴趣寻找最便宜或最简单的路径。

树木

现实世界中的一棵树是一种生物, 它的根植在地下, 树枝支撑着叶子, 结果在野外露宿。树的树枝以某种有组织的方式散开。在计算机科学中, 树木用于描述有时是如何组织数据的, 除了根在顶部, 树枝, 树叶跟随, 向底部扩散, 并且与真实树相比, 树是倒置绘制的。

为了引入更多的符号, 根始终在树的顶部。保持树的隐喻, 后面的其他节点称为分支, 每个分支中的最后一个节点称为叶子。你可以想象每个分支本身就是一棵较小的树。根通常称为父节点, 而它在其下方引用的节点称为子节点。具有相同父级的节点称为同级。你知道为什么这也称为家谱吗？

树有助于定义现实世界场景, 从游戏世界到设计XML解析器, 到处都使用树, 并且PDF设计原理也基于树。在数据科学中, “基于决策树的学习”实际上构成了很大的研究领域。存在许多著名的方法, 例如装袋, 增强使用树模型来生成预测模型。像国际象棋这样的游戏用所有可能的动作来构建一棵大树, 以分析和应用启发式方法来确定最佳动作。

你可以使用和组合到目前为止在本教程中看到的各种数据结构来实现树结构。但是, 为简单起见, 本主题将在另一篇文章中讨论。

class Tree:
    def __init__(self, info, left=None, right=None):
        self.info = info
        self.left  = left
        self.right = right

    def __str__(self):
        return (str(self.info) + ', Left child: ' + str(self.left) + ', Right child: ' + str(self.right))

tree = Tree(1, Tree(2, 2.1, 2.2), Tree(3, 3.1))
print(tree)

1, Left child: 2, Left child: 2.1, Right child: 2.2, Right child: 3, Left child: 3.1, Right child: None

你已经了解了数组, 还看到了列表数据结构。但是, Python提供了多种不同的数据收集机制, 尽管它们可能不包括在计算机科学的传统数据结构主题中, 但是对于Python编程语言, 它们还是值得特别了解的：

• 元组
• 字典
• 套装

元组

元组是另一种标准序列数据类型。元组和列表之间的区别在于元组是不可变的, 这意味着一旦定义, 就不能删除, 添加或编辑其中的任何值。如果你可能会将控件传递给其他人, 但又不希望他们操纵集合中的数据, 而只是看到它们或在数据副本中单独执行操作, 则这可能很有用。

让我们看看如何实现元组：

x_tuple = 1, 2, 3, 4, 5
y_tuple = ('c', 'a', 'k', 'e')
x_tuple[0]

1

y_tuple[3]
x_tuple[0] = 0 # Cannot change values inside a tuple

---------------------------------------------------------------------------

TypeError                                 Traceback (most recent call last)

<ipython-input-74-b5d6da8c1297> in <module>()
      1 y_tuple[3]
----> 2 x_tuple[0] = 0 # Cannot change values inside a tuple


TypeError: 'tuple' object does not support item assignment

字典

如果你想实现类似于电话簿的功能, 那么词典正是你所需要的。你以前见过的数据结构都不适合电话簿。

这是字典可以派上用场的时候。字典由键值对组成。键用于标识项目, 值保留, 顾名思义就是该项目的值。

x_dict = {'Edward':1, 'Jorge':2, 'Prem':3, 'Joe':4}
del x_dict['Joe']
x_dict

{'Edward': 1, 'Jorge': 2, 'Prem': 3}

x_dict['Edward'] # Prints the value stored with the key 'Edward'.

1

你可以在字典上应用许多其他内置功能：

len(x_dict)

3

x_dict.keys()

dict_keys(['Prem', 'Edward', 'Jorge'])

x_dict.values()

dict_values([3, 1, 2])

套装

集是不同(唯一)对象的集合。这些对于创建仅在数据集中保留唯一值的列表很有用。这是一个无序的集合, 但是是一个可变的集合, 这在处理庞大的数据集时非常有帮助。

x_set = set('CAKE&COKE')
y_set = set('COOKIE')

print(x_set)

{'A', '&', 'O', 'E', 'C', 'K'}

print(y_set) # Single unique 'o'

{'I', 'O', 'E', 'C', 'K'}

print(x - y) # All the elements in x_set but not in y_set

---------------------------------------------------------------------------

NameError                                 Traceback (most recent call last)

<ipython-input-3-31abf5d98454> in <module>()
----> 1 print(x - y) # All the elements in x_set but not in y_set


NameError: name 'x' is not defined

print(x_set|y_set) # Unique elements in x_set or y_set or both

{'C', '&', 'E', 'A', 'O', 'K', 'I'}

print(x_set & y_set) # Elements in both x_set and y_set

{'O', 'E', 'K', 'C'}

档案

传统上, 文件是数据结构的一部分。而且, 尽管大数据在数据科学行业中很普遍, 但是没有存储和检索以前存储的信息功能的编程语言将几乎无用。你仍然必须利用数据库中文件中的所有数据, 并且你将学习如何做。

用Python读写文件的语法与其他编程语言相似, 但是更易于处理。以下是一些基本功能, 可帮助你使用Python处理文件：

• open()用于打开系统中的文件, 文件名是要打开的文件的名称；
• read()读取整个文件；
• readline()一次读取一行；
• write()将字符串写入文件, 并返回写入的字符数；和
• close()关闭文件。

# File modes (2nd argument): 'r'(read), 'w'(write), 'a'(appending), 'r+'(both reading and writing)
f = open('file_name', 'w')

# Reads entire file
f.read() 

# Reads one line at a time
f.readline() 

# Writes the string to the file, returning the number of char written
f.write('Add this line.') 

f.close()

open()函数中的第二个参数是文件模式。它允许你指定要读取(r), 写入(w), 追加(a)还是读取和写入(r +)。

要了解有关Python中文件处理的更多信息, 请务必查看此页面。

你做到了！

欢呼！你已达到本教程的结尾！这使你的话题更接近征服数据科学世界的梦想。

如果你有兴趣, srcmini的两部分Python Data Science Toolbox将更深入地研究函数, 迭代器, 列表等。

休息一下, 准备就绪后, 请转至推荐的教程之一, 继续你的旅程！