• 我们现在开始重新学习线性表，先贴一下关于线性表需要学习的内容吧。

前面我们已经给了线性表的定义，现在我们来分析一下，线性表应该有一些什么样的操作呢？然后再定义线性表的ADT。

• 还是拿伍迷老师的精彩例子：

创建与初始化：老师为了让小朋友有秩序地出入，所以就考虑给他们排一个队，并且是长期使用的顺序，这个考虑和安排的过程其实就是一个线性表的创建和初始化过程。

置空：一开始没经验，把小朋友排好队后，发现有的高有的矮，队伍很难看，于是就让小朋友解散重新排——这是一个线性表重置为空表的操作。

获取元素：排好了队，我们随时可以叫出队伍某一位置的小朋友名字及他的具体情况。这种可以根据位序得到数据元素也是一种很重要的线性表操作。

查找：还有什么呢，有时我们想知道，某个小朋友，比如麦兜是否是班里的小朋友，老师会告诉我说，不是，麦兜在春田花花幼儿园里，不在我们幼儿园。这种査找某个元素是否存在的操作很常用。

表长度：而后有家长问老师，班里现在到底有多少个小朋友呀，这种获得线性表长度的问题也很普遍。

插入与删除。显然，对于一个幼儿园来说，加入一个新的小朋友到队列中，或因某个小朋友生病，需要移除某个位置，都是很正常的情况。对于一个线性表来说，插入数据和删除数据都是必须的操作。

• 线性表大概就是上面这些操作了，所以其ADT可以定义为：

ADT 线性表 (List)
Data
Operation  
    void initList(*L);	//创建并初始化一个空线性表，如果成功返回true，修改表传指针   
    bool listEmpty(L);	//判断一个线性表是否为空，不修改表传值   
    void clearList(*L);	//清空一个线性表，成功返回true   
    bool getElem(L,i,*e);	//从某个位置取出元素并赋值给e(i的范围是[1,L.length])，修改e的值所以传递一个指针，成功返回true  
    int locateElem(L,e);	//查找线性表中是否有e，如果有返回它的位置(从1开始)，否则返回0表示失败  
    bool listInsert(*L,i,e);	//插入一个元素e在第i个元素之前(i的取值范围是[1,L.length+1]) ，成功返回true   
    bool listDelete(*L,i,*e);	//删除在第i个位置上的元素(i的取值范围是[1,L.length]),删除的元素赋给e，成功返回true  
    int listLength(L);	//返回线性表的元素个数  
endADT

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

比如，要实现两个线性表集合A和B的并集操作。即要使得集合A=AUB。说白了，就是把存在集合B中但并不存在A中的数据元素插入到A中即可。

仔细分析一下这个操作，发现我们只要循环集合B中的毎个元素，判断当前元素是否存在A中，若不存在，则插入到A中即可。思路应该是很容易想到的。

void unionL(List *la,List lb){  
    int index;  
    int laLength = listLength(*la);	//得到a的长度，需要一个线性表而不是一个地址   
    int lbLength = listLength(lb);}   
    ElemType e;	//声明一个元素   
      
    for(index=1;index<=lbLength;index++){	//遍历lb   
        getElem(lb,index,&e);	//依次得到lb中的元素   
        if(!locateElem(*la,e)){	//检查是否在la中出现   
            listInsert(la,++laLength,e);	//没有出现则插入队尾，前自增！   
        }  
    }  
}  

• 这里，我们对于union操作，用到了前面线性表基本操作ListLength、GetElem、LocateElem、Listlnsert等，可见，对于复杂的个性化的操作，其实就是把基本操作组合起来实现的。

延伸阅读

此文章所在专题列表如下：

1. 第01话：线性表的概念与定义
2. 第02话：线性表的抽象数据类型ADT定义
3. 第03话：线性表的顺序存储结构
4. 第04话：线性表的初始化
5. 第05话：线性表的遍历、插入操作
6. 第06话：判断线性表是否为空与置空操作
7. 第07话：线性表的查找操作
8. 第08话：线性表删除某个元素
9. 线性表顺序存储的优缺点
10. 线性表链式存储结构的由来与基本概念
11. 单链表的头指针、头结点与首元结点
12. 单链表的结构体定义与声明
13. 单链表的初始化
14. 单链表的插入与遍历操作
15. 单链表的删除某个元素的操作
16. 获取单链表中的指定位置的元素
17. 查找某数在单链表中的位置
18. 用头插法实现单链表整表创建
19. 用尾插法实现单链表整表创建
20. 将单链表重置为空表
21. 单链表反转/逆序的两种方法
22. 单链表反转/逆序的第三种方法
23. 求单链表倒数第N个数
24. 用标尺法快速找到单链表的中间结点
25. 如何判断链表是否有环的存在
26. 单链表建环，无环链表变有环
27. 删除单链表中的重复元素

本文地址：http://www.nowamagic.net/librarys/veda/detail/2199，欢迎访问原出处。