数据结构-线性表(3)

线性表的链式存储结构

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。

意味着数据元素可以存在内存未被占用的任意位置。

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

为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置）。

我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。

指针域中存储的信息称做指针或链。

这两部分信息组成数据元素ai的存储映像，称为结点 Node。

n个节点(ai的存储映像)链结成一个链表，即为线性表（a1,a2,…,an）的链式存储结构。

此链表的每个结点中只包含一个指针域，所以叫做单链表。

单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。

我们把链表中的第一个结点的存储位置叫做头指针，整个链表的存取必须是从头指针开始进行，之后的每一个结点，就是上一个的后继指针指向的位置。

最后一个节点的指针没有直接后继，因此指针是 空 （NULL 或者 ^ 表示）

一般会在单链表的第一个结点前附设一个节点，称为头结点。可以不存储任何信息，也可以存储链表长度等附加信息。

头结点的指针域存储指向第一个结点的指针。

头指针与头结点的异同

头指针:

头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针

头指针具有标识作用，所有常用头指针冠以链表的名字

无论链表是否为空，头指针均不为空。头指针是链表的必要元素

头结点:

头结点是为了操作的统一和方便而设立的，放在第一元素的节点之前，其数据域一般无意义（可以存放链表的长度）

有了头结点，对在第一元素节点前插入节点和删除第一节点，其操作与其它节点的操作就统一了

头结点不一定是链表必须要素

线性表链式存储结构代码描述

若线性表是空表，头结点的指针域为空。

结点由存放数据元素的数据域，存放后继结点地址的指针域组成。

假设p是指向线性表第i个元素的指针，

节点ai的数据域，可以用p->data表示，p->data的值是一个数据元素，

节点ai的指针域，可以用p->next表示，p->next的值是一个指针。

p->next指向第i+1个元素，即指向ai+1的指针。

如果p->data = ai 那么 p->next->data = ai+1