用户登录
用户注册

分享至

循环链表的基本操作及C语言代码实现

  • 作者: 想到你我就硬了唉
  • 来源: 51数据库
  • 2022-09-29

如图,对于插入数据的操作,基本与单链表的插入操作相同,我们可以创建一个**的结点,通过将需要插入的结点的上一个结点的next指针指向该节点,再由需要插入的结点的next指针指向下一个结点的方式完成插入操作。 

单向循环链表插入

其代码可以表示为:

//插入元素

list *insert_list(list *head,int pos,int data){

    //三个参数分别是链表,位置,参数

    list *node=initlist();  //新建结点

    list *p=head;       //p表示新的链表

    list *t;

    t=p;

    node->data=data;

    if(head!=NULL){

        for(int i=1;i<pos;i++){

            t=t->next;  //走到需要插入的位置处

        }

        node->next=t->next;

        t->next=node;

        return p;

    }

    return p;

}

2.   循环单链表的删除操作

如图所示,循环单链表的删除操作可以参考单链表的删除操作,其都是找到需要删除的结点,将其前一个结点的next指针直接指向删除结点的下一个结点即可,但需要注意的是尾节点和头结点的特判,尤其是尾结点,因为删除尾节点后,尾节点前一个结点就成了新的尾节点,这个新的尾节点需要指向的是头结点而不是空,其重点可以记录为【当前的前一节点.next=自身结点.next】这样的操作可以省去头尾结点的特判:

单向循环链表删除结点


其代码可以表示为:

//删除元素

int delete_list(list *head) {

    if(head == NULL) {

        printf("链表为空!\n");

        return 0;

    }

    //建立临时结点存储头结点信息(目的为了找到退出点)

    //如果不这么建立的化需要使用一个数据进行计数标记,计数达到链表长度时自动退出

    //循环链表当找到最后一个元素的时候会自动指向头元素,这是我们不想让他发生的

    list *temp = head;          

    list *ptr = head->next;

  

    int del;

    printf("请输入你要删除的元素:");

    scanf("%d",&del);

  

    while(ptr != head) {

        if(ptr->data == del) {

            if(ptr->next == head) { 

                temp->next = head;

                free(ptr);

                return 1;

            }

            temp->next = ptr->next;    //核心删除操作代码

            free(ptr);

            //printf("元素删除成功!\n");

            return 1;

        }

        temp = temp->next;

        ptr = ptr->next;

    }

    printf("没有找到要删除的元素\n");

    return 0;

}

3.   循环单链表的遍历

与普通的单链表和双向链表的遍历不同,循环链表需要进行结点的特判,找到尾节点的位置,由于尾节点的next指针是指向头结点的,所以不能使用链表本身是否为空(NULL)的方法进行简单的循环判断,我们需要通过判断结点的next指针是否等于头结点的方式进行是否完成循环的判断。

此外还有一种计数的方法,即建立一个计数器count=0,每一次next指针指向下一个结点时计数器加一,当count数字与链表的节点数相同的时候即完成循环,这样做有一个问题,就是获取到链表的节点数同时也需要完成一次遍历才可以达成目标。

其代码可以表示为:

//遍历元素

int display(list *head) {

    if(head != NULL) {

        list *p  = head;

        //遍历头节点到,最后一个数据

        while(p->next != head ) {

            printf("%d   ",p->next->data);

            p = p->next;

        }

        printf("\n");   //习惯性换行 ( o=^?ェ?)o ┏━┓

        //把最后一个节点赋新的节点过去

        return 1;

    else {

        printf("头结点为空!\n");

        return 0;

    }

}

4.   进阶概念—双向循环链表

循环链表还有一个进阶的概念练习,同双向链表与单链表的关系一样,循环单链表也有一个孪生兄弟——双向循环链表,其设计思路与单链表和双向链表的设计思路一样,就是在原有的双向链表的基础上,将尾部结点和头部结点进行互相连接,这个链表的设计不难,就交给读者自主进行设计。

5.   循环单链表代码

#include<stdio.h>

#include<stdlib.h>

typedef struct list{

    int data;

    struct list *next;

}list;

//data为存储的数据,next指针为指向下一个结点

 

//初始结点

list *initlist(){

    list *head=(list*)malloc(sizeof(list));

    if(head==NULL){

        printf("创建失败,退出程序");

        exit(0);

    }else{

        head->next=NULL;

        return head;

    }

}

 

//创建--插入数据

int create_list(list *head){

    int data;   //插入的数据类型

    printf("请输入要插入的元素:");

    scanf("%d",&data);

 

    list *node=initlist();

    node->data=data;

    //初始化一个新的结点,准备进行链接

 

    if(head!=NULL){

        list *p=head;

        //找到最后一个数据

        while(p->next!=head){

            p=p->next;

        }

        p->next=node;

        node->next=head;

        return 1;

    }else{

        printf("头结点已无元素\n");

        return 0;

    }

 

}

 

//插入元素

list *insert_list(list *head,int pos,int data){

    //三个参数分别是链表,位置,参数

    list *node=initlist();  //新建结点

    list *p=head;       //p表示新的链表

    list *t;

    t=p;

    node->data=data;

    if(head!=NULL){

        for(int i=1;i<=pos;i++){

            t=t->next;

        }

        node->next=t->next;

        t->next=node;

        return p;

    }

    return p;

}

 

//删除元素

int delete_list(list *head) {

    if(head == NULL) {

        printf("链表为空!\n");

        return 0;

    }

    //建立零时结点存储头结点信息(目的为了找到退出点)

    //如果不这么建立的化需要使用一个数据进行计数标记,计数达到链表长度时自动退出

    //循环链表当找到最后一个元素的时候会自动指向头元素,这是我们不想让他发生的

    list *temp = head;          

    list *ptr = head->next;

 

    int del;

    printf("请输入你要删除的元素:");

    scanf("%d",&del);

 

    while(ptr != head) {

        if(ptr->data == del) {

            if(ptr->next == head) { //循环结束的条件换成ptr->next == head

                temp->next = head;

                free(ptr);

                return 1;

            }

            temp->next = ptr->next;

            free(ptr);

            //printf("元素删除成功!\n");

            return 1;

        }

        temp = temp->next;

        ptr = ptr->next;

    }

    printf("没有找到要删除的元素\n");

    return 0;

}

 

 

//遍历元素

int display(list *head) {

    if(head != NULL) {

        list *p  = head;

        //遍历头节点到,最后一个数据

        while(p->next != head ) {

            printf("%d   ",p->next->data);

            p = p->next;

        }

        printf("\n");   //习惯性换行 ( o=^?ェ?)o ┏━┓

        //把最后一个节点赋新的节点过去

        return 1;

    } else {

        printf("头结点为空!\n");

        return 0;

    }

}

 

int main(){

    //////////初始化头结点//////////////

    list *head=initlist();

    head->next=head;

    ////////通过插入元素完善链表/////////

    for(int i=0;i<5;i++){   //只是演示使用,不具体提供输入

        create_list(head);

    }

    display(head);

    ////////////插入元素////////////////

    head=insert_list(head,1,10);

    display(head);

    ////////////删除元素////////////////

    delete_list(head);

    display(head);

    return 0;

}


软件
前端设计
程序设计
Java相关