数据结构-线性表(5)

静态链表

可以用数组代替指针，来描述单链表。

数组的元素都由两个数据域组成，data和cur组成，data是数据域，cur是指针域。

这种用数组描述的链表叫静态链表。还被叫做游标实现法。

1. 为了方便插入数据，数组会建立得大一些；
2. 数组的第一个和最后一个元素作为特殊元素处理，不存数据；
3. 未被使用的数组元素被称为备用链表。

静态链表的插入操作

将所有未使用过以及被删除的分量游标链成一个备用链表，每当进行插入时，

便可以从备用链表上取得第一个结点作为待插入的新结点。

静态链表的删除操作

把第一个元素cur值赋给要删除的分量cur

把要删除的分量下标赋值给第一个元素的cur

静态链表的优缺点

优点

在插入和删除操作时，只需修改游标，不需要移动元素，从而改进了在顺序存储结构中插入和删除操作

需要移动大量元素的缺点

缺点

没有解决连续存储分配带来的表长难以确定的问题

失去了顺序存储结构随机存取的特性

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，是整个单链表形成了一个环，这种头尾相接的单链表称为单循环链表，简称循环链表(circular linkedlist)。

单链表是通过p->next是否为空判断循环结束。

循环链表则是通过p->next是否等于头结点，来判断循环结束。

可以用尾指针rear表示终端结点，则查找终端结点是O(1),而开始结点，其实就是rear->next->next，

时间复杂度是O(1)。

双向链表

双向链表(doube linked list)是在单链表的每个节点中，再设置一个指向其前驱结点的指针域。

双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

prior 直接前驱指针 next直接后继指针。

插入操作 （实现将结点s插入到结点p 和 p->next之间）

//将p赋值给s的前驱
s->prior = p;
//将p->next赋值给s的后继
s->next = p->next;
//将s赋值给p->next的前缀
p->next-> prior=s;
//将s赋值给p 的后继
p->next = s;