#include<iostream>
#include<stdlib.h>

#define	LIST_INIT_SIZE 10/*线性表初始长度*/
#define LIST_CREATENT 2/*每次的增量*/

typedef int ElemType;

using namespace std;

typedef struct SqList/*线性表的数据结构定义*/
{
	ElemType *elem;/*线性表基址*/
	int length;/*当前线性表所含的元素个数*/
	int listSize;/*已经分配的长度*/
}SqList;

void InitList(SqList &L)/*线性表初始化*/
{
	L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
	L.length = 0;
	L.listSize = LIST_INIT_SIZE;
}

void DestoryList(SqList &L)/*销毁一个线性表*/
{
	free(L.elem);
	L.length = 0;
	L.listSize = 0;
}

void ClearList(SqList &L)/*清空一个线性表*/
{
	L.length = 0;
}

void listInsert(SqList &L, int k)/*往线性表中添加一个元素，按照元素从小到大的顺序*/
{
	ElemType *p,*q,*e;
	p = e = L.elem;
	if (L.length == L.listSize)/*线性表已经没有空间了，需要分配新空间*/
	{
		ElemType *newBase;
		newBase = (ElemType*)realloc(L.elem,(L.listSize+LIST_CREATENT)*sizeof(ElemType));
		if (!newBase)
			exit(1);
		L.elem = newBase;
		L.listSize += LIST_CREATENT;
	}
	if (L.length == 0)/*如果表中没有元素，则直接插入元素即可*/
	{
		*p = k;
		++L.length;
	}
	else/*线性表中有元素，则需要进行比较，找到合适的插入位置*/
	{
		int i = 0;
		while (i != L.length - 1)/*用一个指针指向线性表最后一个元素*/
		{
			++e;
			++i;
		}
		q = e;
		i = 0;
		while (k > *p&&i != L.length)/*寻找插入位置：如果k比当前元素大且p指向的元素不是最后一个*/
		{
			++p;
			++i;
		}
		--p;/*分两种情况：当前元素不是最后一个元素和当前元素是最后一个，两种情况均需要将待插入元素插在当前元素前面*/
		while (q != p)/*依次地将元素往后移动一个位置*/
		{
			*(q + 1) = *q;
			--q;
		}
		*(q + 1) = k;/*找到插入位置*/
		++L.length;/*线性表长度增加1*/
	}
}

void createList(SqList &L, int *k, int n)/*创建一个线性表*/
{
	int i;
	for (i = 0; i < n; ++i)
		listInsert(L,k[i]);
}

void ListDelete(SqList &L, int k)/*删除线性表中的一个元素*/
{
	ElemType *p, *q;
	p = q = L.elem;
	int i = 0,flag=1;
	while (i != L.length)
	{
		if (*p == k)
		{
			for (; i != L.length; ++p,++i)
				*p = *(p + 1);
			--L.length;
			cout << "Delete :" << k << endl;
			flag = 0;
			i = L.length;
		}
		else
		{
			++p;
			++q;
			++i;
		}
	}
	if (flag)
		cout << "Have not been found " << k << endl;
}

void ListTraveller(SqList L)/*遍历线性表*/
{
	int i = 0;
	ElemType *p=L.elem;
	while (i != L.length)
	{
		cout << *p++ << " ";
		i++;
	}
	cout << "\n";
}

bool LocateElem(SqList L,int k)
{
	ElemType *p = L.elem;
	int i = 0;
	while (i != L.length)
	{
		if (*p == k)
			return true;
		else
		{
			++p;
			++i;
		}
	}
	return false;
}

void unionSq(SqList &aL, SqList b)/*合并两个线性表*/
{
	int i=0,bl=b.length;
	ElemType *bp;
	bp = b.elem;
	while (i != bl)
	{
		if (!LocateElem(aL, *bp))
			listInsert(aL,*bp);
		++i;
		++bp;
	}
}

int main()
{
	ElemType a[] = { 1, 3, 5, 7, 9 }, b[] = { 2, 4, 6, 8, 10 };
	int a_len = sizeof(a) / sizeof(ElemType);
	int b_len = sizeof(b) / sizeof(ElemType);
	SqList sa, sb;
	InitList(sa);
	InitList(sb);
	createList(sa, a, a_len);
	createList(sb, b, b_len);
	unionSq(sa,sb);
	cout << "合并后的线性表：" << endl;
	ListTraveller(sa);
	return 0;
}