#include
#include
#include

#define?MAXSIZE?1000
/*/**最優(yōu)合并問題
給定k個(gè)有序序列s1??s2...??sk?
?用2路合并算法將這k個(gè)序列合并成一個(gè)序列。
假設(shè)所采用的2路合并算法合并2個(gè)長度分別為m和n的序列需要m?+?n?-1次比較。
試設(shè)計(jì)一個(gè)算法確定合并這個(gè)序列的最優(yōu)合并順序，
使所需的總比較次數(shù)最少。*/?


/*先進(jìn)行排序在進(jìn)行入隊(duì)列：?
申請兩個(gè)隊(duì)列P和Q，先判斷兩個(gè)是不是非空隊(duì)列，（如果兩個(gè)都非空，就比較隊(duì)列大小，小的出隊(duì)列，最小兩個(gè)進(jìn)行合并）
排序之后把數(shù)字放在Q，合并之后把數(shù)字放在P?。
定義min1，min2為最小的兩個(gè)數(shù)。在數(shù)組P，Q里面找到一個(gè)最小的數(shù)min1?
在數(shù)組P，Q里面找到另一個(gè)最小的數(shù)min2??。把兩個(gè)小數(shù)想家summin入隊(duì)列P，即已合并的數(shù)字放在隊(duì)列P?
加起來?循環(huán)得到最后輸出sum*/?
/***********相關(guān)定義****************/
typedef?struct
{
	int?data[MAXSIZE];
	int?length;
}SqList;

//打印當(dāng)前L數(shù)組的順序?
void?print（SqList?*L）
{
???	for（int?i=0;ilength;i++）
	{
		printf（“%4d?“L->data[i]）;
	}
	printf（“\n“）;
}



typedef?int?datatype;

//鏈?zhǔn)疥?duì)列?
typedef?struct?node
{
	datatype?data;
	struct?node?*next;
}?QNode*L