datetime:2022-04-09 17:46
author:nzb

数据结构与算法

绪论

  • 基本概念

    • 数据

    • 数据元素、数据项

    • 数据对象、数据结构

    • 数据类型、抽象数据类型（ADT）

  • 数据结构三要素

    • 逻辑结构

      • 集合

      • 线性结构

      • 树形结构

      • 图状结构（网状结构）

    • 物理结构（存储结构）

      • 顺序存储

        物理内存中是连续的

      • 非顺序存储

        物理内存中是分散的

        • 链式存储

        • 索引存储

        • 散列存储

    • 数据的运算

  • 学习建议

    • 概念多，比较无聊。抓大放小，重要的是形成框架，不必纠结细节概念。

串

字符串

  • 定义

    • 串，即字符串（string）是由零个或多个字符组成的有限序列

    • 术语：串长、空串、空格串、子串、主串、字符在主串中的位置、子串在主串中的位置

  • 串 V.S 线性表

    • 串的数据对象限定为字符集

    • 串的基本操作大多以“子串”为操作对象

  • 基本操作

    • 定位操作

    • 比较操作

  • 字符集编码

    每个字符在计算机中对应一个二进制数，比较字符的大小其实就是比较二进制数的大小

  • 存储结构

    顺序存储和链式存储跟线性表一样

    • 顺序存储

      • 静态数组

      • 动态数组

    • 链式存储

      可让每个结点存多个字符，没有字符的位置使用“#” 或 “\0”补足

    • 静态数组

    • 基本操作

      • 求子串

      • 串的比较

      • 求串在主串中的位置

  • 子串匹配算法

    • 朴素模式匹配算法

      • 串的模式匹配：在主串中找到与模式串相同的子串，并返回其所在的位置

      • 朴素模式匹配算法（简单模式匹配算法）思想

        • 将主串中与模式串长度相同的子串搞出来，挨个与模式串对比

        • 当子串与模式串某个对应字符不匹配时，就立即放弃当前子串，转而检索下一个子串

      • 若模式串长度为 m，主串长度为 n，则直到匹配成功/匹配失败最多需要（n - m + 1）* m次比较

        • 最坏时间复杂度：O(nm)

        • 最坏情况：每个子串的前 m- 1个字符都和模式串匹配，只有第 m 个字符不匹配

        • 比较好的情况：每个子串的第 1 个字符就与模式串不匹配

    • KMP 算法

      • 粗劣分析算法性能

      • KMP 算法优化

    • 二者比较

      • 朴素模式匹配算法的缺点：当某些子串与模式串能部分匹配时，主串的扫描指针 i 经常回溯，导致时间开销增加。最坏时间复杂度 O(nm)

      • KMP 算法：当子串和模式串不匹配时，主串指针 i 不回溯，模式串指针 j = next[j]

        如果不会经常出现子串与模式串部分匹配的时候，KMP 算法性能也不会比朴素算法好多少

        • 算法平均时间复杂度：O(n + m)

        • next 数组手算方法：当第 j 个字符匹配失败，由前 1~j - 1 个字符组成的串记为 S，则：next[j] = S 的最长相等前后缀长度 + 1

        • 特别的：next[1] = 0, next[2] = 1

results matching ""

    No results matching ""