一、顺序表结构定义
#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;
}
标签:pbase,顺序,--,kx00016,pb,pc,pa,NULL From: https://www.cnblogs.com/kxwslmsps/p/17110311.html