大佬教程收集整理的这篇文章主要介绍了【转译】每个Python开发者都应该掌握的8种数据结构,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
当解决实际编码问题时,每个人都在追求执行时和资源消耗方面的高效率。
选择当前方案中最适合的数据结构,会提升程序性能并且减少执行时间。因此很多大公司在面试的时候都非常注重求职者对数据结构的理解。
数据结构是一种存储和组织数据,使它更容易修改、浏览和访问的代码结构。数据结构决定了数据是如何聚集的、我们能使用的功能和数据之间的关系。
数据结构几乎应用在所有的计算机科学和编程领域,从操作系统到 Web前后端开发再到机器学习。
数据结构可以帮助我们
数据结构是高效解决实际问题的至关重要的一部分,是一种经过反复验证和优化的工具,可以给你提供一种简易的框架来组织你的程序。这样你解决问题的时候,不需要每次重新造轮子。
每种数据结构都有一个与之最匹配的任务或使用情境。Python中有四种内置的数据结构,列表、字典、元组和集合。这些内置结构有一些默认方法,并做了些底层的优化,使他们更好用。
大多数 Python 中的数据结构都修正了这些内置结构的格式或使用它们作为它的基础。
下面我们看看这些结构是如何创造一些高级数据结构的。
@H_801_70@数组/列表 Array/ListPython 中没有内置的 array 类型,但可以使用 List 来实现。数组是一些值的集合,这些值具有相同类型,并保存在同一名称下。
列表中的每个值都叫一个元素,同时具有一个索引,代表它的位置。你可以通过使用列表名和索引值来访问特定的元素,也可以通过 len()
方法获取列表的长度。
不像 Java等静态语言,Python中的列表会自动放大或缩小,当元素增加/减少的时候。
比如,我们可以通过 append()
方法在一个已存在的列表末尾增加一个额外的元素而不需要声明一个新列表。
这使得Python列表更好使用,能动态适应。
cars = ["Toyota", "Tesla", "Hyundai"]
print(len(cars))
cars.append("Honda")
cars.pop(1)
for x in cars:
print(X)
优点
缺点
应用场景
队列是一种线性结构,存储数据时遵循”先进先出”(FIFO)的次序。不像列表,你不能通过索引值访问元素,只能获得最先进去的元素。这个非常适合于一些对次序敏感的任务,比如线上订单处理、语言信箱存储。
我们可以通过list的 append 和 pop 方法实现一个队列。但这样效率不高,因为list在头部增加一个元素的时候需要移动所有的元素。
使用 collections 模块的deque类是个更好的选择。deque优化了append和pop的操作,很容易实现一个双端队列(double-ended queue),可以通过popleft和popright方法访问队列的头尾两端。
from collections import deque
# Initializing a queue
q = deque()
# Adding elements to a queue
q.append('a')
q.append('b')
q.append('c')
print("Initial queue")
print(q)
# Removing elements from a queue
print("\nElements dequeued from the queue")
print(q.popleft())
print(q.popleft())
print(q.popleft())
print("\nQueue after removing elements")
print(q)
# UncommenTing q.popleft()
# will raise an IndexError
# as queue is now empty
优点
缺点
应用场景
栈是一种“后进先出”(LIFO)的队列。最后入栈的元素被认为是在栈顶,是唯一可以访问的元素,想访问中间的元素,必须首先删除足够的元素,以确保指定的元素在栈顶。
许多开发者把栈想象成一堆碟子,你只能在碟子堆顶部添加或移除碟子,如果想把碟子放在底部则必须移除整个栈。
添加元素用 push,删除元素用 pop。可以使用Python内置的list来实现栈,实现时分别使用 append 和 pop 来实现 push和 pop操作。
stack = []
# append() function to push
# element in the stack
stack.append('a')
stack.append('b')
stack.append('c')
print('Initial stack')
print(stack)
# pop() function to pop
# element from stack in
# LIFO order
print('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
print('\nStack after elements are popped:')
print(stack)
# uncommenTing print(stack.pop())
# will cause an IndexError
# as the stack is now empty
优点
缺点
应用场景
链表是一个连续的数据集合,它使用每个数据节点上的关系指针链接到列表中的下一个节点。
不同于数组,链表中没有对象所在的位置,而拥有关系位置,根据包围他们的节点确定。
链表中的第一个节点被称为头结点,最后一个称为尾结点,它有一个空指针。
根据节点是只有一个指向下一个节点的指针还是同时也拥有指向上一个节点的第二个指针,链表可分为单向链表和双向链表。
可以把链表想象成一个链条⛓,单个连接都只与相邻的节点相连,所有的连接一起形成一个更大的结构。
Python没有一个内置的链表实现方式,因此需要你实现一个 Node类来存放节点值和一个或多个指针。
class Node:
def __init__(self, dataval=NonE):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2
# Link second Node to third node
e2.nextval = e3
链表主要用于创建高级数据结构,如图形和树,或者用于需要在结构中频繁添加/删除元素的任务。
优点
缺点
应用场景
标准链表的主要缺点是你始终需要从头节点开始,循环链表通过将尾结点的空指针null替换成头结点,从而解决了这个问题,链表遍历的时候程序会一直跟踪指针,直到它回到它开始的节点。
这样设置的优势是可以从任何节点开始遍历整个链表。它还允许您通过设置结构中所需的循环数,将链表用作可循环结构。循环列表非常适合用于需要长时间循环的处理中,比如操作系统中的CPU分配。
优点
缺点
应用场景
树是另一种基于关系的数据结构,专门用于表示层次关系。同链表一样,树也存在于包含节点值和一个或多个指针的节点对象中。
每个树都包含一个根节点,其他所有节点都从中产生。根节点包含直接跟它相连的节点的指针,这些节点被称为子节点。子节点也可以用于自己的子节点。二叉树的子节点数量不得超过2个。
同一个等级的节点称为同级节点,没有子节点的节点称为叶子节点。
二叉树的最常见的应用是二叉搜索树。二叉搜索树长于搜索大的数据集,时间复杂度取决于树的深度而非节点数量。
二叉搜索树的四个规则
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
def insert(self, data):
# Compare the new value with the parent node
if self.data:
if Data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif Data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
root.PrintTree()
优点
缺点
应用场景
图是一种数据结构,用于表示数据顶点(图的节点 vertex)之间可见的关系,而把顶点连接在一起的叫边(edgE)。
边定义了哪些顶点连接在一起但没有在他们之间指定一个方向。每个顶点都有一些跟其他顶点的连接,这些信息以逗号分隔的list 形式保存在顶点中。
有一些特殊的图称为有向图,它定义了关系的方向,类似于链表。有向图在建立单向关系模型或流程图时非常有用。
它们主要用于用代码形式来传递可视化的web结构网络,这些结构可以模拟不同类型的关系,比如层级结构、分支结构,或者只是一个简单的无序的关系网。图的多功能性和直观性使其成为数据科学的最爱。
书写时,图有分别有一个顶点和边的列表:
V = {a, b, c, d, E}
E = {ab, ac, bd, cd, dE}
Python中,图可以通过一个字典实现,每个顶点作为key,边的列表作为 value。
# Create the Dictionary with graph elements
graph = { "a" : ["b","c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}
# Print the graph
print(graph)
优点
缺点
应用场景
哈希表是一种复杂的数据结构,适合存储大量数据,高效获取指定元素。
这种结构使用 Key/value 对,键是元素的名称而值则是存储在此名称下的数据。
每个输入键都经过一个散列函数,它将其从起始形式转换为一个整数,称为散列。散列函数必须同一输入时总是生成相同的值,必须快速计算,并且长度相同。Python引入了一个内置的hash()
函数,用于提升速度。
哈希表使用散列来查找所需值的一般位置,称为存储桶。程序查找值时只需要搜索这个子组,而不是整个数据池。
超出这个一般框架之外,哈希表还可以根据应用程序的不同而有很大的不同。一些可能允许键值是不同的数据类型,另一些可能有不同设置的桶或不同的散列函数。
import pprint
class Hashtable:
def __init__(self, elements):
self.bucket_size = len(elements)
self.buckets = [[] for i in range(self.bucket_sizE)]
self._assign_buckets(elements)
def _assign_buckets(self, elements):
for key, value in elements: #calculates the hash of each key
hashed_value = hash(key)
index = hashed_value % self.bucket_size # positions the element in the bucket using hash
self.buckets[index].append((key, value)) #adds a tuple in the bucket
def get_value(self, input_key):
hashed_value = hash(input_key)
index = hashed_value % self.bucket_size
bucket = self.buckets[index]
for key, value in bucket:
if key == input_key:
return(value)
return None
def __str__(self):
return pprint.pformat(self.buckets) # pformat returns a printable representation of the object
if __name__ == "__main__":
capitals = [
('France', 'Paris'),
('United States', 'Washington D.C.'),
('Italy', 'Rome'),
('Canada', 'Ottawa')
]
hashtable = Hashtable(capitals)
print(hashtablE)
print(f"The capital of Italy is {hashtable.get_value('Italy')}")
优点
缺点
应用场景
以上是大佬教程为你收集整理的【转译】每个Python开发者都应该掌握的8种数据结构全部内容,希望文章能够帮你解决【转译】每个Python开发者都应该掌握的8种数据结构所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。