第四讲 线性表的抽象数据类型

上节课我们讲到了线性表的定义，讲到了所谓抽象数据类型就是把数据类型和相关操作捆绑在一起。
那么我们接下来分析一下，线性表应该有什么样的相关操作呢？
从上讲中的老师组织春游活动排队的例子中，我们可以总结相关的操作如下：

• 开始排队：线性表创建
• 队伍里让某个同学出列：线性表删除某个元素
• 有入列就有入列吧：线性表插入某个元素
• 等等。。。
  好了，剩下的还有很多大家可以自己想象。

线性表的抽象数据类型定义：

ADT 线性表（List）
Data
线性表的数据对象集合为{a1,a2,…,an}，每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
InitList(): 初始化操作，建立一个空的线性表L。
isEmpty():判断线性表是否为空操作
clear():线性表置空操作
getItem(int i)：获取指定位置上面的元素操作
insert(int i, Object x)：在指定位置上面插入元素的操作
remove(int i)：删除指定位置上面的元素的操作
indexOf(Object x)：查找指定元素的位置首次出现的位置操作
display()：显示线性表中的内容操作
length()：获取线性表中元素的长度操作
endADT

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

代码描述

/**
 * 
 * @author wangxiaojian
 * 
 */
public interface IList {
    // 线性表置空操作
    public void clear();

    // 判断线性表是否为空操作
    public boolean isEmpty();

    // 获取线性表中元素的长度操作
    public int length();

    // 获取指定位置上面的元素操作
    public Object get(int i);

    // 在指定位置上面插入元素的操作
    public void insert(int i, Object x);

    // 删除指定位置上面的元素的操作
    public void remove(int i);

    // 查找指定元素的位置首次出现的位置操作
    public int indexOf(Object x);

    // 显示线性表中的内容操作
    public void display();
}

举个例子

比如要实现两个线性表A、B的并集操作，即要使得集合A=A∪B。

A∪B

其实仔细思考一下，我们只需要循环遍历集合B中的每个元素，判断当前元素是否存在A中，弱不存在，则插入A中即可。
综合分析，我们需要运用到几个基本的操作组合即可：
length()
getItem(int i)
indexOf(Object x)
insert(int i, Object x)

public class Union {
    public static void unionL(List a,List b){
        int bLen = b.size();
        for(int i=0;i<bLen;i++){
            if (a.indexOf(b.get(i))==-1){
                //跟insert一样
                a.add(b.get(i));
            }
        }
        System.out.print(a);
    }

    public static void main(String[] args) {
        List<String> a = new ArrayList<String>();
        a.add("苍井空");
        a.add("武藤兰");
        a.add("吉泽明步");
        List<String> b = new ArrayList<String>();
        b.add("苍井空");
        b.add("武藤兰");
        b.add("锋诚");
        unionL(a,b);
    }
}

运行结果：[苍井空, 武藤兰, 吉泽明步, 锋诚]

欢迎关注，每天更新