线性表

定义：线性表表示零个或多个数据元素的有限序列。

线性表的特点：

存在唯⼀的一个被称作”第一个”的数据元素；

存在唯⼀的一个被称作”最后一个"的数据元素；

除了第一个数据元素之外，结构中的每个数据元素均有⼀个前驱；

除了最后一个数据元素之外，结构中的每个数据元素都有⼀个后继；

线性表有两种物理结构：

顺序存储结构：指用一段连续的存储单元依次存储线性表的数据元素。

链式存储结构：用一组任一存储单元存储数据元素，这个存储单元可以是连续的，可以是不连续的。

顺序存储结构

顺序存储结构的代码

*data：存储空间的起始位置；

length:当前线性表中数据元素的个数；

顺序存储结构的初始化

1、为顺序表分配指定大小的空间；

2、将顺序表的长度置为0；

注意：MAXSIZE是数组的长度，即：分配这个长度的空间，此空间分配好之后将不会变化。length为顺序表的长度，即：线性表中数据元素的个数，在顺序表的使用过程，可随着增加数据元素而增加，删除数据元素而减少。

顺序存储结构的插入

步骤：

1、先对i位置进行合法性判断，不能超过顺序表的存储空间；

2、将顺序表中i位置之后的数据元素往后移动一个位置；

3、将新增的数据元素放入原顺序表的i位置；

4、由于是新增数据元素，故顺序表的长度需要+1；

顺序存储结构的删除

步骤：

1、先对i位置进行合法性判断，判断删除的位置是否合法；

2、将位置i后面的元素统一往前移一个位置；

3、由于删除操作，则需要将顺序表的长度-1；

顺序存储结构的优缺点

优点：

无需为表中数据元素的逻辑关系而增加额外的存储空间；

可以快速的存取表中任一位置的数据元素；

缺点：

插入和删除操作需要移动大量的数据元素；

当线性表长度变化较大时，难以确定存储空间的容量；

造成存储空间的碎片；

链式存储结构

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

存储数据元素本身信息的域称为信息域

存储其直接后续数据元素信息域称为指针域

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

单链表

定义：N个结点链结成一个链表，称为线性表的链式存储结构，如果每个结点只包含一个指针域，则此链表称为单链表。

链表的第一个结点存储位置称为头指针，链表的存取必须从头指针开始。链表的最后一个结点的指针域为空，因为最后一个结点没有后继的数据元素了。

为了方便对链表操作，我们会在第一个结点前附设一个头结点，头结点的数据域可以空，或者其它信息（如链表的数据元素个数等），头结点的指针域指向了第一个结点。

头结点和头指针的区别

单链表结点的代码

单链表的初始化

单链表的读取

获取链表第i个数据元素的算法思路：

1、声明一个结点p指向链表的第一个结点，初始化j从1开始；

2、当j<i时就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；

3、若到链表末尾p为空，则说明第i个元素不存在；

4、否则查找成功，返回结点p的数据；

单链表的插入

算法思路：

1、声明一个结点p指向链表的第一个结点，初始化j从1开始；

2、当j<i时，遍历链表，让p指针向后移动，不断指向下一个结点，j累加1；

3、若到链表末尾p为空，则说明第i个元素不存在；

4、否则查找成功，在系统中生成一个空结点s；

5、将数据元素e赋值给s的数据域；

6、单链表插入标准语句s->next=p->next; p->next=s；

7、返回成功；

单链表的删除

算法思路：

1、声明一个结点p指向链表的第一个结点，j初始化从1开始；

2、当j<i时就遍历链表，让p指针向后移动，不断指向下一个结点，j累加1；

3、若到链表末尾p为空，则说明第i个元素不存在；

4、否则查找成功，将欲删除的结点p->next赋值给q；

5、单链表的删除标准语句p->next=q->next；

6、将q结点的数据赋值给e，作为返回；

7、释放q结点；

总结：顺序结构和链式结构

顺序结构采用一段连续的存储单元依次存储线性表的数据元素；链式结构采用链式结构，用一组任意的存储单元存放线性表的数据元素；

时间性能方面：

查找线性表：顺序结构的算法复杂度为O(1)；单链表的算法复杂度为O(n)；

插入和删除：顺序结构的算法复杂度为O(n)；单链表的算法复杂度为O(1)；

空间性能方面：

顺序结构需要预分配存储空间，分大了浪费，分小了容易溢出；

单链表不需要用的时候不需要分配存储空间，只要有就可以分配，数据元素个数也不受限制。