数据结构C（4）——循环链表、双向链表、双向链表的插入、删除

一、循环链表

• 循环链表是一种头尾相接的链表（即：表中最后一个结点的指针域指向头结点，整个链表形成一个环）

• 优点：从表中任一结点出发均可找到表中其他结点

• 注意：由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p->next是否为空，而是判断他们是否等于头指针

• 循环条件

  p!=NULL → p!=L

  p->next!=NULL → p->next!=L

  ​ 单链表 单循环链表

• 带尾指针循环链表的合并

LinkList Connect(LinkList Ta,LinkList Tb)
{
    p=Ta->next;
    Ta->next=Tb->next->next;
    delete Tb->next;
    Tb->next=p;
    return Tb;
}

二、双向链表

• 双向链表：在单链表的每个结点里再增加一个指向其前驱的指针域prior，这样链表中就形成了有两个方向不同的链，故称为双向链表

• 双向循环链表：和单链的循环表类似，双向链表也可以有循环表

  • 让头结点的前驱指针指向链表的最后一个结点
  • 让最后一个结点的后继指针指向头结点

• 双向链表结构的对称性：

  p->prior->next = p = p->next->prior

三、双向链表的插入

void ListInsert_DuL(DuLinkList &L,int i,ElemTyoe e)
{
    if(!(p=GetElemP_DuL(L,i)))
        return ERROR;
    s=new DuLNode;
    s->date=e;
    s->prior=p->prior;
    p->prior->next=s;
    s->next=p;
    p->prior=s;
    return OK;
}

四、双向链表的删除

void ListDelete_DuL(DuLink &L,int i,ElemType &e)
{
    if(!(p=GetElemP_DuL(L,i)))
        return ERROR;
    e=p->data;
    p->prior->next=p->next;
    p->next->prior=p->prior;
    free(p);
    return OK;
}