备案控制台
开发者社区 云计算 文章 正文

两个有序表的合并（三种方法）

2023-02-01 714
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 设有两个递增排列的有序表，要求合并后仍按递增（非递减）有序排列

一、顺序表

利用顺序存储结构合并有序表， 需要依次从两个有序表中取出一个元素进行比较，将较小的元素放入第三个表中，最后输出第三个表，就是合并后的有序表了。

1.1 初始化顺序表

int Init_List(PList L){
    L->data=(int *)malloc(sizeof(int)*SIZE);   //初始化动态分配内存
    L->len=0;      //初始化表长为空
    L->size=SIZE;
    return 1;
}

1.2 创建顺序表

int Creat_List(PList L){
    int e,i=0;
    while(scanf("%d",&e)==1){
        if(L->len>=L->size){     //当前顺序表超长时要重新分配空间
            L->data=(int *)realloc(L->data,(L->size+INCREAM)*sizeof(int));
            L->size+=INCREAM;
        }
        L->data[i++]=e;
        L->len++;
    }
    return 1;
}

1.3 合并两个有序表

int Connect_List(PList L1,PList L2,PList L3){
    int i=0,j=0,k=0;
    if(L1->len+L2->len>L3->size){    //合并有序表要先判断两者长度和是否大于第三个表
        L3->data=(int *)realloc(L3->data,(L3->size+INCREAM)*sizeof(int));
        L3->size+=INCREAM;
    }
    while(i<L1->len&&j<L2->len){     //循环判断
        if(L1->data[i]==L2->data[j]){
            j++;    
        }else if(L1->data[i]<L2->data[j]){    //将较小元素放入第三个顺序表
            L3->data[k++]=L1->data[i++];
        }else{
            L3->data[k++]=L2->data[j++];
        }
    }
    while(i<L1->len){              //将另一个未空的顺序表剩余元素放入第三个顺序表
        L3->data[k++]=L1->data[i++];    
    }
    while(j<L2->len){
        L3->data[k++]=L2->data[j++];
    }
    L3->len=k;     //最后别忘了第三个顺序表的长度
    return 1;
}

1.4 完整代码

#include<stdio.h>
#include<malloc.h>
#define SIZE 10
#define INCREAM 10
typedef struct List{
    int *data;
    int len;
    int size;
}List,*PList;
int Init_List(PList L){
    L->data=(int *)malloc(sizeof(int)*SIZE);
    L->len=0;
    L->size=SIZE;
    return 1;
}
int Creat_List(PList L){
    int e,i=0;
    while(scanf("%d",&e)==1){
        if(L->len>=L->size){
            L->data=(int *)realloc(L->data,(L->size+INCREAM)*sizeof(int));
            L->size+=INCREAM;
        }
        L->data[i++]=e;
        L->len++;
    }
    return 1;
}
int Print_List(PList L){
    int i;
    for(i=0;i<L->len;i++){
        printf("%d ",L->data[i]);
    }
    printf("\n");
    return 1;
}
int Connect_List(PList L1,PList L2,PList L3){
    int i=0,j=0,k=0;
    if(L1->len+L2->len>L3->size){
        L3->data=(int *)realloc(L3->data,(L3->size+INCREAM)*sizeof(int));
        L3->size+=INCREAM;
    }
    while(i<L1->len&&j<L2->len){
        if(L1->data[i]==L2->data[j]){
            j++;    
        }else if(L1->data[i]<L2->data[j]){
            L3->data[k++]=L1->data[i++];
        }else{
            L3->data[k++]=L2->data[j++];
        }
    }
    while(i<L1->len){
        L3->data[k++]=L1->data[i++];
    }
    while(j<L2->len){
        L3->data[k++]=L2->data[j++];
    }
    L3->len=k;
    return 1;
}
int main(){
    List L1,L2,L3;
    Init_List(&L1);
    Init_List(&L2);
    Init_List(&L3);
    Creat_List(&L1);
    getchar();
    Creat_List(&L2);
    Connect_List(&L1,&L2,&L3);
    Print_List(&L3);
    return 0;
}

二、单链表

用单链表合并两个有序表，我们有两种方法，一种是带头结点的单链表，另一个是不带头结点的单链表

2.1 不带头结点的单链表

运用不带头结点单链表时，我们需要先找到两个有序表中首元素较小的有序表，然后将它给第三个表，作为第三个表的首元素，在执行接下来的判断

2.1.1 初始化不带头结点的单链表

PNode Init1_Node(){
    PNode head;
    head=NULL;     //初始置头结点为空
    return head;
}

2.1.2 创建不带头结点的单链表

int Creat1_Node(PNode *head){
    int e;
    PNode Last;
    while(scanf("%d",&e)==1){
        PNode Pnew=(PNode)malloc(sizeof(Node));
        Pnew->data=e;
        Pnew->next=NULL;
        if(*head==NULL){    //判断头结点是否为空
            *head=Pnew;        //不带头结点单链表的创建具体见我的专栏
            Last=Pnew;     
        }else{
            Last->next=Pnew;
            Last=Pnew;
        }
    }
    return 1;
}

2.1.3 合并两个有序表

PNode Connect1_Node(PNode p,PNode q){
    PNode r;
    if(p->data<q->data){     //首先要找到首元素较小的，使r的首元素为这个较小元素
        r=p;                                     
        p=p->next;
    }else if(p->data<q->data){
        r=q;
        q=q->next;
    }else{
        r=p;
        p=p->next;
        q=q->next;
    }
    while(p&&q){           //然后一直循环，直到其中一个单链表为空
        if(p->data<q->data){       //将较小的元素插入r后面
            r->next=p;
            r=p;
            p=p->next;
        }else if(p->data>q->data){   
            r->next=q;
            r=q;
            q=q->next;
        }else{          //当两者相等时，我们直接跳过即可
            q=q->next;
        }
    }
    if(p) r->next=p;    //最后将另一个还有元素的单链表连接到r后面
    if(q) r->next=q;
    return r;
}

2.2 带头结点的单链表

运用带头结点的单链表合并有序表，我们直接进行判断，将较小的元素插入第三个表的表尾

2.2.1 初始化带头结点的单链表

PNode Init2_Node(){
    PNode head=(PNode)malloc(sizeof(Node));    //初始化一个头结点
    head->next=NULL;
    return head;
}

2.2.2 创建带头结点的单链表

int Creat2_Node(PNode head){
    PNode p=head;
    int e;
    while(scanf("%d",&e)==1){ 
        PNode Pnew=(PNode)malloc(sizeof(Node));    //具体见专栏 
        Pnew->data=e;
        p->next=Pnew;
        p=Pnew; 
    }
    p->next=NULL;
    return 1;
}

2.2.3 合并两个有序表

int Connect2_Node(PNode head1,PNode head2){
    PNode head3,p,q,r;
    p=head1->next;
    q=head2->next;
    r=Init2_Node();
    while(p&&q){          //思路其实和顺序表，不带头结点单链表的思路一样，就是这里
        if(p->data<q->data){      //不用管两个链表中哪个首元素较小，因为
            r->next=p;            //我们的头结点没有值
            r=p;  
            p=p->next;             //其他和不带头结点单链表方法一样
        }else if(p->data>q->data){
            r->next=q;
            r=q;
            q=q->next;
        }else{
            q=q->next;
        }
    }
    if(p) r->next=p;
    if(q) r->next=q;
    return 1;
}

2.3 完整代码

#include<stdio.h>
#include<malloc.h>
typedef struct Node{
    int data;
    struct Node *next;
}Node,*PNode;
PNode Init1_Node(){
    PNode head;
    head=NULL;
    return head;
}
PNode Init2_Node(){
    PNode head=(PNode)malloc(sizeof(Node));
    head->next=NULL;
    return head;
}
int Creat1_Node(PNode *head){
    int e;
    PNode Last;
    while(scanf("%d",&e)==1){
        PNode Pnew=(PNode)malloc(sizeof(Node));
        Pnew->data=e;
        Pnew->next=NULL;
        if(*head==NULL){
            *head=Pnew;
            Last=Pnew;
        }else{
            Last->next=Pnew;
            Last=Pnew;
        }
    }
    return 1;
}
int Creat2_Node(PNode head){
    PNode p=head;
    int e;
    while(scanf("%d",&e)==1){
        PNode Pnew=(PNode)malloc(sizeof(Node));
        Pnew->data=e;
        p->next=Pnew;
        p=Pnew; 
    }
    p->next=NULL;
    return 1;
}
int Print1_Node(PNode head){
    while(head){
        printf("%d ",head->data);
        head=head->next;
    }
    printf("\n");
}
int Print2_Node(PNode head){
    PNode p=head->next;
    while(p){
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
    return 1;
}
PNode Connect1_Node(PNode p,PNode q){
    PNode r;
    if(p->data<q->data){
        r=p;
        p=p->next;
    }else if(p->data<q->data){
        r=q;
        q=q->next;
    }else{
        r=p;
        p=p->next;
        q=q->next;
    }
    while(p&&q){
        if(p->data<q->data){
            r->next=p;
            r=p;
            p=p->next;
        }else if(p->data>q->data){
            r->next=q;
            r=q;
            q=q->next;
        }else{
            q=q->next;
        }
    }
    if(p) r->next=p;
    if(q) r->next=q;
    return r;
}
int Connect2_Node(PNode head1,PNode head2){
    PNode head3,p,q,r;
    p=head1->next;
    q=head2->next;
    r=Init2_Node();
    while(p&&q){
        if(p->data<q->data){
            r->next=p;
            r=p;
            p=p->next;
        }else if(p->data>q->data){
            r->next=q;
            r=q;
            q=q->next;
        }else{
            q=q->next;
        }
    }
    if(p) r->next=p;
    if(q) r->next=q;
    return 1;
}
int main(){
    PNode p,q;
    p=Init2_Node();
    Creat2_Node(p);
    getchar();
    q=Init2_Node();
    Creat2_Node(q);
    Connect2_Node(p,q);
    Print2_Node(p);
    return 0;
}

三、运行结果

1.png

文章标签：
存储
Want595
目录
相关文章
干饭小白
|
6月前
|
Linux C++
合并k个已排序的链表
合并k个已排序的链表
干饭小白
17 0
风水道人
|
2月前
|
算法
合并两个有序链表
合并两个有序链表
风水道人
13 0
极客李华
|
4月前
|
存储 C++
合并两个有序数组(C++)
合并两个有序数组(C++)
极客李华
43 0
人不走空
|
4月前
|
算法 Java
算法题 合并两个有序数组
算法题 合并两个有序数组
人不走空
14 1
春人.
|
9月前
|
C++
【C/C++练习】合并k个已排序的链表（一）
【C/C++练习】合并k个已排序的链表（一）
春人.
49 0
小米睡不醒
|
6月前
|
C++
合并有序链表C++递归
合并有序链表C++递归
小米睡不醒
34 0
春人.
|
9月前
|
C++
【C/C++练习】合并k个已排序的链表（二）
【C/C++练习】合并k个已排序的链表（二）
春人.
62 0
【C/C++练习】合并k个已排序的链表（二）
Trouble..
|
9月前
|
存储 搜索推荐
合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
Trouble..
44 0
真题OK撒
|
12月前
|
存储
6-1 两个有序链表序列的合并
6-1 两个有序链表序列的合并
真题OK撒
84 0
真题OK撒
|
12月前
7-174 两个有序链表序列的合并
7-174 两个有序链表序列的合并
真题OK撒
48 0

热门文章

最新文章

  • 1
    企业应用架构实践（复杂性应对之道）
  • 2
    SolidWorks2021中文版【Solid Works 附补丁】完美破解版下载 安装教程
  • 3
    3+1保障：高可用系统稳定性是如何炼成的？
  • 4
    大数据上手实战！《Elasticsearch 实战进阶营》第二季限时免费报名啦
  • 5
    OLAP与OLTP介绍
  • 6
    浅显易懂的机器学习（八）—— 随机森林分类
  • 7
    Windows 2008 AD 备份
  • 8
    《Ext JS权威指南》——2.9节为本书示例准备一个模板
  • 9
    NS2原理
  • 10
    Asp.net MVC2.0系列文章-显示列表和详细页面操作
  • 1
    Java中数组详解
    41
  • 2
    智能评估时代：SurveyKing开源问卷系统YYDS
    63
  • 3
    LabVIEW编程LabVIEW开发高级数据采集技术 操作数字IO 例程与相关资料
    37
  • 4
    【大模型】描述与 LLM 相关的个人项目或感兴趣的领域
    37
  • 5
    【大模型】使用哪些资源来了解 LLM 的最新进展？
    47
  • 6
    LabVIEW编程LabVIEW开发高级数据采集技术 计数器定时器的操作 例程与相关资料
    25
  • 7
    LabVIEW编程LabVIEW开发高级数据采集技术 模拟波形的生成 例程与相关资料
    23
  • 8
    Linux：进程等待 & 进程替换
    27
  • 9
    LabVIEW编程LabVIEW开发高级数据采集技术 同步 例程与相关资料
    19
  • 10
    LabVIEW编程LabVIEW开发高级数据采集技术定时与触发 例程与相关资料
    18

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）