嵌入式开发交流网论坛

标题: 为什么要爱你——链表” [打印本页]

作者: 寒之筠 时间: 2018-11-23 17:23
标题: 为什么要爱你——链表”

在程序中我们经常遇到顺序处理相同类型数据的时候。比如在使用串口屏做GUI的时候，在一个屏幕上会有很多的同类控件。如果一个一个的处理，那么当增加一个控件之后，程序就得相应的改动。有什么很好的方法解决这个吗？

我们可以使用链表将相同的控件串起来，然后处理这一串的控件。这样当我们增加新的同类控件时，只需要将控件串入链表就行。下面我们分别说说什么是链表，链表与数组的异同，链表的用途？
一、什么是链表

链表是一种数据结构，是一种线性表。链表由一系列结点组成。
[attach]18195[/attach]
链表就像一列火车一样，每个结点就是一节车厢，每节车厢又通过指针相连接。使用最前面的火车头指向第一节车厢。在顺着数车厢的过程中，我们既可以寻找某个车厢（查找操作），也可以一个个的在上面做记号（处理操作）。
二、数组与链表的区别

数组是静态的，各元素在内存中是连续的。链表是动态的，各结点在内存中可以不是连续的。
[attach]18196[/attach]
链表的动态性，使得其在做添加、删除操作时有优势。而数组的静态性，使得我们可以通过索引更快的访问各个元素。所以各有各的优点。
三、如何实现链表的动态性

链表的动态性主要是通过指向前后结点的指针实现的。
3.1链表的组成
一个简单的链表数据结构由两部分组成：

指向头结点的指针，例如上图中的火车头
各个结点，就是各节车厢

每个结点也是由两部分组成：

结点中的数据
指向后继结点的指针，如上图车厢的next指针

3.2链表的起点与终点
[attach]18197[/attach]
通过root指向第一个结点，来确定处理程序从哪开始，那通过什么来确定最后一个结点？
上图中最后一个结点的link的值为0。所以是通过判断结点的后继指针是否为NULL来确定最后一个结点的。
链表的具体实现这里就不多说了。
四、链表的用途

[attach]18198[/attach]
从上面的对比中，我们可以看出链表的优势在动态性上，适合处理数据数量不确定的情况。比如开篇提到的GUI中相同类型的控件，各个页面的控件个数是不同的。UCOS中也大量的使用了链表，比如任务控制块、内存控制块等。都是可以根据需求增加和减少的。
欢迎大家添加我的微信公众号“光豆儿”

欢迎光临嵌入式开发交流网论坛 (http://www.dianzixuexi.com/bbs/)