单链表——C语言实现
目次一.相关指针知识点
二.链表
1.为什么学了顺序表还要学链表
2.优点
三.实现
1.链表的打印 —— 理解链表结构
(2) 物理结构图
2.链表的尾插 —— 入门
错误写法：tail != NULL
总结：
精确代码物理图解：
(2) 尾插团体代码 (思考对吗?)
Bug
3.头插
4.尾删
Bug
5.头删
6.查找
7. Find 查找的功能
（1）pos 之前插入
（2）pos 位置删除
（3）pos 之后插入
（4）pos位置后面删除
四.头脑提升
五.总结
1.传什么？
2.要不要断言？
（1）打印、查找
（2）pphead
（3）*pphead
六.团体代码
SList.h
SList.c
一.相关指针知识点
调用一个函数，就会建立一个空间，这个空间叫栈帧。局部变量是存放在栈帧里的（除了static修饰的局部变量）。函数竣事，栈帧空间就烧毁，局部变量也烧毁
函数传参，不管是传值，还是传地址，实在都是拷贝。就看拷贝值还是地址。
代码1：y 的改变，不会改变 x 的值
void Func(int y)
{
y = 1;
}
int main()
{
int x = 0;
Func(x);
return 0;
} 这是两个栈帧，Func 里面是 y，main 里面是 x。x 传给 y 是拷贝给 y，y 的改变不会影响 x，而且 Func 会烧毁
https://i-blog.csdnimg.cn/direct/065a1b9384ad4ce8a24fdd5bd33b7f93.png
代码2：办理上面题目，传地址。改变的是 int ，使用的是 int 的指针
void Func(int* p)
{
*p = 1;
}
int main()
{
int x = 0;
Func(&x);
return 0;
} 这里的 p 是 x 地址的拷贝。在传参里面，我们要改变什么，就要用它的指针。然后 * 解引用可以改变
https://i-blog.csdnimg.cn/direct/967019e2b8524b74b5a2fec4393c5383.png
代码3：
void Func(int* ptr)
{
ptr = (int*)malloc(sizeof(int));
}
int main()
{
int* px = NULL;
Func(px);
free(px); // 加上也没用
return 0;
} 这也是拷贝值，把 px 的值拷贝给 ptr，ptr 是空。但是我 malloc 了一块空间，让 ptr 指向这块空间。
px 拷贝给 ptr，ptr 的改变不会影响 px 。而且出了作用域 Func 烧毁，malloc 的内存块还找不到了（内存泄漏），就算 free 也 free 不到
https://i-blog.csdnimg.cn/direct/336cdd5053704e1f924b57184dfeee73.png
这里我们要改变的是 int* ，不是 int 。传 int* 不起作用。应该传 int**（二级指针）
代码4：改变 int* ，使用 int* 的地址，int**（二级指针）
void Func(int** pptr)
{
*pptr = (int*)malloc(sizeof(int));
}
int main()
{
int* px = NULL;
Func(&px);
free(px);
return 0;
} 这里把 px 的地址传过去，pptr 指向 px 。malloc了一块空间，是让 *pptr 即 px 指向这块空间
Func 竣事，栈帧烧毁。但 px 还指向这块空间，free 可以 free 到。这里内存开释，值也拿返来了
https://i-blog.csdnimg.cn/direct/a2ea727a4b1d4381b3dd01d3446f7d3b.png
二.链表
1.为什么学了顺序表还要学链表
顺序表是有许多缺陷的：
（1）中间,头部 插入,删除数据，必要挪动数据，服从低下。你也不可能说在中间插入一块空间，没有这种概念，这本来就是一块一连的空间。
（2）空间不敷必要扩容，拷贝数据，开释旧空间。会有不小的消耗
扩容有一定的服从消耗。原地扩还好，异地扩呢？
还可能会有一定的空间浪费。一次扩太少，会频繁扩；一次扩太多，浪费
能不能说，我用一点给一点呢？存一块数据，开一块空间
可以，但怎么管理呢？
顺序表里，开了整片空间，由于存放的数据是一连的，只必要记录这块空间最开始的地址。
现在要一块空间，去 malloc 。多次 malloc ，他们之间的地址不能保证相邻。
这时候，链表会用一个指针指向第一个内存块（节点 Node）。
为了通过第一个能找到第二个怎么办？上一个会存下一个的地址，上一个指向下一个。
什么时候竣事？顺序表是 size 。链表里末了一个节点的指针存 NULL 即可
2.优点
不必要扩容。存一块，开一块。
可以从中间插入，不必要挪动数据。
顺序表，链表是互补，相辅相成的。许多情况是共同起来使用的
三.实现
上面的理解，链表是一个个的内存块，再由指针链接起来
先来界说它的结构：从语言的角度来说，凡是有多个数据，都要存到结构体里面
为方便替换成其他范例的数据，我们将范例统一重命名为 SLTDataType
1.链表的打印 —— 理解链表结构
SList.h
上一个节点要存下一个节点的地址，每个节点都是结构体范例，以是存结构体指针 next
链表要有个头指针 phead 指向第一个节点，判定竣事只必要走到空 NULL 即可。
不能断言 phead 为空，空链表也可以打印
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
//打印链表
void SLTPrint(SLTNode* phead); SList.c
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
//while (cur->next != NULL) 错误写法！！！
//while(cur != NULL)
while (cur)
{
printf("%d->", cur->data);
cur = cur->next; // 指向下一个位置
// 不能写成 ++cur;
}
printf("NULL\n");
}
问：为什么不能写成 ++cur ？
答：链表地址不一连，++cur 不能保证它指向下一个位置。如果强行把地址弄成一连，不就成顺序表了吗？
怎么理解 cur = cur->next；
cur 是结构体指针，cur-> 就是访问结构体成员。next 是结构体成员，是下一个节点的地址
赋值操纵是把下一个节点的地址给 cur
https://i-blog.csdnimg.cn/direct/cbe1a605d8df40b0bb6e8e891f4ead7a.png
为什么循环判定条件 cur->next != NULL 为错？
cur->next 是下一节点地址。走到尾就竣事了，没有打印末了的数据
https://i-blog.csdnimg.cn/direct/b31fa28596784714b916dd894c63452a.png
(2) 物理结构图
上面画的是逻辑结构图，是为方便理解，形象画出来的
物理结构图：实实在在数据在内存中的变化
https://i-blog.csdnimg.cn/direct/6dd815d704b34fa787c4502020c7869f.png
2.链表的尾插 —— 入门
依然不能断言 phead 为空。为空（没有数据）依然可以尾插
顺序表尾插，先要判定空间够不敷，不敷扩容。 链表不用，永远有空间
第一步：搞个节点，并初始化。后面多次用到，分装成函数
第二步：找尾。 尾的特征：tail->next == NULL
// 搞节点，并初始化
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
// 初始化
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SLTPushBack(SLTNode* phead, SLTDataType x) // 思考这里对吗？
{
SLTNode* newnode = BuySLTNode(x);
// 找尾
SLTNode* tail = phead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
} 错误写法：tail != NULL
// 找尾
SLTNode* tail = phead;
while (tail != NULL)
{
tail = tail->next;
}
tail = newnode; 从逻辑结构图角度，看似精确：
https://i-blog.csdnimg.cn/direct/8cc45a74aaa04168861e0d3f264ffb6c.png
从物理结构图理解：
https://i-blog.csdnimg.cn/direct/6a562202cb2745c98da4627e391ce81b.png
https://i-blog.csdnimg.cn/direct/e55f0dc3e440494fbe69cf3b3d34effb.png
https://i-blog.csdnimg.cn/direct/ad26aa0b760146eb94c5458d02af5720.png
tail ，newnode 都是局部变量，出了作用域烧毁
https://i-blog.csdnimg.cn/direct/ace3648582134656bcfa025c6bceae41.png
上一个节点没有存下一个节点的地址，链接失败
总结：
tail 是个局部变量。不应该赋值给 tail 。应该赋值给 tail 指向的结构体(存放下一个节点地址的)成员
不为空链表尾插的本质：原尾节点中要存新的尾节点的地址
精确代码物理图解：
// 找尾
SLTNode* tail = phead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode; https://i-blog.csdnimg.cn/direct/d1848e40a36c4e928b27132380e1117b.png
https://i-blog.csdnimg.cn/direct/92773a4b4af148138a7fd10a8100ad38.png
https://i-blog.csdnimg.cn/direct/ff826466af644b24a7335381959400fa.png
tail ，newnode 都是局部变量，出了作用域烧毁
https://i-blog.csdnimg.cn/direct/121627f52bd4492c9d2c61b14ac45cda.png
上一个节点存储下一个节点的地址，链接成功
(2) 空链表尾插
phead == NULL tail = phead 让 phead 指向新节点即可
https://i-blog.csdnimg.cn/direct/682a00529c624598ba9ac30350b39bb6.png
(2) 尾插团体代码 (思考对吗?)
SList.h
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
//打印链表
void SLTPrint(SLTNode* phead);//尾插void SLTPushBack(SLTNode* phead, SLTDataType x); // 思考这里对不对 SList.c
void SLTPushBack(SLTNode* phead, SLTDataType x) // 对吗？
{
SLTNode* newnode = BuySLTNode(x);
if (phead == NULL)
{
phead = newnode;
}
else
{
// 找尾
SLTNode* tail = phead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
} Test.c
void TestSList1()
{
SLTNode* plist = NULL;
SLTPushBack(plist, 1);
SLTPushBack(plist, 2);
SLTPushBack(plist, 3);
SLTPushBack(plist, 4);
SLTPrint(plist);
} Bug
我们运行上面的代码：https://i-blog.csdnimg.cn/direct/bc35b7edc4ff44d3a1ad05196596aa3c.png
看下图，phead 和 newnode 都是结构体指针范例的指针变量
phead = newnode 是赋值行为，其真正寄义是让 phead 也指向 newnode 指向的新节点
函数竣事，栈帧空间烧毁。我们的目标是让 plist 指向新节点，但末了没有，造成了内存泄漏
https://i-blog.csdnimg.cn/direct/a041e1e2445f4999ac80bd7f54a6b74f.png
改Bug
我们要改变 SLNode* plist ，传参里要传 SLNode* plist 的地址 ，用 SLNode** 接收
SList.h
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
//打印链表
void SLTPrint(SLTNode* phead);//尾插void SLTPushBack(SLTNode** pphead, SLTDataType x); SList.c
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
// 找尾
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
} pphead 存的是 plist 的指针。*pphead 就是 plist 。
函数竣事，栈帧空间烧毁。plist 指向了新节点
https://i-blog.csdnimg.cn/direct/7bc963c8ffab444097bec82b6692e27f.png
链表运行结果：https://i-blog.csdnimg.cn/direct/cefb0d85010a4796a0c3f836aea7614b.png
3.头插
盲猜头插要用二级指针，因为一定有一个情况是为空，为空肯定要用
https://i-blog.csdnimg.cn/direct/b640197066224295bc6c5dec3231fd20.png
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
} 如果传的是 phead ，改变的就是 phead ，无法改变外边的 plist
这段代码同样可以办理空的情况
4.尾删
SList.c
void SLTPopBack(SLTNode** pphead) // 这么写对吗？
{
assert(pphead);
assert(*pphead);
// 找尾
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
free(tail);
tail = NULL;
} Test.c
void TestSList1()
{
SLTNode* plist = NULL;
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
} Bug
https://i-blog.csdnimg.cn/direct/8893c3b2cd964ca4945a1e452aa0cc60.png 碰上这种情况多半是野指针，调试看看
https://i-blog.csdnimg.cn/direct/c906238232004a869b8faa92c0f52de6.png
尾就是1这个节点，2这个节点存着他的地址
https://i-blog.csdnimg.cn/direct/bcde9054de4f415c938ccf0ec17ba045.png
直接把 tail 指向的尾节点 free 了，前一个节点的 next 就是野指针了。指向已经被开释的空间的指针是野指针
https://i-blog.csdnimg.cn/direct/b5aa6e10d7984c1e84536459e6a0c7b4.png
这里把 tail 置空，不会把前一个节点的 next 置空
前一个节点是结构体，想改变结构体的内容要用结构体指针
修改1
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* prev = NULL;
// 找尾
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
} https://i-blog.csdnimg.cn/direct/82cf43845e0f447c8f166eb890fd6239.png
修改2：找的是倒数第2个
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
// 找尾
SLTNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
} 如果链表删到只剩1个元素，还删。
如果链表本身为空
void TestSList1()
{
SLTNode* plist = NULL;
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
} https://i-blog.csdnimg.cn/direct/61877f0449fb4b0baa34d53836438733.png https://i-blog.csdnimg.cn/direct/4804a484cb26444bbf3826dd32118a40.png
下面用红圈圈起来的是两组代码在只剩1个的情况下，分别有误的地方
https://i-blog.csdnimg.cn/direct/159e8b4fb4464f2d98875cb01993c253.png
修改：只有1个节点，直接 free，plist 置空。不用找尾节点
以是尾删如果用一级指针接收，phead 是 plist 的拷贝，对 phead 置空的改变不影响 plist，达不到置空 plist 的目标，plist 会酿成野指针
void SLTPopBack(SLTNode** pphead)
{
//暴力检查
assert(pphead);
assert(*pphead);
//温柔检查
/*if (*pphead == NULL)
return;*/
if ((*pphead)->next == NULL) // 只有1个节点
{
free(*pphead);
*pphead = NULL;
}
else // 多个节点
{
/*SLTNode* prev = NULL;
// 找尾
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;*/
// 找尾
SLTNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
} 5.头删
不必要单独处理只有1个节点的情况
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* first = *pphead;
*pphead = first->next;
free(first);
first = NULL;
} 6.查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
} 返回的是对应节点的指针，可以用 Find 实现修改
void TestSList2()
{
SLTNode* plist = NULL;
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
SLTPrint(plist);
// 值为2的节点 *2
SLTNode* ret = SLTFind(plist, 2);
ret->data *= 2;
SLTPrint(plist);
} https://i-blog.csdnimg.cn/direct/6544efa215b94b0ca20f90c879551460.png
Find 重要是与下面的功能相共同
7. Find 查找的功能
我们这里不传下标，传结构体指针，与 C++ 贴合
（1）pos 之前插入
为啥不是在 pos 位置插入？ 是把 pos 及以后的数据往后移，以是逻辑上说是之前插入
单链表不得当 pos 之前插入，只得当在后面插入，因为要找到 pos 前一个节点的地址，只能重新找
https://i-blog.csdnimg.cn/direct/7c1126a8e3724ecfb107d51e9e36d6bf.png
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
// 找到 pos 的前一个位置
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos;
prev->next = newnode;
}
} 如果 pos 不是链表里的指针，while 循环停不下来，终极出现空指针
这种情况怎么办 (以致 pos 就是 NULL)？
阐明传错了，断言，起码可以排除 NULL
（2）pos 位置删除
这里 *pphead 可以不停言，pos 间接断言了
pos 不为空，有节点，一定不为空链表
pos 位删除，要找到前一个位置。pos 是头，就是头删，先处理这个特殊情况
https://i-blog.csdnimg.cn/direct/51c60e2633d7457a958350798f2b695f.png
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
assert(*pphead);
if (*pphead == pos)
{
SLTPopFront(pphead);
}
else
{
// 找到 pos 的前一个位置
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
// pos = NULL;
}
} pos = NULL 没用，形参的修改不改变实参。要不要传二级指针呢？不。
为保持和其他的划一性，通常由用的人考虑置空
void TestSList4()
{
SLTNode* plist = NULL;
SLTPushFront(&plist, 1);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 3);
SLTPushFront(&plist, 4);
SLTPrint(plist);
SLTNode* ret = SLTFind(plist, 2);
SLTErase(&plist, ret);
ret = NULL;
SLTPrint(plist);
} https://i-blog.csdnimg.cn/direct/6cf1969938744d5abfa40ec39cd86312.png
（3）pos 之后插入
错误写法：会造成死循环
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
pos->next = newnode;
newnode->next = pos->next;
} https://i-blog.csdnimg.cn/direct/68689337284c4e8e8b3e6c444264a9da.png
精确写法：先改后面
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
} （4）pos位置后面删除
法1：pos->next = pos->next->next; 这里从右往左赋值 橙圈的内容丢了，以是要引入del
https://i-blog.csdnimg.cn/direct/0b7fefce047440699fb3b9e1ec8dcc90.png
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
} 法2：好理解
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
} 四.头脑提升
单链表给了 pos 没给头指针
（1）插入
https://i-blog.csdnimg.cn/direct/8e637b67e0a544e5a8081021950bd0f2.png
（2）删除
没有前一个位置，就删后一个。先换值，后删。但是不能删尾
https://i-blog.csdnimg.cn/direct/0e4369cd88184de3898db200aacc688c.png
五.总结
1.传什么？
我们刚开始拿到链表，plist 是 NULL 。要插入新节点，要让 plist 指向新节点，会改变 plist ，以是要传指针的地址。
删除时，总会删到空，这时要将 plist 置为 NULL ，也改变 plist ，以是也传指针的地址
如果不必要修改头指针的链接，就传一级指针
2.要不要断言？
断言可以排挤显着的错误，制止调试耗时。一定不能为空，就断言
（1）打印、查找
问：是否要 assert 指针 phead 为空？ （一级指针）
答：不要。空的 (没有数据) 的链表，顺序表都可以打印、查找。链表为空时，phead == NULL，断言直接停止程序不合适。
顺序表，链表结构不一样，不能一概而论。
phead 是指向第一个存有数据的节点，链表为空时，phead == NULL
https://i-blog.csdnimg.cn/direct/f150d37606de42449199983f3d7dea8c.png
顺序表的打印
void SLPrint(SL* ps)
{
assert(ps);
for (int i = 0; i < ps->size; ++i)
{
printf("%d ", ps->a);
}
printf("\n");
} 指针 ps 指向结构体 SL ，顺序表的数据不是存储在结构体上。而是存储在结构体里的一个指针 a 指向的空间。纵然顺序表里没有数据，ps 指向的结构体也是必须要有的。ps->a 是否为空也不重要，到底有没有数据，取决于 ps->size 是否为 0
以是对顺序表而言，指针就不能为空
https://i-blog.csdnimg.cn/direct/17b5b4fb004e4b9ca3edd5a03d123581.png
总结：不要看到指针上来就断言
（2）pphead
要，pphead 不能为空。为什么？
pphead 是 plist 的地址。plist 是指针变量，值有可能是空，地址一定不为空
（3）*pphead
*pphead 就是 plist ，是看是否为空 （二级指针）
要不要断言 *pphead 取决于函数是否包涵空链表的情况
先 assert ( pphead ) 后 assert ( *pphead ) 如果反了，先 * ，再查抄，有啥用？
空链表能插入，不停言；不能删，要断言。
六.团体代码
SList.h
#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); // 打印链表
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); // 查找
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); // pos之前插入
void SLTErase(SLTNode** pphead, SLTNode* pos); // pos位置删除
void SLTInsertAfter(SLTNode* pos, SLTDataType x); // pos之后插入
void SLTEraseAfter(SLTNode* pos); // pos位置后面删除 SList.c
#define _CRT_SECURE_NO_WARNINGS 1#include "SList.h"void SLTPrint(SLTNode* phead){ SLTNode* cur = phead; //while (cur->next != NULL) 错误写法！！！ //while(cur != NULL) while (cur) { printf("%d->", cur->data); cur = cur->next; //cur++; 错误写法！！！ } printf("NULL\n");}// 搞新节点，并初始化SLTNode* BuySLTNode(SLTDataType x){ SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail"); return NULL; } // 初始化 newnode->data = x; newnode->next = NULL; return newnode;}void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
// 找尾
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}void SLTPopBack(SLTNode** pphead){ //暴力查抄 assert(pphead); assert(*pphead); //温柔查抄 /*if (*pphead == NULL) return;*/ if ((*pphead)->next == NULL) // 只有1个节点 { free(*pphead); *pphead = NULL; } else // 多个节点 { /*SLTNode* prev = NULL; // 找尾 SLTNode* tail = *pphead; while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); tail = NULL; prev->next = NULL;*/ // 找尾 SLTNode* tail = *pphead; while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; }}void SLTPopFront(SLTNode** pphead){ assert(pphead); assert(*pphead); SLTNode* first = *pphead; *pphead = first->next; free(first); first = NULL;}SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){ assert(pphead); assert(pos); if (pos == *pphead) { SLTPushFront(pphead, x); } else { // 找到 pos 的前一个位置 SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } SLTNode* newnode = BuySLTNode(x); newnode->next = pos; prev->next = newnode; }}void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
assert(*pphead);
if (*pphead == pos)
{
SLTPopFront(pphead);
}
else
{
// 找到 pos 的前一个位置
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
// pos = NULL;
}
}void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}void SLTEraseAfter(SLTNode* pos){ assert(pos); assert(pos->next); //SLTNode* del = pos->next; //pos->next = pos->next->next; //free(del); //del = NULL; SLTNode* del = pos->next; pos->next = del->next; free(del); del = NULL;}
本篇的分享就到这里了，感谢观看，如果对你有帮助，别忘了点赞+收藏+关注。
小编会以本身学习过程中遇到的题目为素材，一连为您推送文章
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]