辛集专业网站建设,网络文学网站开发,电白区建设局网站,开源建站工具使用Python实现几种底层技术的数据结构 数据结构(data structure)是带有结构特性的数据元素的集合#xff0c;它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系#xff0c;并对这种结构定义相适应的运算#xff0c;设计出相应的算法#xff0c;并确保经过这…使用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 - Rightif 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
