连载——数据结构（4）——线性表与链表

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

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

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

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

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

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

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

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

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

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

1.数组第一个元素在哪（数组名）

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

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

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

但这又会带来一个问题，由于各元素都是通过malloc()获取的内存，所以各元素都分散开了，那么我们该如何找到各元素呢？实现的办法很简单，就是令每个元素“记住”下一个元素的位置！这样一来，我们就只需要保存第一个元素的位置就可以了，第二个元素的位置在第一个元素中，第三个元素的位置又在第二个元素中，以此类推。

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

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

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

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

structElement a=;structElement * List=&a;//这个List就是一个“链表”

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

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

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