当前位置：首页 > news >正文

让单链表不再云里雾里

news 来源：原创 2025/9/4 11:40:50

一日不见，如三月兮！接下来与我一起创建单链表吧！

单链表的结构：

创建单链表：

增加结点：

插入结点：

删除结点：

打印单链表：

单链表查找：

单链表指定位置插入：

单链表指定位置删除：

答疑解惑：

结语：

单链表的结构：

单链表有不带头单向不循环，和带头单向非循环两种类型，我们将探索的是不带头单向不循环的链表；它有两种结构：逻辑结构和物理结构，如下图：

因为物理结构便于理解，所以我们参照它来进行代码书写，物理结构中我们访问的都是地址，所以我们会使用指针，且蓝色所指表示它们两的地址相同！

创建单链表：

首先我们要定义一个结构体，然后我们要访问数值，所以会定义一个整型变量，为了找下一个数值的地址，我们还需创建一个指针

typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;//方便查找下一个结点
}SLTNode;

增加结点：

因为每次插入，都需要书写一个代码，为了节省空间，我们将它包装成一个函数，方便我们进行调用

SLTNode* Buynewnode(SLDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//开辟空间if(newnode == NULL)//判断是否开辟成功{perror("malloc fail");return;}newnode->data = x;//将数据赋值newnode->next = NULL;return newnode;//返回地址
}

插入结点：

头插：

首先将一开始头的数据地址赋给新的结点的下一个(newnode->next)地址，再将头指针变为新结点

void SLTPushFront(SLTNode** pphead，SLTDataType x)
{assert(pphead);SLTNode* newnode = Buynewnode(x);newnode->next = *pphead;*pphead = newnode;
}

尾插：

首先判断链表是否为空的情况，若为空，则将新结点赋给头结点即可，如果不是，再进行找尾，当找到尾时，将新结点的地址赋给tail的下一个。

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = Buynewnode(x);//判断是否为空if(*pphead == NULL){*pphead = newnode;}else{//找尾while(tail->next != NULL){tail = tail->next;}tail->next = newnode;//链接新结点}
}

删除结点：

头删：

先判断链表是否为空，若不为空，将第二个的数据地址赋给头指针即可，但我们怎么找到第二个的数据地址呢？我们可以先将头指针赋给一个指针进行保存，再将创建的指针找到其下一个的地址(即第二个数据的地址)赋给头指针，在释放第一个结点的地址即可。

void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* begin = *pphead;//保存头指针*pphead = begin->next;free(begin)//释放第一个结点的空间begin = NULL;
}

尾删：

首先判断单链表是否为空，其次判断一下是否只有一个结点，若只有一个，直接将头指针释放置空即可，剩下的情况我们只要找到尾将它删除即可，有人想偷懒，将上面的找尾代码拷贝，然后将其置空，果真这么简单吗？会导致什么结果呢？又该怎么处理呢？

如果将tail置空，会使前一个结点的下一个指针变为野指针，tail置空是将局部变量置空，而非将结构体变量置空，若要改变这个情况，我们再定义一个结构体指针，找到tail的前面一个头结点，再将其下一个置空就行了

void SLTPopBack(SLTNode** pphead)
{//为空assert(pphead);assert(*pphead);//只有一个结点if((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* prev = NULL;SLTNode* tail = *pphead;//找尾while(tail->next != NULL){prev = tail;//找到tail前一个结点tail = tail->next;}//释放掉尾结点free(tail)tail = NULL;prev->next = NULL；}
}

打印单链表：

将头指针赋值给一个指针变量，这样可以防止头指针被覆盖(这个作用这里体现不明显)，然后循环遍历就OK了

void SLTPrint(SLTNode* phead)
{SLTNode* begin = phead;//循环遍历while(begin){printf("%d->", begin->data);begin = begin->next;}printf("NULL\n");
}

单链表查找：

将头指针赋值给一个指针变量，然后遍历，用if语句判断

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while(cur){if(cur->data == x){//找到返回return cur;}cur = cur->next;}return NULL;
}

单链表指定位置插入：

我们先定义一个指针变量，用来找我们指定插入的位置地址，找到这个指针变量的前一个位置的地址，再将新结点的地址赋给前一个的下一个地址(next)，再将指针变量赋给新节结点的下一个地址

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pos);//判断pos是否为空assert(pphead);SLTNode* newnode = Buynewnode(x);if(*pphead == pos){newnode->next = pos;*pphead = newnode//将新结点赋给头指针}else{SLTNode* prev = *pphead;//找到pos前面一个地址while(prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;}
}

单链表指定位置删除：

我们先定义一个指针变量，用来找我们指定插入的位置地址，找到这个指针变量的前一个位置的地址，再将指定位置的下一个，赋给前一个位置的下一个，再将指定位置释放置空

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);//判断pos是否为空assert(pphead);//只有一个结点if(*pphead == pos){*pphead = pos->next;free(pos);pos = NULL;}else{SLTNode* prev = *pphead;//找pos前一个位置while(prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);//释放指定位置空间pos = NULL;}
}

答疑解惑：

为什么要传二级指针？因为要修改结构体指针，所以要用二级指针，比如修改变量，用一级指针修改才行！

什么时候用assert？当一个变量一定不为空时，则用assert，比如插入数据时，*pphead可以为空，所以不用断言，亦或者打印时，也可以打印空数据，所以也不用断言。

结语：

谢谢大家观看！期待下次见面哦！

单链表的结构：

创建单链表：

增加结点：

插入结点：

删除结点：

打印单链表：

单链表查找：

单链表指定位置插入：

单链表指定位置删除：

答疑解惑：

结语：

相关文章：