简单说说链表和一个应用实例

caroline11

对于算法和数据结构，常常有两种极端看法。      

一种是觉得非常高深，难以触及，比如很多的算法书，一开篇就是一堆很复杂的计算分析。而对于毕业很多年的我们，不管你当年高数复变很高分还是和我一样刚刚合格，可能很多人都是很难看懂那些分析。但实际上，对我们中的很多人，我们更多的时候是需要去学习一种已经被设计出来的算法或者数据结构——我们中有多少人是打算去设计算法的呢？如果不是，至少是不是先学会如何在已有的方案里挑选合适的结构，算法，而且还需要稍作修改，以适应在自己面对的问题里使用呢？

——比如 现在提到的链表，他的“标准”实现就是需要 malloc/free的，但在单片机，尤其是裸机程序中，我们通常被告诫尽量不要使用malloc/free函数，所以，我们需要另一种折中方案，用一个静态数组作为空间，然后通过对数组下标的计算操作模拟 malloc/free这对动态分配函数。一般这种方案被称为 游标实现。除了需要预先预留一个足够大的数组以外，它的使用和语境，和标准链表实现完全一模一样——我的意思是，你可以通过只改写这两个函数，然后直接套在 原来的 链表API里就可以了。

另一种，是觉得某些基础结构 很简单，实现起来又麻烦，干脆就不用了。比如 三种最基础的数据结构，链表 队列 栈。它们的概念确实非常简单，但是实际上，如果我们真的完全理解了它的用途，并妥善使用，那其实还是会发现它们虽然简单，却威力无比。

但从我们看到的一些实现，我们经常会发现，他们对这些 数据结构 的理解，其实是有偏差的，甚至有的基本都错了。

比如我自己，我第一个真正开始大量使用数据结构是 队列，我把它用在 串口接收上。但直到我对着书去写，我才发现我以前从来没有理解 队列的本质特点就是 通过移动 头 和 尾 来避免直接移动数据本身，以保证它的操作时间可以被控制在一定的范围内（数学不好）。

另外一点要强调的是，即使是同一个结构，算法，不同的人都会有不同的出发点和定义的方式。

而我个人对此的态度是，我会选择一个大家比较公认而且我自己也觉得挺不错的 定义，然后尽全力去试图理解他的出发点，把并按它的定义严格完成实现。由于选择看书的原因，我看的是 Mark Allen Weiss(以后简称 M.A.K)的 C语言描述 这本书，我觉得他的定义和（部分）实现 都相当的标准的感觉，而且在我几经使用后都发现他的定义确实很有道理，所以基本上都以他的定义为实现版本。