数据结构--链表（单链表）
目录
一.链表的定义：
1.链表的概念和结构
2.链表的分类
3.链表的特点
二.单链表的实现
1.创建单链表
2.链表的初始化
注意：
3.链表的销毁
4.链表的打印
5.新结点的创建
6.链表的插入
6.1头插
6.2尾插
6.3指定位置之前插入结点
6.4指定位置之后插入结点
7.链表的删除
7.1头删
7.2尾删
7.3删除指定位置的结点
7.4指定位置之后删除结点
8.查找（根据元素查找）
9.查找（根据位置查找）
三.总结
顺序表和链表的区别
一.链表的定义：
1.链表的概念和结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链 接次序实现的 。
2.链表的分类
3.链表的特点
- 动态内存分配：链表中的节点是在运行时动态创建的，可以根据需要分配和释放内存。
- 可扩展性：链表的大小可以根据需要动态增长或缩小，没有固定的大小限制。
- 非连续存储：链表中的节点可以分散在内存的不同位置，每个节点包含数据和指向下一个节点的指针。
二.单链表的实现
1.创建单链表
//创建链表
typedef int data;
typedef struct SListNode
{
data n;
struct SListNode* next;
}SLN;2.链表的初始化
注意：
1.若创建为空链表则调用函数时进行地址传递，即二级指针
2.若要有哨兵位，并且头插插在哨兵位后面，这时只需要传递一级指针就可以了，不会改变头结点的位置
1.
SLN* List = NULL;2.
SLN* List=(SLN*)malloc(sizeof(SLN));
if (List == NULL)
{
exit(1);
}
List->n = 0;
List->next = NULL;
SLNinsertback(List, 1);3.链表的销毁
//销毁链表
void SLNDesTroy(SLN** pphead)
{
assert(pphead && *pphead);
SLN* pital = *pphead;
while (pital)
{
SLN* next = pital->next;
free(pital);
pital=next;
}
*pphead = NULL;
}4.链表的打印
void SLNprint(SLN* phead)
{
SLN* prev = phead;
while (prev)//prev！=NULL,
{
printf("%d->", prev->n);
prev = prev->next;
}
printf("NULL
");
}5.新结点的创建
//新建结点
SLN* Newnode(data x)
{
SLN* newnode = (SLN*)malloc(sizeof(SLN));
if (newnode == NULL)
{
exit(1);
}
newnode->n = x;
newnode->next = NULL;
return newnode;
}6.链表的插入
6.1头插
void SLNinsertfront(SLN** pphead, data x)
{
assert(pphead);
SLN* newnode = Newnode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
newnode->next = *pphead;
*pphead = newnode;
}
}6.2尾插
void SLNinsertback(SLN** pphead, data x)
{
assert(pphead);//不能传递空地址
SLN* newnode = Newnode(x);
//判断是否为空链表
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLN* prev = *pphead;
//寻找尾结点
while (prev->next)
{
prev = prev->next;
}
prev->next = newnode;
}
}6.3指定位置之前插入结点
//在指定位置之前插入结点
void SLNseatinsertfront(SLN** pphead, int num, data element)
{
assert(pphead && *pphead);
SLN* seatfind = SLNseatfind(*pphead, num);
if (seatfind != NULL)
{
if (seatfind == *pphead)
{
SLNinsertfront(pphead,element);
}
else
{
SLN* prev = *pphead;
while (prev->next != seatfind)
{
prev = prev->next;
}
SLN* newnode = Newnode(element);
newnode->next = seatfind;
prev->next = newnode;
}
}
else
{
printf("该位置不存在！
");
exit(1);
}
}6.4指定位置之后插入结点
//在指定位置之后插入结点
void SLNseatinsertback(SLN** pphead, int num, data element)
{
assert(pphead && *pphead);
SLN* seatfind = SLNseatfind(*pphead, num);
if (seatfind != NULL)
{
SLN* prev = seatfind->next;
SLN* newnode = Newnode(element);
newnode->next = prev;
seatfind->next = newnode;
}
else
{
printf("该位置不存在！
");
exit(1);
}
}7.链表的删除
7.1头删
//头删
void SLNdeletefront(SLN** pphead)
{
assert(*pphead && pphead);
SLN* prev = (*pphead)->next;
free(*pphead);
*pphead = NULL;
*pphead = prev;
}7.2尾删
//尾删
void SLNdeleteback(SLN** pphead)
{
//判断链表是否为空和传递过来的地址是否为空
assert(*pphead && pphead);
if ((*pphead)->next == NULL)//->的优先级高于*
{
free(*pphead);
*pphead = NULL;
}
//下列注释只能找到最后一个结点并释放，但是前一个结点的找不到，就会导致前一个结点的next无法置为NULL
/*SLN* prev = *pphead;
while (prev->next)
{
prev = prev->next;
}
free(prev);
prev = NULL;*/
else
{
SLN* prev = *pphead;
SLN* pital = *pphead;
while (prev->next)
{
pital = prev;
prev = prev->next;
}
//这时prev指向最后一个结点，pital指向倒数第二个结点
free(prev);
prev = NULL;
pital->next = NULL;
}
}7.3删除指定位置的结点
//删除指定位置结点
void SLNseatDelete(SLN** pphead, int n)
{
assert(pphead && *pphead);
SLN* seatfind = SLNseatfind(*pphead, n);
if (seatfind != NULL)
{
if (seatfind == *pphead)
{
SLNdeletefront(pphead);
}
else
{
SLN* prev = *pphead;
while (prev->next != seatfind)
{
prev = prev->next;
}
SLN* pital = seatfind->next;
free(seatfind);
seatfind = NULL;
prev->next = pital;
}
}
else
{
printf("该位置不存在！
");
exit(1);
}
}7.4指定位置之后删除结点
//删除指定位置结点之后的结点
void SLNseatDeleteAfter(SLN* pphead, int n)
{
assert(pphead);
SLN* seatfind = SLNseatfind(pphead, n);
if (seatfind!= NULL)
{
if (seatfind->next == NULL)
{
printf("该结点后面没有结点！
");
return;
}
else
{
SLN* pital = seatfind->next;
SLN* prev = pital->next;
free(pital);
pital = NULL;
seatfind->next = prev;
//seafind pital
/* SLN* pital = seatfind->next;
seatfind->next = pital->next;
free(pital);
pital = NULL;*/
}
}
else
{
printf("该位置不存在！
");
exit(1);
}
}8.查找（根据元素查找）
查找链表中是否存在该数据，若存在返回该结点的地址
SLN* SLNfind(SLN* phead, data n)
{
assert(phead);
SLN* prev = phead;
while (prev)
{
if (prev->n == n)
{
return prev;
}
prev = prev->next;
}
return NULL;
}9.查找（根据位置查找）
//查找指定位置结点所在的地址
SLN* SLNseatfind(SLN* phead, int num)
{
assert(phead);
int n = 1;
SLN* prev = phead;
while (n != num && prev != NULL)
{
prev = prev->next;
n++;
}
if (prev == NULL)
{
return NULL;
}
else
{
return prev;
}
}三.总结
1.链表的实现可以节省大量的空间，不会造成空间浪费，需要插入时只需创建一个结点即可
2.链表更加侧重于插入和删除，操作比顺序表更加方便
顺序表和链表的区别
下篇文章主要讲解双向链表的实现
