«

Python高级数据结构与算法实例分析

时间:2024-4-26 19:55     作者:韩俊     分类: Python


本文小编为大家详细介绍“Python高级数据结构与算法实例分析”,内容详细,步骤清晰,细节处理妥当,希望这篇“Python高级数据结构与算法实例分析”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。

    一、简介

    我们将从以下几个方面来展开本文的内容:

    栈(Stack)

    队列(Queue)

    链表(Linked List)

    堆(Heap)

    排序算法(Sorting Algorithms)

    查找算法(Searching Algorithms)

    二、栈(Stack)

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

    class Stack:
        def __init__(self):
            self.items = []
     
        def push(self, item):
            self.items.append(item)
     
        def pop(self):
            if not self.is_empty():
                return self.items.pop()
     
        def peek(self):
            if not self.is_empty():
                return self.items[-1]
     
        def is_empty(self):
            return len(self.items) == 0
     
        def size(self):
            return len(self.items)

    三、队列(Queue)

    队列是一种先进先出(FIFO)的数据结构,只允许在队尾进行插入操作,而在队头进行删除操作。在Python中,我们可以使用

    collections
    模块中的
    deque
    类实现队列。

    from collections import deque
     
    class Queue:
        def __init__(self):
            self.items = deque()
     
        def enqueue(self, item):
            self.items.append(item)
     
        def dequeue(self):
            if not self.is_empty():
                return self.items.popleft()
     
        def is_empty(self):
            return len(self.items) == 0
     
        def size(self):
            return len(self.items)
                previous.next = current.next
        else:
            raise ValueError("Data not found in the list")

    四、堆(Heap)

    堆是一种特殊的完全二叉树,它的每个节点都大于等于(最大堆)或小于等于(最小堆)其子节点。在Python中,我们可以使用

    heapq
    库实现堆。

    import heapq
     
    class MaxHeap:
        def __init__(self):
            self.items = []
     
        def push(self, item):
            heapq.heappush(self.items, -item)
     
        def pop(self):
            return -heapq.heappop(self.items)
     
        def peek(self):
            return -self.items[0]
     
        def is_empty(self):
            return len(self.items) == 0
     
        def size(self):
            return len(self.items)

    五、排序算法(Sorting Algorithms)

    1. 冒泡排序(Bubble Sort)

    冒泡排序是一种简单的排序算法,通过重复遍历列表,比较相邻元素并交换不正确的顺序。

     def bubble_sort(arr):
        n = len(arr)
        for i in range(n):
            for j in range(0, n - i - 1):
                if arr[j] > arr[j + 1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]

    2. 选择排序(Selection Sort)

    选择排序是一种简单的排序算法,每次遍历列表找到最小(或最大)的元素,将其放到正确的位置。

    def selection_sort(arr):
        n = len(arr)
        for i in range(n):
            min_index = i
            for j in range(i + 1, n):
                if arr[j] < arr[min_index]:
                    min_index = j
            arr[i], arr[min_index] = arr[min_index], arr[i]

    3. 插入排序(Insertion Sort)

    插入排序是一种简单的排序算法,将未排序的元素逐个插入已排序的序列中。

    def insertion_sort(arr):
        n = len(arr)
        for i in range(1, n):
            key = arr[i]
            j = i - 1
            while j >= 0 and arr[j] > key:
                arr[j + 1] = arr[j]
                j -= 1
            arr[j + 1] = key

    六、查找算法(Searching Algorithms)

    1. 顺序查找(Sequential Search)

    顺序查找是一种简单的查找算法,通过遍历列表,逐个比较元素来查找目标值。

    def sequential_search(arr, target):
        for i in range(len(arr)):
            if arr[i] == target:
                return i
        return -1

    2. 二分查找(Binary Search)

    二分查找是一种高效的查找算法,要求列表已排序。每次查找都将范围缩小一半,直到找到目标值。

    def binary_search(arr, target):
        low, high = 0, len(arr) - 1
        while low <= high:
            mid = (low + high) // 2
            if arr[mid] == target:
                return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

    标签: python

    热门推荐