devbox
空白诗007
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Python 数据结构与算法_python数据结构的总结

作者：空白诗007 | 2024-07-26 15:04:16

赞

踩

python数据结构的总结

1、算法概念

在计算机科学中，算法是一个解决特定问题或执行特定任务的有序步骤的有限序列。算法是对一系列输入数据进行处理，产生期望输出结果的一种有效方法。它是解决问题的一种清晰而精确的描述，可以被实现为计算机程序。

算法必须满足以下关键特性：

  1. 有限性（Finiteness）： 算法的执行必须在有限的步骤内终止，不会永无止境地执行下去。

  2. 确定性（Determinism）： 对于给定的输入，算法的每一步都有确切的定义，不会产生模糊或不确定的结果。

  3. 输入（Input）： 算法接受零个或多个输入，这些输入是算法在执行过程中处理的原始数据。

  4. 输出（Output）： 算法产生至少一个输出，这是由输入经过一系列步骤计算得到的结果。

  5. 效率（Effectiveness）： 算法必须在有限时间内执行，而且在解决问题上是有效的，不会消耗过多的资源。

 2、时间复杂度和空间复杂度

Python(算法)-时间复杂度和空间复杂度-CSDN博客

 3、排序算法

3.1  冒泡排序

3.1.1 解释

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

冒泡排序的时间复杂度为O(n^2)，其中n是数组的大小。尽管冒泡排序在时间复杂度上相对较高，但是它实现简单直观，对于小规模的数据集仍然是一种有效的排序方法。此外，冒泡排序还具有稳定性，即相等元素的相对顺序不会改变。

3.1.2 python代码

  1. def bubble_sort(arr):
  2.     n = len(arr)
  3.  
  4.  
  5.  
  6.     # 外层循环控制比较的轮数
  7.     for i in range(n):
  8.         # 标记是否在本轮比较中发生交换
  9.         swapped = False
  10.  
  11.         # 内层循环执行相邻元素的比较和交换
  12.         for j in range(n - 1 - i):
  13.             if arr[j] > arr[j + 1]:
  14.                 arr[j], arr[j + 1] = arr[j + 1], arr[j]
  15.                 print("ll",arr)
  16.                 swapped = True
  17.  
  18.         # 如果本轮比较中没有发生交换，则表示数组已经有序，跳出循环
  19.         if not swapped:
  20.             break
  21.  
  22.     return arr
  23.  
  24.  
  25. # 测试
  26.  
  27. arr = [64, 34, 25, 12, 22, 11, 90]
  28. sorted_arr = bubble_sort(arr)
  29. print("排序后的数组:", sorted_arr)
'
运行

 3.1.3 结果

  1. C:\Users\Thinkpad\AppData\Local\Programs\Python\Python39\python.exe C:/Users/Thinkpad/Desktop/python的数据结构/冒泡排序.py 
  2. ll [34, 64, 25, 12, 22, 11, 90]
  3. ll [34, 25, 64, 12, 22, 11, 90]
  4. ll [34, 25, 12, 64, 22, 11, 90]
  5. ll [34, 25, 12, 22, 64, 11, 90]
  6. ll [34, 25, 12, 22, 11, 64, 90]
  7. ll [25, 34, 12, 22, 11, 64, 90]
  8. ll [25, 12, 34, 22, 11, 64, 90]
  9. ll [25, 12, 22, 34, 11, 64, 90]
  10. ll [25, 12, 22, 11, 34, 64, 90]
  11. ll [12, 25, 22, 11, 34, 64, 90]
  12. ll [12, 22, 25, 11, 34, 64, 90]
  13. ll [12, 22, 11, 25, 34, 64, 90]
  14. ll [12, 11, 22, 25, 34, 64, 90]
  15. ll [11, 12, 22, 25, 34, 64, 90]
  16. 排序后的数组: [11, 12, 22, 25, 34, 64, 90]
  17.  
  18. Process finished with exit code 0

        3.1.4 参考文献Python 冒泡排序 | 菜鸟教程 (runoob.com)

以上对数据排序在菜鸟都有

4、数据结构

4.1  定义

在Python中，常见的数据结构定义包括以下几种：

  1. 列表（List）：列表是Python中最常用的数据结构之一，用于存储一组有序的元素。列表使用方括号[]来定义，其中的元素可以是任意数据类型，并且可以动态增加、删除或修改。
my_list = [1, 2, 3, 'apple', 'banana']

  1. 元组（Tuple）：元组与列表类似，不同之处在于元组使用圆括号()来定义，一旦创建就不能被修改（即元组是不可变的）。
my_tuple = (1, 2, 3, 'apple', 'banana')

  1. 字典（Dictionary）：字典是无序的键值对集合，用大括号{}来定义，可以通过键来访问对应的值。字典的键必须是唯一的，但值可以重复。
my_dict = {'name': 'Alice', 'age': 25, 'city': 'New York'}

  1. 集合（Set）：集合是一种无序的、不重复的数据集合，用大括号{}来定义，可以进行集合运算（如并集、交集、差集等）。
my_set = {1, 2, 3, 4, 5}

  1. 字符串（String）：字符串是由字符组成的有序序列，可以用单引号''、双引号""或三引号''' '''来定义。
my_string = "Hello, Python!"

这些是Python中常见的数据结构定义方式，代表的是我们的数据应该怎么定义组织

  4.2 二叉树

4.2.1 二叉树基本概念

  1. 二叉树（Binary Tree）：二叉树是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的节点通常由一个存储元素值的数据域、一个指向左子节点的指针和一个指向右子节点的指针组成。如果某个节点没有子节点，则相应的指针可以为空。

  2. 根节点（Root Node）：树中的顶层节点称为根节点。在二叉树中，根节点是整个树的起始节点，它没有父节点。

  3. 父节点（Parent Node）：每个节点除了根节点外，都有一个父节点，父节点是指向当前节点的直接上级节点。

  4. 子节点（Child Node）：每个节点可能有零个、一个或两个子节点。子节点是当前节点的直接下级节点。

  5. 叶子节点（Leaf Node）：没有子节点的节点称为叶子节点，也叫终端节点。

  6. 内部节点（Internal Node）：除了叶子节点外的其他节点都称为内部节点。内部节点既有父节点也有子节点。

  7. 深度（Depth）：节点的深度是指从根节点到该节点的唯一路径的长度。根节点的深度为0，依次往下递增。

  8. 高度（Height）：节点的高度是指从该节点到一个叶子节点的最长路径的长度。叶子节点的高度为0，依次往上递增。

  9. 子树（Subtree）：在二叉树中，每个节点都可以作为子树的根节点，该节点下的所有子节点和它们的子节点组成了一个子树。

  10. 左子树和右子树（Left Subtree and Right Subtree）：每个节点都有一个左子节点和一个右子节点，它们分别称为左子树和右子树。

4.3 二叉树代码

  1.  
  2. class Node(object):
  3.     """树节点"""
  4.  
  5.     def __init__(self, item):
  6.         self.item = item
  7.         self.left_child = None
  8.         self.right_child = None
  9.  
  10.  
  11. class BinaryTree(object):
  12.     """二叉树"""
  13.  
  14.     def __init__(self):
  15.         self.root = None
  16.  
  17.     def is_empty(self):
  18.         """判断二叉树是否为空"""
  19.         return self.root is None
  20.  
  21.     def add(self, item):
  22.         """添加树节点"""
  23.         node = Node(item)
  24.         if self.root is None:
  25.             self.root = node
  26.             return
  27.         temp = [self.root]
  28.         # print(temp)
  29.         while temp:
  30.             current_node = temp.pop(0) #移除列表最后一个元素
  31.             if current_node.left_child:
  32.                 temp.append(current_node.left_child)
  33.             else:
  34.                 current_node.left_child = node
  35.                 return
  36.             if current_node.right_child:
  37.                 temp.append(current_node.right_child)
  38.             else:
  39.                 current_node.right_child = node
  40.                 return
  41.         '''
  42.             广度优先遍历(层次遍历)
  43.             从树的root开始，从上到下从从左到右遍历整个树的节点
  44.             '''
  45.     def breadth_traversal(self):
  46.         """广度遍历"""
  47.         if self.root is None:
  48.             return
  49.         temp = [self.root]
  50.         while temp:
  51.             current_node = temp.pop(0)
  52.             print(current_node.item, end=' ')
  53.             if current_node.left_child:
  54.                 temp.append(current_node.left_child)
  55.             if current_node.right_child:
  56.                 temp.append(current_node.right_child)
  57.         print()
  58.  
  59.     '''
  60.         深度优先遍历
  61.         对于一颗二叉树，深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。
  62.         那么深度遍历有重要的三种方法。这三种方式常被用于访问树的节点，它们之间的不同在于访问每个节点的次序不同。这三种遍历分别叫做
  63.         先序遍历（preorder），中序遍历（inorder）和后序遍历（postorder）。我们来给出它们的详细定义，然后举例看看它们的应用。
  65.         先序遍历
  66.         在先序遍历中，我们先访问根节点，然后递归使用先序遍历访问左子树，再递归使用先序遍历访问右子树
  67.         先序遍历 在先序遍历中，我们先访问根节点，然后递归使用先序遍历访问左子树，再递归使用先序遍历访问右子树
  69.          顺序如右：根节点->左子树->右子树
  70.         '''
  71.  
  72.     def preorder_traversal(self, node):
  73.         """先序遍历"""
  74.         if node is None:
  75.             return
  76.         print(node.item, end=' ')
  77.         self.preorder_traversal(node.left_child)
  78.         self.preorder_traversal(node.right_child)
  79.         """
  80.         中序遍历 在中序遍历中，我们递归使用中序遍历访问左子树，然后访问根节点，最后再递归使用中序遍历访问右子树
  82.         顺序如右：左子树->根节点->右子树
  83.         """
  84.     def inorder_traversal(self, node):
  85.         """中序遍历"""
  86.         if node is None:
  87.             return
  88.         self.inorder_traversal(node.left_child)
  89.         print(node.item, end=' ')
  90.         self.inorder_traversal(node.right_child)
  91.  
  92.  
  93.  
  94.  
  95.     """
  96.     后序遍历 在后序遍历中，我们先递归使用后序遍历访问左子树和右子树，最后访问根节点
  98. 顺序如右：左子树->右子树->根节点
  99. 代码实现：
  100.     """
  101.  
  102.  
  103.     def postorder_traversal(self, node):
  104.         """后序遍历"""
  105.         if node is None:
  106.             return
  107.         self.postorder_traversal(node.left_child)
  108.         self.postorder_traversal(node.right_child)
  109.         print(node.item, end=' ')
  110.  
  111.  
  112. if __name__ == '__main__':
  113.     tree = BinaryTree()
  114.     print(tree.is_empty())
  115.     tree.add(0)
  116.     tree.add(1)
  117.     tree.add(2)
  118.     tree.add(3)
  119.     tree.add(4)
  120.     tree.add(5)
  121.     tree.add(6)
  122.     tree.add(7)
  123.     tree.add(8)
  124.     tree.add(9)
  125.     print(tree.is_empty())
  126.     print("广度遍历")
  127.     tree.breadth_traversal()
  128.     print("先序遍历")
  129.     tree.preorder_traversal(tree.root)
  130.     print("\n中序遍历")
  131.     tree.inorder_traversal(tree.root)
  132.     print("\n后序遍历")
  133.     tree.postorder_traversal(tree.root)
'
运行

 4.3.1 运行结果

C:\Users\Thinkpad\AppData\Local\Programs\Python\Python39\python.exe C:/Users/Thinkpad/Desktop/python的数据结构/二叉树.py 
True
False
广度遍历
0 1 2 3 4 5 6 7 8 9 
先序遍历
0 1 3 7 8 4 9 2 5 6 
中序遍历
7 3 8 1 9 4 0 5 2 6 
后序遍历
7 8 3 9 4 1 5 6 2 0 
Process finished with exit code 0
 

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号