（一）线性表

线性表（linear_list）：n个数据元素的有限序列。如字母表、成绩表、价目表，图书索引表等。

• 线性表中的元素可以是各种各样，但是同一线性表中的元素必定有相同特性，即属于同一数据对象，相邻元素之间存在着序偶关系。
• 可以理解为多个点用线连起来
  o------o------o------o------o------o------o

线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短，即对线性表的数据元素不进可以进行访问，还可以插入删除。

算法示例：

• 1. 有两个线性表LA和LB，合并两个线性表LA=LA U LB（无重复元素）。
  伪代码:

// 获取长度
la_len = ListLength(La); 
lb_len = ListLength(Lb);
for (i = 1; i <= lb_len; i++) {
  GetElem(Lb, i, e); // 取Lb中的第i个元素赋给e
  // La中不存在相同的元素就插入到La中
  if (!LacateElem(La, e, equal)) ListInsert(La, ++la_len, e)
}

思路：遍历线性表LA，依次取得元素，从线性表LB中依次取得每个元素，并依值在线性表LA中进行查询对比，若不存在，则插入之。

• 2. 已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列，
  如:

LA = (3, 5, 8, 11);
LB = (2, 6, 8, 9, 11, 15, 20);
则
LC = (2, 3, 5, 6, 8, 8, 9, 11, 15, 20);

思路：先设LC为空表，然后将LA或LB中的元素逐个插入到LC中即可。为使LC中元素按值非递减有序排列，可设两个指针i和j分别指向LA和LB中某个元素，若设i当前所致的元素为a，j档期所致的元素为b，则当应插入到LC中的元素C为：

当 a <= b 时，c = a
当 a > b 时，c = b

显然，指针i和j的初始值为1，在所指元素插入LC之后，在LA或LB中顺序后移，上诉归并算法如下所示：

InitList(Lc); // 初始化Lc
i = j = 1, k = 0;
// 获取la和lb的长度
la_len = ListLength(La);  
lb_len = ListLength(Lb);
while ((i <= la_len) && (j <= lb_len)) { // la和lb均非空
    GetElem(La, i, ai); 
    GetElem(Lb, j, bj); 
    if (ai <= bj) {
        ListInsert(Lc, ++k, ai);
        ++i;
    }else {
        ListInsert(Lc, ++k, bj);
        ++j;
    }
}
while (i <= la_len) {
    GetElem(La, i, ai); 
    ListInsert(Lc, ++k, ai);
}
while (i <= lb_len) {
    GetElem(Lb, j, bj); 
    ListInsert(Lc, ++k, bj);
}

算法中含有3个（while）循环语句，但只有当i和j均指向表中实际存在的元素时，才能取得数据元素的值并进行比较；并且当其中一个线性表的元素均已插入到线性表LC中后，只要将另一个线性表中剩余元素依次插入即可。因此，对于每一组具体的输入（LA或LB），后两个（while）循环语句只执行一个循环体。