顺序表：合并2个非递减顺序表

一、定义顺序表结构

#define INIT_SIZE 10	///< 顺序表初始容量
typedef int seqType;	///< 定义顺序表元素类型
/// @brief 顺序表结构定义
typedef struct t_sqList
{
	seqType* pbase;	///< 表基址
	int capacity;	///< 表容量
	int size;	///< 表长度
}mySList;

二、合并2个非递减顺序表。具体题目与解法如下：

1、题目一

1. 给定2个非递减顺序表：pa，pb，
2. 再给定一个用于存放合并结果的顺序表：pc
3. 要求按元素值由小到大合并，结果存放在pc

/// @brief 合并2顺序表，结果存放于第3顺序表
/// @param pc：合并结果存放于pc表
/// @param pa：顺序表a
/// @param pb：顺序表b
/// @return status：返回是否成功合并标志
/// @retval ERROR(0)：顺序表不存在，不可操作
/// @retval ERR_OVERFLOW(-2)：空间不足，开辟新空间失败，合并失败
/// @retval OK(1)：合并成功
status sList_merge1(mySList* pc, const mySList* pa, const mySList* pb)
{
	if (NULL == pa || NULL == pb || NULL == pc)
	{
		return ERROR;
	}
	
	if (NULL == pa->pbase || NULL == pb->pbase || NULL == pc->pbase)
	{
		return ERROR;
	}
	/// 构建表pc的容量，使其可以容纳pa,pb所有元素
	int capacity = pa->capacity + pb->capacity;
	if (pc->capacity < capacity)
	{
		pc->capacity = capacity;
		if (pc->pbase != NULL)
		{
			free(pc->pbase);
		}
		pc->pbase = (seqType*)malloc(sizeof(seqType) * (capacity));
		if (NULL == pc->pbase)
		{
			return ERR_OVERFLOW;
		}
	}
	/// 指针指向表基地
	seqType* p1 = pa->pbase;
	seqType* p2 = pb->pbase;
	seqType* p3 = pc->pbase;
	/// 指针指向表尾元素
	seqType* p1_last = pa->pbase + pa->size - 1;	
	seqType* p2_last = pb->pbase + pb->size - 1;
	/// 比较2表元素，将较小元素拷贝至pc表。至少其中一表遍历完，循环退出
	while (p1 <= p1_last && p2 <= p2_last)
	{
		if (*p1 <= *p2)
		{
			*p3++ = *p1++;
		}
		else
		{
			*p3++ = *p2++;
		}
	}
	/// 合并a表剩余部分
	while (p1<=p1_last)
	{
		*p3++ = *p1++;
	}
	/// 合并b表剩余部分
	while (p2 <= p2_last)
	{
		*p3++ = *p2++;
	}
	pc->size = capacity;
	return OK;
}

2、题目2：方法一

1、题目要求

• 给定2个非递减顺序表：pa，pb，表容量分别是：m+n，n
• 将2表元素由小到大合并，合并结果存放于pa表中
• 要求不能额外开辟开辟辅助的数组的空间，即要求空间复杂度为O(1)

2、思路

• 逐个比较2表的表尾元素，取较大的元素从pa的表尾空间处向前存放。
• 继续上述比较、存放步骤，直接到其中一表所有元素被处理完
• 把另一个未处理完的表剩余元素拷贝至pa剩余空间

/// @brief 方法1：合并2顺序表，结果存放于第1个顺序表，要求不能开辟额外数组空间
/// @param pc：合并结果存放于pc表
/// @param pa：顺序表pb，其长度为n，容量为n
/// @param pb：顺序表pa，其长度为m，容量为m+n，结果存放于pa
/// @return status：返回是否成功合并标志
/// @retval ERROR(0)：顺序表不存在，不可操作
/// @retval OK(1)：合并成功
/// @see sList_merge3()
status sList_merge2(mySList* pa, const mySList* pb)
{
	if (NULL == pa || NULL == pb)
	{
		return ERROR;
	}
	if (NULL == pa->pbase || NULL == pb->pbase)
	{
		return ERROR;
	}

	int m = pa->size;
	int n = pb->size;
	int index = m + n - 1;
	int i = m - 1;
	int j = n - 1;
	while (i > -1 && j > -1)
	{

		if (pa->pbase[i] > pb->pbase[j])
		{
			pa->pbase[index--] = pa->pbase[i--];
		}
		else
		{
			pa->pbase[index--] = pb->pbase[j--];
		}
	}
	 
	/// 若pa表元素全部处理完，处理剩下pb表元素即可
	/// 若pb表元素全部处理完，剩余pa表元素则无须再处理
	while (i < 0 && j>-1)	
	{
		pa->pbase[index--] = pb->pbase[j--];
	}
	pa->size = m + n;
	return OK;
}

3、题目2：方法二

1、思路

• 遍历pb表，将最小元素与pb[0]交换，即pb[0]处存放pb表中的最小元素
• 取pa[i]元素与pb[0]比较，取较大者存于pb[0]，较小者存于pa[i]。i自增。
• 重复执行上述2个步骤，直接遍历完pa表元素
• 对pb表进行由小到大排序后将pb表元素拷贝至pa表剩余空间

/// @brief 交换2个数组对应下标i,j处元素
void mySwap(seqType* arr, seqType* brr, int i, int j)
{
	if (arr == NULL || brr == NULL || i < 0 || j < 0)
	{
		return;
	}
	int tmp = arr[i];
	arr[i] = brr[j];
	brr[j] = tmp;
}


/// @brief 方法2：合并2顺序表，结果存放于第1个顺序表，要求不能开辟额外数组空间
/// @param pc：合并结果存放于pc表
/// @param pa：顺序表pb，其长度为n，容量为n
/// @param pb：顺序表pa，其长度为m，容量为m+n，结果存放于pa
/// @return status：返回是否成功合并标志
/// @retval ERROR(0)：顺序表不存在，不可操作
/// @retval OK(1)：合并成功
/// @see sList_merge2()
status sList_merge3(mySList* pa, mySList* pb)
{
	if (NULL == pa || NULL == pb)
	{
		return ERROR;
	}
	if (NULL == pa->pbase || NULL == pb->pbase)
	{
		return ERROR;
	}
	int i = 0;	///< 用于遍历pa
	int j = 0;	///< 用于遍历pb

	
	while (i < pa->size)
	{
		///取pb最小元素存放于pb[0]处
		while (j<pb->size)
		{
			if (pb->pbase[0] > pb->pbase[j])
			{
				mySwap(pb->pbase, pb->pbase, 0, j);
			}
			++j;
		}

		/// 取pa[i]与pb[0]比较，取较大者存于pb[0]，较小者存入pa[i]：
		if (pa->pbase[i] > pb->pbase[0])
		{
			mySwap(pa->pbase, pb->pbase, i, 0);
		}
		++i;
	}

	/// while循环结束后，pa表原数据已全部处理完。再对pb排序后追加到pa表尾即可
	for (i = 0; i < pa->size; ++i)
	{
		for (j = i + 1; j < pb->size; ++j)
		{
			if (pb->pbase[i] > pb->pbase[j])
			{
				mySwap(pb->pbase, pb->pbase, i, j);
			}
		}
	}
	
	/// 将pb表元素从小到大追加至pa表尾
	j = 0;
	while (j < pb->size)
	{
		pa->pbase[pa->size + j] = pb->pbase[j];
		++j;
	}
	pa->size += pb->size;
	return OK;
}