欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

顺序合并两个非有序的链表(C语言写法)

程序员文章站 2022-06-26 11:31:25
...

  题目要求:给定由整数组成的两个无序数组,根据顺序合并成一个数组。

  输入要求:输入包括两行,每行由若干个由->分隔的整数组成,分别表示以最左整数为链表头,单向指向右侧节点的链表,每行输入均以 .结尾。

  输出要求:输出为合并后的单向链表,由->表示其间的指针,最终指向由NULL表示的空值。在合并过程中,比较两个链表当前待合并的第一个元素,选择其中较小的那个元素放入合并后的数组。
输入格式:输入两行字符串,每行字符串由 有符号整数、->和.组成。
输出格式:输出一行字符串,表示合并后的数组。
样例输入

1->2->3.
1->0->2.

  样例输出

1->1->0->2->2->3->NULL

  关于这道题,考察链表的熟练程度:会打链表、并且链表之间比较来进行插入操作。
要先打好结构体:

struct node
{
	int num;//存储数字
	struct node * next;//指向下一个结点
};

  打链表模板:

	struct node * head,* p,* q;//先定义必须的指针;
	head=NULL;//让头指针指向NULL,不然后面判断head没法进行。
	while(scanf("%d->",&a))//输入的同时也判断输入的内容,如果是"1->"scanf返回的是1,也是true,当输入'.'的时候,scanf返回的是0,false。被留在缓冲区
	{
		p=(struct node *)malloc(sizeof(struct node));
		p->num=a;
		p->next=NULL;
		if(head==NULL)
		{
			head=p;//第一次时候,将链表的结点地址传给head
		}
		else
		{
			q->next=p;//第二次以及以上母结点的下一个结点为p
		}
		q=p;//改选中的结点为下一个结点
	}

  那么我们可以根据这个模板,打出两个链表:

struct node * head,* p,* q,* t,* head1,* p1,* q1;
	int a,b;
	head=NULL;
	head1=NULL; 
	while(scanf("%d->",&a))//这是第一个链表开始
	{
		p=(struct node *)malloc(sizeof(struct node));
		p->num=a;
		p->next=NULL;
		if(head==NULL)
		{
			head=p;
		}
		else
		{
			q->next=p;
		}
		q=p;
	}
	getchar();//为了清除缓冲区中残留的'.',不影响到下一个
	while(scanf("%d->",&b))//第二个链表开始
	{
		p1=(struct node *)malloc(sizeof(struct node));
		p1->num=b;
		p1->next=NULL;
		if(head1==NULL)
		{
			head1=p1;
		}
		else
		{
			q1->next=p1;
		}
		q1=p1;
	}

  那么到了交换的时候了,我们先定义一个函数来专门交换两个链表之间(递归实现)

struct node * exchange(struct node *head,struct node *head1)//定义的函数返回值为head结点地址
{
	if(head==NULL||head1==NULL)
	{
		return head==NULL?head1:head;//判断语句如果其中一个为NULL,则返回另一个
	}
	struct node *head3=NULL;//该值被返回,用来做索引该链表的结点。
	if(head->num<=head1->num)//开始比较大小
	{
		head3=head;
		head3->next=exchange(head->next,head1);//递归的开始
	}
	else
	{
		head3=head1;
		head3->next=exchange(head,head1->next);//递归的开始
	}
	return head3;
}

  最后返回的是一个已经排好序的链表的头结点,只要利用头结点,并且按结点循环就可以依次输出我们所需的值:

	t=exchange(head,head1);//传给t
	while(t->next!=NULL)
	{
	printf("%d->",t->num);
	t=t->next;//让t按着结点链
	}
	printf("%d->NULL",t->num);
	return 0;

  总代码图:

#include<stdio.h>
#include<stdlib.h>
struct node
{
	int num;
	struct node * next;
};
struct node * exchange(struct node *p,struct node *p1);
int main()
{
	struct node * head,* p,* q,* t,* head1,* p1,* q1;
	int a,b;
	head=NULL;
	head1=NULL; 
	while(scanf("%d->",&a))
	{
		p=(struct node *)malloc(sizeof(struct node));
		p->num=a;
		p->next=NULL;
		if(head==NULL)
		{
			head=p;
		}
		else
		{
			q->next=p;
		}
		q=p;
	}
	getchar();
	while(scanf("%d->",&b))
	{
		p1=(struct node *)malloc(sizeof(struct node));
		p1->num=b;
		p1->next=NULL;
		if(head1==NULL)
		{
			head1=p1;
		}
		else
		{
			q1->next=p1;
		}
		q1=p1;
	}
	t=exchange(head,head1);
	while(t->next!=NULL)
	{
	printf("%d->",t->num);
	t=t->next;
	}
	printf("%d->NULL",t->num);
	return 0;
}
struct node * exchange(struct node *head,struct node *head1)
{
	if(head==NULL||head1==NULL)
	{
		return head==NULL?head1:head;
	}
	struct node *head3=NULL;
	if(head->num<=head1->num)
	{
		head3=head;
		head3->next=exchange(head->next,head1);
	}
	else
	{
		head3=head1;
		head3->next=exchange(head,head1->next);
	}
	return head3;
}
相关标签: 算法大法好!