循环链表-空表

image

在空表中，只有头结点，故头结点的指针域指向本身。

*L = (*LinkList)malloc(sizeof(Note));
(*L)->data = item;
(*L)->next = *L;

循环链表-非空表

image

在非空表中，尾结点的指针域指向首元结点。

temp = (*LinkList)malloc(sizeof(Node));
(*temp)->data = item;
(*temp)->next = *L;//尾结点的指针指向首元结点
prev->next = temp;//前一个结点的指针指向新结点

循环链表创建

循环链表创建分为两种情况：

第一次开始创建
已经创建了链表，往里面新增数据元素
算法思路：
判断当前是否是第一次开始创建，如果是则新建结点，并将结点的指针域指向本身。
如果不是第一次开始创建，则新增结点将前面结点的指针域指向新结点，将新结点的指针域指向首元结点。

Status CreateList(LinkList *L){
    int num;
    LinkList temp = NULL;
    LinkList target = NULL;
    printf("输入节点的值，输入0结束\n");
    while(1){
        scanf("%d", num);
        if(num == 0) break;
        if(*L == NULL){
            *L = (LinkList*)malloc(sizeof(Node));
            if(!L) return ERROR;
            (*L)->data = num;
            (*L)->next = *L;
        }
        else{
            temp = (LinkList*)malloc(sizeof(Node));
            if(!temp) return ERROR;
            temp->data = num;
            //找到最后一个结点
            for(target = *L; target->next != *L; target = target->next);
            temp->next = *L;
            target->next = temp;
        }
    }
    return OK;
}

循环链表插入数据

插入位置是否是首元结点
插入位置为其它
算法思路：
1.1 插入位置是首元结点
创建新结点，并判断新结点是否malloc成功，如果创建失败退出；
找到链表的尾结点，将链表的尾结点指针域指向新结点；
将新结点的指针域指向首元结点；
将头结点指针指向新结点；
2.1 插入其它位置（思路与单链表插入相同）；
创建新结点，并判断新结点是否malloc成功，如果创建失败退出；
找到插入位置的前一个结点，将前一个结点的指针域指向新结点；
将新结点的指针域指向前一个结点的next；

Status ListInsert(LinkList *L, int place, int num){
    LinkList temp ,target;
    int i;
    if (place == 1) {
        temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) {
            return ERROR;
        }
        temp->data = num;
        for (target = *L; target->next != *L; target = target->next);
        temp->next = *L;
        target->next = temp;
        *L = temp;
    }else
    {
        temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) {
            return ERROR;
        }
        temp->data = num;
        for ( i = 1,target = *L; target->next != *L && i != place - 1; target = target->next,i++) ;
        temp->next = target->next;
        target->next = temp;
    }
    return OK;
}

循环链表删除数据

链表中只有首元结点
链表中有除首元结点外其它数据时，删除首元结点
删除非首元结点的其它结点
算法思路
1.1 链表中只有首元结点
直接将链表指针置空，释放首元结点的位置；
2.1 链表中有除首元结点外其它数据时，删除首元结点
找到链表的尾结点，将尾结点的指针域指向首元结点的下一个结点；
将链表的指针指向首元结点的下一个结点；
释放首元结点的内存；
3.1 删除非首元结点的其它结点
找到预删除结点并用指针指向预删除结点temp；
找到预删除结点的前一个结点target；
target的指针域指向temp的指针域指向的下个结点；
释放temp的内存；

Status  LinkListDelete(LinkList *L,int place){
    LinkList temp,target;
    int i;
    //temp 指向链表首元结点
    temp = *L;
    if(temp == NULL) return ERROR;
    if (place == 1) {
        if((*L)->next == (*L)){
            temp = *L;
            free(temp);
            (*L) = NULL;
            return OK;
        }
        for (target = *L; target->next != *L; target = target->next);
        temp = *L;
        *L = (*L)->next;
        target->next = *L;
        free(temp);
    }else
    {
        for(i=1,target = *L;target->next != *L && i != place -1;target = target->next,i++) ;
            temp = target->next;
            target->next = temp->next;
            free(temp);
        }
    return OK;
}

总结：在单向链表中，头指针是相当重要的，因为单向链表的操作都需要头指针，所以如果头指针丢失或者破坏，那么整个链表都会遗失，并且浪费链表内存空间，因此我们引入了单向循环链表这种数据结构。