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. 将链表La的头结点同时作为Lc的头结点
2. 设立指针pa和pb，分别指向两个链表中的首元结点
3. 当pa和pb都不为空时，将pc指针指向pa和pb中较小的结点。随后将此较小结点的地址赋给pc，将目前指向此结点指针（pa或pb）后移
4. 若pa或pb为空，将另一链表中剩下的元素接入pc指针之后
5. 释放非返回链表的头结点

代码实现：

void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) {
	pa = La->next; //将pa和pb指向表La和Lb的首元结点
	pb = Lb->next;
	pc = La = Lc;
	while(pa && pb) {
		if(pa->data <= pb->data) {
			pc->next = pa; //将pc的指针域指向较小结点pa
			pc = pa; //将pc指向最新结点pa
			pa = pa->next; //将pa指针后移一位
		} else {
			pc ->next = pb;
			pc = pb;
			pb = pb->next;
		}
	}
	pc->next = pa ? pa:pb;
	free(Lb);
}

算法时间复杂度：O(ListLength(La)+ListLength(Lb))

算法空间复杂度：O(1)

2-9 案例与实践(1)-多项式运算

【案例】多项式运算

多项式：$P_n(X)=p_0x^0+p_1x^1+p_2x^2+...+p_nx^n$