• 【考研】线性表的应用之有序表的合并

    前言

    本文内容源于对《数据结构（C语言版）》（第2版）、王道讲解学习所得心得、笔记整理和总结。

    1、有序表（Order List）：数据元素相互之间可以比较，且数据元素在线性表中依值非递减或非递增有序排列。

    2、有序集合：集合中的元素有序排列。

    求解有序集合的并集问题，考点为有序表的合并，其又可分为顺序有序表的合并、链式有序表的合并。本文以举例子说明此两种合并，部分题目内含多种解法，讲解详细。

    其中，顺序有序表的合并，类似于归并排序算法，所以，可搭配以下链接进行学习：

    【考研】数据结构考点——归并排序_住在阳光的心里的博客-CSDN博客

    【考研】《数据结构》知识点总结.pdf_考研数据结构知识点总结背诵-其它文档类资源-CSDN文库

    目录

    前言

    一、有序表的合并

    （一）顺序有序表的合并

    1、算法步骤

    2、算法代码

    3、算法分析

    （二）链式有序表的合并 

    1、算法步骤

    2、算法代码

    3、算法分析

    二、练习

    （一）解法一：暴力解（数组保存 + 快速排序）

    1、算法思想

    2、算法分析

    3、算法代码

    （二）解法二：较优解（数组保存 + 指针后移归并）

    1、算法思想

    2、算法分析

    3、算法代码

    （三）解法三：最优解（指针后移归并 + 头插法逆置）

    1、算法思想

    2、算法分析

    3、算法代码

    一、有序表的合并

    已知两个有序集合 A = （3，5，8，11），B = （2，6，8，9，11，15，20），数据元素按值非递减有序排列，现要求一个新的集合 C=A\cup B，使集合 C 中的数据元素仍按值非递减有序排列。

    解析：记三个线性表 LA、LB 和 LC分别表示集合 A 、B 和 C，其表长分别为 m 、n 和 m + n 。

    可先假设 LC 为空表，再将 LA 或 LB 中的元素逐个插入 LC 中。

    因为 LC 是按值非递减有序排列，所以可设两个指针 pa 和 pb 分别指向 LA、LB 中的某个元素，若设 pa 、pb 当前所指元素分别为 a 、b，则当前应插入到 LC 中的元素 c 为 c=\left\{\begin{matrix} a & ,a\leq b \\ b & ,a> b \end{matrix}\right.，显然，指针 pa 和 pb 分别指向两个有序表的第一个元素，在所指元素插入 LC 之后，在  LA 或 LB 中顺序后移。

    以下是有序表的顺序存储结构和链式存储结构相应合并算法的实现。

    （一）顺序有序表的合并

    1、算法步骤

    1、创建一个表长为 m + n 的空表 LC。

    2、指针 pc 初始化，指向 LC 的第一个元素。

    3、指针 pa 和 pb 初始化，分别指向 LA 和 LB 的第一个元素。

    4、当指针 pa 和 pb 均未到达相应表尾时，则依次比较 pa 和 pb 所指向的元素值，从 LA 或 LB 中“摘取” 元素值较小的结点插入到 LC 的最后。

    5、如果 pb 已到达 LB 的表尾，依次将 LA 的剩余元素插入 LC 的最后。

    6、如果 pa 已到达 LA 的表尾，依次将 LB 的剩余元素插入 LC 的最后。
     

    2、算法代码

    1. //顺序表的存储结构
    2. typedef struct{
    3.     ElemType *elem;
    4.     int length;
    5. }SqList;
    6.  
    7. //已知顺序有序表 LA 和 LB 的元素按值非递减排列
    8. //归并 LA 和 LB 得到新的顺序有序表 LC, LC 的元素也按值非递减排列
    9. void MergeList_Sq (SqList LA, SqList LB, SqList &LC){
    10.     int m = LA.length, n = LB. length;
    11.     LC.length = m + n;      //新表长度为待合并两表的长度之和
    12.  
    13.     LC.elem = new ElemType[LC.length];      //为合并后的新表分配一个数组空间
    14.     pc = LC.elem;     //指针 pc 指向新表的第1个元素
    15.  
    16.     //指针 pa 和 pb 的初值分别指向两个表的第1个元素
    17.     pa = LA.elem;
    18.     pb = LB.elem;
    19.  
    20.     pa_last = LA.elem + m - 1;    //指针 pa_last 指向 LA 的最后一个元素
    21.     pb_last = LB.elem + n - l;    //指针 pb_last 指向 LB 的最后一个元素
    22.  
    23.     while((pa <= pa_last) && (pb <= pb_last)){     // LA 和 LB 均未到达表尾
    24.         if(*pa <= *pb) *pc++ = *pa++;     //依次“摘取”两表中值较小的结点插入到 LC 的最后
    25.         else *pc++ = *pb++;
    26.     }
    27.  
    28.     while(pa <= pa_last) *pc++ = *pa++;    //LB已到达表尾，依次将 LA 的剩余元素插入 LC 的最后
    29.     while(pb <= pb_last) *pc++ = *pb++;    //LA已到达表尾，依次将 LB 的剩余元素插入 LC 的最后
    30. }

    3、算法分析

    （1）时间复杂度：O(m + n)

    （2）空间复杂度：O(m + n)

    【补充：合并线性表的完整代码，看下方】

    1. //C语言
    2. #include
    3. #include
    4.  
    5. #define MaxSize 10
    6.  
    7. //顺序表的存储结构
    8. typedef struct{
    9.     int *elem;
    10.     int length;
    11. }SqList;
    12.  
    13. //已知顺序有序表 LA 和 LB 的元素按值非递减排列
    14. //归并 LA 和 LB 得到新的顺序有序表 LC, LC 的元素也按值非递减排列
    15. void MergeList_Sq(SqList LA, SqList LB, SqList *LC){
    16.     int m = LA.length, n = LB.length;
    17.     LC->length = m + n;      //新表长度为待合并两表的长度之和
    18.  
    19.     LC->elem = (int*)malloc(MaxSize * sizeof(int));     //为合并后的新表分配一个数组空间
    20.     int *pc = LC->elem;     //指针 pc 指向新表的第1个元素
    21.  
    22.     //指针 pa 和 pb 的初值分别指向两个表的第1个元素
    23.     int *pa = LA.elem;
    24.     int *pb = LB.elem;
    25.  
    26.     int *pa_last = LA.elem + m - 1;    //指针 pa_last 指向 LA 的最后一个元素
    27.     int *pb_last = LB.elem + n - 1;    //指针 pb_last 指向 LB 的最后一个元素
    28.  
    29.     while((pa <= pa_last) && (pb <= pb_last)){     // LA 和 LB 均未到达表尾
    30.         if(*pa <= *pb) *pc++ = *pa++;     //依次“摘取”两表中值较小的结点插入到 LC 的最后
    31.         else *pc++ = *pb++;
    32.     }
    33.  
    34.     while(pa <= pa_last) *pc++ = *pa++;    //LB已到达表尾，依次将 LA 的剩余元素插入 LC 的最后
    35.     while(pb <= pb_last) *pc++ = *pb++;    //LA已到达表尾，依次将 LB 的剩余元素插入 LC 的最后
    36. }
    37.  
    38. //创建顺序表
    39. void initList(SqList* L){
    40.     L->elem = (int*)malloc(MaxSize * sizeof(int));    //构造一个空的顺序表，动态申请存储空间
    41.     
    42.     if (!L->elem){
    43.         printf("初始化失败");
    44.         exit(0);
    45.     }
    46.     L->length = 0;   //空表的长度初始化为0
    47. }
    48.  
    49. //插入函数，其中，e为插入的元素，i为插入到顺序表的位置
    50. void insertList(SqList* L, int i, int e){
    51.     if ((i > L->length + 1) || (i < 1)) {   //i值不合法
    52.         printf("插入位置有问题\n");
    53.         return;
    54.     }
    55.  
    56.     if (MaxSize == L->length) {
    57.     	printf("当前存储空间已满\n");
    58.     	return;
    59.     }
    60.     //插入操作，需要将自插入位置之后的所有元素全部后移一位
    61.     for (int j = L->length - 1; j >= i - 1; j--) {
    62.         L->elem[j + 1] = L->elem[j];
    63.     }
    64.     
    65.     L->elem[i - 1] = e;    //后移完成后，直接插入元素
    66.     L->length++;    //表长加一
    67. }
    68.  
    69. //输出顺序表中的元素
    70. void displayList(SqList L){
    71.     for (int i = 0; i < L.length; i++) {
    72.         printf("%d ", L.elem[i]);
    73.     }
    74.     printf("\n");
    75. }
    76.  
    77. int main(){
    78. 	SqList LA, LB, LC;
    79. 	
    80. 	initList(&LA);
    81. 	initList(&LB);
    82. 	initList(&LC);
    83. 	
    84.     for (int i = 1; i <= MaxSize; i++) {
    85.         LA.elem[i - 1] = i;
    86.         LA.length++;
    87.     }
    88.     
    89.     for (int j = 1; j <= MaxSize; j++) {
    90.         LB.elem[j - 1] = j + 2;
    91.         LB.length++;
    92.     }
    93.     
    94. 	printf("顺序表LA(元素按值非递减排列)：\n");
    95.     displayList(LA);
    96.     
    97.     printf("顺序表LB(元素按值非递减排列)：\n");
    98.     displayList(LB);
    99.     
    100.     printf("归并 LA 和 LB 得到新的顺序有序表 LC：\n");
    101. 	MergeList_Sq(LA, LB, &LC);
    102. 	displayList(LC);
    103. }

    运行结果如下：

     

    （二）链式有序表的合并 

    1、算法步骤

    1、指针 pa 和 pb 初始化，分别指向 LA 和 LB 的第一个结点。

    2、LC 的结点取值为 LA 的头结点。

    3、指针 pc 初始化，指向 LC 的头结点。

    4、当指针 pa 和 pb 均未到达相应表尾时，则依次比较 pa 和 pb 所指向的元素值，从 LA 或 LB 中“摘取”元素值较小的结点插人到LC的最后。

    5、将非空表的剩余段插入到 pc 所指结点之后。

    6、释放 LB 的头结点。

    2、算法代码

    1. //已知单链表 LA 和 LB 的元素按值非递减排列
    2. //归并 LA 和 LB 得到新的单链表 LC, LC 的元素也按值非递减排列
    3. void MergeList_L(LinkList &LA, LinkList &LB, LinkList &LC){
    4.     //pa 和 pb 的初值分别指向两个表的第一个结点
    5.     pa = LA->next; 
    6.     pb = LB->next;
    7.  
    8.     LC = LA;      //用 LA 的头结点作为 LC 的头结点
    9.     pc = LC;     //pc 的初值指向 LC 的头结点
    10.  
    11.     while (pa && pb){    //LA和LB均未到达表尾，依次“摘取”两表中值较小的结点插入到 LC 的最后
    12.         if (pa->data <= pb->data){    //“摘取” pa 所指结点
    13.             pc->next = pa;     //将 pa 所指结点链接到 pc 所指结点之后
    14.             pc = pa;    //pc 指向 pa
    15.             pa = pa->next;    //pa 指向下一结点
    16.         }
    17.         else{    //“摘取” pb 所指结点
    18.             pc->next = pb;      //将 pb 所指结点链接到 pc 所指结点之后
    19.             pc = pb;     //pc 指向 pb
    20.             pb = pb->next;    //pb 指向下一结点
    21.         }
    22.     }
    23.  
    24.     pc->next = pa?pa:pb;    //将非空表的剩余段插入到 pc 所指结点之后
    25.     delete LB;      //释放 LB 的头结点
    26. }

    3、算法分析

    （1）时间复杂度：O(m + n)

    （2）空间复杂度：O(1)

    二、练习

    有两个带头节点的降序单链表 L1、L2，较长的链表元素个数为 n。链表结点定义如下所示。请设计一个时间上尽可能高效算法，按升序输出两个链表中所有元素的权值。

    1. typedef struct LinkNode {
    2.     double data;      //权值
    3.     struct LinkNode *next;      //指向单链表的下一个结点
    4. } LinkNode, *Linklist;

    （一）解法一：暴力解（数组保存 + 快速排序）

    1、算法思想

    将两个链表存入数组A中，通过对数组A进行快速排序，再从后到前升序输出数组。

    2、算法分析

    时间复杂度为 O(nlog_2n)，空间复杂度为 O(n)。

    3、算法代码

    1. void Qsort(double A[], int L, int R){    //a 数组保存数据，L 和 R 是边界
    2.     if (L >= R) return;    //当前区间元素个数 <= 1 ，则退出
    3.     int pivot, i = L, j = R;     //i 和 j 是左右两个数组下标移动
    4.     swap(A[L], A[m]);      //A[m]是在 A[L~R]之间随机选取的一个元素（快排优化）
    5.     pivot = A[L];     //pivot 作为枢值参与比较
    6.  
    7.     while (i
    8.         while (i < j && A[j] > pivot) j--;
    9.         while (i < j && A[i] <= pivot) i++;
    10.         if (i < j) swap(A[i], A[j]);      //交换 A[i] 和 A[j]
    11.     }
    12.     swap(A[L], A[i]);
    13.     Qsort(A, L, i-1);     //递归处理左区间
    14.     Qsort(A, i+1, R);     //递归处理右区间
    15. }
    16.  
    17. void ans(Linklist L1, L2){
    18.     double A[maxn];
    19.     int t = 0;     // t 是新数组中元素个数
    20.  
    21.     Linklist p = L1->next;     //p 指向 L1 链表的第一个元素
    22.     while (p != null){      //链表 L1 转数组保存
    23.         A[t++] = p->data;
    24.         p = p->next;
    25.     }
    26.  
    27.     Linklist q = L2->next;     //q 指向 L2 链表的第一个元素
    28.     while (q != null){     //链表 L2 转数组保存
    29.         A[t++] = q->data；
    30.         q = q->next;
    31.     }
    32.  
    33.     Qsort(A, 0, t-1);
    34.     for(int i = t - 1; i >= 0; i--){  //数组从后到前升序输出
    35.         cout<", ";
    36.     }
    37. }

    （二）解法二：较优解（数组保存 + 指针后移归并）

    1、算法思想

    将两链表归并存入数组得到降序数组，然后从后到前升序输出数组。

    2、算法分析

    时间复杂度为 O(n)，空间复杂度为 O(n)。

    3、算法代码

    1. void ans(Linklist L1, L2){
    2.     double A[maxn];
    3.     int t = 0;    //t 是新数组中元素个数
    4.     Linklist p = L1->next;   //p 指向 L1 链表的第一个元素
    5.     Linklist q = L2->next;   //q 指向 L2 链表的第一个元素
    6.  
    7.     while (p!= null && q != null) //归并两个降序链表，每次选较大元素
    8.     if (p->data > q->data){
    9.         A[t++] = p->data;
    10.         p = p->next;
    11.     }
    12.     else{
    13.         A[t++]=q->data;
    14.         q=q->next;
    15.     }
    16.  
    17.     while (p != null){     //如果 L1 链表中有剩余元素则放在数组末尾
    18.         A[t++] = p->data;
    19.         p = p->next;
    20.     }
    21.     while (q != null){     //如果 L2 链表中有剩余元素则放在数组末尾
    22.         A[t++] = q->data;
    23.         q = q->next;
    24.     }
    25.     for (int i = t-1; i >= 0; i--)
    26.         cout << A[i] << ",";    //数组从后到前升序输出
    27. }

    （三）解法三：最优解（指针后移归并 + 头插法逆置）

    1、算法思想

    将两链表归并到链表 L3 中，归并时采用头插法（输入顺序与线性表中的逻辑顺序是相反的），得到的降序链表 L3，依次输 出链表中的元素。

    2、算法分析

    时间复杂度为 ​​​​​​​O(n)，空间复杂度为 O(1)。

    3、算法代码

    1. typedef struct LinkNode {
    2.     double data;      //权值
    3.     struct LinkNode *next;      //指向单链表的下一个结点
    4. } LinkNode, *Linklist;
    5.  
    6.  
    7. LinkNode L3; //定义全局变量 L3
    8. Linklist Head_Insert(Linklist p){    //头插法插入 L3 中
    9.     Linklist p1 = p->next;
    10.     p->next = L3->next;
    11.     L3->next = p;
    12.     p = p1;
    13.     return p;
    14. }
    15.  
    16. void ans(Linklist L1, L2){
    17.     int t = 0; //t 是新数组中元素个数
    18.     Linklist p = L1->next;    //p 指向 L1 链表的第一个元素
    19.     Linklist q = L2->next;    //q 指向 L2 链表的第一个元素
    20.     L3->next = null;    //初始链表 L3 为空
    21.  
    22.     while (p != null && q != null){    //归并两个降序链表，每次选较大元素
    23.         if (p->data > q->data)
    24.             p = Head_Insert(p);    //将 p 头插法插入 L3 中，p 指向下一个结点
    25.         else
    26.             q = Head_Insert(q);    //将 q 头插法插入 L3 中，q 指向下一个结点
    27.     }
    28.  
    29.     while (p != null){    //如果 L1 链表中有剩余元素则头插法插入 L3
    30.         p = Head_Insert(p);     //将 p 头插法插入 L3 中，p 指向下一个结点
    31.  
    32.     while (q != null)     //如果 L2 链表中有剩余元素则头插法插入 L3
    33.         q = Head_Insert(q);     //将 q 头插法插入 L3 中，q 指向下一个结点
    34.  
    35.     p = L3->next;
    36.  
    37.     while (p != null){      //依次输出链表 L3 中的元素
    38.         cout << p->data;
    39.          p=p->next;
    40.     }
    41. }

  • 相关阅读:
    RT-Thread Hoist_Motor PID
    Web攻防--Java_SQL注入--XXE注入-- SSTI模板注入--SPEL表达式注入
    Java之JvisualVM简介
    idea 基础设置
    云上攻防--云原生&&Docker逃逸--特权逃逸--危险挂载--漏洞逃逸
    AWS无服务器 应用程序开发—第十一章API Gateway
    Spring Cloud Alibaba+saas企业架构技术选型+架构全景业务图 + 架构典型部署方案
    Unity实现方圆X范围随机生成怪物
    TDengine 3.0 重磅发布，首届开发者大会圆满结束
    【自动驾驶】自动驾驶感知系统与关键技术介绍
  • 原文地址：https://blog.csdn.net/qq_34438969/article/details/126544665