2.1.2　线性表的基本运算

数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在存储结构上的，因此下面定义的线性表的基本运算作为逻辑结构的一部分，每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。

线性表上的基本操作如下。

（1）线性表初始化：Init＿List（L）。

初始条件：表L不存在。

操作结果：构造一个空的线性表。

（2）求线性表的长度：Length＿List（L）。

初始条件：表L存在。

操作结果：返回线性表中所含元素的个数。

（3）取表元：Get＿List（L，i）。

初始条件：表L存在且1≤i≤Length＿List（L）。

操作结果：返回线性表L中第i个元素的值或地址。

（4）按值查找：Locate＿List（L，x），x是给定的一个数据元素。

初始条件：线性表L存在。

操作结果：在表L中查找值为x的数据元素，其结果返回在L中首次出现的值为x的那个元素的序号或地址，称为查找成功；否则，在L中未找到值为x的数据元素，返回一特殊值表示查找失败。

（5）插入操作：Insert＿List（L，i，x）。

初始条件：线性表L存在，插入位置正确（1≤i≤n＋1，n为插入前的表长）。

操作结果：在线性表L的第i个位置上插入一个值为x的新元素，这样使原序号为i，i＋1，…，n的数据元素的序号变为i＋1，i＋2，…，n＋1，插入后表长＝原表长＋1。

（6）删除操作：Delete＿List（L，i）。

初始条件：线性表L存在，1≤i≤n。

操作结果：在线性表L中删除序号为i的数据元素，删除后使序号为i＋1，i＋2，…，n的元素变为序号为i，i＋1，…，n－1，新表长＝原表长－1。

需要说明以下几点。

（1）某数据结构上的基本运算不是它的全部运算，而是一些常用的基本的运算，而每一个基本运算在实现时也可能根据不同的存储结构派生出一系列相关的运算来。比如线性表的查找在链式存储结构中还会有按序号查找；再如插入运算，也可能是将新元素x插入适当位置上等，不可能也没有必要全部定义出它的运算集，读者掌握了某一数据结构上的基本运算后，其他的运算可以通过基本运算来实现，也可以直接去实现。

（2）在上面各操作中定义的线性表L仅仅是一个抽象在逻辑结构层次的线性表，尚未涉及它的存储结构，因此每个操作在逻辑结构层次上尚不能用某种程序语言写出具体的算法，而算法的实现只有在存储结构确立之后。