数据结构:绪论

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版		 前一修订版
数据结构:绪论 [2025/12/11 16:14] – [3. 动态规划 (Dynamic Programming)] 张叶安数据结构:绪论 [2025/12/11 16:24] (当前版本) – [1. 穷举法 (Brute Force)] 张叶安
行 1: 行 1:
 ====== 绪论：数据结构与算法详解 (进阶版) ====== ====== 绪论：数据结构与算法详解 (进阶版) ======
  
-程序设计的核心公式（N.沃思）： +**"程序设计 = 数据结构 + 算法"** —— 尼克劳斯·沃思 (Niklaus Wirth, 图灵奖得主)
-> **程序 = 数据结构 (骨架) + 算法 (灵魂)**+
  
-  * **数据结构**：是**静态**的。就像图书馆的书架，决定了书怎么放（是按首字母放，还是按类别放）。 +如果把编程比作**烹饪**： 
-  * **算法**：是**动态**的。就像图书管理员找书的流程（是从左往右一本本找，还是先查索引再找）。+  *   **数据结构 (Data Structure)** 是**食材与厨具的收纳方式**。你是把所有东西堆在桌子上（杂乱无章），还是把蔬菜放保鲜层、肉类放冷冻层、刀具挂在磁吸架上（井井有条）？这决定了你取用材料的效率。 
 +  *   **算法 (Algorithm)** 是**菜谱与烹饪流程**。是先切菜还是先烧油？是慢火炖还是大火爆炒？这决定了做菜的速度和口味。 
 + 
 +本教程旨在通过可视化的方式，深入剖析计算机科学的这两大基石。
  
 ===== 第一部分：数据结构 (Data Structure) ===== ===== 第一部分：数据结构 (Data Structure) =====
 +
 +数据结构不仅仅是存储数据，更是为了**高效地**检索和操作数据。
  
 ==== 1. 核心概念辨析 ==== ==== 1. 核心概念辨析 ====
  
-我们通过一个**“学生信息管理系统”**的例子来理解：+在深入具体结构前，我们需要厘清以下术语的层级关系：
  
-  * **数据 (Data)**：计算机处理的符号总称。 +^ 术语 ^ 定义 ^ 举例 (学生管理系统) ^ 
-  * **数据元素 (Data Element)**：数据的**基本单位**（例：学生表中的一行记录）。 +| **数据 (Data)** | 描述客观事物的符号，是计算机操作的对象 | 整个数据库文件 | 
-  * **数据项 (Data Item)**：构成元素的最小单位（例：记录中的“学号”）。 +| **数据元素 (Data Element)** | 数据的**基本单位**，在程序中通常作为一个整体处理 | 一名学生的完整记录 (行) | 
-  * **数据对象 (Data Object)**：性质相同的数据元素的集合（例：所有学生的集合）。+| **数据项 (Data Item)** | 构成数据元素的**最小单位**，不可分割 | 学生的学号、姓名、性别 (列) | 
 +| **数据对象 (Data Object)** | 性质相同的数据元素的集合 | 所有学生的集合 (表) |
  
-==== 2. 逻辑结构可视化 ====+==== 2. 逻辑结构：数据之间的“思想关系” ====
  
-逻辑结构描述的是数据在**思想上**的关联。以下是四种基本结构的交互式演示：+逻辑结构是指数据元素之间的相互关系，它与数据在计算机中的存储位置无关。我们通常将其分为四类。
  
 <html> <html>
行 37: 行 42:
         margin: 0 auto 20px auto;         margin: 0 auto 20px auto;
     }     }
- 
-    /* 网格布局 */ 
     .ds-grid {     .ds-grid {
         display: grid;         display: grid;
-        grid-template-columns: repeat(auto-fit, minmax(220px, 1fr)); /* 稍微加宽一点卡片 */+        grid-template-columns: repeat(auto-fit, minmax(220px, 1fr));
         gap: 25px;         gap: 25px;
     }     }
- 
-    /* 卡片样式 */ 
     .ds-card {     .ds-card {
         background: white;         background: white;
行 58: 行 59:
         align-items: center;         align-items: center;
     }     }
- 
     .ds-card:hover {     .ds-card:hover {
         transform: translateY(-7px);         transform: translateY(-7px);
行 64: 行 64:
         border-bottom-color: #3498db;         border-bottom-color: #3498db;
     }     }
- 
-    /* 图标区域 */ 
     .ds-icon-box {     .ds-icon-box {
-        height: 110px; /* 稍微增高以容纳更多元素 */+        height: 110px;
         width: 100%;         width: 100%;
         display: flex;         display: flex;
行 76: 行 74:
         border-radius: 8px;         border-radius: 8px;
     }     }
- 
-    /* SVG 通用样式 */ 
     .ds-svg {     .ds-svg {
-        width: 140px; /* SVG 画布更宽 */+        width: 140px;
         height: 90px;         height: 90px;
         overflow: visible;         overflow: visible;
     }     }
-     +    .ds-shape { fill: #3498db; }  
-    /* 节点样式 */ +    .ds-shape-2 { fill: #e74c3c; }  
-    .ds-shape { fill: #3498db; } /* 蓝色 */ +    .ds-shape-3 { fill: #f1c40f; }  
-    .ds-shape-2 { fill: #e74c3c; } /* 红色 */ +    .ds-shape-4 { fill: #2ecc71; } 
-    .ds-shape-3 { fill: #f1c40f; } /* 黄色 */ +
-    .ds-shape-4 { fill: #2ecc71; } /* 绿色 */ +
-     +
-    /* 线条样式 */+
     .ds-line { stroke: #34495e; stroke-width: 1.5; stroke-linecap: round; }     .ds-line { stroke: #34495e; stroke-width: 1.5; stroke-linecap: round; }
     .ds-dashed { stroke: #bdc3c7; stroke-width: 2; stroke-dasharray: 5,3; fill: none; }     .ds-dashed { stroke: #bdc3c7; stroke-width: 2; stroke-dasharray: 5,3; fill: none; }
- 
-    /* 集合动画：不同步的浮动 */ 
     .anim-float-1 { animation: float 3s infinite ease-in-out; }     .anim-float-1 { animation: float 3s infinite ease-in-out; }
     .anim-float-2 { animation: float 4s infinite ease-in-out 0.5s; }     .anim-float-2 { animation: float 4s infinite ease-in-out 0.5s; }
     .anim-float-3 { animation: float 3.5s infinite ease-in-out 1.2s; }     .anim-float-3 { animation: float 3.5s infinite ease-in-out 1.2s; }
     .anim-float-4 { animation: float 4.5s infinite ease-in-out 2s; }     .anim-float-4 { animation: float 4.5s infinite ease-in-out 2s; }
-     
     @keyframes float {     @keyframes float {
         0%, 100% { transform: translateY(0); }         0%, 100% { transform: translateY(0); }
         50% { transform: translateY(-4px); }         50% { transform: translateY(-4px); }
     }     }
- 
-    /* 文字排版 */ 
     h4 { margin: 0 0 8px 0; color: #2c3e50; font-size: 1.1em; font-weight: 700; }     h4 { margin: 0 0 8px 0; color: #2c3e50; font-size: 1.1em; font-weight: 700; }
     p.desc { font-size: 0.9em; color: #7f8c8d; margin: 0; line-height: 1.5; }     p.desc { font-size: 0.9em; color: #7f8c8d; margin: 0; line-height: 1.5; }
     p.example { font-size: 0.8em; color: #95a5a6; margin-top: 5px; font-style: italic; }     p.example { font-size: 0.8em; color: #95a5a6; margin-top: 5px; font-style: italic; }
- 
 </style> </style>
 </head> </head>
 <body> <body>
- 
 <div class="ds-container"> <div class="ds-container">
     <div class="ds-grid">     <div class="ds-grid">
-         +        <!-- 1. 集合结构 -->
-        <!-- 1. 集合结构 (Set) -->+
         <div class="ds-card">         <div class="ds-card">
             <div class="ds-icon-box">             <div class="ds-icon-box">
                 <svg class="ds-svg" viewBox="0 0 140 90">                 <svg class="ds-svg" viewBox="0 0 140 90">
-                    <!-- 集合边界 --> 
                     <ellipse cx="70" cy="45" rx="60" ry="40" class="ds-dashed" />                     <ellipse cx="70" cy="45" rx="60" ry="40" class="ds-dashed" />
-                    <!-- 元素：更多数量，更杂乱 --> 
                     <circle cx="40" cy="30" r="6" class="ds-shape anim-float-1" />                     <circle cx="40" cy="30" r="6" class="ds-shape anim-float-1" />
                     <circle cx="90" cy="35" r="7" class="ds-shape-2 anim-float-2" />                     <circle cx="90" cy="35" r="7" class="ds-shape-2 anim-float-2" />
行 136: 行 118:
             <p class="example">例：购物车里的商品</p>             <p class="example">例：购物车里的商品</p>
         </div>         </div>
- +        <!-- 2. 线性结构 -->
-        <!-- 2. 线性结构 (Linear) -->+
         <div class="ds-card">         <div class="ds-card">
             <div class="ds-icon-box">             <div class="ds-icon-box">
                 <svg class="ds-svg" viewBox="0 0 140 90">                 <svg class="ds-svg" viewBox="0 0 140 90">
-                    <!-- 连接线 --> 
                     <line x1="20" y1="45" x2="120" y2="45" class="ds-line" />                     <line x1="20" y1="45" x2="120" y2="45" class="ds-line" />
-                    <!-- 节点：5个节点，体现序列 --> 
                     <circle cx="20" cy="45" r="6" class="ds-shape" />                     <circle cx="20" cy="45" r="6" class="ds-shape" />
                     <circle cx="45" cy="45" r="6" class="ds-shape" />                     <circle cx="45" cy="45" r="6" class="ds-shape" />
行 155: 行 134:
             <p class="example">例：排队、链表、数组</p>             <p class="example">例：排队、链表、数组</p>
         </div>         </div>
- +        <!-- 3. 树状结构 -->
-        <!-- 3. 树状结构 (Tree) -->+
         <div class="ds-card">         <div class="ds-card">
             <div class="ds-icon-box">             <div class="ds-icon-box">
                 <svg class="ds-svg" viewBox="0 0 140 90">                 <svg class="ds-svg" viewBox="0 0 140 90">
-                    <!-- 连线：根到第二层 --> 
                     <line x1="70" y1="10" x2="40" y2="40" class="ds-line" />                     <line x1="70" y1="10" x2="40" y2="40" class="ds-line" />
                     <line x1="70" y1="10" x2="100" y2="40" class="ds-line" />                     <line x1="70" y1="10" x2="100" y2="40" class="ds-line" />
-                    <!-- 连线：第二层到第三层 --> 
                     <line x1="40" y1="40" x2="20" y2="75" class="ds-line" />                     <line x1="40" y1="40" x2="20" y2="75" class="ds-line" />
                     <line x1="40" y1="40" x2="55" y2="75" class="ds-line" />                     <line x1="40" y1="40" x2="55" y2="75" class="ds-line" />
                     <line x1="100" y1="40" x2="85" y2="75" class="ds-line" />                     <line x1="100" y1="40" x2="85" y2="75" class="ds-line" />
                     <line x1="100" y1="40" x2="120" y2="75" class="ds-line" />                     <line x1="100" y1="40" x2="120" y2="75" class="ds-line" />
- +                    <circle cx="70" cy="10" r="6" class="ds-shape" /> 
-                    <!-- 节点：3层结构 --> +                    <circle cx="40" cy="40" r="5" class="ds-shape-2" /> 
-                    <circle cx="70" cy="10" r="6" class="ds-shape" /> <!-- Root --> +                    <circle cx="100" cy="40" r="5" class="ds-shape-2" /> 
-                     +                    <circle cx="20" cy="75" r="4" class="ds-shape-4" /> 
-                    <circle cx="40" cy="40" r="5" class="ds-shape-2" /> <!-- L2 Left --> +                    <circle cx="55" cy="75" r="4" class="ds-shape-4" /> 
-                    <circle cx="100" cy="40" r="5" class="ds-shape-2" /> <!-- L2 Right --> +                    <circle cx="85" cy="75" r="4" class="ds-shape-4" /> 
-                     +                    <circle cx="120" cy="75" r="4" class="ds-shape-4" />
-                    <circle cx="20" cy="75" r="4" class="ds-shape-4" /> <!-- L3 --> +
-                    <circle cx="55" cy="75" r="4" class="ds-shape-4" /> <!-- L3 --> +
-                    <circle cx="85" cy="75" r="4" class="ds-shape-4" /> <!-- L3 --> +
-                    <circle cx="120" cy="75" r="4" class="ds-shape-4" /> <!-- L3 -->+
                 </svg>                 </svg>
             </div>             </div>
行 185: 行 157:
             <p class="example">例：公司组织架构、文件系统</p>             <p class="example">例：公司组织架构、文件系统</p>
         </div>         </div>
- +        <!-- 4. 图形结构 -->
-        <!-- 4. 图形结构 (Graph) -->+
         <div class="ds-card">         <div class="ds-card">
             <div class="ds-icon-box">             <div class="ds-icon-box">
                 <svg class="ds-svg" viewBox="0 0 140 90">                 <svg class="ds-svg" viewBox="0 0 140 90">
-                    <!-- 复杂的网状连线 --> 
-                    <!-- 外圈连接 --> 
                     <line x1="70" y1="10" x2="20" y2="40" class="ds-line" />                     <line x1="70" y1="10" x2="20" y2="40" class="ds-line" />
                     <line x1="70" y1="10" x2="120" y2="40" class="ds-line" />                     <line x1="70" y1="10" x2="120" y2="40" class="ds-line" />
行 197: 行 166:
                     <line x1="120" y1="40" x2="100" y2="80" class="ds-line" />                     <line x1="120" y1="40" x2="100" y2="80" class="ds-line" />
                     <line x1="40" y1="80" x2="100" y2="80" class="ds-line" />                     <line x1="40" y1="80" x2="100" y2="80" class="ds-line" />
-                     
-                    <!-- 内部交叉连接 (制造复杂感) --> 
                     <line x1="70" y1="10" x2="40" y2="80" class="ds-line" />                     <line x1="70" y1="10" x2="40" y2="80" class="ds-line" />
                     <line x1="70" y1="10" x2="100" y2="80" class="ds-line" />                     <line x1="70" y1="10" x2="100" y2="80" class="ds-line" />
                     <line x1="20" y1="40" x2="120" y2="40" class="ds-line" />                     <line x1="20" y1="40" x2="120" y2="40" class="ds-line" />
- +                    <circle cx="70" cy="10" r="6" class="ds-shape" /> 
-                    <!-- 节点：五边形布局 --> +                    <circle cx="20" cy="40" r="6" class="ds-shape-2" /> 
-                    <circle cx="70" cy="10" r="6" class="ds-shape" />   <!-- Top --> +                    <circle cx="120" cy="40" r="6" class="ds-shape-2" /> 
-                    <circle cx="20" cy="40" r="6" class="ds-shape-2" /> <!-- Left --> +                    <circle cx="40" cy="80" r="6" class="ds-shape-3" /> 
-                    <circle cx="120" cy="40" r="6" class="ds-shape-2" /> <!-- Right --> +                    <circle cx="100" cy="80" r="6" class="ds-shape-3" />
-                    <circle cx="40" cy="80" r="6" class="ds-shape-3" /> <!-- Bot Left --> +
-                    <circle cx="100" cy="80" r="6" class="ds-shape-3" /> <!-- Bot Right -->+
                 </svg>                 </svg>
             </div>             </div>
行 215: 行 180:
             <p class="example">例：互联网、神经网络、交通图</p>             <p class="example">例：互联网、神经网络、交通图</p>
         </div>         </div>
- 
     </div>     </div>
 </div> </div>
- 
 </body> </body>
 </html> </html>
  
 +=== 2.1 集合 (Set) ===
 +  *   **特性**：元素之间除了“同属于一个集合”外，无其他关系。
 +  *   **操作**：主要涉及并集、交集、差集、判断元素是否存在。
 +
 +=== 2.2 线性结构 (Linear) ===
 +  *   **特性**：存在唯一的“第一个”和“最后一个”元素；除首尾外，每个元素都有且仅有一个前驱和一个后继。
 +  *   **典型代表**：
 +    *   **数组 (Array)**：连续存储。
 +    *   **链表 (Linked List)**：离散存储。
 +    *   **栈 (Stack)**：后进先出 (LIFO)，如弹夹。
 +    *   **队列 (Queue)**：先进先出 (FIFO)，如排队。
  
-==== 3. 存储结构：数据在“内存”中的样子 ====+=== 2.3 树状结构 (Tree) === 
 +  *   **特性**：存在一个根节点；每个节点可以有多个子节点，但只能有一个父节点（根除外）。 
 +  *   **典型代表**：二叉树、红黑树、B树（数据库索引常用）。
  
-这是逻辑结构的物理实现。+=== 2.4 图形结构 (Graph) === 
 +  *   **特性**：最复杂的结构，节点（顶点）之间可以任意连接（边）。 
 +  *   **分类**：有向图 vs 无向图；带权图 vs 无权图。
  
-=== 3.1 顺序存储 vs 链式存储 ===+==== 3. 存储结构：数据在“内存”中的物理形态 ====
  
-^ 特性 ^ 顺序存储 (数组) ^ 链式存储 (链表) ^ +逻辑结构是“想出来的”，存储结构是“写在内存条上的”。
-| **物理位置** | 必须相邻 | 可以散落在内存各处 | +
-| **优点** | **查找快** (直接算地址)，存储密度大 | **增删快** (改指针即可)，不需预分配 | +
-| **缺点** | 插入删除需移动元素 | 查找慢 (必须从头找)，指针占空间 |+
  
-=== 3.2 进阶存储方式 ===+=== 3.1 顺序存储 (Sequential Storage) === 
 +  *   **原理**：把逻辑上相邻的元素存储在**物理位置也相邻**的存储单元中。 
 +  *   **代表**：数组 (Array)。 
 +  *   **优点**： 
 +    *   **随机访问**：可以通过下标 $index$ 瞬间找到地址：$Addr = Start + index \times size$。时间复杂度 $O(1)$。 
 +    *   **存储密度高**：不需要额外空间存指针。 
 +  *   **缺点**： 
 +    *   **插入删除困难**：插入一个元素，后面的所有元素都要往后挪，效率低。 
 +    *   **大小固定**：需要预先分配空间，容易浪费或溢出。
  
-  * **索引存储**：建立一张“目录表”。先查目录找到地址，再找内容。（类似字典的拼音索引）。 +=== 3.2 链式存储 (Linked Storage) === 
-  * **散列存储 (Hash)**：**速度之王**。 +  *   **原理**：逻辑上相邻的元素在物理上可以**不相邻**。通过“指针” (Pointer) 链接。 
-    * //原理//：通过公式直接算出地址。 +  *   **代表**：链表 (Linked List)。 
-    * //例子//：存 `105`，公式 `key % 10`，直接扔进 `5` 号房间。查找时直接去 `5` 号拿。+  *   **优点**： 
 +    *   **插入删除快**：只需要修改指针指向，不需要移动数据。 
 +    *   **动态扩展**：有多少数据申请多少内存，不浪费。 
 +  *   **缺点**： 
 +    *   **无法随机访问**：想找第10个元素，必须从第1个顺藤摸瓜找下去。时间复杂度 $O(n)$。 
 +    *   **空间开销**：每个数据都要额外存一个指针地址。 
 + 
 +=== 3.3 索引存储与散列存储 === 
 +  *   **索引存储 (Index)**：建立附加的索引表（类似字典目录）。虽然检索快，但增加了索引表的空间开销和维护成本。 
 +  *   **散列存储 (Hash)**：**速度之王**。 
 +    *   不通过比较，而是通过公式（哈希函数）直接计算出存储地址。 
 +    *   **冲突 (Collision)**：当不同的数据算出了相同的地址时，需要特殊处理（如拉链法）。
  
 ===== 第二部分：算法 (Algorithm) ===== ===== 第二部分：算法 (Algorithm) =====
  
-==== 1. 算法效率度量 (Big O) ====+算法是解决特定问题求解步骤的描述。一个好的算法应该具备：**正确性、可读性、健壮性、高效率**。 
 + 
 +==== 1. 算法效率度量：大O记号 ====
  
-我们用 **大O记号** 表示随着数据量 $n$ 增大，耗时增长的趋势。+我们不计算具体的秒数（因为这取决于机器性能），而是计算**操作步骤数量随数据量 $n$ 的增长趋势**。
  
 <html> <html>
行 293: 行 289:
         transition: width 1s ease-out;         transition: width 1s ease-out;
     }     }
-    /* 颜色定义 */ 
     .bg-green { background-color: #2ecc71; width: 10%; }     .bg-green { background-color: #2ecc71; width: 10%; }
     .bg-blue { background-color: #3498db; width: 25%; }     .bg-blue { background-color: #3498db; width: 25%; }
行 325: 行 320:
 </html> </html>
  
 +=== 1.1 常见复杂度详解 ===
  
-  * **$O(1)$ 常数阶**：无论数据多少，耗时不变。 +  *   **$O(1)$ 常数阶**：代码执行次数固定，不随数据增加而增加。 
-  * **$O(n)$ 线性阶**：数据翻倍，耗时翻倍。 +<code c> 
-  * **$O(n^2)$ 平方阶**：数据翻倍，耗时变 4 倍（双层循环）。 +    int n = 10000; 
-  * **$O(\log_2 n)$ 对数阶**：非常快（二分查找）。+    x = n + 1; // 无论n多大，这行只执行一次 
 +</code> 
 +  *   **$O(n)$ 线性阶**：一层循环。 
 +<code c> 
 +    for(int i=0; i<n; i++) { ... } 
 +</code> 
 +  *   **$O(n^2)$ 平方阶**：双层嵌套循环。 
 +<code c> 
 +    for(int i=0; i<n; i++) { 
 +        for(int j=0; j<n; j++) { ... } 
 +    } 
 +</code> 
 +  *   **$O(\log n)$ 对数阶**：每次循环，数据量都砍半（如二分查找）。 
 +<code c> 
 +    while(n > 1) { 
 +        n = n / 2; // 1024 -> 512 -> 256 ... 10次就到了 
 +    } 
 +</code>
  
 ===== 第三部分：五大常用算法思想详解 ===== ===== 第三部分：五大常用算法思想详解 =====
 +
 +这是算法的灵魂，掌握这些思想比背诵代码更重要。
  
 ==== 1. 穷举法 (Brute Force) ==== ==== 1. 穷举法 (Brute Force) ====
-  * **核心**：暴力破解，试遍所有可能。 
-  * **优化**：**剪枝 (Pruning)**。如果在搜索过程中发现当前路径不可能成功，就直接放弃，不再往下试（剪掉树枝）。 
  
 +  *   **别名**：暴力破解法。
 +  *   **核心**：列出所有可能的情况，逐一验证。
 +  *   **优点**：逻辑简单，几乎适用于所有问题，保证能找到解（如果存在）。
 +  *   **缺点**：效率极低。
 +  *   **案例**：破解4位数字密码。从 `0000` 试到 `9999`，最多试 10000 次。
  
 ==== 2. 分治法 (Divide and Conquer) ==== ==== 2. 分治法 (Divide and Conquer) ====
  
-  * **核心口诀**：**分而治之，各个击破**。 +  *   **核心口诀**：**分而治之，各个击破**。 
-  * **三个步骤**： +  *   **适用场景**：问题可以拆解为多个独立的子问题，且子问题与原问题结构相同。 
-    - 1. **分解 (Divide)**：将大问题分解为若干个规模较小的同类子问题。 +  *   **典型应用**：归并排序 (Merge Sort)、快速排序 (Quick Sort)、MapReduce (大数据处理)。
-    - 2. **解决 (Conquer)**：递归地解决这些子问题。 +
-    - 3. **合并 (Combine)**：将子问题的解合并为原问题的解。 +
-  * **经典案例**：归并排序、快速排序、二分查找。+
  
 <html> <html>
行 374: 行 389:
 <body> <body>
 <div class="dc-wrapper"> <div class="dc-wrapper">
-    <!-- Level 1 --> 
     <div class="dc-block" style="width: 200px; background: #33691e;">大问题 (排序 8 个数)</div>     <div class="dc-block" style="width: 200px; background: #33691e;">大问题 (排序 8 个数)</div>
     <div class="dc-arrow">↓ 拆分 (Divide)</div>     <div class="dc-arrow">↓ 拆分 (Divide)</div>
-    <!-- Level 2 --> 
     <div>     <div>
         <div class="dc-block" style="width: 90px; background: #558b2f;">子问题 A</div>         <div class="dc-block" style="width: 90px; background: #558b2f;">子问题 A</div>
行 383: 行 396:
     </div>     </div>
     <div class="dc-arrow">↓ 递归解决 (Conquer)</div>     <div class="dc-arrow">↓ 递归解决 (Conquer)</div>
-    <!-- Level 3 --> 
     <div>     <div>
         <div class="dc-block">A1</div><div class="dc-block">A2</div>         <div class="dc-block">A1</div><div class="dc-block">A2</div>
行 394: 行 406:
 </html> </html>
  
 +==== 3. 动态规划 (Dynamic Programming, DP) ====
  
-==== 3. 动态规划 (Dynamic Programming) ==== +  *   **核心**：**历史记录**。通过空间换时间。 
- +  *   **原理**：将复杂问题分解为子问题，但与分治法不同的是，DP 的子问题是**重叠**的。为了避免重复计算，DP 会把每个子问题的结果**存进一张表**里。 
-  * **核心**：**拒绝重复劳动**。 +  *   **案例：斐波那契数列** (1, 1, 2, 3, 5, 8...) 
-  * **原理**：把大问题拆成小问题，但**每个小问题的结果都存起来**（通常存在数组或表中）。下次需要时，直接查表，不用重新算。 +    *   求第 5 个数：$F(5) = F(4) + F(3)$ 
-  * **适用场景**：求最值（最长路径、最大价值）、背包问题。 +    *   求 $F(4)$ 时需要算 $F(3) + F(2)$。 
-  * **与分治法的区别**：分治法的子问题是独立的；DP 的子问题是有重叠的。+    *   **注意**：$F(3)$ 被计算了两次！如果是递归，$n$ 很大时重复计算量是指数级的。 
 +    *   **DP做法**：算完 $F(3)$ 就把它记在本子上，下次直接看本子。
  
 <html> <html>
行 463: 行 477:
 </body> </body>
 </html> </html>
- 
  
 ==== 4. 贪心算法 (Greedy) ==== ==== 4. 贪心算法 (Greedy) ====
  
-  * **核心**：**目光短浅，只看眼前**。 +  *   **核心**：**活在当下**。 
-  * **策略**：在每一步选择中都采取在当前状态下最好（即最有利）的选择，希望最后堆出来的结果也是全局最好的。 +  *   **策略**：每一步都做出在当前看来最好的选择。它不从整体最优考虑，但在很多情况下（如最小生成树），局部最优能导致全局最优。 
-  * **局限**：不能保证一定是全局最优解（比如走迷宫，一直往目标方向走可能会走进死胡同）。 +  *   **案例：找零钱** 
-  * **经典案例**：找零钱问题（优先用大面额）、霍夫曼编码。+    *   问题：找 66 元，纸币规格有 100, 50, 20, 10, 5, 1。 
 +    *   贪心策略：优先用面值最大的。 
 +    *   步骤： 
 +        *  66 < 100，跳过。 
 +        *  66 >= 50，**给一张 50**。剩 16。 
 +        *  16 < 20，跳过。 
 +        *  16 >= 10，**给一张 10**。剩 6。 
 +        *  6 >= 5，**给一张 5**。剩 1。 
 +        *  **给一张 1**。结束。 
 +  *   **局限**：如果纸币规格是 1, 3, 4，找 6 元。贪心会给 4+1+1 (3张)，但最优解是 3+3 (2张)。此时贪心失效，需用 DP。
  
 ==== 5. 回溯法 (Backtracking) ==== ==== 5. 回溯法 (Backtracking) ====
  
-  * **核心**：**不撞南墙不回头**。 +  *   **核心**：**试错与回退**。 
-  * **策略**：一条路走到黑，发现走不通了，就退回到上一个路口（回溯），换一条路继续走。 +  *   **策略**：这是一种深度优先搜索 (DFS)。一条路走到黑，如果发现走不通（不满足条件），就**回溯**到上一个路口，换一条路继续走。 
-  * **本质**：深度优先搜索 (DFS) 的一种形式。 +  *   **剪枝 (Pruning)**：在搜索过程中，如果发现当前分支已经不可能找到解，就直接切断该分支，不再往下搜，大大提高效率。 
-  * **经典案例**：八皇后问题、走迷宫、数独。+  *   **典型应用**：走迷宫、八皇后问题、数独。
  
 <html> <html>
行 498: 行 520:
         transition: all 0.5s;         transition: all 0.5s;
     }     }
-    /* 模拟路径 */ +    .p1 { top: 50px; left: 10px; width: 40px; height: 10px; }  
-    .p1 { top: 50px; left: 10px; width: 40px; height: 10px; } /* 起点 */ +    .p2 { top: 20px; left: 40px; width: 10px; height: 40px; }  
-    .p2 { top: 20px; left: 40px; width: 10px; height: 40px; } /* 向上尝试 */ +    .p3 { top: 20px; left: 40px; width: 40px; height: 10px; background: #f44336; }  
-    .p3 { top: 20px; left: 40px; width: 40px; height: 10px; background: #f44336; } /* 死路 */ +    .p4 { top: 50px; left: 40px; width: 60px; height: 10px; }  
-     +    .p5 { top: 50px; left: 90px; width: 10px; height: 40px; }  
-    .p4 { top: 50px; left: 40px; width: 60px; height: 10px; } /* 回溯后向右 */ +    .p6 { top: 80px; left: 90px; width: 60px; height: 10px; background: #4caf50; } 
-    .p5 { top: 50px; left: 90px; width: 10px; height: 40px; } /* 向下 */ +
-    .p6 { top: 80px; left: 90px; width: 60px; height: 10px; background: #4caf50; } /* 通路 */ +
-    +
     .bt-label {     .bt-label {
         position: absolute;         position: absolute;
行 522: 行 541:
         <div class="bt-path p3"></div>         <div class="bt-path p3"></div>
         <div class="bt-label" style="top:5px; left:50px; color:#ff8a80;">X 死路</div>         <div class="bt-label" style="top:5px; left:50px; color:#ff8a80;">X 死路</div>
-         
         <div class="bt-path p4"></div>         <div class="bt-path p4"></div>
         <div class="bt-path p5"></div>         <div class="bt-path p5"></div>
行 532: 行 550:
 </body> </body>
 </html> </html>
-</html> 
- 
-===== 总结 ===== 
- 
-学习数据结构与算法，不是为了死记硬背代码，而是为了培养**“计算思维”**： 
  
-  - 遇到复杂问题 -> **分治** +===== 总结：如何选择算法？ =====
-  - 遇到重复计算 -> **动态规划** +
-  - 需要快速试错 -> **回溯** +
-  - 需要资源最优 -> **贪心**+
  
-希望这份可视化的笔记能帮助你建立起知识框架！+| 场景特点 | 推荐策略 | 核心思想 | 
 +| 问题可拆分，子问题独立 | **分治法** | 大事化小 | 
 +| 问题可拆分，子问题重叠 | **动态规划** | 拒绝健忘，查表 | 
 +| 需要快速找到一个可行解 | **贪心算法** | 目光短浅，先拿再说 | 
 +| 需要遍历所有解或路径 | **回溯法** | 不撞南墙不回头 | 
 +| 没有任何规律 | **穷举法** | 暴力出奇迹 |
Detach Close

该主题尚不存在

您访问的页面并不存在。如果允许，您可以使用创建该页面按钮来创建它。

  • 数据结构/绪论.1765440887.txt.gz
  • 最后更改: 2025/12/11 16:14
  • 由 张叶安