单向循环链表实现总结

说说单向循环链表

人狠话不多. 上图. 单向循环链表就是这个样子!

与单向链表区别之处在于单向链表的最后的结点的指针域 next 是设置为 null. 但是单向循环链表最后一个结点是重新指向它的第一个首元结点的位置;

单向循环链表结构体设计

与单向链表在结构设计上,是一致的.不需要做额外的调整. 虽然修改为单向循环链表,但是总体来说还是单向的;

//定义结点
typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node * LinkList;

单向链表的创建 (采用尾插法)

在实现单向链表的创建时,需要考虑.你进行创建新增结点时的2种情况

第一种情况: 第一次创建; 第二种情况: 链表已经创建成功,并且已经存储了相应的结点. 需要在链表的末尾继续新增数据;

代码实现如下:

/*
 4.1 循环链表创建!
 2种情况:① 第一次开始创建; ②已经创建,往里面新增数据
 
 1. 判断是否第一次创建链表
    YES->创建一个新结点,并使得新结点的next 指向自身; (*L)->next = (*L);
    NO-> 找链表尾结点,将尾结点的next = 新结点. 新结点的next = (*L);
 */
Status CreateList(LinkList *L){

    int item;
    LinkList temp = NULL;
    LinkList target = NULL;
    printf("输入节点的值，输入0结束\n");
    while(1)
    {
        scanf("%d",&item);
        if(item==0) break;
        
          //如果输入的链表是空。则创建一个新的节点，使其next指针指向自己  (*head)->next=*head;
        if(*L==NULL)
        {
            *L = (LinkList)malloc(sizeof(Node));
            if(!L)exit(0);
            (*L)->data=item;
            (*L)->next=*L;
        }
        else
        {
           //输入的链表不是空的，寻找链表的尾节点，使尾节点的next=新节点。新节点的next指向头节点
            
            for (target = *L; target->next != *L; target = target->next);
            
            temp=(LinkList)malloc(sizeof(Node));
            
            if(!temp) return ERROR;
            
            temp->data=item;
            temp->next=*L;  //新节点指向头节点
            target->next=temp;//尾节点指向新节点
        }
    }
    
    return OK;
}

在上面的代码实现中,我们使用了一个for循环来实现关于最后一个结点的获取; 但是这样的方式会增加时间复杂度. 所以在创建链表时,可以使用一个临时指针来记录最后一个结点. 用来确保每次新增数据后,都能添加到最后并且及时修改链表信息;

Status CreateList2(LinkList *L){
    
    int item;
    LinkList temp = NULL;
    LinkList r = NULL;
    printf("请输入新的结点, 当输入0时结束!\n");
    while (1) {
        scanf("%d",&item);
        if (item == 0) {
            break;
        }
        
        //第一次创建
        if(*L == NULL){
            
            *L = (LinkList)malloc(sizeof(Node));
            if(!*L) return ERROR;
            (*L)->data = item;
            (*L)->next = *L;
            r = *L;
        }else{
            
            temp = (LinkList)malloc(sizeof(Node));
            if(!temp) return  ERROR;
            temp->data = item;
            temp->next = *L;
            r->next = temp;
            
            r = temp;
        }
    }
    return OK;
}

单向循环链表插入数据

在往一个单向循环链表中插入数据,需要提前分析2种情况.

• 第一种情况,则是插入的位置在首元结点上;
• 第二种情况,插入其他位置(包括链表中间/末尾);

在这里就不单独解释为什么插入单向链表不需要考虑末尾的情况. 如果有需要可以看图了解一下;

单向循环链表插入情况(首元结点位置)

• 判断输入的位置是否是place = 1;
• 创建新的结点temp,并且做出合理的健壮性判断;以及赋值
• 将新创建的结点temp 的next 指向原始的首元结点 A 的位置
• 通过循环找到链表最后一个尾结点,将尾结点的next 指针域指向 新创建的结点 temp.
• 由于链表的首元结点,通过插入发生了改变,所以此时将*L 指向新的首元结点 temp

代码实现如下:

if (place == 1) {
        
        //如果插入的位置为1,则属于插入首元结点,所以需要特殊处理
        //1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
        //2. 找到链表最后的结点_尾结点,
        //3. 让新结点的next 执行头结点.
        //4. 尾结点的next 指向新的头结点;
        //5. 让头指针指向temp(临时的新结点)
        
        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;
        
    }

单向循环链表插入情况(其他位置)

• 判断输入的位置是否是place = 1;
• 创建新的结点temp,并且做出合理的健壮性判断;以及赋值;
• 通过循环找到待插入的位置前一个结点 p ;
• 将新创建的结点 temp 指向 p->next;
• 将待插入结点的前一个结点 P 与新结点 temp 之间连接起来;

代码实现如下:

 //如果插入的位置在其他位置;
        //1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
        //2. 先找到插入的位置,如果超过链表长度,则自动插入队尾;
        //3. 通过target找到要插入位置的前一个结点, 让target->next = temp;
        //4. 插入结点的前驱指向新结点,新结点的next 指向target原来的next位置 ;
        
        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;

单向循环链表的删除

在实现单向链表的创建时,需要考虑.你进行创建新增结点时的3种情况

• 第一种情况: 删除的位置在首元结点上;
• 第二种情况: 删除时,当链表只剩下最后一个结点时;
• 第三种情况: 删除其他位置上的结点;

代码实现如下:

//4.4 循环链表删除元素
Status  LinkListDelete(LinkList *L,int place){
    
    LinkList temp,target;
    int i;
    //temp 指向链表首元结点
    temp = *L;
    if(temp == NULL) return ERROR;
    
    
    if (place == 1) {
        
        //①.如果删除到只剩下首元结点了,则直接将*L置空;
        if((*L)->next == (*L)){
            (*L) = NULL;
            return OK;
        }
        
        
        //②.链表还有很多数据,但是删除的是首结点;
        //1. 找到尾结点, 使得尾结点next 指向头结点的下一个结点 target->next = (*L)->next;
        //2. 新结点做为头结点,则释放原来的头结点
        
        for (target = *L; target->next != *L; target = target->next);
        temp = *L;
        
        *L = (*L)->next;
        target->next = *L;
        free(temp);
    }else
    {

        //如果删除其他结点--其他结点
        //1. 找到删除结点前一个结点target
        //2. 使得target->next 指向下一个结点
        //3. 释放需要删除的结点temp
        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;
    
}

嗯.关于单向循环链表的最核心的几个动作就已经实现了. 下一次博客见!