第四讲 线性表的抽象数据类型
上节课我们讲到了线性表的定义，讲到了所谓抽象数据类型就是把数据类型和相关操作捆绑在一起。
那么我们接下来分析一下，线性表应该有什么样的相关操作呢？
从上讲中的老师组织春游活动排队的例子中，我们可以总结相关的操作如下：
- 开始排队：线性表创建
- 队伍里让某个同学出列：线性表删除某个元素
- 有入列就有入列吧：线性表插入某个元素
- 等等。。。
好了，剩下的还有很多大家可以自己想象。
线性表的抽象数据类型定义：
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);
}
}
运行结果：[苍井空, 武藤兰, 吉泽明步, 锋诚]
欢迎关注，每天更新
