【C 数据结构】线性表

【 1. 线性表 】

• 线性表，全名为线性存储结构，线性表结构存储的数据往往是可以依次排列的（不考虑数值大小顺序）。
  例如，存储类似 {1,3,5,7,9} 这样的数据时，各元素依次排列，每个元素的前面和后边有且仅有一个元素与之相邻（除首元素和尾元素），因此可以使用线性表存储。
• 使用线性表存储的数据，要求数据类型必须一致（如同向数组中存储数据那样，）。也就是说，线性表存储的数据，要么全部都是整形，要么全部都是字符串。一半是整形，另一半是字符串的一组数据无法使用线性表存储。
• 使用线性表存储数据的方式可以理解为 “把所有数据用一根线儿串起来，再存储到物理空间中”。

• 例如，数据为 1,2,3,4,5
  
• 用 “一根线儿” 把它们按照顺序“串”起来，左侧是“串”起来的数据，右侧是空闲的物理空间。
  
• 把这 “一串儿” 数据放置到物理空间，可以选择以下两种方式：左侧是顺序存储结构，右侧是链式存储结构。
  

【 2. 顺序存储结构、链式存储结构 】

• 上图中我们可以看出，线性表按存储结构可细分为顺序存储结构和链式存储结构。：
  • 将数据依次存储在连续的整块物理空间中，这种存储结构称为顺序存储结构，简称 顺序表；
  • 将数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系，这种存储结构称为链式存储结构，简称 链表；

【 3. 前驱、后继 】

• 数据结构中，一组数据中的每个个体被称为“数据元素”（简称 元素 ）。
• 某一元素的左侧相邻元素称为 直接前驱 ，位于此元素左侧的所有元素都统称为“前驱元素”；
• 某一元素的右侧相邻元素称为 直接后继，位于此元素右侧的所有元素都统称为“后继元素”；

• 以数据 1,2,3,4,5 中的元素 3 来说，它的直接前驱是 2 ，此元素的前驱元素有 2 个，分别是 1 和 2；同理，此元素的直接后继是 4 ，后继元素也有 2 个，分别是 4 和 5。如图 4 所示：