单向循环链表

单向循环链表

循环链表顾名思义就是链表是循环的,最后一个节点的next指向首元节点,从而形成一个环.如图

单向循环链表

单向循环链表结构设计

与上篇的单向链表设计是一样的,不一样的是将最后一个节点的next指向了首元节点

typedef int ElemType;
typedef int Status;
typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node * List;

单向循环链表的创建

这里我们采用的尾插法
分为两种情况

1. 第一次创建
2. 链表已经创建成功
   为了方便我们声明一个临时变量来存储最后 一个节点

Status createList(List *L){
    List r = NULL;
    List temp = NULL;
    for (int  i = 1; i < 10; i++) {
        //第一次创建
        if (*L == NULL) {
            *L = malloc(sizeof(Node));
            if (!*L) return ERROR;
            (*L)->data = I;
            (*L)->next = *L;
            r = *L;
        }else{
            temp = malloc(sizeof(Node));
            temp->data = I;
            temp->next = *L;
            r->next = temp;
            r = temp;
        }
    }
    return OK;
}

单向循环链表的插入

插入也分为两种情况

1. 插入位置在首元结点时
2. 其他位置

首元结点插入

• 判断place是否=1
• 创建新的临时节点temp,判断是否创建成功
• 找到最后节点
• 将temp的next指向target的next
• target的next指向temp

首元结点插入

其他位置插入

• 创建新的临时节点temp,判断是否创建成功
• 循环查找要插入位置的前一个节点target
• 将temp的next指向target的next
• 将target的next指向temp

image.png

Status insertList(List *L,int place,ElemType e){
    List temp = NULL;
    List target = *L;
    if (place == 1) {
        temp = malloc(sizeof(Node));
        if (!temp) return ERROR;
        temp->data = e;
        //找到最后节点
        while (target->next != *L) {
            target = target->next;
        }
        temp->next = target->next;
        target->next = temp;
        *L = temp;
    }else{
        temp = malloc(sizeof(Node));
        if (!temp) return ERROR;
        temp->data = e;
        for (int  i = 1; i < place - 1; i++) {
            if (target->next == *L) break;
            target = target->next;
        }
        temp->next = target->next;
        target->next = temp;
        
    }
    return OK;
}

单向循环链表的删除

单向循环链表的删除,考虑到三种情况

1. 删除的是首元结点
2. 删除的链表只剩下一个节点
3. 删除其他位置

Status deleteList(List *L,int place){
    List target = *L;
    List temp;
    if (place == 1){
        //如果链表只有一个首元节点那么直接置空
        if ((*L)->next == *L) {
            (*L) = NULL;
            return OK;
        }
        //找到最后节点
        while (target->next != *L) {
            target = target->next;
        }
        *L = (*L)->next;
        target->next = *L;
    }else{
        for (int  i = 1; i < place - 1; i++) {
            if (target->next == *L) break;
            target = target->next;
        }
        temp = target->next;
        target->next = temp->next;
        free(temp);
    }
    return OK;
}