编辑“︁算法与数据结构”︁（章节）

= 算法与数据结构 =

'''算法与数据结构'''是计算机科学的核心基础，研究如何高效地组织和处理数据。算法指解决问题的一系列明确步骤，数据结构则是存储和组织数据的方式。两者相辅相成，共同构成了高效程序设计的理论基础和实践工具。

== 基本概念 ==
=== 算法 ===
算法是具有以下特性的计算过程：
* '''有限性'''：必须在有限步骤后终止
* '''确定性'''：每个步骤都有明确定义
* '''输入'''：有零个或多个输入
* '''输出'''：产生至少一个输出
* '''有效性'''：每个步骤都能在有限时间内完成

=== 数据结构 ===
常见的基本数据结构包括：
* [[数组]]：连续内存空间存储相同类型元素
* [[链表]]：通过指针连接的节点序列
* [[栈]]：后进先出(LIFO)的线性结构
* [[队列]]：先进先出(FIFO)的线性结构
* [[树]]：具有层次关系的非线性结构
* [[图]]：由顶点和边组成的网络结构

== 复杂度分析 ==
算法效率通常用[[大O符号]]表示：

<math>
O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)
</math>

时间复杂度示例：
<syntaxhighlight lang="python">
# O(1) 常数时间
def get_first(arr):
    return arr[0]

# O(n) 线性时间
def linear_search(arr, target):
    for item in arr:
        if item == target:
            return True
    return False

# O(n^2) 平方时间
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]
</syntaxhighlight>

== 经典算法 ==
=== 排序算法 ===
* [[冒泡排序]]：简单但效率低
* [[快速排序]]：分治策略，平均O(n log n)
* [[归并排序]]：稳定排序，适合大数据集

=== 搜索算法 ===
* [[线性搜索]]：简单但效率低
* [[二分搜索]]：要求有序数组，O(log n)
* [[深度优先搜索]](DFS)和[[广度优先搜索]](BFS)：图遍历算法

== 应用实例 ==
=== 路径规划 ===
使用[[Dijkstra算法]]寻找图中两点间最短路径：

<mermaid>
graph LR
    A((A)) --5--> B((B))
    A --3--> C((C))
    B --2--> D((D))
    C --7--> D
    C --1--> E((E))
    D --4--> F((F))
    E --2--> F
</mermaid>

=== 数据压缩 ===
[[哈夫曼编码]]利用字符出现频率构建最优前缀码：

<syntaxhighlight lang="python">
from heapq import heappop, heappush

def build_huffman_tree(freq):
    heap = [[weight, [char, ""]] for char, weight in freq.items()]
    heapify(heap)
    while len(heap) > 1:
        lo = heappop(heap)
        hi = heappop(heap)
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    return heap[0]
</syntaxhighlight>

== 学习资源 ==
* [[算法导论]] - 经典教材
* [[LeetCode]] - 算法练习平台
* [[可视化算法]] - 交互式学习工具

== 参见 ==
* [[计算复杂性理论]]
* [[程序设计范式]]
* [[软件工程最佳实践]]

[[Category:编程教程]]
[[Category:计算机科学]]
[[Category:算法]]