1456 - C语言-链表排序
已有a、b两个链表，每个链表中的结点包括学号、成绩。要求把两个链表合并，按学号升序排列。
Input
第一行，a、b两个链表元素的数量N、M,用空格隔开。 接下来N行是a的数据 然后M行是b的数据 每行数据由学号和成绩两部分组成
Output
按照学号升序排列的数据
Examples
Input
2 3 5 100 6 89 3 82 4 95 2 10
Output
2 10 3 82 4 95 5 100 6 89
Solution 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; }
Solution 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; }