// 合并链表
#include "pch.h"
#include <iostream>
#include <fstream>
using namespace std;

#define ERROR 0

// 定义单链表 
typedef struct LNode 
{
	int data;
	struct LNode *next;
}LNode,*LinkList;

int num_a;
int num_b;
int st = 'A';

// 创建单链表
void InitList_LL(LinkList &L) 
{
	L = new LNode;
	L->next = NULL;
}

// 依次向单链表L输入对应的数据
void LinkList_Input(LinkList &L, int n) 
{
	int i;
	LNode *p, *r;
	r = L;
	char filename[20] = { 0 };
	cout << "请输入非递减单向链表" << st << "的数据文件名称(文件名+“.txt”，比如List" << st << ".txt)" << endl;
	++st;
	gets_s(filename);
	fstream file;
	file.open(filename);
	if (!file)
	{
		cout << "未找到相关的数据文件，无法打开." << endl;
		exit(ERROR);
	}

	while (!file.eof()) 
	{
		p = new LNode;
		file >> p->data;
		p->next = NULL;
		r->next = p;
		r = p;
		n++;
	}

	file.close();
}

// 输出链表的数据结点
void Output_LL(LinkList L)
{
	int i = 0;
	LNode *p;
	p = L->next;
	while (p) 
	{
		if (i)
			cout << "，";
		cout << p->data;
		p = p->next;
		i = 1;
	}
}


// 链式存储结构有序表的合并
void MergeLinkList_LL(LinkList &LA, LinkList &LB, LinkList &LC) 
{
	LinkList pa, pb, pc;
	pa = LA->next;
	pb = LB->next;
	LC = LA;		// 用La的头结点作为LC头结点
	pc = LC;		// pc的初值指向LC的头结点 

	while (pa && pa) 
	{
		if (pa->data <= pb->data)
		{
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		}
		else
		{
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
	}
	pc->next = pa ? pa : pb;		// 插入非空表的剩余段
	delete LB;
}

int main()
{
	LinkList la, lb, lc;

	InitList_LL(la);
	LinkList_Input(la, num_a);
	Output_LL(la);
	cout << endl;


	InitList_LL(lb);
	LinkList_Input(lb, num_b);
	Output_LL(lb);
	cout << endl;

	InitList_LL(lc);
	MergeLinkList_LL(la, lb, lc);

	cout << "非递减单向链表A B合并后非递减单向链表C为:\n";
	Output_LL(lc);
	cout << endl;

	return 0;
}