// 合并顺序表

#include "pch.h"

#include <iostream>
#include <fstream>
using namespace std;

#define ERROR 0
#define MAXSIZE 50

typedef struct // 定义顺序表
{
	int *elem;
	int length;
}SqList;

int num_a = 0, num_b = 0;
char st = 'A';

// 创建顺序表
void InitList_SQ(SqList &L, int n) 
{
	L.elem = new int[MAXSIZE];
	if (!L.elem)
		exit(0);
	L.length = 0;
}

// 依次往顺序表L插入数据
void InputData_SQ(SqList &L, int n) 
{
	int i = 0;
	char FileName[20] = { 0 };

	cout << "请输入非递减线性表" << st << "的数据文件名称(文件名+“.txt”,比如List" << st << ".txt)" << endl;
	++st;
	gets_s(FileName);
	fstream fFile;
	fFile.open(FileName);
	if (!fFile) 
	{
		cout << "未打到相关数据文件，无法打开." << endl;
		exit(ERROR);
	}
	while (!fFile.eof()) 
	{
		fFile >> L.elem[i];
		i++;
	}
	L.length = i;
}

// 输出顺序表里面的每一个元素
void Output_SQ(SqList L) 
{
	for (int i = 0; i < L.length; i++) 
	{
		if (i)
			cout << "，";
		cout << L.elem[i];
	}
}

// 顺序表有序合并
void MergeList_SQ(SqList  LA, SqList LB, SqList &LC) 
{
	int *pa, *pb, *pc,*pa_list, *pb_list;
	pa = LA.elem;
	pb = LB.elem;
	LC.length = LA.length + LB.length;		// LC长度是两个顺序之和的长度
	
	LC.elem = new int[LC.length];
	pc = LC.elem;		// 指针pc指向新表的第一元素

	pa_list = LA.elem + LA.length - 1;		// 指针pa_list指向LA表的最后一个元素
	pb_list = LB.elem + LB.length - 1;

	while (pa <= pa_list && pb <= pb_list)  // 两个表都非空的
	{
		if (*pa <= *pb)		// 依次 摘取两表中值比较小结点插入到LC表的最后位置
			*pc++ = *pa++;
		else
			*pc++ = *pb++;
	}

	while (pa <= pa_list)		// LB已经到达表尾，依次将LA剩余元素插入到LC表的最后
		*pc++ = *pa++;
	while (pb <= pb_list)
		*pc++ = *pb++;
}


int main()
{
	SqList LA, LB, LC;
	InitList_SQ(LA, num_a);
	InputData_SQ(LA, num_a);
	Output_SQ(LA);
	cout << endl;


	InitList_SQ(LB, num_b);
	InputData_SQ(LB, num_b);
	Output_SQ(LB);
	cout << endl;


	MergeList_SQ(LA, LB, LC);

	cout << "非递减纯属表A,B合并后的线性表C结果为:" << endl;
	Output_SQ(LC);
	cout << endl;
	
	return 0;
}