1.                          线性表顺序存储结构

问题1：

现有一个字符串需要我们存储，我们希望有着某一种类型（比如说MyString这种类型吧）可以直接表示一个字符串类型，我们应该怎么实现。首先我们不考虑如何实现这个MyString类型，假设已经存在了一个表示MyString类型，我们作为用户，希望MyString这个类型给我们提供哪些操作？比如声明或者定义一个字符串，两个字符串合并，等等。

问题2：

现有一电话簿程序，需要存储一些联系人的信息，然后还有一些相应的操作，比如添加、查找以及删除等，如何实现？

问题3：等等

一、问题抽象

解决上述提出的这些问题我们当然可以一个一个的问题去解决，即用一个字符数组实现MyString，以及用一些数组实现其他的类型。

我们现在来考虑一下，这些问题有没有一些共同点？我们想到了，这些问题的共同点都是可以用一个数组来解决该问题。因此，我们可以考虑做一个通用的模板，以后每次使用，只需要在这模板基础上来进行一些其他的装饰作用即可。

下面举一个不是很恰当的例子。不知道大家有没有见过以前捏泥人的。以前捏泥人都是工匠信手就来，直接捏。针对不同人的喜好， 来捏不同造型的泥人。

那么现在有了另外一种改进的工艺来使得这种过程变得更加容易，效率更高。什么样的工艺呢？是这样做的：首先我们做一个空心的模具，然后把泥巴装进模具里，等干了之后拆开模具。这样是不是就结束啦？不要急，还没有结束，这只是一个简单的泥人坯子，而不具备各种多姿多彩的造型，因此我们还有最后一步，就是给这样一个泥人坯子造出特定的形状，比如关公耍大刀，孙悟空等等。

那么回到我们的话题，对于前面所提出来的几个问题，我们是否也可以采用这种方式，来构造出一个模板？然后再在这个模板上进行稍加修饰就能使之使用于不同的情景之中？答案当然是可以。而这种技术，也就是我们这门课《数据结构》的目的。即构造一个适用于某一类问题的通用结构（数据类型）。

二、问题分析

我们已经分析过，上述问题均是使用一个数组来存储，同时我们也可以将数组和这个数组的长度封装起来，组成一个结构体（当然还有一些其他的操作是必须有的）。代码如下：

那么对比我们这几个例子， 发现它们的结构都是惊人的相似（不相似的也可以简单的构造下就相似了）。因此我们决定，把这个几个例子提炼一个模板出来。

三、具体实现

我们在实现之前，必须搞清楚以下几点，不然写代码的时候比较棘手。

（1） 这个结构取一个什么样的名字？

（2） 结构里面的第一个元素（即数组）的基类型是什么？

（3） 该结构的各种操作该怎么取舍（比如有的字符有字符的相关操作，有的联系人有联系人相关操作等等。）？

这个结构体当然不能取特殊的名字，因此我们取一个它的逻辑含义的名字SeqList（实际上名字可以随便取，只是规范性问题）。其次，我们不能确定此数组的基类型，因此我们只能用一个空洞的名次代替ElemType，在使用到SeqList的时候，我们再把ElemType换成我们需要的类型（对于这个问题大家在使用的时候就很清楚了）。其次，我们应当分析一下这个SeqList结构的操作集到底有哪些操作。具体的有哪些操作在这里我就不作赘述（课上会仔细讨论，注意基于用户），大家自己思考。

四、理论

（1） 线性表的物理定义

课本中的定义：一个线性表是n个数据元素的有序序列。

我给出的定义：线性表是一个无序二元组，该二元组的其中一个元素是一个具有n个元素的有序序列，该二元组的另一个元素是该有序序列的长度。

定义大家喜欢哪个就用哪个，其实本质都是一样。

（2） 线性表n个元素的有序序列的分析

（3） 线性表的逻辑定义

（4） 线性表的操作集