一.无头链表的实现
- 我们上回链表的接口功能实现到了尾插和尾删，我们下面接着上回的内容继续我们链表的学习。
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLTDataType; typedef struct SListNode { SLTDataType Data; struct SListNode * next; }SLTNode; //打印链表 void SLTPrint(SLTNode* phead); //初始化链表 SLTNode* BuySListNode(SLTDataType x); void SLTPushBack(SLTNode** pphead, SLTDataType x); void SLTPushFront(SLTNode** pphead, SLTDataType x); void SLTPopBack(SLTNode** pphead); void SLTPopFront(SLTNode** pphead); // 找某个数 SLTNode* SLTFind(SLTNode* phead, SLTDataType x); // 在pos之前插入x void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); // 在pos以后插入x void SLTInsertAfter(SLTNode* pos, SLTDataType x); // 删除pos位置 void SLTErase(SLTNode** pphead, SLTNode* pos); // 删除pos的后一个位置 void SLTEraseAfter(SLTNode* pos); //修改pos位置的值 void SLTModify(SLTNode**pphead, SLTNode* pos, SLTDataType x); // 单链表的销毁 void SListDestroy(SLTNode** pphead);
1.查找某个节点 SLTFind以及修改某个节点的数 SLTModify
查找某个节点是否存在
//找某个节点是否存在 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; while (cur) { if (cur->Data == x) return cur; cur = cur->next; } printf("该节点不存在\n"); return NULL; }
- 对于查找来说，我们只需要遍历一下链表依次比较一下每个节点存放的Data是否与我要找的x相等即可，如果到最后都不相等，说明链表中没有该节点
修改某个节点的数
//修改某个节点的值 void SLTModify(SLTNode** pphead, SLTNode* pos, SLTDataType x) { pos->Data = x; }
- 这个与上面的查找函数联动即可，我先找到这个节点是否存在，如果能找到，我就把该节点的Data改为我想要的x就行。
- 示例如下：
void TestSList2() { int n = 0; int x = 0; printf("请输入需要定义的链表的长度：\n"); scanf("%d", &n); printf("请输入需要放入链表中的元素，中间用空格隔开\n"); SLTNode* plist = NULL; int val = 0; for (size_t i = 0; i < n; i++) { scanf("%d", &val); SLTPushBack(&plist, val); } SLTPrint(plist); //SLTFind(plist, 5); printf("请输入要修改的值\n"); scanf("%d", &x); SLTNode* pos = SLTFind(plist, x); if (pos) { int m; printf("请输入要把该节点修改成什么值：\n"); scanf("%d", &m); SLTModify(&plist, pos, m); } SLTPrint(plist); }
2.在pos之前插入值 SLTInsert与在pos之后插入值 SLTInsertAfter
在pos之前插入值
// 在pos之前插入x void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { SLTNode* cur = *pphead; SLTNode* newnode = BuySListNode(x); //如果没有节点时就得头插 assert(pphead); assert(pos); if (pos == *pphead) { SLTPushFront(pphead, x); } else { while (cur->next) { if (cur->next->Data == pos->Data) { cur->next = newnode; newnode->next = pos; } cur = cur->next; } } }
- 特殊情况的分析：
- 在pos之前插入我们得考虑这些地方：1，pos是否合法？ 2.pphead是否为空
- 当我们判断完上面两个后，我们现在就要考虑pos的特殊插入了，如果我们pos就在链表头部时，
- 此时我们的pos之前插入就相当于我们的头插，如果不是，我们来通过逻辑图分析一下一般情况
在pos后插入x
// 在pos以后插入x void SLTInsertAfter(SLTNode* pos, SLTDataType x) { SLTNode* cur = BuySListNode(x); cur->next = pos->next; pos->next = cur; }
- 这部分就比较简单啦，我们通过与之前的SLTFind找到pos的位置，把它next里下一个节点的地址给我们要插入的cur，再让pos的next指向cur就行了。
3.删除pos位置的值 SLTErase以及删除pos下一位的值 SLTEraseAfter
删除pos位置的值
// 删除pos位置 void SLTErase(SLTNode** pphead, SLTNode* pos) { SLTNode* cur = *pphead; assert(pos); assert(pphead); if (pos == *pphead) { SLTPopFront(pphead); } else { while (cur) { if (cur->next == pos) { cur->next = pos->next; free(pos); } cur = cur->next; } } }
- 对于断言的分析同上这里不赘述，我们这里是删除，当pos在表头时，删除这个节点，就是我们的头删，当一般情况时，逻辑分析图如下：
删除pos后一位的值
// 删除pos的后一个位置 void SLTEraseAfter(SLTNode* pos) { assert(pos); //检查是否是尾节点 assert(pos->next); pos->next = pos->next->next; free(pos->next); pos->next = NULL; }
- 这个我们既然知道pos了，想删除pos的下一个直接把pos的next指向下一个节点的next即可，最后再free(pos->next),然后置空。
4.单链表的销毁
- 当我们的链表用完后，由于我们的单链表是动态开辟的，所以也需要free释放一下然后置空。
// 单链表的销毁 void SListDestroy(SLTNode** pphead) { assert(pphead); SLTNode* cur = *pphead; while (cur) { SLTNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
- 通过遍历的方式把每个节点都给free释放，最后把头指针置空，链表销毁。
总结
- 由于篇幅有限，今天的内容到这里就结束了，本篇我们把剩下没讲的接口讲完了，之后会再带大家做几道oj题让大家更加熟悉链表的实际应用。
- 相信如果你能一直跟着坚持下去那么你链表这一块的初阶知识就一定没什么问题啦！切记要自己上手敲敲代码哦！
- 好了，如果你有任何疑问欢迎在评论区或者私信我提出，大家下次再见啦！
