循环链表的实现

在单链表中，从一已知结点出发，只能访问到该结点及其后继结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上更易于实现。

循环链表在实现上大多操作都与单链表相同，如创建、查找等，这些部分在单链表与双向链表中都有详细的讲解及代码实现，此处就不再重复，接下来主要讲解其插入与删除元素时与单链表的异同。

1、插入元素

在循环链表中插入元素，如果是插入到第一个位置，即头结点之后的位置，则稍稍有一些麻烦，需要处理三个指针，头结点中的指针、尾结点中的指针和插入元素的结点指针。其过程如图17所示。

图1 在循环链表的头结点插入元素

在头结点之后插入元素时，要将新结点中的指针指向此位置上原来的结点，头结点中的指针指向新结点，尾结点指针指向新结点。比单链表多处理了一个尾结点指针。

在尾部插入元素时也有所不同，p->next不再指向NULL，而是指向head->next。

除此两处以外，在其他位置插入元素，则与单链表处理相同。其代码实现如下：

int ClistInsert(pHead ph, int pos, int val) //在链表的pos位置插入元素val
{

    if (ph == NULL || pos < 0 || pos > ph->length)
    {
        printf("插入元素时，参数传入有误！\n");
    }

    pNode pval = NULL;
    //参数传入无误，则为新元素val分配结点
    pval = (pNode)malloc(sizeof(struct Node));
    pval->data = val;                     //将值val保存到此结点中

     //接下来要判断在哪个位置插入元素，先判断链表是否为空
     if (IsEmpty(ph)) //如果链表为空
     {
         ph->next = pval;                  //直接将结点插入到头结点后
         pval->next =pval;                 //将第一个结点指向它自己
     }
    else //循环链表不为空，则分为在头部插入（即头结点后）和普通位置插入
    {
        pNode pRear = ph->next; 
         if (pos == 0) //在第一个位置（头结点后）插入
         {
             //在0号位置插入，需要先找到尾结点
            while (pRear->next != ph->next) //循环结束的条件
            {
                pRear = pRear->next;         //pCur指针向后移动
            }
            //while循环结束后，pRear指向尾结点
            //然后插入元素
            pval->next = ph->next;
            ph->next = pval;
            pRear->next = pval;             //这三个步骤顺序不能更改
         }
        else //如果不是0号位置插入，则和单链表无区别
        {
            pNode pCur = ph->next;
            for (int i = 1; i < pos; i++) //就要遍历链表找到要插入的位置
             {
                 pCur = pCur->next;             //pCur指针向后移
             }
             //循环结束后，此时pCur指向的是要插入的位置
             pval->next = pCur->next;         //指针断开再连接的过程
            pCur->next = pval;
        }
    }
    ph->length++;
    return 1;
}

在插入新元素时，先判断链表是否为空，如果为空，则将元素插入到头结点后，然后将其指针指向自身；如果不为空，根据插入的位置作出相应操作。

2、删除元素

在删除元素时，也要考虑删除的是否为头结点后的第一个元素，如果是，则需要将头结点与尾结点的指针指向待删除结点的后继结点，如图2所示。

图2 删除头结点后的第一个元素

如果是删除其他位置的元素，则和单链表处理方式相同。其代码实现如下：

pNode ClistDelete(pHead ph, int val) //删除循环链表ph中的元素val
{
    if (ph == NULL || ph->length == 0)
     {
         printf("参数传入有误！");
     }
    //先找到链表的尾结点
    pNode pRear = ph->next;
    while (pRear->next != ph->next)
    {
        pRear = pRear->next;
    }

    //查找此元素
    pNode pval = ClistFind(ph, val);     //关于ClistFind()函数，与单链表相同
    if (pval == NULL)
        return NULL;

    if (pval == ph->next)                 //如果是第0号位置上的结点
    {
        ph->next = pval->next;
        pRear->next = pval->next;
    }
    else                                  //如果是其他位置的结点
    {
        //就要找到pval的前驱结点
        pNode pRe = ph->next;
        for (int i = 0; i < ph->length; i++)
        {
            if (pRe->next == pval)
            {
                pRe->next = pval->next;
                return pval;
            }
            pRe = pRe->next;
        }
    }
    return NULL;
}

在循环链表中，除了插入和删除操作与单链表稍有不同之外，其他操作与单链表都是一样的，读者可以参照单链表的操作自己动手实现循环链表，并完成测试。