数据结构—单链表

  • 开发
  • 32

1、链表的概念及结构

1.1链表的概念

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

1.2链表的结构

如下图：

逻辑上的链表，pList是指向头个元素的指针 

物理上的链表

有人可能会有疑问，不是说链表只是在逻辑结构上是连续的，在物理存储结构上是不连续的，那为什么上图中一个个结点明明是挨在一起的，那么它在物理存储结构上肯定是连续的呀，其实不然，上图是为了方便大家理解，才用线条连接了结点，实际上在内存中，每个结点可能会隔得很远，仔细观察每个结点上面的红色文字，那就是这个结点的地址，而蓝色文字是下一个结点的地址，很明显能看到这两个结点并不是相邻的，因此也验证了顺序表在逻辑结构上确实是连续的，但在物理存储结构上确实是不连续的。

2、链表的实现

2.1 定义结点

介绍一下单链表的英文名——single linked list，我们简写成SL（区别于顺序表的SeqList或者SQL）。

注意：next指针的类型是SListNode*，千万不要写成SLTDataType*，因为next指针是结构体指针，是用来指向下一个结点的

typedef int SLTDataType;
typedef struct SListNode
{
    SLTDataType data;
    struct SListNode* next;
}SLTNode;

2.2链表的功能

链表要实现那些功能呢？其实这些功能我们都很熟悉，数据结构无非是对数据进行管理，要实现数据的增删查改，因此链表的基本功能也都是围绕着数据的增删查改展开。

注意：链表是不需要初始化的

//打印单链表
void SLTPrint(SLTNode* phead);
//创建一个结点
SLTNode* BuyLTNode(SLTDataType x);
//销毁单链表
void SLTDestroy(SLTNode** pphead);
//头插
void SLPushFront(SLTNode** pphead, SLTDataType x);
//尾插
void SLPushBack(SLTNode** pphead, SLTDataType x);
//头删
void SLPopFront(SLTNode** pphead);
//尾删
void SLPopBack(SLTNode** pphead);
// 单链表查找
SLTNode* STFind(SLTNode* phead, SLTDataType x);

// 在pos之前插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos之后插入
void SLInsertAfter(SLTNode* pos, SLTDataType x);

// 删除pos位置的值
void SLErase(SLTNode** pphead, SLTNode* pos);

// 删除pos位置后面的值
void SLEraseAfter(SLTNode* pos);


// 单链表结点修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDataType x);

2.3链表功能实现

2.3.1打印单链表

注意：链表和顺序不同的是，顺序表传过来的指针是肯定不会为空的，而链表传过来的指针是可能为空的，比如说当链表中没有元素时，头指针所指向的就是NULL，如果在第一行写上断言就会有问题。

当cur指向空的时候就可以停止打印了。

void SLTPrint(SLTNode* phead)
{
    SLTNode* cur=phead;
    while(cur!=NULL)
    {
        printf("%d->",cur->data);
        cur=cur->next;
    }
    printf("NULL\n");

}

2.3.2 创建一个新结点

后面我们要在单链表中进行头插和尾插，此时插入的不再是像顺序表一样简单的SLDataType数据了，而是一个结点，这个结点是包括SLTDataType数据以及SLTDataType*的指针，因此，为了方便和减少代码的重复度，我们另写一个函数用来专门创建新结点。

SLTNode* BuyLTNode(SLTDataType x)
{
    SLTNode * newnode=(SLTNode*)malloc(sizeof(SLTNode));
    if(newnode==NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    newnode->data=x;
    newnode->next=NULL;//初始化

    return newnode;
}

2.3.3 单链表尾插

注意：在创建结点时，已经让 结点.next=NULL，所以不需要在插入完结点后，再让新结点的next指针为NULL。

有人可能会有疑问，为什么之前打印链表的时候不用断言指针，而在尾插时就要断言指针，以及为什么函数的形参是二级指针，而不使用一级指针。

因为，尾插分为两种情况（下面有写），当链表为空时，头指针phead指向NULL，尾插相当于头插，此时要改变phead的指向，让phead指向这个新结点，此时就需要二级指针来改变一级指针的值（如果我们用一级指针做形参，形参的改变不会影响实参，那么一级指针phead就不会被改变）。

至于这个什么时候要断言指针，什么时候不用断言指针：一级指针也就是phead，当链表为空的时候，phead就是为NULL，而二级指针永远指向phead，phead的地址是永远存在的，那么pphead就一定不可能为空，所以需要断言pphead。

//尾插
//第一个尾插需要二级指针，接下来就不用二级指针
//第一次是改变结构的指针plist
//第二次是改变结构体尾结点
void SLPushBack(SLTNode** pphead, SLTDataType x)
{
    SLTNode *newnode= BuyLTNode(x);
    //是否为空链表
    if(*pphead==NULL)
        *pphead=newnode;//改变结构的指针plist
    else
    {
        SLTNode *tail=*pphead;
        while(tail->next!=NULL)//找到链表最后一位，当tail->为空时，就把新开辟的链表节点接上去
            tail=tail->next;
        tail->next=newnode;//改变结构体尾结点
        //就是把newnode存放的新结点地址给tail->next，然后在存放在之前最后一个结点的struct SListNode* next;中，这样next指向的地址不是NULL，而是新加的结点的位置
        //不能用tail=newnode,因为tail和newnode是局部变量，当这函数结束后就释放了
    }
}

2.2.4 单链表尾删

要想删除链表中的元素，就必须保证原链表就有元素，因此要断言assert(*pphead)。

尾删需要分情况去讨论

//尾删
void SLPopBack(SLTNode** pphead)
{
    //当没有结点（空链表）

    //暴力检查
    assert(*pphead);

    //温柔检查
//    if(*pphead==NULL)
//        return;
    //当只有一个结点时
    if((*pphead)->next==NULL)
    {
        free(*pphead);
        *pphead=NULL;
    }
    else
    {
        SLTNode *prev = NULL;//用来指向倒数第二个结点
        SLTNode *tail = *pphead;//用来释放最后一个指针空间
        //找尾
        while (tail->next) {
            prev = tail;
            tail = tail->next;
        }

        free(tail);//把最后一个指针空间释放掉
        prev->next = NULL;//把最后一个的前一个结点指针设为空
        //如果直接tail=NULL的话，倒数第二个结点就指向一个NULL，就成为了一个野指针

        //while(tail->next->next)//找到倒数第二个
        //    tail=tail->next;
        //free(tail->next);//把倒数第二个结点指向的结构体释放掉
        //tail->next=NULL;//把倒数第二个结点置为空
    }
}

2.2.5  单链表头删

头删没什么好说的，记住要断言*pphead，保证链表内容不为空。

//头删
void SLPopFront(SLTNode** pphead)
{
    //空链表
    assert(*pphead);

//    //一个结点
//    if((*pphead)->next==NULL)
//    {
//        free(*pphead);
//        *pphead=NULL;
//    }
//    //多个结点
//    else
//    {
//        SLTNode *del=*pphead;
//        //*pphead=del->nest;
//        *pphead=(*pphead)->next;
//        free(del);
//    }

    SLTNode* del = *pphead;
    *pphead = (*pphead)->next;
    free(del);

}

 2.2.6 单链表头插

现在是不是觉得头插很简单了啊！

//头插
void SLPushFront(SLTNode** pphead, SLTDataType x)
{
    SLTNode *newnode= BuyLTNode(x);

    newnode->next= *pphead;
    *pphead=newnode;//都需要二级指针
}

2.2.7 查找某个结点

这个函数返回值不再是void，而是SLTNode*，把找到的结点的地址返回去，这个函数一般会跟结点修改之类的函数一起使用。

SLTNode* STFind(SLTNode* phead, SLTDataType x)
{
    SLTNode *cur=phead;
    while (cur)
    {
        if(cur->data==x)
        {
            return cur;
        }

        cur=cur->next;
    }

    return NULL;
}

2.2.8 删除某个节点

// 删除pos位置的值
void SLErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead);
    assert(pos);

    //如果只有一个结点
    if(pos==*pphead)
        SLPopFront(pphead);
    else
    {
        SLTNode *p1=*pphead;
        while(p1->next!=pos)
            p1=p1->next;
        p1->next=pos->next;
        free(pos);
    }
}

注意：

  1. pos也要断言，pos可不能为空呀！
  2. cur->next也要断言，因为当cur->next为NULL时，说明整个链表的结点都排查完了，最后还是没有找到地址为pos的结点，证明pos传值有误。

 2.2.9单链表结点修改

// 单链表结点修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDataType x)
{
    SLTNode* cur=phead;
    while(cur!=pos)
    {
        cur=cur->next;
        assert(cur);
    }
    pos->data=x;
}

2.2.10 单链表在pos位前插入结点

// 在pos之前插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    assert(pphead);
    assert(pos);

    //如果只有一个结点
    if(*pphead==pos)
        SLPushFront(pphead,x);
    else
    {
        SLTNode *p1=*pphead;
        while(p1->next!=pos)
        {
            p1=p1->next;
        }

        SLTNode *newnode= BuyLTNode(x);
        p1->next=newnode;
        newnode->next=pos;
    }
}

2.2.11单链表在pos位后插入结点

//在pos之后插入
void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
    assert(pos);

    SLTNode *newnode= BuyLTNode(x);
    newnode->next=pos->next;
    pos->next=newnode;
}

2.2.12销毁链表

销毁链表这一块，咱可不敢直接free(phead)，因为链表在物理结构上是不连续存储的，销毁链表必须要一个结点一个结点去销毁！！！！最后不要忘记把phead置为NULL。

//单链表销毁
void SListDesTroy(SLTNode** pphead)
{
    assert(pphead && *pphead );

    SLTNode *pcur=*pphead;
    while(pcur)
    {
        SLTNode *next=pcur->next;
        free(pcur);
        pcur=next;
    }
    *pphead=NULL;

}

3、总代码

3.1 SList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLTDataType;
typedef struct SListNode
{
    SLTDataType data;
    struct SListNode* next;
}SLTNode;

void SLTPrint(SLTNode* phead);
//头插
void SLPushFront(SLTNode** pphead, SLTDataType x);
//尾插
void SLPushBack(SLTNode** pphead, SLTDataType x);
//头删
void SLPopFront(SLTNode** pphead);
//尾删
void SLPopBack(SLTNode** pphead);
// 单链表查找
SLTNode* STFind(SLTNode* phead, SLTDataType x);

// 在pos之前插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos之后插入
void SLInsertAfter(SLTNode* pos, SLTDataType x);

// 删除pos位置的值
void SLErase(SLTNode** pphead, SLTNode* pos);

// 删除pos位置后面的值
void SLEraseAfter(SLTNode* pos);

//单链表销毁
void SListDesTroy(SLTNode** pphead);


// 单链表结点修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDataType x);

3.2 SList.c

#include "SList.h"

void SLTPrint(SLTNode* phead)
{
    SLTNode* cur=phead;
    while(cur!=NULL)
    {
        printf("%d->",cur->data);
        cur=cur->next;
    }
    printf("NULL\n");

}

//创建一个新的动态内存
SLTNode* BuyLTNode(SLTDataType x)
{
    SLTNode * newnode=(SLTNode*)malloc(sizeof(SLTNode));
    if(newnode==NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    newnode->data=x;
    newnode->next=NULL;//初始化

    return newnode;
}

//头插
void SLPushFront(SLTNode** pphead, SLTDataType x)
{
    SLTNode *newnode= BuyLTNode(x);

    newnode->next= *pphead;
    *pphead=newnode;//都需要二级指针
}


//尾插
//第一个尾插需要二级指针，接下来就不用二级指针
//第一次是改变结构的指针plist
//第二次是改变结构体尾结点
void SLPushBack(SLTNode** pphead, SLTDataType x)
{
    SLTNode *newnode= BuyLTNode(x);
    //是否为空链表
    if(*pphead==NULL)
        *pphead=newnode;//改变结构的指针plist
    else
    {
        SLTNode *tail=*pphead;
        while(tail->next!=NULL)//找到链表最后一位，当tail->为空时，就把新开辟的链表节点接上去
            tail=tail->next;
        tail->next=newnode;//改变结构体尾结点
        //就是把newnode存放的新结点地址给tail->next，然后在存放在之前最后一个结点的struct SListNode* next;中，这样next指向的地址不是NULL，而是新加的结点的位置
        //不能用tail=newnode,因为tail和newnode是局部变量，当这函数结束后就释放了
    }
}

//头删
void SLPopFront(SLTNode** pphead)
{
    //空链表
    assert(*pphead);

//    //一个结点
//    if((*pphead)->next==NULL)
//    {
//        free(*pphead);
//        *pphead=NULL;
//    }
//    //多个结点
//    else
//    {
//        SLTNode *del=*pphead;
//        //*pphead=del->nest;
//        *pphead=(*pphead)->next;
//        free(del);
//    }

    SLTNode* del = *pphead;
    *pphead = (*pphead)->next;
    free(del);

}

//尾删
void SLPopBack(SLTNode** pphead)
{
    //当没有结点（空链表）

    //暴力检查
    assert(*pphead);

    //温柔检查
//    if(*pphead==NULL)
//        return;
    //当只有一个结点时
    if((*pphead)->next==NULL)
    {
        free(*pphead);
        *pphead=NULL;
    }
    else
    {
        SLTNode *prev = NULL;//用来指向倒数第二个结点
        SLTNode *tail = *pphead;//用来释放最后一个指针空间
        //找尾
        while (tail->next) {
            prev = tail;
            tail = tail->next;
        }

        free(tail);//把最后一个指针空间释放掉
        prev->next = NULL;//把最后一个的前一个结点指针设为空
        //如果直接tail=NULL的话，倒数第二个结点就指向一个NULL，就成为了一个野指针

        //while(tail->next->next)//找到倒数第二个
        //    tail=tail->next;
        //free(tail->next);//把倒数第二个结点指向的结构体释放掉
        //tail->next=NULL;//把倒数第二个结点置为空
    }
}

// 单链表查找
SLTNode* STFind(SLTNode* phead, SLTDataType x)
{
    SLTNode *cur=phead;
    while (cur)
    {
        if(cur->data==x)
        {
            return cur;
        }

        cur=cur->next;
    }

    return NULL;
}

// 在pos之前插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    assert(pphead);
    assert(pos);

    //如果只有一个结点
    if(*pphead==pos)
        SLPushFront(pphead,x);
    else
    {
        SLTNode *p1=*pphead;
        while(p1->next!=pos)
        {
            p1=p1->next;
        }

        SLTNode *newnode= BuyLTNode(x);
        p1->next=newnode;
        newnode->next=pos;
    }
}

//在pos之后插入
void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
    assert(pos);

    SLTNode *newnode= BuyLTNode(x);
    newnode->next=pos->next;
    pos->next=newnode;
}

// 删除pos位置的值
void SLErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead);
    assert(pos);

    //如果只有一个结点
    if(pos==*pphead)
        SLPopFront(pphead);
    else
    {
        SLTNode *p1=*pphead;
        while(p1->next!=pos)
            p1=p1->next;
        p1->next=pos->next;
        free(pos);
    }
}

// 删除pos位置后面的值
void SLEraseAfter(SLTNode* pos)
{
    assert(pos);
    assert(pos->next);

    SLTNode *newnode=pos->next;
    pos->next=newnode->next;
    free(newnode);
}

//单链表销毁
void SListDesTroy(SLTNode** pphead)
{
    assert(pphead && *pphead );

    SLTNode *pcur=*pphead;
    while(pcur)
    {
        SLTNode *next=pcur->next;
        free(pcur);
        pcur=next;
    }
    *pphead=NULL;

}
// 单链表结点修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDataType x)
{
    SLTNode* cur=phead;
    while(cur!=pos)
    {
        cur=cur->next;
        assert(cur);
    }
    pos->data=x;
}

3.3 text.c

测试函数可以根据大家的想法进行测试，下面是我的测试函数以及输出情况

#include"SList.h"

void TestSList1()
{
    SLTNode* plist = NULL;
    SLPushFront(&plist, 1);
    SLPushFront(&plist, 2);
    SLPushFront(&plist, 3);
    SLPushFront(&plist, 4);

    SLTPrint(plist);
}

void TestSList2()
{
    SLTNode *plist=NULL;
    SLPushFront(&plist, 1);
    SLPushFront(&plist, 2);
    SLPushFront(&plist, 3);
    SLPushFront(&plist, 4);
    SLPushBack(&plist, 5);
    SLPushBack(&plist, 6);
    SLPushBack(&plist, 7);
    SLPushBack(&plist, 8);
    SLTPrint(plist);

    SLTNode *pos= STFind(plist,3);
    if(pos)
    {
        SLInsert(&plist,pos,30);
    }
    SLTPrint(plist);

    pos= STFind(plist,6);
    if(pos)
    {
        SLInsertAfter(plist,88);
    }
    SLTPrint(plist);

    pos= STFind(plist,7);
    if(pos)
    {
        SLErase(&plist,pos);
    }
    SLTPrint(plist);

    pos= STFind(plist,1);
    if(pos)
    {
        SLEraseAfter(pos);
    }
    SLTPrint(plist);
    SListDesTroy(&plist);
}


void Swapi(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

void Swappi(int** pp1, int** pp2)
{
    int* tmp = *pp1;
    *pp1 = *pp2;
    *pp2 = tmp;
}

int main()
{
//    TestSList1();

    TestSList2();
//    int a = 0, b = 1;
//    Swapi(&a, &b);
//
//    int* px = &a, * py = &b;
//    Swappi(&px, &py);

    return 0;
}

阅读全部

相关推荐

  6. 数据结构:单链表

    2024-04-22 22:30:06       33 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-04-22 22:30:06       18 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-04-22 22:30:06       19 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-04-22 22:30:06       18 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-04-22 22:30:06       20 阅读

热门阅读

  2. 【团体程序设计天梯赛 往年关键真题 详细分析&完整AC代码】L2-003 月饼（贪心）& L2-004 这是二叉搜索树吗？ （数据结构）

    2024-04-22 22:30:06       23 阅读

  3. 数据结构——线索树

    2024-04-22 22:30:06       38 阅读

  5. 【数据结构】分块查找

    2024-04-22 22:30:06       19 阅读

  12. 每日一练：九九乘法表（双重循环）

    2024-04-22 22:30:06       41 阅读

  14. springboot日志使用 SLF4J+Logback 实现（springboot默认的日志实现），日志打印到控制台及日志输出到指定文件

    2024-04-22 22:30:06       14 阅读

  16. json文件的格式化

    2024-04-22 22:30:06       39 阅读

  17. 双向链表的实现

    2024-04-22 22:30:06       17 阅读

  19. 高级软考项目管理之项目进度管理

    2024-04-22 22:30:06       48 阅读

  22. 计算机网络面试问题

    2024-04-22 22:30:06       52 阅读

  26. pprof火焰图排查问题小计

    2024-04-22 22:30:06       16 阅读

  30. Gitea：开源世界的协作灵魂

    2024-04-22 22:30:06       17 阅读