Python数据结构详细

Python数据结构详细攻略

什么是数据结构?

数据结构是计算机中存储、组织数据的方式。常见的数据结构有数组、链表、栈、队列、哈希表、树和图等。不同的数据结构适用于不同的场景,通过选择合适的数据结构能够提高程序的效率和性能。

数组(Array)

数组是一种线性数据结构,它是一组连续的内存空间,用来存储同类型的数据。数组中的元素可以被通过下标访问,下标通常从0开始,用来表示元素在数组中的位置。

示例:

# 定义数组
numbers = [1, 2, 3, 4, 5]

# 访问数组元素
print(numbers[0]) # 输出1
print(numbers[2]) # 输出3

# 修改数组元素
numbers[2] = 6
print(numbers) # 输出[1, 2, 6, 4, 5]

链表(Linked List)

链表也是一种线性数据结构,不同的是它的元素不是存储在连续空间中,而是通过指针相连,形成一个链式结构,链表中的每个节点都包含数据元素和指向下一个节点的指针。

示例:

# 定义链表节点
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 定义链表
class MyLinkedList:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.head = None

    def get(self, index: int) -> int:
        """
        Get the value of the index-th node in the linked list. If the index is invalid, return -1.
        """
        if index < 0 or not self.head:
            return -1
        p = self.head
        for i in range(index):
            p = p.next
            if not p:
                return -1
        return p.val

    def addAtHead(self, val: int) -> None:
        """
        Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
        """
        self.head = ListNode(val, self.head)

    def addAtTail(self, val: int) -> None:
        """
        Append a node of value val to the last element of the linked list.
        """
        if not self.head:
            self.head = ListNode(val)
        else:
            p = self.head
            while p.next:
                p = p.next
            p.next = ListNode(val)

    def addAtIndex(self, index: int, val: int) -> None:
        """
        Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
        """
        if index <= 0:
            self.addAtHead(val)
        else:
            p = self.head
            for i in range(index-1):
                p = p.next
                if not p:
                    return
            p.next = ListNode(val, p.next)

    def deleteAtIndex(self, index: int) -> None:
        """
        Delete the index-th node in the linked list, if the index is valid.
        """
        if index < 0 or not self.head:
            return
        if index == 0:
            self.head = self.head.next
            return
        p = self.head
        for i in range(index-1):
            p = p.next
            if not p:
                return
        if p.next:
            p.next = p.next.next

# 测试链表操作
obj = MyLinkedList()
obj.addAtIndex(0, 1)
obj.addAtIndex(1, 2)
obj.addAtIndex(2, 3)
print(obj.get(1)) # 输出2
obj.deleteAtIndex(1)
print(obj.get(1)) # 输出3

栈(Stack)

栈是一种先进后出(FIFO)的数据结构。它支持两个操作:入栈(push)和出栈(pop)。在栈中,只能在栈顶进行插入和删除操作。

示例:

# 使用Python的列表(list)实现栈
class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()

    def is_empty(self):
        return len(self.stack) == 0

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]

    def size(self):
        return len(self.stack)

# 测试栈操作
s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.peek()) # 输出3
s.pop()
print(s.peek()) # 输出2

队列(Queue)

队列是一种先进先出(FIFO)的数据结构。它支持两个操作:入队列(enqueue)和出队列(dequeue)。在队列中,只能在队列尾进行插入操作,在队列头进行删除操作。

示例:

# 使用Python的列表(list)实现队列
class Queue:
    def __init__(self):
        self.queue = []

    def is_empty(self):
        return len(self.queue) == 0

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)

    def size(self):
        return len(self.queue)

# 测试队列操作
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.size()) # 输出3
print(q.dequeue()) # 输出1
print(q.dequeue()) # 输出2

哈希表(Hash Table)

哈希表是一种通过哈希函数将关键字映射到表中位置来实现数据的快速查找的数据结构。哈希表包含一个数组和一个哈希函数,通过哈希函数将关键字映射到数组中的位置,然后在这个位置上存储数据。

示例:

# 使用Python内置哈希表字典(dict)实现哈希表
class HashTable:
    def __init__(self):
        self.table = {}

    def put(self, key, value):
        self.table[key] = value

    def get(self, key):
        return self.table.get(key, -1)

    def remove(self, key):
        if key in self.table:
            del self.table[key]

# 测试哈希表操作
ht = HashTable()
ht.put(1, 'A')
ht.put(2, 'B')
ht.put(3, 'C')
print(ht.get(2)) # 输出B
ht.remove(2)
print(ht.get(2)) # 输出-1

树(Tree)

树是一种非线性的数据结构,它由节点和边组成。每个节点包含一个数据元素和指向其子节点的指针。根节点是整个树的唯一入口。

示例:

# 定义树节点
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 定义二叉搜索树(Binary Search Tree, BST)
class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
        else:
            current_node = self.root
            while True:
                if val < current_node.val:
                    if not current_node.left:
                        current_node.left = TreeNode(val)
                        break
                    else:
                        current_node = current_node.left
                else:
                    if not current_node.right:
                        current_node.right = TreeNode(val)
                        break
                    else:
                        current_node = current_node.right

    def search(self, val):
        current_node = self.root
        while current_node:
            if current_node.val == val:
                return True
            elif val < current_node.val:
                current_node = current_node.left
            else:
                current_node = current_node.right
        return False

# 测试树操作
bst = BST()
bst.insert(5)
bst.insert(3)
bst.insert(7)
print(bst.search(3)) # 输出True
print(bst.search(6)) # 输出False

图(Graph)

图是一种由节点和边组成的非线性数据结构。节点表示图中的元素,边表示图中元素之间的关系。图可以分为有向图和无向图,有向图表示边有方向,无向图表示边没有方向。

示例:

# 定义有向图
graph = {
    'A': ['B', 'C'],
    'B': ['C', 'D'],
    'C': ['D'],
    'D': ['C'],
    'E': ['F'],
    'F': ['C']
}

# 实现深度优先搜索(DFS)
visited = set() # 用set来记录已经遍历的节点集合

def dfs(graph, node):
    if node not in visited: # 如果节点没有遍历过
        visited.add(node) # 将节点加入已遍历集合
        for neighbor in graph[node]: # 遍历所有邻接点
            dfs(graph, neighbor)

dfs(graph, 'A') # 遍历整个图

# 实现广度优先搜索(BFS)
from queue import Queue

def bfs(graph, start):
    visited = set() # 用set来记录已经遍历的节点集合
    q = Queue()
    q.put(start) # 将起始节点加入队列
    visited.add(start) # 将起始节点加入已遍历集合
    while not q.empty():
        node = q.get()
        print(node)
        for neighbor in graph[node]: # 遍历所有邻接点
            if neighbor not in visited: # 如果节点没有遍历过
                visited.add(neighbor) # 将节点加入已遍历集合
                q.put(neighbor) # 将节点加入队列

bfs(graph, 'A') # 遍历整个图

结论

以上就是Python中常见的基本数据结构的详细介绍和示例代码,希望能够对大家编程学习有所帮助。根据不同的场景需要,选择合适的数据结构能够提高程序的效率和性能。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Python数据结构详细 - Python技术站

(0)
上一篇 2023年5月13日
下一篇 2023年5月13日

相关文章

  • Python SVM(支持向量机)实现方法完整示例

    Python SVM(支持向量机)实现方法完整示例 本文介绍如何使用Python实现SVM(支持向量机)分类器。将会涵盖以下内容: SVM的基本概念 SVM的实现方法 SVM的参数调整 实现一个SVM分类器的完整示例 SVM的基本概念 SVM是一种强有力的、灵活的、可用于分类、回归和异常检测的机器学习算法。SVM基于找到一个最优的超平面来区分两个或多个类别。…

    python 2023年5月18日
    00
  • Python微信库:itchat的用法详解

    Python微信库:itchat的用法详解 介绍 itchat是一个基于网页版微信实现的开源Python微信库,可以帮助我们实现简单的微信自动回复、微信信息获取、微信发送等功能。同时,itchat还支持Python3.x版本。 安装 我们可以使用pip命令安装itchat,具体命令如下: pip install itchat 登录微信 使用itchat登录微…

    python 2023年6月2日
    00
  • Python安装spark的详细过程

    安装Python并不是安装Spark的必需步骤,因为Python和Spark是两个独立的组件。但是,安装Python是进行数据分析、数据处理和机器学习时常用的一个语言。因此,我们在这里提供一个Python安装Spark的详细过程攻略。 安装Python 首先,我们需要在计算机上安装Python。Python有两个主要版本:Python 2和Python 3。…

    python 2023年5月14日
    00
  • 使用python求解二次规划的问题

    二次规划是一种经典优化问题,可用于各种领域的建模。Python语言提供了一些强大的库,如cvxopt、qpOASES等,可用于求解二次规划问题。本文将介绍如何使用cvxopt库来求解二次规划问题,并给出两个具体的示例说明。 安装cvxopt cvxopt是一个Python库,提供了许多数学优化功能,如线性规划、二次规划、凸优化等。在本文中,我们将使用cvxo…

    python 2023年5月30日
    00
  • Python time库的时间时钟处理

    让我针对Python time库的时间时钟处理,给大家详细讲解一下。 Time库简介 time库是Python中的标准库之一,它提供了关于时间的各种函数,并且常常用于计算机程序的时间统计、任务调度、日期处理等方面。其中,最常用的函数有:time(), localtime(), strftime(),功能分别为获取当前时间戳、将时间戳转化为本地时间、将时间格式…

    python 2023年6月2日
    00
  • python实现测试工具(一)——命令行发送get请求

    Python实现测试工具(一)——命令行发送GET请求 在进行Web开发或API开发时,我们需要对接口进行测试,以确保其正常工作。Python提供了丰富的库和工具,可以帮助我们实现接口测试。本文将介绍如何使用Python实现一个命令行工具,用于发送GET请求并输出响应结果。 实现步骤 步骤一:安装requests库 在Python中,我们可以使用reques…

    python 2023年5月15日
    00
  • python快速查找算法应用实例

    下面是详细讲解“Python快速查找算法应用实例”的完整攻略。 快速查找算法 快速查找算法(Binary Search)是一种高效的查找算法,它的基本思想是将查找区间不断缩小,直到找到目标元素或者确定目标元素不存在。快速查找算法的时间复杂度为O(log n),比线性查找算法的时间复杂度O(n)更加高效。 Python实现快速查找算法 下面是一个Python实…

    python 2023年5月14日
    00
  • 一文带你了解ChatGPT API的使用

    一文带你了解ChatGPT API的使用 ChatGPT API是一个基于GPT模型的自然语言处理API,可以用于生成文本、问答、对话等多种应用场景。以下是一个示例,介绍了如何使用ChatGPT API。 示例一:使用Python请求ChatGPT API生成文本 以下是一个示例,使用Python请求ChatGPT API生成文本: import reque…

    python 2023年5月15日
    00
合作推广
合作推广
分享本页
返回顶部