游客 注册 | 登录
中文 | En

1456 - C语言-链表排序

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

已有a、b两个链表，每个链表中的结点包括学号、成绩。要求把两个链表合并，按学号升序排列。

题目输入

第一行，a、b两个链表元素的数量N、M,用空格隔开。 接下来N行是a的数据 然后M行是b的数据 每行数据由学号和成绩两部分组成

题目输出

按照学号升序排列的数据

输入/输出样例

输入格式

2 3
5 100
6 89
3 82
4 95
2 10

输出格式

2 10
3 82
4 95
5 100
6 89

C语言解答

#include<stdio.h>
#include<stdlib.h>
struct lianbiao
{
	int id;
	int score;
	struct lianbiao*next;
};
typedef struct lianbiao node;
node* create(int n)
{
	node*head=(node*)malloc(sizeof(node));
	head->next=NULL;
	node*pre=head;
	int i;
	for(i=0;i<n;i++)
	{
		node*p=(node*)malloc(sizeof(node));
		scanf("%d %d",&p->id,&p->score);
		pre->next=p;
		p->next=NULL;
		pre=p;
	}
	return head;
}//创建链表
void hebing(node*a,node*b)
{
	node*p=a;
	node*q=b;
	while(p->next!=NULL)
	{
		p=p->next;//找到最后一个指针
	}
	p->next=q->next;//链接两个链表
	free(q);
	q=p->next;
}
void show(node*a)
{
	node*p=a->next;
	while(p!=NULL)
	{
		printf("%d %d\n",p->id,p->score);
		p=p->next;
	}
}
void merge(node*a,node*b)
{
	node*p=a->next;//a,b是头节点，p和q是有序链表指针
	node*q=b->next;
	node*pre=a;//a是新链表头,pre是新链表指针
	a->next=NULL;
	b->next=NULL;
	while(p!=NULL&&q!=NULL)
	{
		if(p->id<q->id)
		{
			pre->next=p;
			pre=p;
			p=p->next;
			pre->next=NULL;
		}
		else
		{
			pre->next=q;
			pre=q;
			q=q->next;
			pre->next=NULL;
		}
	}
	if(p!=NULL)
	{
		pre->next=p;
	}
	if(q!=NULL)
	{
		pre->next=q;
	}
}
void mergesort(node*a)
{
	int count=1;
	int i=1;
	node*p=a->next;//p指第一个结构体
if(p->next!=NULL)//p的下一个不为空，证明有两组数据，接着分，为空证明只有一组数据
{
		node*fast=a->next;//fast指链表最后一块结构体
	while(fast!=NULL)
	{
		fast=fast->next;
		count++;//结构体个数
	}
	node*slow=a->next;//slow指中间结构体
	while(i<count/2)
	{
		slow=slow->next;
		i++;//只要走到中间就停
	}
	node*fenjie=(node*)malloc(sizeof(node));//被劈开结构体的头节点
	fenjie->next=slow->next;//指着slow的下一块结构体
	slow->next=NULL;//分开两个链表
		mergesort(a);//递归
		mergesort(fenjie);//递归
		merge(a,fenjie);//合并有序链表
		free(fenjie);
}
}
int main()
{
	int m,n;
	node*al,*bl;
	scanf("%d %d",&m,&n);
	al=create(m);
	bl=create(n);
    hebing(al,bl);
	mergesort(al);
	show(al);
	return 0;
}

C++解答

#include "stdio.h"
#include <algorithm>
using namespace std;

struct number
{
 int id,grad;
}num[100];
bool cmp(number a,number b)
{
  return a.id<b.id;
}
int main(int argc, char* argv[])
{
	int a,b,i;
	while(~scanf("%d%d",&a,&b))
	{
	  for(i=0;i<a+b;i++)
	   scanf("%d%d",&num[i].id,&num[i].grad);
	  sort(num,num+a+b,cmp);
	for(i=0;i<a+b;i++)
	   printf("%d %d\n",num[i].id,num[i].grad);
	}
	return 0;
}
请先登陆