数据结构与算法（四）线性表的抽象数据类型描述

一、回顾

        上一篇我们讲到了线性表的定义，讲到了所谓抽象数据类型就是把数据类型和操作捆版在一起。那么我们接下来分析一下，线性表应该有什么样的相关操作呢？。

        从一个例子来看一看，回到我们上一篇开学参加升旗仪式的例子：

        老师把同学们按照规律排成一队，并且是长期使用这样的顺序排队，大家只需要记住自己前驱的同学就可以了。那么这种考虑和安排的过程其实就是一个线性表的创建和初始化过程。

        一开始老师没有经验，把同学们按照名字首字母的顺序排队，发现排列最后有的高有的矮，导致队伍很难看，于是让同学们解散从新按照从矮到高排队。上述过程其实就是线性表重置为空表的操作过程，接着我们描述一下删除数据。

        排好队之后，我们发现张三由于昨晚睡觉没盖被子，感冒发烧来不了了，那么张三原来的位置就被空出来了，由原来排在张三后面的同学开始往前挪。

        当然，有删除数据就会有插入数据，几天过后，张三同学康复回来上课了，他说他记得排在李四的后面，所以原本排在张三后面的同学就往后挪了一个位置，张三就插入回自己的位置上了。

        升旗后领导开始发言，领导发言的时候，下面的张三在说话搞小动作，年级主任找到班主任投诉，说：“你们班队伍里第八个同学在下面搞小动作，麻烦你去处理一下。”老师查了一下名单说，噢，他叫张三。这就是根据位序得到数据元素的例子。

二、线性表的抽象数据类型

        我们来总结一下线性表的抽象数据类型定义：

        1、ADT 线性表（List）

        2、Data：线性表的数据对象集合为{}，每个元素的类型均为DataType。其中，除第一个元素外，每一个元素有且只有一个直接前驱元素，除了最后一个元素之外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

        而抽象数据类型就是把数据和操作捆绑在一起。

        3、Operation

        IniList(*L)：初始化操作，建立一个空的线性表L。

        ListEmpty(L)：判断线性表是否为空表，若线性表为空，返回true，否则返回false

        ClearList(*L)：将线性表清空

        GetElem(L,i,*e)：将线性表L中的第i个位置元素值返回给e。

        LocateElem(L,e)：在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败。

        注意：我们在数组中，下标是从0开始的；但是在线性表中，回到了我们日常的用法，从1开始，所以0是没有东西的。

        ListInsert(*L,i,e)：在线性表L中第i个位置插入新元素e。

        ListDelete(*L,i,*e)：删除线性表L中第i个位置元素，并用e返回其值。

        ListLength(L)：返回线性表L的元素个数。

三、复杂的线性表操作

        对于不同的应用，线性表的基本操作是不同的，上述操作是最基本的，对于实际问题中设计的关于线性表的更复杂操作，完全可以用这些基本操作的组合来实现。

        举个例子，假设有两个集合A和B（一个集合中没有相同值的元素），分别用两个线性表LA和LB表示，即线性表中的数据元素为集合中的元素，利用线性表的基本运算设计一个算法求一个新的集合，即将两个集合的并集放在线性表LC中。

        先初始化线性表LC，即创建一个空的线性表LC，将LA的所有元素复制到LC中，然后遍历线性表LB，将LB中不属于LA的元素插入LC中。假设List是一个已经实现了的线性表数据结构，LA、LB和LC均为List类型变量。

        综合分析，我们需要运用到几个基本的操作组合即可：

        -ListLength(L);

        -GetElem(L,i,*e);

        -LocateElem(L,e);

        -ListInsert(*L,i,e);

        程序示例如下：

void unionList(List LA,List LB,list &LC)
{
    int lena,i;
    ElemType e;
    InitList(LC)；//初始化LC
    for(i=1;i<=ListLength(LA);i++)//将LA中的所有元素复制到LC中
    {
        GetElem(LA,i,e);//取LA中的第i个元素赋给e
        ListInsert(LC,i,e);//将元素e插入LC中
    }
    lena = Listlength(LA);//求线性表LA的长度
    for(i=1;i<=ListLength(LB);i++)//循环处理LB中的每一个元素
    {
        GetElem(LB,i,e);//取LB中的第i个元素赋给e
        if(!LocateElem(LA,e))//判断e是否在LA中
            ListInsert(LC,++lena,e);//若不再LA中，则将其插入LC中
    }
}

        在上述算法中，LA和LB是输入型参数，而LC是求解结果，为输出型参数，所以将LC设计为引用型形参。

        从中可以看出，当线性表List实现以后，可以利用它作为存放集合数据的容器，也可以利用它的基本运算完成更复杂的集合运算，例如求两个集合的并集等。

          （本节完）

参考资料：

1、《数据结构教程》李春葆主编-清华大学出版社-2022.7

2、线性表2_哔哩哔哩_bilibili 鱼C小甲鱼