数据结构拾遗线性表的详细介绍

二 线性表

这一次，我们就来看一看线性表。

我们先给出一个线性表的知识图，它或许并不非常准确，但可以帮助您回忆您在您看过的数据结构教材中所学的大部分内容。事实上，在阅读以下的内容之前，我也鼓励您停下来想一想，想一想线性表那些在您封存的记忆中依然闪光的部分。

我无意和您对此图的细节划分标准进行辩论，也无意于全部讨论它们，既然是“拾遗”，我以对您有所启发为乐，希望能提出些容易让人忽视的问题，促使您更好、更主动的去学习和思考。

1，数据组织内在的逻辑联系

一个小蚂蚁，急奔在一望无际的沙滩上。它有一个棘手的任务，就是，它需要考察这沙地上所有的沙子。万里平沙呵，我所走之处，都是千差万别的沙粒，让我如何开始考察呀！风儿建议它，以某点为中心，给所有的沙子建立一个“序”：若半径为r，同在此圆周上的为等，其内的为小，其外的为大，借r去考察沙子们，断不会无处下手了。

如果沙子可比喻数据，那么建立一种序，亦即建立一种模型，是我们组织数据的第一步，否则我们也要面临“万里平沙”的局面了。在所有的序中，“线性”当是最简单的一种。我们今日所要谈的线性表，就基本上是基于这种关系建立的一类数据结构。

对于数据的集合A={…，x，y，z，…}，|A|=n，我们映射其为An={a0，a1，…，an-1}，且对于元素

ai，1<=i<=n-2，

和它有关系的只有ai-1，ai+1，前者称其为前驱，后者称其为后继，都是唯一的。这是线性表的基本逻辑特征。

抽象出一种序（或关系）出来，往往是计算机解决问题的一种基本方法。数据结构的发展与演化，也就是从数据存储与组织的角度，深刻发展、展示这一思想的。

我们看线性表。可以图示说明。对于基本部分，如下图：

如果对存取加以限制，就是我们计算机科学中使用非常广泛的两种数据结构：

线性表检索某个数据的时候，一般是顺序搜索下一个，直到搜索到该数据为止。换句话，一次检索或一次更新的时候需要的时间是线性的，为了解决这个问题，可以扩张为一个基于概率的数据结构，跳跃表。而对于线性表的元素，如果亦允许之满足一定的结构，则可以扩张为广义表，这个数据结构定义满足很好的递归性。见下图：

图形的背后的不变的概念，表明它们是由同一个模型变化而来。抽象的魅力，还远不止于此。我们以后有机会，再在计算机科学的经典例子中说明。对于串和矩阵，稀疏矩阵，有些算法，值得大家注意。

对于这些基本内容不熟悉的读者，请您查阅有关数据结构书。

2，线性表实现时要注意的地方

我们不会详细谈线性表的实现。诸如链表实现的时候，您是使用c语言，还是使用c++语言进行封装，诸如链表的插入节点的时候，您应注意指针的顺序，诸如线性表，您是否要加一个头节点以统一操作；并非它们不是重点，它们恰恰是基础部分，但我想这是您首先要熟悉的。

（1）实现的时候，我想给您总结一下，接着图1的知识结构，线性表所有可常见的形式。

链表的实现。链表的形式，有A={单链表、双向链表}， B={循环，不循环}之分。则前后组合，类别为：B×A，共有四种。是否加头节点，是一个技巧。

栈与队列。栈与队列，可用顺序表实现，也可用链表实现。另外，循环队列与优先级队列，是大家所熟悉的。但有意思的，循环栈，大家是少见的；想一想，如下棋等活动，只允许连续后退n步，那么保存刚经历的活动n步，就可以如此实现了。建议大家写程序试试。

跳跃表与广义表。它们的实现，大家可见于《数据结构与算法分析》（张铭等译）和《数据结构（用面向对象方法与C++描述）》（殷人昆等编著）。

（2）指针的意义，在于存储地址。所以实现上，不仅指针变量可以为之，诸如整型变量也可以作为指针之用。所以链表等，也可以使用复杂的顺序存储方式实现。

（3）如下图，一个执行了一段时间后的链表：

对于c语言或c++语言实现的链表等数据结构，申请了内存资源，当内存资源回收时，问题就出来了。即使经过了细心的设计，没有出现错误；但因为节点（一个小的内存单元）是经过多次申请的，当回收时需要一个一个的回收，速度就会特别慢。如果节点数目巨大，则速度通常是难以忍受的。

这个问题的解决，通常是申请内存资源时，一次性申请一个较大的单元，然后作为节点分配的缓存区，当使用完毕后，再一次申请同样一个较大的单元。对这些较大的单元进行管理，回收时不再以一个节点为单位，而以该较大的单元为单位。速度就可以提升。

（4）只有当必要的时候，否则就不要使用复杂的数据结构。解决问题以方便为准。