静态链表
用数组描述的链表叫做静态链表；
数组的元素由两部分组成， data和cur， data存储数据；cur存储该元素的后继在数组中的下标（类似单链表中的next指针）；
数据元素类似下面结构体
typedef struct{
ElemType data;
int cur;
} Componet,StaticLinkList[MAXSIZE];
备用链表
- 数组中未使用的数组元素；
- 数组的第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点下标，而数组的最后一个元素的cur 则存放第一个有数值的元素的下标，相当于单链表中的头结点的作用，当链表为空时，为0；
静态链表的插入操作
如下图所示；
初始链表
插入操作
将丙插入乙和丁之间；
- 将元素丙添加到备用链表；
- 将乙的cur 改为 丙的游标；
- 将丙的cur 改为 丁的游标；
静态链表的优缺点；
1、优点
- 在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点；
2、缺点
- 没有解决连续存储分配带来的表长难以确定的问题；
- 失去了顺序存储结构随机存取的特性；
循环链表
将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表；简称循环链表；
- 尾指针： rear；
- 开始结点： rear->next->next;
双向链表
在单向链表的每个链表结点中
每一个链表元素结构类似下面
typedef struct{
ElemType data;
struct DuLNode *prior /* 直接前驱指针*/;
struct DuLNode *next; /*直接后驱指针 */
}DuLNode, *DuLinkList
非空的循环带头结点的双向链表
双向链表的插入操作
假设存储元素e的结点为s，要实现将结点s插入到结点p与p->next之间；
算法思路：
s->prior = p; /*把p赋值给s的前驱*/
s->next = p->next; /*把p->next赋值给s->next*/
p->next->prior = s; /*将s赋值给p->next的前驱*/
p->next = s; /*将s赋值给p->next*/
双向链表的删除操作
p->prior->next = p->next; /*把p->next 赋值给p->prior的后继*/
p->next->prior = p->prior; /*把p->prior赋值给p->next 的前驱*/
free(p);
网友评论