Python 数据结构与算法入门

本文是《Python 101：现代 Python 入门》的续篇，在前文中我们介绍了 Python 的基本概念、设置方法并给出了一些基础知识。本文将讨论 Python 中的各种数据结构，例如列表、字典、元组、集合、队列、栈、链表等等。

什么是数据结构？

这是计算机中组织数据的一种特殊方式，以便能够有效地访问/使用/处理数据。

什么是数据算法？

这是执行任务、履行义务或解决问题的一系列有限步骤/指令。
它的重要性在于，它可以帮助人们估算实施过程中所需的资源量。

Python中的数据结构类型

Python 中的数据结构分为 2 类：

• 内置数据结构：这些类型的数据结构包括lists，，，。dictionariestuplessets
• 用户自定义数据结构：这类数据结构包括queues、stack、、和。linked listtreelinked-listgraphHashMap

它们还可以分为线性数据结构或非线性数据结构，其中线性数据结构中的数据是按顺序排列的，例如列表、链表、队列、栈等；而非线性结构中，一个元素或节点连接到“n”个元素，例如树和图。

列表

Python 列表与其它语言中的数组类似，都是有序的数据集合。它非常灵活，因为列表中的元素不需要是同一类型。

Python List 的实现方式与 Java 中的 ArrayList 类似。耗时的操作是从列表开头插入或删除元素，因为需要移动列表中的所有元素。这两个操作的时间复杂度通常为 O(n)，也就是说列表越大，耗时越长。

Python 中列表的示例如下所示。

Python 3.9.9 (main, Dec 16 2021, 23:13:29) 
[GCC 11.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> mylist = ["Jeff", 44, 2.3, "Ous"]
>>> print(mylist)

输出

['Jeff', 44, 2.3, 'Ous']

列表元素通过指定的索引访问。列表的起始索引是 ` 0n`，结束索引是`n`，n-1其中 `n` 是元素的数量。
例如，要访问上面示例中的 `Jeff`，我们使用 `0`，
print(mylist[0])这将输出 ` n` Jeff，而` print(mylist[2])n` 将输出 `n` 2.3。
添加元素

append()可以使用 `append ()` 、`extend()`extend()和`insert() insert()` 函数向列表中添加元素。`append
()`
函数会将所有传入的元素合并为一个元素添加到列表中。`extend()` 函数会将元素逐个添加到列表中。`insert
()`函数会将传入的元素添加到列表中，并同时增加列表的大小。

mylist.append(12)
mylist.extend("Smart")
mylist.insert(1, "Lux")
print(mylist)

输出：

['Jeff', 'Lux', 44, 2.3, 'Ous', 12, 'S', 'm', 'a', 'r', 't']

与 List 相关的其他方法包括del()for deletion、len()function returns the length of the list、index()function（finds the index value of value passed它已遇到）、count()functionfinds the count of the value passed to it和functions sorted()，并且具有返回类型，而 sort() 会修改原始列表。sort()sort the values of the listsorted()

字典

字典用于存储键值对。它是一个无序的数据值集合，类似于映射，用于存储数据值。字典中提供键值对是为了提高其性能优化。

Python 字典的索引是通过键来实现的。键可以是任何可哈希类型。我们可以使用花括号 ( {}) 或dictionary.

示例代码：

Python 3.9.9 (main, Dec 16 2021, 23:13:29) 
[GCC 11.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> dictionary = {1: "Jeff Odhiambo",2:"Lux Academy",3:"Laurent Ous"}
>>> print(dictionary)

输出：

{1: 'Jeff Odhiambo', 2: 'Lux Academy', 3: 'Laurent Ous'}

要访问字典中的各个元素，我们可以使用键，例如，我们可以使用它1来访问，Jeff Odhiambo例如运行print(dictionary.get(<key>))，即print(dictionary.get(1))会打印Jeff Odhiambo，print(dictionary.get(2))会打印Lux Academy。

>>> print(dictionary.get(1))
Jeff Odhiambo
>>> print(dictionary.get(2))
Lux Academy 
>>> print(dictionary.get(3))
Laurent Ous
>>> 

元组

元组是 Python 中的一种不可变数据类型，它在索引和允许重复成员方面与 Python 中的列表非常相似。它存储以逗号分隔的 Python 对象。
以下示例展示了如何在 Python 中创建或声明元组。

>>> tuple1=("Jeff","LUX")
>>> tuple2=(23,78)
>>> print(tuple1+tuple2)

输出

('Jeff', 'LUX', 23, 78)
>>> 

访问元组元素与访问列表类似，我们可以使用索引访问元组中的元素。我们可以指定索引值，它会返回存储在该索引处的元素。例如，`{{ 元组 } }`print(tuple1[0])将输出 ` {{ 元组 } }` Jeff。
其他操作，例如slicing使用切片运算符 `{{元组 } } :`、changing` concatenating{{ 元组 } }` 等，deletion也可以对元组执行。

套

集合是一种数据类型，它由一系列无序元素组成。这些元素可以是任何数据类型，也就是说，它们不依赖于特定的数据类型。集合是可变的（可以更改），并且不会包含重复的元素副本。集合的值没有索引，因此不能对集合执行索引操作。

示例代码：

>>> set1={1.2,56,"Jeff",'G'}
>>> print(set1)
{56, 1.2, 'Jeff', 'G'}

当你尝试使用集合中的索引访问对象时，你会得到'set' object is not subscriptable,这样的结果，这证实了索引操作不能对集合执行。

>>> print(set1[1])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'set' object is not subscriptable
>>> 

由于无法使用索引访问集合中的值，我们可以遍历该集合来访问元素并显示它们，如下所示。

>>> for setvalues in set1:
...     print(setvalues)
... 
56
1.2
Jeff
G
>>> 

我们还可以使用该方法、在集合中使用、以及函数等add values进行设置。update()remove itemsremove()discard()pop()

队列

队列也是一种线性数据结构，它以先进先出（FIFO）的方式存储元素。在队列中，最近添加的元素会最先被移除。队列的一个很好的例子是操作系统中的一种称为FIFO的算法，其中队列中第一个进程会最先被执行。或者在现实生活中，在银行排队办理业务时，也会按照先到先得的原则为您服务。

与队列相关的操作

Enqueue：向队列中添加一个元素。
Dequeue：从队列中移除一个元素。
Front：获取队列首元素。
Rear：获取队列末元素。

使用列表实现

┌──(jeff㉿kali)-[~]
└─$ python3 
Python 3.9.9 (main, Dec 16 2021, 23:13:29) 
[GCC 11.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> queue = []
>>> queue.append("Jeff")
>>> queue.append("12")
>>> queue.append("LUX")
>>> queue.append(45.7)
>>> print(f"Initial Queue is {queue}")
Initial Queue is ['Jeff', '12', 'LUX', 45.7]
>>> queue.pop(0)
'Jeff'
>>> queue.pop(0)
'12'
>>> queue.pop(0)
'LUX'
>>> queue.pop(0)
45.7
>>> print(f"Queue after removing element: {queue}")
Queue after removing element: []
>>> 

堆

栈是一种线性数据结构，它以按顺序存储元素。在栈中，新元素添加到现有元素之上，例如，将元素 1 添加到元素 2 之上；删除元素时，必须从最顶层的元素开始，例如，先删除元素 1，再删除元素 2。插入和删除操作通常分别称为 push 和 pop。Last-In/First-Out (LIFO)First-In/Last-Out (FILO)

与堆栈相关的操作：

empty()– 返回栈是否为空。
size()– 返回栈的大小。
top()– 返回栈顶元素的引用。
push(a)– 将元素 'a' 插入栈顶。
pop()– 删除栈顶元素。

使用列表实现

>>> stack = []
>>> stack.append("Jeff")
>>> stack.append("12")
>>> stack.append("LUX")
>>> stack.append(45.7)
>>> print(f"Initial stack : {stack}")
Initial stack : ['Jeff', '12', 'LUX', 45.7]
>>> stack.pop()
45.7
>>> stack.pop()
'LUX'
>>> stack.pop()
'12'
>>> stack.pop()
'Jeff'
>>> print(f"Stack after elements are removed : {stack}")
Stack after elements are removed : []
>>> 

链表

链表是由一系列数据元素通过链接连接而成的序列。每个数据元素都包含一个指向其他数据元素的指针，如下图所示。链表 有四种类型：

• 单链表。
• 双向链表。
• 循环链表。
• 循环双向链表。

链表的实现

class Node:
    def __init__(self, data):
        self.data = data  # Assign data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def printList(self):
        temp = self.head
        while (temp):
            print (temp.data)
            temp = temp.next

if __name__=='__main__':
    linked_list = LinkedList()

    linked_list.head = Node("Jeff")
    second = Node(27)
    third = Node("LUX")

    linked_list.head.next = second;
    second.next = third;

    linked_list.printList()

输出

Jeff
27
LUX