# 程序设计能力实训

1051. 分数链表排序

// ********** 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
*/


### 样例

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;
}