Python 中的数据结构和算法

2024 年 8 月 29 日 | 阅读 15 分钟

本课程将作为 Python 数据结构和算法的简单介绍。通过实际且经过充分解释的示例，我们将介绍列表、集合、字典、元组等内置数据结构，以及一些用户自定义数据结构，如链表、树和图，以及一些常用的算法。

列表

同样，与其他编程语言中的数组和 Python 中的列表一样，它们都是以任何方式排列的项的集合。它允许列表中包含多种数据类型的元素。Python 的列表版本可与 C++ 的 vector 或 Java 的 ArrayList 相媲美。由于所有元素都必须重新定位，因此从列表的开头添加或删除元素是最昂贵的操作。如果预先分配的内存已用完，则在列表末尾插入和删除元素也可能变得昂贵。

代码

# Python program to show how to create a Python List and some of its operations

# Creating a Python list
List = ["Python", "Data", "Structures", "Tutorial"]
print("The created Python list is: ")
print(List)
  
# Creating a multi-dimensional list using nested lists (list inside a list)
List_ = [["Python", "Data"], ["Structures", "Tutorial"]]
print("The multi-Dimensional list is: ")
print(List_)
  
# We can access the list of elements using the index of the element
print("Single element: ", List[1])
print("Multiple elements (slicing): ", List[0:2])
print("For nested lists: ", List_[1][0])
  
# We can access elements using negative indices also
      
# printing the last element of the list
print("Last element: ", List_[-1])
      
# Slicing the list using negative indexing
print("Last two elements: ", List[-1:-3:-1]) # Last first order

输出

The created Python list is: 
['Python', 'Data', 'Structures', 'Tutorial']
The multi-Dimensional list is: 
[['Python', 'Data'], ['Structures', 'Tutorial']]
Single element:  Data
Multiple elements (slicing):  ['Python', 'Data']
For nested lists:  Structures
Last element:  ['Structures', 'Tutorial']
Last two elements:  ['Tutorial', 'Structures']

元组

列表和 Python 元组是等效的，但与列表不同，元组是不可变的，这意味着一旦创建，我们就无法更改它们。与列表一样，元组可以包含多种类型的元素。

Python 元组是通过将一系列值组合在一起创建的。这些值由“逗号”分隔，无论是否使用括号。

代码

# Python program to show how to create a Python Tuple and to access its elements

# Creating a Python tuple
Tuple = ("Python", "Data", "Structures", "Tutorial")
print("The Python tuple is: ")
print(Tuple)
      
# Create a tuple using a Python list
list = [3, 6, 2, 7, 4, 5, 3]
print("Tuple using a List: ")
Tuple_ = tuple(list)

# Accessing tuple elements using indices
print("Single element: ", Tuple[1])
print("Multiple elements (slicing): ", Tuple[0:2])
  
# Using negative indexing
      
# printing the last element of the list
print("Last element: ", Tuple[-1])
      
# Trying to modify a tuple
try:
    Tuple[1] = "Tuple"
    print(Tuple)
except Exception as e:
    print("Exception raised: ", e

输出

The Python tuple is: 
('Python', 'Data', 'Structures', 'Tutorial')
Tuple using a List: 
Single element:  Data
Multiple elements (slicing):  ('Python', 'Data')
Last element:  Tutorial
Exception raised:  'tuple' object does not support item assignment

Set

Python 集合数据结构是一种可修改的、非重复的数据集合。集合主要用于成员资格筛选和删除冗余条目。这些过程使用哈希数据结构，这是一种常见的遍历、插入和删除元素的方法，通常需要 O(1) 时间。

代码

# Python program to show how to create a Python Set and its operations

# Creating a Python set
Set = {"Python", "Data", "Structures", "Tutorial"}
print("The Python Set is: ")
print(Set)
  
# Accessing the set elements
for ind, i in enumerate(Set):
    print(ind, i)

# Finding the intersection of two sets
Set_ = {1, 2, "Python", "Data"}
print("Intersection: ", Set.intersection(Set_))

# Union of two sets
print("Union: ", Set.union(Set_))

输出

The Python Set is: 
{'Python', 'Data', 'Tutorial', 'Structures'}
0 Python
1 Data
2 Tutorial
3 Structures
Intersection:  {'Python', 'Data'}
Union:  {1, 2, 'Structures', 'Python', 'Tutorial', 'Data'}

字典

一种称为 Python 字典的键值对格式化数据集合用于存储数据。此数据结构的时间复杂度为 O(1)，与其他编程语言中的哈希表非常相似。Python 字典是使用键索引的。键的值可以是任何类型，即常量项，如字符串、整数、序列等。我们可以使用花括号 {} 或字典推导式来构建字典。

代码

# Python program to show how to create a Python Dictionary and its operations

# Creating a Python Dictionary
Dict = {"1": "Python", "2": "Data", "3": "Structures", "4": "Tutorial"}
print("The Python Dictionary is: ")
print(Dict)
  
# accessing the dictionary element using the keys
print("Value of key 2 is: ", Dict["2"])
  
# accessing the elements using the built-in get method
print("Using the get method: ", Dict.get("2"))

输出

The Python Dictionary is: 
{'1': 'Python', '2': 'Data', '3': 'Structures', '4': 'Tutorial'}
Value of key 2 is:  Data
Using the get method:  Data

链表

链表是一种线性数据结构，其元素不存储在内存的连续位置。链表的元素通过指针连接。

指向链表第一个节点的指针用于表示链表。head 指的是顶节点。如果链表为空，则 head 的值为 NULL。在列表中，每个节点至少包含两个组件

数据
指向下一个节点的指针（或引用）

代码

# Python program to show the implementation of the linked list

# Creating a node class
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

# Creating a linked list class
class LinkedList:
    def __init__(self):
        self.head = None

# Initializing a linked list
list_ = LinkedList()

# Creating the nodes
list_.head = Node("Python")
second_node = Node("Tutorial")
third_node = Node("Data Structures")

# Connecting the nodes
list_.head.next = second_node
second_node.next = third_node

# Printing the linked list
while list_.head != None:
    print(list_.head.value, end = "\n")
    list_.head = list_.head.next

输出

Python
Tutorial
Data Structures

链表是重要的数据结构。以下是链表的一些基本操作。

代码

# Python programs to show linked list operations 

# Creating a node class
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

# Creating a linked list class
class Linked_List:
    def __init__(self):
        self.head = None

    # Inserting a node at the beginning of the list
    def insertInBeginning(self, value):
        insertion_node = Node(value)
        insertion_node.next = self.head
        self.head = insertion_node

    # Inserting a node after a particular node
    def insertAfterNode(self, previous_node, value):
        if previous_node is None:
            print("There is no previous node. Make a new head.")
            return

        insertion_node = Node(value)
        insertion_node.next = previous_node.next
        previous_node.next = insertion_node

    # Inserting the node at the end of the list
    def insertInEnd(self, value):
        insertion_node = Node(value)

        if self.head is None:
            self.head = insertion_node
            return

        last_node = self.head
        while (last_node.next):
            last_node = last_node.next

        last_node.next = insertion_node

    # Deleting a particular node 
    def deleteANode(self, pos):

        if self.head is None:
            return

        temporary = self.head

        if pos == 0:
            self.head = temporary.next
            temporary = None
            return

        # Finding the key which is to be deleted
        for i in range(pos - 1):
            temporary = temporary.next
            if temporary is None:
                break

        # If the key is not in the list
        if temporary is None:
            return

        if temporary.next is None:
            return

        next_ = temporary.next.next

        temporary.next = None

        temporary.next = next_

    # Searching an element in the list
    def search(self, key):

        current_node = self.head

        while current_node is not None:
            if current_node.value == key:
                return True

            current_node = current_node.next

        return False

    # Sorting the linked list
    def sortList(self, head):
        current_node = head
        index_node = Node(None)

        if head is None:
            return
        else:
            while current_node is not None:
                index_node = current_node.next

                while index_node is not None:
                    if current_node.value > index_node.value:
                        current_node.value, index_node.value = index_node.value, current_node.value

                    index_node = index_node.next
                current_node = current_node.next

    # Printing the linked list
    def printLinkedList(self):
        temporary = self.head
        while (temporary):
            print(str(temporary.value) + " ", end = "")
            temporary = temporary.next


if __name__ == '__main__':

    listt = Linked_List()
    listt.insertInEnd(7)
    listt.insertInBeginning(4)
    listt.insertInBeginning(9)
    listt.insertInEnd(2)
    listt.insertAfterNode(listt.head.next, 8)

    print('Linked list:')
    listt.printLinkedList()

    print("\nAfter deleting a node:")
    listt.deleteANode(2)
    listt.printLinkedList()

    value_to_find = 4
    if listt.search(value_to_find):
        print("\n", value_to_find, "is found in the list")
    else:
        print("\n", value_to_find, " is not found in the list")

    listt.sortList(listt.head)
    print("Sorted Linked List: ")
    listt.printLinkedList()

输出

Linked list:
9 4 8 7 2 
After deleting a node:
9 4 7 2 
 4 is found in the list
Sorted Linked List: 
2 4 7 9

Stack

栈是一种线性数据结构，它使用先进后出 (FILO) 或后进先出 (LIFO) 的顺序来存储对象。在栈中，一个项目仅从一端删除，而新项目则添加到另一端。Push 和 Pop 是插入和删除操作的常用名称。

栈的基本操作

我们可以使用一些基本操作对栈执行各种活动。

Push：此方法将一个项目添加到栈顶

Pop：此方法将从栈顶删除一个项目

IsEmpty：此方法检查栈是否为空。

IsFull：此方法检查栈是否已满。

Peek：此方法将返回栈顶元素而不删除它。

代码

# Python program to show how to create a stack and implement the operations

# Creating a stack
def create():
    new_stack = []
    return new_stack

# To check if it is an empty stack
def check(stack):
    if len(stack) == 0:
        return True
    else:
        return False


# Adding new elements to the stack
def push(stack, value):
    stack.append(value)
    print("New stack after pushing: ", stack)


# Eleminating an item from the stack
def pop(stack):
    if (check(stack)):
        return "Given Stack is Empty."
    stack.pop()
    print("New stack after popping: ", stack)
    
# Peeking into the stack
def peek(stack):
    print("Last element of the stack: ", stack[-1])

# Driver code for the above methods
stack = create()
push(stack, 2)
push(stack, 5)
push(stack, 3)
push(stack, 1)
pop(stack)
peek(stack)

输出

New stack after pushing:  [2]
New stack after pushing:  [2, 5]
New stack after pushing:  [2, 5, 3]
New stack after pushing:  [2, 5, 3, 1]
New stack after popping:  [2, 5, 3]
Last element of the stack:  3

Queue

队列是另一种与栈相似的线性数据结构，它以先进先出 (FIFO) 的顺序存储对象。队列以我们最近添加项目的顺序移除项目。任何用户等待访问服务的队列，其中最先到达的用户最先得到服务，都是队列的一个绝佳示例。

与队列相关的操作包括

Enqueue：将内容添加到队列。当队列已满时，定义溢出条件。将元素添加到队列的时间复杂度：O(1)

Dequeue：从队列中移除一个项目。项目的弹出顺序与入队顺序相同。如果队列为空，则称为下溢条件。获取队列的第一个项目的时间复杂度为 O(1)。

Rear：获取队列中的最后一个项目。获取队列最后一个项目的时间复杂度为 O(1)。

代码

# Python program to create a queue and implement operations of a queue

# Creating a class for queue
class Queue:
    # Initializing a queue
    def __init__(self):
        self.queue = []

    # Adding an element to the queue
    def enqueue(self, element):
        self.queue.append(element)
        print("New queue after enqueuing: ", self.queue)
        
    # Removing an element to the queue
    def dequeue(self):
        if len(self.queue) == 0:
            return None
        else: return self.queue.pop(0)
        print("New queue after dequeuing: ", self.queue)
        
    def rear(self):
        print("Last element: ", self.queue[-1])

# Drivers code for the above methods
queue = Queue()
queue.enqueue(6)
queue.enqueue(3)
queue.dequeue()
queue.enqueue(9)
queue.rear()

输出

New queue after enqueuing:  [6]
New queue after enqueuing:  [6, 3]
New queue after enqueuing:  [3, 9]
Last element:  9

堆

Python heapq 模块提供了堆数据结构，它主要用于描述优先队列。堆数据结构的特点是，每次弹出项目时，它总是返回最小的项目（最小堆）。在保持堆结构的同时，始终推送或弹出项目。此外，heap[0] 项始终返回最小值。它允许以 O(log n) 的时间检索和插入最小元素。

堆通常有两种类型

最大堆：最大堆数据结构根节点的键必须高于其子节点的键。对于二叉树中的每个子树，相同的条件应递归成立。

最小堆：最小堆的根节点的键应该是所有子节点键的最小键。对于二叉树中的每个子树，相同的条件应递归成立。

代码

# Python program to implement a heap data structure in Python

# Defining a method to create a heap
def heapify(array, n, j):
    largest = j
    a = 2 * j + 1
    b = 2 * j + 2 
    
    if a < n and array[j] < array[a]:
        largest = a
    
    if b < n and array[largest] < array[b]:
        largest = b
    
    if largest != j:
        array[j],array[largest] = array[largest], array[j]
        heapify(array, n, largest)

def insert_element(array, value):
    s = len(array)
    if s == 0:
        array.append(value)
    else:
        array.append(value);
        for j in range((s//2)-1, -1, -1):
            heapify(array, s, j)

def delete(array, value):
    s = len(array)
    for j in range(0, s):
        if s == array[j]:
            break
        
    array[j], array[s - 1] = array[s - 1], array[j]

    array.remove(value)
    
    for j in range((len(array)//2)-1, -1, -1):
        heapify(array, len(array), j)

# Drivers code for the above methods
heap = []

insert_element(heap, 3)
insert_element(heap, 6)
insert_element(heap, 5)
insert_element(heap, 4)
insert_element(heap, 8)

print("Heap array: ", heap)

delete(heap, 5)
print("After deleting an item: ", heap)

输出

Heap array:  [6, 4, 5, 3, 8]
After deleting an item:  [8, 4, 6, 3]

二叉树

树是一种非线性分层数据结构，由节点和边组成。

一种称为二叉树的 Python 树数据结构允许每个父节点最多有两个子节点。二叉树在每个节点处有三个组件

数据元素
左子节点的地址
右子节点的地址

代码

# Python program to show how to create a binary tree and traverse it in Python

# Creating a class for a Node of the tree
class Node:
    def __init__(self, value):
        self.left = None
        self.val = value
        self.right = None

    # Method to transverse in a pre-order manner
    def traverseAsPreOrder(self):
        print(self.val, end = ' ')
        if self.left != None:
            self.left.traverseAsPreOrder()
        if self.right != None:
            self.right.traverseAsPreOrder()

    # Method to transverse in an in-order manner
    def traverseAsInOrder(self):
        if self.left != None:
            self.left.traverseAsInOrder()
        print(self.val, end = ' ')
        if self.right != None:
            self.right.traverseAsInOrder()

    # Method to transverse in an post-order manner
    def traverseAsPostOrder(self):
        if self.left != None:
            self.left.traverseAsPostOrder()
        if self.right != None:
            self.right.traverseAsPostOrder()
        print(self.val, end = ' ')

# Drivers code for the above binary tree class
root_node = Node(4)

root_node.left = Node(5)
root_node.right = Node(7)
root_node.right.left = Node(2)
root_node.right.left.right = Node(9)
root_node.left.right = Node(0)
root_node.left.left = Node(10)
root_node.left.left.right = Node(1)

# Transferring the tree
print("Pre-order traversal of the tree: ", end = "")
root_node.traverseAsPreOrder()
print("\nIn-order traversal of the tree: ", end = "")
root_node.traverseAsInOrder()
print("\nPost-order traversal of the tree: ", end = "")
root_node.traverseAsPostOrder()

输出

Pre-order traversal of the tree: 4 5 10 1 0 7 2 9 
In-order traversal of the tree: 10 1 5 0 4 2 9 7 
Post-order traversal of the tree: 1 10 0 5 9 2 7 4

冒泡排序算法

一种称为冒泡排序的排序方法，它分析两个相邻的项，然后交换它们，直到达到所需的顺序。

在每次迭代中，列表的每个元素都会移动到列表的末尾。这类似于液体中的气泡浮到表面的行为。因此，它被称为冒泡排序。

代码

# Python program to implement Bubble Sort Algorithm 

# Creating a method to perform bubble sort
def bubbleSort(listt):
    
  # looping over each element of the list
  for c in range(len(listt)):

    # looping over remaining elements to compare with the current element
    for n in range(0, len(listt) - c - 1):

        # comparing the two adjacent elements
        # we are sorting in descending order 
        if listt[n] < listt[n + 1]:

            # Swapping the two elements if they are not in the correct order
            temporary = listt[n]
            listt[n] = listt[n + 1]
            listt[n + 1] = temporary

# Drivers code for the above method
listt = [3, 7, 9, 2, 5, 0]

bubbleSort(listt)

print('Sorted List in Descending Order:')
print(listt)

输出

Sorted List in Descending Order:
[9, 7, 5, 3, 2, 0]

选择排序算法

一种称为选择排序的排序算法，它在每次迭代中选择未排序列表中的最大元素，并将其插入列表的开头。

代码

# Python program to implement Selection Sort 

# Defining a method to perform Selection Sort
def selectionSort(listt, size):
   
    for s in range(size):
        max_index = s

        for i in range(s + 1, size):
         
            # We are sorting in descending order
            # Selecting the maximum element of the listt
            if listt[i] > listt[max_index]:
                max_index = i
         
        # putting the maximum value at the beginning of the list
        (listt[s], listt[max_index]) = (listt[max_index], listt[s])

# Drivers code
listt = [20, 35, 29, 85, 23, 97]
size = len(listt)
selectionSort(listt, size)
print('Sorted List in Descending Order:')
print(listt)

输出

Sorted List in Descending Order:
[97, 85, 35, 29, 23, 20]

快速排序算法

在称为快速排序的排序算法中，使用分治策略将数组分割成更小的子数组（从数组中选取一个项）。

在分割给定数组时，枢轴元素应设置得使大于枢轴元素的项位于右侧，而小于枢轴值的项则存储在左侧。

使用相同的方法来分割右子数组和左子数组。重复此过程，直到每个子数组只剩下一个元素。

此时，元素已排序。项目组合最终会创建一个排序数组。

代码

# Python program to perform Quick Sort Algorithm

# Defining a function to search for the pivoting position
def pivot(listt, low, high):

  # selecting the right-most element as a pivot
  pivot = listt[high]

  # the greater item
  g = low - 1

  # transversing through all the elements
  for i in range(low, high):
    if listt[i] <= pivot:
      # if the value of j is smaller, we will swap it with the pointer g
      g = g + 1

      # swap the elements at g and i
      (listt[g], listt[i]) = (listt[i], listt[g])

  # swapping the pivot with the element of greater value
  (listt[g + 1], listt[high]) = (listt[high], listt[g + 1])

  # returning the position from where the pivot is done
  return g + 1

# defining a function to perform Quick Sort
def quickSortAlgo(listt, low, high):
    if low < high:

        # searching the pivot for which elements on its left are smaller and elements on its right are greater
        p = pivot(listt, low, high)

        # calling left pivot recursively
        quickSortAlgo(listt, low, p - 1)

        # calling right pivot recursively
        quickSortAlgo(listt, p + 1, high)

# Drivers code
listt = [3, 7, 2, 4, 9, 1, 0, 8]

size = len(listt)

quickSortAlgo(listt, 0, size - 1)

print('Sorted List in Ascending Order:')
print(listt)

输出

Sorted List in Ascending Order:
[0, 1, 2, 3, 4, 7, 8, 9]

计数排序算法

一种称为计数排序的排序方法，它根据给定数组中每个不同元素出现的次数来排列给定数组的元素。排序是通过将数组元素的计数映射到我们创建的另一个数组的索引来完成的。此数组存储元素的计数。

代码

# Python program to perform Counting Sort

# Defining a function to perform Counting Sort
def countingSort(listt):
    s = len(listt)
    o = [0] * size

    # Initializing the counting list
    c = [0] * 10

    # Creating a list of counts of the elements
    for i in range(0, s):
        c[listt[i]] += 1

    # Storing the cumulative count
    for j in range(1, 10):
        c[j] += c[j - 1]

    # Finding the indices of every item of the initial list in the count list
    # placing the elements in the counting list
    j = s - 1
    while j >= 0:
        o[c[listt[j]] - 1] = listt[j]
        c[listt[j]] -= 1
        j -= 1

    # Copying the sorted list elements into the original list
    for k in range(0, s):
        listt[k] = o[k]

# Drivers code
listt = [3, 7, 9, 2, 4, 7, 2, 8]
countingSort(listt)
print("Sorted list: ")
print(listt)

输出

Sorted list: 
[2, 2, 3, 4, 7, 7, 8, 9]

二分查找算法

二分查找是一种在已排序数组中查找元素位置的搜索算法。

在此方法中，元素始终在数组某一部分的中间进行搜索。

代码

# Python program to perform the Binary Search

# Defining a function to perform Binary Search
def binarySearch(listt, e, l, h):

    # We will use two pointers iteration to find the element
    while l <= h:

        mid_element = l + (h - l)//2

        if listt[mid_element] == e:
            return mid_element

        elif listt[mid_element] < e:
            l = mid_element + 1

        else:
            h = mid_element - 1

    return -1

# Drivers code
listt = [4, 2, 7, 6, 7, 8, 1, 9, 0, 5]
e = 7

index = binarySearch(listt, e, 0, len(listt)-1)

if index != -1:
    print("The element we searched for is present at: " + str(index))
else:
    print("Not found")

输出

The element we searched for is present at: 4

下一个主题使用 Tkinter 在 Python 中创建 GUI 来关闭、重启和注销计算机

Python 中的数据结构和算法

列表

元组

Set

字典

链表

Stack

Queue

堆

二叉树

冒泡排序算法

选择排序算法

快速排序算法

计数排序算法

二分查找算法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Python 问题

Python 中的数据结构和算法

列表

元组

Set

字典

链表

Stack

Queue

堆

二叉树

冒泡排序算法

选择排序算法

快速排序算法

计数排序算法

二分查找算法

相关帖子

Python 程序检查两个字符串是否是彼此的字谜

Python 程序计算复利

Python 按位异或运算符

使用随机森林进行时间序列预测

PyDev 是什么

如何在 Python 中使用 pass 语句

使用 PyQt5 在 Python 中制作数字时钟

Python 程序打印帕斯卡三角形

字符串转整数

Python 采购分析项目

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器