链表合并

code

6 年前

链表合并

时间： 1ms 内存：128M

描述：

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

输入：

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

输出：

按照学号升序排列的数据

示例输入：

示例输出：

提示：

参考答案（内存最优[1092]）：

#include <stdio.h>
#include <stdlib.h>
typedef struct student
{
    int num;
    float score;
    struct student *next;
}stu;
stu *creat(int n)
{
    int i;
    stu *p,*head = NULL,*tail = head;
    for (i = 0; i < n; i++)
    {
        p = (stu *)malloc(sizeof(stu));
        scanf("%d%f",&p->num,&p->score);
        p->next = NULL;
        if ( p->num <= 0)
        {
            free(p);
            break;
        }
        if(head == NULL)
            head = p;
        else
            tail->next = p;
        tail = p;
    }
    return head;
}

void print(stu *p)
{
    while (p != NULL)
    {
        printf("%d %.0f\n",p->num,p->score);
        p = p->next;
    }
}

stu *link(stu *p1,stu *p2)
{
    stu *head,*p,*q;
    head = (stu *)malloc(sizeof(stu));
    head->next=NULL;
    p=head;
    if(head->next==NULL)
    {
        q = (stu *)malloc(sizeof(stu));
        q->num=p1->num;
        q->score=p1->score;
        q->next=p->next;
        p->next=q;
        p1=p1->next;
    }
    while(p1!=NULL)
    {
        p=head;
        q = (stu *)malloc(sizeof(stu));
        q->num=p1->num;
        q->score=p1->score;
        while(p->next!=NULL)
        {
            if(p->next->num<q->num)
            {
                p=p->next;
            }
            else
            {
                q->next=p->next;
                p->next=q;
                p=head;
                break;
            }
        }
        if(p->next==NULL)
        {
            q->next=p->next;
            p->next=q;
            p=head;
        }
        p1=p1->next;

    }
    while(p2!=NULL)
    {
        p=head;
        q = (stu *)malloc(sizeof(stu));
        q->num=p2->num;
        q->score=p2->score;
        while(p->next!=NULL)
        {
            if(p->next->num<q->num)
            {
                p=p->next;
            }
            else
            {
                q->next=p->next;
                p->next=q;
                p=head;
                break;
            }
        }
        if(p->next==NULL)
        {
            q->next=p->next;
            p->next=q;
            p=head;
        }
        p2=p2->next;
    }
    head=head->next;
    return head;
}


int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    stu *a,*b,*c;
    a = creat(n);
    b = creat(m);
    c = link(a,b);
    print(c);
    return 0;
}

参考答案（时间最优[0]）：

#include <stdio.h>
#include <malloc.h>
struct StuLink
{
    int no;
    int score;
    struct StuLink *next;
};
/*by lyh   2013.9.26  */
struct StuLink * CreatLink(struct StuLink  *p, int num)
{ /*递归建立 具有num节点的链表，返回链表的首节点 */
    struct StuLink  *head = p,*p1;
    if(num>0)
    {
        p1=(struct StuLink *)malloc(sizeof(struct StuLink));
        scanf("%d%d",&p1->no,&p1->score);
        p1->next=NULL;
        if(p==NULL)
        {
            return CreatLink(p1,num-1);
        }
        while(p->next)
            p=p->next;
        p->next = p1;
        return CreatLink(head,num-1);

    }
    return head;
}
void OutputLink(struct StuLink  *p)
{
    while(p)
    {
        printf("%d %d\n",p->no,p->score);
        p=p->next;
    }
}
struct StuLink  *MergeLink(struct StuLink  *p1,struct StuLink  *p2)
{ /* 合并 */
    struct StuLink *head = p1;
    while(p1->next)
         p1=p1->next;
    p1->next = p2;
    return head;
}

void DestoryLink(struct StuLink  *p){
    struct StuLink *p1;
    while(p){
        p1=p;
        p=p->next;
        free(p1);
    }
}
struct StuLink *InsertSortedLink(struct StuLink  *p1,struct StuLink  *p2)
{/*节点p2 插入到有序链表p1中*/
    struct StuLink *head = p1,*pre;
    if(p1==NULL)
        return p2;
    while(p1&&p1->no<p2->no){
        pre=p1;
        p1=p1->next;
    }
    if(p1==NULL){ /*p2 插入在尾节点*/
        pre->next=p2;
        return head;
    }
    if(p1==head){/*p2 插入在首节点*/
        p2->next = p1;
        return p2;
    }
    pre->next = p2;
    p2->next = p1;
    return head;
}
struct StuLink *InsertSortLink(struct StuLink  *p){
/* 对链表 p 实现插入排序 */
    struct StuLink *head=NULL,*p1;
    while(p){
        p1=p;
        p=p->next;
        p1->next =NULL; /*将节点p从链表上摘下*/
        head = InsertSortedLink(head,p1);
    }
    return head;
}
int main()
{
    int num1,num2;
    scanf("%d%d",&num1,&num2);
    struct StuLink  *link1,*link2;
    link1=link2=NULL;
    link1=CreatLink(link1,num1);
    link2=CreatLink(link2,num2);
    MergeLink(link1,link2);
    link1=InsertSortLink(link1);
    OutputLink(link1);
    DestoryLink(link1);
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。