数据结构——链表
概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
节点（或结点）是链表的基本单位，通常每个节点可以分为数据区和指针区，数据区顾名思义用来储存该节点的数据，指针区用于存放指向下一个节点的指针
具体的链接方式如下图，从头节点开始，每个节点通过指针，如同火车车厢一样依次链接
代码实现
接下来我们用代码实现这个结构
节点
typedef int SLTDataType;//方便修改链表存储的数据类型
typedef struct SListNode
{
SLTDataType data;//数据区
struct SListNode* next;//指针区
}SLTNode;
链表由多个节点链接，并且具有增删查改等基本功能，因此需要用函数来实现这些功能
申请节点空间
对链表的操作中，需要多次开辟空间，用于存放新的节点，因此可以将这段代码封装为一个函数
函数的接口传入新节点的数据x，返回新节点的地址
1.申请一个节点大小的空间，赋值给中间指针newnode
2.有开辟失败的可能性，因此要判断newnode指向是否为空，如果为空，则异常退出程序
3.如果开辟成功，将数据x赋值给新节点的data，同时将新节点的next指针初始化为NULL
4.返回newnode
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;
}
尾插
尾插是向链表尾部插入新的节点
函数的接口传入链表的头节点指针和新节点的数据
1.首先断言传入的头节点指针，pphead为空表示不存在头节点则无法解引用，pphead为空表示链表为空，可以被解引用
2.申请新的节点空间
3.将新节点链接到链表尾部，如果链表为空，那么新节点视为头节点，将节点地址赋值给*pphead；如果链表不为空，那么通过while循环寻找尾节点，最后将尾节点的next指针指向新节点
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
//判断空链表和非空链表
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾节点
SLTNode* ptail = *pphead;
while (ptail->next != NULL)//!=NULL 可以省略
{
ptail = ptail->next;
}
//ptail此时指向尾节点
ptail->next = newnode;
}
}
补充：c语言中assert函数在assert.h头文件中，是一种调试工具，可以用于检查程序运行时，是否满足特定条件
头插
头插是从链表头部插入新节点
函数的接口传入链表的头节点指针和新节点的数据
1.对头节点指针断言
2.申请新节点空间
3.将新节点的next指针指向链表的头节点
4.将新节点设置为链表的头节点
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
尾删
尾删是删掉链表的最后一个节点
函数的接口传入链表的头节点指针
1.断言头节点指针和链表，判断头节点指针为空且链表为空，指针为空表示链表不存在，链表为空表示没有可以被删除的节点。此处注意先判断pphead再判断*pphead，如果pphead为空则发生短路，不会因为*pphead的解引用错误而发生报错
2.如果链表只有一个节点，那么直接将头节点内存释放，next指针置空
3.如果链表有多个节点，那么通过while访问next指针，找到尾节点和尾节点的前一个节点，释放尾节点，尾节点指针置空，将前一个节点next置空
void SLTPopBack(SLTNode** pphead)
{
assert(pphead && *pphead);
//链表只有一个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* prev = *pphead;
SLTNode* ptail = *pphead;
//链表有多个节点
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
free(ptail);
ptail = NULL;
prev->next = NULL;
}
}
头删
头删是删掉链表的第一个节点
函数的接口传入链表的头节点指针
1.断言头节点指针和链表
2.用中间指针next保存头节点的next
3.释放头指针
4.将中间指针next设为头节点
void SLTPopFront(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
查找
查找数据在链表中的节点
函数的接口传入链表头节点指针和要查找的数据x
1.用指针pcur指向传入的链表phead的头节点
2.在while中对链表遍历，每访问过一个节点，pcur指向下一个节点，将pcur的data与x比较，如果相等则返回pcur
3.直到循环结束也没有返回pcur，说明不存在该值，最后返回NULL
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
在指定位置之前插入数据
将新节点插入到指定的节点前一个
函数的接口传入链表头节点指针，指定节点pos，插入的数据x
1.断言头节点指针和链表
2.断言指定节点pos
3.申请新节点newnode
4.将prev指针指向链表头节点
5.如果指定位置是头节点，则调用前面写好的头插函数
6.不是头节点，那么在while中从prev开始遍历访问next
7.如果prev的下一个节点是指定节点pos，那么将newnode的next指向pos，将prev的next指向newnode
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead && *pphead);
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
SLTNode* prev = *pphead;
//若prev == *pphead 说明是头插
if (pos == *pphead)
{
SLTPushFront(pphead,x);
}
else
{
while (prev->next != pos)
{
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}
}
在指定位置之后插入数据
将新节点插入到指定的节点后一个
函数的接口传入链表头节点指针，指定节点pos，插入的数据x
1.断言pos
2.申请新节点空间
3.将newnode的next指向指定节点pos的next
4.将指定节点pos的next指向newnode
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
补充：最后两步顺序不能互换，否则原本pos的next指针会丢失
删除pos节点
删除指定节点pos
函数的接口传入链表头节点指针，指定节点pos
1.断言头节点指针和链表
2.断言节点pos
3.将指针prev指向头节点
4.如果pos是头节点，调用前面写好的头删函数
5.如果不是头节点，那么从头节点开始遍历访问，如果prev的next是指定节点pos，那么将prev的next指向pos的next，将pos节点跨过
6.释放pos节点，将pos指针置空
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && *pphead);
assert(pos);
SLTNode* prev = *pphead;
//pos是头节点
if (pos == *pphead)
{
//头删
SLTPopFront(pphead);
}
else
{
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
删除pos后一节点
删除指定节点pos的下一个节点
函数接口传入指定节点pos
1.断言pos节点和pos的下一个节点，确保两个节点都存在
2.用指针del指向指定节点的下一节点
3.让指定节点的next赋值为del的next节点，将del（也就是pos的下一节点）跨过
4.释放del，将del指针置空
void SLTErase(SLTNode* pos)
{
assert(pos && pos->next);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
销毁链表
释放链表占用的内存
函数接口传入链表的头节点指针
1.断言指针和链表
2.用指针pcur指向头节点
3.在while循环中，用指针next保存pcur的下一节点，释放pcur，将pcur指向next
4.最后将链表头节点指针置空
void SLTDestroy(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
//销毁头节点
*pphead = NULL;
}
以上是链表的基本结构和常用的链表操作
如果存在错误，欢迎指正