数据结构——第二章 线性表（8）——线性表总结

线性表总结

线性表是线性结构的基本形式，用于描述一组同类型而具有1:1线性关系的数据对象。将此类数据对象存放在计算机的内存中时，必须考虑数据元素的存放和数据元素之间关系的存放。常用的存储结构有顺序存结构和链式结构。

顺序表存储特点是用一维数组存放线性表中的数据元素，用下标的相邻关系表示数据元素的直接前驱和直接后继关系。为了方便使用，经常需要用到表中数据元素的个数以及是否存在剩余空间，能够满足上述要求的变量类型是结构体类型。由于C语言没有给出此种结构体类型的定义，因此必须自定义该类型，即顺序表类型。本书给出了两种顺序表类型的定义，并进行了对比分析。第一种容易掌握，但是由于在类型中直接给出了数组的大小，因此通用性和灵活性较差。第二种在类型中给出的是存放一维数组首地址的指针成员，数组的大小由初始化操作完成，大大提高了该类型的实用性。

如果数据元素的类型是简单类型，则顺序表类型的自定义只需一步，直接定义顺序表结构体类型即可。如果数据元素的类型是结构体类型是结构体类型，则顺序表类型的自定可分两步完成。
（1）先定义数据元素对应的结构体类型。
（2）再定义顺序表结构体类型。

链式存储结构的特点是用一个带头结点的单向链表存放线性表的数据元素。其存储空间遵循“按需分配”，根据需要动态申请结点空间，不需要是可释放结点的存储空间。线性表中数据元素的关系用结点中存放后继结点地址的指针变量表示。链表对内存空间的连续性要求较低，每个数据元素占用的存储空间比顺序表中占用的空间要大。

如果数据元素的类型是简单类型，链表类型的自定义只需一步，直接定义结点类型和指向结点的指针类型即可。如果数据元素的类型是结构体类型，链表类型的自定义可分两步完成。
（1）先定义数据元素对应的结构体类型。
（2）再定义链表的结点类型和指向结点的指针类型。

链表有多种形式，除了单向链表外，还有单向循环链表和双向循环链表。
基于这两种存储结构的基本操作实现，需根据每个基本操作是否改变了存储结构中的成员值以及需要的其他条件，正确定义函数的形参。熟练掌握基本操作之后，对于其他复杂的操作，只需对基本操作进行组合或修改某些基本操作即可。