🔊个人介绍
🇨🇳大家好，我是_奇奇，一名C/C++博主。河牧院大一在读。
🔔欢迎大家交流学习
❤️编程的前途是光明的，道路是曲折的。
🌳笑到最后才是赢家🍺
这里是目录
🌳无头单向链表
🌳结构体声明(节点)
🌳动态申请新节点
🌳尾插
1.当链表为空的时候。
2.当链表不为空的时候。
🌳打印
🌳头插
1.当表为空时
2.当表不为空时
🌳尾删
1.当表不为空时
2.当表为空时
3.当表只有一个节点时
🌳头删
1.当表为空时
2.当表为一个节点时
3.当表不为空时
🌳查找
🌳在指定元素前面插入一个节点
1.当头指针等于指定元素的地址时
2.一般情况
🌳销毁
1.当表为空时
2.当表不为空时
🌳test.c
🌳SList.h
🌳SList.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
1.
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" int main() { 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); return 0; }
🌳SList.h
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLNDataType; typedef struct SListNode { SLNDataType data; struct SListNode* next; }SListNode; //动态申请一个节点 SListNode* SListNodeBuyNewnode(SLNDataType x); //尾插 void SListNodePushBack(SListNode** pphead, SLNDataType x); //打印 void SListNodePrint(SListNode** pphead); //头插 void SListNodePushFront(SListNode** pphead, SLNDataType x); //尾删 void SListNodePopBack(SListNode** pphead); //头删 void SListNodePopFront(SListNode** pphead); //查找 SListNode* SListNodeFind(SListNode** pphead, SLNDataType x); //在一个地址前面插入一个节点 void SListInsert(SListNode** pphead, SListNode* pos, SLNDataType x); //销毁 void SListNodeDestory(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; } //尾插 void SListNodePushBack(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; } } //打印 void SListNodePrint(SListNode** pphead) { while (*pphead != NULL) { printf("%d->", (*pphead)->data); (*pphead) = (*pphead)->next; } printf("NULL\n"); } //头插 void SListNodePushFront(SListNode** pphead, SLNDataType x) { SListNode* newnode = SListNodeBuyNewnode(x); newnode->next = *pphead; *pphead = newnode; } //尾删 void SListNodePopBack(SListNode** pphead) { assert(pphead); //当表为空时 if (*pphead == NULL) { return; } //当表只有一个节点 else if ((*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; } } //头删 void SListNodePopFront(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; } } return NULL; } //在一个地址前面插入一个节点 void SListInsert(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; } } //销毁 void SListNodeDestory(SListNode** pphead) { assert(pphead); SListNode* cur = *pphead; while (cur) { SListNode* tmp = cur->next; free(cur); cur = tmp; } *pphead = NULL; }
