4.单链表.md

#4.单链表

##题目描述 编程实现下述功能：

编一函数struct node * create()，建立如下形式的单链表，并把每次读入的整数添加到链首。

编写一函数sort（struct node *head），按将无序单链表中的整数data成员按大到小的次序变为有序单链表。

主函数调用函数create创建一个单链表，并分别输出排序前和排序后的单链表。

##输入 输入文件有多组测试数据。第一行有一个整数n，它是测试数据组数，（n≤20）。接下来有n行，每行至多有m个整数，（m≤1000），整数之间有一个或多个空格。行尾无多余空格。每一行的数据输入结束标志为换行符号。

##输出 对每一组测试数据，先在一行上先输出“Case #:”，其中“#”是测试数据的行编号（从1开始），接着的一行上输出“Before sorting:”,再在接下来的行上输出排序前的单链表，每行10个结点值；然后在下面的一行上输出“After sorting:”,再在接下来的行上输出排序后的单链表，也是每行10个结点值。

##样例输入

3
1 3 2 -1
1 2 1 0
12 3 4 5 67 8 9 1 2 34 5 67 28 19 0

##样例输出

Case 1:
Before sorting:
-1 2 3 1
After sorting:
3 2 1 -1
Case 2:
Before sorting:
0 1 2 1
After sorting:
2 1 1 0
Case 3:
Before sorting:
0 19 28 67 5 34 2 1 9 8
67 5 4 3 12
After sorting:
67 67 34 28 19 12 9 8 5 5
4 3 2 1 0

##源代码（C++）

//Programmed by Daphne 2015.7.7
//E-mail: Daphne.Chang@foxmail.com
#include <stdio.h>
#include <list>
#include <iostream>
#include <strstream>
using namespace std;

int main()
{
    int k,count=1,x;
    scanf("%d",&k);
    char str[10000];
    cin.getline(str,10000);
    while(k--)
    {
        list<int>l;
        l.clear();
        cin.getline(str,10000);
        istrstream iss(str,10000);
        while(iss>>x)
        {
            l.push_front(x);
        }
        printf("Case %d:\n",count++);
        printf("Before sorting:\n");
        list<int>::iterator it=l.begin();
        printf("%d",*it);
        it++;
        int i;
        for(i=1;it!=l.end();it++,i++)
        {
            //printf(" %d",*it);
            if(i%10==0)
            {
                printf("\n%d",*it);
            } 
            else printf(" %d",*it);
        }
        printf("\nAfter sorting:\n");
        l.sort(greater<int>());
        it=l.begin();
        printf("%d",*it);
        it++;
        for(i=1;it!=l.end();it++,i++)
        {
            //printf(" %d",*it);
            if(i%10==0)
            {
                printf("\n%d",*it);
            } 
            else printf(" %d",*it);
        }
        printf("\n");
    }
    return 0;
}