学步园

请用链表完成下面题目要求。
xiaobai 很喜欢音乐，几年来一直在收集好听的专辑。他有个习惯，每次在听完一首音乐后会给这首音乐打分，而且会隔一段时间给打好分的音乐排一个名次。今天 xiaobai打开自己的音乐文件夹，发现有很多不同时期打过分的排好序的子音乐文件夹，他想把这些音乐放到一块，组成一个分数有序的序列。由于音乐文件很多，而文件里音乐的数目也是不确定的，怎么帮帮 xiaobai完成这件工作呢？
   

输入数据第一行为一个整数n（n<1000)，代表文件夹的数量。接下来是n个文件夹的信息，每个文件夹信息的第一行是一个数字m，代表这个文件夹里有m首歌，后面m行每行一个歌曲名、分数，之间用空格分开。

输出一行，为所有音乐组成的一个序列，音乐只输出名字。

如果音乐分数相同则按照音乐名字典序进行排序。

3

4

aaa 60

aab 50

aac 40

aad 30

2

kkk 60

kkd 59

3

qow 70

qwe 60

qqw 20

qow aaa kkk qwe kkd aab aac aad qqw

 分析：本题考验的是对链表的建立输出，最重要是对有序链表的合并等知识的掌握。纯属基础性问题，掌握链表的基本知识即可做出本题。
#include <stdio.h>
#include <malloc.h>
#include <string.h>

struct node  //建立结点
{
    char name[10];   //歌曲的名字变量
    int s;           //歌曲的分数
    struct node *next;    //指针域
};

//--------建立链表-------
struct node *create1(int num)
{
    struct node *head,*tail,*p;
    int i;
    head = (struct node*)malloc(sizeof(struct node));   //建立头结点
    head->next = NULL;       
    tail = head;      //尾指针指向头结点
    for(i = 1;i <= num;i++)
    {
        p = (struct node*)malloc(sizeof(struct node));
        p->next = NULL;
        scanf("%s %d",p->name,&p->s);
        tail->next = p;   //形成链表间的结点连接
        tail = p;         //尾结点指向下一个结点
    }
    return (head);        //返回头结点

}
//--------链表合并--------
/*归并过程是一个新建链表的过程，先借用原来链表头结点生成一个空的新链表，
 同时两个旧链表指针指向要比较的结点的位置，用p1, p2指向两个链表的当前结点。
struct node *merg(struct node *head1,struct node *head2)
{
    struct node *tail,*p1,*p2;
    p1 = head1->next;   //将head1链表复制给p1
    p2 = head2->next;   //将head2链表复制给p2

    tail = head1;    //尾结点指向head1
    free(head2);   //释放head2
    while(p1&&p2)
    {
        if(p1->s >= p2->s)  //归并的条件
        {
            if(strcmp(p1->name,p2->name) < 0)   //按照音乐名字典序进行排序
             {   tail->next  = p1;    //把数值较大的结点从所在链表删除并插入到新链表尾结点之后，同时使得新链表的尾指针指向新的尾结点
                 tail = p1;           //被删结点的旧链表游动指针往后移动，指向后面的结点。
                 p1 = p1->next;
             }
             else
                {
                    tail->next = p2;
                    tail = p2;
                    p2 = p2->next;
                }
        }else
        {
            tail->next = p2;
            tail = p2;
            p2 = p2->next;
        }

    }
    if(p1)   //p1的结点还剩余，则尾指针指到p1
        tail->next = p1;
    else
        tail->next = p2;

    return (head1);
}
 //-------输出链表--------
 void output(struct node *head)
 {

     struct node *p;
     p = head->next;
     while(p->next != NULL)
     {
         printf("%s ",p->name);
         p = p->next;

    }
    printf("%s\n",p->name);
    free(p);
 }
int main()
{
    struct node *Head1,*Head2;
    int NUM,j,Num;
    scanf("%d",&NUM);
    scanf("%d",&Num);
    Head1 = create1(Num);  //首先建立指针1，判断是否输入的组数大于1，如果等于1，则输出链表1，
                           //否则，继续输入链表2，与链表1合并。
    if(NUM == 1)
    {
        output(Head1);

    }else
    {
          for(j = 2;j <= NUM;j++)
       {
           scanf("%d",&Num);
           Head2 = create1(Num);
           Head1 = merg(Head1,Head2);
       }
    }
      output(Head1);
      free(Head1);
    return 0;
}