1052: [编程入门]链表合并题解

解题思路:

参考了最赞，不过大部分按照自己理解重新写了答案

1、新建链表节点结构体；

2、定义创建链表函数；

3、定义合并链表函数；

4、定义链表按学号升序函数；

5、定义输出链表数据函数；

6、主函数：输入两张链表的长度，创建两张链表，合并两张链表，排序链表，最后输出链表。

注意事项:

新手，虽然运行没有报错，结果也是正确的，但是可能代码有语句上的错误，仅供参考。

参考代码:

#include <stdio.h>

#include <malloc.h>

typedef struct student

{

    int sid;

    int score;

    struct student *next;

}*node;    //链表节点结构体

node creat(int n)    //创建链表函数

{

    int i;

    node h;    //创建头节点

    h=(node)malloc(sizeof(node));    //给头结点分配内存

    h->next=NULL;    //此时头结点也是尾结点，下一节点指向NULL

    node q=h;    //指针q指向尾结点，此时尾结点是头结点

    node p;    //该节点是用于新建节点

    for(i=0;i<n;i++)    //函数输入的n为带数据节点的数量

    {

        p=(node)malloc(sizeof(node));    //给新节点分配内存

        scanf("%d %d",&(p->sid),&(p->score));    //输入数据

        p->next=NULL;    //此时新建的结点是尾结点，下一节点指向NULL

        q->next=p;    //q指向之前的尾结点，之前的尾结点的下一节点指向新节点

        q=p;    //此时尾结点是新建的结点

    }

    return h;    //返回头结点

}

node combine(node l1,node l2)    //合并链表函数

{

    node q;

    q=l1;    //指针指向表a的头结点l1

    while(q->next!=NULL) q=q->next;    //通过一次次下移，指针指向表a尾结点

    q->next=l2->next;    //表a的尾结点的下一节点指向表b的第一个有数据的节点

    return l1;    //返回头结点

}

node order(node l)    //排序函数

{

    int t0,t1;

    node q,p;

    q=l->next;    //q指向表的第一行数据

    while(q->next!=NULL)    //q一直到倒数第二行数据

    {

        p=q->next;    //p指向q的下一行数据

        while(p!=NULL)    //p和q一直比较到之后以后数据

        {

            if(q->sid>p->sid)    //如何q的sid比p大就交换两行数据

            {

                t0=q->sid;

                t1=q->score;

                q->sid=p->sid;

                q->score=p->score;

                p->sid=t0;

                p->score=t1;

            }

            p=p->next;    //p指向p的下一行

        }

        q=q->next;    //q指向q的下一行

    }

    return l;    //返回头结点

}

void output( node l )      //输出链表函数

{

    l = l->next;    //下移一个节点

    node q; //用于释放每个结点

    while ( l != NULL )    //直到到最后一行数据

    {

        printf( "%d %d\n", l->sid, l->score );    //输出该行数据

        q=l;    //q指向该节点

        l = l->next;    //下移一个节点

        free(q);  //释放结点

    }

}

int main()

{

    int m,n;

    node l1,l2;

    scanf("%d %d",&m,&n);  //输入的第一行两个数字为两个表长度

    l1=creat(m);  //新建表a

    l2=creat(n);  //新建表b

    combine(l1,l2);  //合并表a、b成新表a

    order(l1);  //按sid排序表a

    output(l1);  //输出表a

}