#include "SqList.h"
#include "LinkList.h"
#include <iostream>
using namespace std;
//线性表的合并-顺序表实现
void merge(SqList& La, SqList Lb) {
	int La_len = getLength_Sq(La);
	int Lb_len = getLength_Sq(Lb);
	for (int i = 1; i <= Lb_len; i++) {
		ElementType temp;
		getElem_Sq(Lb, i, temp);
		cout << locateElem_Sq(La, temp) << endl;
		if (!locateElem_Sq(La, temp)) {
			listInsert_Sq(La, ++La_len, temp);
		}
	}
}
//有序表的合并-顺序表实现
void merge_Sq(SqList La, SqList Lb, SqList& Lc) {
	Lc.elem = new ElementType[getLength_Sq(La) + getLength_Sq(Lb)];
	Lc.length =0;
	int a = 0;
	int b = 0;
	int c = 1;
	while (a<getLength_Sq(La) && b<getLength_Sq(Lb)) {
		if (La.elem[a] <= Lb.elem[b]) {
			listInsert_Sq(Lc, c++, La.elem[a++]);
		}
		else {
			listInsert_Sq(Lc, c++, Lb.elem[b++]);
		}
	}
	while (a < getLength_Sq(La)) {
		listInsert_Sq(Lc, c++, La.elem[a++]);
	}
	while (b < getLength_Sq(Lb)) {
		listInsert_Sq(Lc, c++, Lb.elem[b++]);
	}
}
//有序表的合并-链表实现
void merge_L(LinkList& La, LinkList& Lb, LinkList& Lc) {
	Lc = La;
	LinkList pa = La->next;
	LinkList pb = Lb->next;
	//用La的头节点作为Lc的头节点
	LinkList pc = Lc;
	while (pa && pb) {
		if (pa->data <= pb->data) {
			pc->next = pa;
			pc = pc->next;
			pa = pa->next;
		}
		else {
			pc->next = pb;
			pc = pc->next;
			pb = pb->next;
		}
	}
	//插入剩余段
	pc->next = pa ? pa : pb;
	//释放Lb的头节点
	delete Lb;
}
int main() {
	/*
	SqList La,Lb,Lc;
	initList_Sq(La);
	initList_Sq(Lb);
	listInsert_Sq(La, 1, '1');
	listInsert_Sq(La, 2, '4');
	listInsert_Sq(La, 3, '5');
	listInsert_Sq(Lb, 1, '4');
	listInsert_Sq(Lb, 2, '6');
	merge_Sq(La, Lb,Lc);
	for (int i = 1; i <= getLength_Sq(Lc); i++) {
		ElementType e;
		getElem_Sq(Lc, i, e);
		cout <<e<<endl;
	}
	*/
	LinkList La, Lb, Lc;
	initList_L(La);
	initList_L(Lb);
	listInsert_L(La, 1, '1');
	listInsert_L(La, 2, '4');
	listInsert_L(La, 3, '5');
	listInsert_L(Lb, 1, '4');
	listInsert_L(Lb, 2, '6');
	listInsert_L(Lb, 3, '7');
	merge_L(La, Lb, Lc);
	for (LinkList p =Lc->next; p != NULL; p = p->next) {
		cout << p->data<<endl;
	}
	return 0;
}