近几次总是讨论着各种各样的表，难免有些晕。
这次的内容依然是一个表（笑哭脸），为了不“晕表”，我们先来理一理：这是个什么表。
我们前面已经说过线性表了。对于线性和非线性的逻辑结构，都对应有顺序存储和链式存储两种方式。
先说顺序表，也就是线性表的顺序存储。
顺序表
大家都学过C语言，那么顺序表好理解一些的方式就是用C语言的数组作为例子来说。
（我好像确实比较喜欢用例子来类比。。。见谅）
C语言的数组实际上就是线性表的完全表现载体。
我们先来回顾一下数组的种种：
- 数组有一个首地址；
- 只要知道数组的首地址，那么我们可以随意访问数组中的元素；
- 数组的存储（在内存中）是连续的；
顺序表的性质和以上三个大致相同。
但是依然需要区别数组和顺序表：顺序表依然是一种存储模型，但是数组是实实在在的存储容器。我们可以对顺序表执行一系列的运算（这时候把顺序表作为对象来看待），但是对于数组我们依然只能对其进行一些基础操作。
比如说，一个顺序表是用数组去表达的（即在数组中存放顺序表元素，一般数组要足够大），这时候顺序表的长度和数组的长度是不完全一致的。数组的长度指的是数组所占的空间数，而顺序表的长度仅仅是指有效数据所占的空间。
其实我们可以简单总结一下：顺序表=数组+各种针对数组的运算的函数
关于顺序表的运算的函数这里不再赘述，相对来说比较基础，有C语言学习经历的小伙伴们可以很容易自己去实现。
链式线性表
说完了顺序表，接下来说链式存储的线性表。
基于前面的顺序表的概念，链式线性表是存储上不连续的线性表——对应到C语言中就是用链表来表达线性表。
有C语言基础的小伙伴一定都很熟悉单链表的基础操作了，这里不再赘述。
因为链表是用指针实现线性表的前驱与后继，所以更适合利用指针的操作来使得线性表的修改操作变得更容易一些。故，一些需要改动内容的线性表更适合用链式线性表来表达。
但是有时候用之前学过的单链表来表达线性表依旧是不方便、不形象的。所以还有几种不同于之前单链表的几种链表：
1.循环链表：
所谓的循环链表就是之前的单链表的一个“变形”。原来的单链表的尾指针是指向NULL的，这时候只要把该单链表的尾指针指向该单链表的头结点，即可构成循环链表。此时尾结点成为了首节点的前驱。且因为循环链表的操作一般是对原先的单链表的首尾节点进行操作，为了减少从头开始遍历到尾结点的时间，所以习惯性用尾指针来指示链表。当然这也不是绝对的，具体情况具体对待。
2.双向链表：
在使用之前学过的单链表或者循环链表时会发现，无论如何我们只能从某个节点开始定向遍历，所以当我们需要找到该节点的前驱的时候就需要从头开始重新遍历单链表或者循环遍历一遍链表，在时间开销上来说十分不划算。所以这时候用双向链表就会好一些。
双向链表就是在之前单链表的节点基础上，对节点的结构再添加一个指针，该指针指向该节点的前驱节点。这时候每个节点都可以直接访问该节点的前驱和后缀，就能大大减少时间的开销。
同时要注意的一点是，在双向链表的操作中，修改链表（增、删等）都需要同时操作前驱节点的指针和后继结点的指针，并且需要使当前节点的两个指针的指向都正确。
3.静态链表：
在这之前我们说到的都是动态链表，因为节点都是在用的时候申请、不用时销毁的。但是静态链表就有些特殊了。
静态链表是用数组实现的。
先不要慌。静态链表之所以依然取名为链表，就是因为它还是具有链表的特点：以节点为单位、相邻元素间的逻辑由指针的指向来确定。
但是为什么叫静态链表并且强调它是用数组来实现的呢？
想象一下，把一条贪吃蛇揉吧揉吧塞到一个盒子里，蛇宝宝的头可能和尾巴都是相邻存放的，但是逻辑结构依然是蛇的身子表达出来的。静态链表就是这样，将一个链表“存到“数组中，兼顾了链表和数组的特点：链式逻辑，数组存储。下面盗一张图来说明一下：
图片.jpg
可以看出，本来应该是指针的，现在是用一个数（作为数组的下标）来指示下一个节点的位置。这时候next已经不是指针了，而被称为游标，游标就是用来模拟链表中的指针的。
一般来说，都是用大数组去作为静态链表的存储空间，然后去执行单链表的（增、删、改、查）一系列操作。好处是不用遍历链表到指定的位置即可操作元素，只要改动next的值就可以实现。
顺序表和链式线性表的比较
上面说完了顺序、；链式两种方式以及各自的载体去实现线性表的表达。下面分析一下二者各自的优缺点:
对于顺序表而言，就是一系列的数组特性：存取数据操作简单、存储密度高、连续读取的效率高。但是执行插入、删除等操作时，会有大量数据被连同操作，资源开销大；而且总占用空间有一个固定的大小，容易产生资源闲置或溢出的现象。
对于链式存储来说则是链表的特性：存储密度较小（因为节点中往往需要分配指针域，而且数据在内存中的存储并不是连续的地址，连续读取的过程中需要不断进行指针运算）。但是执行插入、删除等操作时十分方便，不用操作其他无关数据。
总结起来说就是：如果线性表不需要执行插入、删除等改动元素的操作的话用顺序表比较合适，否则则采用链式线性表。
还有就是，几乎所有的编程语言都支持数组，但不一定支持指针。
这就意味着，顺序表无论如何是可以实现的，但是链式线性表就不一定能实现了！
以上就是线性表的两种存储形式的表达的讨论和总结。
说点题外话：
为什么要把这个并不复杂的东西的概念说这么多呢？
私以为,概念神马的还是蛮重要的，从根本出发弄清楚概念，对后面的应用或者更复杂的操作会有比较大的帮助。另外一方面，很多东西我们会用，但不知道为什么这么用。作为计算机专业的学生，在专业知识方面，我还是想达到“知其然，知其所以然”的程度。
新手上路，才疏学浅。如有错漏，恳请指教。
网友评论