循环链表与双向链表
循环链表：
循环链表也是一种线性表的链式存储结构，其实他和单链表很像，其特点是它是一个环，也就是指单链表的最后一个结点的指针域不为空，而是指向头结点或是第一个结点，这样整个链表就形成了一个环。循环链表一般可以分为单循环链表和多循环链表，多循环链表也就是将表中的结点链在多个环上。
这种方式在单向和双向链表中皆可实现，其转换方法是，选择从任一结点开始沿着列表的任一方向直到返回开始的结点。
除此之外，还有一种模拟的循环链表，就是在访问最后一结点之后的时候，手工跳转到第一个结点，访问第一个结点之前的结点也一样。通过这样的方式也可以实现循环链表的功能，在直接运用循环链表比较麻烦或者可能会出现问题的时候可以用。
循环链表的操作：
下面主要讲单循环链表，单循环链表的操作和单链表的操作没什么区别，只是循环结束的条件判断不再是判断指针p或p->next是否为空，而是判断他们是否等于头结点。
有时候，循环链表中会设置一个指向表尾的尾指针，这样对某些操作会很方便
代码实现
其实绝大部分操作和单链表都很相像，这里就不在描述，下面可以讲讲
两个单循环链表的合并操作
/*
假设现在有两个单循环链表AB，将其合并的思路如下
A B分别为单循环链表的尾指针
q = B->next; //q指向B的头结点
B->next = A->next; //B的指针指向A的头结点
A->next = q->next; //A的尾指针指向B的第一个结点，即B链接到A上
A = B; //A指向B，作为合并后链表的尾指针
free(q); //释放B的头结点
*/
LinkList ConnectList(LinkList headA,LinkList headB)
{
Node *p;
Node *tailA,*tailB;
tailA = headA->next;
tailB = headB->next;
//分别找到两个链表的尾结点
while(tailA->next != headA)
tailA = tailA->next;
while(tailB->next != headB)
tailB = tailB->next;
p = tailB->next;
tailB->next = tailA->next;
tailA->next = p->next;
tailA = tailB;
free(p);
return headA;
}
双向链表：
在单链表中，访问任一结点，如果访问的是后继结点，直接通过后继指针就可以轻松完成此操作（O（1）），如果是访问其前驱结点，就必须从表头结点顺链查找，其实时间复杂度为O（n），显然这样十分不方便，但如果加多一个指针域呢，这样无论是前驱结点还是后继结点访问起来就比较容易了，这种链表就是双向链表。
双向联表的描述：
typedef struct dualnode
{
ElemType data;
struct dualnode *prior; //指向前驱结点的指针域
struct dualnode *next; //指向后继结点的指针域
}DNode;
typedef DNode* DLinkList;
对于带有头结点的双向链表来说，其头结点的prior域为NULL，尾结点的next域为NULL，所以如果是一个空的双向链表的话，两个指针域都为空。
双向链表转化为循环链表时，双向循环链表的头结点的前驱指针prior指向表尾结点，尾结点的后继指针指向头结点，所以对于一个空的双向循环链表，头结点的两个指针均指向自身。
双向链表的基本操作：
对于一些向计算表长，获取元素位置和获取元素等只涉及一个方向的指针的操作，与单链表的操作相同。但是对于插入删除操作来说比起单链表就有较大的差异。
//插入操作
Status ListInsert(DLinkList l,int i,ElemType e)
{
int k = 1;
DNode *p,*s;
p = l->next;
while(p->next && k<i)
{
k++;
p = p->next;
}
if(k>i || !p) //插入位置无效
return ERROR;
s = (DNode*)malloc(sizeof(DNode));//为新结点开辟空间
s->data = e;
s->prior = p->prior; //新结点的前驱指针指向p的前驱结点
p->prior->next = s; //p的前驱结点的后继指针指向新结点
s->next = p; //新结点的后继指针指向p
p->prior = s; //p的前驱指针指向s
return OK;
}
//删除操作
Status DeleteList(DLinkList l,int i,ElemType *e)
{
int k = 1;
DNode *p;
p = l->next;
while(p->next && k<i)
{
p = p->next;
k++;
}
if(!p || k>i) //删除位置无效
return ERROR;
*e = p->data;
p->prior->next = p->next; //将P的前驱结点的后继指针指向p的后继结点
p->next->prior = p->prior; //将p的后继结点的前驱指针指向p的前驱结点
free(p); //释放结点p
return OK;
}
网友评论