使用Python实现几种底层技术的数据结构

news/2024/5/20 19:52:11

使用Python实现几种底层技术的数据结构

数据结构(data structure)是带有结构特性的数据元素的集合,它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系,并对这种结构定义相适应的运算,设计出相应的算法,并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之,数据结构是相互之间存在一种或多种特定关系的数据元素的集合,即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系。

Python实现了许多常见的底层数据结构,以下是其中几种常见的:

列表(List):列表是Python中最常用的数据结构之一,它可以存储任意类型的元素,并且可以动态地改变大小。列表使用方括号 [] 来表示,可以通过索引访问和修改元素。

元组(Tuple):元组与列表类似,但是元组是不可变的,即创建后不能修改。元组使用圆括号 () 来表示,可以通过索引访问元素。

字典(Dictionary):字典是一种键值对的数据结构,可以用来存储和访问具有唯一键的值。字典使用花括号 {} 来表示,键和值之间使用冒号 : 分隔。

集合(Set):集合是一种无序且不重复的数据结构,可以用来进行集合运算,如并集、交集、差集等。集合使用花括号 {} 来表示,元素之间使用逗号分隔。

字符串(String):字符串是一种由字符组成的序列,可以用来表示文本。字符串是不可变的,即创建后不能修改。字符串可以使用单引号或双引号来表示。

在Python中,虽然内置的类型如列表、字典、集合和元组可以用于大多数应用,但有时我们可能需要实现更具体的底层数据结构,例如栈、队列、链表、二叉树等。以下是这些数据结构的简单Python实现:

★栈(Stack)

栈是一种后进先出(LIFO)的数据结构。只允许在栈顶进行插入(push)和删除(pop)操作。在Python中可以使用列表来实现一个简单的栈。

class Stack:def __init__(self):self.items = []def is_empty(self):return not self.itemsdef push(self, item):self.items.append(item)def pop(self):if not self.is_empty():return self.items.pop()raise IndexError("pop from empty stack")def peek(self):if not self.is_empty():return self.items[-1]raise IndexError("peek from empty stack")def size(self):return len(self.items)#使用Stack类创建一个栈对象,并进行操作:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.size())    # 输出:3
print(stack.pop())     # 输出:3
print(stack.peek())    # 输出:2
print(stack.is_empty())     # 输出:False

★队列(Queue)

队列是一种先进先出(FIFO)的数据结构。只允许在队尾进行插入(enqueue)操作,在队头进行删除(dequeue)操作。在Python中可以使用列表来实现一个简单的队列。

class Queue:def __init__(self):self.items = []def is_empty(self):return not self.itemsdef enqueue(self, item):self.items.insert(0, item)def dequeue(self):if not self.is_empty():return self.items.pop()raise IndexError("dequeue from empty queue")def size(self):return len(self.items)#使用Queue类创建一个队列对象,并进行操作:
queue = Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
print(queue.size())    # 输出:3
print(queue.dequeue())     # 输出:'a'
print(queue.is_empty())    # 输出:False

★链表(Linked List)

链表是一种由节点组成的序列,每个节点包含数据和指向下一个节点的引用。单链表(Singly Linked List)是一种常见的链表,由一系列节点组成,每个节点包含两个部分:数据和指向下一个节点的引用。

在Python中,引用可以被看作是自动管理的指针,它们指向对象的内存地址,但这一切都是在Python的内部机制中自动处理的。

在Python中可以使用类来实现一个简单的链表。

 下面是一个简单的示例,展示了如何在Python中实现单链表:

class Node:def __init__(self, data):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = Nonedef is_empty(self):return self.head is None        def append(self, data):if not self.head:self.head = Node(data)else:current = self.headwhile current.next:current = current.nextcurrent.next = Node(data)def display(self):elements = []current = self.headwhile current:elements.append(current.data)current = current.nextreturn elementsdef remove_node(self, data):if not self.is_empty():current_node = self.headif current_node.data == data:self.head = current_node.nextelse:while current_node.next:if current_node.next.data == data:current_node.next = current_node.next.nextbreakcurrent_node = current_node.nextdef get_size(self):size = 0current_node = self.headwhile current_node:size += 1current_node = current_node.nextreturn size#使用LinkedList类创建一个链表对象,并进行操作:
linked_list = LinkedList()
print(linked_list.is_empty())    # 输出:Truelinked_list.append(1)
linked_list.append(2)
linked_list.append(3)print(linked_list.display())   # 输出[1, 2, 3]print(linked_list.get_size())    # 输出:3linked_list.remove_node(2)
print(linked_list.get_size())    # 输出:2

★二叉树(Binary Tree)

二叉树是每个节点最多有两个子节点的树结构。二叉树是另一种树形结构,其特点是每个结点至多只有两棵子树( 即二叉树中不存在度大于2的结点),并且二叉树的子树有左右之分,其次序不能任意颠倒。

class TreeNode:def __init__(self, data):self.data = dataself.left = Noneself.right = Noneclass BinaryTree:def __init__(self, root):self.root = TreeNode(root)def insert_left(self, current_node, data):if current_node.left is None:current_node.left = TreeNode(data)else:new_node = TreeNode(data)new_node.left = current_node.leftcurrent_node.left = new_nodedef insert_right(self, current_node, data):if current_node.right is None:current_node.right = TreeNode(data)else:new_node = TreeNode(data)new_node.right = current_node.rightcurrent_node.right = new_node# 用于演示的简单遍历方法def preorder_traversal(self, start, traversal=[]):"""Root -> Left -> Right"""if start:traversal.append(start.data)self.preorder_traversal(start.left, traversal)self.preorder_traversal(start.right, traversal)return traversal#使用 BinaryTree类创建一个二叉树对象,并进行操作
# 创建一个二叉树对象
binary_tree = BinaryTree(1)# 插入左子节点
binary_tree.insert_left(binary_tree.root, 2)
# 插入右子节点
binary_tree.insert_right(binary_tree.root, 3)# 插入左子节点的左子节点
binary_tree.insert_left(binary_tree.root.left, 4)
# 插入左子节点的右子节点
binary_tree.insert_right(binary_tree.root.left, 5)# 插入右子节点的左子节点
binary_tree.insert_left(binary_tree.root.right, 6)
# 插入右子节点的右子节点
binary_tree.insert_right(binary_tree.root.right, 7)# 进行先序遍历
print(binary_tree.preorder_traversal(binary_tree.root))

上述这些代码示例,演示了如何使用Python实现栈、队列、链表和二叉树的基础版本,实际应用中可能需要更多的功能和错误处理。这些数据结构在算法和数据处理中都有广泛的应用,掌握它们的实现原理和使用方法对于进一步提升编程能力十分重要。

附录

你应该了解的8种常见数据结构 https://www.toutiao.com/article/6799768009498952203/

算法基础系列 https://blog.csdn.net/cnds123/article/details/120061638


https://www.xjx100.cn/news/3090458.html

相关文章

Thinkphp-商城项目之oss文件上传及web端直传

4.3头像上传 一般商城网站都会把文件上传到第三方云,例如阿里云(oss),腾讯云(cos),当然如果公司有足够的实力,可以自己部署一台文件服务器,用于文件的保存。 头像上传一般是用户在用户中心上传的,后台管理…

从0开始学习JavaScript--JavaScript使用Promise

JavaScript中的异步编程一直是开发中的重要话题。传统的回调函数带来了回调地狱和代码可读性的问题。为了解决这些问题,ES6引入了Promise,一种更现代、更灵活的异步编程解决方案。本文将深入探讨JavaScript中如何使用Promise,通过丰富的示例代…

执行npm的时候报权限问题的解决方案

我们在执行npm操作的过程中,会出现以下权限问题,解决方案: 管理员身份 运行cmd 切换目录到要执行命令的文件下 再进行npm操作即可

openssl C++研发之pem格式处理详解

一、PEM_writeXXX和EM_write_bio_XXX 在OpenSSL的crypto/pem.h头文件中,PEM_write_XXXX和PEM_write_bio_XXXX系列函数用于将特定类型的数据写入文件或BIO(内存缓冲区)中,其中XXXX代表不同的数据类型。 这些函数的使用方式相似&a…

如何进行数据结构的设计和实现?

数据结构的设计和实现 数据结构是计算机科学中至关重要的概念之一,它涉及如何组织和存储数据以便有效地进行操作。在软件开发中,数据结构的选择和设计直接影响了程序的性能、可维护性和可扩展性。在这篇文章中,我们将深入探讨如何进行数据结…

Oracle 11g 多数据库环境下的TDE设置

19c的TDE wallet的设置是在数据库中设置的,也就是粒度为数据库,因此不会有冲突。 而11g的设置是在sqlnet.ora中,因此有可能产生冲突。 这里先将一个重要概念,按照文档的说法,wallet是不能被数据库共享的。 If there …

DES加密前端入参

js中使用DES加解密解决方案总结_js des加密-CSDN博客 1.需求背景 最近开发vue项目中,对于用户手机号码需要进行DES加解密操作。 简介:DES加密,是一种比较传统的加密方式,其加密运算、解密运算使用的是同样的密钥,信息…

全志H616开发版

开发板介绍: 二、开发板刷机 SDFormatter TF卡的格式化工具、Win32Diskimager 刷机工具 刷机镜像为:Orangepizero2_2.2.0_ubuntu_bionic_desktop_linux4.9.170.img 使用MobaXterm_Personal_20.3连接使用 网络配置:nmcli dev wifi 命令接入网…