数据结构引言：

    数据结构是组织数据的方式，以便能够更好的存储和获取数据。数据结构定义数据之间的关系和对这些数据的操作方式。数据结构屏蔽了数据存储和操作的细节，让程序员能更好的处理业务逻辑，同时拥有快速的数据存储和获取方式。

    在这篇文章中，你将了解到多种数据结构以及这些数据结构在Python中实现的方式。

抽象数据类型和数据结构

    数据结构是抽象数据类型(ADT)的实现，通常，是通过编程语言提供的基本数据类型为基础，结合相应的代码来实现。

    通常来说，数据结构分为两类：原始数据结构和非原始数据结构，原始数据结构是用来表示简单的数据关系，非原始数据结构包含原始数据结构，同时，数据关系更加复杂，数据操作也更加复杂。

原始数据结构

    原始数据结构 - 顾名思义 - 是最原始的或基本的数据结构。 它们是数据操作的构建块，包含纯粹，简单的数据值。 Python有四种原始变量类型：

• Integers

• Float

• Strings

• Boolean

Integers

    您可以使用Integers表示数字数据，具体地说，可以使用从负无穷大到无穷大的整数

Float

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

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

String

    String是字母，单词或其他字符的集合。 在Python中，您可以通过在一对单引号或双引号中包含一系列字符来创建字符串。 例如：‘cake’，“cookie”等。您还可以对两个或多个字符串应用+操作来连接它们，就像下面的示例中一样：

x = 'Cake'
y = 'Cookie'
x + ' & ' + y #结果:'Cake & Cookie'

以下是您可以使用字符串执行的一些其他基本操作; 例如，您可以使用*重复字符串一定次数：

# Repeat
x * 2 #结果：'CakeCake'

您还可以切割字符串

z1 = x[2:] 
print(z1)
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 = "Cake 4 U"
str2 = "404"
str1.isdigit()
False
str2.isdigit()
True

• 替换

str1 = "Cake 4 U"
str2 = "404"
str1.replace('4 U', str2)
'Cake 404'

• 查找子字符串

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

Boolean

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

x = 4
y = 2
x == y
False
x > y
True
x = 4
y = 2
z = (x==y)
if z:
    print("Cookie")
else:
    print("No Cookie")
No Cookie

数据类型转换

    有时，你需要整型，但是接口返回给你的是字符串，这时，你就需要数据类型转换，Python里，可以使用type函数来查看数据类型。

i = 4.0
type(i)
float

当你把数据的类型改变时，就称作数据类型转换。数据类型转换分为两种：隐式转换和显示转换。

隐式数据类型转换

    数据类型自动转换，不需要指定，编译器会为您处理。 看看以下示例：

# float
x = 4.0 
# integer
y = 2 
z = x/y
type(z)
float

在上面的示例中，您不必将x的数据类型显式更改为float以执行浮点值除法。 编译器隐式地为你做了这个。

显式数据类型转换

    这种类型的数据类型转换是用户定义的，这意味着您必须明确地通知编译器更改某些实体的数据类型。例如：

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

上面的示例，没有明确的告诉编译器x,y的数据类型，编译器认为x为整型，y为字符串，当你试图连接字符串和整数，编译器报错了，这个问题你可以这样解决：

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

python内置了一些类型转换函数：int(), float(), 和 str()

非原始数据结构

    非原始数据结构的数据关系更加复杂，主要包括：

• Arrays

• Lists

• Files

Arrays

    首先，Python中的数组是一种收集基本数据类型的紧凑方式，数组中的所有条目必须具有相同的数据类型。 但是，与其他编程语言（如C ++或Java）不同，数组在Python中不常用。
    一般来说，当人们在Python中谈论数组时，他们实际上是指List。 但是，它们之间存在根本区别。 对于Python，数组可以被视为存储某种数据列表的更有效方式。 但是，列表里的元素具有相同数据类型。
    在Python中，数组由array模块支持，在使用前需要导入并初始化。 存储在数组中的元素受其数据类型的约束。 数组类型在数组创建期间指定，并使用类型代码指定，类型代码是单个字符，如下例中所示：

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

Lists

    Python中的列表用于存储同类项的集合。 这些是可变的，这意味着您可以在不改变其身份的情况下更改其内容。 您可以通过方括号[和]来识别列表，其中包含以逗号分隔的元素。 列表内置于Python中：您无需单独调用它们。

x = []
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) 
print(list_num)
[1, 2, 45, 6, 7, 2, 90, 23, 435, 11]

• 插入数据

list_num.insert(0, 11)
print(list_num)
[11, 1, 2, 45, 6, 7, 2, 90, 23, 435, 11]

• 删除元素

list_char.remove('o') 
print(list_char)
['c', 'o', 'k', 'i', 'e']

• 根据索引删除元素

list_char.pop(-2) # Removes the item at the specified position
print(list_char)
['c', 'o', 'k', 'e']
list_num.sort()
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]

Array vs List

    你可能想，既然List那么方便，为什么还要Array，这是因为由于Array存储的数据类型一致，可以通过简单的函数完成一些特殊的操作。例如

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数组可以有效地处理大型稀疏数据集。例如:

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)) 
print(multi_arr_ones)
[[ 1.  1.  1.  1.]
 [ 1.  1.  1.  1.]
 [ 1.  1.  1.  1.]]

通常，列表数据结构可以进一步分类为线性和非线性数据结构。 堆栈和队列称为线性数据结构，而图形和树是非线性数据结构。 这些结构及其概念可能相对复杂，但由于它们与现实世界模型的相似性而被广泛使用。

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

Stack

    堆栈是根据Last-In-First-Out（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]

Queue

    队列是根据先进先出（FIFO）原则插入和移除的对象的容器。 在现实世界中排队的一个很好的例子是售票柜台的线路，根据他们的到达顺序上车，因此首先到达的人也是第一个离开的人。
    队列可以有许多不同的类型，但在本教程中仅讨论最基本的类型。 列表实现队列效率不高，因为列表末尾的append（）和pop（）速度很快， 但是，最后插入和从列表开头删除不是那么快，因为它需要元素位置的移动。

Graphs

    数学和计算机科学中的图是由节点组成的网络，节点也称为顶点，它们可以相互连接，也可以不相互连接。 连接两个节点的线或路径称为边。 如果边缘具有特定的流动方向，那么它是有向图，方向边缘被称为弧。 否则，如果未指定方向，则该图形称为无向图。
    这可能听起来非常理论化，当你深入挖掘时会变得相当复杂。 然而，图形是数据科学中特别重要的概念，通常用于模拟现实生活中的问题。 社会网络，化学和生物学的分子研究，地图，推荐系统都依赖于图形和图形理论原理。这有个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')]

    您可以使用Graph做一些很酷的事情，例如尝试找到两个节点之间存在路径，或者找到两个节点之间的最短路径，确定图形中的周期。

    事实上，着名的“旅行商问题”是找到一个最短路径，它只访问每个节点一次并返回起点。 有时图形的节点或弧已经分配了权重或成本，您可以将其视为指定行走难度级别，并且您有兴趣找到最便宜或最简单的路径。

Tree

    现实世界中的一棵树是一种生物，它的根在地上，树枝上有叶子、果实。树的分支以一种有组织的方式展开。在计算机科学中，树被用来描述数据如何被组织，除了根在顶部并且树枝，树叶跟随，向底部蔓延并且树被绘制为与真实树相比被倒置。

    为了引入更多的符号，根始终位于树的顶部。后面的其他节点称为分支，每个分支中的最终节点称为叶。您可以将每个分支想象成一个较小的树本身。根通常称为父节点，它在其下面引用的节点称为子节点。具有相同父节点的节点称为兄弟节点。

    树有助于定义现实世界场景，并且从游戏世界到设计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

Tuples

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

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

Dictionary

    如果你想实现类似于电话簿的东西，字典是要使用的数据结构。 您之前看到的所有数据结构都不适用于电话簿。

    这是一本字典可以派上用场的时候。 字典由键值对组成。

x_dict = {'Edward':1, 'Jorge':2, 'Prem':3, 'Elisa':4}
del x_dict['Elisa']
x_dict
{'Edward': 1, 'Jorge': 2, 'Prem': 3}
x_dict['Edward'] # Prints the value stored with the key 'Kevin'.
1

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

len(x_dict)
3
x_dict.keys()
dict_keys(['Prem', 'Edward', 'Jorge'])
x_dict.values()
dict_values([3, 1, 2])

Sets

    集合是唯一对象的集合。 这些对于创建仅在数据集中包含唯一值的列表很有用。 它是一个无序的集合，但是一个可变的集合。

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'}

Files

    文件传统上是数据结构的一部分。 虽然大数据在数据科学行业中很常见，但是没有存储和检索先前存储的信息的能力的编程语言几乎没有用。在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的数据结构已经有了一个基本的了解了。看完了归看完了，需要勤劳的你动手操练起来呀！