以无头单向不循环链表为例
1.整体布局
1.链表的打印
void SLTPrint(SLNode* phead);
2.创造结点
SLNode* CreateNode(SLNDataType x)
3.尾插结点
void SLTPushBack(SLNode** pphead, SLNDataType x);
4.头插结点
void SLTPushFront(SLNode** pphead, SLNDataType x);
5.尾删节点
void SLTPopBack(SLNode** pphead);
6.头删结点
void SLTPopFront(SLNode** pphead);
7.查找结点
SLNode* SLTFind(SLNode* phead, SLNDataType x);
8.任意位置pos之前插入节点
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x);
9.删除任意位置pos前的结点
void SLTErase(SLNode** pphead, SLNode* pos);
10.任意位置pos之前后插入节点
void SLTInsertAfter(SLNode* pos, SLNDataType x);
11.删除任意位置pos后的结点
void SLTEraseAfter(SLNode* pos);
12.单链表的销毁
void SLTDestroy(SLNode * *pphead);
别着急，我们先看一下整体的代码组成，后面有每一部分的详解
2.总体代码
1.SList.h部分
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLNDataType; // Single List typedef struct SListNode { SLNDataType val; struct SListNode* next; }SLNode; void SLTPrint(SLNode* phead); void SLTPushBack(SLNode** pphead, SLNDataType x); void SLTPushFront(SLNode** pphead, SLNDataType x); void SLTPopBack(SLNode** pphead); void SLTPopFront(SLNode** pphead); SLNode* SLTFind(SLNode* phead, SLNDataType x);//查找 // pos之前插入 void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x); // 删除pos位置 void SLTErase(SLNode** pphead, SLNode* pos); // void SLTInsertAfter(SLNode* pos, SLNDataType x); void SLTEraseAfter(SLNode* pos); void SLTDestroy(SLNode * *pphead);
2.SList.c部分
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLNDataType; // Single List typedef struct SListNode { SLNDataType val; struct SListNode* next; }SLNode; void SLTPrint(SLNode* phead); void SLTPushBack(SLNode** pphead, SLNDataType x); void SLTPushFront(SLNode** pphead, SLNDataType x); void SLTPopBack(SLNode** pphead); void SLTPopFront(SLNode** pphead); SLNode* SLTFind(SLNode* phead, SLNDataType x);//查找 // pos之前插入 void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x); // 删除pos位置 void SLTErase(SLNode** pphead, SLNode* pos); // void SLTInsertAfter(SLNode* pos, SLNDataType x); void SLTEraseAfter(SLNode* pos); void SLTDestroy(SLNode * *pphead);
2.SList.c部分
#include"SList.h" void SLTPrint(SLNode* phead) { SLNode* cur = phead;// while (cur != NULL) { printf("%d->", cur->val); cur = cur->next; } printf("NULL\n"); } SLNode* CreateNode(SLNDataType x) { SLNode* newnode = (SLNode*)malloc(sizeof(SLNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->val = x; newnode->next = NULL; return newnode; } void SLTPushBack(SLNode** pphead, SLNDataType x) { assert(pphead); SLNode* newnode = CreateNode(x); if (*pphead == NULL)//*pphead就是plist { *pphead = newnode;//改变结构体成员 } else { // 找尾 SLNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } } void SLTPushFront(SLNode** pphead, SLNDataType x)//头插一个链表 { assert(pphead); SLNode* newnode = CreateNode(x); newnode->next = *pphead; *pphead = newnode; } void SLTPopBack(SLNode** pphead)//尾删：时间复杂度为O(N); { // 温柔的检查 //if (*pphead == NULL)//不能为空 // return; assert(pphead); // 空 assert(*pphead); // 1、一个节点 // 2、一个以上节点 if ((*pphead)->next == NULL)//一个节点 { free(*pphead); *pphead = NULL; } else//一个以上节点 { // 找尾——常规型 /*SLNode* prev = NULL;//找尾的前一个 SLNode* tail = *pphead; while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); tail = NULL; prev->next = NULL;*/ SLNode* tail = *pphead; while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } } void SLTPopFront(SLNode** pphead)//头删 { assert(pphead); // 空 assert(*pphead); 一个以上节点 + 一个 //SLNode* tmp = (*pphead)->next; //free(*pphead); //*pphead = tmp; // 一个以上节点 + 一个 SLNode* tmp = *pphead; *pphead = (*pphead)->next; free(tmp); } SLNode* SLTFind(SLNode* phead, SLNDataType x)//查找 { SLNode* cur = phead; while (cur) { if (cur->val == x) { return cur; } else { cur = cur->next; } } return NULL; } void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x) assert(pphead); assert(pos); assert(*pphead); if (*pphead == pos) { // 头插 SLTPushFront(pphead, x); } else//中间插入或者尾插要找pos前一个结点 { SLNode* prev = *pphead;//头结点 while (prev->next != pos)//找前一个 { prev = prev->next; } SLNode* newnode = CreateNode(x); prev->next = newnode; newnode->next = pos; } } void SLTErase(SLNode** pphead, SLNode* pos)//pos位置前面删除 { assert(pphead); assert(*pphead); assert(pos); if (*pphead == pos) { // 头删 SLTPopFront(pphead); } else//中间插入或者尾插要找pos前一个结点 { SLNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } } void SLTInsertAfter(SLNode* pos, SLNDataType x)//pos位置后面插入 { assert(pos); SLNode* newnode = CreateNode(x); newnode->next = pos->next;//注意顺序 pos->next = newnode; } void SLTEraseAfter(SLNode* pos)//pos位置下一个节点删除 { assert(pos); assert(pos->next); SLNode* tmp = pos->next;//注意顺序 pos->next = pos->next->next; free(tmp); tmp = NULL; } void SLTDestroy(SLNode** pphead)//清空所有节点 { assert(pphead); SLNode* cur = *pphead; while (cur) { SLNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
3.Test.c部分
#include"SList.h" void TestSLT1() { SLNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); //SLTPopBack(&plist); //SLTPrint(plist); } void TestSLT2() { SLNode* plist = NULL; SLTPushFront(&plist, 1); SLTPushFront(&plist, 2); SLTPushFront(&plist, 3); SLTPushFront(&plist, 4); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); SLNode* pos = SLTFind(plist, 3); SLTInsert(&plist, pos, 30); } void TestSLT3() { SLNode* plist = NULL; //SLTInsert(&plist, NULL, 1); SLTPushFront(&plist, 1); SLTPushFront(&plist, 2); SLTPushFront(&plist, 3); SLTPushFront(&plist, 4); SLTPrint(plist); SLNode* pos = SLTFind(plist, 4); SLTInsert(&plist, pos, 40); SLTPrint(plist); pos = SLTFind(plist, 2); SLTInsert(&plist, pos, 20); SLTPrint(plist); //pos = SLTFind(plist, 200); //SLTInsert(&plist, pos, 2); } void TestSLT4() { SLNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPrint(plist); SLNode* pos = SLTFind(plist, 1); SLTErase(&plist, pos); SLTPrint(plist); pos = SLTFind(plist, 3); SLTErase(&plist, pos); SLTPrint(plist); } void TestSLT5() { SLNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPrint(plist); SLNode* pos = SLTFind(plist, 1); SLTInsertAfter(pos, 10); SLTPrint(plist); SLTDestroy(&plist); } int main() { TestSLT5(); return 0; } struct ListNode { struct ListNode* next; int val; }; struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* prev = NULL; struct ListNode* cur = head; //while(cur != NULL) while (cur) { if (cur->val == val) { struct ListNode* next = cur->next; free(cur); if (prev) prev->next = next; cur = next; } else { prev = cur; cur = cur->next; } } return head; } int main() { struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode)); n1->val = 7; n2->val = 7; n3->val = 7; n4->val = 7; n1->next = n2; n2->next = n3; n3->next = n4; n4->next = NULL; struct ListNode* head = removeElements(n1, 7); return 0; }
3.牢记
当前作用域的变量出了作用域就会自动销毁
类型
pphead SLNode** 对应的是外部的plist的地址，地址不可能为空，为空就是错误
*pphead SLNode* 对应的是外部的plist,若为空代表没有节点的空链表
(*pphead)->next SLNode* 若为空代表只有一个节点的链表
4.细致讲解
1.链表的打印
该函数为打印单链表的函数，接受一个单链表头节点指针作为参数，无返回值。函数使用了一个指针变量 cur 来遍历整个链表，每次打印当前节点的值，并将指针指向下一个节点，直到遍历完整个链表。最后打印 "NULL" 作为链表末尾的标志。
void SLTPrint(SLNode* phead)//链表打印 { SLNode* cur = phead; while (cur != NULL) { printf("%d->", cur->val); cur = cur->next; } printf("NULL\n"); }
2.创造结点
这段代码是一个函数，用于创建一个单向链表节点（SLNode），输入参数为节点值（x），返回值为创建的节点指针。
首先，通过malloc函数分配一个大小为SLNode结构体大小的内存空间，并将其强制转换为SLNode类型指针newnode
然后，给新节点newnode的val成员赋值为输入参数x，next成员赋值为NULL。
最后，返回新节点newnode的指针。如果malloc分配内存失败，则打印出错信息并结束程序。
SLNode* CreateNode(SLNDataType x) //创作结点 { SLNode* newnode = (SLNode*)malloc(sizeof(SLNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->val = x; newnode->next = NULL; return newnode; }
3.尾插结点
本函数实现了在单链表中进行尾插操作。函数的参数包括链表的头结点指针的地址pphead和待插入数据x。函数内部首先判断pphead是否为空指针，如果为空，则直接将新结点作为链表的头结点；否则则遍历链表找到尾结点，将尾结点的next指针指向新结点。需要注意的是，由于函数需要修改外部结构体指针的值，因此使用二级指针进行传参。
void SLTPushBack(SLNode** pphead, SLNDataType x)//尾插一个链表 //pphead是SLNode*的地址 //改变外部结构体指针SLNode*要用要用二级指针SLNode** { assert(pphead); SLNode* newnode = CreateNode(x); if (*pphead == NULL)//*pphead就是plist { *pphead = newnode;//改变结构体成员 } else { // 找尾 SLNode* tail = *pphead;//定义一个* tail的指针 while (tail->next != NULL) //链表里的插入一定是让上一个结点指向下一个结点，存下一个结点的地址 //找到下一个节点 tail->next != NULL 为了让 tail->next指向newnode(空NULL) { tail = tail->next; } tail->next = newnode; //改变结构体指针 //改变外部结构体SLNode*要用要用一级指针SLNode* } }
4.头插结点
该函数实现了在单向链表的头部插入一个新的节点，其参数为pphead表示指向一个指针的指针，即指向头节点的指针的地址；x表示要插入节点的数据。
函数首先进行参数的断言判断，确保pphead不为空指针。
然后创建一个新的节点，并将其数据域赋值为x。
接着将新节点的next指向原头节点，再将pphead指向新节点，这样就完成了在头部插入新节点的操作。
值得注意的是，在单向链表中，头节点不存储数据，只用于指向链表的第一个真正存储数据的节点，所以新节点的next指向原头节点。
void SLTPushFront(SLNode** pphead, SLNDataType x)//头插一个链表 { assert(pphead); SLNode* newnode = CreateNode(x); newnode->next = *pphead; *pphead = newnode; }
5.尾删节点
该函数是单链表的尾删操作，时间复杂度为O(N)。
在函数中，首先进行了两个断言的检查，确保传入的指针和指针指向的结点不为空。
接着，根据单链表中结点的个数进行区分处理：
如果单链表中只有一个结点，直接将该结点释放并将头指针置空即可。
如果单链表中有多个结点，需要先找到最后一个结点，然后将该结点进行释放，并将其前一个结点的 next 指针置空。常规方法是使用两个指针进行循环遍历，找到最后一个结点，但这里使用了一个指针 tail 进行遍历，找到倒数第二个结点，并进行释放操作。
void SLTPopBack(SLNode** pphead)//尾删：时间复杂度为O(N); { // 温柔的检查 //if (*pphead == NULL)//不能为空 // return; assert(pphead); // 空 assert(*pphead); // 1、一个节点 // 2、一个以上节点 if ((*pphead)->next == NULL)//一个节点 { free(*pphead); *pphead = NULL; } //指针指向一个不属于你的空间或者释放的空间就会变成野指针 else//一个以上节点 { // 找尾——常规型 /*SLNode* prev = NULL;//找尾的前一个 SLNode* tail = *pphead; while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); tail = NULL; prev->next = NULL;*/ SLNode* tail = *pphead; while (tail->next->next != NULL)//tail指向为最后一个结点的前一个结点 { tail = tail->next; } free(tail->next); tail->next = NULL; } }
6.头删结点
函数名：SLTPopFront
参数：SLNode** pphead，传入一个指向链表头指针的指针。
功能：删除链表头节点。
返回值：无。
函数实现：
assert(pphead); 断言传入指针不为空。
assert(*pphead); 断言链表不为空。
保存头节点指针 tmp = *pphead。
将头节点指针指向下一个节点 *pphead = (*pphead)->next。
释放原头节点 tmp。
函数结束。
void SLTPopFront(SLNode** pphead)//头删 { assert(pphead); // 空 assert(*pphead); 一个以上节点 + 一个 //SLNode* tmp = (*pphead)->next; //free(*pphead); //*pphead = tmp; // 一个以上节点 + 一个 SLNode* tmp = *pphead; *pphead = (*pphead)->next;//先指向下一个，再释放，防止因为头删使*pphead变为野指针 free(tmp); }
7.查找结点
该函数是为了在一个单链表中查找值为x的节点，并返回该节点的指针（SLNode*）。
函数的参数为phead，即单链表的头节点指针，和x，即要查找的节点的值。
函数首先定义一个cur指针指向头节点phead。
然后，while循环遍历整个单链表，如果当前节点的值等于x，就返回该节点的指针；否则，就将指针cur指向下一个节点。
如果整个单链表中没有值为x的节点，就返回NULL。
注意：本函数只能返回第一个值为x的节点的指针，如果链表中有多个值为x的节点，只会返回第一个。
SLNode* SLTFind(SLNode* phead, SLNDataType x)//查找 { SLNode* cur = phead; while (cur) { if (cur->val == x) { return cur; } else { cur = cur->next; } } return NULL;//如果没有这个节点就返回NULL }
8.任意位置pos之前插入节点
这是一个单链表的插入函数，可以将一个新节点插入到链表中任意一个节点的位置。
函数的参数为指向指针的指针pphead（链表的头指针），待插入节点的位置pos和待插入节点的值x。
首先进行参数检查，确保传入的参数都有效。
如果待插入节点的位置是链表头节点，即pos == *pphead，则进行头插操作，调用SLTPushFront函数实现。头插需要修改链表头指针，因此传入pphead的地址。
否则，进行中间插入或尾插操作，需要找到待插入节点的前一个节点。可以从链表头节点开始依次向后遍历，直到找到pos的前一个节点为止。
创建新节点，将前一个节点的next指针指向新节点，新节点的next指针指向pos，完成插入操作。
最后，由于插入操作可能会修改链表头指针，因此需要保证pphead的值一直指向链表的头节点。
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)//pos前面插入 { // 严格限定pos一定是链表里面的一个有效节点 assert(pphead); assert(pos); assert(*pphead); if (*pphead == pos) { // 头插 SLTPushFront(pphead, x); } else//中间插入或者尾插要找pos前一个结点 { SLNode* prev = *pphead;//头结点 while (prev->next != pos)//找前一个 { prev = prev->next; } SLNode* newnode = CreateNode(x); prev->next = newnode; newnode->next = pos; } }
9.删除任意位置pos前的结点
该函数的作用是删除单链表中指定位置(即pos的前一个位置)的结点，实现时需要注意以下几点：
首先需要对函数参数进行断言，确保传入的参数有效。
若要删除的结点为头结点，则执行SLTPopFront函数实现头删。
若要删除的结点为中间结点或者尾结点，则需要先找到要删除结点的前一个结点prev，然后让prev的next指向pos的next，最后释放pos结点所占用的内存空间。
在删除结点前需要确保单链表不为空。
总之，该函数的核心思想是找到要删除的结点的前一个结点，然后通过修改前一个结点的指针来实现删除操作。
void SLTErase(SLNode** pphead, SLNode* pos)//pos位置前面删除 { assert(pphead); assert(*pphead); assert(pos); if (*pphead == pos) { // 头删 SLTPopFront(pphead); } else//中间插入或者尾插要找pos前一个结点 { SLNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } }
10.任意位置pos之前后插入节点
这是一个单链表的插入函数，在链表的 pos 位置后面插入一个值为 x 的节点。
首先，需要判断 pos 指针是否为空，如果为空，说明链表为空，直接返回。
创建一个节点 newnode，值为 x。
将 newnode 的 next 指针指向 pos 的 next 指针所指向的节点，这里需要注意顺序，先赋值 next 指针再插入节点。
将 pos 的 next 指针指向 newnode，这样就完成了节点的插入。
void SLTInsertAfter(SLNode* pos, SLNDataType x)//pos位置后面插入 { assert(pos); SLNode* newnode = CreateNode(x); newnode->next = pos->next;//注意顺序 pos->next = newnode; }
11.删除任意位置pos后的结点
这是一个单链表中删除pos位置下一个节点的函数实现。具体解析如下：
1. 确定删除节点位置：函数参数为pos，pos表示要删除节点的前一个节点，所以要先判断pos及其下一个节点是否存在。
2. 记录删除节点：用一个临时指针tmp来记录要删除的节点，方便后续释放节点内存。
3. 删除节点：将pos指向tmp的下一个节点，即pos->next = pos->next->next，就可以将tmp节点从链表中删除了。
4. 释放内存：使用free()函数释放tmp节点的内存，并将tmp指针置为NULL。
注意事项：在删除节点时，要注意顺序，先记录要删除的节点，再删除节点；在释放内存后，要将指针置为NULL，避免野指针的产生。
void SLTEraseAfter(SLNode* pos)//pos位置下一个节点删除 { assert(pos); assert(pos->next); SLNode* tmp = pos->next;//注意顺序 pos->next = pos->next->next; free(tmp); tmp = NULL; }
12.单链表的销毁
这是一个销毁单链表的函数实现，函数接收一个指向指针的指针参数 pphead，指向链表头节点的地址。
首先使用 assert 函数判断 pphead 是否为 NULL，保证程序的健壮性。然后定义 cur 指针指向头节点。
使用循环遍历整个链表，每次都将 cur 指向的节点释放，并将 cur 指向下一个节点。释放当前节点后，要保留下一个节点的指针，否则无法继续遍历下去。
循环结束后，将原来的头指针 *pphead 赋值为 NULL，表示整个链表已经销毁。
void SLTDestroy(SLNode** pphead)//清空所有节点 { assert(pphead); SLNode* cur = *pphead; while (cur) { SLNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
5.单链表的缺陷
1.操作时需要对头节点进行特殊处理，增加了代码的复杂度。
2.插入和删除节点时需要遍历链表找到前一个节点，耗费时间和空间。
3.无法有效处理空链表的情况，因为没有头节点可以代表一个空链表，这使得在对空链表进行操作时会出现问题。
4.无法遍历链表的最后一个节点，因为最后一个节点没有指针指向下一个节点，必须使用其他方式来判断是否到达链表的末尾，比如使用哨兵节点。
