在我们谈论本文具体内容之前，我们首先要说明一些事情。在现实生活中我们所说的“表”往往是二维的，比如课程表，就有行和列，成绩表也是有行和列。但是在数据结构，或者说我们本文讨论的范围内，我们所说的“表”是一维的，即所有“元素”都是前后排列的。就我个人而言，这样的“表”用“队列”来形容比较恰当。但是，数据结构中“队列”这个名词是被一种特殊的“表”给占用了的，所以我们没法再用“队列”来表示“表”，后期我们会对“队列”进行介绍。

　　在第一段的说明过程中，我们其实已经说出了“表”的定义，就是若集合中的元素是一前一后像队伍一样联系起来的，那么这个集合就是一个表。

　　显然，我们常用的数组就是表的一种，它符合“元素一前一后联系起来”的要求。表是最基础的数据结构（虽然结构体也能存多个数据在内，但其整体还是视为一个对象的），每当我们需要存储的数据不存在特殊的关系（比如以后会说的一对多关系），或者存在的关系为“一前一后”时（比如用户输入多个字符，字符间就存在输入顺序上的“一前一后”关系。在应用上，比如我们可以将字符存储进字符数组，然后判断用户输入的是不是正确的密码等），我们就可以使用表。

　　那么，表的相关知识讲到这儿就算结束了吗？（毕竟数组大家应该都会用了）显然不是，我们说了，数组是表的一种，但也只是表的一种啊~

　　接下来我们就要说说，使用数组作为表的缺点。首先让我们假设一种情况（这个在深入浅出数据结构（1）中提到过）：

　　我们要写一个程序，这个程序的过程很简单：获取用户输入（这里就需要用到表来存储用户的输入），对用户输入进行计算或操作，输出结果。

　　但是这个程序要考虑一个情况：用户有时候只需要输入几个数据，而有时候却需要输入几万个数据（可能有人会说怎么可能输入那么多，人都累死了。。。但是别忘了有一种操作叫文件重定向，虽然我记不得也没用过╮(╯_╰)╭）。对于C程序来说，这个问题是不得不考虑的，如果你决定使用数组来存储用户的输入，那么数组的大小在创建之时就要确定好（印象中C11标准允许数组创建时的大小不再是固定的，但总是用最新的标准来写程序并不是什么好事，因为标准的普及总是要时间的）。很显然，数组的大小很好确定，比如十万（反正绝对大于用户可能的输入数量就行）。但是这会带来一个很严重的问题，就是你的程序在不需要那么多空间的情况下依然会使用那么多空间，比如用户平均输入只有几百个，然而每次运行程序都先占用了十万大小的数组空间。显然这样的程序很不好，一来用户的内存可能还有别的程序需要使用，二来可能别的用户不需要十万个的存储空间而且他的内存也不够。

　　那么对于这种情况，我们该怎么办呢？

　　首先我们发现我们依然要用到表（假设用户的输入数据间的关系就是一前一后），所以我们先确定下来使用的是表类型的数据结构。然后我们希望的关键点其实就是：表能够随着需要而改变大小。那么我们该如何实现这样一个表呢？现在，不需要你去思考解决方案了，我们已经有了现成的数据结构，那就是链表！

　　回顾数组，我们发现，其实我们知道的信息有两个：

　　1.数组第一个元素在哪

　　2.数组中元素都是相邻的，后一个元素就在前一个元素的后面，中间没有“空”

　　因为我们知道这两个信息，所以我们不需要知道各个元素的具体位置，只要根据某个元素在表中的顺序位置n，就可以由第一个元素的位置加上n来得到该元素。

　　但这也正是数组的不足所在，为了满足第2点，我们必须在创建数组时就指定其大小，只有这样我们才能找到满足2的一整块区域给数组。那么，为了解决这个不足，我们要做的就是不再使用一整块区域，各元素自取所需（即元素不一定是相邻的了，只要添加元素时找一个可以放下该元素的容身之所就行）！

　　但这又会带来一个问题，就是大家都分散开了，又如何找到大家呢？

　　让我们再次回顾数组的信息2，然后进行另一个角度的解释：

　　数组中某个元素的位置其实是根据其前一个元素的位置+1来获得的，而第一个元素的位置则需要我们手动保存。换句话说，某个元素的位置是其前一个元素“告诉”我们的！

　　让我们把这一想法应用到我们的新想法中！即令每一个元素“记住”其下一个元素的位置！这样一来，我们就可以根据需要来向表中添加元素了，只要加入新元素后，原先的最后一个元素“记住”新元素在哪就可以令这个表像锁链一样“链”起来！我们的“链表”思想也就诞生了~:-P

　　接下来我们要做的，就是将这个想法付诸实现了。相信很快，我们就会发现，实现链表的关键之处在于如何“令元素记住下一个元素的位置”？在这里我们要多嘴一句，正如第一篇博文所说的，数据结构不仅决定如何存储数据，有时候也要决定或者说不得不考虑“存储什么数据”。现在我们就遇上了这样的问题。显然，数据本身是不会记住下一个数据在哪的，比如数据类型为int，它又如何去记住下一个int在哪？这时候，我们就需要对数据“封装”一下，形成一种新的数据类型，然后这种数据类型要能够记住下一个相同数据类型的位置。

　　思路已经出来了，就是“封装”出新的数据类型，然后要求其能记住下一个相同数据类型数据的位置。“封装”可以令我们想到结构体（也许你想不到但没关系，现在知道了╮(╯_╰)╭），而“位置”则会让我们想到指针。因此我们“封装”出来的新数据类型应该是一个类似这样的结构体：

struct  Element
{
      DataType  data;   //DataType根据实际元素类型决定
      struct  Element  *  next;   //next意味着其存储下一个元素的位置
}

　　然后在我们的程序中，我们只需要知道第一个元素在哪就行了（第一个会告诉我们第二个在哪，以此类推）：

struct  Element  a={data,NULL};
struct  Element  * List=&a;

//然后向这个以List开头的链表添加元素

　　现在，对于为什么要使用链表，以及链表该如何实现的基本思想及如何“封装”出链表的元素我们应该都明白了。

　　但是虽然知道了链表添加新元素时该怎么做已经有了口头上的描述，却还没有给出代码上的实现，并且如何从链表中删除一个元素以及如何找到第n个元素也还没给出实现。

　　这些可以统称为对链表的操作，也可以说是能对链表这种数据结构使用的算法。关于这些，我们将在下一次博文中介绍。

　　最后总结，我们这次讲了哪些呢？

第一，什么是表。

第二，表有什么可能的用处。

第三，数组作为表的缺点。

第四，引出链表的想法以及基本思路、基本元素的“封装”

　　下一次博文，我们将介绍链表的操作，以及特殊的“链表”——游标数组

深入浅出数据结构C语言版（4）——表与链表