下一文章将会介绍贪吃蛇小游戏的实现，这一章节主要介绍写游戏需要用到的数据结构——链表
一、什么是链表
链表是一种线性的数据结构，由一系列的节点组成，每一个节点包含两部分：
● 数据域：存放数据的部分
● 指针域：存放指向下一个节点的指针
如图：
上图中一个方框就是一个节点，如地址0x0012FFB0，该节点中存放的有数据和指向下一个节点的指针，图中plist我们可以形象地理解为“头指针”（注意这并不是真正的头指针，仅仅只是便于理解），每个节点在内存上的分布并非是连续的，他们通过每个节点存放的指针连接起来，每个节点都存放着指向下一个节点的地址，需要注意的是最后一个节点中存放的地址是NULL。
节点的结构定义
如下
sturct SListNode
{
int data; //节点数据
struct SListNode* next; //下一个节点的地址
};
二、为啥使用链表
在游戏运行的过程中，需要不断的维护蛇身每个位置的坐标，比如说，吃到食物需要新存入一个坐标数据，向前走一步需要需要改变每个坐标的位置等等，坐标的维护就通过创建链表来实现。
链表的优点：
● 使用灵活：想加就加，想减就减，不用把整块数据摞来摞去，插入删除都是O(1)。
● 使用方便：插入和删除数据都只需修改指针指向就行了，无需修改其他节点的位置。
● 永远不会装不下：想加数据就直接往后加就行了，不需要提前知道最多有多少数据需要存储，也不需要想数组那样提前申请多少空间。
三、链表的创建与维护
链表节点的创建
链表的节点的结构一般是在头文件中定义的，因此我们先创建一个头文件，就叫SList.h（这里的S就是single(单身的)单身的朋友应该很熟悉，SList就是单链表啦），在里面写上节点的定义
//SList.h
typedef int SLTDataType;
//这里弄是为了方便修改链表中的数据类型
//定义节点
typedef struct SLTNode
{
SLTDataType data;
struct SLTNode* next;
}SLTNode;
函数的声明：
除此之外，头文件也要包含维护该链表的函数申明（即对链表的数据进行增删查改的函数），同时也包含上要用到的头文件吧：
//SList.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SLTNode
{
SLTDataType data;
struct SLTNode* 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);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);
这里的SLTNode就是函数的节点类型，phead就是指链表头的头指针，就是要插入或寻找的数据。
这函数些就是我们即将要对链表进行的操作了，我们一个一个来实现吧
尾插实现
这里需要创建一个源文件用于，存放函数的定义，就取名叫SList.c吧
SList.c
//尾插节点
void SLTPushBack(SLTNode** pphead, SLTDataType x);
尾插就是在连表的最后插入数据
SLTNode** pphead：头指针的地址（二级指针）。因为链表可能为空，或者插入操作可能需要修改头指针本身，所以必须传二级指针。
SLTDataType x：要插入的新数据。
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);//检查空指针
//申请空间
SLTNode* pnew = (SLTNode*)malloc(sizeof(SLTNode));
if (!pnew)
{
perror("malloc");
exit(1);
}
//初始化新节点data,next
pnew->data = x;
pnew->next = NULL;
//处理空链表的情况
if (*pphead == NULL)
{
//修改首指针
*pphead = pnew;
return;
}
//有节点
else {
//遍历链表，找到前驱节点，即最后一个节点
SLTNode* prev = *pphead;
while (prev->next)
{
prev = prev->next;
}
//链接前驱节点
prev->next = pnew;
}
}
assert(pphead)：断言检查。确保传入的指向头指针的地址不是空指针
1. 申请节点：
SLTNode* pnew = (SLTNode*)malloc(sizeof(SLTNode))：在堆区申请一块内存，用来存放新的节点。
2. 初始化新节点
pnew->data = x：将传入的数据 x 存入新节点。
pnew->next = NULL：由于是尾插，新节点将成为新的最后一个节点，所以必须把它的指针域显式置为 NULL（对应图片中“记得把节点的存放的指针置为空”）。
3. 分情况处理
情况一：链表为空（if (*pphead == NULL)）
如果头指针指向空，说明此时链表中还没有任何数据节点。
操作：*pphead = pnew 直接将头指针指向刚刚创建的新节点。
情况二：链表非空（else 分支）
如果链表里已经有数据，就需要“找尾巴”和“链接”。
操作：找尾（遍历链表） SLTNode* prev = *pphead：定义一个遍历指针 prev，从头节点开始。
while (prev->next) { prev = prev->next; }：依次往后走，直到 prev 指向的节点的 next 为空。 此时prev 刚好停在最后一个节点上。
链接（修改指针）：prev->next = pnew;：把当前最后一个节点（prev）的 next 指针指向新 节点（pnew）。至此，新节点成功被连接到链表的尾部。
头插实现
//前插节点
void SLTPushFront(SLTNode** pphead, SLTDataType x);
头插就是在链表的最前面插入数据
这里的参数和上面是差不多的，这里就不过多赘述了。
//头插节点
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);//检查空指针
//申请空间
SLTNode* pnew = (SLTNode*)malloc(sizeof(SLTNode));
if (!pnew)
{
perror("malloc");
exit(1);
}
//修改新节点data,next
pnew->data = x;
//处理无节点的情况
if (*pphead == NULL)
{
//定义首指针
*pphead = pnew;
(*pphead)->next = NULL;
return;
}
//有节点
else {
//链接首节点
SLTNode* nest = *pphead;
*pphead = pnew;
pnew->next = nest;
}
}
解释：
1. 申请空间：申请堆区空间（malloc），用于存放新节点，并检查申请是否成功（if (!pnew)）。
2. 初始化新节点：在申请的空间中放入要插入的数据 pnew->data = x;。
接下来同样是分两种情况处理：
情况一：if (链表中没有数据，即 *pphead == NULL)
3. 修改头指针，让头指针指向新生成的节点 *pphead = pnew。
4. 因为是唯一的节点，记得把它的指针域置为空 (*pphead)->next = NULL。
情况二、else (链表中有数据)
3. 因为我们要把新节点放到最前面，所以需要先保存原来的头节点。定义临时指针 SLTNode* next = *pphead;
4. 修改头指针的指向，让它指向新生成的节点 *pphead = pnew;。
5. 将新节点的指针指向刚才保存的旧头节点 pnew->next = nest;，至此链接完成。
尾删节点
//尾删节点
void SLTPopBack(SLTNode** pphead);
就是在链表尾部删除节点
//尾删节点
void SLTPopBack(SLTNode** pphead)
{
assert(pphead && *pphead);
//找到前置节点和尾节点
SLTNode* prev = *pphead;
SLTNode* ptail = *pphead;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
//处理只有一个节点的情况
if (ptail == prev)
{
free(ptail);
*pphead= NULL;
}
//多个节点
else{
free(ptail);
prev->next = NULL;
}
}
1. 寻找前驱节点和尾节点
SLTNode* prev = *pphead; 和 SLTNode* ptail = *pphead;：定义两个指针，一开始都指向头节点。
while (ptail->next) 循环内部：
prev = ptail; 让 prev 紧跟在 ptail 后面。
ptail = ptail->next; 让 ptail 继续向后走。
循环结束条件：当 ptail->next 为 NULL 时循环停止。此时 ptail 指向尾节点，而 prev 刚好指向倒数第二个节点（尾节点的前驱）。
2. 分情况处理
情况一：链表只有一个节点（if (ptail == prev)）
如果是单节点，ptail 和 prev 都会指向同一个节点（首尾相同）。
free(ptail)：直接释放这个唯一节点的内存。
*pphead = NULL：因为节点被释放了，原来的头指针就变成了“野指针”。必须将头指针置为 NULL，表示此时链表已空。
情况二：链表有多个节点（else）
此时 ptail 指向尾节点，prev 指向倒数第二个节点。
free(ptail);：释放尾节点的内存空间。
prev->next = NULL;：将新的尾节点（原来的倒数第二个节点）的指针域置为空，确保结 构完整（它现在是新的尾巴了）。
头删节点
//头删节点
void SLTPopFront(SLTNode** pphead);
就是在链表头部删除节点
//头删节点
void SLTPopFront(SLTNode** pphead)
{
assert(pphead && *pphead);
//处理只有一个节点的情况
if ((*pphead)->next == NULL)
{
SLTPopBack(pphead);
return;
}
//多个节点
else{
//保存新的首节点地址
SLTNode* next = (*pphead)->next;
//释放空间
free(*pphead);
//定义首指针
*pphead = next;
}
}
1. 分情况处理
情况一：链表只有一个节点（if ((*pphead)->next == NULL)）
SLTPopBack(pphead)：在只有一个节点的情况下，头删和尾删是同一个操作。代码直接复用了之前写好的尾删函数 SLTPopBack 来处理
情况二：链表有多个节点（else 分支）
如果有多个节点，删除头节点后，我们需要让第二个节点成为新的头节点。
SLTNode* next = (*pphead)->next;：先保存新头节点的地址。定义一个临时指针 next，让它指向原来的第二个节点。如果不先保存，一旦释放了旧的头节点，我们就找不到后面的链表了。
free(*pphead);：释放旧的头节点内存。
*pphead = nest：修改头指针，让它指向刚刚保存的新头节点（即原来的第二个节点）。
打印链表
//打印单链表
void SLTPrint(SLTNode* phead);
就是打印链表中每一个节点的数据
这里由于不用修改头指针和链表数据，索性使用一级指针吧
//打印
void SLTPrint(SLTNode* phead)
{
//遍历链表并打印
SLTNode* pcur = phead;
while (pcur)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
//表明最后的节点指向NULL
printf("NULL\n");
}
循环遍历：
while (pcur)：只要 pcur 不为空（还没有走到链表末尾），就继续循环。
printf("%d->", pcur->data);：打印当前节点的数据，并加上 -> 符号。
pcur = pcur->next;：指针向后移动，指向下一个节点。
打印出来的效果：1->2->3->4->NULL;
销毁链表
//销毁链表
void SListDesTroy(SLTNode** pphead);
就是销毁创建的每一个节点，释放内存。
//销毁链表
void SListDesTroy(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* next = *pphead;
SLTNode* pcur = *pphead;
while (pcur)
{
next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
1. 定义遍历与辅助指针：
SLTNode* next = *pphead; 和 SLTNode* pcur = *pphead;：一开始都指向头节点。
2. 循环释放内存：
while (pcur)：只要当前节点 pcur 不为空，就继续循环。
next = pcur->next;：在释放 pcur 之前，先把下一个节点的地址保存到 next 中。
free(pcur);：释放当前节点占用的内存。
pcur = next;：让 pcur 移动到刚才保存的下一个节点，准备下一轮释放。
心得体会：
到这里就结束了，已经是凌晨00：40了，写到这里真的是身心俱疲，实在写不下去了，至于没写的函数，贪吃蛇用不到的，我就不写了。唉，想要坚持下去真的不容易，但每次写完看到有人点赞，虽然可能都没认真看，人也不多，但想到有人支持我，都会莫名感动，我想这就是我坚持下去的动力吧。最近开学了，课是排的满满当当，有的还听不懂，只能调整为月更了。好吧，就不吐苦水了，翻这么久翻到这里也不容易，就来张图吧
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/lei_jiale/article/details/167282702
