首页 > 其他分享 >两种方法线性表合并有序线性表

两种方法线性表合并有序线性表

时间：2024-04-06 17:29:46浏览次数：320  
标签：LNode 合并 数组 next LinkList L2 有序 L1 线性表

【问题描述】编写一个程序，将两个元素从小到大有序的一维数组归并成一个有序的一维数组。
【输入形式】用户在第一行输入第一个有序数组的元素数目，以回车结束此输入。然后在第二行按照刚才输入的元素数目依次输入数组元素，中间用空格分隔，最后用回车结束输入。第三行和第四行只需重复刚才的步骤，将第二个有序数组也输入即可。输入时候一定是有序输入的，即数组元素已经按照从小到大顺序排列。
【输出形式】程序将两个有序一维数组合并为一个有序数组并按照从小到大顺序输出。每个元素输出时用空格分隔，最后一个输出之后没有空格。
【样例输入】
6
2 5 8 11 20 35
4
1 6 15 60                    
【样例输出】1 2 5 6 8 11 15 20 35 60
【样例说明】第一行输入为第一个有序数组的元素数目，第二行为有序数组元素；第三行为第二个有序数组的元素数目，第四行为有序数组元素。
【评分标准】结果完全正确得20分。提交程序名为：arraysort.c

方法一:数组

 数组方法1:

将两组数据全部输入到同一个数组中,然后进行排序,输出;

代码如下:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int main()
{
	int num[2] = { 0 }, shuru[50] = { 0 };
	int i, j = 0, m;//循环变量

	//输入
	for (i = 0; i < 2; i++)
	{
		scanf("%d", &num[i]);
		for (; j < num[0] + num[1]; j++)
		{
			scanf("%d", &shuru[j]);
		}
	}

	// 插入排序 从大到小
	for (i = 0; i < num[0] + num[1]; ++i)
	{
		int end = i;//有序数列最后一个元素下标
		shuru[num[0] + num[1]] = shuru[end + 1];
		while (end >= 0)
		{
			if (shuru[num[0] + num[1]] < shuru[end])//向后移  
			{
				shuru[end + 1] = shuru[end];
				end--;
			}
			else
				break;
		}
		shuru[end + 1] = shuru[num[0] + num[1]];
	}

	for (i = 0; i < j; i++)
		printf("%d ", shuru[i]);

	return 0;
}
数组方法2:

定义两个数组,长度够长(20左右) 依次载入数据

设计一个比较算法:

如果数组1已经比较结束,则接下来全输出数组2:数组2同理.  

如果两个数组都没输出完,则比较当前位置上,数组1的数据和数组2的数据哪个大,哪个小输出哪个,再将该数组下标++;

提示:数组动态创建可用 malloc 函数实现   malloc(sizeof(int)*Length);

代码略~

方法二:单链表

单链表方法1:

尾插法生成单链表 新建一个单链表,依次合并插入数据,最后输出新的单链表.


#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>  
#include <stdlib.h>  

typedef struct LNode 
{
	int data;
	struct LNode* next;
} LNode, * LinkList;

// 创建单链表头节点  
LinkList CreateList() 
{
	return (LinkList)malloc(sizeof(LNode));
}

// 尾插法
void CreateListWithCount(LinkList L, int count) 
{
	L->next = NULL;                          

	int i = 0;
	for (; i <count; i++) 
	{
		int value;
		scanf("%d", &value);
		LNode* newNode = (LNode*)malloc(sizeof(LNode));
		newNode->data = value;
		newNode->next = L->next;
		L->next = newNode;
		L = L->next;                                        //  debug  少了这句话就倒序，逐链表输出！！！！！
	}
}

//递归
LinkList MergeList(LinkList L1, LinkList L2)
{

	if (L1 == NULL)
		return L2;
	if (L2 == NULL)
		return L1;

	LinkList MergedList;                                //合并的链表

	if (L1->data <= L2->data)
	{
		MergedList = L1;
		MergedList->next = MergeList(L1->next, L2);
	}
	else
	{
		MergedList = L2;
		MergedList->next = MergeList(L1, L2->next);
	}

	return MergedList;
}

/*
// 合并两个有序单链表  
LinkList MergeList(LinkList L1, LinkList L2) 
{
	LinkList MergedList = CreateList();
	LNode* p1 = L1->next;
	LNode* p2 = L2->next;
	LNode* tail = MergedList;

	while (p1 && p2)                      //不为空
	{
		if (p1->data <= p2->data) 
		{
			tail->next = p1;
			p1 = p1->next;
		}
		else 
		{
			tail->next = p2;
			p2 = p2->next;
		}
		tail = tail->next;
	}

	tail->next = p1 ? p1 : p2;

	free(L1);
	free(L2);

	return MergedList;
}

*/

// 打印链表  
void PrintList(LinkList L) 
{
	LNode* s = L->next;/头节点为空  输出地址   若不适用递归  则：	LNode* p = L->next; 就行

	LNode* p = s->next;
	while (p) 
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

// 释放链表内存  
void FreeList(LinkList L) 
{
	LNode* temp;
	while (L->next) 
	{
		temp = L->next;
		L->next = L->next->next;
		free(temp);
	}
	free(L);
}

int main() 
{
	int count1, count2;

	// 输入第一个数组的大小  
	scanf("%d", &count1);
	LinkList L1 = CreateList();
	CreateListWithCount(L1, count1); // 创建第一个有序链表  

	// 输入第二个数组的大小  
	scanf("%d", &count2);
	LinkList L2 = CreateList();
	CreateListWithCount(L2, count2); // 创建第二个有序链表  

	LinkList MergedList = MergeList(L1, L2); // 合并链表  
	PrintList(MergedList);                  // 打印合并后的链表  

	// 释放链表内存  
	FreeList(MergedList);

	return 0;
}
另外一种写法:
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef struct LNode //链表定义
{
	int data;
	struct LNode* next;
}*LinkList, LNode;

//带头结点的初始化
bool InitList(LinkList & L) {
	L = (LNode*)malloc(sizeof(LNode));
	if (L == NULL) {
		return true;
	}
	L->next = NULL;
	return true;
}

//尾插法创建一个单链表
bool TailInsert(LinkList L) // L是指向定义的LNode结构体的指针
{
	int num = 0;//元素个数
	int ele = 0;//数据
	LNode* p = L;
	printf("请输入你要插入的元素个数：\n");
	scanf("%d", &num);

	int i = 0;
	for (; i < num; i++) {
		printf("请输入第%d个元素: ", i + 1);
		scanf("%d", &ele);
		LNode* s = (LNode*)malloc(sizeof(LNode));
		if (s == NULL) {
			return false;
		}
		s->data = ele;
		s->next = NULL;
		p->next = s;
		p = p->next;
	}
	return true;
}

//合并两个单链表
LinkList mergeList(LinkList L1, LinkList L2) {
	LNode* head = (LNode*)malloc(sizeof(LNode));
	LNode* p1 = L1->next;			//扫描指针p1指向第一个链表
	LNode* p2 = L2->next;			//扫描指针p2指向第二个链表
	LNode* pre = head;		//记录前驱结点
	while (p1 != NULL && p2 != NULL) {
		if (p1->data <= p2->data) {            //按降序进行连接
			pre->next = p1;
			p1 = p1->next;
		}
		else {
			pre->next = p2;
			p2 = p2->next;
		}
		pre = pre->next;
	}
	pre->next = p1 == NULL ? p2 : p1;
	return head;
}

//遍历一个单链表
void TranverseLinkList(LinkList L) {
	LNode* p = L->next;
	printf("单链表序列为：");
	while (p != NULL) {
		printf("%d ", p->data);
		p = p->next;
	}
}

int main() {
	LinkList L1 = NULL;
	LinkList L2 = NULL;
	InitList(L1);
	InitList(L2);
	TailInsert(L1);
	TailInsert(L2);
	LinkList L3 = mergeList(L1, L2);
	TranverseLinkList(L3);
}
单链表方法2:

一边比较两个单链表,一边输出数据.原理与数组类似,代码略

//关于 #define _CRT_SECURE_NO_WARNINGS

在VS里面,不可直接使用scanf  否则会报 sacnf 不安全 或 scanf返回值被忽略

解决方法添加该句话  或者将scanf 改为 scanf_s  但是scanf_s交作业时候编译不通过qwq~ 交作业时候删去_s即可(略显麻烦

一次性解决      

标签：LNode,合并,数组,next,LinkList,L2,有序,L1,线性表
From： https://blog.csdn.net/m0_54369037/article/details/137403270

相关文章

  • 两个顺序表的合并问题
    两个顺序表的合并问题#include<stdio.h>#defineMAXSIZE300typedefstruct{ intlength; int*p;}Sqlist;voidSXB(Sqlist&L){ L.length=0; L.p=newint[MAXSIZE];}voidinsert(Sqlist&L,intn){ if(n>MAXSIZE)printf("inputerror!"); in......
  • FFmpeg音视频裁剪和合并命令
    FFmpeg音视频裁剪和合并命令命令简介裁剪音视频和合并音视频。合并命令ffmpeg-i[输入文件1]-i[输入文件2]...[滤镜参数][输出文件]输入文件指明输入你要合并的文件，可以有多个输入文件。滤镜参数可以为合并的文件添加滤镜，详细参数查看ffmpeg滤镜命令中的参数。输......
  • 线性表基本操作物理实现
    #include<stdio.h>//顺序表的初始化及插入操作实战#defineMaxSize50typedefintElemType;//为什么这样设计，一旦用这种方式下面写代码，方便后续顺序表存储的不是整形方便修改，统一修改typedefstruct{ElemTypedata[MaxSize];intlen;//顺序表长度}Sqlist;/......
  • 代码随想录算法训练营第二天 | 数组 977.有序数组的平方
    leetcode977.有序数组的平方题目977.有序数组的平方给你一个按非递减顺序排序的整数数组nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。示例1：输入：nums=[-4,-1,0,3,10]输出：[0,1,9,16,100]解释：平方后，数组变为[16,1,0,9,100]排序后，数组变为[0,1,9......
  • LeetCode in Python 88. Merge Sorted Array (合并两个有序数组)
    合并有序数组也有两种方法，区别是空间复杂度不同。第一种，重新开辟一个数组空间，大小为O(m+n)，另外需要三个指针分别指向两个有序数组和新开辟的数组，依次判断两个数组内元素大小，不断更新指针即可。第二种，无需单独开辟空间，在第一个数组(该数组空间足够存放两个数组总长的数据)内进行......
  • 分布式进阶（五）——分布式框架之高性能：消息有序性
    作者简介：大家好，我是smart哥，前中兴通讯、美团架构师，现某互联网公司CTO联系qq：184480602，加我进群，大家一起学习，一起进步，一起对抗互联网寒冬学习必须往深处挖，挖的越深，基础越扎实！阶段1、深入多线程阶段2、深入多线程设计模式阶段3、深入juc源码解析阶段4、深入jdk其余源码解析......
  • 数据结构——从入门到飞升——两个有序链表的交集
    题目：已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。输入格式:输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。输出格式:在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有......
  • Pandas Dataframe合并连接Join和merge 参数讲解
    文章目录函数与参数分析otheronhowlsuffix,rsuffix,suffixesleft_index,right_index函数与参数分析在pandas中主要有两个函数可以完成table之间的joinJoin的函数如下：DataFrame.join(other,on=None,how=‘left’,lsuffix=‘’,rsuffix=‘’,sort=False,va......
  • 数据结构——从入门到飞升——两个有序链表的合并
    首先，我们要知道sort（）函数的使用方法：1.需要函数头#include2.sort(begin,end,cmp)begin：指向待分类元素的第一个指针end:指向待分类元素最后一个的指针其中end-begin是所有数的数量cmp：表示排序的样式，没有就是默认从小到大排要是想从大到小排，可写成greater，int也可以写成别的......
  • intellij idea 使用git ，快速合并冲突
    可以选择左边的远程分支上的代码，也可以选择右边的代码，而中间是合并的结果。一个快速合并冲突的小技巧：如果冲突比较多，想要快速合并冲突。也可以直接点击上图中Applynon-conflictingchanges旁边的All。这样Idea就会自动帮你把左右两边的分支内容合并，不用自己一个一......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99