【知识分享】数据结构的应用——链表

  • Post author:
  • Post category:其他




背景

对于数据结构,其实学过C语言的都不陌生,无外乎就队列、栈、二叉树等等这些。但其实对于初学者最困惑的不是数据结构是怎么样的,而是数据结构有什么用?我自己也是工作好几年后才体验到数据结构的快乐。所以本系列文章重点从应用场景切入,让大家理解数据结构的好处。



简介

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。由于在物理存储上可以以非连续状态存在,使得链表变得极其灵活。同时,链表就是C语言指针最完美的表现形式之一。常见的链表形式有两种,单向链表和双向链表。

  • 单向链表

一个节点数据带一个链接信息,如下图所示,链路方向只有一个,只能一直往后链,查找方式也只能从头到尾地遍历,无法反向查找。

链表1

  • 双向链表

一个节点数据带两个链接信息,一个用于链接下个节点,一个用于链接上个节点,这种结构使得可以从任意一个节点找到另个一个节点的数据。

链表2

单向链表和双向链表,其实这只是链表在顺序队列中结合的体现,实际链表的应用远不止这两种,它可以跟任意一种数据结构结合,比如树,二叉树的应用很大程度依赖于链表的实现。还有一些散列表,也可以由链表实现。



应用场景

链表应用面极为广泛,上面已经教你学会1+1=2,接下来要开始来做微积分了。举个GUI设计的场景,假设现在让你做一个显示屏,用户可通过拉取按键组件自己编辑界面内容,而你要做的,就是把用户编辑的内容显示出来,那应该怎么做?我们先用普通方式来实现。

#include <stdint.h>

/* 定义按键创建的最大个数 */
#define BUTTON_MAX_NUM			100

/* 按键的内置信息 */
struct tagButtonPrv
{
	int32_t StartX;		/* 起始横坐标 */
	int32_t StartY;		/* 起始纵坐标 */
	int32_t EndX;		/* 结束横坐标 */
	int32_t EndY;		/* 结束纵坐标 */
	…………
};

/* 首先得有个按键的结构对象 */
struct tagButtonCB
{
	struct tagButtonPrv Member[BUTTON_MAX_NUM];
	uin32_t Num;
};

struct tagButtonCB Button;

/* 用户创建按键信息 */
void CreateButton(struct tagButtonPrv data)
{
	Button.Member[Button.Num].StartX = data.StartX;
	Button.Member[Button.Num].StartY = data.StartY;
	Button.Member[Button.Num].EndX = data.EndX;
	Button.Member[Button.Num].EndY = data.EndY;
	…………
	
	Button.Num++;
}

/* 根据按键信息显示按键 */
void DisplayButton(struct tagButtonPrv* data)
{
	/* 显示的相关操作,这里就不展示了 */
}

/* 用户操作任务 */
void UserTask(void)
{
	struct tagButtonPrv data;
	data.StartX = 0;
	data.StartY = 0;
	data.EndX = 100;
	data.EndY = 100;
	…………

	CreateButton(data);
	
	while(1)
	{
		/* 干其他事 */
	}
}

/* 显示任务 */
void DisplayTask(void)
{
	while(1)
	{
		/* 把用户加的按键显示出来 */
		for (uint32_t i = 0; i < Button.Num; i++)
		{
			DisplayButton(&Button.Member[i]);
		}
	}
}

int main(void)
{
	/* 创建用户操作和显示刷新两个任务--伪代码,重在逻辑理解 */
	task_create(UserTask);
	task_create(DisplayTask);
	return 0;
}

上面这种实现方式有个很明显的问题,就是按键数量的上限是固定的,如果此时用户想要编写一个庞大的工程时,100个按键可能完全不够用。所以这里动态分配空间的方式来实现,再加上一个指针的链接信息,就可以组成一个链表。

#include <stdint.h>

/* 按键的内置信息 */
struct tagButtonPrv
{
	int32_t StartX;		/* 起始横坐标 */
	int32_t StartY;		/* 起始纵坐标 */
	int32_t EndX;		/* 结束横坐标 */
	int32_t EndY;		/* 结束纵坐标 */
	…………
};

struct tagButton
{
	struct tagButtonPrv Member;
	struct tagButton *Next;			/* 链接信息 */
};

struct tagButton *ButtonHead = NULL;

/* 用户创建按键信息 */
void CreateButton(struct tagButton *data)
{
	struct tagButton *i = ButtonHead;
	
	/* 查找到链表的尾部,把信息添加进去 */
	for (; i != NULL; i = i->Next);
	i = data;
}

/* 根据按键信息显示按键 */
void DisplayButton(struct tagButton* data)
{
	/* 显示的相关操作,这里就不展示了 */
}

/* 用户操作任务 */
void UserTask(void)
{
	while(1)
	{
		/* 用户配置了按键后执行动作 */
		if (xxx)
		{
			struct tagButtonPrv *data = malloc(sizeof(struct tagButtonPrv));
	
			data->StartX = 0;
			data->StartY = 0;
			data->EndX = 100;
			data->EndY = 100;
			…………
		
			CreateButton(data);
		}
		/* 干其他事 */
	}
}

/* 显示任务 */
void DisplayTask(void)
{
	while(1)
	{
		/* 把用户加的按键显示出来 */
		for (struct tagButton *i = ButtonHead; i != NULL; i = i->Next)
		{
			DisplayButton(i);
		}
	}
}

int main(void)
{
	/* 创建用户操作和显示刷新两个任务--伪代码,重在逻辑理解 */
	task_create(UserTask);
	task_create(DisplayTask);
	return 0;
}

那再如果,现在要显示的不止是按键,还有文本框、图片等组件,此时作为不同组件封装的结构和所占空间大小是不一样的,如果要把它们都链接到同一个链里,以上面这种链表包含数据信息的写法是无法满足的,这里我们再来提一种实现方式,也是Linux操作系统里的经典链表应用,在数据信息里添加单独的链信息。

链表3

#include <stdint.h>

/* 链接信息单独封装 */
struct tagLink
{
	struct tagLink *Next;
};

/* 文本框的内置信息 */
struct tagTextPrv
{
	struct tagLink *Next;	/* 数据中插入链信息,要放在数据前面,方便后面操作 */
	
	int32_t StartX;		/* 起始横坐标 */
	int32_t StartY;		/* 起始纵坐标 */
	int32_t EndX;		/* 结束横坐标 */
	int32_t EndY;		/* 结束纵坐标 */
	int8_t *Str;		/* 显示的文本内容 */
	…………
};

/* 按键的内置信息 */
struct tagButtonPrv
{
	struct tagLink *Next;	/* 数据中插入链信息,要放在数据前面,方便后面操作 */
	
	int32_t StartX;		/* 起始横坐标 */
	int32_t StartY;		/* 起始纵坐标 */
	int32_t EndX;		/* 结束横坐标 */
	int32_t EndY;		/* 结束纵坐标 */
	…………
};

/* 定义一个链头 */
struct tagLink *LinkHead = NULL;

/* 用户创建组件信息 */
void CreateComponent(void *data)
{
	struct tagLink *i = LinkHead;
	
	/* 查找到链表的尾部,把信息添加进去 */
	for (; i != NULL; i = i->Next);
	i = (struct tagLink *)data;
}

/* 根据组件信息显示组件 */
void DisplayComponent(void* data)
{
	/* 显示的相关操作,这里就不展示了 */
}

/* 用户操作任务 */
void UserTask(void)
{
	while(1)
	{
		/* 用户配置了按键后执行动作 */
		if (xxx)
		{
			struct tagButtonPrv *data = malloc(sizeof(struct tagButtonPrv));
	
			data->StartX = 0;
			data->StartY = 0;
			data->EndX = 100;
			data->EndY = 100;
			…………
		
			CreateComponent((void *)data);
		}

		/* 用户配置了文本框后执行动作 */
		if (xxx)
		{
			struct tagTextPrv *data = malloc(sizeof(struct tagTextPrv));
	
			data->StartX = 0;
			data->StartY = 0;
			data->EndX = 100;
			data->EndY = 100;
			data->Str = "Hello!!";
			…………
		
			CreateComponent((void *)data);
		}
		/* 干其他事 */
	}
}

/* 显示任务 */
void DisplayTask(void)
{
	while(1)
	{
		/* 把用户加的按键显示出来 */
		for (struct tagLink *i = LinkHead; i != NULL; i = i->Next)
		{
			DisplayComponent((void *)i);
		}
	}
}

int main(void)
{
	/* 创建用户操作和显示刷新两个任务--伪代码,重在逻辑理解 */
	task_create(UserTask);
	task_create(DisplayTask);
	return 0;
}

这里可能有人会问了,上面两个例子不都是实现功能了么,那两者有什么区别?第一种是链表中包含数据,而第二种是数据里面添加链接信息,所以可以任意给定链表中的数据长度。而且第二种方式,链表是可以单独封装成模块的,具体可以参考Linux内核里链表的实现。



总结

  1. 链表一般由链接信息和数据两部分组成。
  2. 在数据不连续且个数不确定的情况,可使用链表进行链接。
  3. 根据不同的使用情况,链接信息可以有多个。所以链表可以与队列、树、图等其他数据结构结合使用。
  4. 缺点:需要多一些空间用于存储链接信息,所以对于有序连续的数据,就没必要使用链表。



相关链接


队列

、栈、树、图、散列表



版权声明:本文为u012749085原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。