4.10 在pos位置之后插入节点
我们实现了在pos位置之前插入节点之后，是不是觉得实现的很难受，这么麻烦，还要实现，这明显不合理啊。
在pos位置之后插入更加合适吧？这样我根本不需要遍历链表，我只需要让 新节点newnode 和 pos 位置的下一个节点链接，然后将pos位置的next变为我的新节点即可。
// 在pos位置之后插入节点 void SListInsertAfter(SLTNode* pos, SLTDateType x) { assert(pos); // 避免pos传参传错 SLTNode* newnode = BuyListNode(x); newnode->next = pos->next; pos->next = newnode; }
4.11 删除pos位置的节点
删除pos位置的节点，需要考虑此时链表是否为空，但这只是一部分，只需要用断言处理一下就好。
而我们着重处理的为，头删和多个节点删除的情况。
如果是头删，那么删除的就是第一个节点，那么此时就需要将头变为pos->next，并且释放pos位置。头删情况也完美处理了单个节点删除时的情况。
如果是多个节点，那么就需要找到pos的前一个位置，将 pos 前一个位置(prev)的 next 链接为我当前 pos 的 next。然后释放我的pos节点。
// 删除pos位置的节点 void SListErase(SLTNode** pphead, SLTNode* pos) { assert(pos); // 处理头删 if (*pphead == pos) { *pphead = pos->next; free(pos); } // 处理其他情况 else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } }
4.12 删除pos位置之后的节点
和在pos位置之前插入一样，我们发现删除pos位置的节点，也很麻烦。因为需要找pos的前一个位置，所以这种设计也比较麻烦。
所以有时我们会删除pos位置之后的节点，这样就很方便了。
既然要删除pos位置之后的节点，那么我就需要将 pos 位置的节点和pos位置的 next 的 next 链接起来。
那么我们首先用 next 拷贝记录一下 pos->next ，然后，再将pos->next赋值为next->next，也就是pos往后的两个节点。最后释放next位置的节点即可。
注意：我pos位置的下一个节点不能是尾结点后面的节点！
// 删除指定pos位置后的一个节点 void SListEraseAfter(SLTNode** pphead, SLTNode* pos) { assert(pos); assert(pos->next);// 删除的不能是尾结点后面的位置 SLTNode* next = pos->next;// 拷贝pos的下一个节点 pos->next = next->next;// 将pos的next变为下一个节点的next free(next);// 释放之前pos的下一个节点 next = NULL; }
4.13 打印
打印整个链表，只需要遍历链表，控制好循环的停止条件：
// 打印 void SListPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
4.14 销毁
销毁链表，如果仅仅释放我的*pphead，可行吗？这当然不可行。
因为单链表是由不同地址的节点串联起来的。它不像数组，存储连续，只要释放起始位置。
如果我仅仅释放*pphead，那么只释放了我的第一个节点，后面的节点没释放，函数调用结束后，这些节点也找不到了。所以我们需要逐个销毁。
首先，使用 cur 拷贝头部位置。然后使用循环迭代。迭代过程中，需要记住我的 cur->next ，否则 cur 被释放后，无法找到下一个节点，然后逐个释放就可以了。
注意：当销毁后，记得把*pphead 置空，防止销毁链表后对链表误操作而导致的野指针问题。
// 销毁 void SListDestory(SLTNode** pphead) { SLTNode* cur = *pphead; while (cur) { SLTNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; // 置空 }
5. 完整代码
SList.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLTDateType; typedef struct SListNode { int data; struct SListNode* next; }SLTNode; // 打印 void SListPrint(SLTNode* phead); // 尾插 void SListPushBack(SLTNode** pphead, SLTDateType x); // 头插 void SListPushFront(SLTNode** pphead, SLTDateType x); // 尾删 void SListPopBack(SLTNode** pphead); // 头删 void SListPopFront(SLTNode** pphead); // 查找 SLTNode* SListFind(SLTNode* phead, SLTDateType x); // 在pos位置之前插入一个节点 void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x); // 在pos位置之后插入一个节点 void SListInsertAfter(SLTNode* pos, SLTDateType x); // 在指定位置删除一个节点 void SListErase(SLTNode** pphead, SLTNode* pos); // 删除指定pos位置后的一个节点 void SListEraseAfter(SLTNode** pphead, SLTNode* pos); // 销毁 void SListDestory(SLTNode** pphead);
SList.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "SList.h" // 创建新节点 SLTNode* BuyListNode(SLTDateType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1);// 内存申请失败，说明几乎没有空间了，直接退出程序 } newnode->data = x; newnode->next = NULL; return newnode; } // 打印 void SListPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } // 尾插 void SListPushBack(SLTNode** pphead, SLTDateType x) { // 建立新节点 SLTNode* newnode = BuyListNode(x); // 链表没有节点，给新节点 if (*pphead == NULL) { *pphead = newnode; } else { // 找到尾结点 SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } // 尾结点链接新节点 tail->next = newnode; } } // 头插 void SListPushFront(SLTNode** pphead, SLTDateType x) { assert(pphead); SLTNode* newnode = BuyListNode(x); newnode->next = *pphead;// 新节点链接之前plist的地址 *pphead = newnode;// 头指针更改为newnode } // 尾删 void SListPopBack(SLTNode** pphead) { // 温柔处理 /*if (*pphead == NULL) { return; }*/ // 暴力处理 一个节点 assert(*pphead); if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else// 两个及以上节点 { // plan1 SLTNode* prev = NULL;// 记录上一个节点的地址 SLTNode* tail = *pphead; //while (tail->next != NULL)// 计算逻辑表达式的值为真或假决定循环是否继续执行 while (tail->next)// 当值为空指针，被隐式转换为0，结束循环 { prev = tail; tail = tail->next; } free(tail);// 释放尾结点空间 tail = NULL; // 将前一个节点的next置空 prev->next = NULL; } // plan2： //SLTNode* tail = *pphead; //while (tail->next->next)// 如果当前tail的next的地址访问下一个next为空，则停止 //{ // tail = tail->next;// 将尾结点赋值为最后一个节点的next //} //free(tail->next);// 释放最后一个节点 //tail->next = NULL;// 最后一个节点置空 } // 头删 void SListPopFront(SLTNode** pphead) { // 处理空链表 assert(*pphead); // 处理1个及以上节点 SLTNode* newpphead = (*pphead)->next; free(*pphead); *pphead = newpphead; } // 查找 SLTNode* SListFind(SLTNode* phead, SLTDateType x) { SLTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } else { cur = cur->next; } } return NULL;// 没找到 } // 在pos位置之前插入节点 void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x) { assert(pos); SLTNode* newnode = BuyListNode(x); // 头插情况特殊处理 if (*pphead == pos) { newnode->next = *pphead;// newnode链接头 *pphead = newnode;// 头变为newnode } // 其他位置插入 else { // 找到pos前一个位置 SLTNode* posPrev = *pphead; while (posPrev->next != pos) { posPrev = posPrev->next; } posPrev->next = newnode;// 将pos前一个位置链接到newnode newnode->next = pos;// newnode连接到pos } } // pos不太适合在节点前插入，适合在节点后插入 // 在pos后面 插入节点 void SListInsertAfter(SLTNode* pos, SLTDateType x) { assert(pos); SLTNode* newnode = BuyListNode(x); newnode->next = pos->next; pos->next = newnode; } // 删除pos位置的节点 void SListErase(SLTNode** pphead, SLTNode* pos) { assert(pos); // 处理头删 if (*pphead == pos) { *pphead = pos->next; free(pos); // 直接调用头删 // SListPopFront(pos); } // 处理其他情况 else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } } // 删除指定pos位置后的一个节点 void SListEraseAfter(SLTNode** pphead, SLTNode* pos) { assert(pos); assert(pos->next);// 删除的不能是尾结点后面的位置 SLTNode* next = pos->next;// 拷贝pos的下一个节点 pos->next = next->next;// 将pos的next变为下一个节点的next free(next);// 释放之前pos的下一个节点 next = NULL; } void SListDestory(SLTNode** pphead) { SLTNode* cur = *pphead; while (cur) { SLTNode* next = cur->next; free(cur); cur = next; } // 这里一定要置空，放置销毁链表后被误使用 *pphead = NULL; }
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "SList.h" // 测试尾插、带节点的头插 void TestList1() { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPushBack(&plist, 5); SListPrint(plist); SListPushFront(&plist, 1); SListPushFront(&plist, 2); SListPushFront(&plist, 3); SListPushFront(&plist, 4); SListPushFront(&plist, 5); SListPrint(plist); } // 测试头插、尾删 void TestList2() { SLTNode* plist = NULL; SListPushFront(&plist, 1); SListPushFront(&plist, 2); SListPushFront(&plist, 3); SListPushFront(&plist, 4); SListPushFront(&plist, 5); SListPrint(plist); SListPopBack(&plist); SListPopBack(&plist); SListPopBack(&plist); SListPopBack(&plist); SListPopBack(&plist); //SListPopBack(&plist); SListPrint(plist); } // 测试头删 void TestList3() { SLTNode* plist = NULL; SListPushFront(&plist, 1); SListPushFront(&plist, 2); SListPushFront(&plist, 3); SListPushFront(&plist, 4); SListPushFront(&plist, 5); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); } //void TestList4() //{ // SLTNode* plist = NULL; // // SListPushFront(&plist, 1); // SListPushFront(&plist, 2); // SListPushFront(&plist, 3); // SListPushFront(&plist, 2); // SListPushFront(&plist, 5); // // SLTNode* pos = SListFind(plist, 2); // int i = 1; // while (pos) // { // printf("第%d个pos节点：%p->%d\n", i++, pos, pos->data); // pos = SListFind(pos->next, 2); // } // // // 修改 3->30 // pos = SListFind(plist, 3); // if (pos) // { // pos->data = 30; // } // SListPrint(plist); //} void TestList5() { SLTNode* plist = NULL; SListPushFront(&plist, 1); SListPushFront(&plist, 2); SListPushFront(&plist, 3); SListPushFront(&plist, 2); SListPushFront(&plist, 5); // 3前面插入一个30 SLTNode* pos = SListFind(plist, 3); if (pos) { SListInsert(&plist, pos, 30); } SListPrint(plist); // 5前面插入一个10 pos = SListFind(plist, 5); if (pos) { SListInsert(&plist, pos, 10); } SListPrint(plist); } int main() { //TestList1(); //TestList2(); //TestList3(); TestList5(); return 0; }
到这里本篇博客就到此结束了，仔细阅读这篇文章，你会发现，链表其实也没有那么难！
但是光看懂了还不够，链表是一个面试常考点，所以是十分重要的！于是在接下来几期，anduin 会带着大家一起刷链表的OJ题，多写多练，手撕链表~
更多精彩内容敬请期待~
如果觉得anduin写的还不错的话，还请一键三连！如有错误，还请指正！
我是anduin，一名C语言初学者，我们下期见！
