//顺序表的合并
//输入元素函数  put
//输出元素函数  output
//合并  		Merge 
#include<stdio.h> 
#include<stdlib.h>
#include<algorithm> 
using namespace std;
#define LIST_INIT_SIZE  80
#define LISTINCREMENT 10
typedef struct 
{
	int *elem;
	int length;  //有效长度 
	int size;    //顺序表的容量 
}Sq;
Sq L1,L2,L3;
void InitSq(Sq &L) //创建一个新链表
{
	int *p;
	p=(int*)malloc(LIST_INIT_SIZE*sizeof(int));
	if(p==NULL)
	{
		printf("内存分配失败!\n");
		exit(-1);
	}
	 L.elem=p; 
	 L.length=0;
	 L.size=LIST_INIT_SIZE; 
	 return;
}
void listput(Sq &L,int N) //为L赋N个值 【1~N】 
{
	int a,k=0;
	//printf("\n请输入该非递减顺序表的有效元素个数:\n");
	//scanf("%d",&N);
	while(1)
	{
	
		if(L.length==L.size)
		{
			int* newbase; 
			newbase=(int *)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(int));
			if(newbase==NULL)
			{
				printf("内存分配失败!\n");
				exit(-1) ;
			}
			L.elem=newbase;
			L.size+= LISTINCREMENT;
		}
		printf("请输入第%d个元素:\n",k+1);
		scanf("%d",&a);
		if(L.length!=0&&L.elem[L.length-1]>a)
		{
			printf("\n对不起,该数据不合格,请重新输入!\n\n");
		}
		else
		{
			L.elem[L.length]=a;
			L.length++;
			k++;
		} 
		if(k==N)
		return;
	}
}
bool listinsert(Sq &L)//在第 i 个元素之前插入一个数据  
{
	int i; 
	printf("请输入要插入元素的位置【在该位置之前插入】:\n") ;
	scanf("%d",&i) ;
	if(i>L.length||i<1)
	{
		printf("插入位置不合理,请重新操作!\n");
		listinsert(L);
	}
	else
	{
		if(L.length==L.size)
		{
			int* newbase; 
			newbase=(int *)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(int));
			if(newbase==NULL)
			{
				printf("内存分配失败!\n");
				exit(-1) ;
			} 
			L.elem=newbase;
			L.size+= LISTINCREMENT;
		}
		int j,e;
		printf("请输入要插入的元素的数值");
		scanf("%d",&e);
		for(j=L.length -1;j>=i-1;--j)
		{
			L.elem [j+1]=L.elem [j];
		}
		//L.elem [j+1]=L.elem [j];
		L.elem [j+1]=e;
		L.length ++;
		printf("插入成功!\n");
		return true; 
	}
	
}
bool listdelet(Sq &L)//删除第 i 个数据 
{
	int i;
	printf("请输入要删除的元素的位置:\n");
	scanf("%d",&i);
	if(i<1||i>L.length)
	{
		printf("删除位置不合理,重新输入!\n********************\n\n");
		listdelet(L);
	}
	else
	{
		printf("成功删除第%d个元素%d!\n",i,L.elem[i-1]);
		for(;i<L.length;++i) 
		{
			L.elem[i-1]=L.elem[i];
		}L.length--;
		return true;
	} 
	
}
void MergeList(Sq &L3,Sq L1,Sq L2)
{
	if(L3.size <L1.length+L2.length) 
	{
		int* newbase; 
		newbase=(int *)realloc(L3.elem,(L1.length+L2.length+LISTINCREMENT)*sizeof(int));
		if(newbase==NULL)
		{
			printf("内存分配失败!\n");
			exit(-1) ;
		} 
		L3.elem=newbase;	
	}
	int i;
	L3.elem=L1.elem;
	L3.length=L1.length;
	for(i=0;i<L2.length;++i)
	{
		L3.elem[L1.length+i]=L2.elem[i];
		L3.length++;
	}
	sort(L3.elem,L3.elem+L3.length);
}
void listprint(Sq L) //输出该表数据,每10 个一行
{
	if(L.length==0) 
	{
		printf("Sorry,该表是空表!\n");
		return; 
	}
	int i;
	for(i=0;i<L.length;++i)
	{	
		if(i%10==0&&i!=0) 
		printf("\n");
		printf("%-4d",L.elem[i]);
	} 
	printf("\n") ;
	return;
}
/*int get(Sq L,int i)// 取出第 i 个数据 
{
	if(i<1||i>L.length)
	{
		printf("该数据无效!\n");
		exit(-1);
	}
	return L.elem[i-1];
}*/
//选择  1: 插入	2:删除:	3:合并  4:输出:  0:退出 
void menu(Sq L) 
{
	printf("- - - - - - - - - - - - - - - - -\n") ;
	printf("如下操作:\n") ;
	printf("1:	插入.	2:	删除.\n3:	合并.	4:	输出.\n");
	printf("0:	退出.\n- - - - - - - - - - - - - - - - -\n") ;
	printf("请选择..\n") ;
	int k;
	scanf("%d",&k);
	switch(k) 
	{
		case 1: 
			listinsert(L);menu(L);
		case 2:
		    listdelet(L);menu(L);
		case 3:
		    MergeList(L3,L1,L2);menu(L);
		case 4: 
		    listprint(L);menu(L);
		default:return;
	}
}
int main()
{
	int N1,N2;
	InitSq(L1);
	InitSq(L2);
	InitSq(L3);
	printf(" *************************\n");
	printf(" 请输入第一个顺序表L1的有效元素个数:");
	scanf("%d",&N1);
	listput(L1,N1);
	menu(L1);
	printf(" 请输入第二个顺序表L2的有效元素个数:");
	scanf("%d",&N2);
	listput(L2,N2) ;
	menu(L2);
	MergeList(L3,L1,L2);
	menu(L3);
	return 0;
}

非递减顺序表的合并