#include
#include
#include

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


/*先進(jìn)行排序在進(jìn)行入隊列：?
申請兩個隊列P和Q，先判斷兩個是不是非空隊列，（如果兩個都非空，就比較隊列大小，小的出隊列，最小兩個進(jìn)行合并）
排序之后把數(shù)字放在Q，合并之后把數(shù)字放在P?。
定義min1，min2為最小的兩個數(shù)。在數(shù)組P，Q里面找到一個最小的數(shù)min1?
在數(shù)組P，Q里面找到另一個最小的數(shù)min2??。把兩個小數(shù)想家summin入隊列P，即已合并的數(shù)字放在隊列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)疥犃?
typedef?struct?node
{
	datatype?data;
	struct?node?*next;
}?QNode*L