Cracking the coding interview--Q13.1

February 10, 2013
作者:Hawstein
出处:http://hawstein.com/posts/13.1.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

Write a method to print the last K lines of an input file using C++.

译文:

用C++写一个函数,打印输入文件的最后k行。

解答

一种方法是打开文件两次,第一次计算文件的行数N,第二次打开文件,跳过N-K行, 然后开始输出。如果文件很大,这种方法的时间开销会非常大。

我们希望可以只打开文件一次,就可以输出文件中的最后k行。 我们可以开一个大小为k的字符串数组,然后将文件中的每一行循环读入。 怎么样循环读入呢?就是将k行字符串保存到字符串数组后, 在读第k+1时,将它保存到数组的第1个元素,依次类推。这样一来, 实际上文件中第i行的字符串会被保存到数组的第i%k的位置。最后当文件读完时, 数组保存的就是最后k行的字符串。当然了,它的开始位置不是0,而是i%k。

代码如下:

#include <iostream>
#include <fstream>
using namespace std;

void printLastKLines(ifstream &fin, int k){
    string line[k];
    int lines = 0;
    string tmp;
    while(getline(fin, tmp)){
        line[lines%k] = tmp;
        ++lines;
    }
    int start, cnt;
    if(lines < k){
        start = 0;
        cnt = lines;
    }
    else{
        start = lines%k;
        cnt = k;
    }
    for(int i=0; i<cnt; ++i)
        cout<<line[(start+i)%k]<<endl;
}
int main(){
    ifstream fin("13.1.in");
    int k = 4;
    printLastKLines(fin, k);
    fin.close();
    return 0;
}

注意上面函数中的while循环,不能写成下面的样子:

while(!fin.eof()){
	getline(fin, line[lines%k]);
	++lines;
}

eof()函数是在fin中已经没有内容可输入时,才被置为true。 如果使用上面的循环,getline在读入最后一行后,由于这一行仍然是有内容的, 所以eof()返回的仍然为false,表示还没到文件结尾。然后会再进入循环一次, 这时getline读入一个空串,已经没有内容可输入,eof()返回true而退出循环。 结果就是因为多读入一个空串,line数组中保存的是最后k-1行再加一个空串, 两个字:错误。如果我们将循环改成printLastKLines中的样子,那就没问题了。

最后说一句:珍爱生命,远离EOF

参考资料

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview