数据结构（5）线性表之双向链表

╰+哭是因爲堅強的太久メ 2023-06-04 06:55 148阅读 0赞

### 数据结构（5）线性表之双向链表 ###

*   *   *  前言
         *  增加双向链表的管理结构
         *  双向链表的插入
         *   *  尾部插入
             *  头部与按值插入
         *  双向链表的删除
         *  排序与逆置
         *  全部代码
         *   *  DList.h
             *  DList.cpp
             *  Main.cpp

### 前言 ###

在先前讨论的链式存储结构中，无论是单链表还是单循环链表，都只有一个指向后继的指针，因此可以很容易找到它的后继，但是要找它的前驱却很麻烦。那么可不可以再增加一个指向前驱的指针，这样在遍历链表时不仅能从前往后遍历，也能从后往前遍历呢？这就是我们今天所说的双向链表。

顾名思义，双向链表就是其结点中有两个指针域，一个指向直接前驱，一个指向直接后继。当然，链表的第一个结点无直接前驱，最后一个结点无直接后继，设置为空即可。

![img\_1][img_1]

实现双向链表的相关操作，思路上同单链表是一致的，唯一的区别是还需要考虑Prior指针的指向问题。

### 增加双向链表的管理结构 ###

我们同样为双向链表设置管理结构，first指针指向头结点，last指针指向最后一个结点，size保存链表结点的数量。同单链表一样，在增加了管理结构之后，在做插入、删除操作时，除了保证链表本身的正确性，还要考虑到管理结构的正确性，也就是注意first和last指针指向的正确，和size的数量正确。

![img\_2][img_2]

### 双向链表的插入 ###

与单链表不同的是，双向链表的改动除了涉及Next指针外，还涉及Prior指针，因此每当我们要执行插入操作时，一般要考虑四个指针的指向

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

![img\_3][img_3]

只要想好了这四个指针的指向问题，双向链表的操作也就没什么难点了

#### 尾部插入 ####

尾部插入只涉及两个结点，因此只需要考虑两个指针，以及管理结构的last指针即可

![img\_4][img_4]

#### 头部与按值插入 ####

头部插入是直接插在头结点后的位置，按值插入是找到插入位置后直接进行插入(如果是最后一位直接进行尾部插入)，两种方式都需要考虑四个指针的指向

同时，在设置四个指针指向的时候要注意先后的顺序，避免出现指针丢失的问题

![img\_5][img_5]

### 双向链表的删除 ###

双向链表的删除比单链表的删除方便，因为可以找到直接前驱，所以也不需要使用修改值的方法了，直接修改直接前驱和直接后继的指针就好了。尾部、头部和按值删除的方法都类似，只是涉及到的指针有区别，不详谈了。

![img\_6][img_6]

### 排序与逆置 ###

与单链表的思路一样，在进行双向链表的排序时，可以借鉴按值插入的思路，将原有的双向链表断开，再遍历一个个取出结点，进行按值插入。而在进行逆置时，则进行头部插入即可。

在这里我是利用了已经写好的方法，直接调用方法进行按值插入，再将原来的结点释放掉。

while (q != NULL) { 
            //取出后续结点
            s = q;
            q = q->next;
            //进行按值插入
            insert_val(list, s->data);
            //释放原来的结点
            free(s);
            list->size --;
        }

也可以不调用方法，通过设置指针的方式将结点重新连接到链表中

while (q != NULL) { 
            //取出后续结点
            s = q;
            q = q->next;
        
            Node *p = list->first;
              //寻找插入位置
              while (p->next != NULL && p->next->data<s->data) { 
                  p = p->next;
              }
              
              //判断是否是最后一个
              if (p->next == NULL) { 
                  //是，进行尾部插入
                  s->next = NULL;
                  s->prior = list->last;
                  list->last->next = s;
                  list->last = s;
              }else{       
                  //s的后继指向p的后继
                  s->next = p->next;
                  //s的前驱指向p
                  s->prior = p;
                  //p后继的前驱指向s
                  p->next->prior = s;
                  //p的后继指向s
                  p->next = s;
              }

逆置同理

### 全部代码 ###

#### DList.h ####

#ifndef DList_h
    #define DList_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 InitDList(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 /* DList_h */

#### DList.cpp ####

#include "DList.h"
    
    //初始化
    void InitDList(List *list){ 
        Node *s = (Node *)malloc(sizeof(Node));
        assert(s != NULL);
        
        list->first = list->last = s;
        list->first->next = NULL;
        list->first->prior = NULL;
        list->size = 0;
    }
    
    //1.尾部插入
    void push_back(List *list,ElemType x){ 
        //获得一个结点
        Node *s = getNode(x);
        
        //s的前驱指向最后一个结点
        s->prior = list->last;
        //最后一个结点的后继指向s
        list->last->next = s;
        //重新设置last指针的指向
        list->last = s;
        
        list->size ++;
    }
    
    //2.头部插入
    void push_fount(List *list,ElemType x){ 
        Node *s = getNode(x);
        //判断是否是第一个结点
        if (list->first == list->last) { 
            //是第一个结点，s的后继不需要设置
            //s的前驱指向头结点
            //s->prior = list->first;
            //重新设置first指针的指向，使s成为新的首元结点
            //list->first->next = s;
            
            //重新设置last指针的指向
            list->last = s;
        }else{ 
            //s的后继指向首元结点
            s->next = list->first->next;
            //s的前驱指向头结点
            //s->prior = list->first;
            
            //首元结点的前驱指向s
            //s->next->prior = s;
            list->first->next->prior = s;
            //重新设置first指针的指向，使s成为新的首元结点
            list->first->next = s;
            
        }
        //if-else语句中有重复的部分，可以提出来
        //s的前驱指向头结点
        s->prior = list->first;
        //重新设置first指针的指向，使s成为新的首元结点
        list->first->next = s;
        
        list->size ++;
    }
    
    //3.展示
    void show_list(List *list){ 
        Node *p = list->first->next;
        
        while (p != NULL) { 
            printf("%4d",p->data);
            p = p->next;
        }
        printf("\n");
    }
    //4.尾部删除
    void pop_back(List *list){ 
        if (list->size == 0) { 
            printf("链表已空！\n");
            return;
        }
        
        //方法1
        Node *p = list->first;
        //循环到链表的最后一位
        while (p->next != NULL) { 
            p = p->next;
        }
    
        //将last指针指向倒数第二位(即p的前一位
        list->last = p->prior;
        //释放该结点的空间
        free(p);
        //此时链表最后一位的后继为空
        list->last->next = NULL;
        
        list->size --;
        
        /* //方法2 Node *p = list->first; //循环到链表倒数第二位 while (p->next != list->last) { p = p->next; } //释放最后一个结点的空间 free(p->next); p->next = NULL; //重新设置last指针的指向 list->last = p; list->size --; */
    }
    
    //5.头部删除
    void pop_fount(List *list){ 
        if (list->size == 0) { 
            printf("链表已空!\n");
            return;
        }
        
        Node *s = list->first->next;
        
        //判断是否是最后一个结点
        if (s->next == NULL) { 
            //是，则s没有后继,不需要修改后继的指针
            //修改last指针的指向
            list->last = list->first;
            list->last->next = NULL;
        }else{ 
            
            //s的后继的prior指针指向头结点
            s->next->prior = list->first;
            //头结点的next指针指向s的后继
            list->first->next = s->next;
        }
    
        //释放该结点
        free(s);
        list->size --;
    }
    
    //6.按值插入(要求插入前的链表是有序的(此处为顺序
    void insert_val(List *list,ElemType x){ 
        Node *p = list->first;
        //寻找插入位置
        while (p->next != NULL && p->next->data<x) { 
            p = p->next;
        }
        
        //判断是否是最后一个
        if (p->next == NULL) { 
            //是，直接进行尾部插入
            push_back(list, x);
        }else{ 
            Node *s = getNode(x);
            
            //s的后继指向p的后继
            s->next = p->next;
            //s的前驱指向p
            s->prior = p;
            //p后继的前驱指向s
            p->next->prior = s;
            //p的后继指向s
            p->next = s;
            
            list->size ++;
        }
    }
    
    //7.按值查找
    Node* find(List *list,ElemType x){ 
        Node *p = list->first->next;
        while (p != NULL && p->data != x) { 
            p = p->next;
        }
        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{ 
            //p后继的前驱指向p的前驱
            p->next->prior = p->prior;
            //p前驱的后继指向p的后继
            p->prior->next = p->next;
            //释放结点空间
            free(p);
            list->size --;
        }
    }
    
    //10.排序
    void sort(List *list){ 
        if (list->size <= 1) { 
            //不需要排序
            return;
        }
        
        Node *s = list->first->next;
        Node *q = s->next;
        //将链表断开
        list->last = s;
        list->last->next = NULL;
        
        while (q != NULL) { 
            //取出后续结点
            s = q;
            q = q->next;
            //进行按值插入
            insert_val(list, s->data);
            //释放原来的结点
            free(s);
            list->size --;
            
    // Node *p = list->first;
    // //寻找插入位置
    // while (p->next != NULL && p->next->data<s->data) { 
    // p = p->next;
    // }
    //
    // //判断是否是最后一个
    // if (p->next == NULL) { 
    // //是，直接进行尾部插入
    // s->next = NULL;
    // s->prior = list->last;
    // list->last->next = s;
    // list->last = s;
    // }else{ 
    //
    // //s的后继指向p的后继
    // s->next = p->next;
    // //s的前驱指向p
    // s->prior = p;
    // //p后继的前驱指向s
    // p->next->prior = s;
    // //p的后继指向s
    // p->next = s;
    // }
            
        }
    }
    
    //11.逆置(前后转换
    void resver(List *list){ 
        if (list->size <= 1) { 
            //不需要逆置
            return;
        }
        
        Node *s = list->first->next;
        Node *q = s->next;
        
        //将链表断开
        list->last = s;
        list->last->next = NULL;
        
        while (q != NULL) { 
            s = q;
            q = q->next;
            //直接进行头部插入
            push_fount(list, s->data);
            //释放原有结点
            free(s);
            list->size --;
        }
    }
    //12.清除单链表 ->只清除数据，保留头结点
    void clearList(List *list){ 
        if (list->size == 0) { 
            printf("链表已空！\n");
            return;
        }
        
        Node *s = list->first;
        Node *p = s->next;
        //遍历整个链表
        while (p != NULL) { 
            s = p;
            p = p->next;
            //释放结点
            free(s);
            list->size --;
        }
    
        list->last = list->first;
        list->last->next = NULL;
    }
    //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 = NULL;
        s->next = NULL;
        
        return s;
    }

#### Main.cpp ####

#include "DList.h"
    
    int main(int argc, const char * argv[]) { 
    
        List myList;
        InitDList(&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/20230601/be97daad0b464f2fa5791e310f4eab64.png
[img_2]: /images/20230601/f21ae3d71f5c43b1812f5ef84a8fa574.png
[img_3]: /images/20230601/94034b9fbab7453e9ca86e72f1d21e3a.png
[img_4]: /images/20230601/7a2a6d0877d34cf5a4d0000bb549d492.png
[img_5]: /images/20230601/0f7038e5177b4235abb36d04065e7e24.png
[img_6]: /images/20230601/b5cbcb31497043d1ba07b97def47f4bd.png