线性表-单向循环链表

为了方便，本文介绍的单向循环链表不包含头节点

单向循环链表内容

• 单向循环链表的的定义
• 单向循环链表的创建
• 单向循环链表插入
• 单向循环链表的删除
• 单向循环链表的查询

单向循环链表的的定义

在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点
它的有点是：从任一结点出发都可访问到表中所有结点。

单向循环链表的创建

单向循环链表有两种表现形式，如下图：

表现形式

在创建单向循环链表，分为两种情况：
第一次创建、已创建，新增元素，所以，思路如下
判断是否第一次创建
YES：创建节点，将指针域指向自己
NO：找到链表结尾的位置
创建新的节点
尾节点->next=新节点
新节点->next=头节点
早

//单向循环链表的创建
Status createSCycleList(Linklist *node){
    int item;
    
    Linklist temp;
    Linklist tail = NULL;//记录最后一个节点
    while (1) {
        scanf("%d", &item);
        
        if (item == 0)
            break;
        
        if (*node == NULL) {
            //节点为空时，第一次创建，将节点的next指向自己，同时记录尾节点
            *node = malloc(sizeof(lNode));
            if (*node == NULL)
                return ERROR;
            (*node)->data=item;
            (*node)->next = *node;
            tail = *node;
        }else{
            
            //创建节点
            temp = malloc(sizeof(lNode));
            if (temp == NULL)
                return ERROR;
            temp->data=item;
            //指向头节点
            temp->next = *node;
            //尾节点指向新建节点
            tail->next = temp;
            tail = temp;
        }
    }
    
    return OK;
}
//在其他地方调用
LinkList sCycleList;
createSCycleList(&sCycleList);

上面一直是把节点插在后面，下面这个是把节点插在前面

Status createSCycleList(Linklist *node){
    int item;
    
    Linklist temp;
    Linklist tail = NULL;//记录最后一个节点
    while (1) {
        scanf("%d", &item);
        
        if (item == 0)
            break;
        
        if (*node == NULL) {
            //节点为空时，第一次创建，将节点的next指向自己，同时记录尾节点
            *node = malloc(sizeof(lNode));
            if (*node == NULL)
                return ERROR;
            (*node)->data=item;
            (*node)->next = *node;
            tail = *node;
        }else{
            
            //创建节点
            temp = malloc(sizeof(lNode));
            if (temp == NULL)
                return ERROR;
            temp->data=item;
            //指向头节点
            temp->next = *node;
            //尾节点指向新建节点
            tail->next = temp;
            //将头指针指向新首元节点
            *node = temp;
        }
    }
    
    return OK;
}

---

单向循环链表插入

单向循环链表插入分为两种情况：
如果是在第一个位置：
1.首先创建新节点p，将值赋值给p节点的数据域；
2.将p->next指向首元节点node；
3.遍历找到尾节点tail，将tail->next指向新的首元节点p
4.将头指针指向新的首元节点：*node = p

如果不是在第一个位置：
1.找到要插入位置的前一个节点p；
2.将新建节点的next指向p->next；
3.将p->next指向新建节点

//单循环链表插入
Status insertCycleList(Linklist *node,int place,int num){
    
    //链表为空
    if (*node == NULL)
        return ERROR;
    
    //插入位置不对
    if (place < 1)
        return ERROR;
    
    Linklist target,temp;
    int i = 0;
    if (place == 1) {
        //创建temp
        temp = malloc(sizeof(lNode));
        if (temp == NULL)
            return ERROR;
        temp->data = num;
        //找尾节点
        //尾节点下一个节点等于头节点时，找到尾节点
        for (target = *node; target->next != *node; target = target->next);
        
        //新节点->next
        temp->next = *node;
        //尾节点->next = 新节点
        target->next = temp;
        //让头节点 = temp
        *node = temp;
    }else{
        //创建新节点 temp
        temp = malloc(sizeof(lNode));
        if (temp == NULL)
            return ERROR;
        temp->data = num;
        
        //找到插入前的一个位置target
        for (i = 1,target = *node; target->next != *node && i != place-1 ; target = target->next,i++);
        
        if (*node == target->next && (i+1) < place) {
            //第i-1位置的节点的下一个节点是头节点，且插入位置大于末尾位置，超出插入范围
            //比如，只有四个元素，你可以插在第五个的位置，你不能插入到第六个位置
            return ERROR;
        }
        
        //新节点next指向target->next
        temp->next = target->next;
        //target后继是新节点
        target->next = temp;
        
    }
    
    return OK;
}

单向循环链表的删除

单向循环链表的删除分为两种情况：
如果是在第一个位置：
1.遍历找到尾节点tail；
2.temp记录首元节点；
3.首元节点=首元节点->next
4.尾节点指向首元节点，同时释放temp

如果不是在第一个位置：
1.找到要删除位置的前一个节点p；
2.将p->next赋值要删除的节点q；
3.将p->next指向q->next,并释放q

//单循环链表的删除
Status deleteCycleList(Linklist *node,int place){
    
    if(*node == NULL || place < 1) return ERROR;
    
    lNode *target,*temp;
    int i = 0;
    
    //如果只有一个节点
    if ((*node)->next == *node) {
        if (place > 1) {
            return ERROR;
        } else {
            temp = *node;//记录该节点
            *node = NULL;//将头节点指向NULL
            free(temp);//释放该节点
            return OK;
        }
    }
    
    if (place == 1) {
        //找尾节点
        //尾节点下一个节点等于头节点时，找到尾节点
        for (target = *node; target->next != *node; target = target->next);
        temp = *node;
        *node = (*node)->next;
        target->next = *node;
        free(temp);
    } else {
        //找到删除前的一个位置target
        for (i = 1,target = *node; target->next != *node && i != place-1 ; target = target->next,i++);
        
        if (*node == target->next) {//第i-1位置的节点的下一个节点是头节点，超出删除范围
            return ERROR;
        }
        
        temp = target->next;
        target->next = temp->next;
        free(temp);
    }
    
    return OK;
}

单向循环链表的查询

//单循环链表的查询
int findNodeFromCycleList(Linklist node, int value){
    
    if (node == NULL) {
        return -1;
    }
    
    int i = 1;
    Linklist temp = node;
    while (temp && temp->data != value && temp->next != node) {
        i++;
        temp = temp->next;
    }
    
    //防止没有找到，返回了1
    if (temp->next == node && temp->data != value) {
        return -1;
    }
    return i;
}