2、单链表（single linked list）程序：
经过上面简单的单链表链接，想必你已经对单链表有了些许认识，下面让我们来实现单链表吧！！
1、结构体定义结点
typedef int SLTDataType;//重定义数据类型，方便切换数据类型 typedef struct SListNode//定义单链表结构 32位环境下共8个字节， { SLTDataType data;//定义数据 struct SListNode* next;//指向下一个结构的指针，指向同类 //SLTNode* next; }SLTNode;//重定义 缩写，在本行之后起效，在结构体中不能使用
注意：这里重定义的结构名，只能在定义之后使用，不能在结构体中使用。
2、尾插
tail->next是结构体指针指向结构体成员next，而next存放的是下一个结点的地址，next指向下一个结点。
初始代码：
//尾插 void SLTPushBack(SLTNode* phead, SLTDataType x) { SLTNode* newnode = BuySLTNode(x); SLTNode* tail = phead; //找尾 while (tail->next) { tail = tail->next;//不是结尾，tail向后移动。 } tail->next = newnode;//是结尾，tail->next链接新结点 }
测试：
void TestSList2() { SLTNode* plist = CreateSList(5); SLTPushBack(plist, 100); SLTPushBack(plist, 200); SLTPushBack(plist, 300); SLTPrint(plist); } void TestSList3() { SLTNode* plist = NULL; SLTPushBack(plist, 100); SLTPushBack(plist, 200); SLTPushBack(plist, 300); SLTPrint(plist); } int main() { TestSList2(); //TestSList3(); return 0; }
调用TestSList2时：
调用TestSList3时：
此时，我们插入的数据并没有插进去，所以要考虑到链表为空的情况。
改进代码：
//尾插 void SLTPushBack(SLTNode* phead, SLTDataType x) { SLTNode* newnode = BuySLTNode(x); if (phead == NULL) { phead = newnode; } else { SLTNode* tail = phead; //找尾 while (tail->next) { tail = tail->next;//不是结尾，tail向后移动。 } tail->next = newnode;//是结尾，tail->next链接新结点 } }
如图，还是没插入进来
这里就要注意，phead是plist的拷贝，phead的改变不会影响plist，phead出作用域销毁，plist此时还是NULL。
这就涉及到实参传给形参，形参是实参的临时拷贝，形参的改变不会影响实参
举一个经典的例子：
如图：
1、改变int，传递int给形参，解引用形参进行交换改变。
2、改变int，传递int**给形参，解引用形参进行交换改变。
所以需要进行修改，这里的pphead是为了方便区分，也可以直接使用phead。
左图代码phead的改变是无法影响plist的值的，所以我们用到二级指针做如下改变（函数栈帧）：
注意：想要改变结构体，只需要使用结构体的指针tail->next，无需使用二级指针。
正确代码：
//尾插 void SLTPushBack(SLTNode** phead, SLTDataType x) { SLTNode* newnode = BuySLTNode(x); if (*phead == NULL) { *phead = newnode; } else { SLTNode* tail = *phead; //找尾 while (tail->next) { tail = tail->next;//不是结尾，tail向后移动。 } tail->next = newnode;//是结尾，tail->next链接新结点 } }
3、尾删
经典错误：
当我们将tail释放时，d2->next还指向tail，这就形成了野指针。
tail是局部变量，不需要置空。
改进方法：
方法一：
如图，在tail往下走之前，我们可以将tail赋值给一个新的变量prev，从而找到最后一个结点之前的结点，释放tail之后，再使用结构体指针将前一个结点的指针域置为空。
void SLTPopBack(SLTNode* phead) { SLTNode* tail = phead; SLTNode* prev = NULL; while (tail->next) { prev = tail; tail = tail->next; } free(tail); prev->next = NULL; }
方法二：
如图,当tail指向d1时，tail->next->next就是d2->next不为空，tail指d2，此时tail->next->next为空，tail->next为d2->next，将其释放并置为空。
void SLTPopBack(SLTNode* phead) { SLTNode* tail = phead; while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; }
但是上面代码并不完善，当我们进行多次删除打印，错误就会暴露出来，如下图，我们进行了四次打印，但却只输出了3次。
如图，当删除tail后面的两个结点后，tail->next为空，这时就再去使用tail->next就是错误的。
初步改进：
void SLTPopBack(SLTNode* phead) { if (phead->next == NULL) { free(phead); phead = NULL; } else { SLTNode* tail = phead; while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
分析原因，我们发现phead的改变不会影响plist，而我们这里释放了phead并且将phead置为了空，所以尾删也得用二级指针。
注意：链表为空不能删除，所以我们需要assert断言
正确代码：
void SLTPopBack(SLTNode** phead) { assert(*phead);//链表为空，不可删除，为空直接报错，终止 if ((*phead)->next == NULL) { free(*phead); *phead = NULL; } else { SLTNode* tail = *phead; while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
4、头插
如图，我们看出头插相对比较简单，我们只需要将newnode->next指向原来的开始结点，再将phead指针指向新的开始，也不必考虑空的情况：
正确代码：
//头插 void SLTPushFront(SLTNode** phead, SLTDataType x) { SLTNode* newnode = BuySLTNode(x); newnode->next = *phead; *phead = newnode; }
5、头删
当链表为空时，不能进行头删，所以这里同样需要断言。
头删不能直接删，直接删会导致找不到链表
先创建一个变量next间接指向下一个结点，再释放前一个结点，最后再将phead指向next，保证第一个节点的指针。
//头删 void SLTPopFront(SLTNode** phead) { assert(*phead); SLTNode* next = (*phead)->next; free(*phead); *phead = next; }
链表的优势在于头删，又快又简洁。
6、查找数据指定位置pos
在查找时，最好用一个变量来接收phead，保证phead在过程中一直指向链表的开始。
经典错误：
//查找数据指定位置pos SLTNode* SListFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; while (cur->next != NULL) { if (cur->data == x) { return cur; } cur=cur->next; } }
问题：
1、当链表为空时，进行查找，此时phead为空，cur也为空，那么cur->next,解引用失败，程序就会崩。
2、这样会漏掉最后一个结点，如下图，当cur->next为空时，循环结束，最后一个结点的data没有查找到。
所以最好不要写这样的代码。
最终代码：
//查找数据指定位置pos SLTNode* SListFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } }
7、在指定位置pos之后插入x
和顺序表的最大区别：给的位置不再是下标，而是结点的指针
经典错误：
如图，将pos->next先指向了新节点newnode，此时无法找到4的位置，所以newnode->next又指向了自己，形成了带环链表。此时程序是死循环：
此时，我们可以先保存4的位置，再进行链接，或者直接将上面的两步跌倒。
这里只写第二种：
最终代码：
注意这里需要检查pos是否为空
如图，先将newnode和4链接，再进行前面的链接就不会出现上面的错误，代码如下：
//在pos位置之后插入x void SListInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = BuySLTNode(x); newnode->next = pos->next; pos->next = newnode; }
这里改变的是结构体成员，有结构体的指针足以，不需要二级指针。
8、在指定位置pos之前插入x
如图，分析可知有下面两种情况：
//在pos位置之前插入x void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x) { assert(pos); if (*phead == pos)//头插 { SLTPushFront(phead, x);//复用 } else { SLTNode* prev = *phead; while (prev->next != pos) { prev = prev->next; } SLTNode* newnode = BuySLTNode(x); prev->next = newnode; newnode->next = pos; } }
9、删除指定位置pos之后的值
可能遇到两种情况：
1、pos指向最后一个结点，pos之后的值为空，适合用温柔的检查（如下if语句）
2、pos在中间，直接链接3和5会找不到4，从而无法释放造成内存泄漏。所以需要将4的位置给一个新的变量nextNode以便释放。
经过分析，
//删除pos位置之后的值 void SListEraseAfter(SLTNode* pos) { assert(pos); if (pos->next == NULL) { return; } else { /*free(pos->next); pos->next = pos->next->next;*///错误，释放了后一个结点，这个空间被置为随机值，找不到后面的结点 SLTNode* nextNode = pos->next; pos->next = nextNode->next; free(nextNode); } }
10、删除指定位置pos的值
//删除pos位置 void SListErase(SLTNode** phead, SLTNode* pos, SLTDataType x) { assert(pos); if (pos == *phead) { SLTPopFront(phead); } else { SLTNode* prev = *phead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } }
11、释放单链表
//单链表的释放 void SLTDestory(SLTNode** phead) { SLTNode* cur = *phead; while (cur) { SLTNode* next = cur->next; free(cur); cur = next; } *phead = NULL;//plist置空，防止释放后再调用 }
总代码：
1、SList.h文件
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> //相当于下面的重定义 //struct SListNode //{ // STLDataType data; // struct SListNode* next; //}; //typedef struct SListNode SLTNode; //void SLTPushBack(SLTDataType x) //{ // SLTNode node;//这样定义的结点出作用域销毁 //} typedef int SLTDataType;//重定义数据类型，方便切换数据类型 typedef struct SListNode//定义单链表结构 32位环境下共8个字节， { SLTDataType data;//定义数据 struct SListNode* next;//指向下一个结构的指针，指向同类 //SLTNode* next; }SLTNode;//重定义 缩写，在本行之后起效，在结构体中不能使用 SLTNode* BuySLTNode(SLTDataType x); SLTNode* CreateSList(int n); void SLTPrint(SLTNode* phead); //尾插尾删 void SLTPushBack(SLTNode** phead, SLTDataType x); void SLTPopBack(SLTNode** phead); //头插头删 void SLTPushFront(SLTNode** phead, SLTDataType x); void SLTPopFront(SLTNode** phead); //查找数据指定位置pos SLTNode* SListFind(SLTNode* phead, SLTDataType x); //在pos位置之后插入x void SListInsertAfter(SLTNode* pos, SLTDataType x); //删除pos位置之后的值 void SListEraseAfter(SLTNode* pos); //在pos位置之前插入x void SListInsert(SLTNode** phead,SLTNode* pos, SLTDataType x); //删除pos位置 void SListErase(SLTNode** phead, SLTNode* pos); //单链表的释放 void SLTDestory(SLTNode** phead);
2、SList.c文件
#define _CRT_SECURE_NO_WARNINGS 1 #include"SList.h" //直接用malloc需要自行赋值，检查空，很烦，所以封装一个函数 SLTNode* BuySLTNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1);//未开辟成功，结束程序 } newnode->data = x; newnode->next = NULL;//最后一个结点默认为空 return newnode; } SLTNode* CreateSList(int n) { SLTNode* phead = NULL, * ptail = NULL; /*int x = 0;*/ for (int i = 0; i < n; ++i) { /*scanf("%d", &x); SLTNode* newnode = BuySLTNode(x);*/ SLTNode* newnode = BuySLTNode(i); if (phead == NULL) { ptail = phead = newnode; } else { ptail->next = newnode; ptail = newnode; } } return phead; } //打印函数封装 void SLTPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur != NULL) { printf("[%d|%p]->", cur->data,cur->next); cur = cur->next; } printf("NULL\n"); } //尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySLTNode(x); if (*pphead == NULL) { *pphead = newnode; } else { SLTNode* tail = *pphead; //找尾 while (tail->next) { tail = tail->next;//不是结尾，tail向后移动。 } tail->next = newnode;//是结尾，tail->next链接新结点 } } //尾删 //void SLTPopBack(SLTNode* phead) //{ // SLTNode* tail = phead; // SLTNode* prev = NULL; // while (tail->next) // { // prev = tail; // tail = tail->next; // } // free(tail); // prev->next = NULL; //} //尾删 void SLTPopBack(SLTNode** phead) { assert(*phead); if ((*phead)->next == NULL) { free(*phead); *phead = NULL; } else { SLTNode* tail = *phead; while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; } } //头插 void SLTPushFront(SLTNode** phead, SLTDataType x) { SLTNode* newnode = BuySLTNode(x); newnode->next = *phead; *phead = newnode; } //头删 void SLTPopFront(SLTNode** phead) { assert(*phead); SLTNode* next = (*phead)->next; free(*phead); *phead = next; } //查找数据指定位置pos SLTNode* SListFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } } //在pos位置之后插入x void SListInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = BuySLTNode(x); newnode->next = pos->next; pos->next = newnode; } //在pos位置之前插入x void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x) { assert(pos); if (*phead == pos) { SLTPushFront(phead, x); } else { SLTNode* prev = *phead; while (prev->next != pos) { prev = prev->next; } SLTNode* newnode = BuySLTNode(x); prev->next = newnode; newnode->next = pos; } } //删除pos位置之后的值 void SListEraseAfter(SLTNode* pos) { assert(pos); if (pos->next == NULL) { return; } else { /*free(pos->next); pos->next = pos->next->next;*///错误，释放了后一个，这个空间被置为随机值，找不到后面的结点 SLTNode* nextNode = pos->next; pos->next = nextNode->next; free(nextNode); } } //删除pos位置 void SListErase(SLTNode** phead, SLTNode* pos) { assert(pos); if (pos == *phead) { SLTPopFront(phead); } else { SLTNode* prev = *phead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } } //单链表的释放 void SLTDestory(SLTNode** phead) { SLTNode* cur = *phead; while (cur) { SLTNode* next = cur->next; free(cur); cur = next; } *phead = NULL;//plist置空，防止释放后再调用 }
3、test.c测试文件
#include"SList.h" void TestSList1() { //SLTNode* n1 = malloc();//直接用malloc需要自行赋值，检查空，很烦，所以封装一个函数 SLTNode* n1 = BuySLTNode(1); SLTNode* n2 = BuySLTNode(2); SLTNode* n3 = BuySLTNode(3); SLTNode* n4 = BuySLTNode(4); n1->next = n2; n2->next = n3; n3->next = n4; n4->next = NULL; //SLTNode n1;//为什么不直接定义结构体变量 //SLTNode n2; //n1.next = &n2;//这样也可以链接，但是不可行 //SLTNode* plist = CreateSList(5); //SLTPrint(plist); } //初始测试代码 void TestSList2() { SLTNode* plist = CreateSList(5); SLTPushBack(&plist, 100); SLTPushBack(&plist, 200); SLTPushBack(&plist, 300); SLTPrint(plist); } void TestSList3() { SLTNode* plist = NULL; SLTPushBack(&plist, 100); SLTPushBack(&plist, 200); SLTPushBack(&plist, 300); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); } void TestSList4() { SLTNode* plist = NULL; SLTPushFront(&plist, 100); SLTPushFront(&plist, 200); SLTPushFront(&plist, 300); SLTPushFront(&plist, 400); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); } void TestSList5() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPushBack(&plist, 5); SLTPrint(plist); SLTNode* pos = SListFind(plist, 3); SListInsertAfter(pos, 30); pos = SListFind(plist, 2); SListInsert(&plist, pos, 200); SLTPrint(plist); // if (pos) // { // SListInsertAfter(pos, 30);//找到之后在后面插入30 // printf("找到了\n"); // // } // else // { // printf("找不到\n"); // } // SLTPrint(plist); } void TestSList6() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPushBack(&plist, 5); SLTPrint(plist); SLTNode* pos = SListFind(plist, 3); SListEraseAfter(pos); SLTPrint(plist); pos = SListFind(plist, 3); SListErase(&plist,pos); pos = NULL; SLTPrint(plist); SLTDestory(&plist); SLTPrint(plist); } int main() { //TestSList1(); //TestSList2(); //TestSList3(); //TestSList4(); //TestSList5(); TestSList6(); return 0; } ////二级指针经典例子 //void Swap1(int* p1, int* p2) //{ // int tmp = *p1; // *p1 = *p2; // *p2 = tmp; //} //void Swap2(int** pp1, int** pp2) //{ // int tmp = *pp1; // *pp1 = *pp2; // *pp2 = tmp; //} // //int main() //{ // int a = 0, b = 1; // swap1(&a, &b); // // int* ptr1 = &a, * ptr2 = &b; // swap2(&ptr1, &ptr2); // // return 0; // //}
注意：
如果不用二级指针，我们可以用返回值，但是每次返回得接收，c++中可以用引用
不需要修改头指针就用一级，需要修改就用二级，必须将实参的地址传给形参
结语：
这里本章内容就介绍完了，文章中某些内容我们之前有介绍，所以只是一笔带过，还请谅解。希望以上内容对大家有所帮助👀，如有不足望指出🙏
前路漫漫！努力变强💪💪 吧！！c
