#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define MAX 100
typedef int DataType;
typedef struct {
	DataType data[MAX];
	int length;
}SqList;

void initList(SqList *L){
	L->length = 0;
	printf("\n初始化成功\n");
}
int insertList(SqList *L, int i, DataType e){
	if(i<1 || i>(L->length+1)){
		return 0;
	}
	// 将 i 及其以后的元素向后移动 1 个单位
	for(int j=L->length;j<i-1;j--){
		L->data[j] = L->data[j-1];
	}
	// 插入
	L->data[i-1]=e;
	L->length++;
	return 1;
}
int DeleteList1(SqList *L, DataType e){
	for(int i=0;i<L->length;i++){
		if(L->data[i]==e){
			// 将 i 以后的元素向前移动 1 个单位
			for(int j=i;j<L->length;j++){
				L->data[j]=L->data[j+1];
			}
			L->length--;
			return 1;
		}
	}
	return 0;
}
int DeleteList2(SqList *L, int i){
	if(i<1 || i>(L->length)){
		return 0;
	}
	// 将 i-1 以后的元素向前移动 1 个单位
	for(int j=i-1;j<L->length;j++){
		L->data[j]=L->data[j+1];
	}
	L->length--;
	return 1;
}
int FindList(SqList *L, DataType e){
	int i=0;
	while(i<L->length && L->data[i]!=e){
		i++;
	}
	// 未找到
	if(i>=L->length){
		return -1;
	}
	return i+1;
}
void OutputList(SqList *L){
	printf("\n\n");
	for(int i=0;i<L->length;i++){
		printf("第 %d 个元素的值为：%d\n",i+1,L->data[i]);
	}
	printf("\n\n");
}
int DeleteList3(SqList *L, DataType start, DataType end){
	// 确认 start <= end
	int temp;
	if(start>end){
		temp=end;
		end=start;
		start=temp;
	}
	int l_s=-1,l_e=-1;
	for(int i=0;i<L->length;i++){
		// 查找区间小的位置
		if(L->data[i] >= start && l_s==-1){
			l_s=i;
		}
		// 查找区间大的位置
		if(L->data[i] <= end){
			l_e=i;
		}
	}
	// 未找到
	if(l_s==-1 || l_e==-1){
		return 0;
	}
	// 将 l_e + 1 以后的元素向前移动 l_e - l_s + 1 个单位
	int move = l_e - l_s + 1;
	for(int i=l_e + 1;i<L->length;i++){
		L->data[i-move] = L->data[i];
	}
	L->length -= move;
	return 1;
}
SqList Merge(SqList L1, SqList L2){
	SqList L3;
	int x=0,y=0,n=0;
	initList(&L3);
	while(x<L1.length && y<L2.length){
		if(L1.data[x]<L2.data[y]){
			L3.data[n]=L1.data[x];
			n++;
			x++;
		} else if (L1.data[x]>L2.data[y]){
			L3.data[n]=L2.data[y];
			n++;
			y++;
		} else if (L1.data[x]==L2.data[y]){
			L3.data[n]=L1.data[x];
			n++;
			x++;
			y++;
		}
	}
	// 插入剩余元素
	for(int i=x;i<L1.length;i++){
		L3.data[n]=L1.data[x];
		n++;
		x++;
	}
	for(int i=y;i<L2.length;i++){
		L3.data[n]=L2.data[y];
		n++;
		y++;
	}
	L3.length=n;
	return L3;
}
int main(){
	SqList L1,L2,L3;
	int n,choice,x,y;
	DataType e;
	initList(&L1);
	
	for(;;){
		printf("\t\t1.输入线性表\n");
		printf("\t\t2.查找元素\n");
		printf("\t\t3.删除指定值的元素\n");
		printf("\t\t4.删除指定位置的元素\n");
		printf("\t\t5.删除位于区间的元素\n");
		printf("\t\t6.合并另一个线性表\n");
		printf("\t\t0.退出\n");
		
		printf("请选择：");
		scanf("%d",&choice);
		if(choice==0) break;
		switch (choice) {
		case 1:
			printf("请输入线性表长度：");
			scanf("%d",&n);
			initList(&L1);
			for(int i=0;i<n;i++){
				printf("请输入第 %d 个元素：",i+1);
				scanf("%d",&e);
				insertList(&L1,i+1,e);
			}
			OutputList(&L1);
			break;
		case 2:
			printf("请输入需要查找的元素：");
			scanf("%d",&e);
			n=FindList(&L1,e);
			if(n>-1){
				printf("该元素在 %d\n",n);
			} else {
				printf("未找到该元素\n");
			}
			break;
		case 3:
			printf("请输入需要删除的元素的值：");
			scanf("%d",&e);
			n=DeleteList1(&L1,e);
			if(n==0){
				printf("删除失败，元素不存在。\n");
			} else {
				printf("删除成功\n");
			}
			OutputList(&L1);
			break;
		case 4:
			printf("请输入需要删除的元素的位置：");
			scanf("%d",&n);
			n=DeleteList2(&L1,n);
			if(n==0){
				printf("删除失败，位置不存在。\n");
			} else {
				printf("删除成功\n");
			}
			OutputList(&L1);
			break;
		case 5:
			printf("请输入需要删除的元素值区间 x y：");
			scanf("%d %d",&x,&y);
			n=DeleteList3(&L1,x,y);
			if(n==0){
				printf("删除失败，位置不存在。\n");
			} else {
				printf("删除成功\n");
			}
			OutputList(&L1);
			break;
		case 6:
			printf("请输入第二个线性表的长度：");
			scanf("%d",&n);
			initList(&L2);
			for(int i=0;i<n;i++){
				printf("请输入第 %d 个元素：",i+1);
				scanf("%d",&e);
				insertList(&L2,i+1,e);
			}
			OutputList(&L2);
			L3=Merge(L1,L2);
			printf("合并后线性表：");
			OutputList(&L3);
		default:
			break;
		}
		printf("请按任意键继续...");
		getch();
		system("cls");
	}
    printf("感谢使用，再见\n");
	return 0;
}