下一个→ ←上一页

Python中的数据结构和算法

本课将简单介绍Python的数据结构和算法。借助实际和详细解释的插图，我们将讨论内置的数据结构，如列表、集、字典、元组等，以及其他一些用户定义的数据结构，如链接树、列表和图，以及一些常用的算法。

列表

同样，其他计算机语言中的数组和Python中的列表是以任何方式排列的项的集合。它允许列表中元素的多种数据类型。Python版本的列表可与c++的向量或Java的数组列表相媲美。由于所有组件都必须重新定位，因此从列表头部添加或删除成员是最昂贵的操作。如果预先分配的内存全部用完，在列表末尾插入和删除元素的代价也可能很高。

代码

            #创建Python列表List = ["Python"， "Data"， "Structures"， "Tutorial"] print("已创建的Python列表是:")print(List) #使用嵌套列表创建多维列表(列表中列表)List_ = [["Python"， "Data"]， ["Structures"， "Tutorial"]] print("多维列表是:")print(List_) #我们可以使用元素的索引来访问元素列表print("Single element: ""， List[1]) print("多个元素(切片):"，List[0:2]) print("对于嵌套列表:"，List_[1][0]) #我们可以使用负索引访问元素也#打印列表的最后一个元素打印("最后一个元素:"，List_[-1]) #使用负索引打印("最后两个元素:"，List[-1:-3:-1]) #最后的第一个顺序
           

输出

创建的Python列表为:['Python'， 'Data'， 'Structures'， 'Tutorial']多维列表为:[['Python'， 'Data']， ['Structures'， 'Tutorial']]单个元素:数据多个元素(切片):['Python'， 'Data']对于嵌套列表:Structures最后一个元素:['Structures'， 'Tutorial']最后两个元素:['Tutorial'， 'Structures']

元组

列表和Python元组是等价的，但与列表不同的是，元组是不可变的，这意味着一旦形成，我们就不能更改它们。元组可以包括多种类型的组件，就像List一样。

Python元组由一系列值分组而成。无论是否使用圆括号，这些值都由“逗号”分隔。

代码

            #创建Python元组Tuple = ("Python"， "Data"， "Structures"， "Tutorial") print(" Python元组是:")print(元组)#使用Python列表创建元组list = [3,6,2,7,4,5,3] print("使用列表的元组:")Tuple_ = Tuple (list) #使用索引访问元组元素print("Single element: "， Tuple[1]) print("多个元素(切片):， Tuple[0:2]) #使用负索引#打印列表的最后一个元素打印(" last element: "， Tuple[-1]) #尝试修改一个元组try: Tuple[1] = "Tuple"打印(元组)except Exception as e: print("异常引发:"，e
           

输出

Python元组是:('Python'， 'Data'， 'Structures'， 'Tutorial')使用列表的元组:单个元素:数据多个元素(切片):('Python'， 'Data')最后一个元素:教程异常引发:'tuple'对象不支持项赋值

集

Python集数据结构是可修改的非重复数据集合。集合主要用于成员筛选和去除冗余项。这些进程使用哈希数据结构，这是一种用于遍历、插入和删除元素的流行方法，通常需要O(1)时间。

代码

            #创建Python集Set = {"Python"， "Data"， "Structures"， "Tutorial"} print("The Python Set is: ") print(Set) #在enumerate(Set)中访问ind, i的集合元素:print(ind, i) #查找两个集合的交集Set_ = {1,2， "Python"， "Data"} print(" intersection: "， Set.intersection(Set_)) #两个集合的并集print("Union: "， Set. Union (Set_)))
           

输出

Python集合是:{'Python'， 'Data'， 'Tutorial'， 'Structures'} 0 Python 1 Data 2 Tutorial 3 Structures交集:{'Python'， 'Data'}联合:{1,2，'Structures'， 'Python'， 'Tutorial'， 'Data'}

字典

被称为Python字典的键值对格式的数据集合用于存储数据。这个数据结构的时间复杂度是O(1)，很像其他编码语言中的哈希表。Python字典是在键的帮助下索引的。键的值可以是任何类型，例如字符串、整数、序列等常量项。我们可以使用花括号{}或字典推导式来构建字典。

代码

            #创建Python字典Dict = {"1": "Python"， "2": "Data"， "3": "Structures"， "4": "Tutorial"} print(" Python字典是:")print(Dict) #使用键访问字典元素print("键2的值是:"，Dict["2"]) #使用内置的get方法访问元素print("使用get方法:"，Dict.get("2"))
           

输出

Python字典是:{'1':'Python'， '2': 'Data'， '3': 'Structures'， '4': 'Tutorial'}键2的值是:Data使用get方法:Data

链表

称为链表的线性数据结构具有不在内存中连续位置保存的元素。链表的元素是通过指针连接的。

指向链表第一个节点的指针作为链表的表示。头指的是顶部节点。如果链表为空，头的值为NULL。在列表中，每个节点至少有两个组件:

数据
指向下一个节点的指针(或引用)

代码

            #创建一个节点类类node: def __init__(self, value): self。价值=价值自我。next = None #创建一个链表类class LinkedList: def __init__(self): self。head =无#初始化链表list_ = LinkedList() #创建节点head = Node(“Python”)second_node = Node(“教程”)third_node = Node(“数据结构”)#连接节点list_.head。Next = second_node。在list_. next = third_node #打印链表= None:打印(list__head .head. list)Value, end = "\n") list_。Head = list_.head.next
           

输出

Python教程数据结构

链表是重要的数据结构。下面是链表的一些基本操作。

代码

            node: def __init__(self, value): self。价值=价值自我。next = None #创建一个链表类class Linked_List: def __init__(self): self。head = None #在列表的开头插入一个节点def insertInBeginning(self, value): insertion_node =节点(value) insertion_node。下一个=自我。头的自我。head = insertion_node #在一个特定的节点后面插入一个节点def insertAfterNode(self, previous_node, value):如果previous_node为None:打印("没有上一个节点。")返回insertion_node =节点(值)。Next = previous_node。下一个previous_node。if self. next = insertion_node #在列表末尾插入节点def insertInEnd(self, value): insertion_node = node (value)head为None: self。Head = insertion_node返回last_node = self。头部while (last_node.next): last_node = last_node。下一个last_node。delete (self, pos): if self. next = insertion_node #删除一个特定的节点。head为None:返回temporary = self。pos == 0: self。头=暂时的。next temporary =无return #查找i在范围(pos - 1)中要删除的键:temporary = temporary。如果键不在列表中，如果键为None，则返回。next为None:返回next_ = temporary.next.next temporary。next = None临时的。next = next_ # Searching an element in the list def search(self, key): current_node = self.head while current_node is not None: if current_node.value == key: return True current_node = current_node.next return False # Sorting the linked list def sortList(self, head): current_node = head index_node = Node(None) if head is None: return else: while current_node is not None: index_node = current_node.next while index_node is not None: if current_node.value > index_node.value: current_node.value, index_node.value = index_node.value, current_node.value index_node = index_node.next current_node = current_node.next # Printing the linked list def printLinkedList(self): temporary = self.head while (temporary): print(str(temporary.value) + " ", end = "") temporary = temporary.next if __name__ == '__main__': listt = Linked_List() listt.insertInEnd(7) listt.insertInBeginning(4) listt.insertInBeginning(9) listt.insertInEnd(2) listt.insertAfterNode(listt.head.next, 8) print('Linked list:') listt.printLinkedList() print("\nAfter deleting a node:") listt.deleteANode(2) listt.printLinkedList() value_to_find = 4 if listt.search(value_to_find): print("\n", value_to_find, "is found in the list") else: print("\n", value_to_find, " is not found in the list") listt.sortList(listt.head) print("Sorted Linked List: ") listt.printLinkedList()
           

输出

链表:9 4 8 7 2删除节点后:在列表中发现9 4 7 2 4排序链表:2 4 7 9

堆栈

堆栈是一种线性数据结构，它使用先入后出(FILO)或后进先出(LIFO)排序来存储对象。在堆栈中，一个项只从一端删除，而一个新项则放在另一端。推送和弹出是插入和删除操作的常用名称。

栈的基本操作

我们可以使用一些基本操作在堆栈上执行各种活动。

推动:此方法将一个项添加到堆栈顶部

流行:此方法将从堆栈顶部删除一个项

IsEmpty:这个方法检查堆栈是否为空。

IsFull:这个方法检查堆栈是否已满。

看:此方法将返回顶部元素，但不会删除它。

代码

            #创建堆栈def create(): new_stack = [] return new_stack #检查是否为空堆栈def check(stack): if len(stack) == 0:返回True else:返回False #向堆栈中添加新元素def push(stack, value): stack.append(value) print(" push后的新堆栈:"，stack) #从堆栈中删除一个项def pop(stack): if (check(stack)):返回"给定堆栈为空" Stack .pop() print("弹出后的新堆栈:"，Stack) #窥探堆栈def peek(Stack): print("堆栈的最后一个元素:"，Stack[-1]) #上述方法的驱动程序代码Stack = create() push(堆栈，2)push(堆栈，5)push(堆栈，3)push(堆栈，1)pop(堆栈)peek(堆栈)
           

输出

推入后的新堆栈:[2]推入后的新堆栈:[2,5]推入后的新堆栈:[2,5,3]推入后的新堆栈:[2,5,3,1]弹出后的新堆栈:[2,5,3]堆栈最后一个元素:3

队列

队列以先进先出(FIFO)的顺序保存对象，是另一种类似于堆栈的线性数据结构。队列按照最近添加项的顺序删除项。任何排队等待访问服务的用户，其中最先到达的用户最先得到服务，都是队列的极好说明。

链接到队列的操作包括:

排队:向队列中添加一段内容。溢出条件定义为当队列被填充时。向队列中添加元素的时间复杂度:O(1)

出列:从队列中取出一些东西。这些东西以与值排队相同的顺序弹出。如果队列为空，则称为下溢条件。获取队列的第一项的时间复杂度为O(1)。

后:获取队列中的最后一项。获取队列最后一项的时间复杂度为O(1)。

代码

            #创建队列并实现队列操作的Python程序#为队列类创建一个类queue: #初始化队列def __init__(self): self。queue =[] #向队列中添加一个元素def enqueue(self, element): self.queue.append(element) print("进入队列后的新队列:"，self.queue) #从队列中移除一个元素def dequeue(self): if len(self.queue) == 0:返回无其他:返回self.queue.pop(0) print("退出队列后的新队列:"，self.queue) def rear(self): print("最后一个元素:"， self.queue[-1]) #上述方法的驱动程序代码queue = queue() queue.enqueue(6) queue.enqueue(3) queue.dequeue() queue.enqueue(9) queue.rear()
           

输出

enqueuing后的新队列:[6]enqueuing后的新队列:[6,3]enqueuing后的新队列:[3,9]最后一个元素:9

堆

堆数据结构主要用于描述优先级队列，由Python heapq模块提供。堆数据结构的特点是，每当弹出一个项时，它总是返回最小的项(min-heap)。在保留堆结构的同时，始终将项推入或弹出。此外，堆[0]项始终返回最小值。它支持O(log n)时间检索和插入最小值元素。

堆通常有两种类型:

Max-Heap:Max-Heap数据结构的根节点的键必须在其子节点的键中排名最高。对于二叉树中的每一个子树，同样的条件应该递归为真。

最小堆:Min-Heap的根节点的键应该是它所有子节点的键中最小的公共键。对于二叉树中的每一个子树，同样的条件应该递归为真。

代码

            # Python程序实现一个Python #堆数据结构定义一个方法来创建一个堆def heapify(数组,n, j):最大= j = 2 * + 1 b = 2 * j + 2如果< n和阵列[j] <数组[a]:最大=如果b < n和数组(最大)<数组[b]:最大= b如果最大! = j: [j]数组,数组(最大)=数组(最大),数组[j] heapify(数组,n,最大)def insert_element(数组、价值):s = len(数组)如果s = = 0: array.append(价值)其他:array.append(价值);j的范围((s / / 2) 1, 1, 1): heapify(数组,年代,j) def删除(数组、价值):s = len(数组)j的范围(0,年代):如果s = = array [j]:打破[j]数组,数组(s - 1] = [s - 1]数组,数组[j] array.remove j(值)的范围((len(数组)/ / 2)1,1,1):heapify(数组,len(数组),j) #驱动代码上面的方法堆= []insert_element(堆,3)insert_element(堆,6)insert_element(堆,5)insert_element(堆,4)insert_element(堆,8)打印(“堆数组:"， heap) delete(heap, 5) print("删除项后"，heap)
           

输出

堆数组:[6,4,5,3,8]删除项后:[8,4,6,3]

二叉树

一种称为树的非线性层次数据结构由节点和边组成。

被称为二叉树的Python树数据结构允许每个父节点最多有两个子节点。二叉树在每个节点上有三个分量:

数据元素
左子节点的地址
右子节点的地址

代码

            #为树类的一个节点创建一个类Node: def __init__(self, value): self。left = None self。Val = value self。#以预先排序的方式横向的方法def traverseAsPreOrder(self): print(self.;)Val, end = ' ') if self。= None: self.left. traverseaspreorder()如果self.left。= None: self.right. traverseaspreorder() #以有序方式横向的方法= None: self.left. traverseasinorder () print(self. left. traverseasinorder)Val, end = ' ') if self。= None: self.right. traverseasinorder() #以后序方式横向的方法= None: self.left. traverseaspostorder () if self.left. traverseaspostorder ()= None: self.right. traverseaspostorder () print(self. right. traverseaspostorder)val, end = ' ') #上述二叉树类的驱动程序代码root_node = Node(4) root_node。left =节点(5)root_node。right =节点(7)root_node.right。left =节点(2)root_node.right.left。right =节点(9)root_node.left。right =节点(0)root_node.left。left =节点(10)root_node.left.left。right = Node(1) # Transferring the tree print("Pre-order traversal of the tree: ", end = "") root_node.traverseAsPreOrder() print("\nIn-order traversal of the tree: ", end = "") root_node.traverseAsInOrder() print("\nPost-order traversal of the tree: ", end = "") root_node.traverseAsPostOrder()
           

输出

树的前序遍历:4 5 10 10 7 2 9树的序遍历:10 1 5 0 4 2 9 7树的后序遍历:1 10 0 5 9 2 7 4

冒泡排序算法

一种称为冒泡排序的排序方法分析附近的两个项并交换它们，直到达到所需的顺序。

在每次迭代中，列表中的每个项都移动到列表的末尾。这与液体中浮到表面的气泡的行为类似。因此，它被称为冒泡排序。

代码

            #实现冒泡排序算法#创建一个执行冒泡排序的方法def bubbleSort(list): #循环遍历列表中c在range(len(list))中的每个元素:#循环遍历剩余元素，与当前元素在range(0, len(list) - c - 1)中的n进行比较:#比较两个相邻元素#如果list [n] < list [n + 1]，则按降序排序:#交换两个元素，如果它们的顺序不正确temporary = List [n] List [n] = List [n + 1] List [n + 1] = temporary #上述方法的驱动代码List = [3,7,9,2,5,0] bubbleSort(List) print('排序列表降序:')print(List)
           

输出

按降序排序的列表:[9,7,5,3,2,0]

选择排序算法

一种称为选择排序的排序算法在每次迭代中选择未排序列表的最大元素，并将其插入到列表的开头。

代码

            #定义一个执行选择排序的方法def selectionSort(list, size): for s in range(size): max_index = s for i in range(s + 1, size): #我们正在按降序排序#选择列表的最大元素if list [i] > list [max_index]:max_index = i #将最大值放在列表的开头(list [s]， list [max_index]) = (list [max_index]， list [s]) #驱动代码list = [20,35,29,85,23,97] size = len(list) selectionSort(list, size) print('排序列表降序排列:')print(list)
           

输出

按降序排序列表:[97,85,35,29,23,20]

快速排序算法

使用称为快速排序(从数组中取出的项)的排序算法中的分治策略，将数组分割为更小的数组。

拆分给定数组时，应该设置枢轴组件，以便值大于枢轴组件的项位于右侧，值小于枢轴值的组件存储在左侧。

同样的方法用于划分左右子数组。重复这个过程，直到每个子数组中只剩下一个元素。

此时元素已经排序。这些项的组合在最后创建一个排序数组。

代码

            #定义一个函数来搜索旋转位置def pivot(list, low, high): #选择最右边的元素作为枢轴pivot = list [high] #更大的项g = low - 1 #在range(low, high)中横切i的所有元素:如果list [i] <= pivot:#如果j的值比较小,我们将交换的指针g g = g + 1 #交换元素在g和我(listt [g], listt[我])= (listt[我],listt [g]) #交换的主元素的值(listt (g + 1), listt(高))= (listt(高),listt [g + 1]) #返回位置的主完成返回g + 1 #定义一个函数来执行快速排序def quickSortAlgo (listt、低、高):如果低<高:#查找它左边的元素更小，右边的元素更大p = pivot(List, low, high) #递归调用左枢轴quickSortAlgo(List, low, p - 1) #递归调用右枢轴quickSortAlgo(List, p + 1, high) #驱动代码List = [3,7,2,4,9,1,0,8] size = len(List) quickSortAlgo(List, 0, size - 1) print('按升序排序的列表:')print(List)
           

输出

按升序排序列表:[0,1,2,3,4,7,8,9]

计数排序算法

一种称为计数排序的排序方法根据每个不同元素在给定数组中出现的次数来排列给定的元素数组。排序是通过将数组的元素计数映射为我们所创建的另一个数组的索引来完成的。该数组存储元素的计数。

代码

            # Python程序执行计数排序#定义一个函数来执行计数排序def countingSort (listt): s = len (listt) o =[0] *大小#初始化计算c =[0] * 10 #创建列表的列表项我的元素范围(0,年代):c [listt[我]]+ = 1 #存储j的累积计数范围(10):c [j] + = c [j - 1] #的指标数列表中每一项的初始列表#将计算列表中的元素j = s - 1 j > = 0:o[c[list [j]] - 1] = list [j] c[list [j]] -= 1 j -= 1 #将排序的列表元素复制到范围(0,s)中k的原始列表:list [k] = o[k] #驱动代码list = [3,7,9,2,4,7,2,8] countingSort(list) print(" sorted list: ") print(list)
           

输出

排序列表:[2,2,3,4,7,7,8,9]

二分搜索算法

二分搜索是一种在已排序数组中查找元素位置的搜索算法。

在这种方法中，元素总是在数组的一部分中间进行搜索。

代码

            # Python程序执行二进制搜索#定义一个函数来执行二进制搜索def binarySearch (listt、e、l、h): #我们将使用两个指针迭代找到元素,而l < = h: mid_element = l + (h - l) / / 2如果listt [mid_element] = = e:返回mid_element elif listt [mid_element] < e: l = mid_element + 1: h = mid_element - 1返回1 #驱动代码listt =[4、2、7、6、7、8、1 9 0 5]e = 7指数= binarySearch (listt e 0, len (listt) 1)如果指数! = 1:打印("我们搜索的元素存在于:" + str(index))否则:打印("未找到")
           

输出