rt-thread 双链表分析及教程(附带demo)

[sky-littlestar]

本次实验使用的是(Visual Studio 2022,EasyX)文末附完整代码，可直接复制运行

前言

 我们平时在进行玩电子游戏时，会发现很多资源都是动态加载的，会不断的生成加载和删除。比如说，我们玩飞机大战时，不同的关卡和地图中，生成的飞机数量是不一样的，然后他被我们的炮弹击落后，飞机的数量又会减少，飞机数量一直处于不确定的状态。我们在玩贪食蛇游戏时，蛇身的长度也是不固定的，蛇吃到食物时，身体会变长，蛇碰到障碍物时，身体会变短，处于一个动态变化的过程。因此，在设计这类动态加载资源的场景是，数组是不太合适的(数组是静态的，在固定初始长度后，不方便扩展)，因此，采用链表完成此类应用场景是比较理想的选择。按照传统教科书的教程，我们一般的链表都是一个指针域+一个数据域，通过遍历链表上的每一个节点，得到相关数据。

其数据结构如下表示(以双链表为例子)
typedef struct DLnode
{
int data; //也可以是其他数据类型
DLnode* next;
DLnode* next;
}DLnode_list;
但是，这种固定数据域的方法，并不方便灵活，这要求我们链表上的节点用的都是统一的结构体，由于各个用户对链表数据的需求不同，是没办法直接通过一个统一的API接口，进行链表初始化的。我们可以参考一下rt-thread实时操作系统的做法。把指针域单独提取出来，通过指针域再进行数据域的访问，下面，我们将通过经典的贪食蛇游戏进行示例讲解。

本次实验需要使用到Visual Studio 2022，EasyX图形库。
EasyX的坐标系如下：

贪食蛇需要一个蛇头，还有一段蛇身，其实，每一个蛇的部位，就是一个节点，我们统一用一个结构体进行表示。

enum COMPRESS_E                 //当前节点的运行方向
{
	COMPRESS_UP,
	COMPREES_DOWN,
	COMPRESS_LEFT,
	COMPRESS_RIGHT,
};

typedef struct doublelink_listnode   //当前蛇身节点
{
	doublelink_listnode* prev;
	doublelink_listnode* next;
}Doublelink_listnode;

typedef struct                               //蛇的节点结构体
{
	float x;                                  
	float y;                                
	COLORREF color;                
	COMPRESS_E compass;
	Doublelink_listnode node;
}Snake;

这样，我们通过计算蛇的每一个节点的位置，并通过链表将其串联起来，改变链表上节点的位置数据，就是在操纵蛇身的移动。通过增加链表上的节点或者删除链表上的节点，即可以实现蛇身的增长或缩短。首先，我们先初始化一个头节点。
Doublelink_listnode list;
list= Doublelink_Listinit(list);

其前驱节点后后继节点均指向自身。
随后，将蛇身插入链表中,我们先初始化6节蛇身，一个圆点表示一段蛇身。

注意，分配空间的时候，要按蛇的整个结构体去分配，不能仅分配Doublelink_listnode node。这是RT-Thread链表和我们平时用的带数据域的链表很大的不同，假如仅分配Doublelink_listnode node，由于该变量的作用域仅在该函数中，当跳转到其他函数时，Snake中的其他数据会被破坏，会导致程序出错。

for (int i = 0; i < 6; i++)   
{
	Snake* snake= (Snake*)malloc(sizeof(Snake));
	snake ->x=(i* Radius*2)+100;
	snake ->y= 300;
	snake->color = RED;
	snake->compass = COMPRESS_RIGHT;
	doublelink_insertback(&list, &(snake->node));  //将蛇的蛇身插入链表中
}

entrylist_foreach(&list,pos)   //遍历6段蛇身，并将其坐标信息以圆圈的形式在图上画出来
{
	setlinecolor(list_entry(pos, Snake, node)->color);
	setfillcolor(list_entry(pos, Snake, node)->color);
	fillcircle(list_entry(pos, Snake, node)->x, list_entry(pos, Snake, node)->y, Radius);   //以圆圈的形式画出来
}

通过doublelink_insertback将数据插入链表，然后我们再entrylist_foreach遍历链表，list_entry进入node节点即可得到蛇身的位置，然后利用EasyX在界面上描绘出来，就是我们这个游戏的实现思路。

我们通过一个最小例子，展示一下RT-thread双链表的插入，遍历，读取用法。
分析一下void doublelink_insertback(Doublelink_listnode* list, Doublelink_listnode* node)；其函数定义如下：

void doublelink_insertback(Doublelink_listnode* list, Doublelink_listnode* node)
{
	node->next = list->next; //1
	list->next->prev = node;  //2
	list->next = node;   //3
	node->prev = list;   //4
}

假设之前node1已经插入到链表中，此时我们调用doublelink_insertback(&head, &(node2.node));，将node2插入到链表中，图中分别对应函数中的四个过程:
图中的标号1，对应node->next = list->next;插入node2,node2的next指针指向node1的指针域;
图中的标号2，对应list->next->prev=node，头指针的next对应的是node1,node1的prev指针更新为node2,正如标号2和下面带红色叉号的箭头所示，head->next的指针被废除，而node2与node1建立起关系，node1->prev=node2;
图中的标号3，对应list->next = node，重新构造list->next指向的地方，如图中上面带红色叉号的箭头所示，head的next指针被重定向,指向node2;
图中的标号4，代表node->prev = list，新插入的node2的prev指针指向head。所以，根据以上的分析我们可以知道，利用doublelink_insertback函数，节点可以插入到链表中，而且，越是后边插入的，当遍历的时候，反而会被优先遍历。
当我们完成链表的插入后，如何遍历链表呢？这个是比较简单的，我们直接通过指针，即可访问各个元素：
#define Doublelink_foreach(list,pos)
for(pos=(&list)->next;pos!=&list;pos=pos->next)
遍历各个元素时，我们还要进入当前节点，读取我们想要的变量
#define list_entry(ptr,type,member)
((type*)((unsigned char*)ptr-(unsigned long)&(((type*)0)->member)))
ptr指的是当前指针指向的位置，type值的是结构体的类型，member是当前指针指向的结构体成员。通过当前指针指向的位置，减去当前指向的成员在结构体中的偏移量，可以知道当前结构体的地址，然后通过指针去访问当前结构体成员可以得到访问变量的值。


下面，运行一个demo展示一下具体用法：

typedef struct Doublelink_listnode
{
	Doublelink_listnode* prev;
	Doublelink_listnode* next;
}Doublelink_list;

typedef struct 
{
	uint8_t data;
	Doublelink_listnode node;
}Doublelink_listdata;

Doublelink_list		head;
Doublelink_list*	pos;
#define Doublelink_Listinit(list) {&list,&list}
#define Doublelink_foreach(list,pos)  \
				  for(pos=(&list)->next;pos!=&list;pos=pos->next)
#define list_entry(ptr,type,member)   \
				  ((type*)((unsigned char*)ptr-(unsigned long)&(((type*)0)->member)))

void doublelink_insertback(Doublelink_listnode* list, Doublelink_listnode* node);
int main()
{
	head=Doublelink_Listinit(head);
	Doublelink_listdata node1;
	node1.data = 1;
	doublelink_insertback(&head, &(node1.node));
	Doublelink_listdata node2;
	node2.data = 2;
	doublelink_insertback(&head, &(node2.node));
	Doublelink_listdata node3;
	node3.data = 3;
	doublelink_insertback(&head, &(node3.node));
	
	Doublelink_foreach(head, pos)
	{
		printf("%d\r\n", list_entry(pos, Doublelink_listdata, node)->data);
	}
}

void doublelink_insertback(Doublelink_listnode* list, Doublelink_listnode* node)
{
	node->next = list->next;
	list->next->prev = node;
	list->next = node;
	node->prev = list;
}

运行结果正确。
蛇身生成完毕，还要生成食物和怪兽，蛇吃到食物后，蛇身会变长，遇到怪兽后，蛇身会变短。
初始化蛇身和怪兽的坐标：

#define Food_Num       5
#define Master_Num     2
for (int i = 0; i < Food_Num; i++)
{
	Food_pos[i].x = -1;
	Food_pos[i].y = -1;
}

for (int i = 0; i < Master_Num; i++)
{
	Master_pos[i].x = -1;
	Master_pos[i].y = -1;
}

初始化蛇，食物和怪兽后，调用绘图函数，在界面上根据坐标绘制图形。

cleardevice();                                                                           //清空画布
entrylist_foreach(&list,pos)                                                     //遍历蛇身，根据蛇身，绘制圆形
{
	setlinecolor(list_entry(pos, Snake, node)->color);
	setfillcolor(list_entry(pos, Snake, node)->color);
	fillcircle(list_entry(pos, Snake, node)->x, list_entry(pos, Snake, node)->y, Radius);
}

for (int i = 0; i < Food_Num; i++)                                           //根据坐标，绘制食物
{
	setlinecolor(HSVtoRGB(i * 30, 0.6, 1));
	setfillcolor(HSVtoRGB(i * 30, 0.6, 1));
	fillrectangle(Food_pos[i].x, Food_pos[i].y, Food_pos[i].x+(2* Radius), Food_pos[i].y + (2 * Radius));       //绘制正方形
}

for (int i = 0; i < Master_Num; i++)                                        //根据坐标，绘制怪兽
{
	setlinecolor(RED);
	setfillcolor(BROWN);
	POINT pts[] = { {Master_pos[i].x, Master_pos[i].y-Radius}, {Master_pos[i].x- Radius, Master_pos[i].y + Radius},  {Master_pos[i].x + Radius, Master_pos[i].y + Radius} };               //绘制三角形
	fillpolygon(pts, 3);
}

当资源都加载完毕时，我们可以通过键盘操纵蛇的移动

enum COMPRESS_E
{
	COMPRESS_UP,
	COMPREES_DOWN,
	COMPRESS_LEFT,
	COMPRESS_RIGHT,
};

if (_kbhit())                                     //当探测到键盘输入时
{
	char input = _getch();
	switch (input)
	{
		case KEY_UP:                                                                 
			if (list_entry_firstnode(pos, Snake, node)->compass != COMPREES_DOWN)
			{
				list_entry_firstnode(pos, Snake, node)->compass = COMPRESS_UP; 
			}   //按下向上键，当蛇头的移动方向不是向下时，蛇头的移动方向设置为向上
			break;
		case KEY_DOWN: 
			if (list_entry_firstnode(pos, Snake, node)->compass != COMPRESS_UP)
			{
				list_entry_firstnode(pos, Snake, node)->compass = COMPREES_DOWN;
			}   //按下向上键，当蛇头的移动方向不是向上时，蛇头的移动方向设置为向下
			break;
		case KEY_LEFT: 
			if (list_entry_firstnode(pos, Snake, node)->compass != COMPRESS_RIGHT)
			{
				list_entry_firstnode(pos, Snake, node)->compass = COMPRESS_LEFT;
			}   //按下向上键，当蛇头的移动方向不是向右时，蛇头的移动方向设置为向左
			break;
		case KEY_RIGHT: 
			if (list_entry_firstnode(pos, Snake, node)->compass != COMPRESS_LEFT)
			{
				list_entry_firstnode(pos, Snake, node)->compass = COMPRESS_RIGHT;
			}    //按下向上键，当蛇头的移动方向不是向左时，蛇头的移动方向设置为向右
			break;
	}
	if (gamestatus == -1)
	{
		start_up();   //当游戏为结束状态时，按下任意键，重启
	}
}

#define list_entry_firstnode(list,type,member)
((type*)((char*)((list)->next)-(unsigned long)(&((type*) 0)->member)))
进入链表的第一个节点，可以直接求出蛇头。

if (list_entry_firstnode(&list, Snake, node)->x >= WindowWidth|| list_entry_firstnode(&list, Snake, node)->x <= 0\
	|| list_entry_firstnode(&list, Snake, node)->y <= 0|| list_entry_firstnode(&list, Snake, node)->y>=WindowHeight\
	|| doublelink_nodenum(&list) < 2
	)
{
	entrylist_foreach(&list, pos)
	list_entry(pos, Snake, node)->color = GREEN; 
	gamestatus = -1;  //碰撞检测，当蛇头到达界面的边缘时，游戏结束
}

entrylist_foreach((&list)->next, pos)
{
	if (list_entry(pos, Snake, node)->x == list_entry_firstnode(&list, Snake, node)->x && list_entry(pos, Snake, node)->y == list_entry_firstnode(&list, Snake, node)->y)
	{
		gamestatus = -1;   //碰撞检测，当蛇头与其他蛇身部位碰撞时，游戏结束
	}
}

list_entry_firstnode(&list, Snake, node)->x += dirs[list_entry_firstnode(&list, Snake, node)->compass][0] * Speed*2; 
//结合移动方向和速度更新蛇头的x坐标
list_entry_firstnode(&list, Snake, node)->y += dirs[list_entry_firstnode(&list, Snake, node)->compass][1] * Speed*2;
//结合移动方向和速度更新蛇头的y坐标

entrylist_foreach(&list,pos)     
{	
	if (pos->next != (&list))   //更新蛇身各段的坐标
	{
	list_entry(pos->next, Snake, node)->x = list_entry(pos, Snake, node)->x - dirs[list_entry(pos, Snake, node)->compass][0] * Radius * 2;
	list_entry(pos->next, Snake, node)->y = list_entry(pos, Snake, node)->y - dirs[list_entry(pos, Snake, node)->compass][1] * Radius * 2;
	}
}


for (pos = (&list)->prev; pos != &list; pos = pos->prev)
{
	if (pos != (&list)->next)   //更新蛇身各段的移动方向
		list_entry(pos, Snake, node)->compass = list_entry(pos->prev, Snake, node)->compass;
}

蛇的身体各段坐标计算方法如下：

当此时接收到键盘来的指令向下时，蛇头的运动方向变为向下，随后更新蛇的各个节点坐标。

随后，由于你的蛇头运动方向已经更改，所以蛇身的各个方向也会随着变化，后一个节点的运动方向将会继承前一个节点。

所以蛇身的轨迹更新模块，我们已经完成。
下面还需要一些事件更新模块，比如说，蛇吃到食物，蛇身会变长，蛇遇到怪兽，蛇身会变短。

void snake_eatfood(void)   //蛇吃到食物
{
	for (int i = 0; i < Food_Num; i++)
	{
		if ((list_entry_firstnode(&list, Snake, node)->x) >= Food_pos[i].x- Radius && (list_entry_firstnode(&list, Snake, node)->x) <= Food_pos[i].x + 3 * Radius &&\
			(list_entry_firstnode(&list, Snake, node)->y) >= Food_pos[i].y- Radius && (list_entry_firstnode(&list, Snake, node)->y) <= Food_pos[i].y + 3 * Radius \
			)     //坐标检测，由于食物占用一定空间，当蛇头的坐标与食物的坐标距离在一定范围内，认为蛇吃到食物
		{
			Food_pos[i].x = -1;
			Food_pos[i].y = -1;
			Snake* snake = (Snake*)malloc(sizeof(Snake));
			snake->color = GREEN;
			snake->compass = list_entry((&list)->prev,Snake,node)->compass;   
			doublelink_inserttop(&list,&(snake->node)); 
			return; //分配更多的节点，蛇身边长，这次是doublelink_inserttop，将节点加到蛇尾后边，分析方法跟之前insertback一样
		}
	}
}

void food_generate(void)  //生成食物
{
	int count = 0;
	int index[Food_Num];

	for (int i = 0; i < Food_Num; i++)
	{
		if ((Food_pos[i].x == -1 && Food_pos[i].y == -1))  //当食物坐标为x=-1,y=-1时，证明没有加载，需要生成
		{
			index[count]=i;
			count++;
		}
	}

	while(count)   //生成一定数量的食物，生成完退出
	{
		uint16_t x_rand = rand() % (WindowWidth - 2* Radius);
		uint16_t y_rand = rand() % (WindowHeight - 2 * Radius);
		int pos_legal = 1;


		for (int i = 0; i < Food_Num; i++)
		{
			if ((Food_pos[i].x == x_rand && Food_pos[i].y == y_rand))  //假如新生成的食物坐标，与现有的食物重叠，判定不合法，重新生成
			{
				pos_legal = 0;
				break;
			}
		}

		for (int i = 0; i < Master_Num; i++) //假如新生成的食物坐标，与现有的怪兽坐标重叠，判定不合法，重新生成
		{
			if (Master_pos[i].x == x_rand && Master_pos[i].y == y_rand)
			{
				pos_legal = 0;
				break;
			}
		}

		if (pos_legal)    //合法食物坐标，可以生成
		{
			Food_pos[index[count-1]].x = x_rand;
			Food_pos[index[count-1]].y = y_rand;
			count--;
		}
	}
}

void snake_acrossmaster(void)
{
	for (int i = 0; i < Master_Num; i++)
	{
		if ((list_entry_firstnode(&list, Snake, node)->x) >= Master_pos[i].x - Radius && (list_entry_firstnode(&list, Snake, node)->x) <= Master_pos[i].x + Radius \
			&& (list_entry_firstnode(&list, Snake, node)->y) >= Master_pos[i].y - Radius && (list_entry_firstnode(&list, Snake, node)->y) <= Master_pos[i].y + Radius
			)  //坐标检测，由于怪兽占用一定空间，当蛇头的坐标与怪兽的坐标距离在一定范围内，认为蛇遇到怪兽
		{        //撞到怪兽，每次减少两节蛇身，前面的代码我们判定，当蛇身小于2节时，游戏结束，所以来到这里，蛇身是大于2节的，能够删除
			for (int j = 0; j < 2; j++)  
			{
				Snake* snake = list_entry((&list)->prev,Snake,node);
				doublelink_removenode((&list)->prev);  //移除节点
				if (snake != NULL)
				{
					free(snake);      //释放内存
					snake = NULL;
				}
			}
			Master_pos[i].x = -1;
			Master_pos[i].y = -1;
		}
	}
}

void generate_master(void)   //生成怪兽
{
	uint8_t count = 0;
	int index[Master_Num];

	for (int i = 0; i < Master_Num; i++)  //当怪兽坐标为x=-1,y=-1时，证明没有加载，需要生成
	{
		if (Master_pos[i].x == -1 && Master_pos[i].y == -1)
		{
			index[count] = i;
			count++;
		}
	}

	while (count)
	{
		uint8_t poslegal=1;
		uint16_t x_pos = Radius + rand() % (WindowWidth - 2 * Radius);
		uint16_t y_pos = Radius + rand() % (WindowHeight - 2 * Radius);

		for (int i = 0; i < Master_Num; i++)   //假如新生成的怪兽坐标，与现有的怪兽重叠，判定不合法，重新生成
		{
			if (Master_pos[i].x == x_pos && Master_pos[i].y == y_pos)
			{
				poslegal = 0;
				break;
			}
		}
 
		for (int i = 0; i < Food_Num; i++)  //假如新生成的怪兽坐标，与现有的食物重叠，判定不合法，重新生成
		{
			if (Food_pos[i].x == x_pos && Food_pos[i].y == y_pos)
			{
				poslegal = 0;
				break;
			}
		}

		if (poslegal)    //合法怪兽坐标，可以生成
		{
			Master_pos[index[count-1]].x = x_pos;
			Master_pos[index[count-1]].y = y_pos;
			count--;
		}
	}
}

至此，我们已经介绍完蛇身的坐标计算方法，食物的生成方法，蛇身的增长方法，怪兽的生成方法，已经遇到怪兽蛇身变短的计算方法。游戏基本运行逻辑已经建立起来。但是，我们前面说过，当蛇撞到墙(界面边缘)也会死去，触发游戏结束界面，此时，我们也应该把蛇的节点全部去掉，为下一轮游戏重启做准备。于是，我又添加了以下逻辑：

if (gamestatus == -1)
{
	settextstyle(WindowHeight/ 20, 0, _T("宋体")); // 设置文字大小、字体
	// 设定文字颜色，不同数值，颜色不同					
	settextcolor(RGB(120, 120, 120));
	RECT r = { 0,0,WindowWidth,WindowHeight };
	if (gamestatus == -1)
		drawtext(_T("游戏失败，按任意键重新开始"), &r, DT_CENTER | DT_VCENTER | DT_SINGLELINE);
	else if (gamestatus == 1)
		drawtext(_T("游戏胜利，按任意键重新开始"), &r, DT_CENTER | DT_VCENTER | DT_SINGLELINE);

	if (!doublelink_isempty(&list))
	{
		Doublelink_listnode* temp = NULL;
		entrylist_foreach_safe(&list, pos, temp)  //安全遍历链表
		{
			doublelink_removenode(pos);    //删除节点
			Snake* snake = list_entry(pos, Snake, node);
			if (snake != NULL)
			{
				free(snake);  //释放空间
				snake = NULL;
			}
		}
		temp = NULL;
	}
}

值得注意的是，这里删除节点的遍历方法和之前的遍历方法不一样。
我们引入了安全遍历，entrylist_foreach_safe(&list, pos, temp)；
#define entrylist_foreach_safe(head,pos,temp)
for(pos=(head)->next,temp=pos->next;pos!=head;pos=temp,temp=pos->next)
安全遍历与普通遍历相比，多了temp，记录将要遍历的下一个节点，假如我们利用普通遍历，删除节点的时候不记录下一个节点的方向，释放当前节点pos后，将无法进行下一步寻址。

假设，此时调用，doublelink_removenode(pos)；

void doublelink_removenode(Doublelink_listnode* node)
{
	node->prev->next = node->next;
	node->next->prev = node->prev;

	node->next = node;
	node->prev = node;
}

如上图所示，node2的前节点node3和后节点node1将会建立联系，node3->next=node1;node1->prev=node3;
但是，经过这一步操作后，node2将会成为一个孤立的节点，他的next和prev将会指向自己。我们将无法通过node2找到他的下一个节点node1。


当我们此时调用for(pos=(head)->next;pos!=(head);pos=pos->next)，由于找不到pos->next所以会直接导致死机。
而我们采用安全遍历，for(pos=(head)->next,temp=pos->next;pos!=head;pos=temp,temp=pos->next)可以有效地避免这一个问题。

我们的创建一个指针temp，指向当前节点pos的下一个节点，假如我们执行doublelink_removenode时要移除pos时，由于我们已经保存了temp，我们下一轮直接读取temp,我们也可以进入到下一个节点。

至于我们之前蛇碰到食物时，为啥不用安全遍历，因为我们当时删除蛇身，不是用遍历链表的方法，而是用循环，直接找到尾节点删除的。

至此，我们游戏的各个模块都已经搭建完毕，下面我直接贴出运行代码，读者可以下载Easy X图形库，复制代码到VS 2022平台，直接运行，体验游戏。

#include <stdio.h>
#include <stdlib.h>
#include<time.h>
#include<stdint.h>
#include<graphics.h>
#include<conio.h>
#include<assert.h>
#include<math.h>
#include<string.h>
#include<time.h>

#define WindowWidth    600
#define WindowHeight   500
#define Radius         10
#define Speed          10
#define Food_Num       5
#define Master_Num     2
#define ROWNUM         50
#define COLNUM         60
#define KEY_UP         72
#define KEY_DOWN       80
#define KEY_LEFT       75
#define KEY_RIGHT      77
#define Doublelink_Listinit(list) {&list,&list}
#define list_entry(ptr,type,member) \
	((type*)((char*)(ptr)-(unsigned long)(&((type*) 0)->member)))
#define list_entry_firstnode(list,type,member)\
	((type*)((char*)((list)->next)-(unsigned long)(&((type*) 0)->member)))
#define entrylist_foreach(head,pos) \
	for(pos=(head)->next;pos!=(head);pos=pos->next)
#define entrylist_foreach_safe(head,pos,temp) \
	for(pos=(head)->next,temp=pos->next;pos!=head;pos=temp,temp=pos->next)

enum COMPRESS_E
{
	COMPRESS_UP,
	COMPREES_DOWN,
	COMPRESS_LEFT,
	COMPRESS_RIGHT,
};

typedef struct doublelink_listnode
{
	doublelink_listnode* prev;
	doublelink_listnode* next;
}Doublelink_listnode;

typedef struct
{
	float x;
	float y;
	COLORREF color;
	COMPRESS_E compass;
	Doublelink_listnode node;
}Snake;

typedef struct
{
	int x;
	int y;
}Coordinate;

const int dirs[4][2] = { {0,-1},{0,1},{-1,0},{1,0} };
Coordinate Food_pos[Food_Num];
Coordinate Master_pos[Master_Num];
Doublelink_listnode list;
Doublelink_listnode* pos=NULL;
int gamestatus = 0;
void start_up(void);
void show(void);
void update(void);
void food_generate(void);
void generate_master(void);
void snake_eatfood(void);
void snake_acrossmaster(void);
void doublelink_listinit(doublelink_listnode* list);
void doublelink_insertback(Doublelink_listnode* list, Doublelink_listnode* node);
void doublelink_inserttop(Doublelink_listnode* list, Doublelink_listnode* node);
void doublelink_removenode(Doublelink_listnode* node);
int doublelink_isempty(Doublelink_listnode* list);
uint8_t doublelink_nodenum(const Doublelink_listnode* list);

int main()
{
	start_up();
	while (1)
	{
		show();
		update();
	}
	_getch();
	return 1;
}

void start_up(void)
{
	srand((unsigned)time(NULL));
	initgraph(WindowWidth, WindowHeight);
	BeginBatchDraw();
	setbkcolor(RGB(0, 0, 0));
	cleardevice();
	gamestatus = 0;
	list= Doublelink_Listinit(list);
	for (int i = 0; i < 6; i++)
	{
		Snake* snake= (Snake*)malloc(sizeof(Snake));
		snake ->x=(i* Radius*2)+100;
		snake ->y= 300;
		snake->color = RED;
		snake->compass = COMPRESS_RIGHT;
		doublelink_insertback(&list, &(snake->node));
	}

	for (int i = 0; i < Food_Num; i++)
	{
		Food_pos[i].x = -1;
		Food_pos[i].y = -1;
	}

	for (int i = 0; i < Master_Num; i++)
	{
		Master_pos[i].x = -1;
		Master_pos[i].y = -1;
	}
}

void show(void)
{
	cleardevice();
	entrylist_foreach(&list,pos)
	{
		setlinecolor(list_entry(pos, Snake, node)->color);
		setfillcolor(list_entry(pos, Snake, node)->color);
		fillcircle(list_entry(pos, Snake, node)->x, list_entry(pos, Snake, node)->y, Radius);
	}

	for (int i = 0; i < Food_Num; i++)
	{
		setlinecolor(HSVtoRGB(i * 30, 0.6, 1));
		setfillcolor(HSVtoRGB(i * 30, 0.6, 1));
		fillrectangle(Food_pos[i].x, Food_pos[i].y, Food_pos[i].x+(2* Radius), Food_pos[i].y + (2 * Radius));
	}

	for (int i = 0; i < Master_Num; i++)
	{
		setlinecolor(RED);
		setfillcolor(BROWN);
		POINT pts[] = { {Master_pos[i].x, Master_pos[i].y-Radius}, {Master_pos[i].x- Radius, Master_pos[i].y + Radius},  {Master_pos[i].x + Radius, Master_pos[i].y + Radius} };
		fillpolygon(pts, 3);
	}

	if (gamestatus == -1)
	{
		settextstyle(WindowHeight/ 20, 0, _T("宋体")); // 设置文字大小、字体
		// 设定文字颜色，不同数值，颜色不同					
		settextcolor(RGB(120, 120, 120));
		RECT r = { 0,0,WindowWidth,WindowHeight };
		if (gamestatus == -1)
			drawtext(_T("游戏失败，按任意键重新开始"), &r, DT_CENTER | DT_VCENTER | DT_SINGLELINE);
		else if (gamestatus == 1)
			drawtext(_T("游戏胜利，按任意键重新开始"), &r, DT_CENTER | DT_VCENTER | DT_SINGLELINE);

		if (!doublelink_isempty(&list))
		{
			Doublelink_listnode* temp = NULL;
			entrylist_foreach_safe(&list, pos, temp)
			{
				doublelink_removenode(pos);
				Snake* snake = list_entry(pos, Snake, node);
				if (snake != NULL)
				{
					free(snake);
					snake = NULL;
				}
			}
			temp = NULL;
		}
	}
	Sleep(100);
	FlushBatchDraw();
}

void update(void)
{
	if (_kbhit())
	{
		char input = _getch();
		switch (input)
		{
			case KEY_UP:   
				if (list_entry_firstnode(pos, Snake, node)->compass != COMPREES_DOWN)
				{
					list_entry_firstnode(pos, Snake, node)->compass = COMPRESS_UP;
				}
				break;
			case KEY_DOWN: 
				if (list_entry_firstnode(pos, Snake, node)->compass != COMPRESS_UP)
				{
					list_entry_firstnode(pos, Snake, node)->compass = COMPREES_DOWN;
				}
				break;
			case KEY_LEFT: 
				if (list_entry_firstnode(pos, Snake, node)->compass != COMPRESS_RIGHT)
				{
					list_entry_firstnode(pos, Snake, node)->compass = COMPRESS_LEFT;
				}
				break;
			case KEY_RIGHT: 
				if (list_entry_firstnode(pos, Snake, node)->compass != COMPRESS_LEFT)
				{
					list_entry_firstnode(pos, Snake, node)->compass = COMPRESS_RIGHT;
				}
				break;
		}
		if (gamestatus == -1)
		{
			start_up();
		}
	}

	if (list_entry_firstnode(&list, Snake, node)->x >= WindowWidth|| list_entry_firstnode(&list, Snake, node)->x <= 0\
		|| list_entry_firstnode(&list, Snake, node)->y <= 0|| list_entry_firstnode(&list, Snake, node)->y>=WindowHeight\
		|| doublelink_nodenum(&list) < 2
		)
	{
		entrylist_foreach(&list, pos)
		list_entry(pos, Snake, node)->color = GREEN;
		gamestatus = -1;
	}

	entrylist_foreach((&list)->next, pos)
	{
		if (list_entry(pos, Snake, node)->x == list_entry_firstnode(&list, Snake, node)->x && list_entry(pos, Snake, node)->y == list_entry_firstnode(&list, Snake, node)->y)
		{
			gamestatus = -1;
		}
	}

	list_entry_firstnode(&list, Snake, node)->x += dirs[list_entry_firstnode(&list, Snake, node)->compass][0] * Speed*2;
	list_entry_firstnode(&list, Snake, node)->y += dirs[list_entry_firstnode(&list, Snake, node)->compass][1] * Speed*2;

	entrylist_foreach(&list,pos)
	{	
		if (pos->next != (&list))
		{
			list_entry(pos->next, Snake, node)->x = list_entry(pos, Snake, node)->x - dirs[list_entry(pos, Snake, node)->compass][0] * Radius * 2;
			list_entry(pos->next, Snake, node)->y = list_entry(pos, Snake, node)->y - dirs[list_entry(pos, Snake, node)->compass][1] * Radius * 2;
		}
	}
	

	for (pos = (&list)->prev; pos != &list; pos = pos->prev)
	{
		if (pos != (&list)->next)
			list_entry(pos, Snake, node)->compass = list_entry(pos->prev, Snake, node)->compass;
	}
	food_generate();
	generate_master();
	snake_eatfood();
	snake_acrossmaster();
}

void food_generate(void)
{
	int count = 0;
	int index[Food_Num];

	for (int i = 0; i < Food_Num; i++)
	{
		if ((Food_pos[i].x == -1 && Food_pos[i].y == -1))
		{
			index[count]=i;
			count++;
		}
	}

	while(count)
	{
		uint16_t x_rand = rand() % (WindowWidth - 2* Radius);
		uint16_t y_rand = rand() % (WindowHeight - 2 * Radius);
		int pos_legal = 1;


		for (int i = 0; i < Food_Num; i++)
		{
			if ((Food_pos[i].x == x_rand && Food_pos[i].y == y_rand))
			{
				pos_legal = 0;
				break;
			}
		}

		for (int i = 0; i < Master_Num; i++)
		{
			if (Master_pos[i].x == x_rand && Master_pos[i].y == y_rand)
			{
				pos_legal = 0;
				break;
			}
		}

		if (pos_legal)
		{
			Food_pos[index[count-1]].x = x_rand;
			Food_pos[index[count-1]].y = y_rand;
			count--;
		}
	}
}

void snake_eatfood(void)
{
	for (int i = 0; i < Food_Num; i++)
	{
		if ((list_entry_firstnode(&list, Snake, node)->x) >= Food_pos[i].x- Radius && (list_entry_firstnode(&list, Snake, node)->x) <= Food_pos[i].x + 3 * Radius &&\
			(list_entry_firstnode(&list, Snake, node)->y) >= Food_pos[i].y- Radius && (list_entry_firstnode(&list, Snake, node)->y) <= Food_pos[i].y + 3 * Radius \
			)
		{
			Food_pos[i].x = -1;
			Food_pos[i].y = -1;
			Snake* snake = (Snake*)malloc(sizeof(Snake));
			snake->color = GREEN;
			snake->compass = list_entry((&list)->prev,Snake,node)->compass;
			doublelink_inserttop(&list,&(snake->node));
			return;
		}
	}
}

void generate_master(void)
{
	uint8_t count = 0;
	int index[Master_Num];

	for (int i = 0; i < Master_Num; i++)
	{
		if (Master_pos[i].x == -1 && Master_pos[i].y == -1)
		{
			index[count] = i;
			count++;
		}
	}

	while (count)
	{
		uint8_t poslegal=1;
		uint16_t x_pos = Radius + rand() % (WindowWidth - 2 * Radius);
		uint16_t y_pos = Radius + rand() % (WindowHeight - 2 * Radius);

		for (int i = 0; i < Master_Num; i++)
		{
			if (Master_pos[i].x == x_pos && Master_pos[i].y == y_pos)
			{
				poslegal = 0;
				break;
			}
		}

		for (int i = 0; i < Food_Num; i++)
		{
			if (Food_pos[i].x == x_pos && Food_pos[i].y == y_pos)
			{
				poslegal = 0;
				break;
			}
		}

		if (poslegal)
		{
			Master_pos[index[count-1]].x = x_pos;
			Master_pos[index[count-1]].y = y_pos;
			count--;
		}
	}
}

void snake_acrossmaster(void)
{
	for (int i = 0; i < Master_Num; i++)
	{
		if ((list_entry_firstnode(&list, Snake, node)->x) >= Master_pos[i].x - Radius && (list_entry_firstnode(&list, Snake, node)->x) <= Master_pos[i].x + Radius \
			&& (list_entry_firstnode(&list, Snake, node)->y) >= Master_pos[i].y - Radius && (list_entry_firstnode(&list, Snake, node)->y) <= Master_pos[i].y + Radius
			)
		{
			for (int j = 0; j < 2; j++)
			{
				Snake* snake = list_entry((&list)->prev,Snake,node);
				doublelink_removenode((&list)->prev);
				if (snake != NULL)
				{
					free(snake);
					snake = NULL;
				}
			}
			Master_pos[i].x = -1;
			Master_pos[i].y = -1;
		}
	}
}

void doublelink_listinit(Doublelink_listnode* list)
{
	list->prev = list;
	list->next = list;
}

void doublelink_insertback(Doublelink_listnode* list, Doublelink_listnode* node)
{
	node->next = list->next;
	list->next->prev = node;
	list->next = node;
	node->prev = list;
}

void doublelink_inserttop(Doublelink_listnode* list, Doublelink_listnode* node)
{
	list->prev->next = node;
	node->prev = list->prev;
	node->next = list;
	list->prev = node;
}

void doublelink_removenode(Doublelink_listnode* node)
{
	node->prev->next = node->next;
	node->next->prev = node->prev;

	node->next = node;
	node->prev = node;
}

int doublelink_isempty(Doublelink_listnode* list)
{
	return (list->next == list);
}

uint8_t doublelink_nodenum(const Doublelink_listnode* list)
{
	uint8_t len = 0;
	const Doublelink_listnode* p = list;

	while (p->next != list)
	{
		len++;
		p=p->next;

	}
	return len;
}

[sky-littlestar]

各位大佬一起来交流，多多指教

[sky-littlestar]

@sky-littlestar 在 rt-thread 双链表分析及教程(附带demo) 中说：

其数据结构如下表示(以双链表为例子)
typedef struct DLnode
{
int data; //也可以是其他数据类型
DLnode* next;
DLnode* next;
}DLnode_list;

(更正)

其数据结构如下表示(以单链表为例子)
typedef struct SLnode
{
int data; //也可以是其他数据类型
SLnode* next;
}SLnode_list;
更正一下，上面的图是单链表，我这边改单链表说明一下，原理是一样的。

[SPeak]

感觉是不是可以拆分一下, 把游戏主体 和 链表实现 分开 用比较项目的目录树风格, 然后放到github上 变成一个Demo项目

[sky-littlestar]

@SPeak 在 rt-thread 双链表分析及教程(附带demo) 中说：

感觉是不是可以拆分一下, 把游戏主体 和 链表实现 分开 用比较项目的目录树风格, 然后放到github上 变成一个Demo项目

这个写法应该不错，博主有没有什么参考的博文推荐，我学习一下他的写法

[SPeak]

@sky-littlestar 我说的意思就是把你上面的代码 整理一下 用项目(Demo)的方式 放到github, 不是说其他什么写法