单链表（第二部分）单链表的实现！！！

链表（第二部分）单链表的实现！！！"/>

单链表（第二部分）单链表的实现！！！

1.单链表的头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include"contact.h"typedef struct PersonInfo 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);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

为什么一些接口的参数是二级指针一些是一级指针？

因为二级指针可以对 头结点pphead 进行更改，如果只是一级指针的话形参只是一个局部变量并不能更改 pphead 的值。

就假如一个 add（int a，int b），你的两个形参都是int并没有用 int * 接收的话，那么传入的值是不会更改的。 

2.前置声明

typedef struct PersonInfo SLTDataType;
typedef struct SListNode
{//SLTDataType data;struct SListNode* next;
}SLTNode;

这一步主要是把每个节点要存储的数据类型确定，然后在用结构体 存储一个 数据，一个结构体指针。并且重命名为sltnode。 

2.1关于节点的开辟 

SLTNode* SLBuyNode(SLTDataType x)
{SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));node->data = x;node->next = NULL;return node;
}

返回的是一个结构体指针 ，这就是相当于是一块新的火车车厢，还没插入的。

首先传入一个值 x。用node 指针开辟一块新的空间，大小就为sltnode。

里面的值就是 x 然后下一个指针就是 置为NULL。返回node 指针就可以了。

3.打印单链表数据

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

因为打印不需要更改节点信息，所以接受的参数用一级指针即可。 用一个 中间变量pcur，进行遍历，遍历的条件就是让pcur 走到下一个数据为NULL的时候结束，因为节点的开辟时最后一个节点下一个节点必定为NULL。

最后在打印一个NULL就可以了。

4.尾部插入和头部插入

4.1尾部删除

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* node = SLBuyNode(x);if (*pphead == NULL){*pphead = node;return;}else{SLTNode* pcur = *pphead;while (pcur->next != NULL){pcur = pcur->next;}pcur->next = node;}
}

 1.断言pphead 是否为空指针。因为空指针不能被解引用。

2.开辟一个新的节点node。

3.判断第一个节点是不是为空，如果为空直接把node 作为第一个节点。

4.如果不是空 将第一个的节点 给 pcur 接收，用pcur 遍历到最后一个节点。跳出循环

5.将pcur 的下一个节点置为node。

4.2头部插入

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* node = SLBuyNode(x);node->next = *pphead;*pphead = node;
}

代码相对尾插断。因为不用判断第一个节点是否为空。

因为对于头插如果你的第一个节点为空也没事，因为是把节点往头结点前面插入，这样就不会解引用到空指针。

1.首先断言pphead 是否为空

2.开辟一个 名字为node 的新空间的指针。

3.将node 里的next 指针 的空间置为 *pphead （头结点）。

4.将node 变为新的头结点。 

5.尾部删除和头部删除

5.1尾部删除

void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* prev = NULL;SLTNode* ptail = *pphead;while (ptail->next != NULL){prev = ptail;ptail = ptail->next;}prev->next = ptail->next;free(ptail);ptail = NULL;
}

1.先用断言判断pphead 和 *pphead 是否为空（因为是删除，所以头结点不应该为空。）

2.需要用到两个指针，prev指针先指向空，ptail指针指向第一个节点。

3.用ptail去遍历链表 ，每一次将 prev 指针指向 ptail 现在在的空间。然后ptail继续往下走。

直到ptail 的下一个 空间为空。

此时ptail 在尾结点，prev在尾结点的前一个节点。

4.先让 ptail 指向下一个空间的指针指向 prev 的下一个空间，即尾空间。然后释放ptail的空间，再把ptail置为空。 

5.2头部删除 

void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* del = *pphead;*pphead = (*pphead)->next;free(del);del = NULL;
}

1.删除都要断言 pphead 和* pphead 是否为空。

2.设置一个del指针指向头指针。 

3.头结点变为头结点的下一个节点。

4.将之前的头结点 del 指针的空间释放掉，并置空。

6.查找位置

SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* pcur = *pphead;while (pcur){if (strcmp(pcur->data.name,x.name)== 0){return pcur;}pcur = pcur->next;}return NULL;
}

 这个接口很重要，因为后续的接口都会用到。（这里采用的是查找名字的方法寻找）

1.断言pphead是否为空

2.用一个 pcur 接收 *pphead（不让头结点改变）。

3.遍历pcur 直到空

4.用strcmp比较两个名字的数据，如果相同则为0，不同则不为0.

相同返回pcur即可。

5.如果遍历结束还没找到则就返回一个空指针。

7.在指定位置之前插入数据

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);assert(*pphead);SLTNode* node = SLBuyNode(x);if (pos == *pphead){node->next = *pphead;*pphead = node;return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = node;node->next = pos;}

 1.断言 pphead pos *pphead（因为是指定位置所以头结点不能为空和 传入的pos位置节点也不能为空）

2.同样先创建一个node节点。

3.如果pos 找到的就是头结点，则再执行一次头插即可。

4.如果不是pos 找到的不是头结点，用prev 接收 头结点。遍历prev ->next 直到找到pos节点。找到后将prev的下一个节点的指针置为node，将node的下一个指针指向pos即可。

8.删除指定位置数据

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);assert(*pphead);if (pos == *pphead){*pphead = (*pphead)->next;free(pos);pos = NULL;return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;
}

 1.断言pphead和pos 和*pphead（指定位置那就代表必须要有数据）

2.如果头结点就是pos 指针。那就执行一次头删即可。

3.如果不是那一样的用两个指针，找到最后一个节点和最后一个节点前的一个节点。

将prev的next 置为 pos 的next。即可，

4.最后释放掉pos的空间。（为什么不直接删呢？因为pos里存储下一个空间的指针，如果直接删除那就找不到下一块空间的地址了。）

9.在指定位置之后插入数据

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* node = SLBuyNode(x);node->next = pos->next;pos->next = node;
}

 和上述类似，不会的可以私聊我，看到后给出解答

10.删除指定位置之后的节点

void SLTEraseAfter(SLTNode* pos)
{assert(pos);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

 和上述类似，不会的私聊我，看到后给出解答

11.销毁链表

void SListDesTroy(SLTNode** pphead)
{assert(pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

不能直接销毁要一个一个进行销毁。因为要通过前一个空间的钥匙找到下一个空间的位置。