c - how to read last n lines from a file in C

Question

Its a microsoft interview question.

Read last n lines of file using C (precisely)

Well there could be so many ways to achieve this , few of them could be :

-> Simplest of all, in first pass , count the number of lines in the file and in second pass display the last n lines.

-> Or may be maintain a doubly linked-list for every line and display the last n lines by back traversing the linkedlist till nth last node.

-> Implement something of sort tail -n fname

-> In order to optimize it more we can have double pointer with length as n and every line stored dynamically in a round robin fashion till we reach the end of file.

for example if there are 10 lines in file and want to read last 3 lines. then we could create a array of buffer as buf[3][] and at run time would keep on mallocing and freeing the buffer in circular way till we reach the last line and keep a counter to know the current index of array.

Can anyone please help me with more optimized solution or atleast guide me if any of the above approaches can help me get the correct answer or any other popular approach/method for such kind of questions.

Answer 1

您可以使用队列并存储在此队列中看到的最后 n 行。当您看到 eof 时，只需打印队列。

另一种方法是从文件末尾到开头读取一个 1024 字节的块。当您找到n \n字符并打印出最后几行时停止n。

Answer 2

您可以有两个最初指向文件开头的文件指针。

继续递增第一个指针，直到找到'\n'字符也存储文件指针的实例，当它找到'\n'。

一旦找到第 (n+1) 个“\n”，将我们之前保存的文件指针的第一个存储实例分配给第二个文件指针。继续这样做直到 EOF。

因此，当第一个文件指针位于 EOF 上时，第二个将位于 n '\n' 后面。然后将第二个文件指针中的所有字符打印到 EOF。

所以这是一个可以单次打印文件中最后 n 行的解决方案。

Answer 3

如何使用内存映射文件并向后扫描文件？如果行恰好比您的缓冲区空间长，这消除了每次更新缓冲区窗口的繁重工作。然后，当您找到 a 时\n，将该位置推入堆栈。这适用于O(L)其中 L 是要输出的字符数。所以没有什么比这更好的了不是吗？