数据结构绪论

数据结构绪论读书笔记分享！下图详细地介绍了数据结构的基本概念、逻辑结构、存储结构和算法设计与分析的基本概念、基本算法和算法分析。期末复习时有这一份思维导图就够啦！

数据结构理论

• 数据结构概念
  • 基本概念
    • 数据
      • 对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
    • 数据元素
      • 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据元素又可称为元素，节点记录。
    • 数据项
      • 数据元素可以由若干个数据项组成。数据项还可区分为组项和基本项，组项可以由更小的组项和基本项构成，而基本项则是具有独立含义的最小标识单位。
    • 数据对象
      • 数据元素的集合构成一个数据对象，它针对某种特定的应用。注意，本书所说数据对象不是面向对象系统中所指的数据对象，后者还需要考虑对象所包含的操作。
    • 数据结构
      • 1. 数据结构指某一数据对象中的所有数据元素及他们之间的关系。完整的定义为：数据结构={D, R}; 其中D是某一数据对象； R是该对象中所有数据元素之间的关系的有限集合。
      • 2.数据结构是指数据元素间的逻辑关系，即数据的逻辑结构。它可以看作是从具体问题抽象出来的数据模型，与数据的存储无关。
      • 3. 4类基本结构：集合，线性结构，树形结构，图状结构或网状结构
    • 数据类型
      • 1.数据类型是一个值的集合和定义在这个值集合上的一组操作的总称。
      • 2.数据类型可分为两大类：基本数据类型和构造数据类型
        • 基本数据类型可以看作是计算机中已经实现的数据结构。例如，C语言中的字符型(char), 整型(int), 浮点型(float),双精度型(double)和无值（void),可直接使用由它们定义的变量和相应的操作。
        • 构造数据类型由基本数据类型或构造数据类型组成，在应用中可视为一种数据模型。构造数据类型由不同成分类型构成，在C语言中用typedef struct来定义。
    • 抽象数据类型
      • 抽象数据类型是一种构造数据类型，它具有三大特征：信息隐蔽，数据封装，使用与实现相分离。
      • 把数据类型的存储结构和操作的实现细节隐藏起来，使得使用者只能通过类型提供的操作来存取他们，这样，如果想修改类型的存储结构或操作的实现，只要呈现在使用者面前的使用方式不变，整个程序都不必大概。修改的局部化将大大提高程序的可修改习性。
  • 逻辑结构
    • 逻辑结构
      • 数据结构定义中的关系描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构
    • 逻辑结构分类
      • 数据的逻辑结构分为线性结构，树形结构，图结构和集合结构。
    • 逻辑结构特点
      • 线性结构中元素之间的关系是一对一的，集合结构中元素之间的关系为空，树形结构中元素之间的关系是一对多的，图结构中元素之间的关系是多对多的。集合结构的实现往往采用其他逻辑结构的存储表示。
  • 存储结构
    • 存储结构
      • 数据结构在计算机中的表示(又称映像)称为数据的物理结构，又称为存储结构。它包含数据元素的表示和关系的表示。
    • 存储结构分类
      • 数据存储结构分为4类： 顺序存储，链接存储，索引存储，散列存储。
      • 在内存中组织各种数据结构，可采用顺序存储或链接存储。顺序存储采用连续的存储区域相继存放数据元素；链接存储采用链表存储数据元素并通过各个元素附加的指针将它们按其逻辑顺序链接起来。
      • 对于数量特别大的数据元素集合，一般需要存放于外存中。因此，有索引存储和散列存储。索引存储通过建立索引表来组织所有数据元素，散列存储通过散列函数直接把数据记录的关键码映射为该元素的存放地址。
• 算法设计与分析
  • 基本概念
    • 算法
    • 算法特性
    • 算法评价标准
    • 算法描述语言
    • 算法设计步骤
  • 基本算法
    • 穷举法
    • 递推法
    • 迭代法
    • 递归法
  • 算法分析
    • 事后测量
    • 事前估计
    • 问题规模
    • 执行频度
    • 时间复杂度
    • 空间复杂度