【数据结构与算法】链表

文章目录

链表的引入

对于顺序表存在一些缺陷：

• 中间/头部的插入删除，时间复杂度为O(N) 。头部插入需要挪动后面的元素
• 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
• 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间

对于链表而言，能够避免上述问题的出现。头部插入数据不需要挪动大量的数据，按需申请释放空间，不会造成空间的浪费。

链表的概念及结构

概念:链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

现实中 数据结构中（箭头实际上并不存在，这里只是形象化）:

链表的种类有很多

以下情况组合起来就有8种链表结构：

单向或者双向 ：

带头或者不带头：

循环或者非循环：

面对这么多种类的链表，我们该如何选择？虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了

话不多说，直接进入我们单链表的实现：

单链表的接口我们需要实现：

• 打印销毁
• 头插尾插创建新结点(由于后面会频繁使用，故将其封装成函数)
• 尾删头删查找
• 在pos之前插入、在pos之后插入
• 删除pos、删除pos之后的位置

我们还是老样子，通过三个部分组成：

**SList.h:**包括头文件的引用，结构体的声明定义，接口函数的声明。

**SList.c:**对SList.h中接口函数进行实现。

**test.c:**主函数进行测试：通过void TestSList()函数对SList.c的函数进行调用，测试有没有错误。

注意：对于一些问题的所在，我已经通过注释进行相关说明。注释才是精髓。

SList.h

#define_CRT_SECURE_NO_WARNINGS#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefint SLTDataType;typedefstructSListNode{
    SLTDataType data;structSLTNode* next;}SLTNode;//打印voidSListPrint(SLTNode* phead);//创建新结点
SLTNode*BuySLTNode(SLTDataType x);//销毁voidSListDestory(SLTNode** pphead);//头插voidSListPushFront(SLTNode** pphead, SLTDataType x);//尾插voidSListPushBack(SLTNode** pphead, SLTDataType x);//尾删voidSListPopBack(SLTNode**pphead);//头删voidSListPopFront(SLTNode**pphead);//查找
SLTNode*SListFind(SLTNode* pphead,SLTDataType x);//在pos之前插入voidSListInsert(SLTNode** pphead,SLTNode*pos,SLTDataType x);//在pos之后插入voidSListInsertAfter(SLTNode* pos, SLTDataType x);//删除posvoidSListErase(SLTNode** pphead,SLTNode*pos);//删除pos后面位置,了解voidSListEraseAfter(SLTNode* pos);

SList.c

#define_CRT_SECURE_NO_WARNINGS#include"SList.h"//打印voidSListPrint(SLTNode* phead){//phead不需要断言。因为phead有可能有空，没有数据//而顺序表的结构体不可能为空，所以要进行断言
    SLTNode* cur = phead;while(cur !=NULL){printf("%d->", cur->data);
        cur = cur->next;}printf("NULL\n");}//创建新结点
SLTNode*BuySLTNode(SLTDataType x){
    SLTNode* newnode =(SLTNode*)malloc(sizeof(SLTNode));if(newnode ==NULL){perror("mail fail");exit(-1);}
    newnode->data = x;
    newnode->next =NULL;return newnode;}//销毁voidSListDestory(SLTNode** pphead){assert(pphead);
    SLTNode* cur =*pphead;while(cur){
        SLTNode* next = cur->next;free(cur);
        cur = next;}*pphead =NULL;}//头插voidSListPushFront(SLTNode** pphead, SLTDataType x){assert(pphead);
    SLTNode* newnode =BuySLTNode(x);
    newnode->next =*pphead;*pphead = newnode;}//尾插——有无结点。需要找前一个voidSListPushBack(SLTNode** pphead, SLTDataType x){assert(pphead);
    SLTNode* newnode =BuySLTNode(x);//空,改变的是SListNode*,需要二级指针//非空。尾插要改变的是结构体SListNode，只需要结构体的指针if(*pphead ==NULL){*pphead = newnode;}else{//找尾
        SLTNode* tail =*pphead;while(tail->next !=NULL){
            tail = tail->next;}
        tail->next = newnode;}}//尾删——有无结点。需要找前一个voidSListPopBack(SLTNode** pphead){assert(pphead);
    SLTNode* tail =*pphead;
    SLTNode* prev =NULL;assert(*pphead !=NULL);if((*pphead)->next ==NULL){free(*pphead);*pphead =NULL;}else{while(tail->next !=NULL){
            prev = tail;
            tail = tail->next;}
        prev->next =NULL;free(tail);
        tail =NULL;/*while (tail->next->next!=NULL)
        {
            tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;*/}}//头删voidSListPopFront(SLTNode** pphead){assert(pphead);assert(*pphead);/*if (*pphead == NULL)
    {
        return;
    }*/
    SLTNode* del =*pphead;*pphead =(*pphead)->next;free(del);
    del =NULL;}//查找
SLTNode*SListFind(SLTNode* pphead, SLTDataType x){assert(pphead);
    SLTNode* cur = pphead;while(cur){if(cur->data == x){return cur;}
        cur = cur->next;}returnNULL;}//在pos之前插入，需要找前一个voidSListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){assert(pphead);assert(pos);if(pos ==*pphead){SListPushFront(pphead, x);}else{
        SLTNode* newnode =BuySLTNode(x);
        SLTNode* prev =*pphead;while(prev->next != pos){
            prev = prev->next;assert(prev);}
        prev->next = newnode;
        newnode->next = pos;}}//在pos后插入voidSListInsertAfter(SLTNode* pos, SLTDataType x){assert(pos);
    SLTNode* newnode =BuySLTNode(x);
    newnode->next = pos->next;
    pos->next = newnode;}//删除pos位置，需要找前一个voidSListErase(SLTNode** pphead, SLTNode* pos){assert(pphead);assert(pos);if(pos ==*pphead){SListPopFront(pphead);}else{
        SLTNode* prev =*pphead;while(prev->next != pos){
            prev = prev->next;//检查pos不是链表中的结点assert(prev);}
        prev->next = pos->next;free(pos);}}//删除pos后面位置voidSListEraseAfter(SLTNode* pos){assert(pos);if(pos->next ==NULL){return;}else{
        SLTNode* next = pos->next;
        pos->next = next->next;free(next);}}

test.c

#define_CRT_SECURE_NO_WARNINGS#include"SList.h"//头插、头删voidTestSList1(){
    SLTNode* plist =NULL;SListPushFront(&plist,1);SListPushFront(&plist,2);SListPushFront(&plist,3);SListPushFront(&plist,4);SListPrint(plist);SListPopFront(&plist);SListPrint(plist);SListPopFront(&plist);SListPrint(plist);SListPopFront(&plist);SListPrint(plist);SListPopFront(&plist);SListPrint(plist);SListPopFront(&plist);SListPrint(plist);SListDestory(&plist);}//尾插、尾删voidTestSList2(){
    SLTNode* plist =NULL;SListPushBack(&plist,1);SListPushBack(&plist,2);SListPushBack(&plist,3);SListPushBack(&plist,4);SListPrint(plist);SListPopBack(&plist);SListPopBack(&plist);SListPopBack(&plist);SListPopBack(&plist);SListPopBack(&plist);SListDestory(&plist);}//查找、在pos之前插入voidTestSList3(){
    SLTNode* plist =NULL;SListPushBack(&plist,1);SListPushBack(&plist,2);SListPushBack(&plist,3);SListPushBack(&plist,4);SListPrint(plist);

    SLTNode* pos =SListFind(plist,3);if(pos){//修改
        pos->data *=10;printf("找到了\n");}else{printf("找不到\n");}

    pos =SListFind(plist,1);if(pos){SListInsert(&plist, pos,10);}SListPrint(plist);SListDestory(&plist);}//删除pos位置、删除pos后面的位置voidTestSList4(){

    SLTNode* plist =NULL;SListPushBack(&plist,1);SListPushBack(&plist,2);SListPushBack(&plist,3);SListPushBack(&plist,4);SListPrint(plist);

    SLTNode* pos =SListFind(plist,3);if(pos){SListErase(&plist, pos);}SListPrint(plist);

    pos =SListFind(plist,1);if(pos){SListErase(&plist, pos);}SListPrint(plist);}intmain(){//TestSList1();//TestSList2();//TestSList3();TestSList4();return0;}

以上就是单链表的相关操作，我们不难发现，单链表的优势在于头插头删

而对于一些操作：如尾插尾删而言，我们都需要去找前一个位置，这是比较麻烦的。单链表我们就先介绍到这里了。

这里同时也有一个问题存在：

删除当前位置我们需要去找前一个位置，这效率是比较低的，我们如何改进这个问题❓

找pos位置删除，而就是不找前一个位置（即要求是O（1））：替换法删除，把pos的值和下一个节点的值进行交换，再把pos进行释放掉。但是有一个缺陷：pos不能是尾节点。尾节点没有下一项。

那如果在pos位置之前插入，要求为O（1）呢：

直接插入到pos后面，然后进行交换。

总结

• 我们从链表的引入开始，了解了为什么链表会出现，同时认识了链表的概念和结构。本篇博客主要介绍了单链表的操作，以及解决了一个问题。本次就先到这里结束了。