美文网首页
循环链表

循环链表

作者: ios小喽喽 | 来源:发表于2020-09-30 16:56 被阅读0次

    定义结构体:

    导入头文件:

    #include<stdio.h>

    #include "string.h"

    #include"ctype.h"

    #include "stdlib.h"

    #include"math.h"

    #include"time.h"

    #define ERROR0

    #define TRUE1

    #define FALSE0

    #define OK1

    #define MAXSIZE20/* 存储空间初始分配量 */

    typedef int Status;/* Status是函数的类型,其值是函数结果状态代码,如OK等 */

    typedef int ElemType;/* ElemType类型根据实际情况而定,这里假设为int */

    //定义结点

    typedef struct Node{

        ElemTypedata;

        structNode*next;

    }Node;

    typedefstructNode* LinkList;

    创建方式

    /*

     4.1 循环链表创建!

     2种情况:① 第一次开始创建; ②已经创建,往里面新增数据

     1. 判断是否第一次创建链表

        YES->创建一个新结点,并使得新结点的next 指向自身; (*L)->next = (*L);

        NO-> 找链表尾结点,将尾结点的next = 新结点. 新结点的next = (*L);

     */

    Status CreateList(LinkList *L){

        intitem;

        LinkListtemp =NULL;

        LinkListtarget =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)returnERROR;    

                temp->data=item;

                temp->next=*L;  //新节点指向头节点

                target->next=temp;//尾节点指向新节点

            }

        }

        returnOK;

    }

    Status CreateList2(LinkList *L){

        intitem;

        LinkListtemp =NULL;

        LinkListtarget =NULL;

        LinkListr =NULL;

        printf("请输入新的结点, 当输入0时结束!\n");

        while(1) {

            scanf("%d",&item);

            if(item ==0) {

                break;

            }

            //第一次创建

            if(*L ==NULL){

                *L = (LinkList)malloc(sizeof(Node));

                if(!*L)returnERROR;

                (*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;

            }

        }

        returnOK;

    }

    遍历循环链表

    //遍历循环链表,循环链表的遍历最好用do while语句,因为头节点就有值

    void show(LinkList p){ 

        if(p ==NULL){//如果链表是空

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

            return;

        }else{

            LinkListtemp;

            temp = p;

            do{

                printf("%5d",temp->data);

                temp = temp->next;

            }while(temp != p);

            printf("\n");

        }

    }

     循环链表插入数据

    StatusListInsert(LinkList*L,intplace,intnum){

        LinkListtemp ,target;

        inti;

        if(place ==1) {

            //如果插入的位置为1,则属于插入首元结点,所以需要特殊处理

            //1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;

            //2. 找到链表最后的结点_尾结点,

            //3. 让新结点的next 执行头结点.

            //4. 尾结点的next 指向新的头结点;

            //5. 让头指针指向temp(临时的新结点)

            temp = (LinkList)malloc(sizeof(Node));

            if(temp ==NULL) {

                returnERROR;

            }

            temp->data= num;

            for(target = *L; target->next!= *L; target = target->next);

            temp->next= *L;

            target->next= temp;

            *L = temp;

        }else

        {        //如果插入的位置在其他位置;

            //1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;

            //2. 先找到插入的位置,如果超过链表长度,则自动插入队尾;

            //3. 通过target找到要插入位置的前一个结点, 让target->next = temp;

            //4. 插入结点的前驱指向新结点,新结点的next 指向target原来的next位置 ;

            temp = (LinkList)malloc(sizeof(Node));

            if(temp ==NULL) {

                returnERROR;

            }

            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;

        }

        returnOK;

    }

    循环链表删除元素

    Status  LinkListDelete(LinkList*L,intplace){

        LinkList temp,target;

        int i;

        temp = *L; //temp 指向链表首元结点

        if(temp ==NULL)returnERROR;

        if(place ==1) {

            //①.如果删除到只剩下首元结点了,则直接将*L置空;

            if((*L)->next== (*L)){

                (*L) =NULL;

                returnOK;

            }

            //②.链表还有很多数据,但是删除的是首结点;

            //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);

            }

        returnOK;

    }

    循环链表查询值

    intfindValue(LinkListL,intvalue){

        int i =1;    LinkList p;    p = L;

        //寻找链表中的结点 data == value

        while(p->data!= value && p->next!= L) {

            i++;

            p = p->next;

        }

        //当尾结点指向头结点就会直接跳出循环,所以要额外增加一次判断尾结点的data == value;

        if(p->next== L && p->data!= value) {

            return  -1;

        }

        returni;

    }

    相关文章

      网友评论

          本文标题:循环链表

          本文链接:https://www.haomeiwen.com/subject/ayxpuktx.html