非递减有序集合合并-链表

港控/mmm° 2023-06-19 15:26 9阅读 0赞

## 非递减有序集合合并 ##

巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。

输入  
三行，第一行A,B集合的个数n,m  
第二行：集合A的数据；  
第三行：集合B的数据。

输出  
二行，第一行，集合C的个数k  
第二行：集合C的数据。

样例输入  
11 12  
2 4 6 7 8 9 12 34 56 78 89  
3 5 7 9 12 34 56 98 234 456 789 1234

样例输出  
18  
2 3 4 5 6 7 8 9 12 34 56 78 89 98 234 456 789 1234

#include<stdio.h>
    #include<stdlib.h>
    #define N 250 
    #define INIT 10 
    typedef int ElemType;
    
    typedef struct LNode{ 
    	ElemType data;
    	struct LNode *next;
    }LNode,*LinkList;
    
    
    void createList(LinkList &l,int a[N],int n){ 
    	LinkList p,r; 
    	int i;
    	l=(LNode*)malloc(sizeof(LNode)*INIT);
    	r=l;
    	for(i=0;i<n;i++){ 
    		p=(LinkList)malloc(sizeof(LNode)*INIT);//新建节点p 
    		p->data=a[i]; //数组值赋给链表的数值域 
    		r->next=p;	  //r指向p，p为链表最后一个节点 
    		r=p;		  //r移动到链表最后一个节点的位置，r的位置在不断变化 
    	}
    	r->next=NULL;//r在链表的末尾，将r指向置为空 
    	
    } 
    
    
    int mergeList(LinkList &l1,LinkList &l2,LinkList &l3){ 
    	int i=0;
    	LinkList p,q,r;
    	l3=(LNode*)malloc(sizeof(LNode)*INIT);//创建新链表l3
    	 
    	r=l3; //使r指向l3末尾 
    	p=l1->next;//p指向l1头节点 
    	q=l2->next;//q指向l2头节点 
    	while(p&&q){  
    		if(p->data<q->data){ //若此时l1元素小于l2，将l1值放进l3中 
    			r->next=p;
    			r=p;
    			p=p->next;
    			i++;
    		}
    		else if(p->data>q->data){ //若此时l2元素小于l1，将l2值放进l3中 
    			r->next=q;
    			r=q;
    			q=q->next; 
    			i++;
    		}
    		else{ //若相等，将值放入l3，并同时是p，q往后移动 
    			r->next=p;
    			r=p;
    			p=p->next;
    			q=q->next;
    			i++;
    		}
    	}
    	
    	while(p){ //若q已遍历完，p未遍历完 
    		r->next=p;//将值依次放入l3 
    		r=p;
    		p=p->next;
    		i++;
    	}
    	
    	while(q){ 
    		r->next=q;
    		r=q;
    		q=q->next;
    		i++;
    	}
    	r->next=NULL; //r在链表的末尾，将r指向置为空 
    	
    	return i;//返回合并后集合中的元素个数 
    }
    
    void print(LinkList &l3){ 
    	LinkList p;
    	p=l3->next;
    	while(p){ 
    		printf("%d ",p->data);
    		p=p->next;
    	}
    }
    
    int main(){ 
    	int i,a[N],b[N],n1,n2,n3;
    	LinkList l1,l2,l3;
    	scanf("%d%d",&n1,&n2);
    	for(i=0;i<n1;i++)
    		scanf("%d",&a[i]);
    		
    	for(i=0;i<n2;i++)
    		scanf("%d",&b[i]);
    			
    	createList(l1,a,n1);//创建l1 
    	createList(l2,b,n2);//创建l2 
    	n3=mergeList(l1,l2,l3);//合并集合 
    	printf("%d\n",n3);
    	print(l3);//输出集合 
    	return 0;
    }

结果![在这里插入图片描述][20191207112721378.png]

[20191207112721378.png]: https://img-blog.csdnimg.cn/20191207112721378.png

发表评论取消回复

表情：

评论列表（有 0 条评论，9人围观）

还没有评论，来说两句吧...

相关阅读

相关有序链表合并讲解

include <stdio.h> include<stdlib.h> define MAXSIZE 100 define TRUE 1

╰+哭是因爲堅強的太久メ/ 2023年09月30日 12:39/ 0 赞/ 21 阅读

相关合并两个有序链表

一思路按老师上课讲的，先用其他链表记录两个链表共有部分，然后判断谁null，再接上另一个二代码 class Solution(object):

爱被打了一巴掌/ 2023年07月13日 10:51/ 0 赞/ 46 阅读

相关非递减有序集合合并-链表

非递减有序集合合并巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。输入

港控/mmm°/ 2023年06月19日 15:26/ 0 赞/ 10 阅读

相关合并两个有序链表

合并两个有序链表 1、题目题目要求：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例：输

灰太狼/ 2023年03月01日 12:52/ 0 赞/ 46 阅读

相关数据结构：用C语言实现非递减有序表的合并

实验要求（1）实验目的通过该实验，深入理解顺序表的逻辑结构、物理结构等概念，掌握顺序表基本操作的编程实现，注意顺序表插入、删除等操作过程中数据元素的移动现象，培养学

忘是亡心i/ 2022年12月13日 12:57/ 0 赞/ 158 阅读

相关合并有序链表

合并有序链表 1、参考资料 https://www.nowcoder.com/practice/a479a3f0c4554867b35356e0d57cf03d

﹏ヽ暗。殇╰゛Y/ 2022年12月03日 15:49/ 0 赞/ 210 阅读

相关合并有序链表详细题解

题目描述将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的。示例1 输入{ 1},{ }

╰半夏微凉°/ 2022年11月21日 11:56/ 0 赞/ 174 阅读

相关合并两个有序链表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

向右看齐/ 2022年09月01日 12:56/ 0 赞/ 265 阅读

相关有序链表合并

有序链表合并 include<stdio.h> include<iostream> using namespace std; //测试数据

柔情只为你懂/ 2021年12月15日 21:15/ 0 赞/ 316 阅读

相关合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例：输入：1->2->4, 1->3->4

我会带着你远行/ 2021年10月30日 08:20/ 0 赞/ 379 阅读