拼题--两个有序链表序列的合并 （20 分)（三种算法的比较）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了拼题--两个有序链表序列的合并 （20 分)（三种算法的比较），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3115字，纯文字阅读大概需要5分钟。

内容图文

7-18 两个有序链表序列的合并 （20 分)

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。

输入格式:

输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用?1表示序列的结尾（?1不属于这个序列）。数字用空格间隔。

输出格式:

在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例:

1 3 5 -1
2 4 6 8 10 -1

输出样例:

1 2 3 4 5 6 8 10

 法一：数组表示

#include<stdio.h>
#define N 500000
int main()
{
	int a[N],b[N],c[N],asize=0,bsize=0,csize=0;
	int temp,i=0,j=0,k;
	while(scanf("%d",&temp)!=EOF&&temp!=-1)
	{
		a[asize++]=temp;
	}
	while(scanf("%d",&temp)!=EOF&&temp!=-1)
	{
		b[bsize++]=temp;
	}
	while(i<asize&&j<bsize)
	{
		if(a[i]<b[j])
		{
			c[csize++]=a[i];
			i++;
		}
		else
		{
			c[csize++]=b[j];
			j++;
		}
	}
	if(i==asize)
	{
		for(k=j;k<bsize;k++)
		{
			c[csize++]=b[k];
		}
	}
	else
	{
		for(k=i;k<asize;k++)
		{
			c[csize++]=a[k];
		}
	}
	if(csize>0)
	{
		printf("%d",c[0]);
		for(i=1;i<csize;i++)
		{
			printf(" %d",c[i]);
		}
	}
	else printf("NULL");
}

优点：简洁易懂，编码速度快

缺点：会有一个大数据测试发生段错误，只能得16分

法二：链表表示

#include<stdio.h>
#include<stdlib.h>
typedef struct Node *LNode;
typedef struct Node
{
	int data;
	LNode Next;
}Node;
void Insert(LNode head)
{
	LNode p,q=head;
	int temp;
	while(scanf("%d",&temp)!=EOF&&temp!=-1)
	{
		p=(LNode)malloc(sizeof(Node));
		p->data=temp;
		p->Next=NULL;
		q->Next=p;
		q=p;
	}
}
void cmp(LNode head1,LNode head2,LNode head3)
{
	LNode p1,p2,p3,q3;
	p1=head1->Next;
	p2=head2->Next;
	p3=q3=head3;
	while(p1&&p2)
	{
		if(p1->data<p2->data)
		{
			p3=(LNode)malloc(sizeof(Node));
			p3->data=p1->data;
			p3->Next=NULL;
			
			q3->Next=p3;
			q3=p3;
			p1=p1->Next;
		}
		else
		{
			p3=(LNode)malloc(sizeof(Node));
			p3->data=p2->data;
			p3->Next=NULL;
			
			q3->Next=p3;
			q3=p3;
			p2=p2->Next;
		}
	}
	
	if(p1)
	{
		while(p1)
		{
			p3=(LNode)malloc(sizeof(Node));
			p3->data=p1->data;
			p3->Next=NULL;
			
			q3->Next=p3;
			q3=p3;
			p1=p1->Next;
		}
	}
	else
	{
		while(p2)
		{
			p3=(LNode)malloc(sizeof(Node));
			p3->data=p2->data;
			p3->Next=NULL;
			
			q3->Next=p3;
			q3=p3;
			p2=p2->Next;
		}
	}
}
void Print(LNode head3)
{
	LNode p3;
	p3=head3->Next;
	if(!p3) printf("NULL");
	else 
	{
		printf("%d",p3->data);
		p3=p3->Next;
	}
	while(p3)
	{
		printf(" %d",p3->data);
		p3=p3->Next;
	}
}
int main()
{
	LNode head1,head2,head3;
	head1=(LNode)malloc(sizeof(Node));
	head2=(LNode)malloc(sizeof(Node));
	head3=(LNode)malloc(sizeof(Node));
	
	head1->Next=NULL;head2->Next=NULL;head3->Next=NULL;
	
	Insert(head1);   //用来建立链表1 
	Insert(head2);   //用来建立链表2 
	cmp(head1,head2,head3); //将链表1和链表2对比，对比结果填入链表3中 
	Print(head3);   //将链表3输出 
	
}

优点：测试点全部通过

缺点：太复杂，编码速度慢

法三：数组表示（动态申请内存）

#include<stdio.h>
#include<stdlib.h>
#define N 2000000
int main()
{
	int *a,*b,*c,asize=0,bsize=0,csize=0;
	a=(int *)malloc(sizeof(int)*N);
	b=(int *)malloc(sizeof(int)*N);
	c=(int *)malloc(sizeof(int)*N);
	int temp,i=0,j=0,k;
	while(scanf("%d",&temp)!=EOF&&temp!=-1)
	{
		a[asize++]=temp;
	}
	while(scanf("%d",&temp)!=EOF&&temp!=-1)
	{
		b[bsize++]=temp;
	}
	while(i<asize&&j<bsize)
	{
		if(a[i]<b[j])
		{
			c[csize++]=a[i];
			i++;
		}
		else
		{
			c[csize++]=b[j];
			j++;
		}
	}
	if(i==asize)
	{
		for(k=j;k<bsize;k++)
		{
			c[csize++]=b[k];
		}
	}
	else
	{
		for(k=i;k<asize;k++)
		{
			c[csize++]=a[k];
		}
	}
	if(csize>0)
	{
		printf("%d",c[0]);
		for(i=1;i<csize;i++)
		{
			printf(" %d",c[i]);
		}
	}
	else printf("NULL");
	free(a);
	free(b);
	free(c);
}

很完美！使用malloc申请内存比数组要申请的多！！！

内容总结

以上是互联网集市为您收集整理的拼题--两个有序链表序列的合并 （20 分)（三种算法的比较）全部内容，希望文章能够帮你解决拼题--两个有序链表序列的合并 （20 分)（三种算法的比较）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---