线性表

1. 基本概念

线性表是具有像线一样的性质的表，它是零个或多个数据元素的有限序列。

在物理结构中的线性结构又称线性表，线性表中的数据元素可以是各种各样的，但是同一线性表中的元素必定具有相同的特性，即属于同一个数据对象，相邻的数据元素之间存在着序偶关系。若将线性表记为(a1,a2,..an)，则有以下的特性:

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。数组就是一个典型的顺序存储结构。

下面是线性表的顺序存储结构代码。

#define SIZE 8

typedef struct
{
    int a[SIZE];
    int length;
}sqlint;

在地址连续的空间存储数据：

0x1000	0x1004	0x1008	0x100C	0x1010	0x1014	0x1018	0x101C
a[0]	a[1]	a[2]	a[3]	a[4]	a[5]	a[6]	a[7]

描述顺序存储结构的需要三个属性：

注意：数组的长度是存放线性表的存储空间的长度，存储分配后这个量是不变的，线性表的长度是线性表中数据元素的个数，随着线性表的增删步骤，这个量是变化的。

在任意时刻，线性表的长度应该小于或等于数组的长度。

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。

数据元素在链式结构中，除了要存数据元素信息外，还要存储它后继元素的存储地址。

头指针：
- 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。
- 头指针具有标识作用，常用头指针作为链表的名字。
- 无论链表是否为空，头指针均不为空，头指针是链表的必要元素。

整个链表的存取必须是从头指针开始进行，之后的每一个结点，其实就是上一个结点的后继指针指向的位置。

最后一个结点它的指针指向的是“ 空 ”（通常用 NULL 或 **“ ^ ”**表示）。

头结点：
- 头结点是为了更方便对链表进行操作而设立的，放在第一元素的结点之前，其数据域一般无意义（也可以存放链表的长度）。
- 有了头结点，对在第一要素结点前插入结点和删除第一结点与其他结点的操作就统一了。
- 头结点不一定是链表的必须要素。