数据结构—单链表

devtools/2024/9/24 6:01:37/

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;//改变结构的指针plistelse{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;//改变结构的指针plistelse{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;
}


http://www.ppmy.cn/devtools/9368.html

相关文章

YOLOv9改进策略 | 损失函数篇 | EIoU、SIoU、WIoU、DIoU、FocusIoU等二十余种损失函数

YOLOv9改进策略 | 损失函数篇 | EIoU、SIoU、WIoU、DIoU、FocusIoU等二十余种损失函数

一、本文介绍 这篇文章介绍了YOLOv9的重大改进&#xff0c;特别是在损失函数方面的创新。它不仅包括了多种IoU损失函数的改进和变体&#xff0c;如SIoU、WIoU、GIoU、DIoU、EIOU、CIoU&#xff0c;还融合了“Focus”思想&#xff0c;创造了一系列新的损失函数。这些组合形式的…
阅读更多...
【若依前后端分离】仪表盘绘制

【若依前后端分离】仪表盘绘制

示例&#xff1a; 代码&#xff1a; InstrumentPanel.vue组件 <template><div><!-- 在这里放置你的图表组件 --><div ref"echarts" style"width: 100%; height: 400px;"></div></div> </template><script&g…
阅读更多...
混杂设备驱动

混杂设备驱动

混杂设备驱动 之前我们编写的是标准字符设备驱动程序，看起来还是有点复杂的样子。linux内核api接口提供了一种混杂设备驱动程序框架，可以大幅度降低编写字符设备驱动程序复杂性。 misc的意思是混合、杂项的，因此 misc 驱动也叫做杂项驱动，misc 驱动其实就是最简单的字符设…
阅读更多...
.NET Core中间件管道MAP的作用和使用

.NET Core中间件管道MAP的作用和使用

在ASP.NET Core中&#xff0c;中间件是构建HTTP请求管道的基本组件。中间件组件负责在ASP.NET Core应用程序中处理请求和响应。中间件可以执行多种任务&#xff0c;例如身份验证、记录、异常处理等。你可以按顺序将多个中间件组件组合在一起&#xff0c;形成一个请求处理管道。…
阅读更多...
vue3【实用教程】侦听器 watch，自动侦听 watchEffect()，$watch，手动停止侦听器

vue3【实用教程】侦听器 watch，自动侦听 watchEffect()，$watch，手动停止侦听器

watch 侦听明确指定的状态变化执行回调 实战场景 侦听路由传参的变化&#xff0c;重新访问接口&#xff0c;刷新页面侦听接口返回值的变化&#xff0c;刷新页面 侦听值类型数据 // 选项式 API watch: {// 每当 question 改变时&#xff0c;这个函数就会执行question(newQue…
阅读更多...
vue2 mixins混入

vue2 mixins混入

在Vue2中&#xff0c;使用mixins混入有两种方式&#xff1a; 全局混入&#xff1a;在Vue实例初始化之前&#xff0c;使用Vue.mixin()方法进行全局混入。具体步骤如下&#xff1a; 在main.js&#xff08;或其他入口文件&#xff09;中引入Vue和混入对象&#xff1a;import Vue f…
阅读更多...
在Vue3中如何使用H.265视频流媒体播放器EasyPlayer.js？

在Vue3中如何使用H.265视频流媒体播放器EasyPlayer.js？

H5无插件流媒体播放器EasyPlayer属于一款高效、精炼、稳定且免费的流媒体播放器&#xff0c;可支持多种流媒体协议播放&#xff0c;可支持H.264与H.265编码格式&#xff0c;性能稳定、播放流畅&#xff0c;能支持WebSocket-FLV、HTTP-FLV&#xff0c;HLS&#xff08;m3u8&#…
阅读更多...
CentOS 7安装、卸载MySQL数据库（一）

CentOS 7安装、卸载MySQL数据库（一）

说明&#xff1a;本文介绍如何在CentOS 7操作系统下使用yum方式安装MySQL数据库&#xff0c;及卸载&#xff1b; 安装 Step1&#xff1a;卸载mariadb 敲下面的命令&#xff0c;查看系统mariadb软件包 rpm -qa|grep mariadb跳出mariadb软件包信息后&#xff0c;敲下面的命令…
阅读更多...
最新文章

Copyright @ 2022~2023