[数据结构] 线性表

1. 线性表的逻辑结构

线性表是具有相同数据类型的n （n>= 0）个数据元素的有限序列。

线性表中第一个元素称为表头元素；最后一个元素称为表尾元素。
除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且只有一个直接后继。

2. 线性表的顺序存储结构

（1）
线性表的顺序存储是用一组地址连续的存储单元（比如c语言里面的数组），依次存储线性表中的数据元素。

• 静态建表
  顺序表需要的三个部分：存储空间的起始位置、顺序表最大存储容量和顺序表当前长度。

• 动态建表
  存储数组的空间是在程序执行过程中通过动态分配语句来分配。

动态分配并不是链式存储，同样还是属于顺序存储结构，只是分配的空间大小可以在运行时决定。

（2）双链表
单链表：单个指针，单向火车
双链表：双指针，像我们上火中的电梯

双链表的操作：插入、删除

（3）线性表的链式表示
a. 循环链表
循环单链表：循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环。

• 判断条件不是头结点的后继指针是否为空，而是它是否等于头指针。
• 有时对单链表常做的操作是在表头和表尾进行的，此时可对循环单链表不设头指针而是尾指针，从而使得操作效率更高。

循环双链表类比循环单链表，循环双链表链表区别于双链表就是首尾结点构成的环。

• 尾结点的后继指针指向表头结点，头结点的前驱指针指向表尾结点。
• 当循环双链表为空表时，其头结点的prior域和next域都等于L。

b. 静态链表
借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next。与前面所讲的链表中的指针不同的是，这里的指针是结点的相对位置（数组下标）。

c. 优缺点
优点：存储密度大：不需要为表中元素之间的逻辑关系增加额外存储空间；随机存储：可以快速存取表中任一位置的元素。
缺点：插入和删除操作需要移动大量元素；对存储空间要求高，会产生存储空间的“碎片”。

3. 线性表的链式存储结构

头结点和头指针的区别？
不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息，它是为了方便做的一种处理。

为什么要设置头结点？

• 处理操作起来方便
• 无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就统一了。