2-8 线性表的应用(1) 线性表的合并

【算法】线性表的合并

问题描述：假设利用两个线性表La和Lb分别表示两个集合A和B，现要求一个新的集合A=AUB（若两个集合有重复元素，只取一次）

La=(7, 5, 3, 11) Lb=(2, 6, 3) → 修改La=(7, 5, 3, 11, 2, 6)

算法步骤：

1. 将Lb（或La）中元素依次取出
2. 在La中查找该元素
3. 如果找不到，将其插入La的最后
4. 如果插入，将La的长度加一

代码实现：

void union(List &La, List Lb) {
	La_len = ListLength(La);
	Lb_len = ListLength(Lb);
	for(i = 1 ;i <= Lb_len;i++) { //将表Lb循环一遍
		GetElem(Lb, i ,e); //从表Lb中取出i位元素，用e返回
		if(!GetElem(La, e)) //如果表La中没有e元素
			ListInsert(&La, ++La_length,e);  //在La末尾插入e
	}
}

时间复杂度：O(ListLength(La)*ListLength(Lb))

2-8 线性表的应用(2) 有序表的合并

【算法】有序表的合并

问题描述：已知线性表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新线性表Lc，且Lc中的数据元素仍按值非递减有序排列

La=(1,7,8) Lb=(2,4,6,8,8,10,11) → Lc=(1,2,4,6,7,8,8,8,10,11)

算法步骤：

1. 创建一个空表Lc
2. 依次从La或Lb中选取元素较小的结点插入到Lc表的最后，直至其变为一个空表为止
3. 继续将La或Lb其中一个表的剩余结点插入在Lc表的最后