目录
前言
一.什么是链表
1.概念
编辑
2.分类
二.单链表的实现(不带头单向不循环链表)
2.1初始化
2.2打印
2.3创建新节点
2.4头插、尾插
2.5头删、尾删
2.6查找
2.7在指定位置之前插入
2.8在指定位置之后插入
2.9删除pos位置
2.10删除pos之后的
2.11销毁链表
前言
通过前面所学的顺序表，我们发现存在着几个问题,顺序表的中间/头部的插入需要挪动数据、扩容存在着性能的消耗、或多或少有空间的浪费，由此我们引入链表这一概念.
一.什么是链表
1.概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
2.分类
结构多样，根据是否带头，单向/双向，循环/不循环分为8种
其中使用较多的是单链表（不带头单向不循环链表）和双向链表(带头双向循环链表),这节讲解单链表的实现
二.单链表的实现(不带头单向不循环链表)
2.1初始化
结构的声明和定义
typedef int SLTDataType;
//该链表由节点组成
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;//这里不能写成SLTNode,这时还未重命名
}SLTNode;
//typedef struct SListNode SLTNode;2.2打印
这里有pcur去接收phead,然后依次遍历，当pcur指向NULL时跳出循环，最后再打印NULL
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}2.3创建新节点
与顺序表的扩容不同，这里需要新节点即开辟，不会造成浪费
如果开辟失败，则会报错
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//新节点
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}2.4头插、尾插
头插相较于尾插较容易，这里面传递的是二级指针
//链表的头插、尾插
void SLTPushBack(SLTNode** phead, SLTDataType x);
void SLTPushFront(SLTNode** phead, SLTDataType x);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
//链表为空，新节点为phead
if (*pphead == NULL)
{
*pphead = newnode;
return;
}
//链表不为空，找尾节点
SLTNode* ptail = *pphead;
while (ptail->next)
{
ptail = ptail->next;
}
//为空，跳出循环，此时ptail就是尾节点
ptail->next = newnode;
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
//newnode *pphead
newnode->next = *pphead;
*pphead = newnode;
}2.5头删、尾删
//链表的头删、尾删
void SLTPopBack(SLTNode** phead);
void SLTPopFront(SLTNode** phead);
//尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
//链表不能为空
assert(*pphead);
//链表不为空
//链表只有一个节点,有多个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
return;
}
SLTNode* ptail = *pphead;
SLTNode* prev = NULL;
while (ptail->next)//prev ptail ptail->next
{
prev = ptail;
ptail = ptail->next;
}
prev->next = NULL;
//销毁尾节点
free(ptail);
ptail = NULL;
}
//头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
//链表不能为空
assert(*pphead);
//让第二个节点成为新的头
//把旧的头节点释放掉
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}2.6查找
通过遍历链表，查找是否与x相等,若有则返回pcur;若未找到,则返回NULL
//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//遍历链表
SLTNode* pcur = *pphead;
while (pcur)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
//没有找到
return NULL;
}2.7在指定位置之前插入
与头插类似
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
//要加上链表不为空,若是空链表，那么前面将断言
assert(*pphead);
SLTNode* newnode = SLTBuyNode(x);
//pos刚好是头节点
if (pos == *pphead)
{
//头插
SLTPushFront(pphead,x);
return;
}
//pos不是头节点的情况
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev->newnode->pos
prev->next = newnode;
newnode->next = pos;
}2.8在指定位置之后插入
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
//pos newnode pos->next
newnode->next = pos->next;
pos->next = newnode;
}2.9删除pos位置
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(*pphead);
assert(pos);
//pos刚好是头节点，没有前驱节点，执行头删
if (*pphead == pos)
{
//头删
SLTPopFront(pphead);
return;
}
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev pos pos->next
prev->next = pos->next;
free(pos);
pos = NULL;
}2.10删除pos之后的
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//删除链表之后的节点
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
//pos->next不能为空
assert(pos->next);
//pos pos->next pos->next->next
SLTNode* del = pos->next;
free(del);
del = NULL;
}2.11销毁链表
//销毁链表
void SListDesTroy(SLTNode** pphead);
//销毁链表
void SListDesTroy(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}如果上述内容对您有帮助，希望给个三连谢谢
