C语言：贪吃蛇前奏曲——链表的创建与维护

下一文章将会介绍贪吃蛇小游戏的实现这一章节主要介绍写游戏需要用到的数据结构——链表一、什么是链表链表是一种线性的数据结构由一系列的节点组成每一个节点包含两部分●数据域存放数据的部分●指针域存放指向下一个节点的指针如图上图中一个方框就是一个节点如地址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 #includestdio.h #includestdlib.h #includeassert.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-gt;data x; pnew-gt;next NULL; //处理空链表的情况 if (*pphead NULL) { //修改首指针 *pphead pnew; return; } //有节点 else { //遍历链表找到前驱节点即最后一个节点 SLTNode* prev *pphead; while (prev-gt;next) { prev prev-gt;next; } //链接前驱节点 prev-gt;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-gt;data x; //处理无节点的情况 if (*pphead NULL) { //定义首指针 *pphead pnew; (*pphead)-gt;next NULL; return; } //有节点 else { //链接首节点 SLTNode* nest *pphead; *pphead pnew; pnew-gt;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-gt;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-gt;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 移动到刚才保存的下一个节点准备下一轮释放。心得体会到这里就结束了已经是凌晨0040了写到这里真的是身心俱疲实在写不下去了至于没写的函数贪吃蛇用不到的我就不写了。唉想要坚持下去真的不容易但每次写完看到有人点赞虽然可能都没认真看人也不多但想到有人支持我都会莫名感动我想这就是我坚持下去的动力吧。最近开学了课是排的满满当当有的还听不懂只能调整为月更了。好吧就不吐苦水了翻这么久翻到这里也不容易就来张图吧