深入剖析无头单链表——C语言动图演示

🔊个人介绍
🌳数据结构系列点击跳转
🌳戳我跳到本人个人主页
🇨🇳大家好，我是_奇奇，一名C/C++博主。河牧院大一在读。
🔔欢迎大家交流学习
❤️编程的前途是光明的，道路是曲折的。
🌳笑到最后才是赢家🍺

这里是目录

单链表的实现，学习单链表就需要对C语言指针熟悉了解。因为链表，顾名思义就是用链子连起来的的表。而这个链子就是指针。实际上就是地址。通过地址来连接起来的表。
画图

画图画图

，让我们来看看单链表是什么样子吧。
我实现的这个单链表是没有头的。不带首元节点。只有一个头指针。指向第一个元素。单链表的每个元素(一般称之为节点）都是一个结构体类型。每个这样的节点都包含一个指向下一个节点的指针和一个数据。
如下图所示。
假设每个节点的地址都是已知的。我把每个结构体的地址都写了出来

🌳无头单向链表

• 和严老师书上的不同的是，我们这个单链表没有首元结点，原因是刚开学单链表先从简单开始，否则容易迷糊。
• 链表的实质就是下面的一幅图。这张图只要看懂了。单链表你就会了。
• 链表的实质是通过16进制表示的地址连接起来的，可以这么说地址就是指针如图所示。
• 指针相当于绿色的箭头。头指针plist里面存放的是第一个节点的地址0x00000030，第一个节点里面的next指针里面存放的是第二个节点的地址0x00000050，第一个节点里面的next指针里面存放的是第二个节点的地址0x00000010…以此类推直到最后一个节点的next指针指向NULL；

🌳结构体声明(节点)

• 在头文件中对结构体进行声明创建，为什么起名叫SListNode，因为是Signle List Node （单链表）的缩写；
• 将int类型typedef为SLNDataType的原因是易于后期更换每个节点的数据。
• 每个SListNode节点包含一个int类型数据 和 一个指向这个节点的指针next。

🌳动态申请新节点

• 在尾插之前需先申请一个节点，我们把它命名为newnode。按需所取。不浪费空间。
• 再申请的同时我们需要这个新节点初始化了。
• 把next指针赋值为空指针。数据传我们想传递的数据。
• 如果开辟失败了，就结束程序。
• else将节点初始化。
• 最后返回节点。

头文件中函数声明

源文件中函数定义

🌳尾插

• 在这里有点需要注意。那就是二级指针。因为需要修改头指针里面的地址所以要传头指针的地址。传地址才能修改里面的值。
• 原因是因为形参只是实参的一份临时拷贝。只有传地址才能改变里面的值。
• 在严蔚敏老师的数据结构书中用的是C++语法中的引用，是&符号，和传地址的效果一样。
• 尾插之前先调用申请空间的函数。

• 在尾部插入数据分为两种情况

1.当链表为空的时候。

为空时直接将newnode这个地址赋给*pphead就ok了。

2.当链表不为空的时候。

需要先找到尾结点。这时我们定义一个指向头节点的指针

tail

tail->next

不为空，就执行

tail = tail->next

.

意思就是让tail指针向前移动一个节点

。
3.不为空，向前移动一个节点
4.newnode->next是空。跳出while循环5.加入新节点

6.将newnode的值赋给tail->next.就此完成了尾删。

🌳打印

• 打印依次遍历链表就ok了。 源文件test源文件

🌳头插

1.当表为空时

两种情况可以合二为一。

2.当表不为空时

1.在第一个节点处插入
2.创建新节点

3.第一步将newnode->next指针里面存放第一个节点的地址

0x0000 0030

。
第二步再将newnode的值

0x00000020

赋给头指针。

顺序不能错，否则逻辑错误。

这样就完成了头插的解释。

🌳尾删

二话不说，先画图。

1.当表不为空时

定义一个

prev

指针变量。用来找到

倒数第二个节点

并把他的next指针赋为NULL。
当tail->next不为空，prev指向tail指向的位置。tail向前移动。

两个指针继续移动直至tail->next 为NULL。当tail->next为空时跳出循环

跳出循环然后

prev->next置为空。free掉tail的空间。tail置为空

2.当表为空时

当表为空时直接return。

3.当表只有一个节点时

直接free掉 头指针（*pphead）指向的空间。

记得给头指针赋值为空。否则头指针就是野指针了

。
尾删的解释到此结束

🌳头删

1.当表为空时

2.当表为一个节点时

只有一个节点和有多个节点代码一样。可以合二为一。

3.当表不为空时

先定一个current变量用来记住第二个节点的地址。（

因为free掉第一个节点后。第二个节点的地址就无法访问了

。）然后再free掉头指针。再把current里存放的值放给头指针。

🌳查找

查找某个元素，若找到返回他的地址。否则返回空指针。

🌳在指定元素前面插入一个节点

先调用查找函数。找到这个元素的地址。然后返回。

1.当头指针等于指定元素的地址时

这个情况和头插一样。看前面的头插

2.一般情况

和尾插情况一样。详情见尾插。

🌳销毁

为什么要销毁？
当我们的链表还有节点 或者 不想继续用下去的时候可以销毁掉。

1.当表为空时

此时不进入while循环，直接将头指针赋为空。

2.当表不为空时

设置一个临时变量tmp。用来保存头指针cur的next里面地址。
然后free掉头指针指向的空间。
再让头指针前进一个节点，直至遍历完整个链表。
此时就结束了整个链表。

各位观众老爷，创作不易，喜欢的话来个三连吧、

🌳test.c

#define _CRT_SECURE_NO_WARNINGS#include"SList.h"intmain(){
    SListNode* plist =NULL;SListNodePushBack(&plist,1);SListNodePushBack(&plist,2);SListNodePushBack(&plist,3);SListNodePushBack(&plist,4);SListNodePushBack(&plist,1);SListNodePushFront(&plist,0);SListNodePushFront(&plist,-1);SListNodePopBack(&plist);SListNodePopBack(&plist);SListNodePopBack(&plist);SListNodePopBack(&plist);SListNodePopBack(&plist);SListNodePopBack(&plist);SListNodePopBack(&plist);SListNodePopBack(&plist);SListNodePopBack(&plist);SListNodePushFront(&plist,0);SListNodePushFront(&plist,-1);

    SListNode* pos =SListNodeFind(&plist,0);SListInsert(&plist, pos,6);SListNodePrint(&plist);SListNodeDestory(&plist);SListNodePrint(&plist);return0;}

🌳SList.h

#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefint SLNDataType;typedefstruct SListNode
{
    SLNDataType data;struct SListNode* next;}SListNode;//动态申请一个节点
SListNode*SListNodeBuyNewnode(SLNDataType x);//尾插voidSListNodePushBack(SListNode** pphead, SLNDataType x);//打印voidSListNodePrint(SListNode** pphead);//头插voidSListNodePushFront(SListNode** pphead, SLNDataType x);//尾删voidSListNodePopBack(SListNode** pphead);//头删voidSListNodePopFront(SListNode** pphead);//查找
SListNode*SListNodeFind(SListNode** pphead, SLNDataType x);//在一个地址前面插入一个节点voidSListInsert(SListNode** pphead, SListNode* pos, SLNDataType x);//销毁voidSListNodeDestory(SListNode** pphead);

🌳SList.c

#define _CRT_SECURE_NO_WARNINGS#include"SList.h"//动态申请一个节点
SListNode*SListNodeBuyNewnode(SLNDataType x){
    SListNode* newnode =(SListNode*)malloc(sizeof(SListNode));if(NULL== newnode){printf("malloc fail");exit(-1);}else{
        newnode->data = x;
        newnode->next =NULL;}return newnode;}//尾插voidSListNodePushBack(SListNode** pphead, SLNDataType x){
    SListNode* newnode =SListNodeBuyNewnode(x);//当链表为空的时候if(*pphead ==NULL){*pphead = newnode;}//当不为空的时候else{
        SListNode* tail =*pphead;while(tail->next !=NULL){
            tail = tail->next;}
        tail->next = newnode;}}//打印voidSListNodePrint(SListNode** pphead){while(*pphead !=NULL){printf("%d->",(*pphead)->data);(*pphead)=(*pphead)->next;}printf("NULL\n");}//头插voidSListNodePushFront(SListNode** pphead, SLNDataType x){
    SListNode* newnode =SListNodeBuyNewnode(x);
    newnode->next =*pphead;*pphead = newnode;}//尾删voidSListNodePopBack(SListNode** pphead){assert(pphead);//当表为空时if(*pphead ==NULL){return;}//当表只有一个节点elseif((*pphead)->next ==NULL){free(*pphead);*pphead =NULL;return;}//当表不为空else{
        SListNode* prev =NULL;
        SListNode* tail =*pphead;while(tail->next !=NULL){
            prev = tail;
            tail = tail->next;}
        prev->next =NULL;free(tail);
        tail =NULL;}}//头删voidSListNodePopFront(SListNode** pphead){assert(pphead);if(*pphead ==NULL){return;}
    SListNode* current =(*pphead)->next;free(*pphead);*pphead = current;}//查找
SListNode*SListNodeFind(SListNode** pphead, SLNDataType x){
    SListNode* cur =*pphead;while(cur){if(cur->data == x){return cur;}else{
            cur = cur->next;}}returnNULL;}//在一个地址前面插入一个节点voidSListInsert(SListNode** pphead, SListNode* pos, SLNDataType x){
    SListNode* newnode =SListNodeBuyNewnode(x);if(*pphead == pos){
        newnode->next =*pphead;*pphead = newnode;}else{
        SListNode* prev =*pphead;while(prev->next != pos){
            prev = prev->next;}
        prev->next = newnode;
        newnode->next = pos;}}//销毁voidSListNodeDestory(SListNode** pphead){assert(pphead);

    SListNode* cur =*pphead;while(cur){
        SListNode* tmp = cur->next;free(cur);
        cur = tmp;}*pphead =NULL;}