单链表
前面我们完成了顺序表以及通讯录，为了节省空间，在顺序表中我们是以2倍的方式来扩大我们的存储空间的，但是假如我们存入10001个数据，那么程序就会将空间扩大到20000，会浪费9999个空间，这样看的话我们浪费的空间仍然比较多，那么有没有办法不浪费我们的空间呢？有的，那就是链表。
一、链表是什么：
链表的结构：
struct SListNode
{
int data;//这里是存储的是整形的数据
struct SListNode*next;//指向下一个节点的指针
}
这就是一个节点。
二、实现链表：
我们使用链表是让其实现与通讯录，顺序表一样的存储数据的功能，那么我们就需要链表完成与顺序表一样的增，删，查，找的功能。那下面我就来完成上述功能：
1、头文件的创建
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLNtype;
typedef struct SListNode//我们定义的节点
{
SLNtype data;
struct SListNode* next;
}SLN;
void print(SLN* ptr);//打印链表
void SLNPushBack(SLN** pptr, SLNtype x);//链表的尾插
void SLNPushPront(SLN** pptr, SLNtype x);//链表的头插
void SLNDelBack(SLN** pptr);//链表的尾删
void SLNDelPront(SLN** pptr);//链表的头删
SLN* SLNFind(SLN** pptr, SLNtype x);//查找指定数据的节点
void SLNPushZDQ(SLN** pptr, SLN* zd, SLNtype x);//在指定位置前插入数据
void SLNPushZDH(SLN* zd, SLNtype x);//在指定位置后插入数据
void SLNDelZD(SLN** pptr, SLN* zd);//删除指定节点
void SLNDelZDh(SLN* zd);//删除指定节点之后的节点
void SLNDestroy(SLN** pptr);//销毁链表
在这个头文件中，结构体与数据类型的重命名与之前类似，我就不重复讲了，看下面的函数声明，我们或许有疑问，为什么用的是二级指针？我们想一下，当我们使用这些函数的时候我们是不是需要传入指向这个链表的头节点的指针，当我们直接传入这个指针时，实际上是值传递，它是不会改变我们原链表的，因此我们只能使用地址传递，也就是取地址，而取出的地址是指针的地址即二级指针 ，因此我们需要用二级指针去接收它。
明白上述内容后我们就可以来实现我们的函数体了：
（一），尾插
在链表中插入数据，首先我们需要先创建一个储存插入数据的节点，然后将这个节点放入链表之中，尾插也就是将新节点插入链表的尾部。
SLN* buynode(SLNtype x)
{
SLN* newnode = (SLN*)malloc(sizeof(SLN));//开辟空间用的是malloc函数，开辟的是结构体（节点）的大小
newnode->data = x;//放入数据
newnode->next = NULL;//节点的next指针为空
return newnode;//将新节点的地址返回
}
这个就是我们的开辟节点的代码。
开辟好了节点我们就可以插入链表的尾部了。
void SLNPushBack(SLN** pptr, SLNtype x)
{
SLN* newnode = buynode(x);
if (*pptr == NULL)//我们的链表为空，也就是头指针为空
{
*pptr = newnode;//新节点就是链表的首节点
}
else//我们的链表不为空
{
SLN* ptail = *pptr;//ptail用来遍历我们的链表
while (ptail->next)//当ptail->next为空时，ptail也就为我们的尾节点
{
ptail = ptail->next;
}
ptail->next = newnode;//将新节点与尾节点连接
}
}
（2）、打印链表
在我们完成一个函数后需要测试我们这一部分的代码是否正确，我们就需要打印这个链表，那我们完成一个打印函数。
那我们该如何打印呢？我们只需要遍历这个链表，将链表每一个节点存储的数据打印出来即可。
void print(SLN* ptr)
{
SLN* ptail = ptr;//创建一个patil指针用来遍历我们的链表
while (ptail)
{
printf("%d->", ptail->data);
ptail = ptail->next;
}
printf("NULL");
}
现在我们就可以来测试下我们的尾插是否正确：
这里可以看见我们代码运行正确，那我们就可以继续写我们的代码。
（3）、头插
头插与尾插一样都是需要先创建一个新节点，再将节点插入
void SLNPushPront(SLN** pptr, SLNtype x)
{
SLN* newnode = buynode(x);
newnode->next = *pptr;
*pptr = newnode;
}
代码写完之后，我们仍然需要测试一下
（3）、链表的尾删
void SLNDelBack(SLN** pptr)
{
assert(pptr && *pptr);
SLN* ptail = *pptr;
SLN* pcur = *pptr;
if ((*pptr)->next == NULL)//只有一个节点
{
free(*pptr);
*pptr = NULL;
}
else//多个节点
{
while (ptail->next)
{
pcur = ptail;
ptail = ptail->next;
}
free(ptail);
ptail = NULL;
pcur->next = NULL;
}
}
（4）、链表的头删
void SLNDelPront(SLN** pptr)
{
assert(*pptr && pptr);
SLN* phead = *pptr;
*pptr = (*pptr)->next;
free(phead);
phead = NULL;
}
测试如下：
（5）、查找指定数据的节点
这部分代码的实现就比较简单了，我们只需要遍历链表，当当前节点的数据与我们输入的数据相同时，返回当前节点的地址
SLN* SLNFind(SLN** pptr, SLNtype x)
{
assert(pptr && *pptr);
SLN* ptail = *pptr;
while (ptail)
{
if (ptail->data == x)
{
return ptail;
}
ptail = ptail->next;
}
return NULL;
}
当我们找到了的时候，我们可以让其输出“找到了”，反之输出“不存在”。
（6）、在指定位置前插入节点
在上面我们找到节点后返回了它的地址，我们就可以将其作为我们的指定位置
void SLNPushZDQ(SLN** pptr, SLN* zd, SLNtype x)
{
if (zd==*pptr)
{
SLNPushPront(pptr, x);//头插
}
else
{
SLN* newnode = buynode(x);
SLN* pcur = *pptr;
while (pcur->next != zd)//遍历链表，找到指定节点前一个节点
{
pcur = pcur->next;
}
newnode->next = zd;
pcur->next = newnode;
}
}
（7）、在指定节点后插入节点
void SLNPushZDH(SLN* zd, SLNtype x)
{
assert(zd);
SLN* newnode = buynode(x);
//SLN* pcur = zd;
newnode->next = zd->next;
zd->next = newnode;
}
测试如下
（8）、删除指定节点
void SLNDelZD(SLN** pptr, SLN* zd)
{
assert(*pptr && pptr && zd);
if (zd == *pptr)
{
SLNDelPront(pptr);
}
else
{
SLN* pcur1 = *pptr;
while (pcur1->next != zd)
{
pcur1 = pcur1->next;
}
SLN* pcur2 = zd->next;
pcur1->next = pcur2;
free(zd);
zd = NULL;
}
}
测试如下：
（9）、删除指定节点后的一个节点
void SLNDelZDh(SLN* zd)
{
assert(zd);
assert(zd->next);
SLN* pcur = zd->next;
zd->next = pcur->next;
free(pcur);
pcur = NULL;
}
（10）、销毁链表
我们只需要遍历链表，遍历一个删除一个
void SLNDestroy(SLN** pptr)
{
assert(pptr && *pptr);
SLN* pcur = *pptr;
while (pcur)
{
SLN* next = pcur->next;
free(pcur);
pcur = next;
}
*pptr = NULL;
}
测试如下：
以上就是单链表的全部内容。
