荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: selahx (宿醉未散,早梦半醒), 信区: ACMICPC
标  题: 如何得到输入数据
发信站: 荔园晨风BBS站 (2005年04月23日12:59:00 星期六), 站内信件

  做题的第一步是什么?当然是读懂题。
  第二步呢?那就是得到输入数据了。
  如果在输入数据这一块就不过关,就更谈不上写一手漂亮的程序了。
  这里,我把我得到输入数据的经验与大家分享,希望能对大家有所帮助。

  一、如何处理多组测试数据?

  这恐怕是大家问得最多的问题了。我看到很多同学是先把所有的测试数据读到一个数
组中,再一组一组地处理。这样做有个问题:如果测试数据很多,那么用于保存测试数据
的数组将会很大,极易超出内存限制。实际上,很多题的测试数据不少于100K。
  其实,我们完全没有必要将每组测试数据都保存下来,因为每组测试数据之间是独立
的,互不影响的。一般而言,我们应该读一组测试数据就处理一组,输出这组测试数据的
结果后再读下一组。
  可能有同学会担心一个问题,我在处理这组测试数据的时候,后面的测试数据会不会
趁这个机会“跑掉”呢?答案当然是不会,因为测试数据是以流(Stream)方式输入你的程
序的,未读入的测试数据会一直保留,除非你的程序退出或用了输入函数(scanf,cin等
等……)来接收它们。
  例子:
  测试数据是这样的,第一个数代表测试数据的组数,后面每一行是一组测试数据,这
里为了简单,每组测试数据就是一个数:
3
1
2
3
  读入程序就是这样:
int n, number, i;
scanf("%d", &n);
for (i = 0; i < n; i++)
{
    scanf("%d", &number);
// 下面是对number的处理并输出当前number所产生的结果
}

  二、如何处理“end of file”

  很多题的输入数据并不会告诉你有多少组测试数据或有多少个数,而是说测试数据以
“end of file”结束。遇到这类的输入数据怎么办呢?这里我以scanf为例来告诉大家我
的做法。
  大家可能很少关心scanf函数的返回值是什么,甚至有人以为scanf是void型的。关于
scanf的返回值,MSDN里是这样写的:
Both scanf and wscanf return the number of fields successfully converted and a
ssigned; the return value does not include fields that were read but not assig
ned. A return value of 0 indicates that no fields were assigned. The return va
lue is EOF for an error or if the end-of-file character or the end-of-string c
haracter is encountered in the first attempt to read a character.
  什么意思?就是这样:
  如:
scanf("%d%d", &a, &b);
  如果a和b都被成功读入,那么scanf的返回值就是2,如果只有a被成功读入,返回值为
1,如果a和b都未被成功读入,返回值为0,如果遇到错误或遇到end of file,返回值为
EOF。于是,我们只需要判断scanf的返回值是否等于EOF,就可以判断是不是到了
end of file了。我的习惯是判断scanf的返回值是不是等于变量的个数,对于上面的情
况,我判断的就是(scanf("%d%d", &a, &b) == 2),如果成立,表示还未到end of file。
  例子:
  测试数据为每行一个字符串,以end of file表示输入数据的结束:
abc
def
  输入程序是这样:
char strInput[1000];
while (scanf("%s", strInput) == 1)
{
// 对strInput的处理并输入该strInput产生的结果
}

  三、如何输入字符串
  在C/C++中,说到字符串,很多人想到指针的概率比想到数组的概率要大得多。
  不过,在接收输入时,用数组比用指针要好很多,因为数组比指针更安全,而且不用
考虑内存管理。
  对字符串的输入分三种情况:

  1、每个字符串中不含空格、制表符及回车

  这种情况,用scanf("%s"是再好不过的了,比如,测试数据中只有两个字符串:
abc def
  要读入abc与def,可以这样写:
char str1[1000], str2[1000];
scanf("%s%s", str1, str2);
  数组可以开大一些,没有关系。

  2、字符串中含有空格、制表符,但不含回车

  对于这种情况,scanf("%s"就无能为力了,因为scanf用空格、制表符及回车作为字符
串的分界符。对于一个含有空格、制表符及回车的字符串,如果用scanf("%s来读,将读到
若干个字符串,因为这个字符串被scanf分开了。
  我们只好采用另外一个函数了,那就是gets。gets函数用回车作为字符串的分
界符,比如,有以下的一个字符串:
Hello world!
  要读入这个字符串,这样写:
char str[1000];
gets(str);
  这样,str的内容就是"Hello world!"了。另外,gets返回NULL表示出错或
end of file。

  3、字符串中含回车

  最复杂的情况,因为在这种情况下,如果没有题目的说明,程序无法知道哪里是字
符串的分界。那么,用scanf("%c来读吧,一边读,一边判断分界条件是否满足,如果满
足,则把当前读到的东西存到一个字符串中。

  四、如何输入数组

  看到数组,你第一反应是什么?
  动规?搜索?谢谢!
  一般而言,输入数据中应该包含对数组的线度的描述(比如,一维数组的长度,二维
数组的长、宽,三维数组的长、宽、高),当然,也有一些比较变态的题,只告诉你一行
就是一个一维数组,让你自己判断元素个数,这种情况我在后面讨论。
  输入数组的方法很规范,那就是把scanf放到循环里面去。比如,有下面的测试数据,
第一行为数组的行数、列数,后面按行给出数组的元素:
3 2
1 2
3 4
5 6
  输入程序就是:
int nRow, nCol;
int i, j;
int a[100][100];
scanf("%d%d", &nRow, &nCol);
for (i = 0; i < nRow; i++)
{
    for (j = 0; j < nCol; j++)
        scanf("%d", &a[i][j]);
}
  输入的时候要注意数组是按行给出的还是按列给出的,比如,上面的例子,如果数组
是按列给出的,那么就应该是这样:
1 3 5
2 4 6
  输入程序就应该是:
for (j = 0; j < nCol; j++)
{
    for (i = 0; i < nRow; i++)
        scanf("%d", &a[i][j]);
}

  五、不定长数组的输入

  这里主要讨论不定长一维数组的情况,多维数组的情况一般是不会出现的,因为太恐
怖了。
  例如,有这样的测试数据,每行是一个一维数组:
1 2 3
1 2 3 4
  从输入数据里,我们无法得知每行究竟有几个数。
  对于这种情况,一般做法是,先用gets函数把一行读到字符串中,再处理这个字符
串。以前我的做法是用strtok函数来解析这个字符串,后面Kernel教给我们一种高深的
方法,这样写:
char str[100], *p;
int number[100], n, i;
while (gets(str) != NULL)
{
    p = str;
    i = 0;
    while (sscanf(p, "%d%n", &number[i], &n) == 1)
    {
        p += n;
        i++;
    }

    ...

}
  你知道scanf还可以用%n吗?

--


※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.64.1]
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 210.39.3.80]


[回到开始] [上一篇][下一篇]

荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店