学习数据结构第一弹 线性表（5）

循环链表与双向链表

循环链表：

循环链表也是一种线性表的链式存储结构，其实他和单链表很像，其特点是它是一个环，也就是指单链表的最后一个结点的指针域不为空，而是指向头结点或是第一个结点，这样整个链表就形成了一个环。循环链表一般可以分为单循环链表和多循环链表，多循环链表也就是将表中的结点链在多个环上。

这种方式在单向和双向链表中皆可实现，其转换方法是，选择从任一结点开始沿着列表的任一方向直到返回开始的结点。

除此之外，还有一种模拟的循环链表，就是在访问最后一结点之后的时候，手工跳转到第一个结点，访问第一个结点之前的结点也一样。通过这样的方式也可以实现循环链表的功能，在直接运用循环链表比较麻烦或者可能会出现问题的时候可以用。

循环链表的操作：

下面主要讲单循环链表，单循环链表的操作和单链表的操作没什么区别，只是循环结束的条件判断不再是判断指针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;
}