线性表

[yangsirgo]

考点分析

概念

1. 顺序表：

   • 线性表顺序存储：用一组地址连续的存储单元一次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素，物理上也相邻。
   • 空间事先确定，后续不好拓展。
   • 只存储了数据元素，没有存储元素的逻辑关系，所以存储密度是1。

2. 链表：

   • 线性表的链式存储：指针链接起来的结点存储数据元素，物理上不要求连续。
   • 后期拓展方便。
   • 因为物理上不连续，需要存储逻辑关系，存储密度小于1.

3. 顺序表和链表的对比：

4. 链表的分类：单链表，双链表，循环链表。
5. 特殊的线性表：
   • 队列：先进先出
   • 栈：先进后出

[yangsirgo]

循环队列

• 队空条件： head = tail
• 队满条件也是队空条件，如何区分队空和队满： 写入队满字段比较麻烦，队满了就少存一个。循环队列有5个成员，队满是存四个（少存一个）。尾指针的下一个元素是头指针就是队满。（tail + 1）% size