最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

环球热文：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]

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;// 用于遍历paint j = 0;// 用于遍历pbwhile (i < pa->size){// 取pb最小元素存放于pb[0]处while (jsize){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;}

关键词： 空间复杂度