第 2 章 线性表

【考纲内容】

1. 线性表的基本概念

2. 线性表的实现
   顺序存储; 链式存储

3. 线性表的应用

【知识框架】

• 线性表
  • 顺序存储——顺序表
  • 链式存储
    • 单链表（指针实现）
    • 双链表（指针实现）
    • 循环链表（指针实现）
    • 静态链表（借助数组实现）

【复习提示】

线性表是算法题命题的重点。这类算法题的实现比较容易且代码量较少, 但是要求具有最优的性能 (时间/空间复杂度), 才能获得满分。因此, 应牢固掌握线性表的各种基本操作 (基于两种存储结构), 在平时的学习中多注重培养动手能力。另需提醒的是, 算法最重要的是思想! 考场上的时间紧迫, 在试卷上不一定要求代码具有实际的可执行性, 因此应尽力表达出算法的思想和步骤, 而不必过于拘泥所有细节。此外, 采用时间/空间复杂度较差的方法也能拿到大部分分数, 因此在时间紧迫的情况下, 建议直接采用暴力法。注意, 算法题只能用 C/C++ 语言实现。