首頁手記算法與數據結構入門指南

算法與數據結構入門指南

標簽：

算法與數據結構

本文介绍了算法与数据结构的基础知识，包括算法的基本概念、特性以及如何分析算法效率。同时，文章详细讲解了常见的数据结构如数组、链表、栈和队列，并提供了示例代码帮助理解。此外，文中还介绍了几种常用的算法及其应用场景，并通过代码示例展示了如何使用这些算法解决实际问题。

算法与数据结构入门指南

算法基础

什么是算法

算法是解决问题的一系列清晰、有序的步骤。它是计算机科学的基础，用于从输入数据中产生输出结果。一个有效的算法应当能够在有限的步骤内完成任务，并且每个步骤都是明确定义的。

算法的基本特性

算法具有以下几个基本特性：

输入：算法可以有零个或多个输入。输入是算法处理的对象，通常通过参数传递给算法。
输出：算法必须有至少一个输出。输出是算法处理的结果，表示算法的完成情况。
确定性：算法的每一步都必须是明确的和可执行的，不得有歧义。
有限性：算法必须在有限的时间内完成。也就是说，它不能无限期地运行。
有效性：算法应当能有效地解决问题，而不是无限地循环或浪费资源。

如何分析算法效率

分析算法效率通常涉及计算其时间复杂度和空间复杂度。

时间复杂度

时间复杂度是衡量算法执行时间的一种指标。它表示算法执行时间与输入数据规模的关系。通常用大O表示法（O-notation）来表示时间复杂度。

O(1)：常数复杂度。无论输入规模多大，算法执行的时间都是常数。
O(log n)：对数复杂度。算法执行时间随着输入规模的增加而对数增长。
O(n)：线性复杂度。算法执行时间与输入规模成正比。
O(n^2)：平方复杂度。算法执行时间是输入规模的平方。
O(2^n)：指数复杂度。算法执行时间随着输入规模的增加而指数增长。

空间复杂度

空间复杂度是衡量算法执行所需内存空间的一种指标。它表示算法所需存储空间与输入数据规模的关系。

def find_max_value(arr):
    if not arr:
        return None
    max_value = arr[0]
    for value in arr:
        if value > max_value:
            max_value = value
    return max_value

# 示例：求一个数组中的最大值
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(find_max_value(arr))  # 输出：9

常见数据结构

数组与链表

数组

数组是一种线性数据结构，用于存储一组相同类型的元素。数组中的元素存储在连续的内存空间中，可以通过索引直接访问。数组具有固定大小，一旦创建，其大小不能改变。

优点：
- 索引访问速度快。
- 存储和访问紧凑。
缺点：
- 如果需要插入或删除元素，可能需要移动大量数据。
- 大小固定，不灵活。

# 创建一个数组并访问元素
arr = [1, 2, 3, 4, 5]
print(arr[0])  # 输出：1
print(arr[2])  # 输出：3

# 插入一个新的元素
arr.insert(2, 10)  # 在索引2处插入10
print(arr)  # 输出：[1, 2, 10, 3, 4, 5]

链表

链表是一种线性数据结构，用于存储一组元素。链表中的元素（节点）通过指针链接起来，每个节点包含数据和指向下一个节点的指针。链表可以动态分配内存，插入和删除元素更加灵活。

优点：
- 插入和删除元素非常灵活。
- 无需预留大量空间。
缺点：
- 需要额外的指针空间。
- 无法通过索引直接访问元素。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def display(self):
        elements = []
        current_node = self.head
        while current_node:
            elements.append(current_node.data)
            current_node = current_node.next
        return elements

# 创建一个链表并添加元素
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.append(4)
print(linked_list.display())  # 输出：[1, 2, 3, 4]

栈与队列

栈

栈是一种后进先出（LIFO）的数据结构。栈只有两个基本操作：入栈（push）和出栈（pop）。栈的元素是按照先进后出的原则存储的。

优点：
- 实现简单。
- 直接访问栈顶元素。
缺点：
- 无法直接访问中间元素。
- 有限制的访问方式。

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        return None

    def size(self):
        return len(self.items)

# 创建一个栈并操作
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.peek())  # 输出：3
print(stack.pop())   # 输出：3
print(stack.size())  # 输出：2

队列

队列是一种先进先出（FIFO）的数据结构。队列只有两个基本操作：入队（enqueue）和出队（dequeue）。队列的元素是按照先进先出的原则存储的。

优点：
- 实现简单。
- 直接访问队首元素。
缺点：
- 无法直接访问中间元素。
- 有限制的访问方式。

class Queue:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)
        return None

    def size(self):
        return len(self.items)

# 创建一个队列并操作
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # 输出：1
print(queue.size())     # 输出：2

树与图的简介

树

树是一种非线性的数据结构，由节点和边组成。树中每个节点都有一个父节点（除了根节点）和多个子节点。树通常用于表示层次结构。

优点：
- 能够很好地表示层次结构。
- 搜索效率高。
缺点：
- 结构复杂。
- 需要额外的内存空间。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
        else:
            self._insert(self.root, val)

    def _insert(self, node, val):
        if val < node.val:
            if not node.left:
                node.left = TreeNode(val)
            else:
                self._insert(node.left, val)
        else:
            if not node.right:
                node.right = TreeNode(val)
            else:
                self._insert(node.right, val)

    def display(self):
        if self.root:
            self._display(self.root)

    def _display(self, node):
        if node:
            self._display(node.left)
            print(node.val)
            self._display(node.right)

# 创建一个二叉搜索树并插入元素
binary_tree = BinaryTree()
binary_tree.insert(10)
binary_tree.insert(5)
binary_tree.insert(15)
binary_tree.insert(3)
binary_tree.insert(7)
binary_tree.display()  # 输出：3, 5, 7, 10, 15

图

图是一种非线性的数据结构，由节点和边组成。图中的节点之间可以有任意数量的边连接。图通常用于表示复杂的关系网络。

优点：
- 能够表示复杂的结构和关系。
- 可以表示具有回路的结构。
缺点：
- 结构复杂。
- 需要额外的内存空间。

class Graph:
    def __init__(self):
        self.nodes = {}

    def add_node(self, node_id):
        if node_id not in self.nodes:
            self.nodes[node_id] = []

    def add_edge(self, node1, node2):
        self.nodes[node1].append(node2)
        self.nodes[node2].append(node1)

    def display(self):
        for node, neighbors in self.nodes.items():
            print(f"{node} -> {neighbors}")

# 创建一个图并添加节点和边
graph = Graph()
graph.add_node(1)
graph.add_node(2)
graph.add_node(3)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
graph.display()  # 输出：1 -> [2]，2 -> [1, 3]，3 -> [2]

常用算法介绍

搜索算法（如二分查找）

二分查找是一种在有序数组中查找特定元素的高效算法。通过反复将查找区间缩小，最终找到目标元素。

时间复杂度

时间复杂度为O(log n)。

实际应用

二分查找广泛应用于需要高效查找的场景，如查找数据库中的记录。

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

# 示例：在有序数组中查找目标值
arr = [1, 3, 5, 7, 9, 11]
target = 7
print(binary_search(arr, target))  # 输出：3

排序算法（如冒泡排序、快速排序）

冒泡排序

冒泡排序是一种简单直观的排序算法，通过比较相邻元素的大小并交换位置，反复进行，直至数组有序。

时间复杂度

最坏情况时间复杂度为O(n^2)。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

# 示例：使用冒泡排序对数组进行排序
arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(arr))  # 输出：[11, 12, 22, 25, 34, 64, 90]

快速排序

快速排序是一种高效的排序算法，采用分治法策略，通过选择一个基准值将数组分为两部分，递归地对两部分进行排序。

时间复杂度

平均时间复杂度为O(n log n)。

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# 示例：使用快速排序对数组进行排序
arr = [64, 34, 25, 12, 22, 11, 90]
print(quick_sort(arr))  # 输出：[11, 12, 22, 25, 34, 64, 90]

动态规划基础

动态规划是一种通过将问题分解为更小的子问题，并利用这些子问题的解来构建原问题解的方法。动态规划通常用于优化问题，如最长公共子序列、背包问题等。

状态定义：明确描述子问题的状态。
状态转移方程：定义状态之间的递推关系。
初始条件：明确初始状态下问题的解。
计算顺序：确定子问题的计算顺序。

示例：斐波那契数列

斐波那契数列是一个简单的动态规划案例，定义为：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)。

def fibonacci(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

# 示例：计算斐波那契数列的第10个数
print(fibonacci(10))  # 输出：55

示例：背包问题

背包问题是动态规划的一个经典问题，涉及如何选择物品以最大化总价值，同时不超过背包容量。

def knapsack(capacity, weights, values, n):
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    for i in range(n + 1):
        for w in range(capacity + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])
            else:
                dp[i][w] = dp[i - 1][w]
    return dp[n][capacity]

# 示例：解决一个简单的背包问题
capacity = 10
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
n = 4
print(knapsack(capacity, weights, values, n))  # 输出：10

数据结构实现

如何用Python实现链表

这里展示了如何使用Python实现一个简单的单链表。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def display(self):
        elements = []
        current_node = self.head
        while current_node:
            elements.append(current_node.data)
            current_node = current_node.next
        return elements

# 示例：创建一个链表并添加元素
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
print(linked_list.display())  # 输出：[1, 2, 3]

如何用Python实现栈和队列

这里展示了如何使用Python实现栈和队列。

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        return None

    def size(self):
        return len(self.items)

# 示例：创建一个栈并操作
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.peek())  # 输出：3
print(stack.pop())   # 输出：3
print(stack.size())  # 输出：2

class Queue:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)
        return None

    def size(self):
        return len(self.items)

# 示例：创建一个队列并操作
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # 输出：1
print(queue.size())     # 输出：2

实践项目

使用排序算法解决实际问题

这里提供一个简单的案例，使用排序算法对一组成绩进行排序，并输出前五名的成绩。

def sort_scores(scores):
    return sorted(scores, reverse=True)

# 示例：对一组成绩进行排序并输出前五名
scores = [82, 98, 76, 91, 89, 74, 88, 90, 85, 79, 93, 87]
sorted_scores = sort_scores(scores)
print(sorted_scores[:5])  # 输出：[98, 93, 91, 90, 89]

利用数据结构优化程序性能的小案例

这里提供一个简单的案例，使用栈来优化括号匹配的检查。

def is_balanced_parentheses(s):
    stack = []
    for char in s:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if not stack:
                return False
            stack.pop()
    return not stack

# 示例：检查括号是否匹配
s1 = "(()())"
s2 = "(())()"
s3 = "(()))("
print(is_balanced_parentheses(s1))  # 输出：True
print(is_balanced_parentheses(s2))  # 输出：True
print(is_balanced_parentheses(s3))  # 输出：False

这里提供另一个案例，使用栈来优化表达式求值的计算。

def eval_expr(s):
    stack = []
    num = 0
    sign = 1
    result = 0

    for i in range(len(s)):
        if s[i].isdigit():
            num = num * 10 + int(s[i])
        elif s[i] in "+-":
            result += sign * num
            num = 0
            if s[i] == "+":
                sign = 1
            else:
                sign = -1
        elif s[i] == "(":
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif s[i] == ")":
            result += sign * num
            num = 0
            result *= stack.pop()
            result += stack.pop()
        elif s[i] == " ":
            continue

    if num != 0:
        result += sign * num

    return result

# 示例：计算表达式
expr = "1 + 2 * (3 - 4) + 5"
print(eval_expr(expr))  # 输出：6

點擊查看更多內容

為 TA 點贊

若覺得本文不錯，就分享一下吧！

評論

評論

共同學習，寫下你的評論

評論加載中...

展開查看更多評論

作者其他優質文章

正在加載中

慕碼人8056858

手記
篇

粉絲

351

獲贊與收藏

1324

關注作者，訂閱最新文章

閱讀免費教程

后端通用面試教程

41個小節 32074 358

網絡編程入門教程

20個小節 13196 249

Pandas 入門教程

25個小節 19564 369

推薦

評論

收藏

共同學習，寫下你的評論



感謝您的支持，我會繼續努力的～

掃碼打賞，你說多少就多少

贊賞金額會直接到老師賬戶

支付方式

打開微信掃一掃，即可進行掃碼打賞哦

今天注冊有機會得

100積分直接送

付費專欄免費學

大額優惠券免費領

立即參與放棄機會

點擊
抽獎

慕課手記新用戶專享福利

恭喜你，你的運氣太好了，居然抽中了 100個積分！

恭喜你，抽中了價值元的專欄！

太棒了，直接落到你賬戶里！

積分商城里的羅技鼠標、機械鍵盤、
Kindle 閱讀器、小米平衡車
Apple iPad （10.2英寸）、大額優惠券
在等著你去兌換了噢

作者：

免費贈送

兌換碼：1111222211 復制

優惠券可用于購買實戰課、體系課
無門檻使用

先去看看，有什么好東西馬上兌換我愛學習，選課去


亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

算法與數據結構入門指南

什么是算法

算法的基本特性

如何分析算法效率

时间复杂度

空间复杂度

数组与链表

数组

链表

栈与队列

栈

队列

树与图的简介

树

图

搜索算法（如二分查找）

时间复杂度

实际应用

排序算法（如冒泡排序、快速排序）

冒泡排序

时间复杂度

快速排序

时间复杂度

动态规划基础

示例：斐波那契数列

示例：背包问题

如何用Python实现链表

如何用Python实现栈和队列

使用排序算法解决实际问题

利用数据结构优化程序性能的小案例

閱讀免費教程