2.线性表

顺序表与链表

• 顺序表：数组
• 链表：单向链表、双向链表
• 两者的比较
  • 时间性能
    • 链表：增删快（O(1)），改查慢（O(n)）
    • 顺序表：增删慢（O(n)），改查慢（O(1)）
  • 空间性能
    • 顺序表：需要预分配存储空间。大了，浪费；小了，有溢出风险
    • 链表：不需要预分配空间。

队列与栈

队列

• 特点：先进先出（FIFO）

• 顺序存储实现

  • 元素：一维数组、头元素位置front、尾元素位置rear组成
  • 运算：增加一个元素，rear+1，减少一个元素，front+1
  • 顺序存储环环队列 （256与unsigned char）
  • 问题：当队列为满或为空时，rear与front都是相等的
  • 解决方法：即留一个空位。if（rear+1 == front）//满

• 队列的链式存储实现

  单链表，保存下头尾节点，头插、尾删。

栈

• 特点：后入先出：Last In First Out（LIFO）

• 栈的顺序存储实现

  数组和一个记录栈顶元素位置的变量

• 栈的链式存储实现

  一个单链表，叫做链栈。插入和删除只在栈顶进行。