考研408-数据结构

王道计算机考研408《 数据机构》课程笔记， 考研数据结构知识点总结，详细的总结了基本概念，三要素是逻辑结构，物理结构，数据的运算。

数据结构

• 基本概念
  • 数据
    • 什么是数据？
      • 数据是信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中，并被计算机识别和处理的符号集合。数据是计算机程序的加工原料
  • 数据元素、数据项
    • 什么是数据元素？
      • 数据元素是数据的基本单位，通常作为一个整体进行考虑和处理
    • 什么是数据项？
      • 一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位
  • 数据对象、数据结构
    • 结构
      • 各个元素之间的关系
        • 举例：中文字中的结构
    • 数据结构
      • 数据结构是相互之间存在一种或多种特定关系的数据元素的集合
    • 数据对象
      • 数据对象数具有相同性质的数据元素的集合，是数据的一个子集
  • 数据类型、抽象数据类型(ADT)
    • 数据类型
      • 概念：
        • 数据类型是一个值的集合和定义在此集合上的一组操作的总称。（不好理解，其实就是int类型、string类型等）
      • 分类：
        • 1、原子类型
          • 其值不可再分的数据类型
            • 如：int类型、bool类型
        • 2、结构类型
          • 其值可以再分解为若干成分（分量）的数据类型（Java中的实体类）
    • 抽象数据类型(Abstract Data Type， ADT)
      • 是抽象数据组织及与之相关的操作
      • 在讨论数据结构时：
        • ① 定义逻辑结构（数据元素之间的关系）
        • ②定义数据的运算（针对现实需求，应该对这种逻辑结构进行什么样的运算）
        • ③确定某种存储结构，实现数据结构，并实现对一些数据结构的基本运算
• 三要素
  • 逻辑结构
    • 逻辑结构：数据元素之间的关系是什么？
    • 4大逻辑结构
      • 集合
        • 就是数学意义上的集合
          • • 基本上不讨论集合
      • 线性结构
        • 数据元素之间是一对一的关系。 除了第一个元素，所以元素都有唯一前驱； 除了最后一个元素，所以元素都有唯一后继
      • 树形结构
        • 数据元素之间存在一对多的关系
      • 图状结构(网状结构)
        • 数据元素之间是多对多的关系
          • • 如微信好友就是图结构，每一个用户被抽象成为一个数据元素
  • 物理结构（存储结构）
    • 数据的存储结构
      • 即如何用计算机表示数据元素的逻辑关系？
    • 数据的4种存储（物理）结构
      • 顺序存储
        • 举例：线性结构在计算机如何用顺序存储表示
        • 顺序存储，把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
        • • 顺序存储
      • 链式存储
        • 举例：线性结构在计算机如何用链式存储表示
        • 链式存储，逻辑上相邻的元素，在物理位置上可以不相邻，借助元素存储地址的指针来表示元素之间的关系。
      • 索引存储
        • 举例：线性结构在计算机如何用索引存储表示
        • 索引存储，在存储元素信息的的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引想的一般形式是（关键字，地址）
      • 散列存储
        • 散列存储，根据元素的关键字直接计算出该元素的存储地址，又称哈希(Hash)存储
      • 非顺序存储
      • 绪论部分只需要理解3点： 1、若采用顺序存储，则各个数据元素在物理上是连续的；若采用非顺序存储，则各个数据元素在物理上是离散的。 2、数据的存储结构会影响存储空间的分配的方便程度。(如有人插队，顺序存储需要都往后挪，非顺序存储则只需要一个优先拿号 ) 3、数据的存储结构会影响对数据运算的速度。（顺序存储方便查找，非顺序就没这么容易）
  • 数据的运算
    • 数据的运算
      • 施加在数据上对的运算包括运算的定义和实现。
        • 运算的定义是针对逻辑结构的，指出运算的功能；
        • 运算的实现时针对存储结构的，指出运算的具体操作步骤；
    • 举例：如海底捞叫号，是一种队列
      • 运算的定义
      • 运算的实现
• 学习建议： 1、概念多，比较无聊。抓大放小，重要的是形成框架，不必纠结于细节概念 2、经常总结，多看目录，知识点串起来。

算法的基本概念

• 什么是算法
  • 程序 = 数据结构 + 算法 + 文档
    • • 例如：设计一个算法，解决特点的问题：带小孩的顾客有限就餐
    • 数据结构：
      • 如何把现实世界的问题信息化，将信息存进计算机，同时还要实现对数据结构的基本操作
    • 算法：
      • 如何处理这些信息，以解决实际问题
        • 用有限步骤解决某个特定的问题
• 算法的5个特性
  • 1、有穷性
    • 一个算法必须执行在有穷步骤之后结束，且每一步都可在又穷时间内完成
      • 注：算法必须是有穷的，而程序可以是无穷的
  • 2、确定性
    • 算法中的每条指令必须有确切的含义，对于相同的输入只能得到相同的输出。
      • 例如：设计一个算法，解决特点的问题：带小孩的顾客有限就餐
        • • 这样得到不同的输出的，就不叫算法
  • 3、可行性
    • 算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现
  • 4、输入
    • 一个算法有零个或者多个输入，这些输入取自某个特定的对象的集合
  • 5、输出
    • 一个算法有一个或者多个输出，这些输出是与输入有着某种特定关系的量
• “好”的算法的特质
  • 1）正确性
    • 算法应能够正确地解决求解问题
  • 2）可读性
    • 算法应具备良好的可读性，以帮助人们理解
  • 3）健壮性
    • 输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果
      • 比如：出现bug，就需要明确提醒
  • 4）高效率
    • 执行速度快，时间复杂度低
      • 比如计算1+2+3+...+100, 使用高斯算法效率更快
  • 5）低存储量需求
    • 不费内存，空间复杂度低
  • 有关时间复杂度和空间复杂度后续有更详细剖析