线性表的链式存储结构总结

顺序结构需要一片连续的存储空间，如果我们只有零散的空间，那怎样存储呢？

线性表特点

线性表的链式存储是指通过一组任意的存储单元来存储线性表中的数据元素。

为了建立起数据元素之间的线性关系，对每个链表结点，除了存放元素自身的信息之外，还需要存放一个指向其后继的指针。

线性表表示

typedef struct LNode{ //定义单链表结点类型

ElemType data; //数据域

struct LNode *next; //指针域

}LNode, *LinkList;

因为每个结点只有一个指针指向下一个结点，故又称单链表。

通常用“头指针”来标识一个单链表， 例如Linklist L那么头指针L就代指一个单链表，头指针为“NULL”时则表示一个空表。

单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等相关信息。头结点的指针域指向线性表的第一个元素结点。

头结点和头指针的区别？

不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息。

为什么要设置头结点？

1. 处理操作起来方便，例如：对在第一元素结点前插入结点和删除第一结点起操作与其它结点的操作就统一了。
2. 无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就统一了。