第一章 绪论

  1. 数据结构的三要性: 逻辑结构,存储结构,数据的运算. 要能够明白三者的联系, 元素之间的对应关系就是逻辑结构
  2. 算法是: 对特定问题求解步骤的一种描述
  3. 要区分一些术语是 数据结构 还是 逻辑结构 还是存储结构 比如 线性表就是逻辑结构, 顺序表和链表就是数据结构

第二章 线性表

  1. 定义: 相同数据类型的有序集合 线性表的起始下标从1开始 而数组从0开始
  2. 顺序存储实现线性表: 顺序表, 优点: 可以随机访问, 存储密度大 缺点: 插入删除需要大量移动操作,需要物理上连续的存储单元
  3. 链式存储实现线性表: 链表, 优点: 插入删除较快, 不需要物理上连续的存储单元 缺点: 不支持随机访问,需要额外存储空间来存放指针
  4. 链表存储中分为 带头结点 和 不带 头结点, 带头结点能够简化链表的实现, 无论链表是否有元素, 都有一个头结点, 这样就得到统一, 比如插入元素的时候, 不需要判断链表是否为空
  5. 头插法实现简单 但是插入顺序与访问顺序相反了, 尾插法做到插入语访问顺序相同, 但是需要额外记录尾指针
  6. 无论是怎么样的线性表实现 在运算方法完成后 都要维护它具有的特性, 单链表需要维护next指针, 双链表需要维护pre 和 next 循环链表在上面两种类型链表的基础上还要额外维护 头结点和最后一个结点的pre 和 next
  7. 根据第6点, 在选择何种线性表的时候, 我们不能单纯的判断那个操作的时间复杂度, 我们还要考虑维护这种线性表需要的时间