数据结构–第一章概念总结

用于自己考研复习的笔记。

0. 教材

电子工业出版社 数据结构算法与分析第三版 Clifford A.Shaffer

1. 数据结构

• 数据类型:是一个值的集合以及在这些值上定义的一组操作的总称。

  在高级语言程序中又分为:非结构的原子类型和结构类型

• 抽象数据类型（AD T):是指一个数学模型以及定义在该模型上的一组操作。

  一个抽象的数据类型的软件模块通常包含定义和表示和实现
  用三元组（D， S，P): 数据对象、数据关系、基本操作

• 数据结构:指的是数据之间的相互关系，即数据的组织形式。

  一般包括三个方面的内容:数据的逻辑结构、物理存储结构和数据的运算。

• 常用的物理存储表示方法有四种:

  • 顺序存储方法:它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的
    逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。
  • 链接存储方法:它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是
    由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。
  • 索引存储方法:除建立存储结点信息外，还建立附加的索引表来标识结点的地址。
  • 散列存储方法:就是根据结点的关键字直接计算出该结点的存储地址。

• 逻辑结构有 线形结构，树型结构，图形结构，集合四种。

算法

书上有一些挺有意思的说法，上限，下限和Θ表示法