学习笔记——《大话数据结构》Ch1, Ch2 基础知识

第1章、数据结构绪论

  • 数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。

  • 数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。

  • 数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。

  • 数据项：一个数据元素可以由若干个数据项组成。是数据不可分割的最小单位。

  • 数据对象：是性质相同的数据元素的集合，是数据的子集。

  • 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

  • 逻辑结构：数据对象中数据元素之间的相互关系。包括集合结构、线性结构、树形结构、图形结构等。

  • 物理结构：数据的逻辑结构在计算机中的存储形式。包括顺序存储结构、链式存储结构等。

  • 抽象数据类型：（Abstract Data Type, ADT）：指一个数学模型及定义在该模型上的一组操作。

第2章、算法

  • 算法：是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

  • 算法特性：

    • 输入输出：输入个数>=0，输出个数>=1。
    • 有穷性：（现实意义下的）有限步骤后，自动结束。
    • 确定性：每一步骤都有确定的含义，没有二义性。
    • 可行性：每一步都能通过执行有限次数完成。

  • 算法设计要求：

    • 正确性：能正确反映问题、得到问题的正确答案。其中如何定义“正确”？分为4个阶段：(1) 无语法错误；(2) 合法的输入产生满足预期的结果；(3) 非法的输入不会崩溃，而是产生符合规格说明的结果；(4) 对所有输入（甚至刁难的测试数据）都能产生合规的结果。通常达到(3) 这一级就称为“正确”的算法，而(4)不可能通过穷举输入证明，只能通过数学理论逻辑推导来证明，代价非常高，不实用。
    • 可读性：设计算法的另一目的是便于阅读、理解和交流。（有时为了可读性，略微牺牲一点效率和增加一些代码量是必要的，但要注意尺度把握。有人可能不同意牺牲一定的效率来换取更好的可读性，那么，汇编的执行效率比高级语言更高，难道我们都要回到汇编时代吗？只要时间复杂度f(n)同等量级，通常可以接受）
    • 健壮性：当输入不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。
    • 高时间效率和高空间利用率。

  • 算法效率的度量方法：

    • 事后统计：即测试，通常发生在开发完成之后，不能预先发现问题从而指导算法。
    • 事前估算：设计算法之间就比较各种方案的时间和空间复杂度，选用最优生策略。

  • 函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个 整数N，使得对于所有的n>N，f(n)总是比g(n)大，则称f(n)的渐近增长快于g(n)。

  • 算法的时间复杂度：在进行算法分析时，语句的总执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级，是算法时间量度。记为T(n)=O(f(n))。通常以最坏情况运行时间（而非平均运行时间）来代表时间复杂度。

  • 常见的时间复杂度：

  • 空间复杂度：计算算法所需的存储空间，记为S(n)=O(f(n))。