程序设计能力实训

1052. 分数链表排序

单点时限: 2.0 sec

内存限制: 256 MB

给定一个存储了若干个以字符串表示的分数构成的单向链表。将链表按照节点中的分数值从小到大排序。

分数的格式为 分子 / 分母 分子 , 分母 ),分母为 1 时的格式退化为 分子(即:分母不出现)。

当两个分数值相等时,分子小的那个数排在前面。

例如:

结构体类型 NODE 表示一个单向链表的节点定义。定义函数 SortRationalList, 返回排序后链表的头指针。

// ********** Definition of the structure **********

typedef struct Node {
    char value[100]; // 以字符串形式存贮的分数
    struct Node *next;
} NODE;

//****** Specification of SortRationalList ******

NODE *SortRationalList(NODE *h);

/* PreCondition:
 h is a head pointer of a linked-list
 PostCondition:
 return the head pointer of the sorted linked-list
*/

输入格式

第 1 行:整数 () 为问题数。

第 2∽T+1 行:每一个问题一行数据(输入数据的意义不在这里描述)。

输出格式

对于每个问题,输出一行问题的编号(0 开始编号,格式:case #0: 等),然后在一行中输出相关数据(输出数据的意义不在这里描述)。

样例

Input
3
2 2 1
5 15 -3/6 5/2 -6/12 -2
4 1/2 2/4 -1/2 -2/4
Output
case #0:
 1 2
case #1:
 -2 -6/12 -3/6 5/2 15
case #2:
 -2/4 -1/2 1/2 2/4

提示

typedef struct Node {
    char value[100]; //以字符串形式存贮的分数
    struct Node *next;
} NODE;

/*/////////////////////////////////////////////////////*/

NODE *SortRationalList(NODE *h)
/* PreCondition:
h is a head pointer of a linked-list
PostCondition:
return the head pointer of the sorted linked-list
*/
{ //TODO: your definition
}
/*/////////////////////////////////////////////////////*/
/***************************************************************/
/*                                                             */
/*  DON'T MODIFY following code anyway!                        */
/*                                                             */
/***************************************************************/
#include <stdio.h>
#include <malloc.h>

static unsigned long next = 1;

int RND() {
    next = next * 1103515245 + 12345;
    return (unsigned) (next / 65536) % 32768;
}

void SETSEED(unsigned seed) { next = seed; }

void GENNUMBER(char *p, int len, int x) {
    int v;
    do v = RND() % 10; while (v == 0);
    if (x && RND() % 10) *p++ = '-';
    while (len--) {
        *p++ = v + '0';
        v = RND() % 10;
    }
    *p = 0;
}

void GENRATIONAL(char *p, int s) {
    int sign = RND() % 4, len1 = RND() % 8 + 1, len2 = RND() % 8 + 1;
    char s2[10];
    GENNUMBER(p, len1, 1);
    GENNUMBER(s2, len2, 0);
    if (sign && s2[0] - '1' && s2[1]) strcat(p, "/"), strcat(p, s2);
}

void solve() {
    int i, s;
    NODE *h = 0, *p;
    scanf("%d", &s);
    if (s < 10)
        for (i = 0; i < s; i++) {
            p = (NODE *) malloc(sizeof(NODE));
            scanf("%s", p->value);
            p->next = h;
            h = p;
        }
    else
        for (SETSEED(s <<= 1), i = 0; i < s; i++) {
            p = (NODE *) malloc(sizeof(NODE));
            GENRATIONAL(p->value, s);
            p->next = h;
            h = p;
        }
    h = SortRationalList(h);
    while (h) {
        p = h;
        h = h->next;
        printf(" %s", p->value);
        free(p);
    }
    printf("\n");
}

int main() {
    int i, t;
    scanf("%d\n", &t);
    for (i = 0; i < t; i++) {
        printf("case #%d:\n", i);
        solve();
    }
    return 0;
}
不限期开放

题目列表