单点时限: 2.0 sec
内存限制: 256 MB
给定一个存储了若干个以字符串表示的分数构成的单向链表。将链表按照节点中的分数值从小到大排序。
分数的格式为 分子 / 分母
($-10^8 \le$ 分子 $\le 10^8$, $1 <$ 分母 $\le 10^8$),分母为 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 行:整数 $T$ ($1 \le T \le 10$) 为问题数。
第 2∽T+1 行:每一个问题一行数据(输入数据的意义不在这里描述)。
对于每个问题,输出一行问题的编号(0 开始编号,格式:case #0:
等),然后在一行中输出相关数据(输出数据的意义不在这里描述)。
3 2 2 1 5 15 -3/6 5/2 -6/12 -2 4 1/2 2/4 -1/2 -2/4
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;
}