顺序表-00015-合并顺序表

typedef int seqType;	// 定义顺序表数据类型

// 定义顺序表的结构体
typedef struct t_sList
{
	seqType* pbase;		// 表基址
	int capacity;		// 表容量
	int size;			// 表长度
}mySList;

/**
* @brief 功能：合并2顺序表，结果存放于第3顺序表 \n
* @param[in] pc：合并存放存放于pc
* @param[in] pa：顺序表pa
* @param[in] pb：顺序表pb
* @retval OK(1)：追加成功
* @retval ERROR(0)：顺序表不存在，追加失败
* @retval OVERFLOW(-2)：合并失败
*/
status x01_merge(mySList* pc, const mySList* pa, const mySList* pb)
{
	if (pa == NULL || pb == NULL || pc == NULL || pa->pbase == NULL || pb->pbase == NULL)
	{
		return ERROR;
	}
	// 初始化表pc，构建pc，使得pc可容纳pa,pb2表元素
	if (pc->capacity < pa->size + pb->size)
	{
		if (pc->pbase != NULL)	// 先释放pc表空间
		{
			free(pc->pbase);
		}
		pc->pbase = (seqType*)malloc(sizeof(seqType) * (pa->size + pb->size));
		if (pc->pbase == NULL)	// 重新申请pc表空间，申请失败
		{
			return OVERFLOW;
		}
	}
	pc->size = pc->capacity = pa->size + pb->size;
	seqType* p1 = pa->pbase;	// 指向a表基地址
	seqType* p2 = pb->pbase;
	seqType* p3 = pc->pbase;
	seqType* p1_last = pa->pbase + pa->size - 1;	// 指向a表尾元素地址
	seqType* p2_last = pb->pbase + pb->size - 1;
	while (p1 <= p1_last && p2 <= p2_last)	// 合并
	{
		if (*p1 <= *p2)
		{
			*p3++ = *p1++;
		}
		else
		{
			*p3++ = *p2++;
		}
	}
	while (p1 <= p1_last)
	{
		*p3++ = *p1++;
	}// 合并a表剩余部分
	while (p2 <= p2_last)
	{
		*p3++ = *p2++;
	}// 合并b表剩余部分
	return OK;
}

// 题-表pa,pb均为非递增顺序表,表长度分别为m,n，表容量分别为m+n,n
// 求-将2表元素仍按照非递增顺序合并，存放在pa表中，要求不能开辟辅助数组空间
// 解-01、先对pb表求最小值,将最小值与存放在pb[0]
// 解-02、若pb[0]>pa[i],将pb[0]赋值给pa[index],i,index均自增
// 解-02、重复上步，直至index==1，跳出循环
// 解-03、对pb表由小到大排序后，将pb表元素逐个存放至pa[index]

status x02_merge01(mySList* pa, mySList* pb, int m, int n) // 方法一
{
	if (pa == NULL || pb == NULL || pa->pbase == NULL || pb->pbase == NULL)
	{
		return ERROR;
	}
	int i = 0;		// 辅助下标，用于取pa[i]
	while (i < m)
	{
		int j = 1;
		int tmp = 0;
		while (j < n)
		{

			if (pb->pbase[0] > pb->pbase[j])
			{
				tmp = pb->pbase[0];
				pb->pbase[0] = pb->pbase[j];
				pb->pbase[j] = tmp;
			}
			++j;
		}// 循环结束，pb[0]为pb表中的最小值最小值
		if (pa->pbase[i] > pb->pbase[0])
		{
			tmp = pa->pbase[i];
			pa->pbase[i] = pb->pbase[0];
			pb->pbase[0] = tmp;
		}// 取pa[i]与pb[0]中较小者存入pa[i]
		++i;
	}// 循环结束后，pa已由小到大存入了m个元素，此时i值为m

	for (int i = 0; i < n; i++)
	{
		int tmp = 0;
		for (int j = i + 1; j < n; ++j)
		{
			if (pb->pbase[i] > pb->pbase[j])
			{
				tmp = pb->pbase[i];
				pb->pbase[i] = pb->pbase[j];
				pb->pbase[j] = tmp;
			}
		}
	}// 对pb表进行排序

	int j = 0;
	while (j < n)
	{
		pa->pbase[m + j] = pb->pbase[j];
		++j;
	}
	pa->size = m + n;
	return OK;
	//方法2：取pa[i]与pb[0]比较前，先对pb表进行由小到大排序
	//当pa[0]至pa[m-1]填满元素时，将pb表全部元素存放到pa表的剩余空位置
}

// 解-01、分别取pa,pb表的尾元素比较，较大者存放在pa表末位置，pa[index]
status x02_merge02(mySList* pa, mySList* pb, int m, int n) // 方法二
{
	if (pa == NULL || pb == NULL || pa->pbase == NULL || pb->pbase == NULL)
	{
		return ERROR;
	}
	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[index--]=(pa[i]>pb[j]?pa[i--]:pb[j--]);
	while (i < 0 && j>-1)	// pa表原有元素全部处理完成，剩下pb表的未处理
	{
		pa->pbase[index--] = pb->pbase[j--];
	}
	pa->size = m + n;
	return OK;
}