kx00016-顺序表--用C语言实现：多种方法合并2个非递减顺序表

一、顺序表结构定义

#define INIT_SIZE 10			// 顺序表初始容量
typedef void(myOpFunType)(void*);	// 定义操作函数类型
typedef int seqType;			// 定义顺序表元素类型

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

二、题目：合并2个非递减顺序表

  1、给定2个非递减顺序表pa,pb，再给一个pc表

  2、要求从小到大合并，合并结果存放于pc表

/**
***********************************************************************
* @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 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 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个非递减顺序表

  1、给定2个非递减顺序表pa，pb，其长度分别为m，n，表容量分别是m+n，n

  2、要求将2表按元素值从小到大合并，且要求不能额外开辟辅助的数组空间，即空间复杂度为O(1)

  3、合并结果存放于表pa中

解法一：

  1、逐个比较pa，pb表尾元素，取较大者依次存放于表pa[index]位置

  2、初始值：index=m+n-1，，pa[index]，每存放一个值，index减1

/**
***********************************************************************
* @brief 功能：合并2顺序表，结果存放于第3顺序表，要求不能开辟额外数组空间 \n
* @param[in] pb：顺序表pb，其长度为n，容量为n
* @param[in] pa：顺序表pa，其长度为m，容量为m+n，结果存放于pa
* @retval OK(1)：合并成功
* @retval ERROR(0)：顺序表不存在，合并失败
* @retval OVERFLOW(-2)：合并失败
***********************************************************************
*/
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;
}

方法二：

  1、取pb表中最小元素存放于pb[0]，与pa表元素逐个比较，若pb[0]<pa[i]，则交换2者，

  2、重复1步骤，直至比较完a表所有元素。此时pa表已存放了m(m为pa表长度)个元素

  3、对pb表进行由小到大排序，然后将pb所有元素依次拷贝追加至表pa表尾。

  4、上述交换2表对应 下标处元素，可先提前定义好一个交换函数。方便编写代码

/**
***********************************************************************
* @brief 功能：交换2数组对应下标i,j处元素 \n
***********************************************************************
*/
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顺序表，结果存放于第3顺序表，要求不能开辟额外数组空间 \n
* @param[in] pb：顺序表pb，其长度为n，容量为n
* @param[in] pa：顺序表pa，其长度为m，容量为m+n，结果存放于pa
* @retval OK(1)：合并成功
* @retval ERROR(0)：顺序表不存在，合并失败
* @retval OVERFLOW(-2)：合并失败
***********************************************************************
*/
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;
}