论坛 › C\C++交流 › 循环链表

Julia999 发表于 2019-7-29 14:57:46

循环链表

引言：对于单链表，由于每个结点只存储了向后的指针，到了尾部标识就停止了向后链的操作。也就是说，按照这样的方式，只能索引后继结点不能索引前驱节点所以，不从头结点出发，就无法访问全部结点
解决方法：只需要将单链表中的终端结点的指针端由空指针改为指向头结点，使形成一个环
注意：这里并不是说循环链表就一定要有一个头结点
其实循环链表和单链表的主要差异就是循环判断的空链表的条件上，原来判断head->next是否为null，现在是head->next是否等于head
初始化循环链表：/*初始化循环链表*/
void ds_init(node **pNode)
{
    int item;
    node *temp;
    node *target;

    printf("输入结点的值，输入0完成初始化\n");

        while(1)
        {
      scanf("%d", &item);
      fflush(stdin);

                if(item == 0)
            return;

      if((*pNode) == NULL)
                { /*循环链表中只有一个结点*/
                        *pNode = (node*)malloc(sizeof(struct CLinkList));
                       
                        if(!(*pNode))
                                exit(0);
                       
                        (*pNode)->data = item;
                        (*pNode)->next = *pNode;
                }
      else
                {
            /*找到next指向第一个结点的结点*/
            for(target = (*pNode); target->next != (*pNode); target = target->next)
                                ;

            /*生成一个新的结点*/
            temp = (node *)malloc(sizeof(struct CLinkList));

                        if(!temp)
                                exit(0);

                        temp->data = item;
            temp->next = *pNode;
            target->next = temp;
      }
    }
}
链表存储结构的定义
/*链表存储结构的定义*/
typedef struct CLinkList
{
    int data;
    struct CLinkList *next;
}node;

/*插入结点*/
/*参数：链表的第一个结点，插入的位置*/
void ds_insert(node **pNode , int i)
{
    node *temp;
    node *target;
    node *p;
    int item;
    int j = 1;

    printf("输入要插入结点的值:");
    scanf("%d", &item);

    if(i == 1)
        { //新插入的结点作为第一个结点
      temp = (node *)malloc(sizeof(struct CLinkList));

                if(!temp)
            exit(0);

                temp->data = item;

      /*寻找到最后一个结点*/
      for(target = (*pNode); target->next != (*pNode); target = target->next)
                        ;

                temp->next = (*pNode);
      target->next = temp;
      *pNode = temp;
    }
    else
        {
      target = *pNode;

                for( ; j < (i-1); ++j )
                {
                        target = target->next;
                }
               
                // target指向第三个元素的
               
                temp = (node *)malloc(sizeof(struct CLinkList));

                if(!temp)
            exit(0);

                temp->data = item;
               
      p = target->next;
      target->next = temp;
      temp->next = p;
    }
}
返回链表所在的位置：
/*返回结点所在位置*/
int ds_search(node *pNode, int elem)
{
    node *target;
    int i = 1;

    for(target = pNode; target->data != elem && target->next != pNode; ++i)
        {
                target = target->next;
        }
       
        if(target->next == pNode) /*表中不存在该元素*/
      return 0;
    else
      return i;
}
删除结点：
/*删除结点*/
void ds_delete(node **pNode, int i)
{
    node *target;
    node *temp;
    int j = 1;

    if(i == 1)
        { //删除的是第一个结点
      /*找到最后一个结点*/
      for(target = *pNode; target->next != *pNode;target = target->next)
                        ;

                temp = *pNode;
      *pNode = (*pNode)->next;
      target->next = *pNode;
      free(temp);
    }
    else
        {
      target = *pNode;

                for( ; j < i-1; ++j)
                {
                        target = target->next;
                }
               
                temp = target->next;
      target->next = temp->next;
      free(temp);
    }
}

查看完整版本: 循环链表