（一）线性表（一）线性表

线性表（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）循环语句只执行一个循环体。