数据结构（2.2）线性表之单链表的具体实现

迷南。 2024-04-18 12:57 59阅读 0赞

### 数据结构（2.1）线性表之单链表的具体实现 ###

*   *   *  前言
         *  链表的管理结构
         *  实现的操作
         *  注
         *   *  在进行头部插入与删除时last指针的指向问题
             *  按值删除的几种方法
             *  如何巧妙地进行逆置
             *  针对该链表的排序
         *  几点收获
         *  全部代码
         *   *  工程图
             *  SList.h文件存放单链表的定义和操作函数的声明
             *  SList.cpp文件存放单链表操作函数的具体实现
             *  Main文件用于做测试

### 前言 ###

本篇主要讲的是在增加了管理结构的基础上对单链表进行的插入删除、查找排序等操作(同顺序表的操作一样)。由于链式存储的特性，在进行某些操作时可以特别处理，在后文中会说明。

### 链表的管理结构 ###

一个链表由指向头结点的指针和指向最后一个结点的指针和链表的长度构成。这样，我们对链表进行操作时，还要考虑管理结构的变化。例如在尾部插入结点时，除了生成结点保存数据以外，还要修改last指针的指向以及链表的长度。

![img1][]  
链表的初始化和插入在上一篇中讲得很清楚了，即使增加了管理结构也是大同小异。时间有限，只在比较特殊的地方给出图解，其余部分在注释里说明。

### 实现的操作 ###

*  尾部插入
 *  头部插入
 *  展示单链表
 *  尾部删除
 *  头部删除
 *  按值插入(要求插入前的链表是有序的，代码中为顺序)
 *  按值查找
 *  获取链表长度
 *  按值删除
 *  排序
 *  逆置(即前后转换链表)
 *  清除单链表
 *  摧毁单链表

### 注 ###

#### 在进行头部插入与删除时last指针的指向问题 ####

在头部插入第一个结点时，由于last指针还指向头结点，因此在除了插入结点外还需要额外让last指针重新指向新的结点；同理，在头部删除最后一个结点时，last指针指向的结点空间已经被释放掉了，因此还要额外让last指针重新指向头结点。在这两种情况下如果不进行特殊处理，会造成last指针指向错误的问题，虽然插入、删除操作是正确的，但是从管理结构的角度来看仍是有错误的。

![img2][]

#### 按值删除的几种方法 ####

当我们进行按值删除操作时，首先用find(按值查找)的方法查找链表中是否有这个值，若有则会返回该结点的地址。但是我们删除时，需要释放该结点的内存空间，那么就要修改它前驱的next值，该怎么处理呢？

*  寻常的方法一：遍历整个链表，找到该结点的前驱进行修改即可

![img3][]

*  巧妙的方法二：不直接删除该结点，而是将该结点后继的数据域复制过来，删除后继结点，再修改该结点的next值为后继结点的next
    
    ![img4][]
    
    用这种方法仍需要考虑last指针的指向问题，当要删除的结点是倒数第二个时，如上图，s结点的内存空间被释放后，last指针指向的是一个无意义的地址，因此需要重新设置。而当要删除的结点是最后一个时，只要当做尾部删除，调用push\_back方法即可。
 *  另类的方法三：修改(或者另写一个)find方法，让它返回该结点前驱的地址，这样进行删除操作就很方便了

#### 如何巧妙地进行逆置 ####

对单链表进行逆置，如果想和顺序表中一样，开辟一块辅助空间来储存数据，再倒序存入原有顺序表中，这很明显是不可取的。因为在单链表中只能通过结点找到其后继，却不能返回去找前驱，所以没办法像顺序表一样通过下标直接访问到最后一位。当然，我们也可以用一个顺序表来储存链表中的数据，再倒序存入链表中，这无疑是很麻烦的。

万幸的是，由于链表的特性，可以有比较巧妙的方法来进行逆置：用一个指针指向首元结点的后继，从此处将链表断为两个部分，再从该指针开始取出后续结点，对链表进行头部插入即可。

![img5][]

![img6][]

![img7][]

#### 针对该链表的排序 ####

当我们需要给链表进行排序时，可以参考顺序表的方法，例如冒泡排序、选择排序等。虽然对这些方法略有了解，但是没有进行过具体的整理，也不太清楚在链表中这些方法的性能与线性表中是否有差别。但是针对我们写的这个单链表，其实可以用个比较巧妙的思路，就不需要自己写排序的算法了。

*  之前写的按值插入方法可以在链表本身有序(代码中为顺序)的前提下按值的大小进行插入，插入后的链表也是有序的。因此我们可以充分利用这个方法，类似上文逆置的思路，先将链表断开为两个部分，然后再从指针处不断取出后续结点，对结点进行按值插入即可。

### 几点收获 ###

1.  写代码时要有考虑边际条件的意识，减少低级逻辑错误
2.  多考虑特殊情况(怎样发生的、后果是什么、怎么处理)
3.  广泛打开思路，不要局限于原有的思维里，同时学会举一反三

### 全部代码 ###

#### 工程图 ####

![img8][]

#### SList.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 InitList(List *list);
    
    //1.尾部插入
    void push_back(List *list,ElemType x);
    //2.头部插入
    void push_fount(List *list,ElemType x);
    //3.展示单链表
    void show_list(List *list);
    //void show_list1(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);
    //Node* find1(List list,ElemType x);
    //8.获取长度
    int length(List *list);
    //int length1(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);

#### SList.cpp文件存放单链表操作函数的具体实现 ####

#include "SeqList.h"
    
    //初始化单链表
    void InitList(List *list){ 
        //创建头结点 链表的first和last都指向它
        list->first = list->last = (Node*)malloc(sizeof(Node));
        assert(list->first!=NULL);
        list->first->next = NULL;
        list->size = 0;
    }
    
    //1.尾部插入
    void push_back(List *list,ElemType x){ 
        
        //申请一个结点的空间并赋值
        Node *s= (Node *)malloc(sizeof(Node));
        assert(s != NULL);
        s->data = x;
        s->next = NULL;
        
        //原有的list->last->next指向这个结点
        list->last->next = s;
        //将这个结点设置为新的last
        list->last = s;
        list->size ++;
    }
    
    //2.头部插入
    void push_fount(List *list,ElemType x){ 
        //申请一个结点的空间并赋值
        Node *s= (Node *)malloc(sizeof(Node));
        assert(s != NULL);
        s->data = x;
        
        //这个结点的next值是原来的list->first->next
        s->next = list->first->next;
        //将这个结点设置为新的first->next
        list->first->next = s;
        
        //判断是否是第一个结点，如果是，需要修改last指针的指向
        if (list->size == 0) { 
            list->last = 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");
    }
    //void show_list1(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;
        }
        
        //遍历整个单链表，找到倒数第二个结点
        //将last指针指向它后再释放最后一个结点
        Node *p = list->first;
        while (p->next != list->last) { 
            p = p->next;
        }
        
        //释放最后一个结点
    // free(list->last);
    // //重新设置最后一个结点
    // list->last = p;
    // list->last->next = NULL;
        free(p->next);
        p->next = NULL;
        list->last = p;
        
        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);
        list->size --;
        
        //判断是否是最后一个结点，如果是，则需要修改last指针的指向
        if (list->size == 0) { 
            list->last = list->first;
        }
    }
    
    //6.按值插入(要求插入前的链表是有序的(顺序或倒序(此处为顺序
    void insert_val(List *list,ElemType x){ 
        //申请一个结点的空间并赋值
        Node *s= (Node *)malloc(sizeof(Node));
        assert(s != NULL);
        s->data = x;
        s->next = NULL;
        
        Node *p = list->first;
        
        //遍历整个链表，查找插入位置
        while (p->next != NULL) { 
            //判断是否比下个结点的数据小
            if (x < p->next->data) {         
                //是，在此处插入
                s->next = p->next;
                p->next = s;
                break;
            }else{ 
                p = p->next;
            }
        }
        if (p->next == NULL) { 
            //之前的数据都比要插入的数据小，将s结点放入最后一个
            p->next = s;
            list->last = s;
        }
        list->size ++;
    
        //鲍老师的写法更简洁
    // while (p->next!=NULL && p->next->data<x) { 
    // p = p->next;
    // }
    // if (p->next == NULL) { 
    // //插入最后一个
    // list->last = s;
    // }
    // s->next = p->next;
    // p->next = s;
    // list->size ++;
    //
    }
    //7.按值查找
    Node* find(List *list,ElemType x){ 
        Node *p = list->first->next;
        
        /* while(p->data != x && p != NULL) 不能这样写，因为当p为空的时候没有data值 */
        while (p != NULL && p->data != x) { 
            p = p->next;
        }
        return p;
    }
    //Node* find1(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;
    }
    //int length1(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");
        }
        
        //判断是否是最后一个结点
        if (p == list->last) { 
            //直接进行尾部删除
            pop_back(list);
        }else{ 
            
            if (p->next == list->last) { 
                //倒数第二个结点，仍然要修改last指针的值
                list->last = p;
            }
            Node *q = p->next;
            p->data = q->data;
            p->next = q->next;
            free(q);
            list->size --;
        }
    }
    
    //10.排序 1.交换数据 2.交换结点
    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;
    
            Node *p = list->first;
            while (p->next!=NULL && p->next->data<s->data) { 
                p = p->next;
            }
            if (p->next == NULL) { 
                //插入最后一个
                list->last = s;
            }
            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 = s;
        list->last->next = NULL;
        
        while (q != NULL) { 
            //取出后续结点
            s = q;
            q = s->next;
            
            //进行头部插入
            s->next = list->first->next;
            list->first->next = s;
        }
    }
    
    //12.清除单链表 ->只清除数据，保留头结点
    void clearList(List *list){ 
        if (list->size == 0) { 
            //printf("顺序表已经为空！\n");
            return;
        }
        
    // Node *p = list->first->next;
    // Node *q;
    // while (p != NULL) { 
    // q = p;
    // p = p->next;
    // printf("delete:%d\n",q->data);
    // free(q);
    // list->size --;
    // }
    // list->first->next = NULL;
    // list->last = list->first;
        
        Node *p = list->first->next;
        while (p != NULL) { 
            list->first->next = p->next;
            free(p);
            p = list->first->next;
            
            list->size --;
        }
        
        list->last = list->first;
    }
    //13.摧毁 ->包括头结点在内一起摧毁
    void destroy(List *list){ 
        //清除链表
        clearList(list);
        free(list->first);
        list->first = list->last = NULL;
    }

#### Main文件用于做测试 ####

#include "SList.h"
    
    int main(int argc, const char * argv[]) { 
        List myList;
        InitList(&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_list1(myList);
                    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);
                    //p = find1(myList, item);
                    if (p == NULL) { 
                        printf("要查找的数据不存在!\n");
                    }else{ 
                        printf("地址为:%p\n",p);
                    }
                    break;
                case 8:
                    //展示链表长度
                    printf("链表的长度为:%d\n",length(&myList));
                    //printf("链表的长度为:%d\n",length1(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;
    }

[img1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/b49c87d37c174ae29ffe97f7b6b24da4.png
[img2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/938f34e6585d45bf9b041488a0cfa8a1.png
[img3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/dad1f7f994814cc0aff81643e3b0928b.png
[img4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/a79cc7760faf4cb4a0d97ed92ba229d0.png
[img5]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/6c7a31c58690467083384f0685b16b42.png
[img6]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/e2b192f2a6a74468aa33409cf6aac13d.png
[img7]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/fd8ae135927247a09e5f2105f2047030.png
[img8]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/241e19a45fc5474eb1316abce5124f91.png