数据结构（6）线性表之双循环链表

矫情吗；* 2023-06-08 03:18 8阅读 0赞

### 数据结构（6）线性表之双循环链表 ###

*   *   *  前言
         *  双循环链表的插入与删除
         *  全部代码
         *   *  DCList.h
             *  DCList.cpp
             *  Main.cpp

### 前言 ###

同单链表一样，双向链表也可以是循环表。链表最后一个结点的next指针指向头结点，头结点的Prior指针指向最后一个结点，形成循环。

带头结点的空链表

![img\_1][img_1]

带头结点的非空链表

![img\_2][img_2]

添加管理结构

![img\_3][img_3]

### 双循环链表的插入与删除 ###

实际上，在循环链表中，无论是头部插入还是尾部插入，都可以理解为按位置插入(就是在两个结点中间进行插入)：头部插入是在头结点和首元结点之间进行插入，尾部插入则是在最后一个结点和头结点之间进行插入。这样，我们只需要知道如何在两个结点中间进行插入，就可以实现双循环链表诸多的插入操作。而如何在两个结点中间进行插入，跟在双链表中是一致的，也就是需要考虑四个指针的指向

*  待插入结点的Prior指针
 *  待插入结点的Next指针
 *  待插入结点前驱的Next指针
 *  待插入结点后继的Prior指针

这样，本来区分开的头部插入、尾部插入操作可以整合为按位置插入，参数传要插入的位置即可。但是考虑到我们的双链表增加了管理结构，还需要保证管理结构指针的正确性，所以在代码中仍是区分实现的。

![img\_4][img_4]

尾部插入也是两个结点中的插入

![img\_6][img_6]

实际上

![img\_5][img_5]

插入与删除类似

![img\_7][img_7]  
![img\_8][img_8]  
其他操作同双链表一致，只是判断循环结束的条件有区别罢了，不细说

### 全部代码 ###

#### DCList.h ####

#ifndef DCList_h
    #define DCList_h
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    
    #define ElemType int
    
    typedef struct Node{ 
        ElemType data;
        struct Node *prior;
        struct Node *next;
    }Node,*PNode;
    
    typedef struct List{ 
        PNode first;
        PNode last;
        int size;
    }List;
    
    //初始化
    void InitDCList(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 /* DCList_h */

#### DCList.cpp ####

#include "DCList.h"
    
    //初始化
    void InitDCList(List *list){ 
        //申请头结点
        Node *s = (Node *)malloc(sizeof(Node));
        assert(s != NULL);
        list->first = list->last = s;
        
        //使链表循环
        list->first->prior = list->last;
        list->last->next = list->first;
    
    	list->size = 0;
    }
    
    //1.尾部插入
    void push_back(List *list,ElemType x){ 
        Node *s = getNode(x);
        
        //s的前驱指向最后一个结点
        s->prior = list->last;
        //s的后继指向头结点
        s->next = list->last->next;
        //头结点的前驱指向s
        //list->last->next->prior = s;
        s->next->prior = s;
        //最后一个结点的后继指向s
        list->last->next = s;
        
        //重新设置last指针的值
        list->last = s;
        
        list->size ++;
    }
    
    //2.头部插入
    void push_fount(List *list,ElemType x){ 
        Node *s = getNode(x);
        
        //s的后继是头结点的后继
        s->next = list->first->next;
        //s的前驱是头结点
        s->prior = list->first;
        //原先第一个结点的前驱改为s
        //list->first->next->prior = s;
        s->next->prior = s;
        //头结点的后继改为s
        list->first->next = s;
        
        //判断是否是第一个结点
        if (list->first == list->last) { 
            //是，需要修改last指针的指向
            list->last = s;
        }
        
        list->size ++;
    }
    
    //3.展示
    void show_list(List *list){ 
        Node *s = list->first->next;
        
        while (s != list->first) { 
            printf("%4d",s->data);
            s = s->next;
        }
    
        printf("\n");
    }
    
    //4.尾部删除
    void pop_back(List *list){ 
        
        if (list->size == 0) { 
            printf("链表已空！\n");
            return;
        }
        
        Node *s = list->last;
        //last指针修改为s的前驱
        //list->last = list->last->prior;
        list->last = s->prior;
        
        //s前驱的next指针指向s的后继(即头结点)
        //list->last->next = s->next;
        s->prior->next = s->next;
        
        //s后继的prior指针(即头结点的prior指针)指向s的前驱(即新的最后一个结点)
        //s->next->prior = list->last;
        s->next->prior = s->prior;
        //释放s
        free(s);
        
        list->size --;
    }
    
    //5.头部删除
    void pop_fount(List *list){ 
        if (list->size == 0) { 
            printf("链表已空！\n");
            return;
        }
        
        Node *s = list->first->next;
        //s前驱的后继指向s的后继(即头结点的next指向s的next)
        //list->first->next = s->next;
        s->prior->next = s->next;
        
        //s后继的前驱指向s的前驱(即s的后继的prior指针指向头结点)
        //s->next->prior = list->first;
        s->next->prior = s->prior;
        //释放s
        free(s);
        
        //判断删除的是否是最后一个结点
        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->first && p->next->data < x) { 
            p = p->next;
        }
        
        
        //在p结点之后进行插入
        //判断插入位置
        if (p->next == list->first) { 
            //尾部插入
            push_back(list, x);
        }else{ 
            Node *s = getNode(x);
            
            //s的前驱为p
            s->prior = p;
            //s的后继为p的后继
            s->next = p->next;
            //p后继的前驱改为s
            p->next->prior = s;
            //p的后继改为s
            p->next = s;
            
            list->size ++;
        }
        
    }
    
    //7.按值查找
    Node* find(List *list,ElemType x){ 
        Node *s = list->first->next;
        while (s != list->first && s->data != x) { 
            s = s->next;
        }
        if (s == list->first) { 
            //循环结束，没找到
            return NULL;
        }
        return s;
    }
    //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) { 
            //如果是最后一个，直接进行尾部删除
            push_back(list, x);
        }else{ 
            //p后继的前驱指向p的前驱
            p->next->prior = p->prior;
            //p前驱的后继指向p的后继
            p->prior->next = p->next;
            
            list->size --;
        }
    }
    
    //10.排序
    void sort(List *list){ 
        if (list->size <= 1) { 
            printf("无须排序！\n");
            return;
        }
        
        //将链表分为两个部分,s单独作为一个链表，p指向后续结点
        Node *s = list->first->next;
        Node *p = s->next;
        //将后续结点的最后一个结点的next指针标记为空
        list->last->next = NULL;
        
        //重新设置last指针的值
        list->last = s;
        
        //让链表循环
        //s的后继指向头结点
        //list->last->next = list->first;
        s->next = list->first;
        //头结点的前驱指向s
        //list->first->prior = list->last;
        list->first->prior = s;
        
        while (p != NULL) { 
            s = p;
            p = p->next;
            
            //直接进行按值插入
            insert_val(list, s->data);
            free(s);
            list->size --;
        }
        
        
    }
    //11.逆置(前后转换
    void resver(List *list){ 
        if (list->size <= 1) { 
            printf("无须逆置！\n");
            return;
        }
        
        //将链表分为两个部分,s单独作为一个链表，p指向后续结点
        Node *s = list->first->next;
        Node *p = s->next;
        //将后续结点的最后一个结点的next指针标记为空
        list->last->next = NULL;
        
        //重新设置last指针的值
        list->last = s;
        
        //让链表循环
        //s的后继指向头结点
        //list->last->next = list->first;
        s->next = list->first;
        //头结点的前驱指向s
        //list->first->prior = list->last;
        list->first->prior = s;
        
        while (p != NULL) { 
            s = p;
            p = p->next;
            
            //直接进行头部插入
            push_fount(list, s->data);
            free(s);
            list->size --;
        }
    }
    //12.清除单链表 ->只清除数据，保留头结点
    void clearList(List *list){ 
        if (list->size == 0) { 
            return;
        }
        
        Node *s = list->first;
        Node *p = s->next;
        //遍历整个链表，释放结点
        while (p != list->first) { 
            s = p;
            p = p->next;
            free(s);
            list->size --;
        }
        
        //重新设置last指针
        list->last = list->first;
        //使链表循环
        list->first->prior = list->last;
        list->last->next = list->first;
        
    }
    //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->prior = s->next = NULL;
        
        //返回
        return s;
    }

#### Main.cpp ####

#include "DCList.h"
    
    int main(int argc, const char * argv[]) { 
       
        List myList;
        InitDCList(&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_1]: /images/20230531/d7fe292a68224f8eae90f9e01898c4cd.png
[img_2]: /images/20230531/4f1f356d0c6643c8b38dbbe20f3af6bf.png
[img_3]: /images/20230531/c9686d1864854cf59dcfc8d5c46b7400.png
[img_4]: /images/20230531/36e99c0c52244cffb8167cac4d047bd1.png
[img_6]: /images/20230531/53100d1e6004482e8181c5d574a23780.png
[img_5]: /images/20230531/0b9ed608f0884cb197e83083646fa774.png
[img_7]: /images/20230531/3b406e565c594718b08ae7dae5f60084.png
[img_8]: /images/20230531/d33a93ab2a494949899ab921e9f3ad1e.png