数据结构:二、线性结构

    线性结构的知识点占了数据结构内容的一大半差不多，足以看出线性结构地位的重要性。

    线性结构包括线性表、栈和队列、字符串、数组、广义表。其中线性表是典型的、最基本、也是最常用的一种线性结构。

一、线性表：由n（n>=0）个数据特性相同的元素构成的有限序列。其中n定义为线性表的长度，n=0时称为空表。

    1、非空的线性表或者线性结构特点：

（1）、存在唯一的一个被称为“第一个”的数据元素；

（2）、存在唯一的一个被称为“最后一个”的数据元素；

（3）、除了第一个之外，结构中的每一个数据元素均只有一个前驱；

（4）、除了最后一个之外，结构中的每一个数据元素均只有一个后继；

    2、线性表的存储结构分为两种——顺序存储以及链式存储

    （1）、顺序表示的线性表也称顺序表，指的是用一组地址连续的存储单元依次存储线性表的数据元素；其特点：逻辑上相邻的数据元素，其物理次序也是相邻的。

    （2）、链式表示的线性表也称链表，指用一组任意的存储单元存储线性表的数据元素；其特点：这组存储单元可连续可不连续，但每个结点除了存储对应的数据元素之外，还需存储一个直接后继的存储位置（最后一个结点也需指空即NULL）。其中存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域。

    单链表是一般的普通链表，还有根据自身的特点，又分出几种特殊的链表，如循环链表、双向链表等。

    循环链表中，最后一个结点的指针域并不指空，而是指向头结点，使整个链表形成一个环。

    双向链表中，每个结点都有两个指针域，一个指向直接后继，一个指向直接前驱，克服了单链表单向性的缺点。

注：类似单链的循环表，双向链表也可以有循环表，称为双向循环链表，即将双向链表的最后结点的后继指针指向头结点的前继指针域，头结点的前继指针指向最后结点的数据域。

二、栈和队列：两种特殊的线性表

    栈：限定仅在表尾进行插入或删除操作的线性表。表头端称为栈底（base），表尾端称为栈顶（top）。是一种后进先出的线性表。

栈

    队列：只允许在表的一端进行插入，在另一端删除元素；允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）（简直就像在饭堂排队打饭似的）。是一种先进先出的线性表。

    三、线性表的扩展：串和数组

    串：逻辑结构和线性表极为相似，区别在于串的数据对象约束为字符集。

    基本操作：与线性表的基本操作（以“单个元素”作为操作对象）不同，串通常以“串的整体”作为操作对象，例如：在串中查找某个子串、求取一个子串、在某个位置上插入一个子串以及删除一个子串等。

    串也有两种基本存储结构——顺序存储和链式存储，但一般多采用顺序存储结构（考虑到存储效率和算法的方便性）。

    数组：由类型相同的数据元素构成的有序集合，其中每个元素称为数组元素。

    数组的特点就是数组元素本身可以是具有某种结构的数据，但每个数据元素都要属于同一数据类型。eg：二维数组（数组元素是一维数组的一维数组）

    一旦建立了数组，结构中的数据元素个数和元素之间的关系就不再发生变动，故数组通常都采用顺序存储结构表示。