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

本文内容源于对《（C语言版）》（第2版）、王道讲解学习所得心得、笔记整理和总结。1、有序表（Order List）：数据元素相互之间可以比较，且数据元素在线性表中依值非递减或非递增有序排列。2、有序集合：集合中的元素有序排列。求解有序集合的并集问题，考点为有序表的合并，其又可分为顺序有序表的合并、链式有序表的合并。本文以举例子说明此两种合并，部分题目内含多种解法，讲解详细。...

住在阳光的心里

4247人浏览 · 2022-08-26 17:14:28

住在阳光的心里 · 2022-08-26 17:14:28 发布

前言

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

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

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

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

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

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

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

一、有序表的合并

已知两个有序集合 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、算法代码

//顺序表的存储结构
typedef struct{
    ElemType *elem;
    int length;
}SqList;

//已知顺序有序表 LA 和 LB 的元素按值非递减排列
//归并 LA 和 LB 得到新的顺序有序表 LC, LC 的元素也按值非递减排列
void MergeList_Sq (SqList LA, SqList LB, SqList &LC){
    int m = LA.length, n = LB. length;
    LC.length = m + n;      //新表长度为待合并两表的长度之和

    LC.elem = new ElemType[LC.length];      //为合并后的新表分配一个数组空间
    pc = LC.elem;     //指针 pc 指向新表的第1个元素

    //指针 pa 和 pb 的初值分别指向两个表的第1个元素
    pa = LA.elem;
    pb = LB.elem;

    pa_last = LA.elem + m - 1;    //指针 pa_last 指向 LA 的最后一个元素
    pb_last = LB.elem + n - l;    //指针 pb_last 指向 LB 的最后一个元素

    while((pa <= pa_last) && (pb <= pb_last)){     // LA 和 LB 均未到达表尾
        if(*pa <= *pb) *pc++ = *pa++;     //依次“摘取”两表中值较小的结点插入到 LC 的最后
        else *pc++ = *pb++;
    }

    while(pa <= pa_last) *pc++ = *pa++;    //LB已到达表尾，依次将 LA 的剩余元素插入 LC 的最后
    while(pb <= pb_last) *pc++ = *pb++;    //LA已到达表尾，依次将 LB 的剩余元素插入 LC 的最后
}

3、算法分析

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

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

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

//C语言
#include<stdio.h>
#include<stdlib.h>

#define MaxSize 10

//顺序表的存储结构
typedef struct{
    int *elem;
    int length;
}SqList;
 
//已知顺序有序表 LA 和 LB 的元素按值非递减排列
//归并 LA 和 LB 得到新的顺序有序表 LC, LC 的元素也按值非递减排列
void MergeList_Sq(SqList LA, SqList LB, SqList *LC){
    int m = LA.length, n = LB.length;
    LC->length = m + n;      //新表长度为待合并两表的长度之和
 
    LC->elem = (int*)malloc(MaxSize * sizeof(int));     //为合并后的新表分配一个数组空间
    int *pc = LC->elem;     //指针 pc 指向新表的第1个元素
 
    //指针 pa 和 pb 的初值分别指向两个表的第1个元素
    int *pa = LA.elem;
    int *pb = LB.elem;
 
    int *pa_last = LA.elem + m - 1;    //指针 pa_last 指向 LA 的最后一个元素
    int *pb_last = LB.elem + n - 1;    //指针 pb_last 指向 LB 的最后一个元素
 
    while((pa <= pa_last) && (pb <= pb_last)){     // LA 和 LB 均未到达表尾
        if(*pa <= *pb) *pc++ = *pa++;     //依次“摘取”两表中值较小的结点插入到 LC 的最后
        else *pc++ = *pb++;
    }
 
    while(pa <= pa_last) *pc++ = *pa++;    //LB已到达表尾，依次将 LA 的剩余元素插入 LC 的最后
    while(pb <= pb_last) *pc++ = *pb++;    //LA已到达表尾，依次将 LB 的剩余元素插入 LC 的最后
}

//创建顺序表
void initList(SqList* L){
    L->elem = (int*)malloc(MaxSize * sizeof(int));    //构造一个空的顺序表，动态申请存储空间
    
    if (!L->elem){
        printf("初始化失败");
        exit(0);
    }
    L->length = 0;   //空表的长度初始化为0
}

//插入函数，其中，e为插入的元素，i为插入到顺序表的位置
void insertList(SqList* L, int i, int e){
    if ((i > L->length + 1) || (i < 1)) {   //i值不合法
        printf("插入位置有问题\n");
        return;
    }

    if (MaxSize == L->length) {
    	printf("当前存储空间已满\n");
    	return;
    }
    //插入操作，需要将自插入位置之后的所有元素全部后移一位
    for (int j = L->length - 1; j >= i - 1; j--) {
        L->elem[j + 1] = L->elem[j];
    }
    
    L->elem[i - 1] = e;    //后移完成后，直接插入元素
    L->length++;    //表长加一
}

//输出顺序表中的元素
void displayList(SqList L){
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.elem[i]);
    }
    printf("\n");
}

int main(){
	SqList LA, LB, LC;
	
	initList(&LA);
	initList(&LB);
	initList(&LC);
	
    for (int i = 1; i <= MaxSize; i++) {
        LA.elem[i - 1] = i;
        LA.length++;
    }
    
    for (int j = 1; j <= MaxSize; j++) {
        LB.elem[j - 1] = j + 2;
        LB.length++;
    }
    
	printf("顺序表LA(元素按值非递减排列)：\n");
    displayList(LA);
    
    printf("顺序表LB(元素按值非递减排列)：\n");
    displayList(LB);
    
    printf("归并 LA 和 LB 得到新的顺序有序表 LC：\n");
	MergeList_Sq(LA, LB, &LC);
	displayList(LC);
}

运行结果如下：

（二）链式有序表的合并

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、算法代码

//已知单链表 LA 和 LB 的元素按值非递减排列
//归并 LA 和 LB 得到新的单链表 LC, LC 的元素也按值非递减排列
void MergeList_L(LinkList &LA, LinkList &LB, LinkList &LC){
    //pa 和 pb 的初值分别指向两个表的第一个结点
    pa = LA->next; 
    pb = LB->next;

    LC = LA;      //用 LA 的头结点作为 LC 的头结点
    pc = LC;     //pc 的初值指向 LC 的头结点

    while (pa && pb){    //LA和LB均未到达表尾，依次“摘取”两表中值较小的结点插入到 LC 的最后
        if (pa->data <= pb->data){    //“摘取” pa 所指结点
            pc->next = pa;     //将 pa 所指结点链接到 pc 所指结点之后
            pc = pa;    //pc 指向 pa
            pa = pa->next;    //pa 指向下一结点
        }
        else{    //“摘取” pb 所指结点
            pc->next = pb;      //将 pb 所指结点链接到 pc 所指结点之后
            pc = pb;     //pc 指向 pb
            pb = pb->next;    //pb 指向下一结点
        }
    }

    pc->next = pa?pa:pb;    //将非空表的剩余段插入到 pc 所指结点之后
    delete LB;      //释放 LB 的头结点
}

3、算法分析

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

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

二、练习

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

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

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

1、算法思想

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

2、算法分析

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

3、算法代码

void Qsort(double A[], int L, int R){    //a 数组保存数据，L 和 R 是边界
    if (L >= R) return;    //当前区间元素个数 <= 1 ，则退出
    int pivot, i = L, j = R;     //i 和 j 是左右两个数组下标移动
    swap(A[L], A[m]);      //A[m]是在 A[L~R]之间随机选取的一个元素（快排优化）
    pivot = A[L];     //pivot 作为枢值参与比较

    while (i<j){
        while (i < j && A[j] > pivot) j--;
        while (i < j && A[i] <= pivot) i++;
        if (i < j) swap(A[i], A[j]);      //交换 A[i] 和 A[j]
    }
    swap(A[L], A[i]);
    Qsort(A, L, i-1);     //递归处理左区间
    Qsort(A, i+1, R);     //递归处理右区间
}

void ans(Linklist L1, L2){
    double A[maxn];
    int t = 0;     // t 是新数组中元素个数

    Linklist p = L1->next;     //p 指向 L1 链表的第一个元素
    while (p != null){      //链表 L1 转数组保存
        A[t++] = p->data;
        p = p->next;
    }

    Linklist q = L2->next;     //q 指向 L2 链表的第一个元素
    while (q != null){     //链表 L2 转数组保存
        A[t++] = q->data；
        q = q->next;
    }

    Qsort(A, 0, t-1);
    for(int i = t - 1; i >= 0; i--){  //数组从后到前升序输出
        cout<<A[i]<<", ";
    }
}

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

1、算法思想

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

2、算法分析

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

3、算法代码

void ans(Linklist L1, L2){
    double A[maxn];
    int t = 0;    //t 是新数组中元素个数
    Linklist p = L1->next;   //p 指向 L1 链表的第一个元素
    Linklist q = L2->next;   //q 指向 L2 链表的第一个元素

    while (p!= null && q != null) //归并两个降序链表，每次选较大元素
    if (p->data > q->data){
        A[t++] = p->data;
        p = p->next;
    }
    else{
        A[t++]=q->data;
        q=q->next;
    }

    while (p != null){     //如果 L1 链表中有剩余元素则放在数组末尾
        A[t++] = p->data;
        p = p->next;
    }
    while (q != null){     //如果 L2 链表中有剩余元素则放在数组末尾
        A[t++] = q->data;
        q = q->next;
    }
    for (int i = t-1; i >= 0; i--)
        cout << A[i] << ",";    //数组从后到前升序输出
}

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

1、算法思想

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

2、算法分析

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

3、算法代码

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


LinkNode L3; //定义全局变量 L3
Linklist Head_Insert(Linklist p){    //头插法插入 L3 中
    Linklist p1 = p->next;
    p->next = L3->next;
    L3->next = p;
    p = p1;
    return p;
}

void ans(Linklist L1, L2){
    int t = 0; //t 是新数组中元素个数
    Linklist p = L1->next;    //p 指向 L1 链表的第一个元素
    Linklist q = L2->next;    //q 指向 L2 链表的第一个元素
    L3->next = null;    //初始链表 L3 为空

    while (p != null && q != null){    //归并两个降序链表，每次选较大元素
        if (p->data > q->data)
            p = Head_Insert(p);    //将 p 头插法插入 L3 中，p 指向下一个结点
        else
            q = Head_Insert(q);    //将 q 头插法插入 L3 中，q 指向下一个结点
    }

    while (p != null){    //如果 L1 链表中有剩余元素则头插法插入 L3
        p = Head_Insert(p);     //将 p 头插法插入 L3 中，p 指向下一个结点

    while (q != null)     //如果 L2 链表中有剩余元素则头插法插入 L3
        q = Head_Insert(q);     //将 q 头插法插入 L3 中，q 指向下一个结点

    p = L3->next;

    while (p != null){      //依次输出链表 L3 中的元素
        cout << p->data;
         p=p->next;
    }
}

更专业、系统、实战的高性能计算学习资源地

汇聚原天河团队并行计算工程师、中科院计算所专家以及头部AI名企HPC专家，助力解决“卡脖子”问题

更多推荐

计算机广东考研大学排名,广东省最值得考研的8所大学

本文由木哥原创，欢迎转载分享，转载须注明来自百家号“木哥说教”！今日话题：广东省最值得大家考研的8所大学！广东省虽然不是中国好大学最多的省份，但是却是很多名校毕业生最想去的地方，俗话说北上广深，广东就占据两位，足以看得出来广东是非常受大学生欢迎的一个城市，其实广东也有很多好的大学，对于一些想考研的学生也可以参考一下，木哥给大家梳理了8所比较不错的大学出来了，希望能帮到大家。第一所大学：中山大学又叫

高性能计算社区

【考研英语】词汇积累（详细全面，2023最新版）

缺课miss a class、旷课cut a class、辍学drop out、退学quit school、助学金assistantship、奖学金scholarship。老人the elderly、the old、the aged、the senior、aged parents、the old and infirm parents。只有only、nothing but、merely、大约abou

高性能计算社区

计算机类专业学习难度排行,全国33所名校计算机专业考研跨考难度系数排名

计算机系统结构前20名(总共47所高校)1.清华大学，2.华中科技大学，3.西安交通大学，4.上海交通大学，5.浙江大学，6.西安电子科技大学，7.武汉大学，8.复旦大学，9.哈尔滨工业大学，10.东北大学，11.北京大学，12.东南大学，13.北京航空航天大学，14.中国科学技术大学，15.电子科技大学，16.吉林大学，17.南京理工大学，18.重庆大学，19.北京科技大学，20.同济大学计算机