02单项循环链表

2020-11-26 本文已影响0人清风烈酒2157

[toc]

循环链表

循环链表 就是在单链表的基础上修改而来单链表是将尾结点的指针指向NULL，循环链表是将尾结点的指针指向向链表的第一个结点。
没有头结点

图示:

3a0a60b3be968714637d7d9aec4eae14

设计一个循环链表

循环链表初始化和赋值

定义结点,常用宏

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

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

typedef int YZStatus;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int YZElemType;/* ElemType类型根据实际情况而定，这里假设为int */

//定义结点
typedef struct YZNode{
    YZElemType data;
    struct YZNode *next;
}YZNode;

typedef struct YZNode * YZLinkList;

循环链表创建

第一次创建
已经创建好直接插入数据

如何判断是否第一次创建链表?

如果是第一次创建,创建一个新结点,并使得新结点的next 指向自身; (L)->next = (L);
找链表尾结点,将尾结点的next = 新结点. 新结点的next = (*L);

创建循环链表->for循环

699397b5da4a7a574288469314a28fcc

YZStatus CreateList(YZLinkList *L){
    int item;
    YZLinkList temp = NULL;//这是一个好习惯
    YZLinkList target = NULL;
    printf("输入节点的值，输入0结束\n");
    while (1) {
        scanf("%d",&item);
        if (item == 0) break;
         //如果输入的链表是空。则创建一个新的节点，使其next指针指向自己  (*head)->next=*head;
        if (*L == NULL){
            *L = (YZLinkList)malloc(sizeof(YZNode));
            if (!*L) exit(0);
            (*L)->next = *L;
            (*L)->data = item;
        }else{
            //输入的链表不是空的，寻找链表的尾节点，使尾节点的next=新节点。新节点的next指向头节点
            //target->next == *L跳出循环,就找到最后一个结点
            //for只是查找,不作操作
            for (target=*L; target->next != *L; target=target->next);
            temp = (YZLinkList)malloc(sizeof(YZNode));;
            temp->data = item;
            temp->next = *L; //新节点指向头节点
            target->next = temp; //尾节点指向新节点
                
        }
    }
    return OK;
}

创建循环链表->尾插法

32af00ba23ecf804896f579e7bca897b

尾插法更符合我们添加数据的习惯,只需要将最后上一个尾指针,指向插入的数据,而不是指向头结点,让最后一个数据指向头指针.
相比于单链表尾插法,多一个指向头指针,单链表在最后让尾结点指向NULL;

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

遍历显示循环列表结点

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

void show(YZLinkList L){
    if(L == nil){
        printf("这是空表~");
        return;
    }
    
    YZLinkList list = NULL;
    YZLinkList list1 = NULL;
    list = L;
    list1 = L;
    do {
        printf("%5d",list->data);
        list = list->next;
    } while (list != L);
     printf("\n");
   
}

注意使用while循环 list != L,循环不会走,如果list == L,循环走一次,因为头部有值,现在循环体,使用do while最合适.

while (list != L) {
        printf("%5d",list->data);
        list = list->next;
    }

插入

插入位置在头部,需要更改尾结点的执行

c4bbd62a1521c2382dc18bdabda50532
插入在尾部,只需要插入数据的next指针指向头结点就行,和其他位置插入没什么区别.

7f41e8af131f53b7c7437e5b6ba73f6f

如果插入的位置为1,则属于插入首元结点,所以需要特殊处理
创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;

找到链表最后的结点_尾结点,
让新结点的next 执行头结点.
尾结点的next 指向新的头结点;
让头指针指向temp(临时的新结点)

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

创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
先找到插入的位置,如果超过链表长度,则自动插入队尾;
通过target找到要插入位置的前一个结点, 让target->next = temp;
插入结点的前驱指向新结点,新结点的next 指向target原来的next位置

YZStatus ListInsert(YZLinkList *L, int place, int num){
    YZLinkList temp = NULL;
    YZLinkList target = NULL;
    int I;
    if (place == 1) {
        temp = (YZLinkList)malloc(sizeof(YZNode));
        if (temp == NULL) return ERROR;
        temp->data = num;
        for (target=*L; target->next != *L; target=target->next);
        target->next = temp;
        temp->next = *L;
        *L = temp;
    }else{
        temp = (YZLinkList)malloc(sizeof(YZNode));
               if (temp == NULL) return ERROR;
        // 从1开始 到插入4位置,找到3节点 2次就够
        for ( i = 1,target = *L; target->next != *L && i != place - 1; target = target->next,i++) ;
         temp->data = num;
         
         temp->next = target->next;
         target->next = temp;
        
    }
    
    return OK;
}

删除

如果删除为首节点
- 节点只剩下一个
  - 如果删除到只剩下首元结点了,则直接将*L置空;
- 节点还很多
  - 找到尾结点, 使得尾结点next 指向头结点的下一个结点 target->next = (*L)->next;
  - 新结点做为头结点,则释放原来的头结点
删除为其他节点
- 找到删除结点前一个结点target
- 临时temp保存要删除的节点
- 使得target->next() 指向temp下一个结点 temp->next
- 释放需要删除的结点temp

YZStatus  LinkListDelete(YZLinkList *L,int place){
    YZLinkList temp = NULL;
    YZLinkList target = NULL;
    int I;
    if (L == NULL) return ERROR;
    //不用的内存要释放掉
    if (place == 1){
        if ((*L)->next == (*L)){
               *L = NULL;
           }
           for (target = *L; target->next != *L; target = target->next);
           temp =  *L;
           *L =  (*L)->next;
           target->next = *L;
           free(temp);
    }else{
          for(i=1,target = *L;target->next != *L && i != place -1;target = target->next,i++) ;
           if (place >= i){
               place = I;
            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;
}

循环链表查询值

只能查找一遍

int findValue(YZLinkList L,int value){
    
    int i = 1;
    YZLinkList 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;
    }
    
    return I;
    
}

测试

示例:

 YZLinkList L;
        int num,place;
        CreateList(&L);

        show(L);
        ListInsert(&L, 2, 100);
        show(L);
        
      printf("输入要删除的位置：");
       scanf("%d",&place);
       LinkListDelete(&L,place);
       show(L);
       
       
       printf("输入你想查找的值:");
       scanf("%d",&num);
       place=findValue(L,num);
       if(place!=-1)
           printf("找到的值的位置是place = %d\n",place);
       else
           printf("没找到值\n");
    }

打印:

2020-04-02 23:37:33.004448+0800 循环链表[1565:61043] Hello, World!
输入节点的值，输入0结束
1
234
4
5
5
3
0
    1  234    4    5    5    3
    1  100  234    4    5    5    3
输入要删除的位置：2
    1  234    4    5    5    3
输入你想查找的值:3
找到的值的位置是place = 6
Program ended with exit code: 0

02单项循环链表

循环链表

设计一个循环链表

循环链表初始化和赋值

循环链表创建

创建循环链表->for循环

创建循环链表->尾插法

遍历显示循环列表结点

插入

删除

循环链表查询值

测试

猜你喜欢

热点阅读