博客ID：LanFuRen
C系列专栏：C语言重点部分 C语言注意点 C++基础 Linux 数据结构 C++注意点
声明等级：黑色->蓝色->红色欢迎新粉加入，会一直努力提供更优质的编程博客，希望大家三连支持一下啦
目录
1.链表的概念
2.单链表主体的实现
3.单链表内部方法实现
1）二级指针的问题
2）头插尾插的实现
3）其他代码展示
1.链表的概念
链表是⼀种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
链表就像火车一样，由一节一节车厢所构成。
从概念图可以看出，下一节“车厢”，通过上一节“车厢”中的指针来链接。由上图，我们可以清晰地写出链表的主体部分，该链表结构体中有两个结构体成员——节点所存入的数据，结构体指针存放下一个节点的地址。（车厢=节点）。
2.单链表主体的实现
代码如下：
typedef struct SListNode
{int data;//存放的数据struct SListNode* next;//结构体指针
}SLTNode;SList：single单个的意思，list代表链表，node代表节点。
3.单链表内部方法实现
这里依旧提供几个比较重要的方法的实现过程：
//链表的打印
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** pphead, SLTDataType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
1）二级指针的问题
我们先来看看这里的二级指针的问题，为什么要使用SLTNode**pphead?那我们就得看实参跟形参的关系了，我们实参应该是一个链表，假设名字是plist，我们要在函数中去修改这个plist，即修改plist存放的地址（指向），而这个plist应该是SLTNode*plist=NULL(节点)，我们要去修改一级指针的值，就需要得到一级指针的地址，这样就用到了二级指针。
2）头插尾插的实现
代码如下：
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);/*if (*pphead==NULL){*pphead = newnode;return;}*/newnode->next = *pphead;*pphead = newnode;//重要
}//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)//传二级指针是因为这样才能修改plist链表，我们想获得plist的内部成员（节点内容），就是值，得传址，所以说传二级指针
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);//空链表if (*pphead == NULL){*pphead = newnode;return;}//链表不为空SLTNode* ptail = *pphead;//ptail是一级指针while (ptail->next){ptail = ptail->next;//ptail指针存放的是节点地址，节点包括next,这一步仅仅传一级指针就行。}ptail->next = newnode;/*while ((*pphead)->next){*pphead = (*pphead)->next;}(*pphead)->next = newnode;*/
}3）其他代码展示
//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);(*pphead)=NULL;return;}SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;//上一级ptail = ptail->next;//尾}prev->next = NULL;free(ptail);ptail = NULL;
}void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* del = *pphead;*pphead= (*pphead)->next ;free(del);del = NULL;/*SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;*/
}//查找
//为指定位置增删有帮助
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(pphead);//assert(*pphead);SLTNode* val = *pphead;while (val != NULL){if (val->data == x){return val;}val = val->next;}return NULL;
}在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);assert(*pphead);//空链表哪里来的指定位置插入SLTNode* newnode = SLTBuyNode(x);if (pos == *pphead){SLTPushFront(pphead, x);return;}//头节点//不是头节点SLTNode* pos_before = *pphead;while (pos_before->next != pos){pos_before = pos_before->next;}/*pos_before->next = newnode->data;newnode->next = pos->data;*/pos_before->next = newnode;newnode->next = pos;
}//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//pos刚好是头结点，没有前驱节点，执行头删if (*pphead == pos) {//头删SLTPopFront(pphead);return;}SLTNode* pos_before = *pphead;while (pos_before->next != pos){pos_before = pos_before->next;}//找到前驱节点SLTNode* pos_after = pos->next;//后驱节点pos_before->next = pos_after;//pos->next = NULL;free(pos);pos = NULL;
}
