Question

数据结构笔记（四）——线性表

Answer 1

前面说过，数据结构的类型大方向上来说分为 线性结构 和 非线性结构 ，下面要说的线性表就是线性结构的一种。
（复习一下，前面说过的线性结构有：线性表、栈、队列、字符串、数组和广义表）
上一行是课本上的原话，但是感觉这个在逻辑上有一些不清楚的地方，先忘掉上一行的东西吧，看完下面的再回来想想。

先来说一下线性表是什么。
线性表简单来说就是一个* 有限个元素的序列 ***。
本来有一堆山楂，你拿个竹签，一个一个穿起来，就构成了线性表。
请记好，这里还有串“低配版”的只有山楂没有糖的糖葫芦，我们后面就用它来类比线性表。
——OOOOOOOOOOO————————(→.→ 我叫糖葫芦。。。)

1.首先，这串糖葫芦的山楂的个数一定是可数的。
所以类比到线性表，线性表的元素一定是有限的。

2.然后，一般吃糖葫芦都是从开头第一个山楂开始吃，吃到最后一个山楂吃完。
类比到线性表，线性表有且只有一个开始节点、有且只有一个终端节点。

3.除了糖葫芦的第一个和最后一个山楂，其余的每个山楂都左边有一个山楂右边有一个山楂。
类比，线性表除了两端的元素节点，其他的每个元素都有且只有一个前驱节点和后继节点。

4.世界上没有两片完全相同的树叶，也没有两颗完全相同的山楂。对于这串糖葫芦，山楂的位置都是固定的，该是第几个就是第几个（假如你不吃或者不把山楂往前撸的话），只要通过 位序 就能找到对应的山楂的位置。

5.吃完了这串糖葫芦，就只剩一个空竹签了。类比地，把含有0个元素节点的线性表称为 空表 。

6.当然，吃了半天糖葫芦，必须要知道的是，这串糖葫芦的每一个“元素”都是“山楂”，而不是其他什么果子。
类比线性表，线性表要求每一个数据元素的类型都是相同的，不能混进去什么奇怪的东西。

概括来说，线性表的三大特点就是： 同一性 （6）、 有穷性 （1）、 有序性 （2、3、4）。

说完了线性表的性质，可能就会有一些疑问：上面的糖葫芦模型是万能模型吗？（这个模型是不是完整模型？糖葫芦模型能不能代表所有线性表的特点?）

比如：我不想从第一个山楂开始吃，我从第二个开始吃可不可以？那对应的线性表的逻辑会不会乱掉？

答案是：虽然逻辑不会乱，你怎么吃那都是一串山楂；糖葫芦模型只是为了形象地表达一下线性表的最主要的特点，并不能解释所有的线性表的特点。后面还有别的线性表的内容呢，不能老吃糖葫芦呀多腻呀。。。
实际上线性表是有分类的（这个书上没说），按照操作方式，线性表一般分为 一般线性表 和 受限线性表 两种。

有什么区别呢？

一般线性表 就是前面的糖葫芦模型，你爱从哪里开始吃就从哪里开始，爱吃第几个就吃第几个。（对应的线性表例如数组）

受限线性表 就不是糖葫芦了，而是桶装薯片（栈）和吸管（队列）。

这时候你只能先吃最上层的薯片，吃了上层才能拿下一层的，不能随便拿中间的第X层的那张薯片。

或者是吸管，你只能最先喝到最先进入吸管的那一部分，而不能直接就喝到吸管中段的那部分。
总而言之，这时候你的操作受限制了，不能再任性下去了，所以这样的线性表，称为受限线性表。

好，现在关于线性表的一些基础知识都过了一遍，现在让我们回到开头，我说“感觉逻辑怪怪的”这里。

课本上说的线性结构包含了：线性表、栈、队列、字符串、数组和广义表。似乎是把线性表和栈、队列、数组这些东西给平行表示了。
但是实际上，线性表与栈、队列和数组（或者也包括字符串）不是平行的。
线性表包括了栈、队列和数组、字符串 。

所以说，其实数据结构里的线性结构大多都是以线性表表示的。然后根据操作性质分别选用了“一般线性表”或者“受限线性表”，然后又根据不同的使用场景再一步细分为使用哪一种线性表（栈？队列？数组？串？）。

关于线性表的概念就到这里，后面的几期还会有薯片吸管糖葫芦等着我去吃。

新手上路，才疏学浅。如有错漏，多谢指教。