一、定义顺序表结构
#define INIT_SIZE 10 ///< 顺序表初始容量
typedef int seqType; ///< 定义顺序表元素类型
/// @brief 顺序表结构定义
typedef struct t_sqList
{
seqType* pbase; ///< 表基址
int capacity; ///< 表容量
int size; ///< 表长度
}mySList;
二、合并2个非递减顺序表。具体题目与解法如下:
1、题目一
- 给定2个非递减顺序表:pa,pb,
- 再给定一个用于存放合并结果的顺序表:pc
- 要求按元素值由小到大合并,结果存放在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;
}
标签:pbase,顺序,NULL,合并,pb,pc,pa,递减
From: https://www.cnblogs.com/kxwslmsps/p/17121995.html