线性结构：一对一
非线性结构：多对一

2.1 线性表的定义和特点

1. 线性表定义： 线性表是具有相同特性的数据元素的一个有限序列：
   （a₁,a₂,…a_i-1,a_i,a_i+1,…,a_n）

   n=0时，为空表。

2. 线性表的逻辑特征：

• 在非空的线性表，有且仅有一个开始节点a₁，他没有直接前驱，而仅有一个直接后继a₂；
• 有且仅有一个终端节点a_n，它没有直接后继，而仅有一个直接前驱a_n-1；
• 其余的内部结点a_i（2<=i<=n-1）都有且仅有一个直接前驱a_i-1和一个直接后继a_i+1

线性表是一种典型的线性结构

2.2 案例引入

案例1. 一元多项式的运算：
案例2. 稀疏多项式————>用线性存储会浪费空间

顺序存储结构存在问题：

• 存储空间分配不灵活
• 运算的空间复杂度高

所以有些要用链式存储结构

案例3. 图书信息管理系统：
图书表抽象为线性表
表中每本图书抽象为线性表中数据元素
——————选择适当的存储结构，
——————实现此存储结构上的基本操作
——————利用基本操作完成功能

总结：

• 线性表中数据元素的类型可以分为简单类型，也可以分为复杂类型。
• 许多实际应用问题所涉的基本操作有很大相似性，不应为每个具体应用单独编写一个程序
• 从具体应用中抽象出共性的逻辑结构和基本操作（抽象数据类型），然后实现其存储结构和基本操作

2.3 线性的类型定义

2.4 线性表的顺序表示和实现

2.5 线性表的链式表示和实现

2.6 顺序表和链表的比较

2.7 线性表的应用

2.8 案例分析与实现