数据结构第一章绪论

#概念和术语

  • 数据：就是数据
  • 数据元素：就是数据里的每个独立元素
  • 数据对象：是具有相同性质的数据元素的集合，是数据的一个子集
  • 数据类型：原子类型，结构类型，抽象数据类型 PS：建议看书的小定义
  • 数据结构：包含三方面的内容：逻辑结构，存储结构，数据的运算
  • 数据的逻辑结构与存储结构密不可分：算法的设计取决于采用的逻辑结构，算法的实现则依赖于所选取的存储结构。

    • #数据的逻辑结构

  • 数据的逻辑结构可以分为线性结构和非线性结构
  • 线性结构，如线性表
  • 非线性结构，如图，树，集合等
  • （1）集合：结构中的元素除了同属于一个集合外别无其他关系
  • （2）线性结构：结构中的数据元素仅存在一对一的关系
  • （3）树状结构：结构中的数据元素存在一对多的关系
  • （4）图(网)状结构：结构中的数据元素存在多对多的关系

    • #数据的存储结构

  • 数据的存储结构可分为：顺序存储，链式存储，索引存储，散列存储
  • （1）顺序存储：逻辑上相邻的元素物理上存储也是相邻的。优点是可实现随机存取，缺点是要求使用连续的存储空间，可能导致较多的外部碎片。
  • （2）链式存储：不要求逻辑上相邻的元素物理上也相邻，通过指针存储地址来表示逻辑关系。优点是不会出现碎片化，能充分利用空间，缺点是每个元素因为指针而额外占用存储空间，且只能顺序存取。
  • （3）索引存储：在存储信息的同时，额外建立索引表。索引表中的每项称之为索引项，包含关键字及其地址。优点是检索速度快，缺点是需要额外时间来建立索引表，且增加或删除数据时也要更新索引表，带来额外开销。
  • （4）散列(哈希Hash)存储：根据元素的关键字计算出存储地址。优点是检索，插入，删除的速度都很迅速，缺点是若是散列函数设计不当，可能会产生哈希冲突，解决冲突会增大时间空间开销。

    • #数据的运算

  • 数据的运算包含定义和实现两方面。
  • 定义：针对逻辑结构，说明运算的功能。
  • 实现：基于存储结构，描述具体的操作步骤。
  • PS：没考啥，一笔带过，但就两句话，不如记下，免得被阴

    • #算法和算法评价

    算法

    算法评价