1.链表的概念及结构

（1）概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。与顺序表的区别在于链表的空间是要一个给一个，不在是内存空间溢出时将内存空间*2.

（2）结构：

struct SListNode
{int data; //节点数据struct SListNode* next; //指针变量⽤保存下⼀个节点的地址
};

链表是由节点组成的，节点包含节点数据和下一个节点的地址。按照顺序打印结构如下。

2.单链表的应用

2.1 打印链表

通过while (pcur)来判断是否到达链表结尾NULL,pcur = pcur->next将下一跳的地址赋值到pcur来达到循环。

void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

2.2申请新节点

定义一个新的结构体指针来完成，用元素的扩容（插入）。

SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->next = NULL;return node;
}

2.3插入（尾删和头删）

为什么要用双指针（SLTNode** pphead）：
使用双指针 SLTNode** pphead，通过 *pphead = newnode 可以直接修改调用者传递的头指针地址，从而更新链表的头节点。如果使用单指针，只能修改局部变量phead的值，无法修改链表的地址。

总结就是，pphead只是形参，要想通过修改形参来改变实参就必须传实参的地址。

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* pcur = *pphead;while (pcur->next){pcur = pcur->next;}pcur->next = newnode;}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{newnode->next = *pphead;}*pphead = newnode;
}

2.4删除（尾删和头删）

链表重新连接好后要释放掉删除部分的地址（free）

//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* ptail = *pphead;SLTNode* pcur = NULL;while (ptail->next){pcur = ptail;ptail = ptail->next;}pcur->next = NULL;free(ptail);ptail = NULL;}
}
//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* ptail = *pphead;SLTNode* pcur = ptail->next;free(ptail);ptail = NULL;*pphead = pcur;}
}

2.5查找

通过比对data来找到pos的地址。

这里我调试时出现返回的pos1地址传到我新建立的结构体指针中，高位不一致，但低位一致，问题产生的主要原因是，头文件中函数没有定义，我给注释掉了。

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pos1 = phead;while (pos1 != NULL){if (pos1->data == x){return pos1;}pos1 = pos1->next;}return NULL; // 未找到或链表为空时返回 NULL
}

2.6任意位置插入

//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* newnode = SLTBuyNode(x);SLTNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}newnode->next = pos;pcur->next = newnode;}
}
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

2.7删除指定位置的元素

//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);SLTNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}pcur->next = pos->next;
}
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{assert(pos);if (pos->next == NULL){printf("POS后没有元素\n");return;}else{ SLTNode* pcur = pos->next;pos->next = pcur->next;free(pcur);                // 释放被删除节点的内存pcur = NULL;               // 防止悬空指针}}

2.8 销毁链表

//销毁链表
void SListDestroy(SLTNode** pphead)
{free(*pphead);*pphead = NULL;
}

3.总结

主要完成了单链表的插，删，查等功能，编写过程中掌握调试的基本方法。原代码地址在我的gitee仓库中，有需要可以下载查看。https://gitee.com/lisien123/c_learn/tree/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/25-8-31%E5%8D%95%E9%93%BE%E8%A1%A8