常见8种数据结构

embedded/2024/9/25 5:28:27/

常见的数据结构包括数组、链表、队列、栈、树、堆、哈希表和图,每种数据结构都有其特点,如下:

常见数据结构

  • 1.数组
  • 2.链表
  • 3.队列
  • 4.栈
  • 5.树
  • 6.图
  • 7.哈希表
  • 8.堆

1.数组

特点:

  • 固定大小的线性数据结构
  • 支持快速随机访问
  • 插入和删除效率比较低

一般应用于需要快速随机访问元素的场景。
案例:

python"># 定义一个数组
arr = [1, 2 , 3, 4, 5]
# 访问数组元素
print(arr[2])  # 输出: 3# 修改数组元素
arr[2] = 10
print(arr)  # 输出: [1, 2, 10, 4, 5]# 添加元素
arr.append(6)
print(arr)  # 输出: [1, 2, 10, 4, 5, 6]# 删除元素
arr.pop(2)
print(arr)  # 输出: [1, 2, 4, 5, 6]

2.链表

特点:

  • 动态大小的数据结构
  • 插入和删除效率比较高
  • 不支持快速随机访问

适用于需要频繁插入和删除元素的场景
案例:

python">class Node:def __init__(self, data=None):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = Nonedef append(self, data):new_node = Node(data)if not self.head:self.head = new_nodereturnlast = self.headwhile last.next:last = last.nextlast.next = new_nodedef print_list(self):curr = self.headwhile curr:print(curr.data, end=" -> ")curr = curr.nextprint("None")# 使用链表
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.print_list()  # 输出: 1 -> 2 -> 3 -> None

3.队列

特点:

  • 先进先出
  • 插入操作在队尾进行,删除操作在队头进行

应用于需要先进先出访问元素的场景,如任务调度、消息队列等
案例:

python">from collections import deque# 使用 deque 实现队列
queue = deque()# 入队
queue.append(1)
queue.append(2)
queue.append(3)
print(queue)  # 输出: deque([1, 2, 3])# 出队
print(queue.popleft())  # 输出: 1
print(queue)  # 输出: deque([2, 3])

4.栈

特点:

  • 先进后出
  • 插入和删除在栈顶进行

应用于需要后进先出访问元素的场景,如函数调用栈、表达式求值等
案例:

python"># 使用列表实现栈
stack = []# 入栈
stack.append(1)
stack.append(2)
stack.append(3)
print(stack)  # 输出: [1, 2, 3]# 出栈
print(stack.pop())  # 输出: 3
print(stack)  # 输出: [1, 2]

5.树

特点:

  • 非线性,由节点和边组成
  • 树中的节点有层次关系,一个节点可以有多个子节点

应用于需要表示层次结构的场景,比如文件系统、组织结构等
案例:

python">
class TreeNode:def __init__(self, data):self.data = dataself.children = []def add_child(self, child_node):self.children.append(child_node)def print_tree(self, level=0):prefix = " " * (level * 4)print(prefix + self.data)for child in self.children:child.print_tree(level + 1)# 创建树
root = TreeNode("Root")
child1 = TreeNode("Child1")
child2 = TreeNode("Child2")
child3 = TreeNode("Child3")
root.add_child(child1)
root.add_child(child2)child1.add_child(TreeNode("Grandchild1"))
child1.add_child(TreeNode("Grandchild2"))
root.print_tree()

6.图

特点:

  • 非线性,由节点和边组成
  • 图中的节点可以通过边来相互连接

应用于需要表示网络结构的场景,如社交网络、交通网络等。
案例:

python">class Graph:def __init__(self):self.graph = {}def add_edge(self, u, v):if u not in self.graph:self.graph[u] = []self.graph[u].append(v)def print_graph(self):for node in self.graph:print(f"{node} -> {', '.join(self.graph[node])}")# 创建图
g = Graph()
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "D")
g.add_edge("C", "D")
g.print_graph()

7.哈希表

特点:

  • 基于哈希函数实现的键值对数据结构
  • 支持快速的插入、删除和查找操作

应用于需要快速查找和插入操作的场景,如字典、缓存等。
案例:

python"># 使用字典实现哈希表
hash_table = {}# 插入键值对
hash_table["name"] = "John"
hash_table["age"] = 30
hash_table["city"] = "New York"
print(hash_table)  # 输出: {'name': 'John', 'age': 30, 'city': 'New York'}# 查找键值对
print(hash_table["name"])  # 输出: John# 删除键值对
del hash_table["age"]
print(hash_table)  # 输出: {'name': 'John', 'city': 'New York'}

8.堆

特点:

  • 堆是一颗完全二叉树
  • 分为最大堆和最小堆
    • 最大堆:每个节点的值都大于或等于其子节点的值。
    • 最小堆:每个节点的值都小于或等于其子节点的值。
  • 支持快速获取最大值或最小值的操作。

适用于优先队列,堆排序和实现高效的合并K个有序链表问题。
案例:

python">import heapq# 创建一个最小堆
min_heap = []# 插入元素
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 4)
heapq.heappush(min_heap, 2)
print(min_heap)  # 输出: [1, 2, 4, 3]# 弹出最小元素
print(heapq.heappop(min_heap))  # 输出: 1
print(min_heap)  # 输出: [2, 3, 4]# 创建一个最大堆(通过将元素取反实现)
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -4)
heapq.heappush(max_heap, -2)
print([-x for x in max_heap])  # 输出: [4, 2, 3, 1]# 弹出最大元素
print(-heapq.heappop(max_heap))  # 输出: 4
print([-x for x in max_heap])  # 输出: [3, 2, 1]

http://www.ppmy.cn/embedded/94288.html

相关文章

代码随想录算法训练营Day35||01背包

一、01背包 &#xff08;1&#xff09;dp数组定义&#xff1a;当目前背包容量为j时&#xff0c;从第0件物品遍历到第i件物品的最大价值 &#xff08;2&#xff09;递推公式&#xff1a;dp[i][j]dp[i-1][j]&#xff08;一定装不下第i件物品&#xff0c;即j<weight[i]时&#…

Lagent 自定义你的 Agent 智能体

一、Lagent 介绍 Lagent (https://github.com/InternLM/lagent)是一个轻量级开源智能体框架&#xff0c;旨在让用户可以高效地构建基于大语言模型的智能体。同时它也提供了一些典型工具以增强大语言模型的能力。 Lagent 目前已经支持了包括 AutoGPT、ReAct 等在内的多个经典智…

保姆级教程,一文了解LVS

目录 一.什么是LVS tips: 二.优点&#xff08;为什么要用LVS&#xff1f;&#xff09; 三.作用 四.程序组成 五.LVS 负载均衡集群的类型 六.分布式内容 六.一.分布式存储 六.二.分布式计算 六.三.分布式常见应用 tips&#xff1a; 七.LVS 涉及相关的术语 八.LVS 负…

Lambda 表达式:解锁编程世界的魔法之门

引言 在这个技术日新月异的时代&#xff0c;编程语言不断进化以适应日益复杂的软件开发需求。其中&#xff0c;Lambda表达式作为一门现代编程语言的重要特性&#xff0c;已经成为了提升代码效率与可读性的关键工具。无论你是刚刚踏入编程领域的新手&#xff0c;还是已经在软件…

【VScode】如何在anaconda虚拟环境中打开vscode项目

文章目录 【必备知识】打开anaconda虚拟环境切换到项目工作目录激活anaconda虚拟路径让vscode从当前目录打开 【必备知识】 anaconda环境变量配置及配置python虚拟环境 https://blog.csdn.net/xzzteach/article/details/140621596 打开anaconda虚拟环境 切换到项目工作目录 …

面向数据科学家的实用贝叶斯推理

目录 一、说明 二、贝叶斯定理 三、数学框架 四、在数据科学中的应用&#xff1a; 4.1 A/B 测试&#xff1a; 4.2 机器学习算法&#xff1a; 4.2.1. 朴素贝叶斯分类器 4.2.2. 贝叶斯网络 4.2.3. 预测&#xff1a; 五、结论 一、说明 Bayesian Inference 是一种方便的…

软件包管理|npm【前端工具链】

项目中的依赖 依赖是指可能由他人编写的第三方软件&#xff0c;理想情况下能够为你解决单一的问题。 一个 Web 项目可以有任意数量的依赖&#xff0c;从无到多&#xff0c;并且你的依赖里可以包含了你没有明确安装的子依赖&#xff08;依赖的依赖&#xff09;。 项目依赖可以…

51单片机个人学习笔记16(红外遥控)

前言 本篇文章属于STC89C52单片机&#xff08;以下简称单片机&#xff09;的学习笔记&#xff0c;来源于B站教学视频。下面是这位up主的视频链接。本文为个人学习笔记&#xff0c;只能做参考&#xff0c;细节方面建议观看视频&#xff0c;肯定受益匪浅。 [1-1] 课程简介_哔哩…