数据结构知识点总结之线性表

数据结构

线性表

定义

• 相同数据元素的有限序列

存储结构

• 顺序存储

  • 存储密度大
  • 插入、删除麻烦

• 链式存储

  • 便于插入删除操作

分类

• 顺序表

• 链式表

  • 从一边遍历

    • 单向链表

      • 带头节点

        • 操作统一方便

      • 不带头节点

    • 双端链表

  • 从两边遍历

    • 双向链表

      • pre|data|next

  • 循环遍历

    • 单向

      • 插入

        • 连接
        • 修改

    • 双向

      • 插入

        • 先把插入节点前驱后继指针连接到链表上
        • 改变被插入节点的前驱后继

• 静态链表

  • data|cur

    • cur

      • 游标记录下一个节点在数组中的位置

    • 备用链表

      • 未使用数组部分

  • 特殊

    • 第一个元素（0）

      • data不存数据
      • cur存放备用链表第一个节点下标

    • 最后一个元素（maxsize-1）

      • 存放第一个有数值的元素下标

算法复杂度分析

应用

• 一元多项式

  • coef

    • 系数

  • expn

    • 指数

• 多项式相加