数据结构（4）线性表之单循环链表

喜欢ヅ旅行 2023-08-17 16:50 176阅读 0赞

### 数据结构（4）线性表之单循环链表 ###

*   *   *  前言
         *  尾指针
         *  注
         *  全部代码
         *   *  SCList.h
             *  SCList.cpp
             *  Main.cpp

### 前言 ###

所谓单循环链表，实际上就是在单链表的基础上，使最后一个结点的next指针再指向头结点，形成循环的效果。这样，从表中任何一个结点出发都可以找到其他结点的位置。

### 尾指针 ###

顾名思义，尾指针是指向链表的最后一个结点。在单循环链表中，设立尾指针能使得一些操作简化，例如两个单循环链表的合并。

![img\_2][img_2]

![img\_3][img_3]

### 注 ###

我们之前所写的管理结构，是既包括头指针又包括尾指针的，因此在实现某些操作时就很方便了。

单循环链表和单链表的实现思路、注意事项都是一样的，只是需要额外注意的是，在我们的管理结构中要注意保持last的next指针始终指向头结点，达到循环的效果。

附：单链表的实现思路及注意事项  
[数据结构（2.1）线性表之单链表的表示和实现][2.1]  
[数据结构（2.2）线性表之单链表的具体实现][2.2]

*  链表为空

![链表为空][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg_size_16_color_FFFFFF_t_70]

*  链表非空

![链表非空][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg_size_16_color_FFFFFF_t_70 1]

### 全部代码 ###

单循环链表的各项操作与单链表并无差别，只是在判断链表结束的条件有差别，之前是判断next指针是否为空，现在需要判断是否为头结点。因此实现代码并没有巨大的改变，只是在一些判断条件上做出改变。

#### SCList.h ####

#ifndef SCList_h
    #define SCList_h
    
    #include <stdio.h>
    #include <malloc.h>
    #include <assert.h>
    
    #define ElemType int
    
    //结点的结构
    typedef struct Node{ 
        ElemType data;
        struct Node *next;
    }Node, *Pnode;
    
    //链表的结构
    typedef struct List{ 
        Pnode first;
        Pnode last;
        int size;
    }List;
    
    //初始化单循环链表
    void InitSCList(List *list);
    
    //1.尾部插入
    void push_back(List *list,ElemType x);
    //2.头部插入
    void push_fount(List *list,ElemType x);
    //3.展示
    void show_list(List *list);
    //4.尾部删除
    void pop_back(List *list);
    //5.头部删除
    void pop_fount(List *list);
    //6.按值插入(要求插入前的链表是有序的(此处为顺序
    void insert_val(List *list,ElemType x);
    //7.按值查找
    Node* find(List *list,ElemType x);
    //8.获取长度
    int length(List *list);
    //9.按值删除
    void  delete_val(List *list,ElemType x);
    //10.排序
    void sort(List *list);
    //11.逆置(前后转换
    void resver(List *list);
    //12.清除单链表 ->只清除数据，保留头结点
    void clearList(List *list);
    //13.摧毁 ->包括头结点在内一起摧毁
    void destroy(List *list);
    
    //生成一个结点
    Node* getNode(ElemType x);
    #endif /* SCList_h */

#### SCList.cpp ####

#include "SCList.h"
    
    //初始化单循环链表
    void InitSCList(List *list){ 
        Node *s = (Node *)malloc(sizeof(Node));
        assert(s != NULL);
        list->first = list->last = s;
        
        //让最后一个结点的next指向头部，形成循环
        list->last->next = list->first;
        list->size = 0;
    }
    
    //1.尾部插入
    void push_back(List *list,ElemType x){ 
        Node *s = getNode(x);
        
        //将这个结点接到链表尾部
        list->last->next = s;
        
        //重新设置last指针的指向
        list->last = s;
        
        //让最后一个结点的next指向头部，形成循环
        list->last->next = list->first;
        list->size ++;
    }
    
    
    //2.头部插入
    void push_fount(List *list,ElemType x){ 
        Node *s = getNode(x);
        
        s->next = list->first->next;
        list->first->next = s;
        
        //判断是否是第一个结点
        if (list->last == list->first) { 
            //是，更改last指针的指向
            list->last = s;
        }
        
        list->size ++;
    }
    
    //3.展示
    void show_list(List *list){ 
        Node *p = list->first->next;
        
        while (p != list->first) { 
            printf("%4d",p->data);
            p = p->next;
        }
        printf("\n");
    }
    
    
    //4.尾部删除
    void pop_back(List *list){ 
        if (list->size == 0) { 
            printf("无可删除的结点！\n");
            return;
        }
        
        //寻找倒数第二个结点
        Node *p = list->first;
        while (p->next != list->last) { 
            p = p->next;
        }
        
        //释放它后一个结点(即最后一个结点)
        free(list->last);
        //更改last指针的指向
        list->last = p;
        //让最后一个结点的next指向头部，形成循环
        list->last->next = list->first;
        list->size --;
    }
    
    //5.头部删除
    void pop_fount(List *list){ 
        if (list->size == 0) { 
            printf("无可删除的结点！\n");
            return;
        }
        
        Node *p = list->first->next;
        list->first->next = p->next;
        free(p);
        
        //判断是否是最后一个结点
        if(list->size == 1){ 
            //重新设置last的指向
            list->last = list->first;
        }
        
        list->size --;
    }
    //6.按值插入(要求插入前的链表是有序的(此处为顺序
    void insert_val(List *list,ElemType x){ 
        Node *p = list->first;
        
        //寻找插入位置
        while (p->next != list->last && p->next->data < x) { 
            p = p->next;
        }
        
        //到达了最后一个结点后，还需要与最后一个结点的值进行比较
        //判断是否比最后一个结点大
        if (p->next == list->last && p->next->data < x) { 
            //是，直接进行尾部插入
            push_back(list, x);
        }else{ 
            //其他状况，直接在该位置进行插入
            Node *s = getNode(x);
            
            s->next = p->next;
            p->next = s;
            list->size ++;
        }
    }
    //7.按值查找
    Node* find(List *list,ElemType x){ 
        if (list->size == 0) { 
            return NULL;
        }
        
        //遍历整个链表
        Node *p = list->first->next;
        while (p != list->first && p->data != x) { 
            p = p->next;
        }
        
        //判断是否回到头部
        if (p == list->first) { 
            //是，说明链表中没有要找的数据
            return NULL;
        }else{ 
                return p;
        }
    }
    //8.获取长度
    int length(List *list){ 
        return list->size;
    }
    
    //9.按值删除
    void  delete_val(List *list,ElemType x){ 
        if (list->size == 0) { 
            printf("链表为空，无法删除！\n");
            return;
        }
        
        Node *p = find(list, x);
        if (p == NULL) { 
            printf("要删除的数据不存在!\n");
            return;
        }
        
        //判断是否是最后一个结点
        if (p == list->last) { 
            //是，直接尾部删除
            pop_back(list);
        }else{ 
            //判断是否是倒数第二个结点
            if (p->next == list->last) { 
                //是，需要修改last指针的指向
                list->last = p;
            }
            Node *s = p->next;
            p->data = s->data;
            p->next = s->next;
            free(s);
            list->size --;
        }
    }
    
    //10.排序
    void sort(List *list){ 
        if (list->size <= 1) { 
            return;
        }
        
        Node *s = list->first->next;
        Node *q = s->next;
        
        //将链表尾部断开
        list->last->next = NULL;
        //重新设置last指针
        list->last = s;
        //让链表再次循环
        list->last->next = list->first;
        
        while (q != NULL) { 
            s = q;
            q = q->next;
            //进行按值插入
            insert_val(list, s->data);
            free(s);
            list->size --;
            
    // //寻找插入位置
    // Node *p = list->first;
    // while (p->next != list->last && p->next->data < s->data) { 
    // p = p->next;
    // }
    //
    // //判断是否是最后一个结点
    // if (p->next == list->last && p->next->data < s->data) { 
    // //是，直接进行尾部插入
    // s->next = list->last->next;
    // list->last->next = s;
    // list->last = s;
    //
    // }else{ 
    // s->next = p->next;
    // p->next = s;
    // }
            
        }
    }
    
    //11.逆置(前后转换
    void resver(List *list){ 
        if (list->size <= 1) { 
            return;
        }
        
        Node *s = list->first->next;
        Node *q = s->next;
        
        list->last->next = NULL;
        list->last = s;
        list->last->next = list->first;
        
        while (q != NULL) { 
            s = q;
            q = q->next;
            //进行头部插入
            push_fount(list, s->data);
            free(s);
            list->size--;
            
    // //进行头部插入
    // s->next = list->first->next;
    // list->first->next = s;
        }
    }
    
    //12.清除单链表 ->只清除数据，保留头结点
    void clearList(List *list){ 
        Node *p = list->first->next;
        while (p != list->first) { 
            p = p->next;
            pop_fount(list);
        }
        
    }
    //13.摧毁 ->包括头结点在内一起摧毁
    void destroy(List *list){ 
        clearList(list);
        free(list->first);
        list->first = list->last = NULL;
    }
    
    //生成一个结点
    Node* getNode(ElemType x){ 
        Node *s = (Node *)malloc(sizeof(Node));
        assert(s != NULL);
        
        s->data = x;
        s->next = NULL;
        
        return s;
    }

#### Main.cpp ####

#include "SCList.h"
    
    int main(int argc, const char * argv[]) { 
       
        List myList;
        InitSCList(&myList);
        
        //保存要输入的数据
        ElemType item;
        //保存要查找的地址
        Node *p = NULL;
        int select = 1;
        while (select) { 
            printf("**************************************\n");
            printf("* [1] push_back [2] push_front *\n");
            printf("* [3] show_list [4] pop_back *\n");
            printf("* [5] pop_front [6] insert_val *\n");
            printf("* [7] find [8] length *\n");
            printf("* [9] delete_val [10] sort *\n");
            printf("* [11] resver [12] clear *\n");
            printf("* [13*] destroy [0] quit_system*\n");
            printf("**************************************\n");
            printf("请选择:");
            scanf("%d",&select);
            if (select == 0) { 
                break;
            }
            switch (select) { 
                case 1:
                    //尾部插入
                    printf("请输入要插入的数据(-1结束):");
                    scanf("%d",&item);
                    while (item != -1) { 
                        push_back(&myList, item);
                        scanf("%d",&item);
                    }
                    break;
                case 2:
                    //头部插入
                    printf("请输入要插入的数据(-1结束):");
                    scanf("%d",&item);
                    while (item != -1) { 
                        push_fount(&myList, item);
                        scanf("%d",&item);
                    }
                    break;
                case 3:
                    //展示单链表
                    show_list(&myList);
                    break;
                case 4:
                    //尾部删除
                    pop_back(&myList);
                    break;
                case 5:
                    //头部删除
                    pop_fount(&myList);
                    break;
                case 6:
                    //按值插入
                    printf("请输入要插入的数据:\n");
                    scanf("%d",&item);
                    insert_val(&myList, item);
                    break;
                case 7:
                    //按值查找
                    printf("请输入要查找的值:\n");
                    scanf("%d",&item);
                    p = find(&myList, item);
                    if (p == NULL) { 
                        printf("要查找的数据不存在!\n");
                    }else{ 
                        printf("地址为:%p\n",p);
                    }
                    break;
                case 8:
                    //展示链表长度
                    printf("链表的长度为:%d\n",length(&myList));
                    break;
                case 9:
                    //按值删除
                    printf("请输入要删除的值：\n");
                    scanf("%d",&item);
                    delete_val(&myList, item);
                    break;
                case 10:
                    //排序
                    sort(&myList);
                    break;
                case 11:
                    //逆置(前后转换
                    resver(&myList);
                    break;
                case 12:
                    //清除
                    clearList(&myList);
                    break;
                case 13:
                    destroy(&myList);
                    break;
                default:
                    printf("输入的命令有误，请重新插入\n");
                    break;
            }
        }
        return 0;
    }

[img_2]: /images/20230809/bfdb6a15013647dda85897764032941b.png
[img_3]: /images/20230809/da0476d4549d45829660a981fa8dff83.png
[2.1]: https://blog.csdn.net/weixin_42643216/article/details/100178936
[2.2]: https://blog.csdn.net/weixin_42643216/article/details/100586898
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg_size_16_color_FFFFFF_t_70]: /images/20230809/a4395cda393e43df82abfc215397a572.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg_size_16_color_FFFFFF_t_70 1]: /images/20230809/5ff2aaff5ab844c1bfd93817609d6064.png